acceptodds
Under review as a conference paper at ICLR 2027

CatchUp: Replay the First, Reuse the Rest for Prefix Caching in Hybrid LLMs

Abstract

Hybrid language models can incur substantial recovery latency even when a long prefix is cached: token-indexed full-attention (FA) key–value (KV) caches can match beyond the latest recurrent checkpoint, a snapshot of recurrent-layer states at a prefix boundary. Exact recovery recomputes the full model across this gap, limiting the latency benefit of prefix reuse. Denser checkpoints reduce the gap but increase state storage. We introduce CatchUp, which loads the checkpoint and replays a recent tail only through the recurrent layers preceding the first FA layer. Unlike deeper recurrent layers, which require contextual hidden inputs from the preceding network, these layers can be replayed from token embeddings without an additional per-token input cache. A configurable fraction of the checkpoint gap controls replay work. Deeper recurrent layers retain their checkpoint states, while all FA layers reuse matched KV; the full model then processes the uncached suffix. Across three hybrid models on LongBench question answering and summarization, replaying 10% of the checkpoint gap achieves 4.32–7.94× paired time-to-first-token (TTFT) speedups over full-model recovery (Exact) at an 8K gap on 28 timing inputs. Quality differences from Exact range from −1.83 to +0.14 points on all 139 quality questions at that gap. With a 50% window, Qwen3.6-27B reaches 47.39, close to Exact at 47.44. Fixed-history tool-use evaluation on BFCL and long-context evaluation on RULER extend the study to input budgets up to 64K. On RULER at a 64K budget and a 32K gap, CatchUp differs from the full-prefix quality reference (Reference) by −2.61 to +0.20 points across the three models, compared with −4.44 to −0.07 for Tail-Replay.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Hybrid LLMs, Prefix Caching, Recurrent State Recovery, KV Cache Reuse, Warm-Start Replay, LLM Serving

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_4tTzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes CatchUp, a prefix-cache recovery method for hybrid LLMs. It restores a recurrent checkpoint, replays a fraction of the checkpoint gap only through the first recurrent group, and reuses cached full-attention KV states while retaining deeper recurrent states. Experiments on three hybrid models show substantial reductions in time-to-first-token compared with full-model recovery. The authors also evaluate storage overhead and task quality on LongBench, BFCL, and RULER.

Critical strengths
  1. CatchUp aims to address a practical recovery bottleneck in prefix caching for hybrid large language models. Compared to full-model recovery, this approach significantly reduces latency and eliminates the need to store additional per-token context inputs for deeper recurrent groups.

  2. The evaluation covers three hybrid models across various downstream tasks. Furthermore, the paper analyzes storage overhead and sensitivity to the "replay budget," and includes "no-replay" ablation experiments, providing valuable insights into the trade-off between latency and quality.

Critical weaknesses
  1. The benefit of replay itself is not convincingly established. In Table 6, at an 8K gap and 10% replay, CatchUp improves over Stale on Qwen3.5-4B but performs worse on OLMo-Hybrid-7B and Qwen3.6-27B. Table 7 shows positive confidence intervals excluding zero in only 3 of the 60 configurations, while all 27 RULER comparisons in Table 16 have intervals including zero. Since replay adds computation, its advantage over simply reusing the checkpoint remains unclear.

  2. The comparison with Tail-Replay does not fully isolate the source of the improvement. CatchUp replays 10% of the checkpoint gap, whereas Tail-Replay uses 10% of the matched prefix and processes more recurrent groups. The implementation also excludes Tail-Replay's original transfer-overlap optimization. The reported speedups are therefore specific to these different recovery and execution settings. A comparison under matched computational or latency budgets would better establish the relative benefit of CatchUp.

Questions for authors
  1. Given that "first-group replay" offers only limited and inconsistent improvements over the "stale state" approach, under what conditions is the use of "first-group replay" actually beneficial? Could the authors specify the configurations in which the quality gains are sufficient to offset the additional latency incurred?

  2. How does CatchUp perform compared to "tail-replay" when recovery costs or latency budgets are comparable? If the "transfer-overlap" optimization—a native feature of "tail-replay"—is enabled, do the claimed advantages of CatchUp still hold?

  3. Proposition 1 assumes that gates, keys, and values ​​are shared, while the deeper recurrent states remain unchanged within CatchUp. How does this analysis, which relies on specific assumptions, account for the actual performance observed during the full recovery process?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 4tTz

