The attention matrix, built one token at a time — and the redundant work that makes caching keys and values unavoidable.
Scroll to beginFour tokens, four queries. Each row is a query asking "what should I pay attention to?", each column is a key answering "here is what I contain". The matrix is triangular because attention is causal: token 3 can look back at token 0, but token 0 can never see the future.
Take a single score, s₂₀. Computing it needs three vectors: the query q₂ from the token doing the looking, and the key k₀ and value v₀ from the token being looked at. Each one is a matrix multiply against the model weights — real work. Notice the keys sit above their column and the values below it, because every cell in a column draws on the same pair.
Generation starts with one token. One query, one key, one value, one score. Everything here is genuinely new, so there is nothing yet to save. Watch what the key and value strips do as the next tokens arrive.
Now the loop runs. Each step appends a token and computes a new row — but the model is stateless, so it rebuilds every key and value from scratch every time. By step 4 you are computing k₀ and v₀ for the fourth time, from a token that has not changed since step 1. The highlighted strips are the work being redone.
Select any key or value to trace the column that uses it.
Each vector carries how many times it was rebuilt: k₀ four times, k₁ three, k₂ twice, k₃ once. Ten key/value pairs to represent four tokens — the cost grows as n(n+1)/2 while the information grows as n. At a thousand tokens that is 500,500 projections to describe 1,000 tokens.
Nothing about k₀ depends on later tokens, so it never needs recomputing. Cache each key and value the first time it appears and a generation step collapses to one new query, one new key, one new value, one new row. Quadratic work becomes linear — paid for in memory, which is why KV cache size, not arithmetic, is what limits how many requests a server can hold at once.