Why does autoregressive generation use a KV cache?

Short answer·Medium·4.0 · 0·~3 min·Relevant atAnthropic NVIDIA

Attempt it

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

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).

Memory aid

Easy to grasp

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.

Key concepts

KV cache Autoregressive decoding

Detailed answer & concept explanation

~6 min read

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.

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.

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.
llama.cpp supports KV cache quantization (Q8, Q4) to fit longer contexts in limited VRAM.
Anthropic'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?

QHow does prefix sharing reduce KV cache memory in production?

QWhat changes about the cache in speculative decoding?

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.

60-second cheat sheet

The night-before-the-interview bullets. Scan these on the way to the call.

References

Primary sources. Skim if you want the original framing.