Budgeted KV-Cache Repair for Evolving Contexts

arXiv:2610.17338v1 Announce Type: new 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.

Related

• Rethinking KV Cache Eviction via a Unified Information-Theoretic Objective
• EvolveScaler: Synthesizing Information-Evolution Contexts via Executable State Machines and Natural-Language Rendering
• VisCache: Visual KV Cache Pruning for Efficient Vision Large Language Model Inference
• MemFly: On-the-Fly Memory Optimization via Information Bottleneck
• Prior Audit-Repair Context Shifts LLM Verifier Thresholds Toward Leniency

Source: arXiv cs.AI | 2026-10-15