PagedAttention,
explained.

When an LLM generates text, it caches the key and value vectors of every token it has seen so it doesn't recompute them — the KV cache. For long sequences and big models this cache dominates GPU memory, and how much of it fits directly sets how many requests you can batch, which sets throughput. Memory is the bottleneck of serving.

The old way to manage it was crude: give each request one contiguous buffer sized for its maximum possible length. But you don't know how long an answer will be, and most are short. So the server reserves room for 2,000 tokens and the request stops at 100 — the other 1,900 slots are reserved, untouchable by anyone else, and wasted. This is internal fragmentation, and measurements showed it could consume the large majority of the KV cache. Add the gaps left between requests as they come and go (external fragmentation) and a server could be sitting on mostly-empty memory while turning new requests away.

Operating systems solved exactly this problem for RAM decades ago, and PagedAttention imports the solution wholesale. Instead of one contiguous buffer per request, the KV cache is cut into fixed-size blocks (say 16 tokens each). A request is given blocks as it grows, and they can sit anywhere in memory — a block table maps the request's logical token positions to their scattered physical blocks, just like an OS page table.

The attention kernel is rewritten to gather keys and values through this table rather than assuming they are laid out contiguously — that is the "attention" half of PagedAttention. The result is that memory is handed out in small increments and reclaimed the instant a request finishes, keeping the cache densely packed.

The improvement is easy to quantify. With contiguous reservation, the wasted memory per request is everything you reserved but didn't use — max_len − seq_len, which for a short answer is nearly the whole buffer. With paging, a request uses ⌈seq_len / block_size⌉ blocks, so the only waste is the unfilled tail of its last block:

The paged waste is capped at less than one block regardless of sequence length — a handful of tokens, not thousands. Concretely, a 100-token request with a 2,048 max wastes 1,948 slots contiguously (95%) but only 12 with 16-token blocks. Reclaim that and the same GPU holds many times more requests: in the runnable below, roughly 18× more. Since decoding throughput is set by how many requests you can batch, more requests packed in means proportionally more tokens per second.

Blocks addressed through a table unlock a second win for free: sharing. Because several sequences can point their block tables at the same physical blocks, a common prefix need only be stored once. This is everywhere in practice — parallel sampling (many completions of one prompt), beam search (many beams from one context), a shared system prompt across users. All of them share a prefix.

PagedAttention keeps the shared blocks read-only and applies copy-on-write: the moment one sequence needs to write into a shared block (it diverges), that block alone is copied so the write doesn't corrupt the others. Until then, the prefix costs memory once no matter how many sequences read it. For beam search over a long prompt, that can cut KV memory dramatically — the runnable shows two beams sharing a prefix using 6 blocks instead of 10.

Reclaimed memory doesn't just sit there — it becomes batch size. Decoding is memory-bandwidth-bound, so the way to more tokens per second is to process more requests together in each pass. PagedAttention's dense packing is what makes those bigger batches fit, and vLLM pairs it with continuous batching (swapping finished requests out and new ones in every step, rather than waiting for a whole batch to complete).

The trade is a little indirection: attention now gathers through a block table instead of reading contiguous memory. That cost is tiny compared to the memory it frees, which is why the net effect is a large, consistent throughput gain.

vLLM, built on PagedAttention, became one of the most widely deployed open-source LLM serving engines almost immediately, and paged KV caching is now standard across serving stacks. The reason is that it attacked the exact bottleneck of the moment — GPU memory during inference — with a fix that was principled, general, and required no change to the model. Cheaper serving is what let more teams run large models at all.

Its deeper lesson is a favorite of systems work: the right abstraction from one field often solves a fresh problem in another untouched. LLM serving had reinvented contiguous memory allocation and inherited its decades-old fragmentation pains; PagedAttention simply pointed out that operating systems had already solved this with paging, and ported the idea. Sometimes the breakthrough is recognizing which old, well-understood mechanism your new problem secretly is.