BubbleRAG: 블랙박스 지식 그래프를 위한 증거 기반 검색 증강 생성

기존의 그래프 기반 RAG 시스템은 지식 그래프의 구조(스키마)를 미리 알고 있어야 한다는 제약이 있었으나, BubbleRAG는 이를 모르는 '블랙박스' 환경에서도 동작합니다. 특히 여러 단계를 거쳐야 하는 복잡한 질문에 대해 정보 밀도가 높은 부분 그래프를 효율적으로 찾아내어 답변의 정확도를 크게 높였습니다.

기존의 임베딩(Embedding) 기반 검색은 텍스트 조각들 사이의 논리적 연결 고리를 놓치기 쉽고, 지식 그래프(KG)를 활용하려 해도 데이터의 구조(Schema)를 모르면 어디서부터 검색을 시작할지 막막하다는 한계가 있다. BubbleRAG는 이를 해결하기 위해 쿼리의 각 키워드를 '앵커(Anchor)'로 설정하고, 이 앵커들이 그래프 상에서 어떻게 연결되는지를 추적하는 방식을 취한다.

동작 원리는 비눗방울이 커지다가 서로 만나는 과정과 유사하다. 각 키워드 노드에서 시작된 탐색은 의미적 유사도가 높은(Semantic Cost가 낮은) 경로를 우선적으로 따라가며 '거품'처럼 팽창한다. 이때 단순히 거리를 재는 것이 아니라, LLM이 판단한 키워드의 중요도와 그래프 엣지에 포함된 텍스트 정보를 결합하여 탐색의 방향성을 결정한다.

서로 다른 키워드에서 시작된 탐색 거품들이 그래프 상의 특정 노드에서 충돌(Collision)하면, 시스템은 이를 중요한 증거들이 모이는 지점으로 판단한다. 이렇게 연결된 부분 그래프들을 모아 정보 밀도가 가장 높은 후보군을 추려냄으로써, 방대한 데이터 속에서 질문의 답을 찾기 위한 최적의 맥락(Context)을 구성하게 된다.

BubbleRAG의 파이프라인은 데이터 준비와 4단계의 온라인 검색 과정으로 구성된다. 먼저 데이터 준비 단계에서는 텍스트 코퍼스에서 추출된 개체와 관계를 그래프로 구축하되, 엣지에 단순 라벨이 아닌 풍부한 텍스트 정보를 임베딩하여 저장한다.

온라인 단계의 첫 번째인 Semantic Anchor Grouping에서는 LLM이 쿼리에서 핵심 키워드를 추출하고, 이를 그래프 내의 노드나 엣지에 매핑한다. 이때 LLM은 각 키워드의 중요도 가중치 w를 할당한다. [쿼리 입력 → LLM 키워드 추출 및 가중치 계산 → 가중치 합이 1인 벡터 출력] 과정을 통해 검색의 우선순위를 정한다.

두 번째 단계인 CEG Discovery에서는 Bubble Expansion 알고리즘을 수행한다. 각 앵커 그룹에서 Dijkstra 기반 확장을 시작하며, 노드 v의 비용 cost(v) = 1 - cos(zq, zv)를 계산한다. [쿼리 벡터 zq와 노드 벡터 zv의 코사인 유사도 입력 → 1에서 뺀 값 계산 → 의미적 거리 출력] 순으로 연산하여 유사도가 높을수록 낮은 비용으로 탐색하게 한다. 여러 그룹의 탐색 경로가 겹치는 지점을 Steiner Node로 식별하여 후보 증거 그래프(CEG)를 생성한다.

마지막으로 CEG Ranking과 Reasoning-aware Expansion 단계를 거친다. 생성된 후보 그래프들을 의미적 일관성과 구조적 완성도를 결합한 Composite Score로 정렬하고, 상위 후보들에 대해 LLM이 직접 이웃 노드를 탐색하며 부족한 정보를 보완한다. 최종적으로 선택된 그래프의 텍스트 조각들을 LLM에 전달하여 답변을 생성한다.

BubbleRAG는 MuSiQue, HotpotQA, 2WikiMultiHopQA 등 세 가지 주요 다단계 QA 벤치마크에서 평가되었다. 30B 모델 기준, 가장 난이도가 높은 MuSiQue 데이터셋에서 F1 스코어 53.03을 기록하며 기존 최고 성능 모델인 HippoRAG2(45.04)를 약 8%p 차이로 크게 앞질렀다.

Ablation Study 결과, 'Schema Relaxation' 기능을 제거했을 때 2Wiki 데이터셋에서 F1 점수가 11.35포인트 하락하여 가장 치명적인 성능 저하를 보였다. 이는 블랙박스 환경에서 엄격한 라벨 매칭 대신 유연한 의미적 매칭을 허용하는 것이 검색 재현율(Recall) 확보에 핵심적임을 시사한다.

효율성 측면에서 BubbleRAG는 쿼리당 평균 20.99초의 지연 시간을 기록했다. 이는 단순 벡터 검색인 Naive RAG보다는 느리지만, 유사한 그래프 탐색 방식인 ToG(45.93초)보다는 2배 이상 빠르면서도 훨씬 높은 정확도를 보여주어 실용적인 트레이드오프를 달성했음을 확인했다.

BubbleRAG의 핵심은 그래프 검색을 Steiner Tree 문제의 변형인 OISR로 정의한 것이다. OISR은 연결성을 보장하면서 선택된 노드와 엣지의 평균 의미적 가중치를 최대화하는 것을 목표로 한다. 이는 단순히 짧은 경로를 찾는 것을 넘어 정보의 밀도(Information Density)를 최적화하는 접근이다.

알고리즘적으로는 이방성(Anisotropic) 확장을 사용한다. 표준 BFS가 모든 방향으로 동일하게 확장되는 것과 달리, BubbleRAG는 쿼리와의 의미적 거리에 기반한 우선순위 큐를 사용하여 유망한 경로를 먼저 탐색한다. 이는 탐색 공간을 획기적으로 줄여 대규모 그래프에서도 확장이 가능하게 한다.

또한, 'Anchor Specialization' 기법을 통해 모호한 키워드를 쿼리 맥락에 맞게 재작성한다. 예를 들어 '어머니'라는 일반적인 단어를 '로타르 2세의 어머니'로 구체화하여 검색 범위를 좁힘으로써 정밀도(Precision)를 높인다. 마지막 단계의 'Reasoning-aware Expansion'은 LLM이 현재까지 수집된 증거를 바탕으로 다음에 읽어야 할 노드를 직접 선택하게 하여 추론의 완결성을 더한다.

논문은 BubbleRAG가 LLM과의 다단계 상호작용(앵커 그룹화 및 추론 확장 단계)을 포함하므로, 단순 벡터 검색 방식인 Naive RAG나 HippoRAG2에 비해 추론 지연 시간(Latency)과 토큰 소모량이 더 많다는 점을 한계로 언급했다.