acceptodds
Under review as a conference paper at ICLR 2027

HorizonKV: Future-Aware KVCache Reuse via Lightweight Relevance Estimation for Interleaved Agent Contexts

Abstract

In agent scenarios, context interleaving continuously combines historical context with new context, including user questions, tool calls, and more. KVCache reuse reduces prefill computation, while recomputing important positions maintains accuracy. However, existing methods select recomputation positions based on fixed positions or historical relevance, which fail in dynamically evolving agent contexts. We observe that the next token query helps identify historical positions relevant to subsequent generation. This motivates future-aware KVCache reuse for interleaved contexts, which introduces two challenges. First, this query is unavailable when recomputation positions are selected, and obtaining it requires full prefill. Second, even after selecting recomputation positions, their recovery only requires a subset of historical dependencies, introducing redundant computation. To address these challenges, we propose HorizonKV, a two-stage sparse recovery framework guided by future relevance estimated from current dynamic content. First, we propose future relevance guided recomputation selection, which averages shallow-layer queries at dynamic positions to score historical positions and select them for recomputation within the budget. Second, we propose future relevance guided shared-key recovery, which reuses these scores to construct a shared KV set, reducing recovery computation without additional dense query-key scoring. On agent traces, HorizonKV improves the average score by up to 64.9% over CacheBlend under the same 10% recomputation ratio. On HotpotQA agent trace, it achieves a 5.85× TTFT speedup over CacheBlend at comparable accuracy.

Primary area:
generative models
Keywords:
LLM Agents, KVCache Reuse, Efficient Inference

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_PjdCOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes HorizonKV, a two stage sparse recovery framework for KV cache reuse across different agent contexts. In KV-Cache reuse scenario, HorizonKV computes the relevance score of each token using mean of dynamic Qs in early layers and select the tokens to re-prefill, while leaving the other tokens' KV cache unchanged. HorizonKV also adopts K-sparse attention with the same relevance scores. HorizonKV presents additional ideas built upon CacheBlend (Yao et al., 2024).

Critical strengths

None.

Critical weaknesses
  1. Weak logical, experimental justification of using mean-Q. Broadly speaking, the idea of predicting future attention demand using prompt queries is a fairly well-established idea. However, the justification for using query mean as a proxy is not enough, comparing this only with the last query and a random query. we can compare this with recent queries' attention patterns (SnapKV, PyramidKV, FastKV, ...) or CacheBlend method (From Fig.3, we can see that cacheblend can recall upto ~50% of top-k for the future Q). More fundamentally, since HorizonKV also predicts later layers from early layers using the current tokens, it belongs to the category of query/context relevance, and the term "future relevance" is a stretch.

  2. Baselines are weak. Since CacheBlend, several other efficient KV reuse methods have been appeared, so it is natural to compare HorizonKV with them. Comparable works include RelayCaching, KVCOMM, ProphetKV. Like these works, HorizonKV ultimately aims to reduce latency (TTFT, TPOT) with minimal accuracy degradation. Contrary to the statement in Appendix E, these methods are not complementary to HorizonKV: combining them with HorizonKV is either infeasible or, even if feasible, would further aggravate accuracy degradation. Therefore, a head-to-head comparison is necessary.

  3. The paper lacks the explanations needed to verify that the comparison with the baselines is fair:

  • HorizonKV performs full attention up to layer 4. Does CacheBlend perform full attention up to layer 2?
  • The recomputation ratio described in the Appendix appears to exclude sink tokens and early layers from the count. How was this applied to the baselines?
  • From Figure 6 and Table 2, Random-Q appears to achieve higher accuracy than CacheBlend. This implies that some factor in HorizonKV other than T1 and T2 already gives it an advantage over the CacheBlend baseline. This needs to be specified and justified.
  • Table 2 shows a notable accuracy gain from T2 (Table 7 also shows.). This is a phenomenon frequently observed in KV eviction studies, arising from the removal of attention noise from unimportant tokens. If so, can HorizonKV be compared with CacheBlend combined with a KV eviction method such as SnapKV?

In other words, some results suggest that CacheBlend and HorizonKV are not being compared fairly, and the Evaluation section does not clearly resolve this issue.

Questions for authors
  • I would like to see detailed configurations, a sound interpretation of the results, and additional experiments that address the issues raised in Critical Weaknesses 2 and 3.

  • Please specify which segments are treated as cached(historical) vs dynamic for each agent trace (multi, single), which segments are the cached KV, where they are from, and the positional relationship/distribution of dynamic and historical context. For example, we can describe an agent trace like this: Agent1 prefills A+B and decodes C. Agent2 prefills A+D+C and decodes E. Lastly Agent3 prefills A+F+C+E and decodes G. For Agent3, A,F,C,E are historical, C,E are cached KV, and the last few tokens of F are the dynamic tokens.

