# Optimizing Anytime Reasoning via Budget Relative Policy Optimization

arXiv: https://arxiv.org/abs/2505.13438 · HTML: https://mlsanity.com/paper/2505.13438/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 32 of its 44 references that are in the map.
- First posted on arXiv 19 May 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 32)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [OlympiadBench: A Challenging Benchmark for Promoting AGI with Olympiad-Level Bilingual Multimodal Scientific Problems](https://mlsanity.com/paper/2402.14008/) (2024)
- [Tulu 3: Pushing Frontiers in Open Language Model Post-Training](https://mlsanity.com/paper/2411.15124/) (2024)
- [SimpleRL-Zoo: Investigating and Taming Zero Reinforcement Learning for Open Base Models in the Wild](https://mlsanity.com/paper/2503.18892/) (2025)
- [Process Reinforcement through Implicit Rewards](https://mlsanity.com/paper/2502.01456/) (2025)
- [Open-Reasoner-Zero: An Open Source Approach to Scaling Up Reinforcement Learning on the Base Model](https://mlsanity.com/paper/2503.24290/) (2025)
- [L1: Controlling How Long A Reasoning Model Thinks With Reinforcement Learning](https://mlsanity.com/paper/2503.04697/) (2025)
- [Demystifying Long Chain-of-Thought Reasoning in LLMs](https://mlsanity.com/paper/2502.03373/) (2025)
- [Token-Budget-Aware LLM Reasoning](https://mlsanity.com/paper/2412.18547/) (2024)
- [Training Language Models to Reason Efficiently](https://mlsanity.com/paper/2502.04463/) (2025)
- [Dynamic Early Exit in Reasoning Models](https://mlsanity.com/paper/2504.15895/) (2025)
- [ReMax: A Simple, Effective, and Efficient Reinforcement Learning Method for Aligning Large Language Models](https://mlsanity.com/paper/2310.10505/) (2023)
- [Reasoning Models Can Be Effective Without Thinking](https://mlsanity.com/paper/2504.09858/) (2025)
- [The Impact of Reasoning Step Length on Large Language Models](https://mlsanity.com/paper/2401.04925/) (2024)
- [Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuning](https://mlsanity.com/paper/2503.07572/) (2025)
- [Concise Thoughts: Impact of Output Length on LLM Reasoning and Cost](https://mlsanity.com/paper/2407.19825/) (2024)
- [Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thought](https://mlsanity.com/paper/2501.04682/) (2025)

## Built on by (most cited first, 27 of 27)

- [Don't Overthink it. Preferring Shorter Thinking Chains for Improved LLM Reasoning](https://mlsanity.com/paper/2505.17813/) (2025)
- [Defeating the Training-Inference Mismatch via FP16](https://mlsanity.com/paper/2510.26788/) (2025)
- [e3: Learning to Explore Enables Extrapolation of Test-Time Compute for LLMs](https://mlsanity.com/paper/2506.09026/) (2025)
- [Don't Overthink It: A Survey of Efficient R1-style Large Reasoning Models](https://mlsanity.com/paper/2508.02120/) (2025)
- [Rethinking the Trust Region in LLM Reinforcement Learning](https://mlsanity.com/paper/2602.04879/) (2026)
- [Promoting Efficient Reasoning with Verifiable Stepwise Reward](https://mlsanity.com/paper/2508.10293/) (2025)
- [Entropy After </Think> for reasoning model early exiting](https://mlsanity.com/paper/2509.26522/) (2025)
- [SofT-GRPO: Surpassing Discrete-Token LLM Reinforcement Learning via Gumbel-Reparameterized Soft-Thinking Policy Optimization](https://mlsanity.com/paper/2511.06411/) (2025)
- [Does Your Reasoning Model Implicitly Know When to Stop Thinking?](https://mlsanity.com/paper/2602.08354/) (2026)
- [Towards Concise and Adaptive Thinking in Large Reasoning Models: A Survey](https://mlsanity.com/paper/2507.09662/) (2025)
- [Language Models Can Learn from Verbal Feedback Without Scalar Rewards](https://mlsanity.com/paper/2509.22638/) (2025)
- [From Efficiency to Adaptivity: A Deeper Look at Adaptive Reasoning in Large Language Models](https://mlsanity.com/paper/2511.10788/) (2025)
- [Group Distributionally Robust Optimization-Driven Reinforcement Learning for LLM Reasoning](https://mlsanity.com/paper/2601.19280/) (2026)
- [How Far Are We from Optimal Reasoning Efficiency?](https://mlsanity.com/paper/2506.07104/) (2025)
- [Variational Reasoning for Language Models](https://mlsanity.com/paper/2509.22637/) (2025)
- [ROI-Reasoning: Rational Optimization for Inference via Pre-Computation Meta-Cognition](https://mlsanity.com/paper/2601.03822/) (2026)
- [Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models](https://mlsanity.com/paper/2601.11340/) (2026)
- [The Art of Efficient Reasoning: Data, Reward, and Optimization](https://mlsanity.com/paper/2602.20945/) (2026)
- [Not All Turns Are Equally Hard: Adaptive Thinking Budgets For Efficient Multi-Turn Reasoning in Agents](https://mlsanity.com/paper/2604.05164/) (2026)
- [Best Practice Critic Optimization](https://mlsanity.com/paper/2608.23566/) (2026)
- [Process Supervision of Confidence Margin for Calibrated LLM Reasoning](https://mlsanity.com/paper/2604.23333/) (2026)
- [One Policy, Any Budget: Internalizing Budget-Aware Search via Reinforcement Learning](https://mlsanity.com/paper/2609.00813/) (2026)
- [Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data](https://mlsanity.com/paper/2601.11038/) (2026)
- [A State-Transition Framework for Efficient LLM Reasoning](https://mlsanity.com/paper/2602.01198/) (2026)
- [Internalizing Agency from Reflective Experience](https://mlsanity.com/paper/2603.16843/) (2026)
- [Avoiding Overthinking and Underthinking: Curriculum-Aware Budget Scheduling for LLMs](https://mlsanity.com/paper/2604.19780/) (2026)
- [Breaking the Reward Barrier: Accelerating Tree-of-Thought Reasoning via Speculative Exploration](https://mlsanity.com/paper/2605.10195/) (2026)

## Abstract (arXiv)

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.