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.
Methods
The authors introduce FrontierReplay, which centers on three main innovations:
- 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.
- 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.
- 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.
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.
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