Generating the 500th word of a reply, a transformer would — naively — re-read all 499 words before it, every single time. The KV cache is the trick that makes chatbots fast: it SAVES each token’s key and value the first time and never recomputes them, so each new word costs a fixed amount instead of a growing one. Slide the length and watch the two costs diverge.
Self-attention at position i needs the keys and values of all earlier positions. WITHOUT a cache, generating n tokens recomputes them each step — total work ~n²/2. WITH the cache, each token’s K and V are computed once and stored; each new step reuses them and adds just ONE, so total work is ~n (linear). A fail-loud self-check throws unless the cached cost grows linearly while the uncached grows quadratically, for the SAME output — identical results, a quadratic-to-linear speed-up.
The cache trades compute for MEMORY — it must hold every past key/value, so long contexts are limited by cache size (hence work on multi-query attention, paged/quantised KV caches). The linear-vs-quadratic op counts are exact.