KV Cache Prefix Reuse in Hybrid Attention: Why a Cache Hit No Longer Guarantees Correctness

Background: The Reuse Assumption Taken for Granted

Mainstream inference frameworks support high-concurrency serving through paged KV cache management: token history is split into fixed-size blocks, a page table maps logical positions to physical memory blocks, and incoming requests hash-match against their prefix. On a hit, the new request’s logical pages are mapped directly onto existing physical blocks, skipping prefill computation for that portion of the prefix. This entire mechanism rests on an implicit assumption that is almost never written down:

Identical prefix ⇒ every layer’s KV state can be restored exactly as computed.

Under this assumption, “prefix cache hit rate” has long been treated as the single most important optimization metric for inference serving: the higher the hit rate, the more tokens skip recomputation, the lower the time-to-first-token, and the better the throughput. Engineering practice has operated this way for so long that “hit” and “usable” became synonyms by default.

Why Hybrid Attention Breaks “Hit = Usable”

To support contexts of a million tokens and beyond, a new generation of models has moved toward “hybrid” attention designs: some layers apply low-rank or implicit compression over the full history and retain only the compressed implicit states; some layers keep a sliding window over only the most recent W tokens; still others rely on sparse routing (selectors/indexers) to pick a small set of key tokens from the long history. The same prefix leaves completely different “cache forms” in different layers.

Consequently, “same prefix” no longer implies “recoverable state.” Consider a minimal counterexample: two requests have completely identical prefixes, but one of them has had exactly one page of its sliding-window cache evicted while the other is intact. By hash, both report a hit; at computation time, the first one misses a page at the window boundary, attention reads the wrong history range, and the generated output is wrong. The hit rate did not change; correctness did.

An analogy: in a traditional model, finding a block is like looking up a shelf number in a library—you simply go and take the book. In a hybrid architecture, after finding the number you still have to verify that the book is on the shelf (compressed KV), that the latest pages are bound in (uncompressed tail), that the checkout record has not expired (SWA window), that the catalog index is in sync (routing state), and that the book has not been shipped to an off-site warehouse and is still in transit (on-disk prefix). Only when all five checks pass can you truly continue reading.

Five Cache States and Their Recovery Conditions

A serving system must explicitly track five classes of objects, whose lifecycles, recovery conditions, and hit criteria all differ:

1. Compressed KV (compressed full history)

   • Form: compressed implicit states, usually stored as contiguous blocks;
   • Recovery condition: the compressed block is complete, and its quantization precision and tensor layout match the current weights and operator conventions;
   • Cost of loss: the layer cannot participate in computation, and the gap cannot be patched with a small recompute—recomputation costs roughly the entire prefix.

2. Uncompressed tail

   • Form: standard KV for the most recent tokens; small in size but required at every decode step;
   • Recovery condition: the tail tokens are contiguous, and the junction with the compressed portion matches exactly;
   • Cost of loss: a single missing page makes it unusable; there is no “approximate splice.”

3. SWA window (sliding window)

   • Form: ring-buffer-style KV pages within the window;
   • Recovery condition: window boundaries are aligned and all pages inside the window are present;
   • Cost of loss: window misalignment—attention reads the wrong history range.

4. Indexer state (sparse routing state)

   • Form: the router/selector’s internal statistics and index structures;
   • Recovery condition: one-to-one correspondence with the prefix tokens; must be fully synchronized when restored across requests;
   • Cost of loss: sparse layers select the wrong tokens—output quality degrades in ways that are hard to notice.

5. On-disk prefix

   • Form: cold prefixes swapped out to host memory or local disk;
   • Recovery condition: the asynchronous transfer has completed and readiness is confirmed;
   • Cost of loss: a “registered but not ready” intermediate state is misjudged as a hit, causing runtime stalls or errors.

The Allocator’s Expanded Role: From “Finding Empty Blocks” to “State Machine”

A traditional allocation does one thing: pick an empty block for the new tokens. In a hybrid architecture, the allocator must also record the “current form” of every token segment, and alloc and prefix match (hash-based hit determination) turn from two parallel actions into a tightly coupled state machine:

