Prefix caching: reusing the KV cache across turns and requests

Every turn, an agent sends the server the whole conversation again: system prompt, tool definitions, history, and the new message at the end. Prefilling all of it from scratch is the single biggest waste in agent serving. My fork’s README records a long-context turn taking about 46 seconds to re-prefill, against about 460 ms once the cache is reused. Here’s how the reuse works and what silently breaks it.

Why reuse is possible

In a causal model, the keys and values at position N depend only on tokens 0 to N. So if a new request starts with exactly the same tokens as one the server has already processed, the KV entries for that shared prefix are identical. The server can keep them, find the longest common prefix, and prefill only the tokens after it.

For an agent this is almost everything. Turn 40 shares its first 99% of tokens with turn 39.

What breaks it

Reuse needs the prefix to be token-for-token identical. One changed token invalidates everything after it, so whatever changes early costs the most:

• A timestamp in the system prompt. It changes every request, so nothing after it is ever reused.
• Tool definitions in a different order, or regenerated with different whitespace. The tokens differ, even if the meaning doesn’t.
• History rewritten in place, such as summarising old turns at the top. Every turn after the edit point is recomputed.
• Truncating from the front to fit the context. The whole prefix shifts and reuse drops to zero.

The design rule follows: keep the context append-only, put stable content first and volatile content last.

Within a server and across requests

• llama.cpp’s server reuses the cache for a slot when the new prompt shares a prefix with what that slot last processed (cache_prompt). It can also save and restore slot state to disk (--slot-save-path).
• vLLM’s automatic prefix caching hashes KV blocks by content. Any request whose prefix matches cached blocks shares them, across users, on top of PagedAttention’s block tables (the batching note covers those).
• API providers apply the same principle and bill cached prefix tokens at a discount. The prompt-design rules are identical.

Hybrid models need checkpoints

With a pure transformer, rewinding the cache to a shared prefix just means discarding the entries after it. Hybrid models such as Gated DeltaNet ones also carry a recurrent state, and that state can’t be rewound: the state at position N can’t be recovered from the state at a later position. Reusing a prefix requires a snapshot taken at that position (the hybrid models note explains why).

My fork keeps up to 32 prompt checkpoints of about 149 MiB each, about 4.7 GB in host RAM. Capturing them used to stall prefill, because each capture synchronised the whole context. I made the capture asynchronous through a pinned two-slot staging ring; the fork note has the design.

Rules I use

1. Design prompts for the cache. Stable system prompt and tools first, no timestamps or request IDs near the top, history appended rather than rewritten.
2. Compact at the end, not the beginning. If history must be summarised, do it at clear boundaries and accept one cache miss, rather than rewriting the top every turn.
3. Measure the hit rate. Prompt tokens processed per turn should be a small fraction of prompt tokens sent. If they aren’t, something early in the prompt is changing.
4. Budget host memory for checkpoints on hybrid models, and cap how many you keep.

Sources: the 46 s and 460 ms figures and the checkpoint sizes are from my fork’s README. Server flags are from llama.cpp’s server documentation. Kwon et al., PagedAttention (SOSP 2023), for block-level sharing.