acceptodds
Under review as a conference paper at ICLR 2027

BubbleRAG: One Question, Many Possible Paths to Evidence in Knowledge Graphs

Abstract

Graph-based retrieval-augmented generation supports knowledge-intensive question answering by connecting evidence across documents. Retrieving useful evidence, however, requires determining how query concepts are represented in the graph and how their supporting facts are connected. A query concept may match multiple nodes or edges, and the usefulness of each match can depend on its connections to other supporting facts. Pruning these alternatives too early may exclude useful evidence, while exploring all of them extensively can be costly. Moreover, relevant evidence may follow different structural patterns, making the resulting candidates difficult to compare. These issues create three challenges: preserving plausible concept matches, exploring diverse connections, and comparing candidates with different evidence structures. To address these challenges, we propose BubbleRAG, a training-free retrieval framework. BubbleRAG first extracts query concepts and retrieves candidate nodes or edges for each concept. It then constructs connected candidate subgraphs to assess these matches together with their connections, and ranks the subgraphs by query-concept coverage and semantic relevance. The top-ranked subgraphs provide starting points for LLM-guided exploration to retrieve additional facts needed for answering. Experiments on HotpotQA, MuSiQue, and 2WikiMultiHopQA show that BubbleRAG achieves the best average F1 and LLM-judged accuracy among the evaluated baselines with both 8B and 30B backbones, with the largest F1 gain reaching 7.99 points on MuSiQue.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Large Language Models, Retrieval-Augmented Generation, Knowledge Graphs

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Zr5UOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes BubbleRAG, a training-free GraphRAG framework for multi-hop question answering. Prior to resolving queries, the corpus is segmented to chunks for triple extraction with an LLM, which the triples form a KG. Given a query, Semantic Anchoring Grouping first retrieves relevant text chunks as contextual clues, using them to answer questions if they are sufficient or to guide the LLM to refine query concepts via anchor specialization and schema relaxation. These refined phrases are then used to retrieve candidate nodes and edges within the KG, which the LLM further cluster them into weighted semantic anchor groups. Since finding an optimal informative (minimal sufficient) subgraph that covers all semantic anchor groups remains NP-hard, BubbleRAG adopts an alternative approach to find discover candidate evidence graphs, which contain two phases: CEG discovery and CEG ranking. The CEG discovery stage is implemented via bubble expansion, which starts from each anchor and gradually explores nearby nodes, visiting the most query-relevant ones first. When searches from different anchors meet, their paths are combined into a small connected subgraph that links the key concepts in the query. The CEG ranking phase scores the quality of each subgraph, and prioritize those that are close to the original query and miss less important concepts. The top-ranked CEGs will be provided to the LLM for answer generation. BubbleRAG, as well as GraphRAG baselines, are evaluated on the three widely adopted benchmarks, HotpotQA, MuSiQue, and 2wiki.

Critical strengths
  1. The paper contains a detailed related work section, which summarizes the pros and cons of different types of GraphRAG methods in detail.

  2. Different from linking to isolated entities, BubbleRAG explores and prunes evidence at the subgraph level, yielding evidence with global coverage of the query’s relevant concepts and logical relationships.

  3. The proposed evidence subgraph retrieval method (w/ CEG discovery and CEG ranking steps) is able to bypass the need of resolving the NP-hard graph-join problem that requires minimal-sufficiency.

Critical weaknesses
  1. The manuscript contains many technical terms that readers from other domains cannot easily understand. The relationships between different terms, namely “semantic anchor group”, “alternative concept match”, “candidate evidence graph” and “optimal informative subgraph retrieval” are less intuitive. It is hard for readers to understand that the purpose of optimal informative subgraph retrieval is to combine different semantic anchor groups with a minimal-sufficient subgraph within the KG. This reviewer suggests the authors refrain from the excessive use of technical terms without establishing the necessary connections between them.

  2. The proposed method is not compared with the latest GraphRAG solutions, namely GFM-RAG [1] and G-Reasoner [2].

  3. The experimental section lacks a detailed analysis of the performance improvements. Section 4.2 merely restates results that can be read directly from Table 1. It would be more informative to explain in depth why BubbleRAG outperforms the baselines.

[1] Luo et al., GFM-RAG: Graph Foundation Model for Retrieval Augmented Generation (Neurips 2025)

[2] Luo et al., G-reasoner: Foundation Models for Unified Reasoning over Graph-structured Knowledge (ICLR 2026)

Questions for authors
  1. What if there are no direct connections between different semantic anchor groups, in this case, how can they be connected into a candidate evidence graph?

  2. Given that questions in HotpotQA, MuSique, and 2Wiki datasets are constructed based on 1 single path only. It is possible that some of the questions may have multiple solution paths, but whether it is necessary to consider all of them remains questionable.

3 comments
AuthorsOpenReview ↗

Rebuttal by Authors (1/2)

