PagedAttention,
Internals First

The KV cache has a memory problem that has nothing to do with model size: reserve a contiguous slab per request and most of it sits empty — the PagedAttention paper measured 60–80% of KV-cache memory going to waste. The fix is the operating system's oldest trick. Split the cache into fixed-size blocks, track them with per-sequence block tables, and let the attention kernel gather from anywhere. Everything else — beam sharing, prefix caching, preemption — falls out of that one decoupling.

01 The fragmentation tax

Why contiguous KV cache wastes 60%+ of memory.

Serve an LLM the naive way and the memory manager does this for every request: allocate max_seq_len × bytes_per_token of contiguous GPU memory up front, then fill it in as tokens arrive. Contiguity made the kernels simple — K and V lived in flat arrays, attention streamed through them sequentially — and reserving the maximum avoided reallocation mid-decode. It also quietly set most of the GPU's memory on fire.

Two distinct wastes compound. Internal fragmentation: you reserve for the longest sequence you might see and the request uses a fraction of it; the unused tail is reserved but dead. External fragmentation: requests of wildly different lengths arrive and depart, carving the free pool into holes no single reservation fits into, even when the total free bytes would suffice. This is not a metaphor for the OS paging problem — it is the OS paging problem, the one Atlas and Multics solved with fixed-size pages in the 1960s, replayed on HBM.

Work the arithmetic for a 70B-class model with grouped-query attention — say 80 layers, 8 KV heads, head dimension 128, fp16. Every token's KV footprint is:

2 (K,V) × 80 layers × 8 kv_heads × 128 dim × 2 bytes = 327,680 bytes = 320 KiB per token

Reserve a 4K context window and each request pins 4096 × 320 KiB = 1.25 GiB, contiguous. Now a typical chat request uses 300 tokens: 300 × 320 KiB ≈ 92 MiB. Waste per request: (1280 − 92) / 1280 ≈ 92.8%. That is one request's story; across a fleet with mixed prompt lengths, prefill-heavy and decode-heavy traffic interleaved, the PagedAttention authors measured 60.2% to 80.4% of KV-cache memory wasted in the systems they studied. Three-fifths to four-fifths of the most expensive memory in the machine, holding nothing.

The damage isn't just bytes — it's batch size. Throughput in LLM serving is overwhelmingly a function of how many sequences you can batch together per forward pass, and batch size is capped by KV-cache memory. If 70% of that memory is fragmentation, your achievable batch is a third of what the hardware could support, and your tokens-per-second-per-dollar collapses with it. In the paper's evaluation, vLLM served up to 24× the throughput of HuggingFace Transformers on identical hardware — most of that gap is not a faster kernel, it is simply fitting more sequences into the same HBM by refusing to waste it.

It is worth asking why anyone built it the naive way, because the answer explains what paging had to preserve. Contiguity bought two things: kernel simplicity (one base pointer per sequence, no indirection in the hottest loop in the system) and freedom from reallocation (reserve the max once, never move a live sequence). For single-sequence generation — the HuggingFace Transformers loop the paper compared against — neither waste mattered, because there was no fleet to pack. The tax only appears under concurrency, which is exactly where serving lives.

External fragmentation deserves its own concrete picture, because it is the waste paging critics underestimate. Imagine the free pool after an hour of mixed traffic: freed 4K reservations leave 1.25 GiB holes scattered between live ones. A new request wants an 8K window — 2.5 GiB contiguous. Ten gibibytes stand free in aggregate, but the largest single hole is 1.25 GiB, so the allocation fails. And here is the trap: without a level of indirection, you cannot compact. Moving a live sequence's KV to consolidate free space would invalidate every pointer the kernel holds, so the holes are permanent until the neighboring requests drain. Overcommit is impossible; the only fix is indirection — which is precisely what the block table provides.

