Why cache keys and values

Avoiding the quadratic cost of recomputing all past tokens at every generation step.

Without a cache, generating each new token requires running the full attention mechanism over every token in the sequence from scratch. That means for step t the model must recompute t key vectors and t value vectors — even though all but the latest were already computed at the previous step. As the sequence grows, each step pays the cost of the whole sequence again, making inference time quadratic in sequence length: O(t²).

The KV cache breaks that pattern by storing each position's key and value vectors the moment they are computed and never recomputing them. At step t, only the new token needs its key and value derived; for every prior position the stored result is read directly. The attention query for the current token can then attend over all cached positions at constant marginal cost per step — O(t) total — turning quadratic growth into linear growth.

The improvement is not just theoretical. Even on a small context window, recomputing from scratch dominates runtime within a handful of generated tokens. Caching is what makes practical generation fast enough to be interactive — the diagram below shows the lane of stored positions, each one a past computation that will never be repeated.

Every cell holds the key and value vectors already computed for that position. The amber cell is the current token; it reads from the cache instead of triggering a full sequence recompute.

Related: Reading occupancy · Correctness · Greedy decoding