Research map / Reinforcement learning / RL from feedback
Optimizing Anytime Reasoning via Budget Relative Policy Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes AnytimeReasoner, which trains LLM reasoning under sampled thinking budgets with forced summaries that give verifiable dense rewards, plus a BRPO variance-reduction baseline and decoupled thinking/summary optimization.
Problem
RL for LLM reasoning optimizes only final accuracy under a large fixed token budget, which hurts training efficiency and gives no good answers when thinking is interrupted early (anytime reasoning).
Approach
Sample thinking budgets from a prior distribution, truncate the thinking trace and force a summary at each budget to obtain verifiable dense rewards; reduce advantage variance with BRPO, a baseline mixing discounted past-budget rewards (V1) and the group average return (V2); and optimize thinking and summary policies with different budget priors.
Key results
- Final accuracy averaged over five benchmarks rises from 50.7 (GRPO) to 52.7 (AR-base) and 52.5-52.6 for budget-sampled variants at the 8000-token budget.
- Anytime accuracy averaged over 32 budgets rises from 43.0 (GRPO) to 46.0 (AR-uniform) on the 1.5B model.
- Achieves 32.7% on AIME 2024 versus 30.3% reported for MRT.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AnytimeReasoner with a uniform thinking-budget prior instead of GRPO | DeepSeek-R1-Distill-Qwen-1.5B · AMC2022 | anytime accuracy: 53.4 -> 58.8 | Helped |
| Use AnytimeReasoner with a uniform thinking-budget prior instead of GRPO | DeepSeek-R1-Distill-Qwen-1.5B · AIME2024 | anytime accuracy: 19.0 -> 22.9 | Helped |
| Use AnytimeReasoner with a uniform thinking-budget prior instead of GRPO | DeepSeek-R1-Distill-Qwen-1.5B · MATH500 | anytime accuracy: 77.2 -> 79.4 | Helped |
| Use AnytimeReasoner with a linear thinking-budget prior instead of GRPO | DeepSeek-R1-Distill-Qwen-1.5B · AMC2022 | final accuracy: 65.0 -> 68.6 | Helped |
| Use AnytimeReasoner with maximum-budget-only training instead of GRPO | DeepSeek-R1-Distill-Qwen-1.5B · AIME2024 | final accuracy: 28.9 -> 32.7 | Helped |
| Use AnytimeReasoner with a linear thinking-budget prior instead of GRPO | DeepSeek-R1-Distill-Qwen-1.5B · MATH500 | final accuracy: 84.7 -> 85.6 | Helped |
| Use AnytimeReasoner with maximum-budget-only training instead of GRPO | DeepSeek-R1-Distill-Qwen-1.5B · Minerva Math | final accuracy: 28.9 -> 29.6 | Helped |
| Use AnytimeReasoner with maximum-budget-only training instead of GRPO | DeepSeek-R1-Distill-Qwen-1.5B · Olympiad Bench | final accuracy: 45.9 -> 47.3 | Helped |
| Add verifiable dense rewards to the thinking-policy objective (ablation) | GRPO with linear budget prior · Mathematical reasoning tasks | anytime accuracy | Helped |
| Add verifiable dense rewards to the thinking-policy objective (ablation) | GRPO with linear budget prior · Mathematical reasoning tasks | average thinking length | Helped |
| Train the summary policy on uniformly distributed thinking budgets, decoupled from the thinking policy (ablation) | GRPO · AMC benchmark | accuracy | Helped |
| Add BRPO variance reduction to the thinking-policy training (ablation) | GRPO · AIME benchmark | accuracy | Helped |
Surprising findings
- Even the AR-base variant, which optimizes only the maximum budget, outperforms GRPO at all thinking budgets, which the authors attribute to decoupled summary optimization and BRPO variance reduction.
Limitations
- Evaluated only on mathematical reasoning tasks.
- Only a small budget support (m<=8) is used rather than evaluating all budgets.
Experimental setup
Datasets: DeepScaleR
Benchmarks: AIME2024 AMC2022 MATH500 Minerva Math OlympiadBench
Metrics: final accuracy at 8000 budget anytime accuracy averaged over 32 budgets average thinking length
Baselines: GRPO Dr. GRPO MRT length penalty reward shaping DeepSeek-R1-Distill-Qwen-1.5B
Builds on: GRPO Dr. GRPO PPO DAPO VinePPO
Closest papers by meaning
- Thinking on the Fly: Test-Time Reasoning Enhancement via Latent Thought Policy Optimization (ICLR 2026 · similarity 0.91)
- Resource-Efficient Reinforcement for Reasoning Large Language Models via Dynamic One-Shot Policy Refinement (ICML 2026 · similarity 0.91)
- Think Smarter not Harder: Adaptive Reasoning with Inference Aware Optimization (ICML 2025 · similarity 0.90)
- Don’t Think Longer, Think Wisely: Optimizing Thinking Dynamics for Large Reasoning Models (NeurIPS 2025 · similarity 0.90)
- Accelerating RL for LLM Reasoning with Optimal Advantage Regression (NeurIPS 2025 · similarity 0.90)
- How Far Are We from Optimal Reasoning Efficiency? (NeurIPS 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.