Prefix caching by hash (vLLM)

Take a realistic deployment: an agent product, Llama-3-8B, a system prompt of 2,000 tokens (tool schemas, formatting rules, safety preamble), and a user turn averaging 200 tokens. Every request is a fresh HTTP POST. The engine sees 2,200 prompt tokens and prefills all of them.

Using the per-token FLOP formula from FORMULAS, $\text{FLOPs}_{\text{tok}} \approx 2P + 4\,L\,h\,d_h\,s$, the cost of prefilling a prompt of $S$ tokens is the sum over positions $s = 0 \dots S-1$:

where $P$ is parameter count, $L$ layers, $h$ query heads, $d_h$ head dimension. For Llama-3-8B ($P = 8.03 \times 10^9$, $L = 32$, $h = 32$, $d_h = 128$):

So 90.6% of the prefill FLOPs are redundant, and the reduction from caching the shared prefix is $36.60 / 3.43 = 10.7\times$. Convert that to time on §0.4's reference hardware — H100 SXM, 989.4 TFLOP/s bf16 peak — at a prefill MFU of 45%, so $4.45 \times 10^{14}$ FLOP/s achieved:

The third number is the one that should alarm you. At 20 requests per second the redundant prefill alone demands 664 TFLOP/s; the H100 at 45% MFU delivers 445 TFLOP/s in total. The machine is saturated by work it has already done and the queue grows without bound. This is not an optimisation; it is the difference between a system that serves the load and one that does not.

The KV cache is already paged into fixed-size blocks of block_size tokens (§2.2 owns the block pool). Prefix caching adds one idea: give each full block a content-addressed name, and keep a dictionary from name to block. When a new request arrives, compute the names its blocks would have, look them up, and adopt any block that already exists.

The trick is what goes into the name. Hashing only the block's own 16 token ids would be catastrophically wrong: the same 16 tokens appearing after "Ignore all prior instructions." and after "You are a helpful assistant." have completely different K and V, because attention at position 20 depends on positions 0–19. Same name, different contents — the engine would serve one request's KV to another.

So a block's name is a hash of its parent's name together with its own token ids. That single recursion makes the name a fingerprint of the entire prefix ending at that block boundary. Matching prefixes and all cache-identity inputs produce the same hash in the same namespace; equal hashes do not logically prove equal inputs because collisions are possible.

The hash function

Twenty-eight lines contain the whole idea:

def hash_block_tokens(
    hash_function: Callable[[Any], bytes],
    parent_block_hash: BlockHash | None,
    curr_block_token_ids: Sequence[int],
    extra_keys: tuple[Any, ...] | None = None,
) -> BlockHash:
    """Computes a hash value corresponding to the contents of a block and
    the contents of the preceding block(s). The hash value is used for
    prefix caching. We use LRU cache for this function to avoid recomputing
    hash values for the same block contents.
# ...
    """
    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))
    )

Define $t_i$ as the token-id tuple of block $i$, $e_i$ as its extra keys, and $H$ as the configured hash function. Then

a Merkle-style chain: $h_i$ fingerprints the entire token sequence $[0, (i{+}1)\cdot B)$ plus every extra key along the way, where $B$ is the block size. This is the correctness property the whole feature rests on. Without the parent term, $h_i$ would depend only on $t_i$, and any two prompts whose $i$-th block happened to hold the same 16 tokens would be judged interchangeable — not a rare coincidence when "\n\nAssistant: ", JSON punctuation runs, and few-shot separators recur at block granularity constantly. You would serve one user's attention state to another within seconds of startup.

NONE_HASH is the chain's initialisation vector, and its choice is a documented security decision:

# The hash seed for the first block of any prefix block sequence.
#
# For cryptographic hash algorithms it is derived deterministically from a fixed
# default seed, so independent vLLM processes compute identical block hashes for
# identical content and can share a prefix cache (e.g. KV cache reuse across
# nodes) without extra configuration. This does not weaken collision resistance,
# which for SHA-256 does not depend on keeping the seed secret; ``cache_salt``
# remains the mechanism for intentional cache isolation.
#
# Non-cryptographic algorithms keep a per-process random seed, because a
# predictable seed would let an attacker precompute colliding blocks offline
# (see #12621). Setting PYTHONHASHSEED overrides the seed in both cases.
#
# The function `init_none_hash` initializes this variable globally.
NONE_HASH: BlockHash

# Fixed seed used when the PYTHONHASHSEED environment variable is not set and
# the hash algorithm is cryptographic.
DEFAULT_NONE_HASH_SEED = "vllm-none-hash"

