acceptodds
Under review as a conference paper at ICLR 2027

BRIDGE-Prop: Reasoning-Guided Bridge Propagation for Multi-Hop Retrieval

13 views

Abstract

Multi-hop question answering often requires combining evidence linked through entities that are absent from the question itself. In reasoning-based iterative GraphRAG, a language model may infer such bridge entities during multi-round retrieval. However, these entities remain in unstructured reasoning text and may be omitted or diluted in later retrieval steps, rather than being retained as explicit, reusable representations in the graph. As a result, they cannot directly guide subsequent graph propagation. We introduce BRIDGE-Prop (Reasoning-Guided Bridge Propagation), an iterative GraphRAG framework that grounds predicted bridge entities to graph nodes and retains them as a cumulative bridge memory across rounds. These bridges act as explicit seeds for the existing Personalized PageRank graph-ranking algorithm, allowing retrieval to pursue multiple intermediate connections. We evaluate BRIDGE-Prop on MuSiQue and 2WikiMultiHopQA on the HippoRAG-2 backbone. It raises 2WikiMultiHopQA recall@5 from .889 to .962 over the strongest iterative baseline, ITER-RETGEN, and lifts answer EM from .608 to .709. By question type and reasoning depth, the gain is largest where a single query cannot gather all the evidence at once: 2Wiki bridge-comparison questions and deeper MuSiQue hops. The retrieval advantage holds for both a proprietary and an open-weight model. BRIDGE-Prop shows how free-text LLM reasoning can be grounded into discrete, symbolic structure, tightening the loop between neural reasoning and structured graph-based retrieval.

Primary area:
foundation or frontier models, including LLMs
Keywords:
multi-hop question answering, GraphRAG, bridge entities, iterative retrieval, Personalized PageRank, knowledge graph, LLM reasoning, retrieval-augmented generation

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

This paper proposes BRIDGE-Prop, an iterative GraphRAG framework that uses LLM-generated bridge entities as additional seeds for Personalized PageRank. The method maintains bridge entities across retrieval rounds and combines retrieved evidence for multi-hop question answering.

Critical strengths
  1. The problem of multi-hop evidence retrieval is important.

  2. The experiments show improvements over iterative retrieval baselines.

Critical weaknesses
  1. Limited novelty. The main idea is to use LLM reasoning to identify intermediate entities and guide subsequent graph retrieval. Similar ideas have already been explored in agentic graph retrieval methods [1, 2, 3, 4]. The proposed approach mainly combines bridge-entity extraction, PPR seeding, and rank fusion, without a sufficiently clear methodological contribution beyond existing approaches.

  2. Insufficient baselines. The paper lacks comparisons with many recent agentic retrieval methods[1,2,3,4]. These methods also support multi-step reasoning and graph exploration. Comparing primarily against IRCoT and ITER-RETGEN is insufficient to demonstrate the advantages over modern agentic GraphRAG systems.

  3. Limited generalizability. Although the authors evaluate two graph construction methods, both rely on PPR for retrieval. Different GraphRAG systems employ substantially different retrieval mechanisms, including agentic graph traversal and learned retrieval policies. It is unclear whether the proposed approach generalizes beyond PPR-based retrieval.

  4. Limited datasets. The evaluation only includes MuSiQue and 2WikiMultiHopQA, two traditional multi-hop QA benchmarks. More diverse datasets and reasoning tasks are needed to support the generality of the findings.

  5. Missing efficiency comparison. The proposed framework requires multiple LLM reasoning rounds, bridge-entity grounding, and repeated PPR retrieval. However, the paper does not provide a comprehensive comparison of actual LLM calls, token consumption, inference latency, and computational costs. The additional overhead should be justified against the performance improvements.

[1] Sun et al. Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph.

[2] Li et al. GraphReader: Building Graph-based Agent to Enhance Long-Context Abilities of Large Language Models.

[3] Luo et al. Graph-R1: Towards Agentic GraphRAG Framework via End-to-end Reinforcement Learning.

[4] Han et al. Reasoning by Exploration: A Unified Approach to Retrieval and Generation over Graphs.

Questions for authors

Please refer to the weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer bdAG (Part 1/2)

We thank the reviewer for engaging with our work and for acknowledging the improvements our method provides. We address the five weaknesses in order.


W1: Novelty and relation to agentic graph retrieval

Our related work discusses Think-on-Graph [1] and GraphReader [2] and states the difference. In these methods the LLM navigates the graph step by step, and it is called at every step. BRIDGE-Prop does not navigate the graph. It uses PPR to propagate over the graph nodes. Our contribution is to make untrained PPR work for multi-hop retrieval by improving its seeds and their weights (W3).

In this revision we add Think-on-Graph as a baseline on the same NER graph we use (W2). With the search width and depth of the original paper (both three), it needs 13 to 22 LLM calls per question, against about three for BRIDGE-Prop (W5), and its EM and R@5 are lower on both datasets.

