FrontierReplay: Split-Free Exact Prefix Caching for Hybrid Language Models

Zekun Wang, Yizhuo WangarXiv 2026 · arXiv

TL;DR

FrontierReplay is a novel prefix caching system for hybrid language models (like Qwen3.5 and Falcon-H1) that achieves up to 4.26× higher throughput and 89% lower latency. It avoids the performance pitfalls of traditional caching by using a "split-free" checkpointing method: instead of interrupting the model's computation to save state, it logs a small amount of data and uses a hyper-efficient "replay" kernel to reconstruct exact checkpoints in the background.

What Problem Does This Paper Address?

Modern "hybrid" language models combine standard self-attention with recurrent layers (like Mamba-2 or Gated DeltaNet) to handle massive contexts efficiently. However, these models are a nightmare for prefix caching—the technique of saving the "brain state" of a prompt so it doesn't have to be recomputed for every follow-up question.

In standard Transformers, you can cache and reuse Key-Value (KV) data at almost any point. In hybrid models, the recurrent state is a single, compressed tensor that "folds" the entire history into itself. To reuse a prefix, you must resume from the exact token where the state was saved.

Current systems like vLLM save these states on a coarse grid (e.g., every 528 tokens). If a user's chat turn ends at token 600, the system has to recompute everything from token 528 to 600. While "fine-grained" caches exist, they usually require "cutting" the prefill process into multiple steps to save the state at the right spot. This "cutting" adds significant scheduling overhead, often making the "optimized" system slower than the one doing full recomputation.

Figure 1: Reuse ends at predictable positions that vLLM’s state grid misses. Measured across each workload trace with an unbounded KV cache. (a) Share of reusable prefix tokens that lie past the last state block boundary of vLLM. (b) Share of reusable prefix tokens by where the prefix ends. A turn boundary is the template stable end or the end of a finished turn. A known branch point is one where two earlier requests have already diverged.

Methods

The authors introduce FrontierReplay, which centers on three main innovations:

  1. Split-Free Checkpointing: Instead of stopping the model to save a state, FrontierReplay lets the "prefill" (initial processing) run uninterrupted. While it runs, the system logs the inputs to the recurrent layers. After the main pass finishes, a specialized state-only replay kernel recomputes the exact state at the desired boundary. This is 6–37× cheaper than a full model pass because it skips the most expensive parts of the model: the attention and MLP layers.
  2. Boundary Planner: The authors observed that prefix reuse isn't random; it almost always ends at predictable "structural boundaries," such as the end of a chat turn or a branch point in a search tree. The planner identifies these targets in advance without needing to see the future.
  3. Frontier-Aware Retention: Since recurrent states are large (up to 67 MiB each), the system uses a tiered eviction policy. It prioritizes "anchors" (the ends of active conversations) and "proven branches" (points where multiple requests have diverged before). It also dynamically "lends" memory from the state cache back to the attention KV cache when it's not needed.
Figure 3: Two ways to obtain the exact state at a reuse boundary t. (a) Cutting vs (b) Split-free checkpointing.

Datasets

The system was evaluated using four diverse public workload traces:

  • ShareGPT: Multi-turn chat conversations.
  • SWE-agent: Tool-use sessions for software engineering tasks.
  • LongBench: Question answering over long documents (8K–30K tokens).
  • ToT (Tree of Thoughts): Complex reasoning using GSM8K search trees.

Evaluation was performed on Qwen3.5 (4B, 9B, 27B) and Falcon-H1 (7B, 34B) models.

Key Insights and Ideas

  • The "Cutting" Penalty: The most surprising finding is that the act of "cutting" a prefill into two steps to save a checkpoint is often more expensive than the computation it saves. FrontierReplay’s "split-free" approach is the key to unlocking real-world gains.
  • State-Only Replay is a Superpower: Because recurrent state updates are mathematically separable from the rest of the model, you can recompute them in isolation. As models scale up, this "leverage" increases: for a 34B model, replaying the state is nearly 37× faster than running the full model (Figure 4).
  • Exactness Matters: Some competing methods use "approximate" states to save time. The authors show that on long contexts, these approximations can cause a 17% drop in task accuracy. FrontierReplay provides bit-for-bit exact states, preserving the model's original performance.

Key Results

  • Latency: Reduced median Time to First Token (TTFT) by 16–89% across all workloads.
  • Throughput: Improved "goodput" (requests served within latency targets) by up to 4.26× compared to vLLM.
  • Capacity: Raised the 80% Service Level Objective (SLO) capacity by up to 1.73×.
  • Scaling: The benefits actually increase with model size, making this a future-proof strategy for the next generation of massive hybrid models.
Figure 4: GPU efficiency of state-only replay vs full prefill.

Limitations and Future Work

The authors note that their current implementation uses static memory pools for tensor-parallel models. In scenarios where workloads are extremely memory-constrained (KV-capacity bound), these static pools can be less efficient than a fully unified memory pool. They suggest that dynamic cross-pool scaling—automatically shifting memory between the KV cache and the state checkpoints based on real-time demand—is a promising direction for future research.

Summary updated

Abstract

Hybrid language models combine self-attention with recurrent layers whose in-place state updates restrict prefix reuse to exact saved positions. Saving states on a coarse grid wastes reusable prefixes, whereas existing fine-grained exact caches must cut the prefill forward pass at each mid-prompt checkpoint, adding scheduler steps that outweigh the reuse gains under load. We observe that across multi-turn chat, agent loops, document question answering, and tree search, prefix reuse almost always ends at structural boundaries predictable in advance, such as turn ends and known branch points. We present FrontierReplay, a prefix caching system that materializes exact checkpoints at these boundaries without cutting the prefill. While the forward pass runs uncut, FrontierReplay logs a short window of recurrent-layer inputs and invokes a cross-layer, state-only replay kernel to build the target state 6-37x cheaper per token than full recomputation without host synchronization. A frontier-aware retention policy prioritizes active anchors and proven branches while lending dead checkpoint slots to the attention KV cache. Across diverse hybrid architectures, model scales, and workloads, FrontierReplay delivers clear gains over existing exact caches, lowering median time to first token (TTFT) by 16-89% (up to 8.9x), raising 80% service-level objective (SLO) capacity by up to 1.73x, and improving goodput by up to 4.26x (3.67x at larger scales). Compared with approximate replay methods, FrontierReplay delivers up to 1.54x higher goodput while preserving exact task accuracy, avoiding the up to 17% accuracy drop suffered by approximation on long contexts.
BibTeX
@misc{wang2026frontierreplay,
  author = {Zekun Wang and Yizhuo Wang},
  title = {{FrontierReplay: Split-Free Exact Prefix Caching for Hybrid Language Models}},
  year = {2026},
  eprint = {2611.26020},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.26020},
}
Figure