G raph R eason: Enhancing Reasoning Capabilities of Large Language Models through A Graph-Based Verification Approach (2024)

Abstract: 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.

## introduction large language models (llms) have demonstrated exceptional capabilities in a variety of human tasks @xcite . among the many abilities llms possess, their reasoning capacity is of paramount importance @xcite . this has been substantiated by recent progresses @xcite @xcite . equipped with the ability to reason, especially in a multistep manner, llms can decompose complex prob-q: janet's ducks lay 16 eggs per day. she eats three for breakfast every morning and bakes muffins for her friends every day with four. she sells the remainder at the farmers' market daily for $2 per fresh duck egg. how much in dollars does she make every day at the farmers' market? lems into simpler tasks, thereby facilitating their resolution. in everyday life, many complex tasks typically require multi-step solutions. a prime example of a reasoning task is arithmetic reasoning, also known as solving math word problems @xcite . these math word problems represent simplified versions of complex real-life situations. the reasoning ability is inherent in large language models (llms), but it necessitates specific methods for manifestation. to activate the robust reasoning capability of llms, the use of specially designed prompts should be considered. numerous methods have been proposed to tap into this potential, among which chain-of-thought reasoning @xcite and in-context learning @xcite are two notable approaches. chainof-thought reasoning can elucidate the reasoning paths during the process. in-context learning fur-nishes llms with exemplary cases, thereby enabling them to learn from and simulate these examples for improved results. in the arithmetic reasoning scenario, gpt-4 can achieve an accuracy of 92% on the gsm8k dataset using 5-shot chainof-thought prompts @xcite . this represents a level of difficulty that a bright middle school student should be capable of handling. as depicted in figure 1 , this illustrates a multi-step arithmetic reasoning process in llms. in addition to further training of llms and prompt design, some methods have been proposed to enhance the reasoning capabilities of llms from the perspective of output verification. the primary idea is to have llms generate reasoning paths multiple times, and then design a verifier to evaluate these paths and deliver the final results. @xcite introduces the concept of self-consistency, based on the intuition that a complex reasoning problem usually allows for multiple thought processes, all leading to a unique correct answer. @xcite also proposes all roads lead to rome, which introduces a step-aware verifier to analyze reasoning paths not just through the entire path, but at every step. however, both methods treat each reasoning path as an independent entity and do not consider the potential interrelation and interaction between different reasoning paths. once reasoning paths are disassembled into steps, intermediate steps from one path may bear reasoning relations to other reasoning paths. these methods do not perceive all llm outputs for a given input as a collective entity, thereby failing to analyze the internal relations of all candidate paths in depth. inspired by these observations, we propose reasoning graph verifier (graphreason) in this paper. we posit that reasoning paths of one question can form reasoning graphs, where similar intermediate reasoning steps can be merged into the same node. with a graph structure, we can more effectively model and capture the reasoning logic between intermediate steps from different reasoning paths. specifically, we first construct a reasoning graph based on all outputs from llms, and then train a verifier to learn the relationship between the graph structure and the final answer. during the prediction stage, we process the data in the same way as in the training stage, and use the verifier to evaluate each reasoning graph. we then select the reasoning graph with the highest score, using its answer as the final answer. to the best of our knowledge, we are the first to approach reasoning logic of llms from a graph perspective. we conduct extensive experiments to demonstrate the improvements over the original llms, and show that our method outperforms other verifiers. in summary, our contributions are as follows: reasoning of large language models has garnered significant attention and demonstrated immense potential. recent advancements in llms suggest that the ability for multi-step reasoning is already embedded within these large-scale models @xcite , such as palm @xcite , @xcite . therefore, providing an adequate prompt is sufficient to utilize this reasoning ability. for example, the prompting method proposed by @xcite , which is based on a chain-of-thought, could aid llms in generating text with arithmetic reasoning and common factual knowledge. following @xcite , experiments on current language models demonstrated that chain-of-thought prompting could enhance the accuracy of solving math problems from 18% to 57%. @xcite included explanations in the in-context examples and tested the influence of explanations by evaluating the score between explain-then-predict and predict-then-explain. moreover, @xcite suggested a two-stage prompting strategy, leastto-most prompting, which breaks down a complex problem into a series of subproblems and solves them step-by-step. @xcite proposed sampling multiple times from diverse prompts to enhance the variety of responses. in addition to designing prompts, adopting additional strategies like verifier has contributed to enhancing the performance of reasoning abilities of large language models. for instance, @xcite proposes self-consistency, which involves sampling different reasoning paths from the language model, and then returning the most consistent final answer via majority voting. @xcite used a step-aware voting verifier to enhance the reasoning ability of llms from two perspectives. these methods strive to augment the reasoning abilities or yield superior reasoning results without necessitating additional training of llms. our work continues this research direction, with a specific focus on developing a novel graph-based verifier to boost the reasoning capabilities of llms. ## experiments in this section, we conducted extensive experiments to demonstrate the performance of graphreason, along with a more in-depth analysis. universally, we reproduced all types of verifiers to report their results based on the same generated solutions. our experiments are conducted in two settings: arithmetic reasoning and commonsense reasoning. we ensured a fair comparison by setting the same random seed, using the same hardware environment, and applying similar hyperparameters. we used accuracy as the metric to evaluate the ability of solving math word problems, which determines whether the final answer is correct or not. ## conclusion in this paper, we propose graphreason, a novel and general method to enhance the reasoning abilities of large language models. our method is the first to approach reasoning logic of large language models from a graph perspective and verifies candidate reasoning paths accordingly. we demonstrate the superiority of graphreason through extensive experiments.