Thank you for the questions on replay, baseline fairness, and Proposition 1. CatchUp selectively recovers recurrent states while reusing matched FA KV, without an additional deeper-group input cache.

The original A100/vLLM evaluation reports 4.32–7.94× paired TTFT speedups over full-model recovery (Exact) across three models, at an 8K gap and 10% replay on 28 timing inputs. Quality was evaluated separately on 139 inputs, with differences of -1.83 to +0.14 versus Exact. The supplement tests replay's incremental effect and the FFN-skipping Tail comparison.

Q1. When do quality gains offset replay latency?

The state diagnostic asks whether replay repairs the first group. Median matrix-state relative L2 error against the exact producer state falls from 0.4021 for Stale to 0.1645 and 0.0649 for CatchUp 10% and 50%, improving on all 28 inputs. CatchUp uses token-derived first-group inputs and preserves deeper checkpoint states and matched FA KV. Stale also avoids the extra input cache.

Complete-answer evaluation tests whether this repair improves task scores:

MethodMacro scoreRecovery-to-first-token time (ms)
Stale48.6085.28
CatchUp 10%47.9191.66
CatchUp 50%48.22107.67

Paired differences versus Stale are -0.69 (95% interval [-1.47, -0.07]) and -0.38 ([-1.11, 0.27]). On this cohort, replay's additional cost is not offset by a higher task score. These tests establish state repair and distinguish it from task-quality gains.

For Qwen3.5-4B, gap 8192, and 10% replay, the original 139-input result was +0.81 versus Stale (paper interval [-0.32, 2.44]); the 28-input timing subset gave -0.11. The new backend gives -0.69 on those 28 inputs. We report these evaluation scopes separately.

The supplement uses Qwen3.5-4B, gap 8192, BF16, RTX 4090, and HF/FLA with original greedy generation and scoring. Supplemental intervals use 10,000 paired context-cluster bootstrap resamples within tasks, equal task weights, and no multiple-comparison correction (28 inputs, 26 contexts). Timings average per-input medians within tasks and then across tasks, with three warmups and five shuffled rounds, including restoration, required transfers, replay, suffix processing, and returning the first token.

Q2. Comparable recovery budgets and transfer overlap

Latency calibration tests budget comparability: CatchUp budgets against the checkpoint gap, whereas Tail budgets against the matched prefix and replays all groups. With Tail's terminal FFN skipped, we tested windows of 16, 32, 64, 128, 256, 512, 1024, 1536, and 2048 tokens on four fixed, context-disjoint calibration inputs, one per task.

Timing-only selection chose 16 tokens as closest to CatchUp 50%, but it remained 15–37% slower. Tail windows 16–1024 differed in latency by less than 1% on each calibration input. After calibration, before inspecting evaluation quality, we retained the primary 16-token selection and added 1024 as the longest window in Tail's near-constant-cost range.

The paired comparison tests this baseline's quality and cost. Tail-16 scored 41.93. In the secondary run, CatchUp 50% scored 48.22 at 107.49 ms versus Tail-1024's 42.71 at 132.09 ms: +5.50 points, with a wide 95% interval [0.22, 11.96]. CatchUp's outputs matched the main run token-for-token on all inputs. This is a favorable measured operating point; no equal-latency point was found in the tested grid, and Tail-1024 was within 10% of CatchUp 50%'s latency on 0/28 inputs.

A separate FFN-omission test isolates this cost on the supplemental HF/FLA backend. At Tail's original 10%-of-prefix budget, states and first-generation logits remained bitwise identical on all 28 inputs; latency fell by 5.58% (task-balanced mean of paired per-input percentage reductions). CatchUp retains its FFN.

FA KV is GPU-resident, and required state/input transfers are timed. Host-resident KV with optimized transfer/replay overlap remains unmeasured. These results concern the tested backend and residency setting.

Q3. How does Proposition 1 relate to full recovery?

Proposition 1 explains single-layer initial-state error propagation under shared gates, keys, and values. In multilayer recovery, earlier-layer perturbations can alter later updates; deeper groups retain checkpoint states missing gap updates. Token-derived inputs do not ensure shared internal transitions.