We thank the reviewer for the careful reading and constructive feedback. Below, we address each concern and explain the corresponding clarifications and revisions.


W1. Excessive technical terminology and unclear connections between concepts.

Thank you for pointing this out. We agree that we introduced too many technical terms before explaining the overall idea, without clearly showing how these concepts are connected. This made the paper harder to follow. We used these terms to describe the roles of different stages in our method, but our explanation was not clear enough.

To address this issue, we have revised our paper to simplify the explanation and add the necessary introduction at the beginning of the method section. We now first explain how BubbleRAG finds candidate entities for the concepts in a question, connects them into subgraphs, selects useful subgraphs, and then adds further facts needed to answer the question, before introducing the corresponding technical terms. We have also improved the transitions between stages to explain why each next step is needed and how it uses the results of the previous step. These changes help readers understand the overall idea before going into the details.


W2. Missing comparisons with GFM-RAG and G-Reasoner.

Thank you for drawing our attention to GFM-RAG and G-Reasoner. Both are closely related to our work. However, our experiments mainly compare methods that use off-the-shelf models without additional training of retrieval or reasoning components. GFM-RAG and G-Reasoner introduce trained components for graph retrieval or reasoning, while BubbleRAG focuses on handling uncertainty in concept matching and evidence connection at query time, without training additional components. We therefore limit our experimental comparisons to training-free methods to reduce the influence of additional training data and supervision. We agree that both works are important for understanding recent progress in GraphRAG. We have added a discussion of these methods in Related Work.

We have also added experiments with two recent training-free GraphRAG methods, QAFD-RAG and LinearRAG. The results with the 30B model are shown below:

Method2Wiki F1HotpotQA F1
QAFD-RAG69.5771.39
LinearRAG65.0266.84
BubbleRAG72.5474.35

W3. Insufficient analysis of why BubbleRAG improves over the baselines.

Thank you for your suggestion. We have added a more detailed analysis of BubbleRAG’s gains in Section 4.2. Using the original run logs of BubbleRAG and HippoRAG2 with the 30B model, we compared their retrieval results and answers question by question. We explain the gains from two aspects. First, BubbleRAG selects candidate entities together with their connections, allowing evidence that ranks lower but is important for answering the question to be selected. Second, RAE uses the question to guide further retrieval of specific information, helping the model find the relations, attributes, and dates needed to answer it.

On 2Wiki, BubbleRAG’s gains mainly come from questions where HippoRAG2 did not rank key supporting documents in its top 15 results. Some supporting documents for these questions were ranked between 16 and 200 by HippoRAG2. BubbleRAG’s subgraph ranking allows these documents to be selected based on their connections to other concepts in the question. The case study in the appendix shows this difference: by connecting a film to its director, BubbleRAG selected a subgraph containing the director’s biography and included this answer-bearing biography in the context for answering the question. HippoRAG2 ranked the same biography only 65th.

On MuSiQue, about 57% of the net F1 gain also comes from questions where HippoRAG2’s top 15 results did not cover all annotated supporting document titles. The remaining gain comes from questions where all supporting document titles were already covered. After examining the answers and saved traces, we found that even when relevant documents were retrieved, the answers could still mix up attributes of different entities or facts from different time periods. RAE continues retrieval based on the question. For example, after finding a relevant person, it searches for the specific family relationship or dates of holding office asked about in the question, providing more targeted evidence for the final answer.

AuthorsOpenReview ↗

Rebuttal by Authors (2/2)

Q1. Connecting semantic anchor groups when no direct connections exist.

Thank you for raising this point. In BubbleRAG, we consider two cases where semantic anchor groups cannot be connected.

In the first case, some groups cannot be connected to each other, but useful connections can still be found within individual groups or between some groups. This often occurs in comparison or aggregation questions, where the required evidence may lie in separate subgraphs. For example, to compare which of two directors was born earlier, we can form a subgraph containing birth information for each director without connecting the two subgraphs. BubbleRAG keeps these locally connected subgraphs, ranks them, and selects multiple subgraphs up to the specified limit. These are then passed to RAE for further retrieval, as shown in Figure 3 of the main paper.

In the second case, the search cannot form any useful connected subgraph: both within-group and between-group connections fail. Among queries that entered graph retrieval, this occurs in only 6.18% and 5.11% of questions on 2Wiki and HotpotQA, respectively. Algorithm 1 handles this case by keeping the initial anchors and allowing RAE to continue retrieval from them. This prevents the process from stopping when no connected subgraph can be formed.


Q2. The necessity of considering multiple paths when a single evidence path is annotated.

Thank you for this important question. We chose these datasets because they are widely used benchmarks in GraphRAG, making it easier to compare with existing methods. Although these datasets usually provide one annotated evidence path supporting the answer, the KGs we search are extracted from text by an LLM. The same entity may appear under different names, and the same relation may be expressed in different ways. Therefore, finding a clearly defined annotated path in the actual KG may still require exploring different entity matches and connections.

