acceptodds
Under review as a conference paper at ICLR 2027

Budgeted Cache Repair for Cross-Context KV-Cache Reuse

Abstract

Cross-context KV-cache reuse predicts a shared segment's keys and values under a new prefix instead of recomputing them, and has been reported to do so without quality loss. We find otherwise, and identify two problems. (1) A hidden cost: on MMLU and GSM8K, reuse costs substantial accuracy. (2) A decision at the wrong unit: no rule for deciding whether to reuse a cache removes that cost. What does help is choosing which parts of the cache to recompute, and the value of choosing well falls as the unit of choice grows: informed selection removes 49.5% of the cache error beyond chance at single rows (one token's keys and values), 10.6% at 64-token chunks, and nothing at the level of whole calls. Budgeted Cache Repair (BCR) acts at the unit where selection still pays. It drafts two tokens from the assembled cache, ranks cache rows by the attention those tokens pay them, and recomputes a fixed budget of rows exactly, in one of three layouts. The cost is paid rather than predicted away, and the draft that fails as a gate succeeds as a selector. BCR restores GSM8K to dense-prefill accuracy while still serving most calls from cache, and its best layout outperforms every reuse baseline's mean in the reference grid. The draft also beats a coin-flip selector at the same budget - a control prior evaluations lack.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Budgeted Cache Repair, Cross-Context KV-Cache Reuse

Reviews

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

The paper investigates accuracy degradation from cross-context KV cache reuse, mainly focusing on KVCOMM. It proposes Budgeted Cache Repair (BCR) to obtain attention queries from a short draft, use them to rank cached positions, and selectively recompute a fixed budget using individual rows, fixed chunks, or grown spans.

Critical strengths

The paper shows that KVCOMM can appear lossless in short evaluations while losing accuracy over longer runs, exposing a blind spot in evaluating online cache reuse.

Critical weaknesses
  • The central insight is not established. Table 8’s row-to-chunk decline is budget-matched, but the call-level endpoint is not (50% and 100% budgets), and is combined with a separate allocation experiment. More importantly, the curve’s prediction fails at the task level as single-row selection (BCR-single, CacheBlend) does not beat 64-token chunks in any cell of Table 14.

  • The paper does not demonstrate the proposed method’s quality/cost advantage. Accuracy uses draft-scored repair and the advertised 2.85× speedup uses random repair and excludes the draft. And, algorithm1 does not make selected rows dense-exact: they still attend to erroneous un-repaired entries, which can contaminate their later layer representations.

Questions for authors
  • Does Table 8 run Algorithm 1, or replace selected entries with entries copied from a dense reference? These measure different interventions.
  • What accuracy and TTFT does the complete draft-scored implementation achieve, including scoring, rollback, and repair?
  • Does the generated-token query improve selection over using only the final prompt-token query? Without this comparison, the contribution of generation remains unidentified.
12 comments
AuthorsOpenReview ↗

Dear Reviewer VwvB

We appreciate the reviewer's detailed comments on the experimental methodology and presentation. We agree with the concerns regarding the oracle-based evaluation, budget matching, and the interpretation of the granularity results.

AuthorsOpenReview ↗

Q1 — Does Table 8 run Algorithm 1?

Q1 — Does Table 8 run Algorithm 1?

The reviewer is correct. Table 8 restores selected entries using their dense reference values rather than executing Algorithm 1. It therefore represents an oracle upper bound, not the actual output of our method.

We have clarified this distinction in the revised caption and added Table R10 to measure the residual error produced by Algorithm 1 directly.

Table R10. The residual at three budgets. GSM8K, five agents, pinned roles, γ=0.3\gamma=0.3, k=2k=2, n=150n=150, 486486–532532 repair calls per condition. Panel (a) varies the budget at 6464-token chunks; panel (b) holds the budget and varies the ranking rule, with the rule in place of ρ and the decision unit in place of k. Panel (b) is tail-masked — its conditions cannot select the last 128128 positions, which is the only way both rules choose from the identical pool, since InfoFlowKV's needs a query block there — so the two panels are different regimes and the bold marks the best value within each panel, not across them. The italic row repeats (a)'s operating point unmasked. The three tail-masked floors agree to 0.00030.0003 in keys and 0.00090.0009 in values, which makes those residuals comparable. Both error columns share one denominator — the repaired rows' own pre-repair deviation — so floor and residual are directly comparable. already exact is the share of selected rows matching dense at every layer to 1010⁻² before the repair.

