skip to content

Why does a contiguous per-request KV cache waste most of an LLM server's VRAM?

level: middleimportance: must knowfreq 62%

answer

  1. length unknown when the request arrives
  2. reserve for the worst case
  3. holes of the wrong shape
  4. internal versus external fragmentation
  5. measured 60-80% of KV memory wasted

basics

~20 s

A contiguous allocator must reserve one slab per request sized for the longest output that request could produce. Most requests never grow into it, so the reserved tail sits idle, and the leftover gaps between slabs are too small for the next request to use.

solid answer

~50 s

A contiguous cache needs each sequence's keys and values to live in one unbroken range, but the sequence's final length is unknown when it arrives. The allocator therefore reserves the worst case — typically the model's maximum context length — at admission. Three kinds of waste follow. **Internal fragmentation**: the reserved tail a request never fills, which is most of it when the average answer is 200 tokens and the reservation is 8k. **External fragmentation**: when requests of different sizes finish, the freed holes are the wrong shape for the next arrival, so free memory exists but is unallocatable. **No sharing**: two requests with the same system prompt each get their own copy of identical key/value tensors. The PagedAttention work measured 60–80% of KV memory wasted this way, which is why concurrency, not weights, was the binding constraint.

code

python · 6 lines
python
MAX_LEN = 8192          # reserved per request by a contiguous allocator
actual = [180, 240, 95, 1300, 60, 410]

reserved = MAX_LEN * len(actual)
used = sum(actual)
print(f"used {used} of {reserved} token-slots -> {100 * (1 - used / reserved):.1f}% wasted")

go deeper

for a junior

Know that each in-flight request holds its own KV cache and that the cache, not the weights, is what usually limits how many requests fit at once.

for a middle

Be able to explain why an unknown output length forces a worst-case reservation, and name internal versus external fragmentation as two separate wastes with two different symptoms.

for a senior

Show you can read the symptom in production: a queue backing up while cache utilization sits well below full points at allocation shape, not at genuine capacity. Tie recovered memory to larger batches and therefore to throughput.

for a principal

Own the framing that KV memory is the per-concurrency cost that sets your cost per token, and that advertised context length, expected output length, and admission policy are one coupled decision rather than three independent knobs.

## What the allocator is being asked to do An inference server holds, for every in-flight sequence, the attention keys and values already computed for that sequence's tokens. That store grows by one token's worth of state on every decode step and is freed only when the request finishes. The server does not know at admission time how long the request will run: the model stops when it emits an end-of-sequence token or hits the request's token limit, and those can differ by two orders of magnitude between one request and the next. ## Why "contiguous" forces a worst-case reservation The naive implementation stores each sequence's cache as one dense tensor, because attention kernels want to read a flat, strided range of memory. A tensor cannot grow in place — anything adjacent may already be owned by another sequence — so the server has two options: reserve the maximum up front, or reallocate and copy every time a sequence outgrows its slab. Copying tens of megabytes mid-decode is unacceptable, so real contiguous implementations reserve up front, sized by the request's token limit or by the model's maximum context length. ## The three wastes **Internal fragmentation** is the reserved-but-unused tail inside a slab. If you reserve 8,192 tokens of cache and the answer stops at 180 tokens, roughly 98% of that slab was never touched, yet no other request could use it, because it was already accounted to this one. This dominates in chat workloads, where output length is short and highly variable. **External fragmentation** is the unusable space *between* slabs. Requests arrive and finish in arbitrary order, so the free list becomes a patchwork of holes. A new request needing one large contiguous range can be refused while several gigabytes of total free space exist, scattered across holes of the wrong size. The server reports that it is out of KV cache with a utilization gauge that looks far from full — a confusing symptom that is diagnostic of a contiguous allocator. **Duplication** is the third: a thousand requests that share the same 900-token system preamble each carry a private, byte-identical copy of that preamble's keys and values. Nothing in a contiguous layout lets two tensors overlap. ## Why this matters more than it sounds Weights are a fixed cost you pay once per replica. KV cache is a per-concurrent-sequence cost, so it is the term that decides how many users a GPU serves at once. Every wasted byte is a request that could have been batched but was not, and batch size is what keeps a decode step's matrix multiplies from being pure memory-bandwidth waste. Fragmentation therefore shows up as a throughput problem, not just a memory problem: the server queues requests while holding memory it is not using. ## What replaced it PagedAttention borrows the operating system's answer to exactly this problem. The physical cache is carved into many small fixed-size blocks, each holding the keys and values for a fixed number of tokens (vLLM calls this `block_size`, commonly 16). A sequence gets a *block table* — an indirection layer mapping its logical token positions to whatever physical blocks happen to be free. Blocks are allocated one at a time as the sequence grows, so nothing is reserved for a future that may never arrive. That removes external fragmentation entirely: every block is the same size, so any free block fits any request. It shrinks internal fragmentation to at most one partially-filled block per sequence — with a 16-token block, under 16 tokens of waste instead of thousands. And because two sequences' block tables can point at the *same* physical block, identical prefixes can be stored once and shared. ## How to recognize the problem in production Symptoms of over-reservation: cache-utilization metrics that plateau well under 100% while the queue grows; admitted concurrency that tracks the advertised maximum context rather than actual output lengths; a large drop in achievable batch size when you raise the advertised context window without changing the workload. On an engine with a paged cache, raising the maximum model length costs you a longer *possible* sequence, not a per-request reservation — a distinction candidates frequently get backwards.

  • If a contiguous cache is so wasteful, why not just reserve each request's own token limit instead of the model maximum?
    It helps, but only when clients set an honest limit — most send a generous default or none at all, and a chat UI cannot know how long the answer will be. It also leaves external fragmentation untouched: variable-sized slabs are exactly what produces unusable holes. You have traded one form of over-reservation for a scheduler that still cannot admit a request when free memory is the wrong shape.
  • Where does internal fragmentation go in a paged cache — is it eliminated?
    Reduced, not eliminated. Each sequence still has one partially-filled tail block, so the waste per sequence is bounded by the block size minus one token instead of by the reservation. With vLLM's typical block size of 16 and a few hundred concurrent sequences, that is a few thousand token-slots total rather than millions. It is also why very large block sizes reintroduce measurable waste.
  • Does a paged cache slow the attention kernel down compared with a contiguous one?
    Slightly, yes. The kernel must read a block table and gather keys and values from scattered physical blocks instead of striding through one range, which costs indirection and can hurt coalescing. The trade is overwhelmingly worth it: the lost kernel efficiency is a few percent, while the recovered memory multiplies batch size, and larger batches are what make decode steps efficient in the first place.

It is the difference between giving every hotel guest a whole floor in case they bring family, and giving them one room at a time as the family shows up.

saying these in an interview costs you the question

  • Says model weights are what limits concurrency, not the cache
  • Thinks fragmentation is fixed by simply buying a bigger GPU
  • Claims the cache is freed after every decode step
  • Confuses external fragmentation with the cache being genuinely full
  • Assumes each request's output length is known at admission

context

resolving links…