Day 98: KV cache: why generation speeds up after the first token
The optimization that makes generation practical
Generating token by token, a naive implementation recomputes attention over the entire sequence for every new token — quadratic waste. The KV cache fixes this: since previous tokens' Keys and Values don't change as you generate, cache them. Each new token computes its query, attends against the cached K/V, and appends its own K/V to the cache. This is why LLM generation has a slow first token (prefill) then fast subsequent ones.
This is where Stage 6A vocabulary begins
The KV cache grows with sequence length and consumes real GPU memory — managing it efficiently is exactly what vLLM's paged attention (Day 105, and Stage 6A) exists to do. Understanding the KV cache now means 'paged attention' later is a memory-management refinement of a concept you already grasp, not a new mystery.
Key terms
- KV cache
- Cached Key and Value vectors of previous tokens, reused during generation so attention need not recompute them each step.
- Prefill
- The initial pass computing K/V for the whole prompt — the slow first step before fast per-token generation.
- Decode step
- Generating one new token by attending its query against the cached K/V and appending its own.
Why does the KV cache speed up autoregressive generation?
