Just Let Linear States Forget the Distant Past: Prefix Caching via Suffix Replay for Hybrid LLMs

Yirui Liu; Ruoling Qi; Xuaner Wu; Yuxin Jin; Jian Chen; Penghang Liu; Yafei Huang; Jiawei Shao

cs.AISep 27, 2026

Just Let Linear States Forget the Distant Past: Prefix Caching via Suffix Replay for Hybrid LLMs

Authors: Yirui Liu, Ruoling Qi, Xuaner Wu, Yuxin Jin, Jian Chen, Penghang Liu, Yafei Huang, Jiawei Shao, +1 more

Organizations: Institute of Artificial Intelligence, China Telecom (TeleAI) China · Shanghai Jiao Tong University · Individual Researcher · Tsinghua University Institute of Artificial Intelligence, China Telecom (TeleAI) China

Abstract

Hybrid LLMs interleave full-attention layers with linear-attention layers to reduce long-context inference cost, but this structure complicates prefix caching. Full-attention KV caches are token-addressable, whereas linear-attention layers maintain recurrent states that cannot be rolled back to arbitrary prefix boundaries. Existing systems materialize recurrent-state checkpoints, restricting prefix reuse to checkpoint-aligned positions. We present SuffixReplay, the first prefix caching system that lets hybrid LLMs reuse cached prefixes at every cache-supported page boundary without materializing recurrent-state checkpoints. Our key insight is to just let linear states forget the distant past. Modern linear-attention mechanisms use recurrent decay and gating to attenuate the influence of old inputs. Therefore, instead of checkpointing every prefix boundary, SuffixReplay approximates the state at a matched boundary by replaying only a recent suffix of the layer's input hidden states, which we retain as anchors. At the algorithmic level, SuffixReplay combines layer-wise and token-wise anchor sparsity with a bounded replay budget to control storage, computation, and quality. At the system level, it uses an independently managed anchor sidecar and a pipelined replay path to overlap anchor movement and state reconstruction with the native serving pipeline. We evaluate SuffixReplay on three hybrid LLMs: OLMo-Hybrid-7B, Qwen3.5-4B, and Qwen3.6-27B-FP8. Across these models, SuffixReplay retains 91.4-100% of full-prefill quality on average across LongBench and RULER, while using only 0.36-0.51x the amortized per-token storage of SGLang's default 8192-token checkpoint cache. Integrated into SGLang, SuffixReplay reduces median TTFT by 15-70% on branching workloads, sustains 2.3-4.3x SGLang's throughput when the working set exceeds HBM, and matches SGLang on high-hit continuation traffic.

Figures & tables

Model	SGlang@8192	Naive	Ratio
OLMo-7B	6.5	180	27.6 $\times$
Qwen3.5-4B	6.1	120	19.5 $\times$
Qwen3.6-27B-FP8	18.4	480	26.2 $\times$

Table 1. Additional storage per token (KiB) on top of the KV cache. Appendix A derives both columns.

Model	$A$	SGlang	Naive	Ours	Ours/Native
OLMo-7B	7	6.5	180	3.3	0.50 $\times$
Qwen3.5-4B	7	6.1	120	2.2	0.36 $\times$
Qwen3.6-27B-FP8	15	18.4	480	9.4	0.51 $\times$

Table 2. Additional storage per token (KiB) with anchors at the entry of each group (

A

layers) and anchor density

\rho=1/16

(Ours), against SGLang’s cache at its 8192-token interval and naive replay (Table 1 ). SuffixReplay stores

A\cdot d\cdot 2\rho

bytes per token; Appendix A gives the derivation.

	OLMo-Hybrid-7B						Qwen3.5-4B				Qwen3.6-27B-FP8
Cell	$k{=}16$	32	64	128	256	512	$k{=}16$	32	64	128	$k{=}16$	32	64	128
LongBench QA
NarrativeQA@16K	85.8	88.1	91.1	92.5	93.6	97.2	97.5	98.5	100	100	98.3	97.2	100	99.3
NarrativeQA@32K	84.2	91.0	93.3	94.8	95.3	95.4	91.6	91.8	97.4	97.9	100	95.8	99.2	100
NarrativeQA@64K	85.6	82.9	86.8	92.8	93.3	96.8	94.1	96.5	100	99.2	95.7	100	97.2	99.7
HotpotQA@16K	86.8	89.9	90.9	95.5	92.5	94.1	99.2	99.5	99.6	100	99.2	98.1	97.5	97.4

Table 3. Anchor replay quality relative to full prefill (%full) for different replay budgets

k

. Each entry is a paired sample average; entries below 90% are bold. @ denotes context length.

		throughput (req/s)		TTFT p50 (ms)
model	$N$	SGLang	ours	SGLang $\to$ ours
Qwen3.5-4B	8	21.9	23.1 (+5.4 %)	54 $\to$ 47
	16	26.9	27.6 (+2.7 %)	62 $\to$ 57
	32	32.7	32.2 ( $-1.4$ %)	68 $\to$ 65
Qwen3.6-27B-FP8	8	8.8	9.3 (+5.6 %)	97 $\to$ 86
	16	11.4	12.1 (+6.5 %)	119 $\to$ 107

