Prefix cache eviction attribution after event gaps

Prefix cache eviction attribution after event gaps needs a third answer besides evicted and no match: unknown. A missing BlockRemoved event cannot prove that a resident prefix survived.

The distinction changes the fix. A proven eviction points to capacity or routing. A proven key mismatch points to prompt or hash inputs. Incomplete history points to the telemetry path first.

Prefix cache eviction attribution after event gaps

A recent vLLM feature proposal suggests classifying the first failed block lookup as evicted when its hash appears in a bounded recent-eviction set.

The proposal uses no_match when no matching key was seen recently. It also adds lookup_limit for a block that was never probed because vLLM recomputes the final prompt token for logits.

That request-local design avoids several false positives. An external consumer has another problem: its history may be incomplete even when the engine's own bounded set is correct.

vLLM emits BlockStored, BlockRemoved, and AllBlocksCleared events. Its KV-event publisher attaches a sequence number to each published batch.

Sequence continuity tells a consumer whether it observed every state change. It does not reconstruct events that have already fallen out of the replay buffer.

Once continuity is lost, absence from the index is not evidence of no_match. The block may have been stored or removed inside the missing interval.

Keep a publisher epoch beside the sequence

The current publisher creates its counter with count(), so a new publisher process starts sequencing from zero. A bare sequence number cannot distinguish an old batch from a new process lifetime.

Track a publisher epoch for each stream. A practical key combines stable worker identity with a process-start or pod-instance identifier.

Within one epoch, accept sequence n only after n minus 1 or a replay that fills the gap. When the epoch changes, discard the worker's old resident-block view before applying new events.

Do not carry cache residency across a restart because GPU memory is volatile.

The Aerospike cache-tiering overview notes that a worker restart loses its GPU-resident KV state.

If an external tier survives the worker, rebuild that tier from its own authoritative events. Do not infer survival from the old GPU index.

The publisher includes data_parallel_rank in event batches, but rank is not a process lifetime. Reusing rank zero after a restart still needs a new epoch.

Work through a complete eviction

Suppose worker A, epoch 42, publishes sequence 100 with BlockStored for hash H.

The consumer then receives every batch through sequence 147. Sequence 148 contains BlockRemoved for H, and the stream stays continuous through the request at sequence 160.

If that request probes H and misses, eviction attribution is defensible. The consumer observed H become resident, observed its removal, and has no gap between those facts and the lookup.

Now change one detail. The consumer receives sequence 200, then 207. Replay returns only 205 through 207 because older batches have expired.

Sequences 201 through 204 are unrecoverable. They may contain a store, removal, or reset. A miss at sequence 208 is unknown_history even if H is absent from the reconstructed index.

Calling it no_match would blame prompt construction without proof. Calling it evicted would blame memory pressure without proof.

Keep unknown as a first-class metric. Do not quietly fold it into the larger of the other two buckets.

Size replay from outage time

vLLM's KV-events configuration defaults buffer_steps to 10,000 batches. It also defaults the ZeroMQ high-water mark and publisher queue to 100,000.

These limits protect different stages. The high-water mark controls queued messages, while buffer_steps controls how far back a reconnecting consumer can request replay.

Size replay with three measurements: peak published batches per second, the longest supported consumer outage, and reconnect plus catch-up time.

If the peak is 800 batches per second, outage allowance is 12 seconds, and catch-up needs 3 seconds, the minimum window is 800 times 15, or 12,000 batches.

Apply a safety factor for bursts. At 2x, configure at least 24,000 replay steps. The default 10,000 would cover only 12.5 seconds at that peak before any safety margin.

This calculation uses event batches, not individual block events. Measure the publisher's actual batch rate because one batch can carry many stores or removals.

Alert on the oldest replayable sequence and the consumer's last contiguous sequence. Lag in seconds is useful, but sequence coverage decides whether recovery is possible.

Quarantine a stream when recovery fails

When the consumer sees sequence 207 after 200, it should request replay from 201 before applying 207 to its trusted state.

If replay starts at 205, mark the epoch incomplete. Remove that worker from precise attribution or label every dependent result unknown until a full snapshot or clean epoch rebuild restores trust.

The current vLLM replay service returns buffered batches at or after the requested sequence. It cannot return batches older than its bounded deque.

Do not bridge the hole by assuming no events occurred. ZeroMQ delivery loss, consumer downtime, and publisher backpressure are exactly the cases the sequence exists to expose.

The llm-d KV-cache indexer uses engine events to maintain a near-real-time view for routing. That view is precise only while its input history is trustworthy.

If routing must continue during quarantine, fall back to an approximate or load-aware scorer. A stale exact index can be worse than an honest approximation because it sends work toward blocks that no longer exist.

Separate event delay from event loss

Back-to-back requests can arrive before BlockStored reaches the indexer. llm-d addresses this blind spot with speculative entries that expire unless a confirming event arrives.

Its precise producer documentation describes a default two-second speculative TTL.

Delay keeps the sequence contiguous once the event arrives. Loss creates a permanent hole. Track them separately.

Measure route-to-BlockStored latency at P50, P95, and P99. Size a speculative TTL from that distribution and record how often entries expire before confirmation.

For loss, count detected gaps, successful replays, unrecoverable gaps, epoch changes, and the duration each worker remains quarantined.

Do not use a longer speculative TTL to hide replay failures. That converts a temporary routing hint into stale cache residency.

Fanout's prefix cache hash collision guide covers key identity. Event continuity is a separate condition: the key can be correct while the observer's state is stale.

Preserve the request-level distinctions

Complete event history still does not make every absent hash a token divergence.

The vLLM proposal notes that no_match can result from different cache salt, LoRA, or multimodal hash inputs even when decoded text is unchanged.

Report extra-key kinds without their values. Keep prompt snippets opt-in because they can expose user content.

Also preserve lookup_limit. With a block size of 16, the proposal's test cases return 0 cached tokens for 16 prompt tokens, 16 for 17, 16 for 32, and 32 for 33.

The 32-token case is not an eviction. The second block is not probed because of the logits boundary.

Fanout's prefix cache salt granularity guide explains why a salt change creates a different hash chain even when token IDs match.

A useful outcome set is evicted, no_match, lookup_limit, unknown_history, and unknown_epoch. That vocabulary keeps engine behavior apart from observer failure.

Test failure paths before trusting attribution

Start with a continuous stream. Store a known block, remove it, issue the matching request, and verify evicted.

Then drop one batch that contains the removal. If replay can recover it, attribution should stay evicted. If replay cannot, the same request must become unknown_history.

Restart the publisher and reuse the same rank. Verify that the consumer rejects the old epoch's residency and does not treat the reset sequence as duplicate delivery.

Drive the consumer beyond its replay window. Confirm that it quarantines the worker instead of silently resuming a supposedly precise index.

Finally, test changed salt, changed LoRA, a prompt-token difference, and the 16/17/32/33-token lookup boundaries. Event completeness cannot replace those request-level controls.

Prefix cache eviction attribution after event gaps is an evidence problem. Prove continuity first, then classify the miss. When the history is incomplete, unknown is the accurate operational answer.