Title: Graph-Guided Reasoning for Multi-Hop Question Answering in Large Language Models

Institution: Korea University, Amazon Alexa AI

Authors: Jinyoung Park, Ameen Patel, Omar Zia Khan, Hyunwoo J. Kim, Joo-Kyung Kim

Arxiv Link: https://arxiv.org/abs/2311.09762

Code Link: None

Date: 2023.11.16

Abstract: Chain-of-Thought (CoT) prompting has boosted the multi-step reasoning capabilities of Large Language Models (LLMs) by generating a series of rationales before the final answer. This paper analyzes the reasoning paths generated by CoT and identifies two issues in multi-step reasoning: (i) Generating rationales irrelevant to the question, (ii) Unable to compose subquestions or queries for generating/retrieving all the relevant information. To address these issues, the authors propose a graph-guided CoT prompting method, which guides the LLMs to reach the correct answer with graph representation/verification steps. This involves leveraging LLMs to construct a “question/rationale graph” using knowledge extraction prompting given the initial question and the rationales generated in previous steps. Then, the graph verification step diagnoses the current rationale triplet by comparing it with the existing question/rationale graph to filter out irrelevant rationales and generate follow-up questions to obtain relevant information. Additionally, CoT paths that exclude the extracted graph information are generated to represent the context information missed from the graph extraction. The proposed graph-guided reasoning method shows superior performance compared to previous CoT prompting and its variants on multi-hop question answering benchmark datasets.

Introduction

The paper proposes an LLM-based, graph-guided reasoning approach for multi-step reasoning problems.

It makes two main contributions:

• The reasoning approach described above

• An in-context learning method for knowledge triplet extraction that allows variable definitions

An LLM-Based, Graph-Guided Reasoning Approach for Multi-Step Reasoning

The method has four steps:

1. Build the question graph

2. Decompose the question and generate intermediate subquestions

3. Answer the subquestions

4. Verify the intermediate reasoning

Question graph

The question graph is built by extracting triplets from the question. What “graph-based” means here is essentially converting the question into a symbolic reasoning process that forms part of a graph.

For example, the question “When did the director of film Hypocrite (Film) die?” can be converted into two subquestions serving as two edges in the graph: (“Hypocrite (Film)”, directed by, $1), ($1, death date, $2).

The novelty here is that the paper introduces formal logic into the reasoning process in a form resembling first-order logic (FOL). In this process, the variables ($1, $2) can only stand for individuals, not for propositions or other functions.

The authors introduce variable entities to handle wh-questions.

“Wh-questions” are a type of question in English that begin with “wh-” words, such as “who,” “what,” “where,” “when,” “why,” and “how” (though “how” does not start with “wh,” it is grouped with them functionally).

Intermediate subquestion generation

What distinguishes the subquestion generation here from other work is that it is carried out under the guidance of the graph.

Concretely, the paper filters out question triplets whose subject and object are both variables or both entities, so the process only attends to triplets pairing an entity subject with a variable object, or a variable subject with an entity object.

The reason is easy to see: for a triplet (variable1, relationship, variable2) or a triplet (entity1, relationship, entity2), further decomposition serves no purpose.

Answering the subquestions

Subquestions are shorter and simpler than the original question, so a correct answer is easier to produce. Because LLMs are prone to hallucination and may never have been trained on the documents in question, the output can still be wrong; RAG is one way to improve answer accuracy.

Verifying the intermediate reasoning

The generated rationale triplets are checked for validity by verifying that the answers align with the question graph.

Concretely, at least two components must match between the rationale triplet and some triplet in the question graph. If they do, we accept the rationale that produced the matched triplet; if the triplet matches nothing in the question graph, we reject it.

Take the rationale triplet (“Hypocrite (Film)”, directed by, “Miguel Morayta”) and the question graph (“Hypocrite (Film)”, directed by, $1), ($1, death date, $2). The question graph contains the triplet (“Hypocrite (Film)”, directed by, $1), whose subject is “Hypocrite (Film)” and whose relation is “directed by”, so the rationale is accepted.

For a counterexample, no triplet in the question graph matches the rationale triplet (“Miguel Morayta”, place of death, “Mexico”), so it is rejected.

Experiments

Setup

Datasets:

• 2WikiMultihopQA consists of complex 2-hop questions that require composition or comparison.

• MuSiQue is a more challenging dataset whose 2- to 4-hop questions can be decomposed into simpler ones.

• Bamboogle consists of 125 two-hop questions whose supporting evidence comes from Wikipedia.

Models:

• Llama-2 13B

• Llama-2 70B

Result

The figure above shows part of the experimental results: the proposed method outperforms every baseline.