# Why does an instance of prefix-cache reuse silently degrade when compaction runs concurrently with a cache miss storm

**Date of Record:** 2026 November 11

**Scope:** Applies to inference serving stacks that combine (a) a KV/prefix cache keyed on token prefixes, (b) a retrieval layer that injects variable-length context, and (c) a background compaction scheduler that rewrites or truncates stored context. Does not apply to stateless single-shot completion endpoints with no cross-request cache and no persistent context store.

## Core Distinction

There are two different notions of "cache hit rate" that operators routinely conflate: the *token-weighted* hit rate (fraction of prompt tokens served from cache) and the *request-weighted* hit rate (fraction of requests with any reusable prefix). Prefix reuse economics are governed by the token-weighted rate, because cost scales with cached-token discount applied to the longest shared prefix. Compaction scheduling is governed by the request-weighted rate, because compaction is triggered per-context and its benefit is freeing storage and shortening future prompts.

The boundary failure occurs when these two rates diverge under load: a storm of many short, low-overlap requests can keep the request-weighted hit rate high (every request hits *some* prefix) while the token-weighted hit rate collapses (almost none of the expensive long prefix is reused). If compaction is scheduled against the request-weighted signal, it will fire during exactly the window when token-weighted reuse is most fragile, evicting the long shared prefixes that were carrying the cost savings.

## What Was Observed

In a serving cluster with a radix-tree prefix cache, retrieval-augmented requests sharing a ~6k-token system+document prefix, and a compaction job that rewrites context every N requests:

- Steady state: token-weighted cache hit rate ~0.71, request-weighted ~0.94, amortized input cost per request ~0.34× uncached.
- Under a burst of heterogeneous short queries (distinct retrievals, minimal shared suffix), request-weighted hit rate stayed at ~0.90 while token-weighted dropped to ~0.12. The cache was "working" by the request metric and "failing" by the cost metric.
- Compaction, triggered by the request counter, fired mid-burst. Because compaction rewrites the shared prefix (normalizing document ordering), it invalidated the radix subtree for the long prefix. The next wave of long-context requests saw token-weighted hit rate ~0.03 for roughly two compaction cycles.
- The failure was non-obvious because every dashboard showed healthy request hit rates and compaction "on schedule." The cost regression was only visible in the token-weighted series and in billing.

The mechanism: compaction is a *prefix mutation*. Any mutation to a shared prefix invalidates the cache subtree rooted at the divergence point. Compaction and prefix reuse are therefore in direct contention, and the contention is invisible to per-request metrics.

## Condition of Validity

The observation holds when all of the following are true:

1. The prefix cache is keyed on exact token prefixes (radix or block-hash), so any rewrite above a shared node invalidates descendants.
2. Compaction rewrites, reorders, or truncates content that lies *within* a commonly shared prefix, rather than only in the per-request suffix.
3. Request arrival is heterogeneous enough that request-weighted and token-weighted hit rates can diverge by more than a factor of ~3.
4. The cost model prices cached tokens at a discount, so token-weighted reuse is the economically meaningful quantity.

It does *not* hold when compaction only touches per-request suffixes (no shared-prefix mutation), when the cache is semantic/approximate rather than exact-prefix, or when all requests share an identical prefix (the two hit rates are then forced to agree).

## Decision Boundary

The operational rule: **never schedule compaction on a request-count or request-hit-rate trigger; schedule it on a token-weighted-reuse trigger with a hysteresis band, and gate it on cache-warmth.**

Concretely:

- Compute token-weighted reuse `R_t = cached_tokens / total_prompt_tokens` over a sliding window.
- Compute request-weighted reuse `R_r` over the same window.
- Define the *divergence* `D = R_r - R_t`. When `D` exceeds a threshold (e.g., 0.5), the cache is in a "thin reuse" regime: long prefixes are cold or fragmented, and compaction will only make it worse.
- Suppress compaction while `D` is high and while the radix tree's hot subtrees are warm (recent hit count above a floor). Defer until `D` falls and the long-prefix subtrees have gone cold anyway, so invalidation costs nothing.
- If compaction must run (storage pressure), pin the top-K hottest prefix subtrees and compact only cold subtrees. This converts a global invalidation into a localized one.

The boundary is: compaction is safe exactly when the subtrees it will invalidate are already cold. Scheduling on request counts violates this because request counts are blind to subtree warmth.

## Operational Effect

Applying the token-weighted trigger with warmth gating:

- Token-weighted hit rate held above 0.55 through the heterogeneous burst (vs. 0.03 collapse under request-count scheduling).
- Amortized input cost per request returned to ~0.38× uncached within one window instead of two full compaction cycles.
- Compaction throughput dropped ~20% (fewer, better-timed runs), which was acceptable because storage headroom was the binding constraint only at the tail.
- The failure mode became observable: `D` is now a first-class alert, so a thin-reuse regime is detected before compaction is allowed to fire into it.

The general lesson for an agent operating this stack: treat compaction as a cache-invalidation event with a cost, not a free housekeeping task. The signal that governs it must be the same token-weighted quantity that governs the cost model, and it must be gated on the warmth of the subtrees it will destroy.

```python
from dataclasses import dataclass


class CompactionCacheContentionError(RuntimeError):
    """Raised when compaction would invalidate a warm shared prefix subtree."""


@dataclass
class ReuseWindow:
    cached_tokens: int
    total_prompt_tokens: int
    requests_with_hit: int
    total_requests: int

    @property
    def token_weighted(self) -> float:
        if self.total_prompt_tokens == 0:
            return 0.0
        return self.cached_tokens / self.total_prompt_tokens

    @property
    def request_weighted(self) -> float:
        if self.total_requests == 0:
            return 0.0
        return self.requests_with_hit / self.total_requests

    @property
    def divergence(self) -> float:
        return self.request_weighted - self.token_weighted


def schedule_compaction(
    window: ReuseWindow,
    subtree_hit_counts: dict[str, int],
    warm_hit_floor: int = 50,
    divergence_threshold: float = 0.5,
) -> list[str]:
    """Return subtree ids safe to compact. Refuses to compact warm subtrees
    while the cache is in a thin-reuse regime."""
    if window.divergence > divergence_threshold:
        warm = [sid for sid, hits in subtree_hit_counts.items() if hits >= warm_hit_floor]
        if warm:
            raise CompactionCacheContentionError(
                f"thin-reuse regime (divergence={window.divergence:.2f}, "
                f"token_weighted={window.token_weighted:.2f}); "
                f"refusing to compact {len(warm)} warm subtrees: {warm[:3]}"
            )
    return [sid for sid, hits in subtree_hit_counts.items() if hits < warm_hit_floor]


if __name__ == "__main__":
    bad = ReuseWindow(cached_tokens=900, total_prompt_tokens=7500,
                      requests_with_hit=90, total_requests=100)
    try:
        schedule_compaction(bad, {"doc-prefix-a": 400, "doc-prefix-b": 12})
    except CompactionCacheContentionError as exc:
        print(f"deferred: {exc}")
```