ChainPrune: Evaluating and Reducing Redundancy in Long Chain-of-Thought Reasoning

Introduction

• Token-only optimization can produce pseudo-conciseness: fewer tokens but many redundant micro-steps, longer chains, and reduced structural efficiency.Overthinking increases computational overhead and error accumulation. Guide-based tree-search methods (Liao et al. 2025) can introduce reward bias that propagates reasoning errors.Source: Introduction · pp. 1–2
• ChainPrune consolidates sampled reasoning paths into a tree and dynamically merges semantically equivalent nodes, reducing redundant steps while preserving critical reasoning and core logic.The low-cost semantic structural optimization targets shorter paths in both tokens and steps without sacrificing correctness or completeness.Source: Introduction · p. 2
• Preference construction automatically searches merged reasoning trees for Pareto-optimal paths, jointly targeting chain and token efficiency without manual annotation.Selection prioritizes Pareto-dominant paths when available; otherwise, it favors shorter non-dominated candidates. Rejected responses must exhibit substantially longer reasoning steps or incorrect logic.Source: Introduction · p. 2
• 26.8% chain-length and 28.1% token-length reductions across five reasoning benchmarks are reported for ChainPrune without an accuracy drop.These results evaluate reductions in both reasoning steps and token usage.Source: Introduction · p. 2
• 57.8% fewer faulty steps, 62.1% fewer invalid reflections, and 65.9% fewer redundant steps distinguish ChainPrune from the base model.An LLM-as-a-Judge framework with human verification evaluates faulty reasoning, reflection mechanisms, and step efficiency.Source: Introduction · p. 2
• DPO + NLL Loss (Pang et al. 2024) significantly shortens reasoning steps while maintaining reasoning quality.Experiments compare it with DPO (Rafailov et al. 2023) and SimPO (Meng, Xia, and Chen 2024). The added NLL term trains on winning responses to support correctness and efficiency.Source: Introduction · p. 2

Formal Modeling of Autoregressive Inference

• Autoregressive inference forms a token-expansion tree rooted at the input context, with branching factor b = |A| and exponential growth O(b^d) with depth.The model generates tokens sequentially, with each branch representing a candidate vocabulary token.Source: Formal Modeling of Autoregressive… · p. 2
• Reasoning-focused models extend token prediction into structured chains, but improved reasoning quality still leaves inefficiencies in path generation and selection.Implicit CoT lacks explicit intermediate supervision; explicit-format approaches separate reasoning and answers with semantic tags and format-constrained rewards. Self-verification, including code execution and symbolic checks, detects and corrects reasoning errors.Source: Formal Modeling of Autoregressive… · p. 2

Challenges in RL-Optimized Reasoning Paths

• Token-focused reward designs can produce pseudo-conciseness: short phrases fragment reasoning into many steps, leaving structurally long and inefficient chains.The analysis attributes this behavior to rewarding token-level conciseness while neglecting reasoning-chain length.Source: Challenges in RL-Optimized Reasoning… · p. 2
• 33.95% of the shortest-token correct paths are also shortest in steps, demonstrating misalignment between token-based and structural conciseness.The authors report that most existing preference-learning pipelines, including DPO, select chosen responses solely by minimum token length among correct outputs.Source: Challenges in RL-Optimized Reasoning… · p. 3
• A correct path dominates another only when it has both fewer reasoning steps and fewer tokens.A Pareto-dominant path dominates every alternative; when none exists, the non-dominated candidates form the Pareto frontier.Source: Challenges in RL-Optimized Reasoning… · p. 3

Cross-Path Semantic Reusability in Tree Search

• Attention concentrated on recent tokens after semantically equivalent nodes supports the assumption that merging these nodes preserves subsequent conditional distributions.Equivalent intermediate steps frequently recur across sampled paths, including chosen and rejected candidates, often at similar structural positions.Source: Cross-Path Semantic Reusability in… · p. 3, Figure 2 · p. 3
• ChainPrune combines semantic tree merging with Pareto-based selection to produce reasoning chains that are shorter in both tokens and steps while preserving logical integrity.Merging semantically equivalent nodes eliminates duplicated segments and enables reuse of their best-performing continuations.Source: Cross-Path Semantic Reusability in… · p. 3

