KV Cache Prefix Hits Are Not Reuse: Managing Cache State Under Hybrid Attention

1. The Classic Paradigm: Matching Prefixes Mean Reuse

Modern large model inference frameworks commonly rely on paged KV cache management: the key-value state of historical tokens is divided into fixed-size logical pages, which are mapped to physical GPU memory blocks through a page table. When multiple requests share an identical input prefix—such as the same system prompt or the shared history of a multi-turn conversation—the framework can point the new request’s page table at existing physical blocks and skip repeated prefill of that prefix. This mechanism significantly improves throughput and time to first token, and it has made prefix cache hit rate one of the most important optimization metrics for inference services.

This mechanism rests on an implicit assumption: every layer of the model processes historical tokens in exactly the same way. As long as the token sequence is identical, the KV state produced by each layer at each position is deterministic and consistently laid out. Therefore, “same prefix means the cache can be reused directly” is a sufficient condition, and a hash hit is enough to safely continue computation. Mainstream inference frameworks have operated on this assumption for a long time, and engineering mental models have been built around it.

2. Hybrid Attention Breaks This Rule

To control both memory footprint and computation under extremely long contexts—for example, millions of tokens—newer models increasingly adopt hybrid attention architectures that mix different attention mechanisms across layers. Common combinations include:

• Full-history compression layers: distant history is compressed into a small number of aggregated states, while full KV is retained only for recent tokens.
• Sliding-window attention (SWA) layers: only the KV within the most recent window is maintained, and entries outside the window are evicted as the position slides.
• Sparse routing layers: an indexer dynamically selects the subset of tokens that participate in that layer’s attention.

Under this architecture, an identical prefix only guarantees an identical token sequence; it does not guarantee identical cache state across layers:

1. The compression result in compression layers depends on when compression occurred and what content existed at that time. Two identical prefixes with different compression progress will have different cache states.
2. Sliding-window layer state continuously expires as the position slides, so the window boundary may already be misaligned at hit time.
3. The sparse layer’s index state must remain synchronized with the compressed state. A missing piece on either side causes incorrect routing results.

As a result, a “hash hit” degrades from a sufficient condition to a necessary one: it only indicates that reuse may be possible. Whether computation can actually continue depends on whether every layer’s cache objects are in a recoverable state.

An analogy: in a traditional architecture, finding a cache block is like looking up a shelf number in a library and taking the book directly. Under hybrid attention, after finding the number you must verify item by item—whether the book is still on the shelf, whether the latest pages have been bound, whether the lending card has expired, whether the index catalog is synchronized, and whether it has been transferred to an offsite storage facility and not yet returned. Only after all checks pass can you genuinely “continue reading.”

3. Five Cache Object Types: Lifecycles and Recovery Conditions

An inference system serving hybrid attention models must explicitly track the following five cache object types:

Cache object	Meaning	Lifecycle	Reusable condition	Consequence of absence
Compressed history state	Aggregated KV of distant context after compression	Rolling updates with the compression policy	Compression result complete and aligned with the current position	Historical semantics lost; long-range dependencies broken
Uncompressed tail	Full KV of the most recent tokens not yet compressed	Extends backward from the generation position	Contiguous and complete, and correctly joined with the compressed segment	A “gap” appears in the context
Sliding-window state	KV within the current window of SWA layers	Continuously evicted as the window slides	Window boundary aligned and not expired	Attention reads holes or misaligned data
Indexer state	Selection metadata required for sparse routing	Updated in sync with compression state	Version-consistent with compressed history state	Sparse layers select wrong tokens; output drifts
Disk prefix	Prefix blocks swapped out to host disk or object storage	Remains resident long-term after swap-out	Swap-in complete and page table pointing correctly	Reads dangling addresses or blocks waiting on I/O

The key takeaway from this table is that the five object types have completely different lifecycles, recovery paths, and hit criteria. Any shortcut that treats “a unified hit” as “reuse” plants correctness risks.

4. The Allocator’s Expanding Role: From “Find a Free Block” to “Maintain a State Machine”

In traditional designs, the allocator does one thing: pick a free physical block for a new token and write to it. Once cache objects become heterogeneous, the allocator must be upgraded into an explicit state machine:

• Form tracking: record the current form of each token segment—which pages are compressed, which remain in the tail, which are within the sliding window, and which have been swapped out.
• State transitions: manage transitions such as “tail → compressed,” “window-slide eviction,” and “swap-out → swap-in,” and guarantee their atomicity.
• Admission decisions: before accepting a reuse request, validate capacity and state together rather than looking only at the number of free blocks.

