[논문리뷰]Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning

Luo, L., Li, Y., Haffari, G., & Pan, S. (2023, October 2). Reasoning on graphs: Faithful and interpretable large language model reasoning. arXiv.org. https://arxiv.org/abs/2310.01061

Problem Statement

최신 지식의 부족과 환각 문제 (Lack of Up-to-Date Knowledge and Hallucinations)
LLM은 복잡한 작업에서 인상적인 추론 능력을 보여주지만, 최신 지식이 부족하고 추론 중에 환각을 경험할 수 있다. 이는 잘못된 추론 과정으로 이어져 성능과 신뢰성을 떨어뜨릴 수 있다.​

구조적 정보의 중요성 간과 (Overlooking the Importance of Structural Information)
기존의 KG 기반 LLM 추론 방법은 KG를 사실적 지식 기반으로만 취급하고, 추론을 위한 구조적 정보의 중요성을 간과한다. 이는 KG의 관계 경로가 제공하는 의미론적 연결을 충분히 활용하지 못하게 한다.​

비실행 가능성 문제 (Non-Executable Queries)
Semantic Parsing 방법은 논리적 쿼리를 생성하여 KG에서 답변을 얻지만, 생성된 논리적 쿼리가 실행 불가능한 경우가 많아 답변을 얻지 못할 수 있다. 이는 구문 및 의미적 제한 때문에 발생할 수 있다.​

구조적 정보의 부족으로 인한 문제 (Issues Due to Lack of Structural Information)
Retrieval-augmented 방법은 KG에서 사실을 검색하여 LLM의 추론 성능을 향상시키지만, 이러한 방법들은 KG를 사실적 지식 기반으로만 취급하고, 추론을 위한 KG의 구조적 정보를 간과한다. 예를 들어, 관계 경로가 중요한 의미론적 연결을 제공할 수 있음에도 불구하고 이를 충분히 활용하지 못한다​.

Related Work

LLM Reasoning Prompt

• 이 연구는 prompt engineering으로 불리며, LLM의 fine-tuning 없이 주어진 프롬프트를 통해 모델이 복잡한 추론 작업을 수행하도록 하는 것이다. 주로 LLM에게 계획을 생성하게 하거나, 추론 단계를 세분화하도록 하여, 일련의 하위 작업으로 나누어 해결하는 방식이다. 이를 통해 최신 지식을 반영하고, 신뢰할 수 있는 추론을 수행할 수 있다. 예를 들어, Chain-of-Thought (CoT), Tree of Thoughts (ToT), Plan-and-Solve, ReACT등이 연구들이 있다.

Knowledge Graph Question Answering(KGQA)

• Embedding-based Methods
  • 엔티티와 관계를 임베딩 공간에서 모델링하고 특별한 모델 구조를 설계하여 답변을 추론한다.
  • KV-Mem, EmbedKGQA, NSM, QA-GNN, Greaselm.
• Retrieval-augmented Methods
  • KG에서 관련 사실을 검색하여 추론 성능을 향상시킨다. 초기 연구들은 페이지 랭크(Page Rank)나 랜덤 워크(Random Walk) 알고리즘을 사용하여 서브그래프(subgraph)를 검색한다.
  • GraftNet, PullNet, SR+NSM, UniKGQA.
• Semantic Parsing Methods
  • 질문을 구조적 쿼리(e.g., SPARQL)로 구문 분석하여 쿼리 엔진이 답변을 얻도록 합니다.
  • SPARQL, ArcaneQA, RnG-KBQA, DECAF.

Method

Overview

Resoning on Graphs(RoG)는 KG에 근거해 추론 계획은 세우고, LLM을 통해 신뢰할 수 있는 reasoning path를 검색하고 정답을 추론하는 planning-retrieval-reasoning 프레임워크를 제안한다. RoG는 크게 1)Planning, 2)Retreival-reasoning 두 개의 모듈로 구성된다.

• Planning 모듈
  • 주어진 질문 \(q\)에 대해 신뢰할 수 있는 관계 경로(relation path) \(z\)를 생성
• Retreival-reasoning 모듈
  • 계획 모듈에서 생성된 관계 경로 \(z\)를 사용하여 KG에서 유효한 추론 경로(reasoning path) \(w_z\)를 검색하고, 이를 기반으로 답변 \(a\)를 생성

