PaperlayerView exact revision on arXiv

Source-linked AI summary

HGOT: Hierarchical Graph of Thoughts for Retrieval-Augmented In-Context Learning in Factuality Evaluation

Yihao Fang, Stephen W. Thomas, Xiaodan Zhu

arXiv:2402.09390v2cs.AIcs.CL

TL;DR

Hallucinations—factually incorrect or ungrounded content—raise concerns about LLM reliability, including in retrieval-augmented in-context learning. HGOT organizes query planning and retrieval in a hierarchical graph and weights answer voting by thought citation quality, while also scoring retrieved passages. It outperforms methods in FEVER by up to 7% and matches leading models in Open-SQuAD and HotPotQA.

  • Problem

    LLM hallucinations—content that is factually incorrect or not grounded in reality—raise concerns about reliability and trustworthiness, particularly in high-stakes applications.

    Source: §1 · p. 1

  • Method

    HGOT builds a hierarchical graph by decomposing complex queries and combines citation-quality-weighted answer voting with multi-factor scoring of retrieved passages.

    Source: §1 · pp. 1–2, §3.1 · p. 4, §3.3 · p. 5

  • Results

    HGOT outperforms existing retrieval-augmented in-context learning methods in FEVER by up to 7%, matching Retrieve-then-Read in Open-SQuAD and DSP in HotPotQA.

    Source: §1 · p. 2

  • Takeaways & Limitations

    HGOT is presented as a structured way to source and incorporate relevant external information, thereby reducing LLM hallucinations.

    Source: §1 · p. 1

    Evaluation uses ChatGPT and Google Search API from SerpApi.com; other language models, search engines, and domain-specific data sources have not been examined.

    Source: Limitations · p. 9

Abstract

from arXiv · show

With the widespread adoption of large language models (LLMs) in numerous applications, the challenge of factuality and the propensity for hallucinations has emerged as a significant concern. To address this issue, particularly in retrieval-augmented in-context learning, we introduce the hierarchical graph of thoughts (HGOT), a structured, multi-layered graph approach designed to enhance the retrieval of pertinent passages during in-context learning. The framework utilizes the emergent planning capabilities of LLMs, employing the divide-and-conquer strategy to break down complex queries into manageable sub-queries. It refines self-consistency majority voting for answer selection, which incorporates the recently proposed citation recall and precision metrics to assess the quality of thoughts, linking an answer's credibility intrinsically to the thought's quality. This methodology introduces a weighted system in majority voting, prioritizing answers based on the citation quality of their thoughts. Additionally, we propose a scoring mechanism for evaluating retrieved passages, considering factors such as citation frequency and quality, self-consistency confidence, and the retrieval module's ranking. Experiments indicate that HGOT excels as a versatile approach, outperforming competing models in FEVER by up to $7\%$ and matching leading models such as Retrieve-then-Read in Open-SQuAD, and DSP in HotPotQA, demonstrating its efficacy in enhancing LLMs' factuality.

1 Introduction

HGOT addresses hallucinations in retrieval-augmented in-context learning with a hierarchical graph that organizes query planning and external information. It combines citation-quality-weighted answer voting with a multi-factor score for retrieved passages.

1 Introduction

  • HGOT uses LLM planning to divide complex queries into simpler sub-queries within a hierarchical graph.The divide-and-conquer strategy is intended to simplify problem-solving and improve retrieved information's accuracy and relevance.Source: §1 · p. 1
  • Answer voting weights responses by thought citation quality, assessed with citation recall and precision.The approach links response quality to the quality of the underlying thought.Source: §1 · p. 2
  • Retrieved passages are scored using citation frequency and quality, self-consistency confidence, and retrieval-module ranking.The scoring mechanism evaluates the quality of passages used in response generation.Source: §1 · p. 2
  • HGOT outperforms retrieval-augmented in-context learning methods in FEVER by up to 7%, matching Retrieve-then-Read in Open-SQuAD and DSP in HotPotQA.The evaluation groups questions by length and emphasizes samples from the distribution tails.Source: §1 · p. 2
  • The paper evaluates fact retrieval and reasoning on FEVER, Open-SQuAD, and HotPotQA, grouping questions as Long, Medium, or Short.Sampling emphasizes the tails of the question-length distribution.Source: §1 · p. 2