Graph-R1 [3] and Reasoning by Exploration [4] are not cited in the paper, and we will add them. Both train the LLM with reinforcement learning. BRIDGE-Prop is training-free. These directions are complementary: the bridge entities that BRIDGE-Prop grounds could serve as an intermediate training signal for such learned policies, which we leave to future work.


W2: Baselines

We add two baselines. Both run on our NER graph with the same LLM.

Self-Ask (Press et al., 2023) is an iterative method based on question decomposition. The LLM breaks the question into follow-up questions, retrieves passages for each one, answers it, and then composes the final answer. Table 1 compares it with ITER-RETGEN and BRIDGE-Prop on all 1000 questions.

Table 1: Self-Ask on all 1000 questions

DatasetMethodEMF1R@5
MuSiQueSelf-Ask.307.399.413
ITER-RETGEN.352.454.616
BRIDGE-Prop.398.494.638
2WikiSelf-Ask.618.698.600
ITER-RETGEN.555.630.837
BRIDGE-Prop.649.721.896

On 2Wiki Self-Ask has a higher EM than ITER-RETGEN and a lower EM than BRIDGE-Prop (p=.029). Self-Ask writes an intermediate summary of the retrieved passages for each follow-up question. Its final answer reads the passages of the last round together with these intermediate summaries. This helps its EM and takes 6.6 to 6.9 LLM calls per question. The evidence of earlier rounds is kept in the summaries and not in the final five passages, which is why its R@5 is lower than both on both datasets.

In Think-on-Graph [1] the LLM navigates the graph step by step. It was designed for knowledge graphs with typed relations. We adapt it to our NER graph by treating the sentence in which two entities co-occur as the relation between them. It explores the graph with a limited search width and depth (both three, as in the original paper). At each step the LLM selects a few neighbouring entities to follow, so only a small part of the graph is visited. This takes 13 to 22 LLM calls per question and more tokens than any other method (37.6k against 8.5k for BRIDGE-Prop on HoVer, Table 5). Because of this cost we ran it on 200 questions per dataset. Its difference from the other methods is already clear on this subset.

Think-on-Graph returns only the passages on its reasoning paths, so we also report Think-on-Graph + fill, which fills the passages up to five with single-pass graph retrieval and answers with the same QA prompt as all other methods. The fill raises R@5 from .332 to .566 on MuSiQue and from .454 to .691 on 2Wiki. PPR retrieval on the same graph therefore provides useful evidence that is different from the passages on the reasoning paths.

Table 2: Think-on-Graph on 200 questions

MethodMuSiQue EMMuSiQue R@52Wiki EM2Wiki R@5
Think-on-Graph.205.332.390.454
Think-on-Graph + fill.335.566.435.691
ITER-RETGEN.385.590.545.851
BRIDGE-Prop.430.626.675.907

BRIDGE-Prop is above both Think-on-Graph variants on both datasets.

AuthorsOpenReview ↗

(Part 2/2)

W3: Applicability of PPR and generalization

PPR is a widely used graph ranking algorithm. It has been used for word sense disambiguation on WordNet (Agirre and Soroa, 2009), for subgraph retrieval in knowledge-graph question answering (Sun et al., 2018), and for passage retrieval in recent GraphRAG methods such as LinearRAG (Zhuang et al., 2026). It needs no training and only requires nodes and edges, so it applies to very different kinds of graphs. BRIDGE-Prop improves two inputs of PPR, the quality of the seeds and the weight of each seed. This finding is relevant to a wide range of existing systems, and our results add empirical evidence on how to steer untrained graph propagation. We have not tested retrieval mechanisms other than PPR, and we will acknowledge this in the revised Discussion. Given how many methods build on PPR, however, we believe this does not limit the scope of our findings.


W4: Datasets

The standard multi-hop benchmarks in this line of work are HotpotQA, 2WikiMultiHopQA and MuSiQue. HotpotQA's questions are only 2 hops deep though, which is why our paper covers the last two. For this revision, we add HoVer (Jiang et al., 2020). HoVer is built from HotpotQA: each claim is written from a HotpotQA question-answer pair, and it is then extended to three and four hops by replacing an entity with information from a further Wikipedia article. The task is to decide whether a claim is supported, and the evidence comes from up to four articles.

Table 3: HoVer (1000 samples)

MethodEMR@5
Single-pass graph retrieval.633.594
ITER-RETGEN.693.735
BRIDGE-Prop.725.758

On HoVer the answer is a label (supported or not supported), so EM is the accuracy of the predicted label. A closed-book LLM reaches .503. Both iterative methods are well above single-pass retrieval. BRIDGE-Prop is above ITER-RETGEN in both metrics. The EM difference is +.032 (p=.012) and the R@5 difference is +.024 (p=.019).


W5: Efficiency

We agree that this was missing. We will add Tables 4 and 5 to the revised paper. Table 4 gives the LLM calls per question for reasoning and for answering.

