[Paper Review] Retrieval-Augmented Generation with Hierarchical Knowledge

Retrieval-Augmented Generation with Hierarchical Knowledge

 

---

 

 

0. Abstract

그래프 기반의 RAG 방식은 특정 도메인 태스크에서 LLMs의 엄청난 성능 향상을 가져왔습니다.

그러나, 기존 RAG 방법들은 인간 사고의 계층적 지식을 적절히 활용하지 못해 RAG 시스템의 능력을 제한했습니다. 해당 논문에서는, indexing과 retireval 단계에서의 의미적 이해와 구조를 캡처하여 계층적 지식을 활용하는 HiRAG를 제안합니다. 실험을 통해 HiRAG는 기존 베이스라인 모델 대비 SOTA 성능을 달성했습니다.

 

 

1. Introduction

Naive RAG는 관련된 청크를 통해 ‘Hallucination’ 문제를 줄이는데 도움을 줬습니다. 하지만 관련 청크 안에서의 엔티티간의 관계만을 본다는 한계가 존재했습니다.

이 한계를 해결하기 위해, input document를 지식 그래프로 구축하여 엔티티간의 관계를 파악하는 RAG 시스템이 제안되었습니다. 이 방법은 다양한 태스크에서 좋은 성능을 내지만 여전히 심각한 한계점들이 존재합니다. GraphRAG는 Leiden 알고리즘을 이용한 커뮤니티 인덱싱을 활용했지만, 이 커뮤니티가 오직 지식그래프 내의 구조적 유사성만 이용했습니다. KAG는 정보와 지식을 계층적으로 표현했지만, 일반적 태스크에 대한 확장성이 부족하며 전문가의 수동적 표기가 필요했습니다. LightRAG는 지역적과 전역적의 2가지 접근방식을 활용했지만, 로컬과 글로벌의 knoewledge gap을 무시했습니다.

기존 RAG 시스템이 가진 2가지 핵심 문제에 주목했습니다.

(1) 의미론적 유사성을 가진 엔티티들간의 구조적 거리

(2) 지역적 지식과 전역적 지식 간의 knowledge gap

 

이를 해결하기 위해 HiRAG(계층적 지식을 이용한 RAG)를 제안합니다.

HiRAG는 인덱싱과 검색 단계를 통해 계층적 지식을 통합합니다.

(1)번 문제를 해결하기 위한 Indexing with Hierarchical Kneowledge(HiIndex)를 소개합니다. 간단히 구축되는 평면의 KG와 달리, 층층마다 계층적으로 구성된 KG를 구축합니다. 더 높은 층일수록 아래 층의 엔티티들의 군집을 요약합니다.

(2)번 문제를 해결하기 위한 Retrieval with Hierarchical Knowledge(HiRetrieval)를 소개합니다. 지역적 지식의 엔티티 설명과 전역적 지식의 커뮤니티를 연결함으로써 지식층의 분산을 해결합니다. global level, bridge level, and local level의 3가지 레벨을 LLM에서 제공하여 좀 더 포괄적이고 정확한 응답을 돕습니다.

 

 

2. The HiRAG Framework

크게 2개의 모듈로 구성 : HiIndex와 HiRetireval

HiIndex는 각 층마다의 계층적 KG 구축

HiRetireval은 각 커뮤니티에서 가장 관련된 엔티티들을 찾고 이것들의 최단경로를 연결합니다.

이를 통해 LLM이 3가지 레벨의 지식을 통해 답변을 생성합니다.

 

2.1 Indexing with Hierarchical Knowledge

 

우선, 기본적인 KG를 만들기 위해 입력 문서에서 엔티티 중심 트리플을 추출합니다. 특히, 문서를 청크를 쪼갤 때 중복되는 부분이 존재하게 합니다. 그리고 LLM에게 잘 짜여진 프롬프트와 함께 전달합니다. LLM은 문서 청크를 통해 각 쌍간의 엣지(릴레이션)을 생성합니다.

이런 KG는 0번째 층 KG가 됩니다. 각 층의 임베딩을 가지고 와서 GMM(Gaussian Mixture Models)을 통해 의미론적 클러스터링을 취합니다.

