Why does PagedAttention exist?

Naive KV-cache allocation reserves a contiguous slab for the worst-case sequence length, then watches 60–80% of it sit unused. PagedAttention asks: what if we treated GPU memory the way an operating system treats RAM?

The picture version

Six pictures for a reader who has never thought about how a chat server budgets memory. The prose below fills in the seams the pictures skip.

Why it exists

You type “what’s the capital of France?” into a chat app and get back four words. That request carried a generation cap with it — whatever the app set, or its default, say “up to 2,048 tokens.” And here’s the awkward part: in the serving systems that predate this post’s subject, the engine had to decide how much GPU memory to set aside for your answer’s KV cache before it generated a single token, and the only safe guess was that cap. Twelve tokens came back. Memory for the other 2,036 sat locked and empty for the whole request.

The KV cache is the chunk of state that grows by one entry per generated token and is read on every subsequent step; the engine can’t know in advance how many entries there will be. So the safe move is to allocate the worst case: a contiguous slab big enough for 2,048 tokens, right now, before generation even starts.

Multiply that by every concurrent request and you get the situation the vLLM team measured across the systems they benchmarked in 2023: those systems wasted 60–80% of the HBM they had set aside for KV caches (Kwon et al., 2023). Some of it was internal fragmentation — slots reserved for tokens the model never generated. Some was external fragmentation — the engine knows there are 200 MB free somewhere across all the gaps between live caches, but no single contiguous 200 MB block, so a new request has to wait or be rejected. Both failure modes have the same cause: KV caches were allocated as one contiguous tensor per sequence, sized for the worst case, and contiguous worst-case allocation does not survive a workload of varied generation lengths.

The fix turns out to be a 50-year-old idea from operating systems.

Why it matters now

LLM serving is overwhelmingly KV-cache-bound when you push the batch size up. Continuous batching already wins back the GPU cycles wasted on padding; the next bottleneck is whether you can fit enough sequences in memory at once for that scheduler to have something useful to schedule. Reduce KV-cache waste from 60–80% to under 4% (the figure the vLLM team reports) and you fit materially more concurrent sequences on the same hardware — enough, in the paper’s measurements, to translate into 2–4× higher throughput at matched latency vs the contemporary baselines (FasterTransformer, Orca).

That is why block-based KV-cache management is now table stakes rather than a differentiator: vLLM originated PagedAttention, and other serving stacks ship their own paged KV cache — NVIDIA’s TensorRT-LLM, for instance, documents a paged KV-cache manager built on the same block idea. It also unlocks a class of features that look unrelated until you see the mechanism: prefix caching across requests, parallel sampling without duplicating the prompt’s KV state, beam search that doesn’t blow up memory in the number of beams. All of those are paging tricks in disguise.

The short answer

PagedAttention = KV cache stored in fixed-size non-contiguous blocks + page table mapping logical positions to physical blocks

Picture to keep: a coat check instead of a private closet — your answer’s cached tokens get handed out one small numbered tray at a time, scattered wherever there’s room, and a ticket stub lists which trays are yours in order.

Instead of giving each sequence one contiguous slab of GPU memory for its KV cache, chop the cache into small fixed-size blocks (16 tokens in the original vLLM paper; current vLLM treats block_size as platform/backend-dependent rather than a hard default) scattered anywhere in HBM. Keep a per-sequence table that maps “logical token positions 0–15” to “physical block #427”, “positions 16–31” to “physical block #88”, and so on. The attention kernel reads through this table the way a CPU reads through a page table. Allocation now happens one block at a time, on demand, instead of worst-case up front. Fragmentation collapses, and a bunch of useful sharing patterns become almost free.

How it works

The trick is borrowed almost verbatim from how operating systems manage RAM. A process doesn’t get a contiguous block of physical memory; it gets a virtual address space, and the OS maintains a page table that maps virtual pages to wherever they happen to live in physical RAM. Two processes can share a page (e.g. a shared library) by pointing their page tables at the same physical frame.

Now rebuild the allocator one failure at a time, with the Paris request in hand.

Naive attempt: one contiguous slab per sequence, sized to the cap. This is what makes the attention kernel simple — token t lives at keys[t], a single stride away from token t−1. It’s also what produced the two failures above: 2,036 reserved-and-unused slots per short answer, and a free-memory map full of gaps too small to hold the next request’s slab.

Why the obvious repair fails. You could shrink the reservation and grow it later — but “grow” on a contiguous tensor means finding a bigger contiguous hole and copying the whole cache into it, mid-generation, on the critical path. That trades one bad property for a worse one.

