A transformer generates one token at a time. Naively, each new token re-runs attention over the whole sequence from scratch — O(n²) work every step, O(n³) to finish. But the causal mask guarantees a past token never attends forward, so its key and value never change. Store them once. Now each step attends over a cache in O(n), and the whole run costs O(n²). This page runs both paths side by side and proves, bit-for-bit, that they emit the identical sequence — while the op-counter shows the cost collapse.
source Vaswani, Shazeer, Parmar, et al., Attention Is All You Need (2017) — arxiv.org/abs/1706.03762. The causal self-attention is theirs; the KV-cache is the inference optimization it makes exact. Rendered, not quoted.
Single-head causal attention. Each token xi projects to a query, key and value: qi=xiWQ, ki=xiWK, vi=xiWV.
The output at position t is softmax(qt·ki/√d) weighting vi over i ≤ t only (causal). Because i ≤ t never looks forward, ki, vi depend on xi alone — appending a later token cannot change them.
So they are memoizable. Cached: 1 new projection + t+1 dot-products per step → O(n)/step, O(n²) total. Recompute-from-scratch: re-project all t+1 and rebuild the whole matrix → O(n²)/step, O(n³) total. Exact closed forms, checked on load.
The cache is not a trick you may or may not get away with — it is licensed by one upstream fact. the-causal-mask makes every past token blind to the future, so its K,V are frozen the instant that token exists. Memoizing frozen values is always exact.
That is how the-attention is made fast for generation. Each sphere is the next one's premise: mask ⟶ frozen past ⟶ cache.
AMBER The cache is engineering folklore built on the 2017 paper, not a named result in it; the weights here are a fixed-seed toy, not trained. The invariant proven — frozen K,V ⇒ identical output — is exact and model-independent.
The blue team's live check: for the current length, run both paths and confirm the cached output equals the recompute ground truth to ≤1e-12, that cached K,V are invariant, and that the op counts hit their closed forms. If red drops a cache entry, this badge is where it shows.
A tiny model: dimension d=4, vocabulary V=6, fixed-seed projections WQ, WK, WV. Generation starts from a one-token prompt and picks each next token as the nearest embedding to the attention output — fully deterministic, no training, no randomness at decode.
prompt fed in: t0 = 2
The prompt goes in; the engine below extends it token by token down both paths. What flows out the bottom is the generated sequence plus the proven op counts.
the growing cache — one (K,V) per token, frozen once written:
QK dot-products · recompute does —× the work
per-step QK ops — cached grows linearly, recompute quadratically:
| n | cached O(n) | recompute O(n²) | out ≡ |
|---|
generated sequence (identical from both paths):
Change n — both paths re-run live from the four rules of attention, never looked up. The cache is exact: same tokens, a third of the arithmetic.
What the machine produces, proven: the cached path and the recompute-from-scratch path emit the bit-for-bit identical token sequence, while the cache cuts total attention cost from O(n³) to O(n²) — and per-step from O(n²) to O(n). Same answer, cheaper.
The blue team's witness (left) confirms the identity and counts live; the red team (right) drops a cache entry to break it.
This is why the field grew MQA/GQA (share K,V across heads), sliding-window and paged attention (PagedAttention) — every one of them is a fight against the cache's memory, not its compute. The cache is a correctness-preserving optimization with a cost that scales, not a free lunch.
"The KV cache makes attention O(n)." Cut. Per decode step attention is O(n) over the cache; the total to decode n tokens is O(n²). The cache turns the naive O(n³) into O(n²) — it does not make attention sub-linear.
"The cache is free." Cut. It costs 2·n·d·layers of memory that grows with the sequence and often dominates — the reason paging and window-attention exist.
"Cache the queries too." Cut. Only K and V are reused across steps. Each step's query is new and used once; caching Q buys nothing.
The red team's move: drop one entry from the cache, so the new token attends over a hole in its past. The cached output no longer matches the recompute ground truth. The blue team's witness (window 7) is watching.
Drop a cached (K,V) and the attention over the past is wrong — the cached sequence diverges from the from-scratch path, the identity check fails, and the witness turns red. Nothing is faked; the attack is real and it is caught.