# GraphReason: Enhancing Reasoning Capabilities of Large Language Models through A Graph-Based Verification Approach

arXiv: https://arxiv.org/abs/2308.09267 · HTML: https://mlsanity.com/paper/2308.09267/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 18 Aug 2023.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 16 of 16)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge](https://mlsanity.com/paper/1811.00937/) (2018)
- [Are NLP Models really able to Solve Simple Math Word Problems?](https://mlsanity.com/paper/2103.07191/) (2021)
- [Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies](https://mlsanity.com/paper/2101.02235/) (2021)
- [A Diverse Corpus for Evaluating and Developing English Math Word Problem Solvers](https://mlsanity.com/paper/2106.15772/) (2021)
- [Can language models learn from explanations in context?](https://mlsanity.com/paper/2204.02329/) (2022)
- [Making Large Language Models Better Reasoners with Step-Aware Verifier](https://mlsanity.com/paper/2206.02336/) (2022)
- [CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text](https://mlsanity.com/paper/1908.06177/) (2019)
- [Logic-Driven Context Extension and Data Augmentation for Logical Reasoning of Text](https://mlsanity.com/paper/2105.03659/) (2021)
- [Turning Tables: Generating Examples from Semi-structured Tables for Endowing Language Models with Reasoning Skills](https://mlsanity.com/paper/2107.07261/) (2021)
- [The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers](https://mlsanity.com/paper/1808.07290/) (2018)
- [Seeking Patterns, Not just Memorizing Procedures: Contrastive Learning for Solving Math Word Problems](https://mlsanity.com/paper/2110.08464/) (2021)

## Built on by (most cited first, 21 of 21)

- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [Evaluating LLM-based Agents for Multi-Turn Conversations: A Survey](https://mlsanity.com/paper/2503.22458/) (2025)
- [Graph Meets LLMs: Towards Large Graph Models](https://mlsanity.com/paper/2308.14522/) (2023)
- [TableMaster: A Recipe to Advance Table Understanding with Language Models](https://mlsanity.com/paper/2501.19378/) (2025)
- [SuperRL: Reinforcement Learning with Supervision to Boost Language Model Reasoning](https://mlsanity.com/paper/2506.01096/) (2025)
- [A Survey of Large Language Models on Generative Graph Analytics: Query, Learning, and Applications](https://mlsanity.com/paper/2404.14809/) (2024)
- [Pelican: Correcting Hallucination in Vision-LLMs via Claim Decomposition and Program of Thought Verification](https://mlsanity.com/paper/2407.02352/) (2024)
- [A Survey on Feedback-based Multi-step Reasoning for Large Language Models on Mathematics](https://mlsanity.com/paper/2502.14333/) (2025)
- [Not All Tokens Matter: Towards Efficient LLM Reasoning via Token Significance in Reinforcement Learning](https://mlsanity.com/paper/2506.08125/) (2025)
- [Scaling Graph Chain-of-Thought Reasoning: A Multi-Agent Framework with Efficient LLM Serving](https://mlsanity.com/paper/2511.01633/) (2025)
- [Assessing the Reasoning Capabilities of LLMs in the context of Evidence-based Claim Verification](https://mlsanity.com/paper/2402.10735/) (2024)
- [Towards A Unified View of Answer Calibration for Multi-Step Reasoning](https://mlsanity.com/paper/2311.09101/) (2023)
- [Reasoning with Graphs: Structuring Implicit Knowledge to Enhance LLMs Reasoning](https://mlsanity.com/paper/2501.07845/) (2025)
- [Modeling Complex Mathematical Reasoning via Large Language Model based MathAgent](https://mlsanity.com/paper/2312.08926/) (2023)
- [Reasoning Graph Enhanced Exemplars Retrieval for In-Context Learning](https://mlsanity.com/paper/2409.11147/) (2024)
- [Toward Consistent World Models with Multi-Token Prediction and Latent Semantic Enhancement](https://mlsanity.com/paper/2604.06155/) (2026)
- [TuringQ: Benchmarking AI Comprehension in Theory of Computation](https://mlsanity.com/paper/2410.06547/) (2024)
- [Diagnosing Multi-step Reasoning Failures in Black-box LLMs via Stepwise Confidence Attribution](https://mlsanity.com/paper/2605.19228/) (2026)
- [From Chains to Graphs: Self-Structured Reasoning for General-Domain LLMs](https://mlsanity.com/paper/2601.03597/) (2026)
- [Matching Game Preferences Through Dialogical Large Language Models: A Perspective](https://mlsanity.com/paper/2507.20000/) (2025)
- [TRACE: Trajectory Selection for Parallel Scaling of Search Agents](https://mlsanity.com/paper/2609.39912/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have showcased impressive reasoning capabilities, particularly when guided by specifically designed prompts in complex reasoning tasks such as math word problems. These models typically solve tasks using a chain-of-thought approach, which not only bolsters their reasoning abilities but also provides valuable insights into their problem-solving process. However, there is still significant room for enhancing the reasoning abilities of LLMs. Some studies suggest that the integration of an LLM output verifier can boost reasoning accuracy without necessitating additional model training. In this paper, we follow these studies and introduce a novel graph-based method to further augment the reasoning capabilities of LLMs. We posit that multiple solutions to a reasoning task, generated by an LLM, can be represented as a reasoning graph due to the logical connections between intermediate steps from different reasoning paths. Therefore, we propose the Reasoning Graph Verifier (GraphReason) to analyze and verify the solutions generated by LLMs. By evaluating these graphs, models can yield more accurate and reliable results.Our experimental results show that our graph-based verification method not only significantly enhances the reasoning abilities of LLMs but also outperforms existing verifier methods in terms of improving these models' reasoning performance.