The exact-first-group intervention asks whether perfect first-group recovery suffices to improve scores when deeper states remain stale. We installed exact producer recurrent/convolution states only in that group, keeping FA KV unchanged. It scored 47.97, or -0.63 versus Stale (95% interval [-1.60, 0.13]). This separates first-group fidelity from end-to-end behavior. The theory describes the conditional repair mechanism; the experiments assess actual multilayer recovery. The intervention is a diagnostic, not deployable recovery or a quality upper bound.

Reviewer_XEb7OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

CatchUp addresses prefix-cache recovery in hybrid attention LLMs when reusable KV extends beyond the latest recurrent checkpoint. It loads the checkpoint and replays a recent tail through only the first recurrent group, while reusing the matched full-attention KV. This avoids full-model gap recomputation and the additional contextual-input storage required by deeper-group replay. Experiments on three hybrid models report substantial TTFT reductions over exact recovery and evaluate task quality across multiple benchmarks.

Critical strengths
  1. The architecture design is clear. It saves storage by replaying a recent tail only through the recurrent layers preceding the first FA layer.
  2. Catup achieves substantial speed up on prefill compare with the full re-computation baseline.
  3. The paper presents comprehensive ablation studies and evaluation across different settings and baselines.
Critical weaknesses
  1. Insufficient motivation: The paper assumes gaps between 1-8k without evidence supporting how often this happens under realistic checkpoint retention policies.
  2. Unclear necessity of replay: The default 10% replay incurs higher TTFT over Stale without a statistically supported quality gain in the reported benchmark comparisons. Sometimes it not even scores as high as using stale states.
  3. Limited evidence on long horizon: The main evaluation disables thinking without explanation and does not systematically examine long reasoning trajectories or repeated approximate cache recovery.
Questions for authors

See weaknesses.

2 comments
AuthorsOpenReview ↗

Response to Reviewer XEb7

Thank you for the questions about workload realism, replay, and longer-horizon behavior. CatchUp's system contribution is selective recovery that reuses matched FA KV without an additional deeper-group replay-input cache.

In the original A100/vLLM evaluation, 10% replay at an 8K gap achieves 4.32–7.94× paired TTFT speedups over full-model recovery (Exact), across three models on 28 timing inputs. On the separately evaluated 139 quality inputs, score differences versus Exact range from -1.83 to +0.14. The supplement examines what targeted replay adds to this recovery design and how its benefits depend on the comparison being made.

1. How common are 1K–8K gaps under realistic checkpoint retention policies?

The motivating condition is a mismatch between the reusable FA-KV boundary and the latest available recurrent checkpoint. CatchUp addresses recovery from that available checkpoint while preserving the reusable KV.

The paper's 1K–8K sweep asks how recovery behaves as the mismatch grows, holding the input and uncached suffix fixed. It measures sensitivity to gap size. The occurrence of these gaps depends on checkpoint admission and retention policies; our experiments do not estimate that distribution from serving traces. The measured results characterize recovery under specified gaps, while workload-level impact also depends on their frequency.

2. Is default 10% replay necessary when Stale is competitive?

The state diagnostic tests whether replay performs the intended repair. Median first-group matrix-state relative L2 error against the exact producer state decreases from 0.4021 for Stale to 0.1645 and 0.0649 for 10% and 50% replay, improving on all 28 inputs. The first group's external inputs come from tokens, so repair requires no deeper-group contextual-input cache. Stale also avoids this cache; CatchUp adds the repair step.

The FFN-skipping Tail comparison tests selective recovery against multi-group replay after accounting for terminal-FFN skipping. In a paired run, CatchUp 50% scores 48.22 at 107.49 ms, versus 42.71 at 132.09 ms for Tail-1024. The Tail window was selected using timing on separate calibration inputs. This provides a favorable measured operating point at these different budgets and latencies.

Complete-answer evaluation separately tests whether repair improves task scores over Stale:

MethodMacro scoreRecovery-to-first-token time (ms)
Stale48.6085.28
CatchUp 10%47.9191.66
CatchUp 50%48.22107.67

Paired differences versus Stale are -0.69 (95% interval [-1.47, -0.07]) and -0.38 ([-1.11, 0.27]). Stale has the better measured trade-off here. Accordingly, 10% is an evaluated replay setting rather than an established deployment default. These experiments distinguish the consistent state-repair effect from its task-level outcome.