얘를 들어, 입력으로 들어온 질문이 “Who is the child of Alice?”라고 해보자. 이 때,

Module 1. Planning Module(계획 모듈)

Planning Module은 말 그대로 추론을 위해 계획을 수립하는 부분이다. 이 몯모듚듈의 핵심은, 주어진 입력에 대해 정답을 찾기 위한 추론 경로를 찾기 전, 일차적으로 적합한 관계 경로를 찾아내는 것이다. 처음부터 추론 경로를 찾지 않는 이유는 여러가지가 있다. 첫번째로 정답에 대한 추론 경로는 엔티티의 정보를 포함하기 때문에, 가능한 모든 경로에 대한 임베딩을 계산하는 것은 컴퓨팅 자원을 많이 소모할 수 있다. 또한, 정보가 많아지는 만큼 불필요한 정보도 많아져 노이즈가 발생할 수 있기 때문이다. 이러한 이유로 많은 선행 연구들도 추론 경로를 추출하기 전에 관계 경로를 먼저 찾아낸다.

• Notations
  • Knowledge Graph: \(\{(e, r, e^{'} \vert e, e^{'} \in \mathcal{E}, r \in \mathcal{R})\}\)
  • Relation Path(관계 경로): \(z = \{r_1, r_2, \cdots, r_l\}\) (\(r_i\)는 path에서 i번째 relation)
  • Reasoning Path(추론 경로): \(w_z = e_0 \xrightarrow{r_1} e_1 \xrightarrow{r_2} \cdots \xrightarrow{r_l} e_l\)

예를 들어, (Alice, marry_to, Bob), (Bob, father_of, Charlie) 두 개의 트리플로 이루어진 관계 경로 \(z\)와 추론 경로 \(w_z\)를 다음과 같이 정의할 수 있다.

• 관계 경로: \(z = \text{marry_to} \rightarrow \text{father_of}\)
• 추론 경로: \(w_z = \text{Alice} \xrightarrow{\text{marry_to}} Bob \xrightarrow{\text{father_of}} Charlie\)

1) Planning Optimiation

RoG는 관계 경로와 추론 경로를 통해 최적화하고자 하는 수식은 다음과 같다. 질문과 KG과 주어졌을때, 정답에 대한 확률을 계산하는 것이며, 정답 엔티티의 확률값이 최대화되도록 하는 것이다.

결론적으로, RoG은 이 확률값을 계산하기 위해 계획 모듈과 검색-추론 모듈에서 각각 따로 계산된 확률을 이용하므로 두 개의 최적화 프레임워크를 가지게 된다. 위의 식은 evidence lower bound(ELBO)를 최대화하는 것으로 식을 변형할 수 있다. (ELBO)

여기서 오른쪽 항의 첫 번 째 term인 기댓값에 대한 부분은 검색-추론 모듈로부터, KL dievergency term은 계획 모듈로부터 만들어지는 term이다. \(Q(z)\)는 KG에 존재하는 모든 관계 경로 중, 신뢰할 수 있는 관계 경로의 posterior를 의미한다.

질문 \(q\)와 정답 \(a\)가 주어졌을 때

• 관계 경로: \(z = \{r_1, r_2, \cdots, r_l\}\)
• 추론 경로: \(w_z(e_q, e_a) = e_q \xrightarrow{r_1} e_1 \xrightarrow{r_2} \cdots \xrightarrow{r_l} e_a\)

여기서 입력으로 들어온 질문에 대해 신뢰할 수 있는 질문만을 고려한다면 \(Q(z)\)의 식은 근사 가능하다. 논문에서는 \(\mathcal{Z}\)의 확률 분포를 uniform으로 가정하였다.

이러한 근사 방식을 이용하면 planning 뫃모듈에서 정의되는 손실 함수 \(\mathcal{L_{plan}}\) 또한 위의 식처럼 변형이 가능하다. 결론적으로 KG로부터 지식을 추출하여 LLM이 신뢰할 수 있는 관계 경로를 생성할 확률을 최대화하는 방향으로 위의 식을 최적화한다.

2) Planning

