Automatic Prefix Caching

Automatic Prefix Caching (APC) keeps the key/value (KV) cache blocks of finished requests around and hands them to new requests that share the same prompt prefix, so the shared part is computed once instead of once per request. vLLM’s implementation, documented in its prefix caching design note, is content-addressed: each full block is keyed by a hash of (parent block’s hash, the block’s token IDs, extra keys), which makes the key both position-dependent and content-dependent, exactly as correctness requires. SGLang’s RadixAttention (Zheng et al., arXiv 2312.07104) solves the same problem with a radix tree instead of a hash map, which handles branching prefixes naturally and enables cache-aware scheduling. The vLLM docs call it “almost a free lunch”: it does not change model outputs, and since vLLM V1 the overhead is small enough that it is on by default (enable_prefix_caching: bool = True in vllm/config/cache.py, verified at tag v0.26.0).

The operational sting is in the tail: a cache hit is per-replica. A router that treats inference pods as interchangeable will send the second turn of a conversation to a replica that has never seen the first, and pay a full prefill to recompute what another pod already holds. That is the entire reason Prefix-Cache-Aware Request Routing exists as a distinct concern.

Why This Exists: Prefill Is Recomputable, and Prompts Repeat

Generating a token requires the key and value vectors of every preceding token. Those vectors are a pure function of the token sequence up to that point — token i’s KV depends on tokens 1..i and nothing else. Two consequences follow, and the whole technique sits on them.

First, KV can always be recomputed rather than stored, which is why Preemption and Recomputation in LLM Serving can discard a victim’s cache and rebuild it. Second — the one that matters here — two requests that begin with the same tokens have bit-identical KV for that shared span. If one request has already computed it, the other never needs to.

Real traffic is drenched in shared prefixes. The vLLM feature page names the two canonical shapes (Automatic Prefix Caching):

• Long document query. The user asks many questions about the same manual, contract, or annual report. Without APC the document is prefilled on every question.
• Multi-round conversation. Turn n of a chat has turns 1..n−1 as its prefix by construction, so a 10-turn conversation without APC prefills turn 1 ten times.

Add a third that dominates production: a shared system prompt. Every request from an application carries the same few thousand tokens of instructions. Without APC that is a fixed prefill tax on every single request forever.

flowchart LR
    subgraph WITHOUT["Without prefix caching"]
        R1["Req 1<br/>[SYSTEM 2000 tok][Q1 20 tok]"] --> P1["prefill 2020 tokens"]
        R2["Req 2<br/>[SYSTEM 2000 tok][Q2 20 tok]"] --> P2["prefill 2020 tokens"]
        R3["Req 3<br/>[SYSTEM 2000 tok][Q3 20 tok]"] --> P3["prefill 2020 tokens"]
    end
    subgraph WITH["With prefix caching"]
        S1["Req 1"] --> Q1["prefill 2020 tokens<br/>+ cache 125 blocks"]
        S2["Req 2"] --> Q2["hit 125 blocks<br/>prefill ~20 tokens"]
        S3["Req 3"] --> Q3["hit 125 blocks<br/>prefill ~20 tokens"]
    end

The economics of a shared system prompt, at block size 16 (2000 tokens = 125 full blocks). What it shows: the marginal cost of a request collapses from 2020 tokens of prefill to roughly the length of the actual question. The insight to take: the saving is proportional to shared_prefix_length / total_prompt_length, so APC is transformative for short questions against long shared context and nearly worthless when every prompt is unique. Note also what it does not touch — see the Limits section: this is a prefill optimization and does nothing for decode.

The vLLM feature page is careful about the boundary: “APC only reduces the time of processing the queries (the prefilling phase) and does not reduce the time of generating new tokens (the decoding phase). So APC does not bring performance gain when vLLM spends most of the time generating answers.”

Mental Model: A Content-Addressed Cache Over the Block Pool

APC is a layer on top of PagedAttention and KV Cache Blocks, and the division of labour is clean. PagedAttention makes KV live in fixed-size, reference-counted blocks and lets a sequence’s logical blocks point anywhere physically. APC adds one thing: a map from content hash to physical block, plus the reference-counting discipline to make sharing safe.

flowchart TB
    subgraph LAYER2["APC layer -- content addressing"]
        MAP["cached_block_hash_to_block<br/>hash -> KVCacheBlock"]
        FQ["FreeKVCacheBlockQueue<br/>LRU order, doubly linked"]
    end
    subgraph LAYER1["PagedAttention layer -- physical blocks"]
        POOL["BlockPool<br/>num_gpu_blocks KVCacheBlock objects<br/>each with ref_cnt"]
    end
    subgraph REQ["Requests"]
        A["Request A<br/>block table"]
        B["Request B<br/>block table"]
    end
    A -->|"logical -> physical"| POOL
    B -->|"logical -> physical"| POOL
    MAP --> POOL
    FQ --> POOL
    A -.->|"shares blocks 0,1 with"| B

