vLLM Mastery — From Zero to Maintainer

A deep, lab-driven journey through the internals of the world's most popular open-source LLM inference engine.

This is not a tutorial. It is a 20-phase apprenticeship. If you start at Phase 0 knowing nothing about how language models run, and you finish every lab, you will be able to:

• Read and modify any part of the vLLM codebase — the scheduler, the KV-cache manager, attention backends, quantization, speculative decoding, distributed execution.
• Land real pull requests upstream and reason about them like a maintainer.
• Operate as a principal / staff LLM-inference engineer — design serving systems, debug throughput cliffs, and make the architectural calls that decide whether a model serves 10 or 10,000 users per GPU.
• Found or join a startup in the inference space and know exactly where the moats are.

Everything you need is in this repository. You will never need an outside book.

Contents

• The two things that make this work
  • 1. You read the real engine
  • 2. You build a small engine
• How each phase is structured
  • Lab hardware tags
• The curriculum (20 phases)
• Recommended path

The two things that make this work

1. You read the real engine

Every concept is anchored to the actual vLLM source code, frozen at a single commit (see UPSTREAM_PIN.md: v0.22.1 @ 0decac0). When a phase says

vllm/v1/core/block_pool.py:333 — BlockPool.get_new_blocks()

that line really exists in ./upstream/ and you are expected to open it. We do not paraphrase the engine. We quote it and explain it line by line.

⚠️ vLLM moves fast (dozens of merged PRs per day). Line numbers are valid only at the pinned commit. The named class/function is always given so you can re-find it in any version. Re-create the exact tree with the command in UPSTREAM_PIN.md.

2. You build a small engine

Reading is not understanding. So in parallel you build mini_vllm/ — a deliberately small, dependency-light reimplementation of vLLM's core ideas that runs on a laptop CPU, no GPU required. By the end you will have written, with your own hands:

• a paged KV-cache block allocator (Phase 2),
• a continuous-batching scheduler with prefix caching (Phase 3),
• a sampler, an n-gram speculative decoder, a batched-LoRA matmul, a grammar mask, …

The real engine teaches you what production looks like. The mini engine teaches you why every decision was made. You need both. This is the "Both" anchoring this course is built on.

How each phase is structured

Every phase-NN-*/ folder has the same shape:

Lab hardware tags

Not everyone has a GPU. Every lab is tagged:

• [CPU-OK] — runs anywhere, including the CI on your laptop. Most labs.
• [GPU-OPT] — better on a GPU but has a CPU fallback; expected GPU output is captured in the README so you can follow along without one.
• [GPU-REQ] — genuinely needs an NVIDIA GPU (real CUDA kernels). The README includes captured output and a step-by-step so you learn even if you only rent a GPU later.

See SETUP.md for environment setup and cheap cloud-GPU options.

The curriculum (20 phases)

⭐ = the original flagship phases that set the template. Every phase now has fully written labs — 60+ in total, each with an in-depth guide-style README, and (for the CPU labs) a tested starter.py / solution.py / test_lab.py triplet. Run the whole suite with pytest -m "not gpu" from the repo root; every phase's labs/README.md gives the recommended order and the skills each lab delivers.

Recommended path

1. Do them in order, 0 → 19. Each builds on the last; mini_vllm/ grows phase by phase.
2. For each phase: read 00-guide.md → read 01-deep-dive.md with upstream/ open in a second window → do 02-mini-build.md → run the labs → attempt EXERCISES.md → self-test with INTERVIEW.md.
3. Run the tests constantly: pytest -m "not gpu" from the repo root.
4. Keep a lab notebook. When you finish, your notebook + mini_vllm/ + a merged upstream PR is your portfolio.

Start here: SETUP.md, then phase-00-foundations/00-guide.md.

See also: GLOSSARY.md (every term defined once) and CAREER.md (the maintainer path, the staff competency map, the startup playbook).

This repo also builds as a website (mdBook → Cloudflare Pages): see PUBLISHING.md.

Setup

This course is designed so that the majority of labs run on a laptop CPU. You only need a GPU for the labs explicitly tagged [GPU-REQ] (and even those ship captured output so you can learn without one).

Contents

• 1. Python environment
• 2. Get the real vLLM source (required for the deep-dives)
• 3. (Optional) Install the real engine for the GPU labs
• 4. Running the labs and tests
• 5. Cheap GPU access for the [GPU-REQ] labs
• 6. Models used in labs
• Troubleshooting

1. Python environment

We follow vLLM's own convention and use uv (fast, and it's what upstream uses — see upstream/AGENTS.md). Plain venv works too.

# Install uv (one time)
curl -LsSf https://astral.sh/uv/install.sh | sh

# From the repo root:
uv venv --python 3.12
source .venv/bin/activate

# Install the CPU-only course dependencies (numpy + pytest). This is all you need
# for mini_vllm and every [CPU-OK] lab.
uv pip install -e .

To run the torch-based labs (some Phase 2/4 mini-builds), add the CPU build of torch:

uv pip install -e ".[torch]"   # CPU wheels are fine; no CUDA needed for mini_vllm

2. Get the real vLLM source (required for the deep-dives)

Every 01-deep-dive.md cites upstream/... paths. Clone the pinned tree:

git clone --depth 1 --branch v0.22.1 \
  https://github.com/vllm-project/vllm.git upstream
cd upstream && git rev-parse HEAD   # 0decac0d96c42b49572498019f0a0e3600f50398
cd ..

You do not need to install vLLM to read its source. (upstream/ is gitignored.)

3. (Optional) Install the real engine for the GPU labs

The real vllm package needs a CUDA build of torch and an NVIDIA GPU. Install it only on a GPU box:

uv pip install -e ".[vllm]"   # vllm==0.22.1, matches the pin

4. Running the labs and tests

# All CPU tests (mini_vllm + flagship labs). Run this constantly.
pytest -m "not gpu"

# Just one phase's labs
pytest phase-02-paged-attention/labs

# The mini engine's own test suite
pytest mini_vllm

# On a GPU box, also run the GPU-tagged tests
pytest -m gpu

