Why does an autoregressive LLM use a KV cache during generation? What specifically is cached, and what would the cost be without it?
Free · 2 AI evals / day
Autoregressive generation means producing one token at a time. To produce token `t+1`, the model runs a full forward pass over tokens `1..t`, with attention reading from every past position.
Vocabulary anchor: **K** (keys) and **V** (values) are linear projections of past hidden states, `K_i = x_i W_K`, `V_i = x_i W_V`. They're what attention reads from. **Q** (query) is what attention reads with.
Here's the redundancy: `K_i` and `V_i` depend only on the hidden state at position i, which was already computed at step i and doesn't change at step t. Re-projecting them at every step is pure waste: you'd get the same tensors. Naively, this costs `O(n²)` total projection work across an n-token generation.
The **KV cache** is a tensor that stores K and V at every layer and head for every position seen so far. Each new step: compute Q, K, V only for the new token, append the new K, V, then attend with the new Q against the full cached K, V. Q isn't cached because past Qs are never re-read, each token's Q is used once, at its own step.
The KV cache is the optimization that turns autoregressive decoding from O(n²) projection work into O(n).
Each generation step needs K and V for every past token to compute attention. But those depend only on past hidden states, which don't change after they're first computed. Re-projecting them every step is `O(n²)` waste over a full generation.
The **KV cache** stores K and V for every `(layer, head, position)` of prompt plus generated tokens. Per step: compute Q, K, V only for the new token, append the new K, V to the cache, run attention with the new Q against the full cached K, V.
Q isn't cached because past Qs are never re-read, each Q participates only in its own step's attention output. K and V are read by every subsequent query, so they must persist.
With cache: `O(n)` projection work total for n tokens. Without: `O(n²)`. That's the difference between practical generation and a system that gets slower with every token.
Quick reference
TL;DR
Without a cache, each step re-projects K and V for every past token, O(n²) wasted work. The cache stores K and V (not Q) per layer/head and reuses them, cutting per-step projection cost to O(1).
Think of cooking dinner one course at a time. Each new course uses ingredients you already chopped earlier, the onions are diced, the garlic is minced, the herbs are ready on the counter. Without a KV cache, you re-chop every ingredient from scratch for every new course, even though they're sitting right there ready to use. With a cache, you keep the pre-chopped pile on the counter and just add the one new thing for the current course. Same dinner, none of the wasted prep.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Very short sequences (single turn classification, <64 tokens total) The fixed bookkeeping cost of allocating, indexing, and reading a KV cache exceeds the savings on a handful of tokens. A vanilla full attention forward pass is simpler and not measurably slower.
Stateless streaming inference where no past context is retained If each request is independent and short (audio chunk transcription, embedding generation), there's no past to cache. Cache management overhead is pure deadweight.
Encoder-only architectures (BERT, embedding models) No autoregressive decode loop, the encoder runs once and produces all outputs in parallel. KV caching is meaningless because there are no incremental decode steps to amortize across.
Severely memory constrained deployment with very long context At 128k+ context the KV cache can exceed weight memory and force HBM offload, blowing tail latency. Recompute on demand with sliding window attention or KV cache quantization (Q8/Q4) may be necessary tradeoffs.
Quick scan · 2–4 min
Everything important, quickly.
Walk the causal attention asymmetry (Q reader vs K/V read target), the prefill/decode split, the exact cache shape and memory footprint, and the cascade of production optimizations (MHA→GQA→MLA, paged allocation, prefix sharing, quantization, spec decoding).
Code example
python
# Decode loop with KV cache (conceptual)
def generate(prompt_ids, model, max_new_tokens):
# Prefill: process whole prompt in one pass, get initial cache
logits, cache = model.forward(prompt_ids, cache=None)
next_token = sample(logits[:, -1])
out = [next_token]
# Decode: one token at a time, reuse and grow cache
for _ in range(max_new_tokens - 1):
logits, cache = model.forward(next_token[:, None], cache=cache)
next_token = sample(logits[:, -1])
out.append(next_token)
if next_token == eos: break
return out
# Inside model.forward at decode step:
# q_new, k_new, v_new = project(x_new)
# cache.append(k_new, v_new) # only K and V: no Q!
# attn = softmax(q_new @ cache.k.T / sqrt(d)) @ cache.v
Real-world examples
Real products, models, and research that use this idea.
1HuggingFace transformers' generate() returns past_key_values; you pass it in to subsequent calls for incremental decoding.
2vLLM uses paged KV cache allocation to eliminate fragmentation and enable prefix sharing across requests.
3llama.cpp supports KV cache quantization (Q8, Q4) to fit longer contexts in limited VRAM.
4Anthropic's prompt caching billing reflects KV cache reuse across requests that share a prefix.
Interviewer follow-ups
What an interviewer would ask next. Try answering before peeking at the approach.
QWhy is decode often memory bandwidth bound while prefill is compute bound?
Sign in or go Pro to see the approach for this follow-up.
QHow does prefix sharing reduce KV cache memory in production?
Sign in or go Pro to see the approach for this follow-up.
QWhat changes about the cache in speculative decoding?
Sign in or go Pro to see the approach for this follow-up.
Don't say this
Red flags and common mistakes that signal junior thinking. Click to expand.
Most common mistake
Confusing the prefill phase (compute K, V for the whole prompt at once) with the decode phase (append one K, V row per step), or thinking the cache stores Q, attention weights, or outputs.