GMM을 통한 클러스터링 후에, LLM에게 C_{i-1}을 주고 i번째 층의 요약 엔티티를 만듭니다. 그리고 L_{i-1}과 L_{i} 사이의 릴레이션을 입실론_i라고 표기합니다.

 

L_i번째 층의 요약 엔티티들을 생성하기 위해, 메타 요약 엔티티 집합 X를 같이 주어 요약 엔티티 생성합니다.

X 예시) “조직”, “사람”, “장소”, 사건”, “기술” 등

X 예시) 빅데이터나 AI를 요약할 때 “기술”을 활용

이런 X는 윗층에 더해지지만, 계층적 KG의 실제 일부는 아닙니다.

 

커뮤니티 P 집합을 계산할떄 Leiden 알고리즘을 사용합니다. 각 커뮤니티가 여러층의 엔티티를 포함하고 있을 수도 있고 엔티티가 여러 커뮤니티를 나타내고 있을 수도 있습니다.

각 커뮤니티 p에서, LLM을 통해 의미적 리포트를 생성합니다. 윗 층의 엔티티는 시멘틱 허브로써 연관된 엔티티들을 거리에 관계없이 함축합니다.

 

 

2.2 Retrieval with Hierarchical Knowledge

 

local-level knowledge를 검색하기 위해, top-n개의 가장 관련된 엔티티를 추출합니다. 유저 쿼리와 엔티티 사이의 의미적 유사성을 측정합니다. (n = 20, default)

 

global-level knowledge를 검색하기 위해, 검색된 엔티티와 연결된 커뮤니티를 찾습니다.

그런 다음 쿼리와 관련된 대략적인 지식을 나타내는 커뮤니티 리포트를 찾습니다.

 

찾은 지역적 지식과 전역적 지식의 knowledge gap을 연결하기 위해서는, 찾은 커뮤니티들을 연결하는 reasoning path R을 찾습니다. 각 커뮤니티로부터, top-m개의 연관된 중요 엔티티를 고릅니다. Reasoning path R 집합은 중요 엔티티들의 최단경로로 정의합니다. R을 기반으로, 우리는 서브그래프 R^을 만듭니다. 이런 서브그래프는 지역적 엔티티 지식과 전역적 커뮤니티 지식을 가지고 있습니다.

 

이렇게 3단계의 계층적 지식을 찾은 후에, LLM에게 이것들을 문맥으로 제공합여 포괄적인 답변을 생성합니다.

 

 

3. Experimental Evaluation

Baseline

• NaiveRAG, GraphRAG, LightRAG, FastGraphRAG, KAG

Datasets and Queries

• 4 datasets from UltraDomain benchmark

LLM

• DeepSeek-V3 → 정보추출, 엔티티 요약, 정답생성
• GLM-4-Plus → 벡터 검색 임베딩, 의미적 클러스터링
  • 딥시크가 제공하지 않아서 사용

 

3.1 전반적인 성능 비교

• 평가지표 : win rate, LLM(GPT-4o)을 통해 다른 방법들보다 답변 품질이 높은지 비교하는 지표
• 4가지 차원에서 평가
  1. Comprehensiveness (포괄성)
     • 질문을 얼마나 철저하게, 다양한 측면에서 다뤘는가?
  2. Empowerment (실행력 제공)
     • 사용자가 실질적 행동을 취할 수 있도록 유용한 정보나 솔루션을 제시했는가?
  3. Diversity (다양성)
     • 다양한 관점, 접근 방식, 해결책을 얼마나 잘 반영했는가?
  4. Overall (종합적 품질)
     • 위 세 항목을 종합하여 전체적인 응답 품질은 어떤가?
  이 기준들은 단순한 정답 일치(EM, F1)를 넘어서 LLM 기반 생성 응답의 실용성과 다양성, 종합성을 평가하기 위한 기준.
• 평가결과
  • HiRAG가 다른 베이스라인보다 4개의 데이터셋과 4개 차원의 지표에서 월등한 성능

 

3.2 계층적 KG vs Flat KG

