Technical Summary: Budget-Efficient Thinking (BET)

Problem Statement

Large Reasoning Models (LRMs) such as OpenAI-o1 and DeepSeek-R1 enhance problem-solving capabilities through extended, multi-step reasoning. However, this capability comes with unsustainable inference-time costs. A critical inefficiency identified in the paper is the misallocation of test-time compute. Existing efficiency methods typically fall into two categories:

1. Uniform Compression: Techniques that globally shorten reasoning traces or compress chains of thought. These often suppress productive exploration on hard-but-solvable queries.
2. Difficulty-Conditioned Control: Methods that adjust reasoning depth based on perceived query difficulty. These often fail to distinguish between "hard-but-solvable" queries (which benefit from deeper reasoning) and "effectively unsolvable" queries (where the model lacks the capability regardless of budget).

The core problem is that current methods lack solvability awareness. They may waste significant compute on queries beyond the model's capability (futile exploration) while prematurely truncating reasoning on difficult queries that could be solved with sufficient investment. The challenge is to allocate test-time compute based on the expected return of reasoning rather than just perceived difficulty.

Methodology: Budget-Efficient Thinking (BET)

The authors propose Budget-Efficient Thinking (BET), a framework that treats test-time compute as a computational investment under uncertainty. BET aims to learn three distinct behaviors:

1. Short Solve: Answering easy queries concisely.
2. Nice Fold: Abstaining early when continued reasoning has near-zero expected return (i.e., the query is unsolvable by the current policy).
3. Hero Call: Preserving sufficient compute for hard-but-solvable queries where deeper reasoning can change the answer.

Core Components

BET operates on the principle that solvability is policy-dependent. A query may be unsolvable for a current policy but solvable for a more capable one. Therefore, BET estimates solvability dynamically from the model's own behavior rather than relying on static difficulty labels.

The framework consists of two stages:

1. Behavioral Cold-Start (Supervised Fine-Tuning)

• Goal: Initialize the policy with the necessary structured output format and behavioral repertoire.
• Process: The model is fine-tuned on a curated dataset derived from offline profiling of the base model. Queries are partitioned into:
  • Short Solve: Solvable queries with low efficient cost.
  • Hero Call: Solvable queries with high efficient cost.
  • Nice Fold: Queries where the base model fails to produce a correct solution in $K$ rollouts.
• Output: The model learns to emit a structured <predict> block containing a solvability estimate ($\hat{s}$) and a budget estimate ($\hat{b}$) before generating the reasoning trace.

2. Investment-Cost-Aware Training (GRPO)

• Goal: Optimize the policy to align solve-or-fold decisions with empirical solvability.
• Mechanism: The authors employ Group Relative Policy Optimization (GRPO). For each query, the policy generates $K=16$ independent rollouts.
• Group Profile: From these rollouts, two statistics are computed online:
  • Group Success Rate ($\hat{s}(x)$): The proportion of correct rollouts, serving as the solvability estimate.
  • Efficient Solution Cost ($\hat{c}^*(x)$): The mean length of the shortest correct trajectories (e.g., the top 30%), representing the cost ceiling for productive reasoning.
• Composite Reward Function: The reward $R(y|x)$ is composed of three terms:
  • $R_{VAL}$ (Value with Abstention Gate): Assigns a positive reward ($+\delta$) for abstaining on unsolvable queries (where $\hat{s}(x) < \epsilon_{abs}$) and a heavy penalty ($-\lambda$) for abstaining on solvable ones. Incorrect attempts incur a cost-proportional penalty.
  • $R_{EFF}$ (Query-Adaptive Efficiency): Rewards correct solutions that are shorter than the efficient cost estimate $\hat{c}^*(x)$. This encourages concision on easy queries without penalizing necessary depth on hard-but-solvable ones.
  • $R_{CAL}$ (Solvability Calibration): Penalizes discrepancies between the model's predicted solvability/budget and the empirical group profile. This ensures the model's pre-reasoning estimates are grounded in reality.

Key Contributions

1. Solvability-Aware Diagnosis: The paper identifies that existing adaptive reasoning methods overlook solvability, leading to excessive compute on beyond-capability queries and under-investment on hard-but-solvable ones.
2. Investment-Aware Training (BET): A two-stage framework combining behavioral cold-start with GRPO under a composite reward. This induces the three target behaviors (Short Solve, Nice Fold, Hero Call) by aligning decisions with rollout-derived solvability.
3. Evidence at Scale: Extensive experiments demonstrating that BET reduces token usage while maintaining or improving accuracy, and generalizes to out-of-domain tasks.

Experimental Results

The authors evaluated BET on seven benchmarks (four in-domain math, three out-of-domain) using three base models (Qwen3-4B, DeepSeek-R1-Distill-7B, and 14B).

• Efficiency and Accuracy: Across all models, BET reduced reasoning tokens by approximately 55% on average while achieving overall performance improvements.
  • On Qwen3-4B, accuracy on Omni-Math increased from 73.64% to 74.41% while tokens dropped from 10,516 to 4,561.
  • On DeepSeek-R1-Distill-7B, BET achieved the lowest average token cost while staying within 0.54 points of the best accuracy.
• Selective Compression: Unlike baselines that compress uniformly, BET selectively reduces tokens on unsolvable queries (cutting usage by over 90% for these cases) while preserving depth for worthy queries.
• Zero-Shot Transfer: Trained solely on mathematical reasoning, BET transferred effectively to scientific QA (GPQA-Diamond), multi-step narrative reasoning (MUSR), and logical reasoning (LSAT-AR), achieving 53–59% token savings with comparable accuracy gains.
• Pareto Frontier: BET positions itself on the Pareto frontier of accuracy-efficiency trade-offs, outperforming baselines like Length-Penalty, DR.SAF, and DiffAdapt.

Significance and Claims

The paper claims that BET represents a shift from difficulty-conditioned compression to solvability-aware budget investment. By treating compute as an investment where the return is uncertain, the model learns to:

• Stop early when the expected return is zero (Nice Fold), preventing futile exploration.
• Invest deeply only when the query is solvable and the reasoning is likely to change the answer (Hero Call).
• Be concise when the solution is straightforward (Short Solve).

The authors emphasize that the "Nice Fold" behavior is not a claim of intrinsic impossibility but a policy-dependent abstention. It signals that, under the current model and budget, further reasoning is unlikely to yield a correct answer. This capability-aware uncertainty can be leveraged in cascaded systems to route difficult queries to stronger models, optimizing system-level efficiency.

The work concludes that BET provides a tunable policy family where the trade-off between accuracy and cost can be adjusted (e.g., via the fold reward $\delta$), offering a principled approach to managing test-time compute without sacrificing problem-solving capability.