For Qwen3.5-4B at an 8K gap and 10% replay, the original 139-input evaluation reported +0.81 versus Stale (paper interval [-0.32, 2.44]); its 28-input timing subset gave -0.11. The new backend gives -0.69 on those 28 inputs. We keep the full-cohort, subset, and new-backend results separate to preserve their evaluation scopes.

The supplement uses Qwen3.5-4B, gap 8192, BF16, RTX 4090, and HF/FLA, preserving original greedy generation, stopping rules, and scoring. No answer reached its generation cap. Supplemental intervals use 10,000 paired context-cluster bootstrap resamples within tasks, equal task weights, and no multiple-comparison correction (28 inputs, 26 contexts). Timings are task-balanced averages of per-input medians from five shuffled rounds after three warmups, including restoration, required transfers, replay, suffix processing, and returning the first token. These are separate from the original A100/vLLM measurements.

3. What about disabled thinking, long reasoning, and repeated approximate recovery?

The Qwen evaluations use a shared non-thinking protocol and task-specific output limits, providing a controlled comparison of recovery methods under the same generation conditions.

BFCL evaluates recovery at one target turn from a frozen history, and RULER tests longer inputs with short generation limits. The supplemental complete-answer evaluation checks whether first-token diagnostics carry through to generated answers, retaining the original protocol. Together, these experiments characterize individual recovery events and their outputs. Thinking-enabled long reasoning and error accumulation across repeated approximate recoveries remain outside this evaluation scope.

Thanks for the response. However, the response still doesn't answer my main concerns. The sensitivity test cannot explain why this assumption is practical. The benefits over Stale is still incremental. Given the importance of thinking, the performance drift of long-horizon generation after recovery or multiple recoveries during agentic tasks is still not evaluated. Based on these, I will keep my rating.

Reviewer_67ahOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies positional misalignment between Full-Attention KV caches and recurrent checkpoints in Hybrid LLM prefix-cache recovery, where attention KV caches may extend beyond the latest recurrent checkpoint, leading to re-execution overhead. CatchUp addresses this misalignment by restoring the latest recurrent checkpoint and replaying a short tail only through the first recurrent group, while preserving the states of deeper recurrent groups and reusing cached attention KV. This enables approximate recovery without additionally caching the inputs to deeper recurrent groups. Evaluations show that CatchUp reduces recovery latency compared with Exact recompute and requires less persistent storage than Tail-Replay.

Critical strengths
  1. The work is timely and practically relevant. Recent open models, including Qwen3.8 and DeepSeek-V4.1-Flash, move beyond conventional full-attention architectures. These developments make efficient prefix caching and state recovery increasingly important for LLM serving.
  2. The proposed design has practical potential. It avoids an additional per-token replay-input cache. The evaluation covers several models and task types, providing evidence of potential benefits in latency and storage.
Critical weaknesses
  1. The central contribution is not convincingly established. The evidence does not show a reliable quality-latency advantage of first-group replay over the simpler Stale baseline. See Q1.
  2. The paper remains difficult to follow after careful reading. The narrative is fragmented, and the main figures do not clearly communicate the method. Visible drawing and layout defects suggest insufficient manual checking.
Questions for authors

What makes Replay more valuable than Stale?

Stale directly tests the incremental value of first-group replay and should be included in the main paper, rather than as extended ablations in the Appendix.

Furthermore, Tables 7 and 16 show limited and inconsistent quality gains over the Stale baseline. All 27 RULER confidence intervals include zero. In this case, Replay seems rarely necessary, especially in Appendix D.3, where the author also reports additional latency from replay.

Section 5.1 states that the measured Tail-Replay implementation retains each group’s terminal FFN. The original Tail-Replay method explicitly skips this computation. Why was this optimization omitted? Does CatchUp retain the corresponding computation? How significantly does it impact the TTFT comparison?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 67ah

Thank you for the questions about replay's value, baseline fairness, and presentation. CatchUp provides selective recovery from an existing checkpoint while reusing matched FA KV, without storing additional contextual inputs for deeper-group replay.