A back-of-the-envelope for the batch-size damage, labeled as an estimate: suppose 50 GiB of HBM is available for KV. Contiguous reservations of 1.25 GiB cap the batch at 40 sequences — but if the average sequence actually holds 300 tokens (92 MiB), those 40 sequences consume under 4 GiB of real data. The same 50 GiB paged, at 19 blocks per sequence, fits roughly 2,700 such sequences by capacity (50 GiB / 95 MiB) — in practice you hit compute or latency limits long before that, but the memory ceiling moves from 40 to the hundreds. That is the shape of the 24×: not a faster matmul, a bigger batch.

The diagram makes the trade visible in bytes, not adjectives. On the left, four requests each reserve 1.25 GiB contiguously and collectively strand about 3.5 GiB. On the right, the same tokens occupy 301 blocks of 5 MiB each, packed with no gaps; the only waste left in the system is 16 tokens — the unused slots in two sequences' final blocks. Internal fragmentation doesn't disappear under paging, it gets bounded: at most block_size − 1 tokens per sequence, regardless of how long the reservation would have been.

One subtlety worth naming: the naive scheme's waste grows with the reservation (4K, 8K, 128K — wherever context windows go), while paging's waste is capped by the block size, a constant you choose. As context windows stretched from 4K to 128K and beyond, contiguous reservation went from wasteful to absurd; paging's waste stayed at ≤15 tokens. That scaling property, more than any single benchmark, is why every serious serving engine now pages.

02 Block tables

Virtual memory for attention.

Paging splits the KV cache into fixed-size blocks — vLLM's default is 16 tokens per block — and gives every sequence a block table: a small array mapping logical block index to physical block id. Token t of a sequence lives in logical block t // 16 at offset t % 16; the physical location is block_table[t // 16] plus the offset. Logical blocks are always dense and sequential. Physical blocks are wherever the allocator found room — scattered across HBM, shared between sequences, in no particular order. The attention kernel is the MMU: it translates on every access.

Concretely, the PagedAttention kernel is launched with one thread-block per (sequence, KV head). For each query position it needs K and V for all previous positions, so it walks the sequence's block table: for logical block b, it reads phys = block_table[b], then loads that physical block's K/V tile into SRAM and accumulates the attention scores. The gather is the whole trick — instead of one flat array, the kernel does ceil(seq_len / 16) indexed lookups per head, each resolving to a contiguous slab. vLLM lays the cache out block-major, so all K (or V) entries of one physical block sit in a single contiguous region — for our 70B example, one 5 MiB slab — making each block fetch a clean coalesced read rather than a scatter.

The block table itself is nearly free. A 4K-token sequence needs 256 entries; at 4 bytes each that's 1 KiB of metadata guarding 1.25 GiB of KV data — six orders of magnitude smaller than the payload. Even at 128K context (8,192 entries, 32 KiB) the table is noise. This is the same reason OS page tables won: the mapping structure costs nothing next to what it manages — 1 KiB of table guarding 1.25 GiB of KV is six orders of magnitude of leverage.

Look closer at the kernel walk, because the gather pattern determines what block sizes are affordable. The kernel launches one thread-block per (sequence, KV head) pair. For grouped-query attention the mapping is direct: each KV head serves its group of query heads, so the walk happens once per KV head, not per query head — GQA doesn't just shrink the bytes (8 KV heads instead of 64), it shrinks the gather work by the same 8×. For each query position, the thread-block iterates logical blocks 0 through ceil(seq_len/16) − 1, translates each through the table, and streams the block's K tile — 16 tokens × head_dim — into SRAM, accumulating softmax statistics as it goes. The per-iteration cost is one table lookup plus one coalesced tile load, which is why the table-entry counts in the chart double as kernel iteration counts: at B=8 the loop runs 38 iterations per head per query position; at B=128, three.

Push the table math to the long-context extreme to see where it bends. A million-token sequence needs 62,500 blocks; the table is 250 KiB. The KV it guards is 10⁶ × 320 KiB = 320 GiB — a thought experiment at that scale, since no single GPU holds it, but the ratio is the point: the table is still six orders of magnitude smaller than the payload. The table never becomes the problem. What becomes the problem at 1M tokens is the gather loop itself: 62,500 iterations per head per query token is a lot of translation overhead, and it is the honest version of the argument for larger blocks at extreme context — section 06's huge-pages question.