ρkresidual keys ↓residual values ↓floor keys ↓floor values ↓already exact ↓accuracy ↑vs. Dense
KVComm (no repair)——————75.375.3%6/216/21, p=0.0059p=0.0059
(a) the budget, at 6464-token chunks
0.050.0520.7330.7330.7930.7930.02070.02070.03440.034493.093.0%77.377.3%6/186/18, p=0.023p=0.023
0.200.2020.5270.5270.5770.5770.01030.015363.2%87.3%6/36/3, p=0.508p=0.508
0.400.4020.3790.4350.01190.01190.01650.016564.864.8%86.086.0%5/45/4, p=1.000p=1.000
(b) the ranking rule, at ρ=0.20\rho=0.20, tail-masked
BCR (unmasked, from (a))chunk 64640.5270.5270.5770.5770.01030.01030.01530.015363.263.2%87.387.3%6/36/3, p=0.508p=0.508
BCRchunk 64640.3560.4050.01080.01080.01620.016273.173.1%81.3%6/126/12, p=0.238p=0.238
InfoFlowKVchunk 64640.4710.4710.5080.5080.01070.01070.01530.015350.350.3%80.780.7%7/147/14, p=0.189p=0.189
InfoFlowKVtoken0.4860.4860.5280.5280.01100.01100.01590.015946.7%81.3%6/126/12, p=0.238p=0.238
Dense (ceiling ref.)——————85.385.3%—
AuthorsOpenReview ↗

Q2 — Does the method improve latency?

Q2 — Latency

As discussed in our response to JnoT, we corrected the latency evaluation and now report the complete implementation cost in Table R3. We also distinguish the configurations used for the previously reported speedup figures.

Table R3. Complete-implementation latency. 300300 pinned GSM8K problems, five agents, ρ=0.20\rho=0.20.

accuracy ↑TTFT, cached call ↓vs. KVComm ↓dense-prefill control
KVComm (baseline)71.071.0%109.4 ms—139.0139.0 ms
BCR, k=2k=284.3%221.9221.9 ms+112.5+112.5 ms138.9138.9 ms
BCR, k=1k=183.083.0%192.2192.2 ms+82.8 ms140.6140.6 ms
Reviewer_2uLXOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates accuracy loss from cross-context KV-cache reuse and proposes Budgeted Cache Repair (BCR). Starting from KVComm’s approximated cache, BCR uses attention from a short draft to select positions for recomputation. It studies three repair layouts and several allocation policies, finding substantial recovery on GSM8K but more limited benefits elsewhere.

Critical strengths
  1. The strongest result is the 300-problem GSM8K experiment with fixed agent roles: accuracy improves from 71.0% to 84.3%, close to dense prefill’s 84.7%. The five-seed random control provides useful evidence that informed selection helps beyond repair alone.
  2. The evaluation audit is valuable. The authors uncover tokenization, retrieval, and implementation issues, and correct misleading statistical analyses. These findings should help others evaluate cache reuse more carefully.
Critical weaknesses
  1. The paper has not yet demonstrated the complete method’s accuracy–latency trade-off. As Appendix C acknowledges, the strongest accuracy results use draft-selected repair, while the reported 2.85× time-to-first-token speedup uses a different implementation with random selection and no draft. Measurements of the same complete configuration are needed.
  2. The contribution of the generated-token query remains unclear. The selector also uses the final prompt token, so the random control cannot establish whether the extra query earns its cost. A prompt-only ablation is needed. The different reuse-gate settings in the GSM8K CacheBlend comparison also limit conclusions about relative performance.
Questions for authors
  1. Can you report accuracy and latency for the same complete draft-selected implementation, including all selection and repair overhead, with matched baseline settings?
  2. At the same repair budget and layout, how does the current selector compare with attention from the final prompt token alone?
  3. Algorithm 1 lets repaired positions attend to unrepaired, approximate keys and values. Their later-layer representations therefore need not match dense prefill. Does “exact” mean recomputation conditional on this mixed cache, and how much error remains in the repaired rows at the 20% budget?
7 comments
AuthorsOpenReview ↗

Dear Reviewer 2uLX

