Long-running LLM agent workflows often revise interior context spans while retaining long suffixes. Although suffix tokens remain unchanged, altered causal histories and rotary positions prevent exact reuse of their offloaded key-value (KV) states. Full suffix recomputation wastes prefill work, while indiscriminate reuse propagates stale states and full-precision restoration adds data movement. We present PatchKV, a profile-guided recovery system for suffix-preserving revisions. PatchKV decomposes adjacent context versions into an exact prefix, an updated span, and an aligned suffix. It predicts an edit-local dirty region using an offline length-conditioned drift model, augments this region with sparse nonlocal blocks selected from stored attention, and block-rounds their union into a fixed repair set. The remaining suffix blocks are restored from CPU memory using frozen per-block precision tags and a fused path for dequantization, RoPE correction, and KV-page placement. Across three models and three long-context question-answering workloads, PatchKV achieves a 2.51-3.85× speedup in mean resume time-to-first-token over full suffix recomputation and a 1.26-2.06× speedup over CacheBlend, while matching or exceeding CacheBlend's F1 score in six of nine settings and remaining within 1.36 points in the others.
Figures & tables
Fig. 1: Recomputation coverage after a dynamic context update.
Fig. 2: Dynamic contexts in long-running agent workloads, where tool execution and context updates create successive prompt versions while KV state may be offloaded.
Fig. 3: KV-state similarity versus suffix distance across three models. Lines are medians and shading is P25–P75 over archived request–layer samples; dashed and dotted guides mark exact-state similarity and 0.90, respectively.
Top-attn. blocks (%)
Exact continuation (%)
Model
Attn. mass
Dist.
Drift only
Near edit
Random
Low attn.
Top attn.
Qwen3-32B
25.8
83.5
81
82
81
82
95
GLM-4-9B
33.0
72.2
86
86
89
85
97
Llama-3.3-70B
14.3
75.8
87
87
89
87
97
TABLE I: Equal-budget exact-state intervention across three models.
Fig. 4: Cumulative block-level precision sensitivity across three models.
Fig. 5: Overview of PatchKV components and recovery workflow.
Fig. 6: Token-to-block partitioning in PatchKV.
Fig. 7: End-to-end TTFT and F1 score across three models and three long-context QA workloads.
Fig. 8: Attention-guided selective recomputation ablation on Qwen3-32B.
Dataset
Metric
0 tokens
64 tokens
Change
HotpotQA-E
F1 score
51.72
53.72
+2.00
TTFT (ms)
618.92
643.01
+24.09
2WikiMQA-E
F1 score
45.10
46.10
+1.00
TTFT (ms)
621.30
656.37
+35.07
TriviaQA-E
F1 score
92.67
94.67
+2.00
TTFT (ms)
587.62
593.06
+5.44
TABLE II: Effect of the selected 64-token dirty window on Qwen3-32B.
Fig. 9: Quantized-transport ablation on Llama-3.3-70B. TTFT is normalized to FP16, and F1 score is shown as the difference from FP16.
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.
Han Yu, Wenhui Zhu, Jincheng Cao +15
LinkedIn · Clemson University · Arizona State University +1
Large Language Models (LLMs) rely heavily on Key-Value (KV) caching to minimize inference latency. However, standard KV caches are context-dependent: reusing a cached document in a new context requires recomputing KV states to account for shifts in attention distribution. Existing solutions such as CacheBlend, EPIC, and SAM-KV mitigate this issue by selectively recomputing a subset of tokens; however, they still incur non-negligible computational overhead (FLOPs) and increased Time-to-First-Token (TTFT) latency. In this paper, we propose KV Packet, a recomputation-free cache reuse framework that treats cached documents as immutable ``packets'' wrapped in light-weight trainable soft-token adapters, which are trained via self-supervised distillation to bridge context discontinuities. Experiments on Llama-3.1 and Qwen2.5 demonstrate that the proposed KV Packet method achieves near-zero FLOPs and lower TTFT than recomputation-based baselines, while retaining F1 scores comparable to those of the full recomputation baseline.
Chuangtao Chen, Grace Li Zhang, Xunzhao Yin +3
Technical University of Munich Munich, Germany · Technical University of Darmstadt Darmstadt, Germany · Zhejiang University Hangzhou, China +1
Cross-request KV caching reduces the prefill cost of Retrieval-Augmented Generation (RAG), but conventional prefix caching severely limits cache reuse across requests. Position-Independent Caching (PIC) removes this constraint by reusing independent chunks, but their KV states miss cross-chunk interactions. Existing methods selectively recompute token states to recover these missing interactions, but primarily allocate the recomputation budget to selecting which states to recompute, while fixing the recomputation context to the full causal prefix. We introduce RelaxKV, which formulates selective cache repair as a joint allocation problem over repair targets and recomputation context. Guided by the user query, RelaxKV identifies layer-specific repair targets and restricts their recomputation to a query-relevant context, reducing attention computation. Across four decoder models, RelaxKV at a 15% anchor ratio improves aggregate LongBench performance over ProphetKV on all models. On Qwen3-14B, RelaxKV provides a stronger quality-TTFT trade-off than ProphetKV across a 5%-30% anchor-ratio sweep, and achieves the best selective results on RULER-MV and LV-Eval at 16K and 32K context lengths. Controlled ablations further demonstrate the importance of recomputation context selection.
Ruoling Qi, Yirui Liu, Xuaner Wu +5
Shanghai Jiao Tong University · Institute of Artificial Intelligence, China Telecom (TeleAI) · State University of New York at Buffalo