Budgeted KV-Cache Repair for Evolving Contexts

Motivation

• Deleting a passage may leave its influence in later KV states, while recomputing the entire retained suffix can make repair costly after a small edit.The prefix before deletion remains valid, but suffix states were computed while deleted content was visible.Source: §1 · p. 1

Contribution

• Budgeted KV-cache repair asks where to spend a user-chosen fraction of suffix recomputation to recover the next answer, rather than rebuild every state.The goal is answer quality within the allowance, not reconstruction of a clean cache.Source: §1 · p. 1
• Semantic-Unit Refresh (SUR) selects query-relevant text regions using frozen embedding scores and text boundaries, without training or an auxiliary transformer forward.This policy can cover separated evidence regions.Source: §1 · p. 2

Results

• With identical relevance scores and token budgets, coherent-region refresh improves exact match by over 80 percentage points over isolated-token selection on Qwen3-8B and Llama-3.3-70B at 2%.These controls identify support organization as a design choice distinct from relevance scoring.Source: §1 · p. 2
• Across five models, SUR reaches 89.6–100% exact match with 2% suffix recomputation in controlled deletion tasks; on four natural multi-hop QA datasets, 5% yields near-full-recompute exact match with lower post-edit latency.The executor accelerates fragmented refresh by up to 16.1× over interval-wise execution.Source: §1 · p. 2

Implementation

• A layer-packed executor processes selected regions together while preserving full causal cache access, reducing fragmented-refresh overhead by up to 16.1× over interval-wise execution.The reported acceleration is for the executor comparison; the contribution passage describes preserving full causal cache access.Source: §1 · p. 2

Context management and cache editing

• Context-management and cache-retention methods decide what information to preserve, whereas deletion repair updates computation after information changes while leaving unselected states available to attention.A surviving state can still encode a removed passage.Source: §2 · p. 3
• Cache-editing methods address effects beyond deleted cache entries through positional correction, learned replacement states, or selective recomputation, while this work studies budgeted repair after physical span removal without a learned editor.Related approaches include PIE, Leyline, KVEraser, and Models Take Notes (He et al., 2025; Ma et al., 2026; Li et al., 2026b; Li, 2026).Source: §2 · p. 3

Selective recomputation and budget allocation

• Modular cache-reuse systems selectively reconstruct cross-chunk interactions, while this paper compares adapted selection signals under a shared deletion-repair operator and equal suffix budgets.The comparison separates allocation decisions from the original systems’ serving implementations.Source: §2 · p. 3

Query-aware reconstruction

• Query-aware methods direct computation toward the next answer, and matched-score experiments here show coherent regions can recover answers isolated high-scoring tokens miss at the same budget.SUR uses frozen embeddings for relevance and text boundaries to organize coherent refresh regions.Source: §2 · p. 3

3 Budgeted cache repair

• After a context deletion, budgeted repair corrects suffix positions and refreshes selected states while reusing the rest of the cache; packed execution batches selected regions to avoid repeated model traversals.The prefix cache remains valid, but suffix states were computed while the removed span was available to attention.Source: §3 · p. 3, §3.1 · p. 3

3.1 The budgeted repair problem

• A user budget sets how many retained suffix positions are refreshed to recover answer quality, while unselected states remain available under causal attention.Sparse repair is approximate because selected tokens can still read earlier unrefreshed states computed with the deleted span present.Source: §3.1 · p. 4

3.2 Semantic-Unit Refresh

• SUR refreshes coherent regions because relevance scores alone do not determine which surrounding tokens should be recomputed with promising locations.A few relevant tokens can select a unit that brings lower-scoring neighbors into the same computation.Source: §3.2 · pp. 4–5
• SUR uses frozen input embeddings to score suffix-token relevance to query tokens without an auxiliary transformer forward or trained selector.It groups tokens at text boundaries, ranks units by their highest token scores, and admits whole units until the allowance is filled, using a contiguous window when the next unit does not fit.Source: §3.2 · pp. 4–5

3.3 Packed execution

• Layer-packed execution processes all selected positions through each layer together, while each selected token still attends to the full causal history, including reused gaps.For B selected positions from an S-token suffix across L layers, selection reduces token-layer updates from LS to LB; packing executes the selection in one traversal rather than R.Source: §3.3 · p. 5

4.1 Experimental setup and baselines

