Source-linked AI summary
Graph-Based Chain-of-Thought Pruning for Reducing Redundant Reflections in Reasoning LLMs
Hongyuan Yuan, Xinran He, Run Shao, Bolei He, Xianwei Xue, Mengke Chen, Qiutong Pan, Haiwei Wang, Haifeng Li
TL;DR
Overthinking in reasoning LLMs can arise from inefficient reflection, including broad checks and repeated verification. The paper converts chains of thought into dependency graphs, prunes redundant reflection, and distills the behavior through SFT, DPO, and GRPO with a length penalty. Experiments report 42% fewer average reasoning tokens while maintaining or improving accuracy.
Problem
Sparse and delayed RL rewards can induce overthinking, where redundant intermediate reasoning increases inference cost, especially through indiscriminate and repetitive reflection.
Method
The method converts reasoning chunks into dependency-structured graphs, applies branch-level and depth-level pruning, then trains with SFT, DPO, and GRPO with a length penalty.
Results
The approach reduces average reasoning length from 8134 to 4660 tokens on DeepSeek-R1-Distill-Qwen-7B while improving average accuracy from 59.72 to 60.95.
Takeaways & Limitations
Graph-based structural modeling can produce more concise reasoning paths while preserving essential logic and maintaining or improving accuracy in the evaluated mathematical reasoning setting.
Takeaways & Limitations
The approach requires a strong teacher model for graph construction, and its generalization beyond mathematical reasoning remains unclear.
Abstract
from arXiv · showhide
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.
1 Introduction
Reinforcement learning can improve reasoning by encouraging longer chains of thought, but sparse rewards may also produce overthinking through inefficient reflection. The paper models reasoning dependencies as graphs and prunes redundant reflection before distilling concise reasoning behavior.
- Motivation: Sparse and delayed RL rewards can make credit assignment difficult over long trajectories, encouraging redundant intermediate reasoning that raises inference cost.The paper identifies this behavior as overthinking.
- Motivation: The paper distinguishes Indiscriminate Reflection from Repetitive Reflection as two forms of reflection that add no useful information to the main reasoning chain.The first broadly checks trivial steps; the second repeatedly re-checks already verified conclusions.
- Graph-Based Optimization: Linear chains of thought are represented as graphs with reasoning units, dependency edges, and semantic roles for Progress and Review nodes.Graph construction uses sequential processing of CoT steps conditioned on the partially built graph.
- Graph-Based Optimization: Branch-level pruning removes narrow, weakly contributing review branches, while depth-level pruning targets later review nodes that repeatedly re-verify validated conclusions.The dual strategy maps each pruning operation to one identified redundancy pattern.
- Training: The training pipeline uses supervised fine-tuning, DPO preference alignment, and GRPO with a length penalty to optimize correctness and reasoning efficiency.DPO contrasts concise and redundant trajectories, while GRPO uses final-answer correctness as the primary signal.
2 Related Work
Related work improves long-chain reasoning through CoT prompting, supervised fine-tuning, and reinforcement learning, while also addressing overthinking through length control or within-trajectory redundancy removal. This paper instead focuses on redundant self-reflection steps.
- CoT and Reinforcement Learning: CoT prompting and later SFT on CoT-annotated data aim to improve complex reasoning and internalize intermediate-step generation.These approaches enable models to generate reasoning steps at inference time.
- CoT and Reinforcement Learning: Reinforcement learning uses outcome-based supervision for verifiable-answer domains, with GRPO becoming a widely adopted method for long-chain reasoning.The related-work discussion places RL at the center of recent reasoning post-training.
- Redundancy Reduction: Existing anti-overthinking methods regulate reasoning budgets or introduce length-aware training objectives to control overall chain length.Examples include token-budget assignment and length-aware reinforcement-learning objectives.
- Redundancy Reduction: Other methods identify low-information steps or tokens using importance, perplexity, or entropy cues, whereas this paper targets redundant self-reflection behavior directly.The distinction is between generic trajectory content reduction and reflection-specific pruning.
3 Methodology
The method converts linear chain-of-thought into dependency-aware graphs, prunes redundant reflection, and trains a policy for concise, accurate reasoning through supervised and preference-based optimization.
- Graph Construction: The method splits reasoning into chunks and incrementally reconstructs them as a DAG with dependency edges and progress/review node labels.An external LLM decides whether to insert or merge nodes while preserving logical dependencies.
- Graph Construction: Progress nodes advance the reasoning frontier, whereas review nodes check, restate, delete, or rewind existing material without advancing it.This distinction operationalizes reflective behavior for subsequent pruning.
- Graph-Based Pruning Criteria: Branch-level pruning removes review nodes with fewer than k descendants because they initiate narrow side branches that rarely develop into the main trajectory.The descendant set contains all nodes reachable from a node, and B(v) counts those descendants.
- Training Pipeline: The training pipeline uses cold-start SFT, DPO over redundancy-ranked correct trajectories, and GRPO with length penalty to optimize reasoning efficiency and correctness.SFT trains on pruned traces; DPO prefers concise trajectories; GRPO regularizes correct trajectories by length.
- Graph-Based Pruning Criteria: Depth-level pruning removes late review nodes whose relative depth exceeds threshold m because they typically represent post-answer backtracking or repeated self-checking.Node depth is the shortest-path length from a source node, while dmax is the terminal-node depth.
- Training Pipeline: GRPO assigns correctness rewards and applies length regularization only to correct trajectories, penalizing substantially longer outputs relative to the shortest correct candidate.Near-shortest correct trajectories receive almost no penalty, while longer correct trajectories receive increasingly larger penalties.
4 Experiments
The experiments evaluate the method across five mathematical reasoning benchmarks and two model scales, comparing it with efficiency-oriented baselines. Results report improved accuracy with substantially shorter reasoning traces, while stage-wise ablations separate accuracy from generation length.
- Experiment Setup: Evaluation covers AIME24, AIME25, AMC23, MATH500, and OlympiadBench across different mathematical difficulty levels.Each problem uses 10 sampled solutions; the study reports average accuracy and average generated tokens.
- Main Results: On the 7B model, average accuracy rises from 59.72 to 60.95 while average reasoning length falls from 8134 to 4660 tokens, a 42.7% reduction.The gains include AIME25 accuracy increasing from 29.00% to 31.67% and OlympiadBench accuracy increasing from 56.77% to 59.85%.
- Main Results: On the 1.5B model, average accuracy improves from 46.68 to 49.91 while average reasoning length decreases from 7442 to 4762 tokens, a 36% reduction.Notable accuracy gains occur on AMC23, from 63.12% to 69.38%, and MATH500, from 72.65% to 80.40%.
- Ablation Study: The stage-wise ablation cumulatively adds SFT, DPO, and GRPO to the base policy and reports accuracy alongside token ratios normalized to Base=1.0.Lower token ratios indicate shorter reasoning, allowing performance changes to be assessed separately from generation cost.
5 Analysis of Graph-based CoT Pruning
The analysis evaluates whether graph-based pruning shortens supervision and inference while preserving essential reasoning. Results show that pruning removes redundant reflections, maintains stronger reasoning reliability than naive truncation, and shifts behavior toward shorter, more direct trajectories.
- Dataset and graph statistics: Graph-based pruning removes many redundant reflection nodes while retaining most main-path reasoning and substantially shortening supervision data.The analysis also reports low data-synthesis cost.
- Preservation of essential reasoning: 93.70% Graph-Pruned accuracy and 90.69% consistency remain well above Len-Trunc’s 73.60% accuracy and 69.10% consistency.Full-CoT reaches 98.95% accuracy and 99.60% consistency in the same evaluation.
- Preservation of essential reasoning: Naive length truncation disrupts logical flow, whereas graph-based pruning preserves reasoning structure needed for stable and accurate generation.The comparison uses Full-CoT, Graph-Pruned, and length-matched Len-Trunc traces across 1,000 sampled examples with eight generations per question.
- Model behavior: After training, reasoning trajectories become noticeably shorter, with the long-tail region associated with excessively long responses suppressed.The change is shown through normalized reasoning-length distributions in Figure 4.
- Model behavior: Reflection-oriented tokens decrease after training, while progress-oriented connectives such as “therefore” become more frequent.This pattern indicates a shift from reflective verbosity toward more direct, decision-driven reasoning.
- Qualitative case studies: Qualitative cases show pruning removing repeated self-checks and digressions while keeping the core derivation intact.The resulting trajectories are described as cleaner and more stable.
6 Conclusion
The paper presents graph-based modeling as a way to identify and prune redundant reflection steps while preserving essential reasoning. This produces more concise CoTs and is positioned as a promising direction for reducing overthinking efficiently.
- Conclusion: The method converts linear CoTs into structured graphs to localize and remove low-importance review nodes while preserving essential logic.The target is reflection that does not contribute to the main reasoning path.
- Conclusion: Graph-based pruning yields more concise CoTs without sacrificing accuracy.The conclusion frames structural reasoning modeling as a promising direction for reducing overthinking and improving efficiency.
Limitations
The approach has preprocessing, labeling, and generalization limitations. Its scalability may be constrained by teacher-based graph construction, coarse progress–review labels, and uncertain transfer beyond mathematical reasoning.
- Scope and limitations: Graph construction requires a strong teacher model, introducing preprocessing cost and potentially limiting scalability.The paper suggests exploring lighter-weight graph construction.
- Scope and limitations: Coarse progress–review labeling may overlook fine-grained reasoning nuances.Richer semantic labels are identified as a direction for future work.
- Scope and limitations: Although effective for mathematical reasoning, the method’s generalization to more open-ended domains remains unclear.The paper calls for broader domain evaluations.
C Node-level Evaluation of Graph Construction
The evaluation tests whether graph nodes correctly represent progress or review functions and whether each node is a single independent reasoning step. Results indicate the constructed graphs are semantically faithful and structurally well-formed.
- 100 randomly sampled graph nodes are evaluated for node-type correctness and step atomicity.Node-type correctness compares predicted progress or review labels with the original reasoning role.
- Atomicity valid rate measures whether each node contains one semantically independent reasoning step without mixed operations.
- A node is valid only when it satisfies both node-type correctness and atomicity criteria.
- The model achieves high node-type classification accuracy and a strong atomicity valid rate.These results indicate semantic faithfulness and structural well-formedness of the constructed graphs.
D.1 SFT Training Settings
The training setup uses separate stages for SFT, DPO, and GRPO with length penalty, while reporting stage-specific hyper-parameters in Tables 5–7.
- SFT uses LLaMA-Factory with LoRA-based parameter-efficient tuning.LoRA adapters are applied to all attention and linear layers.
- DPO uses the same training framework as SFT, with its hyper-parameters summarized in Table 6.
- GRPO with length penalty uses the verl framework, with hyper-parameters summarized in Table 7.
E RL Training Dynamics
RL training tracks reward and response length across model scales. Reward generally increases despite fluctuations, while response length does not rise monotonically with reward.
- Reward exhibits an overall increasing trend despite noticeable fluctuations during training.The curves are smoothed with exponential moving average to reduce high-frequency noise.
- Response length does not grow monotonically with reward improvement, indicating that higher rewards are not solely achieved through longer responses.The authors describe this pattern as learning more effective reasoning strategies under the reward signal.
- Figure 5 compares RL training dynamics for 7B and 1.5B models using mean reward and response length.The left panel shows mean reward; the right panel shows response length in tokens.
F Overall Training Algorithm
The training algorithm constructs graph-structured CoTs, prunes redundant reasoning, and optimizes the policy through SFT, DPO, and GRPO with length penalty. Its graph-update procedure enforces semantic node and dependency rules while retaining a final answer node.
- Overall Training Algorithm: Algorithm 1 organizes training into graph construction and pruning, SFT initialization, DPO preference pairing, and GRPO with length penalty.The pseudocode describes policy optimization across all three training stages.
- Overall Training Algorithm: For each problem and raw CoT, the procedure updates a graph through create-or-merge operations and stores the resulting pruned trace for SFT.
- Graph Construction: The graph-construction prompt incorporates each current text segment by choosing exactly one operation: Insert or Merge.Inputs include an existing partial reasoning graph and the current continuous CoT segment, with strict JSON output.
- Graph Construction: Nodes represent abstract reasoning units with semantic products and dependencies, while purely operational calculations cannot stand alone as nodes.
- Graph Construction: A new node is preferred for goal introduction, product generation, method switching, structural advancement, or branch initiation.
- Graph Construction: Dependency edges connect nodes whose products are reused, branches originate from valid ancestors, IDs increase lexicographically, and the final node is named final answer.
- Pruning Outcome: Qualitative comparison shows the trained model exhibits reduced and more focused reflection relative to the base model.The comparison presents original CoTs alongside graph-structured representations and highlights reflection-related content.