Prefix cache eviction attribution window

A prefix cache eviction attribution window decides how long an operator can distinguish an evicted block from a key that was never seen.

Keep the window too short and old evictions become false no-match diagnoses. Keep it too long and a small diagnostic set becomes a large, expensive index.

Size it from the eviction event rate and the delay between eviction and the later failed lookup. Do not copy the cache TTL or the average session length.

Prefix cache eviction attribution window

An open vLLM diagnostics proposal suggests tracking a small bounded set of recently evicted hashes.

If the first uncached block's key appears in that set, the request can report evicted. If it does not, the proposal uses no_match because tokens or extra hash inputs may differ.

That label is time bounded. An exact key evicted before the set's retention window also appears absent, even though eviction was the historical cause.

The window therefore controls evidence coverage, not cache behavior. It should not change which blocks the engine keeps or which prompts can share state.

Fanout's prefix hash collision guide explains the key identity. This post focuses on how long to retain the eviction evidence.

Measure diagnostic delay

For each evicted key that is later requested, measure the time from eviction to the first failed lookup for that same key.

Build a distribution of those delays. A two-minute window covers an event only when the later miss arrives within two minutes.

Choose a target evidence coverage, such as 99 percent of attributable eviction misses. Then select the smallest window that reaches that target in trace replay.

Do not substitute session duration. The recent prefix-cache trace study found a 55-second median session and a roughly four-hour 99th percentile in its production traces.

Those figures describe that study's sessions, not the delay between one eviction and one later lookup in your service.

The same paper found that reuse is strongly session bounded and often short. That supports measuring recent windows, but it does not supply a universal retention value.

Split the distribution by worker, workload, cache tier, and route. A remote tier or delayed agent turn can create a longer diagnostic delay than a local chat loop.

Size the bounded set

Let E be peak eviction events per second, W be retention seconds, S be measured bytes per stored entry, and L be the target hash-table load factor.

The first memory estimate is E times W times S, divided by L.

Assume a replica emits 50,000 evictions per second at the planning peak. A 120-second window retains up to six million entries.

If the measured entry cost is 24 bytes and the table targets an 0.8 load factor, the estimate is 180 million bytes, or about 171.7 MiB.

Extending the same design to 15 minutes raises the estimate to about 1.26 GiB. Window length scales memory linearly before allocator and bucket overhead.

The 24-byte entry is illustrative. Measure the real digest, timestamp or bucket reference, table metadata, allocator slack, and replication cost.

If full hashes are too expensive, test a shorter keyed digest against the allowed false-attribution rate. A collision here can falsely label no_match as evicted.

Do not treat a probabilistic filter as exact evidence without reporting its false-positive behavior. A Bloom filter may save memory but cannot delete arbitrary old entries without rotation.

Use time buckets for expiry

A ring of time buckets makes the retention bound explicit. For a 120-second window, twelve ten-second buckets hold the recent eviction digests.

Insert each digest into the current bucket. When the ring advances, clear the bucket that just aged out.

A lookup checks the live buckets. The oldest event can remain slightly longer than 120 seconds because expiry is bucket-granular.

Smaller buckets reduce that error but add more bucket probes or merge work. Pick a granularity that is small relative to the evidence window.

Keep a worker epoch with the ring. A process restart creates a new epoch and destroys local eviction history even if the wall clock remains inside the nominal window.

Use a monotonic clock for expiry. Wall-clock corrections should not extend or collapse the diagnostic history.

For a fleet-wide view, shard by the worker that owned the block. One global set without ownership can blame the selected worker for an eviction that occurred on another replica.

Preserve four outcomes

The result should not be a binary evicted or no_match flag.

Report resident when the exact key still exists where the lookup expected it. That points to lookup, ownership, or synchronization trouble.

Report evicted when a trustworthy recent event exists for the same key and owner epoch.

Report no recent match when the key is absent and the event history is complete for the full retention window.

Report unknown when the event stream has a gap, the worker restarted, the lookup exceeded retained history, or the owner cannot be established.

The vLLM proposal adds lookup_limit for a different case. vLLM may recompute the final prompt token for logits, so an unprobed block boundary is not a miss.

These outcomes keep uncertainty visible. Collapsing unknown into no_match makes event loss look like an application serialization bug.

Fanout's prefix retention guide covers how long reusable state survives. Diagnostic evidence needs its own clock.

Detect dropped and reordered events

The llm-d cache architecture consumes vLLM KVEvents for every block creation and eviction, then maps hashes to workers and memory tiers.

Add a per-worker sequence number and epoch to that stream. A jump in sequence numbers marks a range where attribution evidence is incomplete.

Do not count the stream as healthy merely because events are arriving now. A gap that overlaps the retained window affects every later lookup whose eviction could have occurred inside it.

Track consumer lag too. An event still queued outside the attribution service looks missing until it is processed.

Define a maximum accepted lag below the lookup path's wait budget. If the consumer falls behind, return unknown rather than blocking inference for a diagnostic answer.

Reordering needs a bounded grace period. An event that arrives after its corresponding miss can update an offline trace, but a synchronous evicted label still requires the lookup to wait.

Store event coverage as intervals. That makes the unknown decision a check against evidence completeness instead of a guess from queue health.

Keep the record privacy safe

The diagnostic set needs a cache-key digest, owner, epoch, and expiry bucket. It does not need prompt text.

Extra hash inputs can include cache salt, LoRA identity, and multimodal data. Report input kinds, not secret values.

Use a keyed digest if low-entropy inputs make offline guessing practical. Rotate the diagnostic key with a versioned epoch so old and new digests are never compared as equal.

Keep high-cardinality digests in restricted traces, not metric labels. Aggregate metrics should contain counts by outcome, worker, model, and policy version.

The top-ranking Furiosa prefix-cache documentation shows that eviction can differ by cache type in hybrid models.

Include the cache group or state type in the attribution record. One digest marked evicted for sliding-window state does not prove that every full-attention block disappeared.

Validate the window before shipping it

Replay a known key inside the window and verify evicted. Replay it after expiry and verify that the result becomes unknown unless complete older history exists elsewhere.

Drop one event sequence range and verify that affected lookups never become no recent match.

Restart a worker, reuse the same logical identifier with a new epoch, and verify that old eviction evidence cannot cross the restart.

Test two owners with the same block digest. An eviction on worker A must not explain a miss on worker B unless the system models shared ownership.

Test lookup_limit at exact block boundaries so intentional recomputation never becomes an eviction diagnosis.

Measure set memory, insert cost, lookup latency, consumer lag, bucket expiry time, and the share of misses that remain unknown.

Increase the window only when trace replay shows that the extra evidence changes a useful fraction of outcomes. Longer retention without better decisions is metadata accumulation.

A prefix cache eviction attribution window is credible when it names both its coverage and its blind spots.

The result should label a miss as evicted only when recent evidence is complete. Everywhere that evidence expired or broke, report unknown.