Table 4: LLM calls per question (reasoning and answering)

MethodMuSiQue2WikiHoVer
Single-pass graph retrieval111
Single-pass dense retrieval111
IRCoT2.72.83.4
ITER-RETGEN333
BRIDGE-Prop2.82.72.8
Self-Ask6.96.67.1
Think-on-Graph†13.121.617.8

† 200 questions per dataset. All other rows use 1000.

Single-pass retrieval makes no LLM call during retrieval and one call for the answer.

Tokens and latency. Table 5 gives the tokens that we logged on HoVer.

Table 5: Tokens per HoVer sample, in thousands

MethodSamplesInputOutputInput + output
Single-pass graph retrieval10001.00.31.3
Single-pass dense retrieval10001.10.31.4
IRCoT10008.31.39.6
ITER-RETGEN10006.81.28.0
BRIDGE-Prop10006.71.88.5
Self-Ask10005.10.75.8
Think-on-Graph20023.713.937.6

Think-on-Graph was run on 200 samples because of its cost. All numbers include the QA call that reads the five retrieved passages.

BRIDGE-Prop uses about as many tokens as ITER-RETGEN (8.5k against 8.0k per sample). We did not measure latency. All methods use the same LLM. All except Think-on-Graph also use the same retrieval backbone, so their cost differs mainly in calls and tokens.

Bridge prediction is built into the query-rewriting call and adds no separate call. BRIDGE-Prop also stops early when the LLM judges the evidence sufficient, so its number of calls stays close to that of ITER-RETGEN (see Table 4).


References

Agirre and Soroa. Personalizing PageRank for Word Sense Disambiguation. EACL 2009.

Jiang et al. HoVer: A Dataset for Many-Hop Fact Extraction And Claim Verification. Findings of EMNLP 2020.

Press et al. Measuring and Narrowing the Compositionality Gap in Language Models. Findings of EMNLP 2023.

Sun et al. Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text. EMNLP 2018.

Zhuang et al. LinearRAG: Linear Graph Retrieval Augmented Generation on Large-scale Corpora. ICLR 2026.

Thank you for the author’s response. I am curious as to why the authors chose "Self-Ask" as a baseline for performance evaluation, rather than other, more recent benchmark methods? I list a few baselines.

Thank you for the question. We chose the baselines to cover the main reasoning paradigms for multi-hop retrieval. Each is a well-established, training-free representative of its paradigm:

  • Interleaved chain-of-thought (IRCoT). Each reasoning step guides the next retrieval.
  • Generation-as-query (ITER-RETGEN). The model's hypothetical answer is appended to the question as the next query.
  • Question decomposition (Self-Ask, added in the revision). Each sub-question is answered by retrieval.
  • LLM-driven graph traversal (Think-on-Graph, added in the revision). The LLM chooses which neighbouring entities to follow.

All methods use the same LLM on the same graph as BRIDGE-Prop, so the comparison is controlled.

Think-on-Graph is the first method in your list [1] (Section 5.7, Appendix A.10), and GraphReader [2] belongs to the same paradigm. BRIDGE-Prop is more effective than Think-on-Graph at a much smaller LLM budget.

Graph-R1 [3] and Reasoning by Exploration [4] train the model with reinforcement learning. BRIDGE-Prop is training-free, and training these two methods is beyond our compute budget. We cite and discuss both in Related Work.

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

This paper studies iterative graph-based retrieval for multi-hop question answering. It observes that when an LLM reasons over retrieved passages, it often names the intermediate "bridge" entities, but these entities are rarely used to steer the subsequent graph retrieval. BRIDGE-Prop asks the LLM in each round to predict bridge entities, grounds them to graph nodes, keeps them in a cumulative memory, and uses them as additional seeds for Personalized PageRank, weighted by node degree. Rankings from all rounds are then fused. On MuSiQue and 2WikiMultiHopQA, with two types of graphs, the method improves retrieval recall and answer accuracy over iterative baselines in its main setting, especially on questions that need deeper or parallel reasoning.

Critical strengths
  1. The paper addresses an interesting and clearly stated problem: reasoning-guided graph retrieval often identifies the right bridge entities in text but does not turn them into retrieval seeds. Figure 1 illustrates this gap, and the authors show good familiarity with the field.
  2. The main comparison is well controlled. BRIDGE-Prop and ITER-RETGEN share the same corpus, graph, encoder, LLM, retrieval budget and maximum number of rounds. The retrieval gains hold on both graph types and also with a second LLM, and they are supported by paired significance tests.
  3. The analysis is informative. The breakdowns by reasoning depth and question type show the largest gains where the method is expected to help, and the failure analysis and the bridge-memory reuse experiments add useful insight.
