Why architecture matters here
The economics of LLM serving reduce to a single ratio: how many requests can decode concurrently per GPU. Decode is memory-bandwidth-bound — each step reads the entire model plus the batch's KV cache — so throughput scales with batch size until memory runs out. KV memory is therefore the scarce resource, and the pre-paging allocation model wasted most of it three ways: internal fragmentation (a request reserved for 2048 tokens finishes at 180, having pinned 90% of its slab for nothing), external fragmentation (freed slabs of odd sizes cannot fit new requests despite ample total free memory), and reservation waste (memory held for tokens not yet generated, unreadable and unshareable). vLLM's original measurements put usable KV utilization under contiguous allocation at 20-40%; paging lifted it past 90%, which translated directly into 2-4x throughput on identical hardware.
Paging also unlocks structural sharing that contiguous layouts cannot express. Production traffic is drenched in repeated prefixes — system prompts, few-shot preambles, multi-turn histories, the shared stem of parallel sampling (n>1, beam search). With block-granular mapping, every request whose first 512 tokens match can point its first 32 block-table entries at the same physical blocks: prefill for those tokens is skipped entirely (time-to-first-token drops by the shared fraction) and the memory is paid once, ref-counted, copy-on-write on divergence.
Finally, paging changes the failure shape of an overloaded server. Without it, admission control must be pessimistic — assume max length, refuse work the GPU could actually handle. With it, the scheduler can admit optimistically and preempt gracefully: evict a low-priority sequence's blocks to CPU memory or drop them for recomputation, resume later. Overload degrades throughput instead of exploding.
The architecture: every piece explained
Top row: the actors. Requests arrive with prompts and grow token by token. The scheduler runs continuous batching — every decode step it re-forms the batch from whoever is ready, admitting new requests the moment blocks free up. The block manager is the allocator: a free list of physical block indices, a reference count per block, and the accounting that answers the scheduler's one question — can I admit/grow this sequence right now?
Middle row: the mapping. Each sequence owns a block table: entry i names the physical block holding logical tokens [16i, 16i+16). Appending a token usually writes into the current partial block; every 16th token allocates a fresh block from the free list — any free block, anywhere in the pool, since contiguity no longer matters. The physical pool is a single preallocated tensor per layer (num_blocks x block_size x heads x head_dim for K and V), sized at startup from gpu_memory_utilization after weights and activation workspace. The prefix cache indexes immutable full blocks by a chained hash of their token ids; a new request's prompt is hashed block-by-block, and every hit becomes a ref-count bump instead of prefill compute plus fresh memory. Divergence triggers copy-on-write: writing into a block with refcount > 1 first copies it, exactly like a forked process's pages.
Bottom row: where the indirection is paid. The paged attention kernel computes, for each query head, attention over K/V gathered via the block table — an extra integer lookup per block versus a dense layout. The kernel hides this by processing whole blocks per thread group and overlapping index arithmetic with HBM reads; measured overhead sits in the single-digit percent range, dwarfed by the 2-4x batch-size win. The preemption path is the pressure valve: under memory pressure the scheduler picks victims (typically latest-arrived or lowest-priority), either swapping their blocks to pinned CPU memory over PCIe or simply freeing them and recording that the sequence must re-prefill from its tokens later — recompute is often cheaper than swap for short sequences, swap for long ones.
End-to-end flow
Admission and prefill. A request arrives: 700-token prompt, of which the first 512 match a cached system prompt's block chain. The manager bumps refcounts on 32 shared blocks and allocates 12 fresh ones for the remainder; prefill runs only over tokens 513-700, writing their K/V through the block table. Time-to-first-token just shrank by roughly the shared fraction, and the pool paid 12 blocks instead of 44.
Steady decode. Each step, the scheduler assembles the running batch — say 180 sequences — and launches the model. The paged attention kernel reads each sequence's K/V through its block table; the new token's K/V is appended into each sequence's current partial block. Sequence A crosses a 16-token boundary this step: one pop from the free list, one new block-table entry, no other sequence affected. A finished sequence releases its table; every block whose refcount hits zero returns to the free list — and, if prefix-cache-eligible, may instead linger in the cache under LRU until pressure evicts it.
Fork. A request asks for n=4 samples. All four sequences share the prompt's blocks (refcount 4); each diverges at its first generated token, copy-on-writing only the final partial block. Four beams cost one prompt's memory plus four tails — this is why parallel sampling is nearly free under paging and ruinous without it.
Pressure and preemption. A burst of long-context requests drains the free list below the watermark. The scheduler stops admitting, then preempts: the youngest sequence's 60 blocks are swapped to CPU (or dropped for recompute), its state parked. Decode continues for the survivors at full batch. Seconds later, completions free enough blocks; the victim's blocks swap back in, its table is rebuilt, and it rejoins the batch — the user saw added latency, not an error. The watermark, victim policy, and swap-vs-recompute choice are the scheduler's three pressure dials.