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

2608.30310 ↗ · 2026-08-31 · cs.LG, cs.AI

Yirui Liu, Ruoling Qi, Xuaner Wu, Penghang Liu, Jian Chen

The finding

Headline claim

In Gated DeltaNet-based hybrid LLMs, the linear-attention recurrent state for a cached prefix can be accurately reconstructed by replaying only a short recent suffix (5-10% of the prefix), enabling unconstrained token-level prefix caching with 92.8-99.9% of full-prefill quality and up to 14.3x TTFT speedup at 32K.

The test

Three Gated DeltaNet hybrid models (OLMo-Hybrid-7B, Qwen3.5-4B, Qwen3.6-27B) on H100 GPUs: LongBench and RULER quality at replay ratios of 5% and 10% versus full prefill and a zero-state baseline, plus TTFT at matched-prefix lengths of ~8K/16K/32K over 20 timed repetitions using shared NarrativeQA prefixes.

Effect size & scope

With a 5% replay budget, quality retention is 92.8-98.9% on LongBench and 93.1-99.9% on RULER; TTFT speedups over full prefill reach 9.8x, 9.1x, and 14.3x at 32K (OLMo, Qwen3.5-4B, Qwen3.6-27B), with overlapped transfer plus FFN-skip cutting TTFT 18-42% versus serialized transfer. The weakest cell is OLMo-Hybrid-7B at 92.8% LongBench / 93.1% RULER, so retention depends on model and task; replay cost dominates at 10% budget and 32K, eroding speedup (e.g. Qwen3.6-27B drops from 14.3x to 9.7x).

Limitations

Evaluations cover only Gated DeltaNet-style linear attention, three models, and a narrow benchmark set with benchmark-level averages; efficiency tests use a single workload type (shared NarrativeQA prefixes), mean over 20 repetitions, and cache-hit scenarios only; no comparison to checkpoint-based systems like Marconi on identical settings is reported; per-cell results show some 2-6 point drops (e.g. OLMo qasper 0.394 to 0.308). Authors do not discuss storage overhead of caching FA output hiddens for every FA layer.

Counterpoint

The zero-only baseline is a weak strawman; the real comparison, against Marconi or Sparse Prefix Caching with checkpoints, is missing, so whether replay beats stored checkpoints on the quality-latency-storage tradeoff is untested. Benchmark suites like RULER needle tasks may be insensitive to degraded long-range state (gated decay means early tokens matter less), so quality retention may not transfer to tasks where prefix-early information is critical. Results are confined to one linear-attention family, and the evaluation is by the method's own authors with no code-independence check.

Economy implication

Little direct economic evidence yet; but if hybrid linear-attention models become standard for long-context serving, removing the checkpoint constraint makes prefix caching cheap and flexible enough to deploy broadly, incrementally lowering per-token serving cost at long contexts, one of several compounding inference-cost reductions rather than a step change.

Who this matters for

Technical Capability: Systems and inference engineers get a concrete mechanism to combine hybrid architectures with prefix caching, previously incompatible, with measured quality-latency tradeoffs.

Market & Valuation: Falling long-context serving costs strengthen the case that inference, not training, is where cost competition and margin pressure will concentrate over the next couple of years.

Bears on (advisory · papers never write evidence)

[3.1] Inference cost per unit of capability is falling rapidly.

Abstract

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.