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

Yihao Fang, Stephen Thomas, Xiaodan Zhu

TL;DR

This paper introduces HGOT, a novel framework that structures LLM reasoning into a hierarchical graph of thoughts. By breaking down complex queries and evaluating the quality of both thoughts and retrieved information, HGOT significantly improves the factuality of LLM responses, outperforming existing methods on several benchmarks.

What Problem Does This Paper Address?

Large Language Models (LLMs) have revolutionized NLP, but their tendency to "hallucinate" – generate factually incorrect or unsubstantiated content – poses a significant challenge, especially in critical applications. While retrieval-augmented in-context learning (RA-ICL) helps ground LLMs in external information, existing methods struggle with complex queries that require intricate planning and a structured approach to information synthesis. This paper tackles the problem of enhancing LLM factuality by developing a more robust and organized method for utilizing retrieved information, specifically addressing the challenges of dynamic graph construction and the quality assessment of reasoning steps.

Methods

The core of HGOT is its Hierarchical Graph of Thoughts (HGOT). This framework draws inspiration from the "hierarchy of goals" in neuropsychology and uses an LLM's emergent planning capabilities to construct a multi-layered graph.

  • Hierarchical Graph Construction: HGOT employs a "divide-and-conquer" strategy. Complex queries are broken down into smaller, manageable sub-queries (steps) that form a directed acyclic graph (DAG). These sub-queries can themselves be further decomposed into deeper dependency graphs, creating a hierarchical structure.
  • Search and Inference: The framework uses a topological sort to process the dependency graph sequentially. A "Probe" procedure gathers passages and scores them, while a "Plan" procedure outlines the steps and their dependencies. The "Search" procedure navigates the graph, and the "Infer" procedure synthesizes the information to predict the final answer and confidence score.
  • Thought Quality Assessment: HGOT refines the self-consistency majority voting mechanism. It incorporates citation recall and precision metrics to assess the quality of the LLM's generated thoughts (rationales). This links an answer's credibility directly to the quality of the reasoning behind it.
  • Retrieval Quality Scoring: A novel scoring mechanism is proposed for retrieved passages. This mechanism considers citation frequency and quality, self-consistency confidence, and the retrieval module's ranking, ensuring that only high-quality, relevant information is prioritized.

Datasets

The authors evaluated HGOT on three standard datasets:

  • FEVER: (Fact Extraction and VERification) - focused on verifying factual claims.
  • Open-SQUAD: (Stanford Question Answering Dataset) - a large-scale dataset for question answering.
  • HotPotQA: A dataset requiring multi-hop reasoning to answer questions.

The datasets were stratified into "Long," "Medium," and "Short" categories based on question length to analyze performance across different complexity levels.

Key Insights and Ideas

  • Structuring Thought is Key: The paper strongly suggests that simply retrieving more information isn't enough. The way LLMs process and structure their reasoning (thoughts) is crucial for factuality. HGOT's hierarchical graph approach provides this structure.
  • Quality over Quantity (for Thoughts): By explicitly measuring the quality of thoughts using citation metrics, HGOT demonstrates that better-reasoned (and cited) thoughts lead to more factual answers, even if the number of thoughts is the same.
  • Dynamic Planning is Powerful: Leveraging LLMs' emergent planning abilities to break down complex questions into a structured graph is a highly effective strategy for tackling intricate reasoning tasks.
  • Dataset Nuances Matter: Stratifying datasets by question length revealed that different models excel in different scenarios, highlighting the importance of evaluating across diverse complexity levels.

Key Results

HGOT demonstrated strong performance across the evaluated datasets:

  • FEVER: HGOT outperformed competing models by up to 7% in EM score.
  • Open-SQUAD: HGOT matched leading models like Retrieve-then-Read.
  • HotPotQA: HGOT matched leading models like DSP.

The ablation studies indicated that the presence of both thought quality and retrieval quality metrics significantly contributed to the optimal performance of HGOT, underscoring the importance of these novel components.

Limitations and Future Work

  • LLM Dependency: HGOT's performance is tied to the underlying LLM (ChatGPT in this study). Its effectiveness might vary with different LLMs.
  • Retrieval Model: The use of the Google Search API as the retrieval model might influence results; performance could differ with other search engines or domain-specific retrieval systems.
  • Generalization: While promising, the paper notes that the effectiveness of variant implementations (e.g., with different retrieval models or domain-specific data sources) has not been extensively examined.

Future work could explore integrating HGOT with other LLMs, testing it with diverse retrieval systems, and investigating its application in more complex, real-world scenarios.

Summary updated

BibTeX
@inproceedings{fang2024hgot,
  author = {Yihao Fang and Stephen Thomas and Xiaodan Zhu},
  title = {{HGOT: Hierarchical Graph of Thoughts for Retrieval-Augmented In-Context Learning in Factuality Evaluation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2024},
}
Figure