Reviewer_pkXeOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

HorizonKV pick which cached KV positions to recompute when cached segments are recombined with new content in agent prompts. A shallow pass to layer 4 averages the new tokens' queries into one query per head to score cached positions (T1), and T2 restricts the recomputed rows to a shared subset of S = 1000 keys. Experiment wrap seven LongBench datasets in AutoGen traces on Llama-3.1-8B and Qwen2.5-14B-1M, against EPIC and CacheBlend. The paper reports average-score gains of 55.3% (Llama) and 64.9% (Qwen) over CacheBlend at 10%, a 5.85x TTFT speedup over CacheBlend on HotpotQA, and up to 2.77x throughput over full prefill.

Critical strengths
  1. The next-token query covers far more causally important positions than the EPIC or CacheBlend signals.
Critical weaknesses
  1. The accuracy metric is unreliable because it rewards more approximate KV recovery despite worse attention fidelity, with large score inversions potentially caused by divergent conversation traces, undermining the paper’s headline results.

  2. The baseline comparison is unfair due to mismatched task counts, unreported actual recomputation budgets, and unequal optimization paths, while the claimed 5.85× speedup comes from comparing different budget points rather than equal-budget performance.

Questions for authors
  1. Can you report first-token KL and top-1 agreement against Full Prefill for HorizonKV, CacheBlend and EPIC at 10% / 30% / 50% on at least 100 tasks per workload?
  2. What does CacheBlend score with HorizonKV's segment budgets, anchors and top-S key sparsification added?
  3. Which CacheBlend and EPIC implementations were used, and do all methods run on the same attention backend for TTFT?
Reviewer_Yu1AOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a heuristic for improving the efficiency of KV-cache reuse in long-context inference, where reused KV segments are recomposed with new content and become stale. The method takes the attention scores of the newly inserted content (e.g., a new user query or peer agent message), estimated cheaply by averaging its shallow-layer queries, and uses them to (1) recompute only the most-attended subset of the reused KV within a fixed budget, and (2) reduce the cost of this recomputation by having the recomputed positions attend only to a shared subset of high-scoring tokens in the context. The method is compared with EPIC and CacheBlend on seven LongBench tasks converted into single- and multi-agent AutoGen traces, using non-reasoning models (Llama-3.1-8B-Instruct and Qwen2.5-14B-Instruct-1M). The results show higher accuracy than both baselines at the same recomputation budget (up to 64.9% higher average score than CacheBlend at a 10% recomputation ratio) and up to 5.85× faster time-to-first-token than CacheBlend at comparable accuracy.

Critical strengths

Strong gains over prior KV-reuse methods. At the same recomputation budget, HorizonKV substantially outperforms EPIC and CacheBlend, especially at low budgets (55.3% and 64.9% higher average score than CacheBlend at a 10% budget on Llama-3.1-8B and Qwen2.5-14B), while achieving up to 5.85× faster time-to-first-token than CacheBlend at comparable accuracy.

Critical weaknesses

No reasoning models evaluated. All experiments use non-reasoning instruction-tuned models (primarily Llama-3.1-8B-Instruct, plus Qwen2.5-14B-Instruct-1M and Qwen2.5-7B-Instruct-1M). Modern agents increasingly run on reasoning models, whose long thinking traces make up a large share of the agent context and may change which parts of the context are relevant later, so it is unclear whether the results hold in that setting.

Relies on new context being informative of future needs. The method scores cached positions using the queries of newly inserted content, assuming that this content signals what the model needs next. In real agentic applications this often does not hold: for example, an agent decides to retrieve a document after seeing the user query, so the reused document is appended after the intent-bearing content and is often followed by no new context at all before generation.

Questions for authors
  1. How would HorizonKV perform on models with hybrid attention, such as interleaved sliding-window and global layers, or linear-attention layers mixed with full attention? All evaluated models use full attention in every layer.

  2. How are segments defined? How is the context divided into reusable and dynamic segments, what is the distribution of segment lengths and counts per context, and what is the effective recomputation ratio once per-segment minimum budgets and mandatory anchors are included?

  3. How would HorizonKV perform on real agentic workloads? The evaluated "agent traces" are LongBench long-context tasks wrapped in a fixed AutoGen pipeline of one to three calls, with no tool use or iterative interaction. How does the method fare on multi-turn, tool-using agent benchmarks (e.g., SWE-bench, GAIA, BrowseComp), where relevance shifts across many turns?

  4. How does HorizonKV perform with reasoning models? All evaluated models are non-reasoning instruction-tuned models.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.