PathRAG: Pruning Graph-Based Retrieval Augmented Generation with Relational Paths

개요
PathRAG는 기존 graph-based RAG 방법론이 가진 정보의 중복성 문제와 평면적인(flat) 구조로 인한 프롬프트 구성의 비효율성을 해결하기 위해 제안된 새로운 프레임워크임. 기존 방식인 GraphRAG나 LightRAG는 특정 커뮤니티나 이웃 노드의 모든 정보를 검색하여 불필요한 노이즈를 유발하고 토큰을 낭비하는 경향이 있음. PathRAG는 indexing graph 내에서 핵심적인 relational paths만을 추출하여 LLM에 전달함으로써 정보의 질을 높이고 추론 성능을 향상함.

방법론

PathRAG의 워크플로우는 크게 Node Retrieval, Path Retrieval, Answer Generation 세 단계로 구성됨.

1. Node Retrieval: 쿼리 $q$에서 키워드 $K_q$를 추출하고, 의미적 임베딩 공간에서 코사인 유사도를 기반으로 indexing graph $G$에서 상위 $N$개의 관련 노드 $V_q$를 식별함.
2. Path Retrieval: 선택된 노드 쌍($v_{start}, v_{end}$) 사이의 핵심 경로를 식별하기 위해 resource allocation 전략에 기반한 flow-based pruning 알고리즘을 도입함. 노드 $v_i$의 자원 $S(v_i)$는 다음과 같이 전파됨:
   $S(v_i) = \sum_{v_j \in N(\cdot, v_i)} \alpha \cdot \frac{S(v_j)}{|N(v_j, \cdot)|}$
   여기서 $\alpha$는 감쇠율(decay rate)을 의미함. 또한, 계산 효율성을 위해 $S(v_i)/|N(v_i, \cdot)| < \theta$인 경우 조기 종료(early stopping) 전략을 적용함. 추출된 각 경로 $P$의 신뢰도 $S(P)$는 경로상의 노드 자원 평균값으로 정의함:
   $S(P) = \frac{1}{|E_P|} \sum_{v_i \in V_P} S(v_i)$
3. Answer Generation: LLM의 lost in the middle 문제를 완화하기 위해, 신뢰도 $S(P)$를 기준으로 정렬된 textual relational paths $t_P$를 프롬프트에 배치함. 최종 프롬프트는 쿼리와 신뢰도가 낮은 경로에서 높은 경로 순으로 연결된 구조를 가짐:
   $M(q; R(q, G)) = \text{concat}([q; t_{P_K}; \dots; t_{P_1}])$

실험
총 6개의 데이터셋(Legal, History, Biology, Mix, SQuALITY, SummScreen)을 활용하여 성능을 검증함. 기존의 NaiveRAG, HyDE, G-retriever, HippoRAG, GraphRAG, LightRAG와 비교 실험을 수행함. 평가는 Comprehensiveness, Diversity, Logicality, Relevance, Coherence의 5가지 차원에서 win rate를 측정함. 또한 SQuALITY 데이터셋에 대해서는 BLEU, ROUGE, METEOR 지표를 추가로 측정함.

결과

• 성능 우위: PathRAG는 6개 데이터셋 전반에서 기존 SOTA 모델들을 일관되게 능가하며, 특히 GraphRAG 대비 평균 59.93%, LightRAG 대비 57.09%의 win rate를 기록함.
• ablation 연구: Path-based prompting 형식이 flat한 구조보다 우수함을 증명했고, flow-based pruning과 신뢰도 기반 경로 정렬이 성능 향상에 필수적임을 확인함.
• 강건성: 그래프의 Sparsity가 높아지는 상황에서도 PathRAG는 다른 방법론 대비 높은 성능 유지력을 보임.
• 효율성: 토큰 소비량을 약 13.69% 절감하면서도 성능은 향상시켰으며, 더 가벼운 버전인 PathRAG-lt는 LightRAG와 유사한 성능을 훨씬 적은 토큰 비용으로 달성함.

결론
PathRAG는 복잡한 graph-based 정보를 핵심적인 relational paths로 압축하여 검색 효율과 응답 품질을 동시에 개선한 혁신적인 프레임워크임. 향후 indexing graph 구성 방식의 최적화와 더 다양한 구조적 표현 방식에 대한 연구가 기대됨.