Abstract
Modern Large Language Models (LLMs) have achieved significant breakthroughs in complex reasoning by scaling test-time compute through long Chain-of-Thought (CoT) sequences. However, these models typically optimize for a fixed token budget, leading to performance collapse if interrupted and inefficiencies in token usage. We present AnytimeReasoner, a framework designed to train models that provide the best possible answer at any point during the reasoning process. By employing Budget Relative Policy Optimization (BRPO) and a dense reward structure, AnytimeReasoner produces models that are more flexible, token-efficient, and accurate than standard reasoning baselines.
Introduction
The emergence of reasoning-heavy models like OpenAI’s o1 and DeepSeek-R1 has shifted the focus of LLM development toward test-time compute scaling. While effective, these models are often trained to reach a conclusion only after a specific, often lengthy, reasoning path. This "fixed-budget" paradigm introduces three primary challenges:
- Inflexibility: Models often fail to provide a coherent answer if the reasoning process is truncated.
- Inefficiency: There is little incentive for the model to reach a correct conclusion early, leading to unnecessary compute consumption.
- Sparse Rewards: Standard Reinforcement Learning (RL) provides feedback only at the end of a long sequence, complicating the credit assignment problem.
To address these issues, we introduce AnytimeReasoner, which optimizes for the "area under the success curve," ensuring high accuracy across varying computational budgets.
Methodology
The Anytime Reasoning Objective
AnytimeReasoner shifts the training objective from final-state correctness to anytime correctness. During training, we sample multiple "thinking budgets" (e.g., 2,000, 4,000, or 8,000 tokens). The model is required to pause at these intervals and generate a summary of its current best guess. This approach allows the model to learn how to refine its internal state progressively.
Verifiable Dense Rewards
By focusing on mathematical reasoning tasks with verifiable ground-truth answers, we transform the traditional sparse reward signal into a dense one. The model receives feedback at every sampled budget point. This dense reward structure provides a clearer learning signal, helping the model identify which specific segments of its reasoning process contribute to a correct final answer.
Decoupled Optimization and Tree-like Training
To ensure that the quality of the reasoning process is not bottlenecked by the model's ability to summarize, we decouple the "thinking" policy from the "summary" policy. Furthermore, to maintain computational efficiency during training, we utilize a tree-like structure: the model generates a single long reasoning trace and "branches off" at various budget points to produce summaries, rather than re-generating the entire trace for every budget.
Budget Relative Policy Optimization (BRPO)
The core algorithmic innovation is Budget Relative Policy Optimization (BRPO). Building upon Group Relative Policy Optimization (GRPO), BRPO introduces a variance reduction technique using an interpolated baseline. This baseline combines the model's current progress with the average performance of a group of reasoning traces, significantly stabilizing the RL training process when dealing with multiple budget constraints.
Experimental Setup
We fine-tuned DeepSeek-R1-Distill-Qwen-1.5B and 7B models using a dataset of 40,315 math problems from DeepScaleR. Evaluation was conducted across a rigorous suite of benchmarks, including AIME2024, AMC2022, MATH500, and Olympiad Bench.
Results and Discussion
Superior Accuracy and Efficiency
AnytimeReasoner consistently outperformed standard GRPO baselines across all tested budgets. On the AIME 2024 benchmark, the AnytimeReasoner (1.5B) achieved 32.7% accuracy, a notable improvement over the 28.9% achieved by the baseline. Interestingly, optimizing for anytime performance also improved the final-limit performance; the 1.5B model reached a 52.7% average accuracy compared to the baseline's 50.7%.
Robustness to Interruption
One of the most significant advantages of AnytimeReasoner is its robustness. While standard models experience a sharp decline in performance when their reasoning is cut short, AnytimeReasoner maintains high accuracy even when restricted to 25% of its maximum token budget. The model effectively learns to "converge" on the correct answer earlier in the thinking process.
Scalability
The benefits of the framework scale effectively with model size. When moving from the 1.5B to the 7B parameter model, we observed a consistent ~5 point absolute improvement in anytime accuracy, suggesting that the AnytimeReasoner framework is well-suited for larger-scale deployments.
Conclusion and Future Work
AnytimeReasoner demonstrates that LLMs can be trained to be both highly accurate and computationally flexible. By utilizing dense rewards and BRPO, we mitigate the credit assignment problem and create models that are efficient under varying deployment constraints. Future research will explore extending this framework to non-mathematical domains where answers are less easily verifiable and investigating different prior distributions for budget sampling to further optimize short-budget performance.
Summary updated