What else is in the key

Anything that changes a block's KV tensors but not its token ids must be in the key, or the cache is unsound. As of a556f3f the complete list is four items:

    mm_extra_keys: list[Any]
    mm_extra_keys, new_start_mm_idx = _gen_mm_extra_hash_keys(
        request, start_token_idx, end_token_idx, start_mm_idx
    )
    lora_extra_keys: list[str] = _gen_lora_extra_hash_keys(request)
    cache_salt_keys: list[str] = (
        [request.cache_salt] if (start_token_idx == 0 and request.cache_salt) else []
    )
    prompt_embeds_keys = _gen_prompt_embeds_extra_hash_keys(
        request, start_token_idx, end_token_idx
    )

    extra_keys: list[Any] = (
        lora_extra_keys + mm_extra_keys + cache_salt_keys + prompt_embeds_keys
    )

    if not extra_keys:
        return None, new_start_mm_idx

    return tuple(extra_keys), new_start_mm_idx

This list is the security-and-correctness boundary of the feature: anything that must not collide has to appear here. Note what is absent — sampling parameters (correctly; they do not affect KV) and model weights, which is why reset_prefix_cache() exists for RLHF weight updates.

Why block granularity, not token

The block is the unit of allocation, so it is also the unit of sharing: you cannot hand a request the first 31 tokens of a 32-token physical block without handing it the whole block, nor let two requests own overlapping halves while one keeps appending. With $B = 16$:

Reuse is $B \lfloor m / B \rfloor$ for a token-level match of length $m$, so the loss is $m \bmod B$ — at most $B-1$, averaging 7.5 tokens for $B = 16$. Against a 2,000-token shared prefix that is 0.4%, irrelevant.

The alignment sensitivity is the part that is not irrelevant. Hit length is not "longest common prefix rounded down"; it is "longest common prefix starting at token 0, rounded down". Prepend one token — a per-user id, a timestamp, a request uuid — and block 0's token ids change, $h_0$ changes, and by the chain every $h_i$ changes. You do not lose one block. You lose all 125.

Prefix caching is on by default at a556f3f, SHA-256 over a pickle serialisation:

    enable_prefix_caching: bool = True
    """Whether to enable prefix caching."""
    prefix_caching_hash_algo: PrefixCachingHashAlgo = "sha256"
    """Set the hash algorithm for prefix caching:

    - "sha256" uses Pickle for object serialization before hashing. This is the current
      default, as SHA256 is the most secure choice to avoid potential hash collisions.
    - "sha256_cbor" provides a reproducible, cross-language compatible hash. It
      serializes objects using canonical CBOR and hashes them with SHA-256.
    - "xxhash" uses Pickle serialization with xxHash (128-bit) for faster,
      non-cryptographic hashing. Requires the optional ``xxhash`` package.

Hashing happens on the request, not in the block manager

The hashes are computed by the Request object itself, incrementally, whenever a new full block's worth of tokens exists — at construction for the prompt, and again on every append_output_token_ids:

        new_block_hashes: list[BlockHash] = []
        while True:
            end_token_idx = start_token_idx + hash_block_size
            if end_token_idx > num_tokens:
                # We only hash full blocks
                break

            # MM and LoRA requests need extra keys for block-hash computation.
            extra_keys, curr_mm_idx = generate_block_hash_extra_keys(
                request, start_token_idx, end_token_idx, curr_mm_idx
            )

            # Compute the hash of the current block
            block_tokens = request.all_token_ids[start_token_idx:end_token_idx]
            block_hash = hash_block_tokens(
                caching_hash_fn, prev_block_hash_value, block_tokens, extra_keys
            )

            new_block_hashes.append(block_hash)
            start_token_idx += hash_block_size
            prev_block_hash_value = block_hash

        return new_block_hashes

We only hash full blocks: a partially filled tail block has no hash and cannot be shared. Generated tokens are hashed exactly like prompt tokens, which is what makes multi-turn reuse work — turn 2's prompt is turn 1's prompt plus turn 1's output, and those blocks are already named.

The lookup

The map is a plain dict from a 36-byte key (32-byte SHA-256 digest plus a 4-byte KV-cache group id) to a block:

    def get_cached_block(
        self, block_hash: BlockHash, kv_cache_group_ids: list[int]
    ) -> list[KVCacheBlock] | None:
# ...
        cached_blocks = []
        for group_id in kv_cache_group_ids:
            block_hash_with_group_id = make_block_hash_with_group_id(
                block_hash, group_id
            )
            block = self.cached_block_hash_to_block.get_one_block(
                block_hash_with_group_id
            )
            if not block:
                return None
            cached_blocks.append(block)
        return cached_blocks

The prefix scan stops at the first missing physical block because this API returns a contiguous reusable prefix. A token or identity change changes all descendant hashes. Physical eviction is different: it removes an index entry, not the deterministic hashes of later blocks, which may remain stored but cannot fill the ancestor hole. The source comment below compresses these two different reasons for a miss.

        computed_blocks: tuple[list[KVCacheBlock], ...] = tuple(
            [] for _ in range(len(kv_cache_group_ids))
        )
        # 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)
        hit_length = len(computed_blocks[0]) * block_size

Per request the complexity is $O(S)$ to hash (amortised, incremental, once per token) and $O(S/B)$ expected-$O(1)$ dict probes to look up, terminating at the first miss. Insertion is $O(1)$ per newly full block. There is no search, no comparison against other stored sequences, and no structure larger than a dict. For Llama-3-8B on an 80 GB H100, whose KV pool is 52.32 GiB (§2.1, derived), the map holds at most $52.32\,\text{GiB} / 2\,\text{MiB} = 26{,}785$ entries — at 36 raw key bytes per entry, under a megabyte of key payload. Python objects, dictionaries, reference counts, and allocator overhead make the full index larger.

Eviction and the conditions for inexpensive resumption

A cached block is not pinned. It sits in the free queue as an eviction candidate with ref_cnt == 0, still carrying its hash and still findable, and loses that hash only at the moment it is handed to someone else, inside get_new_blocks → _maybe_evict_cached_block. The eviction order is set on free:

    def free_blocks(self, ordered_blocks: Iterable[KVCacheBlock]) -> None:
        """Free a list of blocks. The blocks should be ordered by their
        eviction priority, where the first block will be evicted first.
