[논문리뷰] THINK-ON-GRAPH 2.0: DEEP AND FAITHFUL LARGELANGUAGE MODEL REASONING WITH KNOWLEDGEGUIDED RETRIEVAL AUGMENTED GENERATION

DeepLearing/NLP(LLM)

[논문리뷰] THINK-ON-GRAPH 2.0: DEEP AND FAITHFUL LARGELANGUAGE MODEL REASONING WITH KNOWLEDGEGUIDED RETRIEVAL AUGMENTED GENERATION

notdecidedyet 2024. 11. 26. 19:54

0. Abstract

연구 배경과 문제점
- RAG는 LLM의 지식 부족을 극복하는데 도움을 줌
- 하지만 현재 RAG 방법들은 복잡한 추론에 필요한 정보의 깊이와 완전성이 부족
제안 모델: Think-on-Graph 2.0 (ToG-2)
- hybrid RAG 프레임워크, 비정형 및 정형 지식 소스를 tight-coupling 방식으로 활용
- 작동 방식:
  - KG를 통해 entity 기반으로 문서 연결
  - 문서를 entity context로 활용
  - Graph retrieval과 context retrieval을 번갈아가며 수행
- 장점 :
  - 검색 프로세스의 긴밀한 결합 : Context retrieval을 KG로 강화, Context 기반의 신뢰성 있는 graph retrieval 가능
  - 강화된 추론 능력 : Context와 KG 간 반복적 knowledge retrieval, 깊이 있고 신뢰할 수 있는 LLM 추론 달성
  - 실용적 : Training Free 다양한 곳에서 호환 가능

1. Introduction

연구 배경과 문제점
- 현재 RAG의 한계
  - LLM이 복잡한 작업에서 인간과 같은 추론 경로 유지 어려움, 단편화된 정보와 구조적 관계 통합에 지속적 노력 필요
- 기존 Text-based RAG의 한계
  - 주로 vector retrieval에 의존
  - 구조화된 관계 포착 어려움 (Figure 1a의 Crig Virgin과 Verzbicas의 구조적 관계를 간과)
  - Entity 간 knowledge-level 연관성 간과 (예: "Global Financial Crisis"와 "The 2008 Recession")
  - 다단계 추론과 논리적 연결 추적 부적합
- 기존 KG-based RAG의 한계
  - 장점 : 트리플 형태로 정보를 저정하고, 엔티티간의 구조적 관계를 설립하여 관계를 구조화 하는데 효과적임.
    -> High-level 개념과 관계를 구조화 하는데 효과적임
  - 단점: 내부 불완전성 존재, Out of distribution를 벗어난 정보 부족, 상세한 정보 제공 한계
    -> Figure 1(b)의 Lukas Verzbicas의 경기 기록에 대한 상세한 정보를 제공할 수 없음.
- 기존 Hybrid 접근방식(KG+Text)의 한계
  - 설명 : 텍스트 기반 KG + RAG시스템을 통합하는 연구들이 있음.
    -> 정형 및 비정형 지식 source에서 검색된 정보를통해 LLM이 질문을 답하도록 프롬프팅에 통합
  - (Figure 1(c))느슨한 결합으로 인한 한계, 한 지식 소스의 검색 결과를 다른 소스로 개선 못함, 복잡한 쿼리 처리 한계
    -> 느슨한 결합 : 단순히 KG와 텍스트 데이터를 병렬적으로 사용.
    -> 한 지식 소스의 검색 결과를 다른 소스로 개선 못함 : KG에서 찾은 구조화 관계를 텍스트 검색에 활용하지 못함(vise versa)
제안하는 솔루션 : ToG-2 (Figure 1d)
- 작동 방식
  - 질문에서 topic entity 추출로 시작
  - KG에서 relation retrieval 수행
  - 후보 entity 관련 텍스트 검색
  - Context retrieval 결과로 후보 entity 정리
  - LLM 프롬프팅으로 답변 생성 또는 추가 검색

2. Related Works

Text-based RAG : Query <-> Text간의 의미적 유사성 기반 정보 검색
- 한계 :
  - retrieve텍스트 간 심층적 관계 포착 어려움( Retrieve document들을 독립적으로 보게 됨)
  - retrieve텍스트 간 중복된 내용이 포함될 수 있음.
