PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Elicitation for Guiding Multi-Step Reasoning in Large Language Models

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

arXiv:2311.09762v2cs.CLcs.AIcs.LG

TL;DR

Chain-of-Thought methods can struggle with complex multi-hop questions because of knowledge gaps and difficulty decomposing questions. GE-Reasoning represents questions as triplet graphs to guide sub-question generation and answering, and performs best among the compared prompting methods across three benchmarks in closed- and open-book settings.

  • Problem

    Chain-of-Thought prompting and its variants have difficulty answering complex multi-hop questions because of knowledge gaps and difficulty properly decomposing questions.

    Source: §1 · p. 1

  • Method

    GE-Reasoning extracts question triplets, including variables as head or tail entities, then generates triplet-grounded sub-questions and answers, filtering low-confidence pairs and using retrieval in open-book settings.

    Source: §1 · pp. 1–2, §3.1 · p. 3

  • Results

    GE-Reasoning performs best among the compared prompting methods across three multi-hop QA datasets with different LLMs in both closed-book and open-book settings.

    Source: §1 · p. 2, §4.4 · p. 7

  • Takeaways & Limitations

    Graph-based guidance facilitates relevant and distinct sub-questions and the reported experiments show it suppresses irrelevant sub-question generation.

    Source: §3.2 · p. 4

    Performance depends on the LLM and demonstration quality, while open-book performance depends strongly on the BM25 retriever’s retrieved-knowledge quality.

    Source: §6 · p. 9

Abstract

from arXiv · show

Chain-of-Thought (CoT) prompting along with sub-question generation and answering has enhanced multi-step reasoning capabilities of Large Language Models (LLMs). However, prompting the LLMs to directly generate sub-questions is suboptimal since they sometimes generate redundant or irrelevant questions. To deal with them, we propose a GE-Reasoning method, which directs LLMs to generate proper sub-questions and corresponding answers. Concretely, given an input question, we first prompt the LLM to generate knowledge triplets, forming a graph representation of the question. Unlike conventional knowledge triplets, our approach allows variables as head or tail entities, effectively representing a question as knowledge triplets. Second, for each triplet, the LLM generates a corresponding sub-question and answer along with using knowledge retrieval. If the prediction confidence exceeds a threshold, the sub-question and prediction are incorporated into the prompt for subsequent processing. This approach encourages that sub-questions are grounded in the extracted knowledge triplets, reducing redundancy and irrelevance. Our experiments demonstrate that our approach outperforms previous CoT prompting methods and their variants on multi-hop question answering benchmark datasets.

1 Introduction

The paper addresses multi-hop reasoning challenges and sub-question methods that can produce irrelevant or redundant questions. GE-Reasoning guides question decomposition with graph-elicited triplets and reports the best performance among prompting methods across three benchmarks.

1 Introduction

  • Multi-hop questions challenge CoT prompting through lack of knowledge and difficulty decomposing questions, while direct sub-question generation can yield irrelevant, redundant, or insufficient questions.Earlier sub-question methods often rely on raw-text in-context exemplars without concrete guidance.Source: §1 · p. 1
  • GE-Reasoning elicits a question graph of knowledge triplets, including variables as head or tail entities, then generates triplet-grounded sub-questions and answers.The process repeats sub-question, rationale, and answer generation until a final answer is reached or the maximum reasoning steps are used.Source: §1 · pp. 1–2
  • Grounding each sub-question in a distinct triplet supports relevance, reduces redundancy, and makes its grounding and composition easier to track.Variables serve as entity placeholders that help represent question sentences as triplets.Source: §1 · p. 2
  • The method filters sub-question/answer pairs below a confidence threshold and can retrieve relevant paragraphs using each sub-question as the query.Its retrieval-augmented generation with structural knowledge refinement filters irrelevant knowledge information.Source: §1 · p. 2
  • GE-Reasoning outperforms baseline prompting methods on three multi-hop QA datasets and performs best across evaluated LLMs in both closed-book and open-book settings.The evaluated models are Llama-3 (8B and 70B) and GPT-3.5 Turbo.Source: §1 · p. 2

2 Related Works

The related-work discussion contrasts graph-guided prompting with approaches to multi-step reasoning and knowledge retrieval. It describes GE-Reasoning as providing explicit graph guidance and using iterative rationale generation and verification.

2.1 Prompts for Multi-Step Reasoning

  • GE-Reasoning differs from multi-step prompting approaches by guiding reasoning with elicited graphs and iteratively generating and verifying intermediate rationales without external programs.The section discusses CoT, symbolic functions, least-to-most prompting, and code-based approaches.Source: §2.1 · pp. 2–3

2.2 Prompting with Knowledge Retrieval

  • The related-work comparison covers single-retrieval prompting, Self-Ask, ReAct, and IRCoT, alongside GE-Reasoning's reported effectiveness across diverse LLM sizes in open-domain multi-hop QA.The passage notes limitations involving single retrieval, ReAct's model scale and fine-tuning requirements, and IRCoT's exposure to noisy knowledge.Source: §2.2 · p. 3

