ACL Findings2025
Self-attention-based Graph-of-Thought for Math Problem Solving
Ruiqiao Bai, Xue Han, Shuo Lei, Junlan Feng, Yanyan Luo, Chao Deng
Abstract
Applying Large Language Models (LLM) to solve math problems is one of the hottest research topics at present. Traditional Chain-of-Thought-based methods typically generate the reasoning path in a chain structure, leading to unnecessary interference caused by non-zero self-attention among weakly related reasoning steps. Such a setting also differs from humans' typical graph-structured reasoning habit (with an inter-step relationship graph in mind). To solve the problem, this paper proposes a novel decoding method for Transformer-based LLM, named Self-attention-based Graph-of-Thought (SaGoT). SaGoT constructs a thought graph simultaneously as an LLM inference (based on a newly defined inter-step self-attention indicator), and generates reasoning steps with a novel graph-structured self-attention mechanism. It is a significant contribution for SaGoT to enable an LLM's graph-like reasoning ability by modifying its inner working operations, compared to SOTA prompting methods that are ex-post, rely on huge LLMs and redundant reasoning step generation to form a graph (inefficient & non-human-like). In addition, SaGoT is a training-free technique that can be seamlessly incorporated into pre-trained Transformer-based LLMs. Our experimental results have shown that SaGoT could significantly enhance mathematical reasoning accuracy without the reliance on huge computationally over-expensive LLMs. It also avoids SOTA methods' performance degradation issues when the LLM is too small to comprehend complex prompts. Moreover, SaGoT integrates intrinsic interpretability into the LLM's reasoning procedure, intuitively assisting humans in understanding how an LLM views the relationships among its reasoning steps, and why the LLM succeeds or fails.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph cites Graph of Thoughts: Solving Elaborate Problems with Large Language Models
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Least-to-Most Prompting Enables Complex Reasoning in Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Graph of Thoughts: Solving Elaborate Problems with Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Graph of Thoughts: Solving Elaborate Problems with Large Language Models cites Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models
- Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models cites Least-to-Most Prompting Enables Complex Reasoning in Large Language Models
- Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
Cited by top-tier papers1
Builds on10
- Chain-of-Thought Prompting Elicits Reasoning in Large Language ModelsJason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma et al.NeurIPS 2022 · 22,562 citations
- Graph of Thoughts: Solving Elaborate Problems with Large Language ModelsMaciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger et al.AAAI 2024 · 1,292 citations
- Least-to-Most Prompting Enables Complex Reasoning in Large Language ModelsDenny Zhou, Nathanael Schärli, Le Hou, Jason Wei et al.ICLR 2023 · 318 citations
- Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language ModelsLei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu et al.ACL 2023 · 249 citations
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge GraphJiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang et al.ICLR 2024 · 247 citations
Related papers
- Chain-of-Thought Reasoning Without PromptingXuezhi Wang, Denny ZhouNeurIPS 2024 · 305 citations
- Step Guided Reasoning: Improving Mathematical Reasoning using Guidance Generation and Step ReasoningLang Cao, Yingtian Zou, Chao Peng, Renhong Chen et al.EMNLP 2025 · 7 citations
- Towards Revealing the Mystery behind Chain of Thought: A Theoretical PerspectiveGuhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye et al.NeurIPS 2023 · 470 citations
- Large Language Models are Better Reasoners with Self-VerificationYixuan Weng, Minjun Zhu, Fei Xia, Bin Li et al.EMNLP Findings 2023 · 110 citations
- Premise-Augmented Reasoning Chains Improve Error Identification in Math reasoning with LLMsSagnik Mukherjee, Abhinav Chinta, Takyoung Kim, Tarun Anoop Sharma et al.ICML 2025
