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)

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

Storage Efficiency (Table 2)

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)

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.