# Tail-Replay: Escaping the Curse of Linear Attention in Prefix Caching for Hybrid LLMs

> Tail-Replay enables unconstrained token-level prefix caching in hybrid LLMs by replaying only a 5-10% recent suffix to reconstruct linear-attention states, preserving 92.8-99.9% quality while achieving up to 14.3x TTFT speedup.

- **Source:** [arXiv](https://arxiv.org/abs/2608.30310)
- **Published:** 2026-09-19
- **Permalink:** https://picx.dev/p/sbxqVx
- **Whiteboard:** https://picx.dev/p/sbxqVx/image

## Summary

## 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**

| Model | LongBench Full | LongBench Zero | LongBench r=5% | LongBench r=10% | RULER Full | RULER Zero | RULER r=5% | RULER r=10% |
|---|---|---|---|---|---|---|---|---|
| Qwen3.6-27B | 0.426 | 0.313 | 0.410 (96.2%) | 0.417 (97.8%) | 0.987 | 0.299 | 0.985 (99.8%) | 0.986 (99.9%) |
| Qwen3.5-4B | 0.374 | 0.271 | 0.369 (98.9%) | 0.367 (98.1%) | 0.960 | 0.415 | 0.959 (99.9%) | 0.958 (99.7%) |
| OLMo-Hybrid-7B | 0.317 | 0.159 | 0.294 (92.8%) | 0.297 (93.9%) | 0.812 | 0.215 | 0.756 (93.1%) | 0.785 (96.7%) |

**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)**

| Model | Matched prefix length | FULL | 5% H2D-SER | 5% H2D-OVL+skip | 10% H2D-SER | 10% H2D-OVL+skip |
|---|---|---|---|---|---|---|
| OLMo-Hybrid-7B | 8,225 | 264.3 | 100.7 | 82.9 (3.19×) | 101.2 | 82.7 (3.20×) |
| OLMo-Hybrid-7B | 16,417 | 533.7 | 122.3 | 83.5 (6.39×) | 121.7 | 85.6 (6.24×) |
| OLMo-Hybrid-7B | 31,366 | 1068.3 | 158.8 | 108.8 (9.82×) | 191.7 | 112.5 (9.50×) |
| Qwen3.5-4B | 8,226 | 191.6 | 81.3 | 75.2 (2.55×) | 82.0 | 75.9 (2.53×) |
| Qwen3.5-4B | 16,418 | 387.7 | 87.0 | 75.0 (5.17×) | 87.7 | 76.0 (5.10×) |
| Qwen3.5-4B | 31,847 | 786.4 | 105.8 | 86.2 (9.12×) | 133.9 | 108.1 (7.27×) |
| Qwen3.6-27B | 8,226 | 879.6 | 166.6 | 154.3 (5.70×) | 167.4 | 154.7 (5.69×) |
| Qwen3.6-27B | 16,418 | 1797.2 | 187.7 | 161.6 (11.12×) | 260.8 | 218.1 (8.24×) |
| Qwen3.6-27B | 31,847 | 3605.2 | 311.9 | 251.8 (14.32×) | 453.9 | 371.3 (9.71×) |

**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.

---

_Markdown view of https://picx.dev/p/sbxqVx, served by PicX — AI-generated visual whiteboard summaries of research papers._