Critical weaknesses
  1. The evaluation scope is narrow. The method is evaluated on only two multi-hop benchmarks, MuSiQue and 2WikiMultiHopQA. Other multi-hop benchmarks and single-hop QA benchmarks are not included, so it is unclear how well the method generalizes beyond these two datasets.
  2. The set of baselines is small. Besides single-pass retrieval and a closed-book LLM, only two iterative methods are compared, and the "strongest iterative baseline" is the stronger of these two. The methods discussed in the related work that let the LLM navigate the graph step by step are not included in the comparison.
  3. The diagnostic metrics in Figure 1 partly favor the proposed method. "Seeded" and "seed mass" directly measure what BRIDGE-Prop does by design, so they show that the mechanism works as intended rather than that retrieval improves. Another method may reach the needed evidence without seeding the bridge entity itself. On the more neutral "mentioned" metric, BRIDGE-Prop is only slightly higher than ITER-RETGEN on 2WikiMultiHopQA and clearly lower on MuSiQue. In addition, beyond the brief definitions in the Figure 1 caption, the paper does not describe how the gold bridge entities are obtained or how a bridge is judged to be "mentioned".
  4. Each round requires an LLM call to predict bridges, followed by graph retrieval. Apart from the cap on the number of reasoning rounds, the paper does not report the computational cost, such as the average number of LLM calls, tokens or latency, compared with the single-pass and iterative baselines.
Questions for authors
  1. How are the gold bridge entities obtained, and how is it decided whether a gold bridge is "mentioned" in the reasoning or "seeded" (for example, by exact string matching)?
  2. Could the authors report the cost of BRIDGE-Prop, such as LLM calls, tokens and latency, compared with the single-pass and iterative baselines?
  3. How does BRIDGE-Prop perform against additional baselines, such as the methods discussed in the related work that let the LLM navigate the graph step by step, and on other multi-hop or single-hop benchmarks?
5 comments
AuthorsOpenReview ↗

Response to Reviewer ip7p (Part 1/2)

We thank the reviewer for the careful and constructive review. We are glad that the reviewer finds the problem clearly stated, the main comparison well controlled, and the analyses informative. We answer the three questions in order. Each answer also covers the related weakness.


W3 / Q1: How the Figure 1 metrics are computed

Gold bridges. They come from the annotations that ship with each dataset. We do not label them ourselves. MuSiQue provides a decomposition of each question into steps, and we take the answers of the intermediate steps. 2Wiki provides evidence triples, and we take the entity that is the object of one triple and the subject of the next. We exclude the final answer and entities that already appear in the question.

Mentioned. The bridge string occurs in the text that the method generates, after lower-casing and removing punctuation. For ITER-RETGEN we match against its generated text. For BRIDGE-Prop we match against its rewritten queries and its predicted bridge entities. Its reasoning text is not counted, because it is not passed to retrieval.

Seeded. In both methods the query is encoded by the dense encoder and matched to graph nodes, and the matched nodes become seeds. A gold bridge counts as seeded if its node receives a non-zero seed weight.

Similarity matching does not guarantee that the structurally important entities are selected. Ordinary iterative methods encode the whole generated text and match it to graph nodes by similarity. A bridge entity is a small part of this text and competes with the rest of it, so it can be diluted or missed. This loss is what we call the grounding gap, and the measurements in Figure 1 show where it occurs. We agree that BRIDGE-Prop is lower on mentioned on MuSiQue. MuSiQue questions are harder. The LLM often names a gold bridge in its reasoning there but does not select it as a bridge entity. Such a bridge is not counted as mentioned. The two methods differ in what happens next. Most bridges that BRIDGE-Prop predicts become seeds. For ITER-RETGEN, many of the gold bridges are lost when its generated text is matched to graph nodes by similarity. This is why BRIDGE-Prop retrieves more evidence on MuSiQue although it mentions fewer bridges there. We also agree that BRIDGE-Prop scores high on seeded and seed mass by design. These two metrics confirm that the mechanism works as intended. They are not evidence that retrieval improves. That evidence is R@5 and the ablation without bridge seeds.

We will add these definitions to the appendix.


W4 / Q2: Cost

We agree that this was missing. We will add Tables 1 and 2 to the revised paper. Table 1 gives the LLM calls per question for reasoning and for answering.

Table 1: LLM calls per question (reasoning and answering)

MethodMuSiQue2WikiHoVer
Single-pass graph retrieval111
Single-pass dense retrieval111
IRCoT2.72.83.4
ITER-RETGEN333
BRIDGE-Prop2.82.72.8
Self-Ask6.96.67.1
Think-on-Graph†13.121.617.8

† 200 questions per dataset. All other rows use 1000.

Single-pass retrieval makes no LLM call during retrieval and one call for the answer. In reasoning and answering calls BRIDGE-Prop is close to ITER-RETGEN.

Tokens and latency. Table 2 gives the tokens that we logged on HoVer.

Table 2: Tokens per HoVer sample, in thousands

