BubbleRAG: Evidence-Driven Retrieval-Augmented Generation for Black-Box Knowledge Graphs
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.
69c23bfbc105f45cb0482087
Duyi Pan
claimed_verified
2026-03-24T09:20:36.532Z
645e06bf8a22774edb2987bf
https://cdn-avatars.huggingface.co/v1/production/uploads/645e06bf8a22774edb2987bf/esYK_OoruC4rRO6ROpbd8.png
duyiPan
AzulaFire
user
AzulaFire
69c23bfbc105f45cb0482088
Tianao Lou
69c23bfbc105f45cb0482089
Xin Li
69c23bfbc105f45cb048208a
Haoze Song
69c23bfbc105f45cb048208b
Yiwen Wu
69c23bfbc105f45cb048208c
Mengyi Deng
69c23bfbc105f45cb048208d
Mingyu Yang
69c23bfbc105f45cb048208e
Wei Wang
BubbleRAG: Evidence-Driven Retrieval-Augmented Generation for Black-Box Knowledge Graphs
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.
BubbleRAG addresses recall and precision limitations in graph-based RAG by formulating retrieval as Optimal Informative Subgraph Retrieval and using semantic anchoring, bubble expansion, and composite ranking.
Graph-based retrieval augmented generation RAG knowledge graphs semantic instantiation uncertainty structural path uncertainty evidential comparison uncertainty Optimal Informative Subgraph Retrieval Group Steiner Tree NP-hard APX-hard semantic anchor grouping heuristic bubble expansion candidate evidence graphs composite ranking reasoning-aware expansion