For example, consider the question: “What state was the dissenter in Kessler v. Treat from?” We would expect to start from the matched judge, Justice John Marshall Harlan, and find his home state. However, in the saved candidate graph, this node was only connected to a legal opinion in another case and did not lead to the answer. BubbleRAG instead started from another candidate, the case Kessler v. Treat, and followed a relation identifying the dissenting judge to find John Marshall Harlan. It then obtained the answer, Kentucky, from his linked biography.

Here, Justice John Marshall Harlan and John Marshall Harlan are the same person, but the KG stores them as two disconnected nodes. The latter was not among the initial anchors. It was found during the connection search and included in the top-ranked subgraph. Thus, even after matching the correct person, the method may still need to start from another entity to find the evidence corresponding to the annotated path.

The KG analysis in the appendix further shows the variety of relation expressions. The KGs for 2Wiki, HotpotQA, and MuSiQue contain about 76,900, 150,800, and 157,800 triples, respectively, but have about 14,600, 36,500, and 45,000 distinct relation expressions. About 70% of these expressions appear only once. BubbleRAG keeps multiple candidate matches and connection options to handle these uncertainties during retrieval and avoid ruling out the correct evidence too early.

Reviewer_Zr5UOpenReview ↗

Reply to the rebuttal.

First, I shall apologize for mistakenly copying the weaknesses into the strengths block. I used a Word document to write my initial drafts for my reviews, and the strengths and weaknesses sections look similar.

Thank you for your efforts in improving the manuscript and addressing my questions. Now, this reviewer believes that the strengths weight higher than weaknesses, and adjusted the overall scoring.

Nevertheless, this reviewer remains unconvinced that a paper proposing a pipeline RAG system for question answering offers sufficient novelty for acceptance at a top conference, particularly in light of recent trainable RAG systems (e.g. G-Reasoner, GFM-RAG) that achieve better performance without relying on larger-scale models. In addition, the evaluation lacks experiments on real-world questions with multiple explicitly valid evidence paths.

Regarding these issues, this reviewer would like to defer the decision to the AC/PC.

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

This paper introduces BubbleRAG, a training-free graph-based retrieval-augmented generation (GraphRAG) framework. It addresses several limitations in existing GraphRAG methods for multi-hop question answering, specifically the tendencies to prematurely exclude relevant entities, overlook valid reasoning paths, and struggle with comparing different evidence structures. Concretely, BubbleRAG begins by using "Semantic Anchor Grouping" to retain multiple candidate entities or relations for each concept present in a query. It then employs "Bubble Expansion" to explore the knowledge graph and construct interconnected subgraphs of candidate evidence. These subgraphs are subsequently ranked based on their semantic relevance and the extent to which they cover the concepts in the query. Finally, the framework utilizes "LLM-guided Reasoning-Aware Expansion" to supplement any missing evidence and generate the final answer. Furthermore, the authors formalize the selection of evidence subgraphs as an "Optimal Informative Subgraph Retrieval" (OISR) problem and prove that it is both NP-hard and APX-hard.

Besides, experiments on three multi-hop question answering datasets: HotpotQA, MuSiQue, and 2WikiMultiHopQA show that BubbleRAG outperforms baseline methods across both 8B and 30B model scales in terms of average F1 score and ACC(LLM-evaluated accuracy).

Critical strengths

1.Well-motivated and effective multi-path evidence retrieval framework.

The paper addresses important challenges in GraphRAG, including ambiguous concept grounding, diverse evidence structures, and premature pruning of relevant retrieval paths. By preserving multiple candidate anchors and combining Bubble Expansion with coverage-aware subgraph ranking, the proposed framework offers a practical approach to improving multi-hop evidence retrieval without additional model training.

2.Promising experimental results with comprehensive evaluation.

BubbleRAG achieves the highest average F1 and ACC(LLM-judged accuracy) among the evaluated baselines across three multi-hop QA benchmarks and two backbone scales. The ablation studies, parameter sensitivity analysis, and statistical significance tests further support the effectiveness of the proposed framework.

Critical weaknesses

1.Limited methodological novelty and insufficient experiments.

BubbleRAG primarily combines existing techniques, including multi-source graph search, Steiner-tree-inspired heuristics, semantic relevance scoring, and LLM-guided expansion. Although the overall framework is meaningful, its core algorithmic novelty is not sufficiently established. Moreover, the paper lacks direct comparisons with recent graph retrieval approaches such as NeuroPath, QAFD-RAG, and SubgraphRAG, making it difficult to assess the advantages of Bubble Expansion over existing methods. (Alternatively, I think at least one method published in 2026 should be included to provide a comparison and enhance the credibility of the paper.)

2.Insufficient isolation of the core contribution and high computational overhead.