• Logical hit: the hash match succeeded—it only means “someone once computed this prefix”;
• Physically available: all five object classes satisfy their recovery conditions—only then is it true that “computation can genuinely continue from here.”

Illustrative pseudocode:

def try_reuse(prefix_hash):
    entry = hash_table.lookup(prefix_hash)
    if entry is None:
        return RECOMPUTE_ALL            # logical miss
    # logical hit != physically available; validate item by item
    if not entry.compressed_kv.ready:   return DEGRADE
    if not entry.tail.covers(last_k):   return DEGRADE
    if not entry.swa.aligned(win_size): return DEGRADE
    if not entry.indexer.synced(tokens):return DEGRADE
    if entry.on_disk and not entry.on_disk.resident:
        schedule_prefetch(entry)        # registered but not ready: prefetch, not a hit
        return PREFETCHING
    return REUSE

If downstream systems report hits based on hash alone, while reads encounter a missing tail, a missing SWA window, or missing routing state, generation will inevitably go wrong—and such errors tend to manifest as intermittent quality degradation, which is far harder to diagnose than an outright crash.

Four Validation Layers Between a Hit and Safe Reuse

Between “logical hit” and “physically available,” engineering practice needs at least four gates:

1. Block-level validation: the logical block exists, reference counts are valid, and the block has not been concurrently evicted;
2. Operator interface contract: the cache pages’ layout, precision, and page size satisfy the current kernel’s ABI conventions; any change in weight version or quantization format invalidates the entire batch;
3. Intersection across cache groups: different layer groups maintain their own states; the whole is usable only when every state in the intersection is ready;
4. Byte-level hardware alignment: physical addresses and alignment granularity must satisfy hardware constraints (cache lines, page size); otherwise the kernel reads misaligned data.

Failure at any layer should trigger degradation: reuse some layers and recompute the rest, or recompute everything.

Four Red Lines the State Machine Must Not Cross

1. Admission cap: reuse must not indefinitely crowd out memory needed by new requests; an admission cap is required to prevent cache bloat from causing OOM or starving new requests;
2. Five-state routing: different states have different recovery paths (in-place mapping, tail recomputation, window alignment, index synchronization, asynchronous transfer) and must not share a single recovery routine;
3. TOCTOU protection: between check time and use time, state may be concurrently modified (eviction, swap-out). “Check + bind” must complete atomically under a version number or critical section, and state pointers and versions must be revalidated at use time;
4. Static-graph topology: once multi-step decode is compiled into a static execution graph for throughput, block addresses and topology are fixed at capture time and cannot be dynamically rewritten at runtime; reuse decisions must be made outside the graph, or go through indirect addressing via fixed slots.

Practical Recommendations for Engineering Teams

• Upgrade monitoring metrics: beyond hit rate, track a “usable hit rate” (the share that genuinely skips recomputation) and the degradation rate caused by each type of missing state—only then will hit rate stop being misleading;
• Layered degradation chain: full reuse → partial reuse plus recomputation of the remaining layers → full recomputation, selected automatically based on validation results;
• Close the swap-out and prefetch loop: use asynchronous prefetch with ready acknowledgments for on-disk prefixes, eliminating the “registered = hit” false positive;
• Version fingerprints: any change in weight version, quantization format, or page size triggers fingerprint validation or full invalidation;
• Correctness stress testing: build mixed traffic combining “identical prefixes + different suffixes + interrupt-and-resume,” and compare the outputs of reuse against full recomputation for consistency—rather than watching throughput alone.

Whether you operate your own inference cluster or rely on managed inference, logging, and monitoring services from cloud platforms such as Baidu AI Cloud, this correctness-first standard applies equally—it is the prerequisite for every capacity optimization.

Conclusion

Prefix reuse is evolving from “table lookup” into “state recovery with preconditions.” Hit rate measures capacity and scheduling efficiency, not correctness. As attention architectures become heterogeneous, correctness can only come from explicitly modeling every class of cache state, validating each one, and restoring them under control. Building this boundary into system design is what allows inference services to be both fast and stable in the long-context era.