KV Cache Fragmentation
Once you accept the KV Cache's memory-for-compute trade, the question becomes how to store a cache for many concurrent requests of wildly different, unknown-in-advance lengths. A naive serving stack answers by pre-allocating one contiguous VRAM block per request, sized to the maximum possible output length — reserving an entire hotel floor for a single guest. Three distinct wastes follow, and they are worth separating because they have different cures:
- Internal fragmentation — the reserved-but-unused tail inside each allocation. Max context 2048 tokens, average request uses ~300: ~1,500 tokens of VRAM sit empty, per request, for the life of the request.
- External fragmentation — the unusable gaps between allocations of varying size. A new request needing 500 tokens may find that 500 tokens of free memory exist, but no contiguous region large enough to hold them.
- Redundant duplication — the same content stored many times. Every concurrent request carries its own copy of an identical system prompt.
This taxonomy is the diagnosis that makes Paged Attention legible as the cure: paging attacks internal fragmentation (pages are 16 tokens, so the tail waste is bounded by a page), external fragmentation (pages need not be contiguous), and duplication (a block table lets two requests point at one physical page) with a single mechanism. The lesson generalizes past LLMs: fragmentation is what you get when you allocate for the worst case a request might reach rather than the size it has. Operating systems learned this in the 1960s.
Claims
- Allocating for the maximum an object might reach, rather than the size it has, produces fragmentation. principle — durable, and not specific to LLMs; it is the general result that motivated virtual memory. The LLM case is unusually severe because output length is unknown until generation ends.
- KV cache waste has three separable modes: internal fragmentation, external fragmentation, and redundant duplication. observation — the source's taxonomy. Useful precisely because each mode is measurable and each is fixed by a different property of paging.
- Traditional systems waste roughly 60–80% of the memory budgeted for KV cache. observation — the video states "research shows" this figure, without naming the study; attributed to the source and check-worthy against the PagedAttention/vLLM paper. Note the compounding: on the source's own A100 40 GB / 13B example, the KV budget is only the 35% left after weights, so 60–80% of that is lost.
- Diagnose the memory before optimizing the model. best practice — context: a deployment whose latency climbs and throughput collapses as concurrency rises, on hardware that fits the model. "Best" because in that regime the fragmentation loss dominates any plausible model-side win. It is not a general instruction to ignore model choice — under low concurrency, or when the weights themselves don't fit, the ordering reverses.
Related
- KV Cache — the thing being fragmented; fragmentation is the bill for its memory-for-compute trade.
- Paged Attention — the cure; each of the three waste modes maps to one property of paging.
- Prefill and Decode Phases — decode is memory-bound, which is why fragmentation shows up as latency you can see rather than merely as wasted capacity.
- Prompt Caching — the duplication mode, solved at the API boundary rather than the allocator.
- Distillate: KV Cache and Paged Attention: Why LLM Serving Is Memory-Bound