# ...
        # Identify blocks with hash (LRU cache) and without it (never match APC)
        blocks_to_evict_last = []
        blocks_to_evict_first = []
        for block in ordered_blocks:
            block.ref_cnt -= 1
            if block.ref_cnt == 0 and not block.is_null:
                if block.block_hash is None or not self.enable_caching:
                    # LIFO reuse of non-cached blocks for better GPU locality.
                    blocks_to_evict_first.append(block)
                else:
                    # FIFO reuse of cached blocks for LRU eviction behavior.
                    blocks_to_evict_last.append(block)

        # Blocks to reuse first are prepended to the front of the free queue.
        self.free_block_queue.prepend_n(blocks_to_evict_first)
        # Blocks to reuse last are appended to the end of the free queue.
        self.free_block_queue.append_n(blocks_to_evict_last)

Two policies in one queue: unhashed blocks to the front (LIFO, reuse hot memory at once), hashed blocks to the back (FIFO, so allocation pops the least-recently-freed cached block first). Within a request, KVCacheManager.free walks blocks in reverse, so tail blocks land nearer the front than head blocks — the ordering documented on the queue itself:

    The queue is ordered by block ID in the beginning. When a block is allocated
    and then freed, it will be appended back with the eviction order:
    1. The least recent used block is at the front (LRU).
    2. If two blocks have the same last accessed time (allocated by the
       same sequence), the one with more hash tokens (the tail of a block
       chain) is at the front.
    Note that we maintain this order by reversing the block order when free
    blocks of a request. This operation is outside of this class.

This is the mechanism §1.4 relies on. A preempted request's blocks are freed with their hashes intact and appended to the tail of the queue. Unless the pool churns through the entire free list before the victim is re-admitted, the victim's own hashes still resolve and its "recompute from scratch" is a prefix-cache hit for almost everything. Hash-keyed blocks surviving eviction is what turns preemption from a catastrophe into a scheduling hiccup.

Rule 2 is a crude approximation of tree-order eviction: deeper blocks go first, because a shallow block is likelier to be a shared prefix. But it holds only within one request's free operation. Across requests, ordering is pure LRU over free times, with no knowledge of which block is a parent of which.

Two requests, same 2,000-token system prompt, block_size = 16, single KV cache group, Llama-3-8B.

Request 1, cold cache. Request.__init__ calls update_block_hashes(), which runs the closure from get_request_block_hasher over 2,200 prompt tokens: $\lfloor 2200/16 \rfloor = 137$ full blocks, 137 chained SHA-256 evaluations, 8 tokens left unhashed. The map is empty, the first probe misses, hit length is 0, and the request prefills all 2,200 tokens. As blocks fill, cache_full_blocks inserts each hash into cached_block_hash_to_block.

