KV cache and the cost of generation

The KV cache stores the keys and values of every token already processed. Generating a new token then computes only that token's keys and values, instead of recomputing them for the whole sequence.

Why it matters

Each new token attends to all earlier tokens. Recomputing every earlier key and value at every step makes generation cost grow with the square of the length, which is far too slow for long replies.

The cache makes each step cheap, but its memory grows with every token, layer and user. It often limits how many users a GPU can serve, and how long a context can be.

The idea

When generating, each new token needs the keys and values of all earlier tokens. Instead of recomputing them at every step, we store them. This is the KV cache. It is much faster, but it uses a lot of memory.

Taking notes during a long meeting, instead of replaying the whole recording each time someone speaks.

Meeting notes are small. The KV cache grows with every token, every layer and every user, and it can use more memory than the model itself.

How it works

  1. The prompt is processed in one pass (prefill), and the keys and values of every layer are saved.
  2. For each new token, compute only its query, key and value.
  3. Append its key and value to the cache.
  4. Attend from the new query to all cached keys, and mix the cached values.
  5. Without the cache, step n recomputes n tokens' keys and values; with it, just one.
  6. Memory ≈ 2 (K and V) × layers × tokens × d_model × bytes per number, per sequence. With 32 layers, d_model 4,096, 4,096 tokens and bf16 (2 bytes): about 2.1 GB.
  7. Grouped-query or multi-query attention shares keys and values across heads to shrink this; paged attention (vLLM) manages the cache like virtual memory.

Key points

Common mistakes

Not true: The KV cache changes the model's answers a little, in exchange for speed.
In fact: The cache stores exactly what would otherwise be recomputed, so the output is identical. It trades memory for time, not quality.

Not true: The memory needed to serve a model can be worked out from its parameter count alone.
In fact: The KV cache grows with every token and every user, and at long contexts it can take more memory than the weights. Count it when planning capacity.

Part of Unit 4: Transformers and LLMs in the free ML Foundations course.