PRoH: Dynamic Planning and Reasoning over Knowledge Hypergraphs for Retrieval-Augmented Generation

1. 문제 정의 (Problem)

대형 언어 모델 (LLM) 의 사실적 정확도를 높이기 위해 외부 지식을 활용하는 검색 증강 생성 (RAG) 이 중요한 기술로 부상했습니다. 특히 복잡한 추론이 필요한 멀티홉 질문 답변 (Multi-hop QA) 과 관련하여, 기존 지식 그래프 (KG) 기반 RAG 는 다음과 같은 한계를 겪고 있습니다.

• 이진 관계의 한계: 기존 KG 는 두 개 엔티티 간의 관계 (이진 관계) 만 표현합니다. 그러나 실제 세계의 지식은 3 개 이상의 엔티티가 관여하는 n-ary 관계 (예: "게임 A 는 회사 B 와 C 의 첫 번째 협업이다") 를 많이 포함합니다. 이를 이진 간선으로 분해하면 중요한 구조적, 의미적 정보가 손실됩니다.
• 지식 하이퍼그래프 (KH) 의 미활용: n-ary 관계를 자연스럽게 표현할 수 있는 지식 하이퍼그래프 (Knowledge Hypergraphs, KH) 가 제안되었으나, 기존 KH 기반 RAG 방법론들은 다음과 같은 세 가지 주요 결함을 가집니다.
  1. 정적 검색 계획 (Static Retrieval Planning): 쿼리나 그래프 컨텍스트에 관계없이 고정된 검색 파이프라인을 사용합니다.
  2. 비적응형 검색 실행 (Non-Adaptive Retrieval Execution): 중간 추론 결과를 반영하지 않는 일회성 (one-shot) 검색에 의존합니다.
  3. 표면적인 구조 활용: 하이퍼에지를 단순한 링크로만 취급하여, 하이퍼에지에 내재된 풍부한 관계적 의미 (semantics) 를 충분히 활용하지 못합니다.

2. 방법론 (Methodology)

저자들은 이러한 한계를 극복하기 위해 PRoH (Dynamic Planning and Reasoning over Knowledge Hypergraphs) 라는 새로운 동적 RAG 프레임워크를 제안합니다. PRoH 는 하이퍼그래프 위에서 구조화된 계획과 추론을 수행하며, 크게 4 단계로 구성됩니다.

2.1 그래프 앵커링 (Graph Anchoring)

• 하이퍼그래프 구축 및 인덱싱: 텍스트에서 엔티티와 n-ary 관계를 추출하여 KH 를 구축합니다.
• 동의어 하이퍼에지 증강: 기존 방법의 단점인 엔티티 이름의 정확한 매칭 의존성을 보완하기 위해, 임베딩 유사도를 기반으로 동의어 엔티티들을 연결하는 '동의어 하이퍼에지'를 추가하여 그래프의 연결성을 강화합니다.
• 질문 서브그래프 구성: 입력 질문에 대한 토픽 엔티티와 타겟 하이퍼에지를 식별하고, 이를 시드 (seed) 로 하여 관련 하위 그래프를 구성합니다.

2.2 계획 (Planning)

• 컨텍스트 인식 계획 (Context-aware Planning): 질문을 바로 분해하는 대신, 먼저 질문과 관련된 KH 의 국소 이웃 (local neighborhood) 을 스케치하여 '계획 컨텍스트 그래프'를 생성합니다. 이는 LLM 이 그래프의 토폴로지와 의미적 범위를 인지하게 하여, 실행 가능한 추론 계획을 수립하도록 돕습니다.
• 구조화된 질문 분해 및 DAG 구성: 생성된 계획은 단순한 시퀀스가 아닌, 하위 질문 간의 의존성을 표현하는 방향 비순환 그래프 (DAG) 로 변환됩니다. 이는 하위 질문의 논리적 순서를 명확히 합니다.

2.3 추론 (Reasoning)

• 상태 공간 탐색 (State-Space Search): PRoH 는 추론 과정을 DFS(깊이 우선 탐색) 기반의 상태 공간 탐색으로 모델링합니다.
  • 동적 DAG 정제: 현재 상태 (DAG) 에서 해결된 하위 질문의 답변을 바탕으로 DAG 를 반복적으로 정제 (refine) 하고, 새로운 하위 질문이나 의존성이 발생할 경우 DAG 를 확장합니다.
  • 다중 경로 탐색: 각 하위 질문에 대해 단일 정답이 아닌 여러 후보 답안 (Answer-Path Pairs) 을 허용하여, n-ary 관계의 모호성을 처리하고 국소적 오류에서 복구할 수 있도록 합니다.

2.4 답변 및 경로 검색 (Answer and Path Retrieval)

