LLM Inference #7: Prefix Caching
Every request sends the same 4,000-token system prompt, and the GPU prefills it every time. How block hashing turns the KV free list into a cache, what it will not match, and why one salted block isolates a whole tenant.
An internal API sends the same 4,096-token policy document before every question. One user asks for a summary. The next asks about a single clause. The GPU processes that identical document twice, and both users wait while it does.
Nothing about the second prefill produces new information. The keys and values for those 4,096 positions are the same both times. The tokens are the same, and attention is causal, so a position depends only on the tokens before it.
The paged attention article left one detail hanging. When a request finishes, its blocks go back on a free list that keeps their contents and their hash. That detail is the whole feature. The vLLM details here come from the source rather than from the docs, which lag the code in a few places.
The work being repeated
Prefill processes the prompt and builds its KV state. Decode then generates tokens one at a time. Two requests that start with the same tokens do the same prefill work for the shared part.
Caching the answer instead would not help. The users ask different questions, so the answers differ. What repeats is the prompt, and what the GPU can keep is the KV state for the prompt.
What counts as the same prefix
This is an exact match on token IDs, in order, from position zero. Similar wording does not count. “The policy says” and “This policy says” tokenize differently at the first word, so the match ends there.
The match also ends for good at the first difference. If two prompts agree for 1,000 tokens, diverge at token 1,001, then contain the same paragraph later, that later paragraph is not reusable. Its keys and values were computed after different earlier tokens, so they hold different numbers.
Hashing a block together with its history
Reuse needs a lookup key. A request arrives, the runtime cuts the prompt into 64-token blocks, and for each one it has to ask the pool a yes-or-no question: do you already hold this block?
The obvious key is a hash of the block’s 64 token IDs. That key is wrong, for the reason the last section showed. Two prompts can put identical tokens in a block and still need different keys and values there, because the tokens before that block were different. A key built from the block’s own tokens would call those two blocks the same block, and the second request would read the first request’s attention state.
vLLM builds the key from the block’s tokens and the hash of the block before it. hash_block_tokens takes the parent block’s hash, the block’s token IDs, and a tuple of extra keys, which is where tenant isolation enters later. The first block has no parent, so it starts from a fixed seed.
The effect is that a block’s hash stops being a fingerprint of 64 tokens. The hash of the fourth block fingerprints all 256 tokens up to that point, with its own 64 at the end. Identical tokens after a different prefix hash differently, so they cannot collide by accident.
Stopping at the first miss costs nothing. Attention over a block needs the keys and values of every block before it, so once one block is missing, no later block in that prompt is usable even if the pool happens to hold it.
The cache is the free list
There is no separate cache. The pool from the last article already has everything a cache needs.
When a request finishes, its blocks lose their reference and go on the free list, keeping their contents and their hash entry. A block in that state is free and cached at the same time. If a matching request arrives first, the block gets referenced again and nothing is recomputed. If the allocator needs space first, the block gets taken from the front of the list, its hash entry goes away, and the content is overwritten.
Two consequences follow. Prefix caching costs no extra memory, because the blocks were sitting there anyway. It also offers no guarantee, because any block can lose its contents the moment the pool is under pressure.
Only full blocks get cached
cache_full_blocks stores full blocks. A trailing partial block has no hash and no entry, since appending the next token would change its contents.
With the default block size of 64, a shared prefix of 100 tokens caches one block. The other 36 tokens get prefilled on every request.
There is one more boundary case. If a prompt hits the cache completely, the scheduler still recomputes its last token. Sampling the first output token needs logits, and the cache stores keys and values rather than logits. kv_cache_manager.py caps the hit at prompt_length - 1 for exactly this reason.
One salted block isolates a tenant
Shared prefixes across tenants are a security question, not only a performance one. A request that returns quickly tells the sender that someone else recently sent that prefix. No KV bytes leak, and the timing does.
vLLM’s control is cache_salt. A request carries a salt string, and the salt enters the extra keys of the first block only, at start_token_idx == 0. Because hashes chain, changing the first block’s hash changes every hash after it.
What improves, and by how much
A hit removes prefill work for the matched positions. It removes nothing else.
The number to track is matched tokens per request, not hit rate. A request that matches 16 tokens and one that matches 4,000 both count as hits, and they are not worth the same. vLLM reports vllm:prefix_cache_queries and vllm:prefix_cache_hits in tokens, so the ratio of those two already says what you want.
For the Llama 3.1 70B example at 320 KiB per token, a 4,096-token document holds 1.25 GiB of KV across the model. Keeping it resident is free while nothing else needs those blocks, and it costs you a smaller working set the moment something does.
A warm cache lives on one replica
Prefix caching is local to a GPU pool. A prefix that is warm on replica A does nothing for replica B.
Routing by prefix raises the hit rate and skews the load, so a router has to weigh cache affinity against queue depth on the replica that holds the prefix. Sending everything to the warm replica is how you turn a cache win into a latency regression.
When it does not pay
Short prompts with no shared opening cannot hit. A template that changes per request breaks the chain at its first block, which makes every later block unmatchable. A timestamp or a user name near the front does it. Put the variable part at the end of the prompt, after the stable part, and the stable part stays cacheable.
Retained blocks also compete with running sequences. The free list holds cached blocks only until the allocator wants them, so a server under memory pressure evicts prefixes before it preempts requests. A high hit rate measured on an idle server tells you very little about a busy one.
Summary
- Prefix caching skips the prefill for prompt tokens that an earlier request already computed. It never skips decode.
- A match is exact on token IDs from position zero, and it stops for good at the first difference.
- vLLM hashes each full block together with its parent’s hash, so a block matches only after an identical history.
- The cache is the free list. Freed blocks keep their contents and hash until the allocator needs the space, so the feature costs nothing and guarantees nothing.
- Only full blocks are cached, and a complete hit still recomputes the last token to get logits.
cache_saltenters the first block’s hash and the chain carries it, so one salted block isolates a tenant.- Hits improve time to first token. Routing decides how often a hit is even possible.
Next in this series: chunked prefill, and what to do about the long prompt that misses.
References
- Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023. arXiv
- vLLM source, in
kv_cache_utils.py,block_pool.py, andkv_cache_manager.py - vLLM automatic prefix caching design, production metrics, and security guidance on the timing side channel and
cache_salt - Zheng et al., SGLang: Efficient Execution of Structured Language Model Programs, NeurIPS 2024, which indexes shared prefixes with a radix tree instead of a hash chain. paper
- Meta Llama 3.1 model configuration, the source of the 320 KiB per token figure