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.