What is KV cache fragmentation?

It is an allocation failure where free accelerator memory exists, but it is split into pieces that do not fit the next request’s KV cache shape. The allocator may reject a request or trigger expensive compaction even though the sum of free regions is large enough.

Why does KV cache fragmentation happen in LLM serving?

Requests have different prompt lengths, generate for different amounts of time, and finish unpredictably. When one request ends, its KV cache region becomes free while neighbouring requests remain live. Over time, this creates gaps of many sizes, so a later longer request may not find a suitable contiguous region.

How is this related to operating system fragmentation?

It is the same external fragmentation problem seen in classical allocators: variable-size objects with variable lifetimes are placed into a linear memory space, then leave holes when freed. OS paging avoids requiring contiguous physical frames. Paged KV cache uses the same idea by storing logical sequences across fixed-size physical blocks.

The KV Cache

03.06 · Concept

Fragmentation

Explain the KV cache fragmentation problem: a finished request leaves variable-sized holes that block larger allocations even though total free memory is sufficient. Connect it to classical OS memory fragmentation.

KV cache fragmentation is external fragmentation in accelerator memory: completed generations free differently sized regions, and the next long request may need a contiguous layout that none of those regions can satisfy. Total free memory can look healthy while admission still fails, just like a classical heap or physical-memory allocator without paging.

What this lesson answers

why KV cache has memory fragmentation
how finished requests cause KV cache holes
why paging helps KV cache allocation

Notes

KV-cache fragmentation is the allocator failure mode where the free capacity in accelerator memory is large enough in aggregate but is split into holes whose shapes do not satisfy the next request’s required KV-cache layout. For a decoder-only model, the per-token KV footprint is $b_{tok} = 2 \cdot L \cdot H_{k v} \cdot d_{h} \cdot s$ , where $2$ is for K and V, $L$ is layer count, $H_{k v}$ is the number of KV heads, $d_{h}$ is head dimension, and $s$ is bytes per scalar. A request with current or reserved length $T$ therefore needs $T b_{tok}$ bytes if allocated contiguously.

References

KV Cache & Transformer Attention Optimization

Common questions

What is KV cache fragmentation?: It is an allocation failure where free accelerator memory exists, but it is split into pieces that do not fit the next request’s KV cache shape. The allocator may reject a request or trigger expensive compaction even though the sum of free regions is large enough.
Why does KV cache fragmentation happen in LLM serving?: Requests have different prompt lengths, generate for different amounts of time, and finish unpredictably. When one request ends, its KV cache region becomes free while neighbouring requests remain live. Over time, this creates gaps of many sizes, so a later longer request may not find a suitable contiguous region.
How is this related to operating system fragmentation?: It is the same external fragmentation problem seen in classical allocators: variable-size objects with variable lifetimes are placed into a linear memory space, then leave holes when freed. OS paging avoids requiring contiguous physical frames. Paged KV cache uses the same idea by storing logical sequences across fixed-size physical blocks.

Short definition: what is Fragmentation?

03.05 · The KV CacheMHA, MQA, GQA 03.07 · The KV CachePaged Attention