Prefix Caching

The idea in one minute#

In a causal language model, the keys and values computed for token i depend only on tokens 0 to i. Two prompts that begin with the same tokens therefore have identical KV cache contents for that shared beginning. vLLM exploits this without being asked: every full block is given a hash that identifies the entire prefix up to and including that block, and before a new request is scheduled the engine looks its hashes up. Every block that matches is reused; only the remainder of the prompt is computed. System prompts, few-shot examples, long documents queried repeatedly and the earlier turns of a conversation all become nearly free. It is on by default, it never changes outputs, and whether it works for you depends almost entirely on what your prompts have at the front.

A picture#

flowchart LR
  subgraph RQ["New request: system prompt + question B"]
    direction LR
    B0["block 0<br/><small>tokens 0–15</small>"] --> B1["block 1<br/><small>16–31</small>"] --> B2["block 2<br/><small>32–47</small>"] --> B3["block 3<br/><small>48–63</small>"] --> B4["tail<br/><small>64–69</small>"]
  end
  B0 -. "h0 = H(seed, tokens)" .-> M[(":i-search: <b>hash to block</b>")]
  B1 -. "h1 = H(h0, tokens)" .-> M
  B2 -. "h2 = H(h1, tokens)" .-> M
  B3 -. "h3 = H(h2, tokens)" .-> M
  M -->|"h0, h1, h2 found"| HIT[":i-check: <b>reuse 3 blocks</b><br/><small>48 tokens skipped</small>"]
  M -->|"h3 missing: stop"| MISS[":nvidia: <b>compute 22 tokens</b><br/><small>the question</small>"]
  class B0,B1,B2 memory
  class B3,B4 compute
  class M queue
  class HIT neutral
  class MISS compute

How it really works#

The hash is a chain#

A block’s KV depends on every token before it, so its identity must too. Hashing the full prefix for every block would cost time quadratic in the prompt length. Instead each block’s hash includes its parent’s hash (vllm/v1/core/kv_cache_utils.py):

def hash_block_tokens(hash_function, parent_block_hash, curr_block_token_ids, extra_keys=None):
    if not parent_block_hash:
        parent_block_hash = NONE_HASH
    curr_block_token_ids_tuple = tuple(curr_block_token_ids)
    return BlockHash(
        hash_function((parent_block_hash, curr_block_token_ids_tuple, extra_keys))
    )

Three inputs:

Two properties follow from the chain. Hashing a prompt is linear in its length. And if block k misses, every later block must miss too, so the lookup can stop at the first miss.

Where and when hashes are computed#

Not in the scheduler. When a request arrives in the engine core, the input thread builds the Request object and calls the block hasher immediately, overlapping with whatever the GPU is doing (Processes and Wires):

req = Request.from_engine_core_request(request, self.request_block_hasher)

The hasher covers only new full blocks, so it is called again cheaply each time generated tokens complete another block:

start_token_idx = len(request.block_hashes) * hash_block_size
...
while True:
    end_token_idx = start_token_idx + hash_block_size
    if end_token_idx > num_tokens:
        # We only hash full blocks
        break

By the time the scheduler considers the request, request.block_hashes is already a list of finished hashes.

The lookup#

In pass 2 of schedule(), once per request, when it has computed nothing yet:

# NOTE: When all tokens hit the cache, we must recompute the last token
# to obtain logits. Thus, set max_cache_hit_length to prompt_length - 1.
max_cache_hit_length = request.num_tokens - 1
computed_blocks, num_new_computed_tokens, ... = self.coordinator.find_longest_cache_hit(
    request.block_hashes, max_cache_hit_length
)

and inside, for an ordinary full-attention model:

