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.)