KV Cache, Batching and Little's Law

The memory equation that decides how many sequences fit, and why static batching wastes a logarithmically growing fraction of the GPU.

LLM OpsAdvanced⏱ 1 hour13 min readkv cachebatchinglittle's lawgqapaged attention

4 problems →

AssumesInference Arithmetic and the Roofline · Expectation, Variance and Conditional Expectation

The memory equation

PropositionKV cache size

For a model with $L$ layers, key/value width $d_{kv}$ and $b$ bytes per stored element, the cache holds

M_{\mathrm{KV}} = 2\,L\,d_{kv}\,b \quad \text{bytes per token per sequence},

so a batch of $B$ sequences of length $S$ requires $2BSLd_{kv}b$ bytes.

Assumptions

One key vector and one value vector are stored per layer per token — hence the leading 2.
$d_{kv} = n_{kv} \cdot d_h$ , where $n_{kv}$ is the number of key/value heads and $d_h$ the head dimension. Multi-head attention has $n_{kv} = n_{\text{heads}}$ and so $d_{kv} = d$ ; grouped-query attention shrinks $n_{kv}$ ; multi-query attention takes $n_{kv} = 1$ .
No cross-sequence sharing. Prefix sharing changes this and is discussed below.

CorollaryMaximum concurrent sequences

With total device memory $M$ , weights $M_W$ and overhead $M_O$ , the number of concurrent sequences at context length $S$ is bounded by

B_{\max} = \left\lfloor \frac{M - M_W - M_O}{2SLd_{kv}b} \right\rfloor .

Throughput and concurrency

TheoremLittle's law

For a system in which requests arrive, spend time inside, and depart, let $\lambda$ be the long-run arrival rate, $W$ the long-run mean time a request spends in the system, and $\bar L$ the long-run mean number of requests in the system. If these limits exist and are finite, then

\bar L = \lambda W .

Assumptions

Stationarity and finiteness of the three limits. No assumption on the arrival process, the service-time distribution, the number of servers, or the scheduling discipline. This is what makes the law usable: it holds for a system as messy as an LLM server.

Key idea

For a server, read Little's law as

\underbrace{B}_{\text{mean concurrency}} = \underbrace{\lambda}_{\text{requests/s}} \times \underbrace{W}_{\text{mean latency}}.

Concurrency is not a free parameter you tune independently of latency and throughput — fixing any two fixes the third. Since $B$ is capped by memory, so is the product $\lambda W$ : you may serve many slow requests or few fast ones, and the trade is arithmetic, not engineering skill.

Why static batching wastes the machine

Static batching groups $B$ requests, runs them together, and returns the batch when all have finished. Since sequences stop at different lengths, the short ones keep occupying a slot — and consuming decode steps — long after they are done.

PropositionStatic batching utilisation decays like 1/log B

Let output lengths $S_1,\dots,S_B$ be i.i.d. exponential with mean $\mu$ . Define utilisation as the expected fraction of computed token-slots that carry useful work,

U_B = \frac{\E\big[\sum_i S_i\big]}{B \cdot \E\big[\max_i S_i\big]} .

Then

U_B = \frac{1}{H_B}, \qquad H_B = \sum_{k=1}^{B}\frac{1}{k} \sim \ln B .

At $B = 8$ this is $U \approx 0.37$ ; at $B = 32$ , $U \approx 0.25$ ; at $B = 128$ , $U \approx 0.19$ . Utilisation gets worse as you batch harder — the opposite of what batching is supposed to buy.

Key idea

Continuous (in-flight) batching removes this loss by construction: a finished sequence is evicted and a queued one admitted at the next step, so slots never idle. The gain is not an optimisation of a constant factor — it is the removal of an $\Theta(\log B)$ penalty that grows precisely as you scale up.

What this does not say

The exponential assumption is doing real work. It is a reasonable first model for "stop tokens arrive at a roughly constant hazard rate", and empirical length distributions are heavier-tailed than exponential, which makes the gap worse, not better. But the exact constant $1/H_B$ is a property of the exponential model, not a measured quantity. The qualitative claim — utilisation decays with $B$ under any non-degenerate length distribution — follows from $\E[\max] > \E[\text{mean}]$ and needs no distributional assumption.

Paging the cache

Allocating a contiguous buffer sized for the maximum possible context wastes everything between the actual length and that maximum. Block allocation fixes this.

PropositionBlock paging bounds internal fragmentation

If the cache is allocated in blocks holding $k$ tokens each, then a sequence of length $S$ wastes

w(S) = k\left\lceil \frac{S}{k} \right\rceil - S \ <\ k \quad\text{token-slots},

independent of $S$ and of any maximum context length.

So total waste across $B$ sequences is under $Bk$ slots regardless of context length, versus $\sum_i (S_{\max} - S_i)$ for contiguous preallocation — a quantity that grows with the declared maximum rather than the used length. Choosing $k$ trades fragmentation (small $k$ ) against per-block indirection overhead in the attention kernel (large $k$ ); values in the tens are typical.

References

PaperJ. D. C. Little (1961). A Proof for the Queuing Formula L = λWThe original distribution-free proof.
PaperW. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttentionIntroduces block-paged KV allocation; the fragmentation bound below is stated independently.
PaperJ. Ainslie et al. (2023). GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionKV cache sizeproof includedThe cache costs 2·L·d_kv·b bytes per token per sequence, linear in context length and independent of batch-wide sharing.
CorollaryMaximum concurrent sequencesproof includedAvailable memory after weights, divided by per-sequence cache, bounds the batch size — usually well below the batch needed to be compute-bound.
TheoremLittle's lawproof includedIn any stable queueing system the mean number in system equals arrival rate times mean time in system, with no distributional assumptions.
PropositionStatic batching utilisation decays like 1/log Bproof includedWith exponentially distributed output lengths, a static batch of size B wastes a fraction 1 − 1/H_B of its decode steps.
PropositionBlock paging bounds internal fragmentationproof includedAllocating the cache in blocks of k tokens wastes fewer than k tokens per sequence, independent of context length.

Problems (4)

All problems