Why architecture matters here
Throughput in LLM serving is almost purely a batching game. A decode step for one sequence and for sixty sequences costs nearly the same wall-clock time, because decode is memory-bandwidth-bound: the dominant cost is streaming the model weights through the GPU's compute units, and that stream is amortized across every sequence in the batch. Double the batch, nearly double the tokens per second. The only thing standing between you and a bigger batch is KV cache memory — so every byte of cache wasted on reservation or fragmentation is throughput burned.
Contiguous allocation wastes those bytes three ways. Internal waste: reserving max-length slabs for sequences that finish early. External fragmentation: variable-sized slabs leave holes no new sequence fits into, even when total free memory is ample. No sharing: two requests with the same 1,000-token system prompt store two identical copies of its KV. Paging attacks all three: blocks are allocated on demand as tokens are actually generated, all blocks are the same size so any free block serves any sequence, and identical blocks can be shared between sequences with copy-on-write semantics.
The architecture matters beyond raw efficiency because it changes the engine's failure behavior. With on-demand allocation, memory exhaustion is no longer an admission-time impossibility but a runtime event: a batch admitted comfortably can grow itself out of memory as sequences lengthen. The system therefore needs a policy answer — preemption, swapping, or recomputation — and that policy's tuning separates production clusters that degrade gracefully under load from ones that oscillate between OOM and idle. Understanding paging is understanding where your latency SLO actually comes from.
The architecture: every piece explained
Top row of the diagram: admission. Requests queue at the scheduler, which implements continuous batching — the batch is rebuilt every iteration, so a finishing sequence's slot is refilled on the very next step rather than waiting for a batch boundary. Before admitting a sequence, the scheduler asks the block manager whether enough physical blocks exist for its prompt (and a margin for growth). The block manager owns the free pool: at startup the engine profiles a forward pass, subtracts weights and activation headroom from gpu_memory_utilization × HBM, and carves everything left into fixed KV blocks — this is why vLLM logs 'number of GPU blocks' at boot, and why that number is your capacity.
Middle row: the mapping machinery. Each sequence carries a block table — an array where entry i holds the physical block id backing logical tokens [16i, 16i+15]. Appending a token usually writes into the current block; every 16th token grabs a fresh block from the pool and appends an entry. The prefix cache hashes each full block's token ids (chained with its prefix hash); when a new request's prompt blocks match cached ones, the block table simply points at the existing physical blocks with a bumped refcount — prefill for those tokens is skipped entirely. Blocks are immutable while shared; a write to a shared block (sequence divergence, e.g. parallel sampling) triggers copy-on-write: copy the block, update one table, decrement the refcount.
Bottom rows: execution and pressure relief. The attention kernel receives block tables as tensors and gathers K/V through the indirection — the reason paging needs custom kernels rather than stock attention. The forward pass appends the new token's K/V into the right physical block, the sampler picks the next token, and the loop continues. When the pool empties — sequences grew — preemption engages: a victim sequence (typically latest-arrived) releases its blocks and either has its KV swapped to pinned CPU memory for later swap-in, or is simply reset and recomputed from its tokens when memory frees; recomputation is often cheaper than PCIe round-trips for short-to-medium contexts. Telemetry — block utilization, preemption rate, prefix hit rate — closes the loop for operators.
End-to-end flow
Trace one chat request through the engine. It arrives with a 1,200-token prompt: a 900-token system preamble shared by every conversation in this product, plus 300 tokens of user history. The scheduler asks the block manager for backing: 1,200 tokens is 75 blocks. The prefix cache hashes the prompt block-by-block and finds the first 56 blocks (the 900-token preamble, rounded to block granularity) already resident from earlier requests — those are mapped into this sequence's block table refcounted, for free. Only 19 new blocks are allocated, and only ~300 tokens need prefill compute. Admission granted; the request joins the running batch on the next iteration.
Prefill runs the 300 uncached prompt tokens through the model in one (or, with chunked prefill, several interleaved) passes, writing K/V into the 19 fresh blocks. Long prefills are the latency bullies of the batch — a single 100k-token prefill monopolizes an iteration — which is why chunked prefill splits them into slices that interleave with other sequences' decode steps, trading a little prefill time for everyone else's inter-token latency.
Decode then produces one token per iteration. Each step, the kernel gathers this sequence's K/V through its block table, computes attention, appends the new token's K/V (allocating block 76 when token 1,216 crosses the boundary), and samples. Meanwhile the batch around it churns — sequences finish, new ones are admitted. Suppose the pool runs dry at some iteration: the scheduler preempts the youngest sequence, freeing its non-shared blocks (shared preamble blocks just drop a refcount), and our request keeps decoding at full speed. The victim re-enters the queue and, when blocks free up, is recomputed — its user never sees an error, only added latency. On completion, an EOS token or length limit ends the sequence; its private blocks return to the pool, the shared blocks' refcounts tick down, and the preamble stays warm in the prefix cache for the next request.