Table 4. High-hit agent continuation with 240 multi-turn traces and a 98% hit rate. Results use closed-loop HBM-only serving;

N

is the number of concurrent sessions.

SGLang prefill chunk	8192 (stock)	2048	1024
cold prefill TTFT p50 (ms)	677	823 (+22 %)	1,268 (+87 %)
throughput (req/s)	13.8	14.1	11.5 ( $-16$ %)
state bytes per cached token	6,286	25,144	50,288

Table 5. Effect of smaller SGLang prefill chunks on cold-prefill TTFT, throughput, and checkpoint storage. Results use Qwen3.5-4B in HBM-only serving.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

	OLMo-7B	Qwen3.5-4B	Qwen3.6-27B
$L_{\text{lin}}$	24	24	48
$d$	3840	2560	5120
$H_{k}$ / $H_{v}$	30 / 30	16 / 32	16 / 48
$d_{k}$ / $d_{v}$	96 / 192	128 / 128	128 / 128
$C$	11,520	8,192	10,240
$B_{\text{rec}}$	2,211,840	2,097,152	3,145,728

Appendix

Table 6. Model parameters and the resulting sizes. All three models use convolution kernel width

w=4

Explore similar work

Aug 31, 2026cs.LG

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

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.

Yirui Liu, Ruoling Qi, Xuaner Wu +2

Institute of Artificial Intelligence, China Telecom (TeleAI) · Shanghai Jiao Tong University

Kimi Delta Attention Linear Attention Efficient Long-Context Inference Cache Recurrent State Gated Deltanet+1

Ask PDF

Apr 17, 2026cs.LG

Sparse Prefix Caching for Hybrid and Recurrent LLM Serving

Prefix caching is a key latency optimization for autoregressive LLM serving, yet existing systems assume dense per-token key/value reuse. State-space models change the structure of the problem: a recurrent layer can resume from a single stored state rather than requiring the entire token history. This asymmetry opens a new design point between no reuse and dense caching: store exact recurrent states at a sparse set of checkpoint positions and, on a cache hit, resume from the deepest stored checkpoint and recompute the remaining suffix exactly. We formalize sparse prefix caching as checkpoint placement under a distribution over overlap depths, yielding an exact O(NM) dynamic program. For use cases where requests share a non-trivial prefix (e.g. asking different questions about a single long document), we show that our method consistently improves the Pareto frontier traced by standard heuristics on real-world data. Across QuALITY and System Prompts, distribution-aware placement dominates every fixed-budget baseline on the measured layer-group Pareto frontier and matches or outperforms the strongest heuristic (block caching) while typically using substantially fewer checkpoints, with the largest gains at low checkpoint budgets where the overlap distribution is most non-uniform. The method is most relevant when many requests share a substantial but not identical prefix within a retained cache entry. It preserves exact outputs, does not change the recurrent computation itself or require new recurrent update kernels, applies to recurrent/SSM layers whose hidden state can be extracted and restored exactly, and for hybrid models can be combined with existing KV-cache compression techniques.

Mikhail Shirokikh, Sergey Nikolenko

Large Language Model Serving Recurrent Model Intermediate Checkpoints

Ask PDF

Jul 31, 2026cs.AI

LinearKV: One Cached State Suffices for Position-Independent Caching in Hybrid LLMs

LLM serving is increasingly accelerated by position-independent caching (PIC). Existing PIC methods, however, are built for full-attention models, where a token-indexed KV cache underlies its core operations: matching reusable token chunks, concatenating their KV entries, and selectively recomputing a few tokens to restore cross-chunk context. Hybrid LLMs break these primitives---they replace most attention layers with linear recurrences that expose only a fixed-size state, leaving no token-indexed KV to concatenate or to locally repair. This raises a natural question: can PIC benefit hybrid models, and what would it take? We present LinearKV, a training-free hybrid-PIC framework. Its key insight is a \emph{decoupled initialization}: each linear layer maps its

K

matched local states to a single initial state, while full-attention layers concatenate their KV as before. LinearKV is therefore compatible with existing PIC methods, reusing their token selection and recomputation as-is. Under this framework, we find that a \emph{single cached state} suffices as the linear layer's initializer. The algebraically principled alternative---composing all

K

cached states into the exact full-prefix state, as concurrent work HYPIC does---is unnecessary and, on some architectures, even harmful. We compare the two across three hybrid models and three PIC selectors. On the two GDN models the two tie, both recovering most of full quality (up to

92\%

); on the Mamba-2 model, exact composition instead collapses under every selector---under EPIC, for instance, it recovers only

46.6\%

of full quality, versus

86.8\%

for a single cached block initializer. A single state initializer is also cheaper, cutting time-to-first-token to

0.46\times

full prefill versus a further

5

17\%

overhead for exact composition; results hold across LongBench QA and RULER at 8K--32K.

Yirui Liu, Ruoling Qi, Longwen Wang +5

Institute of Artificial Intelligence, China Telecom (TeleAI) · Shanghai Jiao Tong University · Xi’an Jiaotong University +1

Kimi Delta Attention Key-Value Cache

Ask PDF