We sincerely thank the reviewer for carefully examining Algorithm 1 and identifying the ambiguity in the term "exact." We have clarified its usage at all relevant first occurrences and removed the statement that "we restore the true values." Our remaining disagreement concerns the interpretation of the residual error: the row-matched floor accounts for only 2.0–4.3% of the residual, suggesting that the algorithmic procedure is exact and that the remaining error primarily arises from mixed neighbourhoods.

AuthorsOpenReview ↗

Q1 — Does the method improve latency in practice?

Q1 — Latency

We agree that the original latency comparison was incomplete. The complete measurements are now reported in Table R3. At k=2, BCR adds 112.5 ms per cached call over KVComm and is slower than dense prefill on GSM8K.

The corrected kernel-matched speedup is 1.66×–1.82×. We have revised the corresponding claims and added MuSiQue results to demonstrate when the repair becomes beneficial.

Table R3. Complete-implementation latency. 300300 pinned GSM8K problems, five agents, ρ=0.20\rho=0.20.

accuracy ↑TTFT, cached call ↓vs. KVComm ↓dense-prefill control
KVComm (baseline)71.071.0%109.4 ms—139.0139.0 ms
BCR, k=2k=284.3%221.9221.9 ms+112.5+112.5 ms138.9138.9 ms
BCR, k=1k=183.083.0%192.2192.2 ms+82.8 ms140.6140.6 ms
AuthorsOpenReview ↗

Q2 — Does the generated-token query help?

Q2 — Does the generated-token query help?

We conducted a controlled draft-length ablation (Table R9). The k=1 baseline, which uses only the prompt-final query, achieves 83.0%, compared with 84.3% for k=2. However, the difference is not statistically significant (p=0.454).

Longer drafts also increase computational cost without providing a measurable accuracy improvement. We therefore retain k=2 as the submitted operating point and explicitly report the lower cost of k=1.

Table R9. Draft-length ablation, with both ends of the range the draft has to beat. GSM8K, five agents, ρ=0.20\rho=0.20, n=300n=300, same problems throughout. In each split b is what the row solves and the comparison condition misses. closed is the share of the 4141-problem reuse gap recovered. Repaired rows per call are 259.0259.0, 257.9257.9, 259.2259.2 and 260.3260.3, so the budget is matched across k.

kaccuracy ↑b/cb/c vs. KVCommb/cb/c vs. k=2k=2closed ↑TTFT ↓dense control
KVComm (no repair)71.071.0%———109.4 ms139.0139.0 ms
1 (prompt token only)83.083.0%50/1450/14, 7.1×1010⁻⁶6/106/10, 0.4540.4548888%192.2192.2 ms140.6140.6 ms
284.3%49/949/9, 9.0×1010⁻⁸—98%221.9221.9 ms138.9138.9 ms
483.783.7%49/1149/11, 7.6×1010⁻⁷5/75/7, 0.7740.7749393%282.8282.8 ms138.5138.5 ms
884.084.0%49/1049/10, 2.72.7×1010⁻⁷5/65/6, 1.0001.0009595%411.5411.5 ms138.7138.7 ms
Dense (ceiling ref.)84.784.7%——100100%——
Reviewer_JnoTOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper presents Budgeted Cache Repair (BCR) for a multi-agent system, where instead of deciding whether to recompute the whole KV representation or not, it identifies the most important tokens required for new generation and recomputes their KV representations only, while using the KV cache for others. Specifically, BCR drafts two tokens for the query attention from the reused KV cache using KVCOMM [1], then ranks KV cached rows, by aggregating attention received across layers, heads, and draft positions, for recomputation at a fixed budget with three repair approaches. BCR ranks based on which positions matter to the answer rather than which KV rows have the largest prediction error.

Critical strengths
  1. BCR shows that identifying which tokens to recompute is more useful than selecting which complete requests to recompute. Its proposed attention-based selection reduces cache error beyond random selection by 49.5% for individual rows.
  2. BCR presents strong accuracy recovery on GSM8K. At the same repair budget, it achieves accuracy near the dense prefill.
  3. BCR does not require any fine-tuning, making it quite straightforward to integrate into existing cache-reuse frameworks
