🤖 AI

OS-Pruner: Pruning Chains-of-Thought of Reasoning Models via Optimal Stopping

The paper introduces OS-Pruner, a lightweight plug-in framework that formulates chain-of-thought pruning as an optimal stopping problem to dynamically determine the most efficient termination point for reasoning chains, thereby reducing generation length by 20–60% with minimal accuracy loss.

Original authors: Mohammed Ehab, Aymane El Gadarri, Vivek F. Farias, Adam Jozefiak, Ciamac C. Moallemi

Published 2026-07-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mohammed Ehab, Aymane El Gadarri, Vivek F. Farias, Adam Jozefiak, Ciamac C. Moallemi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you're solving a tricky math puzzle. You start thinking out loud, writing down every step, checking your work, and maybe even re-checking it just to be sure. But then, you realize you've already found the answer! Yet, your brain (or in this case, a super-smart computer brain called a Large Language Model) keeps going. It writes more paragraphs, repeats old arguments, or does extra calculations that don't actually help. This is what the paper calls "computational overthinking." It's like a student who keeps writing on the test long after they've solved the problem, just burning time and paper without getting a better grade.

The paper introduces a new tool called OS-Pruner to fix this. Think of OS-Pruner as a super-smart "stop-watch" or a wise coach standing next to the computer. Its job is to watch the computer's thinking process step-by-step and ask a simple question after every paragraph: "Is it worth writing one more sentence, or should we just give the answer now?"

The "Stop or Go" Game

The authors realized that deciding when to stop isn't just about guessing if the answer is right. It's a balancing act.

The Cost: Every extra sentence the computer writes costs money (in "tokens") and time (latency).
The Reward: The only reason to keep writing is if there's a good chance the next sentence will make the final answer more accurate.

The paper argues that most current methods are like a strict teacher who says, "Stop after exactly 10 sentences!" or "Stop if you feel 90% confident!" The authors suggest these methods are too rigid. Instead, they frame the problem as an Optimal Stopping game. This means the computer learns to weigh the cost of writing more against the chance of getting a better answer. If the next step is unlikely to help much, the "coach" (OS-Pruner) says, "Stop! We're good!"

What They Rejected

The paper explicitly argues against a few common ideas:

Fixed Budgets: They say simply forcing the model to stop after a set number of steps (like "think for exactly 5 minutes") doesn't work well because some problems are easy and need only a few steps, while others are hard and need many.
Simple Confidence Checks: They show that just asking, "Are you confident enough?" isn't enough. Sometimes a model might be confident but still have a better path ahead, or it might be unsure but actually be done. The paper proves mathematically that a simple "confidence threshold" can miss out on huge improvements compared to their method.
Retraining the Whole Brain: Many other methods try to retrain the entire computer model to be shorter. The authors say this is expensive and slow. OS-Pruner is a "plug-in," meaning it's a tiny add-on that doesn't need to rebuild the whole brain.

How They Tested It

The researchers didn't just guess; they ran serious experiments. They took several powerful reasoning models (like DeepSeek-R1-Distill-Qwen-7B, GPT-OSS-20B, and DRPO-7B) and tested them on math problems ranging from easy grade-school arithmetic to tough Olympiad-level challenges.

They found that by using OS-Pruner:

The models cut their thinking length by 20% to 60% on many tasks.
For example, on the GSM8K (easier math) dataset, the model DeepSeek-R1-Distill-Qwen-7B shortened its thinking by 59.3% while barely changing its accuracy (only a tiny drop of 0.7 percentage points).
On harder problems like AIME, the model was more careful, only cutting 6.9% of the length, because extra thinking was actually needed there.

The paper suggests that even models that were already trained to be short (like the DRPO-7B model) still suffered from overthinking, and OS-Pruner could make them even better.

The Bottom Line

The paper doesn't claim to have "solved" AI reasoning forever. Instead, it suggests that by treating the decision to stop as a smart trade-off between time and accuracy, we can make these powerful models much faster and cheaper to run without losing their smarts. It's like teaching a genius student to stop talking once they've made their point, saving everyone's time while still getting an A+.

The authors measured these results on specific datasets and found that OS-Pruner consistently sits on the "Pareto frontier"—a fancy way of saying it offers the best possible deal: the most accuracy for the least amount of writing. They even showed that you can control this trade-off with a single number (called $\lambda$ ), letting users decide if they want the model to be super fast (and maybe slightly less accurate) or super careful (and take a bit longer).

Technical Summary: OS-Pruner

Problem Statement

Large Language Models (LLMs) utilizing Chain-of-Thought (CoT) prompting have achieved significant success in complex reasoning tasks. However, these models frequently exhibit "computational overthinking," generating redundant reasoning steps that increase latency and inference costs without improving final answer accuracy. This behavior includes restating arguments, verifying settled conclusions, or pursuing low-value calculations. While recent studies suggest CoT trajectories can be pruned, existing solutions suffer from specific limitations:

Static Budgets: Methods like budget forcing impose a fixed thinking limit externally, ignoring the evolving state of the reasoning trace.
Model-Side Compression: Techniques such as length-penalized fine-tuning or token skipping require costly retraining of the base model and can degrade performance on non-reasoning tasks.
Heuristic Early Stopping: Current dynamic methods often rely on classification or thresholding (e.g., stopping when confidence exceeds a fixed value), which fails to account for the trade-off between the cost of additional tokens and the expected improvement in answer quality.

The authors argue that CoT pruning is fundamentally a sequential decision problem best framed as an optimal stopping problem, where the system must decide at each step whether the expected gain in accuracy justifies the cost of generating another token.

Methodology: OS-Pruner

