Source-linked AI summary
LCoT-GV: Graph Attention Networks for Verifying Long Reasoning Chains in Large Language Models
Bérénice Jaulmes, Mehwish Alam
TL;DR
Long reasoning chains can contain flawed intermediate steps even when their final answers are correct, motivating more effective verification. LCoT-GV builds reasoning graphs with local NLI-derived relations and uses a GAT for correctness prediction. It is competitive with LCoT2Tree on average, with especially strong coding-task performance but continued difficulty on mathematical reasoning.
Problem
LCoTs may contain contradictions, irrelevant information, arithmetic inconsistencies, or unsupported inferences despite correct final answers, while existing verification methods can be local, sequential, or expensive.
Method
LCoT-GV represents reasoning steps as graph nodes with NLI-identified semantic and logical relations, then applies a Graph Attention Network to predict reasoning correctness.
Results
LCoT-GV achieves performance competitive with LCoT2Tree on average, with particularly strong performance on coding tasks while mathematical-language verification remains challenging.
Takeaways & Limitations
Graph structure provides valuable information for some downstream tasks, but semantic information is needed for further improvements and effectiveness varies by task.
Takeaways & Limitations
The evaluation procedure constrains the diversity of downstream tasks, motivating broader evaluation on non-mathematical reasoning tasks.
Abstract
from arXiv · showhide
Large Reasoning Models produce Long Chains-of-Thought (LCoTs) which involve breaking down the problem into smaller reasoning steps before reaching the conclusion. However, these steps often contain contradictions, unsupported inferences, or irrelevant steps, even when the final answer is correct. We propose Long Chain-of-Thought Graph Verifier (LCoT-GV), a graph-based framework that represents LCoTs as reasoning graphs. Each node in the graph represents a reasoning step and the edges encode semantic and logical relations. A Graph Attention Network is then trained to predict chain-of-thought correctness from the reasoning graph. We construct a new graph-oriented verification dataset from multiple reasoning benchmarks for question answering in various domains. The results show that our method is competitive with the most similar approaches.
1 Introduction
LCoTs can contain contradictory, irrelevant, or unsupported steps despite correct final answers, while existing verification methods are often local, sequential, or expensive. LCoT-GV addresses this with locally constructed reasoning graphs and reports competitive performance with LCoT2Tree.
- LCoTs may contain contradictions, arithmetic inconsistencies, irrelevant information, or unsupported inferences despite correct final answers.
- LCoT-GV represents reasoning chains as graphs and uses a Graph Attention Network to verify whether the reasoning process is correct.
- The framework constructs reasoning graphs locally with an NLI model instead of requiring multiple LLM calls, reducing computational cost.
- The authors introduce a graph-oriented verification dataset containing LCoTs, correctness labels, and graph structures derived from semantic relations.The existing DeltaBench dataset contained too few samples for training LCoT-GV.
- LCoT-GV achieves performance competitive with the most similar graph-based method, LCoT2Tree.Performance varies across downstream tasks, and the generating model has a comparatively smaller effect.
2 Related Work
Prior work represents reasoning processes with graphs or trees and evaluates reasoning at step or chain level, but often focuses on shorter CoTs or relies on LLM-generated representations. LCoT-GV instead uses NLI models to identify semantic and logical relations between LCoT steps.
- Graph-of-Verification verifies CoT nodes from the root and stops branch verification when an error is detected.
- ReasoningFlow defines nine step types and three relation types as an annotation scheme for reasoning processes.
- LCoT2Tree uses an LLM and task sketches to map thought segments to abstract depths, constructing a tree through advancement, backtracking, and branch resets.
- LCoT-GV represents reasoning steps as nodes connected by semantic and logical relations identified with NLI models rather than LLMs.This contrasts with methods that are generally dependent on LLMs to build their representations.
3 LCoT-GV
LCoT-GV splits each chain into reasoning-step nodes, connects them using NLI-based entailment or contradiction relations, and learns graph representations for correctness classification. Its construction handles candidate parents and repeated subsequences to support scalable graph building.
- Constructing Reasoning Graphs: Each LCoT step becomes a graph node, while edges represent entailment or contradiction between steps identified using NLI.Steps are split at logical-transition keywords such as “So”, “Actually”, “Let’s”, and “Wait”.
- Constructing Reasoning Graphs: Candidate parents are selected from recent main-branch nodes, highly connected earlier nodes, and leaf nodes before NLI scoring.
- Constructing Reasoning Graphs: The NLI classifier assigns entailment or contradiction scores, and the highest-scoring candidate parents receive positive or negative edges.Three highest-entailment and two highest-contradiction parents are linked to the current node.
- Constructing Reasoning Graphs: Repeated reasoning subsequences are detected and reuse the original graph structure instead of being reconstructed.This addresses chains containing thousands of nearly identical steps.
- Learning Representations from Reasoning Graphs: A GAT combines node features, edge features, and adjacency information to produce graph embeddings for final-answer correctness classification.Node features use sentence embeddings, and edge features encode relation types as one-hot vectors.
4 Experimentation
The evaluation uses a balanced multi-benchmark dataset of evaluated LCoTs and compares LCoT-GV with LCoT2Tree and a length-based classifier across several LRMs. Results show strong coding performance, weaker mathematical performance, and sensitivity to semantic features and task characteristics.
- Datasets: 8,000 evaluated LCoTs form the graph-based dataset used for experimentation.
- Datasets: The dataset evenly samples 2,000 LCoTs from each of MMLU-Pro, MATH, LiveCodeBench-v5, and GPQA, balanced across three LRMs and answer correctness.Task-specific evaluators determine correctness for multiple-choice, mathematical, and coding benchmarks.
- Datasets: The dataset uses an 80%/20% train-test split, with 10% of the training set reserved for validation.
- Experimental Setup: The experiments use DeepSeek-R1-Distill-Llama-70B, DeepSeek-R1-Distill-Qwen-32B, and QwQ-32B as generating reasoning models.
- Results: 76.58 average score across the two LRMs outperforms LCoT2Tree at 74.68.LCoT-GV gains on LCB and GPQA but drops on MATH and MMLU.
- Model Variations: Metadata-only features reduce performance to random guessing except on LCB, while removing negative edges causes a small performance drop.Combining embeddings and metadata decreases overall performance but improves LCB by +1.16.
5 Conclusion
LCoT-GV is a graph-based framework for verifying long reasoning chains, using local NLI models to reduce computational overhead. It outperforms the closest related method on average and is particularly strong on coding tasks, though mathematical language remains challenging.
- LCoT-GV uses a local NLI model instead of expensive LLM calls, reducing computational overhead and improving scalability.
- LCoT-GV outperforms the most closely related existing method on average.
- LCoT-GV performs particularly strongly on coding tasks, where reasoning is more structured.
- Verification of mathematical language remains challenging for LCoT-GV.
Limitations
The evaluation adopts a data-collection procedure from the closest related method to enable methodological comparison, but this constrains downstream-task diversity. Future work will broaden evaluation toward non-mathematical reasoning tasks.
- Using the closest related method’s data-collection procedure ensures methodological comparability but constrains downstream-task diversity.
- Future work will broaden evaluation toward non-mathematical reasoning tasks, where the approach may be better suited to LCoT verification.