Optimizing Anytime Reasoning via Budget Relative Policy Optimization
Authors: Penghui Qi
Zichen Liu
Tianyu Pang
Chao Du
Wee Sun Lee
Min Lin
Venue: NeurIPS 2025 poster ()
Keywords: Anytime Reasoning
Reinforcement Learning
LLM Reasoning
GRPO
Primary area: deep_learning
TL;DR: AnytimeReasoner optimizes LLM reasoning under variable token budgets by introducing verifiable dense rewards and a variance reduction method (BRPO), enabling more efficient RL for both final and anytime reasoning performance.

Abstract: 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 **AnytimeReasoner**, a novel framework for optimizing reasoning performance under varying thinking 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.

Optimizing Anytime Reasoning via Budget Relative Policy Optimization
Penghui Qi Zichen Liu Tianyu Pang', Chao Du', Wee Sun Lee", Min Lin'
'Sea Lab Naational University of Singapore
https: //g::////tttt com/sail-sg Anytmmeeeasooeer
Anytime reasoning
Budget Relative Policy Optimization
Taytia (9)
Aphnish
by
+
6m
b
bm
V1
Optimize anytime reasoning
Success probability
by maximizing this grest
daak
0.38
by
5g
...
Dye
0.33
Thinking budget (token)
Figure 1: Left: We optimize anytime reasoning by sampling thinking budgets from a prior distribution Ps and maximizing the rewards at sampled budgets to push up the area under the curve. This objective naturally introduces verifiable dense rewards into the thinking process. Right: Budget Relative Policy Optimization (BRPO) leverages these dense rewards to improve advantage estimation via the Monte Carlo return (R) and an interpolated baseline that combines current progress (V1) and the average return within the rollout group (V2).
Abstract
Scaling test-time compute crucial for enhancing the reasoning capabilities of large language models (LLMs). Existing approaches typically employ reinforce- ment learning (RL) to maximize a verifiable reward obtained at the end reasoning traces. However, such methods optimize only the final performance under large and fixed token budget, which hinders efficiency and flexibility in both training and deployment. In this work, present SenytimeReasoonee optimizing reasoning performance under varying thinking budget constraints. To achieve this, truncate the complete thinking process to fit within sampled token budgets from 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 assign- ment 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.
novel framework for
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Introduction
OpenAI ol [OpenAI, 2024] and DeepSeek-R1 [Guo et al., 2025] have shown that scaling test-time compute via RL is crucial for LLM reasoning. This involves an extensive thinking process using the chain of thought (CoT) [Wei et al., 2022] before producing an answer. RL is then employed to maximize the outcome reward provided by a rule-based verifier to check the correctness of the generated answer. While RL for LLM reasoning is an active area of research, most existing work focuses on optimizing final performance based on the complete thinking process. This approach can be inefficient in both training and deployment, as long CoTs are costly, especially for online services.
In our work, we focus on optimizing anytime reasoning for LLMs via RL. This is conceptually similar to the anytime algorithms introduced in Dean and Boddy [1988], Zilberstein and Russell [1995], where the system can be interrupted at any point during computation, providing the best possible solution so far and is expected to improve the solution quality when more resources allocated. Concretely in LLM reasoning, we assume the thinking process can be interrupted at any time, and the model should be able to summarize the best solution from incomplete thinking. This capability can significantly extend the serving capacity for online services with limited computing resources. When there are too many requests to handle, the service can choose interrupt in- in-progress requests once the thinking length is able to give sufficient accuracy, reserving longer thinking with better accuracy when resources are available. Moreover, users may want to control the thinking budget as in Gemini 2.5[Comanici et al., 2025], but the optimal budget is often agnostic. Compared to budget- aware reasoning| Han et al., 2024], our design supports an economical strategy by incrementally increasing the budget, as it allows for continued thinking and reuses the computation already spent.
To achieve optimal performance for anytime reasoning, propose sampling the thinking budget from a prior distribution while learning, rather than using a fixed, large budget as in prior work [Liu al., 2025, Zeng et al., 2025, Luo al., 2025]. This approach makes the model performance robust to potential interruptions in the thinking process, while incentivizing it to reach correct answers more efficiently. By achieving a balance between token efficiency and thorough exploration [Qu et al.. 2025], these models are also able to obtain better performance when given larger budgets.
We investigate how to efficiently train LLMs with RL under sampled thinking budgets. By forcing the model to summarize the answers at predefined thinking budgets (drawn from the support of the prior distribution), we introduce verifiable dense rewards into the reasoning process. These rewards provide richer signals and better credit assignment during training [Qu et al., 2025, Cui al., 2025a]. We also propose a novel variance reduction technique termed Budget Relative Policy Optimization (BRPO) that advances beyond GRPO [Shao et al., 2024] to improve training stability and efficiency under this dense reward framework. As illustrate in Figure (right), we leverage rewards at previous budgets to compute the advantage function, combining with the average return of group of reasoning trajectories. Empirically, we observe that generating a high-quality summary is critical for both final and anytime performance. Thus. we decouple the optimization of the thinking and summary policies, always sampling from a uniform distribution to derive a better summary policy, thereby improving training efficiency.
We term overall framework as AnytimeReasoner. Experimental results demonstrate that Any- timeReasoned consistently surpasses GRPO in both final and anytime performance. We conduct extensive ablation studies to evaluate the impact of each component. By independently incorporating decoupled optimization, variance reduction, and budget sampling into GRPO, we observe significant performance enhancements, underscoring the effectiveness of our methods. Notably, even when merely using the maximum token budget (without budget sampling), our method still outperforms GRPO in both standard and anytime reasoning. highlighting the robustness of our approach.
2 Methodology
In a training paradigm similar to RI-Zero [Guo et al., 2025], the model is tasked with generating a comprehensive CoT within designated "thinking box" upon receiving a question. Subsequently, the model summarizes the answer based on this thinking process. A rule-based reward is then calculated according to the summarized answer. The RL objective is to maximize the expected reward:
I [(0]=
Ex ~ 2x
To (-x) By ~ Te 1,,
[r(z, 2)]
(1)
queetion
Sritiig process
2

---

where r represents the question, denotes the thinking process, is the summarized answer, and r(z, y) is the reward function.
In previous studies [Zeng et al., 2025, Liu et al., 2025, Luo et al., 2025], the generation of thinking process and summary are typically sampled together. If the thinking process exceeds the predefined generation limit, the response is considered a negative sample. We contend that this approach is impractical, particularly in online services where valid summary should be provided even if the thinking process is incomplete. We propose decoupling the generation of the thinking process and its summary, allocating separate token budgets for each. When the thinking process halted due to budget constraints, we insert ellipses followed by </think> to prompt the model to produce summary (see Appendix A), similar Muennighoff al. [2025] and Qu al. [2025].
To differentiate between the thinking and summary policies, we denote the thinking policy as me E.
[r(a,y)]. the objective can be and the summary policy TT. By defining re r2( y(
expressed as:
0(, empx. [ro(2,
Given that ly| < |z|. multiple summaries can be sampled better estimate the expected reward for each thinking process, while incurring only small computational overhead.
2.1 Optimizing Anytime Reasoning
Test-time scaling [OpenAI, 2024] is crucial for enhancing the reasoning capabilities of LLMs. This concept operates on the premise that increased computational effort during the reasoning process generally leads better performance. However, in typical RL training setups like R1-Zero-like [Guo et al., 2025], the performance on anytime reasoning is not guaranteed. The reward evaluation is based on the entire thinking process, lacking insight into whether incremental thinking consistently improves performance [Qu et al., 2025].
To optimize anytime reasoning, rather than using a fixed token budget. Let b represent the token budget for thinking. sampled from a prior distribution pg over of increasing budgets {bi...., bm, (P3 ps(b = bj) for simplicity).
propose sampling the thinking budget from prior distribution
The anytime reasoning objective is:
m Parola, Pyro(e, 2500)
E Janytime (0, 2o-px to
[To =50)]
(3)
where zgb the truncated thinking process at length of the token budget b,
if 2 |z| zgb truncate(2, b). if b [2|
Instead of focusing solely on the final score based on the entire thinking process as in standard reasoning task, we maximize the expected score over all possible budgets with distribution ps. As illustrated in Figure I, this is akin to maximizing the area under the score curve when is uniform distribution across every token budget. However, evaluating for all token budgets impractical and unnecessary, so we evaluate the score only at a small predefined budget support (with r S 8 in our experiments).
important to note that this approach transforms the problem into a dense reward framework, introducing verifiable dense rewards for each thinking budget. This facilitates better credit assignment during RL training and enhances the identification of each component's 's contribution to successful reasoning process. As illustrated in Figure 2, the dense rewards for budgets prior to reaching correct answer are low. However, the cumulative return is relatively higher if the reasoning process ultimately arrives at correct answer. contrast, the cumulative return after the first correct answer is relatively low, localizing and highlighting the tokens that contributed to the initial correct answer. This approach distinct from typical sparse reward RL training for standard reasoning tasks, where all tokens receive the same return. Such sparse reward structures typically lead to unstable and inefficient RI training, while our dense reward approach provides more informative learning signals throughout the entire reasoning process.
3

---

Reasoning
4
question
Intermediate
reward
0.1
Tj 0.8
1.0
thinking
Cumulative
1.9
1.9
Ry = 1.8 Rg 1.0
Return
Figure 2: By introducing dense rewards, we achieve better credit assignment during RL training. We assume uniform distribution over thinking budgets and omit the probability for simplicity.
Relation to Standard Reasoning Tasks A larger thinking budget is supposed to yield better performance in expectation. Since zgb is always a prefix of 2, the optimal summary policy Tg
should satisfy:
E [ro- (2, a><0(112))
E (x, (z,
for any b and x. Then we have:
Janytime (0, (0,6') S T(0,6")
(5)
This justifies the anytime reasoning objective as a lower bound of the standard reasoning objective. Therefore, maximizing performance in anytime reasoning should also enhance performance in standard reasoning tasks. In am extreme case where P'm = 1 (training only with full reasoning length), Janyúme falls back to the standard reasoning objective J. For detailed proof, refer to Appendix C.
2.2 Budget Relative Policy Optimization
By defining arg miny by f, which represents the nearest token budget after t, the gradient for the thinking policy can be computed as follows:
V Janyuiee (0,
Ve log
(6)
xxpx mommolll
where
R(x,2,0) Σ Para( 2gb,),
j=
and V(z, Z<1) is the variance reduction term, which should be a function correlated to R(x, 2.) but invariant with respect to 2t.
Typically, we set Vax, 22() ~ 2.22))
R(x, [Res, 22d J.)]. representing the expected future
return [Sutton and Barto, 2018]. In traditional RI, GAE[Schulman et al., 2015] often used by estimating this value with critic model. However, training critic model for LLM can be both costly and noisy [Guo et al., 2025]. alternative is sampling-basee approach, as in VinePPO [Kazemnejad et al., 2024] and Remax [Li et al., 2023], but this requires significant additional computation across all thinking budgets. Group-based methods, such as GRPO [Shao et al., 2024] and RLOO [Ahmadian al., 2024], treat generation as a bandit and use the average score of multiple responses for variance reduction. However, they are unsuitable in our scenario due to the presence of dense rewards.
In LLM generation, newly sampled tokens (actions) are consistently appended to the existing context (states). This implies that current context (=<x) always serves as a prefix for any future context (I=c; This unique property distinguishes it from traditional RL but is often overlooked. Assuming perfect summary policy that consistently extracts the best answer from the thinking process, the reward should increase monotonically with the number of generated tokens, satisfying To(2, =<c2) S (1 [Z<1, 2. Consequently, the current reward r Z<t) is correlated with any future reward r (x. [Zee, ). particularly when t is large enough yield correct answer when [ | This correlation justifies its use as a suitable baseline for variance reduction.
Building on this insight, we introduce Budget Relative Policy Optimization (BRPO) for efficient variance reduction. Specifically, we employ the following variance reduction term:
- -rrrrr 25b,)
V1
1=
Σ Ps
E No-J
j=j.

---

Normalized Coveriance
Normalizeed Variance
Viarty (Mr A1
0.0
Whrrly (ibee VLNNNAA
EAPO (OdR VIYWTA3
0.3
0.-
0.4
V.
Corri C. RR
C.)
1002
2300
1000
6003
7000
1500
3050
6200
0.8
0.8
0.9
0.0
0.1
0/-
02-
V.
1002 2000
1000
7000
1500
3030
1002
6con
7000
Figure 3: Left: The correlation coefficient of V1 and 1/2 with R(x, z, jt). Right: The normalized variance of our BRPO. We evaluate the R1-Distill-1.5B model under the scenario where 0.5, and ps is uniform distribution over (1000, 2000, .... 8000).
where the evaluated scores at previous budgets, weighted by a discount factor A. serve as the reward baseline (highlighted in red), and are multiplied by the sum of probabilities after je align with the scale of R(z, (t)).
As illustrated in Figure 3, when is small, the effectiveness of Ví may diminish because short thinking process z<* provides limited information. such cases, we apply a variant of GRPO as a complement. We sample set of thinking processes {2 22 ,..., C) and compute:
V/2 = T Σ 2(a,e'.jo)
which represents the expected return after je given the question Note that the correlation between V22 and R(x, 2, jt) decreases as increases, as shown in Figure 3, due to differing prefixes (z<z) in these thinking processes.
By combining Vi and V2, the overall variance reduction term is: Jr
V(r, Rct) = j: - m
V2_
(9)
m
As demonstrated in Figure 3, our BRPO significantly outperforms GRPO in reducing variance, especially when the thinking is long.
2.3 Decoupled Optimization for Thinking and Summary
In rigorous derivation, the optimization of thinking and summary policies should share the same prior budget distribution Ps- However, an optimal summary policy crucial when the thinking process is incomplete, and its effectiveness is significantly influenced by ps. An imbalanced prior distribution can lead to suboptimal summary policy. To achieve a robust anytime reasoning performance, we decouple the optimization of thinking and summary policies by using different budget distribution, P'g. for the summary policy. The decoupled gradient of the summary policy with respect to the anytime reasoning objective 3 can be computed as follows:
V log(Ts(y/aa R5a, Dr(a, wi]| w
E V a Janytimee (0, () awPA.Emea (-ba))
PS
(10)
In our experiments, we set P/ as uniform distribution over the budget support (b....., b,, }. We employ distinct approach to optimize the summary policy. Specifically, for each question æ and thinking process zgby,> we sample a group of summaries and use GRPO to stabilize the optimization.
Typically, shared model (o = 0) is used for both thinking and summary policies. In such cases, the overall gradient is:
V Janytime (0)
Vo Vomatiieeee (0, (0,0) 1omo + V Vo Tanattieee (0, ()) 6=00
5

---

Average
AMC 2022
AIME 2024
Accurcy (%
NL B6A1-155 GAPO
RJ Diill1135 GRFO
11
GAPO
Anyli reaassneaaseeeeeeeee
Angtmmeeassiee bace
Aryf mekeassne base
Aryllnekessiretiinnn
Arytimeteassone Stear
mekeasseee Enear
Angtimeeessseenene
Any metessonen unifor
2003
2010
4100
100
20.00
12:0
1080
180
2000
199
1269
2000
MATH
MINERVA
OLYMPIAD BENCH
Accuracy (54
NL D6A.-1155
RC Diiil1135
RI BLLBUULL.
GAPO
GRPO
GAPO
Anylira Dewscrann-Caee
Angt mateeccoee bove
Anylima Deatcren Inear
Anyf mateessone-
Anylina Fwwascne form
Aryf wwnggmmtttsssoo..co www.ooooo--oooorrr
200
200
2010
4.00
1280
20.0
3009
+2/0
2010
6000
N00
2800
2007
2:00
+0.0
5800
6200
7000
Budget
Budget
Budget
Figure 4: The comparison of anytime reasoning performance between GRPO and our AnytimeRea- soner with various prior budget distributions, Notably, the accuracies the maximum token budget (8000) reflect the performance in the standard reasoning task.
Experiments
We implement algorithms based on the Verl framework [Sheng al., 2024], incorporating several key modifications as detailed in Appendix B. We employ Proximal Policy Optimization (PPO) [Schulman et al., 2017] optimize both thinking and summary policies. For the thinking policy, we use BRPO to compute the advantage function, as detailed in Section 2.2. During training, we allocate four token budgets (m = for thinking: (2000, 4000, 6000, 8000). For each question, sample group of 8 complete thinking processes (stopped either by </think> or when exceeding 8000 tokens). We sample answers calculate the average score at each thinking budget, which is used to compute the advantage function as in Dr. GRPO [Liu et al., 2025]. The summary length is restricted 128 tokens. We extract the first answer and use rule-based verifier determine the 0/1 outcome reward. As detailed in Section 2.3, we employ different prior distributions for the thinking and summary policies. Unless otherwise specified, the prior distribution P's for the summary policy is set to uniform distribution.
We fine-tuned DeepSeek- SeepSeck-R1-DDee R1-Distill- Seeill-wenn--.... 1.5B [Guo al., 2025] 40,315 math problems from DeepScaleR [Luo et al., 2025] for a single epoch, using a batch size of 64 questions per policy iteration. Our experiments were conducted 8 NVIDIA A 100 80G GPUs, with each experiment taking approximately 30 hours to complete (less than 10% overhead in total compared to GRPO). During training, we evaluate the average scores of AIME2024 and AMC2022 every 20 steps and report their performance curves, sampling 32 responses for each question. After training, we assess the final model using five benchmarks: AIME2024 [Li et al., 2024a], AMC2022 [Li al., 2024a], MATH500 [Hendrycks et al., 2021], Minerva Math [Lewkowycz et al., 2022], and Olympiad Bench [He al., 2024], with 32 uniform token budgets ranging from 0 to 8000. We compare our methods with GRPO [Shao et al., 2024], incorporating the corrections introduced in Dr. GRPO [Liu al., 2025].
3.1 Main Results
We consider the following prior distributions Ps when optimizing the thinking policy by equation 3:
Base: We only optimize the final performance as in standard reasoning task, namely Pm. 1.
Uniform: We set Ps as uniform distribution.
Linear: We assign probability proportional to the budget length, such that ps (b) oc b.

---

We evaluate the final models after training and plot the score curves under varying thinking budgets Figure 4. For each question AMC and AIME, we sample 320 thinking processes to compute the average score. For other datasets, we sample 80 thinking processes per question.
As shown in Figure 4, all variants of method consistently outperform GRPO by large margin across varying prior distributions. With small budgets, ing optimization of these budgets. When the thinking budget large, AnytimeReasoner with different prior distributions tends to converge to similar performance, demonstrating the robustness of our where we optimize performance only under the
excels by prioritiz-
approach. Notably, even for AnytimeReasoner- maximum thinking budget as in the GRPO baseline, we still achieve significant better performance all thinking budgets. This improvement is due the decoupled optimization and our variance reduction technique (discussed further in Section 3.2.3). More details and additional evaluations on longer context can found in Appendix
3.2 Ablations
To further investigate which aspects of our framework contribute performance improvements, we conduct detailed ablations considering three factors: verifiable dense rewards (Section 3.2.1) I), decoupled optimization (Section 3.2.2), and variance reduction (Section 3.2.3). We report three metrics during training. Anytime Accuracy: the average accuracy over thinking budgets at (2000, 4000, 6000, 8000). Final Accuracy: the accuracy the maximum budget (8000). Average Thinking Length: the average thinking length under the maximum budget (8000).
3.2.1 Verifiable Dense Rewards
Anytime Accuracy (%))
Final Accuracy (%)
Thinking
68.00
08/01 lengti panaky.st
08:0+ legth paralty
AMC 2022
0810+11ear
GRPO
GAPO
ChFCwlargth senalty
GRP Beineliggt peralty 1t
carcsstrrgh fogtt senatry
Ghr0+langir peralty 1Q
2000
12
perakl..
AIME 2024
GRnO
CEPO
wwwphh_prnnttyy... GRO0
persity
G6P0-
5000
ale
sio
350
Training Step
Training Step
Training Stop
Figure 5: Ablation verifiable dense rewards. For GRPO+ vl, we follow Aggarwal and Welleck [2025], assigning reward 0.2/2| for the correct answer and 0 for wrong answer. For bm GRPO+length_penndhe v2, we follow Arora and Zanette [2025] with a 0.2.
We investigate the effectiveness of verifiable dense rewards by modifying the objective of the thinking policy in equation 3 with a linear prior distribution, while keeping the summary policy training consistent with GRPO. Specifically, we use V/2 as the variance reduction term to align with GRPO and climinate the influence of enhanced variance reduction. To demonstrate efficiency, we compare it against reward shaping. which uses a length penalty on correct answers to encourage concise reasoning [Aggarwal and Welleck, 2025, Arora and Zanette, 2025].
method's superior token
As illustrated in Figure incorporating dense rewards improves both the anytime and final per- formance. Notably, since our objective diverges from directly optimizing final performance as in the GRPO baseline, the observed improvements can be attributed to enhanced credit assignment facilitated by dense rewards. Another prominent observation is that the average thinking length is clearly shorter than the GRPO baseline under the maximum budget. This because the thinking policy is encouraged to arrive at correct answer quickly as possible, making the model favor
7

---

shorter, correct responses. Although reward shaping with length penalty can also reduce the thinking length. it sacrifices the performance and is unstable during training.
3.2.2
Decoupled Optimization
Anytime Accuracy (%)
Accuracy (%)
Average Thinking Length
6400
AMC 2012
100
-APD G1tD idecouple
GAIP
1100
CRIPSI decAD
12
NUMB 2024
Training Step
Training Stop
Training Step
Figure 6: Ablation on decoupled optimization for summary policy.
To study the impact of decoupled optimization for thinking and summary policies (detailed in Section 2.3), modify the training of summary policy in GRPO align with AnytimeReasoner, while keeping the thinking policy training unchanged. Specifically, we sample 4 answers for each thinking budget in (2000, 4000, 6000, 8000), applying GRPO within each summary group. This approach trains summary policy under uniformly distributed thinking budgets, while the thinking policy optimizes performance only under the maximum budget (8000).
As shown in Figure 6, the decoupled GRPO clearly outperforms the vanilla GRPO, especially in the AMC benchmark. Notably, the significant improvement in anytime accuracy (the average score under sampled thinking budgets) indicates that decoupled optimization results in a better summary policy for anytime reasoning.
3.2.3 Variance Reduction
Anytime Accuracy (%5)
Final Accuracy (%)
Average Thinking Length
AMC 2022
1150
54
GBR
CRTP dendacasl
54-
UIti tut desouple
GRRO
400
200
100
204
G5P0
GRRR
G8.0
GAVF
20 dineeppe
N:0
CiI1
GB30 wore decop
AIRE 2024
1000
18
Training
Training
Figure 7: Ablation on variance reduction.
To evaluate the effectiveness of our BRPO variance reduction (as detailed in Section 2.2), we modified the training of the thinking policy by incorporating BRPO's variance reduction techniques, while maintaining the summary policy training consistent with GRPO. Specifically, we set m and P(bm) in equation 7, aligning the objective exactly with GRPO.

---

Figure 7 shows that our approach enhances performance on the AIME benchmark. As discussed in Section 3.2.2, the suboptimal summary policy in GRPO may constrain the potential of BRPO's effectiveness. To address this, we introduced decoupled optimization (detailed in Section 2.3) to improve the summary policy, resulting in further performance gains.
3.3 Evaluation on 7B Model
We also evaluated our approach a larger model, DeepSeek-R -isbsee-eR---isstil--eee------- For this experi- ment, we modified the training setup by rumning two epochs on the DeepScaleR dataset with a batch size of 128 questions per iteration. We incorporated the clip higher technique from Yu et al., 2025] to prevent entropy collapse[Cui et al., 2025b] observed in the training. As shown in Figure 8, our AnytimeReaseee Reasonr framework achieves clearly superior performance anytime reasoning. with a maximum improvement of about 5 absolute points. For standard reasoning, our methods outperform the GRPO baseline for most of the time during training, despite high variance in the final accuracy..
Anytime Accuracy (56
Accuracy (%)
Average Thinking Length
01:0
AMC 2022
mo Bimn anv mechoa trear
Anydim Reaieeinaaaeeetteeeeee
1750
Anytima Mewsenassssr---oo
Adytlie Keassnen intar Anydima Nasccrannnnnen
Anytino hessonce Frear
Anyl melaas buse
Arytima Taancren
1.0
100
2
AINE 2024
GEPO
CAFD
Anyl rnd Tiuas oner un form
Anytima Nasicren..toom
Arştiri Meascnar-nffom
meeeenneeee kreer
Anytiie-Raaeeee Itear
4150
mrrPecacee buse
Anglima Nassomarn beie
Anylima feaaSTer basa
Training Stop
Training Step
Training Step
Figure& 8: The training curves for Seapeeek-RI-isttiiee Bertill--wee-7B..
4 Related Works
Reinforcement Learning with Verifiable Rewards Since the introduction of DeepSeck-RI [Guo et al., 2025], a growing body of research has adopted the reinforcement learning with verifiable rewards (RLVR) paradigm [Lambert al., 2024] to improve the reasoning capabilities of large language models (LLMs). SimpleRL [Zeng et al., 2025] provides the first open-source replication of R1-Zero in mathematical domains and analyzes RL dynamics across various base models. Hu et al. [2025] demonstrate that removing the KL regularization used in RLHF [Christiano et al., 2017] improves both RI. efficiency and asymptotic performance. Liu al. [2025] identify an optimization bias in GRPO [Shao et al., 2024] and propose Dr.,GRPO, which applies Monte Carlo policy gradient method with a baseline [Sutton and Barto, 2018). While these works improve our understanding of RI RI-Zero-style training, they still depend sparse outcome-basee based rewards, which pose challenges for credit assignment and learning efficiency [Kazemnejad et al., 2024]. In contrast, our method introduces novel policy optimization framework that leverages cheaply estimated verifiable dense rewards to improve sample efficiency and learning stability.
Token Budget Efficiency of Reasoning Models Previous efforts have studied budgeted reasoning by reducing response length through prompting [Jin et al., 2024, Nayab et al., 2024, Lee et al., 2025, Ma et al., 2025] or adaptive sampling (Yang al., 2025]. While these training- free approaches can shorten outputs, they often entail trade-off between conciseness and task performance. More recent work explores token efficiency within online RL frameworks, enabling models to jointly optimize for accuracy and brevity. Yeo et al. [2025] observe that the output lengths on harder questions tend to grow during RI training, and propose a cosine-shaped reward to constrain length. Liu et al. [2025] trace this issue to optimization bias in GRPO and show that correcting it enhances token efficiency.

---

Further, Arora and Zanette [2025] and Aggarwal and Welleck [2025] apply explicit reward shaping to target shortened or fixed outputs. Our work differs by operating in an anytime reasoning framework, where the reasoning process can be interrupted at anytime and the best-effort solution should be provided [Dean and Boddy, 1988, Zilberstein and Russell, 1995]. Despite not explicitly enforeing conciseness, our objective naturally encourages efficient reasoning, as demonstrated empirically.
Connection to MRT An independent work to ours, MRT [Qu et al., 2025], optimizes test-time compute by minimizing cumulative regret relative to an oracle. Since the oracle is unknown, they employ meta-RL. [Xiang et al., 2025, Beck et al., 2023] as an approximation, aiming to maximize the "progress" of each newly generated episode. Despite sharing a similar high-level goal, our formulation fundamentally differs. Rather than minimizing regret, we optimize anytime performance by sampling the thinking budget from prior distribution, remaining tractable with standard RL techniques. These foundational distinctions lead to significant methodological differences. Firstly, per-token basis, instead of on episode which is ambiguous and can be hackable in RL if not well handled. Secondly, our method is grounded in principled RL, explicitly accounting for long term returns. In contrast, MRT adopts a greedy strategy, optimizing the progress of immediate next episode only. Our experimental results also significantly outperform their reported outcomes. We achieve accuracy of 32.7% compared their reported 30.3% AIME 2024.
approach operates
5
Conclusion
The effectiveness of test-time scaling in LLM reasoning is commonly attributed to the generation- verification gap [Xiang et al., 2025], where verifying solutions substantially easier than generating them. During reasoning, the model engages in an iterative search process, exploring potential solutions until valid one found. Once generated, the solution verified for correctness, and this search-verificatio loop continues until confident answer is produced.
In this work, we present framework that systematically exploits this ceneration-verificatiin gap. Our approach is based on the key observation that verifying answers and extracting them from partial reasoning traces easy and computationally cheap. Building on this insight, we design our framework to produce answers at some predefined thinking budgets, thereby introducing verifiable dense rewards enhance RL training. Furthermore, we utilize these additional rewards to construct a more effective variance reduction baseline than GRPO, significantly improving the stability and efficiency of RL training. By integrating these techniques, our framework achieves superior performance in both standard and anytime reasoning tasks.
10

---

References
Pranjal Aggarwal and Sean Welleck. L1: Controlling how long reasoning model thinks with reinforcement learning. arXiv preprint arXiv: 2503.04697, 2025.
Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzich Fadace, Julia Kreutzer, Olivier Pietquin, Ahmet Üstün, and Sara Hooker. Back to basies: Revisiting reinforce style optimization for learning from human feedback in llms. arXiv preprint arXiv:2402.14740, 2024.
Daman Arora and Andrea Zanette. Training language models to reason efficiently. arXiv preprint arXiv: 2502.04463 2025.
Jacob Beck, Risto Vuorio, Evan Zheran Liu, Zheng Xiong, Luisa Zintgraf, Chelsea Finn, and Shimon Whiteson. A survey of meta-reinforrcemet learning, arXiv preprini arXiv:2301.08028, 2023.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, et al. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arXiv preprint arXiv:2507.0622), 2025.
Ganqu Cui, Lifan Yuan, Zefan Wang, Hanbin Wang, Wendi Li, Bingxiang He, Yuchen Fan, Tianyu Yu, Qixin Xu, Weize Chen, et al. Process reinforcement through implicit rewards. arXiv preprint arXiv:2502.01456, 2025a.
Ganqu Cui, Yuchen Zhang, Jiacheng Chen, Lifan Yuan, Zhi Wang. Yuxin Zuo, Haozhan Li, Yuchen Fan, Huayu Chen, Weize Chen, al. The entropy mechanism of reinforcement learning for reasoning language models. arXiv preprint arXiv:2505.22N0 22611, 2025b.
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory- efficient exact attention with io-awareness. Advances in neural information processing systems, 35: 16344 16359, 2022.
Thomas L. Dean and Mark S Boddy. An analysis of time-dependent planning. In AAAI, volume 88, pages 49-54, 1988.
Daya Guo, Dejian Yang, Haowei Zhang. Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseck-rl: Incentivizing reasoning capability in 1lms via reinforcement learning. arXiv preprint arXiv:2501. 2025.
Tingxu Han, Zhenting Wang, Chunrong Fang, Shiyu Zhao, Shiging Ma, and Zhenyu Chen. Token- budget-aware IIm reasoning. arXiv preprint 2rXiv:2412.18557, 2024.
Chaoqun He, Renjie Luo, Yuzhuo Bai, Shengding Hu, Zhen Leng Thai, Junhao Shen, Jinyi Hu, Xu Han, Yujie Huang, Yuxiang Zhang, al. Olympiadbench: A challenging benchmark for promoting agi with olympiad-level bilingual multimodal scientific problems. arXiv preprint arXiv:2402. 14000 14008, 2024.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.0387. 2021.
Jingeheng Hu, Yinmin Zhang, Qi Han, Daxin Jiang, and Heung Yeung Shum Xiangyu Zhang. Open- reasoner-zero: An open source approach to scaling reinforcement learning on the base model. cww/ com/Open Swaam/Deen-Rasoee---Zaaa
https://githut
Reasoner- Zero, 2025.
Mingyu Jin, Qinkai Yu, Dong Shu, Haiyan Zhao, Wenyue Hua, Yanda Meng, Yongfeng Zhang, and Mengnan Du. The impact of reasoning step length on large language models, In ACL (Findings), 2024.
11

---

Amirhossein Kazemnejad, Milad Aghajohari, Eva Portelance, Alessandro Sordoni, Siva Reddy, Aaron Courville, and Nicolas Le Roux. Vineppo: Unlocking rl potential for Ilm reasoning through refined credit assignment. arXiv preprint arXiv:2410.01679, 2024.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James V Miranda, Alisa Liu, Nouha Dziri, Shane Lyu, et al. TŞ"" ulu 3: Pushing frontiers in open language model post-training. arXiv preprint urXiv:2411. 151124, 2024.
Ayeong Lee, Ethan Che, and Tianyi Peng. How well do Ilms compress their own chain-of-thoughh? a token complexity approach. arXiv preprint arXiv: 33140, 2025.
Aitor Lewkowyez, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ra- masesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, et al. Solving quantitative reasoning problems with language models. Advances in Neural Information Processing Systems, 35:3843-3857, 2022.
Jia Li, Edward Beeching, Lewis Tunstall, Ben Lipkin, Roman Soletskyi, Shengyi Huang, Kashif Rasul, Longhui Yu, Albert Q Jiang, Ziju Shen, et al. Numinamath: The largest public dataset in ai4maths with 860k pairs of competition math problems and solutions. Hugging Face repository, 13:9, 2024a.
Junyan Li, Delin Chen, Tianle Cai, Peihao Chen, Yining Hong, Zhenfang Chen, Yikang Shen, and Chuang Gan. Flexattention for efficient high-resolution vision-language models. In European Conference on Computer Vision, pages 286-302. Springer, 2024b.
Ziniu Li, Tian Xu, Yushun Zhang, Zhihang Lin, Yang Yu, Ruoyu Sun, and Zhi- Zhi-Quan Luo. Remax: A simple, effective, and efficient reinforcement learning method for aligning large language models. arXiv preprint arXiv: 230::23000.000 2023.
Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi, Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin. Understanding r rl-zero-like training: A critical perspective. arXiv preprint arXiv:2503.20783, 2025.
Michael Luo, Sijun Tan, Justin Wong, Xiaoxiang Shi, William Y. Tang, Manan Roongta, Colin Cai, Jeffrey Luo, Tianjun Zhang, Li Erran Li, Raluca Ada Popa, and Ion Stoica. Deepscaler: Surpass- ing ol -preview with a 1.5b model by scaling rl. https: //github./ wwt. www.aaninnnanjeeeeee deepscaler, 2025.
Wenjie Ma, Jingxuan He, Charlie Snell, Tyler Griggs, Sewon Min, and Matei Zaharia. Reasoning models can be effecctive without thinking. arXiv preprint arXiv:2504. 09858, 2025.
Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannanch Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling. arXiv preprint arXiv:2501.1939) 2025.
Sania Nayab, Giulio Rossolini, Marco Simoni, Andrea Saracino, Giorgio Buttazzo, Nicolamaria Manes, and Fabrizio Giacomelli. Concise thoughts: Impact of output length on Ilm reasoning and cost. arXiv preprint arXiv: 2407. 19007.9955... 2024.
OpenAI. Learning to reason with llms, 2024. te-sinn setason-wwtt--1e with-11ms/.
URL https://openai.com www.coodem////////eco/c
Yuxiao Qu, Matthew YR Yang, Amrith Setlur, Lewis Tunstall, Edward Emanuel Beeching, Ruslan Salakhutdinov, and Aviral Kumar. Optimizing test-time compute via meta reinforcement fine- tuning. arXiv preprint arXiv:2503.07572. 2025.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv: 150.. 004802438 2015.
12

---

John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint wTXiv:1077.06347, 2017.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300. 2024.
Guangming Sheng, Chi Zhang, Zilingfeng Ye, Xibin Wu, Wang Zhang, Ru Zhang, Yanghua Peng, Haibin Lin, and Chuan Wu. Hybridflow: A flexible and efficient rlhf framework. arXiv preprint arXiv:2409. 19256, 2024.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
Violet Xiang, Charlie Snell, Kanishk Gandhi, Alon Albalak, Anikait Singh, Chase Blagden, Duy Phung, Rafael Rafailov, Nathan Lile, Dakota Mahan, et al. Towards system reasoning in llms: Learning how to think with meta Shain-of-though! arXiv preprint arXiv:250I 004682, 2025.
Chenxu Yang, Qingyi Si, Yongjie Duan, Zheliang Zhu, Chenyu Zhu, Zheng Lin, Li Cao, and Weiping Wang. Dynamic early exit reasoning models. arXiv preprint arXiv: 2504. 15895, 2025.
Edward Yeo. Yuxuan Tong, Morry Niu, Graham Neubig, and Xiang Yue. Demystifying long chain-of-thought reasoning llms. arXiv preprint arXiv:2502.03377, 2025.
Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yue, Weinan Dai, Tiantian Fan, Gaohong Liu, Lingjun Liu, et al. Dapo: An open-source IIm reinforcement learning system at scale. arXiv preprint arXiv:2503.144700 2025.
Weihao Zeng, Yuzhen Huang, Qian Liu, Wei Liu, Keqing He, Zejun Ma, and Junxian He. Simplerl- zoo: Investigating and taming zero reinforcement learning for open base models in the wild. arXiv preprint arXiv:2503. 220.55333.822.22 18892, 2025.
Shlomo Zilberstein and Stuart Russell. Approximate reasoning using anytime algorithms. In Imprecise and approximate computation, pages 43-62. Springer, 1995.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We focus on optimizing anytime reasoning task, and present novel framework in Section 2.1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [NA]
13

---

Justification:
There is no obvious limitation.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
We provide assumptions in Section 2.1 and proofs in Appendix C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide implement details in Section B,
Guidelines:
The answer NA means that the paper does not include experiments.
14

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The data public accessible. We will open-source our code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ Sodiides/CodeSubmissst
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: (oodeSSmmissioonll...c
/ //nips. /twpss.ccppubbii.. http:cccpppppppccccceeeecopppeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We provide training and details in 3.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: For the training curves in ablation studies (Section 3.2.1, 3.2.2, 3.2.3), the experiments are expensive (8 GPUs for 30 hours). For the main results in Section 3.1, we rum many enough data points report the average score.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide these information in Section 3.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tttps://neurpps... http://hwurrips.cccpuulc////eeee cc/publicc/thiccouueeee
Answer: [Yes]
Justification: No ethics issue involved.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: It is just research task, no any societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We do not release any data and model, there is risk.
17

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The code and data is cited in Section 3.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
18

---

Answer:
[NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: No such risks.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non soa-standard components.
Please refer to our LLM policy (https : /ttp///eeerppeeeeee cc/Conferences//22 /LLM) for what should or should not be described.
19

---

Appendix
Table of Contents
Implementation Details
20
B Tree-like Generation and Training
20
Relation Between Standard and Anytime Reasoning
21
D Experimental Results
22
D.1 Main Results
22
D.2 Evaluation on 16k Context Length
22
A Implementation Details
We illustrate the implementation details about how we truncate the reasoning process and prompt the model to output an answer.
|| User polynomial SxN22)+ox+368 have two distinct integer roots? Let's
>Far how many values of the constant Sk$ will the
User how many values constant the polynomial (2)+k++x+36 have two distinct integer roots? Let's
think step by step and output the final answer within (boxed]].
step by step cutput
answer (boxed]].
Assislant ><thhin>>
< Assistant >-sthink>
Okay, so have this problem here: For how many values of the have distinct integer roots? Hmm, let me to figure this out step by step.
Okay,
problem
many values
constant V |)
polynomial ((x)
constant V \) will the polynomial x²(2) lox 36 have two
distinct integer roots? Hmm, let me try to figure this step by step.
posilive negalive pairs, making
So, we have 4 positive and negative pairs, making pairs in <ithink>
"Final Answer** number of (( (boxed(8).
"Fiinal Answer"
The number of values of k1) is \boxed(B).
(a) Thinking is stopped by </think>.
(b) Thinking is stopped due to out of budget.
Figure 9: We decouple the generation of thinking and its summary. Given the question, the model first generates the thinking. which can be stopped by special token </think> or the budget limit. Then insert Final Answer (and two ellipsis plus </think> for out of budget cases) to prompt the model to summarize the answer. In training, these inserted tokens will be ignored when calculating the loss.
B Tree-like Generation and Training
Unlike previous methods with sequential question-respome generation and training, our approach employs tree-like structure. In this section, introduce how to address implementation challenges for efficient training.
During generation, we use the prefix caching feature of vLLM [Kwon et al., 2023] to reuse computa- tions. We sample a complete thinking process for question æ, then split based on predefined token budgets (fi,j,) in Figure 10). Each partial thinking process is appended with special end- of-think token (</think>), and the model prompted to output the answer directly (see Appendix for more details).
20

---

X2
X
x
x question
incourest Answer
Generation
thinking
cornect Answer
Y
1.0
Training
y
Figure 10: Our methods utilize a tree-like structure for generation and training.
During training, each response is typically concatenated with its corresponding question using FlashAttention [Dao et al., 2022] for speed. However, this introduces significant duplicated compu- tation for tree-like structures, making impractical due high computational demands for LLM training. We implement a tree structure attention mask based on FlexAttention [Li et al., 2024b]. As shown in Figure 10, we append all summaries the end of the thinking process and record their connection positions in a ID tensor. This tensor is converted to block mask by FlexAttention, avoiding 2D tensors that can cause out-of-mente -e--orr issues for long generation lengths.
C Relation Between Standard and Anytime Reasoning
In this section, we provide a proof for the inequality below:
1 - Janytime (0, (,.))) x*).
I Innytim (0, 0, $ J(0,
Pm
According to equation 4, we have:
[ra- (z, (x, z56)l 2-
E
E s>aa((1a))
(x,
Thus, it follows that:
Janytime (0, (0,
E
E [ro(x, 250)] b-ps
E
[r)(2,2))
(11)
amppx
= T(0,6"))
Assuming r(x,)) 2 0, which is always achievable by adding constant to each reward, we also have:
T annytime (005))
E x<px w
E [ro(x, 2<0o] baps
E
[Pm Pmrolon Zgbb
x (-)
(12)
E
(Pmro(s,2))
(0,
Combining 11 and 12, we can get
1 Janytime (0, Φ²).
Janytime (0,005
J(0,0')
<
J
(13)
Pm
This completes the proof.
21

---

Algorithm
AMC22
AIME24
MATH500
Minerva
OlympiadBench
Avg.
RI-Distil-11.5
56.4
22.3
81.1
26.3
42.0
45.6
GRPO
65.0
28.9
84.7
28.9
45.9
50.7
AR-base
68.4
32.7
85.5
29.6
47.3
52.7
AR-linear
68.6
32.1
85.6
29.6
47.3
52.6
AR-uniform
68.5
32.2
85.6
29.2
47.2
52.5
Table 1: The Final Accuracy by evaluating the maximum budget (8000) for the final models.
Algorithm
AMC22
AIME24
MATH500
Minerva
OlympiadBench
Avg.
R1-Distill-1.BB
48.2
16.3
74.5
24.1
36.0
39.8
GRPO
53.4
19.0
77.2
26.6
38.8
43.0
AR-base
57.0
21.9
78.2
27.3
40.2
44.9
AR-linear
58.2
22.3
79.0
27.7
40.9
45.6
AR-uniform
58.8
22.9
79.4
27.5
41.2
46.0
Table 2: The Anytime Accuracy by evaluating 32 budgets (every 250 tokens) for final models.
D Experimental Results
D.1 Main Results
We present the training curves of our AnytimeReasoner in Figure 11, corresponding the experiments in Section 3.1. We also evaluate the performance of the models training step of 600, and report the final accuracy in Table and the anytime accuracy Table
Anytime
Final
Thinking
6420
Anytino www.sher-nnnenneeeeeeeee
Anytine lessance inear
AMC 2022
Anytima Sasa
4102
GAPO
GAPO
Any miluaa orer un form melovrreee freer
Anytima sesoseerrrfoomm Weytime-reeeeee Inear
melleaaeee bas
Angliim Nassomen besd
4100
18
CITO
Argdama TesacTer
MINI 2074
GUUD
SHIP
Anylima Nesscreruution
Training Stop
Training Stop
Training Stop
Figure 11: The training curves for main results.
D.2 Evaluation on 16k Context Length
We also verified the effectiveness of our method on longer context lengths by fine-tuning DeepSeek- Li-Ditill--wee--... up to 16k maximum context. We used a uniform prior over eight thinking budgets: (2k, 4k, 6k, 8k, 10k, 12k, 14k, 16k). As shown in Figure 12, our approach consistently achieves stronger performance in both anytime and standard reasoning.
22

---

Final
GAPO
GRFC
8000
CPPO Unfomm
Un farm
J
ANC 2022
975
355
0370
2210
CEPO Unifomm
AIME 2024
2109
3300
.000
Training Step
Training Stop
Training Stop
Figure 12: The training curves for RI-Distill- with maximum 16k context length.
23


Reviews:
[{"review_id": "ViiCuRXS5P", "reviewer": "Reviewer_Hybv", "summary": "In this paper, the authors propose to improve the token efficiency of large language models by optimizing the accuracy of summarization across different token budgets with reinforcement learning. The authors introduce dense rewards uniformly spaced in the reasoning process. To ensure stable optimization with dense rewards using GRPO, the authors propose two variance reduction baselines, one considering rewards before some certain token budget, and one computing the average reward of all trajectories. The correlation analysis along with the variance analysis shows that the proposed techniques effectively reduces variances.", "questions": "1. In line 113 - 120, the claim \"a larger thinking budget is supposed to yield better performance in expectation\" is questionable. It is possible that an LLM could have higher accuracy under a restricted thinking budget than the full thinking budget. Therefore Eq. 4 and Eq. 5 may not hold in practice.\n\n2. A natural counterpart for the introduced variance reduction techniques is using value models with PPO. How does GRPO with variance reduction compare with PPO w. value model?\n\n3. In Figure 5, is \"GRPO+Linear\" using the variance reduction techniques? How does \"GRPO+Uniform\" that uses uniform distribution perform compared with \"GRPO\" and \"GRPO+Linear\" in this case?\n\n4. In this paper, the authors use a summary policy to summarize a partial reasoning trajectory within 128 tokens. This design would allow the LLM learning to perform additional reasoning within the 128 tokens, contradicting the argument of \"Budget-agnostic LLMs\" in the MRT paper [1]. Could the authors provide a discussion on any negative effects of using and optimizing a summary policy?\n\n[1] Qu, Yuxiao, et al. \"Optimizing test-time compute via meta reinforcement fine-tuning.\" arXiv preprint arXiv:2503.07572 (2025).", "limitations": "As I discussed in the Weakness, the major limitation of this work is lack of meaningful baselines, making it unable to make a fair comparison with prior works. It would be great if the authors could include more baselines.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n- The writing is clear and easy to follow.\n- This work introduces a natural online extension to the prior work, Meta Reinforced Fine-Tuning, by introducing dense rewards.\n- The proposed variance reduction techniques have shown to be able to reduce the variance by a clear margin. \n\nWeakness:\n- The major issue is lack of sufficient baselines. There are many prior works on improving the token efficiency through training, e.g. MRT [1], Efficient Reasoning [2], and O1-Pruner [3]. \n- There exists a convergence issue regarding the experiment setup. The GRPO baseline has not converged according the benchmark results and training curves. If the DeepSeek-R1-Distill-Qwen-1.5B model is well trained, it should achieve at least 40+ score on the AIME24 benchmark.\n- Lack of evaluation on other LLMs. The experiments are all taken on the DeepSeek-R1-Distill-Qwen-1.5B model, limiting the scope of evaluation.\n\n[1] Qu, Yuxiao, et al. \"Optimizing test-time compute via meta reinforcement fine-tuning.\" arXiv preprint arXiv:2503.07572 (2025).\n[2] Arora, Daman, and Andrea Zanette. \"Training Language Models to Reason Efficiently.\" arXiv preprint arXiv:2502.04463 (2025).\n[3] Luo, Haotian, et al. \"O1-Pruner: Length-Harmonizing Fine-Tuning for O1-Like Reasoning Pruning\" arXiv preprint arXiv:2501.12570v2 (2025).", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments. We respond to individual points from your review below.\n\n> In this paper, the authors propose to improve the token efficiency of large language models\n\nTo clarify, while our method does improve the token efficiency in some sense, we believe that the motivation and purpose of the paper go far beyond just token efficiency.\n\nAs stated in the paper, our primary goal to **improve the anytime reasoning capability**, conceptually similar to the established topic in computer science known as the **Anytime Algorithm** (see wikipedia for details). In our setting, reasoning can be interrupted at anytime (following a prior distribution $p_B$). When interrupted, the model should provide the best solution available and is expected to enhance the solution (in quality, accuracy, or confidence) when additional resources are allocated.\n\nIn standard reasoning tasks, the model is not interruptible and always runs to completion under a fixed budget. In contrast, anytime reasoning provides more flexibility and supports features like predefined **thinking budget** (as seen in Gemini 2.5) for cost-sensitive users. Compared to budget-aware methods like L1 (which include the thinking budget in context before reasoning), anytime reasoning operates in a budget-agnostic manner. This supports an economical strategy by incrementally increasing the budget, allowing for continued thinking and reusing the computation already spent.\n\n> The major issue is lack of sufficient baselines. There are many prior works on improving the token efficiency through training, e.g. MRT [1], Efficient Reasoning [2], and O1-Pruner [3].\n\nFor [2] and [3], they are basically based on reward shaping with length penalty. We do compare with a similar baseline L1-Max [4] in our Ablation 3.2.1 (experimental setting in line 221 and the results in line 228). Unfortunately, we uploaded the wrong Figure 5 by mistake, so the curve of length-penalty is missing. The experimental results of length-penalty are (we use the maximum value during training):\n\n| Algorithm    |  Dataset | Anytime Accuracy | Final Accuracy | Average Thinking Length |\n|----|------|------|-------|---------|\n| GRPO  | AMC22     | 59.5    | 66.0   | ~4700   |\n| GRPO+length_penalty   | AMC22     | 60.2    | 65.2  | ~3900 |\n| GRPO+linear  | AMC22     | 61.8    | 67.0  | ~4100  |\n| GRPO         | AIME24    | 23.5 | 30.5 | ~6600 |\n| GRPO+length_penalty   | AIME24    | 23.2    | 29.0  | ~5900 |\n| GRPO+linear  | AIME24     | 25.2    | 32.0  | ~5900    |\n\nAdditionally, as discussed above, anytime reasoning is far beyond token efficiency, so our work is fundamentally different with those prior work focusing on reducing the response length (for token efficiency), including [2] and [3].\n\nMRT [1] is somewhat conceptually similar to our method. However, they hadn't released their code by the time of our submission (their GitHub was empty). They released some code on July 15, but it only included a brief guideline for their RL method. Upon reviewing the guideline, we found that it doesn't make any sense and is inconsistent with the algorithm described in their paper. Moreover, implementing MRT ourselves is not feasible due to missing details — the paper contains only a single paragraph on their RL approach. Therefore, we provide a detailed discussion and comparison with MRT in the final paragraph of Related Work.\n\n[4] Pranjal Aggarwal and Sean Welleck. L1: Controlling how long a reasoning model thinks with\nreinforcement learning. arXiv preprint arXiv: 2503.04697, 2025.\n\n> There exists a convergence issue regarding the experiment setup. The GRPO baseline has not converged according the benchmark results and training curves. If the DeepSeek-R1-Distill-Qwen-1.5B model is well trained, it should achieve at least 40+ score on the AIME24 benchmark.\n\nMany factors can affect the score, including grader, computational resources, maximum token budget, and so on so forth. We argue that only apple-to-apple comparison is meaningful.\n\nOur implementation basically follows DeepScaleR, with 8k thinking budget (for both training and evaluation) and a stricter grader for formatting. \nSome examples reporting AIME24 performance based on the same model:\n* DeepScaleR official: around 32 under 8k token budget.\n* DeepScaleR reproduce (in their issue #44): around 29 under 8k token budget.\n* MRT [1]: 28.7 for original model, and 29.8 for GRPO, under 16k token budget.\n* LASER [5]: 28.9 for original model, 31.5 for LASER_8192. For evaluation, 32k is used.\n\nAll these numbers align with our results.\n\n[5] Liu, Wei, et al. \"Learn to reason efficiently with adaptive length-based reward shaping.\" arXiv preprint arXiv:2505.15612 (2025).\n\n> Lack of evaluation on other LLMs. The experiments are all taken on the DeepSeek-R1-Distill-Qwen-1.5B model, limiting the scope of evaluation.\n\nWe believe RL algorithm should be orthogonal to model architecture because they are in totally different dimensions. Due to compute constraints and non-trivial engineering efforts, we mainly focus on the ablation study to verify the effectiveness of each component in the paper. \n\nTo address the concerns, we started two new experiments on other models. (We report the best score during training in the table).\n\n## Qwen3-4B-Base with 16k token budget (Running)\n\n400 training steps by now.\n\nAfter 160 step, GRPO fallbacks to short-CoT with an obvious performance drop, while AR-uniform still maintains a stable performance improvement. Even before 160 step, AR-uniform still clearly outperforms GRPO in both anytime and final accuracy. This shows that our framework leads to more stable RL training than GRPO.\n\n| Algorithm    |  Dataset | Anytime Accuracy | Final Accuracy |\n|-----|----|----|-----|\n| GRPO         | AMC22     | 52.5  | 55.6 |\n| AR-uniform   | AMC22     | 57.3  | 59.1 |\n| GRPO         | AIME24    | 21.6  | 22.7 |\n| AR-uniform   | AIME24    | 25.6  | 27.3 |\n\n## R1-Distill-Qwen-7B with 16k token budget (Running)\n\n300 training steps by now.\n\n| Algorithm    |  Dataset | Anytime Accuracy | Final Accuracy |\n|----|----|-----|-----|\n| GRPO         | AMC22     | 78.6 | 84.1 |\n| AR-uniform   | AMC22     | 80.6 | 84.4 |\n| GRPO         | AIME24    | 49.1 | 57.5 |\n| AR-uniform   | AIME24    | 51.4 | 59.2 |\n\n\n> In line 113 - 120, the claim \"a larger thinking budget is supposed to yield better performance in expectation\" is questionable. It is possible that an LLM could have higher accuracy under a restricted thinking budget than the full thinking budget. Therefore Eq. 4 and Eq. 5 may not hold in practice.\n\n* For optimal summary policy, there is no doubt that the claim is true. So we use a conservative $\\phi^*$ in Eq. 4 and 5 to avoid controversy.\n* As shown in Figure 4, it also holds in practice. Especially after RL, the performance is smoothly increasing with larger thinking budget.\n* We belive that test-time scaling is based on this premise basically, that's the core idea in principle how we improve the reasoning through RL.\n\n> A natural counterpart for the introduced variance reduction techniques is using value models with PPO. How does GRPO with variance reduction compare with PPO w. value model?\n\nThe main purpose of this paper is to show anytime reasoning framework is superior to standard reasoning. We argue that the choice of RL algorithm should be orthogonal to our main experiments, so a fair comparison should be: GRPO (under standard reasoning) vs. GRPO (under anytime reasoning), or PPO (under standard reasoning) vs. PPO (under anytime reasoning).\n\nAs PPO with a critic model is known to be noisy and requires extra resources, we just choose GRPO, which is more popular and widely adopted as a strong baseline in community. Due to compute constraints and limited human efforts, we cannot afford two RL algorithms in this paper. We leave the exploration of other RL algorithms in the future work.\n\n> In Figure 5, is \"GRPO+Linear\" using the variance reduction techniques? How does \"GRPO+Uniform\" that uses uniform distribution perform compared with \"GRPO\" and \"GRPO+Linear\" in this case?\n\nAs in line 218, we use V_2 only to eliminate the influence of enhanced variance reduction.\n\nWe didn't get enough compute resources during rebuttal to run this experiment, but we believe it won't affect the conclusion.\n\nAs we only train the final summary to align GRPO in this ablation, the summary policy is suboptimal. So we suppose GRPO+linear would be more stable (in Final Accuracy) as the objective is more closer to standard reasoning. This is why we choose linear instead of uniform prior.\n\n> In this paper, the authors use a summary policy to summarize a partial reasoning trajectory within 128 tokens. This design would allow the LLM learning to perform additional reasoning within the 128 tokens, contradicting the argument of \"Budget-agnostic LLMs\" in the MRT paper [1]. Could the authors provide a discussion on any negative effects of using and optimizing a summary policy?\n\n* As in Figure 8, we prompt the model to output the final answer directly after <\\think>, and extract the first answer within \\box{}, instead of the last answer as in many privious work.\n* If the model does continual reasoning (<\\think> appears in $y$), we label it as incorrect answer.\n* We found that the typical format of $y$ is: the model will rephrase the question, and then output the answer. So we set the budget as 128 to allow this format.\n* The average summary length is about 30, which cannot do meaningful reasoning compared to 8k thinking budget.\n* As in our ablation (Section 3.2.2 and 3.3.3), optimizing summary policy is critical, we don't see any negative effects.\n* We don't understand why it contradicts \"Budget-agnostic LLMs\", could you please clarify on this?"}, {"review_id": "kjdcTd95So", "reviewer": "Reviewer_ATMH", "summary": "This paper suggest anytime reasoning, a way to predefine the thinking budget and reason based on the budget. To implement this effectively, the author proposes to truncate the reasoning process based on the given budget and further propose budget relative policy optimization to reduce the variance.  The experimental result show that the propose method largely improve the efficiency and effectiveness over GPRO on anytime reasoning scenario.", "questions": "See the weakness above.", "limitations": "See the weakness above.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\n1) I believe this topic is important as overthinking (and thinking complexity) is one major problem of current reasoning models. In this sense, anytime reasoning is a novel topic to tackle this issue.\n\n2) Also, the method is very well-designed. All components are reasonable and also somewhat simple.\n\n3) The experiments are very well conducted. I like the fact that the authors have considered multiple benchmarks, including easy to hard datasets. Also, I like the analysis. All components are verified well.\n\n4) Overall, the paper is well written and easy to follow\n\n**Weakness**\n\nI do not find a major weakness in this paper. I think the overall paper is very well written and should be accepted to NeurIPS.\\\nThe following are some minor suggestions, and I hope these are well resolved throughout the rebuttal.\n\n1) I can see that the proposed method is more effective on challenging datasets such as AMC or AIME. Does the author have any intuition behind this improvement? To validate this, I think it would be great if the author can provide the performance on easy dataset (e.g., GSM8K) and also include some challenging ones such as AMC 2023, AIME 2025 and GPQA diamond as well (I think it would have similar trends as AIME 2024 and AMC 2023, but will maybe worth it).\n\n2) While I do agree that math is one reasoning-intensive domain, but also considering coding domains will benefit the readers, e.g., MBPP, Humaneval\n\n3) Can the author provide the final accuracy based on no budget (i.e., generate until the model outputs the answer)? I think it is also good to know the upper bound performance without the constraints.\n\n4) One concern is that the budget should be pre-defined before solving the problem. If there is a simple way to estimate the budget (i.e., complexity of the problem) before thinking, it would be great.", "was_revised": true, "final_justification": "I still think the paper has the strength to be accepted. While there was no experimental support (so the concerns are still not resolved), I also agree that academia may not have enough resources for additional experiments. It is not necessary, but it would be great if the AC could check whether the authors' affiliations are academic.", "rebuttal": "We thank the reviewer for the insightful feedbacks. Please see individual points below.\n\n> I can see that the proposed method is more effective on challenging datasets such as AMC or AIME. Does the author have any intuition behind this improvement? \n\nThanks for this insightful observation, we do observe similar trends. We guess there may be two reasons:\n* For harder dataset, the reward signal (the correct responses) is even sparser. By evaluating more thinking budgets, it can potentially provide more positive rewards to help RL training.\n* For harder problems, the model usually spends more thinking tokens before reaching a correct solution. As shown in Figure 3, GRPO suffers from high gradient variance when optimizing those long responses. By introducing BRPO, our RL training becomes more stable, which leads to better performance, especially for longer responses.\n\n> To validate this, I think it would be great if the author can provide the performance on easy dataset (e.g., GSM8K) and also include some challenging ones such as AMC 2023, AIME 2025 and GPQA diamond as well (I think it would have similar trends as AIME 2024 and AMC 2023, but will maybe worth it).\n\n> Can the author provide the final accuracy based on no budget (i.e., generate until the model outputs the answer)? I think it is also good to know the upper bound performance without the constraints.\n\nWe thank the reviewer for the valuable suggestion. Due to the compute constraints, we didn't get enough resources to run such evaluation during rebuttal. We will run them when we get available compute resources.\n\n\n> While I do agree that math is one reasoning-intensive domain, but also considering coding domains will benefit the readers, e.g., MBPP, Humaneval\n\nWe agree that it is worth to validate on more domains especially for coding. However, it is not realistic for most academic researchers to cover too much domains in one paper due to compute constraints and non-trivial engineering efforts. We leave the exporation of other domains in future work.\n\n\n> One concern is that the budget should be pre-defined before solving the problem. If there is a simple way to estimate the budget (i.e., complexity of the problem) before thinking, it would be great.\n\nTo clarify, the generation of anytime reasoning is budget agnostic, taking only question $x$ as input (not depending on a predefined thinking budget $b$).\n\nFor training, we believe it does help if we can adjust the pre-defined budget distribution based on the complexity of the problem. Some initial ideas: 1> we can use a reference model to estimate the token budget it requires to solve a problem 2> after we sample a group of responses, we can use the average response length (multiple a constant) to decide the maximum budget.\n\nIn this paper, we want to keep it simple as the first version. We leave the exploration of adaptive budget in future work."}, {"review_id": "kDdjAvZTnK", "reviewer": "Reviewer_takS", "summary": "This paper introduces AnytimeReasoner, a novel framework designed to optimize the \"anytime reasoning\" capabilities of LLMs under varying computational budgets. The core technique involves sampling thinking budgets from a prior distribution, truncating the reasoning trace at these budgets, and compelling the model to generate a summary. Overall this work proposes three key contributions: \n\n- **Verifiable Dense Rewards in Anytime Reasoning**: This work introduces verifiable dense rewards throughout the anytime reasoning trajectory, which provides richer training signals and enables more effective credit assignment compared to the sparse rewards of conventional methods.\n\n- **Budget Relative Policy Optimization (BRPO)**: A novel variance reduction technique that leverages these dense rewards to stabilize and improve the learning process.\n\n- **Decoupled Optimization**: A strategy for separately optimizing the thinking and summary policies to ensure high-quality output from incomplete thoughts, resulting in a better summary policy for anytime reasoning.", "questions": "1. What is the computational overhead of the AnytimeReasoner framework during training compared to a vanilla GRPO implementation, especially considering the tree-like generation and multiple summary evaluations?\n2. Have you considered evaluating the AnytimeReasoner framework on other foundational models like Llama, across different model scales, or extending to longer response length (>8k) ? These experiments may further validate the effectiveness of your method.\n3. What is the intuition or theoretical explanation for using a linear prior distribution for budget sampling?", "limitations": "See weakness.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strength\n\n1. This paper introduces a novel and practical concept of \"anytime reasoning\" to LLMs, addressing a practical problem where computational resources are limited or users are cost-sensitive, especially in online services.\n\n2. This paper proposes a novel mechanism for introducing verifiable dense reward. By truncating the reasoning process and generating summaries at various budgets, the framework artfully transforms the sparse reward problem common in RL into a dense reward one. This provides a powerful signal for credit assignment and a richer way to analyze the model's reasoning process.\n3. Through solid ablation studies, the paper validates the effectiveness of its three core components: verifiable dense rewards, decoupled optimization, and BRPO variance reduction. This clearly illustrates each component's contribution to the performance gains.\n\n\n### Weakness\n\n1. The study's findings are based on a single model architecture (DeepSeek-R1-Distill-Qwen-1.5B) and are validated exclusively on mathematical reasoning tasks. This narrow scope makes it unclear if the AnytimeReasoner framework would be equally effective for other foundational model series, reasoning domains, or for tasks requiring response lengths beyond the 8,000-token budget used in the experiments.\n\n2. The framework introduces several new hyperparameters, such as the set of budget points $\\{b_1,\\cdots,b_B\\}$ used in training , the discount factor $\\lambda$ in BRPO , and the choice of prior distribution $p_B$. Although the paper tests a few distributions, it lacks an in-depth discussion of how these hyperparameters were chosen and how sensitive the model's performance is to them.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful feedbacks. See responses to individual points below\n\n> The study's findings are based on a single model architecture (DeepSeek-R1-Distill-Qwen-1.5B) and are validated exclusively on mathematical reasoning tasks. This narrow scope makes it unclear if the AnytimeReasoner framework would be equally effective for other foundational model series, reasoning domains, or for tasks requiring response lengths beyond the 8,000-token budget used in the experiments.\n\n> Have you considered evaluating the AnytimeReasoner framework on other foundational models like Llama, across different model scales, or extending to longer response length (>8k) ? These experiments may further validate the effectiveness of your method.\n\nWe believe RL algorithm should be orthogonal to model architecture because they are in totally different dimensions, so we mainly focus on the ablation study to verify the effectiveness of each component. We agree that it is worth to validate on more domains especially for coding. However, it is not realistic for most academic researchers to cover all of these scopes due to compute constraints and non-trivial engineering efforts. So we leave the exporation of other domains in future work.\n\nTo address the concerns, we started several new experiments. (We report the best score during training in the table).\n\n## R1-Distill-Qwen-1.5B with 16k token budget (completed)\n\nWe achieve similar conclusion for 16k token budget: AR-uniform clearly outperforms GRPO in both anytime and final accuracy.\n\n| Algorithm    | Evaluation Dataset | Anytime Accuracy | Final Accuracy | Average Thinking Length |\n|--------------|-----------|------------------|----------------|------------------------|\n| GRPO         | AMC22     | 64.2             | 67.3           | ~6200                  |\n| AR-uniform   | AMC22     | 68.3             | 70.5           | ~6100                  |\n| GRPO         | AIME24    | 29.8             | 33.8           | ~9400                  |\n| AR-uniform   | AIME24    | 34.1             | 37.1           | ~9400                  |\n\n## Qwen3-4B-Base with 16k token budget (Running)\n\n400 training steps by now.\n\nAfter 160 step, GRPO fallbacks to short-CoT with an obvious performance drop, while AR-uniform still maintains a stable performance improvement. Even before 160 step, AR-uniform still clearly outperforms GRPO in both anytime and final accuracy. This shows that our framework leads to more stable RL training than GRPO.\n\n| Algorithm    | Evaluation Dataset | Anytime Accuracy | Final Accuracy |\n|--------------|-----------|------------------|----------------|\n| GRPO         | AMC22     | 52.5             | 55.6           |\n| AR-uniform   | AMC22     | 57.3             | 59.1           |\n| GRPO         | AIME24    | 21.6             | 22.7           |\n| AR-uniform   | AIME24    | 25.6             | 27.3           |\n\n## R1-Distill-Qwen-7B with 16k token budget (Running)\n\n300 training steps by now.\n\n| Algorithm    | Evaluation Dataset | Anytime Accuracy | Final Accuracy |\n|--------------|-----------|------------------|----------------|\n| GRPO         | AMC22     | 78.6             | 84.1           |\n| AR-uniform   | AMC22     | 80.6             | 84.4           |\n| GRPO         | AIME24    | 49.1             | 57.5           |\n| AR-uniform   | AIME24    | 51.4             | 59.2           |\n\n> The framework introduces several new hyperparameters... Although the paper tests a few distributions, it lacks an in-depth discussion of how these hyperparameters were chosen and how sensitive the model's performance is to them.\n\nDue to high computational requirements and the compute constrains, we do not tune the hyperparameters too much, the performance may not be optimal but we suppose in general it works well.\n\nFor $b_B$, we always set it as the maximum allowed generation length, which is a commonly used hyperparameter in existing framework.\n\nFor the support size $B$, we tried 2/4 for $b_B=8k$, found that both outperforms GRPO and $B=4$ performs better. We also tried $B=8$ for $b_B=16k$ (see above table), which also consistently outperforms GRPO. Generally, we set $b_i = 2000i$ in most of our experiments.\n\nFor $\\lambda$, we always set it as 0.5 in all of our experiments and didn't try other values. It may not be the optimal value regarding to variance reduction, but we suppose it should be better than GRPO generally because GRPO has high gradient variance for longer responses (see Figure 3). Additionally, it's easy and relatively cheap to check the variance reduction effectiveness before training (to decide the value of $\\lambda$), as in Figure 3.\n\n\n> What is the computational overhead of the AnytimeReasoner framework during training compared to a vanilla GRPO implementation, especially considering the tree-like generation and multiple summary evaluations?\n\nLess than 10%.\n\nAs mentioned in Appendix B, we implement a tree-like attention based on FlexAttention to avoid duplicated computation, which has comparable throughput with FlashAttention. So the only overhead is the extra summaries sampled. Ususally the summary length is much shorter than thinking, so the overhead is quite small (less than 10%). In our experiments, we sample 4 summaries for each budget (per 2k tokens), where the average length of summaries quickly converge to about 30. The overall training time for some AR settings are even faster than GRPO, because of the shorter response length.\n\nBTW, we have already uploaded our code in Supplementary Material (related code can be found in verl/models/transformers/flex_attn.py), and we will opensource all of the implementations once the paper is released. We hope our engineering efforts can also benefit the community for such tree-like attention training.\n\n\n> What is the intuition or theoretical explanation for using a linear prior distribution for budget sampling?\n\nThe prior distribution describes the optimization objective for an anytime reasoning system, where the system can choose to interrupt the thinking process based on the workload, and users can also predefine a thinking budget to save cost. We can summarize the statistics into the prior distribution to optimize the overall performance of this anytime reasoning system. \n\nIn the paper, we present 3 typical prior distributions:\n* the base prior which equals to the standard reasoning\n* the uniform prior which maximizes the area as in Figure 1 (easy to understand)\n* the linear prior which may be more realistic because longer responses are more likely to be interrupted\n\nAnother motivation why we design the linear prior is: the uniform prior is not theoretically guaranteed to outperform the base prior in Final Accuracy (due to Eq. 5). So we design the linear prior as an interpolation between the uniform prior and base prior, aiming to maintain the Final Accuracy. However, experimental results surprisingly show that all 3 priors converges to similar Final Accuracy (see the last points in Figure 4), because BRPO and decoupled optimization already fully utilize the intermediate rewards to improve the performance."}, {"review_id": "ow5VeyvI66", "reviewer": "Reviewer_JDmN", "summary": "The paper proposes an innovative reinforcement learning framework, AnytimeReasoner, which optimizes the real-time reasoning ability of LLM through budget sampling and dense reward mechanism. The core contributions include: budget sampling mechanism, BRPO variance reduction technology, and policy decoupling optimization. The paper verifies the superiority of the method on 6 mathematical reasoning datasets (AMC/AIME, etc.).", "questions": "1) Does the gradient derivation of formula 6 imply a KL constraint? If V(x,z_{<t}) is removed, will the strategy collapse?\n\n2) Does the negative reward scenario (such as wrong answer penalty) destroy the inequality chain of formula 13? Additional theoretical analysis is needed", "limitations": "No", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1)  Dense Reward Mechanism: Generating verifiable intermediate rewards through mind truncation to solve the credit allocation problem caused by sparse rewards.\n\n2) ​Performance Boundary Proof​​: Deriving the performance relationship between real-time reasoning and standard reasoning to provide a theoretical guarantee for the framework.\n\n3) Tree-like attention mask (Figure 9): Solve the computational redundancy of traditional sequence training.\n\n\nWeaknesses:\n\n1) Convergence proof missing: BRPO's upper bound on gradient variance is not quantified (Formula 6)\n\n2) Reward function assumptions: r(x,y)≥0 is required (Formula 12), and negative reward scenarios are not discussed\n\n3) Limitation of baseline comparison: lack of comparison with classic RL algorithms such as PPO/REINFORCE\n\n4) Insufficient domain generalization: only validates mathematical reasoning (algebra/geometry), does not cover scientific reasoning/decision making\n\n5) Theoretical supplement: Add BRPO convergence proof (upper bound of gradient variance)", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. See response to individual points below.\n\n> Convergence proof missing: BRPO's upper bound on gradient variance is not quantified (Formula 6)\n\n> Theoretical supplement: Add BRPO convergence proof (upper bound of gradient variance)\n\nWe don't understand what do you mean by convergence proof? To the best of our knowledge, we don't see such proof in any RL paper. Could you please provide a reference paper to clarify what is and why we need a \"convergence proof\"?\n\n\n> Reward function assumptions: r(x,y)≥0 is required (Formula 12), and negative reward scenarios are not discussed\n\n> Does the negative reward scenario (such as wrong answer penalty) destroy the inequality chain of formula 13? Additional theoretical analysis is needed\n\nAssuming $r\\geq0$ (or satisfying some other contraints) is a common technique in RL to do theorectical proof, because in theory reward can be scaled/shifted without affecting the optimal policy in the MDP. In practice $r \\geq 0$ is always achievable by adding a large constant to every reward, without changing the optimal policy. Please refer to [1] for a similar assumption and proof (see Assumption 4.1 and the proof of Theorem 4.1).\n\nIn the case of Formula 12 and 13, the purpose is just to show that the final performance of the optimal anytime policy is well bounded, not too far from the optimal policy in standard reasoning task. The range and scale of rewards don't matter, not affecting this conclusion.\n\nMoreover, the right-hand side of formula 13 (formula 12) is relatively trivial. That’s why we only include the left-hand side (formula 11) in the main paper—it demonstrates that maximizing $J_{anytime}$ also improves performance on standard reasoning tasks. If formulas 12 is causing confusion, we can simply remove them without impacting the main logic of the paper.\n\n[1] Hong, Joey, Anca Dragan, and Sergey Levine. \"Q-sft: Q-learning for language models via supervised fine-tuning.\" arXiv preprint arXiv:2411.05193 (2024).\n\n\n> Limitation of baseline comparison: lack of comparison with classic RL algorithms such as PPO/REINFORCE\n\nThe main purpose of this paper is to show anytime reasoning framework is superior to standard reasoning. We argue that the choice of RL algorithm should be orthogonal to our main experiments, so a fair comparison should be: GRPO (under standard reasoning) vs. GRPO (under anytime reasoning), or PPO (under standard reasoning) vs. PPO (under anytime reasoning).\n\nAs PPO with a critic model is known to be noisy and requires extra resources, we just choose GRPO, which is more popular and widely adopted as a strong baseline in community. Due to the compute constraints and limited human efforts, we cannot afford two RL algorithms in this paper. We leave the exploration of other RL algorithms in the future work.\n\nCompared to GRPO, REINFORCE is a relatively weak baseline due to its high variance.\n\n\n> Insufficient domain generalization: only validates mathematical reasoning (algebra/geometry), does not cover scientific reasoning/decision making\n\nWe follow many prior work, including DR.GRPO[2], DeepScaleR[3], MRT[4], to validate the results on five commonly used benchmark. Could you please specify which datasts for scientific reasoning/decision making? We will consider to evaluate on them once compute resources are available.\n\n[2] Liu, Zichen, et al. \"Understanding r1-zero-like training: A critical perspective.\" arXiv preprint arXiv:2503.20783 (2025).\n\n[3] Michael Luo, et al. \"DeepScaleR: Surpassing O1-Preview with a 1.5B Model by Scaling RL\"\n\n[4] Qu, Yuxiao, et al. \"Optimizing test-time compute via meta reinforcement fine-tuning.\" arXiv preprint arXiv:2503.07572 (2025).\n\n> Does the gradient derivation of formula 6 imply a KL constraint? If V(x,z_{<t}) is removed, will the strategy collapse?\n\nNo, formula 6 is just the common policy gradient in RL. KL constraint is not implied.\n\nIf $V(x,z_{<t})$ is removed, formula 6 just fallbacks to REINFORCE. It is still a valid RL algorithm, but suffers from high gradient variance.\n\nIn this paper, we do not assume whether KL constraint should be applied. It's a free choice up to the use cases. In our experiments, we remove the KL term as in many other prior work."}]

Author rebuttal:

Meta-review: This paper presents an approach to optimize anytime performance of LLM reasoning. Reviewers generally like the paper, though I personally feel that the claims of "principled RL" are overblown. I believe that the direction of the paper is correct, but the comparisons are not quite extensive. We are accepting the paper conditioned making the paper on better comparisons in the final version of the paper.
Decision: Accept (poster)