MethodSamplesInputOutputInput + output
Single-pass graph retrieval10001.00.31.3
Single-pass dense retrieval10001.10.31.4
IRCoT10008.31.39.6
ITER-RETGEN10006.81.28.0
BRIDGE-Prop10006.71.88.5
Self-Ask10005.10.75.8
Think-on-Graph20023.713.937.6

Think-on-Graph was run on 200 samples because of its cost. All numbers include the QA call that reads the five retrieved passages.

BRIDGE-Prop uses about as many tokens as ITER-RETGEN (8.5k against 8.0k per sample). We did not measure latency. All methods use the same LLM. All except Think-on-Graph also use the same retrieval backbone, so their cost differs mainly in calls and tokens.

AuthorsOpenReview ↗

(Part 2/2)

W1, W2 / Q3: Additional baselines and benchmarks

Baselines. We add two baselines. Both run on our NER graph with the same LLM.

Self-Ask (Press et al., 2023) is an iterative method based on question decomposition. The LLM breaks the question into follow-up questions, retrieves passages for each one, answers it, and then composes the final answer. Table 3 compares it with ITER-RETGEN and BRIDGE-Prop on all 1000 questions.

Table 3: Self-Ask on all 1000 questions

DatasetMethodEMF1R@5
MuSiQueSelf-Ask.307.399.413
ITER-RETGEN.352.454.616
BRIDGE-Prop.398.494.638
2WikiSelf-Ask.618.698.600
ITER-RETGEN.555.630.837
BRIDGE-Prop.649.721.896

On 2Wiki Self-Ask has a higher EM than ITER-RETGEN and a lower EM than BRIDGE-Prop (p=.029). Self-Ask writes an intermediate summary of the retrieved passages for each follow-up question. Its final answer reads the passages of the last round together with these intermediate summaries. This helps its EM and takes 6.6 to 6.9 LLM calls per question. The evidence of earlier rounds is kept in the summaries and not in the final five passages, which is why its R@5 is lower than both on both datasets.

In Think-on-Graph (Sun et al., 2024) the LLM navigates the graph step by step. It was designed for knowledge graphs with typed relations. We adapt it to our NER graph by treating the sentence in which two entities co-occur as the relation between them. It explores the graph with a limited search width and depth (both three, as in the original paper). At each step the LLM selects a few neighbouring entities to follow, so only a small part of the graph is visited. This takes 13 to 22 LLM calls per question and more tokens than any other method (37.6k against 8.5k for BRIDGE-Prop on HoVer, Table 2). Because of this cost we ran it on 200 questions per dataset. Its difference from the other methods is already clear on this subset.

Think-on-Graph returns only the passages on its reasoning paths, so we also report Think-on-Graph + fill, which fills the passages up to five with single-pass graph retrieval and answers with the same QA prompt as all other methods. The fill raises R@5 from .332 to .566 on MuSiQue and from .454 to .691 on 2Wiki. PPR retrieval on the same graph therefore provides useful evidence that is different from the passages on the reasoning paths.

Table 4: Think-on-Graph on 200 questions

MethodMuSiQue EMMuSiQue R@52Wiki EM2Wiki R@5
Think-on-Graph.205.332.390.454
Think-on-Graph + fill.335.566.435.691
ITER-RETGEN.385.590.545.851
BRIDGE-Prop.430.626.675.907

BRIDGE-Prop is above both Think-on-Graph variants on both datasets.

Benchmarks. Single-hop benchmarks pair each question with one passage or fact that contains the answer, so they measure retrieval and reading comprehension instead of multi-hop reasoning. Since our work is explicitly about multi-hop reasoning, we do not evaluate it on single-hop benchmarks. The standard multi-hop benchmarks in this line of work are HotpotQA, 2WikiMultiHopQA and MuSiQue. HotpotQA's questions are only 2 hops deep though, which is why our paper covers the last two. For this revision, we add HoVer (Jiang et al., 2020). HoVer is built from HotpotQA: each claim is written from a HotpotQA question-answer pair, and it is then extended to three and four hops by replacing an entity with information from a further Wikipedia article. The task is to decide whether a claim is supported, and the evidence comes from up to four articles.

Table 5: HoVer (1000 samples)

MethodEMR@5
Single-pass graph retrieval.633.594
ITER-RETGEN.693.735
BRIDGE-Prop.725.758

On HoVer the answer is a label (supported or not supported), so EM is the accuracy of the predicted label. A closed-book LLM reaches .503. Both iterative methods are well above single-pass retrieval. BRIDGE-Prop is above ITER-RETGEN in both metrics. The EM difference is +.032 (p=.012) and the R@5 difference is +.024 (p=.019).


References

Jiang et al. HoVer: A Dataset for Many-Hop Fact Extraction And Claim Verification. Findings of EMNLP 2020.

Press et al. Measuring and Narrowing the Compositionality Gap in Language Models. Findings of EMNLP 2023.

Sun et al. Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph. ICLR 2024.

