QueryFlow: Multi-Hop Graph Retrieval with Adaptive Query Evolution

The paper builds a multi-hop graph retriever, QueryFlow, that revises the question as it searches. After each propagation layer, it condenses the context found so far into a summary vector, merges it into the question state, and uses the new state to steer how the next layer searches. Earlier graph retrievers such as GFM-RAG keep the original question as the condition throughout propagation. Yet in multi-hop QA, some evidence looks irrelevant to the original question until an intermediate fact has been found. On four multi-hop QA datasets, compared with GFM-RAG, the share of questions whose top 10 results contain all needed evidence rises by 8.40 percentage points on average, and LLM answer accuracy rises by 11.6 percentage points. A question state that updates with what is already known finds complete evidence more often than a fixed question.

Teams working on multi-hop retrieval should read it. It adds no new LLM calls; the change lives entirely inside the graph retriever. Each question-state update is one attention pooling over all entities in the graph followed by a GRU, all tensor operations. That sets it apart from iterative retrieval that has an LLM rewrite the query each round: that kind of method calls an LLM every round and spends tokens. On answer accuracy, QueryFlow is also 8.0 percentage points above LinearRAG, the strongest baseline on answering.

What problem it actually solves

Take the example in Figure 1 of the paper: "Where was the author of The Hobbit born?" Answering it needs two documents: one saying Tolkien wrote The Hobbit, and one saying Tolkien was born in Bloemfontein. Matched against the original question alone, the second struggles to rank near the top.

The most direct measure for this is full recall: a question scores 1 only if every document it needs appears in the top k, and 0 if even one is missing (FR@k, short for full recall at k). R@k can still score well when one document is missing, yet the generator often cannot answer without it.

The overall flow

QueryFlow is built on an entity graph. Offline, entities and the relations between them are extracted from the documents, and the system records which documents each entity appears in. When retrieving for one question online, the flow is:

1. A frozen text encoder turns the question into a vector, the initial question state; entities mentioned in the question are marked as starting points on the graph.
2. The graph propagates for 6 layers. Before propagation, the starting entities take the initial question state as their representation and all other entities start from zero; each relation's vector comes from the same encoder applied to the relation name. In each layer, every entity collects messages from its neighbors and combines them with its previous representation to get a new one.
3. Between adjacent layers (5 times), the current question state pools the entity representations of the whole graph into one vector, which is merged into the question state for the next layer.
4. After the 6 layers, each entity gets a score, entity scores are summed onto the documents they appear in, and the top k documents go to the LLM to answer.

The key division of labor: entity representations accumulate the relations found on the graph, and the question state decides where the next layer searches. Below we take step 3 apart, and then how the question state shapes the next layer.

How the question state is updated

The question state is a 512-dimensional vector that starts as the encoding of the question itself. After each propagation layer except the last, it is updated in two steps.

The first step pools. The previous question state is compared with each entity's representation, softmax over these similarities gives every entity a weight, and the entity representations are averaged with those weights. Entities that match the current question better carry more weight in the pooled vector. However large the graph, the result is a fixed-length vector.

The second step merges. A GRU takes the pooled vector and the old question state and computes a candidate new state; another gate then decides, dimension by dimension, how much of the difference between old and new to take in. In the Tolkien example (illustrative): after the first layer, the representation of the entity "Tolkien" already carries the relation "author of The Hobbit", so it gets a high weight when pooling, and the updated question state shifts somewhat toward Tolkien. Hoot says▾

Hoot saysOne update of the question state (illustrative)Close ✕

Pool the entities by relevance, then decide per dimension how much to change. For the same gap, a wide-open gate takes in a lot and a nearly closed gate barely moves.

1. Illustrative: in one dimension the old value is 0.2 and the candidate is 1.0, a gap of 0.8.
2. Gate 0.9: takes in 0.72, so this dimension becomes 0.92, almost at the candidate.
3. Gate 0.1: takes in only 0.08, so this dimension becomes 0.28, barely moving.

Illustrative example; the numbers are not results from the paper. Entities that match the question weigh more in the pooled vector. The GRU proposes a candidate new state. The gate decides, per dimension, how far to move toward that candidate. So the question state shifts gradually instead of being replaced. Source: paper §3.3 query update (pooling, GRU, per-dimension gate, normalization); numbers are illustrative

Why not simply have an LLM rewrite the query each round? That would cost one LLM call per round. QueryFlow's update is all tensor operations on the graph, and the retriever itself spends no API tokens.

How the new question state shapes the next layer

The question state acts on the next propagation layer through two interfaces.

The first is starting-point injection (the paper calls it boundary feedback). Each layer adds the current question state back onto the starting entities. The starting points are always the entities mentioned in the question, but what is injected changes with the question state. Later layers of propagation thus always carry the latest search intent.

The second is the relation gate (the paper calls it relation feedback). Each relation type on the graph has its own vector, such as "author of" or "born in". The question state produces a set of gates between 0 and 1 that multiply these relation vectors dimension by dimension, one set shared by all relations. After the gating, each layer passes the result through its own two-layer MLP to get the relation vector used in that layer. When a message travels along an edge, the message is the neighbor's representation multiplied, dimension by dimension, by the adjusted relation vector. All messages an entity receives are simply summed, and starting entities also add the injected question state. This sum is concatenated with the entity's previous representation, passed through a linear layer and normalization, and added back to the previous representation. In effect, the question state can amplify or damp some dimensions of the relation vectors and so change how neighbor messages pass.

For the final scoring, the model does not use the updated question state but the original question vector. It concatenates that vector with each entity's final representation and feeds them to a two-layer MLP, which outputs the entity's score. The authors' reasoning: the updated state steers propagation, while final relevance stays tied to the original question. The ablation favors this choice; applying one more update after layer 6 and scoring with the resulting question state lowers FR@10 by 1.82 points. That state exists only in this ablation.

