Paged Attention › The Memory Fragmentation Problem

To understand why fragmentation occurs, we need to examine how traditional KV cache systems allocate memory. When a new request arrives, the system must reserve memory for the KV cache that will grow as tokens are generated. But here is the challenge: the system does not know in advance how long the final sequence will be. A user asking for a one-sentence summary and a user asking for a detailed technical report both arrive as requests, and the system must accommodate both without knowing which is which ahead of time.

The naïve solution is to reserve the maximum possible amount of memory upfront. If your model supports 4,096 tokens, reserve space for 4,096 KV pairs for every single request, regardless of what the request will generate. This approach is safe in the sense that you will never run out of space mid-generation, but it is profligate. Most requests generate only a few hundred tokens, leaving the large majority of the reserved memory permanently empty.

Think of traditional KV cache allocation as a hotel that gives every guest the presidential suite, regardless of how long they are staying. A business traveler checking in for one night gets the same 3,000-square-foot suite as a family staying for a week. The hotel (your GPU) fills up quickly, and yet most of the space is sitting completely empty. The correct solution is to give guests rooms that match their actual needs, and expand to a larger room only if they ask for more space. That is exactly what PagedAttention does.

Two distinct types of fragmentation compound to make this problem severe. Internal fragmentation occurs when the unused portion within a single reservation is wasted. External fragmentation occurs when completed requests free their reservations, leaving gaps in memory that are too small or too scattered to accommodate new requests. Both types are endemic to contiguous-allocation schemes, and together they can make a GPU with 40 GB of memory behave as if it has only 8-16 GB available.

Traditional systems handle uncertainty about output length by pre-allocating memory based on the maximum possible sequence length. If your model supports 4,096 tokens, the system reserves space for all 4,096 KV pairs for each sequence, even if most requests only generate a few hundred tokens. The logic is defensible: if you don't reserve enough space, generation will fail or require expensive memory reallocation mid-flight. But the cost is enormous wasted capacity.

The issue goes deeper than just wasted space on the current request. Because all that reserved memory is locked up, it cannot be used for other requests. A GPU that could theoretically serve forty concurrent requests might be limited to eight or ten, because each request holds ninety percent of its reservation empty. This directly translates to lower throughput: fewer requests per second, higher latency for queued requests, and underutilized compute hardware.

External fragmentation is the second and often more damaging type of memory waste. It occurs not within a single allocation but in the gaps between allocations that form as requests complete and free their memory. Even if every individual request used every byte of its reservation perfectly, the pattern of arrivals and completions over time would still fragment the available memory.

Consider what happens over time in a busy serving system. Requests A, B, C, and D all start at roughly the same time and are allocated contiguous memory blocks. Then A finishes, freeing its block. Then C finishes, freeing its block. Now the memory looks like a checkerboard: used, free, used, free. A new request E arrives needing slightly more memory than either gap provides. The allocator cannot give E a single contiguous region, even though the total free space is more than sufficient.

Think of external fragmentation like trying to fit a long sofa into a truck where someone has already loaded boxes of equal size on each end, leaving two separate gaps in the middle. Each gap is half the sofa's length, but the sofa cannot be split, so it won't fit. The truck looks half-empty, but you cannot use the empty space for the furniture you have.

This is external fragmentation: the memory has 20 free slots, but they're split into two non-contiguous regions of 10 slots each. A new request requiring 12 contiguous slots cannot be served, even though sufficient total memory exists. In practice, with many concurrent requests starting and completing at different times, this fragmentation can become severe. The system will decline new requests not because it has run out of memory in any absolute sense, but because the available memory has been sliced into pieces too small to use.

Internal fragmentation compounds the problem further. Even if we could perfectly eliminate external fragmentation, we would still waste memory within every single allocation. When we allocate based on maximum sequence length but the actual sequence is shorter, the unused portion within the allocation is wasted for the duration of that request. This waste is guaranteed: unless every request uses exactly the maximum number of tokens, some capacity within each block is always empty.

Internal fragmentation is hardest to avoid with fixed pre-allocation because it is a direct consequence of not knowing the future. You reserved 4,096 tokens; the sequence only used 312. The remaining 3,784 tokens worth of KV cache memory sit idle, warming the GPU's memory banks while giving no useful work.