A KV cache is an allocator problem wearing an attention costume. The tensors are simple, but they grow one token at a time, for an unknown number of steps, for hundreds of sequences that start and finish independently. Hand that to a contiguous allocator and most of your HBM evaporates into fragmentation. Paged KV cache is the fix: chop the cache into fixed-size blocks, give every sequence a block table, and let the attention kernel read through the indirection. What follows is the GPU-side view: pool, mapping, kernel, reclamation policy.
The fragmentation tax of contiguous KV allocation
Give each sequence a contiguous KV slab and you must reserve its maximum length: you do not know the true length until a stop token arrives, and you cannot grow the slab in place because the neighbouring bytes belong to someone else. Three wastes follow. Internal fragmentation: a slab sized for 2048 tokens whose request stops at 180 has pinned 90% of itself for nothing. External fragmentation: as requests of differing maximum lengths come and go, the pool becomes a checkerboard of holes, none big enough for the next arrival despite ample free bytes. Reservation waste: memory held for tokens not yet generated is unreadable and unshareable.
The bill is steep because decode is memory-bandwidth-bound: every step streams the whole weight set plus the batch’s KV cache from HBM, so throughput rises with concurrency until memory runs out. KV capacity is the throughput knob, and a contiguous allocator throws most of it away.
Fixed-size blocks and the block-table indirection
The answer is the one operating systems reached decades ago. Carve the KV region into uniform blocks, each holding keys and values for a fixed number of consecutive tokens — 16 is the common default. Give every sequence a block table: an array whose entry i names the physical block holding logical tokens [i·B, (i+1)·B). Growth is a pop from a free list, and the block may live anywhere in the pool, because the table — not address arithmetic — resolves position.
All three wastes vanish by construction. External fragmentation is impossible when every free object is interchangeable. Internal fragmentation is capped at the last partial block: at most B-1 tokens per sequence. Reservation waste disappears because a block is allocated when it is needed, not when the request is admitted. The table itself is cheap: one 32-bit index per block, so a 4096-token sequence needs 256 integers.
Sizing the pool: the arithmetic behind your concurrency ceiling
The pool is preallocated once at startup, typically as one K and one V tensor per layer. Sizing it is the most consequential serving decision, and it is pure arithmetic: per token, per layer, the cache costs 2 × num_kv_heads × head_dim × bytes_per_element; multiply by the layer count for a per-token figure, and by the block size for bytes per block.
The block count is the leftover: the memory budget you allow the server, minus weights, minus the peak activation workspace measured by a profiling pass, minus anything pinned for CUDA graph replay, divided by bytes per block. Concurrency follows directly — blocks available over the average a live sequence holds. This is why grouped-query attention is such a serving lever: shrinking num_kv_heads shrinks every term in that product, and the freed bytes convert straight into batch size. The algorithmic side belongs to the transformer-math articles; here it is the denominator.
The write path: slot mapping and scatter
Reads get the attention, but paging changes the write first. After a layer projects Q, K and V, a small scatter kernel copies the new K and V into the pool, driven by a slot mapping: one integer per token in the flattened batch giving the linear destination, simply block_index × B + offset. The scheduler builds that vector on the host each step, along with the block tables — which under CUDA graph capture must sit at a fixed address and be updated in place, or replay reads a stale pointer.
The indirection is deliberately confined here. Model code never holds a pointer into the cache; it writes through a mapping. That is what makes prefix sharing, copy-on-write and preemption implementable at all: the block manager can share, move or drop blocks between steps without any attention layer noticing. Layouts keep head_dim innermost and contiguous, so each store stays vectorized despite scattered destinations.
Inside the paged attention kernel — and what the lookup costs
A dense-layout kernel walks one pointer down the sequence; a paged kernel cannot. The usual shape assigns a thread block to a (sequence, KV head) pair, iterates over that sequence’s logical blocks, reads each physical index from the block table, loads that block’s keys into registers or shared memory, accumulates dot products against the query into a running online-softmax state, then passes over the values. Within a block the memory is fully contiguous, so warp loads coalesce normally; only the boundary costs an integer lookup. Long contexts force one refinement: a single thread block per sequence leaves most SMs idle at small batch, so the kernel splits each sequence’s block list across several thread blocks and merges the partial softmax states in a cheap reduction — the split-K restructuring flash-decoding uses.
The overhead is real but bounded. The extra integer load per block, amortized over a whole block, is negligible; the larger effect is losing one long contiguous run, so the memory system sees a burst per block rather than a single stream. With a 16-token block that burst still comfortably exceeds DRAM burst granularity, so achieved bandwidth stays near the dense case. The paged kernel does measure slower than a fused contiguous one, but attention is a modest share of decode step time, so the end-to-end cost is small against a multiple-x batch gain.
Prefix sharing, reference counts, and copy-on-write
Uniform blocks buy something slabs cannot express: sharing. Production traffic is saturated with repeated prefixes: system prompts, few-shot preambles, frozen chat history, the common stem of parallel samples. A full block is immutable once written, so it can be keyed by a chained hash: hash block i together with the hash of block i-1, so a match certifies identical token history, not merely identical contents. On admission the prompt is hashed block by block, and every hit becomes a reference-count bump instead of prefill compute plus allocation.
Divergence works like a forked process. Writing into a block whose reference count exceeds one triggers copy-on-write: allocate a fresh block, device-to-device copy it, decrement the old count, redirect the child’s table entry. Only the tail partial block is ever copied, so n parallel samples cost one prompt plus n tails. The hash must key on everything that changes the KV values — adapter identity, multimodal inputs — or you will serve someone else’s cache.
Choosing a block size
B pulls in both directions at once. Larger blocks mean fewer table entries, longer contiguous runs, fewer boundary lookups and a slightly more efficient kernel. They also mean more internal fragmentation — on average about half a block per live sequence — coarser prefix sharing, since a shared prefix counts only in whole blocks, and a costlier copy-on-write when a fork diverges.
The decisive detail is that fragmentation scales with concurrency, not sequence length. Two hundred and fifty-six sequences on 16-token blocks waste roughly two thousand tokens of KV between them: trivial for long-context traffic, distinctly non-trivial for a fleet serving short requests at high concurrency. So long sequences at modest concurrency tolerate larger blocks, while short sequences at high concurrency — or workloads leaning on prefix reuse — want the smaller default. Measure cache utilization rather than guessing.
Reclaiming memory: swap versus recompute
Paging lets the scheduler admit optimistically instead of provisioning for the worst case, which means it can overcommit. A watermark — a reserve of blocks never handed out — guarantees an in-flight step can always append its token rather than failing halfway through a forward pass. Below that, the block manager picks a victim, usually the most recently admitted sequence, which preserves rough arrival-order fairness and avoids starving long-running work.
Two reclamation modes exist. Swap copies the victim’s blocks to pinned host memory, frees them, and copies back on resume: cost is twice the sequence’s KV bytes over the host link. Recompute frees the blocks outright and re-runs prefill from the token ids: one prefill, compute-bound and highly parallel. Recompute usually wins for a single sequence with a moderate prompt; swap wins for very long contexts and forked groups, where recompute repeats the same work per branch. Prefix caching softens recompute further, since a resuming sequence often re-hits its own blocks.
Operating it: the numbers that matter
Four signals tell you almost everything. KV cache utilization, the fraction of blocks in use, should sit high; permanently pinned at the watermark means you are memory-bound, not compute-bound. Preemption rate should be near zero in steady state, and a rising count says admission is outrunning capacity. Prefix cache hit ratio drives time-to-first-token, so a drop after a prompt-template edit is a real regression, not noise. The distribution of blocks per sequence shows whether long contexts or raw concurrency is the binding constraint.
Tune in that order: raise the memory budget until activation headroom gets thin, cap the served context length so block-table and graph padding do not eat the pool, revisit block size, and only then reach for a different attention shape. Note the division of labour: the block manager answers can this fit, while the iteration-level scheduler covered in the continuous-batching article decides who runs next. Paging is what lets an overloaded server degrade in throughput instead of failing outright.