Prefix & Prompt Caching

Speculative decoding made each decode step cheaper. Prefix caching does something even more direct: it skips work entirely. Recall that the KV cache for a prompt is produced during prefill, and prefill cost scales with the number of prompt tokens. Now notice how much prompt is identical across requests in any real application — the same system prompt, the same few-shot examples, the same retrieved document, request after request. Recomputing that shared KV every time is pure waste. The throughline answer here is the bluntest in the part: the cheapest token is the one you never compute, so cache the shared prefix’s KV and reuse it.

Why prefixes repeat

Transformers are causal: a token’s key and value vectors depend only on the tokens before it, never after. So if two requests begin with the exact same sequence of tokens, the KV cache for that shared span is bit-for-bit identical — the suffix the two requests differ in cannot retroactively change it. That is the structural fact prefix caching exploits.

Shared prefixes are everywhere:

Request 1:  [ 2,000-token system prompt + few-shot block ] + "Summarize doc A"
Request 2:  [ 2,000-token system prompt + few-shot block ] + "Translate doc B"
Request 3:  [ 2,000-token system prompt + few-shot block ] + "Extract dates"
            └──────────── identical prefix ─────────────┘   └─ unique suffix ─┘

Without caching, each request prefills all 2,000 shared tokens plus its suffix. The shared work is done over and over.

The fix: cache the prefix KV, reuse it

Compute the prefix’s KV once, keep it resident, and when a new request arrives with a matching prefix, load that KV instead of recomputing it. The request then only prefills its short unique suffix before decoding. This rides directly on the PagedAttention block layout: the prefix occupies a set of physical KV blocks, and every matching request simply points its block table at those same blocks — the copy-on-write sharing from that page, now reused across different requests rather than parallel samples of one.

Worked example: the savings

Take Llama-2-13B (~0.78 MB of KV per token) with a 2,000-token shared system prompt, serving 1,000 requests that share it. Say the model prefills at ~10,000 tokens/sec for this configuration.

Time-to-first-token (TTFT):

Uncached: prefill 2,000 shared + (say) 50 suffix tokens
          ≈ 2,050 / 10,000  ≈ 205 ms before the first output token

Cached:   prefill only the 50 suffix tokens
          ≈ 50 / 10,000     ≈ 5 ms

TTFT improvement ≈ 200 ms per request — a ~40× faster first token

Aggregate compute saved. Prefill costs roughly 2 × params FLOPs per token, so each cached token saves ~2 × 13e9 = 26 GFLOPs:

Saved per request ≈ 2,000 tokens × 26 GFLOP = 52 TFLOP
Across 1,000 requests ≈ 52 PFLOP of prefill never executed

That is compute you do not run, GPU-seconds you do not buy, and — on a metered API — tokens you may not be billed full price for. Latency and dollars both fall, from one idea.

The cost you pay: the prefix KV must stay resident. 2,000 tokens × 0.78 MB ≈ 1.56 GB of HBM held for the cached prefix. That is the trade — memory for compute — and it is almost always worth it when the prefix is hot, because that 1.56 GB serves all 1,000 requests instead of being recomputed 1,000 times.

Automatic prefix caching & RadixAttention

You do not have to mark prefixes by hand. Automatic prefix caching (vLLM) hashes KV blocks and reuses any whose token content matches. RadixAttention (SGLang) stores cached prefixes in a radix tree, so requests sharing a partial prefix — e.g. the same system prompt but different few-shot tails — automatically share the longest common span. Both turn “did anyone compute this prefix already?” into a fast lookup.

Conditions and limits

Prefix caching is powerful but exact:

• Exact, token-level prefix match. The shared span must be identical tokens from position 0. A single different leading token (a changed date, a per-user name before the system prompt) breaks the match. Put the stable, shared content first and the variable content last to maximize cache hits.
• Eviction. Cached prefixes consume HBM that could hold active requests’ KV. Engines evict cold prefixes (typically LRU) when memory is tight, so a rarely used prefix may be gone by the next hit. Hot prefixes — your main system prompt — stay resident and pay off enormously.
• Read-only correctness. Because causality guarantees the prefix KV is independent of the suffix, reuse is exact, not approximate. No quality is lost.

