Million-Token Contexts with Heterogeneous Attention: Why Prefix Cache Hits Can Be False

    Prefix caching assumes that identical token prefixes always produce reusable KV blocks. That assumption holds for layer-homogeneous models but breaks down once attention becomes heterogeneous across layers — full-history compression, sliding windows, sparse routing — and once a 1M-token context no longer fits on one GPU. This article explains why a hash match can report a hit while the state the request actually needs is missing, stale, or malformed, catalogues the five cache objects that now have separate lifecycles and recovery conditions, and lays out the checks (LCM alignment, kernel/ABI layout, per-group intersection, byte-level alignment) and runtime invariants (capacity caps, three-path prefill routing, check-then-use atomicity, static execution graph constraints) that make a hit trustworthy. It ends with a concrete reuse protocol and a consistency-testing checklist for catching silent correctness failures before release.

    1. Background: The Old Assumption Behind Prefix Caching Is Breaking

    Mainstream inference servers split the intermediate results of attention computation (referred to below as the KV cache) into fixed-size blocks, map logical positions to physical blocks through a page table, and let requests with the same prefix reuse each other’s blocks directly. The premise is simple: if two requests share the same token sequence in their prefix, the blocks can be reused as-is, and the hit decision degenerates into a single hash comparison.

    That premise holds up in models that are homogeneous across layers. Every layer and every position represents state the same way, so an identical token sequence implies a one-to-one correspondence of layer states. New long-context architectures break it. Layers mix different attention types (full-history compression, sliding window, sparse routing); a 1M-token context far exceeds the capacity of a single GPU’s memory, which makes cross-request sharing the normal case rather than the exception. Stack those three facts together and “the prefix is identical” now only guarantees that the input tokens match — it no longer guarantees that the reusable cache state is complete or consistent. If you still decide on a hit by hash alone, you get a metric that reports a hit while the state you actually read is missing a piece or carries the wrong version, and the generation output fails silently.

    An analogy: in the old scheme, a hit is like picking a book by its shelf number. In the new architectures, a hit still requires you to confirm the book is on the shelf, the most recent pages are bound in, the loan record is valid, the catalog is in sync, and any book in transit has actually arrived.

    2. How Three Attention Types Amplify the Cache State Problem

    1. Full-history compression. The model no longer retains the full historical KV. Instead, long spans of history are pooled at a given stride into a single “compressed state” that later layers query. This state is highly aggregated information; it cannot be reconstructed on the fly from a handful of raw blocks. Whether it can be reused depends on whether the raw blocks used during compression are all present, whether positions are contiguous, and whether lengths are aligned.

    2. Sliding window. Some layers attend only to the most recent fixed number of tokens, so earlier KV is naturally expired. This keeps memory usage constant, but every decode step evicts the oldest block and adds a newest one, which means the reusable range moves over time. On top of that, if a paging scheme assumes that the attention layer locates the window’s blocks by itself, the backend has to implement or rewrite the attention mask per window; otherwise content outside the window still gets read.

    3. Sparse routing. Some layers use a lightweight indexer to pick a small number of historical blocks per query. Routing results depend on an index state, which is aggregated from the features of all tokens — a derived intermediate artifact. Once a historical block or the tail segment is modified or extended, the index is invalidated along with it. Building the index is far cheaper than generating the raw KV, so it can be rebuilt, but being able to rebuild is not the same as being able to inherit.

    When the three are mixed, one and the same KV has to serve three access patterns at once — “look at all history”, “only look at the near end”, “look at a few blocks on demand” — and the reusable objects split apart accordingly.

    3. Five Heterogeneous Cache Objects: Lifecycles and Recovery Conditions

    Object Why it must exist separately Lifecycle When it is invalid or unrecoverable Recovery path
    compressed KV (compressed state) Full-history compression layers retain only this Solidified with the token segment it belongs to; expensive to build The raw blocks it depends on, the tail segment, the compression stride, or the length marker disagree Rebuild the segment (recompute); cannot be “topped up” in place
    uncompressed tail Near-end raw KV not yet compressed and not covered by the sliding window Frequently appended and dropped; strongly tied to generation length Wrong length, misplaced positions, or mistaken for already-compressed content Drop the surplus; fall back to recomputation for the shortfall
    SWA window Sliding-window layers read only a fixed number of near-end tokens Slides over time; the oldest block expires Reuse length exceeds the window, or the referenced block has already been reclaimed Keep only the reusable part inside the window; fall back to recomputation outside it
    indexer state (routing index) Lookup basis for sparse routing Lives and dies with the KV; cheap to build Underlying KV changes or versions disagree Rebuild from the KV that still exists
    on-disk prefix (external prefix) A 1M-token context far exceeds single-GPU memory, so historical prefixes are pushed down to host memory or external storage Seconds to minutes; persists across requests Transfer incomplete, evicted, or failed verification Re-transfer, or drop it in place and fall back to recomputation

    One criterion runs through the whole table: whether an item “can be picked up where it left off” depends only on whether the information needed to rebuild it is still around. The sliding-window region inherently drops its oldest block, so its reusable length will never equal the token prefix length; if the downstream information a compressed state depends on is gone, the only option is recomputation.

    4. Where It Breaks: A Hash Hit Is Not a Correct State

    The problem reduces to four gaps in the chain:

    1. The criterion is too coarse. The hash covers only the token-id sequence, not “which layers read this span of history, and in what way”.
    2. Semantics are ignored. Paging only guarantees that a block contains bytes, not that those bytes are in the form the current request needs.
    3. Lifecycles are out of sync. Block reclamation policy and the invalidation conditions of the various cache objects are managed independently.
    4. Verification is missing. There is no “state completeness” confirmation between the hit decision and the moment the data is actually read.

    At the code level, the problem usually does not sit in the memory allocator itself but in the protocol layered above it. The gap looks like this:

    1. class CacheManager:
    2. def alloc(self, seq_len):
    3. # The traditional implementation is only responsible for finding an empty block for new tokens
    4. return block_pool.acquire(num_blocks=seq_len)
    5. def match_prefix(self, token_ids, hash_table):
    6. # The traditional implementation is only responsible for finding an existing block by token hash
    7. idx = hash_table.find(token_ids)
    8. return idx # Implicit assumption: a found block is immediately usable
    9. # New protocol layer: before declaring a hit, verify what form this set of blocks is currently in
    10. def resolve(self, token_ids, layer_configs, layer_group_keys):
    11. idx = self.match_prefix(token_ids, hash_table)
    12. if idx is None:
    13. return ReuseResult.none(), Reason.NOT_FOUND
    14. token_len, covered = idx.length, idx.covered_length # how far coverage reaches
    15. # Form: compression stride / sliding-window capacity / quantization / data version
    16. if covered < token_len: # covers only part of it
    17. return ReuseResult.partial(covered), Reason.PARTIAL_COVER
    18. if idx.swa_window < layer_configs.swa_window: # the sliding window does not cover enough
    19. return ReuseResult.none(), Reason.SWA_WINDOW_EXPIRED
    20. if idx.compress_stride != layer_configs.stride: # different compression stride
    21. return ReuseResult.none(), Reason.COMPRESS_STRIDE_MISMATCH
    22. if layer_group_keys and idx.group_key not in layer_group_keys:
    23. # the state intersection across multiple cache groups is empty
    24. return ReuseResult.none(), Reason.GROUP_INTERSECTION_EMPTY
    25. return ReuseResult.full(idx), Reason.OK

    The thing most worth remembering here is that alloc and match are two parallel concerns: one allocates new space, the other decides that old space is reusable. The old frameworks were reliable precisely because the two could stay independent — the allocator understood no semantics, and the hash table cared nothing about form. Once layers become heterogeneous, allocation must additionally take on the responsibility of recording what form each token segment is currently in, so that match has something to decide against. If you report a hit by hash alone, you find out at read time that the compressed state, the near-end tail, or the routing index is missing. That shows up as degraded generation quality rather than an error, which makes it considerably harder to diagnose.

    5. Four Checks Before You Trust a Hit (Whether You Can Just Continue Computing)

    1. Whole-block verification. Take the reuse granularity as the least common multiple (LCM) of the granularities of the various states, so you never hit half a block. Block size (e.g. 16), compression stride (e.g. 64), and sliding-window capacity (e.g. 128) are usually not aligned with one another, and a request length is not necessarily a multiple of any of them either. If you slice reuse by block size, the portion of the length that falls inside a compression boundary actually has no compressed state available, and what you read back is at the wrong position. The correct approach is to align the usable prefix down to an integer multiple of the LCM and send the remaining tail through recomputation.

    2. Kernel / ABI consistency. The KV layout (head count, dimensions, data type, quantization scheme, paging granularity) must match the current kernel implementation. A model upgrade, a quantization switch, or a change in parallelism all alter the layout; at that point the tokens are identical but the meaning of the bytes has changed, so reusing them is contamination.

    3. Non-empty intersection across cache groups. A single deployment often runs multiple cache groups side by side (layer grouping, different precisions, different sliding-window configurations). Each group must be confirmed complete individually; if any group comes up empty, the whole request falls back to recomputation.

    4. Byte-level alignment. When transferring across devices or hosts, page-table entries, alignment requirements, byte order, and the transfer protocol must match, otherwise you get a “logically hit, physically misread” failure.

    6. Four Runtime Invariants

    1. Admission caps. Give each cache type its own capacity and occupancy limit (compressed-state block count, sliding-window length, index entries, total external-prefix volume) and degrade to “recompute only, retain nothing” when the limit is exceeded, so memory is never blown out.

    2. Five-state routing. Route across three branches — complete / partially complete / needs rebuild — to different prefill paths. Never treat a partial hit as a full hit.

    3. Check-then-use atomicity. Between the hit verification and the actual read, you need a lock or a reference count to prevent eviction or reuse in the interim (TOCTOU). Under concurrent requests, the same physical block being written by two requests at once is a textbook data race.

    4. Static topology and execution graph. If the framework reuses computation graphs captured at compile time (CUDA-Graph-style mechanisms), the page-table mapping must be updated outside the graph and read-only inside it; a dynamically allocated address will not match the address fixed at capture time.

    7. Engineering: A Reuse Protocol You Can Actually Ship

    1. Cache entries carry metadata. Every reusable entry must record its form, version, covered length, sliding-window watermark, layer-group identifier, and reference count — not just a hash.

    2. Align after the hit, before reading. Take the usable prefix aligned to the LCM, explicitly mark the tail as “needs recomputation”, and account for it in the prefill budget.

    3. Implement prefill as three paths. Full hit: read directly. Partial hit: keep the prefix and recompute the tail. Miss: take the conventional path. All three paths must share the same positional-encoding and masking logic.

    4. Decouple compression from sliding window. Split “produce the compressed state” and “maintain the sliding window” into separate operators, each declaring its input dependencies, and let the scheduler decide ordering from those dependencies.

    5. Prefetch external prefixes asynchronously. Separate hit-rate evaluation from data movement: look up the table first to get a “possible hit”, then fetch in parallel, and send anything not fetched in time straight to recomputation. Do not trade waiting time for a falsely high hit rate.

    8. Consistency Test Checklist (Kill the Bug Before Release)

    • Differential testing. Run the same batch of prompts under three configurations — cache disabled, cache enabled, and one class of state artificially removed — and compare whether the output tokens are identical. This is the most effective way to catch silent errors.
    • Property testing. Generate random combinations of prompt length, sliding-window capacity, compression stride, and layer configuration, and assert that “reuse prefix + recompute tail” produces the same result as full recomputation.
    • Fault injection. After a hit, randomly tamper with the compressed state, drop the tail, or blank out the index state, and verify the system detects it and falls back instead of continuing to generate.
    • Concurrency stress. With multiple requests sharing the same prefix, verify the correctness of reference counting and locking.
    • Metrics instrumentation. Distinguish a “logical hit” from an “effective hit” (the part actually read and used in computation), and report hit-failure reasons by category (not found / partial coverage / window expired / stride mismatch / empty group intersection / transfer incomplete).

    9. Conclusion

    Prefix-cache failures are not cases of “the algorithm computed the wrong thing”; they are cases of “the state assumption was wrong”. When a model moves from layer-homogeneous to layer-heterogeneous, the cache object goes from one to five, and the criterion for reuse has to be upgraded from “the tokens are identical” to “the tokens are identical + the state is complete + the version matches + the alignment is correct + there is no concurrency contamination”. Three investments are worth the most engineering effort: fold metadata into the cache protocol, make LCM alignment a hard constraint at the reuse entry point, and turn differential testing into a standing gate. Do those three, and a high hit rate becomes a credible performance gain rather than a smokescreen over incorrect results.