QueryFlow: Multi-Hop Graph Retrieval with Adaptive Query Evolution
Manzong Huang, Chenyang Bu, Yi He, Jiapu Wang, Xindong Wu
cs.IR, cs.AI
2026-11-03
QueryFlow updates a shared query from graph context to steer later hops. Across four multi-hop QA sets, macro FR@10 rises 8.40 points over GFM-RAG and LLM-Acc 8.0 over LinearRAG.
Multi-hop retrieval has to return the whole supporting set inside a fixed budget. Miss one page and the reasoning chain breaks. Scoring each candidate against the original question misses units that become relevant only after an intermediate fact appears. For where the author of The Hobbit was born, locking onto J.R.R. Tolkien moves the remaining need to a birthplace, Bloemfontein. A query nailed to the original sentence keeps favoring pages about the novel.
Iterative retrievers feed retrieved passages or rewritten questions into the next search, but cross-document entity relations stay buried in that text history. Graph retrievers make entities and relations explicit. Fixed-query models such as GFM-RAG still update entity states under the original condition. Context piles up on the nodes, and the next layer keeps searching as if the question had not changed.
The corpus becomes an entity graph. Nodes are entities, edges carry relation types, and an incidence matrix records which documents mention which entities. A frozen text encoder embeds the question and the relations; linear maps place them in one vector space. Entities linked to the question start at the initial query q0, and every other entity starts at zero. Topology, document links, and the grounding sites stay fixed.
Each layer lets the current query state drive two inputs. Boundary feedback writes that state only onto the original question-linked entities, putting the residual information need back at the same anchors. Relation feedback turns the query into a gate that rescales each base relation embedding dimension by dimension, then a layer-specific MLP transforms it. The gate is shared across relation types; each relation keeps its own base vector. Messages use DistMult: neighbor states are multiplied elementwise by the gated relation, summed, added to the boundary term, and written back with a residual link.
Between layers the previous query attends over every entity and reads out a fixed-width summary, so the controller does not grow with the graph. A GRU mixes that summary with the previous state, and a second gate decides how far the state moves toward the candidate. The step size α is 1 by default, so the full step is applied. Setting α to 0 freezes the query at q0. The recurrent cell, the transition gate, and the relation gate share parameters across layers.
Ranking stays tied to the original question. After the last layer, an MLP scores each entity from its final state concatenated with q0. softplus turns those logits into positive weights, reciprocal document frequency down-weights entities that occur widely, and the incidence matrix sums the weights onto documents. Training is entity-level only: 0.3 weighted binary cross-entropy plus 0.7 listwise cross-entropy. Document aggregation runs at inference. Gradients from the entity scores train both propagation and the recurrent controller.
The four benchmarks are 2WikiMultiHopQA, HotpotQA, MuSiQue, and ConcurrentQA. Every method generates answers with Qwen3.5-9B. LLM-Acc is the share of answers an LLM judge accepts. Contain is the share whose text includes the normalized gold string. R@k is mean coverage of supporting documents. FR@k credits a question only when every supporting document sits inside the top k. Macro averages weight the four datasets equally.
QueryFlow's macro LLM-Acc is 0.696 and Contain is 0.642. Against LinearRAG, the strongest answer baseline, that is +8.0 and +6.9 points. Against GFM-RAG the gaps are +11.6 and +5.6. LLM-Acc over LinearRAG rises 15.0 points on 2WikiMultiHopQA (0.679 to 0.829), 3.4 on HotpotQA (0.752 to 0.786), and 7.0 on both MuSiQue (0.369 to 0.439) and ConcurrentQA (0.662 to 0.732).
The retrieval comparison centers on GFM-RAG.
| Method | R@10 | FR@10 | R@30 | FR@30 |
| HippoRAG 2 | 74.29 | 51.38 | 80.95 | 61.59 |
| GFM-RAG | 76.95 | 61.98 | 81.41 | 68.15 |
| QueryFlow | 81.93 | 70.38 | 87.12 | 77.78 |
Over GFM-RAG, R@10 and FR@10 rise 4.98 and 8.40 points, and R@30 and FR@30 rise 5.70 and 9.63. FR@10 gains by dataset are +12.60, +8.11, +5.99, and +6.90 on 2WikiMultiHopQA, HotpotQA, MuSiQue, and ConcurrentQA. On MuSiQue, HippoRAG 2 still leads R@10, 64.42% versus 61.60%, while QueryFlow leads FR@10, 37.82% versus 31.11%.
With parameters held fixed, moving α from 0 to 1 lifts macro R@10 from 76.66% to 81.93% (+5.27) and FR@10 from 61.78% to 70.38% (+8.59). From α=0.25 to α=1, FR@10 climbs from 65.60% to 70.38% with no dip. Every dataset gains FR@10, from +2.50 on 2WikiMultiHopQA to +15.51 on ConcurrentQA. Removing boundary feedback costs 4.73 and 3.54 points of FR@10 and FR@30. Removing relation feedback costs 3.44 and 2.58. Scoring with the terminal query qL instead of q0 lowers FR@10 by 1.82 points.
On 4,596 shared questions, QueryFlow completes 434 support sets that GFM-RAG misses and loses 86 the other way, a net of 348. It keeps 97.0% of the 2,891 sets GFM-RAG already completed and repairs 25.5% of the 1,705 it missed. For four-document support sets (n=398), FR@10 moves from 32.16% to 50.25%, up 18.09 points. Two-document and three-document groups gain 6.38 and 9.62 points.
At five documents, QueryFlow's macro FR@5 is 62.63%, above GFM-RAG's FR@10 of 61.98%. Its FR@10 of 70.38% is above that baseline's FR@30 of 68.15%. The lead grows from 4.37 points at k=3 to 9.63 at k=30. Extra documents buy less: about 5.32 points of FR per document from k=3 to 5, and 0.25 from k=20 to 30.
Efficiency is reported only on 2WikiMultiHopQA. Online retrieval plus generation takes QueryFlow 0.580 kiloseconds and 3.59M tokens, against 5.96 ks and 5.44M for GFM-RAG: 90.3% less time and 34.1% fewer tokens. Indexing matches at about 1.80 ks and 11.2M tokens, because the query update is tensor arithmetic on the existing graph. FastToG is cheaper still, at 0.00820 ks and 1.25M tokens online, with LLM-Acc of 0.326 against QueryFlow's 0.829 on the same set.
When the generator only sees a short list, the missing page hurts more than one extra loosely related hit. Full-set recovery moves more than average coverage, and it shows up earlier in the ranking: five documents match the baseline's ten, and ten match its thirty. The prompt can carry fewer pages.
Indexing cost sits in the same range as GFM-RAG. Adaptation stays inside graph compute, so the system does not call a generator to rewrite the query at every hop. A pipeline that already builds an entity graph and propagates under a fixed query can add this controller.
The gain is incremental. HotpotQA moves only 3.4 LLM-Acc points, and MuSiQue still sits at 0.439. A fuller evidence set does not make a 9B generator answer correctly.
The paper does not list limitations on its own. Several checks are open.
Final scores are anchored to q0. The evolved state changes the ranking only by changing entity representations. The rewritten question in Figure 1, Where was J.R.R. Tolkien born?, shows what the state is meant to capture. The system does not emit a new natural-language query.
The loss is an entity-level listwise objective. FR@k and document rank are not trained directly. Entity accuracy still has to pass through the incidence matrix and reciprocal document frequency before it becomes a document set. There is no measurement of how far FR falls when entity linking is wrong.
The timing table covers one dataset. Attention is a softmax over every entity, and nothing shows that 0.580 ks still holds on a much larger graph. α is one global constant, not a switch that depends on question difficulty. The abstract's three headline gains also mix baselines: +4.98 R@10 and +8.40 FR@10 are versus GFM-RAG, while +8.0 LLM-Acc is versus LinearRAG, which is absent from the document-recall table. Generation and judging both use only Qwen3.5-9B. On MuSiQue, average coverage still trails HippoRAG 2.