The server-side cousin of API prompt caching

This is the same idea that surfaces as prompt caching in the Claude API, which the capstone uses: you mark a large stable prefix once and pay a reduced rate to reuse it on later calls. Server-side prefix caching is the engine-level mechanism; API prompt caching is that mechanism exposed as a billing-and-latency feature you control without owning a GPU. See application-layer caching strategies and the capstone’s prompt-caching lever, where we measure the bill it saves on a real app.

Under the hood — how a cache lookup proves an exact prefix match

“Reuse any block whose token content matches” hides a correctness puzzle: a single KV block (say 16 tokens) at position 200 is only safe to reuse if every one of the 200 preceding tokens was also identical — otherwise its keys and values were computed in a different context. Comparing the whole prefix on every request would be slow. vLLM’s automatic prefix caching solves it with a hash chain: each block’s identifier is a hash of the token IDs inside it combined with the identifier of the block before it.

  block_hash(i) = hash( tokens_in_block(i), block_hash(i-1) )

Because each hash folds in its predecessor, two requests’ blocks collide only if their entire prefix up to that point is token-for-token identical — so a single hash comparison stands in for comparing the whole history. A match is a guarantee, not a guess, which is what keeps reuse exact and lossless. It is the same chained-hashing trick a Merkle tree or a blockchain uses, applied to KV blocks.

The architect’s lens

Prefix caching is the bluntest cost cut in the part — don’t compute the token at all. The five questions:

• Why does it exist? Because transformers are causal, a shared leading span’s KV is bit-for-bit identical across requests — so recomputing the same system prompt, few-shot block, or document on every request is pure waste.
• What problem does it solve? Redundant prefill: cache the prefix KV once and matching requests point their block table at it, prefilling only their unique suffix. In the worked example TTFT drops from ~205 ms to ~5 ms (~40×) and ~52 PFLOP of prefill across 1,000 requests never runs.
• What are the trade-offs? Memory for compute — the prefix KV must stay resident (~1.56 GB for 2,000 tokens) — and the match must be exact, token-level from position 0, so cold prefixes get LRU-evicted under memory pressure.
• When should I avoid it? When prefixes don’t actually repeat, or when variable content (a per-user name, a date) sits before the shared span and breaks the match — put stable content first; tiny or rarely-hit prefixes barely pay for the resident memory.
• What breaks if I remove it? Every request re-prefills the whole shared span — TTFT climbs back ~40× and aggregate prefill FLOPs balloon — and the Claude API’s prompt-caching lever loses the engine-level mechanism it exposes.

Check your understanding

1. What property of transformers guarantees that a shared prefix’s KV cache is identical across two requests?
2. How does prefix caching reduce TTFT, and what does a request still have to prefill?
3. For a 2,000-token shared prompt at ~0.78 MB/token, how much HBM must stay resident, and what is being traded for what?
4. Why should you place stable, shared content at the start of a prompt and variable content at the end?
5. What do automatic prefix caching and RadixAttention add on top of manual prefix reuse, and how does this relate to the Claude API’s prompt caching?

Show answers

1. Causality: a token’s key and value depend only on preceding tokens, never on what comes after. So an identical leading token sequence yields bit-for-bit identical KV regardless of how the requests later differ.
2. It loads the shared prefix’s already-computed KV instead of recomputing it, so the request skips prefilling the shared span and only prefills its short unique suffix — cutting TTFT to roughly the suffix’s prefill time.
3. 2,000 × 0.78 MB ≈ 1.56 GB of HBM held resident for the cached prefix. It trades memory (keeping that KV) for compute (not re-running prefill), which pays off whenever the prefix is reused across many requests.
4. Because the cache requires an exact token-level match from position 0; any variation in the leading tokens breaks the prefix match. Keeping shared content first and variable content last maximizes the length of the matching (cacheable) prefix and thus the hit rate.
5. They make reuse automatic: vLLM hashes KV blocks to reuse matching ones, and SGLang’s RadixAttention stores prefixes in a radix tree so requests sharing a partial prefix automatically share the longest common span. This is the engine-level mechanism that the Claude API exposes to developers as “prompt caching” — a billing/latency feature usable without owning a GPU.