54 Prefix Caching → CacheBlend
Context
Prefill — processing the whole input context up to the first generated token — is the most expensive part of inference on long inputs (attention is O(n²)). And the same text goes through prefill again and again: one shared system prompt across thousands of requests, the same history on every turn of a dialogue, the same documents in RAG. Recomputing their KV every time is wasteful.
The idea and the mechanism
Prefix caching. Under causal attention a token's KV depends only on itself and the tokens before it — so for requests that share a PREFIX, the KV of that prefix is bit-for-bit identical. vLLM cuts the sequence into blocks and hashes each one in a chain (hash = the block's tokens + the hash of everything before it); if the hash matches, the ready-made KV block is reused and its prefill skipped, leaving only the uncached tail to compute. The production labs sell exactly the same thing as prompt caching (cached input is cheaper).
CacheBlend. In RAG the reusable pieces are NOT a shared prefix: documents arrive in different orders and combinations. A chunk's KV computed in isolation has not seen the other chunks (no cross-attention) and sits at the wrong position — naive concatenation drops quality. CacheBlend reuses such KV anyway, but recomputes the KV of a small fraction of tokens with the largest deviation (HKVD — high KV-deviation), restoring the stitching. The recompute is pipelined with loading the KV from storage → the cache can live on slow, large storage without adding latency.
linear algebra · systems Why a prefix is exactly reusable, and what CacheBlend recomputes
1. The prefix. The keys and values at position i are functions of the hidden state hi, and under a causal mask that depends only on tokens ≤ i:
If two requests share the prefix x1..k, then their h1..k coincide → K1..k, V1..k are identical. They can be computed once. For a prefix of length k reused across R requests, the prefill saved is ≈ (R−1)·k tokens.
2. Non-prefix (CacheBlend). Let i be the cache computed for a chunk in isolation, and KV*i what a full prefill of the whole concatenation would have given. The deviation:
The key observation: Δ is SPARSE — for most tokens the surrounding context barely changes the KV, and only a few diverge badly (at the joins between chunks). Recompute those HKVD tokens at every layer and you fix the dominant error before it spreads. The fraction r is the trade-off knob: higher → closer to a full prefill, and more expensive. Empirically a small fraction is enough to keep quality intact, and the recompute itself is hidden behind loading the cache.
Python Reusing KV: prefix by hash + CacheBlend stitching
# 1) PREFIX CACHING: chained block hashes → reuse the shared prefix
def block_hash(prev_hash, tokens): # hash = (history + block tokens)
return hash((prev_hash, tuple(tokens)))
def reuse_prefix(req_blocks, cache): # cache: hash -> physical KV block
h, reused = None, 0
for blk in req_blocks:
h = block_hash(h, blk.tokens)
if h in cache:
blk.kv = cache[h]; reused += 1 # hash matched → skip prefill
else:
break # the prefix diverges from here on
return reused # prefill only for the uncached tail
# 2) CACHEBLEND: reuse the KV of any chunks, a small fraction of tokens stitches them
def cacheblend(chunks_kv, model, r=0.15):
kv = concat(chunks_kv) # chunk KV, computed separately
dev = kv_deviation(kv, model) # Δ: deviation from a full prefill
idx = topk(dev, int(r * len(dev))) # HKVD — the most divergent tokens
recompute(kv, idx, model) # recompute only those (layer by layer)
return kv # ~full-prefill quality for a fraction of the computeWhy it matters
Reusing prefill is one of the biggest levers on the cost and latency of LLMs in production. Prefix caching is everywhere already: vLLM, TGI, the commercial prompt-caching APIs (cached input is several times cheaper). CacheBlend lifts the "prefix only" restriction, opening up cheap RAG and modular context assembly ("You Only Prefill Once"). It is the same thought as in vLLM (#49) and MLA from DeepSeek (#53): the KV cache is the bottleneck of inference, and the whole fight is about computing, storing and moving as little of it as possible.
Connections
Prefix caching is built on the block KV cache from #49: the same physical blocks, only now addressed by the hash of their contents and shared between requests (not just within one). CacheBlend is the next step along the same line: reuse blocks even when they are not a shared prefix.
The KV cache exists at all because of causal self-attention: a token's KV depends only on itself and what came before. That is precisely why the KV of a shared prefix is bit-for-bit identical and reusable — a direct consequence of the architecture in #32, not a separate trick.
Two lines of attack on one bottleneck. MLA compresses the KV WITHIN a request (architecturally, via a low-rank latent); prefix caching / CacheBlend reuse KV ACROSS requests (at the systems level). They compose: less KV per request × computing it less often = cheap long context.
Questions worth asking
If the KV of a prefix is exactly reusable, why can't you take any chunk of text the same way?
Only a TRUE prefix is exactly reusable — it alone has the same preceding context. The KV of any interior chunk, computed in isolation, (a) sits at the wrong position and (b) has not seen the chunks before it — there is no cross-attention. Concatenate such KV naively and the model "fails to connect" the chunks; quality drops. That is exactly the hole CacheBlend plugs, by selectively recomputing a small fraction of tokens.
Why is recomputing ~15% of the tokens enough — doesn't the error pile up across layers?
Because KV deviation is SPARSE: for most tokens the real context barely changes the KV, and only a few diverge badly (at chunk boundaries, at special positions). Recompute those high-deviation tokens at every layer and you fix the dominant error before it spreads. The recompute fraction is the trade-off knob: a higher percentage → closer to a full prefill, but more expensive. Empirically a small fraction is enough to keep quality from slipping.
Prefix caching saves on REPEATS — what if requests barely share a prefix?
Then there is little to gain — that is its honest limitation. But it shines wherever repetition is massive: one system prompt across thousands of requests, multi-turn dialogues (the same history every turn), few-shot prompting, agent loops. CacheBlend extends the payoff to RAG, where the same documents come back in different combinations — no longer as a shared prefix. That is why prompt caching became a standard line item on API price lists.
What to read in the original
Read selectively. From vLLM — the design doc on automatic prefix caching (chained block hashing, reuse on a hash match). From CacheBlend (arXiv 2405.16444, EuroSys ’25) — the problem statement (why non-prefix KV cannot be reused naively), the idea of selective recompute by KV deviation, and the pipelining of that recompute with loading the cache from slow storage.