Optimizing Anytime Reasoning via Budget Relative Policy Optimization
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.
682d84d6aa4903837eeac1dc
Penghui Qi
claimed_verified
2025-05-21T08:39:35.138Z
63885f1d0bebb233d8ad6e5b
https://cdn-avatars.huggingface.co/v1/production/uploads/1669881620925-noauth.jpeg
Penghui Qi
user
QPHutu
682d84d6aa4903837eeac1dd
Zichen Liu
claimed_verified
2025-05-21T09:31:12.541Z
65f5392c68b8e0cb3c9977a2
/avatars/aa64772475098e8a135c13072fde6744.svg
Zichen
user
lkevinzc
682d84d6aa4903837eeac1de
Tianyu Pang
admin_assigned
2025-05-21T10:12:08.028Z
63d91b6d255ef6add20e1b38
https://cdn-avatars.huggingface.co/v1/production/uploads/1675921369867-63d91b6d255ef6add20e1b38.jpeg
Tianyu Pang
user
P2333
682d84d6aa4903837eeac1df
Chao Du
admin_assigned
2025-05-21T10:12:18.649Z
632407c892e07e3ca20aca28
/avatars/23b51b37b12b51a0947f687d1de4d3b5.svg
Chao Du
user
duchao
682d84d6aa4903837eeac1e0
Wee Sun Lee
682d84d6aa4903837eeac1e1
Min Lin
Optimizing Anytime Reasoning via Budget Relative Policy Optimization
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.
The AnytimeReasoner framework optimizes token efficiency and reasoning flexibility for large language models by introducing verifiable dense rewards and a decoupled policy optimization technique.
large language models (LLMs) reinforcement learning (RL) token budget anytime reasoning performance verifiable dense rewards thinking and summary policies Budget Relative Policy Optimization (BRPO) mathematical reasoning tasks GRPO