Request 2, same system prompt, different user turn. Its first 125 block hashes are bit-identical to request 1's, because tokens 0–1999 are identical and the chain is deterministic. find_longest_cache_hit probes block 0 (hit), 1 (hit), … 124 (hit), 125 (miss — the user turn diverges), giving hit_length = 125 × 16 = 2000. BlockPool.touch bumps ref_cnt on all 125 and pulls each out of the free queue. The scheduler prefills 200 tokens instead of 2,200.

The exact-duplicate case. Send request 1 twice. Now every hash matches — but look at the cap:

        if not self.prefix_cache_lookup_enabled(request):
            return self.empty_kv_cache_blocks, 0, 0

        # 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.
        # This can trigger recomputation of an entire block, rather than just
        # the single last token, because allocate_slots() requires
        # num_computed_tokens to be block-size aligned. Removing this limitation
        # could slightly improve performance in the future.
        max_cache_hit_length = request.num_tokens - 1
        computed_blocks, num_new_computed_tokens, num_uncached = (
            self.coordinator.find_longest_cache_hit(
                request.block_hashes, max_cache_hit_length
            )
        )

With 2,200 tokens, max_cache_hit_length = 2199 bounds the loop at $\lfloor 2199/16 \rfloor = 137$ — all of them — so the duplicate hits 2,192 tokens and prefills 8. But for a prompt that is an exact multiple of the block size (2,000 tokens, 125 blocks), max_cache_hit_length = 1999, $\lfloor 1999/16 \rfloor = 124$, and the engine recomputes a full 16-token block to obtain logits for one token. This is the most confusing observation for people first reading the hit-rate metric: a perfectly cached prompt reports 124/125.

What invalidates a hit

The prompt_logprobs case surprises people: turn it on for observability and the hit rate for those requests goes to zero, by design —

        if self.skip_reading_prefix_cache is None:
            # If prefix caching is enabled,
            # the output of prompt logprobs may less than n_prompt_tokens,
            # we need to skip reading cache at this request.
            self.skip_reading_prefix_cache = self.prompt_logprobs is not None

And reset_prefix_cache is a request, not a command — it fails if anything is still allocated, and logs it:

        num_used_blocks = self.num_gpu_blocks - self.get_num_free_blocks()
        if num_used_blocks != 1:  # The null block is always marked as used
            logger.warning(
                "Failed to reset prefix cache because some "
                "blocks (%d) are not freed yet",
                num_used_blocks - 1,
            )
            return False

        # Remove all hashes so that no new blocks will hit.
        self.cached_block_hash_to_block = BlockHashToBlockMap()
        self.cached_block_hashes_by_block.clear()

        # Remove all hashes from all blocks.
        for block in self.blocks:
            block.reset_hash()

The security question, honestly

A shared prefix cache across tenants leaks two things.

Timing. A hit drops TTFT by tens of milliseconds — 74 ms in the derivation above, trivially observable over the network. An attacker who can time requests can therefore test whether a given prefix has recently been served by somebody, and search over candidate prefixes at block granularity. This is inherent to any cross-request cache; no hash function fixes it.