Methodology

• ChainPrune integrates semantic path merging, dual-objective path selection, and regularized preference optimization to reduce reasoning redundancy while preserving essential steps.Selection jointly considers token length and reasoning step length rather than token count alone.Source: Methodology · p. 3, Figure 3 · p. 4

Reasoning Paths Merging

• ChainPrune consolidates sampled reasoning paths into a compact tree, preserving essential trajectories through cosine-similarity matching and entropy-checked node merging.Steps merge when cosine similarity reaches θsim; otherwise, a new branch is created. To guard against logically incorrect merges, candidate substitutions are accepted only when Hafter − Hbefore ≤ ϵ.Source: Reasoning Paths Merging · pp. 3–4

Multi-criteria Dominant Path Selection and Preference Data Construction

• Among ground-truth-correct responses, ChainPrune selects a unique path shortest in both tokens and steps, otherwise choosing the shortest-token Pareto-front candidate.Correct responses become rejected examples when they contain at least five additional steps and at least 1.5 times the preferred response’s tokens. Incorrect responses become rejected examples only when both their step and token lengths exceed the preferred response’s.Source: Multi-criteria Dominant Path Selection… · p. 4

Direct Preference Optimization

• ChainPrune combines DPO with supervised fine-tuning loss to encourage concise, correct reasoning while explicitly increasing the likelihood of preferred outputs.The supervised term guards against overly terse or incomplete reasoning. The authors invoke gradient entanglement (Yuan et al. 2024) to explain how margin-based methods can inadvertently synchronize chosen and rejected responses’ log-probabilities.Source: Direct Preference Optimization · pp. 4–5

Experiment Setup

• 9,967 cleaned MATH problem–answer pairs support training DeepSeek-R1-Distilled-Qwen-7B and DeepSeek-R1-Distilled-Qwen-1.5B, with 16 reasoning paths sampled per problem.Evaluation covers MATH500 (Hendrycks et al. 2021), AMC23, AIME24/25, and LiveCodeBench (Jain et al. 2024). Accuracy, token length, and chain length are averaged over 16 runs; length metrics include only correct answers, with steps segmented by double newlines.Source: Experiment Setup · p. 5

Overall Performance

• ChainPrune outperforms all evaluated baselines in accuracy across mathematics and code-generation benchmarks while reducing token and chain lengths.Accuracy matches or surpasses base-model performance; SFT degrades slightly, while reproduced DAST (Shen et al. 2025a) and Kimi-1.5 (Team et al. 2025) show noticeable accuracy drops.Source: Overall Performance · p. 5, Experiment Setup · p. 5
• 28.1% average token reduction over base models accompanies maintained or improved accuracy, with reductions of 22.6% on AIME24 and 23.0% on LiveCodeBench.Token averages include only correct answers; solving harder problems can raise ChainPrune’s reported average above the best baseline on this metric. Nevertheless, it remains best-performing on token efficiency in most datasets.Source: Overall Performance · pp. 5–6

Evaluate with LLM-as-a-Judge

• 43 faulty reasoning steps, 47 invalid reflections, and 45 redundant steps give ChainPrune reductions of 57.8%, 62.1%, and 65.9% over the base model, respectively.On MATH500, GPT-o1, DeepSeek-R1, and Qwen-QwQ judge outputs through majority voting, supplemented by human checks and manual review of high-disagreement cases. Structured semantic pruning merges semantically equivalent nodes using low-cost similarity, reducing invalid reflections and redundancy while preserving core logical integrity.Source: Table 2 · p. 6, Evaluate with LLM-as-a-Judge · p. 6

Overall Performance

