HOW VLLM WORKS

Module 6 derived how much memory paging recovers. This concept is about the data structure that recovers it.

The KV cache is never reserved for a sequence's maximum possible length. Instead it is carved into fixed-size blocks — 16 tokens each, in vLLM's original design — drawn from a single pool shared by every sequence resident on the GPU. Each sequence owns a block table: a small array mapping its logical block indices (0, 1, 2, …, in the order the sequence filled them) to physical block indices anywhere in that shared pool. That is exactly the indirection an operating system uses for virtual-memory pages, mapped onto a much smaller address space — a sequence at 8k context needs 512 logical blocks, not the millions of pages a real OS manages, so the whole table for one sequence is a couple of kilobytes (the math lab makes this precise).

A sequence claims a new physical block only when its current one fills — after its 17th token, not before. Allocation tracks actual usage instead of a worst-case reservation, which is the entire mechanism behind Module 6's fragmentation numbers: nothing is wasted because nothing is reserved ahead of need.

The attention kernel has to cooperate with this or the indirection is pointless. Given a block table and a slot mapping — which physical slot each token in the current step's batch belongs to — a paged-attention kernel gathers the right K and V vectors from scattered physical memory instead of assuming one contiguous run per sequence. This is the detail Module 7's kernel material calls out: paging changes the memory access pattern attention has to support, not just the allocator sitting above it. A kernel written for a contiguous cache cannot serve a paged one; the two were co-designed.

One consequence worth stating plainly, because it explains why the mechanism is boring rather than clever: nothing here is lossy. Every byte in the cache is still exactly the K and V vectors the model would have produced with a contiguous buffer. Paging is pure bookkeeping — it changes where bytes live, never what they are — which is why Module 6 could call it free.

Module 5 established why continuous batching beats static batching: intensity equals batch size, so an idle slot is wasted arithmetic, and a static batch runs at the speed of its slowest member. This concept is the loop that implements that idea inside vLLM specifically.

The scheduler runs once per iteration, and one iteration is one forward pass — not one request processed to completion. Every sequence vLLM is tracking sits in one of three states: running (it will advance by one token this iteration, if it can), waiting (admitted to the system but not yet given a first block), or swapped (preempted, its cache moved to host memory rather than dropped — the alternative to the recomputation policy the next concept covers). Each step, the scheduler decides who moves between those states before anyone's forward pass runs.

Admission is deliberately cheap: a waiting sequence only needs one free block to start, not its eventual total, because paging means "start" and "reserve everything you might need" are different operations for the first time. That is what makes iteration-level scheduling affordable — Orca established the scheduling idea in 2022, a year before PagedAttention, using a coarser memory model; vLLM's contribution was making the memory side cheap enough that the scheduling side could run this fine-grained.

