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
- The prompt is processed in one pass (prefill), and the keys and values of every layer are saved.
- For each new token, compute only its query, key and value.
- Append its key and value to the cache.
- Attend from the new query to all cached keys, and mix the cached values.
- Without the cache, step n recomputes n tokens' keys and values; with it, just one.
- 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.
- 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
- Prefill (the prompt) is compute-heavy; decode (new tokens) is memory-heavy.
- The cache grows linearly with sequence length and with the number of users in a batch.
- It can use more memory than the model's weights at long contexts.
- Grouped-query attention, cache quantisation and paged attention reduce its cost.
- Time to first token depends on prefill; time per output token depends on decode.
Common mistakes
- Forgetting the cache when estimating how many users a GPU can serve.
- Estimating memory from the parameter count alone.
- Running past the cache's maximum length without a strategy (truncation, sliding window).
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.