• ChainPrune produces substantially shorter reasoning chains than Kimi-1.5 with shorter or comparable token usage, reducing redundancy in both dimensions without harming reasoning quality.This contrasts with Kimi-1.5’s explicit optimization for shortest token usage and supports ChainPrune’s joint token–step optimization.Source: Overall Performance · p. 6

Comparison of different variants of DPO in Short-Chosen Preference Optimization

• DPO (Rafailov et al. 2023) and SimPO (Meng, Xia, and Chen 2024) exhibit reward synchronization collapse, lowering both preference-pair probabilities and degrading reasoning performance.This occurs in short-chosen preference optimization, where narrow data distributions and small edit distances between preferred and rejected responses encourage biased strategies.Source: Comparison of different variants of… · p. 6
• ChainPrune remains more token-efficient than DPO+NLL, which maintains or improves mathematical reasoning accuracy while reducing token usage.DPO+NLL improves both Kimi-1.5 and DAST accuracy on AIME24 and MATH500. ChainPrune merges paths semantically and selects Pareto-optimal chains, preserving logical completeness with fewer tokens and shorter chains.Source: Comparison of different variants of… · p. 6

Analysis of Reasoning Path Impact and Sample Efficiency

• Shortest correct responses grow proportionally longer as problem difficulty increases, allowing shortest-response selection to adapt optimization to question difficulty.Figure 4 examines the relationship between difficulty and the token/chain length of the shortest correct response.Source: Analysis of Reasoning Path Impact and… · p. 6, Figure 4 · p. 7
• Shorter chosen training responses produce shorter, equally accurate model outputs, with medium-length and long responses yielding progressively longer outputs.The ablations describe this relationship as linear, with shortest responses consistently producing the most concise outputs.Source: Analysis of Reasoning Path Impact and… · pp. 6–7
• Hundreds of random samples yield only marginal token-length gains, making sufficiently short correct responses expensive to obtain for methods such as DPO and PPO.This sampling cost limits the efficiency of collecting high-quality training data.Source: Analysis of Reasoning Path Impact and… · p. 7
• Merging multiple reasoning paths into a tree enables high-quality training-sample generation with minimal overhead.The authors propose integrating this low-cost approach into online RL frameworks such as PPO to improve exploration efficiency when collecting valuable training data.Source: Analysis of Reasoning Path Impact and… · p. 7

Make Long CoT Short

• Length-penalized reinforcement learning encourages concise reasoning by incorporating length constraints into reward functions, as in O1-Pruner (Luo et al. 2025).O1-Pruner balances accuracy and brevity, while DAST (Shen et al. 2025a) dynamically adjusts reasoning steps to problem difficulty.Source: Related Works · p. 7
• Supervised fine-tuning with variable-length CoTs shortens reasoning through token skipping in TokenSkip (Xia et al. 2025) and LLM-based step compression in C3oT (Kang et al. 2025).TokenSkip identifies less critical tokens to skip; C3oT uses LLMs such as GPT-4 (Achiam et al. 2023) to compress reasoning steps.Source: Related Works · p. 7
• Prompt-driven methods encourage concise reasoning without training: Concise CoT (Renze and Guven 2024) uses simple instructions, while Break the Chain encourages shortcuts.Source: Related Works · p. 7
• Latent reasoning eliminates explicit CoT generation: Implicit-KD (Deng et al. 2023) distills reasoning into hidden states, while Coconut reasons in a continuous latent space.Source: Related Works · p. 7

Guide-based Methods

• Guide-based methods accelerate inference through speculative decoding, including coordinated small models in SEED (Wang et al. 2024) and dual-level generation in SpecSearch (Wang et al. 2025).Gao et al. (Gao et al. 2024) integrated conventional speculative decoding with reasoning; SEED coordinates parallel small models through one shared large model. SpecSearch generates at thought and token levels, accelerating inference without compromising output quality.Source: Related Works · p. 7

Conclusion