OS-Pruner is a lightweight, plug-in framework designed to formulate CoT pruning as an optimal stopping problem. It operates without modifying the frozen base reasoning model.

1. Problem Formulation

Given an input problem $x$ and a partially generated CoT prefix $y_{\le i}$ , OS-Pruner learns a parametric stopping policy $\pi_\theta$ that outputs the probability of stopping. The objective is to maximize an explicit utility function that trades off final answer accuracy against generated length:
$r(y_{\le i}|x) = A(y_{\le i}|x) - \lambda L(y_{\le i})$
Where:

$A(y_{\le i}|x)$ is the accuracy of the answer derived from the prefix (1 if correct, 0 otherwise).
$L(y_{\le i})$ is the number of tokens generated up to step $i$ .
$\lambda$ is a scalar parameter controlling the penalty for length, allowing users to select a specific operating point on the accuracy-efficiency frontier.

2. Theoretical Advantage

The paper distinguishes OS-Pruner from confidence-threshold methods via a Value Function View.

Classification-based methods stop if $A(y_{\le i}|x) \ge \gamma$ (a fixed threshold).
Optimal Stopping (OS-Pruner) stops if the immediate value of stopping exceeds the continuation value: $A(y_{\le i}|x) \ge C_\lambda(x, y_{\le i})$ .
The continuation value $C_\lambda$ represents the expected future reward minus the cost of additional tokens. The authors prove (Theorem 1) that fixed-threshold classifiers can have an arbitrarily large performance gap compared to the optimal stopping policy, as they fail to account for the state-dependent value of future reasoning paths.

3. Implementation and Architecture

Data Preprocessing: The base model generates full reasoning traces. For training, the system intervenes after each reasoning step, forces the model to output a final answer (preventing "thinking" in the answer section), and grades it against ground truth using Math-Verify. This creates fine-grained supervision for every prefix.
Policy Architecture: The policy is a lightweight linear head ( $\sigma(W^\top h_l + b)$ ) applied to the last hidden state $h_l$ of the prefix. To enhance performance, the last $n$ (typically 2) self-attention layers of the base model are fine-tuned, while the rest of the model remains frozen.
Training Efficiency: Because the base model is causal, the hidden state of a paragraph is unaffected by subsequent tokens. This allows the entire reasoning trace to be processed in a single forward pass, with the linear layer applied in parallel to relevant hidden states.
Progressive Training: To avoid getting stuck in local minima where the policy never stops, training begins with a high $\lambda$ (high cost for length) and progressively anneals it to lower values.

4. Inference

During inference, the policy is invoked only at reasoning-step boundaries (e.g., end of a paragraph). The system checks the stopping probability; if the decision is to stop, it elicits the final answer immediately. This design ensures high efficiency on modern LLM serving systems (e.g., vLLM) by leveraging parallel pre-fill processing and minimizing KV cache recomputation.

Key Contributions

Rigorous Formulation: The paper provides a formalization of CoT pruning as an optimal stopping problem with an explicit reward function trading accuracy against length.
Lightweight Plug-in: OS-Pruner is a training-based stopping policy that operates on reasoning prefixes without modifying the frozen base reasoning model, requiring only the fine-tuning of a small policy head and a few transformer layers.
Empirical Performance: Experiments demonstrate that OS-Pruner substantially reduces reasoning length while preserving accuracy across diverse models and benchmarks.
Complementarity: The method is shown to provide additional gains even when applied to models already optimized for brevity via model-side methods.

Experimental Results

The authors evaluated OS-Pruner on three models (DeepSeek-R1-Distill-Qwen-7B, GPT-OSS-20B, and DRPO-7B) across benchmarks of varying difficulty (GSM8K, MATH-500, AIME).

Length Reduction: OS-Pruner achieved a 20–60% reduction in generation length with minimal accuracy sacrifice.
- On DeepSeek-R1-Distill-Qwen-7B, it reduced length by 59.3% on GSM8K and 52.8% on MATH-500, with accuracy changes of only -0.7% and +2.7% respectively.
- On GPT-OSS-20B (a model already optimized for conciseness), it still achieved significant reductions (e.g., 21% on MATH-500) while maintaining competitive accuracy.
Comparison to Baselines: OS-Pruner consistently outperformed training-based baselines (Classification Probe, Answer Convergence, FlashThink) in the Accuracy-Efficiency Score (AES). It lies on or near the Pareto frontier, whereas fixed-threshold baselines degraded more sharply as length budgets were reduced.
Robustness: The method performed well across difficulty levels, being more aggressive on easier tasks (where overthinking is prevalent) and more conservative on hard tasks (AIME), where extra computation is valuable.

Significance and Claims

The paper claims that OS-Pruner offers a more natural and optimal approach to CoT pruning than existing heuristic or static methods. By framing the problem as a sequential decision process, it dynamically assesses the sufficient point of termination based on the specific reasoning state rather than a global threshold.

The authors emphasize that OS-Pruner:

Reduces Computational Cost: By cutting unnecessary tokens, it lowers inference latency and energy footprint.
Provides Fine-Grained Control: The parameter $\lambda$ allows users to explicitly tune the trade-off between reasoning effort and accuracy.
Works with Existing Models: It does not require retraining the base generator, making it a practical "plug-in" for existing reasoning models.
Complements Model-Side Methods: Even models trained for brevity (like DRPO) benefit from the additional pruning, suggesting that model-side compression and optimal stopping address different aspects of efficiency.

The work concludes that while it focuses on mathematical reasoning, the framework is applicable to broader contexts, though future work is needed to explore coding and scientific reasoning tasks and scaling to frontier models.