acceptodds
Withdrawn from ICLR 2027

GRAPH-GUIDED AND ADAPTIVE KV-CACHE PREFETCHING FOR RETRIEVAL-AUGMENTED GENERATION

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

The document order and meaning of the chunks required by a retrieval-augmented language model often show relationships. We have investigated whether these relationships can be used to prepare key–value (KV) cache states before a chunk is requested. We represent the chunks as a graph by including their top semantic neighbours as well as the structural links that exist within the document. For ranking the candidates, we use two-hop retrieval and select a number of chunks up to . We compare three methods: fixed weights, a globally learned balance, and an online policy which adjusts the balance after observing ranking misses. The evaluation involves an archived simulated-cache study covering six model configurations, a real experiment carried out with Qwen2.5-1.5B using vLLM and LMCache, and answer-quality experiments with Gemini 3.5 Flash-Lite. For the real access trace derived from Hotpot at , offline adaptation increases prediction recall from 80.50% to 95.33% and reduces the ready-cache time to the first token from 56.68 to 51.36 ms as compared to cosine prefetching. With synchronous candidate preparation, the corresponding times are 902.67 and 883.27 ms, whereas they are 73.41 ms when there is no prefetching. In the separate 60-question quality experiments, offline adaptation raises the HotpotQA F1 from 47.94 to 53.83, while cosine performs better on 2WikiMultiHopQA, with an F1 of 48.18 versus 40.53. Altogether, these results demonstrate the advantage of graph-guided prediction on the tested access trace and show that its impact on answer quality varies according to the dataset.

Primary area:
optimization
Keywords:
RAG, Cache, Graphs, VLMS, Foundation Models

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_da4yOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes GraphKV, a graph-guided KV-cache prefetching strategy for RAG. It combines semantic similarity, document adjacency, two-hop traversal, and offline/online weight adaptation to predict future chunk accesses.

Experiments using vLLM/LMCache show improved prediction recall (80.50% to 95.33% on HotpotQA at K=10K=10) and lower ready-cache TTFT. Standardized ablations support the contributions of individual components. However, asynchronous experiments show no application-level latency advantage, while answer-quality improvements on HotpotQA do not generalize to 2WikiMultiHopQA. Overall, the results demonstrate better cache candidate selection but not consistent end-to-end efficiency or answer-quality gains.

Critical strengths

S1. Meaningful improvement in cache candidate prediction. GraphKV substantially improves recall over cosine selection. The standardized ablations (80.50% →\rightarrow 88.00% →\rightarrow 89.50% →\rightarrow 95.33%) provide evidence that structural links, two-hop traversal, and offline adaptation contribute beyond semantic similarity alone.

S2. Careful empirical analysis and transparent limitations. The evaluation includes real vLLM/LMCache experiments, cache correctness checks, asynchronous execution, and answer-quality measurements. Importantly, the authors distinguish prediction accuracy from application-level latency and explicitly report negative results, making the evaluation more informative and credible.

Critical weaknesses

W1. No demonstrated end-to-end efficiency benefit. Despite higher prediction recall, GraphKV does not outperform cosine or no-prefetch in application TTFT. At a 1500-ms lead time, offline GraphKV is 9.71 ms slower than cosine, even with all candidates prepared. The small ready-cache savings are outweighed by preparation and scheduling costs, substantially weakening the practical systems contribution.

W2. Limited fidelity to actual multi-chunk RAG inference. The real-cache benchmark evaluates exact-prefix reuse of individually prepared chunks rather than composition within concatenated RAG prompts. Positional dependencies and cross-chunk attention may invalidate direct KV reuse. Thus, the experiments do not establish whether the approach accelerates realistic multi-document generation.

W3. Potentially optimistic workload construction. The access traces deliberately balance semantic, structural, and multi-hop transitions, rather than reflecting observed production retrieval sequences. Such construction may favor the proposed graph topology. Moreover, repeated measurements over the same 600-event traces provide limited evidence of generalization to independent workloads.

W4. Inconsistent answer quality and evidence coverage. HotpotQA F1 improves by 5.89 points, but the confidence interval includes zero. On 2WikiMultiHopQA, F1 drops by 7.65 points because graph pruning excludes essential evidence. This exposes a fundamental trade-off between selective prefetching and evidence completeness, particularly for multi-hop reasoning.