• 26.8% fewer reasoning steps and 28.1% fewer tokens are reported across five reasoning tasks without accuracy degradation.Source: Conclusion · p. 7
• 65.9% fewer redundant steps are reported compared with the base model.Source: Conclusion · p. 7
• 62.1% fewer invalid reflections are reported compared with the base model.Source: Conclusion · p. 7
• 57.8% fewer faulty steps are reported compared with the base model.Source: Conclusion · p. 7
• ChainPrune merges equivalent reasoning-tree nodes to preserve logical integrity while addressing pseudo-conciseness, where superficial token reduction leaves redundant reasoning paths.The conclusion emphasizes semantic coherence rather than token compression alone when evaluating reasoning efficiency.Source: Conclusion · p. 7
• ChainPrune currently uses offline optimization; extending it to online RL frameworks such as PPO remains unimplemented future work aimed at improving exploration efficiency.Time and resource constraints prevented implementation of this extension.Source: Conclusion · p. 7

A Statistical Analysis of Reasoning Path Efficiency

• The analysis examines sampled correct reasoning paths for every training-set math question to test whether token-level optimization overlooks structural compactness.The comparison assesses alignment between minimum token length and minimum chain length as evidence of pseudo-conciseness.Source: A Statistical Analysis of Reasoning… · p. 10

Evaluation Metrics and Key Findings

• 33.95% of training-set questions have min distance = 0, meaning the same correct reasoning path minimizes both token length and chain length.This finding highlights misalignment between expression-level and structural conciseness.Source: Figure 6 · p. 10, Evaluation Metrics and Key Findings · p. 10
• Token Length counts total output tokens, whereas Chain Length counts reasoning steps in the logical chain.Both metrics are computed for multiple sampled correct paths per question.Source: Evaluation Metrics and Key Findings · p. 10
• Paths are ranked separately to identify τ min-tok, the shortest-token path, and τ min-step, the path with the fewest reasoning steps.These separately selected paths define the two optima compared by the analysis.Source: Evaluation Metrics and Key Findings · p. 10
• The normalized min distance metric measures separation between the token-length and step-count optima in their non-primary dimensions.It considers the shortest-step path’s token length and the shortest-token path’s step count; metric minima and maxima are defined over all paths.Source: Evaluation Metrics and Key Findings · p. 10

Pareto Frontier Visualization

• 64 sampled reasoning paths for a representative math question contain no correct path jointly minimizing token length and chain length.This visualization supports the claim that token-minimizing reward heuristics often fail to produce reasoning that is both structurally compact and concise in expression.Source: Figure 7 · p. 10, Pareto Frontier Visualization · p. 10

B Examples of Semantically Equivalent Reasoning Steps in Chosen and Rejected Paths

• Semantically equivalent intermediate steps occur in both chosen and rejected paths but systematically appear earlier in rejected paths, revealing a structural ordering bias.Figure 8 illustrates this with computing meat per hamburger and scaling to 24 hamburgers: both paths share these steps, but the rejected path performs them earlier.Source: B Examples of Semantically Equivalent… · pp. 10–11, Figure 8 · p. 11
• Minimal-token preference construction favors delayed, fragmented reasoning over structural clarity and efficiency, even when chosen and rejected paths both reach correct answers.The favored paths have lower token counts per step despite sharing nearly identical intermediate reasoning with rejected paths.Source: B Examples of Semantically Equivalent… · p. 11

C Multi-Reasoning Paths Merging Algorithm

