title: Optimizing Anytime Reasoning via Budget Relative Policy Optimization
summary: 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.
paper_authors._id: 682d84d6aa4903837eeac1dc
paper_authors.name: Penghui Qi
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-05-21T08:39:35.138Z
paper_authors._id: 63885f1d0bebb233d8ad6e5b
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/1669881620925-noauth.jpeg
paper_authors.fullname: Penghui Qi
paper_authors.type: user
paper_authors.user: QPHutu
paper_authors._id: 682d84d6aa4903837eeac1dd
paper_authors.name: Zichen Liu
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-05-21T09:31:12.541Z
paper_authors._id: 65f5392c68b8e0cb3c9977a2
paper_authors.avatarUrl: /avatars/aa64772475098e8a135c13072fde6744.svg
paper_authors.fullname: Zichen
paper_authors.type: user
paper_authors.user: lkevinzc
paper_authors._id: 682d84d6aa4903837eeac1de
paper_authors.name: Tianyu Pang
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-05-21T10:12:08.028Z
paper_authors._id: 63d91b6d255ef6add20e1b38
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/1675921369867-63d91b6d255ef6add20e1b38.jpeg
paper_authors.fullname: Tianyu Pang
paper_authors.type: user
paper_authors.user: P2333
paper_authors._id: 682d84d6aa4903837eeac1df
paper_authors.name: Chao Du
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-05-21T10:12:18.649Z
paper_authors._id: 632407c892e07e3ca20aca28
paper_authors.avatarUrl: /avatars/23b51b37b12b51a0947f687d1de4d3b5.svg
paper_authors.fullname: Chao Du
paper_authors.type: user
paper_authors.user: duchao
paper_authors._id: 682d84d6aa4903837eeac1e0
paper_authors.name: Wee Sun Lee
paper_authors._id: 682d84d6aa4903837eeac1e1
paper_authors.name: Min Lin
paper_title: Optimizing Anytime Reasoning via Budget Relative Policy Optimization
paper_summary: 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.
paper_ai_summary: The AnytimeReasoner framework optimizes token efficiency and reasoning flexibility for large language models by introducing verifiable dense rewards and a decoupled policy optimization technique.
paper_ai_keywords: 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