Paged attention applies the operating system idea of virtual memory and paging to the KV Cache. It is what lets a server pack many variable-length sequences into GPU memory with almost no waste, and it is the mechanism that makes Continuous Batching practical.
The problem it solves
Allocating one contiguous KV block per request forces you to reserve for the maximum possible length. Most requests are shorter, so memory is lost to internal fragmentation and over-reservation, often more than half.
How it works
- KV cache is split into fixed-size blocks (pages), each holding the keys and values for a fixed number of tokens.
- A per-request block table maps logical token positions to physical blocks, exactly like an OS page table.
- Blocks are allocated on demand as a sequence grows, and need not be contiguous in memory.
- The attention kernel follows the block table to gather K and V.
Payoff
- Memory waste drops to under one block per sequence, so far more sequences fit and batch sizes rise.
- Copy-on-write sharing: several sequences can point at the same physical blocks until one diverges, which is how Prefix Caching and parallel sampling share a prompt’s KV cheaply.
Origin
Introduced by vLLM. The analogy is exact: logical tokens are virtual addresses, blocks are pages, the block table is the page table, and sharing is copy-on-write.