Budgeted KV-Cache Repair for Evolving Contexts

Han Yu; Wenhui Zhu; Jincheng Cao; Rui Cai; Yuanda Xu; Zhengze Zhou; Xiwen Chen; Hao Wang

cs.AIOct 12, 2026

Budgeted KV-Cache Repair for Evolving Contexts

Authors: Han Yu, Wenhui Zhu, Jincheng Cao, Rui Cai, Yuanda Xu, Zhengze Zhou, Xiwen Chen, Hao Wang,

Organizations: LinkedIn · Clemson University · Arizona State University · Rice University

Abstract

Language-model agents revise their working context as information becomes obsolete, but deleting text does not erase its influence on cached computation. Later key-value (KV) states remain conditioned on the deleted content, while recomputing the entire retained suffix can be costly. We introduce budgeted KV-cache repair: recovering task performance by recomputing a user-chosen fraction of the retained suffix. Comparing repair allocations under identical relevance scores and token budgets, we find that refreshing coherent regions can substantially outperform refreshing isolated tokens. This finding motivates Semantic-Unit Refresh (SUR), which allocates the budget to query-relevant text regions using inexpensive embedding scores, without training or an auxiliary transformer forward. To execute these repairs efficiently, a layer-packed executor processes selected states together at each layer while preserving full causal cache access. Across five models, SUR achieves strong recovery in controlled deletion tasks while recomputing only 2-5% of the suffix. On four natural multi-hop QA datasets, it achieves near-full-recompute exact match at a 5% budget with lower post-edit latency. The executor accelerates fragmented refresh by up to 16.1x over interval-wise execution.

Figures & tables

Figure 1: Budgeted repair at an agent’s context-edit boundary. After deletion and position correction, scores retained tokens against the next query using frozen embeddings, ranks text-boundary units by aggregated relevance, and selects regions under a user budget. Lower-scoring neighbors can be refreshed with their selected unit. Packed refresh updates selected states while retaining full causal cache access. Relevance bars and the four-row allowance are schematic.

Figure 2: Same selected tokens, a different execution order. (a) Interval-wise refresh completes every layer for positions

\{3,4\}

before traversing the model again for

\{8,9\}

. (b) Packed refresh processes all four positions together at each layer, sharing one model traversal. (c) After selected K/V are updated, attention still reads all causally available entries, including reused gaps. Filled cells indicate visible K/V, not attention weights; crosses mark future positions.

Figure 3: Budgeted repair across five model systems. Every panel uses the same 96 cases and baseline set, including already-correct cases. Lines connect measured suffix budgets; Shift and Replay are reference operators. Prior-derived selectors share the same repair operator (full results in Appendix 8 ). The bottom row uses a magnified vertical range; Qwen3-30B’s Shift score is annotated off-scale.

Figure 4: Answer quality versus repair-and-generation latency. Exact match across four datasets (1,200 cases from 400 questions) versus mean post-edit latency, including selection and decoding. Small and large markers denote 2% and 5% recomputation. All methods use the same sequential executor. Paired quality comparisons appear in Table 9 .

1	$B\leftarrow\min\{\|s\|,\lceil\|s\|b/100\rceil\}$ .
2	If $B=\|s\|$ : return full suffix Replay from the valid prefix.
3	$\mathcal{C}\leftarrow\operatorname{Shift}(\mathcal{C},e)$ ; if $B=0$ : return $\mathcal{C}$ .
4	Compute token scores $r_{i}$ using Equation 1 .
5	Partition suffix into units; rank by their top-four-mean scores.
6	$A\leftarrow\varnothing$ ; visit units $u$ in ranked order until $\|A\|=B$ :
7	$w\leftarrow B-\|A\|$ ; if $\|u\|\leq w$ , add all positions of $u$ to $A$ .

Algorithm 1 Semantic-Unit Refresh under a suffix budget

Allocator	Implementation in this comparison
ProphetKV-Adapted ( Wang et al., 2026 )	Query-only forward against the Shift cache; suffix score is attention averaged uniformly over query tokens, heads, and layers.
InfoFlow-Motivated ( Teng et al., 2026 )	$L_{2}$ norm of the same query-to-suffix attention tensor over query tokens, heads, and all layers. This differs from the original attention-mass formula, selected-layer scope, and chunk-reordering procedure.
Cache-Craft-Adapted ( Agarwal et al., 2025 )	Replay the dirty suffix in 64-token chunks with deleted keys still visible. Score each retained token by its attention mass on deleted keys, averaged over heads and layers.
CacheBlend-Adapted ( Yao et al., 2025 )	Fresh two-layer edited prefill; score layer-1 KV deviation from Shift by $\sqrt{\\|\Delta K_{1,i}\\|_{2}^{2}+\\|\Delta V_{1,i}\\|_{2}^{2}}$ . One selected support is reused across layers.
A 3 -Adapted ( Zhou et al., 2025 )	Fresh two-layer edited prefill followed by a shallow query forward; sum layer-1 query-to-context attention over heads and query positions.
LegoLink-Adapted ( Hu et al., 2025 )	Treat the valid prefix as the first chunk and split the suffix into 512-token chunks. Rank positions by depth from their chunk boundary, then chunk index. Depths beyond the native 32-token limit are extensions required by the common budget grid.

Table 1: Prior-work-derived allocation signals. Layer indices start at zero; layer 1 is the first contextual KV layer. All rows use the common suffix budget and all-layer refresh operator.

Method	Reference	2%	5%	10%	20%	40%	80%
Dirty	0.00	–	–	–	–	–	–
Shift	0.00	–	–	–	–	–	–
Replay	98.96	–	–	–	–	–	–
Re-prefill	98.96	–	–	–	–	–	–
SUR (ours)	–	89.58	98.96	98.96	98.96	98.96	98.96
Dense tokens (same score)	–	7.29	14.58	28.13	58.33	91.67	97.92

Table 2: Qwen3-8B: complete NIAH allocation sweep. Success rate (%,

\uparrow

) on the same

N=96