The ablation studies do not fully isolate the effectiveness of Bubble Expansion. In particular, only 17.6% of HotpotQA queries and 42.1% of 2Wiki queries enter the graph retrieval stage with the 30B backbone, making it unclear how much of the overall improvement comes from the proposed graph search mechanism rather than preliminary passage retrieval. Additionally, BubbleRAG requires substantially higher inference latency and token consumption than HippoRAG 2, without demonstrating a sufficiently convincing performance–efficiency trade-off. These limitations weaken the evidence supporting the practical value of the proposed framework. These limitations also constrain the development prospects and research significance of this method.

Questions for authors
  1. Novelty and effectiveness of Bubble Expansion (Clarification and additional evidence request): How does the proposed Bubble Expansion fundamentally differ from existing multi-source shortest-path and Group Steiner Tree heuristics? Could the authors provide controlled comparisons with these alternatives while keeping the anchor groups, ranking strategy, and retrieval budget identical? This would help clarify the core algorithmic novelty and effectiveness of the proposed method. In other words, it is suggested that the authors add three experiments: 1. "w/o Bubble Expansion," where anchors are fed directly into the RAE; 2. "Dijkstra-based Search," which employs a traditional shortest-path approach to connect multiple anchor groups; and 3. "Group Steiner Tree Heuristic," which uses a GST heuristic to construct a connected subgraph.

  2. Contribution of the graph retrieval mechanism (Clarification): Appendix D.1 shows that only 17.6% of HotpotQA queries and 42.1% of 2Wiki queries enter the graph retrieval stage with the 30B backbone. Could the authors report the performance separately for queries that enter graph retrieval and those answered through preliminary passage retrieval? Additionally, could the authors clarify how much of the overall improvement can be attributed specifically to Bubble Expansion rather than the preliminary retrieval and early-answering mechanism?

  3. Computational efficiency and practical applicability (Additional evidence request): BubbleRAG requires substantially higher inference latency and token consumption than HippoRAG 2. Could the authors provide comparisons under matched token or latency budgets to demonstrate whether the accuracy improvements justify the additional computational overhead? This would help assess the practical advantages of the proposed framework.

7 comments
AuthorsOpenReview ↗

Rebuttal by Authors (1/2)

We thank the reviewer for the careful reading and constructive feedback. Below, we address each concern and explain the corresponding clarifications and revisions.


W1. Methodological novelty and comparisons with recent methods.

Thank you for your comment. The main contribution of this paper is to identify and study uncertainty in practical KG retrieval: a query concept may match multiple entities, and the evidence needed to answer the question may be connected in ways that cannot be known in advance. Fixing entity matches or connections too early may rule out necessary evidence. BubbleRAG addresses this problem by keeping multiple candidate matches, selecting entities together with their connections, and then retrieving missing facts.

Bubble Expansion is one part of this framework. We do not claim a new general-purpose graph search algorithm as our contribution. Our focus is on the retrieval problem described above and the approach to solving it. Please see our response to Q1 for the specific differences from existing search methods and the controlled experiments.

Following your suggestion to compare with methods from 2026, we have added experiments with two training-free GraphRAG methods: QAFD-RAG (ICLR 2026) and LinearRAG (ICLR 2026). QAFD-RAG was also one of the methods you specifically recommended. The F1 results with the 30B model are shown below:

Method2Wiki F1HotpotQA F1
QAFD-RAG69.5771.39
LinearRAG65.0266.84
BubbleRAG72.5474.35

Q1. Distinction and controlled comparisons with alternative graph search methods

Thank you for suggesting these comparisons. We added three variants:

  • Anchors directly to RAE: Skip subgraph construction and selection, and start RAE from the initial anchors.
  • Shortest-path: Find one lowest-cost path between each pair of anchor groups, considering all candidate entities in both groups. Merge these paths and use each connected component as a candidate subgraph.
  • GST heuristic: Start a tree from each candidate anchor and repeatedly connect the nearest uncovered group through a lowest-cost path. Keep only trees that cover all non-empty groups.

Both search alternatives use the same anchors, ranking, and RAE settings as BubbleRAG. Using the 30B model, we reran questions that entered graph retrieval and kept the original answers for the rest. F1 is reported over all 1,000 questions per dataset:

Method2Wiki F1HotpotQA F1
Anchors directly to RAE70.4470.03
Shortest-path68.7572.17
GST heuristic67.1970.35
Full BubbleRAG72.5474.35

BubbleRAG performs best on both datasets, gaining 2.10 and 4.32 F1 points over anchors directly to RAE. However, on 2Wiki, both alternative searches perform worse than using anchors alone, showing that adding connections does not necessarily help.

A reason is that low-cost paths through shared nodes, such as years or occupations, may connect unrelated facts. Shortest-path keeps only one path per group pair, while the GST heuristic discards candidates that cannot achieve full coverage. Bubble Expansion keeps useful local connections even when they cover only some groups, allowing ranking to select them as starting points for RAE.