Thank you for the response and the additional experiments.

  1. The definitions clarify how the Figure 1 metrics are computed. I also appreciate the acknowledgment that "seeded" and "seed mass" are high by design and are not evidence of improved retrieval.
  2. The added cost analysis addresses my question.
  3. The additional experiments address my concerns about the baselines and the evaluation scope.

Considering the overall quality and novelty of the paper, I keep my original rating.

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

The paper proposes BRIDGE-Prop, a training-free iterative GraphRAG method built on HippoRAG 2’s Personalized PageRank (PPR) retrieval. In each round, an LLM predicts the “bridge” entities still missing from the retrieved evidence. These entities are grounded to graph nodes, accumulated across rounds, and added as PPR seeds with a degree-adaptive weight. The per-round rankings are then fused with weighted RRF. On 1,000 questions each from MuSiQue and 2WikiMultiHopQA, BRIDGE-Prop outperforms ITER-RETGEN; for example, on 2Wiki with the OpenIE graph, R@5 rises from .889 to .962.

Critical strengths

The paper clearly identifies a “grounding gap”: ITER-RETGEN mentions gold bridge entities in its reasoning but rarely seeds them into the graph (Figure 1). Its analyses (ablations, breakdown by hop count and question type, recovery from failed round-0 retrieval) support the claim that bridge seeding drives the gains on 2WikiMultiHopQA.

Critical weaknesses
  1. Limited novelty and missing related work: The method combines existing components: ITER-RETGEN-style query rewriting, HippoRAG 2 PPR, extra seed nodes, a log-degree weighting heuristic, and RRF. It also addresses the same problem as RSF-GLLM (Bandyopadhyay & Muppidi, ICML 2026), which targets the semantic gap at intermediate bridge nodes in multi-hop KG QA. RSF-GLLM should be cited, discussed and compared against.

  2. Limited baselines and inconsistent gains: Table 2 includes only IRCoT, ITER-RETGEN and single-pass graph retrieval. It has no standard single-pass dense RAG baseline, and no other GraphRAG or reasoning-on-graph method. The paper discusses ToG and GraphReader but does not compare against them.

  3. The gains are also not consistent: On MuSiQue, the improvements are small, for example +.022 R@5 on the NER graph (p = .045) and +.004 on 2-hop OpenIE questions. With Llama-3.3-70B (Table 11), BRIDGE-Prop is worse than ITER-RETGEN on MuSiQue EM (−.020) and F1 (−.015), and its R@5 gain is only +.018.

4 Cost: The paper does not report the number of LLM calls, tokens or latency per question. This matters because each question can require up to three bridge-prediction calls plus the QA call.

Questions for authors
  1. How does BRIDGE-Prop differ from RSF-GLLM, and how does it compare empirically?
  2. How many LLM calls (and tokens) are needed per question, compared with ITER-RETGEN and IRCoT?
  3. Can you add a standard single-pass dense RAG baseline and at least one other iterative GraphRAG baseline (e.g., ToG or GraphReader)?
  4. Why does BRIDGE-Prop underperform ITER-RETGEN on MuSiQue EM and F1 with Llama-3.3-70B, despite better R@5?
5 comments
AuthorsOpenReview ↗

Response to Reviewer BAgD (Part 1/3)

We are happy to hear the grounding gap our work addresses is clearly identified and we thank the reviewer for the careful reading and important questions. We answer the four questions in order. Each answer also covers the related weakness.


W1 / Q1: Difference from RSF-GLLM, and novelty

We were not aware of the very recent RSF-GLLM work at submission. We will cite and discuss it in the revision of our paper. It indeed starts from the same observation as our work: semantic relevance does not guarantee structural reachability, most visibly at bridge nodes. The work clearly differs from ours though, in both approach and in setting.

Approach. RSF-GLLM is trained in two stages. It first trains a graph propagation module (RSF) with the gold answer as supervision, and then fully fine-tunes an LLM to generate the answer from the retrieved paths. It makes no LLM calls during retrieval. BRIDGE-Prop is training-free and uses the LLM inside retrieval. In each round one LLM call rewrites the query and names the bridge entities found in the retrieved passages, and we use them as seeds for graph propagation (PPR). Bridge prediction adds no separate call.

Setting and comparability. RSF-GLLM is evaluated on Freebase subgraphs in WebQSP and CWQ, where entities are connected by predefined relation types. Its propagation explicitly uses relation embeddings and query-conditioned relation attention to weight graph transitions (Eqs. 2–4). Our graphs are built from text that includes distractor passages. They are noisy, and their edges have no fixed set of relation types. RSF-GLLM's propagation relies on such relation types, and its experiments do not cover graphs of this kind. Conversely, our bridge prediction reads retrieved passages, which their KGQA setup does not provide. A direct comparison therefore requires adaptations to the input representation and retrieval pipeline, rather than simply running the two methods on the same questions.