Content, on collision. get_cached_block returns a block on hash equality alone. It does not re-verify token ids. A collision therefore serves one request's KV as another's, silently — wrong output, no error. With SHA-256 and a map bounded at ~27k live entries this is not a practical concern: the birthday bound over $n$ blocks is $\approx n^2/2^{257}$, about $10^{-59}$ at $n = 10^9$. xxhash (128-bit) raises that to roughly $10^{-21}$ — still negligible by accident, but no longer collision-resistant against an adversary who chooses inputs, which is exactly why the non-cryptographic path keeps a random per-process NONE_HASH seed (issue #12621).

Cache namespaces and collision resistance address different risks. Assign cache_salt at a trusted authenticated gateway for tenant/user isolation; a caller-controlled salt does not enforce an authorization boundary. Use a suitable cryptographic hash where adversarial collisions matter. Salting alone does not turn a non-cryptographic hash into a collision-resistant one.

    cache_salt: str | None = Field(
        default=None,
        min_length=1,
        description=(
            "If specified, the prefix cache will be salted with the provided "
            "string to prevent an attacker to guess prompts in multi-user "
            "environments. The salt should be random, protected from "
            "access by 3rd parties, and long enough to be "
            "unpredictable (e.g., 43 characters base64-encoded, corresponding "
            "to 256 bit)."
        ),
    )

The residual risk is the tradeoff you are actually making. A salt per user buys per-user isolation and keeps per-user reuse; a salt per request buys full isolation and destroys the feature; a salt shared across a tenant leaves that tenant's members able to probe each other. No configuration gives you both cross-user prefix sharing and cross-user timing isolation.

Metrics you can actually read

Two Prometheus counters, both in tokens (not requests):

        counter_prefix_cache_queries = self._counter_cls(
            name="vllm:prefix_cache_queries",
            documentation=(
                "Prefix cache queries, in terms of number of queried tokens."
            ),
            labelnames=labelnames,
        )
# ...
        counter_prefix_cache_hits = self._counter_cls(
            name="vllm:prefix_cache_hits",
            documentation=("Prefix cache hits, in terms of number of cached tokens."),
            labelnames=labelnames,
        )

Hit rate is rate(vllm:prefix_cache_hits[5m]) / rate(vllm:prefix_cache_queries[5m]). Requests that skipped the lookup are excluded from both, so the denominator is honest. PrefixCacheStats also splits out preempted requests:

    preempted_requests: int = 0
    """The number of previously preempted requests in this update."""

    preempted_queries: int = 0
    """The `queries` number for preempted requests."""

    preempted_hits: int = 0
    """The `hits` number for preempted requests."""

    def record(self, num_tokens: int, num_hits: int, preempted: bool) -> None:
        """Aggregate request information into the stats."""
        if preempted:
            # Previously preempted request
            self.preempted_requests += 1
            self.preempted_queries += num_tokens
            self.preempted_hits += num_hits
        else:
            # New request
            self.requests += 1
            self.queries += num_tokens
            self.hits += num_hits

preempted_hits / preempted_queries is exactly the survival fraction $f$ that §1.4 needs for the recompute-versus-swap decision. If it drops well below 1.0, your pool is churning through the whole free queue between preemption and resumption, and recompute is no longer cheap.

§2.4 covers SGLang's RadixAttention, which replaces the dict with a radix tree over token sequences. To make that comparison sharp, here is what vLLM's structure does and does not give you.

The last two rows are the substantive ones. A tree knows that node $X$ is the parent of node $Y$, so it can evict leaves before internal nodes and rank a waiting request by match depth without touching the block pool. A hash map knows neither. What it buys instead is a lookup with no allocations, no rebalancing, no locks around a mutable structure, and low expected probe cost. Hash construction, CPU contention, and long requests can still make lookup measurable; profile rather than assume. Which side of that trade is correct depends on your workload — the argument §2.4 takes up.

Measure the hashing cost itself, no GPU required:

python benchmarks/benchmark_prefix_block_hash.py --num-blocks 20000 --block-size 16
# compares sha256, sha256_cbor, xxhash, xxhash_cbor over hash_block_tokens

Then the end-to-end effect. benchmarks/benchmark_prefix_caching.py (277 lines, the real implementation, not a shim) replicates each sampled prompt --repeat-count times:

python benchmark_prefix_caching.py \
    --model meta-llama/Llama-2-7b-chat-hf \
    --enable-prefix-caching \
    --num-prompts 1 \
    --repeat-count 100 \
    --input-length-range 128:256

Three things to try, in order. Serve with caching on, scrape /metrics, and confirm the hits/queries ratio matches the shared fraction of your prompt. Then add a fresh unique cache_salt value to every request body and watch the hit rate collapse to zero — the isolation mechanism working. Reusing one fixed new salt gives only an initial cold miss and allows later reuse. Then prepend a single per-request token and confirm the hit rate collapses identically. Confusing those two failure modes in production costs hours. Lab 04 does all three against both engines.

• vLLM PR #9972 — V1 Prefix caching (take 2): the V1 rewrite that introduced the chained block hash and the free-queue-as-LRU design.
• vLLM PR #10507 — Refactor KVCacheManager for more hash input than token ids: where extra_keys was generalised, enabling LoRA and multimodal keying.
• vLLM PR #11187 — Prefix caching for vision language models: the multimodal identifier and the in-block offset.
• vLLM PR #17045 — Prevent side-channel attacks via cache salting, and issue #12621 on precomputed-collision risk with non-cryptographic hashes.
• vLLM PR #29163 — xxHash as a high-performance hash option, and PR #51875 — deterministic NONE_HASH by default, which made cross-process cache sharing work without PYTHONHASHSEED.
• §2.4 — RadixAttention for the tree, and §12.3 for its implementation.
• Lab 04 — prefix cache hit rate: run a shared-prefix workload against both engines and break the cache deliberately.