• Each allocator refreshes the same number of suffix positions per case, with Shift and Replay anchoring the zero- and full-suffix-budget endpoints.The evaluation covers five models and uses a shared sequential interval executor for task quality and post-edit answer latency.Source: §4.1 · pp. 5–6

4.2 Controlled answer recovery on Erasing-NIAH

• At 2% recomputation, SUR reaches 89.6–100% EM across five systems in controlled deletion tasks.Increasing the budget brings several models to dense-reference performance, although Qwen3-30B remains below Re-prefill across the sweep.Source: Figure 3 · p. 6, §4.2 · p. 7

4.1 Experimental setup and baselines

• Four allocation controls separate relevance scoring from grouping, while eight prior-work-derived policies transfer their signals into the shared repair operator.The comparison concerns allocation choices rather than the original systems’ serving throughput.Source: §4.1 · p. 6

4.3 Quality and latency on natural multi-hop QA

• At 5%, SUR is within 0.1 percentage points of Re-prefill’s observed EM on both models and is 1.16–1.43× faster.Source-paired improvements over Shift have positive confidence intervals, while differences from Re-prefill span zero.Source: Figure 4 · p. 7, §4.3 · p. 8
• Natural-QA evaluation uses four datasets and 1,200 cases from 400 source questions, with selection and decoding included in mean post-edit latency.Each source question has three placements of a non-supporting passage; paired quality comparisons keep those placements together.Source: §4.3 · pp. 7–8
• At the larger budget, SUR has higher EM and substantially lower latency than attention/deviation-derived baselines on both natural-QA models.Same-unit BM25 has similarly low selection overhead, while costlier selection signals do not necessarily improve the quality–latency tradeoff.Source: §4.3 · p. 8

4.4 Execution efficiency of packed refresh

• Layer packing yields up to 16.1× faster refresh than interval-wise execution as a fixed budget becomes more fragmented.For a single interval, direct-cache sequential execution is slightly faster than packing.Source: §4.4 · p. 8

5 Discussion

• With identical token scores and budgets, Qwen3-8B EM at 2% rises from 7.3% for individual tokens to 75.0% for the best contiguous window and 89.6% for SUR.The window maximizes summed relevance for its width, but distributing computation across relevant regions improves recovery further.Source: §5 · p. 9
• On Qwen3-8B, SUR reaches near-perfect EM at 5%, while same-score token selection approaches that level at 80% in the measured sweep.The budget specifies available computation, not a guaranteed accuracy level; highlighted budgets are operating choices, not interface limits.Source: §5 · p. 9
• Direct execution suits a single interval, while layer packing avoids repeated model traversals for fragmented selections.The execution strategy depends on selection geometry as well as token count.Source: §5 · p. 9

6 Conclusion

• Controlled experiments show relevant-region allocation can recover answers missed by isolated-token refresh, and layer-wise packing accelerates fragmented refresh by up to 16.1× over interval-wise execution.SUR shows strong controlled recovery at 2–5% budgets and a favorable quality–latency tradeoff on natural multi-hop QA.Source: §6 · p. 9

Limitations

• Execution measurements use one Qwen3-8B checkpoint on one H100 and do not establish deployment-wide speedup.The implemented packed scope is dense Llama/Qwen3 with full attention, fixed default rotary positions, batch size one, and one device; MoE, offloading, sliding windows, and distributed serving are not covered.Source: Limitations · p. 10
• Prior-work-derived allocators share the repair operator and budget, so their results do not reproduce native optimized implementations or support native-system rankings.Source: Limitations · p. 10

Ethical Considerations

• Cache repair does not erase information from model weights or guarantee privacy; unrefreshed states may retain deleted information, so confidential-data removal requires a separately validated security mechanism.The experiments use existing research benchmarks, with source citations and evaluation transformations documented in Appendix A.Source: Ethical Considerations · p. 10

A Repair operators, allocation rules, and evaluation

• The interface fixes repair semantics and selected-token count across allocators, while each allocation rule chooses which retained positions receive computation.Source: A Repair operators, allocation rules,… · p. 12, §A.4 · p. 14

A.1 Operator semantics and exact budgets

• Sparse refresh recomputes selected suffix positions through all layers but leaves unselected states available to attention, so refreshed positions may still read stale history.Selected intervals run sequentially against the evolving cache; any bridging positions count against the same allowance.Source: §A.1 · p. 12

A.2 Task-aware allocation and repair locality