What we find. BRIDGE-Prop avoids step-by-step LLM graph traversal. Its contribution is to make untrained PPR work for multi-hop retrieval by improving the seeds and their weights. Besides IRCoT and ITER-RETGEN, we now compare with Self-Ask and with Think-on-Graph (Sun et al., 2024), a training-free agentic method. BRIDGE-Prop reaches the highest EM and R@5 among these methods on both datasets (Q3), with about three LLM calls per question against 13 to 22 for Think-on-Graph (Q2). On our graphs, it is therefore more efficient than this LLM-guided graph traversal.


W4 / Q2: LLM calls and tokens per question

We agree that this was missing. We will add Tables 1 and 2 to the revised paper. Table 1 gives the LLM calls per question for reasoning and for answering.

Table 1: LLM calls per question (reasoning and answering)

MethodMuSiQue2WikiHoVer
Single-pass graph retrieval111
Single-pass dense retrieval111
IRCoT2.72.83.4
ITER-RETGEN333
BRIDGE-Prop2.82.72.8
Self-Ask6.96.67.1
Think-on-Graph†13.121.617.8

† 200 questions per dataset. All other rows use 1000.

BRIDGE-Prop makes one reasoning call per round and one answer call. It stops when the LLM judges the evidence sufficient. ITER-RETGEN always makes three calls. Single-pass retrieval makes no LLM call during retrieval and one call for the answer. In reasoning and answering calls BRIDGE-Prop is close to ITER-RETGEN. Think-on-Graph uses several times more calls than the other methods.

HoVer (Jiang et al., 2020) is a third dataset that we add in this revision. We describe it in Q4.

Tokens and latency. Table 2 gives the tokens that we logged on HoVer.

Table 2: Tokens per HoVer sample, in thousands

MethodSamplesInputOutputInput + output
Single-pass graph retrieval10001.00.31.3
Single-pass dense retrieval10001.10.31.4
IRCoT10008.31.39.6
ITER-RETGEN10006.81.28.0
BRIDGE-Prop10006.71.88.5
Self-Ask10005.10.75.8
Think-on-Graph20023.713.937.6

Think-on-Graph was run on 200 samples because of its cost. All numbers include the QA call that reads the five retrieved passages.

BRIDGE-Prop uses about as many tokens as ITER-RETGEN (8.5k against 8.0k per sample). We did not measure latency. All methods use the same LLM. All except Think-on-Graph also use the same retrieval backbone, so their cost differs mainly in calls and tokens.

AuthorsOpenReview ↗

(Part 2/3)

W2 / Q3: Additional baselines

Single-pass dense RAG. We followed the reviewer's suggestion and added a single-pass dense RAG baseline. It retrieves the top five passages by embedding similarity in a single step, without a graph and without iteration. It uses all-MiniLM-L6-v2, the same encoder as all other methods in the paper. It reaches EM .245 / F1 .333 / R@5 .457 on MuSiQue and .387 / .420 / .598 on 2Wiki. ITER-RETGEN and BRIDGE-Prop are above it on all three metrics on both datasets. We will add this row to the main results table (Table 2 of the paper) in the revised paper.

Other iterative methods. We add two baselines, Self-Ask (Press et al., 2023) and Think-on-Graph (Sun et al., 2024). Both run on our NER graph with the same LLM.

Self-Ask is an iterative method based on question decomposition. The LLM breaks the question into follow-up questions, retrieves passages for each one, answers it, and then composes the final answer. Table 3 compares it with ITER-RETGEN and BRIDGE-Prop on all 1000 questions.

Table 3: Self-Ask on all 1000 questions

DatasetMethodEMF1R@5
MuSiQueSelf-Ask.307.399.413
ITER-RETGEN.352.454.616
BRIDGE-Prop.398.494.638
2WikiSelf-Ask.618.698.600
ITER-RETGEN.555.630.837
BRIDGE-Prop.649.721.896

On 2Wiki Self-Ask has a higher EM than ITER-RETGEN and a lower EM than BRIDGE-Prop (p=.029). Self-Ask writes an intermediate summary of the retrieved passages for each follow-up question. Its final answer reads the passages of the last round together with these intermediate summaries. This helps its EM and takes 6.6 to 6.9 LLM calls per question. The evidence of earlier rounds is kept in the summaries and not in the final five passages, which is why its R@5 is lower than both on both datasets.

Think-on-Graph was run on 200 questions per dataset, because its cost is high and the gap is large. Think-on-Graph was designed for curated knowledge graphs with typed relations. We adapt it to our NER graph by treating the sentence in which two entities co-occur as the relation between them.

Think-on-Graph returns only the passages on its reasoning paths. These passages are precise (about 60% are gold) but few: 1.3 per question on MuSiQue and 1.8 on 2Wiki. The reason is that its search often ends early. Think-on-Graph keeps at most three paths and stops as soon as it judges the evidence sufficient. To compare under the same conditions, we also report Think-on-Graph + fill. It uses the same Think-on-Graph run and fills the passages up to five with single-pass graph retrieval.

