KV cache fragmentation is the inference-time equivalent of the memory-fragmentation problem operating systems solved decades ago. When a transformer serves a request, it stores a key and value tensor for every token it has already processed, so it does not have to recompute attention from scratch on the next token. That storage is the KV cache. On a serving GPU it lives in a slab of high-bandwidth memory shared across all in-flight requests.

Definition

The naive approach is to give each new request a contiguous block of that slab, sized to whatever the maximum sequence length is. It is simple, it is fast — and it is wasteful in two directions at once.

Internal fragmentation: short requests get the same big block as long ones, and most of it sits unused. External fragmentation: when long requests finish and free their blocks, the holes left behind are big enough in total but each individual hole is too small for the next incoming request. The slab reports gigabytes free; the scheduler still rejects work.

The PagedAttention paper from 2023, the heart of the vLLM serving engine, ported the operating-system answer almost line for line. Instead of contiguous blocks per request, the KV cache is divided into small fixed-size pages. Each request gets a logical sequence of pages that may be scattered anywhere in physical memory, with a small indirection table mapping logical positions to physical pages. The attention kernel is rewritten to walk that table.

Why it matters

Fragmentation, not raw bandwidth, is often the limiting factor in how many concurrent requests a serving GPU can handle. vLLM reported two to four times higher throughput on the same hardware over the previous state of the art, almost entirely from reclaiming the fragmented space. For an operator running inference at scale, that multiplier shows up directly in cost per token and in tail latency.

There is a second win: paging makes it cheap to share. Several requests with the same system prompt can point at the same physical pages instead of each carrying a copy. The same trick supports cheap forks for beam search and tool-use scenarios where a conversation branches.

Common misconceptions

This is not a model property; it is a serving-system property. The same model on the same GPU can be either throughput-bound or fragmentation-bound depending entirely on the allocator.

It is not equivalent to running out of memory. You can be fragmentation-bound with most of the slab free — that is the whole point.

Paging is not free. It adds an indirection on every attention step. The win is that the lost bandwidth is much smaller than the freed capacity.

Short reading list