Source-linked AI summary
BubbleRAG: Evidence-Driven Retrieval-Augmented Generation for Black-Box Knowledge Graphs
Duyi Pan, Tianao Lou, Xin Li, Haoze Song, Yiwen Wu, Mengyi Deng, Mingyu Yang, Wei Wang
TL;DR
Black-box knowledge graphs make it difficult to retrieve evidence with both high recall and precision because their schema and structure are unknown. BubbleRAG formalizes retrieval as OISR and applies a training-free pipeline combining semantic anchoring, heuristic candidate discovery, ranking, and reasoning-aware expansion. On multi-hop QA benchmarks, it consistently outperforms strong baselines in accuracy and F1, including with smaller language models, while remaining plug-and-play.
Problem
Black-box knowledge graphs create recall and precision limitations because query concepts, relational paths, and evidential comparisons are uncertain.
Method
BubbleRAG formalizes retrieval as OISR, a Group Steiner Tree variant, and uses training-free anchor grouping, bubble expansion, candidate ranking, and reasoning-aware expansion.
Results
BubbleRAG consistently outperforms strong baselines in F1 and accuracy on multi-hop QA benchmarks, including with 8B models against baselines using 30B models.
Takeaways & Limitations
BubbleRAG provides a plug-and-play retrieval framework requiring neither retriever fine-tuning nor modifications to the underlying knowledge graph structure.
Takeaways & Limitations
The formulation assumes the knowledge graph is informationally sufficient for the query and permits partial alignment when concepts are missing or disconnected.
Abstract
from arXiv · showhide
Large Language Models (LLMs) exhibit hallucinations in knowledge-intensive tasks. Graph-based retrieval augmented generation (RAG) has emerged as a promising solution, yet existing approaches suffer from fundamental recall and precision limitations when operating over black-box knowledge graphs -- graphs whose schema and structure are unknown in advance. We identify three core challenges that cause recall loss (semantic instantiation uncertainty and structural path uncertainty) and precision loss (evidential comparison uncertainty). To address these challenges, we formalize the retrieval task as the Optimal Informative Subgraph Retrieval (OISR) problem -- a variant of Group Steiner Tree -- and prove it to be NP-hard and APX-hard. We propose BubbleRAG, a training-free pipeline that systematically optimizes for both recall and precision through semantic anchor grouping, heuristic bubble expansion to discover candidate evidence graphs (CEGs), composite ranking, and reasoning-aware expansion. Experiments on multi-hop QA benchmarks demonstrate that BubbleRAG achieves state-of-the-art results, outperforming strong baselines in both F1 and accuracy while remaining plug-and-play.
Yiwen Wu HKUST (GZ)
Yiwen Wu is affiliated with HKUST (GZ) and HKUST.
- Yiwen Wu is affiliated with HKUST (GZ) and HKUST.
Keywords
The paper concerns large language models, retrieval-augmented generation, and knowledge graphs.
- The paper covers large language models, retrieval-augmented generation, and knowledge graphs.
1 Introduction
Black-box knowledge-graph retrieval must balance recall and precision despite uncertain concept grounding, relational paths, and evidence comparison. BubbleRAG formulates this challenge as OISR and uses a training-free retrieval pipeline that combines anchor grouping, heuristic search, ranking, and reasoning-aware expansion.
- LLM hallucinations and outdated training knowledge motivate retrieval-augmented generation for external information at inference time.
- Black-box graph retrieval suffers from semantic instantiation, structural path, and evidential comparison uncertainty, jointly limiting recall and precision.
- The query “find an ML expert” illustrates ambiguity in concept realizations and linking paths when the graph schema is unknown.
- Prior schema-translation and related paradigms have recall or precision limitations because their assumptions may miss divergent graph topologies or lack systematic comparison.
- BubbleRAG is training-free and uses semantic anchor grouping, heuristic bubble expansion, candidate ranking, and reasoning-aware expansion to address recall and precision.
- BubbleRAG formalizes retrieval as OISR, a Group Steiner Tree variant balancing semantic coverage and information density.
2 Preliminaries
The paper defines black-box knowledge graphs, motivates connected evidence subgraphs, and formalizes retrieval as selecting informative connected subgraphs covering semantic anchor groups. The resulting OISR problem is theoretically hard, motivating heuristic retrieval.
- Graph-based RAG indexes documents into graphs, retrieves an evidence subgraph, and generates an answer; graph structure enables cross-document reasoning.
- A black-box knowledge graph exposes topology and textual content but not its schema, entity types, relation types, or constraints.
- Without schema knowledge, retrieval cannot rely on predefined traversal patterns, meta-paths, or type constraints and must reason about structure at query time.
- Answer-supporting subgraphs should semantically anchor query concepts and connect them through compact, topologically cohesive structures.
- OISR seeks a connected subgraph covering at least one element from each semantic anchor group while maximizing average node-and-edge value.
- The average-value objective rewards compact query-relevant subgraphs and penalizes coverage through long irrelevant paths, while anchor groups may contain edges.
- OISR is NP-hard and APX-hard, motivating the heuristic approach developed for retrieval.
3 The BubbleRAG Framework
BubbleRAG combines semantic anchoring, connected candidate-graph discovery, discriminative ranking, and reasoning-aware expansion to retrieve evidence from black-box knowledge graphs. Its formulation and localized construction address recall, precision, theoretical hardness, and scalability.
- 3.3 Candidate Evidence Graph Discovery: Bubble Expansion connects anchor groups into candidate evidence graphs, while separate ranking scores semantic relevance and structural completeness.The separation lets discovery explore broadly with a fast heuristic before richer candidate evaluation.
- 3.1 Data Preparation: BubbleRAG builds a graph with text-enriched edges, enabling semantic matching over both entities and relations.This supports queries whose key constraints are relational predicates.
- 3.2 Semantic Anchor Grouping: LLM-based keyword extraction infers implicit concepts that surface extraction may miss, improving anchor mapping in black-box graphs.For example, it infers Albert Einstein for a query about the winner of the 1921 Nobel Prize in Physics.
- 3.2 Semantic Anchor Grouping: Semantic anchor grouping merges candidate nodes and edges into weighted groups, preserving multiple realizations of each query concept.Weights prioritize central concepts while allowing partial retrieval when lower-weight groups are missing.
- Theoretical Foundations: OISR, the formal retrieval objective underlying the framework, is NP-hard and APX-hard, motivating BubbleRAG’s heuristic retrieval strategy.The hardness results are established through a reduction from Group Steiner Tree and an inapproximability argument.
- Efficiency: Localized construction makes per-query retrieval complexity largely independent of the full graph size, with retrieved subgraphs typically under 10^3 nodes in graphs exceeding 10^5 nodes.This provides the framework’s reported scalability property for massive knowledge graphs.
4 Experiments
BubbleRAG is evaluated on multi-hop QA benchmarks against diverse retrieval baselines, achieving consistently strong accuracy while balancing retrieval quality and computational cost. Ablations and sensitivity analyses support the value of its components and identify practical parameter trade-offs.
- Main Results: BubbleRAG achieves the highest average F1 and LLM-as-a-Judge Accuracy across three benchmarks and both 30B and 8B model settings.With 30B models, it surpasses HippoRAG2 by 2.52% average F1 and 2.23% average accuracy.
- Main Results: 53.03 F1 on MuSiQue with the 30B model outperforms HippoRAG2 by approximately 8 percentage points.The dataset requires 3–4 hop reasoning, where single-anchor or fixed-hop strategies break down.
- Main Results: BubbleRAG’s group-aware expansion handles variable-length reasoning chains without predefined hop limits.Its heuristic Steiner Tree search is described as producing semantically grounded and complete reasoning chains.
- Main Results: 63.02 average F1 with the 8B model is comparable to, and often better than, many baselines using larger 30B models.The reported result attributes this pattern to the quality of the retrieved context compensating for reduced parametric knowledge.
- Ablation Studies: Removing Schema Relaxation decreases F1 by 11.35 points on 2Wiki and 5.17 points on HotpotQA, the largest ablation drop.The analysis links this component to chunk-guided anchor selection and avoiding semantically mismatched nodes.
- Ablation Studies: Removing Anchor Specialization decreases F1 by 4.52 points on 2Wiki and 2.54 points on HotpotQA, while removing CEG Ranking primarily reduces precision.The ablation summary associates the first two removals with recall loss and CEG Ranking removal with noisy candidate selection.
- Parameter Sensitivity: B=10 yields an F1 of 60.52 with 20.99 seconds latency, while larger budgets increase latency without meaningful performance gains.Reasoning depth improves F1 from 58.25 to 62.28 as depth rises from 2 to 8, but d=6 is reported as the best practical trade-off.
- Efficiency & Cost Analysis: BubbleRAG runs in 20.99 seconds, faster than ToG at 45.93 seconds while delivering superior accuracy, but slower than HippoRAG2 at 4.26 seconds.Its approximately 5× latency difference from HippoRAG2 is attributed largely to LLM interactions in anchor grouping and reasoning-aware expansion.
5 Related Work
Prior graph-retrieval methods use schema translation, iterative exploration, random walks, or auxiliary structures, but each has recall or precision limitations. BubbleRAG instead uses grouped anchors and query-specific, dynamically discovered evidence structures without assuming prior schema knowledge.
- Query Rewriting and Schema-Aligned Matching: Schema-translation methods align queries with pre-conceived structural templates, which can limit recall when actual graph topology diverges from LLM assumptions.The limitation is especially noted for distant or implicit connections.
- Iterative Multi-Hop Exploration: Iterative multi-hop methods expand from semantic seed nodes using constrained searches or generated relation plans to construct reasoning chains.Examples include ToG, ToG2, and RoG.
- Stochastic Traversal via Random Walks: Random-walk methods use algorithms such as Personalized PageRank from semantic anchors to capture structural centrality and associative relationships.HippoRAG2 integrates passage nodes directly into the graph.
- Structure-Augmented Retrieval with Auxiliary Graphs: Structure-augmented methods construct hierarchical indices or community structures before retrieval, as in GraphRAG, KAG, and ClueRAG.These approaches rely on pre-processing to build auxiliary graph structures.
- BubbleRAG: BubbleRAG initializes from groups of anchors and discovers query-specific evidence structures dynamically, without assuming prior schema knowledge.This distinguishes it from single-seed traversal and pre-indexed structure methods.
6 Conclusion
BubbleRAG formalizes black-box knowledge-graph retrieval as a joint recall–precision optimization problem and introduces a training-free pipeline to address both goals. Experiments show consistent improvements over state-of-the-art baselines, including with smaller language models.
- 6 Conclusion: OISR models retrieval as a Group Steiner Tree variant balancing semantic coverage and information density, and is proved NP-hard and APX-hard.The formulation captures recall through coverage and precision through evidence density.
- 6 Conclusion: BubbleRAG addresses recall with semantic anchor grouping and heuristic bubble expansion, and precision with candidate evidence graph ranking and reasoning-aware expansion.The pipeline is training-free and derives its retrieval strategy from the OISR formalization.
- 6 Conclusion: BubbleRAG consistently outperforms state-of-the-art baselines, including HippoRAG2, on multi-hop QA accuracy and F1.The reported gains span comprehensive multi-hop question-answering experiments.
- 6 Conclusion: BubbleRAG remains competitive with 8B language models against baselines using 30B models.Its plug-and-play design requires no retriever fine-tuning or modifications to the underlying knowledge graph.