Critical weaknesses
  1. Limited Novelty: The paper seems like an incremental approach. Its core method appears to be the analysis of decision granularity and its application to KVCOMM [1], rather than a fundamentally new caching mechanism. Also, there are some already existing studies that investigate query-driven or attention-informed KV recomputation: ProphetKV [2] and InfoFlowKV [3].
  2. The improvements do not generalize consistently: The performance claim rests heavily on one task and backbone. It is noted that the strongest result is on GSM8K, but on other benchmarks, performance is quite weak. On MMLU, the improvement is not statistically significant, while HumanEval shows little initial cache-reuse degradation.
  3. Incomplete latency: The paper reports a 2.85× TTFT speedup for BCR at a 20% repair budget. The timing experiments use randomly selected repair chunks without the two-token drafting step, but the accuracy experiments use draft-guided selection, which introduces additional computation.

[1] Ye et al., KVCOMM: Online Cross-context KV-cache Communication for Efficient LLM-based Multi-agent Systems. NeurIPS, 2025. [2] Wang et al., ProphetKV: User-Query-Driven Selective Recomputation for Efficient KV Cache Reuse in Retrieval-Augmented Generation. ICML, 2026. [3] Teng et al., InfoFlow KV: Information-Flow-Aware KV Recomputation for Long Context. ICML, 2026.

Questions for authors
  1. How substantially does a two-token draft improve upon existing query-guided recomputation? Direct experimental comparisons against ProphetKV [2] and InfoFlowKV [3] would be helpful.
  2. What is the end-to-end latency when the computation time of draft-guided selection is also included?
6 comments
AuthorsOpenReview ↗

Dear Reviewer JnoT

We thank the reviewer for identifying the mismatch between the accuracy and latency evaluations. We agree that both must be evaluated under the same workload.

AuthorsOpenReview ↗

Q1a — Does the generated-token query help?

Q1a — Does the generated-token query help?

We evaluated different draft lengths on the same 300 GSM8K problems (Table R9). The results show no statistically significant difference among draft lengths (all pairwise p≥0.454p \geq 0.454). The submitted k=2k=2 configuration achieves 84.3% accuracy, recovering 98% of the accuracy gap over KVComm and approaching the dense-reference ceiling of 84.7%.

This near-ceiling performance leaves little room for longer drafts to provide further gains. Consistent with this, increasing the draft length yields no detectable accuracy improvement while substantially increasing TTFT. We therefore retain k=2k=2 as a practical trade-off, without claiming that longer drafts improve performance.

Table R9. Draft-length ablation, with both ends of the range the draft has to beat. GSM8K, five agents, ρ=0.20\rho=0.20, n=300n=300, same problems throughout. In each split b is what the row solves and the comparison condition misses. closed is the share of the 4141-problem reuse gap recovered. Repaired rows per call are 259.0259.0, 257.9257.9, 259.2259.2 and 260.3260.3, so the budget is matched across k.

kaccuracy ↑b/cb/c vs. KVCommb/cb/c vs. k=2k=2closed ↑TTFT ↓dense control
KVComm (no repair)71.071.0%———109.4 ms139.0139.0 ms
1 (prompt token only)83.083.0%50/1450/14, 7.1×1010⁻⁶6/106/10, 0.4540.4548888%192.2192.2 ms140.6140.6 ms
284.3%49/949/9, 9.0×1010⁻⁸—98%221.9221.9 ms138.9138.9 ms
483.783.7%49/1149/11, 7.6×1010⁻⁷5/75/7, 0.7740.7749393%282.8282.8 ms138.5138.5 ms
884.084.0%49/1049/10, 2.72.7×1010⁻⁷5/65/6, 1.0001.0009595%411.5411.5 ms138.7138.7 ms
Dense (ceiling ref.)84.784.7%——100100%--
AuthorsOpenReview ↗

Q1b — Comparison with ProphetKV / InfoFlowKV

Q1b — Comparison with ProphetKV / InfoFlowKV

We appreciate the suggestion to include these comparisons. ProphetKV could not be evaluated because its authors have not publicly released the code. For InfoFlowKV, we evaluated its ranking rule under matched budgets and candidate pools, rather than reproducing the full system (Table R4). Its pooling strategy reduces cache error by (2.0)–(2.25$\times$) more (Table R10), while achieving comparable task-level performance. Our generated query provides an additional 10 correct problems (14/4, (p=0.031)). At a chunk size of 64, our method is the only one among the four evaluated conditions to outperform KVComm (12/3, (p=0.035)).

