Self-attention-based Graph-of-Thought for Math Problem Solving (2025)

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.

## introduction a large language model (llm) is a deep learning model capable of handling various natural language tasks (such as text classification and question answering) and has a large number of parameters. at present, llms employed in academia and industry are commonly based on the transformer architecture, whose core technology is the self-attention mechanism @xcite . in addition to improving model performance, an advantage of the self-attention mechanism is that it can help people interpret an llm's inner working procedure by showing how the model distributes weights among tokens @xcite @xcite . applying llms to solve math problems is one of the hottest research areas at present, and the chainof-thought (cot) technology has been widely applied to such a task (see section 2.1). in a nutshell, cot requires the llm to output texts describing the reasoning steps before generating the final answer @xcite . however, traditional cot-based methods usually generate reasoning steps in a chain structure (see figure 1(a) ). this might prevent humans from knowing whether the llm correctly understands and utilizes the relationship among its reasoning steps (as depicted in figure 1 (b), a human-like deduction trajectory is a graph instead of a chain). in addition, some non-zero self-attention values among weakly related reasoning steps might disturb subsequent model outputs, resulting in lower accuracy of the final answer (as verified by our experiments in section 5). recently, scholars have noticed that combining cot with the graph structure improves llms' responses to complex questions (see section 2.2). however, there is still a lack of methods that efficiently mirror humans' ability (without generating redundant reasoning steps/paths that might be wrong) to directly come up with a new reasoning step based on a graph structure in mind, which depicts the relationships among existing reasoning steps @xcite . besides, some techniques require additional model training that's resource-consuming @xcite , and there is an ignorance of employing selfattention rectification for graph construction. on the other hand, possessing a graph-based reasoning ability is essential for clearly teasing out the relationships among intermediate reasoning steps, and self-attention is a valuable entry point for achieving such a goal, as it involves the llm's inner working mechanism and potentially solves the problem from a fundamental perspective of the decoding technique. to fill the research gap, this paper proposes a novel training-free decoding method for transformer-based llms to solve math problems, namely the self-attention-based graph of thought (sagot), which 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 thought graphbased self-attention mechanism. the thought graph could effectively reflect how llm views the relationships among its reasoning steps, and thus could better assist humans in interpreting an llm's inner working mechanisms compared to traditional cot (see figure 1 ). it is a great novelty and significant contribution for sagot to enable an llm to follow a human-like graph-structured reasoning trajectory by modifying the llm's inner working operations (i.e. integrating intrinsic interpretability), compared to solely prompting-based methods that are ex-post @xcite @xcite ), rely on huge llms such as gpt-4 @xcite , and have to gen-erate redundant reasoning paths/steps to form a graph (which is inefficient and non-human-like, see section 2.2 for details). for instance, the tree-of-thought (tot) method integrates multiple reasoning paths to build a graph, while each path is still generated via a chain-based reasoning structure by the llm @xcite . however, a single reasoning path is usually enough for a human being to establish a reasoning graph @xcite . to solve the problem, sagot is designed to significantly differ from existing approaches, and drive an llm to be more human-like by enabling a single-path-based graph-structured reasoning procedure. our experimental results have shown that sagot could consistently enhance the llm's accuracy in solving math problems compared to sota methods, without additional model training or reliance on huge llms that are computationally overexpensive. it avoids prompting-based reasoning methods' performance degradation issue when the llm is too small to comprehend/achieve the task stated in the complex prompts used for graph construction. moreover, sagot successfully integrates intrinsic interpretability into the llm's reasoning procedure. the thought graph generated could intuitively assist human interpretation of how an llm views the relationships among its reasoning steps, and trace why the llm succeeds or fails in question answering. in the following paper, a literature review of related work is presented in section 2, section 3 illustrates the sagot method systematically, and section 4 introduces our experimental setting. results and thorough discussions of the experiments are provided in section 5. we conclude our analysis and point out the limitations in sections 6 and 7. ## experimental setup as sagot targets open-source small-sized llms, the qwen2-1.5b base model (a decoder-only transformer-based llm) has been employed in our experiments @xcite . the base models of qwen2-7b (qwenteam, 2024), llama3-8b @xcite and llama2-13b @xcite have also been used to examine the sagot's performance when the model scales up. more detailed model hyperparameter settings are illustrated in appendix b. we utilize the open framework opencompass 2.0 (opencompass, 2023) for performance evaluation, and datasets employed include gsm8k @xcite and mathbench-a @xcite . gsm8k is a dataset of english grade school math problems and answers created by humans, including over 1.3k test samples. mathbench-a (annotated as mb) comprises 1.5k math questions covering five stages (arithmetic, primary, middle, high, college) and two languages (english and chinese, denoted as e and c) (liu ## conclusion this paper proposes a novel decoding method named sagot enabling llms to perform humanlike graph-structured mathematical reasoning. experimental results show that sagot could effectively enhance an llm's mathematical reasoning accuracy while exempting the reliance on huge llms that are resource-consuming. it is a trainingfree technique with a thought graph generated that could assist humans in interpreting how an llm views the relationships among its reasoning steps. in the future, a potential research direction is to adapt sagot to llm with the mixture-of-experts structure by enabling different experts to generate different thought graphs, which might focus on different aspects of the inter-step relationships. it could be meaningful for sagot to assist humans in interpreting how the experts diverge in their reasoning approaches. moreover, although sagot is designed to be a training-free technique that enables the llm to have a graph-structured reasoning ability by its inherent working mechanism, it could also shed light on the llm training technique by integrating the graph-structured self-attention mechanism into the model training procedure. specifically, graph-structured training mechanisms might make use of human-annotated inter-reasoning relationships to guide the inter-step self-attention formulation. we would like to encourage further investigations into that.