Scaling test-time compute is crucial for enhancing the reasoning capabilities of large language models (LLMs). Existing approaches typically employ reinforcement learning (RL) to maximize a verifiable reward obtained at the end of reasoning traces. However, such methods optimize only the final performance under a large and fixed token budget, which hinders efficiency in both training and deployment. In this work, we present a novel framework, AnytimeReasoner, to optimize anytime reasoning performance, which aims to improve token efficiency and the flexibility of reasoning under varying token budget constraints. To achieve this, we truncate the complete thinking process to fit within sampled token budgets from a prior distribution, compelling the model to summarize the optimal answer for each truncated thinking for verification. This introduces verifiable dense rewards into the reasoning process, facilitating more effective credit assignment in RL optimization. We then optimize the thinking and summary policies in a decoupled manner to maximize the cumulative reward. Additionally, we introduce a novel variance reduction technique, Budget Relative Policy Optimization (BRPO), to enhance the robustness and efficiency of the learning process when reinforcing the thinking policy. Empirical results in mathematical reasoning tasks demonstrate that our method consistently outperforms GRPO across all thinking budgets under various prior distributions, enhancing both training and token efficiency.
Figures & tables
Figure 1: Left : We optimize anytime reasoning by sampling thinking budgets from a prior distribution pB and maximizing the rewards at sampled budgets to push up the area under the curve. This objective naturally introduces verifiable dense rewards into the thinking process. Right : Budget Relative Policy Optimization (BRPO) leverages these dense rewards to improve advantage estimation via the Monte Carlo return ( R ) and an interpolated baseline that combines current progress ( V1 ) and the average return within the rollout group ( V2 ).
Figure 2: By introducing dense rewards, we achieve better credit assignment during RL training. We assume a uniform distribution over thinking budgets and omit the probability for simplicity.
Figure 3: Left : The correlation coefficient of V1 and V2 with R(x,z,jt) . Right : The normalized variance of our BRPO. We evaluate the R1-Distill-1.5B model under the scenario where λ=0.5 , and pB is a uniform distribution over {1000,2000,...,8000} .
Figure 4: The comparison of anytime reasoning performance between GRPO and our AnytimeReasoner with various prior budget distributions. Notably, the accuracies at the maximum token budget (8000) reflect the performance in the standard reasoning task.
Figure 5: Ablation on verifiable dense rewards. For GRPO+length_penalty_v1 , we follow Aggarwal and Welleck (2025) , assigning reward 1−bm0.2∣z∣ for the correct answer and 0 for wrong answer. For GRPO+length_penalty_v2 , we follow Arora and Zanette (2025) with α as 0.2.
Figure 6: Ablation on decoupled optimization for summary policy.
Figure 7: Ablation on variance reduction.
Figure 8: The training curves for DeepSeek-R1-Distill-Qwen-7B.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 9: We decouple the generation of thinking and its summary. Given the question, the model first generates the thinking , which can be stopped by a special token </think> or the budget limit. Then we insert ∗∗Final Answer∗∗ (and two ellipsis ⋯ plus </think> for out of budget cases) to prompt the model to summarize the answer . In training, these inserted tokens will be ignored when calculating the loss.
Figure 10: Our methods utilize a tree-like structure for generation and training.
Figure 11: The training curves for main results.
Algorithm
AMC22
AIME24
MATH500
Minerva
OlympiadBench
Avg.
R1-Distill-1.5B
56.4
22.3
81.1
26.3
42.0
45.6
GRPO
65.0
28.9
84.7
28.9
45.9
50.7
AR-base
68.4
32.7
85.5
29.6
47.3
52.7
AR-linear
68.6
32.1
85.6
29.6
47.3
52.6
AR-uniform
68.5
32.2
85.6
29.2
47.2
52.5
Appendix
Table 1: The Final Accuracy by evaluating the maximum budget (8000) for the final models.
Algorithm
AMC22
AIME24
MATH500
Minerva
OlympiadBench
Avg.
R1-Distill-1.5B
48.2
16.3
74.5
24.1
36.0
39.8
GRPO
53.4
19.0
77.2
26.6
38.8
43.0
AR-base
57.0
21.9
78.2
27.3
40.2
44.9
AR-linear
58.2
22.3
79.0
27.7
40.9
45.6
AR-uniform
58.8
22.9
79.4
27.5
41.2
46.0
Appendix
Table 2: The Anytime Accuracy by evaluating 32 budgets (every 250 tokens) for the final models.
Figure 12: The training curves for DeepSeek-R1-Distill-Qwen-1.5B with maximum 16k context length.
Scaling test-time compute via extended reasoning has become a key paradigm for improving the capabilities of large language models (LLMs). However, existing approaches optimize reasoning under fixed or uniformly sampled token budgets, ignoring the fundamental mismatch between problem difficulty and allocated compute. This leads to overthinking on easy problems and underthinking on hard ones, resulting in suboptimal token efficiency across diverse reasoning scenarios. In this paper, we propose Budget-Adaptive Curriculum Reasoning (BCAE), a unified framework that jointly optimizes reasoning quality and token efficiency through three synergistic components: (1) a budget-conditioned unified policy that embeds the token budget as a continuous conditioning signal, eliminating the need for decoupled thinking and summarization strategies; (2) a curriculum-aware budget scheduler that adaptively shifts the training budget distribution from easy to hard problems based on real-time learning progress; and (3) a truncation-aware dense reward mechanism that provides fine-grained credit assignment at intermediate reasoning steps via process-level verification. We further introduce Budget-Conditioned Advantage Estimation (BCAE), a novel variance reduction technique that conditions the advantage baseline on the sampled budget, yielding more stable policy gradients. Experiments on mathematical reasoning benchmarks (MATH, GSM8K, AIME, and Minerva Math) demonstrate that BACR consistently outperforms other strong baselines across all token budgets, achieving up to 8.3% accuracy improvement under tight budgets while reducing average token consumption by 34% compared to unconstrained reasoning.
Large language models (LLMs) can achieve strong reasoning performance with sufficient computation, but they do not inherently know how much computation a task requires. We study budgeted inference-time reasoning for multiple problems under a strict global token constraint and formulate it as an Ordered Stochastic Multiple-Choice Knapsack Problem (OS-MCKP). This perspective highlights a meta-cognitive requirement---anticipating problem difficulty and allocating computation strategically. We propose ROI-Reasoning, a two-stage framework that endows LLMs with intrinsic, budget-aware rationality. First, Meta-Cognitive Fine-Tuning teaches models to predict reasoning cost levels and decide whether a problem is worth attempting before generation. Next, Rationality-Aware Reinforcement Learning optimizes sequential decision making under a hard token budget, allowing models to learn long-horizon allocation strategies. Experiments across mathematical reasoning, multiple-choice question answering, and code generation show that ROI-Reasoning improves scores and generally reduces reference-order regret under tight budgets, with up to a 417% relative score improvement over the strongest same-backbone baseline in mathematics.
Muyang Zhao, Chunhao Tian, Qi Qi +1
Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China
Large Reasoning Models (LRMs) have shown remarkable reasoning capabilities, yet they still suffer from overthinking, generating redundant reasoning steps which incur substantial token consumption. Existing methods, such as suppressing reflective keywords or forcing shorter reasoning lengths, attempt to mitigate this issue but inevitably truncate necessary steps and induce underthinking, thereby compromising performance. To address this dilemma, we investigate the latent representations and observe that efficient reasoning steps naturally cluster into a concentrated region in latent space, while those deviating from this region tend to produce verbose sequences. To leverage this, we keep reasoning focused within this region via a quadratic program which projects deviating hidden states back into the region. Then we propose a novel training-free framework to achieve efficient reasoning that reduces token generation costs without sacrificing performance. Extensive experiments conducted on four models ranging from 1.5B to 14B, and across six benchmarks in math reasoning, coding, and scientific QA, validate the effectiveness of our method, up to a 12.1% improvement in accuracy while reducing generated tokens by 11.8% to 52.8%. Codes are available at https://github.com/hzn18/Opt4Reasoning.