[논문리뷰]FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering

Problem Statement

문제1: 추론 경로의 실행 가능성 부족(생성된 추론 경로가 지식 그래프에 존재하지 않는 문제)

기존 연구들에서는 LLM을 지식 그래프(KG)의 구조에 맞게 미세 조정하여 추론 경로를 생성하는 방식이 많았으나, 이러한 방식은 생성된 추론 단계가 KG에 존재하지 않을 수 있다는 문제를 가지고 있다. 특히 다중 단계 추론에서 연속된 단계가 연결될 때 실행 가능성을 보장하지 못하는 경우가 많다. 기존 연구들은 주로 Direct Retrieval와 Semantic Parsing의 두 가지 방법으로 나뉜다.

Direct Retrieval는 질문을 쿼리로 사용해 지식 그래프(KG)의 트리플을 후보로 하여 희소 또는 밀집 검색 기술을 사용해 가장 관련성 있는 후보를 식별하는 방식이다. 하지만, KG 스키마의 차이로 인해 일부 엔티티는 기계 식별자(MID)로 표시되며, 이러한 방식은 사용자 쿼리와의 실제 관련성을 이해하는 데 어려움이 있다.

• 예를 들어, Freebase의 일부 엔티티는 “m3816/15”와 같은 이름을 가짐.

Semantic Parsing은 질문을 구조화된 쿼리(SPARQL 등)로 변환하여 KG에서 실행하는 방식이다. 그러나, 생성된 쿼리가 실행 불가능하거나 잘못 실행되는 문제가 발생할 수 있다. 특히, Multi-hop QA에서는 중간 트리플이 직접 관련 없어 보이지만 중요한 연결 고리가 될 수 있어 이러한 문제는 더 복잡해진다.

문제 2: 탐색 중단 시점의 불명확성(추론 경로 탐색을 언제 멈춰야 할지에 대한 명확한 기준 부족)

추론 모델을 통해 KG의 서브그래프를 반복적으로 검색하고 추론하는 방식도 제안되었으나, 탐색을 언제 중단해야 할지에 대한 명확한 기준이 없다는 문제가 있다. 이로 인해 탐색이 너무 일찍 중단되거나 불필요하게 연장되는 경우가 발생하여, 효율적인 추론 경로 탐색이 어렵다.

Prompt Engineering을 통해 LLM이 각 단계에서 노드의 이웃을 검색하고, 질문에 답할지 아니면 다음 검색 단계를 계속할지를 결정하는 방식이 제안되었으나, 언제 탐색을 멈춰야 할지에 대한 적절한 판단이 어려워 불필요한 계산이 계속되거나, 반대로 필요한 추론이 조기 종료되는 문제가 발생할 수 있다. 예를 들어, ToG는 LLM이 추론 경로의 적절성을 평가하여 답변을 생성하게 한다.하지만, 도메인에 대한 깊은 이해가 필요한 복잡한 작업으로 인해 추론이 너무 일찍 중단되거나 불필요하게 계속될 위험이 있다.

How to Solve?
이 논문에서는 이러한 한계를 극복하기 위해 Path-RAG와 DVBS라는 두 가지 주요 모듈을 제안한다. Path-RAG는 LLM을 활용해 쿼리에서 최대한의 키워드 목록을 생성하고, 이를 통해 KG에서 유용한 중간 지식을 검색한다. 이는 기존의 검색 방식보다 포괄적이고 정확한 추론 경로를 제시하는 데 중점을 둔다.

DVBS는 연역적 검증을 통해 추론 경로의 논리적 타당성을 검증하고, 타당하지 않을 경우 탐색을 멈추는 기준을 제공하여 불필요한 계산을 줄이고 정확한 추론 경로를 선택할 수 있도록 한다.

결론적으로, 이 논문에서 제안하는 방식은 추론 경로의 실행 가능성 부족, 탐색 중단 시점 불명확성 등 기존 연구들의 문제를 해결하며, LLM과 KG를 효과적으로 결합하여 더 신뢰성 있고 효율적인 추론 경로를 제공한다.

Method

Model Architecture

