PagedAttention & vLLM

Continuous batching can only admit a new request when there is free KV space — so the real lever on throughput is how little of HBM you waste holding KV. Early serving systems wasted most of it. This page is about why, and about the idea — PagedAttention — that fixed it and became the foundation of vLLM. The throughline here is stark: the same GPU, the same model, the same KV math from the sizing page, but several times more concurrent requests, purely by not wasting memory.

The problem: contiguous pre-allocation

A request’s KV cache grows one token at a time and you do not know in advance how long the answer will be. The simple solution early systems used was to reserve a contiguous block sized to the maximum possible length — say 2048 tokens — the moment a request starts. Contiguous because the attention kernels wanted the keys and values for a sequence laid out in one unbroken span of memory.

This is disastrous on three fronts:

• Internal waste: an answer that turns out to be 256 tokens still holds a 2048-token reservation. That is 1792 tokens — 87.5% — of its KV region sitting empty for the request’s whole life.
• External fragmentation: freed regions are different sizes, so after some churn you have plenty of total free memory but no single contiguous gap big enough for a new max-length reservation.
• No sharing: two requests with an identical prompt each get their own full copy.

Measurements on the original vLLM work found that naive systems used as little as 20–40% of KV memory for actual tokens; the rest was reservation and fragmentation. You bought 80 GB of HBM and threw most of the KV budget away.

The insight: KV cache as virtual memory

Operating systems solved exactly this problem decades ago. A process does not get one contiguous slab of physical RAM; it gets pages — small fixed-size blocks — mapped through a page table to wherever they physically fit. PagedAttention applies this to the KV cache.

The KV cache is divided into fixed-size blocks (e.g. 16 tokens of KV each). Blocks are allocated on demand as a sequence grows, drawn from a shared pool, and they need not be contiguous in physical HBM. A per-request block table maps the logical token positions to physical block numbers, and the attention kernel is rewritten to gather KV through that table — so non-contiguous storage costs almost nothing.

Naive (contiguous, reserved to max len 2048):
  req A  [ used 256 |·········· empty reservation ··········| 2048 ]  87.5% wasted
  req B  [ used 100 |················ empty ················| 2048 ]  95%   wasted

Paged (16-token blocks, allocated on demand, non-contiguous):
  block table A → [b07][b02][b09][b00]            (16 blocks = 256 tok, ~0 waste)
  block table B → [b03][b05][b08][b01][b04][b06][b…]  (last block partly filled)
  physical HBM   [b00][b01][b02][b03][b04][b05][b06][b07][b08][b09]…  one shared pool

The only waste left is internal fragmentation in the last block — at most block_size − 1 tokens (≤15) per request, a rounding error next to a 1792-token reservation.

Worked example: naive vs paged

Use Llama-2-13B on an 80 GB A100: ~26 GB weights, ~54 GB left for KV, and ~0.78 MB of KV per token (from the sizing page). Suppose the average real answer is 256 tokens but the max supported context is 2048.

Naive (reserve 2048 tokens per request):
  reserved per request = 0.78 MB × 2048 ≈ 1.56 GB
  max concurrent       = 54 GB ÷ 1.56 GB ≈ 35 requests
  (regardless of the fact that each only uses 256 tokens)

