cs.LGNov 19, 2026

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

Authors: Zekun Wang, Yizhuo Wang

Organizations: School of Computer Science, Beijing Institute of Technology

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.

Figures & tables

Explore similar work

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

    Sep 27, 2026Yirui Liu, Ruoling Qi, Xuaner Wu +6Long-Context Language Model InferenceLLM Inference Acceleration

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

    Aug 31, 2026Yirui Liu, Ruoling Qi, Xuaner Wu +2LLM Inference AccelerationPrefix Caching