Why architecture matters here
Without a cache, generating token n requires attention over n tokens whose K and V projections are recomputed from scratch, so producing a sequence of length N costs O(N²) projection work and O(N³)-ish attention in total. With the cache, each step computes projections for exactly one token and attends against stored tensors: total work drops to O(N) projections plus O(N²) attention reads, and — more important in practice — each decode step becomes cheap enough that the GPU is no longer compute-bound but memory-bandwidth-bound: the step time is dominated by streaming the cached K and V through the SMs. Decode speed is, to first order, cache-bytes-read divided by HBM bandwidth.
That inversion drives every architectural decision downstream. Because decode is bandwidth-bound, halving cache size (GQA, quantization) roughly halves step latency at long context — a bigger win than any kernel tweak. Because the cache grows linearly with tokens and lives as long as the request, memory, not FLOPs, caps concurrency: a serving engine that allocates cache poorly runs batches of 4 where a paged allocator runs 40 on the same card. And because two requests that share a prompt prefix compute byte-identical K and V for that prefix, cache sharing is free throughput — chat systems re-sending a 2,000-token system prompt per request are re-buying the same tensors thousands of times a minute.
The cost of getting this wrong is not subtle. Contiguous per-request allocation at max-context size strands 60-80% of reserved memory as internal fragmentation; unbounded contexts convert one greedy request into an OOM that kills the batch; and recomputing prefixes turns a 50ms time-to-first-token into 2 seconds. The KV cache is where inference economics are decided, which is why it deserves the same design rigor as a database buffer pool.
The architecture: every piece explained
Top row: the two phases. Prefill runs the prompt through the model once, in parallel across all its tokens — a compute-bound pass that fills the cache with K and V for every prompt token at every layer. Decode then loops: one new token's Q, K, V are computed; the new K and V are appended to the cache; attention reads Q against all cached keys, weights the cached values, and the sampler picks the next token. The logical shape is [layers, 2, kv_heads, seq_len, head_dim] per sequence, and per-token size is 2 × layers × kv_heads × head_dim × bytes — the constant that converts context length to gigabytes.
Middle row: memory management. The paged allocator (the vLLM insight) divides HBM into fixed-size blocks of, say, 16 tokens' worth of KV per layer, exactly like OS pages. A sequence's cache is no longer contiguous: a block table maps its logical token positions to physical blocks scattered across the pool, and the attention kernel walks the table. Fragmentation collapses to under one block per sequence, so the same GPU holds several times more concurrent sequences. The prefix cache layers copy-on-write on top: blocks holding a shared prompt prefix are reference-counted and mapped into many block tables at once; a request whose prompt hits a cached prefix skips prefill for those tokens entirely.
GQA head sharing shrinks the cache at the model-architecture level: 32 query heads attend against only 8 (or 4, or 1 in MQA) KV heads, cutting cache size 4-32× relative to full multi-head attention with minor quality cost — this is why virtually every model designed since 2023 ships with GQA. KV quantization (fp8, or int4 with per-channel scales) halves or quarters it again, trading a small perplexity bump for doubled batch size.
Bottom rows: policy. The scheduler admits new sequences only when the free-block list can plausibly hold them, and when the pool runs dry it preempts: either swap a victim's blocks to CPU memory (cheap to restore over NVLink/PCIe, expensive in RAM) or drop them and recompute the prefill later (cheap in RAM, expensive in compute). Sliding-window models cap the cache by evicting keys older than the window. The ops strip is what you watch: cache utilization, preemption rate, prefix hit rate, and tokens-per-second per gigabyte.
End-to-end flow
Trace one chat request through a paged-cache serving engine. A user sends a 1,800-token conversation whose first 1,200 tokens (system prompt + few-shot examples) are shared with every other user of the app. The router hashes the token-block sequence and finds the first 75 blocks already resident with refcount 40 — a prefix hit. The scheduler needs blocks only for the 600 unshared tokens plus generation headroom; the free list has them, so the request is admitted immediately instead of queuing.
Prefill runs attention for the 600 new tokens (they still attend against the shared prefix's cached keys — the block table stitches shared and private blocks into one logical sequence). Time-to-first-token is ~90ms instead of the ~450ms a cold prefill would cost. The engine batches this prefill together with decode steps of other in-flight sequences (chunked prefill), so ongoing streams do not stall while the newcomer's prompt is processed.
Decode proceeds at one token per step, the sequence acquiring a fresh block every 16 tokens. At step 200, a burst of new requests exhausts the free list. The scheduler ranks victims — this sequence is mid-generation with high restore cost, so it instead preempts a just-admitted request with 30 blocks, swapping its blocks to pinned host memory. Decode for everyone else continues; the victim resumes two seconds later when blocks free up, its cache copied back rather than recomputed.
The response finishes at 900 generated tokens. The sequence's private blocks return to the free list instantly; the shared prefix blocks merely decrement their refcount. If the user replies within the session-affinity window, the engine's prefix cache still holds the entire prior conversation's blocks, and the follow-up turn prefills only the new user message — the conversation's cost grows incrementally, not quadratically with turns. Multiply this flow by hundreds of concurrent sessions and the block pool, not the model, is the resource being scheduled.