PagedAttention,
explained.

Rung 2 makes the forward pass efficient. This rung looks at what limits how many users a server can hold at once, and finds it is not speed but memory capacity — specifically the key-value cache, which grows with every token of every active sequence and, at realistic concurrency, claims a large share of the accelerator beside the weights (about 30 percent of an A100 in the paper's OPT-13B example, against about 65 percent for the weights).

The diagnosis is that the memory was mostly being wasted. Serving systems allocated each sequence one contiguous buffer sized to the maximum length it might reach, because attention kernels wanted contiguity. A request that generates two hundred tokens against a two-thousand-token budget leaves nine tenths of its allocation untouched, and because the blocks are large and contiguous, the leftovers are also fragmented into gaps too small to reuse. Most of the expensive memory held nothing.

The change is to apply the operating system's answer. Store the cache in fixed-size blocks that need not be adjacent, with a per-sequence table mapping logical positions to physical blocks, and allocate a block only when it is needed. Waste per sequence is then bounded by one partially-filled block instead of the entire unused budget. The second gain follows for free from the indirection: two sequences sharing a prefix — a common system prompt, or several samples drawn from one prompt — can point at the same physical blocks and only copy when one of them diverges. Stated in units, fitting several times as many concurrent sequences multiplies throughput at the same latency, which is the number that decides what serving costs.

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.

Start with the number that motivates the design. For OPT-13B, one token's keys and values take 2 (key and value) × 5,120 (hidden size) × 40 (layers) × 2 bytes = 800 KB, so a single 2,048-token sequence can need 1.6 GB. On a 40 GB A100 the 13B weights take about 26 GB, leaving roughly 30 percent of the GPU for the KV cache, and how that space is managed decides the batch size. vLLM's procedure:

1. Carve the cache into blocks. The GPU memory left for the KV cache is split into fixed-size physical blocks, each holding keys and values for B tokens (16 by default). A free list tracks unused blocks.
2. Give each sequence a block table. A sequence's tokens live in logical blocks 0, 1, 2 and so on. Its block table maps each logical block to a physical block and records how many of its B slots are filled.
3. Prefill. For a new request, the scheduler allocates ⌈prompt length / B⌉ blocks and the prompt's keys and values are written into them.
4. Decode. Each generated token's key and value go into the next free slot of the sequence's last block. Only when that block is full is a new physical block taken from the free list, so a sequence never holds more than one partly empty block.
5. Attend through the table. The PagedAttention kernel computes attention for a query by fetching key and value blocks wherever the table says they are and processing them block by block, so physical blocks need not be adjacent.
6. Share with reference counts. Every physical block counts the logical blocks that point to it. Parallel samples of one prompt point at the same prompt blocks. When a sequence must write into a block whose count is above one, vLLM first copies it to a new block (copy-on-write) and decrements the old count; beam search shares blocks among beams the same way and frees a block when its count reaches zero.
7. Preempt when memory runs out. Scheduling is first-come-first-served at the granularity of one decoding iteration. When no free block is left for the next tokens, vLLM preempts the most recently arrived requests and evicts all of a sequence's blocks at once, since every block of a sequence is read at every step. Sequences that share blocks, such as the beams of one request, are scheduled and evicted together.
8. Recover by swapping or recomputing. Evicted blocks are either copied to CPU memory and copied back later, or dropped and rebuilt when the request resumes: its prompt and the tokens generated so far are run as one new prefill, which is much faster than the original token-by-token decoding.

Across GPUs

For models split with Megatron-style tensor parallelism, a single KV cache manager sits in the central scheduler. Every GPU worker uses the same block table and the same physical block numbers but stores only the keys and values for its own attention heads, so the mapping is decided once and sent out with each step's inputs.

The authors built vLLM with a FastAPI front end and a GPU engine in about 8,500 lines of Python and 2,000 of C++ and CUDA, including fused kernels for writing new keys and values into blocks and for the block copies that copy-on-write needs.

• 2 — one key vector and one value vector per token per layer.
• nlayers · dmodel — every layer caches a hidden-size vector for each. For models whose query heads share key and value heads (multi-query or grouped-query attention), d_model becomes the number of KV heads times the head size.
• B — block size in tokens; n — the sequence's current length.
• tokens reserved per sequence — the maximum length under contiguous allocation; the current length rounded up to a whole block under paging.

At the extremes: B = 1 wastes nothing but makes every token a separate lookup, which keeps the kernel from reading memory in efficient chunks, while B equal to the maximum length is contiguous reservation again. Because the waste bound does not grow with n, long sequences gain the most.

The evaluation served OPT-13B on one A100, OPT-66B on four and OPT-175B on eight, plus LLaMA-13B, replaying ShareGPT and Alpaca request traces with Poisson arrivals at rising rates. The metric was normalized latency (mean end-to-end latency divided by output length); a system's capacity is the request rate it sustains before that latency climbs. Baselines were FasterTransformer and three Orca variants the authors reimplemented: Oracle, which knows each output length in advance; Pow2, which over-reserves by up to 2×; and Max, which reserves the maximum length.

The ablations show the costs. The PagedAttention kernel itself was 20–26 percent slower than FasterTransformer's attention kernel, because it reads through the block table and handles variable lengths; the end-to-end gain comes from batch size, not kernel speed. Block sizes from 16 to 128 worked best on ShareGPT, while on Alpaca's shorter sequences large blocks hurt, which is why 16 is the default. For preemption, swapping was expensive with small blocks, since that means many small transfers over PCIe, while recomputation cost the same at any block size; between 16 and 64 the two were comparable. And on Alpaca with OPT-175B, where eight GPUs leave plenty of room for short sequences, the advantage over the Oracle and Pow2 baselines was much smaller: paging pays off where memory is the bottleneck.

The trade-offs are the familiar ones from paging, and the paper treats them as such. Block size is a tuning decision — smaller blocks waste less and add more indirection — and the non-contiguous layout means the attention kernel has to gather through a block table, so this rung depends on writing a kernel that can, which is why it arrived after rung 2 rather than before.

Prefix sharing is also only as good as the sharing that actually occurs: it is transformative for workloads with a long common prompt and does nothing for unrelated requests, so reported gains depend on a workload shape as much as on the mechanism.

How it held up: it became the default architecture for language-model serving within about a year, and the framing is now simply assumed — the cache is a managed, paged resource rather than a buffer. Read this rung alongside latent compression of the cache on the sparse ladder: one makes each cached entry smaller and the other stops wasting space around it, they compose, and both exist because the cache, which grows with load while the weights stay fixed, is what a serving operator runs out of.

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.

Work each one out before you open it — a number, a prediction or a reason, not a definition. Producing the answer is what makes it stick. Your progress is kept on this device.

Five papers about the bill. Each one buys throughput back from a different part of the stack: the weights, the memory hierarchy, the KV cache, the decode loop.

1. 1Knowledge Distillation2014
2. 2FlashAttention2022
3. 3PagedAttention2023
4. 4Speculative Decoding2023
5. 5Medusa2024

All 110 papers, in 19 ladders →