- 극복 하려했던 연구:(ITER-RETGEN: 검색과 생성을 반복적으로 병합), (Trivedi et al.: RAG와 Chain of Thought(CoT) 결합
KG-based RAG :
- 초기 접근 : KG지식을 LLM의 neural network에 직접 임베딩
- 최근 접근 : KG를 외부 보강 도구로 활용함., 구조화된 지식을 텍스트 프롬프트로 변환(tiplet -> 자연어)
- 한계점 : KG의 지식 불완전성, 상세한 맥락 정보들이 사라짐
Hybrid RAG :
- 연구
  - Chain-of-Knowledge(CoK) : LLM 출력의 grounding(지식 맵핑, 검증) 강화
  - GraphRAG : 문서에서 KG를 구축하고, KG-enhanced text retrieval을 함
  - HybridRAG : vector데이터 베이스와 KG 모두에서 정보를 검색
- 한계
  - 기존 Hybrid는 단순히 KG와 텍스트에서 검색한 정보를 집계할 뿐, 한 지식 소스에서 검색된 결과를 다른 소스를 통해 개선하지는 않음.

해당 연구는 KG-based RAG와 Text-based RAG방법을 긴밀하게 결합하여 심층적인 context retrieval과 정확한 Graph retrieval을 모두 가능하게 하여 Complex reasoning성능을 향상 시키는 것을 목표로 함.

3. Methodology

ToG-2는 ToG 접근 방식을 차용
- 쿼리에서 식별된 주요 entity들에서 시작. LLM + prompt를 통해 entity와 관계를 추출하고, entity기반으로 외부 탐색
- ToG-2는 triple 기반의 논리적 체인 확장 :
  - knowledge-guided context retrieval : KG에서 발견된 것으로 관련문서를 더 정확하게 검색
  - context-enhance graph retrieval : 검색된 텍스트 문석의 맥락 정보로 다시 KG탐색을 함
구체적으로...
- 주어진 질문에서 entity들을 추출, 초기 topic entity 시작
- graph retrieval, context retrieval, LLM reasoning의 반복 프로세스를 수행
  - 각 반복의 시작에서 KG에서 현재 topic entity들과 인접한 entity들을 선택적으로 탐색 -> 검색 범위를 한정
  - ToG-2는 쿼리와 관련 문서에서 검색된 맥락 지식을 기반으로 entity들의 순위를 매기
  - LLM은 triple 경로와 entity 컨텍스트를 포함한 이종의 지식을 활용하여 질문에 답
  - 수집된 정보가 불충분한 경우 추가 검색 진행.

3.1 INITIALIZATION

Entity 식별 및 연결 :
1. 입력 : query
2. 실행 : query에서 LLM을 통해 entity들을 식별하고 KG의 entity들과 연결
  Query : Where was one of the runners born who almost broke Crag Virgin's Illinois Boys Cross Country record?
Topic Prune(TP) :
1. KG에서 탐색을 시작하기에 적합한 entity들을 선택
  (LLM이 q와 추출된 entity들을 평가하여 topic entity $E^0_{topic} = {e_1, e_2, ..., e_N}$ 을 선택 - N개)
  
  Crag Virgin's(o) Illinois(o) Cross Country(x) <- $E^0_{topic}$
  여기서 0은 몇번 째 iteration인지를 의미함
초기 문서 검색 :
1. 입력 : 선택된 Topic entitiy
2. 방법 : dense retrieval model사용하여, $E_0_{topic}$와 관련된 문서에서 상위 K개의 chunk 추출.
  Cosin Sim과 같은 방법을 사용해서 Crag Virgin's, Illinois와 관련된 문서들을 추출
평가 : 추출된 정보가 충분한지 평가 -> 충분하면 프로세스 종료

3.2 Hybrid knowledge exploration

다른 지식을 어떻게 긴밀하게 조화시키는지 설명 (Triplet, Document).
다른 지식이라 하면 (그래프 구조 & Dense Retrieve Document)

Formula :

$E^i_{topic}$ : i번째 반복에서 topic entity들의 집합 {$e^i_1, e^i_2, ..., e^i_j$}
$P^{i-1}$ : i번째 반복 직전의 triple path 집합 $P^{i-1}$ = {$P^{i-1}_1, P^{i-1}_2, ..., P^{i-1}_j$}
- $P^{i-1}_j$ = {$p^0_j, p^1_j, ..., p^{i-1}_j$}로 표시 가능
- $j \in [1, W]$ : W는 각 반복에서 유지되는 topic entity들의 최대수를 나타내는 exploration width
  -> 최고로 좋은 entity W개만을 추출
- $p^{i-1}_j$ : 단일 triple $(e^{i-1}_j, r^{i-1}_j, e^i_j)$
  i-1 번째 entity로 i번째 entity로 연결하는 구조
- $r^{i-1}$ : $e^{i-1}$와 $e^i_j$ 사이의 관계(양방향 가능)
더보기
초기 단계 (i = 0):
- $E^0_{topic}$ = {"Craig Virgin", "Illinois"}
- $P^0$ = {} (비어있음)

첫 번째 반복 (i = 1):
Topic entity "Craig Virgin"으로부터:
- $e^1_1$ = "Lebanon High School"
- $e^1_2$ = "1984 Summer Olympics"
- $P^1_1$ = {(Craig Virgin, attended_at, Lebanon High School)}
- $P^1_2$ = {(Craig Virgin, participated_in, 1984 Summer Olympics)}
두 번째 반복 (i = 2):
- 이전 단계에서 발견된 entity들을 기반으로:
  - $e^2_1$ = "IHSA"
  - $P^2_1$ = {(Craig Virgin, attended_at, Lebanon High School), (Lebanon High School, member of, IHSA)}

3.2.1 Knowledge-guided graph search

KG의 풍부한 구조적 연결성을 활용하여, graph search는 semantic 공간에서 서로 멀어 보이는 질문과 타겟팅하는 정보 사이의 high-level 개념과 관계를 탐색.
Relation Discovery : i-th iteration에서 시작할 때, Edge함수를 통해 모든 관계를 찾음.
- $Edge(e^i_j)$ = {$(r^i_{j,m}, h_m) | h \in {True, False}$} (1)
  - Edge()는 entity들의 관계를 검색하는 함수
  - h는 해당 관계 $r^i_{j,m}$의 방향이 topic entity $e^i_j$를 가리키고 있는지를 나타냄
  - $e^i_j$ : initial에서 얻은 entity, 혹은 i-1번째에서 얻은 Topic entity들
  - Formula
    - m : 발견된 m번째 관계
    - j : j번째 topic entity
    - $e^i_j$ : i번쨰 iteration에서 topic entity
    - $r^i_{j,m}$ : i번쨰 iteration에서 topic entity를 포인팅하는지 관계 여부
  - 더보기
    개인적인 견해 : 논문에서는 Edge라는 함수로 관계가 유효한지 안한지 판단하나, 이는 Target정보도 들어가야 하는 것이 아닌가 싶다.
    
    초기 topic entity: "Craig Virgin" ($e^0_1$)
    
    Edge("Craig Virgin")의 결과:
    1. (place_of_birth, False): Craig Virgin -> place_of_birth -> Illinois
    2. (studied_at, False): Craig Virgin -> studied_at -> Lebanon High School
    3. (participated_in, False): Craig Virgin -> participated_in -> 1984 Summer Olympics
    4. (has student, True) : Lebanon High School -> has student -> Craig Virgin
    
    False : 역방향
    True : 정방향
Relation Prune : 수집된 관계 집합 ${Edge(e^i_j)}^W_{j=1}$에서, LLM에게 q를 해결하는 데 도움이 될것 같은 entity들 찾음.
구체적으로 점수를 매기도록 프롬프팅 : 2가지 방법 (Appendix E table 10, 11, 12)
- 수식 부연 설명
  - ${Edge(e^i_j)}^W_{j=1}$ : i번째 반복에서 후보가 되는 entity의 갯수(j)는 W개 이다.
- $PROMPT_{RP}(e^i_j, q, Edge(e^i_j))$ (2)
  - 여러번 API콜을 수행
    - 더보기
      단일 topic entity($e^i_j$)에 대해서, 관계가 있는 entity들을 개별로 API콜을 진행
      
      Call 1: PROMPT_RP("Craig Virgin", q, Edge("Craig Virgin"))
      Call 2: PROMPT_RP("Lebanon High School", q, Edge("Lebanon High School"))
      ...
- $PROMPT_{RP_(cmb)}(E^i_{topic}, q, {Edge(e^i_j)}^W_{j=1})$ (3)
  - 2번 식 보다 더 적은 API콜 진행.
    - 모든 topic entity들을 한번에 처리
    - 입력이 길어질 경우 LLM에게 부담이 될 수 있음.
    - 더보기
      PROMPT_RP_cmb(
        ["Craig Virgin", "Lebanon High School"],
        q,
        [Edge("Craig Virgin"), Edge("Lebanon High School")]
      )
Entity Discovery : LLM을 사용하는 것은 아니고, graph구조에서 연결된 정보를 사용.
- $E^i_{topic}$의 topic entity $e^i_j$와 그에 해당하는 $R^i$의 선택된 관계 $r^i_{j,m}$이 주어지면,
- 함수
  - $Tail(e^i_j,(r^i_{j,m}, h_m)) = c^i_{j,m}$ (4)
  - 관계 $(r^i_{j,m}, h_m)$를 통해 topic entity $e^i_j$와 연결된 entity들 ${c^i_{j,m}}$을 식별
  - formula :
    - $Tail$: 연결된 entity를 찾는 함수
    - $e^i_j$: i번째 반복에서의 j번째 topic entity
    - $r^i_{j,m}$: i번째 반복에서 j번째 entity의 m번째 관계
    - $h_m$: 관계의 방향을 나타내는 boolean 값 (True/False)
    - $c^i_{j,m}$: 찾은 entity
- Figure 2의 예에서, Craig Sandburg High School, Evan Jager는 Craig Sandburg High School 이후의 entity discovery에서 연결된 entity들임.
- 이후에 context-based entity prune 단계가 실행되어 모든 연결된 entity들 중에서 상위-W개의 entity들을 새로운 topic entity들 $E^{i+1}_{topic}$으로 선택함으로써 전체 graph retrieval 단계를 완료

정리하면!

Topic Entity: "Craig Virgin"
↓
Relation Discovery: 모든 관계와 방향성 찾기 (아무것도 제거하지 않음)
- (has_student, True): Lebanon High School -> has_student -> Craig Virgin
- (attended_by, True): 1984 Olympics -> attended_by -> Craig Virgin
- (born_in, False): Craig Virgin -> born_in -> Illinois
- (alumni_of, True): Lebanon High School -> alumni_of -> Craig Virgin
↓
Relation Prune: 질문에 관련 있는 관계 선택 (LLM이 유용성 평가)
- (has_student, True): 선택됨 (점수: 8/10) - 교육 경력 관련 정보
- (attended_by, True): 선택됨 (점수: 9/10) - 운동 선수 경력 정보
~~- (born_in, False): 선택되지 않음 (점수: 2/10) - 질문과 관련성 낮음~~
- (alumni_of, True): 선택됨 (점수: 7/10) - 교육 경력 관련 정보
↓
Entity Discovery: 선택된 관계들의 source entities 찾기
- has_student(True)를 통해: Lebanon High School 발견
- attended_by(True)를 통해: 1984 Olympics 발견
- alumni_of(True)를 통해: Lebanon High School 발견

3.2.2 KNOWLEDGE-GUIDED CONTEXT RETRIEVAL

ToG-2는 KG에서 추출한 high-level 지식을 바탕으로 세부적인 정보를 발굴
- 함수 4(Entity Discovery)를 통해 모든 후보 entity들을 얻으면, 각 후보 entity $c^i_{j,m}$와 관련된 문서들을 수집
- 현재 반복에 대한 후보 entity들의 context pool을 형성
- Figure 2의 예에서, 첫 번째 반복의 context pool은 Craig Sandburg High School, Evan Jager, Lebanon High School, 1984 Summer Olympics 등을 포함한 후보 entity들과 관련된 문서들을 포함
Entity-guided Context Retrieval:
- 후보 entity들의 문서 맥락 내에서 유용한 정보를 찾기
  - DRM을 적용하여 문단들의 관련성 점수를 계산
    DRM : Dense Retrieval Model
  - 후보 entity $c^i_{j,m}$의 현재 triple $Pc^i_{j,m} = (e^i_j, r^i_{j,m})$을 간단한 문장으로 변환 후 이를 가지고 점수를 계산
  - $c^i_{j,m}$의 z-번째 chunk의 관련성 점수를 다음과 같이 공식화:
    - $s^i_{j,m,z} = DRM(q, [triple$_$sentence(Pc^i_{j,m}) : chunk^i_{j,m,z}])$ (5)
  - 상위-K 점수를 받은 chunk들 $Ctx^i$가 추론 단계에서 참조하게 됨.
- 더보기
  예)
  
  질문(q): "Craig Virgin의 Illinois Boys Cross Country record를 누가 근접했나요?"
  - topic entity (e^i_j): Craig Virgin
  - relation (r^i_{j,m}): attended
  - candidate entity (c^i_{j,m}): Lebanon High School
  
  Triple을 문장으로 변환 :
  $Pc^i_{j,m}$ = (Craig Virgin, attended, Lebanon High School)
  ↓
  triple_sentence = "Craig Virgin attended Lebanon High School"
  
  문서 chunk예 :
  chunk^i_{j,m,z} = "Lebanon High School의 Lukas Verzbicas는 2011년 state meet에서 13:53.84의 기록을 세워 Craig Virgin의 14:07.2 기록에 근접했습니다."
  
  식 5) 관련성 점수 계산
  $s^i_{j,m,z}$ = DRM(
      q = "Craig Virgin의 Illinois Boys Cross Country record를 누가 근접했나요?",
      context = [
          "Craig Virgin attended Lebanon High School" :  // triple_sentence
          "Lebanon High School의 Lukas Verzbicas는 2011년 state meet에서 13:53.84의 기록을 세워 Craig Virgin의 14:07.2 기록에 근접했습니다."  // chunk
      ]
  )
  
  식 6) 가중치고려 Entity Prune
  예를 들어, K=3(상위 3개 chunk 고려)이고 α=0.5라고 가정하면:
  
  w1 = e^(-0.5 * 1) = 0.607  // 첫 번째 chunk의 가중치
  w2 = e^(-0.5 * 2) = 0.368  // 두 번째 chunk의 가중치
  w3 = e^(-0.5 * 3) = 0.223  // 세 번째 chunk의 가중치
  
  특정 entity 'Lebanon High School'에 대해:
  - chunk1 점수(s1) = 0.9, chunk가 해당 entity의 것임 (I=1)
  - chunk2 점수(s2) = 0.7, chunk가 해당 entity의 것임 (I=1)
  - chunk3 점수(s3) = 0.8, chunk가 다른 entity의 것임 (I=0)
  
  score(Lebanon High School)
  = (0.9 * 0.607 * 1) + (0.7 * 0.368 * 1) + (0.8 * 0.223 * 0)
  = 0.546 + 0.258 + 0
  = 0.804
