PagedAttention: The KV Cache as Virtual Memory

In the last post we saw exactly what the KV cache holds — K and V for every token, at every layer — and that at real batch sizes it can be larger than the model weights. It also has an awkward shape: it grows one token at a time, and you don’t know how long a response will be. That combination is what makes KV memory hard to manage, and PagedAttention is the idea that made it easy. It’s the single biggest reason a server like vLLM is fast.

The naïve way, and why it bleeds memory

The obvious approach: give each request one contiguous slab of KV memory. But how big? You don’t know the output length in advance, so you reserve for the maximum — say 16 tokens here (in reality, thousands). Now watch what happens with an arena of 8 blocks (4 slots each — 32 slots total), when each request reserves 16 slots:

Only two requests fit, the GPU is 50% wasted, and a third request that needs almost nothing is turned away. Three kinds of waste are stacked here:

• Reserved waste — slots held for tokens that haven’t been generated (and may never be).
• Internal fragmentation — a request that stops early keeps its whole oversized reservation.
• External fragmentation — variable-size contiguous slabs leave gaps too small or awkward to reuse.

This is not hypothetical: pre-PagedAttention serving systems ran at roughly 20–40% KV-cache utilisation. And utilisation is everything — fewer sequences in memory means a smaller batch, and (from the last posts) a smaller batch means the GPU’s memory bandwidth is amortised over less work. Wasted KV memory is wasted throughput.

The idea: treat the KV cache like virtual memory

Operating systems solved this exact problem decades ago. A program thinks it has one big contiguous address space, but physically its memory is scattered across fixed-size pages, mapped by a page table, and handed out on demand. PagedAttention applies that idea verbatim to the KV cache:

• Cut KV memory into fixed-size blocks (a block holds K/V for a fixed number of tokens — vLLM’s default is 16; we’ll use 4 so it fits on screen).
• A sequence’s cache is a list of blocks that need not be contiguous in physical memory.
• Allocate a new block only when the sequence crosses a block boundary — never max_len up front.
• A per-sequence block table maps logical block index → physical block number. That table is a page table.

Watch it allocate

Same three requests as above, but now memory is paged. Step through the arrivals and decode steps and watch blocks get grabbed one at a time — and watch utilisation stay high and Request C actually fit:

By the end, all three requests are resident in 6 blocks, two blocks are still free, and utilisation is 79% — versus 50% and a rejection for the contiguous scheme. The only waste left is the tail of each sequence’s last block (at most block_size − 1 slots), because everything else is handed out exactly when needed.

The block table is a page table

Look at what the allocator built. Each request sees a tidy, contiguous list of logical blocks; physically those blocks are scattered wherever there was room. The block table is the translation between the two:

Request B (logical → physical)
   logical block 0  →  physical #2
   logical block 1  →  physical #3
   logical block 2  →  physical #4     ← grabbed on demand, not next to the others

B's cache LOOKS contiguous to attention; physically it is #2, #3, #4 — could be anywhere.

Bonus: blocks can be shared

Once the cache is blocks with a level of indirection, sequences can point at the same physical block. Two requests that begin with the same system prompt, or several samples generated from one prompt (parallel sampling, beam search), share the prompt’s blocks instead of each storing a copy:

This is the mechanism behind prefix caching: a long shared system prompt is stored once and reused across every request that starts with it, saving both memory and the prefill compute to rebuild it.

When memory runs out: preemption

Blocks make the unhappy path clean too. If every block is taken and a running sequence needs one more, the scheduler preempts a victim sequence — all of its blocks at once — in one of two ways:

• Swap the victim’s KV blocks out to CPU RAM, and swap them back when memory frees up (the analogue of paging to disk).
• Recompute — drop the blocks and, when the sequence resumes, rerun prefill to rebuild its KV cache (often cheaper than swapping for short sequences).

The payoff, and the OS map

Paging takes KV utilisation from ~20–40% to over 96% (waste under one block per sequence). More resident sequences means a bigger batch, and a bigger batch means the weights you stream from VRAM each step are amortised over more work — the throughput lever from the earlier posts. vLLM’s headline 2–4× throughput over prior systems comes largely from this one idea. Every piece maps onto something an OS already does:

Check yourself

What’s next

Paging solves where the KV cache lives so that many sequences fit at once. The companion question is when each sequence runs: how the server interleaves dozens of them so the GPU never idles — even as some finish and new ones arrive mid-flight. That’s continuous (in-flight) batching, and it rides directly on top of the paged memory we just built. Next post.

• Contiguous, max-length KV allocation wastes 60–80% of memory to reservation and fragmentation.
• PagedAttention = fixed-size blocks + a block table + on-demand allocation — KV cache as virtual memory.
• The block table decouples logical from physical, so attention runs over scattered blocks and any free block fits any request.
• Blocks also enable copy-on-write prefix sharing and clean preemption — and push utilisation past 96%.