정적 그래프의 한계를 극복하는 방법: 문맥 인지 탐색을 통한 견고한 검색 증강 생성

Breaking the Static Graph: Context-Aware Traversal for Robust Retrieval-Augmented Generation

최근 검색 증강 생성(RAG) 분야의 발전은 단순한 벡터 유사성 기반 방식에서 벗어나, 지식 그래프(KG)와 개인화된 페이지랭크(PPR)를 활용하여 다중 홉 의존성을 포착하는 HippoRAG와 같은 구조 기반 접근 방식으로 전환되었습니다. 그러나 이러한 방법은 "정적 그래프 오류"라는 문제점을 가지고 있습니다. 즉, 인덱싱 과정에서 결정되는 고정된 전환 확률에 의존하며, 이는 쿼리에 따라 달라지는 엣지의 관련성을 무시하여, 의미론적 왜곡을 초래하며, 무작위 탐색이 중요한 증거에 도달하기 전에 고차수 "허브" 노드로 분산되는 현상을 발생시킵니다. 그 결과, 모델은 종종 높은 부분적 재현율을 달성하지만, 다중 홉 쿼리에 필요한 전체 증거 체인을 검색하는 데 실패합니다. 이러한 문제를 해결하기 위해, 우리는 견고한 RAG를 위한 문맥 인지 탐색 방법인 CatRAG 프레임워크를 제안합니다. CatRAG은 HippoRAG 2 아키텍처를 기반으로 하며, 정적 KG를 쿼리에 적응하는 탐색 구조로 변환합니다. 우리는 다음과 같은 다각적인 프레임워크를 통해 무작위 탐색을 제어합니다. (1) 심볼릭 앵커링: 약한 엔티티 제약을 주입하여 무작위 탐색을 규제합니다. (2) 쿼리 인지 동적 엣지 가중치 부여: 그래프 구조를 동적으로 조절하여, 쿼리의 의도와 일치하는 경로는 강화하고 관련 없는 경로는 제거합니다. (3) 핵심 사실 기반 패시지 가중치 강화: 비용 효율적인 편향을 통해 무작위 탐색을 잠재적인 증거에 구조적으로 연결합니다. 네 가지 다중 홉 벤치마크에 대한 실험 결과, CatRAG은 최첨단 기준 모델보다 지속적으로 우수한 성능을 보였습니다. 분석 결과, 표준 재현율 지표에서 미미한 개선이 나타나는 반면, CatRAG은 추론의 완전성, 즉 전체 증거 경로를 누락 없이 복구하는 능력에서 상당한 개선을 달성했습니다. 이러한 결과는 우리의 접근 방식이 부분적인 컨텍스트 검색과 완전한 기반 추론을 가능하게 하는 사이의 격차를 효과적으로 해소한다는 것을 보여줍니다. 관련 자료는 https://github.com/kwunhang/CatRAG에서 확인할 수 있습니다.

Recent advances in Retrieval-Augmented Generation (RAG) have shifted from simple vector similarity to structure-aware approaches like HippoRAG, which leverage Knowledge Graphs (KGs) and Personalized PageRank (PPR) to capture multi-hop dependencies. However, these methods suffer from a "Static Graph Fallacy": they rely on fixed transition probabilities determined during indexing. This rigidity ignores the query-dependent nature of edge relevance, causing semantic drift where random walks are diverted into high-degree "hub" nodes before reaching critical downstream evidence. Consequently, models often achieve high partial recall but fail to retrieve the complete evidence chain required for multi-hop queries. To address this, we propose CatRAG, Context-Aware Traversal for robust RAG, a framework that builds on the HippoRAG 2 architecture and transforms the static KG into a query-adaptive navigation structure. We introduce a multi-faceted framework to steer the random walk: (1) Symbolic Anchoring, which injects weak entity constraints to regularize the random walk; (2) Query-Aware Dynamic Edge Weighting, which dynamically modulates graph structure, to prune irrelevant paths while amplifying those aligned with the query's intent; and (3) Key-Fact Passage Weight Enhancement, a cost-efficient bias that structurally anchors the random walk to likely evidence. Experiments across four multi-hop benchmarks demonstrate that CatRAG consistently outperforms state of the art baselines. Our analysis reveals that while standard Recall metrics show modest gains, CatRAG achieves substantial improvements in reasoning completeness, the capacity to recover the entire evidence path without gaps. These results reveal that our approach effectively bridges the gap between retrieving partial context and enabling fully grounded reasoning. Resources are available at https://github.com/kwunhang/CatRAG.