2 Related Work

Prior retrieval-augmented methods extend retrieval through multiple hops, while other approaches structure reasoning as plans, trees, graphs, or recurrent processes. The cited work identifies challenges in adapting search to intricate planning and in sourcing relevant information reliably.

2 Related Work

  • Retrieve-then-Read gathers passages for an LM prompt; Self-ask [Press et al., 2022] and IRRR [Qi et al., 2020] add follow-up questions for multi-hop retrieval.The follow-up answers are combined with the original prompt to support a response.Source: §2 · p. 2
  • ReAct [Yao et al., 2023b] interleaves reasoning traces and actions, while Baleen [Khattab et al., 2021] summarizes multiple passages at each hop.DSP [Khattab et al., 2022] automatically annotates chain-of-thought demonstrations [Wei et al., 2022].Source: §2 · p. 2
  • Multi-hop pipelines can struggle with generality and adaptability of search, especially for inquiries requiring intricate retrieval planning.The passage identifies planning demands as a challenge for retrieving pertinent information.Source: §2 · p. 2
  • Plan-and-Solve prompting [Wang et al., 2023a] decomposes tasks into subtasks, while tree, graph, and recurrent reasoning methods explore structured problem-solving.The cited approaches are described as facing challenges in sourcing relevant information and factual reliability.Source: §2 · pp. 2–3

3 Methodology

HGOT organizes query solving as a recursive hierarchy of dependent sub-queries, then ranks answers and retrieved passages using evidence-related quality signals. Its methodology combines citation-quality-weighted answer voting with passage scoring that also accounts for retrieval rank and confidence.

3.1 Hierarchical Graph Construction, Search, and Inference

  • HGOT breaks complex queries into connected sub-queries arranged in deeper dependency graphs, using a directed acyclic graph to avoid circular dependencies.A sub-query can be expanded into another dependency graph at a deeper level.Source: §3.1 · p. 3, §3 · p. 3
  • Search processes dependency steps topologically and rewrites dependent questions to include the prior sub-query and its probed answer.The procedures recurse until a specified depth or a single-step plan closely resembling the planned sub-query triggers termination.Source: §3.1 · p. 4
  • At each level, Probe gathers passages, Plan builds dependencies, and Infer ranks gathered passages, selects the top K for the prompt, predicts an answer, and estimates confidence.The procedures are recursively executed for sub-queries until the depth limit or Plan's stopping condition.Source: §3.1 · pp. 4–5

3.2 Thought Quality

  • HGOT scores each generated thought using citation recall and precision, then weights answer votes by thought quality when selecting the answer.The paper describes thought quality as a modification of citation recall and precision; the answer-selection formulation uses the resulting thought qualities.Source: §3.2 · p. 5
  • HGOT also incorporates thought quality into its self-consistency confidence score.When the thought-quality weighting reduces to 1, the equations simplify to self-consistency prediction and calibration.Source: §3.2 · p. 5

3.3 Retrieval Quality

  • Retrieved-passage quality accounts for citation frequency, citation quality, self-consistency confidence, and the retrieval module's ranking.Citation indicators combine citation markers with natural-language-inference judgments; citation frequency is adjusted by thought quality and aggregated across thoughts.Source: §3.3 · p. 5
  • HGOT normalizes weighted citation frequency so the highest passage value in a retrieval set is 1, then repeatedly updates passage quality from the search engine's initial score.The weight vector can be tuned for different datasets, retrieval models, and large language models.Source: §3.3 · p. 5

4 Data

The paper evaluates HGOT on FEVER, Open-SQuAD, and HotPotQA, stratifying questions by token length into short, medium, and long groups. It reports exact-match metrics for FEVER and exact match plus F1 for the other two datasets.

