PagedAttention — Math + Memory Model

The KV cache is big, and it grows

Fix the shapes first, because the whole argument is about bytes. For each token the model caches a key and a value vector in every layer. The per-token cost is 2 × n_layers × n_kv_heads × head_dim × dtype_bytes — the leading 2 is for K and V. Take an OPT-13B-class model with 40 layers and a model dimension of 5120, in fp16: 2 × 40 × 5120 × 2 = 800 KB per token.

That number is why everything downstream is hard. A single sequence of 2048 tokens holds 2048 × 800 KB ≈ 1.6 GB of KV cache. On a 40 GB accelerator, after the ~26 GB of fp16 weights you have barely a dozen gigabytes left for all concurrent requests. Throughput on a memory-bound decode workload is essentially ‘how many sequences can I batch,’ and that is capped by how many KV caches fit in memory, so every wasted byte of KV cache is lost throughput. The KV cache, not compute, is the scarce resource.

Naive allocation: one contiguous slab per request

The obvious way to store a growing sequence is a contiguous array, exactly the way you would allocate a C array or a tensor. But a request arrives without telling you how many tokens it will generate, and the attention math wants all of a sequence’s keys and values laid out contiguously so the kernel can stride through them. So the classic serving systems — the pre-paged generation of frameworks — did the only safe thing: they reserved a contiguous chunk sized for the model’s maximum supported length, up front, per request.

Reserve 2048 slots, generate a 128-token reply, and 1920 slots (94%) sit allocated and untouchable for the life of the request. Across a batch the picture is grim: the vLLM measurements found existing systems wasted 60% to 80% of KV-cache memory. The kernel is fast, but the memory bill is brutal, and it shows up as three distinct kinds of waste worth naming precisely.

Three kinds of waste: internal, external, over-reservation

Over-reservation is claiming the max-length slab when you will use a fraction of it. The space is committed the moment the request starts, even though it will only ever be filled slot by slot — it is unusable by anyone else right now, when other requests could have used it.

Internal fragmentation is the reserved-but-never-used tail: the slots between the actual final length and the reserved maximum. If a request reserves L_max and stops at length L, then L_max − L slots are pure waste, discovered only at the end.

External fragmentation is the subtler killer. Because requests reserve different max sizes and finish at different times, the free pool decays into a patchwork of holes. You can have gigabytes free in total and still be unable to admit a new request, because no single hole is big enough to hold its contiguous slab. This is the identical failure mode a memory allocator hits with variable-size blocks — and the identical problem operating systems solved decades ago with paging.

The fragmentation math

Define memory utilization as the fraction of allocated KV slots that actually hold a live token: U = tokens_used / slots_allocated. For a single contiguous request that reserves the maximum and reaches length L:

U_contig = L / L_max

L = 512,  L_max = 2048   →   U = 512/2048   = 0.25   (75% wasted)
L = 128,  L_max = 2048   →   U = 128/2048   = 0.0625 (94% wasted)

That is only internal fragmentation and over-reservation; external fragmentation drags the fleet-wide number down further. The waste is worst exactly where it hurts most — short replies, which are common — because the fixed L_max denominator does not care how little you used. And there is no knob to turn: lower L_max to save memory and you cap the longest sequence you can serve, a lose-lose trade between capacity and reach. The fix is not a better guess at L_max; it is to stop reserving contiguously at all.

The operating-system analogy

A running program thinks it owns a large contiguous address space. It does not. The OS chops both the virtual address space and physical RAM into fixed-size pages (say 4 KB) and keeps a page table that maps each virtual page to some physical page frame — wherever there happens to be room. The frames backing one process’s ‘contiguous’ array can be scattered all over RAM, and the program never knows.

This single indirection kills both fragmentations at once. External fragmentation vanishes because every free frame is the same size and interchangeable — any hole fits any need. Internal fragmentation shrinks to at most part of the last page. And you allocate lazily: pages are mapped only as the program touches them, never reserved for a maximum that may never arrive. PagedAttention is this idea transplanted whole. A logical KV block is a virtual page, a physical KV block is a page frame, and a per-sequence block table is the page table. The KV cache gets to look contiguous while living in scattered physical blocks.

PagedAttention: blocks and the block table