So why 16? Three forces pull on the block size, and 16 is where they balance. Internal fragmentation grows with block size: a sequence wastes on average (B − 1) / 2 tokens in its final partial block, so bigger blocks mean more dead slots per sequence. Kernel gather cost shrinks with block size: fewer blocks per sequence means fewer table lookups and fewer, larger SRAM tiles per attention pass — better coalescing, less loop overhead. Sharing granularity coarsens with block size: prefix caching and beam sharing (sections 03–04) can only share whole blocks, so blocks much larger than 16 would force false sharing of unrelated token spans.

Run the numbers for a 300-token sequence at 320 KiB/token. Expected internal waste is (B−1)/2 tokens:

B=8 → 3.5 tok (1.2%) · B=16 → 7.5 tok (2.5%) · B=32 → 15.5 tok (5.2%) · B=64 → 31.5 tok (10.5%) · B=128 → 63.5 tok (21.2%)

Meanwhile the block table shrinks from 38 entries at B=8 to 3 at B=128, and the kernel's per-head loop drops from 38 iterations to 3. At B=8 you pay gather overhead on every attention call to save ~4 tokens of waste; at B=64+ the waste starts to dominate for short sequences, which are the majority of real traffic. Sixteen keeps waste at 2.5% while keeping the table at 19 entries and the gather loop short. It is tunable (--block-size in vLLM, powers of two), but 16 survives because the arithmetic keeps working out.

Internal fragmentation (blue bars) rises linearly with block size while the block table — and the kernel's per-head gather loop — shrinks (orange line). At 16, a 300-token sequence wastes 2.5% to the final partial block while the table stays at 19 entries. Push to 128 and you save 16 table entries but burn a fifth of the sequence's memory; drop to 8 and you quadruple the gather loop to reclaim a single percentage point. Sixteen is not a magic number — it is the knee of this curve for the sequence lengths that dominate real traffic.

03 Sharing via copy-on-write

One prompt, many beams, one copy.

Once blocks are the unit of allocation, a physical block can be referenced by more than one sequence. Each physical block carries a reference count; multiple block tables may point at the same physical id, and the block is freed only when the count hits zero. This is exactly how an OS shares pages between processes after fork() — and the write path is the same too. When a sequence needs to write a token into a block whose refcount exceeds 1, the allocator hands it a fresh physical block, copies the old block's contents over, decrements the old refcount, and repoints the sequence's table. Copy-on-write, no new ideas required.

The payoff shows up wherever one prompt fans out into many sequences. Take parallel sampling with 4 completions on a 2,000-token prompt at our 320 KiB/token: without sharing, the prompt's KV is stored four times — 4 × 2000 × 320 KiB ≈ 2.44 GiB. With sharing, the 8 prompt blocks (2000/16 = 125 blocks) are stored once: 2000 × 320 KiB ≈ 625 MiB, a 3.9× reduction on the shared prefix, saving ~1.8 GiB. Each sequence then allocates private blocks only for the tokens it generates. The refcount on every prompt block reads 4 until sequences finish and release them.

Beam search exercises the mechanism harder. After each decoding step, vLLM re-sorts the beams by score, remaps block tables so surviving hypotheses inherit the shared prefix blocks, and frees the losers' private blocks. When two beams generate identical token spans — common when hypotheses haven't diverged yet — their fresh blocks are shared too, with refcount 2. The instant one beam's next token differs inside a shared, partially filled tail block, CoW fires: the shared slots are copied — 10 slots, 3.2 MiB in our running example — the beam's table is repointed, and the other beam never notices. The copy cost is bounded by the block size, never by the sequence length — that bound is the entire reason the granularity matters.