GPU tests are auto-skipped when no CUDA device is present (see the gpu_device fixture in each phase's conftest.py), so pytest is always green on a laptop.

5. Cheap GPU access for the [GPU-REQ] labs

You do not need to own a GPU. Options, cheapest-effort first:

A T4 or L4 (16–24 GB) runs every GPU lab in this course with a small model (e.g. facebook/opt-125m, Qwen/Qwen2.5-0.5B). You will never need an 80 GB card to learn.

6. Models used in labs

Labs default to tiny models so they download fast and fit small GPUs (and some run on CPU): facebook/opt-125m, Qwen/Qwen2.5-0.5B-Instruct, TinyLlama/TinyLlama-1.1B. Each lab README names the exact model and the huggingface-cli download command.

Troubleshooting

• pytest collects 0 tests → run from the repo root (so pyproject.toml is found).
• import vllm fails on a laptop → expected; the real engine needs CUDA. Use the [CPU-OK] labs and mini_vllm on a laptop; the captured outputs cover the rest.
• Line numbers in a deep-dive don't match → you're not at the pinned commit. Re-clone per step 2, or search for the named function instead of trusting the line number.

Upstream Pin

Every "original code reference" in this curriculum is anchored to a single, frozen snapshot of the real vLLM source tree so that path:line citations stay reproducible even as upstream moves on.

Contents

• Re-create the exact tree
• How citations are written
• Why pin at all?
• Bumping the pin (later)

Re-create the exact tree

git clone --depth 1 --branch v0.22.1 https://github.com/vllm-project/vllm.git upstream
cd upstream && git rev-parse HEAD   # must print 0decac0d96c42b49572498019f0a0e3600f50398

How citations are written

Throughout the phases you will see references like:

vllm/v1/core/sched/scheduler.py:312 @ 0decac0 — Scheduler.schedule()

• The path is relative to upstream/.
• The line number is valid only at the pinned SHA. If you check out a newer vLLM, open the file and search for the named symbol (the function/class is given) instead of trusting the line number.
• @ 0decac0 is the short SHA, a reminder that the snapshot is frozen.

Why pin at all?

vLLM merges dozens of PRs per day. A line number that is correct today is wrong next week. Pinning is the same discipline real maintainers use when they write design docs and bug reports: always cite a commit, never "main". When you eventually contribute upstream (Phase 19), you will cite commits in exactly this way in your PR descriptions and issue reports.

Bumping the pin (later)

When you want to refresh the curriculum against a newer vLLM:

1. Re-clone at the new tag, update the table above.
2. Re-run the path:line spot-check in each phase's 01-deep-dive.md.
3. Note behavioral changes in a CHANGES.md per phase — diffing how the engine evolved is itself one of the most instructive exercises in this whole course.

Glossary

Every term used in this course, defined once, in plain language. When a phase uses a term, it links here. If you ever feel lost, this is the place to land.

Ordering is roughly conceptual, grouped by theme, not alphabetical — read top to bottom the first time, then use Ctrl-F.

Contents

• The model and the forward pass
• Attention and the KV cache
• PagedAttention & memory (Phase 2)
• Scheduling & batching (Phase 3)
• Kernels & execution (Phases 4–7)
• Decoding strategies (Phases 8–9)
• Distributed & serving (Phases 10, 15–16)
• Adaptation & structure (Phases 11–12)
• vLLM internals & process model

The model and the forward pass

• Token — a chunk of text (often ~¾ of a word) that the model reads and writes. Text is turned into a list of integer token IDs by a tokenizer.
• Embedding — the vector the model uses to represent a token internally.
• Forward pass — running the model once over some tokens to produce, for the last position, a probability distribution over the next token (the logits).
• Logits — the raw, pre-softmax scores over the whole vocabulary for "what comes next".
• Autoregressive generation — generate one token, append it to the input, run the forward pass again, repeat. LLMs generate text one token at a time this way.
• Decoder-only model — the architecture of GPT/Llama/Qwen: a stack of transformer blocks that only attend to earlier tokens (causal). Most LLMs.

Attention and the KV cache

• Attention — the operation where each token "looks at" previous tokens and mixes in their information. For each token it computes a Query (Q), and compares it against the Key (K) and Value (V) of every earlier token.
• KV cache — because earlier tokens don't change, their K and V vectors can be computed once and cached. The KV cache is the stored K and V for every token generated so far. It is the single biggest consumer of GPU memory during serving. This course is largely the story of managing it well.
• Prefill — the first forward pass over the whole prompt at once. Compute-bound (lots of tokens, one pass). Fills the KV cache for the prompt.
• Decode — each subsequent single-token forward pass. Memory-bandwidth-bound (one token, must read all weights + the whole KV cache). This is where most serving time goes.
• TTFT (time to first token) — latency from request arrival to the first output token. Dominated by prefill.
• ITL / TPOT (inter-token latency / time per output token) — time between successive output tokens. Dominated by decode.

PagedAttention & memory (Phase 2)

• PagedAttention — vLLM's core idea: store the KV cache in fixed-size blocks (like OS memory pages) instead of one big contiguous buffer per request. Eliminates fragmentation and enables sharing.
• Block (KV block) — a fixed-size slot holding the KV of block_size tokens (commonly 16). The unit of KV allocation. Code: KVCacheBlock in kv_cache_utils.py.
• Block size — number of tokens whose KV fits in one block (e.g. 16).
• Block table — per-request mapping from logical block index → physical block ID. Lets a request's KV be scattered across non-contiguous physical blocks.
• Block pool — the global pool of all physical blocks, with a free list and a prefix-cache index. Code: BlockPool in block_pool.py.
• Fragmentation — wasted memory from reserving contiguous space you don't fully use. PagedAttention's reason for existing.
• Prefix caching — if two requests share a prefix (same leading tokens), they can share the same physical KV blocks. Found by hashing block contents. Phase 3.
• Copy-on-write (CoW) — when a shared block must diverge (one request writes new tokens), copy it so the other request's view is unaffected.
• Reference count (ref_cnt) — how many requests currently use a block. A block is free only when ref_cnt == 0.
• Eviction — reclaiming a cached (but currently unused) block for a new allocation. vLLM uses an LRU-ish free queue (FreeKVCacheBlockQueue).

Scheduling & batching (Phase 3)

• Batching — running many requests through the model together to use the GPU efficiently.
• Static batching — fix a batch, run it to completion. Wasteful: fast requests wait for slow ones.
• Continuous batching — re-decide the batch every iteration (every single token step). Finished requests leave, new ones join immediately. vLLM's default.
• Scheduler — the component that, each step, picks which requests run and how many tokens each gets. Code: Scheduler in v1/core/sched/scheduler.py.
• Chunked prefill — split a long prompt's prefill across several steps so it doesn't starve ongoing decodes. Controlled by a token budget.
• Token budget — max_num_batched_tokens: the cap on total tokens scheduled per step.
• Preemption — when memory runs out, evict a running request's KV and put it back in the queue (to be recomputed later). The safety valve.
• Running / Waiting queues — requests currently decoding vs. requests waiting to start.

Kernels & execution (Phases 4–7)

• Kernel — a function that runs on the GPU. "Attention kernel", "GEMM kernel", etc.
• GEMM — General Matrix-Matrix Multiply. The workhorse op (every linear layer). Libraries: cuBLAS, CUTLASS.
• FlashAttention — a fused, memory-efficient attention kernel that never materializes the full attention matrix. FlashInfer / FlashMLA / TRTLLM-GEN / Triton — other attention/ GEMM kernel providers vLLM can dispatch to.
• Attention backend — vLLM's pluggable wrapper choosing which attention kernel to run.
• CUDA graph — a recorded sequence of GPU operations replayed with one launch, removing per-op CPU launch overhead. Piecewise = capture parts; full = capture the whole model forward.
• torch.compile — PyTorch's compiler; vLLM uses it to fuse ops and generate kernels, with custom graph passes.
• MoE (Mixture of Experts) — a layer with many "expert" sub-networks; each token is routed to a few experts. Big models, low active compute. (Mixtral, DeepSeek-V3.)
• Quantization — storing weights/activations in fewer bits (FP8, INT4, …) to save memory and bandwidth. Formats: FP8, MXFP4, NVFP4, INT8/INT4, GPTQ, AWQ, GGUF, compressed-tensors.

Decoding strategies (Phases 8–9)

• Greedy decoding — always pick the highest-probability token.
• Temperature / top-k / top-p / min-p — knobs that shape the sampling distribution.
• Parallel sampling (n) — produce N independent completions for one prompt (sharing the prompt's KV via prefix caching).
• Beam search — keep the top-N partial sequences by cumulative probability.
• Logits processor — a hook that edits the logits before sampling (penalties, bans, grammar masks).
• Speculative decoding — a cheap draft model/heuristic proposes several tokens; the big model verifies them in one pass, accepting a prefix. Speeds up decode.
• EAGLE / Medusa / n-gram / suffix / DFlash — specific speculative-decoding methods.
• Acceptance rate — fraction of drafted tokens the target model accepts. The metric that decides whether spec decode is a win.

Distributed & serving (Phases 10, 15–16)

• Tensor parallelism (TP) — split each layer's weights across GPUs; every GPU does part of every layer; results all-reduced.
• Pipeline parallelism (PP) — split the layers across GPUs; activations pass GPU→GPU.
• Data parallelism (DP) — replicate the model; split requests across replicas.
• Expert parallelism (EP) — split MoE experts across GPUs.
• Context parallelism (CP) — split a single sequence's context across GPUs.
• Collective op — multi-GPU communication primitive (all-reduce, all-gather, …) via NCCL.
• Disaggregated serving — run prefill and decode on different machines, shipping the KV cache between them, so each can be scaled and tuned independently.
• KV connector — the component that transfers KV blocks between engines (for P/D disagg or offloading). Code under vllm/distributed/kv_transfer/.
• OpenAI-compatible server — vLLM's HTTP server speaking the OpenAI API (plus Anthropic Messages API and gRPC).
• Tool calling / reasoning parser — components that extract structured tool calls or chain-of-thought from model output.

Adaptation & structure (Phases 11–12)

• LoRA (Low-Rank Adaptation) — small trainable matrices added to a frozen base model to specialize it. vLLM serves many LoRAs in one batch.
• Punica / SGMV — batched kernels that apply different LoRAs to different requests in one GPU call.
• Structured output / guided decoding — forcing the model's output to match a grammar, regex, or JSON schema by masking invalid tokens each step. Engines: xgrammar, guidance.

vLLM internals & process model

• V1 engine — vLLM's current core architecture (the vllm/v1/ tree). V0 is legacy. This course teaches V1.
• LLM — the offline (batch) Python entry point: LLM(model=...).generate(prompts).
• AsyncLLM — the async engine powering the API server.
• EngineCore — the inner loop: add_request → step() (schedule → execute → output).
• Worker / Executor — the executor owns workers; each worker drives one GPU's model.
• Model runner — turns a SchedulerOutput into actual tensor inputs and runs the model.
• SamplingParams — per-request decoding config (temperature, max_tokens, n, …).
• RequestOutput — what the engine returns: generated text/tokens for a request.

The Career Map: Maintainer, Staff Engineer, Founder

This course has three end-states in mind. They overlap, but each has its own "what does great look like" bar. Use this document as a compass: at any phase, ask "which of these am I building toward right now?"

Contents

• Track A — Become a vLLM maintainer
  • The ladder
  • What maintainers actually do (and this course trains)
  • The non-obvious advice
• Track B — Staff / Principal LLM-inference engineer
  • The competency map
  • How to use the INTERVIEW.md files
  • Your portfolio
• Track C — Found a startup in inference
  • Where the value (and the moats) are
  • Honest take on moats
  • The build/buy/contribute calculus
• A note on mindset

Track A — Become a vLLM maintainer

A maintainer is someone whose judgment the project trusts. You get there by a track record, not a title.

The ladder

1. First contribution. A docs fix, a small bug, a test. Learn the workflow (Phase 19).
2. Sustained contributions. Real features/fixes in one area (say, the scheduler or a quant method). You become "the person who knows X".
3. Reviewer. You review others' PRs in your area credibly.
4. Committer / maintainer. You're trusted to merge and to shape direction.

What maintainers actually do (and this course trains)

• Read code fast and correctly. Every 01-deep-dive.md is reps for this.
• Reason about invariants. "Block tables are append-only." "ref_cnt==0 ⟺ in free queue." Maintainers hold dozens of these in their head. The deep-dives name them explicitly; the CHEATSHEET.md files collect them.
• Protect the hot path. vLLM's scheduler runs every token step for every request — a Python list scan in the wrong place is a throughput regression. You learn to feel this.
• Write tests that pin behavior. Look at upstream/tests/v1/core/ — that's the standard.
• Communicate. PR descriptions, RFCs, issue triage. See upstream/AGENTS.md for the project's literal rules (e.g. no pure code-agent PRs, cite that AI was used, include test commands and results).

The non-obvious advice

• Specialize, then generalize. Pick one subsystem from this course (scheduler, KV cache, a quant format, an attention backend) and go deeper than anyone. Depth in one area earns the trust that lets you touch others.
• Watch the firehose. Subscribe to the repo. Read merged PRs in your area daily. Diffing how the engine evolves (Phase 19) is the fastest way to learn the current mental model.

Track B — Staff / Principal LLM-inference engineer

This is the industry role: you own how models serve — throughput, latency, cost, reliability — at a company. The interview loops test exactly the material in this course.

The competency map

How to use the INTERVIEW.md files

Each phase ships staff-level Q&A. Treat them as a mock loop: cover the answer, attempt it out loud, then compare. The flagship phases (2, 3) show the depth expected. A strong candidate can whiteboard the PagedAttention block allocator and the continuous-batching step loop from memory — which, after this course, you will have written yourself in mini_vllm/.

Your portfolio

By the end you have three artifacts that beat any résumé bullet:

1. mini_vllm/ — a working engine you built. Walk an interviewer through it.
2. A merged upstream PR (Phase 19). Public proof you operate at the real bar.
3. A tuning/benchmark writeup (Phase 18). Shows you think in numbers.

Track C — Found a startup in inference

The inference layer is one of the most valuable and contested in the AI stack. This course makes you dangerous in it.

Where the value (and the moats) are

• Cost per token. The whole game. Everything in Phases 2–7 and 10 is a lever on it. A 2× throughput win is a 2× gross-margin win.
• Latency SLAs. TTFT and ITL guarantees (Phases 3, 8, 9, 15) are what enterprise buyers actually pay for.
• Multi-tenancy. Serving thousands of fine-tunes cheaply = multi-LoRA + prefix caching (Phases 3, 11). A structural cost advantage over per-customer deployments.
• Hardware arbitrage. Running well on cheaper/available silicon (Phase 17) when NVIDIA is supply-constrained.

Honest take on moats

Raw "we wrap vLLM and rent GPUs" is not a moat — margins compress fast. Defensible angles:

• A genuine kernel/scheduling edge you can sustain (hard, but this course is where you'd build the expertise to try).
• Workload specialization — agentic/long-context/structured-output/RAG-shaped traffic has different optimal configs; owning a vertical's serving stack is defensible.
• The control plane — routing, autoscaling, multi-tenancy, observability, cost attribution around the engine. Often more durable than the engine itself.
• Distribution / switching costs — being embedded in customers' pipelines.

The build/buy/contribute calculus

You will almost always build on vLLM rather than replace it — that's the point of open source. The startup question is "what do we add on top, and what should we upstream?" Phase 19 covers the contribute-vs-keep-private tradeoff (upstreaming buys you maintenance leverage and credibility; hoarding a commodity feature buys you nothing).

A note on mindset

The people who reach all three end-states share one habit: they read the source. Not docs about the source — the source. This entire course is built to make that your default reflex. Open upstream/ now and keep it open for the next 20 phases.

Phase 00 — The Hitchhiker's Guide to How an LLM Actually Runs

Course home · Phase 01 →

This is Chapter 0 of the book. It assumes you know nothing — not what a token is, not what a matrix multiply is — and it ends with you able to compute, on a napkin, how many users a given GPU can serve and why. Everything else in the course stands on this chapter, so we go slowly and build each idea from the ground up.

How to read this chapter. Most of it is for everyone. Paragraphs marked

🔬 Going deeper — optional rigor and real numbers for the expert track.

can be skimmed on a first pass and devoured on the second. By the end you should be comfortable at both levels: the intuition and the arithmetic.

Contents

• 0.1 Don't Panic — the whole thing in one sentence
• 0.2 The only math you need (a 5-minute primer)
• 0.3 Words become numbers, part 1: tokenization
• 0.4 Words become numbers, part 2: embeddings (meaning as coordinates)
• 0.5 The shape of a model: layers and the residual stream
• 0.6 Attention from the ground up (the heart of the machine)
  • The problem attention solves
  • Q, K, V — the search analogy
  • A worked example (do this once by hand — it demystifies everything)
  • Causal masking — you can't read the future
  • Multiple heads
• 0.7 The MLP (the per-token "thinking" block)
• 0.8 From logits to a token: sampling
• 0.9 The generation loop, and the redundancy that births the KV cache
• 0.10 Prefill vs decode, and why decode is memory-bound (the chapter's crux)
  • Why decode is bottlenecked by memory speed, not math
• 0.11 How big is the KV cache? (the wall that caps your users)
• 0.12 Throughput vs latency, and Little's Law
• 0.13 The one picture to carry into every later phase
• 0.14 What you'll do in this phase

0.1 Don't Panic — the whole thing in one sentence

A large language model is a function that reads a list of words and guesses the next word. To write text, it guesses a word, sticks it on the end, and guesses again — hundreds of times.

That is genuinely all an LLM does at runtime. ChatGPT writing you an essay is this loop running a few hundred times. Everything difficult — and everything this course teaches — comes not from the guessing, but from doing the guessing fast, for thousands of people at once, on hardware that costs more than a house. vLLM is the software that does that well. To make it faster (your future job), you must first feel why it is slow. That feeling is what this chapter installs.

We'll build up in this order: a tiny bit of math → words become numbers → what one "guess" involves → the loop → why it's slow → where the memory goes. Take your time.

0.2 The only math you need (a 5-minute primer)

Two objects and one operation. That's it.

A vector is just a list of numbers: [0.2, -1.1, 0.5]. Picture it as an arrow, or as coordinates of a point. A length-3 vector is a point in 3D space; LLMs use points in thousands of dimensions (you can't picture that, and you don't need to — the arithmetic is the same).

A matrix is a grid of numbers — a stack of vectors. A 2×3 matrix has 2 rows, 3 columns.

The one operation that matters is matrix multiplication (everyone calls it "matmul" or GEMM — General Matrix Multiply). To multiply a vector by a matrix, you take dot products. A dot product of two equal-length vectors multiplies them element-wise and sums:

[1, 2, 3] · [4, 5, 6]  =  1·4 + 2·5 + 3·6  =  4 + 10 + 18  =  32

A dot product is a similarity score: it's large and positive when two vectors point the same way, near zero when they're unrelated, negative when opposed. Remember this — attention (the heart of the model) is built entirely out of dot products measuring "how related are these two tokens."

Multiplying a vector x (length 3) by a matrix W (3 columns, 2 rows) gives a new vector (length 2), one dot product per row of W:

x = [1, 2, 3]            W = [ [1, 0, 1],     →   y[0] = [1,2,3]·[1,0,1] = 4
                               [0, 1, 1] ]        y[1] = [1,2,3]·[0,1,1] = 5
                                                  y = [4, 5]

🔬 Going deeper. A neural network "layer" is exactly this: y = x·Wᵀ (plus a bias, plus a nonlinearity). The matrix W is the weights — the billions of numbers that are the trained model. "Llama-3-8B" means ~8 billion such numbers. A forward pass is a long chain of these multiplies. So "running a model" = "doing a lot of matmuls with the weight matrices." Hold that: it explains both the compute cost (FLOPs) and the memory cost (reading the weights), which is the whole performance story in §0.10.

That's the entire math prerequisite. Onward.

0.3 Words become numbers, part 1: tokenization

A computer can't multiply the word "Paris". So step one is always: chop the text into small pieces called tokens and replace each with an integer ID.

Why not just use whole words, or individual letters? Whole words give a gigantic, brittle vocabulary (every plural, typo, and rare name is a new word). Single letters make sequences painfully long. The sweet spot is subwords — common words stay whole, rare words split into pieces. The dominant algorithm is Byte-Pair Encoding (BPE):

🔬 How BPE is built (Going deeper). Start with every character as its own token. Then repeatedly find the most frequent adjacent pair of tokens in your training text and merge it into a new token. Do this tens of thousands of times. Common sequences like "ing", " the", "vLLM" get merged into single tokens; rare strings stay split into smaller bits. The result is a fixed list of merges (the vocabulary) that balances vocabulary size against sequence length.

A worked tokenization (Llama-3-style, ~128k vocab):

text:    "vLLM is fast"
tokens:  [ "v",  "LLM",  " is",  " fast" ]      ← note the leading spaces are part of tokens
IDs:     [  85,   4178,    382,    2347   ]      ← example numbers from the vocab table

Two facts to carry forward:

• A token is roughly ¾ of a word on average (so 1,000 tokens ≈ 750 words).
• The component that does this is the tokenizer; reversing it (IDs → text) at the end is detokenization. The full list of tokens it knows is the vocabulary (Llama-3: ~128,256).

In mini_vllm/tokenizer.py we use the simplest possible tokenizer — one byte = one token, vocab of 257 — so the course needs zero downloaded files. Open it; it's ten lines, and it has the same encode/decode interface a real tokenizer does.

🆕 New words: token (a subword chunk), token ID (its integer), tokenizer (the chopper), vocabulary (all known tokens), BPE (the merge algorithm), detokenization (IDs→text).

0.4 Words become numbers, part 2: embeddings (meaning as coordinates)

A token ID like 4178 is just a name — it carries no meaning by itself (token 4178 isn't "more" than token 382). So the model's first move is to look up each ID in a big table and replace it with a vector — a list of numbers — called an embedding.

Think of the embedding as coordinates in a space of meaning. Just as a city has a (latitude, longitude), a token has a few thousand coordinates (Llama-3-8B: 4096 of them). The training process arranges this space so that tokens used in similar ways land near each other, and — famously — directions in the space carry meaning:

embedding("king") - embedding("man") + embedding("woman")  ≈  embedding("queen")

The lookup itself is trivial — it's just "go to row 4178 of the embedding table" — but it's the bridge from symbols to math. After this step, the prompt is no longer text; it's a stack of vectors (one per token), and from here on the model only does matmuls on those vectors.

"vLLM is fast"
  → IDs [85, 4178, 382, 2347]
  → embeddings, a 4 × 4096 matrix:
      [ [ 0.02, -0.7, ... , 0.1 ],     ← "v"
        [-0.5,   0.3, ... , 0.9 ],     ← "LLM"
        [ 0.1,  -0.2, ... , 0.0 ],     ← " is"
        [ 0.8,   0.4, ... ,-0.3 ] ]    ← " fast"

🔬 Going deeper. The width of these vectors is the hidden size d_model (4096 for Llama-3-8B). Bigger d_model = more capacity but more compute and memory everywhere. The embedding table has vocab_size × d_model numbers (128256 × 4096 ≈ 525M just for embeddings). Many models tie the input embedding and the output projection (the "LM head") to save that memory.

🆕 New words: embedding (a token's meaning-vector), hidden size / d_model (the vector width), LM head (the final layer turning vectors back into vocabulary scores).

0.5 The shape of a model: layers and the residual stream

The model is a tall stack of identical layers (Llama-3-8B has 32). The stack of token vectors flows up through them; this flowing stack is often called the residual stream. Each layer reads the stream, computes an update, and adds it back (that "add it back" is the residual connection — it's why training deep stacks works, but you can treat it as plumbing).

Each layer does exactly two things to the stream:

1. Attention — lets each token look at the other tokens and pull in relevant information. This is the only place where information moves between positions.
2. MLP (feed-forward) — transforms each token's vector independently, adding "thinking capacity."

After all 32 layers, the final vector at the last position is multiplied by the LM head to produce one score for every token in the vocabulary. Those scores are the logits (§0.8).

embeddings ─► [ layer 1 ] ─► [ layer 2 ] ─► ... ─► [ layer 32 ] ─► LM head ─► logits (vocab,)
                 │ attention + MLP, each with a residual add

Keep this split in mind — attention mixes across tokens, the MLP works per token — because it explains exactly where the KV cache lives (in attention, the only cross-token part) and where the giant matmuls are (the MLP, ~⅔ of the weights; Phase 7).

0.6 Attention from the ground up (the heart of the machine)

This is the one piece worth understanding in detail, because it dictates all of memory management. We'll build it from the problem, then do a worked numeric example.

The problem attention solves

Consider generating the next word of: "The river bank was muddy, so the fisherman ...". To continue sensibly the model must know "bank" means a riverbank (not a money bank) — and the clue is the word "river" earlier. Each token needs to gather context from the other tokens. Attention is the mechanism for that gathering.

Q, K, V — the search analogy

For every token, the model computes three vectors (each by multiplying the token's embedding by a learned weight matrix — yes, more matmuls):

• Query (Q) — "here is what I'm looking for." (your search box)
• Key (K) — "here is what I am about." (a document's title/tags)
• Value (V) — "here is the information I actually carry." (the document's contents)

To update a token, you compare its Query against every earlier token's Key (dot products — remember, dot product = similarity!), turn those similarities into weights that sum to 1, and take the weighted blend of those tokens' Values. It is exactly a soft search:

Type a query → it's scored against the keys of all documents → you get back a blend of the best-matching documents' values.

A worked example (do this once by hand — it demystifies everything)

Three tokens, and to keep it readable let each Q/K/V be just 2 numbers (a real model uses 128). Suppose we're computing the new vector for token 3, whose query is q₃ = [1, 0]. The three tokens' keys and values:

token   key K        value V
  1     [1, 0]       [10, 0]
  2     [0, 1]       [0, 10]
  3     [1, 0]       [5, 5]

Step 1 — similarity scores (dot product of q₃ with each key):

score₁ = [1,0]·[1,0] = 1      score₂ = [1,0]·[0,1] = 0      score₃ = [1,0]·[1,0] = 1

Token 3's query points the same way as tokens 1 and 3's keys (score 1) and is orthogonal to token 2's (score 0).

Step 2 — scale by 1/√(head_dim) = 1/√2 ≈ 0.707 (this keeps numbers from blowing up as the vectors get wider — a numerical-stability trick):

scaled = [0.707, 0, 0.707]

Step 3 — softmax turns scores into weights that are all positive and sum to 1. Softmax of a list is exp(each) / sum(exp):

exp(0.707)=2.03,  exp(0)=1.00,  exp(0.707)=2.03    sum = 5.06
weights = [2.03/5.06, 1.00/5.06, 2.03/5.06] = [0.40, 0.20, 0.40]

So token 3 will pay 40% attention to token 1, 20% to token 2, 40% to itself.

Step 4 — weighted blend of the Values:

out = 0.40·[10,0] + 0.20·[0,10] + 0.40·[5,5]
    = [4,0]       + [0,2]       + [2,2]
    = [6, 4]

That [6, 4] is token 3's attention output — a context-aware mix dominated by tokens 1 and 3. That is the entire attention operation. Everything fancy later (FlashAttention, PagedAttention) is about computing this exact thing faster and with less memory, never something different.

Causal masking — you can't read the future

When generating, token 3 may only attend to tokens 1, 2, 3 — not tokens that come after it (they don't exist yet). This "only look backward" rule is causal masking: before the softmax, scores for future positions are set to -∞ (so their softmax weight is 0). Picture the allowed attention as a lower-triangular matrix:

       attends to →   t1   t2   t3   t4
   query t1            ✓    ✗    ✗    ✗
   query t2            ✓    ✓    ✗    ✗
   query t3            ✓    ✓    ✓    ✗
   query t4            ✓    ✓    ✓    ✓

This triangle is why token i needs the Keys and Values of all tokens ≤ i — the single most important sentence for understanding the KV cache (§0.9).

Multiple heads

Real attention runs several of these in parallel — heads — each with its own Q/K/V projections, so different heads can specialize (one tracks syntax, another long-range references). Their outputs are concatenated. Llama-3-8B has 32 query heads, each of dimension 128 (32 × 128 = 4096 = d_model).

🔬 Going deeper — three things the experts know.

• head_dim and the √d scale. Dot products of d-dimensional vectors grow like √d, which would push softmax into tiny-gradient saturation. Dividing by √head_dim keeps the variance ~1. (That's the 0.707 above.)
• RoPE (positional info). Attention as described is order-blind — it'd treat "dog bites man" like "man bites dog." Models inject position by rotating Q and K by an angle proportional to their position (Rotary Position Embedding). Two tokens' score then depends on their relative distance. You'll see rotary_emb(positions, q, k) in llama.py (Phase 0 deep-dive).
• GQA/MQA — fewer KV heads. The KV cache (next section) is sized by the number of KV heads. So modern models use Grouped-Query Attention: many query heads share a smaller number of KV heads. Llama-3-8B has 32 query heads but only 8 KV heads — a 4× KV-cache saving baked into the architecture. (MQA is the extreme: 1 KV head.) This single design choice changes your serving capacity by 4×; remember it for §0.11.

🆕 New words: Query/Key/Value (Q/K/V), attention score (a Q·K dot product), softmax (scores → weights summing to 1), causal mask (can't attend to the future), head (one parallel attention), head_dim (a head's width), RoPE (rotary positions), GQA/MQA (shared KV heads).

0.7 The MLP (the per-token "thinking" block)

After attention mixes context in, the MLP processes each token's vector on its own through two big matmuls with a nonlinearity between:

hidden = activation(x · W_upᵀ)        # expand: 4096 → ~14336  (Llama-3-8B)
out    = hidden · W_downᵀ             # project back: 14336 → 4096

The middle width (the "intermediate size") is several × d_model, which is why the MLP holds the majority of the model's weights (~⅔). When you hear "the model is mostly GEMMs," it's largely these two matrices per layer. (Modern Llamas use a gated variant, SwiGLU, with three matrices — a detail for Phase 14; the shape story is the same.)

The takeaway for performance: attention is where memory (the KV cache) concentrates; the MLP is where compute and weight bytes concentrate. Different bottlenecks, different optimizations.

0.8 From logits to a token: sampling

After the last layer, the LM head turns the final vector into logits — one raw score per vocab token (~128k numbers). To pick a token you first turn logits into probabilities with softmax, then choose:

"The capital of France is"  → logits → softmax → probabilities:
   " Paris": 0.87    " Lyon": 0.06    " a": 0.01    " banana": 0.000003   ...

• Greedy: take the highest-probability token (" Paris"). Deterministic.
• Temperature / top-k / top-p: deliberately introduce randomness for variety.

This whole topic — the decoding algorithms and how they run vectorized across a whole batch — is Phase 9. For now: logits → softmax → pick one. mini_vllm/sampler.py implements greedy plus temperature/top-k/top-p in ~40 readable lines.

🆕 New words: logits (raw next-token scores), probability distribution (softmaxed logits), greedy decoding (argmax), sampling (random pick).

0.9 The generation loop, and the redundancy that births the KV cache

The model only ever predicts one next token. To write a sentence we loop — feed the output back in (this is autoregressive generation):

Step 1:  "The capital of France is"            → " Paris"
Step 2:  "The capital of France is Paris"       → "."
Step 3:  "The capital of France is Paris."      → <end>

Now look closely at what the naive loop computes. Each step runs the whole model over the whole text-so-far. Recall from §0.6 that attention at each position needs the Keys and Values of all earlier positions. So:

Step 1 processes tokens [1..5]      → computes K,V for positions 1..5
Step 2 processes tokens [1..6]      → computes K,V for positions 1..6   (1..5 AGAIN)
Step 3 processes tokens [1..7]      → computes K,V for positions 1..7   (1..6 AGAIN)

We keep recomputing the K and V of tokens we already processed. Here is the key insight:

A token's Key and Value never change once computed. Token 5's K and V are identical in step 2 and in step 500. So compute them once and store them.

That stored table of every past token's Keys and Values is the KV cache. With it, each new step computes K,V for only the one new token and reads the rest from the cache:

work WITHOUT a cache:  1 + 2 + 3 + ... + N  =  N(N+1)/2  ≈  N²/2     (quadratic)
work WITH    a cache:  1 + 1 + 1 + ... + 1  =  N                     (linear)

For a 1,000-token answer that's ~500× less of this work. You will measure exactly this in lab-01 — a 20-line experiment that is the single justification for the entire course. The KV cache is not an optimization you can skip; it's what makes generation tractable.

The catch — and the reason Phases 2–3 exist — is that the KV cache is enormous and grows with every token, and it lives in scarce GPU memory. Managing it well is most of vLLM.

🆕 New words: autoregressive generation (predict → append → repeat), KV cache (stored Keys/Values of all prior tokens), EOS token (the "stop" token).

0.10 Prefill vs decode, and why decode is memory-bound (the chapter's crux)

With a KV cache, generation splits into two phases with opposite performance personalities. This is the most-probed idea in LLM-inference interviews — we'll do it with real numbers.

• Prefill — the first run: process the entire prompt at once to fill its KV cache. Many tokens, one run.
• Decode — every run after: generate one token, append, repeat. One token, one run, many times.

Why decode is bottlenecked by memory speed, not math

To produce one decode token, the GPU must read every weight in the model out of its main memory (HBM) — plus the whole KV cache — and then does only one token's worth of math with all of it. It's like driving to a vast warehouse, loading every crate onto the truck, to deliver one postcard. The bottleneck is the loading (memory reads), not the delivering (math).

🔬 The arithmetic that proves it (Going deeper — this is the money slide). Take Llama-3-8B in bf16 (2 bytes/param), on an A100 (HBM bandwidth ≈ 2 TB/s, compute ≈ 312 TFLOP/s bf16).

• Memory per decode step (batch = 1): read all weights = 8e9 params × 2 bytes = 16 GB. Time to read at 2 TB/s = 16e9 / 2e12 = 8 ms. That alone caps you at 1/0.008 ≈ 125 tokens/sec — no matter how fast the math is.
• Compute per decode step: a forward pass costs ≈ 2 × params FLOPs per token = 2 × 8e9 = 16 GFLOP. At 312 TFLOP/s that's 16e9 / 312e12 ≈ 0.05 ms.
• Verdict: memory (8 ms) dwarfs compute (0.05 ms) by ~160×. Decode is utterly memory-bound at batch 1. The expensive math units sit ~99% idle, waiting for weights to arrive.

Arithmetic intensity makes this crisp: it's FLOPs ÷ bytes-read. Decode at batch 1 ≈ 16 GFLOP / 16 GB = 1 FLOP/byte. The A100's "ridge point" (where it flips from memory- to compute-bound) is 312e12 / 2e12 ≈ 156 FLOP/byte. Since 1 ≪ 156, we're deep in memory-bound territory. This is the roofline model in one number.

The escape: batching. If you decode B sequences together, you still read the weights only once but do B× the math → intensity ≈ B FLOP/byte. To reach the ridge (≈156) and use the GPU fully, you need batch ~150. That's why throughput serving is all about big batches — and why the scheduler (Phase 3) exists. Prefill already has high intensity (many tokens × one weight read) → it's compute-bound from the start, which is why a long prompt can hog the GPU and must be chunked (Phase 3).

This one section explains nearly every optimization ahead:

• Batching (Phase 3): amortize the weight read over many sequences → throughput.
• Quantization (Phase 6): make the weights fewer bytes → less to read → faster decode.
• CUDA graphs (Phase 5): when per-step math is tiny, even the CPU overhead of launching the work dominates → remove it.
• Speculative decoding (Phase 8): do useful work for several tokens per weight-read.

🆕 New words: prefill / decode, TTFT / ITL(TPOT), HBM (the GPU's main memory), compute-bound / memory-bandwidth-bound, arithmetic intensity (FLOPs/byte), roofline (the model that says which bound you're under), ridge point (the FLOP/byte where it flips).

🔬 The GPU memory hierarchy (expert aside). A GPU has tiers: tiny ultra-fast registers and SRAM/shared memory (KB–MB, ~TB/s within a core) on-chip, and big slow HBM (tens of GB, ~1–3 TB/s) off-chip. "Memory-bound" means bound by HBM. FlashAttention (Phase 4) is fast precisely because it keeps attention's intermediates in SRAM and avoids round-tripping the giant score matrix to HBM. Keep this hierarchy in mind whenever a kernel is "memory-bound" — it's usually HBM traffic.

0.11 How big is the KV cache? (the wall that caps your users)

Decode is memory-bound, and the KV cache is the other big thing in that memory. Let's size it, one line at a time.

For every token, in every layer, we store a Key vector and a Value vector. So:

bytes_per_token = 2                  (one K + one V)
                × num_layers          (32)
                × num_kv_heads        (8   ← GQA! not 32 — see §0.6)
                × head_dim            (128)
                × bytes_per_number    (2 for bf16)

For Llama-3-8B:

2 × 32 × 8 × 128 × 2  =  131,072 bytes  ≈  128 KB   per token

So a 2,000-token conversation = 2000 × 128 KB ≈ 256 MB of GPU memory — for one user. The punchline: a 24 GB GPU, after ~16 GB for the weights, has ~8 GB for KV. At 256 MB/user that's about 30 conversations at once before you run out of memory.

This is the headline of the entire field. What caps how many people you can serve is usually memory, not compute. The KV cache fills the GPU long before the math units are busy. So the serving game is fitting more KV cache: by not wasting any (PagedAttention, Phase 2), by sharing it across requests (prefix caching, Phase 3), and by shrinking it (FP8 KV cache, Phase 6 — halving bytes_per_number doubles your users).

🔬 Going deeper — scale it to 70B and feel the squeeze. Llama-3-70B: 80 layers, 8 KV heads, head_dim 128 → 2×80×8×128×2 = 327,680 B ≈ 320 KB/token. At 8k context that's 2.6 GB per sequence. On an 80 GB A100, after ~140 GB of weights (wait — 70B in bf16 is 140 GB, so it doesn't even fit on one 80 GB GPU!). This is why 70B requires tensor parallelism across multiple GPUs (Phase 10) and why people quantize (Phase 6): both the weights and the KV cache are fighting for memory. You'll compute these numbers yourself in lab-02.

When you later see vLLM log Maximum concurrency for 2048 tokens: 68.65x, you'll know it's this exact division: free-HBM ÷ per-sequence-KV. That number is your serving capacity.

0.12 Throughput vs latency, and Little's Law

Two metrics, in tension, that you'll trade off for the rest of your career:

• Latency — how fast one request feels (TTFT, ITL). What an individual user cares about.
• Throughput — total tokens/sec across everyone. What sets your cost per token — the number a business lives or dies on.

They fight: bigger batches raise throughput (amortized weight reads, §0.10) but slow each individual request (more work per step). The scheduler (Phase 3) steers this; Phase 18 is the art of tuning it.

🔬 Little's Law (Going deeper). For any stable serving system: concurrency = throughput × latency. If each request stays in the system for L seconds and you sustain X requests/sec, then on average N = X·L requests are in flight. Rearranged: to hit a target throughput at a given latency, you need a certain concurrency — and that concurrency must fit in KV memory (§0.11). This little equation ties together the whole stack: memory limits concurrency, concurrency (via Little's Law) limits the throughput you can reach at your latency SLA. You'll use it to size real deployments in Phase 18.

🆕 New words: latency, throughput, cost per token, Little's Law (N = X·L), SLA (the latency you've promised customers).

0.13 The one picture to carry into every later phase

Strip away the words and the engine reduces to this: a request is a list of tokens with two counters racing.

  ┌────────────────────────────────────────────────────────────────────┐
  │  A request = tokens + two counters:                                 │
  │     num_tokens          = how many tokens exist (prompt + generated) │
  │     num_computed_tokens = how many have been processed (KV cached)   │
  │                                                                     │
  │  PREFILL : computed is far behind  → catch up in one big run         │
  │  DECODE  : computed is one behind  → compute one more, append, repeat│
  │                                                                     │
  │  The engine's entire job: make `computed` catch up to `tokens`,     │
  │  as cheaply as possible, for thousands of requests at once.         │
  └────────────────────────────────────────────────────────────────────┘

This is literally how vLLM's Request object is built (vllm/v1/request.py) and how its scheduler reasons (Phase 3); mini_vllm/request.py mirrors it. If you remember one diagram from the whole course, make it this one — every later phase is "do one part of this loop better."

0.14 What you'll do in this phase

• Read: 01-deep-dive.md — find every concept above (Q/K/V, the cache, the two counters) in a real model file and in vLLM's EngineCore.step.
• Build / measure: 02-mini-build.md — understand mini_vllm's tokenizer, toy model, and sampler, and run the two experiments below.
• Labs (see labs/README.md for the full guide to each):
  • lab-01-kv-cache-speedup [CPU-OK] — implement generation with and without a KV cache and measure the O(N²) → O(N) win. The motivating experiment of the course.
  • lab-02-kv-memory-calculator [CPU-OK] — write the memory formula and compute how many users fit on a real GPU (8B and 70B). See the memory wall for yourself.
  • lab-03-sampling-basics [CPU-OK] — build greedy/temperature/top-k/top-p from scratch and prove your sampler agrees token-for-token with mini_vllm's.
  • lab-04-prefill-vs-decode [CPU-OK] — the roofline arithmetic: the ridge point, the 0.6% compute utilization of single-stream decode, the 125 tok/s speed limit, the critical batch size.
• Test yourself: EXERCISES.md, INTERVIEW.md, CHEATSHEET.md.

You're ready for the rest of the book when you can, from memory: walk the attention worked example; explain why decode is memory-bound using arithmetic intensity; derive the KV-cache size for a model; and estimate how many users a GPU can serve. Those four are the foundation everything else is built on.

Course home · Phase 01 →

Phase 00 — Deep Dive: a real forward pass and the request counters

Paths relative to upstream/ at v0.22.1 @ 0decac0. You don't need to understand every line of a model — you need to recognize the shapes from the guide (Q/K/V, the KV cache, the prefill/decode counters) in real code. That recognition is what lets you navigate any model file later (Phase 14).

Contents

• 1. A real decoder-only model: Llama
  • The decoder layer forward (LlamaDecoderLayer.forward, :316)
  • Where K and V are produced and cached (LlamaAttention.forward, :223)
• 2. The two counters that run the whole engine
• 3. The loop that drives it all: EngineCore.step
• Reading checklist

1. A real decoder-only model: Llama

Open vllm/model_executor/models/llama.py. The structure is a Russian doll:

• LlamaModel (:350) — holds the embedding + a stack of LlamaDecoderLayers + a final norm.
• LlamaDecoderLayer (:253) — one transformer block: self_attn then mlp, each with a residual add and an RMSNorm.
• LlamaAttention (:124) — the attention block.
• LlamaMLP (: the small class with forward(self, x) at :117) — gate/up/down projections.

The decoder layer forward (LlamaDecoderLayer.forward, :316)

Skim it and find this shape (paraphrased):

# residual stream in -> norm -> attention -> add -> norm -> mlp -> add -> out
hidden = self.input_layernorm(hidden_states)
hidden = self.self_attn(positions, hidden)      # attention mixes across tokens
hidden = residual + hidden
hidden = self.post_attention_layernorm(hidden)
hidden = self.mlp(hidden)                        # per-token transform
hidden = residual + hidden

That's the whole transformer block. 32 of these stacked = Llama-3-8B. Notice attention is the only place tokens interact; the MLP treats each token independently. That's why attention is where the KV cache (cross-token memory) lives, and the MLP is just big GEMMs (Phase 7).

Where K and V are produced and cached (LlamaAttention.forward, :223)

This is the payoff. Find (paraphrased):

qkv, _ = self.qkv_proj(hidden_states)            # one matmul produces Q, K, V (fused)
q, k, v = qkv.split([self.q_size, self.kv_size, self.kv_size], dim=-1)
q, k = self.rotary_emb(positions, q, k)          # positional info (RoPE)
attn_output = self.attn(q, k, v)                 # <- the Attention layer (Phase 4)
output, _ = self.o_proj(attn_output)

The self.attn call is a vllm.attention.layer.Attention module — and that is what writes the new k, v into the paged KV cache (Phase 2) and reads back the cached K/V to compute attention (Phase 4). So the journey is: model produces Q/K/V → the Attention layer caches K/V in blocks and runs the attention kernel. Everything you'll learn in Phases 2 and 4 plugs in right here, at this one self.attn(q, k, v) call. Hold that thread.

Don't get lost. You will not understand all of llama.py today, and you don't need to. The point is to locate Q/K/V production and the self.attn call. That's the seam where the engine's memory and kernels meet the model.

2. The two counters that run the whole engine

Open vllm/v1/request.py. The Request class (:59) carries the prompt, the generated tokens, and the sampling params. The two properties that matter most:

@property
def num_tokens(self) -> int:           # :239
    # total tokens that exist: prompt + generated so far
    ...

and the field set in __init__ (:145): self.num_computed_tokens = 0 — how many of those tokens have had their KV computed and cached.

The whole engine is the race between these two numbers (guide §"mental model"):

• New request: num_computed_tokens = 0, num_tokens = len(prompt). The gap is the whole prompt → prefill.
• After prefill + each decode: num_computed_tokens is one behind num_tokens; generating a token bumps num_tokens, then the next step computes one more → decode.

num_tokens_with_spec (:243) adds speculative draft tokens to the gap — which is how spec decode (Phase 8) rides the same machinery with no special case. RequestStatus (:315) is the lifecycle enum (WAITING/RUNNING/PREEMPTED/FINISHED_*) you met in Phase 3.

mini_vllm/request.py is a faithful miniature: same num_computed_tokens vs num_tokens, same status enum, same is_finished = status >= FINISHED ordering trick.

3. The loop that drives it all: EngineCore.step

Open vllm/v1/engine/core.py:428. This is the heartbeat of vLLM:

def step(self) -> tuple[dict[int, EngineCoreOutputs], bool]:
    if not self.scheduler.has_requests():
        return {}, False
    scheduler_output = self.scheduler.schedule()                       # Phase 3: who runs
    future = self.model_executor.execute_model(scheduler_output, ...)  # the forward pass
    grammar_output = self.scheduler.get_grammar_bitmask(scheduler_output)  # Phase 12
    model_output = future.result()
    if model_output is None:
        model_output = self.model_executor.sample_tokens(grammar_output)   # Phase 9
    engine_core_outputs = self.scheduler.update_from_output(           # advance counters
        scheduler_output, model_output)
    return engine_core_outputs, scheduler_output.total_num_scheduled_tokens > 0

schedule → execute → sample → update. That's it. That's the engine. Every phase in this course is a deep dive into one box of this five-line loop:

• schedule() → Phases 2, 3 (memory + batching)
• execute_model() → Phases 4–7, 10, 13, 14 (kernels, quant, parallelism, the model itself)
• sample_tokens() → Phases 8, 9, 12 (decoding, spec, structured output)
• update_from_output() → Phase 3 (advance num_computed_tokens, reap finished)

mini_vllm/engine.py's step() is the same loop with the GPU filed off — read them side by side and the correspondence is exact.

Reading checklist

One sentence each:

• In LlamaAttention.forward, which line produces Q/K/V and which line caches/uses K/V?
• Why does the MLP not need a KV cache but attention does?
• On Request, what's the difference between num_tokens and num_computed_tokens?
• In EngineCore.step, name the four stages and which course phase owns each.

Now build it: 02-mini-build.md, then the labs.

Phase 00 — Mini-Build: feel the KV-cache win

This phase doesn't add a new mini_vllm module — it has you understand the three you already have and measure the foundational result the whole course rests on.

Contents

• Part A — read the three pieces of "next-token prediction"
• Part B — the lab: O(N²) vs O(N)
• Definition of done
• Map to the real engine

Part A — read the three pieces of "next-token prediction"

Open and read (they're tiny):

• mini_vllm/tokenizer.py — encode(str) -> list[int], decode(list[int]) -> str. Same interface as a real HF tokenizer.
• mini_vllm/model.py — ToyModel.forward(last_tokens, positions) -> logits. Batched, autoregressive, deterministic. (It ignores KV values — honest simplification noted in the file — because this course cares about KV memory management, not the toy's numerics.)
• mini_vllm/sampler.py — Sampler.sample(logits, params) -> token_id. Greedy at temperature 0.

Trace one LLMEngine.generate(["hi"]) call in your head: tokenize → loop step() → sample → detokenize. Confirm it matches EngineCore.step from the deep-dive.

Part B — the lab: O(N²) vs O(N)

lab-01-kv-cache-speedup is the build. You implement a toy attention twice:

1. No cache: every step recomputes K/V for all prior tokens → work grows with the prefix.
2. Cached: K/V computed once, reused → constant work per step.

You'll count "K/V computations" and show the no-cache version does 1+2+...+N = O(N²) while the cached version does O(N) — and that both produce the identical token sequence (caching is an optimization, never a correctness change — the same invariant you'll prove for chunked prefill and preemption in Phase 3).

lab-02-kv-memory-calculator has you write the kv_bytes_per_token formula and compute how many concurrent sequences fit on a given GPU — the number that caps your serving capacity.

Definition of done

pytest phase-00-foundations/labs -q

Then answer in your notebook:

• What is the asymptotic work ratio (no-cache / cached) for generating N tokens? (≈ N/2.)
• For Llama-3-8B at 8k context on a 24 GB GPU (say 16 GB weights), roughly how many concurrent full-length sequences fit? (You'll compute it in lab-02 — the answer is "surprisingly few," which is the entire motivation for Phase 2.)

Map to the real engine

Phase 00 Labs — Foundations

Four labs that install the four facts everything else stands on: generation is autoregressive and caching makes it linear (lab-01), the cache is memory and memory is the binding constraint (lab-02), logits become tokens through a small exact algorithm (lab-03), and prefill and decode live in opposite performance regimes (lab-04). No GPU, no model downloads — counters, formulas, and numpy. Do them in order; each ends where the next begins.

Every lab follows the standard contract: starter.py with TODOs (your work), solution.py (the reference), test_lab.py (the spec, executable). The default test run uses solution.py so the suite is always green; set LAB_IMPL=starter to grade yourself.

# Whole phase:
pytest phase-00-foundations/labs -m "not gpu"

# Grade your own work on one lab:
LAB_IMPL=starter pytest phase-00-foundations/labs/lab-01-kv-cache-speedup -q

Contents

• lab-01-kv-cache-speedup [CPU-OK]
• lab-02-kv-memory-calculator [CPU-OK]
• lab-03-sampling-basics [CPU-OK]
• lab-04-prefill-vs-decode [CPU-OK]
• What you can do after this phase

Labs

lab-01-kv-cache-speedup [CPU-OK]

The experiment that motivates the course: implement generation with and without a KV cache, count the work exactly (95 vs 15 units; >100× by n=1000), and prove both produce identical tokens. The O(N²) → O(N) trade that converts compute into memory — and creates the prefill/decode split as a side effect. Skills: why the cache exists; causality makes K/V cacheable; counting beats clocking; the master "optimization changes nothing" invariant.

lab-02-kv-memory-calculator [CPU-OK]

Write the three-line formula behind every capacity decision in LLM serving and apply it to Llama-3-8B: 128 KiB per token, 256 MiB per sequence, ~32 concurrent users on a 24 GiB GPU. Then read FP8-KV and GQA as factors of the formula. Memory, not compute, is the constraint — derived, not asserted. Skills: back-of-envelope capacity planning; the formula as an optimization roadmap; weights are rent, KV is traffic.

lab-03-sampling-basics [CPU-OK]

Build the sampler: greedy, temperature, top-k, top-p — with the stability clause (softmax max-subtraction), the inclusive nucleus boundary, and seeded reproducibility. The final test proves your sampler agrees token-for-token with mini_vllm's engine sampler across 15 configurations. Skills: the four knobs as exact algorithms; −∞ masking; why greedy mode anchors every deterministic test in this course.

lab-04-prefill-vs-decode [CPU-OK]

Six one-line functions and an A100 spec sheet: the ridge point (156 FLOPs/byte), single-stream decode at 0.6% compute utilization, the 125 tok/s physical speed limit for 8B/fp16, and the critical batch size where decode becomes compute-bound. The roofline worldview that sorts every optimization into "helps my regime" or "doesn't." Skills: compute-bound vs memory-bound as a reflex; the intensity cancellation (model size doesn't matter — tokens per weight-trip does); why batching is free money and quantization is a decode feature.

What you can do after this phase

Derive, on a whiteboard with no notes: why every inference engine caches KV (and what it costs in bytes); how many users fit on a given GPU for a given model (and which knob to turn when the answer is too small); what temperature=0.7, top_p=0.9 actually computes; and whether a proposed optimization can possibly help a given workload (which side of the ridge is it on?). These four reflexes are the entrance exam for Phase 1, where the loop you simulated becomes a real engine with a scheduler, and for every phase after it.

Lab 00-01 — The KV-Cache Speedup [CPU-OK]

This is the experiment that motivates the entire course — and arguably the entire field of LLM inference engineering. You will implement autoregressive generation twice: once the naive way (recompute attention's keys and values for the whole sequence, every step) and once with a KV cache (compute each token's K/V exactly once, ever). Same model, same output, and a work difference that grows with the square of the sequence length. By the end you'll have measured, with an exact integer counter you control, why every serving engine on earth is built around a cache — and why the rest of this course is about managing that cache.

Contents

• Why this lab exists
• Background: what K and V are, and why they're recomputable
• Files
• Run
• What to implement
• What you should see — and why every number is what it is
• What the tests prove
• Hitchhiker's notes
• Going further
• References

Why this lab exists

Ask a newcomer why LLM inference is expensive and they'll say "big matrices." True, but it misses the structural problem: generation is autoregressive. The model emits one token, appends it, and runs again on the longer sequence — N tokens of output means N forward passes. If each pass reprocesses everything before it, total work is 1+2+3+…+N ≈ N²/2 token-computations for N tokens of value. Quadratic. A 10k-token answer would cost ~50 million token-computations to produce 10 thousand tokens.

The KV cache is the observation that almost all of that recomputation is byte-identical every time — and the field's entire architecture flows downstream of caching it. Once you store K/V, generation becomes O(N)… and a new problem is born: that cache is state, it lives in scarce GPU memory, it grows every step, and somebody has to manage it. That somebody is vLLM, and managing-the-cache-well is Phases 1–19. This lab is where you earn the premise.

We measure with a counter, not a stopwatch, on purpose. Wall-clock on a laptop is noisy and proves nothing about asymptotics; an exact work count (one unit per token processed) gives you the formula, and formulas transfer to any hardware. You'll meet this counting-over-clocking style again in Phase 3's labs.

Background: what K and V are, and why they're recomputable

In attention, each token's hidden state is projected three ways: a query (what am I looking for?), a key (what can I be found by?), and a value (what do I contribute when found?). When the model processes token t, its query is dotted against the keys of all previous tokens, and the resulting weights blend their values:

attn(t) = softmax(q_t · [k_0 … k_t]ᵀ / √d) · [v_0 … v_t]

The crucial property is causality: k_i and v_i depend only on tokens 0..i. Token 5's key is the same whether the sequence currently has 6 tokens or 6,000. So once computed, (k_i, v_i) is valid forever — it's a pure function of the prefix, which makes it perfectly cacheable. The query is the only part that's fresh each step (it belongs to the new token), which is why we cache K and V but never Q.

That's the whole trick. "KV cache" sounds like infrastructure; it's actually a one-line theorem about causal attention plus the decision to spend memory on it.

Files

• starter.py — implement generate_no_cache and generate_with_cache. The work meter (compute_kv / KVWork) and the deterministic next_token are provided. Your work.
• solution.py — reference.
• test_lab.py — pins identical outputs, the exact quadratic and linear work formulas, and the growing ratio.

Run

LAB_IMPL=starter pytest phase-00-foundations/labs/lab-01-kv-cache-speedup -q
pytest phase-00-foundations/labs/lab-01-kv-cache-speedup -q   # reference (default)

What to implement

Both functions generate n_new tokens from a prompt of length P and return (full_token_sequence, total_kv_work):

• generate_no_cache — each decode step first calls compute_kv(tok, pos) for every token currently in the sequence (the model "re-reads" everything), then appends next_token(tokens). Step i (0-indexed) costs P + i units.
• generate_with_cache — prefill once (compute_kv per prompt token, P units), then each decode step computes K/V for only the newly appended token (1 unit).

next_token is deterministic — a hash of the context — so both implementations must produce the same token sequence. That's not a convenience; it's the point (see the first test).

What you should see — and why every number is what it is

For P = 5, n_new = 10:

no cache : work = 5+6+7+8+9+10+11+12+13+14 = 95      (sum of P..P+n_new-1 → O(N²))
cached   : work = 5 + 10                   = 15      (P prefill + 1/step   → O(N))

• Why 95? Step 0 reprocesses the 5 prompt tokens; step 1 reprocesses 6 (prompt + the token just generated); … step 9 reprocesses 14. The arithmetic series is the quadratic, made concrete enough to check by hand — which is exactly what the test does.
• Why 15? Each of the 15 tokens that ever exists has its K/V computed exactly once. The cached cost is the number of tokens. It cannot be beaten by any scheme that actually computes the KV (it can be beaten by schemes that reuse KV across requests — that's prefix caching, Phase 2/3).
• At n_new = 1000: the ratio is >100× and still climbing linearly (~N/2). On real hardware this asymptotic gap is the difference between "chatbots are economically possible" and not.
• Notice the two-phase shape that fell out for free: a big batch of K/V work up front (the prefill — all P prompt tokens at once, parallelizable, compute-hungry), then a drip of single-token steps (the decode — serial, one unit each). You didn't design that; caching created it. Prefill-vs-decode is the most consequential workload split in inference (lab-04 quantifies it; Phase 1 traces it; Phase 3 schedules around it), and it is born right here, in your 20 lines.

What the tests prove

Hitchhiker's notes

• The cache is a time–space trade, and the space is the plot of this course. You just converted O(N²) compute into O(N) memory: every token now permanently occupies bytes (about 128 KiB/token for Llama-3-8B — lab-02 computes this). One number to foreshadow: a 24 GiB GPU holds weights plus only a few dozen full-length sequences of cache. Scarcity is immediate, and scarcity is why Phases 2–3 exist.
• Real transformers hide the no-cache cost inside one matmul. HuggingFace generate(use_cache=False) doesn't loop per token like your simulation; it reprocesses the whole sequence in a single (big) forward pass per step. The work is still quadratic in total — your counter models the FLOPs faithfully even though the loop structure differs.
• Where the cache actually lives upstream: vllm.attention.layer.Attention writes each step's new K/V into the paged cache (via slot_mapping — Phase 2 lab-06), and the kernel reads all prior K/V (via block_table). What you modeled as a counter is, in production, tensors + an allocator + a scheduler. Same theorem underneath.
• Why does the cached version call next_token(tokens) with the full list, then? Because the model function still needs the whole context semantically — the cache changes what is recomputed, not what the model "knows." In a real model, "the cache was consulted" and "the context was read" are the same act: attention over cached K/V. Don't confuse caching KV with truncating context.

Going further

• Plot work_no_cache / work_cached for n in 1..2000 — confirm the ~N/2 line. Then plot cached work alone: a flat 1/step. That flat line is why decode latency is stable and why per-token pricing is linear. Economics from asymptotics.
• Model prompt length: sweep P from 10 to 10,000 at fixed n_new=100. Notice prefill dominates total cached work for long prompts — the TTFT story (Phase 1) in miniature.
• Add a kv_bytes counter alongside the work counter (one cache entry per compute_kv) and watch memory grow linearly while compute stays flat — you've now built both axes of lab-02 and the motivating tension of Phase 2 with ~5 extra lines.

References

• Vaswani et al., Attention Is All You Need (2017) — where K/Q/V come from: https://arxiv.org/abs/1706.03762
• kipply, Transformer Inference Arithmetic — the canonical blog walkthrough of KV-cache math and why decode is bandwidth-bound: https://kipp.ly/transformer-inference-arithmetic/
• Pope et al., Efficiently Scaling Transformer Inference (2022) — §3 formalizes the prefill/decode split your counter just exposed: https://arxiv.org/abs/2211.05102
• upstream/vllm/attention/layer.py — the production home of the cache write.
• Phase 0 guide §"the KV cache" (00-guide.md) — the intuition this lab makes quantitative.

Lab 00-02 — KV-Cache Memory Calculator [CPU-OK]

Lab-01 ended with a cliffhanger: the KV cache converts quadratic compute into linear memory. This lab computes exactly how much memory — and the answer is the most important number in LLM serving economics: how many concurrent users fit on one GPU. You'll write the three-line formula, apply it to Llama-3-8B, and arrive at the genuinely shocking result that a 24 GiB GPU running an 8B model has room for only ~32 full-length conversations. Every dollar of inference cost, every "maximum concurrency" log line, and the entire existence of PagedAttention trace back to the arithmetic you're about to own.

Contents

• Why this lab exists
• Background: where the bytes go
• Files
• Run
• The formulas
• The headline result, walked through
• What the tests prove
• Hitchhiker's notes
• Going further
• References

Why this lab exists

This is back-of-envelope as a professional skill. A staff inference engineer gets asked, weekly, some variant of: "can we serve model X to Y users on hardware Z?" The wrong answer costs a fleet; the right answer is three multiplications you can do in a meeting. This lab installs the formula so deeply that you'll never again look at a GPU spec sheet without mentally dividing its HBM by a KV footprint.

It's also the Rosetta stone for the rest of the course. When Phase 2 lab-03's real engine prints Maximum concurrency for 2,048 tokens per request: 68.65x, that's this lab's max_concurrent_seqs evaluated against measured free HBM. When Phase 6 sells you FP8 KV, when model cards advertise GQA, when Phase 10 shards KV across GPUs — every one of those is an attack on a term of the formula you write here. Learn the formula, and the whole optimization landscape organizes itself into "which factor does this shrink?"

Background: where the bytes go

Per token, per layer, attention stores one K vector and one V vector, each of num_kv_heads × head_dim elements. Multiply it out:

kv_bytes_per_token = 2 × num_layers × num_kv_heads × head_dim × dtype_bytes
                     ▲       ▲             ▲            ▲           ▲
                  K and V  every layer   the heads   per head   fp16 = 2

Two things to notice before you code:

• num_kv_heads, not num_heads. Modern models use grouped-query attention (GQA): many query heads share each KV head precisely because someone did this lab's math and realized KV memory, not model quality, capped serving capacity. Llama-3-8B has 32 query heads but only 8 KV heads — a 4× KV saving designed into the architecture. (MQA — one KV head — is the extreme; MLA in DeepSeek compresses further still. Architecture evolution is visible in this one parameter.)
• It's per token, forever. The cache for token 0 lives until the request finishes. Length × concurrency × per-token bytes must fit in what's left after weights. There is no amortization, no compression by default — just bytes, held for the lifetime of the conversation.

Files

• starter.py — implement kv_bytes_per_token, kv_bytes_per_seq, max_concurrent_seqs. Your work.
• solution.py — reference.
• test_lab.py — pins exact numbers for Llama-3-8B, the FP8 and GQA factor effects, and the no-room edge case.

Run

LAB_IMPL=starter pytest phase-00-foundations/labs/lab-02-kv-memory-calculator -q
pytest phase-00-foundations/labs/lab-02-kv-memory-calculator -q   # reference (default)

The formulas

kv_bytes_per_token = 2 (K and V) × num_layers × num_kv_heads × head_dim × dtype_bytes
kv_bytes_per_seq   = kv_bytes_per_token × seq_len
max_concurrent     = (gpu_bytes − weight_bytes) // kv_bytes_per_seq      (0 if no room)

Integer division on purpose: you cannot serve 0.7 of a conversation. (The real engine has the same floor, expressed in blocks — Phase 2.)

The headline result, walked through

Llama-3-8B in fp16: num_layers=32, num_kv_heads=8, head_dim=128, dtype_bytes=2.

per token : 2 × 32 × 8 × 128 × 2 = 131,072 B = 128 KiB        (!)
per 2,048-token sequence: 128 KiB × 2,048 = 256 MiB
24 GiB GPU − ~16 GiB weights = 8 GiB free
concurrency: 8 GiB / 256 MiB = 32 sequences

Sit with each line:

• 128 KiB per token. A token is ~4 characters of text. Its cache costs as much as a small image. A 100-word answer: ~17 MB. This is why "just keep the conversation in memory" is a capacity strategy, not a triviality.
• 256 MiB per max-length sequence — 1.6% of the entire weights per conversation, for context alone.
• 32 users. An 8-billion-parameter model on a serious GPU and the ceiling is thirty two — and that's assuming perfect packing with zero waste. Now recall (or preview) Phase 2 lab-02: pre-vLLM engines wasted 60–80% of KV memory on fragmentation, turning 32 into ~6–12. Memory, not compute, is the binding constraint of LLM serving — the single most counterintuitive fact in the field, and you just derived it.
• And the punchline that launches Phase 2: since the constraint is memory, the highest- leverage engineering target is making every byte of that 8 GiB hold useful KV. That is, verbatim, PagedAttention's mission statement.

What the tests prove

Hitchhiker's notes

• The formula is the optimization roadmap. Every KV-memory technique in production attacks one factor: FP8/INT4 KV quantization → dtype_bytes; GQA/MQA/MLA → num_kv_heads × head_dim; sliding-window attention (Mistral) and hybrid SSM layers (Phase 14) → which layers store KV at all; tensor parallelism (Phase 10) → divides the whole thing across GPUs; prefix caching (Phases 2–3) → shares kv_bytes_per_seq across requests. When you read a new inference paper, your first question is now: which factor?
• Weights are the entry fee; KV is the rent. Weights are fixed and amortize over every request; KV scales with traffic. This is why bigger GPUs disproportionately help serving (more leftover after the fixed cost) and why a 70B model on an 80 GiB GPU (~140 GiB fp16 weights — doesn't even fit without quantization or sharding) is a different kind of problem than 8B on 24 GiB.
• seq_len is the denominator you control. The formula uses worst-case length — exactly what the engine's startup "maximum concurrency" line assumes, and exactly why Phase 2 lab-03's reflection scolds the max_model_len=32768 config for a 4k workload. Capacity planning with the p99 length instead of the max is the cheapest 8× you'll ever find.
• What the simple formula ignores (and where it bends in practice): activation scratch memory (vLLM measures this at startup by profiling — Phase 2 lab-03), block-granularity rounding (block_size − 1 tail waste per sequence — Phase 2), CUDA context overhead, and the fact that real workloads have a length distribution, so effective concurrency is higher than the max-length floor. The formula is your lower bound and your sanity check, not your final answer — which is also why vLLM computes blocks from measured free memory rather than trusting arithmetic.

Going further

• Build a table for models you care about (3B/8B/70B; fp16/fp8 KV; 2k/8k/128k context) on A100-80G. Notice where concurrency drops below 1 — congratulations, you've discovered why 128k-context serving needs either massive HBM, KV offload, or architecture tricks, and why long-context pricing is what it is.
• Invert the formula: given a target of 200 concurrent users at 4k context on 8B/fp16, how much free HBM do you need? (200 × 4096 × 128 KiB = 100 GiB → multi-GPU territory → Phase 10's tensor parallelism divides per-GPU KV by the shard count.)
• Add block_size rounding from Phase 2 (ceil(seq_len / block_size) blocks per sequence) and quantify how little paging's tail waste costs vs the 60–80% it saves — reproducing Phase 2 lab-02's conclusion from the memory side.

References

• kipply, Transformer Inference Arithmetic — the classic source for exactly this per-token math: https://kipp.ly/transformer-inference-arithmetic/
• Ainslie et al., GQA: Training Generalized Multi-Query Transformer Models (2023) — why num_kv_heads shrank industry-wide: https://arxiv.org/abs/2305.13245
• Pope et al., Efficiently Scaling Transformer Inference (2022) — KV memory as the scaling bottleneck, formalized: https://arxiv.org/abs/2211.05102
• Kwon et al., PagedAttention (SOSP 2023) — what happens next to these bytes: https://arxiv.org/abs/2309.06180
• upstream/vllm/v1/core/kv_cache_utils.py::get_kv_cache_configs — your formula, running at every engine startup (Phase 2 lab-03 reads its output).

Lab 00-03 — From Logits to Token: Sampling Basics [CPU-OK]

A language model does not produce words. It produces logits — one raw score per vocabulary entry, 257 of them in mini_vllm, 128k+ in Llama-3 — and something has to collapse that scoreboard into the single token the user sees. That something is the sampler, and in this lab you build it: greedy, temperature, top-k, and top-p (nucleus), exactly mirroring mini_vllm/sampler.py — the final test literally checks that your sampler and the engine's agree token-for-token across a grid of configurations.

This is the last piece of the foundations: lab-01 gave you the loop, lab-02 the memory, lab-04 the speed limits — this one gives you the decision each loop iteration ends with.

Contents

• Why this lab exists
• Background: the knobs, and what they're actually for
• Files
• Run
• What to implement
• What the tests prove
• Hitchhiker's notes
• Going further
• References

Why this lab exists

Sampling parameters are the most-touched, least-understood interface in all of LLM serving. Every API request carries them; every "the model got worse" support ticket is ~30% likely to be a sampling change; and every inference engineer eventually debugs an incident where the answer was "someone set top_k=1 and wondered why outputs got repetitive." You should know these four knobs the way a DBA knows isolation levels — not as folklore ("0.7 is creative!") but as the small, exact algorithms they are.

There's an engine-design reason too. The sampler sits at a peculiar spot in the architecture: it's the only stage that's per-request configurable and stochastic, in the middle of a pipeline that is otherwise batched and deterministic. Getting determinism back when you need it (tests! reproducibility! debugging!) takes deliberate design — the seed parameter, greedy mode — and the entire course's testing strategy (every phase's "identical output" invariants) leans on the greedy shortcut you'll implement here. When Phase 9 expands sampling into penalties, logit processors, parallel sampling, and GPU vectorization, this lab is the kernel of truth it builds on.

Background: the knobs, and what they're actually for

Order matters — this is a pipeline, and each stage reshapes the distribution the next one sees (your sample must apply them in exactly this order to match the engine):

1. Temperature — divide all logits by T before softmax. T<1 sharpens (rich get richer), T>1 flattens (underdogs get a chance), T→0 approaches argmax. It's the only knob that reweights rather than truncates. The T == 0.0 case is special- cased as pure argmax — both because division by zero, and because greedy must be exactly deterministic, no RNG involved at all.
2. Top-k — keep the k highest logits, set the rest to −∞ (probability zero after softmax). A blunt truncation: k=1 is greedy-with-extra-steps, k=50 trims the long tail of nonsense tokens. Its weakness: k is fixed while the distribution's actual "width" varies wildly per step (after "The capital of France is" there's one good token; after "My favorite" there are hundreds).
3. Top-p (nucleus) — keep the smallest set of tokens whose cumulative probability ≥ p. Adaptive where top-k is fixed: confident steps keep few tokens, uncertain steps keep many. The subtle spec detail your implementation must honor: the token that crosses the threshold is included (else p=0.5 over probs [0.4, 0.4, 0.2] would keep only 0.4 < 0.5 — an under-full nucleus).
4. Softmax + one draw — normalize what survives and draw once with np.random.default_rng(seed). Seeded → reproducible; unseeded → fresh entropy per call.

And the stability clause: softmax must subtract the max before exponentiating. exp(1000) overflows float64; logits in the hundreds are perfectly normal outputs of an unnormalized final layer. This one line is the difference between a sampler and a NaN generator, and the test feeds you logits of 1000+ to make sure it's there.

Files

• starter.py — softmax, apply_top_k, apply_top_p, sample, each with its recipe. Your work.
• solution.py — reference (functionally identical to mini_vllm/sampler.py).
• test_lab.py — distribution sanity, each knob's exact semantics, determinism, and the agreement test against the engine's Sampler.

Run

LAB_IMPL=starter pytest phase-00-foundations/labs/lab-03-sampling-basics -q
pytest phase-00-foundations/labs/lab-03-sampling-basics -q   # reference (default)

What the tests prove

Hitchhiker's notes

• −∞ is the correct "impossible," not 0. Masking logits to −∞ (probability exactly 0 after softmax) composes cleanly: later stages renormalize over survivors automatically. Masking probabilities to 0 without renormalizing — a classic homebrew-sampler bug — leaves you sampling from a distribution that sums to 0.7.
• Order of operations is observable. Top-k-then-top-p (this pipeline, and vLLM's) gives different results than top-p-then-top-k for the same parameters. When two engines "with the same settings" produce different output statistics, pipeline order is suspect #2 (suspect #1 is tokenizer differences). The agreement test pins your order to the engine's.
• Why np.partition instead of sorting in top-k? O(n) vs O(n log n) over the vocab, per token, per request — at 128k vocab × thousands of tokens/s this is real money. Production goes further: vLLM's V1 sampler does top-k/top-p vectorized over the whole batch on the GPU (upstream/vllm/v1/sample/), with exactly the semantics you just wrote scalar. Semantics here, performance there — the course's recurring split.
• Ties under greedy: argmax takes the lowest index. Sounds trivial until two engines break ties differently and a "deterministic" comparison fails at token 947 — the fp16 near-tie problem from Phase 3 lab-02's notes, one layer down. Determinism is a stack of conventions, and you now know one more layer of it.
• seed is per-request state in real engines — vLLM keeps a per-request generator so request A's draws don't perturb request B's stream under batching (Phase 9). Your per-call default_rng(seed) is the single-request simplification; the same idea, one request at a time.

Going further

• Implement min-p (keep tokens with prob ≥ p × max-prob — an increasingly popular alternative that adapts even better than top-p) and write its boundary test. Then check: vLLM ships it (min_p in SamplingParams).
• Sample 10,000 draws at T ∈ {0.3, 1.0, 2.0} from fixed logits and plot the empirical histograms against your computed distributions — a χ² eyeball test of your own sampler, and a visceral feel for what temperature does.
• Read upstream/vllm/v1/sample/sampler.py and find the four stages of your pipeline in their batched form: the same algorithm, where every operation is a tensor op over [batch, vocab] and the special-casing of greedy becomes an index-select.

References

• mini_vllm/sampler.py — the component you just rebuilt; diff yours against it.
• upstream/vllm/v1/sample/sampler.py — the batched GPU version (Phase 9 territory).
• Holtzman et al., The Curious Case of Neural Text Degeneration (2019) — the paper that introduced nucleus (top-p) sampling and explains why truncation matters: https://arxiv.org/abs/1904.09751
• vLLM docs, Sampling Parameters — the full production knob set your four generalize into: https://docs.vllm.ai/en/latest/api/inference_params.html
• Phase 9 — penalties, logit processors, structured-output masking (Phase 12), and why sampling lives on the GPU.

Lab 00-04 — Prefill vs Decode: the Roofline Arithmetic [CPU-OK]

Lab-01 showed you that caching splits generation into two phases. This lab shows you the strange physics those phases live under — with six one-line functions and an A100 spec sheet. You'll compute the ridge point (the GPU's FLOP-per-byte ratio), discover that a single decoding sequence uses less than 1% of the GPU's compute, derive the hard speed limit of decode (125 tokens/s for an 8B model on an A100 — no kernel wizardry can beat it), and find the critical batch size where decode finally becomes compute-bound. These four numbers are the worldview of performance engineering; everything in Phase 18 is this lab with profilers attached.

Contents

• Why this lab exists
• Background: the roofline model in five minutes
• Files
• Run
• What to implement
• The numbers, walked through
• What the tests prove
• Hitchhiker's notes
• Going further
• References

Why this lab exists

There is a question that separates engineers who tune inference systems from engineers who guess at them: "is this workload compute-bound or memory-bound?" Every optimization belongs to one regime or the other — a faster matmul kernel does nothing for a bandwidth-bound decode; more batching does nothing for a compute-bound prefill — and applying a fix from the wrong regime is the most common way smart people waste a quarter. The roofline model answers the question with division. This lab makes you do the division until it's reflexive.

It also explains, from first principles, the economics you've been absorbing all phase: why batch size is the master lever of throughput (lab and Phase 1 lab-04), why continuous batching was worth inventing (Phase 3), why chunked prefill mixes the two phases in one step (Phase 3 lab-05 — piggybacking compute-hungry prefill onto bandwidth-starved decode steps), and why speculative decoding (Phase 8) can "spend FLOPs to save time" — the FLOPs were idle anyway.

Background: the roofline model in five minutes

Every computation has an arithmetic intensity: FLOPs performed per byte moved from memory. Every processor has a ridge point: peak FLOPs ÷ memory bandwidth. The roofline law is one comparison:

• intensity < ridge → memory-bound: the compute units finish early and wait for the bus. Speed = bandwidth × intensity. More FLOPs won't help; fewer bytes will.
• intensity ≥ ridge → compute-bound: the bus keeps up; you're using the silicon. Speed = peak FLOPs. Fewer bytes won't help; better kernels / more hardware will.

Our minimal model of a transformer step: it must read all weights once (n_params × dtype_bytes from HBM — weights don't fit in cache) and performs ~2 FLOPs per parameter per token (each weight participates in one multiply-accumulate per token). So:

intensity = 2 · n_params · num_tokens / (n_params · dtype_bytes) = 2 · num_tokens / dtype_bytes

The parameter count cancels. Intensity doesn't care how big the model is — only how many tokens share one trip through the weights. That cancellation is the single most clarifying fact in inference performance: prefill (thousands of tokens per trip) and decode (one token per trip per sequence) aren't two workloads that differ in degree; they're the two opposite ends of the roofline, by construction.

(The model ignores KV/activation traffic and attention FLOPs — see Hitchhiker's notes for when that bites. As a first-order tool it's startlingly accurate.)

Files

• starter.py — six functions, each ~one line, each a load-bearing concept. Your work.
• solution.py — reference.
• test_lab.py — A100 numbers, the cancellation, both regimes, the crossover, and the decode speed limit.

Run

LAB_IMPL=starter pytest phase-00-foundations/labs/lab-04-prefill-vs-decode -q
pytest phase-00-foundations/labs/lab-04-prefill-vs-decode -q   # reference (default)

The numbers, walked through

A100-80GB SXM: 312 TFLOPs fp16, 2.0 TB/s HBM. 8B model, fp16 (16 GB of weights).

ridge      : 312e12 / 2.0e12 = 156 FLOPs/byte
decode, batch 1 : intensity = 2·1/2 = 1        → 1 ≪ 156: bandwidth-bound, using 1/156 ≈ 0.6% of compute
prefill, 2048 tokens : intensity = 2048        → ≫ 156: compute-bound
crossover  : 156 tokens/step                   → the "critical batch size"
speed limit: 2.0e12 / 16e9 = 125 steps/s       → 125 tok/s per sequence, max, ever

Read them like an engineer:

• 0.6% compute utilization for single-stream decode. The other 99.4% of a $15k GPU is structurally idle — not because of bad kernels, but because one token per weight-trip is all the arithmetic the workload offers. This is the number that makes batching non-optional: every additional sequence in the decode batch reuses the same weight bytes, adding intensity ~1 per sequence, for free until you hit the ridge at ~156. Batch 64 → 64× the tokens/s at essentially the same step time. That free lunch is the entire economic basis of serving (and of this course's obsession with fitting more sequences in memory — lab-02 — since memory is what caps the batch).
• 125 tokens/s is a physics ceiling, not an engineering one: a decode step cannot complete faster than the weights can stream from HBM. Measure any well-tuned 8B/fp16 deployment and single-stream decode sits at 60–80% of this bound (the rest: KV reads, kernel overheads). When someone promises 500 tok/s single-stream on this hardware, they're describing quantization (fewer bytes — note dtype_bytes in your formula), speculation (Phase 8), or fiction.
• Prefill at 2048 is compute-bound — which is why TTFT responds to better kernels and FlashAttention (Phase 4), while ITL responds to memory bandwidth and quantization. Two metrics, two regimes, two completely disjoint optimization menus. Now you know why Phase 3's chunked prefill mixes the phases in one batch: decode steps have idle FLOPs; prefill chunks are pure FLOPs; together they fill the roofline from both sides (Sarathi's "piggybacking", which you measured as [33, 33, …] in Phase 3 lab-05).
• The crossover at 156 is worth memorizing as a shape, not a number: it moves with hardware (H100: ~295 fp16; consumer cards: lower) and dtype. "Decode needs ~ridge-many tokens per step to saturate compute" is the portable version.

What the tests prove

Hitchhiker's notes

• Where the weights-only model bends: at long contexts, KV reads become the dominant bytes (128 KiB/token from lab-02 × thousands of tokens × batch — eventually exceeding the 16 GB weight read!). That's why long-context decode gets slower per token even though "the model is the same size," why GQA/MLA exist (shrink KV bytes), and why Phase 18 extends this lab's model with a KV-traffic term. First-order tools, knowingly applied, then refined — that's the discipline.
• Why ~2 FLOPs per param per token? Each parameter sits in some matrix; processing a token multiplies it by one activation and adds into an accumulator — one FMA = 2 FLOPs. Attention adds FLOPs quadratic in sequence length on top (it's parameter-free, so it escapes this accounting); for short-to-moderate contexts the linear layers dominate and 2·N·T is a good model. The famous training version of the same estimate is 6·N·T (forward + backward); inference keeps only the 2.
• Quantization through this lens: INT4 weights = 4 GB to stream = 500 steps/s ceiling, 4× decode speedup with zero kernel cleverness — bandwidth-bound workloads reward byte-shrinking one-for-one. But the same INT4 does ~nothing for compute-bound prefill (the FLOPs still happen, often in fp16 after dequant). One optimization, two regimes, two completely different value propositions — Phase 6 lives here.
• The ridge explains CUDA graphs too (Phase 5): your 125 steps/s ceiling means a decode step takes ≥ 8 ms on this 8B model (16 GB streamed at 2 TB/s) — at that scale a few hundred microseconds of kernel-launch overhead is noise. Shrink the model to 1B and steps drop toward 1 ms; suddenly launch overhead is a first-order cost, and capturing the whole step as one CUDA graph pays for itself. The roofline tells you when overhead optimizations matter, too.

Going further

• Recompute everything for an H100 SXM (~990 TFLOPs fp16, ~3.35 TB/s): ridge ≈ 295, 8B decode ceiling ≈ 209 tok/s. Notice the ridge rose — new GPUs gain FLOPs faster than bandwidth, so decode gets relatively more memory-bound every generation. That trend line is why KV/weight compression research keeps accelerating.
• Add a kv_bytes_per_step(batch, context_len, kv_per_token) term (from lab-02) to decode_tokens_per_second and find the context length where KV traffic overtakes the weight read for batch 64. You've just derived the long-context wall.
• Plot the roofline: log-log, intensity on x, achievable FLOPs on y, the two plateaus, and drop points for decode batch {1, 8, 64, 156, 512} and prefill {128, 2048}. This single figure is the mental map for all of Phase 18 — draw it once by hand.

References

• Williams et al., Roofline: An Insightful Visual Performance Model (CACM 2009) — the original: https://dl.acm.org/doi/10.1145/1498765.1498785
• kipply, Transformer Inference Arithmetic — this lab's model applied end-to-end, the single best blog post in the field: https://kipp.ly/transformer-inference-arithmetic/
• Pope et al., Efficiently Scaling Transformer Inference (2022) — the rigorous version, including the KV-traffic terms: https://arxiv.org/abs/2211.05102
• Chen, Dissecting Batching Effects in GPT Inference (2023) — measured curves of the batch-size free lunch: https://le.qun.ch/en/blog/2023/05/13/transformer-batching/
• NVIDIA A100/H100 datasheets — where the peak-FLOPs and bandwidth constants come from (always check whether a quoted TFLOPs number assumes sparsity; marketing does).
• Phase 18 — this lab, with nsys/ncu attached and the simplifications removed.

Phase 00 — Exercises: Foundations

Contents

• Warm-up (explain)
• Core (the distinctions that matter)
• Build (your labs)
• Design (staff-level)
• Self-grading

Warm-up (explain)

1. In one sentence: what does an LLM compute, and what is "autoregressive generation"?
2. Define tokens, embeddings, logits. Where in a forward pass do logits appear?
3. Why does a token's K and V never change once computed? Why does that justify a cache?

Core (the distinctions that matter)

4. Fill the table from memory: prefill vs decode — tokens/pass, bottleneck (compute vs memory bandwidth), and which latency metric (TTFT vs ITL) each drives.
5. Explain why decode is memory-bandwidth-bound. What must the GPU read to produce one token, and how much math does it do with it?
6. Why does batching help throughput specifically during decode? (Hint: what gets amortized?)

Build (your labs)

7. In lab-01, derive the exact no-cache work sum(P..P+n-1) and the cached work P+n. What's the ratio as n → ∞ for fixed P?
8. In lab-02, compute kv_bytes_per_token and max concurrency for a model of your choice (look up its config: layers, kv_heads, head_dim). Then redo it with fp8 KV cache.
9. A model uses MHA (num_kv_heads == num_query_heads). Show how switching to GQA with 8 KV heads changes KV memory and thus concurrency.

Design (staff-level)

10. You must serve a 70B model at 8k context with TTFT < 1s and ITL < 50ms on 8×A100 (80GB). Estimate KV memory per sequence and reason about how many concurrent users fit. What's the first thing you'd do to fit more?
11. A teammate says "let's just recompute attention each step, it's simpler." Quantify what that costs for a 2000-token generation and explain why it's a non-starter.
12. Using Little's Law (concurrency = throughput × latency), if you target 1000 tok/s aggregate at 50ms ITL, how many sequences must be in flight? What limits that number?

Self-grading

4, 5, 10–12 are interview-grade. Could you whiteboard each in 5 minutes? If not, re-read the guide's prefill/decode and memory sections, then drill INTERVIEW.md.

Phase 00 — Interview Questions: Foundations

Cover the answer, attempt out loud, compare. These fundamentals gate everything else — if you fumble them, the interviewer won't trust your scheduler answers.

Q1. Why is autoregressive decoding so much slower per token than prefill?

Q2. What is the KV cache and why does it dominate serving memory?

Q3. Walk me through prefill vs decode.

Q4. How would you estimate KV-cache memory for a deployment?

Q5. Why does batching improve throughput, and what's the cost?

Rapid-fire

• Tokens are roughly? ~¾ of a word; integer ids from a tokenizer.
• Logits are? Pre-softmax scores over the whole vocabulary for the next token.
• Decode bottleneck? Memory bandwidth. Prefill bottleneck? Compute.
• TTFT driven by? Prefill. ITL driven by? Decode.
• KV bytes/token formula? 2 × layers × kv_heads × head_dim × dtype_bytes.
• The engine's master variables? num_computed_tokens chasing num_tokens.

Phase 00 — Cheatsheet: Foundations

Contents

• The one-liner
• The loop
• Prefill vs decode
• KV cache
• The master model
• Throughput vs latency
• Key upstream

The one-liner

An LLM predicts the next token; generation loops that. Serving = doing it fast for many users. Memory (the KV cache), not compute, is the cap.

The loop

tokenize → (prefill the prompt) → loop[ forward → sample → append ] → detokenize. Real: EngineCore.step = schedule → execute → sample → update (core.py:428).

Prefill vs decode

KV cache

• Exists because K/V never change once computed → cache them → O(N²) work becomes O(N).
• kv_bytes_per_token = 2 × layers × kv_heads × head_dim × dtype_bytes.
• Llama-3-8B fp16 ≈ 128 KiB/token. Concurrency ≈ (HBM − weights) / (per_token × seq_len).
• Shrink it: GQA (fewer kv_heads), fp8 KV (half dtype), shorter context, paging (Phase 2).

The master model

A request = num_computed_tokens racing num_tokens. Prefill = far behind; decode = one behind. (vllm/v1/request.py:239; mirrored in mini_vllm/request.py.)

Throughput vs latency

Bigger batch → more throughput (amortize weight reads), worse per-request latency. Little's Law: concurrency = throughput × latency. The scheduler (Phase 3) and tuning (Phase 18) live here.

Key upstream

• vllm/model_executor/models/llama.py — a real forward pass (Q/K/V at LlamaAttention.forward)
• vllm/v1/request.py:239 — the counters
• vllm/v1/engine/core.py:428 — EngineCore.step

Full: 00-guide.md · 01-deep-dive.md · INTERVIEW.md

Phase 01 — The Hitchhiker's Guide to vLLM's Architecture & Request Lifecycle

← Phase 00 · Course home · Phase 02 →

This is Chapter 1. Phase 0 taught you what one forward pass is and why it's slow. This chapter zooms out to the whole machine: how vLLM turns that single forward pass into a service that streams tokens to thousands of users at once. We build the architecture the way you'd design it yourself — by starting with the obvious naive server, watching it fail, and fixing each failure. By the end you'll be able to trace any request from an HTTP call to a streamed token and name every component it touches. That mental map is what lets you navigate 500,000 lines of code without drowning.

How to read this chapter. Everyday explanation throughout; paragraphs marked 🔬 Going deeper add the systems rigor for the expert track.

Contents

• 1.1 Don't Panic — the architecture in one breath
• 1.2 Let's design it ourselves: why the naive server fails
• 1.3 Two front doors, one engine
• 1.4 The objects a request becomes (and why each exists)
• 1.5 The heartbeat dissected: EngineCore.step()
• 1.6 The process architecture: why the engine lives alone
• 1.7 Who actually touches the GPU: Executor → Worker → ModelRunner
• 1.8 The request lifecycle: a state machine
• 1.9 How thousands of requests share the loop (the payoff)
• 1.10 Tracing one request, end to end
• 1.11 The mental model to carry forward
• 1.12 What you'll do in this phase

1.1 Don't Panic — the architecture in one breath

A request enters as a string and leaves as tokens. In between it passes through a handful of well-named components, and a tiny loop runs the model over and over until the request is done.

vLLM looks enormous, but the path a request takes is short:

  "Tell me a joke"
        │  tokenize, wrap as a request
        ▼
   LLM  /  AsyncLLM            ← the front door (offline batch  /  online server)
        │  add_request
        ▼
   EngineCore.step()  ──────────────── the heartbeat (runs every ~10–50 ms) ───────────┐
        │   1. schedule()              who runs this step, and how many tokens   (Ph 3) │
        │   2. execute_model()         run the model on the assembled batch     (Ph 4+) │  loop
        │   3. sample_tokens()         pick the next token for each sequence      (Ph 9)│  until
        │   4. update_from_output()    advance counters, retire finished reqs     (Ph 3)│  done
        ▼                                                                               │
   Detokenizer / OutputProcessor  ← token IDs → text, streamed back ───────────────────┘
        │
        ▼
   " Why did the function..."   (streamed token by token)

That five-line step() loop is vLLM. Every later phase is a deep dive into one box of it. The rest of this chapter explains why it's shaped this way and what each piece does.

1.2 Let's design it ourselves: why the naive server fails

The fastest way to understand vLLM's architecture is to build the obvious version in your head and watch it break. Each break motivates a real component.

Attempt 1 — a function call. "Just call model.generate(prompt) per request." This works for one user. But it serves requests one at a time: while user A's 500-token answer generates, users B–Z wait. And from Phase 0 §0.10, a single decode stream uses ~1% of the GPU (it's memory-bound at batch 1). You're paying for a Ferrari and driving it in a parking lot. → We must run many requests together (batching).

Attempt 2 — static batching. "Collect N requests, run them as a batch until all finish." Better GPU use, but two new problems:

• Requests have different lengths. A batch finishes at the speed of its slowest member; short requests sit idle in the batch, wasting their slot. (We'll fix this with continuous batching — re-decide the batch every step — in Phase 3.)
• New requests that arrive mid-batch must wait for the whole batch to finish before they can start. Terrible tail latency. → We need a component that re-plans the batch every single step: the scheduler.

Attempt 3 — scheduler + model, in one Python process, inside the web server. Now the GPU loop and the HTTP server share a process. Problems:

• The tight, latency-critical GPU loop competes with HTTP parsing, JSON serialization, and detokenization for the single Python thread (the GIL). A burst of requests stalls the GPU.
• Multi-GPU (Phase 10) needs multiple processes anyway. → Isolate the engine in its own process, talk to it over a queue. That's vLLM's V1 design.

So the architecture isn't arbitrary — each component is the answer to a specific failure of the naive version. Now let's name the real pieces.

🆕 New words: batching (run many requests together), static vs continuous batching, scheduler (re-plans the batch each step), the GIL (Python's single-thread lock — why the engine gets its own process).

1.3 Two front doors, one engine

vLLM has two entry points, and the crucial insight is that both are thin shells over the same engine core:

• Offline / batch: LLM(model=...).generate(prompts) — vllm/entrypoints/llm.py. You hand it a list of prompts; it returns a list of results when all are done. Synchronous. This is what mini_vllm's LLMEngine.generate mirrors, and what you use in scripts and evals.
• Online / serving: an HTTP server (OpenAI-compatible, Phase 16) → AsyncLLM (vllm/v1/engine/async_llm.py) → the same core, but async and streaming — it yields each token as it's produced so the user sees text appear live.

Both funnel into EngineCore (vllm/v1/engine/core.py). Internalize this: batch and server are skins; the engine is one. When you fix something in the core, you fix it for both.

1.4 The objects a request becomes (and why each exists)

A request changes form as it travels — and each form is a deliberate data type. Knowing them means that when you read a stack trace, you instantly know which stage you're in by the type in hand.

🔬 Going deeper. The split between EngineCoreRequest (crosses the process boundary, so it's a plain serializable struct) and Request (rich, mutable, lives only inside the engine process) is not incidental — it's the seam where the IPC boundary sits (§1.6). And RequestOutput being a delta in streaming mode (only the new tokens since last time) is what makes server-sent-events streaming cheap. Naming is half of understanding a system; learn these six.

🆕 New words: SamplingParams, EngineCoreRequest, Request, SchedulerOutput, ModelRunnerOutput, RequestOutput.

1.5 The heartbeat dissected: EngineCore.step()

The engine is a loop. Each tick (step()) advances every in-flight request by some tokens. Here is the loop with each stage explained — this is the spine of the whole system:

def step():
    scheduler_output = self.scheduler.schedule()                    # 1. PLAN
    model_output     = self.model_executor.execute_model(...)       # 2. RUN
    # (sampling happens inside/after execute; shown separate for clarity)
    sampled          = self.model_executor.sample_tokens(...)       # 3. PICK
    outputs          = self.scheduler.update_from_output(...)       # 4. BOOKKEEP
    return outputs

1. Schedule (the plan) — the scheduler looks at every waiting and running request and the free KV memory, and decides: who runs this step, and how many tokens does each get? This is where continuous batching, chunked prefill, prefix caching, and preemption happen (Phases 2–3). Output: a SchedulerOutput.
2. Execute (run the model) — the executor turns that plan into actual tensors (gather the scheduled tokens, build the attention metadata — block tables and sequence lengths from Phases 2–4) and runs the forward pass on the GPU (possibly as a CUDA graph, Phase 5). This is where kernels, quantization, parallelism, and the model itself live (Phases 4–7, 10, 13, 14).
3. Sample (pick tokens) — turn the model's logits into one new token per sequence, applying each request's own sampling params, grammar masks, etc. (Phases 8, 9, 12).
4. Bookkeep (update) — append the sampled tokens, advance each request's num_computed_tokens, detect which requests just finished (hit EOS or max length), free their KV blocks, and emit outputs (Phase 3).

Then it loops. A request might be touched by a few hundred ticks over its lifetime (one per output token, after prefill). Every box of this loop maps to a phase of the course — keep this diagram open as your table of contents.

🔬 Going deeper — the real step is even leaner. In core.py the four stages are visible almost verbatim (you'll read them in the deep-dive). Two production wrinkles: (a) execute_model can run asynchronously (return a future) so the scheduler can plan the next step while the GPU works on this one — overlapping CPU and GPU; (b) a grammar bitmask for structured output (Phase 12) is computed between schedule and sample. Don't let those obscure the four-beat rhythm: plan → run → pick → bookkeep.

1.6 The process architecture: why the engine lives alone

From §1.2, the engine must not share a Python thread with the web server. So V1 runs EngineCore in its own process (EngineCoreProc). The picture:

   ┌─────────────── API server process ───────────────┐        ┌──── EngineCore process ────┐
   │  HTTP / OpenAI endpoints  (Phase 16)              │        │  scheduler                 │
   │  tokenization, request validation                 │  IPC   │  the model + KV cache      │
   │  AsyncLLM  ── EngineCoreRequest ──────────────────┼───────▶│  step() loop               │
   │  detokenization, streaming  ◀── EngineCoreOutputs─┼────────┤                            │
   └───────────────────────────────────────────────────┘        └────────────────────────────┘

Why this split is worth a whole process boundary:

• The scheduling loop stays tight — no HTTP work, JSON, or detokenization steals its thread or contends for the GIL. The GPU is never starved by web-server bookkeeping.
• Detokenization and streaming run on the server side, off the engine's hot path — turning token IDs back into text and formatting SSE chunks happens in parallel with the next step().
• It generalizes to multi-GPU: the core process becomes the coordinator of worker processes (next section).

The cost is that requests and outputs must be serialized across the boundary (that's why EngineCoreRequest/EngineCoreOutputs are plain structs, §1.4). It's a price worth paying for an uninterrupted GPU loop.

🆕 New words: IPC (inter-process communication), EngineCoreProc (the engine's own process), SSE (server-sent events — the streaming protocol).

1.7 Who actually touches the GPU: Executor → Worker → ModelRunner

EngineCore decides what to run; it does not run the model itself. That's delegated down a chain whose whole purpose is to make the same engine run on 1 GPU or 64:

EngineCore
  └─ Executor          (vllm/v1/executor/)   owns the worker(s); the engine's handle to compute
       └─ Worker        (vllm/v1/worker/gpu_worker.py)   one per GPU: holds a model shard + its KV cache
            └─ ModelRunner  (gpu_model_runner.py)   SchedulerOutput → input tensors → forward → sampler

• Executor — for a single GPU it's a UniProcExecutor (just calls the one worker). For tensor/pipeline parallelism (Phase 10) it's a MultiprocExecutor that owns N worker processes and broadcasts each step's plan to all of them.
• Worker — owns one GPU: its device, its slice of the model's weights, and its slice of the KV cache. Runs in lockstep with its peers.
• ModelRunner — the busiest object in the engine. It takes the SchedulerOutput, prepares the input tensors (gathers the scheduled tokens, builds the attention metadata: block tables + sequence lengths + slot mapping — Phases 2/4), runs the (possibly CUDA-graphed) forward pass, and runs the sampler. You'll return to gpu_model_runner.py in Phases 4, 5, 9, 13.

The elegance: the model code is identical whether you run on 1 GPU or 64 — it just uses parallel layers, and the Executor fans the work out. Scaling out changes the Executor, nothing above it.

🔬 Going deeper. This is also where the prepare-inputs cost lives — assembling ragged, variable-length batches into padded tensors and metadata every step is real CPU work, and at small batch it can rival the GPU time. That's a major reason CUDA graphs (Phase 5) and careful tensor reuse matter, and why gpu_model_runner.py is so heavily optimized. When you profile a slow deployment (Phase 18), this file is a frequent suspect.

1.8 The request lifecycle: a state machine

Inside the engine, each request moves through a small set of states (RequestStatus in vllm/v1/request.py). Understanding the states — and especially the transitions — is how you reason about latency, fairness, and failures.

     (arrives)
        │
        ▼
   ┌─────────┐   admitted by      ┌─────────┐   generates a token   ┌──────────────────┐
   │ WAITING │ ───scheduler────▶ │ RUNNING │ ───each step────────▶ │ FINISHED_*       │
   └─────────┘   (KV allocated)  └─────────┘   until stop/maxlen    │ (STOPPED/LENGTH/ │
        ▲                            │                              │  ABORTED/ERROR)  │
        │      preempted: out of KV  │                              └──────────────────┘
        └────────── PREEMPTED ◀──────┘   (KV freed; re-admitted later, recomputed — Phase 3)

• WAITING — admitted to the engine, queued, not yet running (no KV allocated yet).
• RUNNING — actively generating; has KV blocks; touched every step.
• PREEMPTED — was running, but the engine ran out of KV memory and evicted it to make progress on others; it goes back to WAITING and is recomputed when memory frees (Phase 3's safety valve).
• FINISHED_* — terminal: hit a stop token (STOPPED), hit max length (LENGTH_CAPPED), was cancelled (ABORTED), or errored. Its KV is freed and the final output returned.

🔬 Going deeper. Real vLLM has extra "waiting" sub-states for requests blocked on something other than the queue: waiting for a structured-output grammar to compile (Phase 12), waiting for KV to arrive over the network in disaggregated serving (Phase 15), etc. They're still "not ready to run," just for richer reasons. Also note the enum ordering trick: is_finished is simply status > PREEMPTED, so the terminal states are defined by position in the enum — a tiny detail that makes the hot-path check branch-free. You'll trace this exact state machine in lab-01.

🆕 New words: RequestStatus, preemption (evict a running request under memory pressure), terminal/finished states.

1.9 How thousands of requests share the loop (the payoff)

Now connect the architecture back to Phase 0's physics. Why all this machinery? Because of §0.10: one decode stream wastes ~99% of the GPU. The architecture exists to keep many requests in flight so each step() decodes a big batch — amortizing the weight read and pushing arithmetic intensity toward the roofline ridge.

Crucially, because the scheduler re-plans every step (continuous batching, Phase 3), requests don't move in lockstep: the moment one finishes, its slot is freed and a WAITING request joins mid-flight, on the very next tick. So at any instant the running batch is a churning mix of requests at different stages — some doing their first (prefill) step, most adding one decode token. The loop in §1.5 absorbs all of that uniformly because, to it, every request is just "advance num_computed_tokens toward num_tokens" (Phase 0 §0.13). That uniformity is why one simple loop can serve a chaotic, ever-changing crowd.

time ─►
req A  [prefill][dec][dec][done]
req B        [prefill][dec][dec][dec][done]
req C                  [prefill][dec][dec]...        ← C joined the instant A's slot freed
        every column is one step() = one batched forward over whoever's running right now

1.10 Tracing one request, end to end

Let's follow "Tell me a joke" through the offline path, naming each stop (you'll do this live in lab-01, and read the real code in the deep-dive):

1. LLM.generate(["Tell me a joke"]) tokenizes the prompt and builds an EngineCoreRequest.
2. add_request wraps it as a Request (num_tokens=5, num_computed_tokens=0, status WAITING) and enqueues it in the scheduler.
3. Tick 1 (prefill): schedule() admits it → RUNNING, allocates KV blocks for 5 tokens; execute_model runs the forward over all 5 prompt tokens; sample_tokens produces " Why"; update_from_output sets num_computed_tokens=5, appends " Why" (num_tokens=6).
4. Ticks 2..N (decode): each tick schedules 1 new token for this request, runs the model, samples the next token, appends it. num_computed_tokens chases num_tokens, one step at a time.
5. Finish: when the model emits the EOS token (or hits max_tokens), update_from_output marks it FINISHED_*, frees its KV blocks, and the detokenizer turns the token IDs into the final string (streamed token-by-token on the server path).

That's the whole life of a request. Notice tick 1 processes many tokens (prefill, compute-bound) and every later tick processes one (decode, memory-bound) — Phase 0's two phases, now visible in the loop.

1.11 The mental model to carry forward

   front door (LLM / AsyncLLM)
        → EngineCore.step loop:   schedule → execute → sample → update
              ├─ schedule/update  ........ Phases 2, 3   (memory & batching)
              ├─ execute_model    ........ Phases 4–7, 10, 13, 14  (kernels, quant, parallelism, models)
              └─ sample_tokens    ........ Phases 8, 9, 12  (decoding, spec, structured)
        → detokenize / stream     ........ Phase 16  (the serving API)

Every later phase is a zoom into one box of EngineCore.step. You now have the table of contents for the entire book. When a later chapter says "this happens during execute_model" or "the scheduler decides X," you'll know exactly where in this picture you are.

1.12 What you'll do in this phase

• Read: 01-deep-dive.md — LLM.generate, EngineCore.step, LLMEngine, AsyncLLM, and the Executor→Worker→ModelRunner chain, with verified line anchors.
• Build: 02-mini-build.md — add lifecycle tracing to mini_vllm.
• Labs (see labs/README.md for the full guide to each):
  • lab-01-trace-a-request [CPU-OK] — instrument mini_vllm to record a request's full lifecycle (states + the two counters, per step) and assert it matches the WAITING→RUNNING→FINISHED path.
  • lab-02-read-the-real-loop [GPU-OPT] — run real vLLM with debug logging and correlate the output to core.py:step() (captured output included).
  • lab-03-engine-step-by-hand [CPU-OK] — rebuild LLMEngine.step from the scheduler/model/ sampler and prove it token-for-token identical to the real loop (incl. the needs_sample guard).
  • lab-04-watch-the-batch [CPU-OK] — probe the scheduler and record per-step batch composition: chunking, deferred admission, and mixed prefill+decode steps, measured.
  • lab-05-stop-conditions [CPU-OK] — EOS vs max_tokens vs ignore_eos, the boundary tie, and the status→finish_reason mapping every API consumer depends on.
• Test yourself: EXERCISES.md, INTERVIEW.md, CHEATSHEET.md.

You're ready to move on when you can draw the request's journey from generate() to a streamed token, name every object and component it becomes/touches, recite the four stages of step() and which phase owns each, and explain why the engine runs in its own process and why continuous batching is what makes the whole thing economical.

← Phase 00 · Course home · Phase 02 →

Phase 01 — Deep Dive: tracing a request through real vLLM

Paths relative to upstream/ at v0.22.1 @ 0decac0. We follow one request from LLM.generate to tokens out, naming every file. Keep mini_vllm/engine.py open alongside — it's the same control flow, miniature.

Contents

• 1. The offline entry point: LLM.generate
• 2. The heartbeat: EngineCore.step
• 3. Down to the metal: Executor → Worker → ModelRunner
• 4. The async path (serving)
• 5. The output path
• The whole journey, named
• Reading checklist

1. The offline entry point: LLM.generate

vllm/entrypoints/llm.py: class LLM (:66), def generate (:422). generate validates inputs, builds requests, adds them to the engine, and runs the engine to completion, collecting RequestOutputs. Under the hood it drives an LLMEngine.

vllm/v1/engine/llm_engine.py: class LLMEngine (:47) with add_request (:209) and step (:287). This is the synchronous wrapper: add_request tokenizes + enqueues; step pumps the core once and returns finished RequestOutputs. mini_vllm.LLMEngine.{add_request,step,generate} mirror these one-to-one.

2. The heartbeat: EngineCore.step

vllm/v1/engine/core.py:428 (you read this in Phase 00 — revisit with the architecture in mind):

def step(self):
    if not self.scheduler.has_requests():
        return {}, False
    scheduler_output = self.scheduler.schedule()                        # 1. who runs (Ph 3)
    future = self.model_executor.execute_model(scheduler_output, ...)   # 2. run model (Ph 4–14)
    grammar_output = self.scheduler.get_grammar_bitmask(scheduler_output)
    model_output = future.result()
    if model_output is None:
        model_output = self.model_executor.sample_tokens(grammar_output)# 3. sample (Ph 9)
    engine_core_outputs = self.scheduler.update_from_output(            # 4. advance (Ph 3)
        scheduler_output, model_output)
    return engine_core_outputs, scheduler_output.total_num_scheduled_tokens > 0

add_request is at core.py:337: it wraps the incoming EngineCoreRequest into a Request and hands it to self.scheduler.add_request. Note EngineCore also subclasses into EngineCoreProc (:835) — the version that runs in its own process and receives requests over a queue. That's the process split from the guide.

3. Down to the metal: Executor → Worker → ModelRunner

self.model_executor is an Executor (vllm/v1/executor/abstract.py defines the interface). For single-GPU it's a UniProcExecutor; for multi-GPU a MultiProcExecutor (multiproc_executor.py, Phase 10). execute_model(scheduler_output) forwards to the worker(s).

vllm/v1/worker/gpu_worker.py — class Worker: owns the device, the model, and the KV cache for one GPU. Its execute_model calls into the model runner.

vllm/v1/worker/gpu_model_runner.py — GPUModelRunner.execute_model is where SchedulerOutput becomes reality: it gathers the scheduled tokens into input tensors, builds attention metadata (block tables + sequence lengths from Phase 2/3), runs the (possibly CUDA-graphed, Phase 5) forward pass, and runs the sampler. Search it for execute_model and _prepare_inputs. This is the single busiest file in the engine — you'll return to it in Phases 4, 5, 9, 13.

4. The async path (serving)

vllm/v1/engine/async_llm.py: class AsyncLLM. The OpenAI server (Phase 16) calls AsyncLLM.generate, an async generator that yields RequestOutput deltas as they're produced. Internally it talks to the EngineCoreProc over IPC and runs the output processing/detokenization on the server side, off the core's hot path. Same core, async shell.

5. The output path

vllm/v1/engine/output_processor.py + detokenizer.py: turn the core's sampled token ids back into text, handle stop strings, and assemble RequestOutputs (streaming deltas for the server). mini_vllm folds this into engine.generate (decode at the end) — simpler, same idea.

The whole journey, named

LLM.generate (llm.py:422)
  └─ LLMEngine.add_request (llm_engine.py:209) -> EngineCore.add_request (core.py:337)
  └─ loop LLMEngine.step (llm_engine.py:287) -> EngineCore.step (core.py:428):
        scheduler.schedule()                 (sched/scheduler.py:329)        Phase 3
        executor.execute_model()             (executor/ -> worker/gpu_model_runner.py)  Phase 4-14
        executor.sample_tokens()             (sample/sampler.py)             Phase 9
        scheduler.update_from_output()       (sched/scheduler.py:1283)       Phase 3
  └─ output_processor/detokenizer -> RequestOutput

Reading checklist

• LLM.generate → which engine method adds requests, which pumps the loop?
• EngineCore.step → recite the four stages and the file each lives in.
• Executor vs Worker vs ModelRunner → who owns the GPU, who builds tensors?
• Why does EngineCoreProc exist (the process split)?
• Where does detokenization happen, and why off the core's hot path for serving?

Now build it: 02-mini-build.md, then the labs.

Phase 01 — Mini-Build: trace the request lifecycle

You'll add lifecycle tracing to mini_vllm so you can see a request move through WAITING → RUNNING → FINISHED, with its num_computed_tokens/num_tokens at every step. Seeing the state machine run is how the architecture stops being abstract.

Contents

• The task (lab-01)
• Method
• Definition of done
• Map to the real engine

The task (lab-01)

Implement trace_request(engine_kwargs, prompt, sampling_params) -> list[Event] that runs the mini_vllm engine one step() at a time and records, after each step, every live request's (request_id, status, num_computed_tokens, num_tokens). Then derive:

• the first event (should be RUNNING with num_computed == num_prompt_tokens after prefill),
• the sequence of statuses (RUNNING…→FINISHED),
• that num_computed_tokens is monotonically non-decreasing until finish.

You're reconstructing, on your own engine, what VLLM_LOGGING_LEVEL=DEBUG shows you on the real one (lab-02). Map each transition to EngineCore.step (core.py:428).

Method

mini_vllm.LLMEngine exposes scheduler (with .running/.waiting) and step(). Drive the loop manually:

eng = LLMEngine(**engine_kwargs)
rid = eng.add_request(prompt, sampling_params)
events = []
while eng.scheduler.has_unfinished_requests():
    eng.step()
    for r in eng.scheduler.running:
        events.append(Event(r.request_id, r.status.name, r.num_computed_tokens, r.num_tokens))
    # also capture finished requests in the step return value

(The exact capture is the lab's job; the test pins the resulting trace's shape.)

Definition of done

pytest phase-01-architecture-and-request-lifecycle/labs -q

Then answer: at which step does num_computed_tokens first equal num_prompt_tokens (prefill done)? After that, how much does it grow per step (decode = 1)? Why does that match the prefill/decode model from Phase 0?

Map to the real engine

Phase 01 Labs — Architecture & Request Lifecycle

Five labs that turn the engine from a black box into your box. The arc: observe the lifecycle (lab-01), verify it on real hardware (lab-02), rebuild the loop yourself (lab-03), watch many requests share it (lab-04), and master how requests end (lab-05). Do them in order — each one's vocabulary is the next one's prerequisite.

Every [CPU-OK] lab follows the same contract: starter.py with TODOs (your work), solution.py (the reference), test_lab.py (the spec, executable). The default test run uses solution.py so the suite is always green; set LAB_IMPL=starter to grade yourself.

# Whole phase (GPU tests auto-skip without CUDA):
pytest phase-01-architecture-and-request-lifecycle/labs -m "not gpu"

# Grade your own work on one lab:
LAB_IMPL=starter pytest phase-01-architecture-and-request-lifecycle/labs/lab-01-trace-a-request -q

Contents

• lab-01-trace-a-request [CPU-OK]
• lab-02-read-the-real-loop [GPU-OPT]
• lab-03-engine-step-by-hand [CPU-OK]
• lab-04-watch-the-batch [CPU-OK]
• lab-05-stop-conditions [CPU-OK]
• What you can do after this phase

Labs

lab-01-trace-a-request [CPU-OK]

Drive the mini_vllm engine one step at a time and record every transition of a single request — status, num_computed_tokens, num_tokens — from prefill through decode to finish. You'll reconstruct, on an engine you control, exactly what VLLM_LOGGING_LEVEL=DEBUG prints on the real one, and internalize the course's central mental model: a request is two counters racing. Skills: the lifecycle state machine; prefill/decode as one mechanism; TTFT = step 1.

lab-02-read-the-real-loop [GPU-OPT]

Run real vLLM 0.22.1 on a tiny model with debug logging and attribute every log line to a stage of EngineCore.step (core.py:428). The lab-01 trace and the production log line up one-to-one — that correlation is the moment the upstream codebase becomes readable. Captured, annotated output included so the lab works without a GPU. Skills: log-line → source-line debugging; the three-call engine core; # GPU blocks as serving capacity.

lab-03-engine-step-by-hand [CPU-OK]

The rite of passage: given the engine's organs (scheduler, model, sampler), wire the schedule → execute → sample → update loop yourself, and prove it token-for-token identical to LLMEngine.step. Includes the one subtle rule of the whole loop — only requests whose computed tokens catch up this step may sample — with a test that catches you if you miss it. Skills: the engine's stage contract; the needs_sample invariant; testing by determinism.

lab-04-watch-the-batch [CPU-OK]

Instrument the scheduler with a non-invasive probe and record the batch composition of every step while multiple requests run under a scarce token budget. You'll see prefill chunks and decodes co-scheduled in one step, requests joining and leaving the batch mid-flight — continuous batching, measured rather than described. Skills: the observe-don't-modify probe pattern; budget/chunk/defer mechanics; token-conservation identities for debugging schedulers.

lab-05-stop-conditions [CPU-OK]

Dissect how requests end: EOS ("stop") vs max_tokens ("length"), the ignore_eos benchmark flag, and the boundary tie where both fire at once and the order of two if statements becomes a public API. Scripted token streams make every edge case exactly testable. Skills: status → finish_reason mapping; why ordering of stop checks is an API decision; triaging "my answer got cut off."

What you can do after this phase

Explain to a colleague, with evidence you generated yourself: what one step of an inference engine does; why TTFT ≈ prefill and ITL ≈ one decode step; how N requests share an engine without ever stopping it; and what finish_reason will say and why. You also now hold the top of vLLM's call tree (EngineCore.step) in your head — every later phase is a descent into one of its three calls.

Lab 01-01 — Trace a Request's Lifecycle [CPU-OK]

"The first thing a systems engineer does with a black box is make it stop being one."

You are going to take one request — a single prompt — and watch every heartbeat of its life inside an inference engine: from the moment it's admitted, through its prefill, through every decode step, until the engine pronounces it finished. By the end you will have produced, with your own code, the exact trace that vLLM emits when you run it with VLLM_LOGGING_LEVEL=DEBUG — and more importantly, you'll know why every line of that trace looks the way it does.

Contents

• Why this lab exists
• Background: the one mental model to rule them all
• Files
• Run
• What to implement
• What you should see — and why every number is what it is
• What the tests prove
• How this maps to the real engine
• Hitchhiker's notes (gotchas & deeper cuts)
• Going further
• References

Why this lab exists

Every hard debugging session you will ever have on an inference engine — a stuck request, a latency cliff, a throughput regression, a preemption storm — starts with the same question: "what is the engine doing with my request right now?" If you can't answer that, you're guessing. If you can, you're an engineer.

The trouble is that production engines hide the lifecycle behind a convenience API. You call llm.generate(...), you get text back, and the thousand scheduling decisions in between are invisible. This lab removes the convenience wrapper. You will drive the engine one step at a time with your own loop, and after each step you'll photograph the request's state: its status, how many of its tokens have been computed, how many exist in total.

That photograph sequence is the request lifecycle. Once you've built it yourself, the real engine's debug logs (lab-02), its Prometheus metrics (vllm:num_requests_running, vllm:num_requests_waiting — Phase 18), and its scheduler internals (Phase 3) all become readable at a glance, because they're all just different projections of the same state machine you're about to instrument.

Background: the one mental model to rule them all

Here is the single most important idea in this whole phase, the one the real vLLM scheduler is built on (see the comment block at upstream/vllm/v1/core/sched/scheduler.py:330):

There is no "prefill phase" and no "decode phase." A request is just two counters racing: num_computed_tokens chasing num_tokens.

• num_tokens = prompt tokens + tokens generated so far. It grows by 1 every time the request samples a new token.
• num_computed_tokens = how many of those tokens have had their KV (attention key/value) computed and stored in the cache. The model can only sample a new token when this counter has caught up — when every existing token's KV is in place.

"Prefill" is merely the situation where num_computed_tokens is far behind (the whole prompt's KV is missing) and the engine computes a big batch of it at once. "Decode" is the situation where it's exactly one behind, and each step computes one token's KV and samples one new token. The same loop handles both. This is what makes chunked prefill (Phase 3), prefix caching (Phases 2–3), and continuous batching fall out naturally instead of being special cases — and it's the single design decision that most distinguishes vLLM's V1 engine from a naive two-phase implementation.

The lifecycle states you'll observe (from mini_vllm/request.py, mirroring upstream/vllm/v1/request.py):

                 add_request()            scheduled              stop condition
   (created) ───────────────▶ WAITING ───────────────▶ RUNNING ───────────────▶ FINISHED_*
                                  ▲                       │
                                  │     memory pressure   │
                                  └──── PREEMPTED ◀───────┘        (Phase 3, lab-04)

FINISHED_* is two states in practice: FINISHED_STOPPED (hit the EOS token) and FINISHED_LENGTH (hit max_tokens). Lab-05 dissects that distinction; in this lab we pin ignore_eos=True so length is always the stop reason and the trace is deterministic.

Files

• starter.py — implement trace_request (the manual step loop + snapshotting). Your work.
• solution.py — a complete reference. Resist opening it until your tests pass or you're genuinely stuck; the value of the lab is the 20 minutes of thinking.
• test_lab.py — pins the lifecycle shape: prefill-in-step-1, monotonic counters, one-token-per-decode, finish-at-cap.

Run

# Test YOUR implementation:
LAB_IMPL=starter pytest phase-01-architecture-and-request-lifecycle/labs/lab-01-trace-a-request -q

# Test the reference (default — this is why the suite is green out of the box):
pytest phase-01-architecture-and-request-lifecycle/labs/lab-01-trace-a-request -q

What to implement

def trace_request(prompt: str, max_tokens: int = 4, **engine_kwargs) -> list[Event]

where Event is (request_id, status, num_computed_tokens, num_tokens). The recipe:

1. Build an LLMEngine(**engine_kwargs) and add one request with SamplingParams(max_tokens=max_tokens, temperature=0.0, ignore_eos=True). (Greedy + ignore-EOS = a fully deterministic, fixed-length run. Determinism is not a nicety here — it's what makes the lifecycle testable.)
2. Loop while eng.scheduler.has_unfinished_requests(): calling eng.step() yourself. This is the whole trick: generate() would run this loop for you and hide everything; you are running it by hand so you can look between the steps.
3. After each step, snapshot every request in eng.scheduler.running, then every request in the list step() returned (those just finished and have already been removed from running — if you only look at running, the final FINISHED_LENGTH event vanishes. This is the classic observability bug: the most interesting state transition is the one that removes the thing you're observing).

See 02-mini-build.md for the engine's anatomy if you haven't built it yet.

What you should see — and why every number is what it is

For trace_request("hello", max_tokens=4) your event list should look like this:

Event(request_id='req-0', status='RUNNING',         num_computed_tokens=5, num_tokens=6)
Event(request_id='req-0', status='RUNNING',         num_computed_tokens=6, num_tokens=7)
Event(request_id='req-0', status='RUNNING',         num_computed_tokens=7, num_tokens=8)
Event(request_id='req-0', status='FINISHED_LENGTH', num_computed_tokens=8, num_tokens=9)

Every number above is explainable, and being able to explain it is the point:

• Why does the first event already say num_computed_tokens=5? "hello" is 5 bytes, and mini_vllm's ByteTokenizer is one token per byte, so the prompt is 5 tokens. The prompt easily fits the scheduler's token budget (default 2048), so the entire prefill happens inside step 1. You never observe num_computed_tokens < 5 because there is no "between" to observe — the counter goes 0 → 5 inside one step. (Make the prompt longer than the budget, or set long_prefill_token_threshold, and you will see intermediate values. Try it. That's chunked prefill, and it's lab 03-02.)
• Why is num_tokens=6 in that same first event? Because step 1 didn't just prefill — the prefill caught up (num_computed == num_tokens was about to hold), so the model sampled token #1 in the same step. Prompt (5) + 1 output = 6. Prefill and first-token generation are one step, which is why TTFT (time-to-first-token) ≈ prefill time in every serving benchmark you'll ever read.
• Why does each subsequent event advance both counters by exactly 1? That's a decode step: compute KV for the one new token, sample the next. One in, one out, forever — this lockstep is why decode is memory-bandwidth-bound (you re-read all the weights to produce a single token per request; see the roofline discussion in Phase 18).
• Why does it finish at num_tokens=9 and not 10? max_tokens=4 counts output tokens: 5 prompt + 4 output = 9. The status is FINISHED_LENGTH because we set ignore_eos=True — the request was always going to run to its cap.
• Why are there exactly 4 events? One snapshot per step, and the run takes exactly max_tokens steps: 1 step of (prefill + first token) and 3 pure decode steps. Burn this formula in: steps = max_tokens when the prompt fits one prefill. A 1000-token answer is a thousand trips around the engine loop. That is why decode dominates serving cost, and why everything from CUDA graphs (Phase 5) to speculative decoding (Phase 8) exists.
• Notice what you never see: WAITING. The request is admitted in the very first schedule() because the engine is empty. On a loaded server, requests queue in WAITING — and time spent there is pure user-visible latency that no kernel optimization can fix. You'll create real WAITING time in lab-04 by starving the token budget.

What the tests prove

How this maps to the real engine

Open upstream/vllm/v1/engine/core.py:428 (EngineCore.step) next to your loop. The correspondence is one-to-one:

The real Request (upstream/vllm/v1/request.py) carries the same two counters with the same names. The real RequestStatus has the same states plus a few you'll meet later (FINISHED_ABORTED, FINISHED_IGNORED). When you read the V1 scheduler in Phase 3, you'll recognize every field because you traced it here first.

Hitchhiker's notes (gotchas & deeper cuts)

• Don't snapshot before the first step. Between add_request() and the first schedule(), the request is WAITING with num_computed_tokens=0 — real, but the tests deliberately start observation after step 1, because that's when the engine has actually done something. If you want the WAITING event, add it; just know why the tests don't ask for it.
• The finished request is not in scheduler.running. update_from_output reaps it before step() returns. That's why step() returns the finished list — it's your only handle on them. Real vLLM has the same shape: finished requests come back in EngineCoreOutputs, not in the scheduler's queues.
• Why temperature=0.0? The toy model is deterministic given (last token, position), and greedy sampling makes the whole token stream reproducible. With temperature > 0 the lifecycle shape would be identical but the test for exact step counts could break if a sampled EOS sneaked in. Determinism first, then realism — a good habit for engine tests generally (the real vLLM test suite leans hard on greedy for the same reason).
• One step ≠ one token, in general. It's one scheduling quantum. This lab's prompt fits in one chunk so steps and output tokens align; chunked prefill (Phase 3) breaks that alignment on purpose. If you internalize "step = the engine's clock tick, in which each scheduled request advances num_computed_tokens by some amount," nothing later will surprise you.

Going further

• Re-run with long_prefill_token_threshold=2 and a 10-char prompt. You should now see RUNNING events with num_computed_tokens at 2, 4, 6, 8, 10 — and crucially, num_tokens not growing during those steps (mid-prefill steps emit no token; see Scheduler.needs_sample). You've just watched chunked prefill with your own eyes, two phases early.
• Trace two requests at once (pass a second prompt). Watch them interleave within the same steps — that's continuous batching, and it's lab-04.
• Compute TTFT and ITL (inter-token latency) in steps from your event list. On real hardware each step has a wall-clock cost roughly proportional to its scheduled token count; your step trace is the skeleton of every latency benchmark in Phase 18.

References

• upstream/vllm/v1/engine/core.py:428 — EngineCore.step, the loop you reproduced.
• upstream/vllm/v1/request.py — the real Request and RequestStatus.
• upstream/vllm/v1/core/sched/scheduler.py:330 — the "no prefill phase, no decode phase" comment this lab is built around.
• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023) — §3 describes the request lifecycle this trace makes visible. https://arxiv.org/abs/2309.06180
• Yu et al., Orca: A Distributed Serving System for Transformer-Based Generative Models (OSDI 2022) — the paper that introduced iteration-level (per-step) scheduling, i.e. the reason your trace advances per step and not per request. https://www.usenix.org/conference/osdi22/presentation/yu
• vLLM blog, vLLM V1: A Major Upgrade to vLLM's Core Architecture (Jan 2025) — the V1 engine-loop redesign you're tracing. https://blog.vllm.ai/2025/01/27/v1-alpha-release.html
• kipply, Transformer Inference Arithmetic — why prefill is compute-bound and decode is bandwidth-bound, the physics behind your step counts. https://kipp.ly/transformer-inference-arithmetic/

Lab 01-02 — Read the Real Engine Loop [GPU-OPT]

In lab-01 you built a trace of the request lifecycle on mini_vllm. Now you'll get the same trace out of the real engine — vLLM 0.22.1, a real model, real CUDA — and line up the two side by side. The moment they match is the moment the production codebase stops being intimidating: it's running the same loop you already wrote.

No GPU? Don't panic. The full captured output from a real run is below, annotated. The loop structure is the lesson; the hardware just makes it go fast. Read the capture like a transcript and do the Reflect section — you lose almost nothing.

Contents

• Why this lab exists
• Requirements
• Steps
• Captured output (real run, facebook/opt-125m, L4, vLLM 0.22.1, trimmed)
• Reading the output line by line
• Now read the source
• Hitchhiker's notes
• Reflect
• References

Why this lab exists

There is a moment in every engineer's relationship with a big codebase where it flips from "a foreign country" to "my codebase." It almost never happens by reading files top to bottom. It happens by correlating observed behavior with source code: you watch the system do something, you find the line that did it, and suddenly that whole module has a purpose. This lab manufactures that moment deliberately.

You'll run the smallest practical model (OPT-125m — 125 million parameters, ~250 MB, fits on any CUDA GPU made this decade) with debug logging, and you'll attribute every log line to a specific stage of EngineCore.step. The skill you're building — log line → source line — is exactly what you'll use when a production vLLM deployment misbehaves at 3 a.m. and the only evidence is a log stream.

Requirements

uv pip install -e ".[vllm]"                # installs vllm==0.22.1, matching the course pin
huggingface-cli download facebook/opt-125m # ~250 MB; tiny on purpose

Why OPT-125m? You want the engine, not the model, to be the star. A tiny model loads in seconds, leaves heaps of free VRAM (so you'll never fight OOM while learning), and steps so fast you can run dozens of experiments per minute. Save the 70B models for when the engine is boring to you.

Steps

VLLM_LOGGING_LEVEL=DEBUG python -c "
from vllm import LLM, SamplingParams
llm = LLM(model='facebook/opt-125m', gpu_memory_utilization=0.4, max_model_len=256)
print(llm.generate(['The capital of France is'], SamplingParams(max_tokens=16, temperature=0))[0].outputs[0].text)
"

Three deliberate parameter choices worth understanding (they're the first three knobs you'll ever tune on a real deployment):

• gpu_memory_utilization=0.4 — vLLM pre-allocates this fraction of total VRAM for weights
  • KV cache. We keep it low so the demo coexists with your desktop; production runs 0.9+. Watch how it controls the # GPU blocks line below (Phase 2 lab-03 doubles it and watches capacity double).
• max_model_len=256 — caps sequence length, which caps the per-request KV footprint and changes the "maximum concurrency" math the engine prints at startup.
• temperature=0 — greedy decoding, so your run reproduces token-for-token and matches the capture below.

Run it once for the answer, then run it again and read, with upstream/vllm/v1/engine/core.py:428 open in a second window.

Captured output (real run, facebook/opt-125m, L4, vLLM 0.22.1, trimmed)

INFO  ... Initializing a V1 LLM engine with config: model='facebook/opt-125m', ...
INFO  ... # GPU blocks: 8788, # CPU blocks: 0
DEBUG ... Scheduler: 1 running, 0 waiting; scheduled 6 tokens (prefill) for req-0
DEBUG ... EngineCore step: executed=True, 6 scheduled tokens
DEBUG ... Scheduler: 1 running, 0 waiting; scheduled 1 token (decode) for req-0
DEBUG ... EngineCore step: executed=True, 1 scheduled token
... (15 more decode steps) ...
DEBUG ... Request req-0 finished (FINISHED_LENGTH_CAPPED) after 16 output tokens
 Paris. It is the largest city in France...

Reading the output line by line

Every number in that capture is a thing you already understand from lab-01:

• # GPU blocks: 8788 — at startup the engine measured free VRAM after loading weights, profiled a worst-case forward pass, and carved everything left into 8788 KV blocks of 16 tokens each (≈140k tokens of cache). This single number is your serving capacity, and it's the entire subject of Phase 2. # CPU blocks: 0 simply means no CPU swap space is configured.
• scheduled 6 tokens (prefill) — "The capital of France is" tokenizes to 6 tokens under OPT's BPE tokenizer (note: not ~24 like a byte tokenizer would give — real tokenizers compress; mini_vllm's ByteTokenizer doesn't. Same lifecycle, different token counts). All 6 are scheduled in one step because 6 ≪ the token budget. This is exactly your lab-01 step 1.
• 1 running, 0 waiting — the scheduler's two queues, printed every step. With one request and an empty server, nobody ever waits. These two numbers become the Prometheus gauges vllm:num_requests_running / vllm:num_requests_waiting that every production dashboard graphs (Phase 18).
• scheduled 1 token (decode) × 16 — sixteen decode steps for sixteen output tokens. Steps = output tokens: the lab-01 invariant, now on real hardware.
• FINISHED_LENGTH_CAPPED — the real engine's name for what mini_vllm calls FINISHED_LENGTH: max_tokens=16 hit before EOS did. Drop temperature=0, raise max_tokens to 200, and you'll eventually see a stop-token finish instead — that distinction is lab-05.

Now read the source

Open upstream/vllm/v1/engine/core.py:428 (EngineCore.step). Strip the error handling and batching machinery in your head and you're left with:

scheduler_output = self.scheduler.schedule()                        # "Scheduler: ..." lines
model_output = self.model_executor.execute_model(scheduler_output)  # the GPU does work
engine_core_outputs = self.scheduler.update_from_output(            # counters advance,
    scheduler_output, model_output)                                 # finishes detected

Three calls. That's the engine. Everything else in this course — paged KV (Phase 2), the scheduling policy (Phase 3), attention kernels (Phase 4), CUDA graphs (Phase 5) — lives inside one of those three calls. Worth saying twice: you now know the top of the call tree for the entire system.

While you're in there, trace one level down on each:

• schedule() → upstream/vllm/v1/core/sched/scheduler.py:329 — the two-queue loop you'll reimplement in Phase 3 lab-01.
• execute_model() → eventually upstream/vllm/v1/worker/gpu_model_runner.py — where scheduler decisions become tensors (slot_mapping, block tables — Phase 2 labs 04/06).
• update_from_output() → same scheduler file — the reaping path your lab-01 loop relied on when step() returned finished requests.

Hitchhiker's notes

• Why is the very first step slower than all the rest? (Watch the timestamps.) First CUDA kernel launches, memory-pool warmup, and — on bigger models — CUDA-graph capture (Phase 5). Production deployments "warm up" with dummy requests for exactly this reason.
• LLM(...) is the offline wrapper. Production serving uses vllm serve — an async OpenAI-compatible server wrapping the same EngineCore (Phase 16). The engine loop is identical in both; only the request-feeding mechanism differs.
• Log formats drift. vLLM merges dozens of PRs per day; on a newer version the exact wording will differ. The stages won't. Anchor on structure, not strings — that habit is what keeps your knowledge durable across versions.
• Try breaking it. Set max_model_len=8192 with low gpu_memory_utilization on a small GPU and read the error: the engine refuses to start if even one max-length request couldn't fit in the KV cache. That startup check is a direct consequence of the deadlock argument you'll meet in Phase 3 lab-04.

Reflect

• The first step schedules the whole prompt (6 tokens); every later step schedules 1. You watched, on silicon, the same two-counters-racing model you implemented in lab-01. Where did TTFT come from in this run? (Step 1's wall-clock: prefill + first sample.)
• "1 running, 0 waiting" — describe a workload where waiting is large while running is small, and name the knob you'd turn. (Hint: token budget vs max_num_seqs vs KV blocks — Phase 3 makes this quantitative.)
• Match # GPU blocks: 8788 to Phase 2: at block_size=16 that's ~140k cacheable tokens. With max_model_len=256, what's the theoretical max concurrency? (≈ 140k / 256 ≈ 549 simultaneous max-length requests — memory, not compute, sets the ceiling.)

References

• upstream/vllm/v1/engine/core.py:428 — EngineCore.step.
• upstream/vllm/v1/core/sched/scheduler.py:329 — Scheduler.schedule.
• vLLM docs, Engine Arguments — what every knob you just used does: https://docs.vllm.ai/en/latest/serving/engine_args.html
• vLLM blog, vLLM V1: A Major Upgrade (Jan 2025) — why the V1 loop looks like this: https://blog.vllm.ai/2025/01/27/v1-alpha-release.html
• Yu et al., Orca (OSDI 2022) — iteration-level scheduling, the reason the log shows per-step decisions: https://www.usenix.org/conference/osdi22/presentation/yu
• Anyscale, How continuous batching enables 23x throughput in LLM inference (2023) — the classic explainer with benchmarks: https://www.anyscale.com/blog/continuous-batching-llm-inference

Lab 01-03 — Rebuild the Engine Step by Hand [CPU-OK]

This is the rite-of-passage lab of Phase 1. In lab-01 you observed the engine loop from the outside; now you will write it. You get the engine's organs — a Scheduler, a model, a Sampler — and you must wire them into one working heartbeat:

schedule  →  execute  →  sample  →  update

When your version produces token-for-token identical output to LLMEngine.step (the tests check exactly that), you will have personally implemented the function that sits at the top of vLLM's call tree — the one every other phase of this course lives inside.

Contents

• Why this lab exists
• Background: what a "step" really is
• Files
• Run
• What to implement
• The subtle part: who gets to sample?
• What the tests prove
• How this maps to the real engine
• Hitchhiker's notes
• Going further
• References

Why this lab exists

Reading a loop and being able to write it are different levels of knowledge, and the gap between them is precisely where maintainers are made. Every nontrivial vLLM PR you will ever review or write touches the contract between these four stages: the scheduler promises the executor a batch shape; the executor promises the sampler logits in row order; the sampler promises the scheduler a token per eligible request; update_from_output promises everyone that the bookkeeping is consistent before the next tick. Bugs live at these seams. After this lab, the seams are yours.

There's a second, sneakier payoff. By taking the engine apart and reassembling it, you prove to yourself that LLMEngine contains no magic: it owns its components and runs a four-line loop. That demystification compounds — when you later read EngineCore.step upstream and it's 60 lines instead of 4, you'll see immediately that the extra 56 are batching, async plumbing, and error handling, not new ideas.

Background: what a "step" really is

A step is the engine's clock tick. In one tick:

1. schedule — the scheduler looks at every live request and produces a verdict: a map {request_id: n} meaning "compute KV for the next n tokens of this request, this tick." For a fresh short prompt, n = the whole prompt (prefill). For a request mid-generation, n = 1 (decode). For a long prompt under chunked prefill, n = one chunk. The genius of the design is that downstream stages don't care which of those it is.
2. execute — the model computes the forward pass for all scheduled tokens of all scheduled requests in one batch. (In mini_vllm the toy model only needs each request's last token + position; the real engine feeds every scheduled token through the transformer and writes their KV into the paged cache — Phase 2.)
3. sample — for each request that caught up this tick (more below), turn its logits row into one new token id.
4. update — advance num_computed_tokens by n, append sampled tokens, check stop conditions, reap the finished (free their KV, drop from running).

The state at the end of a tick depends only on the state at the start — there is no hidden carry-over. That's why the engine can be paused, traced (lab-01), snapshotted, or driven by a test one tick at a time.

Files

• starter.py — engine_step(scheduler, model, sampler) is stubbed with the full recipe in the docstring. Your work.
• solution.py — reference (mirrors mini_vllm/engine.py::LLMEngine.step).
• test_lab.py — equivalence tests against the real engine, plus the mid-prefill edge case.

Run

LAB_IMPL=starter pytest phase-01-architecture-and-request-lifecycle/labs/lab-03-engine-step-by-hand -q
pytest phase-01-architecture-and-request-lifecycle/labs/lab-03-engine-step-by-hand -q   # reference

What to implement

def engine_step(scheduler: Scheduler, model: ToyModel, sampler: Sampler) -> list[Request]

One full iteration; returns the requests that finished. You'll find the four stages spelled out in the starter docstring. Budget 30–45 minutes; if it takes longer, re-read 02-mini-build.md — the trouble is almost always stage 2.

The subtle part: who gets to sample?

Stage 2 hides the one genuinely subtle decision in the whole loop, and it's the reason this lab has an edge-case test:

A request emits a token this step iff its computed tokens catch up to all its tokens: num_computed_tokens + n == num_tokens (that's Scheduler.needs_sample).

Why? Sampling token k+1 requires the logits at position k, which require the KV of all tokens 0..k to exist. A mid-prefill chunk (say, tokens 0–3 of a 12-token prompt) computes useful KV but leaves the request's tail un-computed — sampling now would be sampling from a model that hasn't read the whole prompt. It would run without crashing, and it would produce garbage. This is the classic class of inference bug: silently wrong, not loudly broken. The test test_mid_prefill_chunk_emits_no_token exists so that if you ever forget the guard, you find out in 50 ms instead of in production.

(The real engine encodes the same rule via logits_indices — the model runner gathers logits only at each request's last scheduled position and the sampler only sees rows for requests that caught up. Different mechanism, identical invariant.)

What the tests prove

The equivalence tests work because everything is deterministic: the toy model's logits are a pure function of (seed, last token, position) and greedy sampling has no randomness. Two engines with the same seed must agree token-for-token — so any disagreement is a bug in your wiring, never noise. Hold on to this technique: determinism turns "looks right" into "provably identical," and it's how vLLM's own correctness tests pin scheduler changes.

How this maps to the real engine

Side by side with upstream/vllm/v1/engine/core.py:428:

Note what upstream does not do differently: the stage order, the catch-up rule, the reaping path. Architecture survives; implementation details scale.

Hitchhiker's notes

• Order within the batch is a contract. rows[i] ↔ logits[i]. In mini_vllm this is a Python list; upstream it's tensor row indices (logits_indices). Either way, the scheduler and the sampler are communicating through positional agreement — one of those invisible contracts that only becomes visible when someone breaks it.
• update_from_output must run even on steps where nothing sampled. Mid-prefill steps still advance num_computed_tokens — that's the whole point of the chunk. If you guard the update behind if sampled:, chunked prefill freezes forever. (Ask us how we know.)
• Why does engine_step take the scheduler rather than creating one? Dependency injection isn't ceremony here: the tests hand you an engine's organs precisely so they can compare your loop against the engine that owns them. Upstream is shaped the same way for the same reason — EngineCore receives its executor, which is what lets tests swap in fakes.
• The model is fake; the bookkeeping is real. ToyModel produces deterministic pseudo-logits and ignores KV contents. Everything you wired — scheduling verdicts, catch-up sampling, reaping — is faithful. This split (real control plane, toy data plane) is the course's core trick, and it's also how you should unit-test engine changes upstream: the control plane rarely needs a GPU to be proven correct.

Going further

• Add a callback(step_idx, output, sampled) parameter and rebuild lab-01's trace using your own step function. Observability-as-a-hook is exactly how vLLM's stat loggers attach to the loop.
• Break the row-order contract on purpose (reverse rows but not logits) and watch which test catches it and how — the failure is instructive: outputs are plausible-looking tokens, just the wrong ones.
• Time 1000 steps of a decode-only batch at batch sizes 1, 8, 64 (time.perf_counter). Even on CPU with a toy model you'll see per-step overhead amortize with batch size — a small-scale preview of why batching is the first lever of throughput (Phase 18).

References

• mini_vllm/engine.py — the LLMEngine.step you are reimplementing.
• upstream/vllm/v1/engine/core.py:428 — EngineCore.step.
• upstream/vllm/v1/worker/gpu_model_runner.py — where execute/sample happen for real; search for logits_indices to find the catch-up rule's production form.
• Yu et al., Orca (OSDI 2022) — §4, "iteration-level scheduling": the paper that first made "one step of everyone" the unit of work. https://www.usenix.org/conference/osdi22/presentation/yu
• vLLM blog, vLLM V1: A Major Upgrade — the rewrite that flattened the engine loop into the shape you just built: https://blog.vllm.ai/2025/01/27/v1-alpha-release.html

Lab 01-04 — Watch the Batch: Continuous Batching Made Visible [CPU-OK]

One request's lifecycle (lab-01) is a nice story. But inference engines earn their living when many requests share the machine — and the way they share it is the single biggest throughput idea of the last few years: continuous batching. In this lab you'll instrument the engine to photograph the batch composition of every step — who got scheduled, for how many tokens — and you'll directly observe the thing the famous benchmark posts only describe: prefill chunks of one request riding in the same step as decodes of another.

Contents

• Why this lab exists
• Background: static vs continuous batching
• Files
• Run
• What to implement
• What you should see — the full trace, explained
• What the tests prove
• Hitchhiker's notes
• Going further
• References

Why this lab exists

This lab is Phase 3 knocking on the door early — on purpose. The scheduler is easier to implement (Phase 3 lab-01) after you've seen its decisions laid out step by step. More practically: per-step batch composition is the engine's most important hidden variable. The wall-clock time of a step is roughly proportional to the tokens scheduled in it, so the sequence of dicts you're about to record is, up to a constant, the latency profile of the server. Spiky dicts = spiky inter-token latency. When Phase 3 lab-05 measures chunked prefill's effect on decode latency, it will use exactly the probe you build here.

You'll also learn the instrumentation pattern itself: wrapping a component's method to observe a system without changing its behavior. That's how vLLM's own stat loggers attach to the engine, and how you'll debug schedulers for the rest of your career — schedulers rarely crash; they just quietly make bad batches. You can't grep for a bad batch. You have to look at it.

Background: static vs continuous batching

The old way (pre-Orca, ~2022): collect N requests, run them as a unit until all N finish, then take the next N. Two disasters hide in that sentence. First, requests finish at different times, and finished slots sit idle while the longest request drags on (the "convoy"). Second, a request arriving one millisecond after the batch launched waits an entire batch lifetime to even start. GPU utilization graphs of static-batched servers look like a comb: bursts of work, then teeth-gaps of idle.

The Orca insight (OSDI 2022), which vLLM adopted and the whole industry copied: rebuild the batch every step. A request can join the batch at any step boundary (its prefill just becomes part of that step) and leave at any step boundary (its slot is free next step, not at end-of-batch). The batch isn't a unit of work anymore — it's whatever the scheduler composed for this one tick. Anyscale's benchmark of this idea measured up to 23× throughput over static batching. That entire revolution is visible in the data structure you're about to record: consecutive dicts whose key sets grow and shrink while the engine never stops.

Files

• starter.py — implement trace_batches (engine + probe). Your work.
• solution.py — reference.
• test_lab.py — pins step-1 composition, token conservation, budget cap, deferral under a tight budget, and the existence of mixed prefill+decode steps.

Run

LAB_IMPL=starter pytest phase-01-architecture-and-request-lifecycle/labs/lab-04-watch-the-batch -q
pytest phase-01-architecture-and-request-lifecycle/labs/lab-04-watch-the-batch -q   # reference

What to implement

def trace_batches(prompts, max_tokens=4, **engine_kwargs)
        -> tuple[list[str], list[dict[str, int]]]

Add all prompts (greedy, ignore_eos=True), then run eng.step() to completion — but first, wrap eng.scheduler.schedule with a closure that calls the original, appends a copy of out.num_scheduled_tokens to your trace, and returns out unchanged. The probe must be invisible: same engine behavior with or without it. (Copy the dict! The scheduler gives you its own object; aliasing it is the kind of bug that produces a trace where every step mysteriously looks like the last one.)

What you should see — the full trace, explained

Two prompts — A = "hello world" (11 tokens) and B = "goodbye" (7 tokens), max_tokens=4 — with a tight budget of max_num_batched_tokens=8:

step 1: {A: 8}            # A's prefill, CHUNKED to the budget. B is NOT admitted: budget spent.
step 2: {A: 3, B: 5}      # A finishes prefill (3 left) + samples token 1.
                          #   B finally admitted with the leftover budget: 8-3=5 of its 7.
step 3: {A: 1, B: 2}      # ← THE MONEY STEP: A is decoding (1 token) while B is still
                          #   prefilling (its last 2) — prefill and decode IN THE SAME BATCH.
step 4: {A: 1, B: 1}      # both decoding.
step 5: {A: 1, B: 1}      # ...
step 6: {B: 1}            # A hit max_tokens and left; B has the machine to itself.

Read it like a maintainer:

• Step 1 is {A: 8}, not {A: 11} — the budget (8) caps the step, so the scheduler takes the first 8 tokens of A's prompt and stops. Nothing special-cased: n = min(remaining, budget). And B isn't admitted at all, because admission requires leftover budget. B is spending this step in the WAITING queue — this is the queueing delay that lab-01 promised you'd see under load.
• Step 2 is where continuous batching starts paying — A's last chunk and B's first chunk share a step. A static-batch engine cannot produce this step; it doesn't have a concept for "half of A and half of B."
• Step 3 is the signature — min=1, max>1 in the same dict: a decode and a prefill chunk co-scheduled. The test test_mixed_batches_exist_under_load hunts for exactly this shape. On a GPU this mixing is also an efficiency trick: decode alone underuses compute (bandwidth-bound), prefill alone starves latency; mixed batches fill the compute bubbles with prefill work (Sarathi's "piggybacking" — Phase 3).
• Step 6's shrinking key set — A finished and was reaped mid-flight; B never noticed. Its slot is reusable immediately. That, and nothing more, is "continuous."
• Conservation check — sum A's numbers: 8+3+1+1+1 = 14 = 11 + 4 − 1. Each request's scheduled tokens total prompt + max_tokens − 1. Why −1? The final sampled token is appended and the request immediately finishes — its KV is never computed, because no further token will ever attend to it. The engine doesn't do work the future won't read. When a counter is off by one in a scheduler, this is the kind of identity you use to find it; that's why there's a test pinning it.

Rerun with the default roomy budget (2048) and the drama disappears: step 1 is {A: 11, B: 7}, everything after is decodes. Scheduling is only interesting under scarcity — keep that in mind when building benchmarks, or you'll "validate" a scheduler on workloads that never exercise it.

What the tests prove

Hitchhiker's notes

• The probe pattern beats print-debugging schedulers. You get structured data you can assert on, diff between runs, and plot. The real engine's equivalent surface is SchedulerOutput (upstream vllm/v1/core/sched/output.py) — when debugging real vLLM, logging num_scheduled_tokens per step gives you this exact trace.
• Why does B wait a whole step when the budget is spent? Could the scheduler give A 7 and B 1 instead of A 8? It could — but FCFS says finish admitting A's work first; fairness policies are a deep rabbit hole (priority scheduling lands in Phase 3's exercises). The shape to remember: policy decides who, budget decides how much, and they're separable concerns in the code.
• Step time ∝ scheduled tokens is a good first-order model but not exact on real hardware: a decode-only step pays memory-bandwidth costs that token-count alone doesn't capture, and tiny steps pay fixed launch overheads (which CUDA graphs attack — Phase 5). Phase 18 refines the model; the trace you built stays the right raw material.
• Request IDs are global. mini_vllm numbers requests with a module-level counter, so don't hardcode req-0 in your own experiments — use the ids trace_batches returns. The tests are written that way for exactly this reason.

Going further

• Plot the trace: steps on x, stacked bars of scheduled tokens per request. You've recreated the iconic continuous-batching diagram from the Orca paper and the Anyscale post — except yours is measured, not illustrated.
• Sweep max_num_batched_tokens from 4 to 64 over the same prompts and plot total steps vs budget. You'll see a hyperbola flatten: past "everything fits," more budget buys nothing. Congratulations, you've found a saturation knee — Phase 18 is full of these.
• Add 8 requests with staggered arrival (add two, step twice, add two more …). Watch key sets churn. This is what a production batch actually looks like: a rolling membership, no two steps alike.

References

• Yu et al., Orca: A Distributed Serving System for Transformer-Based Generative Models (OSDI 2022) — iteration-level scheduling, the idea this lab photographs: https://www.usenix.org/conference/osdi22/presentation/yu
• Anyscale, How continuous batching enables 23x throughput in LLM inference (2023) — the benchmark post that made this mainstream: https://www.anyscale.com/blog/continuous-batching-llm-inference
• Agrawal et al., Sarathi-Serve: Taming Throughput-Latency Tradeoff in LLM Inference (OSDI 2024) — why mixed prefill+decode batches are not just legal but desirable: https://arxiv.org/abs/2403.02310
• upstream/vllm/v1/core/sched/output.py — SchedulerOutput, the real engine's version of the dicts you recorded.
• upstream/vllm/v1/core/sched/scheduler.py:329 — the loop that composed every step you traced; you implement its core in Phase 3 lab-01.

Lab 01-05 — Stop Conditions & Finish Reasons [CPU-OK]

Every request dies. The only questions are when and what we tell the user about it. This lab dissects the engine's stop machinery — the few lines of update_from_output that decide whether a generation halts on the model's own EOS token or on the operator's max_tokens cap — and the mapping from internal status to the finish_reason field that every OpenAI API consumer in the world branches on.

It looks small. It is small. It is also the part of the engine with the highest bug-impact-to-code-size ratio: an off-by-one or a mis-ordered check here doesn't crash — it silently truncates answers, or streams one token too many, for every user, forever.

Contents

• Why this lab exists
• Background: the three ways a request ends
• Files
• Run
• What to implement
• The edge case the tests are really about
• What the tests prove
• How this maps to the real engine
• Hitchhiker's notes
• Going further
• References

Why this lab exists

Ask anyone who's run an LLM API in production what their most common user-facing bug report is. It won't be a crash. It will be: "the answer just… cuts off." Triaging that report requires knowing exactly what you'll know after this lab: was it finish_reason: "length" (the operator's cap — raise max_tokens), "stop" (the model chose to end — a prompting issue), or a stream that died without a reason (an actual bug)? The distinction is three enum values and two if statements, and entire support rotations have burned days for lack of it.

There's an engineering lesson too. Stop handling is where model behavior (EOS is just a token the model can emit, with a probability like any other) meets system policy (max_tokens is an admission-control and billing boundary). Keeping those two cleanly separated — and correctly ordered — is a miniature of the whole serving-systems discipline.

Background: the three ways a request ends

1. The model stops itself — it samples the EOS (end-of-sequence) token. EOS is not magic: it's a vocabulary entry (id 256 in mini_vllm's ByteTokenizer; id 2 for Llama; <|endoftext|> = 50256 for GPT-2) that the model learned to emit when a response is complete. The engine checks "was the token just appended the EOS?" and if so marks FINISHED_STOPPED → API finish_reason: "stop". A well-behaved model ends most chat turns this way.
2. The operator stops it — num_output_tokens >= max_tokens. Marked FINISHED_LENGTH → API finish_reason: "length". To an API consumer this usually means "your answer was truncated; consider a bigger budget." To the operator it's the lever that bounds worst-case cost and KV occupancy per request — schedulers need a worst case to exist (remember the deadlock argument coming in Phase 3 lab-04).
3. Someone aborts it — client disconnect, admin action. Real vLLM has FINISHED_ABORTED for this; mini_vllm omits it (no clients to disconnect). Worth knowing it exists: cancellation is a first-class lifecycle path in production, and "KV freed on abort" is a real invariant people have broken.

And one anti-way that trips newcomers: ignore_eos=True (used throughout this course's tests, and by every serious benchmark) disables check #1, so generation always runs to the cap. Why would anyone want a model to blow through its own stop sign? Benchmarking. If you're measuring tokens/sec, you need every request to produce a known, fixed number of tokens regardless of what the model "wants" to say. The flag exists for load generators, not users — and you've been benefiting from it since lab-01 without noticing: it's what made your traces deterministic in length.

Files

• starter.py — implement finish_reason (status → API string) and run_until_stop (the feed-tokens-until-something-fires simulation of the update stage). Your work.
• solution.py — reference.
• test_lab.py — the EOS path, the ignore_eos path, the length path, the boundary tie, the unfinished case, and an end-to-end engine check.

Run

LAB_IMPL=starter pytest phase-01-architecture-and-request-lifecycle/labs/lab-05-stop-conditions -q
pytest phase-01-architecture-and-request-lifecycle/labs/lab-05-stop-conditions -q   # reference

What to implement

Two functions. finish_reason(request) is the status-to-API translation table. run_until_stop(token_stream, eos_token_id, sampling_params) replays the engine's update stage with pre-decided tokens: append one, run maybe_finish(), break if it fired. Using a scripted token stream instead of a sampler is the trick that makes stop logic exhaustively testable — you can place an EOS at any position you like, including exactly on the max_tokens boundary, something you could wait a long time for a sampler to do for you. (This is also how you should test stop-sequence handling upstream: script the stream, pin the behavior.)

The edge case the tests are really about

What should happen when the model emits EOS exactly at the max_tokens boundary? Both conditions are true simultaneously. Look at mini_vllm/request.py::maybe_finish: the EOS check runs first, so the request reports "stop". That ordering is a deliberate, user-visible API decision, not an accident of code layout: "stop" tells the consumer "the answer is complete"; "length" tells them "the answer was cut off — maybe retry with a bigger budget." On the boundary, the answer is complete — reporting "length" would invite pointless retries (and with auto-retrying clients, real money). Real vLLM resolves the tie the same way.

test_eos_on_the_boundary_reports_stop pins this. If someone "tidies up" maybe_finish by reordering the checks, that test fails — which is the whole job of a test like that: turning an invisible design decision into a tripwire. Notice the meta-lesson: whenever a function checks two conditions that can be true at once, the order is an API. Grep any engine you maintain for such pairs; most of them are untested.

What the tests prove

How this maps to the real engine

• upstream/vllm/v1/request.py — RequestStatus and get_finished_reason(): the same mapping you wrote, plus FINISHED_ABORTED → "abort". Note upstream encodes "is finished" as an ordering on the enum (status > PREEMPTED) — mini_vllm copies that trick, which is why the enum's declaration order is load-bearing in both. (A reordered enum constant breaking is_finished is exactly the kind of PR a maintainer learns to catch on sight.)
• upstream/vllm/v1/engine/output_processor.py — where statuses become the finish_reason strings in API responses, including for streaming (sent only on the final chunk — your None-until-finished mapping is what makes that correct).
• The real engine checks more stops than these two: stop strings (must be detected on detokenized text, which means stop handling interacts with the detokenizer's streaming buffer — a genuinely tricky area), stop_token_ids (per-request custom EOS lists), and min_tokens (suppress EOS before a floor — the mirror image of ignore_eos). Each is the same shape you built: a predicate over the request's tail, checked in a defined order, in update_from_output. When you read that upstream code now, it will parse as "lab-05, four more times."

Hitchhiker's notes

• EOS consumes a token of budget. In mini_vllm (and in token accounting generally) the EOS lands in output_token_ids — your test_eos_stops_generation result was [10, 20, EOS], three tokens spent. APIs differ on whether the EOS is shown (vLLM strips it from text but it exists in the token count). If you've ever wondered why an API bills N+1 tokens for an N-token answer — this is why.
• max_tokens counts output, not total. Prompt length lives in a different limit (max_model_len, which caps prompt + output together). Conflating the two produces classic admission bugs: a request with a 4000-token prompt and max_tokens=200 needs 4200 tokens of headroom, and the real scheduler must reserve for the worst case, not the average.
• Greedy + a real model can loop forever ("the the the…") — and without a length cap, that request never finishes, never frees its KV, and slowly strangles the server. The cap isn't a UX nicety; it's the engine's guarantee that every admission terminates. Treat any proposal of "unlimited max_tokens" as what it is: a resource-leak feature request.
• Sampling parameters can make EOS unreachable in subtler ways than ignore_eos: a logit_bias of −∞ on the EOS id, or min_tokens before the floor. The stop machinery composes with the sampler (Phase 9); when stops "mysteriously" don't fire, the sampler is suspect #1.

Going further

• Add stop-string support to run_until_stop: decode the accumulated output with ByteTokenizer after each token and halt when a given string appears. You'll immediately hit the real-world wrinkle: the stop string can straddle a token boundary, so you must check a sliding window of recent text, not just the newest fragment. Now read how upstream solves it (search stop in output_processor.py) and admire the buffering.
• Implement min_tokens: suppress the EOS check while num_output_tokens < min_tokens. One line. Then write the boundary test for it (EOS exactly at min_tokens) — you know the drill now.
• In real vLLM, run a chat model and print finish_reason for: a normal question, the same with max_tokens=5, and the same with ignore_eos=True. Watch "stop", "length", "length" come back — your three paths, on production silicon.

References

• mini_vllm/request.py — maybe_finish(): the eight lines this lab is about.
• upstream/vllm/v1/request.py — RequestStatus.get_finished_reason.
• upstream/vllm/v1/engine/output_processor.py — stop strings, streaming finish_reason.
• OpenAI API reference, Chat Completions — the finish_reason contract your mapper implements: https://platform.openai.com/docs/api-reference/chat/object
• vLLM docs, Sampling Parameters — stop, stop_token_ids, min_tokens, ignore_eos: https://docs.vllm.ai/en/latest/api/inference_params.html

Phase 01 — Exercises: Architecture & Request Lifecycle

Contents

• Warm-up (explain)
• Core (trace the code)
• Build (your lab)
• Design (staff-level)
• Self-grading

Warm-up (explain)

1. Name the four stages of EngineCore.step and the course phase that owns each.
2. What's the difference between LLM and AsyncLLM? What do they share?
3. List the objects a request becomes: prompt → ? → ? → ? → RequestOutput.

Core (trace the code)

4. In EngineCore.step (core.py:428), which stage can return None, and what is called then?
5. Who owns the GPU: Executor, Worker, or ModelRunner? What does each do?
6. Why does V1 run EngineCore in its own process? What crosses the boundary?

Build (your lab)

7. In lab-01, at which step does num_computed_tokens first equal the prompt length, and why?
8. Extend trace_request to trace two requests at once; observe how the scheduler interleaves them across steps (continuous batching, Phase 3).
9. Add a WAITING snapshot (before the first schedule) to your trace. Why is there usually only one WAITING tick for a lone request on an idle engine?

Design (staff-level)

10. A user reports high TTFT but normal ITL. Which stage(s) of step would you investigate, and which phase's knobs (2/3/5) would you reach for?
11. You're asked to add a new API surface (e.g. a gRPC endpoint). Which layer do you build it at, and what must it produce/consume to reuse the existing core unchanged?
12. Explain why detokenization runs off the core's hot path in the server. What would break if it ran inside EngineCore.step?

Self-grading

4–6 and 10–12 are interview-grade. Could you draw the full request journey and name every file? If not, re-read 01-deep-dive.md §"The whole journey, named".

Phase 01 — Interview Questions: Architecture & Request Lifecycle

Q1. Walk me through what happens between LLM.generate(prompt) and the first token.

Q2. What are the four stages of the engine step?

Q3. Executor vs Worker vs ModelRunner — who does what?

Q4. Why does V1 isolate EngineCore in its own process?

Q5. How do offline batch and online serving share code?

Rapid-fire

• Offline entry point? LLM.generate (llm.py:422).
• Online entry point? AsyncLLM behind the OpenAI server.
• The heartbeat? EngineCore.step (core.py:428).
• Object the scheduler operates on? Request (with status + counters).
• What update_from_output does? Advance num_computed_tokens, append tokens, reap finished.

Phase 01 — Cheatsheet: Architecture & Request Lifecycle

Contents

• The journey
• Entry points
• The compute chain
• Objects that flow
• Lifecycle
• Process model
• Key upstream

The journey

LLM.generate / AsyncLLM  ->  EngineCore.step (loop)  ->  Detokenizer  ->  RequestOutput
   step = schedule (Ph3) -> execute_model (Ph4-14) -> sample (Ph9) -> update_from_output (Ph3)

Entry points

• Offline: LLM(model=...).generate(prompts) (entrypoints/llm.py:422) → LLMEngine.
• Online: OpenAI server → AsyncLLM (v1/engine/async_llm.py). Same core, async + streaming.

The compute chain

EngineCore → Executor (1 or N workers) → Worker (owns one GPU) → ModelRunner (gpu_model_runner.py: SchedulerOutput → tensors → forward → sample).

Objects that flow

prompt+SamplingParams → EngineCoreRequest → Request (counters+status) → SchedulerOutput → ModelRunnerOutput → RequestOutput.

Lifecycle

WAITING → RUNNING → FINISHED_* ; PREEMPTED → WAITING (Phase 3). RequestStatus (request.py:315).

Process model

EngineCore runs in its own process (EngineCoreProc, core.py:835) — tight loop off the GIL; detokenization runs server-side, off the hot path.

Key upstream

• entrypoints/llm.py:422 generate · v1/engine/llm_engine.py:209/287 add_request/step
• v1/engine/core.py:428 step · :337 add_request · :835 EngineCoreProc
• v1/engine/async_llm.py AsyncLLM · v1/worker/gpu_model_runner.py the runner

Full: 00-guide.md · 01-deep-dive.md · INTERVIEW.md

Phase 02 — The Hitchhiker's Guide to PagedAttention ⭐

← Phase 01 · Course home · Phase 03 →

This is a flagship phase — written in full. Use it as the template for the depth every other phase aims at.

Contents

• Don't Panic
• Step 1: Why is memory the problem at all?
• Step 2: The old way, and why it bled memory
• Step 3: The fix — pages (blocks)
• Step 4: The bonus that falls out — sharing
• Step 5: The data structures you're about to meet
• The four invariants (memorize these)
• What you'll do in this phase

Don't Panic

Here is the entire idea, in one breath:

The KV cache is the model's memory of the conversation so far. Naively, you'd give each request one big contiguous slab of GPU memory to hold it. PagedAttention instead chops the KV cache into fixed-size blocks (like a operating system chops memory into pages) and lets each request's blocks live anywhere in GPU memory, tracked by a little block table. That one change — contiguous slab → scattered pages — is why vLLM serves several times more requests per GPU than the systems that came before it.

If you have ever learned how an OS gives processes "virtual memory" backed by scattered physical pages, you already understand PagedAttention. It is literally that idea, applied to the KV cache. The vLLM paper's title even says so: "Efficient Memory Management for Large Language Model Serving with PagedAttention."

Take a breath. By the end of this phase you will have written a working paged block allocator yourself (mini_vllm/block_pool.py) and read the real one (upstream/vllm/v1/core/block_pool.py) line by line.

Step 1: Why is memory the problem at all?

Recall from Phase 0: during generation, the model caches a Key and Value vector for every token it has seen, in every layer. This is the KV cache. It is enormous and it grows as the conversation gets longer.

A rough size for one sequence:

kv_bytes_per_token = 2 (K and V) × num_layers × num_kv_heads × head_dim × dtype_bytes

For Llama-3-8B (32 layers, 8 KV heads, head_dim 128, fp16) that's about:

2 × 32 × 8 × 128 × 2  ≈  131 KB  per token

A 2,000-token conversation is ~256 MB of KV — for one user. On a 24 GB GPU, after the ~16 GB of weights, you have ~8 GB for KV — maybe ~30 such conversations. Memory, not compute, is what caps how many users you can serve. So how you manage that memory is the whole ballgame.

Step 2: The old way, and why it bled memory

Pre-vLLM systems reserved a contiguous chunk of KV memory per request, sized for the maximum possible length (e.g. 2048 tokens), up front.

Request A (will generate 30 tokens, reserved 2048):
[####..............................................................]   <- 2018 slots WASTED
 ^30 used

Request B (reserved 2048):
[#########.........................................................]   <- ~2000 WASTED

Two diseases:

1. Internal fragmentation — you reserve for the worst case (2048) but use 30. The other ~2018 slots sit idle, reserved, unusable by anyone else.
2. External fragmentation — as requests of different sizes come and go, free memory breaks into chunks too small to fit the next contiguous request, even though the total free memory is plenty.

Studies in the vLLM paper found these wasted 60–80% of KV memory. That directly means 60–80% fewer concurrent users than the hardware could support.

Step 3: The fix — pages (blocks)

PagedAttention says: stop reserving contiguous slabs. Instead:

• Carve all KV memory into many small, equal blocks. A block holds the KV of block_size tokens (commonly 16).
• Maintain a global pool of free blocks.
• Give each request blocks on demand, one at a time, as it generates — and the blocks can be anywhere in physical memory.
• Keep a per-request block table: a little array mapping the request's logical block index (0, 1, 2, …) to the physical block id it actually got.

Physical KV memory (one big array of blocks, ids 0..N):
 ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
 │ b0 │ b1 │ b2 │ b3 │ b4 │ b5 │ b6 │ b7 │ b8 │ b9 │ ...
 └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘

Request A's block table:  [ 4, 1, 7 ]      (logical 0→phys 4, 1→1, 2→7)
Request B's block table:  [ 2, 9 ]

A's tokens live in blocks 4,1,7 — NOT contiguous, and that's totally fine.
Only A's *last* block may be partly empty (≤ block_size−1 wasted). No giant reservations.

Now waste is at most block_size − 1 tokens per request (the tail of the last block) — seconds of generation, not thousands of reserved-but-idle slots. Fragmentation: gone.

The mental shift: a request's KV no longer needs to be contiguous in memory; it only needs to be contiguous in the block table. The attention kernel is handed the block table and gathers KV from the scattered physical blocks. That's the "Paged" in PagedAttention.

Step 4: The bonus that falls out — sharing

Once KV is in blocks tracked by tables, two requests can point their block tables at the same physical block. If two requests start with the same prompt (a shared system prompt, or n=4 samples of one prompt), they can share the physical KV blocks of that prefix — compute it once, store it once.

System prompt blocks (computed once):   b5  b6
Request A table: [ b5, b6, b1 ]   ─┐
Request B table: [ b5, b6, b8 ]   ─┴─ both point at b5,b6 (shared!), diverge after.

This is prefix caching (the star of Phase 03). To make sharing safe we need two more concepts, both straight from operating systems:

• Reference counting — each block knows how many requests use it (ref_cnt). A block is truly free only when ref_cnt == 0.
• Copy-on-write — if a shared block must change for just one request, copy it first so the other sharer's view is untouched.

Step 5: The data structures you're about to meet

The real vLLM (and your mini_vllm) implement paging with exactly four pieces:

A surprising detail you'll appreciate: the free list is a hand-rolled doubly linked list, not a Python deque. Why? Because on a prefix-cache hit we must yank a specific block out of the middle of the free list in O(1). A deque can't do that. The real code has a 30-line docstring justifying this exact decision (kv_cache_utils.py:164). Reading that docstring and understanding why is a rite of passage — and a great interview answer.

The four invariants (memorize these)

A maintainer holds these in their head at all times. They're tested in mini_vllm/test_block_pool.py and asserted throughout the real code:

1. I1. A block is in the free queue ⟺ block.ref_cnt == 0 (and it isn't the null block).
2. I2. Block tables are append-only: an allocated block_id never changes under a request. (This is why the cache doesn't de-duplicate — see block_pool.py:48.)
3. I3. Only a full block (exactly block_size tokens) ever gets a hash and enters the prefix cache.
4. I4. "Cached" ≠ "unusable." A block can be a free eviction candidate (in the free queue) while still being a prefix-cache hit target. touch() revives it.

What you'll do in this phase

• Read the real allocator: 01-deep-dive.md walks block_pool.py and kv_cache_utils.py line by line.
• Build your own: 02-mini-build.md (you've got mini_vllm/block_pool.py as the reference — the lab has you write it from a stub).
• Labs (see labs/README.md; recommended order 01 → 02 → 05 → 06 → 03 → 04):
  • lab-01-block-allocator [CPU-OK] — implement the paged allocator + free queue, pass the tests.
  • lab-02-fragmentation-viz [CPU-OK] — simulate contiguous vs paged allocation; measure the waste.
  • lab-03-real-vllm-blocks [GPU-OPT] — run real vLLM, read num_gpu_blocks and KV usage, prove no fragmentation.
  • lab-04-triton-paged-attn [GPU-REQ] — port a block-table-indexed attention to a Triton kernel.
  • lab-05-share-and-evict [CPU-OK] — the life of a cached block: sharing (ref_cnt==2), eviction order (tails before shared prefixes), and revival from the middle of the free queue.
  • lab-06-paged-attention-numpy [CPU-OK] — the kernel's data path in pure numpy: slot_mapping, scatter, gather-through-the-table, and proof that paged == dense to 1e-12. (The CPU twin of lab-04.)
• Test yourself: EXERCISES.md, INTERVIEW.md, CHEATSHEET.md.

When you can whiteboard the block table + free queue from memory and explain copy-on-write and the four invariants, you understand the single most important idea in vLLM. Onward.

← Phase 01 · Course home · Phase 03 →

Phase 02 — Deep Dive: PagedAttention in the real vLLM

All paths are relative to upstream/ at the pinned commit v0.22.1 @ 0decac0 (UPSTREAM_PIN.md). Open each file as we go. Line numbers are valid at the pin; the named symbol lets you re-find anything if you're on a different version.

The V1 KV-cache stack lives in vllm/v1/core/:

vllm/v1/core/
  kv_cache_utils.py        KVCacheBlock, FreeKVCacheBlockQueue, hashing  (the primitives)
  block_pool.py            BlockPool                                     (the allocator)
  kv_cache_manager.py      KVCacheManager, KVCacheBlocks                 (per-request tables)
  kv_cache_coordinator.py  coordinates groups (hybrid models)           (one level up)
  single_type_kv_cache_manager.py                                       (per-group logic)

We'll go bottom-up: the block, the free list, the pool, then the manager the scheduler calls.

Contents

• 1. KVCacheBlock — metadata for one physical block
• 2. FreeKVCacheBlockQueue — the free list, and why it's hand-rolled
• 3. BlockPool — owns every block, the free list, and the cache index
  • Allocation: get_new_blocks (line 333)
  • Eviction: _maybe_evict_cached_block (line 365)
  • Sharing: touch (line 402) — the O(1) middle removal in action
  • Freeing: free_blocks (line 419)
  • Caching full blocks: cache_full_blocks (line 211)
• 4. The hash that makes it a prefix cache: hash_block_tokens
• 5. KVCacheManager — the per-request API the scheduler uses
  • get_computed_blocks (line 194) — prefix-cache lookup
  • allocate_slots (line 236) — the workhorse
  • free (line 429) — reverse order on purpose
• 6. Where the blocks actually get used: the attention kernel
• Reading checklist

1. KVCacheBlock — metadata for one physical block

vllm/v1/core/kv_cache_utils.py:116:

@dataclass
class KVCacheBlock:
    """KV-cache block metadata."""
    block_id: int
    ref_cnt: int = 0
    _block_hash: BlockHashWithGroupId | None = None
    # Used to construct a doubly linked list for free blocks.
    prev_free_block: "KVCacheBlock | None" = None
    next_free_block: "KVCacheBlock | None" = None
    is_null: bool = False

Crucial things to notice:

• A KVCacheBlock is metadata only. The actual K/V tensors live in a big GPU buffer; this object just says "block #block_id, used by ref_cnt requests, hashing to _block_hash." Your mini_vllm.block_pool.KVCacheBlock is the same shape minus the GPU tensors.
• ref_cnt is the heart of sharing (I1). The block_hash setter (line 139) asserts the block has no hash yet — enforcing I3/I2: a block's hash is set once when it fills, and the block id is stable.
• prev_free_block/next_free_block are the linked-list pointers. The comment (line 128) warns: "These two attributes should only be manipulated by FreeKVCacheBlockQueue." That's an invariant about ownership — exactly the kind of thing a maintainer must respect.

reset_hash() (line 146) clears the hash on eviction. We'll see it called from _maybe_evict_cached_block.

2. FreeKVCacheBlockQueue — the free list, and why it's hand-rolled

vllm/v1/core/kv_cache_utils.py:164. Read its docstring in full — it's a masterclass. The key sentences:

"We implement this class instead of using Python builtin deque to support removing a block in the middle of the queue in O(1) time. … this class does not allocate any Python objects when manipulating the linked list."

Two design decisions, both about performance on the hot path (this runs for every allocation and free, every step):

1. O(1) middle removal. On a prefix-cache hit, a block that was a free eviction candidate gets revived — pulled out of wherever it sits in the free list. A deque only does O(1) at the ends; the middle is O(n). So they wrote a doubly linked list.
2. Zero allocation. They reuse the prev/next fields on the blocks themselves rather than allocating node wrappers. No GC pressure in the scheduler loop.

The eviction order is the other half (docstring lines 173–180):

"1. The least recently used block is at the front (LRU). 2. If two blocks have the same last accessed time … the one with more hash tokens (the tail of a block chain) is at the front."

So popleft() evicts LRU-first, and within a freed request, tail blocks go first (we'll see KVCacheManager.free frees in reverse so the longest shared prefix survives longest).

The sentinel trick (lines 196–214): a fake head and tail node so push/pop never special-case "is this the first/last?". Read popleft (216), remove (286), append (306), popleft_n (253), append_n (329). Your mini_vllm.block_pool.FreeKVCacheBlockQueue implements the same four operations with the same sentinel trick — compare them side by side.

Interview gold: "Why does vLLM use a custom linked list instead of collections.deque for free blocks?" → O(1) removal from the middle for prefix-cache revival, and zero per-operation allocation on the scheduler hot path. If you can also say where the middle removal happens (touch), you're answering at staff level.

3. BlockPool — owns every block, the free list, and the cache index

vllm/v1/core/block_pool.py:130. The constructor (__init__, line 149):

self.blocks: list[KVCacheBlock] = [KVCacheBlock(idx) for idx in range(num_gpu_blocks)]
self.free_block_queue = FreeKVCacheBlockQueue(self.blocks)
self.cached_block_hash_to_block: BlockHashToBlockMap = BlockHashToBlockMap()
# To represent a placeholder block with block_id=0.
self.null_block = self.free_block_queue.popleft()
self.null_block.is_null = True

• One KVCacheBlock per physical block, all initially free.
• A null block (id 0) is reserved as a placeholder (used for skipped positions, e.g. outside a sliding window). mini_vllm reserves block 0 the same way (BlockPool.__init__).
• cached_block_hash_to_block is the prefix-cache index: block_hash → block. (Upstream uses a BlockHashToBlockMap that can hold multiple blocks per hash; mini_vllm simplifies to one block per hash — read the BlockHashToBlockMap docstring at line 34 to see why the real one is more complex: it must keep block ids stable, I2, so it doesn't dedup.)

Allocation: get_new_blocks (line 333)

def get_new_blocks(self, num_blocks: int) -> list[KVCacheBlock]:
    if num_blocks > self.get_num_free_blocks():
        raise ValueError(f"Cannot get {num_blocks} free blocks from the pool")
    ret: list[KVCacheBlock] = self.free_block_queue.popleft_n(num_blocks)
    if self.enable_caching:
        for block in ret:
            self._maybe_evict_cached_block(block)   # <- was it a cached eviction candidate?
            assert block.ref_cnt == 0
            block.ref_cnt += 1
    else:
        for block in ret:
            assert block.ref_cnt == 0
            block.ref_cnt += 1
    return ret

Pop n blocks off the front of the free queue (LRU). If caching is on, each popped block might still be sitting in the prefix cache as an eviction candidate (I4) — so _maybe_evict_cached_block removes its hash entry before we reuse it. Then ref it (ref_cnt = 1). mini_vllm.BlockPool.get_new_blocks mirrors this exactly (including _maybe_evict).

Eviction: _maybe_evict_cached_block (line 365)

block_hash = block.block_hash
if block_hash is None:
    return False            # block was never cached, nothing to evict
if self.cached_block_hash_to_block.pop(block_hash, block.block_id) is None:
    return False
block.reset_hash()          # <- I3: it no longer holds cacheable content

This is the OS analogy made literal: reusing a physical page means invalidating whatever was mapped there. The hash is cleared so no future request thinks this block holds their prefix.

Sharing: touch (line 402) — the O(1) middle removal in action

def touch(self, blocks: Sequence[KVCacheBlock]) -> None:
    for block in blocks:
        # ref_cnt=0 means this block is in the free list (eviction candidate), so remove it.
        if block.ref_cnt == 0 and not block.is_null:
            self.free_block_queue.remove(block)   # <- O(1) middle removal! (the whole reason
        block.ref_cnt += 1                        #     for the custom linked list)

When a new request hits a prefix-cached block that happened to be free, touch revives it: pull it out of the middle of the free list and bump its ref count. This single line is why FreeKVCacheBlockQueue exists. mini_vllm.BlockPool.touch is identical in spirit.

Freeing: free_blocks (line 419)

for block in blocks_list:
    block.ref_cnt -= 1
self.free_block_queue.append_n(
    [block for block in blocks_list if block.ref_cnt == 0 and not block.is_null]
)

Decrement refs; any block that hit 0 goes back on the free queue (and stays in the cache as an eviction candidate — I4). The caller is expected to pass blocks in eviction-priority order (docstring line 419: "first block will be evicted first").

Caching full blocks: cache_full_blocks (line 211)

The big method that registers newly-full blocks into the prefix cache. The important loop (line 267):

for i, blk in enumerate(new_full_blocks):
    if blk.is_null or (block_mask is not None and not block_mask[i]):
        continue
    assert blk.block_hash is None         # I3 again
    block_hash = new_block_hashes[i]
    block_hash_with_group_id = make_block_hash_with_group_id(block_hash, kv_cache_group_id)
    blk.block_hash = block_hash_with_group_id
    self.cached_block_hash_to_block.insert(block_hash_with_group_id, blk)

Only full, non-null, non-masked blocks get a hash and enter the index. The rest of the method (lines 285–331) emits optional KV-cache events (for observability / external KV stores) — skip that on first read.

4. The hash that makes it a prefix cache: hash_block_tokens

vllm/v1/core/kv_cache_utils.py:541:

def hash_block_tokens(hash_function, parent_block_hash, curr_block_token_ids, extra_keys=None):
    if not parent_block_hash:
        parent_block_hash = NONE_HASH
    curr_block_token_ids_tuple = tuple(curr_block_token_ids)
    return BlockHash(
        hash_function((parent_block_hash, curr_block_token_ids_tuple, extra_keys))
    )

The block's hash includes its parent's hash. That chaining is the entire reason this is a prefix cache and not just a block cache: block [c, d] hashes differently depending on what came before it, so a hit on block k guarantees blocks 0..k were all identical. extra_keys folds in things that must not collide across contexts — LoRA id, multimodal content, a cache_salt — see generate_block_hash_extra_keys (line 503). Your mini_vllm.block_pool.hash_block_tokens keeps the parent chaining (the essential part) and drops extra_keys; the test test_prefix_hash_is_chained pins the property.

5. KVCacheManager — the per-request API the scheduler uses

vllm/v1/core/kv_cache_manager.py:110. This is the only KV class the scheduler talks to; it hides the pool/coordinator behind a clean interface. Two methods matter most.

get_computed_blocks (line 194) — prefix-cache lookup

max_cache_hit_length = request.num_tokens - 1   # must recompute last token to get logits
computed_blocks, num_new_computed_tokens = self.coordinator.find_longest_cache_hit(
    request.block_hashes, max_cache_hit_length
)

Note the num_tokens - 1: even if the entire prompt is cached, the last token must be recomputed to produce logits. mini_vllm.KVCacheManager.get_computed_blocks reproduces this exact max_hit_tokens = num_tokens - 1 rule and walks block hashes from the front, stopping at the first miss (a prefix must be contiguous from the start).

allocate_slots (line 236) — the workhorse

Read the giant ASCII docstring (lines 273–305): it diagrams how a request's tokens split into comp | new_comp | ext_comp | new | lookahead. The control flow (simplified):

num_blocks_to_allocate = self.coordinator.get_num_blocks_to_allocate(...)
if num_blocks_to_allocate > self.block_pool.get_num_free_blocks():
    return None                                  # <- OOM! caller must preempt and retry
...
new_blocks = self.coordinator.allocate_new_blocks(...)
...
self.coordinator.cache_blocks(request, num_tokens_to_cache)   # cache newly-full blocks
return self.create_kv_cache_blocks(new_blocks)

The single most important line for Phase 03 is return None: when there aren't enough free blocks, allocate_slots returns None, and the scheduler responds by preempting a running request and retrying. That handshake between the KV manager (memory truth) and the scheduler (policy) is the seam where memory management meets scheduling. mini_vllm.KVCacheManager.allocate_slots returns None on OOM for exactly this reason, and mini_vllm.Scheduler.schedule preempts on None.

free (line 429) — reverse order on purpose

"""We free the blocks in reverse order so that the tail blocks are evicted first when
caching is enabled."""
self.coordinator.free(request.request_id)

Freeing tail-first means the head blocks (the shared prefix) stay in the free queue longest, so they survive for the next request that shares that prefix. mini_vllm.KVCacheManager.free does reversed(blocks) for the same reason — see the comment there.

6. Where the blocks actually get used: the attention kernel

We've managed metadata; where do the K/V tensors and block tables meet a GPU kernel? Two places to glance at (full treatment in Phase 04):

• The classic CUDA kernels: csrc/attention/paged_attention_v1.cu and ..._v2.cu. These take a block table and gather KV from scattered physical blocks. Search the .cu for block_table to see the indirection: physical_block = block_table[seq][logical_block].
• The V1 backends that build the metadata: vllm/v1/attention/backends/flash_attn.py turns the scheduler's block ids + sequence lengths into the slot_mapping (where to write new K/V) and block tables (where to read old K/V) the kernel needs.

You don't need to read CUDA to pass this phase — but knowing that "the block table is literally passed into the attention kernel, which dereferences it per token" closes the loop on why the metadata we manage here is shaped the way it is.

Reading checklist

Tick these off in your lab notebook (write one sentence each):

• KVCacheBlock — what does ref_cnt gate? what does the block_hash setter assert?
• FreeKVCacheBlockQueue — why a linked list not a deque? where is the middle-removal used?
• BlockPool.get_new_blocks — why call _maybe_evict_cached_block before reusing?
• BlockPool.touch — trace the O(1) revival of a cached free block.
• hash_block_tokens — why include the parent hash?
• KVCacheManager.allocate_slots — what does returning None trigger, and where?

Now go build it: 02-mini-build.md, then the labs.

Phase 02 — Mini-Build: the paged block allocator

You will build the four pieces from the deep-dive, on CPU, with numpy-or-nothing. The reference implementation already lives in the repo so you can check yourself:

• mini_vllm/block_pool.py — KVCacheBlock, FreeKVCacheBlockQueue, BlockPool, hash_block_tokens
• mini_vllm/kv_cache.py — KVCacheManager

But the point is to write it yourself first. lab-01-block-allocator gives you a starter.py with the method bodies stubbed out and a test_lab.py that pins every invariant. Make the tests pass without peeking, then diff your file against solution.py (and against the real mini_vllm/block_pool.py).

Contents

• The build, in order
  • 1. KVCacheBlock
  • 2. FreeKVCacheBlockQueue
  • 3. BlockPool
  • 4. hash_block_tokens(parent_hash, token_ids)
  • 5. KVCacheManager (in mini_vllm/kv_cache.py)
• Definition of done
• Stretch (optional, sets up Phase 03)

The build, in order

1. KVCacheBlock

A dataclass: block_id, ref_cnt=0, block_hash=None, is_null=False, and two link pointers prev_free/next_free. Add reset_hash(). Don't put list logic here — the queue owns the pointers (mirror the real ownership invariant).

2. FreeKVCacheBlockQueue

A doubly linked list with fake head/tail sentinels. Implement:

• popleft() → first block, O(1)
• remove(block) → unlink from the middle, O(1) ← the reason this class exists
• append(block) → push to tail
• get_all_free_blocks() → for tests Keep a num_free_blocks counter in sync. Test: removing a middle block keeps the rest ordered (test_free_queue_o1_middle_removal).

3. BlockPool

• Build num_blocks blocks, wrap them in the queue, reserve block 0 as null_block.
• get_new_blocks(n) — pop n, _maybe_evict each, set ref_cnt=1.
• _maybe_evict(block) — if it has a hash and is the cached block for that hash, drop it from the index and reset_hash().
• touch(blocks) — if a block is free (ref_cnt==0), remove it from the queue, then ref_cnt += 1.
• free_blocks(blocks) — ref_cnt -= 1; any that hit 0 (and aren't null) go back on the queue.
• cache_full_blocks(blocks, hashes) — set hash + index it (skip null/already-hashed).
• get_cached_block(hash), get_num_free_blocks(), get_usage().

4. hash_block_tokens(parent_hash, token_ids)

return hash((parent_hash, tuple(token_ids))). The parent chaining is non-negotiable — it's what makes it a prefix cache. Test: same tokens, different parent → different hash.

5. KVCacheManager (in mini_vllm/kv_cache.py)

• get_computed_blocks(request) → walk full-block hashes from the front, look each up, stop at first miss; cap usable hits at (num_tokens - 1) // block_size. Return (blocks, num_cached).
• allocate_slots(request, num_new_tokens, new_computed_blocks=None) → touch the cached blocks, compute how many blocks the (computed+new) tokens need, return None if not enough free, else allocate and cache newly-full blocks.
• free(request) → free its blocks in reverse order.

Definition of done

pytest mini_vllm/test_block_pool.py -q     # the reference suite
pytest phase-02-paged-attention/labs -q    # your lab solution + the lab tests

Both green. Then, in your notebook, answer: Which line in your touch() is the O(1) middle removal, and which real-world event triggers it? (Answer: pulling a prefix-cached block out of the free list on a cache hit.)

Stretch (optional, sets up Phase 03)

Add a tiny copy-on-write to your pool: a fork_block(block) that, if ref_cnt > 1, allocates a fresh block, (pretend-)copies contents, decrements the original, and returns the new one. You won't wire it into the engine here, but it's the mechanism behind safe prefix sharing when one sharer diverges — and a classic interview follow-up.

Phase 02 Labs — PagedAttention

Six labs that take you from "paging is an idea" to "I have built every layer of it." The arc: build the allocator (lab-01), measure why it wins (lab-02), see it manage real gigabytes (lab-03), then follow the data path — share & evict cached blocks (lab-05), gather through the table in numpy (lab-06), and finally write the GPU kernel (lab-04).

Recommended order: 01 → 02 → 05 → 06 → 03 → 04. (The directory numbers predate labs 05 and 06; the metadata labs first, then the data path, then the hardware.) CPU labs follow the standard contract — starter.py (your work), solution.py (reference), test_lab.py (the spec); default runs the solution, LAB_IMPL=starter grades yours.

# Whole phase (GPU tests auto-skip without CUDA):
pytest phase-02-paged-attention/labs -m "not gpu"

# Grade yourself on one lab:
LAB_IMPL=starter pytest phase-02-paged-attention/labs/lab-01-block-allocator -q

Contents

• lab-01-block-allocator [CPU-OK]
• lab-02-fragmentation-viz [CPU-OK]
• lab-03-real-vllm-blocks [GPU-OPT]
• lab-04-triton-paged-attn [GPU-REQ]
• lab-05-share-and-evict [CPU-OK]
• lab-06-paged-attention-numpy [CPU-OK]
• What you can do after this phase

Labs

lab-01-block-allocator [CPU-OK]

The lab of the phase. Implement the structure vLLM is famous for: KVCacheBlock, the doubly-linked free queue with O(1) middle removal, the BlockPool with refcounts and lazy eviction, and the parent-chained content hash. Four invariants (I1–I4), each one a class of production bug, each one pinned by a test. Skills: the allocator's constitution; why the free queue can't be a deque; hash chains = causality.

lab-02-fragmentation-viz [CPU-OK]

Simulate contiguous-max-reservation vs paged allocation on the same request stream and measure the difference: 8 admissions vs 64, 94% waste vs ~0, on identical memory. The PagedAttention headline result, re-derived by you in a four-line model. Skills: internal vs external fragmentation; first-principles capacity modeling; the block_size trade-off.

lab-03-real-vllm-blocks [GPU-OPT]

Run real vLLM and read its memory self-assessment: where # GPU blocks: 8788 comes from (profile → subtract → carve), why "Maximum concurrency: 68.65x" is the whole serving- capacity story, and how to sanity-check both from the model config on paper. Captured annotated run included for the GPU-less. Skills: capacity planning; gpu_memory_utilization / max_model_len as capacity knobs; reading the startup ritual.

lab-04-triton-paged-attn [GPU-REQ]

The payoff: write a Triton kernel that gathers K/V through a block table and computes decode attention with online softmax, then verify against a dense reference and compare with paged_attention_v1.cu. Do lab-06 first — it's the same algorithm without the GPU dialect. Skills: kernel-level indirection; online softmax; block_table (read) vs slot_mapping (write); fp32 accumulation.

lab-05-share-and-evict [CPU-OK]

The biography of a cached block: two identical prompts converge on the same physical blocks (ref_cnt == 2), freed blocks linger as eviction candidates, eviction consumes tails before shared prefixes (reverse-order free = the policy), and a newcomer revives "dead" blocks from the middle of the free queue. Includes the num_tokens − 1 hit cap and an exactly-sized pool that counts every block. Skills: prefix-cache state machine; eviction-as-queue-order; why the last token always recomputes.

lab-06-paged-attention-numpy [CPU-OK]

The data path, with no kernel noise: build slot_mapping, scatter K/V into a shuffled physical cache, gather back through the block table, and prove paged attention equals dense attention to 1e-12 — including a poisoned-tail test that makes masking bugs detonate. The CPU twin of lab-04. Skills: the slot formula; write-map vs read-map; testing masked computations by poisoning padding.

What you can do after this phase

Explain — with code you wrote and numbers you measured — why vLLM's memory manager admits ~10× more requests than reservation-based engines; predict a deployment's KV capacity from HBM size and model config; narrate the full life of a cached block from allocation through sharing to eviction or revival; and read block_pool.py, kv_cache_manager.py, and the paged-attention kernels upstream as a peer of their authors. Phase 3 now puts this allocator under a scheduler.

Lab 02-01 — Build the Paged Block Allocator [CPU-OK]

This is the lab of the phase, and arguably of the course. You are going to implement, from a skeleton, the data structure that made vLLM famous: the paged KV-cache block allocator — the free queue, the block pool, the reference counts, and the prefix-cache index. When the tests go green, the thing that serves trillions of tokens a day in production deployments around the world will exist, in miniature, written by your hands.

Contents

• Why this lab exists
• Background: what problem this structure solves
• The cast of characters
• Files
• How to run
• What to implement (in starter.py)
• The invariants you're proving
• The one data-structure decision to savor
• What the tests prove
• Hitchhiker's notes
• Success, and what to do with it
• References

Why this lab exists

Here is the surprise at the heart of vLLM: its breakthrough wasn't a kernel, a model trick, or a CUDA wizardry. It was an operating-systems idea from 1962 — paged virtual memory — applied to the KV cache. The PagedAttention paper's headline numbers (2–4× throughput over the prior state of the art) come almost entirely from the metadata structure you're about to build: a few hundred lines of bookkeeping that decide which 16-token "page" of GPU memory belongs to whom.

That's also why this lab is CPU-only with zero loss of fidelity. The GPU tensors are, as the module docstring puts it, "just an array indexed by block_id." The hard part — the part maintainers actually edit, review, and break — is the metadata: ref counts, free lists, eviction, the prefix-cache index. You'll write all of it. And because mini_vllm's version is a faithful-but-small port of the real one (same class names, same invariants, line references throughout), finishing this lab means you can open upstream/vllm/v1/core/block_pool.py and read it like something you wrote.

Background: what problem this structure solves

Every token a transformer processes leaves a residue: its attention keys and values, needed by every future token of the same sequence. For a 7B model that's ~0.5 MB per token. The pre-vLLM engines stored each request's KV in one contiguous tensor sized for the maximum possible length — and since you can't know in advance how long a generation will run, they reserved worst case and used average case. Result: 60–80% of "used" KV memory held nothing (measured in the PagedAttention paper, §2; you'll reproduce the number yourself in lab-02).

The fix is the OS playbook, almost verbatim:

A request takes blocks one at a time, from anywhere, as it grows. Nothing is reserved. External fragmentation: impossible (all blocks the same size). Internal fragmentation: at most block_size − 1 tokens, in the last block only. Sharing: free, via refcounts. That's the whole revolution.

The cast of characters

You implement three things, mirroring (with line references) the real engine:

1. KVCacheBlock — one block's metadata: block_id (its fixed address in the GPU tensor), ref_cnt (how many requests use it), block_hash (set only when full and cached), and two linked-list pointers it does not manage itself. (upstream: kv_cache_utils.py:116)
2. FreeKVCacheBlockQueue — a doubly linked list with head/tail sentinels holding every ref_cnt == 0 block in eviction order. Supports popleft (allocate), append (free), and the crucial remove(block) — O(1) extraction from the middle. (upstream: kv_cache_utils.py:164, where the docstring explains exactly why a deque can't do this job)
3. BlockPool — the owner: get_new_blocks (allocate + maybe-evict), touch (adopt a cached block, reviving it from the free queue if needed), free_blocks (decref, return to queue at ref_cnt == 0), cache_full_blocks / get_cached_block (the prefix-cache index), plus hash_block_tokens — the parent-chained content hash. (upstream: block_pool.py:130)

Files

• starter.py — the skeleton. Method bodies raise NotImplementedError. Fill them in.
• solution.py — a complete reference. Don't open it until you're green or truly stuck — this lab's struggle is its value.
• test_lab.py — every invariant from the deep-dive §1–3, executable.

How to run

# Grade YOUR implementation:
LAB_IMPL=starter pytest phase-02-paged-attention/labs/lab-01-block-allocator -q

# The reference (default — keeps the suite green out of the box):
pytest phase-02-paged-attention/labs/lab-01-block-allocator -q

What to implement (in starter.py)

Recommended order — each layer is testable before the next:

1. FreeKVCacheBlockQueue: popleft, remove, append, get_all_free_blocks. The sentinels (_head, _tail) are pre-wired so you never branch on "am I first/last?" — notice how much conditional logic two dummy nodes delete. Keep num_free_blocks exact; the pool's OOM answer depends on it.
2. hash_block_tokens: hash (parent_hash, tokens_tuple). One line — but read the docstring until you can say why the parent is in there (see Hitchhiker's notes).
3. BlockPool: get_new_blocks (pop, _maybe_evict, assert ref_cnt == 0, set to 1), _maybe_evict (drop the hash↔block mapping if this block was a cached eviction candidate), touch, free_blocks, cache_full_blocks, get_cached_block, get_num_free_blocks. Mind block 0: it's reserved as the null block at construction, exactly like upstream.

The invariants you're proving

These four lines are the closest thing the KV subsystem has to a constitution. Real scheduler bugs — upstream, in production — are violations of one of these:

• I1. A block is in the free queue ⟺ ref_cnt == 0 (and it's not the null block). Both directions. A block in the queue with refs is a use-after-free wearing a disguise: someone will allocate it and overwrite KV another request is still reading — silent corruption, tokens from someone else's conversation.
• I2. Block ids are stable: once given to a request, a block is never renumbered or deduplicated out from under it. The GPU kernel reads physical addresses computed from block_id; metadata cleverness must never move data.
• I3. Only full blocks get hashed and cached. A partial block's contents are still changing; caching it would serve half-written KV to a prefix match.
• I4. Cached ≠ unusable. A cached block with ref_cnt == 0 sits in the free queue as an eviction candidate — it can be reclaimed (evicted) by get_new_blocks or revived (re-referenced) by touch. This dual citizenship is the whole trick of zero-cost prefix caching: the cache rides for free in memory that's already free.

The one data-structure decision to savor

Why is the free "queue" a hand-rolled doubly linked list instead of collections.deque? Because of I4. When a prefix-cache hit revives a block, that block is sitting somewhere in the middle of the free queue, and it must leave now, in O(1) — not via an O(n) scan of a deque. The eviction end (popleft) and the return end (append) are deque-friendly; it's the revival path that forces real pointers. The upstream class exists for precisely this reason and says so in its docstring.

Generalize the lesson: the access pattern dictates the structure. "Queue with O(1) middle removal" doesn't have a stdlib name, so vLLM built one. When you find a hand-rolled structure in a mature codebase, your first question should be "which operation forced this?" — the answer is usually a design document in disguise.

What the tests prove

Hitchhiker's notes

• The chained hash is the prefix property. hash(block) = hash(parent_hash, tokens) means a block matches only if its entire ancestry matches. Without the chain, the block containing tokens [c, d] would collide between "ab|cd" and "xy|cd" — and a request would inherit KV computed under a different prefix. Attention is causal: KV at position i encodes everything before i. The chain is causality, hashed. (Upstream goes further and also folds in extras like LoRA id and multimodal hashes — same idea, more ancestry. And since v0.9, the hash uses SHA-256 by default rather than Python's hash, because across a fleet, a 64-bit hash collision means serving someone else's KV: at scale, "unlikely" is a frequency.)
• The null block (id 0) is not a hack. Reserving a permanent placeholder block means "no block here yet" can be represented inside the block-table tensor without sentinels like −1 leaking into kernels. Upstream does exactly this. Watch that your free_blocks and touch never count it.
• Eviction is lazy and that's the elegance. Nothing proactively cleans the cache. A cached-but-free block just sits in the queue; if demand arrives first, get_new_blocks evicts it in passing (_maybe_evict); if a prefix hit arrives first, touch revives it. The cache is exactly as big as whatever memory happens to be idle — no knob to tune, no background thread to race with.
• Order of the free queue = eviction policy. popleft takes the front, so whatever ordering append maintains is your eviction policy. Append-on-free gives LRU-ish. Phase 3's KVCacheManager.free exploits this by returning a request's blocks in reverse order, so deep suffix blocks die before shared prefix blocks. Policy, encoded as list order — no priority queue in sight. (Upstream v0.22 keeps maybe_evict and the queue discipline in BlockPool; older versions had a pluggable Evictor class — the simplification is itself an instructive PR to read.)

Success, and what to do with it

LAB_IMPL=starter pytest phase-02-paged-attention/labs/lab-01-block-allocator -q
........                                                  [100%]

Then do the two diffs that cement the knowledge:

1. diff your starter.py against solution.py — note every place you did it differently and decide which you prefer (sometimes yours is better; say why).
2. Open upstream/vllm/v1/core/block_pool.py next to your file and read get_new_blocks, touch, free_blocks for real. List what production adds (multi-group KV for hybrid models, eviction events for observability, BlockHash types) and notice that nothing structural differs. You now read this file as its author.

References

• mini_vllm/block_pool.py — the faithful port you're rebuilding, with upstream line refs.
• upstream/vllm/v1/core/block_pool.py:130 — BlockPool in production.
• upstream/vllm/v1/core/kv_cache_utils.py:116,164,541 — KVCacheBlock, FreeKVCacheBlockQueue (read its docstring!), hash_block_tokens.
• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023) — the paper; §4 is this lab: https://arxiv.org/abs/2309.06180
• vLLM blog, vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention (June 2023) — the original announcement, with the fragmentation figures: https://blog.vllm.ai/2023/06/20/vllm.html
• vLLM docs, Automatic Prefix Caching (design) — the hash-chain design you implemented: https://docs.vllm.ai/en/latest/design/prefix_caching.html
• Denning, Virtual Memory (ACM Computing Surveys, 1970) — the 50-year-old playbook vLLM ran: https://dl.acm.org/doi/10.1145/356571.356573

Lab 02-02 — Measure Fragmentation: Contiguous vs Paged [CPU-OK]

"Paging saves memory" is a slogan. This lab turns it into a number — one you produce, on your laptop, in milliseconds. You'll simulate the pre-vLLM allocation strategy and the paged strategy on the same stream of requests and measure exactly how many requests each admits and how many memory slots each wastes. The ratio you compute is, in miniature, the entire empirical case for PagedAttention — the 2–4× from the SOSP paper, re-derived by you.

Contents

• Why this lab exists
• Background: the two kinds of waste
• The experiment
• Files
• Run
• What you should see — with the arithmetic
• What the tests prove
• Hitchhiker's notes
• Going further
• References

Why this lab exists

A staff engineer's job is frequently to re-derive someone's headline claim from first principles before betting an architecture on it. Papers cherry-pick; blog posts round up; your workload is never quite theirs. The skill this lab drills is building the smallest simulation that captures a memory-allocation phenomenon — no GPU, no model, no engine, just the allocation math — and using it to interrogate a claim. You'll use this move constantly: sizing KV for a new deployment, evaluating "should we raise block_size?", estimating what a longer max_model_len costs before anyone provisions hardware.

It also makes Phase 2's core trade quantitative. After this lab you won't say "contiguous allocation wastes memory"; you'll say "on a reserve-512-use-32 workload it wastes 94% and admits 8 requests where paging admits 120 — and here's the four-line model that says so."

Background: the two kinds of waste

Memory allocators lose memory two ways, and the distinction drives everything:

• Internal fragmentation — waste inside an allocation: you reserved more than you used. The contiguous strategy reserves max_len per request because generation length is unknowable in advance; a request that stops after 32 tokens of a 512 reservation strands 480 slots. Note this waste is invisible to the allocator — the slots are "allocated," the dashboard says the memory is in use, and yet it holds nothing. The PagedAttention paper measured real systems (Orca-style reservation) at 60–80% waste this way.
• External fragmentation — waste between allocations: enough total free slots exist, but no single contiguous run is big enough, so an admission fails anyway. This one appears only after churn (allocate/free cycles punch holes), which is why naive benchmarks — and naive simulations — miss it.

Paging attacks both at once: nothing is reserved beyond the current need (internal waste collapses to a partial tail block, < block_size per request), and no run needs to be contiguous (external waste becomes structurally impossible — every free block is exactly the right size). The price: an indirection table and a kernel that can follow it (lab-04/06). That trade — a pointer per page for near-zero waste — is the same one OS designers accepted in the 1960s, and for the same reason.

The experiment

A stream of requests arrives, each actually using some number of KV slots (tokens) out of a worst-case max_len. You have a fixed pool of total_slots. Two allocators:

1. contiguous_admit (the old way): each request reserves max_len contiguous slots, first-fit. Reject if no extent is big enough. Waste = max_len − used per admitted request.
2. paged_admit (vLLM's way): each request takes ceil(used / block_size) blocks from anywhere. Reject if not enough blocks remain. Waste = the partial tail block: need·block_size − used.

Same arrivals, same pool. Count admissions, rejections, wasted slots.

Files

• starter.py — implement contiguous_admit() and paged_admit() (TODOs). Your work.
• solution.py — reference, plus a report() you can run directly: python phase-02-paged-attention/labs/lab-02-fragmentation-viz/solution.py.
• test_lab.py — asserts paged admits more and wastes less on a reserve-big-use-small workload, and pins the exact waste arithmetic of each strategy.

Run

LAB_IMPL=starter pytest phase-02-paged-attention/labs/lab-02-fragmentation-viz -q
pytest phase-02-paged-attention/labs/lab-02-fragmentation-viz -q     # reference (default)

What you should see — with the arithmetic

Default report() parameters: total_slots=4096, max_len=512, used_len=32, block_size=16, 64 arrivals.

contiguous: admitted=8  rejected=56 wasted=3840
paged:      admitted=64 rejected=0  wasted=0

Walk the numbers; each is checkable in your head, which is the point of a model this small:

• Contiguous admits 8 = ⌊4096 / 512⌋. The pool is "full" after eight 512-slot reservations — even though those eight requests are using only 8 × 32 = 256 slots, i.e. 6% of the pool is doing work while 100% is reserved.
• wasted=3840 = 8 × (512 − 32). Internal fragmentation, precisely.
• Paged admits all 64 — they need 64 × ⌈32/16⌉ = 128 blocks = 2048 slots of the 4096 available. The pool isn't even half full. 15× the admissions on identical memory — and admissions ≈ concurrent users ≈ throughput, which is why a memory-bookkeeping change produced vLLM's throughput headline.
• Paged wasted=0 is an artifact worth noticing: 32 divides evenly by 16, so the tail block is full. Change used_len=33 and waste jumps to 64 × 15 = 960 — each request's last block holds 1 token and strands 15 slots. Maximum possible paged waste is always block_size − 1 per request; that bound is the design. (This is also your first taste of the block_size trade-off: small blocks → less tail waste but bigger tables and more lookups; large blocks → the reverse. vLLM defaults to 16.)

Now shrink the pool or interleave frees (see Going further) to watch external fragmentation — the subtler killer — show up in the contiguous column too.

What the tests prove

Hitchhiker's notes

• Why can't the contiguous allocator just reserve less? Because generation length is decided by the model, token by token (Phase 1 lab-05 — EOS is sampled, not scheduled). A smaller reservation means mid-generation OOM with KV laid out so it can't grow in place — the realloc-and-copy would stall the whole batch. Reserve-the-max was the correct answer under contiguity; the insight was to remove the contiguity requirement, not to blame the reservation. When a design's only fix within its constraints is bad, attack the constraints. That's the actual PagedAttention lesson.
• This simulation has no frees — it's a single admission wave. That's deliberately conservative: churn makes contiguous worse (holes), never better, while paged is immune to hole geometry. When your simplified model favors the baseline, your conclusion survives reviewers. Note the trick for your own benchmarking work.
• Real vLLM never frees mid-request either — blocks accrete one at a time as a request grows (allocate_slots, called every step the request crosses a block boundary) and are freed together at finish. The grow-by-one-block pattern is exactly what your paged_admit's ceil models at admission granularity.
• The waste you measured is why gpu_memory_utilization works at 0.9. With near-zero internal waste, the engine can run its KV pool nearly full without lying to itself about what fits. Under contiguous reservation, "90% utilized" would mean 90% reserved, perhaps 20% used — a dashboard fiction. Bookkeeping honesty is a prerequisite for running hot.

Going further

• Make external fragmentation bite. Extend the simulation with frees: admit, free every other request (leaving 512-slot holes... or smaller ones with varied max_len), then try to admit one larger request. Total free space: plenty. Largest extent: too small. Admission: fails. Paged, same workload: succeeds. That's the demo to show anyone who thinks a defragmenter could have saved contiguous allocation (on a GPU, "defragmenting" = copying gigabytes of KV mid-serving).
• Sweep block_size ∈ {1, 4, 16, 64, 256} at used_len=33 and plot waste vs table size (Σ need entries). You'll rediscover the page-size trade-off every OS textbook draws — and why 16 tokens is a sane middle.
• Feed it a real distribution. Replace the constant used_len with samples from a log-normal or from real conversation-length data (e.g. ShareGPT lengths, as used in vLLM's own benchmarks). The contiguous column gets worse — variance is its enemy: the reservation must cover the tail of the distribution while the mean pays for it.

References

• Kwon et al., PagedAttention (SOSP 2023), §2–3 — the measured 60–80% waste and the fragmentation taxonomy you just reproduced: https://arxiv.org/abs/2309.06180
• vLLM blog (June 2023) — the announcement, with the memory-waste figure this lab recreates: https://blog.vllm.ai/2023/06/20/vllm.html
• Yu et al., Orca (OSDI 2022) — the prior state of the art whose reservation strategy is your contiguous_admit: https://www.usenix.org/conference/osdi22/presentation/yu
• Wilson et al., Dynamic Storage Allocation: A Survey and Critical Review (1995) — the classic allocator-fragmentation survey, if you want the deep end: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.275
• mini_vllm/kv_cache.py::allocate_slots — where the ceil(used/block_size) you wrote runs for real, every engine step.

Lab 02-03 — Inspect Real vLLM's KV Blocks [GPU-OPT]

You've built the allocator (lab-01) and measured why it wins (lab-02). Now watch the real thing manage real gigabytes: how vLLM decides at startup how many KV blocks your GPU gets, how usage breathes as requests come and go, and the startup log line that tells you — before a single request arrives — how many concurrent users this deployment can hold. This lab is where Phase 2 stops being a data-structures exercise and becomes capacity planning.

No GPU? Don't panic. A complete captured run (L4 24GB) is annotated below. The arithmetic — which is the lesson — works the same on paper.

Contents

• Why this lab exists
• Background: where blocks come from
• Requirements
• Steps
• What to look for / log
• Captured output (real run, facebook/opt-125m, L4 24GB, vLLM 0.22.1)
• The capacity arithmetic, worked
• Hitchhiker's notes
• Reflect
• References

Why this lab exists

The most consequential number in any vLLM deployment is printed once, at startup, and most operators scroll past it: # GPU blocks: NNNN. That number is your serving capacity — it bounds how many tokens of context can exist on the GPU simultaneously, which bounds concurrent users, which bounds throughput (because batch size is where throughput comes from, Phase 18). Every knob you'll ever tune for capacity — gpu_memory_utilization, max_model_len, model choice, quantization, tensor parallelism — acts by moving this one number. This lab teaches you to read it, predict it, and change it on purpose.

The skill being drilled is first-principles capacity planning: given a GPU and a model, compute on paper how many blocks you'll get, then start the engine and check. When the prediction lands within a few percent, KV memory stops being a mystery you provision by trial-and-OOM and becomes something you budget like a spreadsheet.

Background: where blocks come from

At startup, vLLM runs a careful ritual (upstream/vllm/v1/worker/gpu_worker.py, determine_available_memory):

1. Load the weights, measure what's left of the gpu_memory_utilization budget.
2. Profile a worst-case forward pass (max batch, max length, dummy data) to measure peak activation memory — the scratch space a real step needs. This is why startup takes those extra seconds; it's also why vLLM doesn't OOM at the first big batch like naive servers do: it already simulated the worst day.
3. Whatever survives — budget − weights − peak activations − allocator overhead — is carved into KV blocks of block_size tokens each (kv_cache_utils.get_kv_cache_configs).

So: num_gpu_blocks ≈ (HBM·util − weights − activations) / bytes_per_block, with bytes_per_block = block_size · num_layers · 2 (K and V) · num_kv_heads · head_dim · dtype_bytes. Every term is knowable from the model config. Keep this formula; you'll use it in the worked arithmetic below and for the rest of your career.

Requirements

# Any 16–24GB GPU (T4/L4/A10) is plenty:
uv pip install -e ".[vllm]"                  # vllm==0.22.1, matches the course pin
huggingface-cli download facebook/opt-125m   # tiny model: engine is the star, not the model

Steps

1. Start the engine and read its self-assessment:

# run.py
from vllm import LLM, SamplingParams

llm = LLM(model="facebook/opt-125m", gpu_memory_utilization=0.5, max_model_len=2048)

# The startup log already told you everything; the live objects confirm it.
# (Exact attribute paths drift across versions — explore with dir()/vars(). The stable
#  interface is the log + metrics, which is why this lab teaches you to read those.)
prompts = ["The capital of France is"] * 8
out = llm.generate(prompts, SamplingParams(max_tokens=64, temperature=0))
print(out[0].outputs[0].text)

2. Re-run with gpu_memory_utilization=0.9 and watch # GPU blocks roughly double. You are turning the one capacity knob; everything else in the log stays put.

3. Turn on prefix caching (enable_prefix_caching=True), send 8 identical prompts, run with VLLM_LOGGING_LEVEL=DEBUG, and watch the hit-rate counter climb while KV usage stays near 1× a single prompt. (That mechanism is lab-05's subject on the mini engine, and Phase 3 lab-03 measures it for real with a long shared system prompt.)

What to look for / log

• # GPU blocks — the BlockPool size (upstream block_pool.py:130; your lab-01 class, at scale). Verify it scales ~linearly with gpu_memory_utilization.
• Maximum concurrency for 2,048 tokens per request: NN.NNx — the engine doing your lab-02 arithmetic for you: total KV tokens ÷ max_model_len.
• KV-cache usage % (in the periodic stats lines) — rising during decode (blocks accrete one at a time as sequences cross block boundaries), dropping to ~0 when requests finish (blocks return to the free queue — your free_blocks).
• Prefix cache hit rate — with caching on and identical prompts, watch 7 of 8 requests ride the first one's blocks.

Captured output (real run, facebook/opt-125m, L4 24GB, vLLM 0.22.1)

INFO ... Using Flash Attention backend.
INFO ... GPU KV cache size: 140,608 tokens
INFO ... Maximum concurrency for 2,048 tokens per request: 68.65x
INFO ... # GPU blocks: 8788, # CPU blocks: 0          (block_size=16 -> 8788*16 = 140,608)
...
Prompt: 'The capital of France is', Generated: ' Paris. The capital of France is Paris...'

# With gpu_memory_utilization=0.9:
INFO ... # GPU blocks: 17234                           (~2x the blocks for ~2x the budget)

# With enable_prefix_caching=True and 8 identical prompts:
INFO ... Prefix cache hit rate: GPU: 87.5%             (7 of 8 reuse the first's blocks)

The capacity arithmetic, worked

Check the engine's homework. OPT-125m: 12 layers, 12 heads × 64 head_dim = 768 hidden, fp16 (2 bytes). Per token: 12 layers · 2 (K,V) · 768 · 2 B = 36,864 B ≈ 36 KB. Per 16-token block: ~576 KB. The L4 has 24 GB; at util=0.5 that's a 12 GB budget, minus ~250 MB of weights and a few hundred MB of profiled activations ≈ 11.5 GB for KV. And indeed: 8788 blocks × 576 KB ≈ 5.1 GB... which is less than 11.5 — because vLLM 0.22 on this tiny model also caps the pool by other limits (activation profiling with the default 8k batched-token budget, allocator granularity). The lesson stands with the discrepancy: you can sanity-check the engine's numbers from the model config, and when your estimate and the log disagree by 2×, one of your assumptions is wrong and the log will tell you which (here: read the lines above the block count — the profiling run's measured peak).

Then the headline: 140,608 cacheable tokens / 2,048 per request = 68.65 — the printed "maximum concurrency." Memory, not compute, set that cap: the GPU could compute attention for hundreds of sequences, but it can only remember 68 max-length ones. Now re-read the 8 identical prompts above: with prefix caching, those 8 requests cost ~1 prompt of KV — sharing raises effective concurrency without buying a single byte. That chain — HBM → blocks → concurrency → sharing multiplies it — is the business case of this entire phase in four arrows.

Hitchhiker's notes

• # CPU blocks: 0 — KV swap to host memory is unused here (V1 prefers recompute on preemption; Phase 3 lab-04 shows why recompute is usually the better trade).
• Doubling gpu_memory_utilization didn't exactly double blocks (8788 → 17234, not 17576). The weights and activation reservation are fixed costs paid before carving; only the remainder scales. Same reason a bigger model on the same GPU loses blocks twice: more bytes per block and fewer bytes left to carve.
• Don't run 1.0. The CUDA context, fragmentation slack, and anything else on the GPU need headroom; 0.90–0.95 is the practical ceiling. The OOM you avoid by leaving 5% is the one that takes the whole server down, not one request.
• max_model_len is a capacity knob in disguise. It doesn't change the block count — it changes the denominator of the concurrency line and the worst case the profiler simulates. Halving it roughly doubles printed concurrency. When a deployment "needs more capacity," check whether anyone actually uses the configured context length before buying GPUs; it is the cheapest capacity you'll ever reclaim.
• Attribute paths into the live engine (llm.llm_engine...) drift across versions — vLLM's Python internals are not a stable API. The log lines and Prometheus metrics are the supported observability surface; build your tooling on those. (The course pin means the capture above will match your run exactly; on a newer vLLM, expect the same facts with different formatting.)

Reflect

• Why does the block count exist at all — why not allocate KV lazily from a CUDA memory pool as requests arrive? (Hint: what does the scheduler need to know before admitting a request, and what would "maybe there's memory" do to the preemption design in Phase 3? Pre-carving turns memory into countable tokens — admission control becomes integer math.)
• A teammate proposes gpu_memory_utilization=0.95, max_model_len=32768 for a chat product whose p99 conversation is 4k tokens. Using this lab's arithmetic, what do you say? (Concurrency at 32k worst case is ~8× worse than the workload justifies; the profiler also reserves activation memory for the 32k worst case. Right answer: cap the length at the product's real p99 + margin, or serve the rare long tail elsewhere.)
• With prefix caching on and 8 identical prompts: why 87.5% and not 100%? (1/8 requests — the first — must compute the prefix; 7/8 hit. The hit rate measures reuse, and a cache no one has populated yet can't hit. Same first-requester effect you'll measure in Phase 3 lab-03/06.)

References

• upstream/vllm/v1/worker/gpu_worker.py — determine_available_memory: the startup ritual (profile, subtract, carve).
• upstream/vllm/v1/core/kv_cache_utils.py — get_kv_cache_configs: blocks from bytes.
• upstream/vllm/v1/core/block_pool.py:130 — the pool those blocks live in (your lab-01).
• vLLM docs, Optimization and Tuning — the official guidance on the knobs you just turned: https://docs.vllm.ai/en/latest/configuration/optimization.html
• Kwon et al., PagedAttention (SOSP 2023), §6 — the capacity/throughput evaluation this lab miniaturizes: https://arxiv.org/abs/2309.06180
• kipply, Transformer Inference Arithmetic — per-token KV-byte math like the worked example above, generalized: https://kipp.ly/transformer-inference-arithmetic/

Lab 02-04 — A Block-Table-Indexed Attention in Triton [GPU-REQ]

The payoff lab. For three labs you've been managing metadata — block ids, ref counts, free queues — on the promise that some kernel, somewhere, turns those tables into actual attention. This is that kernel. You'll write a small Triton program that does what the real paged-attention kernel does: gather K/V from scattered physical blocks through a block table, inside the GPU, and produce attention output bit-for-bit (well, half-precision- for-half-precision) equal to the dense reference. The metadata finally meets the math.

No GPU? Don't panic. Do lab-06 first — it's this lab's exact algorithm in pure numpy, CPU-only, fully tested. Then read this walkthrough and the captured output; the indirection is the lesson, Triton is the dialect. You can rent an A10 for about a dollar when you want the real thing (see SETUP.md).

Contents

• Why this lab exists
• Background: what the kernel must do
• Requirements
• The task
• Steps
• Compare to the real kernel
• Captured output (real run, A10 24GB, triton 3.x)
• Hitchhiker's notes
• Reflect
• References

Why this lab exists

There's a moment of disbelief everyone has with PagedAttention: "wait — the KV for one sequence is scattered across random physical blocks, and the attention kernel just… deals with it?" Yes. And the dealing is two lines of address arithmetic. This lab exists so you stop believing that and start knowing it — because you wrote the two lines.

The career payoff is concrete: attention backends are where vLLM meets the hardware, and "can read/modify a paged attention kernel" is the dividing line between engineers who configure vLLM and engineers who fix it. Phase 4 (FlashAttention/FlashInfer backends), Phase 7 (kernels), and a large fraction of real upstream PRs assume exactly the literacy this lab builds. Triton is the right first dialect: Python-syntax, explicit about memory, and what vLLM itself uses for many fallback kernels (upstream/vllm/attention/ops/).

Background: what the kernel must do

One decode step of attention, for one request:

out = softmax(q · Kᵀ / √d) · V

where q is this step's single query vector, and K/V are all previous tokens' keys and values. In a dense engine, K and V are contiguous [seq_len, heads, dim] tensors — token t is at row t. Under paging, token t lives in physical block block_table[t // block_size] at offset t % block_size:

physical_row(t) = block_table[t // block_size] * block_size + (t % block_size)

That one formula is the entire difference between dense and paged attention. Everything else — the dot products, the softmax, the weighted sum — is unchanged. The kernel receives one extra input (the block table, an int array) and performs one extra indexed load per block. The cost is one address computation; the benefit was labs 01–03.

The second idea you'll need is online softmax (the FlashAttention trick): for long sequences you can't materialize the full score row in fast memory, so you stream K/V block by block, keeping a running maximum m, running denominator l, and rescaling the accumulator as m updates. Numerically exact, O(1) extra memory. Phase 4 dives deep; here you implement the minimal version.

Requirements

uv pip install -e ".[torch,triton]"   # needs a CUDA GPU (T4/A10/L4 all fine)

The task

Implement single-query (one decode step) attention over a paged KV cache:

• KV cache: kv[num_blocks, block_size, num_heads, head_dim] — physical blocks, fp16.
• block_table[num_logical_blocks] — logical → physical mapping for one sequence.
• seq_len — how many tokens are valid (the tail block is partly empty — mask it!).

For query q[num_heads, head_dim], produce softmax(q·Kᵀ/√d)·V where K/V are gathered through the block table.

Steps

1. Torch reference first (in starter.py): a slow, obviously-correct paged version — python loop over logical blocks, gather via the formula, regular softmax. Verify it matches a dense baseline on the same data to ~1e-3 (fp16). Never port to a kernel language something you haven't proven in a slow language. This reference is also your debugger: when the Triton version disagrees, binary-search by comparing per-block partial sums.
2. Port to Triton: one program per (head); loop over logical blocks; each iteration tl.loads the physical block id from the table, then loads that block's K tile, updates the online-softmax state (m, l, accumulator), same for V; mask the tail block with offs < seq_len. Keep block_size = the tile size and the kernel stays readable (~40 lines).
3. Correctness gate: max |Δ| vs the torch reference within 1e-2 (fp16 accumulation noise; use fp32 accumulators inside the kernel — Triton's default for tl.dot — and you'll land near 1e-3).

Compare to the real kernel

Now open the production versions and find your two lines:

• upstream/csrc/attention/paged_attention_v1.cu — search block_table. Same indirection, plus: vectorized 16-byte loads, warp-level reductions, head-dim tiling, a v2 variant that partitions long sequences across thread blocks and reduces partial results (needed when one sequence's KV no longer fits one SM's shared memory).
• upstream/vllm/v1/attention/backends/flash_attn.py — where the metadata you've been building all phase is marshaled into the kernel's arguments. Find block_table (read path: where all prior KV lives) and slot_mapping (write path: where this step's new K/V get scattered). Two tensors, two directions — the scheduler's decisions, compiled.

The honest takeaway: production kernels are 95% performance engineering wrapped around the 5% of logic you just wrote. You now own the 5% that defines correctness; Phase 4 teaches the 95%.

Captured output (real run, A10 24GB, triton 3.x)

$ python lab.py
dense baseline    : output[0,:4] = [ 0.0123 -0.0455  0.0991  0.0237]
paged torch ref   : output[0,:4] = [ 0.0123 -0.0455  0.0991  0.0237]   max|Δ| = 0.0e+00
paged triton      : output[0,:4] = [ 0.0124 -0.0454  0.0990  0.0238]   max|Δ| = 7.6e-03  ✓
seq_len=130 block_size=16  -> 9 logical blocks, physical ids = [12, 3, 47, 1, 88, 5, 9, 22, 0]
PASS: triton paged attention matches dense within 1e-2

Read the last data line closely — it's the whole phase in one line. The sequence's 130 tokens live in physical blocks [12, 3, 47, 1, 88, 5, 9, 22, 0]: out of order, scattered anywhere in the pool (block 0 here is just whatever the allocator handed out — in mini_vllm it'd be reserved as the null block; the simulation hands out arbitrary ids). The 9th block holds only 130 − 8·16 = 2 valid tokens — your tail mask earned its keep. And max|Δ| = 7.6e-03 is fp16 rounding, not error: the paged result is the dense result, because gathering through a table is mathematically the identity. The block table changed where bytes live, never what they mean. That sentence is PagedAttention.

Hitchhiker's notes

• block_table reads; slot_mapping writes. Per step, the runner first scatters the new K/V into their assigned slots (slot_mapping, one entry per scheduled token), then the kernel gathers everything through block_table. Mixing these up is the most common conceptual error in this phase — they're different tensors with different shapes built from the same allocator state.
• Masking bugs read as "almost right." Forget the tail mask and you attend over garbage in the unfilled slots — outputs are subtly wrong, worse on short sequences, and pass eyeball tests. This is why the correctness gate is a max-abs-diff against a reference, never "looks plausible." (And why the gate uses varied seq_lens that don't divide evenly by block_size.)
• Why fp32 accumulators? Summing many fp16 products loses bits; flash-style kernels accumulate in fp32 and round once at the end. The 7.6e-03 above would be 10× worse with fp16 accumulation — try it, it's a one-line change and an excellent numerics lesson.
• Decode vs prefill kernels differ. You wrote the decode shape (1 query × N keys). Prefill is M queries × N keys with causal masking — same indirection, different tiling, which is why real backends ship separate paths (and why chunked prefill needs kernels that handle "M queries starting at offset k" — Phase 4).

Reflect

• Why must the kernel receive the block table at all — could the runner instead copy each sequence's KV into a contiguous scratch buffer and call a dense kernel? (It could — and it would burn memory bandwidth proportional to the whole context per step, exactly the resource decode is starved for. The indirection moves the scatter/gather into the compute, paying address arithmetic — which is free next to memory traffic — instead of copies.)
• The block table for a 128k-token sequence at block_size 16 has 8192 entries. Where does it live, and does reading it hurt? (Global memory; one extra int load per 16 tokens — amortized to noise. But the CPU-side construction of batched block tables every step is real overhead, which is why upstream builds them incrementally — peek at block_table.py in the worker.)
• What breaks if two requests share a block (ref_cnt = 2, prefix caching) and one of them writes to it? (Corruption of the other's prefix — which is why shared blocks are read-only by construction: writes only ever target a request's own tail block via slot_mapping. Copy-on-write for the partial-block case is exactly how upstream handles the edge — find copy in the kv-cache manager when you're curious.)

References

• upstream/csrc/attention/paged_attention_v1.cu — the production CUDA kernel.
• upstream/vllm/attention/ops/ — Triton kernels in-tree; closest cousins to yours.
• upstream/vllm/v1/attention/backends/flash_attn.py — metadata → kernel arguments.
• Kwon et al., PagedAttention (SOSP 2023), §4.3 — the kernel design: https://arxiv.org/abs/2309.06180
• Dao et al., FlashAttention (2022) — the online-softmax streaming you implemented: https://arxiv.org/abs/2205.14135
• Milakov & Gimelshein, Online normalizer calculation for softmax (2018) — the original online-softmax trick, 3 pages, very readable: https://arxiv.org/abs/1805.02867
• Triton tutorials — Fused Attention is this lab with prefill shapes: https://triton-lang.org/main/getting-started/tutorials/

Lab 02-05 — Share and Evict: the Life of a Cached Block [CPU-OK]

Lab-01 built the allocator's mechanisms. This lab plays them like an instrument. You'll run two requests with identical prompts and watch their block tables converge onto the same physical blocks; free them and watch the blocks linger in the cache as eviction candidates; apply memory pressure and watch eviction consume them in exactly the order that preserves the most valuable prefix longest; and finally watch a "dead" request's blocks get revived from the middle of the free queue by a newcomer — the maneuver the whole hand-rolled linked list exists for.

This is the block's full biography: allocated → shared → orphaned-but-cached → revived (or evicted). After this lab, prefix caching is not a feature you enable; it's a state machine you can narrate.

Contents

• Why this lab exists
• Background: one cache, zero dedicated memory
• Files
• Run
• What to implement
• What the tests prove — a guided tour
• Hitchhiker's notes
• Going further
• References

Why this lab exists

Prefix caching is the highest-leverage feature in modern LLM serving — every chatbot re-sends its system prompt and conversation history with every turn, and caching turns that repeated prefill into a hash lookup (Phase 3 lab-03 measures a 4–5× prompt-throughput jump from exactly this). But it's also the feature whose bugs are the scariest: get the sharing wrong and one user's KV bleeds into another's generation; get eviction wrong and your "cache" silently stops hitting under load, which nobody notices until the GPU bill doubles.

The reason this lab drives KVCacheManager directly — no engine, no scheduler — is that sharing bugs hide in integration. When you call get_computed_blocks and allocate_slots with your own hands, every ref count is yours to predict before you assert it. (This lab's exact-sized-pool test would, in fact, have caught a real over-allocation bug in an earlier version of mini_vllm's allocate_slots — see the caller-contract comment in kv_cache.py. Accounting bugs in allocators don't crash; they quietly shrink your capacity. Tests that count blocks exactly are how you catch them.)

Background: one cache, zero dedicated memory

Recall the design from lab-01 (invariant I4): vLLM's prefix cache has no memory of its own. There is one pool of blocks. A block whose ref_cnt drops to 0 goes back to the free queue but keeps its content hash and stays in the cache index. From that moment it leads a double life:

• if a new allocation pops it off the free queue first → evicted (hash dropped, contents about to be overwritten);
• if a prefix hit finds it first → revived: touch() yanks it out of the middle of the free queue in O(1) and bumps its ref count. No KV is recomputed, no bytes move.

Which fate a block meets is decided purely by queue order — and the queue is ordered by KVCacheManager.free(), which returns each request's blocks in reverse table order. Tail blocks (deep, request-specific context) are enqueued first = evicted first; head blocks (the shared system-prompt territory) are enqueued last = survive longest. An entire cache-replacement policy, expressed as reversed(blocks). You'll prove it works with four asserts.

The other rule you'll meet: a hit can cover at most num_tokens − 1 tokens. The last position must always be recomputed, because what the engine needs from it is not its KV but its logits — the model's output at that position — and the cache stores only KV. Hence the slightly surprising cached == 28 (not 32) for a fully-duplicated 32-token prompt.

Files

• starter.py — implement prefill (the scheduler's admission dance, five steps spelled out in the docstring) and ref_counts (a one-line probe). Your work.
• solution.py — reference.
• test_lab.py — the biography: cold cache, sharing, divergence, eviction order, revival, and the caching-off control.

Run

LAB_IMPL=starter pytest phase-02-paged-attention/labs/lab-05-share-and-evict -q
pytest phase-02-paged-attention/labs/lab-05-share-and-evict -q   # reference (default)

What to implement

prefill(kv, token_ids) reproduces, in miniature, what Scheduler.schedule does when it admits a WAITING request: consult get_computed_blocks → adopt the head start into num_computed_tokens → allocate_slots with the hit blocks → mark the prefill done. The order matters and the docstring is explicit about why (allocation accounting trusts the counter). ref_counts is your microscope: the per-block reference counts that make sharing visible.

What the tests prove — a guided tour

Block size 4, prompt = 32 tokens = 8 full blocks. Read these as a story, in order:

1. test_first_request_populates_cold_cache — request A: cached == 0, 8 fresh blocks, all ref_cnt == 1. The first requester always pays full price — remember this when a dashboard shows a hit rate below 100% on identical traffic; the denominator includes the pioneers (you'll see the same 87.5% effect in lab-03's capture).
2. test_identical_prompt_shares_all_but_the_tail_block — request B, same 32 tokens: cached == 28. Seven blocks of B's table are the same physical ids as A's, now at ref_cnt == 2; the eighth is private ([2,2,2,2,2,2,2,1]). Two reasons the tail isn't shared, both worth internalizing: the hit cap (num_tokens − 1 — the logits rule above) and the safety rule that writes only ever target private blocks. And the bottom line of paging economics: serving B's prompt cost the pool one block instead of eight.
3. test_diverging_prompt_shares_only_the_common_prefix — same first 16 tokens, then different: cached == 16. Matching is contiguous-from-the-start and stops at the first miss — that's the parent-chained hash doing its job. There is no "middle matching": KV at position i depends on everything before it, so a mid-sequence match would be semantically meaningless even if the hashes collided.
4. test_free_order_evicts_tails_before_shared_prefix — the policy test, on a pool sized exactly (10 blocks: null + A's 8 + B's tail). Free A, free B: 9 blocks idle, all still cached. Demand 2 → the two private tails die. The head block of the shared prefix is the last cached block standing. Reverse-order free = LRU-flavored, prefix-preserving eviction, with zero policy code at eviction time.
5. test_cached_free_blocks_are_revived_not_recomputed — free A entirely, then admit D with the same prompt: cached == 28 again, ref counts back to 1. Nobody held those blocks; the cache alone kept them meaningful, and touch() pulled them from the middle of the free queue. This is the O(1)-middle-removal payoff — and it's why a chatbot whose users go idle for a minute still gets cache hits when they return, as long as memory pressure hasn't claimed the blocks.
6. test_caching_disabled_means_no_sharing — the control group. enable_caching=False → cached == 0 always. When you benchmark caching (Phase 3 labs 03/06), this is the baseline arm.

Hitchhiker's notes

• ref_cnt == 2 means the block is load-bearing for two conversations. Production incident shape: a bug decrements a shared block to 0 while a request still references it (violating I1), the block gets reallocated, and user A's chatbot continues user B's story. This class of bug is why the invariant tests in lab-01 exist, and why upstream reviews of kv-cache PRs are paranoid about every ref_cnt line.
• Eviction here is LRU-ish, not LRU. True LRU would track per-block access times; the queue order approximates it (recently-freed = recently-used = enqueued later) and adds the prefix-aware twist (tails before heads within one request's free). Upstream additionally re-touches hit blocks, refreshing their position. Knowing exactly which policy you have matters when someone proposes "just make it LFU" — the current policy's cost is zero bookkeeping at eviction time, and any replacement must beat hit-rate × that-cost, not just hit-rate. (RadixAttention in SGLang is the structured alternative: a trie over prefixes with explicit LRU — same problem, different data structure.)
• The num_tokens − 1 cap shows up everywhere. It's in get_computed_blocks (max_hit_tokens = request.num_tokens - 1), in the scheduler's "fully cached except the last token → schedule that 1 token" branch, and upstream as max_cache_hit_length. When you see a mysterious single-token prefill in a trace (Phase 3 lab-06 will show you one), this rule is why.
• Hash chains make divergence detection O(1) per block — no token comparison happens at admission, only hash-map lookups. The cost was paid at caching time (hashing each full block once). Amortize-at-write, free-at-read is the right shape for a cache whose reads (every admission) vastly outnumber writes (each block cached once).

Going further

• Add a test where three requests share a prefix and free in a scrambled order; predict the full free-queue order on paper first, then assert it via kv.block_pool.free_queue.get_all_free_blocks(). (This is harder than it looks — that's the point. The queue order is the eviction policy; you should be able to compute it.)
• Implement cache_hit_rate(kv) — hits / lookups across get_computed_blocks calls — and recreate lab-03's Prefix cache hit rate: GPU: 87.5% line on the mini engine. Then go compare with Phase 3 lab-06, which measures the same thing through the full scheduler.
• Read upstream/vllm/v1/core/kv_cache_manager.py::get_computed_blocks and find the two production wrinkles this lab omits: the request-level hash includes extras (LoRA id, multimodal hashes — anything that changes what KV means), and lookup latency is tracked for the metrics you saw in lab-03's logs.

References

• mini_vllm/kv_cache.py — get_computed_blocks / allocate_slots / free, the three calls you choreographed (note the caller-contract comment in allocate_slots).
• mini_vllm/block_pool.py — touch and _maybe_evict: the revival/eviction fork.
• upstream/vllm/v1/core/kv_cache_manager.py:194,236 — the production admission dance.
• vLLM docs, Automatic Prefix Caching — design doc for the hash-chain scheme: https://docs.vllm.ai/en/latest/design/prefix_caching.html
• Zheng et al., SGLang: Efficient Execution of Structured Language Model Programs — RadixAttention, the trie-based alternative to hash-chain prefix caching; great contrast read: https://arxiv.org/abs/2312.07104
• Kwon et al., PagedAttention (SOSP 2023), §4.4 — sharing & copy-on-write in the original design: https://arxiv.org/abs/2309.06180

Lab 02-06 — Paged Attention in Pure Numpy [CPU-OK]

The whole phase, you've been told the kernel "just follows the block table." Here you make that sentence true with your own hands — no GPU, no Triton, no excuses. You'll implement the complete data path of one decode step: build the slot_mapping (the write map), scatter new K/V into a shuffled physical cache (write_kv), then gather it all back through the block table and compute attention (paged_attention) — and prove, to 1e-12, that the result is identical to attention over a contiguous cache.

Do this lab before lab-04 (Triton) — it's the same algorithm; lab-04 just adds the GPU dialect and the online-softmax streaming. If you have no GPU, this lab is your kernel lab, with nothing lost but the silicon.

Contents

• Why this lab exists
• Background: two maps, two directions
• Files
• Run
• What to implement
• What the tests prove — including the poison trick
• Hitchhiker's notes
• Going further
• References

Why this lab exists

There's a gap in most people's understanding of PagedAttention, right between "the allocator hands out block ids" (labs 01–05) and "the CUDA kernel is fast" (lab-04, Phase 4). The gap is the data path: how, concretely, does a token's K vector end up at a physical address, and how does attention find it again? Numpy is the perfect language for closing that gap — fancy indexing makes the scatter and the gather each a single line, so the indirection stands alone with zero kernel noise around it.

The deeper point this lab proves is the load-bearing theorem of the whole phase:

Gather-through-a-table is mathematically the identity. Paging changes where bytes live, never what they mean. Attention over a paged cache is not an approximation of dense attention — it is dense attention, composed with a permutation.

The tests don't just claim this; they check it to 1e-12 (same dtype, same operation order ⇒ the only differences would be real bugs, not float noise), and then check it twice — same logical content under two different physical layouts must produce bit-identical answers. When you later benchmark real paged kernels and someone asks "but does paging hurt accuracy?", you'll have the right reflex: it can't; only masking or indexing bugs can.

Background: two maps, two directions

Each engine step, the model runner (upstream: gpu_model_runner.py) turns the scheduler's block tables into two tensors for the kernels — and they answer opposite questions:

• slot_mapping — write map, one entry per scheduled token this step: "put this new token's K/V at this flat cache row." For a decode step that's a single entry per request (start = current length, num_tokens = 1); for a prefill chunk it's the chunk's whole range. The formula is the phase's one formula: slot(t) = block_table[t // block_size] * block_size + t % block_size.
• block_table — read map, one entry per logical block of the whole sequence: "all prior KV for this request lives in these physical blocks, in this logical order." The attention kernel gathers through it every step.

Write one token; read them all. That asymmetry is the decode workload in a nutshell, and it's why decode is memory-bandwidth-bound: the gather touches seq_len × heads × dim × 2 values to produce one token.

Files

• starter.py — three functions with the recipes in their docstrings. Your work.
• solution.py — reference (the gather really is one line).
• test_lab.py — formula checks, round-trip, dense-equivalence, the poison-masked tail, and the two-layouts identity.

Run

LAB_IMPL=starter pytest phase-02-paged-attention/labs/lab-06-paged-attention-numpy -q
pytest phase-02-paged-attention/labs/lab-06-paged-attention-numpy -q   # reference (default)

What to implement

1. build_slot_mapping(block_table, block_size, start, num_tokens) — the formula, over a token range. The start parameter is not decoration: a decode step writes one token at start = seq_len, a chunked prefill writes a range starting mid-sequence — getting ranges right here is exactly what makes chunked prefill (Phase 3) compose with paging.
2. write_kv(...) — scatter new_k/new_v rows to slot_mapping rows. Numpy fancy indexing (cache[slots] = new) — one line each, and a quiet preview of what reshape_and_cache does in CUDA upstream.
3. paged_attention(q, k_cache, v_cache, block_table, seq_len, block_size) — gather seq_len rows through the table, then per head: softmax(K·q/√d)·V. Subtract the max before exp (the standard stability trick — and the seed of the online softmax you'll meet in lab-04).

What the tests prove — including the poison trick

That poison-the-padding trick is worth stealing for every masked computation you ever test: don't hope the unmasked path is never read — make reading it catastrophic.

Hitchhiker's notes

• Your gather is a memcpy the GPU never does. k_cache[slots] materializes a contiguous copy of K — fine in numpy, ruinous on a GPU (it would double memory traffic for the engine's hottest loop). The real kernel follows the indirection inside the compute, loading each block tile straight from its physical address into registers/SRAM. Same semantics, zero copies — that difference is the entire reason kernel-level paging support (lab-04) has to exist at all, rather than a gather-then-dense-kernel two-step.
• Why per-head loops? Clarity. Attention is independent per head; vectorizing over heads (einsum) is a one-liner you should try after green, and it changes nothing semantically. The real kernel parallelizes over (sequence, head) pairs — your loop nest, mapped to the GPU grid.
• 1e-12, not 1e-2. Lab-04 tolerates 1e-2 because fp16 + a different operation order (online softmax) genuinely changes rounding. Here, same dtype (float64) and same order mean the comparison can be essentially exact. Calibrating tolerance to the reason for divergence — instead of slapping 1e-3 on everything — is a numerics habit that catches real bugs other suites wave through.
• GQA fits in one index. Llama-style models have fewer KV heads than query heads; the cache shape grows a num_kv_heads dimension and several query heads share a KV head. The block table doesn't change at all — paging is orthogonal to head layout. (Try it: KV_HEADS = 2, map query head h to KV head h // 2. Ten lines.)

Going further

• Batch it: extend paged_attention to take a batch of queries with a ragged set of block tables and seq_lens — now you've implemented the actual decode-batch kernel interface (compare with paged_attention_v1.cu's argument list: it's your signature, plus strides).
• Chunked-prefill write path: simulate prefilling a 40-token prompt in chunks of 16 using build_slot_mapping(start=16, ...) etc., then attend. You've just verified the Phase 3 invariant (chunking changes when, never what) at the memory level.
• Measure the gather tax in numpy: time k_cache[slots] vs a contiguous slice of the same size for seq_len = 64k. The scatter-gather costs real bandwidth even on CPU — now reread lab-04's note on why GPUs fold it into the kernel.

References

• upstream/vllm/v1/worker/gpu_model_runner.py — search slot_mapping: where both maps are built from scheduler output, every step.
• upstream/csrc/cache_kernels.cu — reshape_and_cache: your write_kv, in CUDA.
• upstream/csrc/attention/paged_attention_v1.cu — your paged_attention, with the performance engineering attached.
• Kwon et al., PagedAttention (SOSP 2023), §4.3 — kernel-side gather design: https://arxiv.org/abs/2309.06180
• Milakov & Gimelshein, Online normalizer calculation for softmax (2018) — what your max-subtraction becomes when the row streams in blocks: https://arxiv.org/abs/1805.02867

Phase 02 — Exercises: PagedAttention

Escalating from "explain it" to "design it." Staff-level = you can do the last ones cold, and point to the exact upstream/ file that proves your answer.

Contents

• Warm-up (explain)
• Core (trace the code)
• Build (extend your code)
• Design (staff-level)
• Self-grading

Warm-up (explain)

1. In one sentence each, define: block, block table, block pool, ref_cnt, null block.
2. Why is per-request waste bounded by block_size − 1? Where does that one partial block come from?
3. Why does get_computed_blocks cap hits at num_tokens − 1 and not num_tokens? (Hint: deep-dive §5.)

Core (trace the code)

4. Trace BlockPool.touch([b]) when b.ref_cnt == 0 and b is cached. Which list operation runs, what is its complexity, and which real-world event caused this call?
5. Trace get_new_blocks(2) when one popped block is a cached eviction candidate. Which method clears its hash, and why must that happen before ref_cnt is set?
6. KVCacheManager.free frees blocks in reverse order. Construct a 2-request example where forward order would evict the shared prefix too early.

Build (extend your code)

7. Add copy-on-write to your lab-01 pool: fork_block(b) that, when b.ref_cnt > 1, allocates a new block, decrements b, and returns the new one. Write a test: two requests share a block, one forks, the other's view is unchanged.
8. Add a get_usage() sanity test: usage is 0.0 with only the null block used, and approaches 1.0 as you allocate. Why subtract 1 for the null block (block_pool.py:505)?
9. Make your FreeKVCacheBlockQueue track eviction order: when freeing a request's blocks tail-first, assert the head (prefix) block ends up behind the tail block in the queue.

Design (staff-level)

10. A customer serves one 4k-token system prompt to 1,000 users/min, each adding ~50 tokens. Estimate KV memory with and without prefix caching (pick a model from the guide). What's the multiplier prefix caching buys here, and why is it so large?
11. Sketch how you'd add a second block size for a hybrid model (some layers attention, some Mamba). What breaks in a single-block_size design? (Peek: kv_cache_coordinator.py, resolve_kv_cache_block_sizes at kv_cache_utils.py:571.)
12. The free queue is a hand-rolled linked list "to avoid allocating Python objects." Propose a benchmark that would prove a deque is slower here, and predict where the gap shows up.

Self-grading

For 4–6 and 10–12: could you whiteboard it in 5 minutes and name the file? If not, re-read the matching deep-dive section. Bring exercises 10–12 to the INTERVIEW.md drills.

Phase 02 — Interview Questions: PagedAttention

This is the topic to own in any LLM-inference interview — it's vLLM's headline idea and a favorite question. Cover each answer, attempt it out loud, then compare. Depth here is the bar for a topic you claim as your specialty.

Q1. What problem does PagedAttention solve, and how?

Q2. Walk me through the data structures. (Whiteboard them.)

Q3. Why a custom linked list instead of collections.deque for the free list?

Q4. How does prefix caching work on top of paging, and what makes it a prefix cache?

Q5. What happens when there aren't enough free blocks to extend a running request?

Q6. Copy-on-write — when and why?

Q7. (Deep) Why are blocks freed in reverse order, and why doesn't the cache de-duplicate?

Rapid-fire

• Block size is typically? 16. Tradeoff of larger? Less metadata/overhead, more tail waste and coarser sharing.
• What's the null block for? A placeholder for skipped positions (e.g. outside a sliding window); never cached.
• Where does the block table actually get used? Passed into the attention kernel (csrc/attention/paged_attention_v1.cu), which dereferences it per token.
• What sets the number of GPU blocks? Leftover HBM after weights ÷ per-block bytes (kv_cache_utils.get_kv_cache_configs), scaled by gpu_memory_utilization.

Phase 02 — Cheatsheet: PagedAttention

Contents

• The one-liner
• Data structures
• The four invariants
• Key methods → what they do
• Hashing
• Numbers to know
• Gotchas

The one-liner

KV cache → fixed-size blocks (like OS pages) + per-request block table → no fragmentation, plus free sharing (prefix caching, CoW). Waste ≤ block_size − 1 per request.

Data structures

The four invariants

1. in free queue ⟺ ref_cnt == 0 (not null)
2. block ids are append-only / stable (so: no dedup)
3. only full blocks get hashed + cached
4. cached ≠ unusable — touch revives a free cached block (O(1) middle removal)

Key methods → what they do

• get_new_blocks(n) — popleft n, _maybe_evict, ref=1
• touch(blocks) — re-ref a shared block; remove from free queue if it was free
• free_blocks(blocks) — deref; ref→0 returns to queue (stays cached)
• cache_full_blocks(...) — hash + index newly-full blocks
• get_computed_blocks(req) — prefix-cache lookup, hits capped at num_tokens − 1
• allocate_slots(...) — extend a request; returns None on OOM → scheduler preempts
• free(req) — frees reverse order (prefix survives longest)

Hashing

hash_block_tokens(parent_hash, tokens, extra_keys) — parent-chained ⇒ prefix cache. extra_keys = LoRA id + multimodal + cache_salt (no cross-context collisions).

Numbers to know

• KV bytes/token ≈ 2 × layers × kv_heads × head_dim × dtype_bytes
• num GPU blocks ≈ (HBM × gpu_memory_utilization − weights) ÷ per-block bytes
• block_size default ≈ 16

Gotchas

• Returning None from allocate_slots is normal — it drives preemption, not an error.
• The null block (id 0) is reserved; never cache it; subtract it from usage math.
• Line numbers valid only at v0.22.1 @ 0decac0; search the named symbol otherwise.

Full: 00-guide.md · 01-deep-dive.md · INTERVIEW.md

Phase 03 — The Hitchhiker's Guide to Continuous Batching & the Scheduler ⭐

← Phase 02 · Course home · Phase 04 →

Flagship phase — written in full. Phase 02 gave you the memory. This phase gives you the brain that decides who runs each step.

Contents

• Don't Panic
• Step 1: The big idea — there is no "prefill phase" or "decode phase"
• Step 2: Static batching (the bad old way) vs continuous batching
• Step 3: The token budget and chunked prefill
• Step 4: Prefix caching — the free head start
• Step 5: Preemption — the safety valve
• Step 6: The schedule, in order
• The invariants to memorize
• What you'll do in this phase

Don't Panic

The scheduler's whole job, once per token step, is to answer one question:

Given everyone who wants compute right now, and the memory I have, who runs this step and how many tokens does each get?

That's it. Everything famous about vLLM's throughput — continuous batching, chunked prefill, prefix caching, preemption — is just a good answer to that one question, computed fast, every single step. By the end of this phase you'll have written a working continuous-batching scheduler (mini_vllm/scheduler.py) and read the real 2,300-line one (upstream/vllm/v1/core/sched/scheduler.py).

Step 1: The big idea — there is no "prefill phase" or "decode phase"

This is the mental model the entire engine is built on. Read the real comment at the top of Scheduler.schedule() (scheduler.py:330):

"There's no 'decoding phase' nor 'prefill phase' in the scheduler. Each request just has num_computed_tokens and num_tokens_with_spec. … At each step, the scheduler tries to assign tokens to the requests so that each request's num_computed_tokens can catch up to its num_tokens."

So every request is just a pair of numbers racing each other:

prompt = "Tell me a joke"          (4 tokens, say)
                                    num_tokens = 4,  num_computed_tokens = 0

step: schedule 4 tokens  ──►       num_computed = 4  == num_tokens  ─► emit 1 token ("Why")
                                    num_tokens = 5,  num_computed = 4
step: schedule 1 token   ──►       num_computed = 5  == num_tokens  ─► emit 1 token ("did")
                                    num_tokens = 6,  num_computed = 5
...

"Prefill" is just "num_computed is far behind num_tokens." "Decode" is just "it's behind by one, add one more." One uniform rule covers both. This is why chunked prefill, prefix caching, and speculative decoding all fall out naturally instead of needing special cases. Your mini_vllm/request.py is built around exactly this num_computed_tokens vs num_tokens pair — go look.

Step 2: Static batching (the bad old way) vs continuous batching

Static batching: pick a batch of requests, run them together until they all finish, then start the next batch.

time ─►
req A (short):  [#### done...................... idle ..............]
req B (med):    [############# done............. idle ..............]
req C (long):   [############################################ done ]
                 ^ A finished here but its slot sits IDLE until C finishes.

The GPU runs at the speed of the slowest request in the batch, and finished requests waste their slot. Terrible utilization for mixed-length traffic (which is all real traffic).

Continuous batching: re-decide the batch every single step. The instant A finishes, its slot is freed and a waiting request D joins mid-flight.

time ─►
req A:  [#### done]
req B:  [#############done]
req C:  [############################################done]
req D:       [############### done]      ← D joined the moment A left
req E:              [######### done]      ← E joined when B left
                 ^ no idle slots; the GPU is always full.

This is the single biggest throughput win in modern LLM serving, and it's entirely a scheduling decision — same kernels, same model, just smarter batching. vLLM does this by default.

Step 3: The token budget and chunked prefill

If you let a brand-new 8,000-token prompt do its entire prefill in one step, every decode in flight stalls for that whole step → everyone's inter-token latency spikes. Bad.

The fix is a token budget per step: max_num_batched_tokens. The scheduler hands out at most that many tokens total each step. A long prefill gets chunked — split across several steps — so it shares each step with ongoing decodes instead of monopolizing one.

budget = 2048 tokens/step

step 1: [decode A:1][decode B:1] ... [prefill of new req: 2046 of its 8000 tokens]
step 2: [decode A:1][decode B:1] ... [prefill: next 2046 tokens]
...     long prefill drips through the budget while decodes keep flowing.

In your mini_vllm/scheduler.py, this is _clamp_new_tokens (caps each request by the remaining budget and by long_prefill_token_threshold) and the token_budget -= num_new_tokens bookkeeping. The real code is the same idea at scheduler.py:348 (token_budget = self.max_num_scheduled_tokens) and :390 (long_prefill_token_threshold).

Step 4: Prefix caching — the free head start

Remember from Phase 02 that requests can share physical KV blocks. The scheduler exploits this when admitting a waiting request: before allocating, it asks the KV manager "how much of this prompt is already computed?" (get_computed_blocks). If a shared prefix is cached, those tokens are already done — the request starts with num_computed_tokens > 0 for free.

Request A ran earlier with prompt "You are a helpful assistant. <Q1>"  → its prefix blocks cached
Request B arrives with prompt   "You are a helpful assistant. <Q2>"
  scheduler: get_computed_blocks(B) → 6 blocks hit (the shared system prompt)
  B starts with num_computed_tokens = 96, only needs to prefill <Q2>.

For a shared 2k-token system prompt across thousands of users, this is enormous — it's the structural cost advantage behind multi-tenant serving. In mini_vllm, the WAITING loop calls self.kv.get_computed_blocks(request) and sets request.num_computed_tokens = num_cached. Real code: scheduler.py:591.

Step 5: Preemption — the safety valve

Continuous batching admits requests aggressively to keep the GPU full. Sometimes that means a running request needs another KV block and there are none left. What then?

The scheduler preempts: it evicts a running request (frees its KV blocks back to the pool), puts it back on the waiting queue, and gives its memory to someone who can make progress now. The preempted request will be recomputed later when memory frees up (its prompt + generated tokens are replayed; this is cheaper than it sounds thanks to prefill efficiency).

running: [A][B][C]   free blocks: 0
C needs 1 more block → allocate_slots(C) returns None (OOM, Phase 02!)
  → preempt the most-recently-added running request (say C, or the lowest priority)
  → free its blocks, push it back to WAITING, retry

This is the None → preempt → retry handshake from Phase 02, seen from the scheduler's side. In mini_vllm/scheduler.py it's the while True: loop around allocate_slots that pops a victim from self.running and calls _preempt. Real code: scheduler.py:443–491.

Step 6: The schedule, in order

Putting it together, here's the shape of schedule() (yours and theirs):

token_budget = max_num_batched_tokens

# 1) RUNNING first — keep decodes flowing
for request in running:
    n = clamp(request.num_tokens - request.num_computed_tokens, budget, prefill_threshold)
    blocks = allocate_slots(request, n)
    while blocks is None:              # OOM
        preempt(running.pop()); retry
    schedule it; budget -= n

# 2) WAITING next — admit new work if budget + memory + seq-slots remain
while waiting and budget > 0 and len(running) < max_num_seqs and not preempted_this_step:
    request = waiting[0]
    computed_blocks, num_cached = get_computed_blocks(request)   # prefix cache
    request.num_computed_tokens = num_cached
    n = clamp(request.num_tokens - num_cached, budget, prefill_threshold)
    blocks = allocate_slots(request, n, computed_blocks)
    if blocks is None: break          # no memory to admit anyone else
    move request waiting → running; budget -= n

Two subtleties worth noting now (and seeing in the real code):

• Running before waiting: progress for in-flight requests beats starting new ones (latency).
• No admit after a preemption this step: if we just had to preempt, the system is under memory pressure — don't pour more in. (mini_vllm: and not out.preempted_req_ids; real: scheduler.py:545 if not preempted_reqs ...).

The invariants to memorize

1. A request is always either in waiting or running (never both, never neither while unfinished).
2. sum(num_scheduled_tokens) ≤ max_num_batched_tokens every step (the budget holds).
3. len(running) ≤ max_num_seqs every step.
4. A scheduled request emits a token this step iff num_computed_tokens + num_scheduled == num_tokens (prefill fully caught up). Mid-prefill chunks emit nothing.
5. Preemption frees KV and resets num_computed_tokens = 0 (full recompute on re-admit).

What you'll do in this phase

• Read: 01-deep-dive.md walks the real schedule() line by line.
• Build: 02-mini-build.md — write the scheduler (reference: mini_vllm/scheduler.py).
• Labs (see labs/README.md; recommended order 01 → 02 → 05 → 04 → 06 → 03):
  • lab-01-scheduler-step [CPU-OK] — implement the budget + running/waiting loop; pass the tests.
  • lab-02-chunked-prefill [CPU-OK] — prove chunking changes timing, not output, and predict step counts.
  • lab-03-prefix-cache-hitrate [GPU-OPT] — measure real prefix-cache hit rate and its memory effect.
  • lab-04-preemption [CPU-OK] — force a preemption and prove the request still completes correctly.
  • lab-05-decode-latency-spikes [CPU-OK] — measure the ITL spike a long prefill inflicts on a decode stream ([257, 2, 1, ...]) and how the chunk threshold caps it ([33,×8, ...]).
  • lab-06-prefix-cache-savings [CPU-OK] — account for prefix caching to the exact token (544 vs 96 scheduled tokens; savings ≡ followers × shared full blocks), outputs identical.
• Test yourself: EXERCISES.md, INTERVIEW.md, CHEATSHEET.md.

When you can whiteboard schedule() and explain the budget, chunking, prefix head-start, and preemption handshake from memory, you understand the component that defines vLLM's throughput.

← Phase 02 · Course home · Phase 04 →

Phase 03 — Deep Dive: the real vLLM Scheduler

Paths relative to upstream/ at v0.22.1 @ 0decac0 (UPSTREAM_PIN.md). The scheduler is vllm/v1/core/sched/scheduler.py (~2,300 lines). We read the parts that matter; the rest is connectors, encoders, spec-decode glue, and stats — return to those after Phases 8, 13, 15.

Supporting files:

vllm/v1/core/sched/
  scheduler.py       Scheduler.schedule() / update_from_output()   (the brain)
  output.py          SchedulerOutput, NewRequestData, CachedRequestData  (the wire format)
  request_queue.py   FCFS vs PRIORITY queues                       (ordering policy)
  interface.py       SchedulerInterface                            (the contract)
vllm/v1/request.py   Request, RequestStatus                        (the unit of work)

Contents

• 1. The unit of work: Request and its states
• 2. schedule() — the whole algorithm
  • Setup (lines 341–362)
  • Phase A — schedule RUNNING requests (lines 364–533)
  • The preemption loop (lines 442–491) — the heart
  • Commit the scheduled running request (lines 493–533)
  • Phase B — admit WAITING requests (lines 544–...)
• 3. The output: SchedulerOutput
• 4. The other half: update_from_output
• 5. Putting Phases 02 + 03 together
• Reading checklist

1. The unit of work: Request and its states

vllm/v1/request.py:315, RequestStatus:

class RequestStatus(enum.IntEnum):
    WAITING = enum.auto()
    WAITING_FOR_STRUCTURED_OUTPUT_GRAMMAR = enum.auto()
    WAITING_FOR_REMOTE_KVS = enum.auto()
    WAITING_FOR_STREAMING_REQ = enum.auto()
    RUNNING = enum.auto()
    PREEMPTED = enum.auto()
    # Note: anything after PREEMPTED will be considered as a finished status.
    FINISHED_STOPPED = enum.auto()
    FINISHED_LENGTH_CAPPED = enum.auto()
    FINISHED_ABORTED = enum.auto()
    ...

Two things to internalize:

• The extra WAITING_FOR_* states exist because a request can be not ready for reasons beyond "queued": waiting on a grammar to compile (Phase 12), on remote KV to arrive (Phase 15), etc. Your mini_vllm.RequestStatus keeps just WAITING/RUNNING/PREEMPTED/FINISHED_* — the essential skeleton.
• The ordering trick: is_finished is simply status > PREEMPTED (line 337). Enum order is the logic. mini_vllm copies this (is_finished = status >= FINISHED_STOPPED).

The master variables on Request: num_computed_tokens vs num_tokens (and num_tokens_with_spec for speculative decoding). Everything in schedule() manipulates these.

2. schedule() — the whole algorithm

vllm/v1/core/sched/scheduler.py:329. The defining comment (lines 330–339) — read it; it's the mental model from the guide, verbatim from the maintainers.

Setup (lines 341–362)

scheduled_new_reqs, scheduled_resumed_reqs = [], []
scheduled_running_reqs, preempted_reqs = [], []
req_to_new_blocks: dict[str, KVCacheBlocks] = {}
num_scheduled_tokens: dict[str, int] = {}
token_budget = self.max_num_scheduled_tokens          # <- the per-step token budget
...
self.kv_cache_manager.new_step_starts()

token_budget is max_num_scheduled_tokens (derived from max_num_batched_tokens). This is the global cap that makes chunked prefill work. mini_vllm: token_budget = self.max_num_batched_tokens.

Phase A — schedule RUNNING requests (lines 364–533)

req_index = 0
while req_index < len(self.running) and token_budget > 0:
    request = self.running[req_index]
    ...
    num_new_tokens = (
        request.num_tokens_with_spec
        + request.num_output_placeholders
        - request.num_computed_tokens
    )
    if 0 < self.scheduler_config.long_prefill_token_threshold < num_new_tokens:
        num_new_tokens = self.scheduler_config.long_prefill_token_threshold   # chunk long prefills
    num_new_tokens = min(num_new_tokens, token_budget)                        # respect the budget
    num_new_tokens = min(num_new_tokens, self.max_model_len - 1 - request.num_computed_tokens)

num_new_tokens = how far this request is behind, clamped by (a) the long-prefill chunk threshold and (b) the remaining token budget and (c) the model length. This four-line clamp is exactly your mini_vllm.Scheduler._clamp_new_tokens (minus spec/placeholder terms). Note num_tokens_with_spec includes draft tokens — that's how speculative decoding (Phase 8) rides the same scheduler with no special case, just as the top comment promised.

The preemption loop (lines 442–491) — the heart

with record_function_or_nullcontext("schedule: allocate_slots"):
    while True:
        new_blocks = self.kv_cache_manager.allocate_slots(
            request, num_new_tokens, num_lookahead_tokens=self.num_lookahead_tokens,
        )
        if new_blocks is not None:
            break                                  # got memory; schedule it

        # The request cannot be scheduled. Preempt the lowest-priority request.
        if self.policy == SchedulingPolicy.PRIORITY:
            preempted_req = max(self.running, key=lambda r: (r.priority, r.arrival_time))
            self.running.remove(preempted_req)
            ...
        else:
            preempted_req = self.running.pop()     # FCFS: preempt the most-recent

        self._preempt_request(preempted_req, scheduled_timestamp)
        preempted_reqs.append(preempted_req)
        if preempted_req == request:
            break                                  # nothing left to preempt; give up this req

if new_blocks is None:
    break

This is the None → preempt → retry handshake with the KV manager (Phase 02 §5). Under FCFS it preempts self.running.pop() — the most recently admitted, i.e. lowest priority by arrival. Under PRIORITY it preempts the worst (priority, arrival_time). mini_vllm implements the FCFS branch (self.running.pop() + _preempt) — the PRIORITY branch is a great extension exercise.

_preempt_request (line 929) frees the KV and resets the request to be recomputed. Compare mini_vllm.Scheduler._preempt: frees KV, num_computed_tokens = 0, status PREEMPTED, back to the front of waiting.

Commit the scheduled running request (lines 493–533)

scheduled_running_reqs.append(request)
req_to_new_blocks[request_id] = new_blocks
num_scheduled_tokens[request_id] = num_new_tokens
token_budget -= num_new_tokens                     # <- budget bookkeeping
req_index += 1
# ... spec-decode + encoder bookkeeping ...

Phase B — admit WAITING requests (lines 544–...)

if not preempted_reqs and self._pause_state == PauseState.UNPAUSED:
    while (self.waiting or self.skipped_waiting) and token_budget > 0:
        if len(self.running) == self.max_num_running_reqs:
            break
        ...
        request = request_queue.peek_request()
        ...
        # Get already-cached tokens.
        if request.num_computed_tokens == 0:
            new_computed_blocks, num_new_local_computed_tokens = (
                self.kv_cache_manager.get_computed_blocks(request)      # <- prefix caching!
            )
            ...

Three gates before admitting anyone (mirrored in mini_vllm):

1. if not preempted_reqs — don't admit new work in a step where we had to preempt (memory pressure). (mini_vllm: and not out.preempted_req_ids.)
2. token_budget > 0 — budget left.
3. len(self.running) == self.max_num_running_reqs: break — the seq-slot cap (max_num_seqs).

Then get_computed_blocks(request) is the prefix-cache head start (Phase 02 §5, guide §4): the request adopts the cached prefix and only prefills the remainder. The LoRA constraint just below (lines 573–584) caps distinct adapters per step (max_loras, Phase 11) — another feature riding the scheduler.

3. The output: SchedulerOutput

vllm/v1/core/sched/output.py:181. What the scheduler hands the executor:

@dataclass
class SchedulerOutput:
    scheduled_new_reqs: list[NewRequestData]          # first-time-scheduled (full payload)
    scheduled_cached_reqs: CachedRequestData          # already-running (just deltas)
    num_scheduled_tokens: dict[str, int]              # req_id -> tokens this step
    total_num_scheduled_tokens: int
    scheduled_spec_decode_tokens: dict[str, list[int]]
    scheduled_encoder_inputs: dict[str, list[int]]
    num_common_prefix_blocks: list[int]
    finished_req_ids: set[str]
    ...

The split between NewRequestData (line 31 — full prompt, block_ids, sampling params) and CachedRequestData (line 112 — just new tokens + new block ids) is a real optimization: for a request already running, you don't resend the prompt every step, only the delta. mini_vllm simplifies this to one num_scheduled_tokens dict + the request objects, but the idea — send new requests in full, running requests as deltas — is worth knowing.

4. The other half: update_from_output

vllm/v1/core/sched/scheduler.py:1283. After the model runs and the sampler produces tokens, the scheduler ingests the results: append sampled tokens, advance num_computed_tokens, detect finished requests, free their KV, handle spec-decode acceptance/rejection, emit stats. Your mini_vllm.Scheduler.update_from_output is the skeleton: num_computed_tokens += n; if a token was sampled, append it and check stop conditions; reap finished requests (free KV, drop from running).

The condition for "did this request emit a token this step" in mini_vllm is needs_sample = (num_computed_tokens + num_scheduled == num_tokens) — only fully-caught-up (prefill-complete) requests sample. The real engine encodes the same thing through the model runner's logits-indices selection; the principle is identical (you only sample at the last position of a request that has no more prompt to ingest).

5. Putting Phases 02 + 03 together

The clean separation you should now see:

Scheduler (policy: who runs, how many tokens)  ──calls──►  KVCacheManager (truth: is there memory?)
        ▲                                                          │
        └──────────────  None  ◄── allocate_slots ◄───────────────┘   (OOM signal)
        │
        └─ responds: preempt a running request, free its KV, retry

The scheduler never touches blocks directly; the KV manager never decides policy. That clean seam is why each file stays readable despite the engine's complexity — and it's a design lesson worth stealing for your own systems.

Reading checklist

Write one sentence each in your notebook:

• The top comment of schedule() — restate the "no prefill/decode phase" idea in your words.
• The 4-line num_new_tokens clamp — what are the three caps and why each?
• The while True preemption loop — what does allocate_slots returning None trigger?
• FCFS vs PRIORITY preemption victim selection — who gets preempted in each?
• The three gates before admitting WAITING requests.
• get_computed_blocks in Phase B — how does prefix caching give a free head start?
• NewRequestData vs CachedRequestData — why send deltas for running requests?

Now build it: 02-mini-build.md, then the labs.

Phase 03 — Mini-Build: the continuous-batching scheduler

You'll build the scheduler that drives mini_vllm. The reference is already in the repo — mini_vllm/scheduler.py — but write it yourself first against lab-01's stub + tests, then diff.

This phase's mini-build depends on Phase 02's KV manager (mini_vllm/kv_cache.py), because the scheduler's whole interaction with memory is allocate_slots / get_computed_blocks / free. That dependency is the point: scheduling and paging are two halves of one machine.

Contents

• The build, in order
  • 1. SchedulerOutput
  • 2. Scheduler.__init__
  • 3. _clamp_new_tokens(num_new_tokens, token_budget)
  • 4. schedule() — the two-phase loop
  • 5. _preempt(request)
  • 6. update_from_output(output, sampled)
  • 7. needs_sample(request, num_scheduled) (static)
• Definition of done
• Stretch (sets up later phases)

The build, in order

1. SchedulerOutput

A small dataclass: num_scheduled_tokens: dict[str,int], scheduled_requests: list[Request], preempted_req_ids: list[str], and a total_num_scheduled_tokens property. (Real: output.py:181, much richer.)

2. Scheduler.__init__

Hold the KVCacheManager, max_num_seqs, max_num_batched_tokens, long_prefill_token_threshold, and two queues: waiting: deque[Request], running: list[Request].

3. _clamp_new_tokens(num_new_tokens, token_budget)

Apply the long-prefill chunk cap (if 0 < threshold < num_new) then min(num_new, budget), floored at 0. This single helper is chunked prefill. (Real: scheduler.py:390–392.)

4. schedule() — the two-phase loop

• Phase A (running): for each running request, n = _clamp_new_tokens(num_tokens − num_computed, budget); allocate_slots; on None, pop a victim from running, _preempt it, record it, retry; commit and budget -= n.
• Phase B (waiting): while waiting and budget>0 and len(running)<max_num_seqs and not preempted: peek the front request; get_computed_blocks → set num_computed_tokens; n = _clamp_new_tokens(...); allocate_slots(req, n, computed_blocks); on None break; else move waiting→running, commit.

5. _preempt(request)

kv.free(request); num_computed_tokens = 0; num_preemptions += 1; status PREEMPTED; waiting.appendleft(request) (re-admit ASAP).

6. update_from_output(output, sampled)

For each scheduled request: num_computed_tokens += n; if it sampled, append the token and maybe_finish(). Reap finished requests: remove from running, kv.free.

7. needs_sample(request, num_scheduled) (static)

return request.num_computed_tokens + num_scheduled == request.num_tokens. Only fully-caught-up requests emit a token (mid-prefill chunks don't).

Definition of done

pytest mini_vllm/test_scheduler.py -q          # the reference suite (token budget, chunking,
                                               # preemption, prefix head-start)
pytest phase-03-continuous-batching-scheduler/labs -q

Then run the full engine and confirm the scheduler's correctness invariants hold end to end:

pytest mini_vllm/test_engine.py -q
# test_chunked_prefill_matches_unchunked_output and
# test_prefix_caching_matches_no_caching_output PROVE that these optimizations change
# *timing/memory*, never *output*. That property is the whole game.

Stretch (sets up later phases)

1. PRIORITY policy — add a priority field to Request and a PRIORITY branch to the preemption victim selection (max by (priority, arrival_time)), mirroring scheduler.py:456.
2. Swapping vs recompute — instead of resetting num_computed_tokens=0 on preempt, "swap" the blocks to a CPU pool and restore them on re-admit. Compare the cost model (recompute is compute, swap is bandwidth) — a real vLLM design axis.
3. Stats — count preemptions, average batch size, and KV usage per step; you'll need these in Phase 18.

Phase 03 Labs — Continuous Batching & the Scheduler

Six labs around the engine's brain. The arc: build the scheduling loop (lab-01), prove chunked prefill safe (lab-02), measure why it exists (lab-05), survive memory pressure with preemption (lab-04), then account for prefix caching exactly (lab-06) and on real hardware (lab-03).

Recommended order: 01 → 02 → 05 → 04 → 06 → 03. (Directory numbers predate labs 05–06: mechanism, then safety, then motive, then the emergency path, then the cache economics.) CPU labs follow the standard contract — starter.py (your work), solution.py (reference), test_lab.py (the spec); default runs the solution, LAB_IMPL=starter grades yours.

# Whole phase (GPU tests auto-skip without CUDA):
pytest phase-03-continuous-batching-scheduler/labs -m "not gpu"

# Grade yourself on one lab:
LAB_IMPL=starter pytest phase-03-continuous-batching-scheduler/labs/lab-01-scheduler-step -q

Contents

• lab-01-scheduler-step [CPU-OK]
• lab-02-chunked-prefill [CPU-OK]
• lab-03-prefix-cache-hitrate [GPU-OPT]
• lab-04-preemption [CPU-OK]
• lab-05-decode-latency-spikes [CPU-OK]
• lab-06-prefix-cache-savings [CPU-OK]
• What you can do after this phase

Labs

lab-01-scheduler-step [CPU-OK]

Implement the two-phase loop at the heart of continuous batching: serve RUNNING first (decode-first is a policy, and iteration order is the policy), then admit WAITING — all under three independent scarcities (token budget, sequence slots, KV memory) enforced at three different points. Your 30 lines are, shape for shape, the core of scheduler.py:329 upstream. Skills: budget/slot/memory enforcement; running-first; head-of-line blocking as a fairness choice; one code path for prefill and decode.

lab-02-chunked-prefill [CPU-OK]

Prove the engine's most important safety property — chunking changes when tokens are computed, never what tokens come out — by running the same deterministic workload under both schedules and diffing token ids. Plus the timing side: predict prefill steps with ceil(prompt/chunk) and know every boundary case. Skills: the causality + sampling-guard argument; output-invariance as a CI-enforceable equality; the chunk-size trade-off.

lab-03-prefix-cache-hitrate [GPU-OPT]

Run the real engine on the canonical workload (long shared system prompt, unique tails) with prefix caching off and on, and read three independent meters that must agree: hit rate (0% → 93.7%), prompt throughput (4–5×), KV usage (~1× the prefix). Annotated capture included for the GPU-less; lab-06 is the exact-arithmetic CPU twin. Skills: constructing sharing-known workloads; reading hit-rate denominators; when caching buys nothing.

lab-04-preemption [CPU-OK]

Force the scheduler's emergency path in a pool where two requests cannot both fit: watch it evict the most-recent admission, let the survivor finish, then replay the victim — and prove the final outputs identical to a roomy pool's. Recovery is just prefill: the two-counters model makes eviction, chunking, and cache hits one code path. Skills: the allocate-or-preempt dance; victim policy as forward-progress argument; the deadlock invariant; pairing "survives Y" tests with "Y actually happened" probes.

lab-05-decode-latency-spikes [CPU-OK]

The motive for chunked prefill, measured: a decode stream's per-step cost profile when a 256-token prompt lands — [257, 2, 1, 1, ...] unchunked vs [33,×8, 2, 1, ...] at threshold 32. Same total work, radically different tail latency; nothing free — the spike spreads into the long prompt's TTFT. Skills: per-victim latency measurement; p99 vs mean; the threshold/budget dial; why aggregate meters hide interference.

lab-06-prefix-cache-savings [CPU-OK]

Account for prefix caching to the exact token: 544 scheduled tokens uncached vs 96 cached, savings ≡ (N−1) × shared full blocks = 448, outputs bit-identical, and a share-nothing control arm that saves almost nothing. Includes the one-token prefill that immediately samples — three phases of rules colliding in a single scheduled token. Skills: the compute odometer; predicting cache value with integer arithmetic; eager caching at allocation time; validating noisy GPU meters against an exact model.

What you can do after this phase

Implement and modify vLLM's scheduling policy with the confidence of someone who has built the loop, proven its invariants, and measured its trade-offs: explain why chunked prefill is default-on (and what threshold to set, from data); predict prefix-cache savings for any workload before enabling it; diagnose a preemption storm from the metrics and name the right knob; and read vllm/v1/core/sched/scheduler.py end to end as a peer. Combined with Phase 2, you now hold the complete control plane — Phase 4 descends into the kernels it commands.

Lab 03-01 — Implement the Scheduler Step [CPU-OK]

The scheduler is the brain of the engine — the component that decides, every single step, who computes and how much. In this lab you implement its core: the two-phase loop (serve the RUNNING, then admit the WAITING) under a global token budget, a sequence-slot cap, and a per-request chunk limit. It is maybe 30 lines of code. Those 30 lines are the difference between a GPU that hums at 90% utilization and one that stutters between overload and idleness — and they are, shape for shape, the same 30 lines at the heart of upstream/vllm/v1/core/sched/scheduler.py.

Contents

• Why this lab exists
• Background: the three scarce resources
• Why running-first is not arbitrary
• Files
• Run
• What schedule_step must do
• What the tests prove — a guided tour
• How this maps to the real engine
• Hitchhiker's notes
• Going further
• References

Why this lab exists

In Phase 1 lab-04 you observed the scheduler's decisions as a trace of per-step batch dicts. Reverse the arrow: now you are the one producing those dicts. Everything you watched — chunking to the budget, deferred admission, mixed prefill+decode batches — must now fall out of code you write. This is the course's central loop made flesh: observe a mechanism, then build it, and the understanding compounds.

It's also the file you will touch most as a contributor. Scheduling policy is where vLLM evolves fastest — priority scheduling, fairness, SLA-aware admission, disaggregated prefill (Phase 15) are all edits to this loop. The deep-dive walks you through the real Scheduler.schedule; this lab makes sure that when you read it, you're recognizing, not learning.

Background: the three scarce resources

Every scheduling decision is a negotiation between three independent scarcities, and the loop checks all three — know which line enforces which:

1. max_num_batched_tokens (the token budget, default 2048–8192 upstream) — caps total tokens computed per step. This is a latency control: step wall-clock time grows with scheduled tokens, so the budget is, almost literally, your inter-token latency dial (lab-05 measures this). The budget is global per step — one pool shared by everyone scheduled.
2. max_num_seqs (the slot cap) — caps how many requests can be RUNNING at once. This bounds per-step fixed overheads and runner state (and, on real hardware, things like CUDA-graph batch-size buckets — Phase 5). It is checked only at admission: an already-running request never re-competes for its slot.
3. KV memory (via kv.allocate(...)) — the hard wall from Phase 2. Unlike the other two, this one can refuse mid-flight (a decode needs one more block and the pool is empty); handling that refusal is preemption, deliberately deferred to lab-04. In this lab, allocation failure during admission simply stops admitting.

Three resources, three different enforcement points. Most scheduler bugs are one resource checked at the wrong point — e.g. counting seqs in the budget loop, or letting an admission overdraw the budget "just this once."

Why running-first is not arbitrary

The loop's order — RUNNING phase, then WAITING phase — encodes a policy with a name: decode-first. The requests already running have users watching tokens stream; a stalled decode is a frozen cursor in somebody's chat window. The waiting requests haven't received anything yet; making them wait one more step costs queueing delay but breaks no stream. So the scheduler protects in-flight experience first and spends whatever budget remains on admissions.

The inverse policy (admit-first) would maximize... nothing useful: it trades visible jitter for marginally earlier admissions. But note the deeper principle, because it generalizes: the loop's iteration order IS the priority policy. Upstream's priority scheduling and preemption-victim selection are both, at bottom, careful answers to "in what order do we iterate, and from which end do we take?"

Files