Summary (Overview)

• Tail-Replay is a novel prefix caching mechanism for hybrid LLMs (interleaving full-attention and linear-attention layers) that enables unconstrained token-level prefix reuse without being limited by recurrent-state checkpoint locations.
• The key insight is that linear-attention mechanisms like Gated DeltaNet (GDN) act as structured, lossy compression of input prefixes—gated recurrent updates progressively attenuate earlier inputs, so the recurrent state of a matched prefix can be well-approximated by replaying only a short, recent suffix.
• Tail-Replay caches exact full-attention (FA) KV caches while omitting recurrent-state checkpoints, reconstructing linear-attention states on cache hits by replaying a short tail (5–10% of the matched prefix).
• Evaluation on three Gated DeltaNet-based hybrid models (OLMo-Hybrid-7B, Qwen3.5-4B, Qwen3.6-27B) shows 92.8–99.9% quality retention on LongBench and RULER with a 5–10% replay budget, and up to 14.3× TTFT speedup at 32K context.
• Two optimizations—tail-FFN skip and transfer/replay overlap—further reduce replay overhead.

---

Introduction and Theoretical Foundation

Background

Modern LLM workloads (multi-turn dialogue, RAG, tool-using agents, multi-agent workflows) demand long contexts, repeated invocations, and high concurrency. Two complementary solutions have emerged:

1. Hybrid architectures (e.g., Gated DeltaNet-based models) interleave full-attention (FA) layers with linear-attention layers to reduce long-context cost.
2. Prefix caching reuses shared prefixes across requests to avoid redundant prefill.

The "Curse of Linear Attention"

The fundamental mismatch: in FA models, reusable state consists of token-indexed KV caches—any token boundary can serve as a reuse point. In linear-attention layers, the prefix is summarized into recurrent states through in-place updates that cannot be rolled back to arbitrary earlier prefixes. This means a token-level prefix match no longer directly implies a reusable model state.

Existing solutions (Marconi, Sparse Prefix Caching) mitigate the problem by storing recurrent-state checkpoints, but prefix reuse remains constrained by checkpoint locations, not by shared-token boundaries.

Key Theoretical Insight

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.

The Gated DeltaNet recurrence is defined as:

$$S_{i} = T_{i} S_{i-1} + \beta_{i} v_{i} k_{i}^{\top}, \qquad T_{i} = \alpha_{i} \big(I - \beta_{i} k_{i} k_{i}^{\top}\big), \tag{1}$$

where $i$ indexes the $i$-th token in the prefix, $k_{i}$ and $v_{i}$ are its key and value vectors, and $\alpha_{i} \in (0, 1]$ is a learned gate that progressively attenuates earlier information.

---

Methodology

Architecture Overview

Tail-Replay caches for each previous input:

• FA layer KV pairs: $(K_{i}^{\mathrm{FA}}, V_{i}^{\mathrm{FA}})$ for each token $i$
• FA output hiddens: $h_{i}$ for each token $i$

On a cache hit covering the first $m$ tokens:

1. Retrieve the FA KV for direct reuse
2. Fetch only the most recent $k = \lceil r \cdot m \rceil$ cached FA output hiddens (replay tail)
3. Reconstruct linear-attention states by replaying the tail

Independent Tail-Replay per Group

The architecture is partitioned into groups, each comprising one FA layer and the consecutive linear-attention layers that follow it. This ensures the input hidden of the first linear-attention layer in every group exactly matches its value during original prefill, confining replay error within each group.

For one linear-attention group, the replay state is initialized to zero at the start of the tail, $\hat{S}_{m-k} = 0$, and the GDN recurrence is applied:

$$\hat{S}_{i} = T_{i} \hat{S}_{i-1} + \beta_{i} v_{i}^{\mathrm{LA}} \big(k_{i}^{\mathrm{LA}}\big)^{\top}, \qquad i = m - k + 1, \ldots, m, \tag{2}$$

The cached FA output hiddens are fed through the group's linear-attention layers, producing $k_{i}^{\mathrm{LA}}$, $v_{i}^{\mathrm{LA}}$, $T_{i}$, and $\beta_{i}$ at each replay step. The final state $\hat{S}_{m}$ approximates the recurrent state at the matched-prefix boundary. This reconstruction is performed independently for every group.