Read the diagram as a freeze-frame of the write fault. Logical blocks 0–7 are the prompt, shared by all three beams as physical blocks P0–P7 with refcount 3 — 640 MiB stored once instead of three times. Each beam owns private blocks for most of its generated tail. Block 9 is the interesting one: beams 1 and 2 happened to generate the same 16 tokens there, so both tables pointed at P9 (refcount 2). When beam 2's next token diverged, the allocator refused the shared write, copied P9's 5 MiB into a fresh block P12, and repointed only beam 2's table. Total data moved for the divergence: one block, not the sequence. That bound — divergence cost ∝ block size, never sequence length — is what makes wide beam search affordable under paging.

A detail that matters for implementers: the refcount check happens on the write path, not the read path. Attention reads never care about sharing — the kernel walks logical blocks identically whether the physical block is shared or private. Only append (the token currently being generated) can trigger a copy, and only when it lands in a block someone else references. Reads are oblivious; writes are careful. That asymmetry keeps the hot path — attention, which dominates runtime — free of any sharing logic.

It helps to separate the two fan-out patterns, because they stress the machinery differently. Parallel sampling (n > 1 in vLLM) is the easy case: n independent completions share the prompt blocks for the entire generation, refcount n, and since the sequences never merge, no table surgery is ever needed — each sequence just allocates private blocks as it generates. Beam search is the hard case: hypotheses are re-ranked every step, survivors inherit block-table entries from the dead, and sharing appears and disappears dynamically as beams converge and diverge. The refcount is the only thing standing between this churn and a use-after-free: increment on share or fork, decrement when a sequence's table drops the block or the block is CoW-replaced, return the block to the free pool at zero. Get the counting wrong and you corrupt a stranger's KV; the allocator treats the refcount as load-bearing, because it is.

One more implementer's detail: the CoW check sits on the append path, which is about as hot as the write path gets — every generated token lands in the sequence's current (last, partially filled) block. The check itself is a single integer compare against the block's refcount: 1 means write in place, >1 means allocate-copy-repoint. A compare and a branch, amortized over the 16 tokens that fill a block. Sharing is never free — you pay one branch per token — but the branch is the cheapest possible price for the gigabytes it saves.

04 Prefix caching falls out for free

Cross-request sharing, same machinery.

Nothing in the block-table design says sharing stops at the request boundary. If two different requests start with the same tokens, their block tables can point at the same physical blocks — the refcount just counts across requests instead of across beams. This is automatic prefix caching (APC), and in vLLM v1 it is on by default. The allocator hashes the token ids of each prompt block; when a new request's block hash matches a live physical block, the request's table references it and the refcount increments instead of allocating and recomputing.

The fleet-wide win concentrates in the most boring tokens: system prompts, few-shot examples, tool definitions, RAG instruction wrappers. A 2,000-token system prompt at 320 KiB/token is 625 MiB of KV. Without sharing, a thousand concurrent requests each carrying that prompt burn 625 GiB — more than the HBM of the cluster — on identical bytes. With prefix caching, the prompt's 125 blocks are stored once and every request's table points at them. The sharing is exact (hash of token ids, block-aligned from position 0), so there is no approximation and no quality risk: identical tokens produce identical KV by construction.

Two constraints shape what actually gets shared. First, block alignment: sharing starts at token 0 and proceeds in whole blocks, so a shared suffix that doesn't start at a block boundary can't be reused — the hash covers fixed 16-token windows from the beginning. Second, eviction: unreferenced blocks (refcount 0) are evicted least-recently-used, and a block with refcount > 0 is pinned — it cannot be evicted while any live sequence points at it, which means a popular system prompt's blocks effectively become immortal for the duration of the traffic spike. The LRU only reclaims blocks nobody wants, which is precisely the set you can afford to recompute.

One honest caveat before moving on: sharing physical blocks across users creates a timing side channel in principle. A cache hit on a prefix block skips prefill work; a miss doesn't. An attacker who can measure time-to-first-token precisely enough could probe whether a given prefix is currently cached — i.e., whether someone else recently sent those tokens. vLLM's APC hashes raw token ids with no tenant isolation, so multi-tenant deployments handling sensitive prompts should think carefully about whether cross-user prefix sharing is acceptable. The mechanism is sound; the threat model is yours to define.