AuthorsOpenReview ↗

Rebuttal by Authors (2/2)

Q2. Contribution of the graph retrieval mechanism.

Thank you for your suggestion. Using the original 30B run logs and the grouping criteria in Appendix D.1, we compared queries that entered graph retrieval with those answered directly after initial retrieval. We report F1 alongside HippoRAG2 to show the gains in each group.

DatasetQuery groupBubbleRAG F1HippoRAG2 F1
2WikiGraph retrieval64.0252.03
2WikiAnswered after initial retrieval78.7279.01
HotpotQAGraph retrieval71.3163.55
HotpotQAAnswered after initial retrieval75.0073.46

Compared with HippoRAG2, BubbleRAG gains 11.99 and 7.76 F1 points on queries that enter graph retrieval, versus −0.29 and +1.54 points on the remaining queries. Thus, although only some queries use graph retrieval, the larger gains are concentrated in this group.

The controlled experiments further show that passing the initial anchors directly to RAE does not match the full method. With initial retrieval, early answers, and subsequent RAE settings unchanged, adding Bubble Expansion and candidate subgraph selection raises overall F1 from 70.44 to 72.54 on 2Wiki and from 70.03 to 74.35 on HotpotQA. The comparisons with shortest-path and the GST heuristic in Q1 also show that Bubble Expansion achieves higher F1 with the same subsequent pipeline, supporting the effectiveness of its candidate construction method.


Q3. Computational efficiency and comparisons under matched budgets.

Thank you for your suggestion. We agree that comparing methods under matched token or latency budgets allows for a more comprehensive assessment of their practical advantages. However, the two methods utilize computational resources differently: HippoRAG2 primarily selects documents via graph ranking, whereas BubbleRAG incorporates query-relevant subgraph selection and iterative expansion. Consequently, a fair comparison under matched budgets would require adjusting the configurations for both methods and verifying their respective performance within the given constraints—a task that is difficult to fully design and validate within the scope of the rebuttal phase.

To illustrate the benefits gained from the additional computation, we have supplemented our original results (which included a time comparison for the 8B model) with data for the 30B setting, showing the average query latency and the corresponding F1 score differences for both methods:

DatasetBubbleRAG Avg. Latency (s)HippoRAG2 Avg. Latency (s)F1 Improvement
HotpotQA9.2610.03+2.63
2Wiki22.9710.69+4.89
MuSiQue23.7511.34+7.99

On the 2Wiki and MuSiQue datasets, BubbleRAG incurs an additional average query latency of 12.28 and 12.41 seconds, respectively, while yielding F1 score improvements of 4.89 and 7.99 points. The grouped results in Q2 further show that the average F1 gain is larger on queries that enter graph retrieval, which HippoRAG2 also finds harder to answer, suggesting that the additional retrieval steps enable the system to resolve queries that the baseline struggles to answer.

The retrieval limitations underlying these challenging questions are precisely what BubbleRAG aims to address: Critical evidence may rank low in the baseline’s retrieval results, but by leveraging connections between entities, its importance for answering the query can be uncovered. Appendix D.4 of the revised manuscript presents a specific case: a biography of a director—which contains the necessary answer—is ranked only 65th by HippoRAG2 and thus fails to be included in the retrieval context. In contrast, BubbleRAG successfully identifies this biography by leveraging the connection between the director and their films, ultimately yielding the correct answer. In this case, additional computation is employed to recover critical evidence that would otherwise be missed by the standard retrieval process.

In practice, BubbleRAG answers directly when the initial evidence is enough and searches further when it is not. This suits settings where more retrieval time is acceptable for better answers. Our research goal is to study difficulties in concept matching and evidence connection and provide an effective solution. These results and the case study show that the extra computation helps address retrieval problems that affect answer quality.

Reviewer_Uj7EOpenReview ↗

Reply to the rebuttal

Thank you for the additional experiments, which address several of my main concerns. However, some concerns remain. The author’s new experiments reveal that the proposed method’s average latency is approximately twice that of HippoRAG2; furthermore, Appendix D.6 notes that BubbleRAG’s token consumption is also roughly double that of HippoRAG2. This increase in cost in exchange for an improvement in F1 score,represents a significant drawback for large-scale, real-world applications, thereby undermining the method’s scalability and practical utility.

My current reservation stems from uncertainty regarding whether the authors' proposed method might suffer a significant drop in performance metrics such as the F1 score when compared to other approaches under constrained resource conditions.

Therefore, at this stage, I will maintain my initial Rating; however, I remain open to the possibility of increasing it, i will continue to follow the subsequent process and the comments from the other reviewers.

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

