Why does autoregressive generation use a KV cache?
Why does an autoregressive LLM use a KV cache during generation? What specifically is cached, and what would the cost be without it?
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.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
The KV cache is the difference between LLM inference being practical and being a homework problem. Understanding the mechanism is the gateway to understanding every downstream optimization in modern serving stacks, paged attention, GQA / MLA, prefix sharing, KV quantization, speculative decoding.
We'll walk the redundancy without a cache, the exact tensors stored, why Q is excluded, the prefill/decode split, the production memory math, and the consequences that cascade through every serving decision at scale.
The mechanism is simple. The production consequences are vast.
The redundancy without a cache
At decode step t of autoregressive generation, the model needs K and V for positions 1..t to compute attention from the new query at position t. Those K, V depend on past hidden states, which were computed at earlier steps and haven't changed.
A naive implementation projects K and V from scratch every step. The arithmetic of the waste:
- Step 1: compute K, V for 1 token.
- Step 2: compute K, V for 2 tokens (redoing step 1's work).
- Step 3: compute K, V for 3 tokens (redoing steps 1-2's work).
- ...
- Step n: compute K, V for n tokens.
Total: 1 + 2 + ... + n = O(n²) projection operations to produce n tokens. Of those, only n are non-redundant, every other projection is a tensor we already computed and threw away.
The KV cache is just 'don't throw away the work you already did'. It's not a clever algorithm: it's the absence of a stupid one.
At 8k context, naive recomputation does ~67 million redundant projections per generation. With a cache, that drops to 8 thousand. The wall clock difference is the difference between a usable chatbot and an unusable one.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
# 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.vReal products, models, and research that use this idea.
- HuggingFace transformers' generate() returns past_key_values; you pass it in to subsequent calls for incremental decoding.
- vLLM uses paged KV cache allocation to eliminate fragmentation and enable prefix sharing across requests.
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?
Decode appends one new K, V row per step but reads the FULL cache, the read traffic is O(seq_len) per step but the new compute is tiny. Prefill processes the whole prompt at once: every position's full attention/FFN math, dense matmuls: compute dominates. Different bottlenecks → different optimizations.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
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.
60 second bullets to scan on the way to the call.
The redundancy: K, V for past tokens don't change but get recomputed naively
Exactly what's cached: K and V per (layer, head, position)
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.