Table R4. Two selection rules × two decision units, everything else fixed (GSM8K, five agents, pinned roles, γ=0.3\gamma=0.3, ρ=0.20\rho=0.20, k=2k=2, n=150n=150, same problems and recompute kernel; effective ρ 0.20000.2000–0.20070.2007, 286286–295295 rows/call). removed is each condition's own before-minus-after on the same calls — a pooled ratio is unusable across conditions, since the random control scores a better ratio than the draft (0.93480.9348 against 0.94390.9439) while losing the task by 1414 problems.

ranking rule, at k=2k=2unitKVCommafter ↓removed ↑accuracy ↑b/cb/c vs. KVComm
BCR6464-token chunk0.11360.11360.10490.10490.00620.006281.3%12/312/3, p=0.035p=0.035
BCRtoken0.11790.11790.10860.10860.00850.008580.080.0%10/310/3, p=0.092p=0.092
InfoFlowKV6464-token chunk0.11500.11500.08920.08920.01390.013980.780.7%12/412/4, p=0.077p=0.077
InfoFlowKVtoken0.10720.10720.08470.017081.3%15/615/6, p=0.078p=0.078

Table R10. The residual at three budgets. GSM8K, five agents, pinned roles, γ=0.3\gamma=0.3, k=2k=2, n=150n=150, 486486–532532 repair calls per condition. Panel (a) varies the budget at 6464-token chunks; panel (b) holds the budget and varies the ranking rule, with the rule in place of ρ and the decision unit in place of k. Panel (b) is tail-masked — its conditions cannot select the last 128128 positions, which is the only way both rules choose from the identical pool, since InfoFlowKV's needs a query block there — so the two panels are different regimes and the bold marks the best value within each panel, not across them. The italic row repeats (a)'s operating point unmasked. The three tail-masked floors agree to 0.00030.0003 in keys and 0.00090.0009 in values, which makes those residuals comparable. Both error columns share one denominator — the repaired rows' own pre-repair deviation — so floor and residual are directly comparable. already exact is the share of selected rows matching dense at every layer to 1010⁻² before the repair.

ρkresidual keys ↓residual values ↓floor keys ↓floor values ↓already exact ↓accuracy ↑vs. Dense
KVComm (no repair)——————75.375.3%6/216/21, p=0.0059p=0.0059
(a) the budget, at 6464-token chunks
0.050.0520.7330.7330.7930.7930.02070.02070.03440.034493.093.0%77.377.3%6/186/18, p=0.023p=0.023
0.200.2020.5270.5270.5770.5770.01030.015363.2%87.3%6/36/3, p=0.508p=0.508
0.400.4020.3790.4350.01190.01190.01650.016564.864.8%86.086.0%5/45/4, p=1.000p=1.000
(b) the ranking rule, at ρ=0.20\rho=0.20, tail-masked
BCR (unmasked, from (a))chunk 64640.5270.5270.5770.5770.01030.01030.01530.015363.263.2%87.387.3%6/36/3, p=0.508p=0.508
BCRchunk 64640.3560.4050.01080.01080.01620.016273.173.1%81.3%6/126/12, p=0.238p=0.238
InfoFlowKVchunk 64640.4710.4710.5080.5080.01070.01070.01530.015350.350.3%80.780.7%7/147/14, p=0.189p=0.189
InfoFlowKVtoken0.4860.4860.5280.5280.01100.01100.01590.015946.7%81.3%6/126/12, p=0.238p=0.238
Dense (ceiling ref.)——————85.385.3%—

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to Reviewers

We sincerely thank all three reviewers for their careful and constructive feedback. Their comments helped us identify several points in our evaluation and presentation. We have corrected the reported latency figures, clarified the scope of our exactness claim, and conducted additional experiments to strengthen the evaluation.

Our main revisions are:

  • Latency: Corrected the kernel-matched speedup from the previously reported 2.35× to 1.66×–1.82× and reported the complete implementation cost.

  • Accuracy and efficiency: Added MuSiQue experiments demonstrating a setting where cache repair improves accuracy over reuse while reducing TTFT relative to dense prefill.

  • Generalization: Added HumanEval experiments using a second backbone.

  • Method analysis: Added controlled comparisons with InfoFlowKV's ranking rule, residual-error measurements, and draft-length ablations.

We address each reviewer separately below, referring to shared experiments where appropriate.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.