KV cache: how inference keeps attention fast

Table of Contents

Generating text one token at a time would be slow if every step recomputed attention over the entire history from scratch. The key-value (KV) cache is the optimisation that makes autoregressive inference tractable.

The problem

Scaled dot-product attention computes, for each query token:

$$ \text{Attention}(Q, K, V) = \text{softmax}!\left(\frac{Q K^\top}{\sqrt{d_k}}\right) V $$

During generation, the keys and values for past tokens don’t change — only the new query arrives. Recomputing them every step is $O(n^2)$ work that’s largely redundant.

The cache

The fix: store the projected $K$ and $V$ for all previous tokens and append only the new token’s contributions.

Step t:   cache holds K_{1..t-1}, V_{1..t-1}
          new token -> q_t, k_t, v_t
          append -> K_{1..t}, V_{1..t}
          attend q_t against the full cached K, V

This turns each generation step into $O(n)$ work instead of $O(n^2)$ — a big win for long contexts.

The cache trades memory for compute. Its footprint grows with sequence length, number of layers, and number of heads: roughly $2 \cdot L \cdot n \cdot d_{\text{model}}$ floats. That’s why long-context and large models strain GPU memory.

Why it matters

Understanding the KV cache is the foundation for most modern inference tricks — multi-query attention, grouped-query attention, PagedAttention, and quantised caches all manipulate this same structure to push the memory/compute trade-off further.