Chunked prefill (Module 5's Sarathi-Serve material) is not a separate scheduling mode bolted on afterward — it is one more admission rule inside the same loop. Instead of running a long prompt's prefill as one uninterrupted unit that blocks every decode step behind it, the scheduler caps how many prefill tokens it will admit in a single iteration and carries the rest over to the next one, interleaving those chunks with whatever decode work is already running. The loop does not change; what counts as "one iteration's work" gets more flexible.

The property worth holding onto, because the next two concepts are both about what threatens it: a sequence can enter or leave the batch on any single step. Nothing waits for a fixed-size batch to drain. That is only true as long as the scheduler can always find a free block for whoever needs one next — which is exactly the condition the next concept is about losing.

Every promise the last concept made — cheap admission, a sequence joining or leaving on any step — depends on a free block being available when a running sequence needs one. Sometimes none is. The scheduler then preempts the lowest-priority running sequence rather than failing the request in front of it.

There are two ways to do it. Swap copies the victim's blocks to host DRAM over PCIe and copies them back when the sequence is re-admitted — the cache survives, at the cost of a round trip over a link roughly 50 to 60 times slower than HBM. Recompute simply drops the blocks and reruns prefill over the sequence's tokens-so-far once it is rescheduled — no host memory required, at the cost of redoing work the GPU had already done once.

The intuition most people reach for is "recompute is cheap for short sequences, swap wins once a sequence is long enough that its cache is expensive to redo." The math lab in this level does the arithmetic and that intuition turns out to be incomplete: under the same linear-in-length approximation these chapters use for prefill FLOPs everywhere else, both costs scale with sequence length, which means their ratio is constant — for Llama-3-8B on an H100 with a real PCIe link, swap comes out cheaper than recompute at every length, not just long ones. What actually produces a length-dependent crossover is something the simple bytes-and-FLOPs model leaves out entirely: a fixed per-transfer overhead on the swap path — DMA setup, driver bookkeeping, synchronization — that does not shrink with sequence length. Work through the math lab and you will find that overhead only has to be small for the crossover to sit at a handful of tokens, which reframes the folklore rather than simply confirming it.

Victim selection is its own small policy question, independent of swap-versus-recompute. FCFS — preempt whoever was admitted most recently — is simple, requires no bookkeeping about how close anyone is to finishing, and is close to what vLLM defaults to. It is not obviously optimal: a sequence one token from completion is a strange thing to throw away over a sequence that just started, and the code lab's stretch goal asks you to try a policy that accounts for it.

One thing every version of preemption costs that neither policy avoids: it is visible to the preempted request as a latency spike, not a throughput loss. The GPU is still working the whole time; the victim's user is the one waiting.

Parallel sampling (several completions from one prompt) and beam search both start several sequences from an identical prefix. Duplicating that prefix's cache once per sequence would waste exactly the kind of memory Module 6 spent an entire level recovering.

Because the block table is already an indirection, sharing costs nothing extra to represent — two sequences' block tables can simply point at the same physical block. What they need beyond that is a reference count per physical block, so the allocator knows a block is still in use by someone even after one of its sharers releases it.

Sharing only works cleanly as long as nobody writes to a shared block. The moment two sequences' continuations diverge — sequence A generates one token, sequence B generates a different one, and the position that used to hold "the next slot in the shared prefix" now needs to hold two different things — the block that both were about to write into gets copied first, for whichever sequence is doing the writing, and the two block tables split there. This is copy-on-write, the identical idea operating systems use for fork(): shared as long as possible, copied at the last possible moment, and only the one block that actually diverged, not the whole cache either sequence holds.

The cost model this produces is worth stating precisely, because it is easy to overestimate. Two sequences sharing a 500-token prompt (32 blocks at the standard block size) pay for 32 shared blocks plus exactly one new block each, the moment they first diverge — not 64 blocks, and not a full duplicate cache re-copied on every subsequent token. Copy-on-write is a one-time fork per divergence point, not an ongoing tax.

Copy-on-write shares a prefix between sequences that started life sharing it — one prompt, several samples. It does nothing for two unrelated requests that happen to carry the same 2,000-token system prompt, because as far as the block manager is concerned they are unrelated requests with unrelated block tables. Automatic prefix caching is the mechanism that catches that case too.

Each physical block is hashed on its own token contents, chained with the hash of the block before it — so the hash of block k commits to every token from the start of the sequence through the end of block k, not just the 16 tokens inside it. A new request's first block is hashed and looked up in a table of existing blocks; on a hit, its block table points at the existing physical block (reference-counted, exactly as in copy-on-write) instead of allocating and writing a new one. The lookup then continues into the request's second block using the chained hash, and keeps matching for as long as the new request's prefix keeps agreeing with something already cached — which is why the mechanism only recognises a shared prefix down to a block boundary: a match that starts one token off from where an existing block began is not a match at all under this scheme, hash chains included.

This is the same problem SGLang's RadixAttention solves, with a different structure and a different trade-off. A radix tree matches at the token, not the block, and evicts by tree structure rather than a flat LRU list — more precise, and more machinery. A hash chain over fixed blocks is coarser but is the same block manager every other feature in this level already needs; there is no second data structure to keep consistent with the first. Neither is strictly better; they are the two answers you get from optimizing the same idea against two different constraints, which is exactly the contrast the serving-engines reference page draws between the two projects.

The payoff shows up as time, not memory. A cache hit is prefill work the GPU never does — the math lab prices exactly this for a system prompt shared across fifty concurrent requests, and it shows up as a drop in time-to-first-token, not a change in how many sequences fit.

Module 9 covered tensor and pipeline parallelism as a way of splitting a model too large for one GPU across several. What it did not cover is who runs the scheduler once the model is split — a question this level is now equipped to answer, because the scheduler this level has been describing is a single piece of sequential logic making yes/no decisions about admission and preemption, and that logic cannot simply be duplicated once per GPU without every replica disagreeing about which blocks are free.

vLLM's answer is a driver process plus worker processes. The driver owns the scheduler and the authoritative block tables — the same structures this level has been describing all along, just now living in exactly one place instead of one per GPU. Each iteration, it decides the batch the way a single-GPU deployment would, then broadcasts that decision — which sequences, which token positions, which block tables — to one worker process per GPU. Each worker holds its shard of the model's weights and runs its slice of the forward pass; under tensor parallelism the workers exchange partial activations through NCCL collectives at the points Module 9 identified, once per attention block and once per MLP block.

The block manager staying single-writer is the detail that makes this whole level's machinery port to multiple GPUs without a redesign. Workers do not negotiate allocation, do not run their own copy of the scheduler, and do not need to agree with each other about which physical block holds which sequence — they simply execute against the block table and slot mapping the driver already computed for them. Every mechanism above — admission, preemption, copy-on-write, prefix-cache lookup — is a decision made exactly once per iteration, by exactly one process, regardless of how many GPUs are executing the result.

What this buys you is that nothing in this level's first five concepts needed to know a second GPU existed. What it costs is a broadcast every iteration and a driver process that is now a sequential bottleneck other systems can choose to remove — which is precisely DistServe's argument in this level's papers, and the reason it is here as the closing citation rather than a footnote.

The single-writer property is also what lets the layout of the cache change without any of this being rewritten. Decode context parallelism — Module 9's answer to the KV-head ceiling, in which each rank holds the blocks for a slice of a sequence's token positions rather than a slice of its heads — changes which physical blocks a given worker is responsible for and adds a collective inside attention. It does not change who allocates them, when they are freed, or what the scheduler decides. A driver that owns every block table can re-shard the cache across ranks; a design where each worker allocated its own could not.