The step from entity scores to document scores has one more detail. Each entity's score is first made positive and then added to every document it appears in; the more documents an entity appears in, the smaller its share for each. An entity that appears everywhere, such as "United States" (illustrative), therefore adds only a little to each document.

Training and evaluation

Training uses 60,000 questions from the training sets of three datasets (2WikiMultiHopQA, HotpotQA, MuSiQue). The supervision is a set of supporting entities for each question, and the loss is computed only on entity scores, pushing supporting entities above the others; the question-update module is learned through its effect on later propagation and on entity scores. Retrieval itself uses none of these annotations.

Evaluation uses fixed subsets of the validation sets of these three datasets: 1,000 questions each for 2WikiMultiHopQA and HotpotQA and 1,003 for MuSiQue, plus all 1,600 validation questions of ConcurrentQA, which was not used in training. At evaluation time, the "needed documents" are the supporting documents annotated in each dataset, used only to compute R@k and FR@k. At retrieval time the retriever sees only the question, the entities linked from it and the graph built offline. Every method answers with Qwen3.5-9B from its retrieved results, and an LLM judge decides whether each answer is right, reported as LLM-Acc.

What the results show

Retrieval numbers are averages over the four datasets (%), and LLM-Acc is the average share answered correctly. LinearRAG is not in the paper's retrieval comparison; only its answers are compared.

Against GFM-RAG, R@10 rises by 4.98 points and FR@10 by 8.40. Full recall gains more, so the benefit comes mainly from adding the last missing document. MuSiQue shows it more clearly: HippoRAG 2 has higher R@10 than QueryFlow (64.42% versus 61.60%) but lower FR@10 (31.11% versus 37.82%). Average recall alone cannot show who more often gathers all the evidence for a question.

How much does the question update contribute? In the merge step, the difference between new and old is multiplied by a coefficient between 0 and 1 before it is added to the question state; the paper calls it the update strength, and the full model uses 1. The authors take the same trained model and set this coefficient to 0, which skips the merge, so the question state stays at its initial value. FR@10 then falls from 70.38% to 61.78%; the paper reports the gap as 8.59 points, which shows this model relies heavily on the question update.

It falls on all four datasets, most on ConcurrentQA at 15.51 points and least on 2WikiMultiHopQA at 2.50. Removing the two interfaces one at a time, starting-point injection matters more: without it FR@10 loses 4.73 points, and without the relation gate 3.44.

Questions needing 4 documents gain the most. Comparing question by question with GFM-RAG on 4,596 shared questions, for questions needing 4 documents FR@10 rises from 32.16% to 50.25%. Across all 4,596 shared questions, QueryFlow newly completes 434 questions and loses 86, a net gain of 348; of the questions GFM-RAG completes, QueryFlow also completes 97.0%. The paper also cautions that support-set size is tied to dataset composition; these numbers pool questions, not averages over the four datasets.

On online cost, on the 1,000 evaluation questions of 2WikiMultiHopQA, question processing, retrieval and answering take 580 seconds in total, against 5,960 for GFM-RAG, and token use falls from 5.44 million to 3.59 million. This gap should not be credited to the question update, which by itself only adds computation. QueryFlow's full recall with only the top 5 documents (62.63%) is already slightly above GFM-RAG's with the top 10 (61.98%), so the context fed to the LLM can be shorter.

Where I think it falls short

First, the "no question update" control was not retrained. The 8.59-point gap comes from freezing the question state in a model trained with updates, a model that never learned to propagate under a fixed question, so the gap may be larger than against a model trained separately with a fixed question. The closest fixed-question baseline is GFM-RAG, which shares the graph construction and document aggregation, with a gap of 8.40 points. But the two may not share the same training setup, so this is not a strict same-architecture control either.

Second, training and evaluation data come from the same sources. 20,000 questions were taken from the training set of each of three datasets, and evaluation uses their validation sets. On ConcurrentQA, the only dataset not used in training, FR@10 is still 6.90 points above GFM-RAG, so it is not just memorizing the data distribution, but each evaluation corpus has only a few thousand to about ten thousand documents, still far from production corpora.

Third, building the graph offline is not cheap. On 2WikiMultiHopQA, indexing uses 11.2 million tokens, about the same as GFM-RAG, and the whole method depends on the quality of entity extraction and entity linking.

Fourth, all results come from a single training run with one random seed. Ablation gaps of 1 to 5 points need more runs to confirm.

How a retrieval team could try it

1. Start by measuring full recall on your own multi-hop questions. Pick queries that need two or three documents and check how far R@10 and FR@10 are apart for your current retriever; if FR@10 is already reasonably high and the gap is small, incomplete evidence is not the main problem.
2. If you already use an entity-graph retriever like GFM-RAG, the architectural change is modest: attention pooling, a GRU, an update gate and the relation gate. But the whole retriever has to be retrained on data with supporting-entity labels. The question-state update is a prerequisite; of the two interfaces, removing starting-point injection hurts more, so keep it first if you have to trim.
3. Use the update strength as a switch. Run the same model at strength 0 and 1 and compare FR@k to see quickly what the question update is worth on your data. Treat that gap as an upper bound; the real gain needs a comparison with a separately trained fixed-question model.
4. Finally, see whether the context can shrink. If full recall with the top 5 documents already matches the old top 10, you can feed the LLM fewer documents and save generation cost.

Verdict

In one sentence: in multi-hop retrieval the question state should update with what has already been found, and this can be done inside the graph retriever with tensor operations and no LLM calls.