GoT: Effective Graph-of-Thought Reasoning in Language Models

Yao Yao, Zuchao Li, Hai Zhao

Introduction

Human reasoning is rarely a straight line; it is a complex web of interconnected ideas, logical leaps, and revisited concepts. While Large Language Models (LLMs) have made significant strides using Chain-of-Thought (CoT) prompting, these methods are fundamentally constrained by their linear nature. This paper introduces Graph-of-Thought (GoT), a framework that models reasoning as a graph, allowing models to transcend linear sequences and capture the intricate, non-linear formations of true deductive logic.

The Limitations of Linear Reasoning

Existing improvements to prompting, such as Tree-of-Thought (ToT), introduce branching paths but still struggle to represent the dense interconnections inherent in human cognition. We often jump between seemingly unrelated ideas or connect multiple disparate concepts simultaneously to reach a conclusion. The authors identify that current models neglect this structural information. GoT bridges this gap by explicitly modeling thoughts as nodes and their logical connections as edges, enabling the model to perceive the "shape" of a reasoning process.

The GoT Framework

The GoT framework employs a sophisticated two-stage reasoning process designed to integrate structural information with natural language processing.

  1. Rationale Generation: The model first generates natural language rationales based on the input question and context.
  2. Answer Inference: The model predicts the final answer by fusing standard text and visual features with a newly constructed thought graph.
The GoT reasoning pipeline, illustrating the transition from text and vision features to a structured graph-based rationale and final answer inference.

At the heart of GoT is the Extract-Cluster-Coreference (ECC) process. It uses Open Information Extraction (OpenIE) to pull subject-verb-object triplets from the text. These triplets are then clustered to identify different mentions of the same entity, creating a dense, interconnected graph. This graph is processed by a Graph Attention Network (GAT), and the resulting features are integrated with standard representations using a gated fusion mechanism.

Multimodal Integration and Benchmarking

GoT is particularly effective in multimodal settings where diagrams or images provide critical context. For instance, in science questions involving life cycles or physical processes, the model can map visual components directly into the thought graph.

Example of vision features used in the GoT framework, such as a diagram of a fern's life cycle, which provides critical context for multimodal reasoning tasks.

The authors evaluated GoT on two primary benchmarks:

  • ScienceQA: A large-scale multimodal dataset (21k questions) covering natural and social sciences.
  • AQUA-RAT: A text-only dataset containing approximately 100,000 algebraic word problems.

Key Results: Surpassing Human Performance

The results demonstrate that graph-based reasoning provides a significant competitive edge:

  • ScienceQA SOTA: GoT-T5_base achieved 87.59% accuracy, a 2.4% improvement over the previous state-of-the-art (Multimodal-CoT).
  • Surpassing Humans: The larger GoT-T5_large reached 90.81% accuracy on ScienceQA, notably higher than the human average of 88.40%.
  • Efficiency: GoT allows smaller models (like T5-base with 223M parameters) to outperform much larger models like GPT-3.5 in specific reasoning tasks.

Key Insights: Why Structure Matters

The paper reveals several critical insights into why the graph approach succeeds:

  • Structure as a Superpower: Ablation studies showed that simply concatenating triplets as text led to lower accuracy. The GAT's ability to perceive structural relationships is vital to the model's success.
  • Robustness to Hallucinations: Even when a model generates a partially incorrect rationale, the graph structure helps it "filter" the noise and focus on key nodes to arrive at the correct answer.
  • Complexity Scaling: The performance gap between GoT and standard CoT widened as questions became more difficult, suggesting that graph-based reasoning is essential for high-complexity logical dependencies.

Conclusion and Future Work

While GoT introduces a small amount of computational overhead (approximately 0.2% increase in parameters), the gains in accuracy and robustness are substantial. Future work will explore more sophisticated graph construction methods and apply the GoT framework to even broader sets of reasoning tasks beyond the domains of math and science.

Summary updated

Abstract

With the widespread use of language models (LMs) in NLP tasks, researchers have discovered the potential of Chain-of-thought (CoT) to assist LMs in accomplishing complex reasoning tasks by generating intermediate steps. However, human thought processes are often non-linear, rather than simply sequential chains of thoughts. Therefore, we propose Graph-of-Thought (GoT) reasoning, which models human thought processes not only as a chain but also as a graph. By representing thought units as nodes and connections between them as edges, our approach captures the non-sequential nature of human thinking and allows for a more realistic modeling of thought processes. GoT adopts a two-stage framework with an additional GoT encoder for thought graph representation and fuses the graph representation with the original input representation through a gated fusion mechanism. We evaluate GoT’s performance on a text-only reasoning task (AQUA-RAT) and a multimodal reasoning task (ScienceQA). Our model achieves significant improvement over the strong CoT baseline on the AQUA-RAT test set and boosts accuracy from 85.19% to 87.59% using the T5-base model over the state-of-the-art Multimodal-CoT on the ScienceQA test set. Our code is publicly available at https://github.com/Zoeyyao27/Graph-of-Thought
BibTeX
@inproceedings{yao2024got,
  author = {Yao Yao and Zuchao Li and Hai Zhao},
  title = {{GoT: Effective Graph-of-Thought Reasoning in Language Models}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2024},
  doi = {10.18653/v1/2024.findings-naacl.183},
}
Figure