This paper proposes BubbleRAG, a training-free graph-based retrieval-augmented generation framework for multi-hop question answering. The method addresses three challenges: ambiguous query-to-graph grounding, diverse evidence structures, and difficulty comparing candidate subgraphs. BubbleRAG introduces semantic anchor grouping to preserve alternative concept matches, bubble expansion to construct connected candidate evidence graphs, and coverage-aware ranking to prioritize promising subgraphs. Experiments on HotpotQA, MuSiQue, and 2WikiMultiHopQA demonstrate improvements over several RAG baselines, achieving average F1 and LLM-judged accuracy of 63.64 and 67.17, respectively.

Critical strengths
  1. The paper clearly identifies limitations of existing GraphRAG approaches, particularly premature anchor selection and rigid evidence traversal patterns.

  2. Preserving multiple semantic anchors and comparing connected evidence subgraphs before further exploration is an intuitive and useful strategy for multi-hop retrieval.

  3. The OISR formulation and NP-hardness/APX-hardness analysis provide mathematical motivation for the proposed heuristic search.

  4. The experiments cover three established benchmarks, two backbone scales, multiple competitive baselines, ablations, parameter sensitivity, and statistical significance.

  5. BubbleRAG outperforms HippoRAG2 by up to 7.99 F1 points, with particularly encouraging results on MuSiQue using the 30B backbone.

Critical weaknesses
  1. The framework primarily integrates established techniques, including LLM-based query refinement, multi-source graph exploration, relevance-based ranking, and iterative evidence expansion. The distinction between Bubble Expansion and existing graph search or Group Steiner Tree heuristics could be articulated more convincingly.

  2. Removing schema relaxation also removes preliminary passage retrieval. Consequently, the substantial performance degradation cannot be attributed specifically to schema relaxation, making it difficult to isolate the contribution of this component.

  3. Only 42.1% of 2Wiki and 17.6% of HotpotQA questions enter graph retrieval in the reported 30B analysis. This raises concerns about how much of the overall improvement originates from the proposed graph-based mechanism rather than preliminary passage retrieval.

Questions for authors

(1) How does Bubble Expansion fundamentally differ from multi-source Dijkstra search or existing graph-based retrieval methods? A more explicit algorithmic comparison would strengthen the novelty claim.

(2) Could schema relaxation and preliminary passage retrieval be ablated independently? Additional comparisons against simple shortest-path would help isolate the benefit of Bubble Expansion.

(3) Can the authors report evidence recall, anchor precision/recall, and coverage at different stages of the pipeline? These would more directly validate the proposed mechanisms.

(4) Efficiency and scalability: How does runtime scale with graph size, number of anchors, and graph density? Reporting accuracy versus latency/token budgets would help establish practical applicability.

7 comments
AuthorsOpenReview ↗

Rebuttal by Authors (1/3)

We thank the reviewer for the careful reading and constructive feedback. Below, we address each concern and explain the corresponding clarifications and revisions.

W1/Q1. Novelty and the distinction from existing graph search and Group Steiner Tree heuristics.

Thank you for your comment. Bubble Expansion draws on the search approach of GST, but they have different goals. Standard GST seeks a connected subgraph that covers all specified groups. BubbleRAG allows candidate subgraphs to cover only some semantic anchor groups, then ranks them based on semantic relevance and concept coverage and selects multiple subgraphs for further retrieval. This allows useful local subgraphs to be kept even when the evidence cannot be connected into a single subgraph.

We would also like to clarify that Bubble Expansion is only one part of the framework, and we do not claim a new general-purpose graph search algorithm as our contribution. The main value of this work is to identify and study a problem in practical KG retrieval: a query concept may match multiple entities, and the evidence needed to answer the question may be connected in ways that cannot be known in advance. To address this problem, BubbleRAG keeps candidate matches, explores possible connections, selects evidence subgraphs, and then retrieves additional facts needed for the answer. Our focus is on this problem and the overall approach to solving it, rather than the novelty of an individual search step.

W2/Q2. Isolating schema relaxation and evaluating alternative graph search methods.

Thank you for pointing this out. The original ablation removed both schema relaxation and initial document retrieval, so it could not isolate the contribution of schema relaxation. We have therefore added an independent ablation: we keep initial document retrieval and remove only schema relaxation, leaving the rest of the pipeline unchanged. Using the same 30B model as in the main experiments, we evaluated all 1,000 questions in each of 2Wiki and HotpotQA:

Setting2Wiki F1HotpotQA F1
Full BubbleRAG72.5474.35
Without schema relaxation only69.3671.83

Removing only schema relaxation reduces F1 by 3.18 and 2.52 points, respectively. This shows that schema relaxation provides additional gains beyond initial document retrieval.

Following your suggestion to add a shortest-path comparison, and considering the other reviewers’ comments, we compared the following three alternatives for candidate subgraph construction:

  1. Initial anchors directly to RAE: Skip subgraph construction and selection, and continue retrieval directly from the initial anchors.
  2. Shortest-path: For each pair of anchor groups, find the lowest-cost path among all pairs of candidate entities across the two groups. Merge these paths and treat each connected component as a candidate subgraph.
  3. GST heuristic: Use each candidate anchor in turn as a root. At each step, connect an uncovered group through the lowest-cost path until all non-empty groups are covered. Discard roots that cannot achieve full coverage, and collect the subgraphs from the remaining roots into the candidate pool.