3 Graph Elicitation for Guiding Multi-Step Reasoning

GE-Reasoning decomposes a complex question into graph-guided sub-questions, answers them iteratively, and uses the resulting answers to resolve variables before producing a final answer. Its pipeline combines question-triplet extraction, sub-question generation, optional retrieval, and confidence-based filtering.

3 Graph Elicitation for Guiding Multi-Step Reasoning

  • GE-Reasoning iteratively generates sub-questions from an elicited question graph, predicts their answers, resolves variables, and then answers the original question.The process stops when no eligible variable triplets remain or the repetition limit is reached.Source: §3 · p. 3, §3.6 · p. 6

3.1 Question Graph Construction.

  • LLM prompting with in-context examples extracts question triplets, whose variable entities represent the unknowns needed to express the question as a graph.Variables can be assigned answers and updated across linked triplets.Source: §3.1 · pp. 3–4

3.2 Sub-Question Generation

  • The model generates a sub-question from a selected graph triplet with one variable, grounding distinct sub-questions in the question structure.Triplets with two variables become eligible after one variable is assigned.Source: §3.2 · p. 4

3.3 Sub-Answer Generation

  • For each sub-question, the LLM predicts an answer using the original question and previously generated sub-question/answer context.When an answer is uncertain, the method uses retrieval-augmented generation for the sub-answer.Source: §3.3 · p. 5

3.4 Retrieval Augmented Generation with Structural Knowledge Refinement

  • Retrieval uses the current sub-question as its query, then extracts and filters triplets so only informative knowledge is added to the prompt.This targets current-step information rather than relying on a compound question or a prior reasoning sentence as the query.Source: §3.4 · pp. 5–6

3.5 Filtering and Variable Assignment

  • Low-confidence sub-answer pairs are filtered out; a high-confidence answer is assigned to its triplet variable and propagated to other triplets containing that variable.A filtered pair may be generated again with high confidence in a later iteration.Source: §3.5 · p. 6

3.6 Iterative Generation

  • Iteration ends when no question triplets with single variables remain or the repetition limit is reached, after which the model generates the original question’s answer..Source: §3.6 · p. 6

4 Experiments

The experiments compare GE-Reasoning with prompting baselines on multi-hop question answering and examine its retrieval, graph-guidance, refinement, filtering, and entity-type choices. GE-Reasoning has the best performance across the tested datasets and LLMs in the open-book setting.

4.1 Experimental Setup

  • The evaluation uses 500 sampled development questions each from 2WikiMHQA and MuSiQue, all 125 Bamboo questions, and answer-level EM and token-level F1.It uses six in-context exemplars; open-domain retrieval uses supplied paragraphs for 2WikiMHQA and MuSiQue and Google search for Bamboo.Source: §4.1 · p. 6

4.2 Models

  • Experiments use Llama-3 at 8B and 70B sizes and GPT-3.5 Turbo; knowledge retrieval uses BM25 with the top two documents.BM25 is implemented with Elasticsearch.Source: §4.2 · p. 6

4.3 Baselines

  • Open-book baselines include no retrieval, one retrieval, Verify-and-Edit, FLARE, IRCoT, and ERA-CoT; closed-book baselines include CoT, Zero-Plus-Few-Shot CoT, Self-Consistency, and Self-ask.ERA-CoT is evaluated with retrieved knowledge for comparison with the other open-book methods.Source: §4.3 · pp. 6–7

4.4 Experimental Results

  • GE-Reasoning has the best performance among baseline prompting methods across all tested datasets and LLMs in the open-book setting.The experiments use Llama3-8B, Llama3-70B, and GPT-3.5 Turbo.Source: Table 1 · p. 7, §4.4 · p. 7

4.5 Additional Experimental Results.

  • With sub-question retrieval, graph guidance improves over unguided prompting by 3.67 F1 on 2WikiMHQA, and sub-question queries outperform input-question queries.The authors report that the input question is insufficient to retrieve all knowledge needed for multi-step reasoning.Source: §4.5 · p. 7, Table 2 · p. 7
  • Structural knowledge refinement and filtering both contribute to GE-Reasoning's performance, with refinement improving EM by 1.4 on 2WikiMHQA.The authors attribute the refinement benefit to mitigating irrelevant information in retrieved paragraphs.Source: Table 3 · p. 7, §4.5 · p. 8
  • Using entity type in question-graph construction improves EM by 0.8, while graph construction is reported accurate with and without type on 2WikiMHQA using Llama-3 8B.The evaluation compares graph quality and question answering with and without entity type.Source: Table 5 · p. 7, §4.5 · p. 8

4.6 Qualitative Analysis

  • In a qualitative example, unguided decomposition asks an irrelevant question and returns “Who is Running,” while graph guidance generates relevant sub-questions and answers.The example compares reasoning about the younger director of Running for Grace or Irulum Oliyum.Source: §4.6 · p. 8, Table 6 · p. 8

