Fragmentation
Fragmentation is an allocator problem where memory is free in total but unusable for a request because it is scattered into incompatible gaps. In LLM serving, KV-cache fragmentation happens when completed or shorter requests leave holes that cannot hold a later sequence’s required cache layout, even though aggregate accelerator memory looks sufficient.
The problem appears because KV cache allocations are large, uneven, and short-lived in unpredictable ways. Each live sequence needs storage for its keys and values across model layers as it is prefilled and then decoded. Some requests finish early, some continue for much longer, and their reserved cache regions are released at different times. If the allocator expects a sequence to occupy one contiguous region, those releases create holes between still-live regions.
Mechanically, this is the same external fragmentation known from operating systems and heap allocators. Imagine accelerator memory as a line of slots. Request A, B, and C reserve differently sized ranges. B finishes, leaving a gap, but A and C remain. A new request may need more contiguous KV space than that gap provides. Several gaps together may be large enough, but a contiguous allocator cannot stitch them together without moving live cache data or rejecting admission.
Paged KV-cache designs change the shape of the problem. Instead of giving each sequence one continuous slab, the runtime splits KV storage into fixed-size physical blocks. Each sequence has a logical table saying which blocks contain its tokens, and the attention kernel follows that table when reading keys and values. This is analogous to virtual memory paging: logical contiguity is preserved for the program, while physical placement can be scattered.
The tradeoff is that paging reduces external fragmentation but does not make memory free. It introduces block-table lookups, less regular memory access, and internal slack in the last block of each sequence. Smaller blocks waste less tail space but add more indirection; larger blocks are simpler but bring back more waste. The right choice depends on context lengths, concurrency, batching policy, kernel implementation, and prefix-sharing behaviour.
Engineers meet this in inference servers, especially with continuous batching and paged-attention runtimes. Symptoms include out-of-memory errors despite apparently available KV capacity, admission failures after mixed workloads, or throughput changes when block size or batching policy is altered. vLLM-style paged KV caches, TensorRT-LLM paged caches, and prefix-reuse systems all expose the same core issue: KV placement is an allocator problem, not just a model-size problem.
Common questions
- Is KV-cache fragmentation the same as running out of memory?
- No. True out-of-memory means the requested live KV data exceeds available capacity. Fragmentation means enough memory may exist in aggregate, but not in a form the allocator can use. Paging can help with fragmentation by using scattered blocks, but it cannot fit a workload whose actual KV requirement is larger than the device can hold.
- Why is the KV cache especially prone to fragmentation?
- Requests have different prompt lengths, generate different numbers of tokens, and finish at unpredictable times. The cache also grows or is reserved according to sequence length, so allocation sizes vary widely. That combination of variable size and variable lifetime is exactly the pattern that creates external fragmentation in classical memory allocators.
- Does PagedAttention eliminate fragmentation?
- It mostly changes external fragmentation into bounded internal waste. Fixed-size blocks mean a sequence can be assembled from many free blocks rather than one large hole. However, the final block of each sequence may be partly empty, and the attention kernel must handle block-table indirection. Whether that is worthwhile depends on workload and implementation.
- Is FlashAttention a fragmentation fix?
- No. FlashAttention is primarily an attention I/O and kernel efficiency technique. It can be combined with paged KV-cache kernels, but by itself it does not decide where KV blocks live or solve the problem of scattered free cache memory. Fragmentation is handled by the serving runtime’s allocator and scheduling design.