How the two layers compose. What it shows: the block pool is unchanged; APC is a hash map and an eviction queue over the same objects. The insight: because both requests’ block tables point at the same KVCacheBlock, a cache hit costs zero copying — it is a reference-count increment and a pointer write. This is the same mechanism the SOSP paper used for parallel sampling and beam search (Kwon et al. 2023), promoted from “within one request” to “across all requests.”

The critical difference from a naive cache is that the key must encode position, not just content. The block containing tokens ["the", "leaves", "as", "children"] has different KV depending on what came before it, because attention is causal — every token attends to all its predecessors. Hash the block’s own tokens alone and you would happily serve one request’s KV to another with a different preamble, silently corrupting the output.

The Hash Chain

vLLM’s answer is a chain: each block’s hash includes its parent’s hash, so the key transitively covers the entire prefix. From the design doc, with the example prompt “A gentle breeze stirred the leaves as children laughed in the distance” at block size 4:

                    Block 1                  Block 2                  Block 3
        [A gentle breeze stirred] [the leaves as children] [laughed in the distance]
Block 1: |<--- block tokens ---->|
Block 2: |<------- prefix ------>| |<--- block tokens --->|
Block 3: |<------------------ prefix -------------------->| |<--- block tokens ---->|

ASCII from the vLLM design document, reproduced because it is a token-span alignment diagram rather than a graph — a mermaid flowchart cannot express “this bracket covers those tokens.” The insight: block 3’s identity is not “laughed in the distance”; it is “laughed in the distance, given everything before it.”

The hash inputs, per the doc, are exactly three:

1. Parent hash value — the hash of the preceding block. This is what makes the chain.
2. Block tokens — the tuple of token IDs in this block. Included, in the doc’s words, “to reduce potential hash value collision” — the parent hash alone would leave collisions undetectable.
3. Extra hashes — anything else that makes the block distinct: LoRA adapter IDs, multi-modality input hashes, and cache salts for multi-tenant isolation.

The implementation in vllm/v1/core/kv_cache_utils.py at v0.26.0 is four lines of substance:

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))
    )

Two details reward attention. NONE_HASH is the sentinel for a first block — and it is not a constant. init_none_hash() sets it to os.urandom(32) unless PYTHONHASHSEED is set, deliberately mirroring Python’s own randomized hash(). That means block hashes are not reproducible across processes by default, which matters the moment you want to share a cache between replicas.

The hash_function is selectable via --prefix-caching-hash-algo, and the four options encode a real security/performance trade-off:

Algorithm	Serialization	Reproducible across versions/languages?	Notes
sha256 (default)	Python pickle	No — pickle output varies by Python/vLLM version	Cryptographically secure; the default since v0.11 per the design doc
sha256_cbor	canonical CBOR	Yes	Recommended for deterministic caching across environments
xxhash	pickle	No	128-bit, fast, not cryptographically secure
xxhash_cbor	canonical CBOR	Yes	Fast and reproducible; still non-cryptographic

The docs are explicit about the risk of the fast options: “Use of a hashing algorithm that is not considered cryptographically secure theoretically increases the risk of hash collisions, which can cause undefined behavior or even leak private information in multi-tenant environments.” A collision here does not corrupt a data structure — it serves one tenant’s KV cache to another tenant’s request, which is a confidentiality breach dressed as a performance optimization.

Cache Isolation and the Timing Side Channel

A subtler leak survives even a perfect hash. If tenant B’s request is faster when it shares a prefix with tenant A’s, B can probe: submit a candidate prompt, measure time-to-first-token, and learn whether that exact text is in someone else’s cache. vLLM’s answer is a per-request cache_salt, injected into the hash of the first block:

{
  "messages": [
    {"role": "system", "content": "You are a helpful assistant."},
    {"role": "user", "content": "Here is a document with details about the world series: ..."},
    {"role": "user", "content": "Who won the world series in 2020?"}
  ],
  "cache_salt": "your-cache-salt"
}

Because the salt enters block 0’s hash and every later block chains off block 0, salting the head re-keys the entire chain — one field isolates a whole tenant. The doc frames it as opt-in trust: “cache sharing is limited to users or requests that explicitly agree on a common salt, enabling cache reuse within a trust group while isolating others.” Give every tenant a distinct salt and you get full isolation; give a tenant’s fleet one shared salt and they get reuse among themselves.

Data Structures: Why It Costs Almost Nothing

APC was disabled by default in vLLM V0 because the bookkeeping cost real throughput when the hit rate was low. The V1 rewrite made it free enough to turn on: “In V1, we optimize the data structure for constant-time cache eviction and carefully minimize Python object creation overhead. This makes V1’s prefix caching introduce near-zero performance degradation, even when the cache hit rate is 0%” — measured at less than 1% throughput loss at a 0% hit rate (V1 blog).