5 Conclusion

GE-Reasoning guides LLMs through repeated sub-question generation, answer generation, and filtering to reach an answer. Experiments on three multi-hop QA benchmarks demonstrate its effectiveness.

5 Conclusion

  • The method explicitly guides large language models toward the correct answer.The conclusion describes retrieval augmentation using intermediate sub-questions as queries.Source: §5 · p. 8
  • GE-Reasoning repeats sub-question generation, answer generation, and answer filtering until it predicts the final answer.In retrieval-augmented use, intermediate sub-questions serve as queries to obtain external knowledge triplets for intermediate reasoning.Source: §5 · p. 8
  • Experiments on three multi-hop question answering benchmark datasets demonstrate the effectiveness of GE-Reasoning.Source: §5 · p. 8

6 Limitations

The method's performance depends on the LLMs and demonstrations; in open-book use, retrieved-knowledge quality also depends on BM25.

6 Limitations

  • GE-Reasoning's performance relies on the LLMs and the quality of the demonstrations.Source: §6 · p. 9
  • In open-book settings, retrieved-knowledge quality is highly dependent on the BM25 retriever.Source: §6 · p. 9
  • The authors state that advanced retrieval methods may help improve performance.Source: §6 · p. 9

7 Ethics Statement

GE-Reasoning is described as addressing potential LLM ethical issues such as hallucination, but concerns remain because it depends on LLMs to reason about multi-hop questions.

7 Ethics Statement

  • Remaining ethical concerns include reliance on Llama-3 and GPT-3.5 to reason about multi-hop questions.The passage also says GE-Reasoning addresses potential issues such as hallucination.Source: §7 · p. 9

A Datasets and Licenses

The evaluation uses three multi-hop question-answering datasets, whose questions span two-hop composition or comparison, two-to-four-hop decomposition, and evidence from Wikipedia.

A Datasets and Licenses

  • The authors state that, to the best of their knowledge, the three datasets have no privacy issue.The privacy statement applies to the datasets used for evaluation.Source: A Datasets and Licenses · p. 12
  • 2WikiMultihopQA consists of 2-hop questions requiring composition or comparison.The dataset is attributed to Ho et al. (2020).Source: A Datasets and Licenses · p. 12
  • MuSiQue covers more challenging questions with 2 to 4 hops that can be decomposed into simpler questions.The passage identifies it as more challenging than the other listed datasets.Source: A Datasets and Licenses · p. 12
  • Bamboogle contains 125 multi-hop questions whose supporting evidence comes from Wikipedia.The passage attributes the dataset to Trivedi et al. (2022).Source: A Datasets and Licenses · p. 12

B Implementaion Details

Experiments use six in-context demonstrations, BM25 retrieval of the top two documents, and different run counts across datasets due to computational cost.

B Implementaion Details

  • Experiments use one run on 2WikiMHQA and MuSiQue and four runs on Bamboogle because of computational costs.All experiments use six demonstrations; retrieval uses BM25 implemented with Elasticsearch and the top two documents.Source: B Implementaion Details · p. 12
  • All datasets use in-context learning with six demonstrations to predict answers.Source: B Implementaion Details · p. 12
  • Knowledge retrieval uses BM25 implemented with Elasticsearch and returns the top two documents.Source: B Implementaion Details · p. 12

C Additional Experiments

On 2WikiMHQA, GE-Reasoning has the best performance among the compared methods with time comparable to other retrieval-based methods, and improves F1 and time relative to FLARE.

C Additional Experiments

  • 10.29 F1 score and 5.0 seconds per question are the reported improvements over FLARE on 2WikiMHQA.The passage describes GE-Reasoning as the best-performing method there, with time comparable to other retrieval-based methods.Source: C Additional Experiments · p. 12

D Input Prompts

The appendix lists prompts for question-graph construction, subquestion and subanswer generation, triplet extraction, and filtering. It also includes the GE-Reasoning algorithm outline and a performance-and-efficiency table caption for 2WikiMHQA using Llama-3 8B.

D Input Prompts

  • The appendix identifies prompts for question-graph construction, subquestion generation, subanswer generation, triplet extraction, and filtering irrelevant triplets.Tables 8–12 cover these prompt functions; their contents are not specified in the supplied passages.Source: D Input Prompts · p. 12, Table 8 · p. 14, Table 9 · p. 14
  • Table 7 compares performance and efficiency on 2WikiMHQA with Llama-3 8B, measuring time in seconds per question.The caption says bold marks the best performance, but the supplied passage contains no table values.Source: Table 7 · p. 12
  • The algorithm takes an input question and hyperparameters k1 and k2, loops until Stop is not False, and checks prediction confidence against both thresholds.The supplied algorithm fragments do not specify the actions taken at each confidence check.Source: D Input Prompts · p. 13

Related papers

Loading 2311.09762v2…