The fix: stop requiring contiguity. Split the sequence’s KV cache into blocks of a fixed token count — 16 in the original vLLM paper (block size is a configurable knob, and current vLLM picks a default per backend). Each block lives wherever there’s room in HBM. Give each running sequence a small block table: a list of physical block IDs in logical order. To attend to token t, the kernel looks up block_table[t // 16], then offsets by t % 16 inside that block. Allocation happens one block at a time, when the current last block fills up — no reservation for tokens not yet generated, and no copying, because growth just appends an entry to the table.

Run the Paris answer through that: twelve tokens now occupy one 16-token block. The waste is four slots, not 2,036. Internal fragmentation is bounded by block_size − 1 tokens per sequence — at most 15 tokens of waste in the last partial block, no matter how large a limit the caller declared. External fragmentation effectively disappears, because every allocation is the same size, so the free list never gets stuck holding unusable scraps.

Why the OS analogy actually works here

You might reasonably ask: paging in operating systems exists because processes have unpredictable, sparse memory access patterns and need isolation. LLM attention reads a sequence’s KV cache fully and densely on every step. Why does the same mechanism help?

It helps because the useful part of OS paging here isn’t the “isolation” part or the “trap on miss” part. It’s the decoupling of logical address from physical layout. Once you have that, two properties fall out:

1. Allocate-on-write. No worst-case reservation; cache grows one block at a time.
2. Cheap sharing. If two sequences share a prefix — same prompt, same first k tokens — they can point their block tables at the same physical blocks for that prefix. No copy. When one of them later diverges and writes into a shared block, the system does copy-on-write at block granularity: allocate one fresh block, copy that single shared block’s contents in, redirect just that sequence’s block-table entry. Earlier shared blocks stay shared.

The second property is where PagedAttention pays for itself a second time. Parallel sampling of n completions from one prompt used to mean n full copies of the prompt’s KV cache. With PagedAttention, all n candidates share the prompt blocks by reference; only the divergent suffixes consume new memory. Beam search, which the vLLM paper benchmarks specifically, gets an even bigger lift because beams share long prefixes among themselves, not just with the prompt — the paper reports vLLM’s improvement over Orca going from 1.3× in basic sampling to 2.3× in beam search at width 6 on OPT-13B with the Alpaca dataset.

What it costs

Paging is not free. Every attention computation now has an extra indirection: instead of keys[t], it’s physical_blocks[block_table[t // 16]][t % 16]. The vLLM team wrote custom CUDA kernels (and rewrote them several times since the 2023 paper) so that this indirection happens at the warp level without serializing memory loads. On the hardware they tested, the per-token cost was small enough to be dominated by the throughput gains from fitting more sequences in the batch — but it is a real cost, and a from-scratch implementation that doesn’t fuse the lookup into the attention kernel will give some of it back. Your Paris answer pays that indirection on every one of its twelve decode steps; it earns it back because a hundred other Paris-sized answers now fit alongside it.

There’s also a tuning knob: block size. Larger blocks mean less table-walking overhead but more internal fragmentation per sequence — and, where an engine matches shared prefixes at whole-block granularity, worse prefix-cache hit rates, since two requests have to agree on an entire block to share it. Smaller blocks invert that trade. The paper’s 16 is a working default, not a universal optimum, and modern engines expose the size (and sometimes decouple the prefix-matching unit from it, which softens the hit-rate half of the trade).

Where the seams show

A few honest caveats:

• The “60–80% wasted” figure is from the original vLLM paper’s measurements on the systems it compared against in 2023 (notably earlier FasterTransformer/Orca configurations on specific workloads). The exact percentage is workload- and baseline-dependent. The direction — naive contiguous allocation is bad, especially with varied generation lengths — is robust.
• PagedAttention isn’t the only way. You can also attack KV-cache waste with eviction policies, KV compression/quantization, or sliding windows. Paging targets the allocation problem specifically; it stacks with those rather than replacing them.
• The kernel engineering matters more than the idea. A page table is a few-line concept; the hard part is the fused attention kernel that reads through that table without serializing memory loads. My read — not a sourced claim — is that this, more than the algorithm, is what separated vLLM from re-implementations. A clone that gets the algorithm right but the kernel wrong will lose to a well-tuned non-paged baseline.
• It interacts with everything. Quantization, speculative decoding, multi-LoRA serving, MoE routing, prefix caching across requests — each one has to be made paging-aware. There’s no public accounting of how much serving-engine work that has absorbed, but “make feature X coexist with paging” is a recurring shape in these codebases’ commit histories.

You started with PagedAttention = fixed-size blocks + a page table. What did this post add that the name doesn’t tell you? — + block tables that two sequences can point at the same time. Allocate-on-demand is what kills the 2,036 wasted slots behind your Paris answer; sharing is what makes parallel sampling, beam search, and cross-request prefix caching nearly free, and that second half is where paging keeps paying after the fragmentation win is banked.

Check yourself

Before you go — an engine that matches shared prefixes block-by-block switches from block size 16 to block size 256, and its prefix-cache hit rate drops even though nothing about the incoming traffic changed. Why?

And one more: paging cut KV-cache waste dramatically, but the vLLM paper still reports a larger speedup for beam search than for plain sampling. What does that tell you about where the second win comes from?

Famous related terms

• Virtual memory / paging (the OS feature) — paging = virtual addresses + page table + physical frames — the original; PagedAttention is paging applied to the KV cache instead of process memory.
• KV cache — KV cache = stored attention keys and values + reused on every decode step — the thing PagedAttention is managing.
• Continuous batching — continuous batching = iteration-level scheduling + per-token batch reshuffling — the partner technique; without paging, fragmentation caps how much continuous batching can buy you.
• Copy-on-write — CoW = share until someone writes + copy the page on write — the OS trick that lets parallel sampling and beam search share prompt blocks for free.
• Prefix caching — prefix caching = remember KV blocks for shared prompt prefixes + reuse them across requests — falls out almost for free once the cache is paged. See why prompt caching exists.
• Block size — block size = tokens per physical KV block — the tuning knob; small means better sharing and less internal fragmentation, large means less indirection overhead. The original paper used 16; production engines expose it as a setting and pick defaults per backend.

Going deeper

• Kwon, Li, Zhuang, Sheng, Zheng, Yu, Gonzalez, Zhang, Stoica — Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023). arXiv · ACM. Read this for where the 60–80% waste figure comes from and exactly which baselines it was measured against.
• vLLM team — vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention. Blog post. Read this if you want the throughput story in plain English, with charts, before touching the paper.
• vLLM docs — Automatic Prefix Caching. Page. Read this to see what block-level sharing looks like once it’s a user-facing feature rather than an internal trick.