Four structures, per the design doc and vllm/v1/core/block_pool.py:

@dataclass(slots=True)
class KVCacheBlock:
    block_id: int
    ref_cnt: int = 0
    _block_hash: BlockHashWithGroupId | None = None      # set when full+cached, reset on evict
    _block_hash_num_tokens: int | None = None
    prev_free_block: "KVCacheBlock | None" = None        # intrusive free-list links
    next_free_block: "KVCacheBlock | None" = None
    is_null: bool = False

• Block Pool — every KVCacheBlock is allocated once at startup, not on demand. The doc’s stated reason: “This avoids Python object creation overheads and can easily track all blocks all the time.” In an engine making a scheduling decision every decode step, per-step Python allocation is the thing you cannot afford.
• Free Block Queue — a doubly linked list threaded through the blocks themselves (prev_free_block / next_free_block) rather than a collections.deque. The doc gives both reasons: O(1) removal from the middle (needed when a cached block sitting in the free queue gets re-referenced by a hit) and no wrapper object per element. FreeKVCacheBlockQueue’s own docstring notes it “does not allocate any Python objects when manipulating the linked list.”
• Cache blocks — cached_block_hash_to_block, the hash → block map. In v0.26.0 this is a BlockHashToBlockMap that stores a bare KVCacheBlock for the common single-block case and only promotes to a dict[int, KVCacheBlock] when duplicates exist, explicitly “to reduce GC costs from the inner dict.”
• Request blocks — request ID → allocated block IDs.

Mechanical Walk-through: Allocate, Touch, Free, Evict

sequenceDiagram
    participant S as Scheduler
    participant M as KVCacheManager
    participant P as BlockPool
    S->>M: get_computed_blocks(request)
    M->>M: hash prompt tokens into block hashes
    M->>P: look up each hash in cached_block_hash_to_block
    P-->>M: longest matching prefix of blocks
    M-->>S: computed_blocks, num_new_computed_tokens
    S->>M: allocate_slots(request, num_new_tokens, new_computed_blocks)
    M->>M: 1. compute blocks needed, bail out if insufficient
    M->>P: 2. TOUCH computed blocks -- ref_cnt += 1, remove from free queue
    M->>P: 3. pop new blocks from HEAD of free queue (evicting if cached)
    M->>P: 4. cache any block that is already full
    M-->>S: KVCacheBlocks

The allocation path for a new request, from vllm/v1/core/kv_cache_manager.py and the design doc. What it shows: lookup and allocation are two separate calls, and the “touch” step sits between them. The insight to take: touching is not bookkeeping pedantry — a cached block that is still sitting in the free queue is an eviction candidate, and without the ref-count bump plus queue removal, step 3 could evict the very blocks step 1 just decided to reuse.

Eviction is LRU, taken from the head of the free queue, and involves three steps per the doc: pop the head, remove the block ID from the cache map, and reset the block hash. But the ordering discipline on free is the clever part:

“When a request is finished, we free all its blocks if no other requests are using them (reference count = 0)… the freed blocks are added to the tail of the free queue in the reverse order. This is because the last block of a request must hash more tokens and is less likely to be reused by other requests. As a result, it should be evicted first.”

Read that twice, because it is the whole eviction policy in one sentence. Blocks near the start of a request are short-prefix blocks — a system prompt’s first block is shared by every request in the system. Blocks near the end encode a long, specific prefix that probably only this one conversation will ever match. Freeing in reverse puts the low-value tail blocks nearest the eviction head. It is LRU with a prefix-length prior baked into the insertion order, and it costs nothing to implement. Contrast with the general-purpose adaptivity of Adaptive Replacement Cache, which learns recency-versus-frequency at runtime; here the structure of the workload hands you the right answer for free.

The design doc’s worked example (block size 4, 10 blocks total) is worth tracing for one moment in particular — Time 3:

“Request 1 comes in with the 14 prompt tokens, where the first 10 tokens are the same as request 0. We can see that only the first 2 blocks (8 tokens) hit the cache, because the 3rd block only matches 2 of 4 tokens.”

Ten tokens of genuinely shared prefix yield only eight tokens of cache hit. Hits are block-aligned: a partial match inside a block is no match at all, because only whole blocks have hashes. This is the single most common source of “why is my hit rate lower than my prefix overlap?” and it is a direct consequence of the block granularity chosen in PagedAttention and KV Cache Blocks. (v0.26.0 begins to soften this with a prefix_match_unit / hash_block_size split, letting hits land on finer boundaries inside a physical block for hybrid models — the config docstring calls it “the finest token boundary a prefix-cache hit can land on.”)

RadixAttention: The Tree Variant

SGLang attacks the same problem with a different structure. From Zheng et al. §3:

“Unlike existing systems that discard the KV cache after a generation request finishes, our system retains the cache for prompts and generation results in a radix tree, enabling efficient prefix search, reuse, insertion, and eviction.”