Paged (allocate only what's used, ~256 tokens):
  used per request = 0.78 MB × 256 ≈ 0.195 GB
  max concurrent   = 54 GB ÷ 0.195 GB ≈ 277 requests

Same hardware, same model: ~8× more concurrent requests simply by not reserving memory you will not use. Because throughput tracks batch size, that is close to an 8× throughput gain — and therefore ~8× lower dollar-per-token — on this workload. The gap is exactly the reservation waste you were paying for before.

Copy-on-write sharing

Because KV now lives in shared physical blocks behind a page table, identical blocks can be shared. Generate 4 samples from one prompt (n=4, beam search, parallel candidates) and all four share the same physical blocks for the common prompt — one copy, not four. When a sequence diverges and needs to write into a shared block, the system does copy-on-write: duplicate just that one block, then write. This is the same trick fork() uses, and it makes parallel sampling and beam search dramatically cheaper. (It is also the structural basis for prefix caching, two pages from now.)

vLLM is the engine built on this

vLLM is the open-source serving system built around PagedAttention. It bundles the paged KV manager, continuous batching, FlashAttention-style kernels, and automatic prefix caching into one server. When people quote large throughput jumps “from switching to vLLM,” PagedAttention’s recovered memory — turned into a bigger effective batch — is the largest single contributor.

Block size is a tuning knob

Smaller blocks (e.g. 8 tokens) cut last-block waste but enlarge the block table and add gather overhead; larger blocks (e.g. 32) reduce bookkeeping but waste more in the final partial block. The default ~16 is a balance, not a law.

It actually happened — PagedAttention and vLLM (SOSP 2023)

The paging idea was introduced in Efficient Memory Management for Large Language Model Serving with PagedAttention (Kwon et al., SOSP 2023) out of UC Berkeley, alongside its reference implementation, vLLM. The paper measured the waste this page describes — naive systems using as little as 20–40% of KV memory for real tokens — and showed that borrowing the operating system’s oldest memory trick recovered nearly all of it, reporting throughput gains of roughly 2–4× over the strong serving systems of the day at the same latency. vLLM then became the default open-source inference engine almost overnight; “we switched to vLLM and throughput went up severalfold” turned into a common refrain, and the recovered KV memory was the largest reason why. It is one of the field’s clearest cases of a decades-old systems idea paying off immediately in a new domain.

The architect’s lens

PagedAttention borrows the OS’s oldest memory trick — judge the adoption with the five questions:

• Why does it exist? Because a request’s KV grows token-by-token to an unknown length, early systems reserved a contiguous, max-length block up front — so a 256-token answer in a 2,048 reservation left 87.5% empty, and naive systems used as little as 20–40% of KV memory for real tokens.
• What problem does it solve? Internal waste, external fragmentation, and no sharing — it splits KV into fixed-size blocks (~16 tokens), allocated on demand from a shared pool and addressed through a per-request block table, so non-contiguous storage is fine and waste falls to ≤15 tokens per request.
• What are the trade-offs? A rewritten gather kernel and a block-size knob: smaller blocks cut last-block waste but enlarge the block table and add gather overhead; larger blocks do the reverse. The payoff on the worked example is ~8× more concurrent requests (35 → 277).
• When should I avoid it? Essentially never in production; only single-request or strictly fixed-length workloads see little gain — which is why it is table stakes in vLLM, TGI, and the rest.
• What breaks if I remove it? Contiguous max-length reservation returns: KV utilization drops to 20–40%, the worked example loses ~8× concurrency (and thus ~8× throughput), and the copy-on-write block sharing that underpins prefix caching disappears.

Check your understanding

1. Why did contiguous, max-length pre-allocation waste so much HBM? Name the three failure modes.
2. What OS concept does PagedAttention borrow, and what plays the role of the page table?
3. With ~54 GB for KV and ~0.78 MB/token, how many 256-token requests fit under naive 2048-reservation vs paged allocation, and what is the ratio?
4. After paging, what is the only remaining source of wasted KV memory, and how large can it be?
5. How does copy-on-write let four samples from one prompt avoid storing the prompt’s KV four times?

Show answers

1. It reserved a full max-length region per request regardless of actual length, causing: internal waste (empty reserved tokens for short answers), external fragmentation (no contiguous gap big enough despite free total memory), and no sharing (duplicate prompts each kept a full copy).
2. Virtual memory / paging. A per-request block table maps logical token positions to physical, possibly non-contiguous, fixed-size KV blocks — the analog of an OS page table.
3. Naive: 54 ÷ 1.56 ≈ 35 requests. Paged: 54 ÷ 0.195 ≈ 277 requests. Ratio ≈ 8×.
4. Internal fragmentation in each request’s last, partially filled block — at most block_size − 1 tokens (≤15 with a 16-token block), a negligible rounding error.
5. The four sequences share the same physical blocks for the common prompt via the block table; only when one diverges and must write does the system copy that single block (copy-on-write), so the shared prompt KV is stored once, not four times.