Paged Attention

Lesson 3 of 4 in The KV Cache.

Knowing how big the cache is was the easy part. The harder question is where to put it — because it grows one token at a time, and nobody knows in advance how long a request will run. Early serving engines took the obvious route: reserve one contiguous slab of GPU memory per request, sized for the longest output the request might produce. That obvious route wastes memory in two ways at once. Internal fragmentation: a request that reserves room for 2,048 tokens but stops after 300 strands the rest of its slab — reserved, empty, unusable by anyone else. External fragmentation: as requests of different sizes come and go, free memory shatters into gaps, each too small to hold a new request’s slab even when the gaps together would be plenty. Kwon et al. (2023) profiled serving systems built this way and reported that only a minority of KV-cache memory ended up holding live token states in the systems they measured — much of the rest was lost to reservation and fragmentation. Wasted cache memory is wasted Throughput: every stranded gigabyte is a request that could have been batched and wasn’t.

Heatmap with two rows of twelve memory slots. Top row, contiguous allocation: three dark slots of live data then three medium reserved-but-empty slots for request A, two dark slots then three medium slots for request B, and one light free slot. Bottom row, paged allocation: five dark slots of live data packed together, two medium partly-filled block slots, and five light free slots. The paged row stores the same live data while freeing five times as many slots.

Toy memory map of twelve cache slots holding the same two requests both ways. Contiguous slabs (top row) strand reserved-but-empty slots inside each slab and leave only one slot free. Paged blocks (bottom row) pack the same live data into scattered fixed-size blocks, leaving five slots free for new requests — the last block of each request may sit partly empty. Slot counts are invented for teaching; the waste pattern is the one Kwon et al. describe. (illustrative — source: Kwon et al. (2023) — PagedAttention (vLLM), arXiv:2309.06180)

vLLM’s PagedAttention (Kwon et al., 2023) fixed this by stealing a fifty-year-old idea from operating systems: stop demanding contiguity. Carve the cache into fixed-size blocks, each holding the keys and values for a small, fixed number of tokens. Give every request a block table mapping its logical token positions to physical blocks that can live anywhere in GPU memory. Allocate a new block only when decode fills the last one; free every block the instant the request completes. Over-reservation disappears — nothing is reserved beyond the current partial block. External fragmentation disappears — every free block is the same size, so any free block fits any request. The only waste left is the tail of each request’s final block. The paper reports that on the authors’ benchmarks this memory efficiency let vLLM batch enough additional requests to serve 2–4× the throughput of the state-of-the-art systems of the time at similar latency — a speedup won almost entirely by wasting less memory, not by computing faster. The idea has since spread across the serving landscape: PagedAttention-style block allocators are now standard equipment in mainstream engines.

The virtual-memory analogy, term by term — PagedAttention is demand paging for the KV cache.
Concept	Operating system	PagedAttention
Unit	Page: fixed-size chunk of physical memory	KV block: keys and values for a fixed number of tokens
Mapping	Page table, one per process	Block table, one per request
Allocation	Demand paging: allocate on first touch	Allocate a fresh block only when decode fills the last one
Contiguity	Virtual addresses contiguous; physical pages scattered	Token positions contiguous; physical blocks scattered
Sharing	Shared pages with copy-on-write between processes	Shared prefix blocks with copy-on-write between sequences — next lesson

Interactive checkpoint quiz (1 questions) — open this page in a browser to take it.