A radix tree is a compressed trie: edges are labelled with sequences of tokens rather than single tokens, so a long unbranched run is one edge instead of a chain of nodes (see Compressed Trie). That compression is what makes it practical here — a 2000-token shared system prompt is a single edge until something diverges from it.

flowchart TB
    ROOT(("root"))
    SYS["'You are a helpful assistant.'<br/>-- shared by every session"]
    T1["'User: Hello!<br/>Assistant: Hi!'"]
    T2["'User: What can you do?<br/>Assistant: I can ...'"]
    T3["'User: Solve this problem...'"]
    T4["'User: Write a story...'"]
    FEW["few-shot examples<br/>Q1/A1 Q2/A2 Q3:"]
    V1["'What ...'"]
    V2["'When ...'"]
    V3["'How ...'"]
    ROOT --> SYS
    ROOT --> FEW
    SYS --> T1
    SYS --> T3
    T1 --> T2
    T2 --> T4
    FEW --> V1
    FEW --> V2
    FEW --> V3

A radix tree mid-flight, following the paper’s Figure 3 scenario: two chat sessions sharing a system prompt, plus a batch of few-shot queries sharing an example block. What it shows: the shared system prompt is one node that every chat session hangs off, and a self-consistency batch (three samples of the same question) fans out from one shared parent. The insight: the tree makes branching first-class. vLLM’s flat hash map represents the same sharing implicitly — the three variants’ first blocks simply hash to the same value — but the tree makes the branch structure explicit and therefore schedulable, which is what §3’s cache-aware scheduler exploits.

The paper describes the dynamics precisely. When a new prompt shares only part of an existing edge, the node is split: “In step (4), a new chat session begins. The node ‘b’ from (3) is split into two nodes to allow the two chat sessions to share the system prompt.” SGLang’s radix_cache.py implements exactly that — _split_node() creates a new parent holding child.key[:split_len], re-parents the child onto it, and splits the stored hash values along the same boundary.

Eviction is LRU on leaves: “we introduce a simple LRU eviction policy that evicts the least recently used leaf first. By evicting leaves first, we enable the re-use of their common ancestors until those ancestors become leaves and are also evicted.” This is structurally the same insight as vLLM’s reverse-order free — evict the specific before the general — but here it falls out of the tree shape rather than needing a queue-ordering trick. Safety under continuous batching comes from a per-node reference counter: “each node maintains a reference counter indicating how many running requests are using it. A node is evictable if its reference counter is zero.” The current implementation (main branch, read 2026-08-08) generalizes this into a priority heap over evictable leaves (eviction_strategy.get_priority(node)), with last_access_time driving the default ordering via TreeNode.__lt__.

One design choice deserves its own note: SGLang does not partition memory between “cache” and “live requests.” From §3: “we do not preallocate a fixed-size memory pool as a cache. Instead, we let the cached tokens and the currently running requests share the same memory pool… When enough waiting requests run, the system will evict all cached tokens in favor of a larger batch size.” Cache retention is therefore automatically subordinate to admission — under load the system spends its memory on running work, which is the right priority and requires no tuning knob.

Cache-Aware Scheduling — the Part vLLM’s Hash Map Cannot Do

Having the tree buys something a flat map cannot: the order you run queued requests changes your hit rate. The paper defines the metric as number of cached prompt tokens / number of prompt tokens, then observes that “if the request scheduler frequently switches between different, unrelated requests, it can lead to cache thrashing and a low hit rate.” Their scheduler sorts the waiting queue by matched prefix length — longest-shared-prefix-first — and they prove it optimal offline:

Theorem 3.1. For a batch of requests, we can achieve an optimal cache hit rate by visiting the radix tree of the requests in the depth-first search order, with a cache size ≥ the maximum request length. The longest-shared-prefix-first order is equivalent to a depth-first search order.

The intuition is clean: DFS visits all of a subtree’s descendants before leaving it, so a shared prefix is loaded once and fully exploited before it becomes evictable. The paper is honest about the cost — “while greedy cache-aware scheduling can achieve high throughput, it can lead to starvation” — and defers fair-scheduling integration to future work. That trade is the same one Multi-Tenancy and Fairness in LLM Serving has to arbitrate: cache locality and fairness pull in opposite directions, because the fairest order is precisely the one that thrashes.

The overhead measurement is the reason this can be default-on: on a ShareGPT benchmark with no reuse opportunities, “it takes 74.3 seconds to run 100 requests; however, the time used for managing the RadixAttention data structures is only 0.2 seconds, which is a negligible overhead of less than 0.3%. This is because the complexity of tree operations is linear and small. Thus, we can turn on RadixAttention by default.”

Hash Map vs Radix Tree

	vLLM: content-hash map	SGLang: radix tree