4 Data

  • The evaluation covers FEVER, Open-SQuAD, and HotPotQA, with questions divided into long, medium, and short groups by token length.The sampling emphasizes distribution tails, and the authors state that this is often overlooked in studies.Source: §4 · pp. 5–6
  • Figure 2 presents question-token length distributions; FEVER's median is 27 tokens, and Open-SQuAD and HotPotQA show similar distributions.Training, development, and test distributions align well, supporting stratification by sentence length.Source: §4 · p. 6, Figure 2 · p. 6
  • FEVER and Open-SQuAD classify questions above the 98.5th percentile as long and below the 1.5th as short; HotPotQA uses the 98th and 2nd percentiles.For medium-length questions, about 1.5% of FEVER and Open-SQuAD examples and 2% of HotPotQA examples are randomly selected for evaluation.Source: §4 · p. 6
  • The evaluation uses Exact Match for FEVER and Exact Match plus F1 for Open-SQuAD and HotPotQA.The paper notes that FEVER answers are limited to three tokens or fewer as the reason for using only Exact Match there.Source: §4 · p. 6

5 Evaluation Setup

The evaluation benchmarks HGOT against five language-model and retrieval-augmented approaches. The experiments use a shared language-model backbone with a stated exception and specify the retrieval and scoring components.

5 Evaluation Setup

  • The benchmark compares HGOT with Vanilla LM, Retrieve-then-Read, Self-ask, ReAct, and Demonstrate-Search-Predict (DSP).Appendix E is cited for further baseline details.Source: §5 · p. 6
  • All approaches use ChatGPT (gpt-3.5-turbo-1106) except ReAct, which uses text-davinci-002; retrieval uses the Google Search API through SerpApi.com.The paper follows the Self-ask approach for retrieval.Source: §5 · p. 6
  • HGOT uses a natural-language-inference model to measure thought and retrieval quality, and NetworkX for topological sorting and deductions.HGOT was implemented in Python using the DSP framework.Source: §5 · p. 6

6 Experimental Results

HGOT variants perform strongly across the evaluated datasets, with HGOT+Sampling leading FEVER and HGOT+KNN leading Open-SQuAD. Ablations identify a best hyperparameter combination when both thought and retrieval quality are considered.

FEVER

  • 61.50% EM: HGOT+Sampling leads FEVER overall, exceeding Retrieve-then-Read by over 3% and DSP by more than 7% on Long.HGOT+Sampling or HGOT+KNN ranks highest in every FEVER length category.Source: Table 2 · p. 7, §6 · p. 7

Open-SQuAD

  • 24.10% EM: HGOT+KNN leads Open-SQuAD overall, more than 1.5% above its nearest competitor, Retrieve-then-Read.Retrieve-then-Read remains competitive across categories.Source: Table 2 · p. 7, §6 · p. 7

Evaluation setup

  • Table 2 reports Overall metrics as weighted averages across the Long, Medium, and Short categories.Source: Table 2 · p. 7, §6 · p. 7

Question-length findings

  • Vanilla LM generally performs best on short questions, except short Open-SQuAD questions; longer questions often require more facts and complex reasoning.Medium and short Open-SQuAD questions usually require one or two facts, while medium questions provide more context than short ones.Source: §6 · p. 7

Cross-dataset findings

  • Retrieval-augmented methods generally surpass Vanilla LM, except Self-ask and ReAct on FEVER; HGOT variants perform strongly across all three datasets.The authors suggest fact gathering matters more than multi-hop reasoning in FEVER.Source: §6 · p. 7

Ablation study

  • α=0.2, β=0.4, γ=0.4, w1=0.2, w2=0.55, and w3=0.25 yield the highest EM in the Open-SQuAD medium-question search.The authors interpret this optimum as supporting the inclusion of both thought quality and retrieval quality.Source: §6 · p. 8, Figure 3 · p. 8

7 Conclusion

The paper evaluates HGOT on FEVER, Open-SQuAD, and HotPotQA, grouping questions by length and emphasizing distribution extremes. It reports strong FEVER performance and results matching leading models on Open-SQuAD and HotPotQA.

Evaluation scope

  • The evaluation covers FEVER, Open-SQuAD, and HotPotQA for fact retrieval and reasoning.Source: §7 · p. 8

Conclusion

  • HGOT surpasses other models in FEVER and matches leading models in Open-SQuAD and HotPotQA.Source: §7 · p. 8