The matching machinery is worth one more paragraph, because its limits explain real-world hit rates. On arrival, the scheduler hashes each prompt block's token ids and looks the hashes up in a block-hash table; matches become shared references, and hashing stops at the first miss — everything after a divergence is computed fresh. A request sharing 2,050 prefix tokens gets 128 blocks (2,048 tokens) for free and recomputes the ragged 2-token edge; the granularity loss is bounded by one block, the same ≤15-token theme as section 01. Note the requirement this imposes: sharing is strictly a prefix property from position 0. Two requests with identical suffixes but different openings share nothing, which is why system prompts go first and user content goes last — prompt engineers who bury the shared instructions after per-user preamble are paying full KV price for every request.

Put a number on the agent-loop case, since that is where prefix caching earns its keep in 2026. Five hundred concurrent sessions, each re-sending a 3,000-token tool-definition block every turn, at 320 KiB/token: 500 × 3000 × 320 KiB ≈ 458 GiB of identical KV without sharing — against 188 blocks × 5 MiB ≈ 0.92 GiB shared, a ~500× reduction on the prefix portion. That is not a benchmark cherry-pick; it is the normal operating shape of tool-using agents, where the shared context dwarfs the per-turn delta. Automatic prefix caching exists because someone measured this.

05 Preemption and the scheduler contract

What happens when the blocks run out.

Blocks are finite, and the allocator will eventually say no. Size the pool for our running example on a single 80 GB A100 serving a Llama-3.1-8B-class model (32 layers, 8 KV heads, head dim 128, fp16): per-token KV is 2 × 32 × 8 × 128 × 2 = 128 KiB, so a 16-token block is 2 MiB. Weights take ~16 GB; after activations and workspace, roughly 54 GiB remains for KV at vLLM's default gpu_memory_utilization=0.9 — that's 27,648 blocks, or about 442K tokens of capacity. Every scheduling decision is a bet about how to spend those blocks.

When a running request can't get the blocks it needs, vLLM preempts: it picks victims by priority (lowest first) and takes their blocks back. The victim then faces two fates. Recompute drops the KV entirely; when the request is rescheduled, its prompt (plus tokens generated so far) goes through prefill again. Swap copies the victim's blocks to CPU RAM, preserving progress, and copies them back on resume. The trade is bandwidth against compute: swapping 1.25 GiB over PCIe 4.0 x16 (≈25 GB/s effective) costs ~50 ms each way plus CPU memory pressure — vLLM defaults to 4 GiB of swap space — while recompute costs one prefill pass over the prefix, which for short prompts is tens of milliseconds of GPU time and needs no CPU RAM at all. Short prefixes favor recompute; long ones, where prefill is expensive, favor swap. There is no universally right default, which is why both exist.

vLLM v1 reworked this layer with a unified scheduler and synchronous scheduling: the entire batch is scheduled in lockstep each iteration, replacing v0's more incremental approach. The practical effect is that block accounting becomes global — the scheduler sees all requests' block demands at once and makes one coherent preemption decision per step, rather than discovering shortfalls request by request. That coherence is what lets preemption policy interact sanely with SLOs: a scheduler that knows every request's deadline and block footprint can choose victims that minimize deadline misses (preempt the request with the most slack, or the one whose recompute is cheapest) instead of preempting blindly. The mechanism doesn't set your SLO policy, but it finally gives the policy complete information to work with.

To see the scheduler's side of the contract, watch the block budget move within a single iteration. Prefill is the hog: admitting a 2,000-token prompt demands 125 blocks at once, before a single token is generated. Decode is the trickle: one new block every 16 generated tokens per sequence. A healthy scheduler therefore thinks in two currencies — bulk allocation for arrivals, drip allocation for the running batch — and the block pool is the single account both draw from. This is also why chunked prefill (the Sarathi-Serve technique vLLM absorbed) composes so cleanly with paging: splitting a long prefill across several decode iterations just means allocating its blocks in installments, and partial prefill progress is already representable as ordinary blocks. Without paging, a half-prefilled request is an awkward half-reservation; with paging, it's 63 blocks like anything else.

