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

> SuffixReplay enables fine-grained prefix caching in hybrid LLMs by reconstructing linear-attention states from sparse anchors, cutting storage by 2x and TTFT by up to 70%.

- **Source:** [arXiv](https://arxiv.org/abs/2609.33477)
- **Published:** 2026-10-03
- **Permalink:** https://picx.dev/p/LWTNcl
- **Whiteboard:** https://picx.dev/p/LWTNcl/image

## Summary

# SuffixReplay: Prefix Caching via Suffix Replay for Hybrid LLMs

## Summary (Overview)

- **Core Problem**: Hybrid LLMs (interleaving full-attention and linear-attention layers) cannot reuse cached prefixes at arbitrary positions because linear-attention layers maintain recurrent states that cannot be rolled back to earlier prefix boundaries.
- **Key Insight**: Modern linear-attention mechanisms use decay and gating to attenuate distant inputs, so instead of storing expensive state checkpoints, SuffixReplay reconstructs linear states by replaying only a recent suffix of cached hidden states (anchors).
- **Main Contribution**: First prefix-caching system giving hybrid LLMs the same fine-grained prefix-reuse granularity as full-attention models, without materializing recurrent-state checkpoints.
- **Results**: Retains 91.4–100% of full-prefill quality on LongBench/RULER, uses only 0.36–0.51× the storage of SGLang's native checkpoint cache, reduces median TTFT by 15–70% on branching workloads, and sustains 2.3–4.3× throughput when working set exceeds HBM.
- **System Integration**: Implemented on SGLang v0.5.18 with an anchor sidecar for storage management and a pipelined replay path overlapping with native serving.

## Introduction and Theoretical Foundation

### Background
LLM workloads (multi-turn dialogue, RAG, tool-using agents) demand long contexts, repeated invocations, and high concurrency. Two complementary techniques address these pressures:
- **Model level**: Hybrid architectures combine full-attention (FA) layers with linear-attention layers to reduce quadratic computation.
- **Serving level**: Prefix caching reuses shared prefixes across requests to avoid redundant prefill.

### The Mismatch
In FA-only models, KV caches are token-addressable, so any prefix boundary can be reused. In hybrid models, linear-attention layers maintain recurrent states that cannot be rolled back. Existing approaches (Marconi, Sparse Prefix Caching, SGLang) materialize state checkpoints at selected positions, discretizing prefix reuse.

**Key problem**: A linear-attention state checkpoint in Qwen3.5-4B is ~49 MiB vs. ~32 KiB for a single-token KV entry (~1,500× larger). Dense checkpoints are prohibitively expensive.

### Theoretical Foundation

The state at any prefix position $j$ is a deterministic function of inputs:

$$S_j = f(h_1, \ldots, h_j)$$

**(Equation 1)**

Since modern linear attention attenuates distant inputs via recurrent decay and erase gates, the state can be approximated by replaying only a recent suffix:

$$S_j \approx S'_j = f(h_{j-k+1}, \ldots, h_j)$$

**(Equation 2)**

where $k$ is the suffix length. The state update rule is:

$$S_t = A_t(S_{t-1}) + B_t, \quad S_0 = 0$$

**(Equation 4)**

where $A_t$ is a linear transformation (e.g., per-head decay in Mamba2, or decay + rank-one erase in Gated DeltaNet) and $B_t$ is the write from token $t$.

### Design Requirements
- **R1 (Quality)**: At least 90% of full-prefill quality on LongBench/RULER.
- **R2 (Storage)**: Additional storage bounded by SGLang's amortized checkpoint cost: $B_{\text{anchor}} \leq B_{\text{ckpt}}/8192$ (Equation 3).
- **R3 (Performance)**: Match or outperform SGLang in TTFT, throughput, and capacity.

## Methodology

### Algorithm Design

#### 1. Layer-wise Sparse Anchors
- Groups consecutive linear-attention layers into independent replay blocks (separated by FA layers).
- Stores one **group-entry anchor** per group rather than per layer, reducing storage from O($L$) to O($G$).
- Replay executes only linear-attention computation within groups (skipping FA layers), so cost depends on replay length, not matched context length.
- Errors don't propagate across group boundaries.

#### 2. Token-wise Sparse Anchors
- Retains anchors at only a subset of token positions, aligned with page boundaries (64-token pages).
- Anchor density $\rho = 1/16$ gives 0.36–0.51× SGLang's storage.
- **Dense sampling** (anchors concentrated near page boundary) outperforms uniform sampling in quality stability (Figure 3).

#### 3. Replay Budget
- Replay length measured in anchors: $k = \min(0.05n, k_{\text{max}})$ for prefix length $n$.
- Conservative caps: $k_{\text{max}} = 512$ for Qwen3.5-4B, $k_{\text{max}} = 256$ for Qwen3.6-27B-FP8.

### System Design

#### Anchor Sidecar
- Each anchor block attaches to the same radix-tree node as its KV page, sharing admission/eviction decisions.
- Independent physical pools: anchors can reside in host DRAM while KV pages stay in GPU HBM.
- **CUDA-graph writes**: Destination table precomputed on host; indexed copies in captured CUDA graphs write selected hidden states directly to sidecar locations, avoiding host synchronization overhead.

#### Pipelined Replay Path
- Anchor fetching launches asynchronously on a dedicated copy stream immediately after radix-tree match, overlapping with KV backfill.
- **Layer-wise handoff**: Replay and extend execution synchronized at group boundaries; forward stream waits only when reaching a layer consuming reconstructed state.
- **Batched replay**: Multiple hits packed into one variable-length execution with device-side boundaries; graphs bucketed by total packed length.

#### Live-State Fast Path
- Multi-turn continuations with resident live state bypass replay entirely.
- Live state is best-effort only; replay path remains the correctness path.

## Empirical Validation / Results

### Quality (Table 3)

| Model | Replay Budget $k$ | LongBench QA Avg | RULER Avg |
|-------|-------------------|-------------------|-----------|
| OLMo-Hybrid-7B | 512 | 95.9% | 91.4% |
| Qwen3.5-4B | 128 | 100% | 99.7% |
| Qwen3.6-27B-FP8 | 128 | 99.1% | 100% |

Both Qwen models remain above 94% even at $k=16$, showing near-insensitivity to replay truncation. OLMo requires larger budgets.

### Storage Efficiency (Table 2)

| Model | SGLang@8192 (KiB) | Naive (KiB) | SuffixReplay (KiB) | Ratio |
|-------|-------------------|-------------|---------------------|-------|
| OLMo-7B | 6.5 | 180 | 3.3 | 0.50× |
| Qwen3.5-4B | 6.1 | 120 | 2.2 | 0.36× |
| Qwen3.6-27B-FP8 | 18.4 | 480 | 9.4 | 0.51× |

### Serving Performance

#### Branching Workloads (Figure 8)
- **ShareGPT**: 15–20% median TTFT reduction.
- **ToolMind (~5K context)**: 20–40% reduction.
- **ToolMind (16K+ context)**: 55–70% reduction.
- SGLang saturates earlier (ShareGPT at 4 sessions/s on 4B vs. SuffixReplay stable at 8 sessions/s).

#### Checkpoint Grid Distance (Figure 9)
- Benefits grow with distance from SGLang's latest checkpoint: 41–42% TTFT reduction at 4K–8K, 66% at 16K on 4B.

#### Branches Between Checkpoints (Figure 10)
- SGLang recomputes 0.6–7.7K tokens (saw-tooth TTFT 30–175 ms); SuffixReplay serves every cut in ~33 ms.
- With 8 sessions: SuffixReplay reduces median TTFT from 369 ms to 72–94 ms (3.9–5.1×).

#### High-Hit Continuation (Table 4)
- Matches or slightly exceeds SGLang throughput (+2.7 to +6.5% at 8–16 sessions) with equal or lower TTFT.

#### Capacity (Figure 12)
- When working set exceeds HBM: SuffixReplay maintains 0.85 hit rate and 2.5–2.6 req/s vs. SGLang's 0.05 hit rate and 0.6 req/s (2.3–4.3× throughput).

### Checkpoint Trade-offs (Table 5)

| SGLang prefill chunk | 8192 (stock) | 2048 | 1024 |
|----------------------|--------------|------|------|
| Cold prefill TTFT p50 | 677 ms | 823 ms (+22%) | 1,268 ms (+87%) |
| Throughput | 13.8 req/s | 14.1 | 11.5 (−16%) |
| State bytes/token | 6,286 | 25,144 | 50,288 |

## Theoretical and Practical Implications

### Theoretical Significance
1. **Establishes that recurrent state reconstruction via suffix replay is viable** for modern hybrid LLMs with decay-based linear attention (Mamba2, Gated DeltaNet).
2. **Shows quality is model-dependent**: Qwen models show near-insensitivity to truncation ($k=128$ achieves ~100%), while OLMo requires larger budgets—indicating different forgetting characteristics across architectures.
3. **Formalizes the storage-quality-computation trade-off** in hybrid prefix caching, with a clear algorithmic framework (layer-wise + token-wise sparsity).

### Practical Implications
1. **Enables fine-grained prefix reuse without dense checkpoints**, eliminating the 1,500× storage overhead problem.
2. **Removes checkpoint-grid alignment constraints**: any 64-token page boundary is reusable, not just checkpoint-aligned positions.
3. **Improves capacity**: anchors page with KV cache, unlike fixed HBM slot pools for checkpoints.
4. **Production-ready integration**: Only ~1.2K lines of engine changes; stock SGLang runs unchanged when component disabled.

## Conclusion

SuffixReplay demonstrates that prefix caching for hybrid LLMs need not be discrete. By storing sparse anchors (inputs to linear layers) and reconstructing states via bounded suffix replay, it achieves:

- **Fine-grained reuse**: Every 64-token page boundary reusable.
- **Quality preservation**: ≥94% of full-recompute quality (91.4–100% on benchmarks).
- **Storage efficiency**: 0.36–0.51× native checkpoint storage.
- **Performance**: 41–69% median TTFT reduction on branching workloads, 2.3–4.3× throughput when working set exceeds HBM.

**Future directions**:
- Automatic per-model replay budget calibration (currently offline).
- Extension to recurrences without decay (outside current scope).
- Application of admission policies (e.g., Marconi) to anchor page retention decisions.

---

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