Evaluation scope

  • Questions are grouped as Long, Medium, or Short, with sampling emphasizing distribution extremes often overlooked in research.Source: §7 · p. 8

Limitations

The evaluation uses ChatGPT and Google Search through SerpApi; alternative language models and retrieval systems remain unexamined.

Language model scope

  • HGOT was evaluated with ChatGPT; Gemini and Llama 2 were not explored.Source: Limitations · p. 9

Retrieval scope

  • Retrieval uses Google Search via SerpApi, and performance with Bing, Yahoo, or Baidu has not been examined.Source: Limitations · p. 9
  • Domain-specific sources such as Oracle or IBM DB2 databases are proposed as possibilities, but their effectiveness is untested.Source: Limitations · p. 9

Ethics Statement

The research uses publicly available data, avoids private data, and focuses on factuality rather than harmful or undesirable content.

Data

Scope

  • The research focuses on factuality and deliberately avoids producing harmful or undesirable content.Source: Ethics Statement · p. 9

A Dataset Summary Statistics

Table 3 summarizes FEVER, Open-SQuAD, and HotPotQA across nine categories using instance counts and question-length statistics.

A Dataset Summary Statistics

B.1 FEVER Data Examples and Examination

This section examines FEVER examples and evaluation methods, describing question types and procedures for decomposing questions, tracking dependencies, and producing evidence-grounded answers. It also covers automated demonstration selection and benchmark baselines ranging from few-shot prompting to retrieval-supported and reasoning-and-search methods.

B.1–B.3 Data Examples and Examination

  • FEVER claims require relevant background facts and logical analysis, while Open-SQuAD questions vary in needed factual detail and HotPotQA often requires multi-hop reasoning.The examples note that longer FEVER claims and HotPotQA questions tend to be more complex; short Open-SQuAD questions are not necessarily easy, and medium questions can provide more retrieval context.Source: §B.1 · p. 12, §B.2 · p. 13, §B.3 · pp. 14–15

C.1–C.3 Planning, Self-reflection, and Formalization

  • The planning prompt asks for essential search-answerable steps as standalone search questions, highlights dependencies, and allows higher-numbered steps to depend on lower-numbered steps, but not vice versa.One example states that Step 2 depends on Step 1 and represents this as Step 1 -> Step 2.Source: §C.1 · p. 16, §C.3 · pp. 18–19

C.4 Prompt and Response of the “Rewrite” Procedure

  • Rewrite incorporates only specified answers from earlier steps to turn the final question into a standalone question.For example, it rewrites a question about Todd Boehly’s former position at the firm where Mark Walter is CEO as a question naming Guggenheim Partners.Source: §C.4 · pp. 19–20

C.5 Prompt and Response of the “Predict” Procedure

  • Predict requests short factoid answers and requires each rationale statement to be attributable to the supplied context passages.The prompt describes answers as often between 1 and 5 words and illustrates passage citations in the rationale.Source: §C.5 · p. 20

D Automated Annotated Demonstrations

  • Demonstrations extend DSP (Khattab et al., 2022) by qualifying examples whose predictions match correct answers, filtering overlong sub-queries with IQR, and selecting examples by balanced sampling or KNN.KNN selects training examples closest to the input question or FEVER claim using sentence representations; balanced sampling preserves an even answer-class distribution.Source: D Automated Annotated Demonstrations · p. 25

E Baselines

F Extended Ablation Study

Three tables report HGOT+KNN hyperparameter evaluations on medium-length categories across Open-SQuAD, FEVER, and HotPotQA.

F Extended Ablation Study

  • Table 7 reports HGOT+KNN hyperparameter combinations and EM and F1 scores for medium-length Open-SQuAD.Source: Table 7 · p. 26
  • Table 8 reports HGOT+KNN hyperparameter configurations and EM scores for medium-length FEVER.Source: Table 8 · p. 27
  • Table 9 reports HGOT+KNN hyperparameter combinations and EM and F1 scores for medium-length HotPotQA.Source: Table 9 · p. 27
Loading 2402.09390v2…