FiDeLiS는 지식 그래프(KG)의 하위 그래프를 반복적으로 검색하고 추론하는 검색-탐색 상호작용 방법을 제공하며, Path-RAG 모듈을 통해 쿼리에서 최대한의 키워드 목록을 생성하여 잠재적 추론 경로를 놓치지 않도록 하고 KG의 구조적 연결성을 통합해 시스템의 정확성을 높인다. 또한, 연역적 추론을 활용해 추론이 중단되어야 할 시점을 명확히 하여 추론 오류와 불필요한 계산을 방지한다. 이 방법은 훈련이 필요 없는 방식으로 낮은 계산 비용과 더 나은 일반성을 제공하며, 기존 강력한 기준선들을 능가하는 성능을 입증했다.

• Path-RAG: LLM을 사용해 쿼리에서 최대한의 키워드 목록을 생성하여 모든 잠재적 추론 경로가 누락되지 않도록 한다.
• 연역적 추론 능력(Deductive Capability)을 활용하여 단계별로 추론 과정을 자동으로 유도하는 더 나은 기준을 제안

1. Path-RAG

Path-RAG는 LLM을 활용해 쿼리에서 최대한의 키워드 목록을 생성하고, 지식 그래프에서 유용한 중간 지식을 검색하는 방식으로 설계되었다. 이 과정에서 각 엔티티와 관계에 대해 임베딩을 생성하고, 최근접 이웃 검색을 통해 상위 후보를 식별한다. 생성된 임베딩을 바탕으로, KG의 구조적 연결성을 고려해 추론 경로 후보를 결정하며, 이를 통해 더 포괄적이고 정확한 추론 경로를 제공한다.

Path-RAG는 세 단계로 구성된다.

• Initialization
• Retrieval
• Reasoning

1-1) Initialization

Path-RAG의 Initialization 단계에서는 LLM을 활용하여 노드와 엣지의 임베딩을 생성한다. 이 임베딩은 이후 최근접 이웃 검색을 위해 사용된다. 먼저 노드와 엣지의 자연어를 각각 사전 학습된 LM을 통해 생성하고 Nearest neighbor data structure에 저장한다. 논문에서는 LM으로 SentenceBERT를 사용하였다. 이 과정은 쿼리에 대한 관련 있는 추론 경로를 효율적으로 탐색하는 데 필수적이다.

• Nearest Neighbor data structure
  • Nearest neighbor data structure는 주어진 데이터 포인트에 가장 가까운 이웃 데이터를 효율적으로 찾기 위한 구조를 말한다. 이 구조는 고차원 공간에서 데이터 간의 유사도 또는 거리를 기반으로 가장 가까운 데이터 포인트들을 빠르게 검색하는 데 사용된다.
  • 예를 들어, 벡터화된 표현(embedding)을 사용해 각 데이터 포인트를 좌표화한 후, 새로운 쿼리와 가장 가까운 데이터를 찾는 데 사용된다. 이 방법은 특히 추천 시스템, 검색 엔진, 그리고 유사도 검색에 많이 활용되며, k-최근접 이웃(k-nearest neighbor, k-NN) 알고리즘이나 KD-트리(KD-tree), 볼록 해체(Voronoi diagram) 같은 구조가 이 역할을 수행할 수 있다.
  • 따라서 여기서 말하는 nearest neighbor data structure는 사전 학습된 언어 모델로 생성된 노드와 엣지 임베딩을 저장하고, 쿼리와 가장 유사한 임베딩을 효율적으로 검색하기 위한 데이터 구조를 의미한다.
  • faiss같은 vector DB도 nearest neighbor의 일종이다.

1-2) Retrieval

두 번째 스텝에서는 User의 쿼리와 연관된 엔티티와 릴레이션을 검색하기 위해, 노드와 엣지 임베딩의 nearast neghibor index를 구성한다. 구체적으로 주어진 쿼리 \(q\)에 대해 LM을 활용하여 잠재적 추론 경로를 찾기 위해 keyword(엔티티 이름) 또는 relation(릴레이션 이름)의 포괄적인 목록 \(k_i \in K\)를 생성한다. 생성된 키워드 목록은 잠재적 추론 단계의 범위를 최대화하고, LLM의 추론 단계 후보 선택을 더 작은 관련성 높은 후보들로 집중시켜 결정 과정을 향상시키는 것을 목표로 한다.

$$\mathcal{K} = \text{LM}(\text{Prompt}_p, q)$$

각 \(k_i^m\)은 하나의 문자열로 concatenation한 후 동일한 latent space에 임베딩되어 \(z(k)\)를 얻을 수 있다. 검색 과정에서는 키워드의 의미적 내용과 가장 잘 맞는 노드 또는 노드들의 순서를 식별하는 작업이 포함된다.