• The task-aware ideal selects exactly B positions to maximize answer quality, but this is an in-hindsight reference rather than an inference-time optimization performed by SUR.Repair locality measures the smallest suffix fraction that reaches a target quality; experiments instead evaluate selected supports at fixed budgets.Source: §A.2 · p. 13

A.3 Semantic-Unit Refresh

• SUR ranks text units using query-token embedding similarity, then spends the suffix allowance on high-scoring units or a width-limited window in the next unit.Its deterministic window heuristic favors local forward context but is not a dependency oracle.Source: §A.3 · pp. 13–14

A.4 Matched controls and prior-work-derived allocators

• Matched controls separate support organization from relevance scoring, while a clean-state oracle tests localization using privileged recomputation rather than serving as an optimal-support or task-accuracy upper bound.The oracle requires a fully recomputed edited cache to obtain its signal; Table 1 lists the prior-work-derived allocation signals under the common refresh operator.Source: §A.4 · p. 14, Table 1 · p. 15

A.5 Datasets and answer scoring

• The controlled NIAH benchmark uses 96 same-key deletion cases per model, while natural QA uses 1,200 paired placement cases across HotpotQA, 2WikiMultiHopQA, MuSiQue, and IIRC.Natural-QA scores are answer-only exact match with dataset-specific normalization; supporting-fact and joint scores are not evaluated.Source: §A.5 · p. 15

B.1 Five-model NIAH allocation sweep

• 98.96% success on Qwen3-8B at 5% recomputation, 100% on Llama-3.3-70B at 10%, and 100% on GLM-4.5-Air at 2%; SUR is not uniformly best across models and budgets.BM25 reaches 98.96% versus SUR’s 97.92% on Qwen3-235B-A22B at 2%; InfoFlow-Motivated reaches 100% versus SUR’s 98.96% on Llama-3.3-70B at 5%.Source: Table 2 · p. 16, §B.1 · p. 16, Table 4 · p. 17

B.2 Natural-QA quality and latency

• Natural-QA tables pair exact-match accuracy with post-edit latency at each budget; latency includes selection, position correction, repair or replay, and query-plus-answer decoding.The reported mean covers 1,200 cases with one timed trial per case and no warmup; initial dirty-context prefill and harness cache cloning are excluded.Source: §B.2 · pp. 16, 19, Table 7 · p. 19

B.3 Paired uncertainty and error transitions

• The paired analysis uses source-question bootstrap intervals, retaining all three placements and all methods for each sampled question.The 95% intervals are pointwise and have no multiple-comparison adjustment.Source: §B.3 · p. 19
• At 5%, SUR improves over Shift by 1.75 points on Qwen3-30B and 2.25 points on Llama-3.3-70B; its differences from Re-prefill are +0.08 and −0.08 points, respectively.The intervals for the Re-prefill differences span zero.Source: §B.3 · p. 19, Table 9 · p. 20
• At 5%, SUR corrects Shift errors on 2.50% of Qwen3-30B cases and 3.50% of Llama-3.3-70B cases, while introducing errors on 0.75% and 1.25%, respectively.Source: §B.3 · p. 19

C.1 Allocation geometry at a fixed relevance score

• At 2%, the token–window–SUR sequence reaches 7.3%, 75.0%, and 89.6% EM on Qwen3-8B, and 7.3%, 65.6%, and 90.6% on Llama-3.3-70B.SUR exceeds the score-optimized single-window control at 2% on all five systems.Source: §C.1 · p. 21, Table 12 · p. 21
• At 2%, random semantic units reach only 2.1% EM on Qwen3-8B and Llama-3.3-70B, showing that grouping without query ranking is insufficient.Source: Table 12 · p. 21, §C.1 · p. 22

C.2 Inexpensive relevance versus attention and state signals

• At 2%, BM25 reaches 82.29% EM on Qwen3-8B; SUR exceeds BM25 on four models, while Qwen3-235B-A22B favors BM25, 98.96% versus 97.92%.This comparison retains SUR’s units and allocator but changes the relevance rule.Source: Table 12 · p. 21, §C.2 · p. 22
• At 2%, SUR exceeds four attention- and state-derived policies on four systems, but InfoFlow-Motivated leads SUR on Llama-3.3-70B, 92.71% versus 90.63%.At 5% on that model, InfoFlow-Motivated reaches 100%, compared with SUR’s 98.96%; the comparison changes both scoring and support construction.Source: §C.2 · p. 22, Table 13 · p. 22

