Prefix cache miss attribution guide

Prefix cache miss attribution starts after the cached-token counter. That counter shows where reuse ended, but not why the next block missed.

An early token difference and an evicted block can produce the same cached-token count. The first needs an application fix. The second needs capacity, routing, or offload work.

Start with the first uncached block, then check its identity and recent lifecycle. Do not guess from a low hit rate or expose raw prompts in production logs.

Prefix cache miss attribution

vLLM reports cached prompt tokens per request, so an operator can see the length of the longest reused prefix.

An open vLLM diagnostics proposal points out the missing field: why the following block was not reused.

The proposal separates an evicted hash from no recent matching hash. It also proposes reporting the kinds of extra values mixed into the hash, without reporting their values.

That distinction is not a shipped guarantee. The issue remains a feature request, so deployments need to verify their version and may need external cache-event correlation.

Fanout's prefix match unit guide covers where a hit may end. Attribution explains why it ended at that boundary.

Exact prefix identity is more than text

The vLLM automatic prefix-caching design builds a block hash from the parent hash, the block's token IDs, and extra hashes.

Those extra inputs can include a cache salt, LoRA adapter identity, and multimodal input hashes.

Changing any component changes the block key. Because each later block includes the parent hash, one early difference changes every descendant key.

This is why a timestamp inserted near the start of a system prompt can destroy reuse for the entire tail.

It is also why identical visible text can miss. A different salt, adapter, image, tokenizer, chat template, or model configuration may produce a different cache identity.

Label that outcome no match, not prompt divergence, until the extra-key kinds and token IDs have been compared.

Fanout's cache salt guide explains how one deliberate namespace change propagates through the full hash chain.

Work the same 640-token symptom

Suppose vLLM uses 16-token blocks. A repeated 2,048-token scaffold contains 128 full blocks.

The new request reports 640 cached tokens. The first 40 blocks hit, and block 40, using zero-based numbering, is the first uncached block.

In the divergence case, one token inside block 40 changed. That block receives a new hash, and every later block inherits a new parent hash.

In the eviction case, block 40 has the same expected hash but is no longer resident. Prefix lookup still stops at that first missing block.

Both requests report the same 640 cached tokens. The cached-token metric cannot distinguish them.

A third case is possible: block 40 still exists on another replica or storage tier, but the current route cannot retrieve it before lookup completes.

That is neither token divergence nor local eviction in the broad operational sense. Treat routing and tier reachability as separate attribution labels.

The Modular prefix-caching guide also stresses exact prefix identity and finite cache capacity.

Those two facts create the ambiguous symptom. Exact matching can fail while capacity is healthy, and eviction can fail while the prompt is byte stable.

Start with the first uncached block

Record the number of cached tokens, the engine's block size, and the index of the first uncached full block.

Then record the expected hash for that block and the extra-key kinds that participated in it. Keep secret salts and customer data out of logs.

Check whether the exact hash is resident on the selected worker. If it is, investigate a lookup, ownership, or synchronization failure rather than ordinary capacity pressure.

If it is absent, check a bounded recent-eviction set or a stream of cache store and remove events.

A recent exact-hash eviction supports the eviction label. No such event supports no match only within the retention window of that diagnostic history.

Older evictions age out. Process restarts lose local history. Dropped events can also turn a real eviction into an unknown result.

Use three labels when the evidence is incomplete: evicted, no recent match, and unknown. A binary classifier will overstate certainty.

The vLLM proposal deliberately names the second class no_match because extra hashes can differ even when prompt text does not.

Compare a known-good request safely

To test divergence, capture a reference request in staging or CI under the same tokenizer, chat template, model revision, adapter, multimodal inputs, and salt scope.

Compare token IDs block by block. Stop at the first different token and report its index, not the surrounding customer text.

If the token blocks match, compare only the names and stable digests of allowed extra-key inputs.

For example, report that cache_salt participated and its digest differed. Do not print the salt itself.

The feature proposal suggests an optional decoded snippet around the first differing token. That should remain an explicit privacy opt-in, not a default production log.

