# BubbleRAG: Evidence-Driven Retrieval-Augmented Generation for Black-Box Knowledge Graphs

arXiv: https://arxiv.org/abs/2603.20309 · HTML: https://mlsanity.com/paper/2603.20309/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge-graph and structured-knowledge RAG, one of 15 directions in Retrieval-augmented generation.
- Builds on 22 of its 37 references that are in the map.
- First posted on arXiv 19 Mar 2026.

## Placed in

- Retrieval-augmented generation / [Knowledge-graph and structured-knowledge RAG](https://mlsanity.com/rag/knowledge-graph-and-structured-knowledge-rag/)

## Builds on (most cited first, 22 of 22)

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [A Survey on Knowledge Graphs: Representation, Acquisition and Applications](https://mlsanity.com/paper/2002.00388/) (2020)
- [RAPTOR: Recursive Abstractive Processing for Tree-Organized Retrieval](https://mlsanity.com/paper/2401.18059/) (2024)
- [Hallucination is Inevitable: An Innate Limitation of Large Language Models](https://mlsanity.com/paper/2401.11817/) (2024)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [A Comprehensive Survey of Hallucination Mitigation Techniques in Large Language Models](https://mlsanity.com/paper/2401.01313/) (2024)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [Hallucination-Free? Assessing the Reliability of Leading AI Legal Research Tools](https://mlsanity.com/paper/2405.20362/) (2024)
- [Medical Hallucinations in Foundation Models and Their Impact on Healthcare](https://mlsanity.com/paper/2503.05777/) (2025)
- [RAG vs. GraphRAG: A Systematic Evaluation and Key Insights](https://mlsanity.com/paper/2502.11371/) (2025)
- [LinearRAG: Linear Graph Retrieval Augmented Generation on Large-scale Corpora](https://mlsanity.com/paper/2510.10114/) (2025)
- [In-depth Analysis of Graph-based RAG in a Unified Framework](https://mlsanity.com/paper/2503.04338/) (2025)
- [A Survey on Large Language Models with some Insights on their Capabilities and Limitations](https://mlsanity.com/paper/2501.04040/) (2025)
- [Large Language Models Meet Knowledge Graphs for Question Answering: Synthesis and Opportunities](https://mlsanity.com/paper/2505.20099/) (2025)
- [Graph-based Approaches and Functionalities in Retrieval-Augmented Generation: A Comprehensive Survey](https://mlsanity.com/paper/2504.10499/) (2025)
- [BYOKG-RAG: Multi-Strategy Graph Retrieval for Knowledge Graph Question Answering](https://mlsanity.com/paper/2507.04127/) (2025)
- [Think-on-Graph 3.0: Efficient and Adaptive LLM Reasoning on Heterogeneous Graphs via Multi-Agent Dual-Evolving Context Retrieval](https://mlsanity.com/paper/2509.21710/) (2025)
- [Clue-RAG: Towards Accurate and Cost-Efficient Graph-based RAG via Multi-Partite Graph and Query-Driven Iterative Retrieval](https://mlsanity.com/paper/2507.08445/) (2025)

## Abstract (arXiv)

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.