Replay Efficiency Optimizations

1. Tail-FFN Skip: The FFN output at the end of a replayed group is not needed for state reconstruction (the next group starts from the exact cached FA output hidden). Only the linear-attention block of the group's final layer is computed.

2. Transfer/Replay Overlap: Since Tail-Replay does not depend on cached FA KV, the host-to-device transfer of FA KV can proceed concurrently with replay on a separate copy stream. Synchronization occurs only before the query forward.

---

Empirical Validation / Results

Experimental Setup

• Models: OLMo-Hybrid-7B, Qwen3.5-4B, Qwen3.6-27B (all Gated DeltaNet-based)
• Hardware: NVIDIA H100 GPUs, PyTorch 2.9.1
• Benchmarks: LongBench (token-F1 or ROUGE-L) and RULER (recall across eight task–length cells)
• Baselines: Full prefill, Zero-only (reuse FA KV but zero recurrent states without replay)

Quality Results

Table 1: Average quality scores within each benchmark

Key findings: Tail-Replay retains 92.8–98.9% of full-prefill quality on LongBench at r=5% and 93.9–98.1% at r=10%; on RULER, it retains 93.1–99.9% and 96.7–99.9%, respectively. The Zero-only baseline shows substantial quality degradation (e.g., OLMo-Hybrid-7B drops to 0.159 on LongBench vs. 0.317 full), confirming the importance of state reconstruction.

Serving Efficiency (TTFT)

Table 2: TTFT (ms, mean over 20 timed repetitions)

Key findings:

• Speedup grows with prefix length, reaching 9.8×, 9.1×, and 14.3× at 32K for OLMo-Hybrid-7B, Qwen3.5-4B, and Qwen3.6-27B, respectively (5% replay with OVL+skip).
• OVL+skip further reduces TTFT by 18–42% at 32K relative to serialized H2D transfer.
• Increasing replay budget to 10% has little effect at shorter contexts but raises TTFT at 32K, where replay becomes the dominant cost.

---

Theoretical and Practical Implications

Theoretical Significance

1. Escaping the checkpoint constraint: Tail-Replay demonstrates that recurrent-state checkpoints are not necessary for prefix caching in hybrid LLMs—the gated attenuation property of linear attention makes recent-suffix replay sufficient.

2. Generalizable insight: The finding that gated recurrent updates behave as lossy compression with temporal locality suggests broader applicability to other gated linear-attention architectures beyond Gated DeltaNet.

3. Error confinement via grouping: The architectural grouping strategy (FA layer + following linear layers) provides a clean theoretical mechanism for bounding replay error propagation.

Practical Implications

1. Simplified caching infrastructure: By omitting recurrent-state checkpoints, Tail-Replay eliminates the need for complex checkpoint placement and management strategies (as in Marconi and Sparse Prefix Caching).

2. Scalable long-context serving: The TTFT speedups (up to 14.3×) at 32K context make long-context hybrid LLMs substantially more practical for serving workloads.

3. Memory efficiency: Caching only FA KV and FA output hiddens (rather than recurrent states at multiple checkpoints) reduces cache storage overhead.

4. Cost-quality tradeoff: The 5% replay budget offers near-optimal quality at minimal computational overhead, making it a practical default configuration.

---

Conclusion

Main Takeaways

Tail-Replay addresses the fundamental mismatch between token-level prefix sharing and recurrent state in hybrid LLMs. By caching exact FA KV and FA output hiddens, then independently replaying only a recent suffix for each linear-attention group, it enables flexible, unconstrained prefix reuse without recurrent-state checkpoints. Across three Gated DeltaNet-based hybrid models, short replay tails (5–10%) preserve 92.8–99.9% of full-prefill quality while delivering up to 14.3× TTFT speedup at long contexts.

Future Directions

• Application to other linear-attention variants: The approach could be extended to other gated recurrent architectures (e.g., Mamba, RWKV) with similar attenuation properties.
• Adaptive replay budgets: Dynamically adjusting the replay ratio based on task difficulty or accuracy requirements.
• Multi-level caching: Combining Tail-Replay with other caching strategies (e.g., chunk-level caching, semantic caching) for further gains.
• Production serving integration: Deploying Tail-Replay in production serving frameworks with heterogeneous hardware and memory hierarchies.