Why it matters
Autoregressive decoding needs the keys and values of every previous token at every layer, and recomputing them for each new token would repeat work proportional to the sequence length. Caching them makes each step cheap but creates a pool that must be divided among concurrent requests, shared where prefixes match and reclaimed when a client disappears. Most serving incidents that look like compute problems are really cache-accounting problems.
Mental model
The cache is a tab kept open on every conversation: each turn adds a page, and the desk only holds so many pages. The analogy breaks because two conversations with the same opening can share the first pages, which a paper desk cannot do without copying.
How it works
Step · 1 of 10
A arrives: prefix and own blocks
A's four-token system prompt fills P0–P3 by reference. A's first four answer positions fill A4–A7. The pool shows eight of twenty-four blocks live; nothing has been shared or evicted yet.
Next: B shares the same prefix
- Allocated blocks
- 8
- Evictions
- 0
- Recomputed blocks
- 0
- Leaked blocks
- 0
- Prefix refs
- 1
Figure. Twenty-four fixed-size blocks, four token positions each, for one illustrative layer. Prefix blocks are shared by reference; a sequence's own blocks are private. The last steps show eviction thrash (two long sequences evicting each other) and an abandoned session whose blocks are not released. All counts are synthetic.
What to notice. Sharing is the cheap part and eviction is the expensive part. From step 6 the pool is full, so every admission evicts a live sequence and the recomputed-block counter climbs while utilisation stays at 100% — throughput falls although the cache looks busy. Step 9 separates a leak (blocks held by a departed request) from the idle sweep that recovers them. The sweep fixes the accounting, not the work already recomputed. The prefix blocks are retained because D, E and G still reference them; the final 22 are 18 request blocks plus 4 shared prefix blocks, not a leak.
Text version
A 24-slot block pool. Step 1: A's four prefix blocks P0–P3 and four own blocks A4–A7 are live, 8 of 24. Step 2: B shares P0–P3 and adds B4–B7, 12 live. Step 3: B leaves, 8 live. Step 4: C adds six blocks, 14 live. Step 5: D adds eight, 22 live, two free. Step 6: E needs six; A's four private blocks are evicted and E takes those slots plus the last two, 24 live, four evictions and four recomputed blocks. Step 7: A returns and evicts D's last four, eight evictions and eight recomputed. Step 8: D returns and evicts A's four, twelve evictions and eight recomputed — the thrash; A's next turn would recompute another four, which has not happened in this window. Step 9: C disconnects but its six blocks remain, marked leak, so the pool stays full with two active requests. Step 10: an idle sweep releases C and G takes four blocks, leaving 22 live, no leak. Counters show allocated blocks 8, 12, 8, 14, 22, 24, 24, 24, 24, 22; evictions 0 until step 6 then 4, 8, 12; recomputed blocks 0 until step 7 then 4 and 8; leaked blocks 6 at step 9 and 0 after the sweep. The prefix reference count is 1, 2, 1, 2, 3, 3, 4, then 3 from step 8 onward.
- Size the pool from cache bytes per token, the maximum context you allow and the concurrency you intend to serve.
- Allocate in fixed-size blocks rather than per-request contiguous buffers, so free memory stays usable.
- Hash the token prefix and reuse blocks when a new request shares it, keyed by model revision and adapter set.
- Choose an eviction or preemption policy and make it visible: least recently used, lowest priority, or recompute on demand.
- Release blocks on client disconnect, cancellation and idle timeout, and assert the pool returns to its baseline.
- Track the prefix reuse rate and the number of recomputed tokens, since both are direct cost signals.
Trade-offs
| Choice | Good for | Cost | Fails when |
|---|---|---|---|
| Prefix sharing | Large savings on repeated system prompts | Hash computation and reference counting | Prompts differ from the first token |
| Recompute on eviction | Simple, no swap storage | Extra prefill work for the evicted sequence | Prompts are long and eviction is frequent |
| Swap to host memory | Preserves progress under pressure | Transfer latency inside the request | Inter-token latency is tightly bounded |
| Long idle timeout | Resumes conversations cheaply | Memory held by users who left | Concurrency is the constraint |
Good for
Large savings on repeated system prompts
Cost
Hash computation and reference counting
Fails when
Prompts differ from the first token
- Prompts differ from the first token
- Prompts are long and eviction is frequent
- Inter-token latency is tightly bounded
- Concurrency is the constraint
Figure. Each choice with what it buys, what it costs, and the case where it loses.
What to notice. The fourth column is the decision: if the losing case describes your situation, the choice is wrong.
Text version
Four trade-offs: Prefix sharing is good for Large savings on repeated system prompts, costs Hash computation and reference counting, and fails when Prompts differ from the first token. Recompute on eviction is good for Simple, no swap storage, costs Extra prefill work for the evicted sequence, and fails when Prompts are long and eviction is frequent. Swap to host memory is good for Preserves progress under pressure, costs Transfer latency inside the request, and fails when Inter-token latency is tightly bounded. Long idle timeout is good for Resumes conversations cheaply, costs Memory held by users who left, and fails when Concurrency is the constraint
Failure modes
- Prefix miss from unstable prompts. A timestamp or request id at the top of the prompt defeats sharing and the reuse rate collapses. Debug: log the shared prefix length per request and look for values near zero.
- Leaked sessions. Closed connections never release blocks and the pool drains over hours. Debug: compare allocated blocks with active request count and check for growth at idle.
- Eviction thrash. Two long sequences evict each other repeatedly and throughput falls while utilisation looks normal. Debug: count recomputed prompt tokens per request against cache pressure.
In production
Export cache utilisation, prefix reuse rate, eviction count and recomputed tokens. Alert on utilisation sustained near the ceiling, and cap context per request so a single large prompt cannot consume the pool.
Common misconceptions
People think: The cache is an optimisation you can add later.
Actually: It is part of the serving contract: capacity, concurrency and cost all derive from how it is managed.
People think: Caching the state changes the model's answers.
Actually: Reusing keys and values for an identical prefix is arithmetically equivalent; what changes is memory and latency, not the distribution.
Interview angle
Describe what the cache holds, how its size scales, and how sharing and eviction interact with admission. A strong answer names the accounting failure that produces an incident and the metric that exposes it. Weak answers call it a speed optimisation and skip memory.
Sources
- Kwon et al., PagedAttention and vLLM — block-based cache allocation and prefix sharing.
- Hugging Face, KV cache — what the cache stores and how it is reused.
- vLLM documentation — prefix caching and preemption in a production engine.