--- title: "Prefix cache hash collision probability" description: "Calculate prefix-cache collision probability for 128-bit and 256-bit hashes, then separate random risk from attacks, salts, and serialization." canonical_url: "https://fanout.sh/blog/prefix-cache-hash-collision-probability" md_url: "https://fanout.sh/blog/prefix-cache-hash-collision-probability.md" last_updated: "2026-10-02" access: "public" --- # Prefix cache hash collision probability Calculate prefix-cache collision probability for 128-bit and 256-bit hashes, then separate random risk from attacks, salts, and serialization. - Author: Suraj Gaud - Published: 2026-10-02 - Track: Inference engineering - Access: Public - Tags: prefix caching, KV cache, hash collisions, vLLM, SHA-256, xxHash, multi-tenancy Prefix cache hash collision probability depends on the number of cached blocks and the digest width. It does not depend directly on the number of prompts. For random inputs, a 128-bit digest can have negligible accidental risk at practical cache sizes. That does not make a non-cryptographic hash safe against a tenant choosing inputs to force a collision. A useful deployment review separates accidental collisions from adversarial resistance, then asks which tenants may share cache entries. ## Prefix cache hash collision probability formula vLLM identifies each full KV-cache block from its parent block hash, the tokens in the current block, and extra identity values. The current[vLLM prefix-caching design](https://docs.vllm.ai/en/latest/design/prefix_caching/)lists LoRA IDs, multimodal hashes, and cache salts among those extra values. If n independent cached block hashes are uniformly distributed across a b-bit space, the probability of at least one accidental collision is approximately 1 minus exp of negative n times (n minus 1), divided by 2 times 2 to the power b. When that probability is small, use the simpler approximation n times (n minus 1), divided by 2 times 2 to the power b. Count block hashes that can meet in the same lookup namespace. Do not put prompt count into the formula without converting prompts to full blocks. Suppose a cache holds 50,000 prompts averaging 400 cached tokens with a 16-token block size. That is about 25 blocks per prompt, or 1.25 million cached block hashes. For a 128-bit digest, the accidental any-pair probability is about 2.3 times 10 to the negative 27. For a 256-bit digest, the same cache has a probability near 6.7 times 10 to the negative 66. Those figures assume uniform random outputs and one shared set of 1.25 million live hashes. Separate servers with separate lookup tables do not create one fleet-wide birthday set. Fanout's[prefix match unit guide](/blog/prefix-match-unit-vs-kv-cache-block-size)explains why only full blocks are reusable. That same block count is the n used here. ## Resident risk and incoming-request risk differ The birthday formula asks whether any pair among n resident hashes collides. An operator may instead ask how long it takes new messages to hit any resident hash. If the resident set contains K hashes and each new message contributes m independent hashes, the approximate hit probability per message is m times K divided by 2 to the power b. With K = 1.25 million, m = 25, and b = 64, the expected number of messages before a random hit is about 590 billion. This works out to roughly 2 to the power 39 messages. The precise result changes with block count, cache turnover, repeated prefixes, and whether hashes are independent. The[vLLM security advisory for CVE-2025-25183](https://github.com/vllm-project/vllm/security/advisories/GHSA-rm76-4mrf-v9r8)used a related workload estimate to explain the old built-in-hash risk. It also made the important distinction that a predictable construction can make malicious collisions more feasible than the random calculation suggests. For a 128-bit digest with the same K and m, the random expectation rises to roughly 1.1 times 10 to the power 31 messages. That number is useful for accidental-failure budgeting. It is not a security proof for xxHash or any other non-cryptographic function. ## Non-cryptographic hashes change the threat model Current vLLM offers SHA-256 and 128-bit xxHash variants. Its design document warns that the xxHash options can cause undefined behavior or leak private information in multi-tenant environments. The issue is not merely digest width. A cryptographic hash is designed to resist attackers who select inputs after studying the function. A fast general-purpose hash is designed for speed and distribution on ordinary inputs. A random 128-bit value has strong birthday arithmetic. An attacker does not have to behave like a random generator if the hash structure gives them a cheaper path. The[Cache Me Catch You paper](https://www.ndss-symposium.org/wp-content/uploads/2026-f2812-paper.pdf)demonstrates how weak or truncated cache-key constructions can poison LLM caches. It shows the consequence of a prefix collision: a request can reuse KV state produced from different tokens, so later generation is conditioned on the wrong cached state. A prefix-cache collision is not equivalent to an ordinary hash-table bucket collision. The cache treats the digest as content identity and may not compare all original tokens again. Use SHA-256 when prompts cross a trust boundary. The additional random-risk margin is almost beside the point. The cryptographic construction is what protects against chosen-input attacks. Use xxHash only when inputs are trusted, the service is single tenant, and measurement proves hashing is a meaningful bottleneck. ## Cache salt solves a different problem A cache salt does not increase a 128-bit digest to 256 bits. It changes which requests are allowed to produce the same identity chain. vLLM mixes cache_salt into the first block hash. Requests with different salts cannot share later prefix blocks because each child includes its parent hash. The current[vLLM security guidance](https://github.com/vllm-project/vllm/blob/main/docs/usage/security.md)recommends a secret random salt scoped to the desired isolation boundary. A per-user salt prevents cross-user reuse. A per-organization salt permits reuse inside one organization but blocks sharing with other organizations. That choice trades hit rate for isolation. Per-user salts create more cache namespaces than per-tenant salts, so common system prompts shared across users will occupy separate blocks. Salt also reduces timing-side-channel exposure. Without isolation, a caller may infer that another caller used a prefix by observing a faster time to first token on a cache hit. Salt is not a substitute for SHA-256. Two tenants with the same salt still share one collision domain, and a guessable salt does not stop a tenant who can reproduce it. Treat the salt as a secret identity boundary. Treat the hash algorithm as the content-integrity boundary. Configure both in a multi-tenant service. ## Serialization affects reproducibility vLLM exposes four current choices: sha256, sha256_cbor, xxhash, and xxhash_cbor. The plain variants serialize the input with Python pickle. The CBOR variants use canonical CBOR before hashing. SHA-256 and sha256_cbor have the same digest width and cryptographic collision resistance. They can still produce different bytes for the same logical components because their serialization formats differ. Choose the CBOR variant when hashes must be reproducible across languages or environments. Choose the pickle variant when the cache lives inside one compatible Python and vLLM deployment. Do not expect cache hashes to survive an upgrade unless the serialization and all identity components remain stable. A harmless hash miss loses reuse, while an incorrect match threatens correctness. The current implementation also includes the parent hash and exact block tokens. That makes position and content part of the key rather than hashing each block's tokens in isolation. Multimodal inputs add another identity question. A placeholder token sequence is not enough to distinguish two images, so the media identity must enter the extra hash values. Fanout's[PagedAttention guide](/blog/pagedattention-vllm-kv-cache)covers the physical blocks being reused. Hash identity decides whether two logical prefixes may point to the same stored KV block. ## Benchmark the whole block-hash path Hash microbenchmarks can overstate or understate the serving cost. Serialization, tuple construction, parent chaining, and block size all sit around the digest call. Current[vLLM benchmark documentation](https://docs.vllm.ai/en/v0.16.0/benchmarking/cli/)lists two scripts for this decision. benchmark_hash.py measures representative hash calls. benchmark_prefix_block_hash.py runs the full prefix-block hashing path across fake blocks. Run the second benchmark with the block size and prompt-length distribution used in production. Compare sha256 with xxhash on the exact vLLM and Python versions you deploy. Then measure end-to-end prefill latency and CPU utilization with prefix caching enabled. A faster digest may not change useful throughput if GPU prefill or scheduling dominates. Keep cache hit rate in the result. Switching serialization or salt scope can cause cold misses that cost much more than the nanoseconds saved inside a hash function. Do not copy an old per-token overhead number into a capacity plan. vLLM now ships multiple serializers and digest implementations, and their relative cost depends on payload shape and runtime. ## A deployment decision with worked numbers Start by estimating the maximum live block count per lookup table. If a worker can hold 1.25 million full blocks, the accidental risk for a uniform 128-bit digest is about 2.3 times 10 to the negative 27. For a private single-tenant batch service, that random risk may be acceptable. Benchmark xxhash and sha256, then choose the faster option only if the difference affects the target workload. For a public multi-tenant endpoint, random risk is the wrong deciding metric. Use SHA-256 because tenants can choose prompts, and set a secret cache_salt for each isolation group. Use sha256_cbor when cache identity must be deterministic across languages or process versions. Otherwise the default sha256 path avoids adding an optional serialization dependency. Record four values in the review: live block count n, digest width b, whether callers control inputs, and the salt-sharing boundary. Also record how collision failures surface. Wrong output, cross-request state reuse, and privacy leakage are harder to detect than a cache miss. Prefix cache hash collision probability is easy to calculate for random values. Random probability alone cannot decide a deployment where an attacker controls inputs and shares the cache namespace. --- This representation contains public Fanout content only. Protected Pro lessons, account data, billing, checkout, and pricing are not included. Browse the public content map: https://fanout.sh/sitemap.md