The experiments use the 30B model, with all other settings unchanged from BubbleRAG. The F1 scores over all 1,000 questions in each dataset are shown below:

Candidate construction method2Wiki F1HotpotQA F1
Initial anchors directly to RAE70.4470.03
Shortest-path68.7572.17
GST heuristic67.1970.35
Bubble Expansion72.5474.35

Bubble Expansion performs best on both datasets. On 2Wiki, passing the anchors directly to RAE also outperforms shortest-path and the GST heuristic. This suggests that adding connections does not always improve the final answer; whether those connections are relevant to the question also matters.

Shortest-path and the GST heuristic prioritize low-cost connections. However, shared nodes such as years or occupations in the KG can create low-cost connections between unrelated facts, leading candidates away from the evidence needed to answer the question. Since RAE starts from the selected subgraphs, this can also affect later retrieval. Bubble Expansion keeps local connections and anchor candidates, so it does not have to give up useful starting points in order to connect all groups.

The methods that construct candidate subgraphs all use the same subsequent ranking mechanism to select candidates based on semantic relevance and concept coverage. This provides a chance to correct errors from the connection search and may help explain why the final performance gaps are not larger. However, ranking can only select from the candidates already available, so the entities and connections kept during candidate construction still affect the final results.

AuthorsOpenReview ↗

Rebuttal by Authors (2/3)

W3. The contribution of selectively triggered graph retrieval.

Thank you for raising this question. Triggering graph retrieval only when needed is part of BubbleRAG’s design. If initial retrieval provides enough evidence, the system answers directly. Otherwise, it uses graph retrieval to find the missing information. This allows us to spend additional computation on questions that initial retrieval struggles to answer.

To examine this, we compared BubbleRAG and HippoRAG2 on the subset of queries that triggered graph retrieval. We found that BubbleRAG’s gains over HippoRAG2 mainly come from this subset. On 2Wiki, these queries account for 42.1% of all questions but contribute all of the overall gain. On HotpotQA, they account for only 17.6% of all questions but contribute more than half of the overall gain.

Among the questions in this subset where HippoRAG2 scored F1 = 0, BubbleRAG achieved F1 = 1 on 39.9% and 36.4% of them on 2Wiki and HotpotQA, respectively. Thus, a low trigger rate does not mean that graph retrieval contributes little. The additional retrieval focuses on a subset of difficult questions, and improvements on these questions are an important source of the overall performance gains.


Q3. Evidence recall across pipeline stages.

Thank you for your suggestion. We now report supporting-document recall at each stage of the pipeline. This metric measures the fraction of a question’s annotated supporting documents found at each stage. For example, if a question has two supporting documents, finding one gives 50% recall, while finding both gives 100%. We match documents by title, remove duplicates, and calculate recall for each question before averaging across questions.

The table below covers questions that entered graph retrieval. For initial retrieval, we count the documents actually retrieved. For the initial anchors, we count the source documents linked to all anchor nodes. After subgraph selection, we count the source documents linked to nodes in the top two selected subgraphs. After RAE, we count the source documents linked to nodes in the expanded subgraphs. Finally, we count the documents actually passed to the answer model.

Stage2WikiHotpotQA
Initial retrieval50.5%81.7%
Sources linked to initial anchors69.8%73.0%
Sources linked to selected subgraphs72.5%79.5%
Sources linked to subgraphs after RAE87.7%84.6%
Final answer context89.9%89.8%

Subgraph construction and selection find supporting documents missing from the initial anchor sources, and RAE adds further evidence. The average supporting document recall in the final answer context increases from 50.5% to 89.9% on 2Wiki and from 81.7% to 89.8% on HotpotQA compared with initial retrieval.

AuthorsOpenReview ↗

Rebuttal by Authors (3/3)

Q4. Efficiency and scalability.

Thank you for raising this question. We use the complexity analysis in Appendix B.4 and the existing runtime breakdown to explain how changes in scale affect runtime. We also add a comparison of accuracy and latency.

In the existing runtime analysis, semantic grouping, candidate subgraph construction, RAE, and final answer generation account for 43.84%, 23.05%, 26.00%, and 7.11% of the total time, respectively. Changes in scale affect these stages differently.

A larger graph mainly affects entity retrieval during semantic grouping. A larger KG requires a larger retrieval index, and the retrieval time depends on the underlying index structure and implementation. When the number of returned candidates is fixed, the amount of information passed to the LLM during semantic grouping does not grow with the full graph. Other GraphRAG methods that use entity retrieval face similar challenges in scaling their indexes. Later graph searches operate in local neighborhoods around the query anchors. Therefore, if the anchors and their search neighborhoods remain unchanged, growth in distant parts of the graph does not increase the work of local traversal.