The original A100/vLLM evaluation establishes the system trade-off against full-model recovery (Exact): at an 8K gap, 10% replay achieves 4.32–7.94× paired TTFT speedups across three models on 28 timing inputs. Quality was evaluated separately on 139 inputs, with score differences of -1.83 to +0.14 versus Exact. The new experiments examine the incremental value over Stale and the comparison with FFN-skipping Tail-Replay.

Q1. What makes replay more valuable than Stale?

Our state diagnostic asks whether first-group replay actually repairs the checkpoint state. Relative to the producer's exact state at the reusable-prefix boundary, median first-group matrix-state relative L2 error decreases from 0.4021 for Stale to 0.1645 and 0.0649 for CatchUp 10% and 50%. Both budgets improve this measure on all 28 inputs. CatchUp obtains the first group's external inputs from tokens and preserves deeper checkpoint states and matched FA KV. Stale also avoids the extra input cache; CatchUp adds targeted repair.

Complete-answer evaluation asks whether that repair improves task scores:

MethodMacro scoreRecovery-to-first-token time (ms)
Stale48.6085.28
CatchUp 10%47.9191.66
CatchUp 50%48.22107.67

Paired score differences versus Stale are -0.69 for 10% replay (95% interval [-1.47, -0.07]) and -0.38 for 50% replay ([-1.11, 0.27]). Stale has the better measured trade-off on this cohort. Thus, the diagnostic verifies state repair, while complete answers show that closer first-group states do not necessarily improve task scores. Stale deserves a prominent place in the main comparison.

For Qwen3.5-4B at an 8K gap and 10% replay, the original 139-input evaluation reported +0.81 versus Stale (paper interval [-0.32, 2.44]); its 28-input timing subset gave -0.11. The new backend gives -0.69 on those 28 inputs. We report these separately to distinguish cohort composition from execution settings. The RULER intervals likewise leave the direction of the quality effect unresolved.

The supplement uses Qwen3.5-4B, gap 8192, BF16, RTX 4090, and HF/FLA with original greedy generation and scoring. Supplemental intervals use 10,000 paired context-cluster bootstrap resamples within tasks, equal task weights, and no multiple-comparison correction (28 inputs, 26 contexts). Timings are task-balanced averages of per-input medians from five shuffled rounds after three warmups, including cache restoration, required transfers, replay, suffix processing, and returning the first token. These are separate from the original A100/vLLM measurements.

Q2. Why retain the terminal FFN, does CatchUp retain it, and how much does it affect TTFT?

The original shared full-layer replay path retained the terminal FFN, including CatchUp's corresponding FFN. Tail processes more groups, so the resulting overhead differs between methods.

The FFN-omission experiment isolates this cost on the supplemental HF/FLA backend. At Tail's original budget of 10% of the matched prefix, recovered recurrent/convolution states and first-generation logits remained bitwise identical on all 28 inputs. Task-balanced time decreased from 155.74 to 146.57 ms. The task-balanced mean of paired per-input percentage reductions was 5.58%; this differs from the percentage change between the two overall means.

The FFN-skipping baseline experiment then asks how CatchUp compares when Tail includes that optimization. A 1024-token Tail window was selected using only timing on four separate calibration inputs. In the paired run, CatchUp 50% scored 48.22 at 107.49 ms, versus Tail-1024's 42.71 at 132.09 ms. CatchUp retained its FFN. This is a favorable measured operating point for selective recovery. The budgets differ, FA KV is GPU-resident, and host-resident KV with optimized transfer/replay overlap remains unmeasured.

Presentation and figures

A clearer explanation centers on two boundaries: p is the recurrent checkpoint boundary, and q is the reusable FA-KV boundary. Stale restores states at p and reuses KV through q. CatchUp uses the same checkpoint and KV but replays a recent tail ending at q through the first recurrent group. Deeper groups retain their checkpoint states; both methods then process the uncached suffix. This identifies the replay scope and source of approximation directly.

Thank you for the response and additional experiments. My main concern in Q1 remains unresolved. On the 28-input cohort, Stale was faster and scored higher on average than both replay settings. The result reported to Reviewer 4tTz reinforces this concern that even restoring the exact first-group state yielded no observed quality gain over Stale. I also saw no improvement in the manuscript’s writing, figures, or layout. I will therefore maintain my original rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.