Planning 뫃모듈은 질문에 답하기 위한 계획으로 신뢰할 수 있는 관계 경로를 생성하는 것을 목표로 한다. LLM의 instruction을 주어 관계 경로를 생성하도록 유도하는 간단한 instruction template을 설계해서 사용한다.

Please generate a valid relation path that can be helpful for answering the following question:
<Question>

LLM을 통해 출력된 관계 경로는 \(z = <\text{PATH}> r_1 <SEP> \cdots <SEP> r_l </PATH>\)으로 출력되며 \(<PATH>\)는 관계 경로에서 시작을 나타내는 스페셜 토큰이고, \(<SEP>\)과 \(</PATH>\)는 각각 분리 연산자(seperator)와 관계 경로의 끝을 알리는 스페셜 토큰이다. 최종적으로 \(\mathcal{L_{plan}}\)은 다음과 같이 변형된다.

Module 2. Retrieval-Reasoning Module(검색-추론 모듈)

Retrieval-Reasoning Module은 만들어진 관계 경로를 이용해 최종적으로 추론 경로를 찾고, 정답을 도출하는 모듈이다.

1) Retrieval-Rreasoning Optimization

2021년에 나온 FiD 프레임워크를 이용하면 \(P_{\theta}(a \vert q, \mathcal{Z}, \mathcal{G})\)는 모든 관계 경로가 아닌, 각 관계 경로별 확률값 \(P_{\theta}(a \vert q, z, \mathcal{G})\)의 곱으로 표현 가능하다. 따라서 기댓값의 log안에 들어가는 부분은 위의 식처럼 바뀐다.

또한 모든 최단 거리 \(\mathcal{Z^{*}}\) 중 top K개의 유망한 샘플의 최단 거리 관계 경로 \(\mathcal{Z_K^{*}}\)만을 고려하면 최종적으로 검색-추론 모듈에서 최적화하는 손실 함수 \(\mathcal{L_{reason}}\)은 위와 같이 정의된다.

2) Retrieval-Reasoning

계획 모듈을 거치면서 관계 경로 \(z\)가 생성되었으므로, 검색-추론 모듈에서 주어진 것은 질문과 관계 경로이다. 주어진 질문과 관계 경로를 통해 추론 경로를 찾아내고, 이는 수식으로 다음과 같이 표현된다. 참고로 LLM에서 검색을 통해 만들어지는 가능한 모든 추론 경로가 추론을 하는데 사용된다. 검색을 위한 알고리즘은 다음과 같다.

최종적으로 검색-추론 모듈은 손실 함수 \(\mathcal{L_{reason}}\)를 최대화하는 방향으로 최적화를 하게 된다.

Experiments

• RQ1: RoG가 KGQA 작업에서 SOTA을 달성할 수 있는가?
• RQ2: RoG의 계획 모듈을 다른 LLM과 통합하여 성능을 향상시킬 수 있는가?
• RQ3: RoG가 신뢰할 수 있는 추론을 수행하고 해석 가능한 추론 결과를 생성할 수 있는가?

Dataset Statistics

실험에는 Freebase를 기반으로 한 WebQeustionSP(WebQSP)와 Complex WebQuestions(CWQ)가 사용되었다.

RQ1: RoG가 KGQA 작업에서 SOTA을 달성할 수 있는가?

본 논문에서는 RoG의 backbone으로 LLaMA2-Chat-7B를 사용하였다. 위의 표에서와 같이 SOTA를 달성한 것을 확인할 수 있다. 특히 LLM만을 사용했을 때와 LLM + KG를 사용했을 때의 성능 차이를 통해, QA문제를 품에 있어서 KG를 사용하는 것이 효과적임을 볼 수 있으며, RoG가 LLM보다 훨씬 파라미터 수가 적은 sLM을 사용했음에도 불구하고 성능이 압도적이라는 점에서 의미있다.

추가적으로 어떤 모듈의 contribution이 더 높은지 비교하기 위해 ablation study를 진행하였다. 결과에서 알 수 있듯이, 계획 모듈 없으면 질문만을 입력으로 사용하는 기존의 LLM으로 퇴화되어 지식 부족(lack of knowledge) 문제가 발생한다. reasoning 모듈을 제거하면 더 많은 답변으로 인해 높은 재현율(Recall)을 얻을 수 있지만, 검색된 경로의 노이즈 때문에 정밀도(Precision)가 크게 떨어진다.