Key structure	hash(parent_hash, tokens, extra) per full block	Path from root; edges carry token sequences
Match granularity	Block-aligned (16 tokens by default)	Token-aligned, floored to page_size
Lookup	O(blocks in prefix) hash probes	O(depth) tree descent
Branching prefixes	Implicit — siblings share a hash prefix	Explicit — a tree node with children
Eviction	LRU over a free queue, reverse-order insert on free	LRU (or priority heap) over evictable leaves
Safety under batching	ref_cnt on KVCacheBlock	lock_ref on TreeNode
Enables cache-aware scheduling	Not directly	Yes — longest-shared-prefix-first ≈ DFS (Thm 3.1)
Split-on-divergence	Not needed (blocks are atomic)	_split_node() on partial edge match

Neither is strictly better. The hash map is simpler and pairs naturally with fixed-size paging; the tree carries structural information that a scheduler can act on. In practice both engines converge behaviourally: both are LRU, both are reference-counted, both are on by default, and both are exact.

Failure Modes and Common Misunderstandings

“Identical prompt, so I should see a 100% hit rate.” You will not. get_computed_blocks() sets max_cache_hit_length = request.num_tokens - 1 with the comment: “When all tokens hit the cache, we must recompute the last token to obtain logits.” You need a forward pass over something to produce the next-token distribution. And because allocation is block-aligned, “recompute one token” can mean recomputing a whole trailing block.

“Cached blocks are deduplicated.” They are not, and this is deliberate. Because v1 block tables are append-only, when a request produces a full block whose hash already exists, vLLM does not rewrite the table to point at the incumbent — it keeps both. The design doc walks the ABCDEF/GHI trace: v0 would free the duplicate block 3 and remap to block 1; v1 cannot, so “we will have duplicated blocks for the hash key E-H. This duplication will be eliminated when the request is freed.” The BlockHashToBlockMap class comment is blunter: “We currently don’t de-duplicate the blocks in the cache… because we want to make sure the allocated block IDs won’t change so that block tables are append-only.”

“Partial blocks are cached.” Note 1 of the design doc: “We only cache full blocks.” A 2001-token system prompt at block size 16 caches 125 blocks and leaves one token homeless.

“Prefix caching will fix my latency.” It fixes time to first token, not inter-token latency — see Time to First Token and Inter-Token Latency. A workload dominated by long generations sees essentially nothing. Diagnose before enabling as a remedy.

Multimodal prompts need image identity in the key. After tokenization an image becomes a run of identical placeholder tokens, so two different images produce byte-identical token IDs. vLLM feeds the frontend image processor’s hash into extra_keys for exactly this reason; the doc walks a 41-placeholder example where all four blocks carry the same <image hash>. Get this wrong and you serve one user’s picture’s KV for another’s.

LoRA adapters partition the cache. The same tokens under a different adapter produce different KV, so the adapter ID is an extra key. A fleet serving many adapters therefore has a fragmented cache — see Model-Aware and LoRA-Aware Routing.

A cheap hash is a security decision. xxhash is faster and is not cryptographically secure; the docs say to weigh “your security risk tolerance against the performance benefits” before enabling it in a multi-tenant deployment.

Resolved 2026-08-15

Accidental collisions are astronomically improbable; the adversarial case is blocked by something the documentation never mentions — a per-process random secret at the head of the hash chain — and that protection is silently forfeited by any deployment that sets PYTHONHASHSEED. Four findings, all from the v0.26.0 source tarball plus xxHash upstream.

1. It is XXH3-128, unkeyed, and it is not the default. vllm/utils/hashing.py resolves the xxhash option to _xxhash.xxh3_128_digest(input_bytes) — the 128-bit XXH3 variant, called with no seed or secret argument — and vllm/config/cache.py sets prefix_caching_hash_algo: PrefixCachingHashAlgo = "sha256". xxHash is an optional dependency, and the source says why in a comment: “It is important that this remains an optional dependency. It would not be allowed in environments with strict security controls, so it’s best not to have it installed when not in use.” So the risky configuration is opt-in twice over — install the package, then pass the flag.

2. A collision is served silently, with no content check. BlockPool.get_cached_block() is a plain dictionary lookup: self.cached_block_hash_to_block.get_one_block(block_hash_with_group_id), returning the block or None. There is no comparison of token IDs after a hash match anywhere on the lookup path. That is the mechanism behind the docs’ “leak private information” wording — a colliding hash does not raise, it hands the other tenant’s KV block straight into the attention kernel.

3. The accidental rate is not a real risk. By the birthday approximation p ≈ n²/2¹²⁹, where n is the number of distinct block hashes in play: a Llama-3-8B server on an 80 GB card with ~60 GiB of KV cache and 16-token blocks holds about 30,720 resident blocks (2 MiB each at 8 grouped-query KV heads × 32 layers × 128 head dimension × 2 bytes × 2 tensors × 16 tokens), giving p ≈ 1.4 × 10⁻³⁰. Even counting every distinct block hash a busy replica computes in a year at 10,000 tokens/second — 625 blocks/s, about 2 × 10¹⁰ hashes — the probability is ≈ 6 × 10⁻¹⁹, roughly one in 1.7 × 10¹⁸. You would need about 1.8 × 10¹⁹ distinct blocks for an even-odds collision. Accidental collision is not the concern; the docs’ “even if collisions are still very unlikely” is an understatement.

