The KV Cache and Incremental Decoding

A decoder-only language model generates one word, then the next, then the next, each time looking back at everything it has said so far. Done naively, producing the 500th token means re-running attention over all 500 preceding tokens from scratch — recomputing things the model already computed 499 tokens ago and hasn't forgotten. Do that for every one of 500 steps and the total work grows roughly with the square of the output length, because step 500 alone costs as much as steps 1 through 499 combined did in total. A model answering a long question would visibly get slower with every word it wrote. The KV cache exists so it doesn't.

The analogy: a translator taking notes, not re-reading the transcript

Picture a live interpreter at a long negotiation. A bad interpreter, asked to translate the next sentence, would re-read the entire transcript of everything said so far before opening their mouth — technically correct, but painfully slow, and it gets slower every time someone speaks. A good interpreter keeps a running notepad: as each sentence is spoken, they jot down its key points once, and from then on they only ever glance at the notepad plus the newest sentence, never re-reading the whole transcript. The notepad is the expensive part done once; each new sentence only adds one new line to it.

The KV cache is that notepad. Inside attention, every token gets turned into a key vector (what this token offers to be matched against) and a value vector (what this token actually contributes if matched). Once token $t$'s key and value are computed, they never change — a later token attending back to token $t$ needs the exact same key and value every time. So instead of recomputing them, the model stores them the first time and reuses them forever after.

The mechanism: store once, append, reuse

Without a cache, generating token $t$ requires the keys and values of tokens $1$ through $t$, and all of them are recomputed at every step $t$, giving total work across a sequence of length $T$ proportional to

$$\sum_{t=1}^{T} t = \frac{T(T+1)}{2} \approx \frac{T^2}{2}$$

Here $t$ indexes the generation step, and the sum says step $t$ costs "$t$ units" of key/value computation, so the total across all steps is the sum of $1+2+\cdots+T$, a well-known quadratic total. With a cache, each step computes the key and value for only the one new token and appends them to storage, so the total work is

$$\sum_{t=1}^{T} 1 = T$$

— linear instead of quadratic. In words: the cache turns "recompute everything every time" into "compute one new thing and remember the rest," and the saving compounds because it applies at every one of the $T$ steps.

Worked example 1: counting operations for a 6-token reply

Suppose computing one token's key and value costs 1 "unit" of work, and generating a reply takes 6 steps. Without caching, step 1 costs 1 unit, step 2 costs 2 units (recomputing token 1's key/value plus token 2's), ..., step 6 costs 6 units. Total: $1+2+3+4+5+6=21$ units. With caching, each step costs exactly 1 unit — compute only the new token — for a total of $6$ units. The saving here, $21$ versus $6$, is already more than 3×, and the ratio keeps growing with length: for a 100-token reply the totals are $5{,}050$ versus $100$, a 50× difference.

Worked example 2: the memory cost of remembering

The cache isn't free — it has to store something. Suppose each token's key and value together take up 2 numbers per attention head, there are 32 heads, and the model uses 4 bytes per number. One cached token then costs $2 \times 32 \times 4 = 256$ bytes per layer. A 40-layer model caching a 2,000-token conversation stores $256 \times 40 \times 2{,}000 = 20{,}480{,}000$ bytes, about 20 megabytes, just for that one conversation's cache — and that scales linearly with how many conversations a server holds open at once, which is exactly why "context length" and "concurrent users" trade off against each other in a deployed system.

What this means in practice

Every production language-model server runs incremental decoding with a KV cache; without it, response time would grow noticeably per word, which no chat product could tolerate. The cache is also the reason "context length" is a hard resource constraint rather than just a modeling choice — doubling the context window roughly doubles the memory every open conversation consumes, which is why techniques like multi-query attention (sharing keys and values across heads) and quantizing the cache to lower precision exist purely to shrink this one piece of memory. RoPE positions are what make the cache trick work smoothly across very long contexts, since a cached key's rotation never needs to be redone as new tokens arrive.

Practice

1. If prefill on a 1,000-token prompt costs the same as one un-cached decoding step at position 1,000, roughly how does prefill cost compare to the total cost of decoding 1,000 new tokens without a cache?
2. A server wants to double its context length from 2,000 to 4,000 tokens per user while keeping the same number of concurrent users. Using the memory arithmetic above, what happens to total cache memory required?
3. Why does multi-query attention (many query heads sharing one key/value head) shrink the cache specifically, rather than shrinking the model's overall parameter count?