• Initialization splits each candidate path into reasoning steps and builds a linear backbone from the shortest resulting step sequence.Each backbone node represents one reasoning step, yielding a minimal but coherent initial trajectory.Source: C Multi-Reasoning Paths Merging… · p. 11
• Candidate steps merge only when embedding cosine similarity exceeds θsim and substitution keeps predictive-entropy change ∆H within tolerance ϵ, protecting logical consistency.Each incoming step’s embedding is compared with existing tree nodes to identify semantically similar merge candidates.Source: C Multi-Reasoning Paths Merging… · p. 11
• A valid match attaches the path’s remaining steps beneath the matched node; without any valid merge, the entire path becomes a new root branch.Paths other than the initial backbone are merged incrementally.Source: C Multi-Reasoning Paths Merging… · p. 11
• ChainPrune’s compact tree preserves logical diversity while reducing redundant computation, representing shared reasoning as internal nodes, divergent strategies as branches, and unique answers as leaves.The algorithm hierarchically merges K candidate reasoning paths generated by a base LLM into a step-level tree, aiming to retain all critical reasoning logic.Source: C Multi-Reasoning Paths Merging… · p. 11

• Gradient entanglement (Yuan et al. 2024) synchronizes chosen and rejected log probabilities, potentially forgetting high-quality responses or failing to suppress rejected responses.Synchronization arises when the gradient inner product is large relative to the individual gradient norms. Synchronized decreases explain reasoning degradation, whereas synchronized increases inadequately discourage rejected responses.Source: D Theoretical Analysis of different… · pp. 11, 13
• 75.4% of DPO cases show synchronized decreases, 21.2% show synchronized increases, and only 3.4% achieve ideal divergence.The study tracks chosen and rejected log probabilities during training using 1,000 sampled preference pairs. Ideal divergence increases the chosen response’s probability while decreasing the rejected response’s probability.Source: D Theoretical Analysis of different… · p. 13, Figure 10 · p. 14
• 85.6% of SimPO cases still exhibit undesirable synchronized changes, showing that length normalization mitigates but does not eliminate gradient entanglement.Length normalization relaxes the divergence inequality but remains insufficient to fully decouple chosen and rejected log-probability dynamics.Source: Figure 10 · p. 14, D Theoretical Analysis of different… · p. 14
• Adding NLL loss to DPO increases the chosen-response gradient coefficient without changing the rejected-response coefficient, preserving contrastive preference learning while explicitly maximizing chosen-response probability.This relaxes the condition for increasing the chosen response’s log probability, avoiding its suppression by a purely margin-based objective.Source: D Theoretical Analysis of different… · p. 14

E LLM-as-a-Judge for Evaluation of Reasoning Model

• GPT-4o dynamically segments reasoning paths into coherent, minimal semantic steps rather than relying on fixed heuristic boundaries.This chain-splitting stage avoids the brittleness of rule-based chunking.Source: E LLM-as-a-Judge for Evaluation of… · pp. 14–15
• GPT-o1, DeepSeek-R1, and Qwen-QwQ independently classify each step, with majority voting determining labels and human experts consulted when disagreement is high.Each evaluator receives the current step and up to three preceding and three following steps, then returns a JSON tag and justification to support context-sensitive judgments.Source: Figure 11 · p. 14, E LLM-as-a-Judge for Evaluation of… · p. 15
• The taxonomy distinguishes faulty reasoning (logical or mathematical errors), invalid reflection (ineffective or incoherent self-assessment), and redundant steps (repetitive or non-contributory content).Faulty reasoning jeopardizes correctness; invalid reflection fails to improve or critically assess reasoning; redundant steps add no new information.Source: E LLM-as-a-Judge for Evaluation of… · p. 15

F More Experiment Results

• 2,170 versus 2,427 output tokens on MATH500 resulted from shortest versus longest chosen samples, respectively.The longest samples were the 10th-shortest reasoning paths for the same questions.Source: F More Experiment Results · p. 15
• Shortest chosen samples reduced reasoning-chain length while maintaining or improving accuracy.The ablation therefore showed improvements in reasoning structure as well as output token counts.Source: F More Experiment Results · p. 15
• Medium-length chosen samples yielded intermediate results across datasets, supporting a consistent relationship between response brevity and computational efficiency.Medium-length samples were the fifth-shortest reasoning paths.Source: F More Experiment Results · p. 15