QueryFlow: Multi-Hop Graph Retrieval with Adaptive Query Evolution
Authors: Manzong Huang, Chenyang Bu, Yi He, Jiapu Wang, Xindong Wu
Organizations: Key Laboratory of Knowledge Engineering with Big Data (the Ministry of Education of China), School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, China · Department of Data Science, College of William and Mary, Williamsburg, Virginia, USA · Nanjing University of Science and Technology, Nanjing, China
Multi-hop retrieval-augmented generation (RAG) supports Web information seeking and fact verification by recovering complementary evidence across related pages within a limited retrieval budget. Scoring evidence independently against the original question can miss supporting units whose relevance emerges through intermediate facts. Iterative retrieval incorporates these facts into subsequent queries, while graph retrieval explicitly models relations among evidence units. Yet fixed-query graph retrievers update entity representations without adapting the query condition to accumulated relational context. We view multi-hop evidence recovery as the coupled evolution of evidence representations and query conditions, with accumulated context informing both what the retriever represents and how it searches for complementary evidence. QueryFlow realizes this perspective by recurrently integrating query-conditioned summaries of graph context into a shared query state, which controls boundary inputs and relation features for subsequent propagation. Across four representative multi-hop question answering (QA) datasets, QueryFlow achieves macro Recall@10 (R@10), Full Recall@10 (FR@10), and LLM-Acc gains of 4.98, 8.40, and 8.0 percentage points over representative baselines, respectively.
Figures & tables
Figure 1. A fixed query state continues to favor evidence directly related to the original question. Updating the state with accumulated context guides retrieval toward complementary evidence, helping complete the support set. Q1 illustrates the updated state’s meaning. A two-round retrieval example compares fixed and updated query states. After identifying J. R. R. Tolkien as the author of The Hobbit, the fixed query state continues to favor related book evidence. Updating the query state with this context guides retrieval toward Tolkien's birthplace, completing the supporting evidence in the example. Q1 illustrates the meaning of the updated latent query state.
Figure 2. Overview of QueryFlow for multi-hop evidence retrieval from interconnected document collections. A question is grounded in an entity graph whose nodes are linked to source documents. Graph propagation and recurrent query updates alternate across layers; the updated query state conditions the boundary inputs and relation features of the next layer. Final entity representations are scored together with the original query, and the scores of all entities are transformed by softplus and aggregated through associations between entities and documents using reciprocal document frequency weights. The documents with the highest scores provide evidence for answer generation. The terminal qL update is used only for the readout ablation. The question initializes a query vector and linked entity states. Intermediate graph layers send entity representations to recurrent query updates that control the next layer. All entity representations are scored with the original query. Softplus scores, reciprocal document frequencies, and links between entities and documents yield document scores; the documents with the highest scores support answer generation. The terminal update after the final graph layer produces qL only for the readout ablation.
Category
Method
2WikiMultiHopQA
HotpotQA
MuSiQue
ConcurrentQA
Average
LLM-Acc
Contain
LLM-Acc
Contain
LLM-Acc
Contain
LLM-Acc
Contain
LLM-Acc
Contain
Query-based retrieval
Dense RAG
0.235
0.228
0.592
0.517
0.241
0.185
0.331
0.381
0.350
0.328
HyDE
0.273
0.266
0.654
0.568
0.288
0.231
0.374
0.415
0.397
0.370
ColBERTv2
0.313
0.306
0.624
0.538
0.237
0.187
0.464
0.486
0.410
0.379
Iterative and structure-aware retrieval
FastToG
0.326
0.331
0.385
0.327
0.077
0.068
0.233
0.269
0.255
0.249
RAPTOR
0.264
0.269
0.393
0.346
0.102
0.076
0.308
0.364
0.267
0.264
Table 1. Answer generation across four datasets. Scores range from 0 to 1. Baselines are grouped by retrieval mechanism and ordered within each group by average LLM-Acc. Averages are unweighted. Best in bold , second underlined .
Method
R@10
FR@10
R@30
FR@30
G-Retriever
36.22
16.72
38.58
17.75
DALK
57.09
29.38
60.63
33.09
RAPTOR
56.53
27.84
68.19
43.84
LightRAG
61.66
37.28
69.67
47.70
GraphRAG
65.72
41.58
74.65
54.27
HyDE
66.52
43.17
75.16
54.73
Table 2. Macro retrieval scores (%), ordered by FR@30. We compare R@ k and FR@ k for methods with document-level outputs, obtained directly or by mapping retrieved graph or hierarchical units to source documents. Results for each dataset appear in Table 7 . Best in bold , second underlined .
Figure 3. Macro retrieval comparison, ordered by R@10. (a) Scores from Table 2 ; darker cells indicate higher values. (b) Differences between the displayed R@ k and FR@ k at k=10 and k=30 , with bars sharing a scale from 0 to 30 percentage points. A score matrix shows R@10, FR@10, R@30, and FR@30 for all ten methods. Two aligned bar columns compare each method's gap between coverage and completeness at budgets ten and thirty on the same scale. QueryFlow scores 81.93, 70.38, 87.12, and 77.78 percent, with gaps of 11.55 and 9.34 percentage points, respectively.
Figure 4. Effect of query evolution. (a) Macro recall and full-recall gains over α=0 at k=10 and k=30 . (b) FR@10 gains from α=0 to α=1 by dataset and their macro average with equal weights. Panel a plots gains across alpha values zero, one quarter, one half, three quarters, and one. At alpha one, R@10, FR@10, R@30, and FR@30 improve by 5.27, 8.59, 3.76, and 6.45 percentage points. Panel b shows FR@10 gains of 2.50, 7.88, 8.48, and 15.51 points on 2WikiMultiHopQA, HotpotQA, MuSiQue, and ConcurrentQA, with a macro gain of 8.59 points.
Variant
R@10
FR@10
R@30
FR@30
Full model
81.93
70.38
87.12
77.78
w/o query evolution ( α=0 )
76.66
61.78
83.36
71.33
w/o boundary feedback
79.04
65.65
85.05
74.24
w/o relation feedback
79.83
66.94
85.62
75.20
Readout with qL
80.65
68.56
86.13
76.76
Table 3. Macro ablation scores (%). Best in bold .
Figure 5. Evidence recovery at k=10 . (a) FR@10 by support set size; labels show gains (pp), and n is group size. (b) Paired outcomes. The 434 gains minus 86 losses yield 348 net recoveries. Panel a compares GFM-RAG and QueryFlow full recall for support sets of size one through four. Panel b is an outcome matrix with two rows for GFM-RAG and two columns for QueryFlow. There are 2805 questions complete for both, 86 only for GFM-RAG, 434 only for QueryFlow, and 1271 incomplete for both, across 4596 paired questions.
Figure 6. Retrieval budget analysis. (a) Macro FR@ k for methods that rank documents. (b) QueryFlow’s marginal FR gain, ΔFR/Δk , in percentage points per added document. Panel a shows six full recall curves at cutoffs 3, 5, 10, 15, 20, and 30. QueryFlow rises from 51.99 to 77.78 percent. Panel b shows marginal gains of 5.32, 1.55, 0.59, 0.38, and 0.25 percentage points per added document over successive budget intervals.
Method
Index/Build
Retrieval/Reasoning
Time (ks)
Tokens (M)
Time (ks)
Tokens (M)
GFM-RAG
1.80
11.2
5.96
5.44
HippoRAG 2
2.08
11.1
1.36
8.53
ToG
2.11
5.15
1.19
12.7
FastToG
0.128
6.44
0.00820
1.25
QueryFlow
1.80
11.2
0.580
3.59
Table 4. Efficiency on 2WikiMultiHopQA. Online time and tokens include query processing, retrieval, and answer generation.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Input records
Documents
2WikiMultiHopQA
1,000
9,594
HotpotQA
1,000
9,811
MuSiQue
1,003
11,666
ConcurrentQA
1,600
2,840
Appendix
Table 5. Evaluation input records and retrieval corpus sizes.
Dataset
EM
F1
Precision
Recall
Contain
LLM-Acc
2WikiMultiHopQA
65.3%
75.4%
73.9%
83.3%
81.9%
82.9%
HotpotQA
56.7%
69.6%
71.0%
77.0%
69.5%
78.6%
MuSiQue
24.5%
35.1%
35.3%
49.0%
37.5%
43.9%
ConcurrentQA
55.7%
63.5%
63.5%
72.5%
67.8%
73.2%
Macro
50.5%
60.9%
60.9%
70.4%
64.2%
69.6%
Appendix
Table 6. Additional answer generation metrics for QueryFlow (%). Macro is the unweighted mean across datasets.
2WikiMultiHopQA
HotpotQA
MuSiQue
ConcurrentQA
Macro
Method
R@10
FR@10
R@30
FR@30
R@10
FR@10
R@30
FR@30
R@10
FR@10
R@30
FR@30
R@10
FR@10
R@30
FR@30
R@10
FR@10
R@30
FR@30
G-Retriever
32.10
11.28
34.37
12.08
44.85
23.51
46.57
24.12
25.80
11.60
27.72
12.10
42.14
20.50
45.66
22.70
36.22
16.72
38.58
17.75
DALK
63.68
28.30
63.95
28.80
63.78
40.54
67.40
45.57
40.44
10.87
44.35
14.08
60.47
37.79
66.81
43.91
57.09
29.38
60.63
33.09
RAPTOR
59.22
27.10
80.30
61.70
65.80
40.70
65.80
40.70
40.87
8.87
66.43
38.29
60.22
34.69
60.22
34.69
56.53
27.84
68.19
43.84
LightRAG
52.20
24.50
59.75
31.80
82.35
67.60
88.90
79.30
57.40
24.23
69.42
39.38
54.69
32.81
60.59
40.31
61.66
37.28
69.67
47.70
GraphRAG
70.62
39.90
74.35
46.50
77.60
60.80
86.70
76.90
49.20
14.56
60.10
26.12
65.44
51.06
77.44
67.56
65.72
41.58
74.65
54.27
Appendix
Table 7. Retrieval scores for each dataset (%), ordered by macro FR@30. We compare R@ k and FR@ k for methods with document-level outputs, obtained directly or by mapping retrieved graph or hierarchical units to source documents. Macro is the unweighted mean across datasets. Best in bold , second underlined .
Readout
R@10
FR@10
R@30
FR@30
MMR Top-20
80.48
67.84
85.31
74.72
Top-20 (no MMR)
80.57
67.79
84.87
73.90
All entities (default)
81.93
70.38
87.12
77.78
Appendix
Table 8. Document readout comparison. Macro retrieval scores across four datasets (%).
Multi-hop question answering studies how systems combine evidence across documents, facts, or modalities to answer questions requiring linked reasoning.
Multi-hop retrieval must recover passages that provide sufficient evidence together. An initial passage often resolves an entity or relation implicit in the question, making the missing evidence easier to describe only after retrieval begins. Graph retrieval improves access to related evidence through stored corpus structure, but its retrieval signal is commonly derived from the original question. Complementary evidence must then be reached through stored relations even when an observed passage provides a more direct semantic cue. We introduce EviReform, which separates revising the retrieval request from aggregating evidence in the graph. Retrieved source passages formulate residual queries for the unresolved information need. The original and residual retrieval signals are normalized separately, combined, and propagated between propositions that share entities. On 2WikiMultiHopQA, HotpotQA, and MuSiQue, EviReform exceeds the strongest baseline by up to 5.59 Recall@5 points and 4.50 F1 points. These results show that observed evidence can guide graph retrieval toward the part of a supporting chain left underspecified by the original question. Code is available at https://github.com/XrazyMee/EviReform.
Xinlong Xu, Yoshua Y. Li
Nanjing University of Information Science and Technology · Meituan
Multi-hop question answering often fails when retrieval treats evidence as isolated matches to the original question, since the facts needed to answer a complex question are usually connected through intermediate entities, relations, and constraints. We propose HyperProve, a retrieval-augmented QA framework that addresses this challenge by coupling question decomposition with answer-conditioned expansion over a hypergraph of atomic facts. HyperProve does not use atomic facts, hypergraphs, or iterative retrieval in isolation; instead, it carries intermediate answers and supporting hyperedges as retrieval state, then uses that state to bias the next local hypergraph expansion. This design enables HyperProve to construct coherent evidence chains for final answer generation while making the retrieval process stateful and fact-centered. Across multi-hop QA benchmarks, HyperProve achieves the best overall performance in our evaluation, outperforming the strongest baselines by an average relative improvement of 6.2% in answer accuracy and 4.9% in F1.
An Nguyen Phu, Dung Nguyen Quang, Luu Hieu An +3
Hanoi University of Science and Technology · Monash University · University of Oregon
A central bottleneck in multi-hop Question Answering (QA) is that the granularity at which a question is expressed often differs from the granularity at which corpus evidence is retrievable. Existing methods address this mismatch by imposing fixed graph structures over the corpus, by iteratively reformulating the query, or by executing a generated program over it, but these strategies do not explicitly decide when a query unit is already supported by evidence and when it should be refined. We formulate this bottleneck as retrievable granularity discovery and introduce Hi-Q, an evidence-conditioned framework for hierarchical query refinement. At each query node, a resolution operator tests whether retrieved evidence supports the current query unit; resolved nodes terminate, while unresolved nodes are expanded by a dependency-preserving binary operator and checked by a semantic coverage verifier. Hi-Q therefore grows a query tree whose topology is determined by corpus support signals rather than by a fixed decomposition template or a pre-built graph. We evaluate Hi-Q on three multi-hop QA benchmarks, primarily under full-corpus retrieval, where dependent evidence must be located among open-domain distractors rather than within a small annotated pool. In this setting Hi-Q reaches 52.3 EM and 64.0 F1 averaged over the three benchmarks, ahead of the iterative retrieval baseline IRCoT by 15.1 EM / 18.2 F1 on that same average, and ahead of the graph-based RAG baseline PropRAG by 11.5 EM / 12.0 F1 on MuSiQue-full, without corpus-wide graph construction. In the restricted supporting/distractor setting used by prior work, Hi-Q likewise attains the best accuracy, with 57.9 EM and 69.3 F1 on average, ahead of PropRAG by 5.6 EM / 3.9 F1 and IRCoT by 13.7 EM / 15.8 F1. The project page is available at https://hi-q-project.github.io/.
Jueun Kim, Sungho Park, Wook-Shin Han
Department of Computer Science and Engineering, POSTECH · Graduate School of Artificial Intelligence, POSTECH