What is the KV cache in transformer inference and what problem does it solve?

During autoregressive generation, a decoder produces one token at a time, and each new token attends to all previous tokens. Naively, you'd recompute the key and value vectors for the entire sequence at every step, making generation O(n^2) redundant work. The KV cache stores the key and value tensors already computed for past tokens, so at each step you only compute Q, K, V for the single new token and append its K,V to the cache. This turns per-step attention cost from quadratic to linear in sequence length and is the main reason generation is fast. The tradeoff is memory: the cache grows linearly with context length and batch size (2 * layers * heads * head_dim * tokens), often becoming the dominant memory consumer for long contexts. Techniques like multi-query/grouped-query attention, paged attention (vLLM), and quantized caches reduce its footprint.