Budgeted KV-Cache Repair：SUR 以 2-5% 预算修复演化上下文

Authors:Han Yu, Wenhui Zhu, Jincheng Cao, Rui Cai, Yuanda Xu, Zhengze Zhou, Xiwen Chen, Hao Wang, Xuanzhao Dong, Han Shi, Menglin Zhou, Shayan Mohajer Hamidi, Lin Su, Mina Razghandi, Sayan Ghosh, Qing Lan, Rohit Jain, Alborz Geramifard

View PDF HTML (experimental)

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.

Submission history

From: Han Yu [view email]
[v1] Mon, 12 Oct 2026 19:44:57 UTC (623 KB)