Questions for authors

Q1. Realistic workloads: How do the prediction gains change on naturally occurring RAG access traces rather than synthetically balanced transitions? What fraction of real accesses are reachable within the proposed two-hop graph?

Q2. End-to-end break-even: Under what concrete conditions (candidate reuse, prefetch cost, concurrency, and available background compute) would GraphKV outperform both cosine and no-prefetch in application latency?

Q3. KV-cache composability: Can the authors demonstrate correctness and latency improvements when independently prefetched chunks are reused within actual multi-document RAG prompts, including necessary positional or attention-aware recomputation?

Q4. Evidence loss: Why does graph pruning exclude critical supporting facts on 2WikiMultiHopQA? Would a coverage-aware fallback to global cosine retrieval recover answer quality without sacrificing prediction gains?

Q5. Statistical robustness: Given that the HotpotQA F1 improvement is not statistically conclusive on 60 questions, do larger evaluation sets or additional random seeds confirm an answer-quality advantage?

Q6. Adaptation and feedback: What proportion of online prediction errors are ranking misses versus graph-coverage misses? How would the online method obtain reliable supporting-evidence feedback in deployment, where ground-truth labels may be unavailable?

Reviewer_MZ1FOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The authors propose a graph-guided KV-cache prefetching method for RAG. It combines semantic similarity, document structure, and two-hop graph traversal to predict future chunk accesses, with offline and online weight adaptation. The results show improvements in prediction recall and ready-cache latency, but these gains do not consistently translate into better end-to-end performance.

Critical strengths
  1. The paper is well organized and easy to understand.

  2. The experimental analysis is detailed.

Critical weaknesses
  1. The novelty is limited. The method mainly combines existing techniques, including semantic similarity, structural connections, two-hop traversal, and relatively simple weight adaptation.

  2. The evaluation requires controlled access traces with predefined semantic, structural, and multi-hop patterns. It is unclear how well the results would generalize to realistic RAG workloads.

  3. The real-cache experiments are limited to exact-prefix reuse and do not naturally show how KV caches would be reused across multiple retrieved chunks in a practical RAG system.

  4. The method does not demonstrate consistent end-to-end latency improvements over the baselines.

Questions for authors
  1. How are the controlled access traces generated?

  2. How would GraphKV handle KV-cache reuse when multiple retrieved chunks are combined into a single prompt?

  3. Could the authors compare against simpler alternatives?

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

This paper proposes GraphKV, a candidate selection policy for KV-cache prefetching in RAG. Its core idea is that future accesses may involve chunks that are semantically related to the current chunk. These chunks may also be linked through document adjacency or indirect relationships. The method organizes semantic neighbors and document structure into a graph. It generates candidates through graph search and learns global semantic and structural weights from training access data. The experiments show that GraphKV improves target prediction accuracy and reduces request latency.

Critical strengths
  1. The paper has a clear motivation. The ablation study shows that the proposed components improve candidate selection. Prediction recall increases from 80.50% with semantic information alone to 88.00% after adding structural information. It further rises to 89.50% with two-hop search and 95.33% with offline weight learning.
  2. The experiments effectively distinguish selection accuracy from execution cost. The authors measure both synchronous preparation and asynchronous execution. These measurements clarify the relationship between candidate selection and system execution.
Critical weaknesses
  1. The main prediction gains are observed on synthetic access patterns that closely match the method’s structure. These gains may largely reflect the alignment between the method and the access generator.
  2. The current experiments do not provide sufficiently clear evidence of practical benefits from the modest algorithmic advance. The available results do not establish how much practical improvement it offers for the target RAG applications.
Questions for authors
  1. Please clarify how the next target is sampled for semantic, structural, and multi-hop events. These details are important for assessing the external validity of the prediction gains.
  2. Please clarify the main source of additional overhead in the asynchronous experiments. Does it come from candidate selection, interference with the current request, or other scheduling operations? This would affect the assessment of the method’s practical value.

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

Related papers

Discussion (0)

Sign in to comment.