Concretely: partition the KV cache into fixed-size blocks, each holding a constant number of tokens B (16 is a common choice) worth of keys and values. Physical blocks live in a global pool on the device and need not be adjacent. Each sequence carries a block table — an array mapping its logical block i (tokens i·B through (i+1)·B − 1) to whatever physical block currently backs it.

Decoding then allocates on demand. A sequence starts owning zero blocks; when it fills its current last block and needs slot B+1, the manager grabs one free physical block from the pool and appends it to the block table. No slab, no max-length reservation, no guessing. The one thing that has to change is the attention kernel: instead of striding through one contiguous K/V array, it reads the block table and gathers keys and values from the scattered physical blocks for the QK^T and the value-weighted sum. That gather is the entire cost of paging, and it is cheap. (How the manager schedules, evicts, preempts, and swaps those blocks is a whole subsystem covered separately in the block-manager deep-dive; here the point is the mapping itself and what it buys.)

Why fragmentation nearly vanishes

With blocks, redo the utilization math. A sequence of length L needs ceil(L / B) blocks, so it allocates ceil(L/B) × B slots. The only waste is unused slots in the final, partially filled block:

U_paged = L / (ceil(L/B) × B)

waste per sequence ≤ B − 1 tokens   (only the last block, ever)

B = 16:  worst-case waste = 15 tokens, average ≈ (B−1)/2 = 7.5

External fragmentation is gone outright: every physical block is identical and interchangeable, so a free block can serve any sequence — there are no unusable holes. Over-reservation is gone: blocks are handed out lazily, never for a max that may not come. What remains is a bounded sliver of internal fragmentation, at most B−1 tokens per sequence however long the sequence runs. For 512 tokens that ceiling is under 3%; the vLLM paper measured real KV-cache utilization near 96%, versus the 20-40% of contiguous systems.

A worked example

Put numbers on the win. Same 40 GB device, same 800 KB/token OPT-13B, L_max = 2048, block size B = 16. Suppose 14 GB is free for KV cache after weights, and the live traffic is short: sequences average L = 256 tokens.

Contiguous (reserve L_max):
  per request = 2048 × 800 KB = 1600 MB
  concurrent  = 14 GB / 1600 MB   ≈ 8 requests

Paged (allocate to length):
  blocks/req  = ceil(256/16) = 16 blocks = 256 slots
  per request = 256 × 800 KB  = 200 MB
  concurrent  = 14 GB / 200 MB    ≈ 71 requests

Same hardware, same model, roughly 9× the concurrent batch — purely from not wasting memory. Because decode is memory-bandwidth-bound and a bigger batch amortizes each weight load across more sequences, that 9× in resident requests is a large, real throughput gain — and a request that runs long simply keeps appending blocks up to L_max, penalizing no one who stayed short.

Copy-on-write: sharing blocks across samples

The block table buys one more thing the contiguous slab never could: sharing. When several outputs spring from the same prompt — parallel sampling of k candidates, or the beams of a beam search — they share an identical prompt prefix. Under paging, all of them can point their early block-table entries at the same physical blocks. The prompt’s KV cache is computed and stored once, and each sample borrows it by reference. A per-block reference count tracks how many sequences share it.

Sharing is safe only while the block is read-only. The moment one sample writes a divergent token into a block others still share, the manager applies copy-on-write: copy that one block to a fresh physical block, decrement the original’s refcount, and let the writer scribble on its private copy while everyone else keeps the shared original. This is exactly how fork() shares pages between parent and child, and it is granular — only the single block written is duplicated, not the whole prefix. The vLLM measurements report roughly 6-10% memory saved for parallel sampling and up to 55% for beam search, where beams share long prefixes and continually diverge and merge; dropping a beam just decrements counts, and a block returns to the free pool the instant its count reaches zero.

None of this is expressible with contiguous slabs, because two sequences cannot share the middle of one array while diverging at the ends — sharing requires the indirection. That is the deeper lesson: the block table is not just a fragmentation fix but a layer of indirection, and indirection is what makes lazy allocation, sharing, and copy-on-write possible at once. The same abstraction that gave operating systems demand paging and fork() gives LLM serving near-full utilization and near-free prefix sharing.