📄 Graph-Based Chain-of-Thought Pruning for Reducing Redundant Reflections in Reasoning LLMs

Summary

Reasoning LLMs trained with reinforcement learning often overthink and produce long chains of thought. The authors attribute much of this waste to unproductive self-reflection of two kinds. The model either checks trivial steps across the board (Indiscriminate Reflection) or keeps re-confirming results it has already verified (Repetitive Reflection).

To target these behaviours, they split each CoT into chunks at cue words such as "wait". An external LLM then incrementally builds a DAG whose nodes are labelled progress or review and linked by logical dependencies. Two rules prune the graph:

• Branch-level pruning drops review nodes that have few descendants.
• Depth-level pruning drops review nodes that appear late in the reasoning.

The pruned traces feed a three-step training pipeline: cold-start SFT, then DPO that favours concise correct trajectories over verbose ones, then GRPO with a length penalty.

Across benchmarks, average reasoning tokens fall by about 42%, with accuracy matched or improved against efficiency baselines. This suggests that structure-aware removal of reflections is a practical way to cut inference cost.

Key points

• The graph labels each node as progress (moves the solution forward) or review (checks, restates or backtracks). Only review nodes are candidates for removal, using a descendant-count threshold k and a depth cutoff ratio m.
• Compared baselines include Light-R1, AdaptThink, TokenSkip, Skywork-OR1 and O1-Pruner. The headline result is roughly 42% fewer reasoning tokens with accuracy maintained or improved.
• The pruning ablation used SFT on DeepSeek-R1-Distill-Qwen-7B:
  • Selective pruning: 42.50% on AIME24 (≈10.4k tokens) and 34.17% on AIME25.
  • No pruning: 42.08% (≈12.7k tokens) and 33.75%.
  • Selective pruning also beat random pruning and removing every review node, so some reflections are worth keeping.
• A threshold sweep (k = 1–3, m = 0.7–0.9) showed stable behaviour. Raising k prunes more aggressively and can lower accuracy, while varying m gives a smoother accuracy–length trade-off.
• After training, reflection words ("wait", "hmm", "check") occur less often and "therefore" more often. The long tail of very lengthy responses on AIME24 also shrinks.