The KV Cache Memory Budget and What It Costs per Token

Accelerator memory is the budget that binds inference capacity, and most of it is not spent on the model. A weight tensor is a fixed charge: it is known before the first request arrives, and it does not change as traffic does. The cache that holds attention keys and values is the opposite. It grows with every token in flight, it persists across steps, and it is the single line item that decides how many sequences a replica can hold at once. Every capacity plan eventually reduces to an inequality in which that cache is the variable.

Bytes per token, derived from the attention shapes

In a decoder layer, attention projects each token into a query, a key, and a value. For $n_{\text{layers}}$ layers and a model width $d_{\text{model}}$, a common arrangement gives each layer a key and value of width $d_{\text{model}}$, or a smaller width $d_{\text{kv}}$ when grouped-query attention shares key and value heads across query heads. Caching requires storing $K$ and $V$ for every token, so the per-token charge is

$$\text{bytes per token} = 2 \cdot n_{\text{layers}} \cdot d_{\text{kv}} \cdot b_{\text{elem}}$$

where the leading 2 counts keys and values and $b_{\text{elem}}$ is the element size, two bytes for FP16 or BF16. A 32-layer model with $d_{\text{kv}} = 1024$ and half-precision elements costs $2 \times 32 \times 1024 \times 2 = 131{,}072$ bytes, or 128 KiB, per token. At 8,192 tokens of context that is one gibibyte per sequence. A 70-billion-parameter model in half precision occupies roughly 140 GB in weights, so on an 80 GB device the weights alone do not fit; with tensor parallelism across several devices, the cache per device becomes the constraint on how many long-context sequences can be resident.

The multiplication is worth doing in the other direction too. If a device has $M$ bytes free after weights, activations, and workspace, and each sequence occupies $S$ bytes at its context length, then the number of resident sequences is bounded by $\lfloor M / S \rfloor$. This is a hard ceiling that no scheduling policy can exceed; it is why batching saturates in practice before arithmetic does.

The three ways the budget is wasted

The naive allocator reserves $S_{\max}$ bytes per sequence at admission, where $S_{\max}$ corresponds to the maximum context the model supports. A request that generates 200 tokens while the model supports 32,768 therefore holds 128 KiB times 32,768 bytes of address space and pins that memory for its lifetime. The waste is not transient; it is the difference between capacity computed at mean length and capacity computed at maximum length, and the two differ by more than an order of magnitude for typical traffic.

Fragmentation is the second loss. Variable-length reservations in a single contiguous arena leave holes that no new sequence can use, because a new sequence needs a contiguous run of a size that depends on its own eventual length, which is unknown at admission. Internal fragmentation appears within a sequence as the gap between reserved and used slots; external fragmentation appears between sequences as unusable gaps.

Over-reservation of the output bound is the third. The output length is not known in advance, so the allocator must either reserve for a worst case, grow the allocation on demand, or evict sequences when the budget runs out. Each choice has a price: worst-case reservation lowers concurrency, growth requires relocatable or paged storage, and eviction means recomputation or preemption, which consumes the very compute the cache was meant to protect.

Paging the cache into fixed blocks

The standard answer borrows from virtual memory. The cache is divided into blocks of a fixed number of tokens, conventionally 16, and a sequence holds a list of block identifiers rather than a contiguous range. A block table per sequence maps logical positions to physical blocks, exactly as a page table maps virtual to physical addresses. Allocation happens on demand, one block at a time, so a sequence that stops after 200 tokens has paid for 13 blocks rather than for the maximum.

Two quantities follow immediately, and both matter to the cost model. The waste per sequence is bounded by one partially filled block, so at 16 tokens per block the internal fragmentation is at most 15 token-slots, which is negligible against a sequence of any realistic length. And the block table is itself a structure with a size: at 4 bytes per entry and 16 tokens per block, a 32,768-token sequence needs 2,048 entries, or 8 KiB, per layer-group. Small, but not zero, and it must be counted when the budget is tight.

The design also makes sharing cheap. Two sequences that begin with the same prompt prefix can point at the same physical blocks as long as neither writes to them, with a reference count per block deciding when a block returns to the free pool. Copy-on-write applies at the moment one sequence needs to append to a block that is shared, which for prefix sharing means the divergence point rather than the first token. This is the mechanism that turns a prefix cache from a prefill optimization into a memory optimization as well, and it is the reason cache-aware routers can improve both latency and cost at once.

Turning the ceiling into a cost per token

Concurrency has a direct price. Suppose a replica’s non-cache memory is fixed, its cache budget is $M$ bytes, and the mean sequence occupies $S$ bytes over its lifetime. Then the mean number of concurrent sequences is at most $M/S$, and the throughput of the replica is bounded by that concurrency divided by the mean time per output token. Cost per token is the replica’s hourly cost divided by its token throughput, so

$$\text{cost per token} \approx \frac{C_{\text{hour}}}{3600} \cdot \frac{t_{\text{step}}}{M/S}$$

with $C_{\text{hour}}$ the fully loaded hourly cost of the replica. The expression makes the levers explicit. Shortening the mean context raises $M/S$ linearly. Raising concurrency through paging raises the achievable fraction of $M$ that is actually in use. Reducing the cache element size, for instance by storing keys and values in 8 bits, halves the bytes per token at some accuracy cost. And shortening $t_{\text{step}}$ through smaller weights or more bandwidth raises throughput without touching memory at all.

The failure mode to watch for is a plan built on mean context length. Because concurrency is set by the maximum, not the mean, of the resident sequences, a traffic mix with a long tail of long contexts will run out of blocks while the average utilization looks comfortable. The scheduler then preempts or queues, and the effective throughput collapses to the behavior of the tail rather than the behavior of the mean. Budgeting from a high percentile of context length, and treating the difference between that percentile and the mean as reserved headroom, is the conservative reading of the same inequality.

The gap between mean and high percentile is often the largest single correction in a plan, because output length is unbounded in a way prompt length is not. A prompt is whatever the client sent, and its distribution is measurable before deployment. An output length is chosen by the model, and while it usually terminates well before the configured maximum, the maximum is what the allocator must be prepared for. Sequences that run to the limit are rare but they are also the longest-lived, so they occupy blocks for many more steps than their share of request count suggests. Counting block-occupancy by token-steps rather than by request reveals that these sequences can account for a disproportionate share of cache time even when they are a small fraction of traffic.

What the budget does not cover

Cache accounting ignores the compute cost of attention itself, which grows with context length and becomes the dominant term well before memory does for some shapes. It also assumes a step time independent of batch, which holds only while weight traffic dominates; past the crossover derived in the prefill and decode analysis, each additional sequence lengthens the step. And it says nothing about the tail latency a nearly full cache produces, where admission control starts rejecting work that the arithmetic could have served. Those are scheduling questions, and they belong to the capacity model rather than to the byte count, but they are set by the same number.