• EWO 기반 탐색 (Entity-Weighted Overlap): 하이퍼그래프의 핵심 혁신입니다. 기존 그래프와 달리 하이퍼에지는 여러 엔티티를 공유할 수 있습니다. PRoH 는 인접한 하이퍼에지 간의 엔티티 가중 중첩 (EWO) 점수를 계산하여 탐색 방향을 결정합니다.
  • 단순히 공유된 엔티티의 수만 세는 것이 아니라, 각 엔티티가 현재 하위 질문 해결에 얼마나 의미적으로 기여하는지를 LLM 과 임베딩을 통해 평가합니다.
  • 이를 통해 의미적으로 일관된 하이퍼에지 경로를 우선적으로 탐색하게 됩니다.
• 최종 답변 생성: 완성된 DAG 들에서 수집된 지식과 추론 경로를 바탕으로 LLM 이 최종 답변을 생성하고, 평가 에이전트가 일관성을 검증합니다.

3. 주요 기여 (Key Contributions)

1. PRoH 프레임워크 제안: 멀티홉 질문 답변을 위해 하이퍼그래프의 표현력을 완전히 활용하는 동적 RAG 프레임워크를 최초로 제안했습니다.
2. 컨텍스트 인식 계획 메커니즘: KH 의 구조를 스케치하여 LLM 이 그래프 지식과 정렬된 실행 가능한 추론 계획을 생성하도록 합니다.
3. EWO 기반 정밀 탐색 전략: 하이퍼그래프의 n-ary 관계 특성을 반영한 엔티티 가중 중첩 (EWO) 점수를 도입하여, 의미적 흐름에 기반한 정밀한 경로 탐색을 가능하게 했습니다.
4. 동적 DAG 기반 추론: 하위 질문을 선형이 아닌 DAG 로 표현하고, 중간 추론 결과를 반영하여 DAG 를 동적으로 정제하는 반복적 추론 메커니즘을 도입했습니다.

4. 실험 결과 (Results)

다양한 도메인 (의학, 농업, 컴퓨터 과학, 법률, 혼합) 에서의 실험을 통해 PRoH 의 성능을 검증했습니다.

• SOTA 성능 달성: 이전 최첨단 모델인 HyperGraphRAG 를 평균 F1 점수 19.73% 및 생성 평가 (G-E) 점수 8.41% 이상 상회하는 성능을 기록했습니다. 특히 CS 도메인에서는 F1 점수가 22.85% 까지 향상되었습니다.
• 장거리 멀티홉 추론: 3~6 홉 (hop) 에 달하는 장거리 질문에서도 강력한 성능을 유지하며, HyperGraphRAG 대비 평균 F1 26.68% 향상 효과를 보였습니다.
• 강건성 (Robustness): 지식 조각의 길이가 길어지거나 (Long-range), 엔티티 수가 증가하는 복잡한 상황에서도 성능이 안정적으로 유지됨을 확인했습니다.
• 효율성: PRoH-L(가벼운 버전) 은 토큰 사용량을 크게 줄이면서도 (최대 34.82% 절감) 경쟁력 있는 성능을 유지하여 비용 효율성을 입증했습니다.
• Ablation Study: EWO 가이드, 동의어 병합, 계획 컨텍스트 등 각 모듈이 제거될 때 성능이 크게 저하됨을 확인하여, 모든 구성 요소의 상호 보완적 기여를 입증했습니다.

5. 의의 및 결론 (Significance)

PRoH 는 RAG 시스템이 단순한 텍스트 검색을 넘어, 복잡한 n-ary 관계를 가진 구조화된 지식을 효과적으로 추론할 수 있는 새로운 패러다임을 제시합니다.

• 하이퍼그래프의 잠재력 실현: 기존 이진 관계 중심의 접근법을 넘어, 하이퍼그래프가 가진 고차원적 관계 표현의 이점을 RAG 에 성공적으로 접목시켰습니다.
• 적응형 추론: 정적인 검색에서 동적이고 반복적인 계획 및 추론으로의 전환을 통해, LLM 이 그래프 구조를 깊이 있게 이해하고 복잡한 문제를 해결하는 능력을 극대화했습니다.
• 해석 가능성: EWO 기반의 경로 탐색과 DAG 기반의 추론 과정을 통해, 모델이 어떻게 답변에 도달했는지 (추론 경로) 를 명확히 추적할 수 있어 해석 가능성 (Interpretability) 을 높였습니다.

이 연구는 복잡한 지식 기반 질문 답변 시스템의 성능 한계를 돌파하고, 차세대 RAG 시스템 설계에 중요한 방향성을 제시한다는 점에서 학술적, 실용적 가치가 매우 높습니다.