Source-linked AI summary
Tail-Replay: Escaping the Curse of Linear Attention in Prefix Caching for Hybrid LLMs
Yirui Liu, Ruoling Qi, Xuaner Wu, Penghang Liu, Jian Chen
TL;DR
Hybrid LLM prefix caching is limited because token-addressable full-attention KV coexists with non-rollbackable linear-attention recurrent states. Tail-Replay reconstructs those states from short recent suffixes while caching exact full-attention states, retaining most quality and improving TTFT at long contexts.
Problem
Hybrid prefix caching is constrained because linear-attention recurrent states cannot be reused at arbitrary token-level boundaries, unlike full-attention KV caches.
Method
Tail-Replay caches exact full-attention KV and output hiddens, then independently reconstructs each linear-attention group by replaying a short recent matched-prefix suffix.
Results
Across LongBench and RULER, Tail-Replay retains 92.8–99.9% of full-prefill quality with 5–10% replay budgets and reaches 9.1–14.3× TTFT speedup at 32K.
Takeaways & Limitations
Tail-Replay enables flexible token-level prefix reuse in three Gated DeltaNet-based hybrid models without recurrent-state checkpoints.
Abstract
from arXiv · showhide
Hybrid large language models interleave full-attention layers with linear-attention layers to reduce the cost of long-context inference. This structure complicates prefix caching: full-attention key-value caches are token-addressable, whereas linear-attention layers maintain recurrent states that cannot be rolled back to arbitrary prefix boundaries. Existing hybrid prefix caching methods address this mismatch by storing recurrent-state checkpoints. As a result, token-level matches are directly usable only at positions aligned with stored checkpoints, constraining prefix reuse to a discrete set of boundaries. We present Tail-Replay, a prefix caching mechanism that enables unconstrained token-level prefix reuse in hybrid large language models. The key insight is that linear-attention mechanisms such as Gated DeltaNet can be viewed as a structured, lossy compression of the input prefix: gated recurrent updates progressively attenuate the contributions of earlier inputs. Consequently, the recurrent state of a matched prefix can be well approximated by replaying only a short, recent suffix of that prefix. Tail-Replay exploits this property by caching the exact full-attention key-value cache while omitting recurrent-state checkpoints. On a cache hit, it reconstructs the linear-attention states by replaying a short, recent suffix of the matched prefix. As a result, the reuse boundary is determined by the shared tokens rather than by recurrent-state checkpoints. We evaluate Tail-Replay on three Gated DeltaNet-based hybrid models using the LongBench and RULER benchmarks. With only a 5--10\% replay budget, it retains 92.8--99.9\% of full-prefill quality on LongBench and RULER. For serving efficiency, we evaluate time-to-first-token speedups across multiple matched-prefix lengths---8K, 16K, and 32K. The speedup grows with prefix length, reaching $9.1$--$14.3\times$ over full prefill at 32K.
1 Introduction
Hybrid LLMs combine full- and linear-attention layers to reduce long-context cost, but their recurrent linear-attention states make token-level prefix caching difficult. Tail-Replay removes checkpoint-aligned reuse constraints by reconstructing matched-prefix states from short suffixes.
- Hybrid architectures reduce long-context cost, while prefix caching avoids redundant prefill for shared prefixes.
- Linear-attention states cannot be rolled back to arbitrary prefix boundaries, unlike token-indexed full-attention KV caches.
- Existing hybrid caching methods retain recurrent-state checkpoints, so reuse remains limited to checkpoint locations rather than shared-token boundaries.
- Tail-Replay caches exact full-attention KV and reconstructs linear-attention states by replaying a short, recent matched-prefix suffix.
- With a 5–10% replay budget, quality retention spans 92.8–99.9% of full-prefill quality, while TTFT speedup reaches 14.3× at 32K.
- The contributions include checkpoint-free token-level reuse, replay-based state reconstruction, evaluation on three hybrid models, and two replay-overhead optimizations.
2 Preliminary and Related Work
Hybrid models expose token-addressable KV caches in full-attention layers but recurrent states in linear-attention layers. Gated DeltaNet gates attenuate earlier information, motivating suffix-based state reconstruction rather than checkpoint storage.
- Full-attention layers provide token-indexed KV caches, whereas linear-attention layers expose only a final recurrent state after token-by-token updates.
- Gated DeltaNet uses a learned gate α_i ∈(0, 1] that progressively attenuates earlier information while a rank-1 correction reshapes the current update.
- Prior hybrid caching systems retain recurrent checkpoints, while LinearKV uses cached local linear states as initializers; Tail-Replay instead reconstructs state from a recent hidden suffix.
- Figure 1 depicts caching full-attention KV and output hiddens, independently applying Tail-Replay to linear-attention groups, then processing unmatched suffix tokens.
3 Method
Tail-Replay retrieves exact full-attention states for a matched prefix and independently reconstructs each linear-attention group by replaying only its recent cached hidden tail. Replay efficiency is improved by confining errors within groups, skipping unnecessary FFNs, and overlapping transfer with replay.
- Tail-Replay reconstruction: On a cache hit, Tail-Replay retrieves matched-prefix full-attention KV and replays only a short recent tail of cached full-attention output hiddens.
- Tail-Replay reconstruction: The replay ratio controls tail length, while caching every full-attention output hidden ensures replay inputs match the original prefill inputs.
- Tail-Replay reconstruction: For a matched prefix of m tokens, the replay length is k = ⌈rm⌉, and each group starts the selected tail from a zero-initialized state.
- Tail-Replay reconstruction: The reconstructed final state approximates the matched-prefix recurrent state, after which unmatched tokens continue using reconstructed linear-attention states and retrieved KV.
- Replay efficiency: Replay omits the final group FFN because the next group already starts from a cached exact full-attention hidden.
- Replay efficiency: Overlapped host-to-device transfer hides most data-movement cost because replay does not depend on the cached full-attention KV.
4 Experiment
Tail-Replay is evaluated on three Gated DeltaNet-based hybrid LLMs using LongBench and RULER, measuring both end-to-end quality and serving efficiency. Short replay budgets preserve most full-prefill quality, while the 5% optimized path delivers large TTFT speedups at long contexts.
- Setup: The evaluation covers OLMo-Hybrid-7B, Qwen3.5-4B, and Qwen3.6-27B on NVIDIA H100 GPUs using PyTorch 2.9.1.
- End-to-end quality: 92.8–99.9% of full-prefill quality is retained across LongBench and RULER with replay ratios of 5% and 10%.LongBench retention is 92.8–98.9% at 5% and 93.9–98.1% at 10%; RULER retention is 93.1–99.9% and 96.7–99.9%, respectively.
- Serving efficiency: 9.8×, 9.1×, and 14.3× TTFT speedups are reached at 32K for OLMo-Hybrid-7B, Qwen3.5-4B, and Qwen3.6-27B, respectively.The 5% OVL+skip path remains comparatively stable, while increasing replay to 10% raises TTFT at 32K because replay becomes the dominant cost.
5 Conclusion
Tail-Replay resolves hybrid prefix caching’s token-boundary mismatch by combining exact full-attention reuse with recent-tail replay for linear-attention state reconstruction. Across three evaluated models, this preserves most quality while reducing TTFT at long contexts.
- Tail-Replay enables flexible token-level prefix reuse without recurrent-state checkpoints.
- Exact FA KV and FA output hiddens are cached, while each linear-attention group independently replays only a recent suffix.
- Short replay tails preserve most full-prefill quality and deliver substantial TTFT reductions across three Gated DeltaNet-based hybrid models.
A Complete Quality Results
The appendix provides the complete per-cell quality results underlying Table 1. Results are organized using LongBench and RULER abbreviations.
- Table 3 lists every quality cell used in Table 1 as absolute scores for full prefill, zero-only, and both replay budgets.
- LB denotes LongBench and R denotes RULER in the complete per-cell results.