4. The adversarial case turns on PYTHONHASHSEED, not on XXH3. init_none_hash() in vllm/v1/core/kv_cache_utils.py sets the chain’s root hash to NONE_HASH = BlockHash(os.urandom(32)) when PYTHONHASHSEED is unset, and hash_block_tokens() feeds (parent_block_hash, curr_block_token_ids, extra_keys) into the hash at every block — so every block hash in the server transitively depends on a 256-bit per-process random value. An attacker cannot compute any target block hash offline, which makes second-preimage construction impossible regardless of XXH3-128’s cryptographic weakness. But the offloading and disaggregation paths require the opposite: vllm/v1/kv_offload/tiering/fs/manager.py states PYTHONHASHSEED “must be set to the same fixed value” across nodes, and the peer-to-peer session client warns identically. Set it, and NONE_HASH becomes hash_fn(hash_seed) — fully derivable from a value that is typically a small integer in a Helm chart. A multi-tenant deployment that combines --prefix-caching-hash-algo xxhash with a fixed PYTHONHASHSEED and cross-node KV sharing is the one configuration where the theoretical risk becomes a real attack surface, because the attacker can then compute block hashes offline and search for a second preimage against a 128-bit non-cryptographic digest.

On XXH3-128 itself, the honest answer is nobody has published cryptanalysis, because nobody claims it is cryptographic. The upstream xxHash README makes only statistical claims — it “has been tested with Austin Appleby’s excellent SMHasher test suite, and passes all tests,” and its collision behaviour is “in line with the birthday paradox” — and its own comparison table reserves the label “Cryptographic” for BLAKE2, SHA-1 and MD5, never for XXH3 or XXH128. Absence of a published break is therefore not evidence of strength: an unkeyed non-cryptographic hash carries no second-preimage guarantee, so the correct posture is the one the source already encodes — keep sha256 in any multi-tenant deployment, and treat xxhash as a single-tenant throughput option.

The Operational Consequence: Cache Hits Are Per-Replica

Everything above happens inside one engine process. The hash map, the free queue, the radix tree — all of it is local state in one pod’s memory, describing one GPU’s HBM. Scale to N replicas behind a load balancer and the arithmetic turns hostile: with round-robin routing, a conversation’s second turn lands on the replica that holds its prefix with probability 1/N.

flowchart TB
    U["User: turn 2 of a conversation"]
    subgraph NAIVE["Round-robin router"]
        LB1["Service / round-robin"]
        RA1["Replica A<br/>HOLDS turn-1 prefix"]
        RB1["Replica B<br/>cold"]
        LB1 -->|"picks B"| RB1
        RB1 --> MISS["full prefill<br/>high TTFT"]
    end
    subgraph AWARE["Prefix-aware router"]
        EPP["Endpoint Picker<br/>tracks per-replica prefix state"]
        RA2["Replica A<br/>HOLDS turn-1 prefix"]
        RB2["Replica B<br/>cold"]
        EPP -->|"picks A"| RA2
        RA2 --> HIT["cache hit<br/>low TTFT"]
    end
    U --> LB1
    U --> EPP

The same request, two routing policies. What it shows: the cache is a property of a replica, so the routing decision and the cache-hit decision are the same decision. The insight to take: every engine-side optimization above can be nullified by an infrastructure component that knows nothing about it — this is the concrete instance of the parent MOC’s “the layers are not independent” theme.

SGLang anticipated this in the paper’s Appendix A.4, and the design is worth knowing because everything since is a variation on it:

“each worker maintains its own sub-tree, while the router oversees a meta-tree. This meta-tree acts as a trie that tracks all sub-trees and their associated devices. Upon the arrival of a new batch of requests at the router, prefix matching is executed on the meta-tree… Should an eviction occur at a worker node, it commits this eviction to a queue, which the router then processes to update the meta-tree during periods of low activity.”

Note the honesty about consistency: the router’s view is weakly consistent — evictions propagate lazily during idle periods, so the meta-tree is sometimes wrong. That is a deliberate trade, and it is fine, because a stale entry costs a cache miss rather than a correctness failure. They benchmarked four workers on MMLU and report “linear scaling and an optimal cache hit rate with minimal overhead from this weakly consistent distributed cache design,” while flagging the real tension: “There exists a trade-off between maximizing data locality and parallel processing efficiency.”