C.3 Matched-token evaluation and design variants

• On a frozen 599-case Qwen3-8B holdout, matched-token region selection improves EM by 9.85 points at smaller support and 1.84 points at larger support.The benefit is concentrated at 1K–2K contexts; both selectors approach saturation from 4K onward, with one SUR regression at 32K.Source: §C.3 · p. 22, Table 14 · p. 23

D.1 Construction and controls

• The evidence-location comparison holds edit geometry and other listed factors fixed within each tail condition, but exchanges also change support order and recency.The side contrast fixes suffix length; the tail contrast jointly changes filler, stale-state volume, and evidence-to-query distance.Source: §D.1 · p. 23, D Matched evidence-location experiment · p. 23

D.2 Estimands and uncertainty

• The matched evidence-side likelihood contrast varies across datasets: −0.155, −0.045, 0.022, and 0.021 nats on 2WikiMultiHopQA, HotpotQA, IIRC, and MuSiQue.The positive task-EM effect does not imply general improvement in answer likelihood.Source: §D.2 · p. 24, Table 15 · p. 24

D.3 Localized refresh and continuation fidelity

• The fixed-slot refresh comparison finds similar point estimates to full suffix replay for measured side effects, but does not establish repair equivalence or a minimum sufficient support.Its NLL side contrast is −0.031 nats ([−0.093, 0.032]).Source: §D.3 · pp. 24–25

E Numerical execution-path controls

• The execution-path controls are not a deterministic-kernel or FP32 reference, and measured Replay accuracy is an operational comparator rather than a mathematical upper bound on sparse accuracy.Exact-logit disagreement can reach 100% while argmax and sequence disagreement remain much smaller.Source: E Numerical execution-path controls · p. 25

F Reproducibility

• The reproducibility checks verify method coverage, exact token allowances, per-dataset denominators, and integer-count pooling before rounding.Natural-QA conditions contain four 300-case datasets, with paired differences checked against repaired and regressed counts.Source: F Reproducibility · p. 26

G.1 Scaling of budgeted recomputation

• For a 10K suffix, 2% and 5% budgets refresh 200 and 500 positions, using at most 4% and 10% of Replay’s causal query–key pairs, respectively.Token-local projection and MLP arithmetic uses 2% and 5%; these are architectural counts, not execution-time guarantees.Source: §G.1 · pp. 26–27

G.2 Mixed-cache recurrence and implementation

• Layer packing processes selected positions together while each selected query reads fresh selected K/V and reused causal K/V from the shifted cache.The schedule preserves the interval-major recurrence in real arithmetic, but different matrix shapes and reduction order can change BF16 outputs; the adapter’s supported models and settings are limited.Source: §G.2 · pp. 27–28

G.3 Repeated execution measurements

• 56.738 ms serial preparation falls to 53.790 ms with overlap on one synthetic input, with support, diagnostics, shifted/output cache, and query logits agreeing bitwise.The timing includes scoring, unit construction, selection, plan/upload, Shift, and refresh, but excludes prefill and subsequent decoding.Source: §G.3 · p. 29

G.4 Timing examples on actual QA supports

• At 5% on four fixed QA inputs, packing is 1.53× faster for refresh and 1.33× faster for recovery than interval-wise execution.These probes measure synchronized cache recovery, not answer generation or scoring.Source: §G.4 · p. 29, Table 20 · p. 30

G.5 Numerical validation

• At 2K with 16 intervals, custom attention exceeds the preset layer-error budget: zero-based layer 18 V maximum error is 0.21346 versus 0.09965 for packed SDPA.Custom attention remains experimental, packed SDPA is the default, and task-quality results were not rerun on either packed backend.Source: §G.5 · p. 30

• A refreshed position can still attend to stale causal predecessors because sparse repair retains shifted K/V states at unselected positions.Source: H Mixed-Cache Error under Sparse Refresh · p. 30
• Refreshing influential predecessors can reduce the residual term when their recomputation reduces their deviation from full-suffix Replay.Source: H Mixed-Cache Error under Sparse Refresh · p. 31
• The bound does not establish semantic boundaries as optimal or show that large attention mass necessarily produces large output error.SUR uses semantic units as a lightweight structural heuristic rather than computing a causal dependency closure.Source: H Mixed-Cache Error under Sparse Refresh · p. 31