이는 중요한 추론 경로를 식별하고 노이즈를 걸러내는 데 있어 reasoning 모듈의 효과를 입증한다. 더욱이, 무작위한 계획(random plans)을 사용할 경우 계획 모듈을 제거하는 것보다 성능이 더 떨어진다. 이는 신뢰할 수 있는 추론 계획을 생성하는 계획 모듈의 중요성을 입증한다. 단순 다수결 추론(vote reasoning)을 사용하는 것은 결과를 개선할 수 있으며, 이는 또한 추론 모듈의 필요성을 입증다.

RQ2: RoG의 계획 모듈을 다른 LLM과 통합하여 성능을 향상시킬 수 있는가?

다음으로 추론 시 RoG의 계획 모듈을 다양한 LLM과 통합하여 성능을 향상시키는 효과를 평가하였다. 구체적으로, 먼저 RoG의 계획 모듈을 사용하여 관계 경로를 생성하고, 검색된 추론 경로를 다른 LLM에 맥락으로 제공하여 추론을 수행합니다. LLM의 출력에서 답변 수를 추출하는 것이 어렵다는 점을 고려하여, Hits@1과 Recall 지표만을 비교하였다. 결과에서 알 수 있듯이, 모든 LLM의 성능은 RoG의 계획 모듈을 통합함으로써 상당히 향상되었다. 구체적으로, ChatGPT, Alpaca, LLaMA2, Flan-T5의 \(Hits@1\)이 각각 8.5%, 15.3%, 119.3% 향상되었다. 이는 RoG의 계획 모듈이 재훈련 없이 다른 LLM과 원활하게 통합되어 성능을 향상시킬 수 있음을 입증한다.

RQ3: RoG가 신뢰할 수 있는 추론을 수행하고 해석 가능한 추론 결과를 생성할 수 있는가?

1) Quantitative Results

위의 그림은 관계 경로의 신뢰성을 평가하기 위한 정량적 결과를 보여준다. 실험에서 RoG가 생성한 top-K개의 관계 경로의 수를 조정하였다. 결과적으로 더 많은 관계 경로의수를 사용할수록 추론 경로의 수가 증가하고, 이는 더 많은 답변을 포함하게 된다(\(Recall\)). 이는 답변을 검색하여 관계 경로의 신뢰성을 입증한다. 하지만, 더 많은 추론 경로는 더 많은 노이즈를 유발하고, 검색 시간에 많은 컴퓨팅 자원을 요구하게 되므로, 정밀도(\(Precision\))이 감소하고 최종 결과 reasoning-f1에 거의 기여하지 않는다. 따라서 실험에서는 K를 3으로 설정하였다.

2) Case Studies

두 표는 두 가지 case study를 보여준다. 표 4에서 ChatGPT+CoT가 지식 부족 문제로 인해 질문에 답하지 못하는 것을 확인할 수 있다. 반면에 RoG는 신뢰할 수 있는 관계 경로를 생성하고 KGs에서 유효한 추론 경로를 검색하여 추론을 수행할 수 있다. 또한 RoG는 추론 경로를 기반으로 해석 가능한 설명을 제공할 수 있다. 표 5에서는 ChatGPT+CoT가 환각으로 인해 잘못된 답변을 생성하는 것을 볼 수 있다. 반면에, 검색된 추론 경로에 노이즈가 포함되어 있음에도 불구하고, 추론 모듈은 올바른 추론 경로를 식별하고 신뢰할 수 있는 추론을 수행할 수 있다. 이러한 결과는 RoG가 신뢰할 수 있는 추론을 수행하고 해석 가능한 결과를 생성하는 데 있어 효과적임을 입증한다.

Limitations and Contributions

• Limitations
  • 추론 경로갈 올바른 경로인지 확신할 수 있는가? RoG는 최단 거리로만 추론을 진행하는데, 만약 질문에 대한 정답을 추론하는 경로가 최단 거리로 이루어지지 않았으면 올바른 추론인가? (추론 경로는 틀리고 정답만 맞히는 경우)
• Contribtuion
  • KG와 LLM을 적절하게 결함하였다.
  • 관계 경로 설정의 중요성을 잘 보여주었다.

NR 카테고리 내 다른 글 보러가기