Raw prompts can contain customer data, credentials, retrieved documents, and tool output. Hashes can also become sensitive when low-entropy values are guessable.

Use keyed or access-controlled diagnostics, short retention, and restricted debug paths. Attribution does not justify building a second prompt archive.

In CI, synthetic fixtures are safer. Serialize the same tool definitions twice, reorder one field, inject one timestamp, and verify the expected first differing block.

Separate routing from eviction

A local miss does not prove that the fleet lost the block.

Prefix-aware routing may send the request to a worker that already holds the longest prefix. Round-robin routing may send it to a cold replica.

The llm-d KV-cache index consumes engine events to track which blocks live on which workers and offload tiers.

That fleet view supports two extra questions: did another worker have the exact block, and was the chosen route expected to reach it?

If another worker held the block, classify the miss as a locality or routing miss before changing the eviction policy.

If an offload tier promised the block but failed to deliver it, report a stale-index or transfer failure. Recomputing the prefix may keep the request correct while hiding the cache-system fault.

Correlate the route decision, cache index version, local lookup, transfer attempt, and recomputation in one request trace.

Without that join, a dashboard can blame memory pressure for misses caused by replica churn or stale ownership data.

Read capacity pressure as evidence, not proof

Eviction rate, free blocks, prefix-cache occupancy, and preemption counters make eviction more plausible. They do not identify the reason for one request.

The prefix-cache eviction study found that LRU remains a strong baseline on two production traces because reuse often follows active session recency.

It also found heavy-tailed session footprints and position-dependent miss costs. One large session can create pressure, and a deep miss can cost more than an early miss.

Use that context after attribution. If exact hashes were evicted, ask whether the cache is undersized, routing fragments reuse, one-hit prefixes crowd the pool, or tier promotion misses its deadline.

Do not begin by replacing LRU. The study evaluated 14 policies and found that most sophisticated alternatives did not improve on LRU across the tested traces.

The immediate fix may be a larger pool, prefix-aware routing, quick demotion of one-hit data, or different retention for expensive deep blocks.

Choose among them with trace replay. A global hit-rate increase can still leave costly deep misses untouched.

Fix each attribution class differently

For token divergence, stabilize serialization. Put reusable system text and tool schemas before volatile values, and append request-specific data later.

Remove timestamps, random IDs, and unstable object ordering from the reusable prefix unless the model needs them there.

For an extra-hash mismatch, fix the identity boundary only if the security and model contract permit sharing.

Do not merge cache salts across tenants or ignore adapter identity to recover hit rate. A miss can be the correct result of isolation.

For eviction, size the cache from a workload trace, reduce one-hit pollution, add a tier, or route requests toward existing state.

Fanout's prefix retention guide shows why cache lifetime and reusable boundaries must be measured together.

For routing misses, compare the value of locality against queue depth. Sending every request to the warmest worker can create a new latency tail.

For stale-index or transfer failures, repair the event path and add a recompute label. Silent fallback keeps correctness but makes the cache look healthier than it is.

Build the attribution record

Emit one compact record per sampled request or per miss, with access controls appropriate to production diagnostics.

Include cached tokens, prompt tokens, block size, first uncached block, model and tokenizer revisions, worker identity, and route decision.

Add the first-miss hash digest, extra-key kinds, local residency result, recent-eviction result, and cache-index ownership result.

Record whether a remote lookup was attempted, completed, timed out, or returned stale ownership. Finish with recomputed tokens and TTFT.

Use the record to calculate miss counts and avoided-prefill loss by attribution class.

Break the metrics down by route, tenant isolation policy, adapter, model revision, and prompt template version without placing raw identities in labels.

High-cardinality hashes belong in sampled traces, not time-series labels.

Set an unknown budget. If too many misses cannot be classified because eviction history expires or events drop, improve the evidence before automating a fix.

Prefix cache miss attribution is complete when one short cache hit leads to one supported cause and one relevant owner.

Application teams fix divergence, platform teams handle eviction and transfer, and routing teams handle locality. None of those fixes should weaken a security boundary to recover hit rate.