Chapter 8 — Next-Generation KV Cache Management

Eighth post of the chapter-by-chapter walkthrough of LLM Primer VI: Scaling AI Systems. The chapter that brings the operating-system paging insight across into the inference engine — and turns the KV cache from a slab of reserved bytes into a shared, evictable, prefix-cacheable resource.

Why this chapter exists

Chapter 7 left continuous batching holding a debt. Sequences enter and leave every iteration; a naive layout gives each slot its own maximum-sized slab, most of which is wasted; the batching throughput win is partly given back. The debt is internal fragmentation, exactly the failure mode operating systems solved with paging in the 1960s. Chapter 8 is about applying that solution to LLM serving: split the KV cache into small physical blocks, decouple them from logical token positions with a page table, and let eviction and caching policies reclaim or share blocks across sequences. PagedAttention is the foundational move; H2O and InfiniGen are the eviction policies; prefix caching is the technique that lets a production cluster serve millions of agentic requests on a dozen GPUs.

One line: Treat the KV cache like a paged virtual memory — small blocks, a page table, reference-counted sharing — and continuous batching's memory problem stops being a problem.

8.1 PagedAttention is virtual memory for the KV cache

vLLM's PagedAttention paper (2023) lifts the OS insight straight into the engine. The KV cache is split into fixed-size blocks — typically 16 tokens each — held in a flat physical pool. A sequence is represented by a block table: an array of pointers mapping logical positions to physical block IDs. The attention kernel takes the block table as an extra input and gathers keys and values by indirection rather than by contiguous slicing; on Hopper the L2 absorbs the random-access pattern well enough that the kernel runs within a few percent of the slab-based version. The wins are large. Internal fragmentation drops from 60–80 percent to about 4 percent (one partial tail block per sequence), which raises available concurrency 2–4×. Reference-counted block sharing makes complex sampling nearly free — best-of-8 on a 2,000-token prompt drops from 16,800 to 2,800 token-blocks — and it is the substrate that prefix caching builds on.

8.2 H2O and InfiniGen evict the tokens that do not matter

PagedAttention solves fragmentation but does not solve contexts that outgrow VRAM at any layout. A 200,000-token Llama-3-70B context needs 60 GB of KV alongside the weights. H2O ("Heavy Hitter Oracle") observes that attention weights during decoding concentrate on a small set of source positions — recency tokens, attention-sink tokens at the very beginning, and a sparse set of content-relevant hits — while most historical positions get essentially zero weight. The engine tracks an accumulated attention score per position; when the sequence's KV budget nears its cap, it evicts the lowest-scoring positions except for a guaranteed-kept window of recent and sink tokens. The saving is large; the cost is permanence — if a later query needs a position that was evicted, the engine cannot recover. InfiniGen refines the trade with dynamic, recoverable selection: instead of dropping tokens outright, it offloads their KV to CPU memory and pages them back if attention starts to concentrate on them again. The right eviction policy depends on how much a workload re-queries its own long history; agentic workloads punish permanent eviction and reward InfiniGen-style recovery.

8.3 Prefix caching is the highest-impact lever PagedAttention unlocks

In real traffic, the first thousands of tokens of most prompts are identical across requests. A chat service reuses the same system prompt for every conversation. A RAG service pastes the same retrieved passages into the prompt for every user who searched for them. An agent injects the same tool descriptions and reasoning scaffolds at every step. PagedAttention makes sharing mechanical: hash the prompt in block-sized chunks; if the hash is in the global cache of compute-filled blocks, point the new request's block table at the cached block and skip that prefix's prefill entirely; if not, prefill runs and the resulting block is registered. Production hit rates are dramatic — above 99 percent for a chat service's system prompt, 30–60 percent for RAG retrieval-dependent prefixes, near 1.0 for an agentic scaffold. SGLang's RadixAttention takes the idea further with a radix-tree that keys shared prefixes of any length, not just block-aligned ones. Prefix caching is the single technique that most often turns an over-budget serving cluster into an under-budget one.

Worth holding onto: If your workload has a shared system prompt, a shared tool-scaffold, or a stable retrieval corpus, prefix caching is likely the highest-ROI switch you can flip. Measure hit rate before assuming your engine has it enabled; the number tells you how much of your prefill you are paying for twice.

What Chapter 8 sets up

Paging, eviction, and prefix caching have shrunk the per-token KV footprint and made the engine's memory behavior tractable at high concurrency. What none of them address is the fundamental sequential dependency of decoding: one output token per iteration, per sequence, no matter how many slots are active. Chapter 9 takes on that constraint with speculative decoding — the family of techniques that predicts several tokens ahead with a cheap draft and verifies the guess in a single expensive forward pass, breaking the one-token-per-step floor for the sequences that matter most for user-perceived latency.

Next — Chapter 9: Speculative Decoding. Draft, verify, and the arithmetic of when speculation pays off.

Want the full picture? The book chapter includes the runnable paged-KV data-structure code, the vLLM and SGLang configuration flags for prefix caching, the H2O eviction tuning knobs, the InfiniGen offload-and-recover mechanism, and the reference architecture that composes all four into a production KV stack. View LLM Primer VI on Amazon →