• w/o HiIndex의 거의 모든 케이스에서 성능이 떨어짐.
• HiIndex가 답변 품질에 중요한 역할을 한다는 것을 시사
• 유사한 엔티티 사이를 의미론적 연결성을 강화.
• w/o HiIndex가 다른 베이스라인들보다 성능이 좋은 것을 통해 HiRetrieval이 flat KG에서도 효과

 

3.3 HiRetrieval vs Gapped Knowledge

• w/o Bridge : knowledge gap이 존재하여 win rate가 떨어짐.

 

3.4 Determining the Number of Layers

• HiIndex의 가장 중요한 것 중에 하나는 층의 개수를 결정하는 것.
• 이것에 따라 각 층에 클러스터의 품질이 달라지기 때문.
• cluster sparsity를 활용해 품질을 평가.
• 층 개수가 커질수록 cluster sparsity가 커지고 안정화.

 

 

 

3.5 효율성과 비용 분석

• 토큰수와 API calls를 분석
  • 인덱스 단계에서는 오프라인이기 때문에 7.55USD 발생.
• 검색 단계에서는 쿼리당 평균 비용을 계산했는데, 다른 베이스라인과 달리 토큰이 들지 않음.
  → HiRAG의 온라인 검색방법이 더 효율적.

 

 

 3.6 Ablation Study

다른 데이터셋 평가

 

•HiRAG가 다른 방법들보다 높음

•HiRAG가 포괄적이면서 더 정확한 답변을 생성함을 시사

 

 

4. Limitation

1. 고품질의 계층적 KG을 구축하기 위해서는 상당한 토큰소비와 time overhead를 일으킴
   1. 최근 LLM의 발전으로 토큰 사용에 대한 부담을 점점 줄어들고 있음
   2. 그러므로 병렬적 인덱싱 과정을 통해 인덱싱 시간을 줄이는 것을 고려 필요
2. 검색단계에서 더 정교한 query-aware ranking 메커니즘이 필요
   1. 현재 LLM이 생성하는 순위 가중치를 사용하고 있어 쿼리 관련성에 영향을 받음.
   2. 좀 더 효과적인 순위 메커니즘 필요

 

 

 

---

 

 

Insight

해당 논문을 통해 계층적 구조를 통한 Knowledge Graph Construction의 긍정적 영향을 볼 수 있었습니다. 

 

하지만, 타 논문에서처럼 평가 데이터셋의 특성에 따라 결과 차이가 나는 것을 확인했습니다. 이렇게 때문에 성능의 신뢰성을 위해서는 다양한 성능 평가를 통해 결과의 타당성을 가지는게 중요합니다.

이 논문과 함께 ArchRAG 논문과 비교분석했습니다. 두 방법론 모두 클러스터링(커뮤니티 구성)을 통해 계층을 표현했습니다. ArchRAG – weighted Leiden(그래프 기반), HiRAG - GMM(확률 기반)으로 클러스터링 방법의 차이가 존재했는데, HiRAG의 임베딩을 통한 클러스터링이 효율성 측면에서 더 효과적인 방법이라고 생각합니다. 또한, 계층적 구조 설계 때문에 KGC 단계에서의 토근과 시간 비용이 크다는 점은 같습니다. ArchRAG 논문에서는 KGC 단계에서의 비용은 크지만, 검색 단계에서의 비용이 효율적이기 때문에 계층적 구조 설계가 긍정적이라고 말하고 있습니다. 저 또한 이 부분에 일부 동의합니다. 

이렇게 찾은 정보를 어떻게 LLM에게 전달하냐 역시 성능에 큰 영향을 줄 것 입니다. HiRAG는 3 level의 정보를 단순히 제공했지만, 이 부분을 개선하면 더 좋은 성능이 나올 수 있다고 생각합니다. 예를들어 reranking을 통해 재가공하거나 유사도 외의 요소를 같이 반영하여 연관성을 판단하는 것입니다.

multi-hop reasoning과 GraphRAG에서 KGC는 성능을 높이는 시작점입니다. 인풋이 좋아야 검색 성능 역시 기대해볼 수 있기에 이 부분에 대한 연구의 필요성이 있습니다.