모든 키워드를 합쳐서 만들어진 임베딩 \(z(k)\)와 노드 e, 엣지 r의 임베딩 \(z(e), z(r)\)을 각각 코사인 유사도를 구해 키워드 표현과 노드, 엣지 임베딩 간의 유사도를 측정한다. argtopm연산은 이러한 유사도를 기준으로 상위 \(m\)개의 항목을 검색하여, 쿼리와 가장 관련성이 높은 노드와 엣지 집합을 반환한다. 각 노드와 엣지의 점수는 다음과 같다.

$$S_i^e = \cos \left( z(k), z(e) \right), \;\;\; S_i^r = \cos \left( z(k), z(r) \right)$$ $$\mathcal{E}_m = \text{argtopm}_{i \in \mathcal E}\cos(z(k), z(e)), \;\;\; \mathcal{R}_m = \text{argtopm}_{i \in \mathcal R}\cos(z(k), z(R))$$

중요한 점은 쿼리 임베딩 \(z(k)\)는 쿼리에서 명시적으로 관련된 k개의 엔티티와 릴레이션을 추출하지만, m개의 후보 임베딩 \(\mathcal{E}_m\)와 \(\mathcal{R}_m\)은 그래프에 존재하는 쿼리와 잠재적으로 관련성이 있는 엔티티와 릴레이션이다. 예를 들어,

• Query: “뉴욕에서 태어난 배우의 이름은?”
  • Keyword z(k): 뉴욕, 태어남
  • 후보 엔티티: 양키스, 로버트 다우니 주니어, 스칼렛 요한슨

1-3) Reasoning Step Candidates Construction

쿼리와 관련된 노드와 엣지의 집합, 그리고 스코어를 이용하 추론 단계에서 후보를 구성한다. 추론 단계에서 제안하는 스코어 함수의 목표는 KG의 연결성을 나타내기 위해 트리플을 활용하는 것이다. 이는 다음 단계의 작업 결정이 향후 여러 단계에서 잘못된 방향으로 이어질지 여부에 대한 힌트를 제공하며, 이웃 노드의 정보를 고려하여 판단할 수 있다.

$$S(p) = S_i^r + S_i^e + \alpha \max_{\forall j \in N_i} \left( S_j^r + S_j^e \right)$$

여기서 엔티티와 릴레이션은 논리적으로 서로 연결되어 있어야(=path)한다. \(S(P)\)는 추론 단계의 점수를 나타내며 ,\(S_i^r\)과 \(S_i^e\)는 다음 단계의 릴레이션 및 이웃에 대한 관련성 점수를 나타낸다. 그리고 \(S_j^r\)과 \(S_j^e\)는 \(i\)번째 엔티티와 릴레이션의 이웃 엔티티와 릴레이션의 score이다. \(\alpha\)는 그래프 내에서 즉각적인 정확성과 장기적인 전망 간의 균형을 맞추는 역할을 한다.
-\(\alpha\)가 크다: 모델이 덜 즉각적이지만, 중요한 결과를 고려하게 되고 -\(\alpha\)가 작다: 모델이 즉각적인 다음 단계에 집중, 장기적인 영향에 대한 고려가 줄어든다.

2. DVBS: Deductive-Verification Guided Beam Search

DVBS는 Path-RAG에서 제공된 추론 단계 후보에 대해 beam search을 반복적으로 실행하도록 LLM을 유도하는 방식으로 설계되었다. 각 시간 단계마다 LLM을 사용하여 상위 \(k\)개의 추론 단계를 선택하고, 다음 검색 단계를 계속할지, 추론 경로 확장을 중단할지를 결정한다.

DVBS도 세 단계로 구성된다.

• 계획(Plan-and-Solve)
• Beam Search
• 연역적 검증(Deductive Verification)

2-1) 계획(Plan-and-Solve)

최근 LLM의 계획 수립 능력과 관련된 연구에서 영감을 받아, 이 단계는 추후 LLM의 의사결정을 돕기 위한 힌트를 제공하는 것을 목표로 한다. 구체적으로, LLM에게 가장 유망한 추론 경로를 찾기 위한 계획 단계를 생성하도록 프롬프트를 제공하며, 이 초기 계획을 \(p\)로 나타낸다.

