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 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 (RGV) 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: The Challenge of LLM Reasoning
While LLMs like GPT-4 have demonstrated a remarkable ability to solve complex problems using "Chain-of-Thought" (CoT) prompting, they remain prone to logical slips and hallucinations. To mitigate this, researchers often employ verifiers—secondary models that evaluate the LLM's output to determine its correctness.
Current state-of-the-art verification involves generating multiple solutions and either selecting the most common answer (Self-Consistency) or training a verifier to score each path independently. However, these methods treat every reasoning path as an isolated sequence. In reality, different ways of solving the same problem often share identical logical "milestones." By ignoring these overlaps, existing verifiers fail to capture the collective intelligence—and the collective errors—hidden in the relationships between different reasoning paths.
The GraphReason Framework
The proposed framework, GraphReason, moves from linear verification to a topological approach. It utilizes a Reasoning Graph Verifier (RGV) to analyze the logical flow across multiple generated solutions. The process operates in four main stages:
- Diverse Generation: The LLM generates a large pool of potential solutions using diverse prompts and sampling techniques.
- Graph Construction: Solutions are grouped by their final answer. For each group, a "Reasoning Graph" is built. If different solutions use the exact same arithmetic expression at any point, those steps are merged into a single node. This creates a "flow" showing how various paths converge or diverge.
- Feature Engineering: Each node (reasoning step) is assigned features based on a "Base Verifier" (a fine-tuned BERT model) that scores the semantic quality of the text. The graph also tracks structural data, such as the "in-degree" (how many paths pass through a specific step).
- Graph Verification: A Graph Isomorphism Network (GIN) processes these structures. It encodes the propagation of logic through the graph to produce a final score for that answer group. The answer with the highest-scoring graph is selected as the winner.
Reasoning as a Topology
The core innovation of GraphReason is the conceptualization of reasoning as a map rather than a simple sequence. If multiple ways of solving a problem all pass through the same intermediate equation, that equation is likely a "logical bottleneck" that carries high weight in determining the correct answer.
This approach allows the model to go beyond simple majority rule. Standard self-consistency relies on the "wisdom of the crowd," but GraphReason proves that a minority answer can be the correct one if its reasoning graph shows a more robust, interconnected logical structure than the majority's fragmented paths.
Experimental Results
GraphReason consistently outperformed existing verifiers and baseline LLM performance across four challenging benchmarks: GSM8K, SVAMP, ASDiv-a, and StrategyQA.
- Accuracy Boosts: On the GSM8K dataset, GraphReason improved
gpt-3.5-turboperformance from 72.7% (Greedy Decode) to 85.7%. - Comparative Performance: It surpassed the previous state-of-the-art "Step-aware Voting Verifier" (DIVERSE) across all datasets, notably gaining +4.3% on the StrategyQA task.
- Transferability: Even when trained on one type of data (GSM8K), the verifier generalized well to other math datasets, suggesting it learned the fundamental nature of logical flow rather than just memorizing specific equations.
Conclusion and Future Work
GraphReason demonstrates that the "shape" of logic—the structural synergy between semantic content and topological connection—is a powerful signal for verification. While the approach faces hurdles such as computational cost and the difficulty of merging semantically identical but linguistically different natural language steps, it represents a significant advancement in LLM reliability. Future work aims to refine node-merging logic using advanced semantic similarity tools and to optimize the framework for even more complex, non-mathematical reasoning tasks.
Summary updated