# Phase 1: longest run of cached full blocks from the start. A missing
# block implies every later block misses too (chained hashes).
for block_hash in itertools.islice(full_block_hashes, max_length // block_size):
    cached_block = block_pool.get_cached_block(block_hash, kv_cache_group_ids)
    if not cached_block:
        break
    for computed, cached in zip(computed_blocks, cached_block):
        computed.append(cached)

The matching blocks are then touched (reference count up, removed from the free queue if they were in it) and placed at the start of the request’s block table. The request begins with num_computed_tokens equal to the hit length.

Two details shape the numbers you will see:

• Hits come in whole blocks. A 50-token shared prefix yields a 48-token hit; the last two tokens are recomputed.
• The last token is always computed. The cache stores keys and values, not the model’s final output. To sample the first new token the model must run on at least one position. So the maximum hit is num_tokens − 1, rounded down to a block: an identical 64-token prompt sent twice hits 48 tokens the second time, not 64. The source acknowledges it: “This can trigger recomputation of an entire block, rather than just the single last token.”

What else goes into the hash#

Identical tokens do not always mean identical KV. generate_block_hash_extra_keys adds whatever else matters:

cache_salt: isolation between tenants#

A shared prefix cache leaks a little information through timing. If a request returns its first token unusually fast, its prefix was already cached, which tells the sender that someone sent that prefix recently. An attacker can probe for the contents of other users’ prompts one block at a time.

The defence is a per-request salt:

{
  "messages": [{"role": "user", "content": "..."}],
  "cache_salt": "tenant-7f3a"
}

The salt is hashed into the first block only. Since every later hash includes its parent’s, the whole chain differs, and requests with different salts can never share a block. Requests with the same salt share normally. Choose one salt per trust boundary — per customer, typically — and set it in the gateway, not the client. Isolation costs cache hits across tenants and nothing else.

Which hash function#

--prefix-caching-hash-algo selects it:

A collision would hand one request another request’s KV: wrong output at best, another user’s context at worst. That is why the default is cryptographic, and why the documentation warns about the alternatives in multi-tenant settings.

The chain starts from a seed, NONE_HASH:

• For the SHA-256 variants it is derived from a fixed string, so independent vLLM processes produce identical hashes for identical content. That is what allows a router, or another node, to reason about what a replica has cached.
• For the xxHash variants it is random per process, because “a predictable seed would let an attacker precompute colliding blocks offline”.
• Setting PYTHONHASHSEED overrides both.

Why your hit rate is low#

Because the chain starts at token 0, a difference at position p invalidates everything from block ⌊p/16⌋ onward. The cache rewards prompts whose stable material comes first.

Order prompts from most stable to least: fixed instructions, tool definitions, long shared documents, conversation history, and last the new message and anything volatile.

Multi-turn chat is the best case. Turn n+1 contains turn n’s prompt and its answer as a prefix, and the answer’s blocks were cached as they were generated — output tokens fill blocks and receive hashes exactly like prompt tokens. Only the new message is computed. One caveat: the hit depends on the chat template rendering the earlier assistant turn to the same tokens the model produced. Templates that drop reasoning text from past turns, for example, break the chain at that point.

Requests that skip the cache#

A few requests must not read from the cache (they still populate it):

• Prompt logprobs requested. The cache holds KV, not logits. Scoring every prompt token needs a real forward pass over all of them.
• Pooling requests that need the hidden state of every token.

In both cases skip_reading_prefix_cache is set and the lookup returns nothing.

And two kinds of model switch caching off entirely at startup: encoder-decoder models, and models with any non-causal attention layer, for which the “depends only on earlier tokens” property does not hold.

Finer than a block: --prefix-match-unit#

For ordinary models the hashing granularity equals the block size, 16 tokens. Some newer architectures need much larger physical blocks: hybrid attention/state-space models may use 1,024 tokens per block. With hits rounded down to a block, a 1,000-token shared system prompt would then never hit at all.

--prefix-match-unit decouples the two. Hashes are computed every prefix_match_unit tokens (say 64) while memory is still managed in 1,024-token blocks, and a hit may land on a 64-token boundary inside a physical block. The scheduler then performs a copy-on-write: the matching part of the cached block is copied into a fresh block that the new request owns, so the request can continue writing where the shared part ends without disturbing the original. This is what the kv_cache_block_copies field of SchedulerOutput carries.

For a standard decoder-only model none of this is active: the unit and the block size are both 16.

Measuring it#

Statistics are recorded when a request is admitted, not when it is merely looked at, so a request that waits in the queue is counted once.

What it saves, and what it does not#

A hit removes prefill compute. For a request with P prompt tokens of which H hit:

prefill work  ∝  P − H        (was P)
decode work   unchanged
memory        the H tokens' blocks are shared, not duplicated

Time to first token falls roughly in proportion to (P − H) / P. Tokens per second during generation do not change. The project’s documentation puts it this way: caching “does not bring performance gain when vLLM spends most of the time generating answers”, nor when requests share no prefix.

The second line of that box is easy to miss: sharing also saves memory. Fifty concurrent requests with a common 4,000-token system prompt hold one copy of those 250 blocks, not fifty.

Code#

The hash chain and the lookup, with SHA-256 as in the default configuration. Eight requests show every rule above.

package main

import (
	"crypto/sha256"
	"encoding/binary"
	"fmt"
)

const blockSize = 16

type hash [32]byte

// noneHash seeds the chain: the "parent" of the first block.
var noneHash = sha256.Sum256([]byte("vllm-none-hash"))

// hashBlock mirrors hash_block_tokens: hash(parent, tokens of this block, extra keys).
func hashBlock(parent hash, tokens []int, extra string) hash {
	h := sha256.New()
	h.Write(parent[:])
	for _, t := range tokens {
		var b [8]byte
		binary.LittleEndian.PutUint64(b[:], uint64(t))
		h.Write(b[:])
	}
	h.Write([]byte(extra))
	var out hash
	copy(out[:], h.Sum(nil))
	return out
}

// blockHashes returns one hash per FULL block. The salt enters the first block only;
// every later block inherits it through its parent.
func blockHashes(tokens []int, salt string) []hash {
	var hs []hash
	parent := noneHash
	for end := blockSize; end <= len(tokens); end += blockSize {
		extra := ""
		if end == blockSize && salt != "" {
			extra = "cache_salt=" + salt
		}
		parent = hashBlock(parent, tokens[end-blockSize:end], extra)
		hs = append(hs, parent)
	}
	return hs
}

type cache map[hash]bool

// lookup returns the number of tokens that can be skipped.
func (c cache) lookup(tokens []int, salt string) int {
	// At least the last token must be recomputed to obtain logits.
	maxHit := len(tokens) - 1
	hit := 0
	for _, h := range blockHashes(tokens, salt)[:maxHit/blockSize] {
		if !c[h] {
			break // chained hashes: one miss means every later block misses too
		}
		hit += blockSize
	}
	return hit
}

func (c cache) store(tokens []int, salt string) {
	for _, h := range blockHashes(tokens, salt) {
		c[h] = true
	}
}

// seq makes n deterministic token IDs from a seed.
func seq(seed, n int) []int {
	out := make([]int, n)
	for i := range out {
		out[i] = (seed*7919 + i*104729) % 50000
	}
	return out
}

func join(parts ...[]int) []int {
	var out []int
	for _, p := range parts {
		out = append(out, p...)
	}
	return out
}

func main() {
	system := seq(1, 50) // a 50-token system prompt
	userA := seq(2, 20)
	userB := seq(3, 20)
	answerA := seq(4, 30)
	followUp := seq(5, 12)

	c := cache{}
	// report looks a prompt up, then stores it together with the answer the model
	// generated for it: output tokens fill blocks and are cached like prompt tokens.
	report := func(name string, prompt []int, salt string, generated []int) {
		hit := c.lookup(prompt, salt)
		fmt.Printf("%-46s %4d tokens  cached %4d  computed %4d\n",
			name, len(prompt), hit, len(prompt)-hit)
		c.store(join(prompt, generated), salt)
	}

	report("1. first request", join(system, userA), "", answerA)
	report("2. same system prompt, different question", join(system, userB), "", nil)
	report("3. next turn of conversation 1", join(system, userA, answerA, followUp), "", nil)
	report("4. timestamp inserted before the system prompt", join(seq(9, 1), system, userA), "", nil)
	report("5. request 1 again, with cache_salt=tenant-b", join(system, userA), "tenant-b", nil)
	report("6. the same, from tenant-b again", join(system, userA), "tenant-b", nil)
	report("7. a 64-token prompt, sent for the first time", seq(7, 64), "", nil)
	report("8. exactly the same 64-token prompt again", seq(7, 64), "", nil)
}

Line by line: (2) a 50-token shared prefix gives a 48-token hit, three whole blocks. (3) the follow-up turn reuses the previous prompt and answer. (4) one token at the front destroys everything. (5) a different salt shares nothing; (6) the same salt shares again. (8) an identical prompt hits all but its last block, because the final token must be computed.

Remember this#

• A block’s hash covers its own tokens and, through its parent’s hash, the entire prefix.
• Lookup walks the chain from block 0 and stops at the first miss.
• Hits are whole blocks, and never include the last token of the prompt.
• LoRA adapter, media content, cache_salt and prompt embeddings are part of the hash.
• cache_salt goes into the first block only and isolates the whole chain.
• The default hash is SHA-256 with a fixed seed, so hashes agree across processes.
• Put stable content first. One volatile token at the top disables the cache.
• Generated tokens are cached too, which is why multi-turn chat hits so well.
• A hit saves prefill compute and memory; decode speed is unchanged.

Try it#

1. Change system to 47 tokens and to 49. What is the hit for request 2 in each case? How many tokens of padding would make a 47-token system prompt cache one more block, and is that ever worth doing?
2. Model a prompt with the date in the last line of the system prompt instead of the first. Put a 1-token “date” after system and vary it between requests. What hit do you get?
3. On a real server with --enable-prompt-tokens-details, send the same long prompt twice and read usage.prompt_tokens_details.cached_tokens. Then add "cache_salt": "x" and repeat.

Check yourself#

1. Why does a block’s hash include the hash of the block before it?
2. An identical prompt of exactly 160 tokens is sent twice. How many tokens are computed the second time?
3. Why is the salt applied only to the first block, and why is that sufficient?

Sources#

Checked on 5 October 2026 against vLLM v0.30.0 and main at commit 0c16eee.

• vllm/v1/core/kv_cache_utils.py — hash_block_tokens, get_request_block_hasher, extra keys, NONE_HASH
• vllm/v1/core/kv_cache_manager.py — get_computed_blocks
• vllm/v1/core/single_type_kv_cache_manager.py — find_longest_cache_hit
• vllm/config/cache.py — hash algorithms, prefix_match_unit
• Automatic prefix caching (design)
• Automatic prefix caching (feature)