B.1 Plan-and-solve
You are a helpful assistant designed to output JSON that aids in navigating a knowledge graph to
answer a provided question. The response should include the following keys:

(1) ’keywords’: an exhaustive list of keywords or relation names that you would use to find the
reasoning path from the knowledge graph to answer the question. Aim for maximum coverage to
ensure no potential reasoning paths will be overlooked;

(2) ’planning_steps’: a list of detailed steps required to trace the reasoning path with. Each step
should be a string instead of a dict.

(3) ’declarative_statement’: a string of declarative statement that can be transformed from the given
query, For example, convert the question ’What do Jamaican people speak?’ into the statement
’Jamaican people speak *placeholder*.’ leave the *placeholder* unchanged; Ensure the JSON object
clearly separates these components.


In-Context Few-shot
Q: {Query}
A:

2-2) Beam-Search

multi-step reasoning에서, T단계의 추론 경로는 여러 시간 단계에 걸쳐 순차적으로 생성된다. T 단계의 추론 경로는 여러 시간 단계에 걸쳐 순차적으로 생성된다. 이를 \(R = [s^1, s^2, s^3, \cdots, s^T] = s^{1:T}\)로 표현한다. 일반적인 텍스트 디코딩 과정에서 각 단계가 단일 토큰으로 구성되는 것과 달리 FiDeLiS는 \((r, e)\) 쌍을 하나의 단계로 본다. \(r\)은 릴레이션(=엣지)이고 \(e\)는 엔티티(=노드)를 의미한다.

각 시간 단계에서 LLM을 사용하여 상위 \(k\)개의 추론 단계를 선택하고, 다음 검색 단계를 계속할지 추론 경로를 중단할지를 결정한다. 각 단계에서의 Beam Search는 다음과 같이 모델링된다.

$$\mathcal{H}_t = \text{Top}_K \left( h \oplus LM(s_t | q, s_{1:t-1}, p) : h \in H_{t-1}, s_t \in S \right)$$

• Notation
  • \(\mathcal{H}_{t-1}\): 이전 시간 단계에서의 추론 경로
  • \(s_t\): 현재의 추론 단계(현재 시점에서의 릴레이션-엔티티 pair\((r, e)\))
  • \(S\): Path-RAG를에서 생성된 모든 가능한 후보 집합
  • \(\text{LM}(s_t \vert q, s_{1:t-1}, p)\): 현재의 시퀀스 \(s_{1:t-1}\), 쿼리 \(q\), 그리고 planning context \(p\)에 대해 LLM이 예측한 다음 단계를 의미한다.
  • \(\oplus\): \(s_t\)를 현재 시퀀스 \(h\)에 더해주는 연산.
  • \(h\): 이전 시간 단계에서 추출된 경로

2-3) 연역적 검증(Deductive Verification)

연역적 검증 단계에서는 잘못된 시점에서 추론 경로 확장이 종료되는 것을 방지하기 위해, LLM의 연역적 추론 능력을 활용하여 더 나은 기준으로 삼는 것을 제안한다. 구체적으로 LLM을 사용해 사용자 쿼리를 선언문(statement)으로 변환한 후, 쿼리의 선언문이 현재 추론 단계 \(s_t\)와 이전 단계들 \(s_{1:t-1}\)에서 추론될 수 있는지 판단한다. 이를 통해 LLM이 자동으로 의사결정을 내릴 수 있도록 한다.