Context-based Entity Prune :
- 후보 entity들의 선택 : contextual chunk들의 순위 점수를 기반으로 후보 선택
- 후보 entity $c^i_{j,m}$의 순위 점수는 상위-K에 가중치를 주어 계산이 된다. 수식은 아래와 같다.
  가중치는 지수적으로 감소하는 함수
  - $score(c^i_{j,m}) = \sum^K_{k=1} s_k \cdot w_k \cdot I$ (6)
    - $c^i_{j,m}$ : i번째 반복에서, j번째 topic entity와 연결된 m번째 후보 entity
    - $w_k = e^{-\alpha \cdot k}$ : weight decay
    - $s_k$ : k-번째로 순위가 매겨진 chunk 점수(entity-guided context retrieval에서 구한 점수)
    - I : k-번째 chunk가 $e^i_{j,m}$에 속하면 1이 되는 indicator 함수
    - i : iteration
    - j : topic entity의 인덱스
    - m : 각 topic entity와 연결된 관계/후보 entity의 인덱스
    - K와 α는 하이퍼파라미터

3.3 REASONING WITH HYBRID KNOWLEDGE

$Clues^{i-1}$ : 이전 반복에서 획득한 유용한 정보들.
- 이전 단계에서 발견한 중요한 정보 요약
- 다음 검색에 도움이 될 수 있는 핵심 정보
- 최종 답변으로 이어지는 중간 추론 과정들
- 더보기
  예)
  Question: "Creatfallen's artwork is done by photographer of which nationality?"
  
  Clues0: null
  
  Clues1: {the photographer who contributed to several Smashing Pumpkins videos and album art was Ukrainian photographer Yelena Yemchuk}
  
  Answer: {Ukrainian}