The Kubernetes-native version of this is the Endpoint Picker (EPP) pattern. The Gateway API Inference Extension defines an EPP as “a data-plane component that communicates via the Envoy external processing protocol, and acts as the Router. It intercepts incoming inference requests and routes each request to the optimal model server replica,” using “Metrics and Capabilities… Includes things like Prefix Cache status or LoRA Adapters availability.”

Resolved 2026-08-15

The migration has settled, and the prefix-aware scorer’s configuration surface is now readable. Re-checked on 2026-08-15. The kubernetes-sigs/gateway-api-inference-extension README now states the split precisely: the Endpoint Picker, the InferenceObjective and InferenceModelRewrite APIs, and the Body Based Router moved out — EPP and its APIs to llm-d/llm-d-router, BBR to llm-d/llm-d-inference-payload-processor — and “no new code will be accepted to these packages in this repository, and they will be archived soon” (the move was decided in GIE issue #2430). What upstream keeps is the InferencePool API, the Endpoint Picker Protocol definition, a reference lightweight EPP (LWEPP) “for conformance test purposes,” and the conformance suite. The llm-d side also renamed itself: “the Inference Scheduler has been renamed to llm-d Router.”

Reading llm-d/llm-d-router at tag v0.9.0 gives the plugin names and knobs the 404-ing docs page could not. Prefix-aware routing is not one component but a producer/scorer pair, wired through a plugin graph:

Plugin type	Role	Key parameters
prefix-cache-scorer	The scorer itself; Category() returns Affinity	prefixMatchInfoProducerName — only this; it names which producer to consume
approx-prefix-cache-producer	Default producer. Guesses replica cache state from the requests the router itself has sent	autoTune (default true), blockSizeTokens (default 16, matching vLLM’s), maxPrefixTokensToMatch (default 131072), lruCapacityPerServer (default 31250), maxPrefixBlocksToMatch (deprecated, 2048), blockSize (deprecated, characters)
precise-prefix-cache-producer	Consumes the engine’s actual KV-cache event stream	tokenProcessorConfig, indexerConfig, kvEventsConfig, speculativeIndexing, speculativeTTL
prefix-cache-affinity-filter, precise-prefix-cache-scorer	Alternative filter/scorer forms of the same signal	—

The scorer having exactly one knob is the design’s whole point: all the tuning lives in the producer, and swapping approximate for precise changes the data source without touching the scorer. Configuration is a CRD-shaped document (apiVersion: llm-d.ai/v1alpha1, kind: EndpointPickerConfig) passed to the EPP through --configFile or --configText, listing plugins and then schedulingProfiles that reference them by pluginRef with a scorer weight (defaulting to 1.0); docs/architecture.md walks a complete example that wires precise-prefix-cache-producer to prefix-cache-scorer at weight: 50. Note also that approx-prefix-cache-producer is in the auto-injected default set, so prefix-aware scoring works with no producer configured at all — the precise variant is the opt-in.

The default lruCapacityPerServer of 31,250 is worth reading for what it reveals: a source comment derives it from Llama-3-8B on an H100 80 GB — 16 GB of weights, 64 GB left for KV, ~128 KB per token, vLLM’s 16-token blocks. (The comment’s own arithmetic slips mid-sentence from “500K tokens” to “250K / 16 = 31.25K blocks”; the shipped constant follows the second figure.) The sizing note is explicit about the trade-off: “a small capacity ensures a high accuracy of cache hit on the model server, but it will increase the chance of false negatives. A high capacity does the opposite.”

This also closes the loop with the engine side described next: precise-prefix-cache-producer’s kvEventsConfig is the consumer of exactly the BlockStored / BlockRemoved stream that vLLM’s block_pool.py emits.

The engine side of that contract is already in place. vLLM v0.26.0 emits KV cache events — BlockStored (with block_hashes, parent_block_hash, token_ids, block_size, lora_id, group_idx) and BlockRemoved — precisely so an external consumer can maintain a meta-tree. block_pool.py has a dedicated emit_cached_block_events() whose docstring says it exists so that “external consumers (e.g. gateway) can learn about reused blocks,” and KVCacheManager gates it on kv_cache_report_mode == "full". That is the engine publishing its cache index to the router — SGLang’s meta-tree, rebuilt as an event stream.

This is also where the non-reproducible NONE_HASH bites. If two replicas seed NONE_HASH from os.urandom(32), the same prompt hashes differently on each, and any scheme that compares hashes across replicas breaks. Set PYTHONHASHSEED and use a CBOR variant if you intend to share or compare hashes between processes — the docs recommend sha256_cbor “for deterministic caching across environments,” and init_none_hash() logs a warning when a CBOR hash function is selected without PYTHONHASHSEED set.

Alternatives, Extensions and Related Work

Tiering the cache instead of evicting it. SGLang’s HiCache (Hierarchical KV Caching) extends the radix cache across the memory hierarchy — GPU HBM, host DRAM, and a storage backend — so an evicted prefix is demoted rather than destroyed. TreeNode carries host_value, host_ref_counter, protect_host() / release_host(), and write_through_pending_id, which is the demotion machinery visible in the data structure. The paper’s own future work anticipated this: “adapting RadixAttention to operate across multiple levels of the memory hierarchy (e.g., DRAM, Disk).” See KV Cache Offloading and Tiering.

Moving the cache instead of the request. If the prefix lives on replica A and the request must run on replica B, an alternative to routing is transferring the KV — the domain of KV Cache Transfer and Connectors and a prerequisite for Prefill-Decode Disaggregation. It trades a network transfer for a prefill; whether that wins depends on interconnect bandwidth versus prefill FLOPs.

Explicit provider-side prompt caching. Hosted APIs expose a user-facing version of the same idea, and the vLLM design doc notes prefix caching “has been widely used by many public endpoints (e.g., OpenAI, Anthropic, etc.).” The mechanism differs in one important way: rather than hashing implicitly, the caller marks a cache breakpoint — in Anthropic’s API a cache_control: {"type": "ephemeral"} marker on a content block, with a 5-minute default time-to-live or an optional 1-hour variant, and distinct billing rates for cache writes versus cache reads (Anthropic prompt caching docs). The shared invariant is the one that matters: it is a prefix match, so any byte changed anywhere in the prefix invalidates everything after it — which is why a timestamp interpolated into a system prompt destroys the cache for the entire request.

Production Notes

The strongest published evidence is SGLang’s own deployment. From §6.2: “SGLang has been deployed in Chatbot Arena to serve open-weight models. Due to low traffic for some models, only one SGLang worker serves each. After one month, we observed a 52.4% RadixAttention cache hit rate for LLaVA-Next-34B and 74.1% for Vicuna-33B. Cache hits come from common system messages, frequently reused example images, and multi-turn chat histories. This reduces first-token latency by an average of 1.7× for Vicuna-33B.”

Three things to take from that. The hit rates are high — half to three-quarters of prompt tokens served from cache on real traffic. The sources are exactly the three the theory predicts (system messages, reused inputs, conversation history), not exotic patterns. And the payoff lands where the theory says it will: on first-token latency.

The ablation (Figure 8a/b) confirms the causal chain on a tree-of-thought benchmark: higher hit rate → larger batch size → higher throughput and lower latency. The batch-size link is the one people miss — a cache hit does not only skip computation, it frees the blocks that computation would have occupied, which raises the batch the scheduler can admit. That is the same coupling Sizing the KV Cache and Continuous Batching describe from the other side.

Operational advice that follows from all of the above:

• Instrument hit rate, not just latency. vLLM tracks PrefixCacheStats (num_tokens, num_hits, and whether the request was previously preempted) and exposes KVCacheManager.usage() for pool occupancy. A hit rate well below your expected prefix overlap usually means block misalignment, an unstable prefix (a timestamp in the system prompt), or a router that ignores locality.
• Keep the shared prefix byte-stable and first. Anything variable — timestamps, request IDs, per-user preamble — belongs after the shared span, because a single differing token re-keys every block from that point on.
• enable_prefix_caching is True by default in vLLM v0.26.0 (latest stable on PyPI as of 2026-07-25). Turning it off is the deliberate act now, and is rarely right: the measured cost at a 0% hit rate is under 1% throughput.
• Decide the hash algorithm deliberately in multi-tenant deployments. Default sha256 unless you have measured hashing to be a bottleneck; sha256_cbor when hashes must be comparable across processes; xxhash* only with an explicit risk acceptance.
• Pair APC with prefix-aware routing or accept losing most of it. Per-replica caching plus locality-blind load balancing is the single most common way a well-tuned engine underperforms in production.

See Also

• LLM Inference Serving MOC — the parent map; this note is §6’s cross-request half
• PagedAttention and KV Cache Blocks — the block layer APC is built on; owns the block table, reference counting, and copy-on-write
• Prefix-Cache-Aware Request Routing — the infrastructure that stops a router from throwing these hits away
• SGLang and RadixAttention · vLLM Architecture — the two engines compared here
• KV Cache Offloading and Tiering · KV Cache Transfer and Connectors — where evicted or remote prefixes go
• Sizing the KV Cache · Continuous Batching · The Inference Request Scheduler — why a hit raises batch size, not just skips work
• Time to First Token and Inter-Token Latency — the metric APC actually moves
• Gateway API Inference Extension · llm-d and Distributed Inference Orchestration — the Kubernetes-side consumers of KV cache events
• Multi-Tenancy and Fairness in LLM Serving — cache locality versus fair scheduling, and the cache_salt isolation boundary
• Adaptive Replacement Cache — a general adaptive eviction policy, for contrast with the prefix-length prior used here
• Compressed Trie — the data structure RadixAttention specializes
• Linux Memory Management MOC — owns Demand Paging, Copy-on-Write and fork and The LRU Lists, whose ideas both engines reimplement