$$C(q', s_t, s_{1:t-1}) = \begin{cases} 1 & \text{쿼리 } q' \text{의 선언문이 } s_t \text{와 } s_{1:t-1} \text{로부터 연역될 수 있다.} \\ 0 & \text{그렇지 않다}. \end{cases}$$

따라서 DVBS의 전체 과정은 다음과 같이 모델링된다.

$$H_t = \text{TopB}\left( h \oplus LM(s_t \mid q, s_{1:t-1}, p) : h \in H_{t-1}, s_t \in S \text{ and } C(q', s_t, s_{1:t-1}) = 1 \right)$$

이 기준은 각 추론 단계가 논리적으로 타당하며, 원래 쿼리와 일치하는지 반복적으로 검증하기 위해 LLM을 활용하는 중요한 요소이다. 또한, 추가적인 추론이 필요 없을 때 명확한 신호로 작용하여 추론을 멈추는 기준이 된다.

Experiments

RQ1: KGQA Performance Comparison

• GPT-4-turbo을 이용해 prompting한 것이 성능이 가장 좋다. FiDeLis는 LM혹은 LLM을 fine-tuning하는 모델이 아니다.
• RoG와 비교했을때, 특히 CWQ에서 큰 성능 차이를 보인다.
• CR-LT에서 Acc(Accuracy)를 사용한 이유는 Hits@1이나 F1 score와 달리, CR-LT(Commonsense Reasoning with Long-Term Dependencies) 같은 문제에서는 정확한 답을 맞혔는지를 평가하는 것이 더 중요하기 때문일 가능성이 크다.
• CR-LT는 상식 추론을 다루는 문제로, 정확한 답변을 요구한다. 이 경우, 답이 부분적으로 맞거나 근사하게 맞는 것보다 정확히 맞혔는지 여부가 중요하다.

RQ2: Ablation Study of FiDeLiS.

Table 2는 FiDeLiS에서 특정 구성 요소를 제거했을 때 성능에 미치는 영향을 상세히 보여준다. Path-RAG와 DVBS의 Beam Search와 같은 기능이 특히 중요하다는 것을 강조하며, 특히 CWQ와 같은 복잡한 추론 과제를 해결하는 데 이들이 중요한 역할을 한다. Path-RAG와 DVBS 내의 Beam Search가 제외되면 성능이 크게 하락하는 것을 확인할 수 있으며, 이는 복잡한 추론을 효과적으로 처리하는 데 이들이 얼마나 중요한지 보여준다.

또한, DVBS 내에서 추론과 계획 단계를 통합하는 것이 다양한 데이터셋에서 일관된 성능을 유지하는 데 중요한 역할을 한다. 연구에서 주목할 만한 한 가지는 DVBS의 Beam Search 단계에서 연역적 검증의 역할이다. 이 기능은 모델이 결정 경계를 명확하게 정의하고 강화하는 데 도움을 주며, 이를 통해 추론 오류를 방지하는 효과가 있다.

RQ3: Robustness Analysis

Error Analysis regarding Whole Path Generation.

• 유효한 추론 경로(valid reasoning path): 전체 생성된 추론 경로 중 67%가 유효한 것으로 나타났다. 이는 지식 그래프에서 추론 경로가 논리적으로 타당하다는 것을 의미한다.
• 유효하지 않은 추론 경로(invalid reasoning path): 33%의 경로는 유효하지 않았다. 이는 다양한 오류로 인해 지식 그래프에 적합하지 않거나 논리적으로 타당하지 않은 경로를 생성했음을 의미한다.
• 유효하지 않은 경로의 구체적 원인
  • 포맷 오류(format error): 18%의 경로에서 포맷 오류가 발생했다. 이는 잘못된 형식으로 인해 경로가 올바르게 해석되지 못했음을 의미한다.
  • 존재하지 않는 관계(relation not exist): 15%의 경우, 생성된 경로에 지식 그래프에 존재하지 않는 관계가 포함되었다.

이 분석은 RoG 방법이 추론 경로를 생성하는 과정에서 지식 그래프 임베딩을 통합하는 데 한계가 있음을 시사한다. 특히, 생성된 경로 중 상당수가 포맷 오류나 존재하지 않는 관계로 인해 유효하지 않게 된다. 이는 기본 LLM 모델에서 지식 그래프를 활용하는 과정에서 생성 과정의 제어에 어려움이 있음을 보여준다.

Limitations and Contributions

• Limitations
  • fine-tuning등의 학습을 하지 않기 때문에 LLM의 성능에 의존적이다.
  • RoG에 대해 비교하면서도, 구체적인 정량적 비교 수치를 충분히 제공하지 않는다는 점이 한계일 수 있다. 예를 들어, RoG의 유효 경로 비율과 오류 비율을 분석한 것처럼, 자신들의 방법론에 대해서도 유사한 수치를 제시하지 않았다면, 개선된 성능을 명확히 증명하는 데 부족함이 있을 수 있다.
• Contribution
  • KG에 기반한 중간 추론 단계를 처리하기 위해 특별히 설계된 retrieval-exploration interactive method를 제안
    • Path-RAG
    • Deductive capability
  • 훈련이 필요 없는 방식으로 낮은 계산 비용과 더 나은 일반성을 제공
  • 특히 추론 과정에서의 오류를 줄여주는 연역적 검증과, beam search를 통한 효과적인 추론 능력 향상을 보여줌.

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