pagedattention

PagedAttention is a memory-management technique for LLM inference that applies operating-system-style virtual-memory paging to the attention key-value (KV) cache. Introduced by the vLLM project, it stores each request's KV cache in small fixed-size blocks scattered anywhere in GPU memory and uses a per-request block table to map logical token positions to those physical blocks — eliminating the large reserved-but-unused regions that classic contiguous allocation leaves behind.\n\n**Contiguous KV allocation wastes most of the memory it reserves.** The straightforward way to hold a request's KV cache is one contiguous buffer sized to the maximum sequence length. But you rarely know the final length in advance, so the server over-reserves; the unused tail is dead memory (internal fragmentation), and the gaps left between requests are too small and scattered to admit new ones (external fragmentation). Because KV-cache capacity, not compute, usually caps how many requests fit on a GPU, this waste directly throttles throughput.\n\n**Paging maps logical tokens to physical blocks through a block table.** PagedAttention breaks the KV cache into fixed-size blocks (say 16 tokens each) and keeps, per request, a block table just like a page table. Logical block N of a sequence can live in any free physical block; the attention kernel follows the table to gather the right keys and values. Memory is handed out one block at a time as tokens are generated, so there is no reservation and near-zero waste — reported internal fragmentation drops to a few percent, letting far more requests share the same GPU.\n\n| | Contiguous KV cache | PagedAttention |\n|---|---|---|\n| Layout | one block per request | fixed-size blocks anywhere |\n| Sizing | reserve to max length | grow one block at a time |\n| Internal waste | large unused tail | ~a few percent |\n| Fragmentation | blocks new requests | none (any free block) |\n| Sharing | copy the whole cache | share blocks copy-on-write |\n| Effect | memory caps concurrency | far more concurrent requests |\n\n```svg ```\n\n**It is the core of vLLM and why paged serving became standard.** By freeing the memory that over-reservation used to strand, PagedAttention lets the server keep many more sequences resident, which is precisely what continuous batching needs to fill the GPU. The block table also makes sharing cheap: a common prompt prefix, or the parallel samples of beam search, can point at the same physical blocks and fork copy-on-write only when they diverge. vLLM pairs this with continuous batching to reach throughput several times higher than allocate-to-max systems at the same latency.\n\nRead PagedAttention through a quant lens rather than a 'clever caching' lens: the number it moves is KV-cache memory efficiency — waste falls from the reserved-tail fraction (often 60-80%) to low single digits — which converts almost directly into how many requests fit on a GPU and thus into throughput. The design question is your block size: smaller blocks cut internal waste but enlarge the block table and per-step bookkeeping, so you tune the page size to the point where fragmentation savings stop outweighing indirection overhead, exactly as an OS balances page size against page-table cost.