More anchors mainly increase the cost of initial matching and candidate construction. Semantic grouping must process more candidates, and graph search must maintain more starting points. For a fixed local graph, the work of the independent searches grows linearly with the number of anchors. After ranking, only a fixed number of subgraphs enter RAE, so the system does not run a full expansion for every additional anchor. The later runtime depends on the sizes of the selected subgraphs and their neighborhoods.

Higher local density can slow down both candidate search and RAE. Search must examine more edges, and each RAE round may need to process more neighboring information. However, this effect is limited to the regions actually visited. The RAE round limit bounds the number of iterations, while the final context budget limits the input to answer generation.

For the accuracy–latency trade-off, the original paper reports query times with the 8B model. We have added average query times with the 30B model, together with F1 gains over HippoRAG2:

DatasetBubbleRAG average time (s)HippoRAG2 average time (s)F1 gain
HotpotQA9.2610.03+2.63
2Wiki22.9710.69+4.89
MuSiQue23.7511.34+7.99

On 2Wiki and MuSiQue, BubbleRAG adds about 12 seconds per query on average and improves F1 by 4.89 and 7.99 points, respectively. These results show the practical trade-off: in settings where additional retrieval time is acceptable and answer quality is a priority, BubbleRAG improves answers through a more thorough search for evidence. The gain is larger on MuSiQue, where questions require combining more complex evidence.

Comments on the paper

2 comments

Dear Reviewers,

Please take a moment to read the authors’ rebuttal and participate in the discussion.

Thanks,

AC

AuthorsOpenReview ↗

General Response on Novelty and Training-Free Retrieval

Dear Reviewers and Area Chair,

We sincerely thank all reviewers and the AC for the time and effort you have put into reviewing and discussing our paper. We also appreciate your positive feedback and constructive suggestions.

We first thank the reviewers for recognizing the following strengths of our work:

  1. Important research problem (9tE9, Uj7E)

  2. Effective retrieval design (9tE9, Uj7E, Zr5U)

  3. Strong experimental results (9tE9, Uj7E)

  4. Solid theoretical foundation (9tE9)

We are glad that our rebuttal and additional experiments have addressed some of the reviewers' concerns. However, we notice that some concerns remain regarding the methodological novelty of BubbleRAG and the value of training-free retrieval. We would like to further clarify these two points.

1. Methodological Novelty

First, we do not agree that combining existing techniques necessarily means a lack of novelty. In fact, many methods in machine learning are built upon existing techniques. For example, HippoRAG2 also combines existing techniques such as entity recognition, knowledge graph construction, graph retrieval, and LLM reasoning. Clearly, we cannot conclude that HippoRAG2 lacks methodological novelty simply because these techniques already existed.

We believe that the novelty of a method should not be judged solely by whether each component is new, but by how these components form a new mechanism and whether this mechanism addresses problems that have not been sufficiently solved before.

More importantly, BubbleRAG is not simply a combination of existing techniques.

Our work starts from a problem in existing KG retrieval methods: they often need to identify the matched entities first and then retrieve evidence starting from these entities. However, in KGs constructed from text, entity matching can be ambiguous, and the connections between supporting facts are often unknown in advance. Selecting an entity or retrieval path too early may cause the system to miss important evidence.

To address this problem, BubbleRAG does not simply add graph search or subgraph ranking to an existing pipeline. Instead, it changes how the starting points for further evidence retrieval are determined. We preserve multiple possible entity matches and draw on ideas from the Group Steiner Tree problem to explore possible connections among candidate entities. We then construct and compare candidate evidence subgraphs, and use the selected subgraphs themselves as starting points for retrieving missing information.

We believe this is fundamentally different from selecting a better anchor based on subgraph relevance and then starting graph traversal from that anchor. Our additional ablation experiments and comparisons with shortest-path search and GST heuristics further support the effectiveness of this design.

2. The Value of Training-Free Methods

Second, we do not believe that whether a method requires additional training is directly related to the value of the research problem we study.

Training can certainly improve entity matching and graph retrieval. However, training does not guarantee that the uncertainty in these processes will disappear. In particular, when a model encounters new entities, relations, or knowledge graphs outside its training data, it may still face ambiguous entity matches and unknown evidence connections. These problems do not simply disappear because a model has been trained.

More importantly, the central idea of BubbleRAG is not limited to training-free methods. We study how to better construct, compare, and select evidence structures when retrieval involves uncertainty. The same idea can also guide the design of trainable GraphRAG systems. For example, training could be used to improve candidate subgraph construction, selection, and subsequent retrieval.

We believe this contribution should not be overlooked simply because our current implementation does not require additional training. The value of addressing retrieval uncertainty should be judged by the problem itself and the effectiveness of the proposed approach.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.