$PROMPT_{rs}(q,P^i, Ctx^i, Clues^{i-1}) = \begin{cases} Ans., & \text{if the knowledge is sufficient} \ Clues^i, & \text{otherwise} \end{cases}$ (7)
- 해당 정보를 바탕으로 query에 대답하기에 적절한지 판단
  Prompt는 Appendix E. Table 13,14
- 적절하지 않다고 판단하면, LLM에게 기존 지식들로 부터 유용한 정보들만 요약 -> $Clues^i$요약
- 정확한 정보를 기반으로 깊이 D에 도달할 때 까지 쿼리를 최적화 하도록 프롬프팅

4. Experiments

4.1 Dataset and Metrics

4.2 Baselines

LLM만 사용하는 방법들 :
1. Direct Reasoning
2. CoT
3. Self-Consistency
Vanilla RAG: entity 문서에서 직접 검색하는 RAG 방법
KG-based RAG : Think on Graph - KG기반 RAG
Chain of Knowledge : Wikipedia, Wikidata, Wikitable에서 지식을 검색하는 hybrid RAG
GraphRAG : 먼저 문서에서 KG구축

4.3 IMPLEMENTATION DETAILS

Model : GPT-3.5-turbo, GPT-4o, Llama3-8B, Qwen2-7B
Context Retrieval Model : BGE-embedding
K : entity prune에서는 entity 점수를 계산하기 위해 상위 10개(K = 10)
Temperature : 0.4(exploration), 0(inference)
W : 3
Depth : 3

