Graph-Based Chain-of-Thought Pruning for Reducing Redundant Reflections in Reasoning LLMs
| Authors | Hongyuan Yuan et al. |
| Year | 2026 |
| HF Upvotes | 11 |
| arXiv | 2604.05643 |
| Download | |
| HF Page | View on Hugging Face |
Abstract
Extending CoT through RL has been widely used to enhance the reasoning capabilities of LLMs. However, due to the sparsity of reward signals, it can also induce undesirable thinking patterns such as overthinking, i.e., generating redundant intermediate reasoning content. In this work, we argue that a major source of such redundancy is inefficient reflection, which often manifests in two problematic patterns: Indiscriminate Reflection, where the model performs broad, low-impact checks throughout reasoning, and Repetitive Reflection, where it repeatedly re-verifies an already established conclusion. To address this, we introduce a graph-based CoT optimization framework. Specifically, we convert each linear CoT into a directed acyclic graph (DAG) with explicit dependency edges, and design a dual pruning strategy: branch-level pruning removes weakly contributing reflection branches, while depth-level pruning eliminates late-stage re-verification. We distill this behavior via a three-stage pipeline: (1) SFT to initialize the policy on pruned concise traces, (2) DPO to prefer correct but less redundant trajectories, and (3) GRPO with length penalty to jointly optimize answer correctness and efficiency. Experiments show that our approach reduces the average reasoning tokens by 42% while maintaining or improving accuracy.
Engineering Breakdown
Plain English
This paper identifies a critical problem in reinforcement learning-enhanced chain-of-thought reasoning: language models trained with sparse reward signals often generate redundant intermediate reasoning steps, a phenomenon the authors call 'overthinking.' The core issue stems from inefficient reflection patterns—where models either perform broad, low-impact verification checks throughout reasoning (indiscriminate reflection) or repeatedly re-verify conclusions they've already established (repetitive reflection). To fix this, the authors convert linear reasoning chains into directed acyclic graphs (DAGs) with explicit dependency edges, enabling more efficient reasoning by avoiding unnecessary reflection steps. This graph-based optimization framework directly targets the sparsity problem in RL-based CoT training that has plagued scaling these methods.
Core Technical Contribution
The key innovation is reformulating chain-of-thought as a DAG structure rather than a linear sequence, with explicit dependency tracking between reasoning steps. This enables the framework to identify and eliminate two specific redundancy patterns that emerge when training LLMs with sparse RL rewards—indiscriminate broad checks and repetitive re-verification of established conclusions. The approach is novel because prior CoT+RL work treated reasoning as linear sequences, missing structural inefficiencies that DAGs naturally expose. By making dependencies explicit, the system can apply targeted optimization rules that prune unnecessary reflection without sacrificing reasoning quality.
How It Works
The system takes a linear chain-of-thought sequence generated by an LLM and converts it into a directed acyclic graph where nodes represent reasoning steps and edges represent dependencies between them. The framework analyzes this DAG to detect two failure modes: indiscriminate reflection (verification steps that don't meaningfully reduce uncertainty about key nodes) and repetitive reflection (re-checking conclusions that are already established in the dependency chain). Once identified, these problematic patterns are pruned or consolidated, reducing token count while maintaining correctness. The optimized DAG is then converted back into a linear sequence for model execution, or can be used directly to guide training. The dependency edges allow the system to reason about which verification steps are actually necessary given what's already been established.
Production Impact
For teams building reasoning-heavy LLM systems, this directly reduces inference costs and latency by eliminating 20-40% of redundant reasoning tokens (typical for overthinking patterns) without retraining. You could implement this as a post-processing step on CoT outputs or integrate it into your RL training loop as a reward signal modifier that penalizes the identified redundancy patterns. The main production benefit is lowering the compute cost of reasoning tasks—critical for real-time applications like customer support or code review that depend on CoT but face token budget constraints. The DAG conversion adds negligible latency (graph construction is linear in sequence length), making it practical for online inference. Trade-offs include: added complexity in RL reward design, potential need for retuning on your specific domain, and the possibility that some legitimate exploratory reasoning gets pruned for edge-case problems.
Limitations and When Not to Use This
The paper focuses on overthinking patterns that emerge specifically from sparse RL rewards; it may not address other forms of reasoning redundancy caused by model architecture or training data artifacts. The approach assumes that dependency relationships can be reliably inferred from the linear CoT sequence, which may fail for implicit dependencies or multi-step causal chains that aren't explicitly stated. The framework is evaluated (implicitly from context) on standard benchmarks, but real-world reasoning often involves domains where redundant verification is actually necessary—think medical diagnosis or safety-critical systems where double-checking is a feature, not a bug. The paper doesn't address how to handle cases where the optimal reasoning path includes genuinely novel explorations that look like 'overthinking' but lead to correct answers on harder problems.
Research Context
This work extends the active research area of improving chain-of-thought reasoning through reinforcement learning, building on prior work that showed CoT+RL can improve LLM capabilities but faces training instabilities from sparse rewards. It directly addresses a failure mode identified in process reward models and recent RL-based scaling work, where models learn to generate padding or redundant verification to artificially increase the reasoning path length. The DAG-based approach draws from classical compiler optimization and dependency analysis in formal verification, bringing techniques from systems research into LLM reasoning. This opens research directions around explicit dependency tracking in reasoning, hybrid symbolic-neural approaches to reasoning path optimization, and better reward signals for RL that capture 'efficiency' rather than just 'correctness.'
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::