Post

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.

LLM Inference #7: Prefix Caching

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.

Same document, two questions without reuse request A prefill 4,096 document tokens question request B prefill the same 4,096 tokens again question with reuse request A prefill 4,096 document tokens question request B read A's blocks, compute nothing question B starts here

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.

The match ends at the first difference and does not resume prompt A system doc 1 doc 2 doc 3 question A same tail prompt B system doc 1 doc 2 doc 3 question B same tail not reusable The tail blocks hold identical tokens, and their keys and values still differ, because they were computed after a different question. Position, not content, decides what a block holds. The whole prompt matters: chat template, system message, tool definitions, whitespace, tokenizer version.

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.

Each block hash carries every block before it tokens 0-63 tokens 64-127 tokens 128-191 tokens 192-255 h0 = hash(seed, tokens) h1 = hash(h0, tokens) h2 = hash(h1, tokens) h3 = hash(h2, tokens) Looking up h2 asks one question: has anyone stored these 64 tokens, after exactly these 128 tokens? A lookup walks the blocks in order and stops at the first miss. The default hash is SHA-256, set by prefix_caching_hash_algo in vllm/config/cache.py. The seed for the first block comes from PYTHONHASHSEED when set, and from a fixed string otherwise.

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.

One block, after its request finishes ref_cnt drops to 0 hash and contents kept A matching request arrives first the block is referenced again, nothing is recomputed The allocator needs space first the hash entry is dropped and the content overwritten The list is ordered least recently used first, so the oldest unreferenced block goes first. Nothing is copied and nothing is written back. Caching here means not yet overwriting.

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.

A 100-token shared prefix, block size 64 tokens 0-63, full block, cached tokens 64-99, partial prefilled every time Block size sets the granularity of a hit. A long shared document loses at most 63 tokens at its tail, which is noise. A short shared prefix can fall below one block and never cache at all. If you depend on prefix hits for short prompts, a smaller block size buys finer matching, and the costs from the last article still apply.

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.

Identical tokens, two tenants, no shared blocks tenant A salt A + tokens 0-63 tokens 64-127 tokens 128-191 h0a, h1a, h2a tenant B salt B + tokens 0-63 tokens 64-127 tokens 128-191 h0b, h1b, h2b Only the first block carries the salt. The chain carries it the rest of the way, so every later hash differs and the two tenants never read each other's blocks. Pick the trust boundary deliberately. One salt for everyone allows the widest sharing. One salt per tenant isolates tenants and keeps sharing inside each one. One salt per request turns the cache off.

What improves, and by how much

A hit removes prefill work for the matched positions. It removes nothing else.

Where the time goes, before and after a hit miss prefill decode hit skipped decode, unchanged first output token Time to first token falls. Time per output token does not, because decode has the same work to do. Under load the saved prefill also frees the GPU for other requests, which shortens queues.

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.

Three requests with the same prefix round robin router replica A, miss replica B, miss replica C, miss three full prefills, three copies of the same KV prefix aware router replica A, hit one prefill, one copy, and replica A carries the load Routing for cache hits concentrates traffic. Routing for even load destroys every hit.

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_salt enters 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

This post is licensed under CC BY 4.0 by the author.