Paper · Issue 1

Why vLLM Uses PagedAttention

Serving an LLM wastes most of its memory on empty reservations. The fix was hiding in a 50-year-old operating-systems trick.

17 July 2026 Pixel-art illustration of paged memory tiles, some filled with green tokens, linked by blue pointers.

The problem

Serving an LLM is a memory problem, not a compute problem

GPU memory divided into weights, KV cache, and activations

A Transformer generates one token at a time, each conditioned on every token before it. That sequential loop barely stresses the GPU's math units, so throughput comes down to one thing: how many requests you can pack into a batch at once.

And batch size is gated by memory. On a 13B model on a 40GB A100, roughly 65% of memory is fixed model weights and a thin slice is activations. The remaining ~30% is the KV cache, the per-token key/value state attention needs. Weights don't move, so the KV cache is the only lever, and how you store it decides how many requests fit.

The failed approach

Contiguous allocation reserves for the worst case

The KV cache is awkward: it grows one token at a time, and you don't know the final length when the request arrives. Deep-learning frameworks want tensors in one contiguous block, so systems like Orca and FasterTransformer do the safe thing and pre-allocate each request a chunk sized for the maximum possible output, say 2048 tokens.

A request reserving 2048 KV slots with only the first few filled

Most requests finish far shorter than that, so those reserved slots sit empty for the request's entire lifetime, blocking others that could run now. Because per-request chunks are different sizes, the allocator also leaves unusable gaps between them.

\text{reserved} = 2 \times n_\text{layers} \times d_\text{model} \times b \times \text{max\_seq}

Bytes one request reserves up front. The 2 covers K and V, b is bytes per element, and max_seq is the worst-case length most requests never reach.

The measured damage: in existing systems only 20.4% to 38.2% of KV cache memory actually holds live token state. The rest is fragmentation. You bought an A100 and got one-fifth of its memory working.

The insight

This is exactly the problem operating systems already solved

Reserving a big contiguous range you might not fill, and fragmenting memory when ranges differ in size, is the classic problem of memory allocation. Operating systems fixed it decades ago with virtual memory and paging: chop memory into fixed-size pages, hand them out on demand, and let a page table hide the fact that they aren't physically next to each other.

A page table mapping logical pages to scattered physical frames

PagedAttention imports that idea wholesale, and the mapping the authors lean on is almost one to one.

  OS paging          LLM serving
  ---------          -----------
  page        <-->   KV block (16 tokens)
  byte        <-->   one token's KV
  process     <-->   a request

The analogy the whole design rests on

Because the correspondence is that exact, the rest of the operating-systems toolkit comes along with it. On-demand allocation, sharing a page between processes, and copy-on-write each have a direct payoff for serving, and cashing them in is what the rest of the paper does.

The mechanism

Split the KV cache into 16-token blocks

Each sequence's KV cache is cut into fixed-size KV blocks of 16 tokens by default. Blocks do not have to sit next to each other in physical memory. A per-request block table maps the sequence's logical blocks to wherever their physical blocks actually live, exactly like a page table.

logical blocks:  [0][1][2][3]
                  |  |  |  |
block table:      v  v  v  v
physical blocks: [7][2][9][1]   (scattered)

The block table hides non-contiguous physical layout

Blocks are allocated on demand and filled left to right as tokens generate. A request only ever holds a partial block at the very end, so its wasted memory is bounded to at most one block, never a 2000-slot reservation. Internal fragmentation drops under 4%, and external fragmentation vanishes because every block is the same size.

But non-contiguous memory isn't free

Attention now has to gather scattered blocks, so the authors wrote custom CUDA kernels: one warp per block for coalesced reads, fused with the attention math. Their kernel measures 20% to 26% slower than FasterTransformer's tuned contiguous kernel. The trick is that it only touches the attention operator, not the big Linear layers, and the batch-size win swamps that loss end to end.

The bonus

Blocks that can be shared, forked, and copied on write

Once KV cache lives in shareable blocks, sequences that overlap can point at the same physical block. A reference count tracks the sharers, and when a shared block needs a write, vLLM copies it first, decrements the count, and lets the writer diverge. This is textbook copy-on-write, borrowed straight from fork().

Two sequences sharing prompt blocks with copy-on-write divergence

This pays off wherever requests overlap. Parallel sampling shares the prompt across N outputs; beam search shares both the prompt and the evolving history across candidates; a fixed system prompt becomes a shared prefix, like a shared library across processes.

Measured savings are large: 16% to 30% of memory for parallel sampling on ShareGPT, and 44% to 66% for beam search. Only the single block being actively written ever needs copying.

The result

2 to 4x more throughput on the same hardware

Because vLLM wastes almost no KV memory, it holds far more requests at once: 2.2x the concurrent requests of a well-tuned Orca that magically knows each output length, and 4.3x more than one reserving the maximum. More requests batched means more throughput at the same latency.

A densely packed GPU beside one holding few requests in reserved blocks

The paper reports 2x to 4x higher sustainable throughput versus Orca and FasterTransformer, with the gap widening for longer sequences, larger models, and complex decoding. Beam search, where sharing compounds, pushes the advantage from 1.3x up to 2.3x.

Orca (Max reserve)

1x requests batched

vLLM (paged)

4.3x requests batched

The launch blog's headline 24x was against vanilla HuggingFace Transformers, a much weaker baseline. The honest number is 2 to 4x over the prior state of the art, proven in production: vLLM served months of live LMSYS Chatbot Arena traffic on university GPUs.

The boundary

Why paging fits LLMs and not everything

The authors are careful about scope. Paging wins here because LLM serving has two specific properties: allocation is dynamic (output length is unknown), and the workload is GPU-memory-bound. Both have to hold for the trick to pay off.

Paging helps memory-bound dynamic serving, not static compute-bound work

DNN training has static tensor shapes, so you can plan allocation ahead of time and paging adds nothing. Non-LLM serving is often compute-bound, where the indirection of a block table could actually hurt. They even show it in the 175B short-sequence case: with memory to spare, the workload turns compute-bound and vLLM's edge shrinks.

The lasting lesson is less about attention and more about method: when a new system hits an old problem (fragmentation, unknown lifetimes, sharing), the operating-systems playbook is often sitting right there, waiting to be ported.

The takeaway

An old idea in a new place

Why it matters

PagedAttention is the reason open-source LLM serving got cheap enough for small teams to run at scale, and vLLM is now a default backend across the industry. For most engineers it changes serving costs and throughput without changing any application code. Its deeper value is the demonstration that classic OS techniques transfer directly to GPU memory once the workload looks like processes competing for pages.

The short version

LLM serving is **memory-bound**: throughput depends on how many requests fit, which the KV cache decides.
Contiguous allocation reserves for the max output length, leaving only **20-38%** of KV memory actually used.
**PagedAttention** stores the KV cache in fixed **16-token blocks** mapped through a block table, cutting waste below **4%**.
Shareable blocks enable copy-on-write, saving **up to 66%** of memory for beam search.
The payoff is **2-4x** higher throughput than prior systems, but only because serving is dynamic and memory-bound.