Why Recompute Would Kill You

Lesson 1 of 4 in The KV Cache.

In the Decode phase, the model emits one Token per step, and each step’s Attention needs the key and value vectors of every token that came before. Now imagine serving without any cache: to generate token 1,001 you would re-run the forward pass over all 1,000 earlier positions just to rebuild those keys and values, use them once, and throw them away. Token 1,002 rebuilds 1,001 positions. Every step re-buys everything the previous step already paid for. Add it up and the bill is quadratic: emitting token t costs t positions of work, so generating n tokens from scratch costs roughly n²/2 position-computations in total. At chat lengths that is not a rounding error — it is the difference between a response in seconds and one in minutes. The escape hatch is a property of Causal masking: a token can only attend backwards, so once token 7’s key and value are computed, they never change — token 9 arriving later cannot alter them. Anything that never changes can be computed once and stored. That store is the KV cache: the key and value vectors of every context token, at every layer, kept in GPU memory for the lifetime of the request.

Log-log line chart comparing two curves as tokens generated grows from 16 to 4,096. The upper curve, labeled without cache, follows n times (n plus 1) over 2 and reaches about 8.4 million cumulative positions processed at 4,096 tokens. The lower curve, labeled with cache, is the identity line and reaches 4,096. The gap between the curves widens steadily, showing quadratic versus linear total work.

Cumulative attention positions processed while generating n tokens, with and without a KV cache. Without a cache, emitting token t re-encodes all t earlier positions, so the total after n tokens is n(n+1)/2; with a cache each step processes only the one new token, so the total is n. Both curves plot those formulas exactly: at n = 4,096 they read 8,390,656 versus 4,096 — a factor of about 2,048. (calculated — source: Counting argument from the causal attention definition — Vaswani et al. (2017), arXiv:1706.03762)

Notice what is not cached: queries. A token’s query is used exactly once — at the step where that token looks back at the others — and never again. Keys and values are what every future token will need, so they are what get stored. Prefill builds the cache for the whole prompt in one parallel pass; decode then appends one key and one value per layer per new token, and reads the rest from memory.

Interactive checkpoint quiz (2 questions) — open this page in a browser to take it.