Table 4: Think-on-Graph on 200 questions

MethodMuSiQue EMMuSiQue R@52Wiki EM2Wiki R@5
Think-on-Graph.205.332.390.454
Think-on-Graph + fill.335.566.435.691
ITER-RETGEN.385.590.545.851
BRIDGE-Prop.430.626.675.907

On the same 200 MuSiQue questions, Think-on-Graph + fill is above Think-on-Graph alone (EM .335 against .205) and above single-pass graph retrieval alone (.335 against .265). The LLM-guided traversal and PPR retrieval therefore provide complementary evidence. Think-on-Graph + fill remains below BRIDGE-Prop on both datasets (EM and R@5, all p≤.017). When an LLM explores a graph step by step, its cost grows quickly with both the search width and the search depth, so both should be kept small. The search can be harder on a noisy text-derived graph, where each node has many candidate neighbours.

AuthorsOpenReview ↗

(Part 3/3)

W3 / Q4: Inconsistent gains, and EM with Llama-3.3-70B on MuSiQue

Consistency of the gains. BRIDGE-Prop explores the intermediate entities of a question and retrieves the evidence around them, and its gain in recall is consistent. Its R@5 is above that of ITER-RETGEN in every setting of the paper, on both datasets, on both graphs and with both LLMs. We agree that the size of the gains is not uniform. The gains are larger on 2Wiki than on MuSiQue. The gain is small on two-hop questions, where ITER-RETGEN already retrieves most of the evidence (Table 3 of the paper). Two-hop questions are 52% of our MuSiQue sample, which is the same for both LLMs, so this lowers the average gain on MuSiQue.

In this revision we add a third dataset, HoVer (Jiang et al., 2020), with claims that need two to four hops of evidence. It shows the same pattern by reasoning depth.

Table 5: HoVer by reasoning depth (1000 samples)

MethodEM 2-hop (n=281)EM 3-hop (n=459)EM 4-hop (n=260)R@5 2-hop (n=281)R@5 3-hop (n=459)R@5 4-hop (n=260)
Single-pass graph retrieval.705.643.538.781.572.431
ITER-RETGEN.783.697.588.875.721.606
BRIDGE-Prop.786.741.631.884.757.625
Δ+.004+.044+.042+.009+.036+.019

Δ is BRIDGE-Prop minus ITER-RETGEN. On HoVer the answer is a label, so EM is the accuracy of the predicted label.

On HoVer BRIDGE-Prop is close to ITER-RETGEN on two-hop claims, and its gain is larger on three-hop and four-hop claims (EM +.004, +.044 and +.042).

With Llama-3.3-70B on MuSiQue, BRIDGE-Prop improves R@5 by +.018 (p<.05), but EM does not improve (−.020, not significant). We looked into this case in more detail. MuSiQue is a hard dataset. Most of its questions are sequential chains, and the answer is in the passage of the last hop. R@5 counts every gold passage equally, so it can rise even when this passage is not retrieved. This is what we see in this setting (Table 11 of the paper). BRIDGE-Prop retrieves more passages of the intermediate hops than ITER-RETGEN, but it retrieves the last-hop passage less often (63.9% of questions against 67.7%, p=.006). When both methods retrieve the same gold passages, their EM is about the same (difference −.010, p=.45). In the other three settings in the paper on the NER graph (qwen-plus on MuSiQue, and both LLMs on 2Wiki), the last-hop recall of BRIDGE-Prop is not significantly lower.


References

Jiang et al. HoVer: A Dataset for Many-Hop Fact Extraction And Claim Verification. Findings of EMNLP 2020.

Press et al. Measuring and Narrowing the Compositionality Gap in Language Models. Findings of EMNLP 2023.

Sun et al. Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph. ICLR 2024.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revision uploaded

We have uploaded a revised version of the paper. It includes all the changes we promised in our responses to the three reviewers.

  • Two new baselines, Self-Ask and Think-on-Graph, and a single-pass dense retrieval row. [BAgD: W2, Q3; ip7p: W2, Q3; bdAG: W2] > Section 4, Table 2, Sections 5.1 and 5.7, Appendix A.10
  • Cost analysis with LLM calls and tokens per question. [BAgD: W4, Q2; ip7p: W4, Q2; bdAG: W5] > Section 5.7, Appendix A.9
  • A third dataset, HoVer. [BAgD: W3, Q4; ip7p: W1, Q3; bdAG: W4] > Section 4, Appendix A.11
  • Relation to RSF-GLLM and to LLM-guided graph navigation, and the role of PPR. [BAgD: W1, Q1; bdAG: W1, W3] > Sections 1, 2 and 6
  • Definition of the Figure 1 metrics. [ip7p: W3, Q1] > Figure 1 caption, Appendix A.5

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.