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

Yihao Fang, Stephen W. Thomas, Xiaodan Zhu

Large Language Models (LLMs) have demonstrated remarkable capabilities in reasoning and generation, yet they remain prone to "hallucinations"—generating factually incorrect but plausible-sounding information. While Retrieval-Augmented Generation (RAG) provides external context to mitigate this, standard RAG often struggles with complex, multi-step queries. This paper introduces Hierarchical Graph of Thoughts (HGOT), a framework designed to enhance factuality by structuring reasoning as a multi-layered graph and implementing rigorous quality metrics for both thoughts and retrieved information.

The Problem: Complexity and Grounding

Existing multi-hop reasoning methods like ReAct or DSP attempt to solve complex queries by asking sequential follow-up questions. However, these methods often lack a structured planning phase and a mechanism to verify if the model's intermediate "thoughts" are truly grounded in the provided sources. The authors identify a critical need for a system that can decompose problems hierarchically while evaluating the quality of citations and retrieved passages in real-time.

The HGOT Framework

HGOT operates through a recursive process involving four key stages: Probing, Planning, Searching, and Inferring. The core of the framework is built upon three pillars:

  1. Hierarchical Graph Construction: Inspired by neuropsychological models of goal-oriented behavior, HGOT decomposes a complex query (Layer 1) into simpler sub-queries (Layer 2), which can be further broken down into atomic tasks (Layer 3). This creates a Directed Acyclic Graph (DAG) where higher-level nodes depend on the successful resolution of lower-level sub-tasks.
  2. Thought Quality Assessment: Rather than relying on simple majority voting, HGOT introduces Weighted Majority Voting. The weight of an answer is determined by the quality of its rationale, calculated using Citation Recall (identifying the correct passages) and Citation Precision (ensuring citations are relevant to the specific claim).
  3. Retrieval Quality Scoring: A dynamic scoring mechanism ranks retrieved passages based on citation frequency, citation quality, model confidence, and initial search engine relevance. This ensures that only the most reliable information informs the final inference.
Figure 1: Overview of the HGOT framework, illustrating the four-stage pipeline (Probe, Plan, Search, Infer) and the hierarchical decomposition of queries into a Graph of Thoughts.

Experimental Evaluation

The authors evaluated HGOT against several strong baselines, including Vanilla LM, Retrieve-then-Read, Self-ask, ReAct, and DSP. Testing was conducted across three benchmark datasets, stratified by question length (Short, Medium, Long) to assess performance across varying complexity levels:

  • FEVER: Fact extraction and verification.
  • Open-SQuAD: Reading comprehension and question answering.
  • HotPotQA: Multi-hop reasoning across multiple documents.

Key Results and Insights

HGOT consistently outperformed existing methods across all benchmarks, particularly in complex reasoning scenarios. For instance, on the FEVER dataset, HGOT+Sampling achieved a 61.50% Exact Match (EM) score, significantly higher than the standard Retrieve-then-Read baseline (58.35%). In multi-hop tasks like HotPotQA, HGOT+KNN reached an EM of 46.62% in the medium-length category, surpassing the next best performer by nearly 5%.

Figure 6: Performance comparison of HGOT against baselines across FEVER, Open-SQuAD, and HotPotQA datasets, categorized by question length.

Key takeaways from the results include:

  • Hierarchy Improves Reliability: Breaking complex reasoning into a hierarchy of atomic goals prevents the model from losing the "thread of truth."
  • Citations as Truth Proxies: By weighting votes based on citation metrics, the system effectively filters out "confident but ungrounded" hallucinations.
  • Dynamic Adaptability: Unlike static RAG systems, HGOT's graph is dynamic; the model determines its next information needs based on what it has already discovered.

Limitations and Future Directions

While HGOT shows significant promise, the authors note several areas for future work. The current study primarily utilized gpt-3.5-turbo-1106, and performance may vary with other LLMs. Additionally, the recursive nature of building and traversing hierarchical graphs introduces higher computational latency and API costs compared to single-shot RAG. Future research will explore more robust formalizations for graph dependencies and the application of HGOT to specialized domains like legal or medical records.

Summary updated

BibTeX
@inproceedings{fang2024hgot,
  author = {Yihao Fang and Stephen W. 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