KV cache capacity planning

Everything a serving engine keeps in GPU memory beyond the weights themselves is key and value tensors, and they come from two places that share one pool: the sequences currently generating, whose caches grow by a row per token, and the prefixes retained from finished requests in the hope that something will reuse them. Neither has a reservation. The engine allocates blocks to whoever needs them and drops retained blocks when the running batch needs the room.

This chapter is about sizing that pool and finding the point where it runs out. The arithmetic is short and worth writing down explicitly rather than trusting a configuration value, because two of the terms — the weights and the CUDA context — consume most of the card before any cache exists. Then two mechanisms make the nominal capacity figure optimistic: padding, which is mostly historical but explains why older stacks bucketed requests by length, and reference counting, which pins blocks that are in use and concentrates all capacity pressure on the retained ones. And finally there is an experiment: ramp concurrency against a realistic length distribution, and record the concurrency at which throughput peaks, which is not the concurrency you want to run at.

The budget, computed rather than assumed#

Everything follows from one expression, which chapter 1 gave per token and which needs multiplying out per device:

kv_bytes = 2 × layers × kv_heads × head_dim × dtype_bytes × total_resident_tokens

The total_resident_tokens term is the sum over every sequence currently generating and every prefix block being retained for reuse. Those are not separate pools.

def kv_capacity(total_vram_gb, weights_gb, overhead_gb,
                layers, kv_heads, head_dim, kv_dtype_bytes, util=0.90):
    usable = total_vram_gb * util - weights_gb - overhead_gb
    per_token = 2 * layers * kv_heads * head_dim * kv_dtype_bytes   # bytes
    return {
        "kv_gb": round(usable, 2),
        "bytes_per_token": per_token,
        "total_tokens": int(usable * 1e9 // per_token),
        "blocks_of_16": int(usable * 1e9 // (per_token * 16)),
    }

kv_capacity(total_vram_gb=24, weights_gb=16.06, overhead_gb=1.8,
            layers=32, kv_heads=8, head_dim=128, kv_dtype_bytes=2)
# {'kv_gb': 3.74, 'bytes_per_token': 131072, 'total_tokens': 28533, 'blocks_of_16': 1783}

Three point seven gigabytes, on a 24 GB card. Sixteen of the twenty-four are weights, roughly two more are the CUDA context, activation workspace, and captured graphs, and the gpu_memory_utilization=0.90 guard hands back another 2.4 to the driver. What is left is not a rounding error on the budget — it is the budget, and it is the smallest number in the calculation.

Every term in that call is worth being able to reproduce, since the whole purpose of writing it out is not to take a configuration value on trust. The weights come first and they are the largest: an 8B model holds eight billion parameters, and bf16 stores each of them in two bytes, which is where sixteen of the twenty-four gigabytes go before anything else is allocated at all. The overhead term covers the CUDA context, the activation workspace intermediate tensors are computed in, and any captured CUDA graphs, none of which scales with the cache. The utilisation guard is a deliberate margin handed back to the driver, so that an allocation the engine did not anticipate does not take the process down. What survives all three is then divided by the per-token cost from chapter 1 — 128 KiB on this architecture — and that division is the 28,533.

max_model_len makes no statement about any of this. It is a ceiling on what a single request may ask for, enforced by the tokenizer and the position encoding; whether the device can hold the result is a separate question that nothing in the configuration checks.

The belief that produces the failure is worth writing out in the form somebody would hold it: the engine accepted max_model_len=32768, so the engine can serve a 32,768-token request. It is tempting because configuration values usually are validated, and because a limit that is silently unachievable is an unusual thing to ship. What is being validated is that the number does not exceed what the model's position encoding supports, which is a statement about the architecture and not about the card the process happens to be running on. The device figure appears nowhere in that check, so the two can disagree by two orders of magnitude and the process will still start cleanly.

The levers on the capacity number are visible in the formula, and they differ enormously in cost:

Every row there is the same formula with one factor changed, which is what makes them comparable at all. Storing each value in one byte rather than two halves dtype_bytes, so the per-token cost halves and the token capacity doubles; the second row is the first row's capacity multiplied by two and nothing else about the deployment has moved. Quantising the weights changes a different term entirely — it leaves bytes per token untouched, shrinks the subtraction at the front of the calculation, and hands the freed gigabytes to the same pool. Splitting the model across two cards divides both the weights and the per-card KV between them, which is why the fourth row shows a halved per-card cost and a much larger total. Read that way, the table says which lever to reach for: the ones that change bytes per token scale the capacity, and the ones that change the subtraction only add a fixed amount to it.

Halving the KV dtype is by far the cheapest of these and the one most teams reach for last, usually because the memory arithmetic was never written down and the problem presented itself as "we need bigger cards".

Where the nominal estimate stops being true#

Twenty-eight thousand tokens is the number if every allocated slot holds a real token. Two mechanisms make that false, and they are worth separating because only one of them is still a live problem.

Padding is the historical one. A static-batching implementation allocates a rectangular KV tensor sized to the longest sequence in the batch, so a batch of 32 requests with lengths ranging from 120 to 7,900 tokens allocates 32 × 7,900 = 252,800 slots to hold about 44,000 tokens of real content. That is 5.7× waste, and it is why early serving stacks bucketed requests by length and refused to mix them — a scheduling constraint that hurt latency in order to protect memory.

That waste figure is one division and is worth performing. Allocating a rectangle 32 rows deep at the length of the longest sequence gives 32 × 7,900 = 252,800 slots, the requests sharing the batch actually carry about 44,000 tokens between them, and dividing the first by the second gives roughly 5.7. Nothing in that arithmetic refers to the model, the prompt, or the hardware, which is why the problem was universal and why the remedy had to be structural rather than a tuning parameter somebody could set better.

PagedAttention removed it by allocating in fixed-size blocks, typically 16 tokens, indexed through a per-sequence block table rather than requiring contiguity. A sequence of 120 tokens takes 8 blocks and a sequence of 7,900 takes 494, with no relationship between them. The residual waste is internal fragmentation only: the last block of each sequence is partly empty, costing on average 7.5 tokens per sequence, which at 32 sequences is 240 tokens out of 28,533. Under one percent.

Two of those numbers reward deriving. A block count is a token count divided by 16 and rounded up, because a partly filled block is still an allocated block: 120 tokens fill seven blocks and start an eighth, and 7,900 tokens reach 494 by the same rounding. The 7.5 is what that rounding costs on average. Dividing a sequence's length by the block size leaves a remainder somewhere between one and sixteen, one remainder is about as likely as another, and the unused part of the final block is sixteen minus that remainder — which comes out at half a block across many sequences. Multiply half a block by the number of concurrent sequences for the total, divide it into the pool, and the result is the sub-one-percent figure. That is the whole of the fragmentation story under paged allocation, which is why the paragraph after it moves on to a different scarcity entirely.

External fragmentation in the classical sense is gone with it, because any free block is as good as any other. What replaces it is a subtler scarcity: blocks that are logically free but cannot be reclaimed because something still references them.

Blocks b0–b2 hold a shared system prefix and carry a reference count of two while both requests are live. An eviction policy can only drop blocks whose count is zero, so a prefix in active use is pinned no matter how much pressure the allocator is under. That is correct behaviour, and it means capacity pressure is absorbed entirely by the retained blocks — the ones nobody is currently generating against, which is precisely the set you were counting on for your hit rate.

The failure you will actually see is not an OOM#

Run a mixed-length continuous-decoding load and watch what happens as you approach capacity. The device does not usually crash; a well-built engine notices it cannot allocate and takes something away instead.

WARNING  Sequence group cmpl-7f3a preempted by PreemptionMode.RECOMPUTE
WARNING  Preemption count: 41. GPU KV cache usage: 99.8%, prefix cache hit rate: 0.11

Preemption means a running sequence had its blocks reclaimed and will be restarted, recomputing its prefill from scratch when it is rescheduled. Nothing errors. The request completes, correctly, having burned its prefill twice. What the caller sees is a time per output token that was 18 ms suddenly showing 400 ms stalls and a p99 that has come apart, and what the dashboard shows is throughput flattening and then declining as load increases, because an increasing share of the GPU is redoing work.

The declining half of that sentence is worth deriving, because a system that gets slower when you add load is counter-intuitive enough to be misread as a fault somewhere else. PreemptionMode.RECOMPUTE discards a sequence's blocks and restarts it, so the prefill that sequence had already paid for is paid a second time. Every preemption therefore adds work to the device without adding a completed request, and the useful fraction of GPU time falls. Requests keep arriving at the same rate, so concurrency does not drop; concurrency does not drop, so pressure does not ease; pressure does not ease, so the next allocation preempts something else. Each link there is checkable and none of them is a bug. The engine is doing exactly what it was built to do, and the design has a regime in which doing it correctly sends throughput backwards.

The second half of that log line is the part that connects back. Prefix cache hit rate 0.11, in a workload where the shared prefix has not changed. Under memory pressure the allocator evicted every retained block to feed the running batch, so every request now pays a full cold prefill, which lengthens every request, which raises concurrency, which increases pressure. Cache hit rate and load are coupled in the wrong direction: the mechanism that protects you from prefill work is the first thing sacrificed when prefill work is what is drowning you.

Instrument for that specifically. Three series, on one graph, sampled every ten seconds:

stats = engine.get_stats()
emit("kv_cache_usage",   stats.gpu_cache_usage_sys)      # 0.0 – 1.0
emit("prefix_hit_rate",  stats.prefix_cache_hit_rate)
emit("preemptions",      stats.num_preemptions_total)    # counter, graph the rate

The shape to recognise is KV usage climbing to a plateau just under 1.0, hit rate collapsing shortly after, and the preemption counter turning from flat to linear. When you see it, the effective fixes are the ones that reduce resident tokens — lower max_num_seqs, lower max_model_len to something the device can actually hold, fp8 KV, or more cards — and the fix that is not effective is enlarging the cache, because there is no separate cache to enlarge.

Running the experiment that finds the cliff#

The point at which throughput stops rising is a property of your length distribution, not of the model, so it has to be measured against traffic shaped like yours. Two design choices make the result meaningful.

Use a realistic mix of lengths rather than a fixed one. A load test that sends 2,000-token prompts thirty-two times over produces a tidy, uniform allocation pattern that no production workload ever exhibits, and it will report a capacity number you cannot reach. Sample from the length distribution in your own logs — usually long-tailed, with a mass of short requests and a thin tail of very long ones — because it is the tail that decides when allocation fails.

Include a shared prefix in a controlled fraction of the requests, since that fraction is what determines how much of the pool is retention rather than in-flight state.

import random, numpy as np

lengths = np.random.lognormal(mean=6.6, sigma=0.9, size=2000).astype(int)
lengths = np.clip(lengths, 64, 8_192)      # p50 ≈ 740, p99 ≈ 5,900

def make_request(shared_fraction=0.7):
    n = int(random.choice(lengths))
    if random.random() < shared_fraction:
        return SHARED_PREFIX + filler(max(0, n - len(SHARED_PREFIX_IDS)))
    return filler(n)                        # unique, forces a write

Then ramp concurrency in steps, holding each level long enough for the queue to reach steady state — ninety seconds is usually enough — and record four series per level.

Throughput peaks at sixteen and declines from there, which is the whole result. The two columns that explain it are the ones nobody graphs by default: the hit rate collapses at exactly the concurrency where KV usage saturates, and preemptions appear in the same row. Past the peak, adding load subtracts throughput, because each additional sequence displaces retained blocks and forces prefill work that the retained blocks were preventing.

The operating point to choose is not the peak. It is a step or two below it — twelve, here — because the peak sits on a cliff and the length distribution in production has a heavier tail than the one you sampled. Admission control — the cap on how many requests the engine will run concurrently, with the rest held in a queue — set at the peak converts a modest traffic surge into a preemption storm; set below it, the same surge queues, which is slower for the requests that wait and stable for everything already running.

Repeat the ramp with the shared fraction set to zero to see the same curve without any retention benefit at all. The gap between the two peaks is what prefix reuse is worth in throughput terms on your traffic, and it is the number to quote when someone asks whether the memory spent on retention is earning anything.

The context window, and where the numbers are moving#

A context window is not a memory guarantee, and max_model_len × max_num_seqs is not a capacity plan. A capacity plan is the kv_capacity calculation above, sized against the distribution of your sequence lengths rather than their maximum, with headroom for retained prefixes you want to keep resident.

This is also not a settled area. The per-token cost in the formula has been the target of steady architectural pressure: grouped-query attention cut it by a factor of four by sharing KV heads across query heads, fp8 and int8 KV quantisation halve or quarter it again, and multi-head latent attention compresses K and V into a shared low-rank representation that is reconstructed on read, trading arithmetic for an order of magnitude less resident memory. Offloading cold blocks to host RAM or NVMe is the other direction — keeping entries alive past the point where device memory would have evicted them, at the cost of a PCIe transfer on the hit. Every one of these changes the numbers in this chapter and none of them changes its structure.

Capacity planning for a KV cache is therefore three steps, in order. Compute the pool from the architecture and the card rather than reading it off a config value, because the weights and the context take most of the device and what remains is smaller than anyone guesses. Recognise that retained prefixes and in-flight sequences draw on that one pool, with reference counting ensuring that pressure lands on retention first. And find the concurrency cliff empirically against a realistic length mix, then operate below it, because the failure past the peak is not a crash you can alert on but a slow inversion where more load produces less work.

What none of that touches is the class of failure where memory is ample, the hit rate is excellent, the latency graphs are flat, and the entry that was served belonged to somebody else. Everything in this chapter announces itself in a log line or a metric. The next one does not announce itself at all.