The SLO interaction is then a question of victim economics. Preempting a request mid-decode discards its KV cache under recompute — the token IDs are kept and the prefix is replayed to rebuild it — so the user-visible cost is a prefill spike added to that request's latency, sized by its prefix length. Preempting a request that is one token from finishing is pure waste; preempting a freshly admitted request costs almost nothing. A deadline-aware scheduler wants exactly this cost model per candidate victim — blocks held, tokens generated, prefix length, time already invested — and the paged design hands it over in O(1) table lookups. The preemption policy is still yours to write; paging just makes sure the inputs to it are cheap and exact.

06 Open questions

Where the paging analogy strains, and what's next.

Bigger blocks, smarter eviction. The OS eventually invented huge pages (2 MiB) alongside 4 KiB pages because TLB pressure demanded it. Paging for KV cache has the analogous pressure: as sequences push toward 1M tokens, a 16-token block means 65,536 table entries per sequence and a 65K-iteration gather loop per head. Variable or larger block sizes with prefix-aware eviction — keep shared prefix blocks fine-grained, let private tails use coarse blocks — would recover the gather efficiency without surrendering sharing granularity. Nobody has shipped the equivalent of transparent huge pages for KV cache yet.

Block tables that span machines. Disaggregated serving (Mooncake-style: prefill on one pool, decode on another, KV shipped between them) already treats blocks as the unit of transfer. The next step is block tables as a distributed data structure — a sequence's logical blocks living on different machines, with the allocator and the refcounts coordinated across the fleet. vLLM v1's KV connector API is the hook this hangs on: it abstracts "move these blocks elsewhere" without the scheduler caring where elsewhere is. Cross-machine CoW and cross-machine prefix sharing are the obvious, unsolved extensions.

Blocks as quantization groups. KV quantization (8-bit, 4-bit) halves or quarters the per-token bytes — our 320 KiB becomes 160 or 80 — but quantization needs grouping: scales and zero-points computed over some span of values. A 16-token block is a suspiciously natural quantization group: already the unit of allocation, already contiguous in the block-major layout, already the granularity at which data moves. Per-block scales would make the metadata ride along with the block for free, including across CoW copies and machine transfers. The interaction to watch: sharing a block means sharing its quantization parameters, which is fine for identical tokens and subtly wrong the moment anyone requantizes — another reason the "identical tokens, identical bytes" invariant of prefix caching matters.

Architectures that change the byte math. Everything above assumed standard multi-head KV. DeepSeek's MLA compresses each token's KV into a low-rank latent vector (a few hundred dimensions instead of thousands), collapsing the per-token footprint by an order of magnitude and rewriting every number in this essay — block byte sizes, fragmentation percentages, the block-size-16 knee. Paging itself survives the transition untouched: block tables don't care what's inside a block. But the tuning (block size, sharing granularity, quantization groups) all re-derives from the new byte counts. The mechanism is architecture-agnostic; the arithmetic isn't.

Run the MLA numbers to feel how far the arithmetic moves. DeepSeek's MLA caches a compressed latent plus rotary key per token — roughly 576 elements per layer (512-dim latent, 64-dim RoPE), which is ~1.15 KiB per layer at bf16. Against our 70B GQA example's per-layer 2,048 elements (8 KV heads × 128 dim × 2 for K,V = 4 KiB), MLA shrinks each layer's cache ~3.6× — and the DeepSeek-V2 paper reports a 93.3% KV-cache reduction versus its MHA baseline, roughly 15× end to end. A 16-token block drops from ~5 MiB to ~1.1 MiB. Internal fragmentation in absolute bytes shrinks with it — but the gather loop now iterates over blocks holding ~1.1 MiB, and the per-block overhead (table entries, kernel iterations, hash-table slots for prefix caching) that used to be noise starts to dominate the cost model. The block-size-16 knee from section 02 was derived at 320 KiB/token; at ~68 KiB/token the curve shifts toward larger blocks, and prefix-cache hit granularity coarsens with it. Same paging, different planet.