4.4 Main Results

4.5 Ablation Study

4.5.1 Ablation of LLM backbones

To what extent do LLMs with varying capabilities benefit from the knowledge enhancement of ToG-2?
- 약한 추론능력을 갖는 Llama3-8B, Qwen2-7B는 강한 추론능력을 갖는 GPT-3.5-turbo 수준으로 끌어올림
- 강한 추론능력을 갖는 GPT-3.5-turbo, GPT-4o와 같은 LLM도 ToG-2를 통해 Knowledge reasoning작업에서 성능 더욱 향상시킬 수 있음.

4.5.2 Choices of Entity Pruning Tools

What kind of tools are most suitable for tight coupling graph-based knowledge and documentbased knowledge?(Figure 3)
- Figure 3a : (K=10고정) - 생성 기반/임베딩 기반 비슷한 성능을 보여줌, BM25도 준수한 성능을 보임.
- Figure 3b : (context수인 K 최적화)
  - BGE-Reranker : 긴 맥락에서 더 좋은 성능.
  - LLM : 긴 맥락에서 성능 저하

4.5.3 Width & Depth Settings

더 넓은 탐색 범위가 반드시 더 나은가?
너비(Width)의 영향
- 너비 2에서 3으로 증가 시 성능이 점진적으로 향상
- 너비 3을 초과하면 성능 향상의 한계 발생
깊이(Depth)의 영향
- 깊이 3을 초과하면 성능 향상이 정체
- 깊은 탐색이 반드시 더 나은 결과를 보장하지 않음

4.6 Runtime Analysis : 생략

4.7 Manual Analysis

ToG-2는 triple 링크와 맥락 정보를 어느 정도로 활용하는가?
- AdvHotpotQA 추론 결과 50개를 무작위로 선택하여 triple 링크 추론, 링크 내의 entity들의 맥락 정보가 정답에 어떻게 기여하는지에 대해 분석을 수행
- Doc-enhanced Answers(문서 강화 답변)가 약 42%로 가장 높은 비율을 차지하는 반면, Triple-enhanced Answers(triple 강화 답변)는 가장 적은 비율을 보임
  - 복잡한 QA 작업에서 텍스트 맥락이 가장 중요한 정보 소스임을 나타냄. Triple 링크만으로는 상세한 맥락이 부족하여 더 깊은 통찰을 제공하기 어려움.