Skipping this work produces a subtle failure mode: a prefix match reports a hit by hash, but the actual read is missing the tail, missing the sliding window, or has an unsynchronized index, and the generated output is silently wrong. Such errors are often hard to reproduce—whether they occur depends on the compression and swap-out history of previous requests. This is a classic “state-dependent” defect.

A state-oriented matching flow looks roughly like the following (illustrative code, not any specific framework’s interface):

def try_reuse_prefix(req, cache):
    blocks = cache.match_by_hash(req.prefix_ids)   # Step 1: hash-level match
    if blocks is None:
        return PrefixResult.MISS
    # Step 2: validate all five state types and take the intersection
    for state in (CompressedKV, Tail, SWAWindow, IndexerState, OnDiskPrefix):
        if not state.recoverable(blocks, req.pos):
            return PrefixResult.PARTIAL_HIT   # trigger recovery flow or fall back to recompute
    # Step 3: only after layout and alignment checks pass may computation continue
    if not layout_and_alignment_ok(blocks):
        return PrefixResult.INVALID
    return PrefixResult.FULL_HIT

5. Four Validation Layers: Deciding Whether a “Hit” Can Actually Continue

Beyond state validation, four validation layers together determine whether a prefix hit is usable:

1. Whole-block consistency validation: block sizes may differ across cache groups. When reusing across groups, whole-block alignment must be validated against the least common multiple of the group sizes to avoid partial contamination from “reusing half a block.”
2. Kernel interface contract validation: different attention kernels have their own expectations for cache layout, strides, and metadata arrangement (the kernel ABI). Before reuse, confirm that the target kernel can correctly interpret the data.
3. Multi-cache-group state intersection: the model has multiple cache groups (compression group, sliding-window group, index group, and so on). The overall result counts as a hit only when all groups’ states at the corresponding position are simultaneously valid—the decision logic is an intersection, not “any one hit.”
4. Byte-level hardware alignment: addresses and boundaries must satisfy hardware alignment requirements; otherwise, even logically complete data may read or write incorrectly or suffer severe performance degradation.

6. Four Consistency Invariants

Beyond validation, the allocator state machine must not violate four invariants throughout its lifecycle:

1. Admission limits: cap concurrent recovery and swap-in operations to prevent a burst of disk requests from crowding out online GPU memory and bandwidth and causing livelock.
2. Five-state separation: the five object types must follow their own explicit processing paths; a unified “hit means reuse” fast path is forbidden.
3. Atomicity of validation and use (TOCTOU protection): between passing validation and the actual read, state may be modified by other requests. The state snapshot at validation time must be bound to the data pointer, ensuring that “what was validated is what is used at runtime.”
4. Static graph execution topology: inference engines that use computation graph capture require addresses and shapes to be statically fixed during execution. All dynamic recovery (swap-in, decompression, state completion) must be materialized before graph execution; cache topology cannot change dynamically during execution.

7. Engineering Practice Recommendations

Based on the analysis above, here are several actionable recommendations:

1. Redesign the metric system: upgrade “hash hit rate” to “effective hit rate” (the proportion of hits that actually complete reuse after all validation), and track recovery success rates and failure-cause distributions for the five state types separately.
2. Build per-state observability: emit independent counters and histograms for tail-length distribution, swap-in latency, validation failure types, and similar signals, making “hidden correctness loss” visible.
3. Fault injection testing: deliberately create missing or unsynchronized states for each cache object type and verify that the system falls back correctly rather than producing wrong results.
4. Prefer graceful degradation: any validation failure should fall back to recomputing that prefix—better to lose latency on a single request than to tolerate silent errors.
5. Co-design with scheduling: swap-in recovery for long-context requests has long-tail latency characteristics. It should be designed jointly with request scheduling and preemption policies to avoid head-of-line blocking.

Whether a team builds its own inference cluster or uses a managed large model inference service from a cloud platform such as Baidu AI Cloud, these mechanisms directly affect capacity planning, metric interpretation, and online troubleshooting. Understanding “correctness beyond hit rate” is a foundational skill for evaluating and operating long-context inference services.

8. Conclusion

Prefix hit rate answers “can we save work?” Cache state correctness answers “can we compute it correctly?” When cache objects move from a single form to five coexisting states, correctness is no longer an implicit property “guaranteed by the framework.” It becomes an engineering problem that requires explicit design: use a state machine to manage form transitions, use layered validation to determine usability, and use invariants to constrain the full lifecycle. Only with all three in place does a “hit” truly mean “reusable.”