Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling
Authors: Xinglin Wang
Yiwei Li
Shaoxiong Feng
Peiwen Yuan
Yueqi Zhang
Jiayi Shi
Chuyi Tan
Boyuan Pan
Yao Hu
Kan Li
Venue: NeurIPS 2025 poster ()
Keywords: Test-Time Scaling
Resource Allocation
Large Language Model
Primary area: deep_learning
TL;DR: We propose DORA, a provably optimal resource allocation strategy for efficient test-time scaling.

Abstract: Test-Time Scaling (TTS) improves the performance of Large Language Models (LLMs) by using additional inference-time computation to explore multiple reasoning paths through search. Yet how to allocate a fixed rollout budget most effectively during search remains underexplored, often resulting in inefficient use of compute at test time. To bridge this gap, we formulate test-time search as a resource allocation problem and derive the optimal allocation strategy that maximizes the probability of obtaining a correct solution under a fixed rollout budget. Within this formulation, we reveal a core limitation of existing search methods: solution-level allocation tends to favor reasoning directions with more candidates, leading to theoretically suboptimal and inefficient use of compute. To address this, we propose Direction-Oriented Resource Allocation (DORA), a provably optimal method that mitigates this bias by decoupling direction quality from candidate count and allocating resources at the direction level. To demonstrate DORA’s effectiveness, we conduct extensive experiments on challenging mathematical reasoning benchmarks including MATH500, AIME2024, and AIME2025. The empirical results show that DORA consistently outperforms strong baselines with comparable computational cost, achieving state-of-the-art accuracy.  We hope our findings contribute to a broader understanding of optimal TTS for LLMs.

Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling
Xinglin Wang', Yiwei Li', Shaoxiong Feng", Peiwen Yuan', Yueqi Zhang', Jiayi Shi', Chuyi Tan', Boyuan Pan?, Yao Hu', Kan Li
School of Computer Science, Beijing Institute of Technology
2 Xiaohongshu Inc
(wangxinglin, liyiwei, Leyiewei,piieenyuan, pewwenyuan, wwwaayg,ssiijiii... tanchuyi, ($haoxiongfengg22333e) yemmail. {panboyuan, xiahou)@kiiaooongshuu
fanchuyi,Likann@bit www.anaabitt.....
edu.
Abstract
Test-Time Scaling (TTS) improves the performance of Large Language Models (LLMs) by using additional inference-time computation to explore multiple reason- ing paths through search. Yet how allocate fixed rollout budget most effectively during search remains underexplored, often resulting in inefficient use of compute at test time. To bridge this gap, we formulate test-time search as a resource al- location problem and derive the optimal allocation strategy that maximizes the probability of obtaining correct solution under fixed rollout budget. Within this formulation, we reveal a core limitation of existing search methods: solution-level allocation tends to favor reasoning directions with more candidates, leading to the- oretically suboptimal and inefficient use of compute. To address this, we propose Direction Oriiented Resource Allocation (DORA), provably optimal method that mitigates this bias by decoupling direction quality from candidate count and allo- cating resources at the direction level. To demonstrate DORA's effectiveness, we conduct extensive experiments on challenging mathematical reasoning benchmarks including MATH500, AIME2024, and AIME2025. The empirical results show that DORA consistently outperforms strong baselines with comparable computational cost, achieving slate-of-the-at accuracy. We hope our findings contribute to a broader understanding of optimal TTS for LLMs
Introduction
As the challenges of scaling up computation and data resources for pretraining continue to grow, scaling test-tine cest-time computation has emerged critical paradigm for enhancing model performance (Brown et al.) 2024; Snell et al.) 2024: Wu et al. 2025a). By allocating additional computation at inference time, Test- Time Scaling (TTS) improves the performance of LLMs complex tasks such as mathematical reasoning by enabling deeper exploration of possible solutions (Qwen Team 2024 Kimi Team al. 2025 DeepSeek-Al et al., 2025). One prominent approach scaling test test-time computation through search, where diverse candidate solutions are proposed and filtered using a Process Reward Model (PRM) to guide the procedure (Chen et al. 2024b] Snell et al., 2024 Beeching et al. 2024. Wu et al., 2025a Liu et al. 2025). By pruning low-quality paths early and focusing computation more promising ones, these strategies help steer the search process toward trajectories that are more likely to yield correct answers (Setlur et al., 2025b).
While these strategies yield promising performance gains, the question of how to optimally allocate a fixed rollout budget across competing candidate trajectories remains underexplored. practice,
Corresponding author.
OOu code and data have been released on htthtpp://ggthuu...c///aaangggnp
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Temperature Sampling
Bearn Search
DVTS
REBASE
Question
Question
Question
hoams
Question
Question
Select Quality Sieps
Saleet Heat Quiltt Stop
Sclec Best Quality Step
Allocate Besed Distribttion
Bramn
Select Top I-M Quality Steps
Select Hest Quality Step
Allucaic Remourze Boncal Distabution
Quality Step
9:15
Voting Metied
Vosing Method
Vating Michoa
Vosing Method
Answer
Answer
Answer
Accepted Path
Rejected Poth
-Step with final
Middle step
Quality Scored by
Figure Comparison of different parallel Test-Time search strategies.
existing strategies rely human-designed heuristics (Figure 1 preserving certain number of high- quality candidates (Beam Search) (Snell et al.] 2024), promoting diversity (DVTS) (Beeching et al.) 2024). or balaneing exploration and exploitation (REBASE) (Wu et al. 2025a). While these intuitions offer practical value, they lack a principled foundation and do not provide guarantees of optimality, such maximizing the probability of obtaining a correct solution. As result, rollout budgets may be allocated inefficiently, limiting the effectiveness of test-time computation.
To bridge this gap, we formulate test-time search as resource allocation problem, where the goal is to maximize the probability of obtaining a correct solution under fixed rollout budget (Section 3.1). Based on this formulation, we derive the theoretical form of the optimal allocation strategy and revisit existing search methods through a unified lens. We show that, under the assumption that candidate solutions independent, several widely used strategies approximate the optimal allocation corresponding to different assumptions about the reliability of the reward estimates. However, this independence assumption does hold in practice, many candidates share the same underlying reasoning direction (Bi et al. 2024 Hooper et al.) 2025). Our theoretical analysis further shows that solution-level allocation is suboptimal: conflates direction quality with candidate count, biasing the allocation toward overrepresented directions and leading to inefficient use of test-time compute (Section 3.2)
To address this issue, we propose Direction-Oriented Resource Allocation (DORA), a provably optimal method that corrects for this allocating bias by decoupling direction quality from candi- date count and allocating resources at the direction level. To validate the effectiveness of DORA, A, we evaluate it on the challenging mathematical benchmarks MATH500 (Hendrycks et al., (02I). AIME2024 (AI-MO) 2024), and AIME2025 across a broad range of rollout budgets and policy models. The empirical results show that DORA consistently outperforms strong baseline strategies under comparable computational budgets, highlighting its ability to improve the effectiveness of each rollout and enhance the overall efficiency of TTS.
2 Setup & Preliminaries
2.1 Problem Formulation
We formulate the parallel search process under unified framework, defined by the tuple
(T,, O,O, where (a r) is policy model that generates an action a (reasoning step) given a partial solution 7 = (I, a1...., (z), where x denotes the input problem; Q [0, 1 is the Process Reward Model (PRM), which scores the quality of a partial or complete solution; O: : R -> N
is the resource allocation strategy, dynamically assigning computational budget based solution

---

scores; V is the voting method that aggregates final answers from completed solutions to select the most likely correct final answer (c.g., via majority voting, best-of-N, or weighted best-of-N); and N is the total rollout budget of parallel explorations.
The parallel search process be summarized Algorithm [ Specifically, the process iteratively expands a set of partial solutions using the policy х, collects complete solutions, and redistributes the rollout budget via the allocation strategy O based on intermediate rewards from Q. Once sufficient complete solutions are gathered, the final answer is selected using the voting method V.
2.2 Parallel Search Method
We consider four parallel TTS methods which are popularly used in practice: Temperature Sampling (Brown et al. 2024), Beam Search (Snell al. 2024), Diverse Verifier Tree Search (DVTS) (Beeching ct al. 2024), and Reward Balanced Search (REBASE) (Wu et al. 2025a). As pointed out by |Snell do not include it or other methods involving lookahead operations, such as Monte Carlo Tree Search (MCTS).
al. 2024). lookahead search is inefficient due sequential sampling,
Based on the unified framework above, we now analyze these strategies from the perspective of resource allocation. While sharing the same overall structure, they differ solely in their choice of allocation function OR),, which determines how the total rollout budget N is distributed across candidate solutions based on their PRM scores. We denote the number of rollouts assigned to the i-th candidate тy ((R);, where O is the allocation function and R .R....., R& is the vector of PRM scores.
Temperature Sampling. This method performs sampling purely from the policy model, without using reward information for rollout allocation. All candidates are treated equally, and each receives rollout. External reward signals may still be used at the final answer selection stage, e.g., through best-of-N or weighted best-of-N voting.
O Temp (R);
Beam Search. Beam Search selects the top K = N/M candidates based on their PRM scores, where M is the number of rollouts assigned per candidate (i.e., the beam width). Only the top-K' receive any rollout allocation, while the rest are discarded:
{M 0,
if E Top-K( otherwise.
Oeamm (R); =
(2)
To encourage exploration across diverse solution branches, DVTS partitions the A: candidates into K = N/M disjoint groups of size M, corresponding to independent subtrees. Within each group, it performs local Beam Search by selecting the candidate with the highest PRM score and assigning it M rollouts. Only one candidate per group receives any resource, and groups do not share information:
DVTS.
ODVIS {0r
M,
if = arg max Rg. otherwise,
(0,
(3)
where G(i) denotes the group containing candidate
REBASE. Instead of selecting fixed number of candidates, REBASE distributes the total rollout budget more smoothly based on the relative quality of each candidate to balance exploitation and exploration. It applies a softmax over the PRM scores R, to compute allocation weights, and assigns rollouts proportionally:
RR//Ts
OREBASE (R); = round (N -ww,, where w. Σ, R
(4)
where T3 is temperature parameter controlling the sharpness of the allocation.
3

---

3 Optimal Parallel Search for Test-Time Scaling
While previous parallel search methods enable efficient TTS by exploring multiple reasoning paths simultaneously. their effectiveness critically depends on how the fixed compute budget (i.e., number of rollouts) is allocated across candidate solutions. We focus on the following question:
Given a fixed rollout budget, how should one allocate resources across candidate reasoning paths maximize performance (i.e., the success rate of achieving a correct solution)?
We are the first to formulate this problem and study the associated parallel search strategies, setting our work apart from previous parallel search studies (Wu et al. 2025a Beeching et al. 2024 Jiang al., (2024). To address this, we introduce Bayesian probabilistic model of solution correctness, and derive an allocation strategy that maximizes expected success under rollout budget constraint.
3.1 Theoretical Formulation of Optimal Resource Allocation
We aim to allocate a fixed rollout budget N across i candidate reasoning paths to maximize the probability of solving the problem correctly, i.e., obtaining at least one successful solution. Let P: E 00, 1] denote the (unknown) success probability of the i-th candidate T; when sampled once.
Assumption 1. The success events of different candidate solutions are independent.
Under Assumption D the probability of obtaining at least one success under an allocation vector B (B:) given by:
k P(success) = - II (1 -1-P))) i=1
(5)
Since the true values of pj are unknown, we adopt a Bayesian modeling approach to capture the uncertainty in their estimation. In practice, p; is often approximated using the Process Reward Model
(PRM) score R2 (T):) (Wang et al. 2024a Luo et al., 2024 Wang et al. 2024b Setlur et al. 2025a Lee et al. 2025). which serves proxy for the probability of correcmess. However, these estimates are subject to considerable noise due to imperfections in the policy model, variations in decoding temperature, and inherent sampling randomness. To model this uncertainty explicitly, we treat each p; latent variable and place a Beta prior over it. Specifically, we normalize the PRM score into w; E (0, 1), and define:
p; (eta(ww; x(1 w;)).
where 6 > 0 controls the concentration of the prior around its mean. Larger values of correspond to higher confidence in the PRM estimate w/s while smaller values encode greater uncertainty (see Appendix C for more details).
Our goal is to maximize the probability of obtaining at least one successful solution. Under the Bayesian model, this is equivalent minimizing the expected joint failure:
k
II (1-p;) Σ B.=N
min
E
This defines convex optimization problem over the rollout allocation vector B = (Bi) By applying the Broish-Kuhn-Tiee (KKT) conditions, we characterize the limiting behavior of the optimal allocation (see Appendix B. for details of proof):
Proposition 1 (Limiting Behavior of Optimal Allocation). Let O" denote the optimal rollout
allocation for candidate i, where w (w } are the normalized PRM scores. Then:
When the optimal allocation assigns one rollout to each of the top-min(k: N)
candidates with highest w; scores:
[1, ifi E Top- min N) of w,
Or(w): = 0, otherwise,
with the remaining N min(k, N) rollouts arbitrarily assigned.

---

When k - oc, the optimal allocation converges to deterministic allocation that assigns scoring candidate:
all rollouts to the highest highest-scoring
Orww); = -NN, [N, if = arg maxj Wij
10, otherwise.
When is fixed and finite, the optimal allocation approximately followw shifted linear rule: O (*w), (N ks) w0 K.
Proposition T shows that the optimal allocation strategy evolves continuously with the confidence parameter 6. When R - oc, the Beta prior becomes highly concentrated around the PRM estimate w;, reflecting strong confidence in its accuracy. In this case, the optimal solution assigns the entire rollout budget to the top-ranked candidate, effectively recovering Beam Search with beam width 2 and fully exploiting the highest-scoring path.
M = N (Equation
Conversely, when x - O, the Beta prior becomes maximally uncertain, collapsing to a Bernoulli mixture where each candidate has a binary chance of being correct or incorrect, with prior weight wy In this setting, relying heavily on any single PRM estimate becomes risky, as the scores provide no meaningful guidance. To mitigate this risk, the optimal strategy spreads the rollout budget across multiple candidates in proportion to their prior likelihoods. This reduces to sampling top candidates according to multinomial distribution over Wi, a behavior closely aligned with temperature sampling used stochastic decoding.
When x is fixed and finite, the optimal allocation takes smoothed, uncertainty- aware form that interpolates between the two extremes above. Specifically, the rollout budget is approximately distributed according to shifted linear rule (Proposition D. which closely matches the REBASE strategy (Equation 4 In this regime, the PRM scores are treated as informative but noisy, and the allocation strategy balances exploration and exploitation accordingly.
In practice, due to sampling noise and imperfections in the policy model, PRM scores carry consider- able uncertainty. Consistent with this observation, we find that REBASE, which allocates rollouts in proportion to PRM scores, outperforms alternative strategies across a wide range of tasks (see 3.. This supports the relevance of the k + O setting, which we adopt as the default throughout the paper. Accordingly, we treat REBASE as the baseline solution- level allocation strategy in all subsequent analysis.
3.2 Suboptimality of Solution-Level Allocation
While REBASE is optimal under the assumption of candidate independence (Assumption D.. this condition often does not hold in practice. In particular, many candidate solutions share the same underlying reasoning direction (Bi et al.. 2024 Hooper al., 2025), forming clusters of highly correlated outputs. The solution-level nature of REBASE leads to skewed allocation when candidate counts are imbalanced across reasoning directions.
To formalize this issue, we group candidate solutions into reasoning directions. Let direction j contain k, candidates, all sharing the same PRM score Ry, and let Ej denote the index set of these candidates.
Under REBASE, rollout allocation is performed at the solution level, which implicitly induces direction-level allocation according to Eq.
R N.
kyeR:
B pisouution)
Σ N KE
(8)
Ei Diakee ki
In contrast, the optimal allocation strategy would treat each reasoning direction as a single unit and assign rollouts in proportion to the softmax over direction-level scores:
B (ddircctoon)
Σ Ri
By comparing the induced solution- level allocation Eq. 3 with the optimal direction- allocation
in Eq. 9 we derive the following proposition (see Appendix B.2 for details of proof):
5

---

Proposition 2 (Suboptimality of Solution-Lewe Allocation). When Assumption 7 does not hold, the solution-level allocation 3 B/jabutionn is suboptimal: it does not match the optimal direction-level allocation B Bldirection) unless all directions contain the same number of candidate solutions. i.e., kg = for all j-
This result reveals a fundamental limitation solution-level allocation: it implicitly favors reasoning directions with more candidate solutions (Figure 2) This bias results in inefficient use of the rollout budget, motivating our proposed method: Dbrection-Orientee Resource Allocation (DORA).
unien belonge Divectio A
Soludio Direction
Quaiitty SCRPP
Bescuroe
Ab 23iinc 2 oiuuals 4...
Direstion recelies more solurions
Solution-Level Resource Allocation
FRM
We lnoce that
Analyca
equal qualtty
Solutions
Quality score
Ao 2 times 2 equati 4
PRM
Direction Oriented Resource Allocation
Wi Inow that 2 2 4
Aratyce problem.
0.95
Disctions A and is equal quility recatve bakinsed allcation
SoteMt
0.35
Medel
3D L0
03
0.32
1.00
Figure 2: Comparison between Solution-Level Resource Allocation and proposed Direction-Oriented
Resource Allocation (DORA).
3.3 Direction-Oriented Resource Allocation (DORA)
To address the bias introduced by solution-level allocation, propose DORA, method that adjusts rollout allocation by identifying and correcting for structural redundancy among candidate solutions. As illustrated in Figure 2 DORA incorporates semantic structure into the allocation process by softly clustering solutions into shared reasoning directions and assigning rollouts proportionally at the direction level, rather than treating each solution independently.
Given set of candidate solutions ( : } DORA first estimates which solutions share reasoning structure by computing semantic embeddings e; E Rdd via a pretrained embedding model. These embeddings are used to construct a cosine similarity matrix S E R R
e e,
Sy
(10)
|elll ||el
To avoid hard clustering and retain flexibility, interpret the similarity between candidates soft assignment over directions. Specifically, we apply a row-wise softmax over S with temperature T., yielding an affinity matrix P B
Sy
Po E Sg.T."
(11)
The diagonal entry 7 = Pax then measures the semantic uniqueness solution T; serving as proxy for the inverse size of the solution's underlying direction.
Following the REBASE formulation in Eq, we compute normalized quality weights w; from PRM scores R² (T..) using a softmax with temperature Tí.

---

To incorporate semantic structure, we reweight each wa by its uniqueness:
Wi
(12)
j= W 7
This downweights redundant solutions and redistributes resourees toward distinct reasoning directions.
Finally, rollouts allocated proportionally:
B, round w!).
(13)
DORA balances rollouts across semantically distinct reasoning directions, mitigating the redundancy bias of solution-level methods like REBASE. As summarized in Theorem [ DORA yields the optimal direction-leve allocation under mild assumptions (See Appendix for the full derivation).
Theorem 1 (Optimality of DORA). Assume candidate solutions are grouped into 9 reasoning directions, where direction j consists of candidates indexed by E5. and all candidates in E share the same PRM score Rj. Then DORA recovers the optimal direction- rollout allocation specified in
Eq. 9
Experiments
4.1
Experimental Setup
We use Frren.55MMtthPPRM. (Zhang et al. (025)) as our Process Reward Model (PRM) due to its superior reward estimation performance (Zheng et al. 2024; Song et al. (025). For the policy models, (Al, 2024). , and ( (Yang et al.) 2024), covering range of model scales and architectures. Considering that existing open-source PRMs are primarily trained on mathematical tasks, we focus our evaluation on three challenging math reasoning benchmarks: MATH500, AIME2024, and AIME2025. To provide more comprehensive assessment of reasoning performance, we further include four additional math reasoning benchmarks: HMMT24, HMMT25, AMC23, and AMC24, which feature diverse question formats and difficulty distributions. We evaluate models under rollout budgets of 16, 32, 64, 128, and 256 on the main benchmarks. Following Hochlehnert et al. (2025), repeat all experiments five times on MATH500 and ten times on AIM42022 and AIME2025, reporting the average performance across all runs reduce the impact of randomness and improve the reliability of conclusions. For reward assignment during rollouts, we use the final PRM score at each step as the reward for that step. The final answer is selected using weighted majority voting, where each trajectory weighted by its final PRM score. We use these aggregation strategies since they have been shown to outperform other methods of aggregating trajectories determine the final response (Beeching et 2024). See Appendix E. for experimental hyperparameters.
we include Llama-3.2-11 2-11B-Instrue L.ama-3.2-3B-Innstt
4.2 Main Results
DORA is the most effective parallel search method. As shown in Figure 3 (a) and Table I DORA consistently achieves the highest accuracy across all policy models on MATH500, AIME2024, AIME2025, and four additional math reasoning datasets (HMMT24, HMMT25, AMC23, and AMC24). This consistent superiority demonstrates DORA's advantage to make more efficient use of limited test-time compute compared baseline strategies. To better understand this advantage, further analyze the pass rate (the number of correct solutions among all sampled rollouts). As shown in Figure 3 (b). DORA consistently reaches more correct solutions than other baselines, highlighting its effectiveness in exploring a broader set of high-quality reasoning paths. Notably, the performance gap between DORA and REBASE widens the rollout budget increases. We hypothesize that this is due to growing redundancy in sampled solutions: with more rollouts, a larger proportion of trajectories tend converge to similar final solutions. making REBASE's colution-oriented allocation increasingly prone to overestimating certain reasoning directions. In contrast, DORA mitigates this issue by allocating rollouts at the direction level, allowing for more accurate resource allocation.
4.3 Analysis
DORA is compute-optimal. Considering that DORA introduces an additional semantic similarity step via embedding model, we examine whether the associated computational overhead is justified
7

---

"erpesders Sansing
DOMA
Xepertur
BVTT
RESASE
Rourery aerrsee
70
50
AOURRA APECION
23-
255
of APREATO
16
266
24
120
104
10
230
24
12
21
(8)
Figure 3: Accuracy and Pass rate comparison under various rollout budgets on MATH500, AIME2024, and AIME2025.
Table 1:
Performance comparison broader math reasoning benchmarks. We set rollout budget as 64, and all results are averaged over five runs.
Policy Model
Method
HMMT24
HMMT25
AMC23
AMC24
Temperature Sampling
0.0
0.0
28.0
13.3
Beam Search
2.0
0.0
41.5
15.5
LLaMA-3.2-IB Instruct
DVTS
1.3
0.0
41.0
18.0
REBASE
2.0
45.0
20.0
DORA
3.3
0.0
45.0
20.0
Temperature Sampling
0.7
0.0
48.5
21.7
Beam Search
2.0
0.7
47.5
25.3
LLaMA-3.2-3B-Imss
DVTS
2.0
REBASE
4.7
0.0
59.0
27.5
DORA
6.7
2.0
59.0
31.1
Temperature Sampling
4.0
0.0
42,0
16.4
Beam Search
4.7
53.0
Qwen2.5-1.5B-Instiee Instructt
DVTS
4.7
2.0
51.5
24.9
REBASE
5.3
2.7
54.0
32,0
DORA
6.7
4.0
55.0
34.2
by the performance gains. To this end, we follow Snell al. (2024). comparing the total FLOPs and inference latency of each method, accounting for the computational cost of the policy model, PRM, and embedding model. Table reports both metrics alongside each method's accuracy. The results demonstrate that DORA is substantially more efficient than all baselines. Specifically, compared to the strongest baseline, REBASE at 256 rollouts, DORA achieves higher accuracy using only 64 rollouts, with 3.5x reduction in total FLOPs and 4x speedup in inference latency. These findings suggest that DORA achieves stronger performance with substantially less compute, demonstrating its effectiveness as the most efficient test-time search method.
DORA enhances search guidance through semantic clustering. To better understand the effect of DORA's semantic grouping mechanism, we conducted an additional analysis focusing on how well each method improves the intermediate success rate along the reasoning trajectory. Specifically, after each method allocates K reasoning steps, we remove the search algorithm and resume temperature sampling based on the intermediate solutions obtained thus far. We then measure the pass rate of these partial trajectories to estimate the success rate step K. This reflects the method's ability

---

Table 2: Comparison of FLOPs and inference latency (S) of different methods on MATH500 and
AIME24 using LLaMA-3.2-IB-Im-se three runs. The best performance for each metric is highlighted in bold. Temperature Sampling is
All results are reported as mean (standard deviation) over
excluded due to its significantly lower accuracy.
Dataset
Method
Rollout
FLOPS
Laiency
Accuracy
Policy Model
PRM
Embedding Model
Total
Seurch
10"
10
2.86(0.03) x 10
345(7)
63.610.8)
MATHS00
REBASE
DVTS
256
256
3.88
3.79
10
1044
2.05 x 10
2.72 x 10th
0
3.03(0.03) x 10
3.11(0.03) x 10th
490(10)
253(8)
62.0(0.9)
67 67.4(0.8)
DORA
64
8.45
10
5,92 10
2.16 x 10
8.92(0.05) x00
124(8)
68.7(0.8)
Beam Seurch
256
6.83 x 10"4
4,99 x 10'6
0
5.67(0.17) x 16's
816(16)
11,3(28)
AIME24
REBASE
DVTS
256
256
6.61
10
10
5.01
10th
10th
3.90(0005) x 10th
5.67(0.05) x 10th
978(14)
734(9)
14.7(2.3)
(1.6(44)
DORA
4.51 x 10'4
9.86
10
2.82 x 20 1.72(0.19) x 10
240(10)
14.7(2.3)
Table 3: Intermediate success rate (%) along the reasoning trajectory on MATH500 with N=64
rollouts, using I. LLMM-3.2-1B-Innsmmue and Qwen2.5-Math-PPMM-7 All results are averaged over
runs.
Step
0
10
15
Beam Search
27.7
39.3
49.6
54.2
55.8
56.8
57.3
57.5
57.5
DVTS
27.7
36.5
40.8
41.7
41.9
41.9
41.9
41.9
42.1
REBASE
27.7
39.5
51.2
54.5
56.5
57.1
58.0
58.3
58.3
DORA
27.7
40.2
51.6
55.6
57.4
58.2
59.0
59,5
59.6
to guide the policy model toward more promising reasoning directions early on. As shown in Table DORA consistently achieves the highest pass rates across intermediate steps compared to all baselines. Notably, Step corresponds to the Temperature Sampling baseline (i.e., without any search intervention). Comparing this with the improvements achieved by REBASE and DORA highlights the value of clustering: while both methods significantly outperform the baseline, DORA consistently maintains lead, suggesting that its semantic clustering mechanism not only reduces redundancy but also enhances the effectiveness search guidance. We will include this result and analysis in the revised version.
5 Related Work
LLM Test-Time Scaling. Scaling LLM test-time compute is an effective way to improve per-
formance (OpenAl 2024). Prior work has explored various strategies, including sampling-based methods with majority voting (Wang et al. (203)) and search-based techniques (Xie et al. 2023
Khanov et al., 2024, Wan et al. 2024). More recently, search algorithms such as breadth- first and depth-first search ( Yao et al. 2023), and Monte Carlo Tree Search (MCTS) (Ma et al. 2023 Li
ctt al., 2022 Liu et al. 2023 Choi et al., 2023) have been applied to enhance reasoning. W While these methods show promise, many rely multi-step lookahead operations that are computationally expensive and limit practical scalability (Snell et al. (022).. To improve efficiency, several studies
have proposed parallel search strategies (Snell et al. 2024 Beeching et al.) 2024 Wu al., 2025a).
Some complementary directions consider branch-and--rruuee strategies or dynamic decomposition at
inference time (Qiu al. 2024 Light et al. 2025; Li al.) 2024 Wang al. 2025). However, how to allocate a fixed rollout budget most effectively during search remains underexplored.
Process Reward Models. Process reward models (PRMs) have emerged as a powerful tool for improving the reasoning and problem-solving capabilities of large language models. By assigning rewards to intermediate steps, PRMs enable finer-grained evaluation and more effective guidance for multi-step reasoning. They have been shown effective in selecting low-error reasoning traces and providing reward signals for reinforcement-stylle optimization (Uesato et al.) [0222] Polu and Sutskever 2020; Gudibande et al. (023). With their rapid development, benchmarks such as ProcessBench (Zheng et al. 2024) and PRMBench (Song et al., (025) have been introduced to provide comprehensive evaluation protocols. Zhang et al. (2025) further offer practical guidelines for training and deploying PRMs, releasing some of the strongest open-source PRMs to date, particularly for mathematical reasoning.

---

Mathematical Reasoning with LLMs. Recent advances have significantly improved LLMs' performance on mathematical tasks, driven by both training -ime and test-time techniques. Training- time methods include large-scale pretraining (OpenAl, 2023; Azerbayev et al. 2024 Shao et al. 2024), supervised fine-tuning (Luo al. [023 lang et al. 2024). and self-improvement via self- generated solutions (Zelikman et al.) 2022; Gulcehre et al. [023] [Setlur et al., 2024). Test-time approaches leverage CoT prompting (Wei et al. [022] Zhao et al. 2025), external tools (Gao et al., 2023 Chen et al. 2023), and self-verification (Weng et al. 2023) enhance reasoning without changing model weights.
6 Conclusions
In this work, we formulate test-time search as resource allocation problem and derive its optimal solution under Bayesian framework. Our theoretical analysis offers unified perspective that explains existing search methods as approximations under varying reward confidence. Furthermore, we find that solution-level allocation favors directions with more candidates and results in suboptimal use test-time compute. To address this, we propose DORA, a direction-oriented. allocation strategy that provably achieves optimality. Extensive experiments three mathematical reasoning benchmarks demonstrate that DORA consistently improves performance while reducing compute cost. It achieves 3.5 fewer FLOPs and 4x lower latency compared to the strongest baseline REBASE. These results highlight DORA's ability to enhance both the effectiveness and efficiency of test-time inference.
Limitations. While our study focuses on scenarios where a process reward model (PRM) is available to evaluate partial trajectories, the underlying framework is not inherently tied to this specific signal. In principle, DORA can incorporate alternative forms of intermediate feedback, such as model confidence or likelihood-basee heuristies, extending its applicability beyond PRM-supervised domains. Another limitation is that our theoretical analysis assumes a low-confidence setting, which may not fully capture the dynamics of confidence accumulation during multi-step reasoning. Adapting the allocation strategy to account for increasing confidence over time presents a promising direction for future work.
Acknowledgements
This work is supported by Beijing Natural Science Foundation (No.4222037, L181010,,
References
Meta AI. 2024. Llama 3.2: Multilingual instruction-tunel language models. httts:://uggiingfacc
Co/meta- -aaaetttaalammmmaaaaaaaa 3.2- In-stnttt Accessed: 2025-05-14.
AI-MO. 2024. Aime 2024
Zhangir Azerbayev, Hailey Schoelkopf, Keiran Paster, Marco Dos Santos, Stephen Marcus McAleer, Albert Q. Jiang, Jia Deng, Stella Biderman, and Sean Welleck. 2024. [Lemma: An open language model for mathematics) In International Conference on Learning Representations (ICLR).
Edward Beeching, Lewis Tunstall, and Sasha Rush. 2024. Scaling test-time compute with open models
Zhenni Bi, Kai Han, Chuanjian Liu, Yehui Tang, and Yunhe Wang. 2024. tfrest-of-thought: Scaling test-time compute for enhancing Ilm reasoning. arXiv preprint arXiv:2412.09077.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. 2024. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.2178)
Jianly Chen, Shitao Xiao, Peitian Zhang, Kun Luo, Defu Lian, and Zheng Liu. 2024a. Bge m3- embedding: lingul, multi funtiontnntionnalittyy multi granulgranularity text embeddings through self. knowledge distillation
10

---

Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei A Zaharia, and James Y Zou. 2024b. Are more Ilm calls all you need? towards the scaling properties of compound ai systems. Advances in Neural Information Processing Systems, 37:45767-45799
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. 2023.
Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks Transactions on Machine Learning Research (TMLR).
Schyun Choi, Tianqing Fang, Zhaowei Wang, and Yangqiu Song. 2023. KCTS: Knowledge- constrained tree search decoding with token-level hallucination detection In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 14035-14053, Singapore. Association for Computational Linguistics.
DeepSeek-AI, Daya Guo, Dejian Yang. Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang, Bochao Wu, Bei Feng. Chengda Lu, Chenggang Zhao, Chengqi Deng. Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongjie Ji. Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen. Guowei Li. H. Zhang, Han Bao. Hanwei Xu, Haocheng Wang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Qu, Hui Li, Jianzhong Guo, Jiashi Li, Jiawei Wang. Jingchang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, J. L. Cai, Jiaqi Ni, Jian Liang, Jin Chen, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang, Lecong Zhang, Liang Zhao, Litong Wang. Liyue Zhang, Lei Xu, Leyi Xia, Mingchuan Zhang, Minghua Zhang, Minghui Tang, Meng Li, Miaojun Wang. Mingming Li, Ning Tian, Panpan Huang, Peng Zhang, Qiancheng Wang, Qinyu Chen, Qiushi Du, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang, R. J. Chen, R. L. Jin, Ruyi Chen, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shengfeng Ye, Shiyu Wang. Shuiping Yu, Shunfeng Zhou, Shuting Pan, S. S. Li, Shuang Zhou, Shaoqing Wu, Shengfeng Ye, Tao Yun, Tian Pei, Tianyu Sun. T. Wang, Wangding Zeng, Wanjia Zhao, Wen Liu, Wenfeng Liang, Wenjun Gao, Wenqin Yu, Wentao Zhang, W. L. Xiao. Wei An, Xiaodong Liu, Xiaohan Wang, Xiaokang Chen, Xiaotao Nie, Xin Cheng, Xin Liu, Xin Xie, Xingchao Liu, Xinyu Yang, Xinyuan Li, Xuecheng Su, Xuheng Lin, X. Q. Li, Xiangyue Jin, Xiaojin Shen, Xiaosha Chen, Xiaowen Sun, Xiaoxiang Wang. Xinnan Song, Xinyi Zhou, Xianzu Wang, Xinxia Shan. Y. K. Li, Y. Q. Wang, Y. X. Wei, Yang Zhang, Yanhong Xu. Yao Li, Yao Zhao, Yaofeng Sun, Yaohui Wang. Yi Yu, Yichao Zhang. Yifan Shi. Yiliang Xiong, Ying He. Yishi Piao, Yisong Wang, Yixuan Tan, Yiyang Ma, Yiyuan Liu, Yongqiang Guo, Yuan Ou, Yuduan Wang, Yue Gong, Yuheng Zou, Yujia He, Yunfan Xiong, Yuxiang Luo, Yuxiang You, Yuxuan Liu, Yuyang Zhou, Y. X. Zhu, Yanhong Xu, Yanping Huang, Yaohui Li, Yi Zheng, Yuchen Zhu, Yunxian Ma, Ying Tang, Yukun Zha, Yuting Yan, Z. Z. Ren, Zehui Ren, Zhangli Sha, Zhe Fu, Zhean Xu, Zhenda Xie, Zhengyan Zhang, Zhewen Hao, Zhicheng Ma, Zhigang Yan, Zhiyu Wu, Zihui Gu, Zijia Zhu, Zijun Liu, Zilin Li, Ziwei Xie, Ziyang Song, Zizheng Pan, Zhen Huang, Zhipeng Xu, Zhongyu Zhang, and Zhen Zhang. 2025. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprins arXiv:2501.12948.
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023. PAL: Program-aided language models. In International Conference on Machine Learning (ICML), volume 202, pages 10764-10799.
Arnay Gudibande, Eric Wallace, Charlie Snell, Xinyang Geng, Hao Liu, Pieter Abbeel, Sergey Levine, and Dawn Song. 2023. The false promise of imitating proprietary Ilms. arXiv preprint arXiv:2305.15717.
Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahern, Miaosen Wang, Chenjie Gu, et al. 2023. Reinforced self-training (rest) for language modeling. arXiv preprint arXiv:2308.088 08998.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. 2021. Measuring mathematical problem solving with the MATH dataset In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual.
11

---

Andreas Hochlehnert, Hardik Bhatnagar, Vishaal Udandarao, Samuel Albanie, Ameya Prabhu, and Matthias Bethge. 2025. A sober look progress in language model reasoning: Pitfalls and paths to reproducibility. arXiv preprint arXiv:2504.07000
Coleman Hooper, Sehoon Kim, Suhong Moon, Kerem Dilmen, Monishwaran Maheswaran, Nicholas Lee, Michael W Mahoney, Sophia Shao, Kurt Keutzer, and Amir Gholami. 2025. Ets: Efficient tree search for inference- scaling. arXiv preprint arXiv:2502.13577
Jinhao Jiang, Zhipeng Chen, Yingqian Min, Jie Chen, Xiaoxue Cheng, Jiapeng Wang, Yiru Tang, Haoxiang Sun, Jia Deng, Wayne Xin Zhao, al. 2024. Technical report: Enhancing Ilm reasoning with reward- reward-guided tree search. arXiv preprint 2rXivv2411..1060
Maxim Khanov, Jirayu Burapacheep, and Yixuan Li. 2024. ARGS: Alignment as reward-guided search In International Conference on Learning Representations (ICLR).
Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, et al. 2025. Kimi k1.5: Scaling reinforcement learning with llms. arXiv preprini arXiv:2501.
Jung Hyun Lee, June Yong Yang. Byeongho Heo, Dongyoon Han, Kyungsu Kim, Eunho Yang, and Kang Min Yoo. 2025. Token-supervised value models for enhancing mathematical problem-solving capabilities of large language models. In The Thirteenth International Conference on Learning Representations.
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. 2022. Making large language models better reasoners with step-aware verifier. arXiv preprint MiXiv:2006.02336.
Yiwei Li, Peiwen Yuan, Shaoxiong Feng, Boyuan Pan, Xinglin Wang, Bin Sun, Heda Wang. and Kan Li. 2024. Escape sky-high cost: strly-stopping self-consistency for multi-step reasoning. In ICLR.
Jonathan Light, Wei Cheng, Benjamin Riviere, Wu Yue, Masafumi Oyamada, Mengdi Wang, Yisong Yue, Santiago Paternain, and Haifeng Chen. 2025. Disc: Dynamic decomposition improves Ilm inference scaling. arXiv preprint arXiv:2502.16706.
Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannaneh Hajishirzi, and Asli Celikyilmaz, 2023. Don't throw away your value model! generating more preferable text with value-guided monte-carlo tree search decoding. arXiv preprint arXiv:2309.1500
Runze Liu, Junqi Gao, Jian Zhao, Kaiyan Zhang, Xiu Li, Biqing Qi, Wanli Ouyang, and Bowen Zhou. 2025. Can 1b lim surpass 405b llm? rethinking compute-optimal test-time scaling. arXiv preprint arXiv:2502.06703.
Haipeng Luo, Qingfeng Sun, Can Xu, Pu Zhao, Jianguang Lou, Chongyang Tao, Xiubo Geng, Qingwei Lin, Shifeng Chen, and Dongmei Zhang. 2023. Wizardmath: Empowering mathematical reasoning for large language models via reinforced evol-instruct. arXiv preprint arXiv:2308. 2.0553330..
Liangchen Luo, Yinxiao Liu, Rosanne Liu, Samrat Phatale, Meiqi Guo, Harsh Lara, Yunxuan Li, Lei Shu, Yun Zhu, Lei Meng, al. 2024. Improve mathematical reasoning in language models by automated process supervision. arXiv preprint arXiv:2406.0659)
Qianli Ma, Haotian Zhou, Tingkai Liu, Jianbo Yuan, Pengfei Liu, Yang You, and Hongxia Yang. 2023, Let's reward step by step: Step-level reward model the navigators for reasoning. arXiv preprint arXiv:2310. 1000:000000
Niklas Muennighoff, Nouamane Tazi, Loic Magne, and Nils Reimers. 2023. Mteb: Massive text embedding benchmark. In Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, pages 2014-2037.
OpenAl. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.0877
OpenAl. 2024. Learning to reason with Ilms
Stanislas Polu and Ilya Sutskever. 2020. Generative language modeling for automated theorem proving, arXiv preprint arXiv:2009.03393.
12

---

Jiahao Qiu, Yifu Lu, Yifan Zeng. Jiacheng Guo, Jiayi Geng, Chenhao Zhu, Xinzhe Juan, Ling Yang, Huazheng Wang, Kaixuan Huang, et al. 2024. Treebon: Enhancing inference ceffrennce-imee alignment with speculative tree-search and best-of-n sampling. arXiv preprini arXiv:2410. 16033.
Qwen Team. 2024. Qwq: Reflect deeply on the boundaries of the unknown
Amrith Setlur, Saurabh Garg, Xinyang Geng, Naman Garg, Virginia Smith, and Aviral Kumar. 2024. RI on incorrect synthetic data scales the efficiency of Ilm math reasoning by eight-fold. arXiv preprint arXiv:2406. 145322.....45.2.
Amrith Setlur, Chirag Nagpal, Adam Fisch, Xinyang Geng, Jacob Fisenstein, Rishabh Agarwal, Alekh Agarwal, Jonathan Berant, and Aviral Kumar. 2025a. Rewarding progress: Scaling automated process verifiers for Ilm reasoning. In The Thirteenth International Conference on Learning Representations.
Amrith Setlur, Nived Rajaraman, Sergey Levine, and Aviral Kumar. 2025b. Scaling test-time compute without verification or rl is suboptimal. arXiv preprint arXiv:2502.12118.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, et al. 2024. DeepSeekMath: Pushing the limits mathe- matical reasoning open language models. arXiv preprint 240.v:240..033300
Charlie Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. 2024. Scaling I1m test-time compute optimally can more effective than scaling model parameters. arXiv preprint arXiv:2408.085 230.03340..
Mingyang Song. Zhaochen Su, Xiaoye Qu Jiawei Zhou, and Yu Cheng. 2025. Prmbench: A fine-grained and challenging benchmark for process-level reward models. arXiv preprint arXiv:2501.03124.
Zhengyang Tang, Xingxing Zhang, Benyou Wang, and Furu Wei. 2024. MathScale: Scaling instruction tuning for mathematical reasoning. In International Conference Machine Learning (ICML), volume 235, pages 47885 479000
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. 2022. Solving math word problems with process-ant and outcome-based feedback. arXiv preprint 1rXiv:2211.1422
Ziyu Wan, Xidong Feng, Muning Wen, Stephen Marcus Mcaleer, Ying Wen, Weinan Zhang, and Jun Wang. 2024. AlphaZero-like tree-search can guide large language model decoding and training. In International Conference on Machine Learning (ICML), volume 235, pages 49890-49920.
Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. 2024a. Math-shepherd: Verify and reinforce Ilms step-by-step without human annotations. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume
1: Long Papers), pages 9426-9439.
Xinglin Wang, Shaoxiong Feng, Yiwei Li, Peiwen Yuan, Yueqi Zhang, Chuyi Tan, Boyuan Pan, Yao Hu, and Kan Li. 2025. Make every penny count: Difficulty-daaptie self-consistency for cost-efficient reasoning. In Findings of the Association for Computational Linguistics: NAACL 2025, pages
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-consistency improves chain of thought reasoning in language models) In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
Zihan Wang, Yunxuan Li. Yuexin Wu, Liangchen Luo, Le Hou, Hongkun Yu, and Jingbo Shang. 2024b. Multi-step problem solving through verifier: An empirical analysis on model-induced process supervision. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 7309-7319.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoe V. Le, and Denny Zhou. 2022. Chain-of-thought prompting elicits reasoning in large language models In NeurIPS.
13

---

Yixuan Weng, Minjun Zhu, Fei Xia, Bin Li, Shizhu He, Shengping Liu, Bin Sun, Kang Liu, and Jun Zhao. 2023. Large language models are better reasoners with self verifeeiiii.,oon. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 2550-2575.
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. 2025a. Inference scaling laws: An empirical analysis of compute-optimat inference for Ilm moblem-sslvingg In The Thirteenth International Conference Learning Representations.
Yuyang Wu, Yifei Wang, Tianqi Du, Stefanie Jegelka, and Yisen Wang. 2025b. When more is less:
Understanding chain-of-thought length in llms. arXiv preprint arXiv:2502.07266.
Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, James Xu Zhao, Min- Kan, Junxian He, and Michael
Xie. 2023. Self-evaluation guided beam search for reasoning. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, pages 41618 41650.
An Yang. Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang. Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Le Yu, Mei Li, Mingfeng Xue, Pei Zhang, Qin Zhu, Rui Men, Runji Lin, Tianhao Li, Tingyu Xia, Xingzhang Ren, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yu Wan, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, and Zihan Qiu. 2024. Qwen2.5 technical report. arXiv preprint 2511555
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2023. Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, pages 11809-11822.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. 2022. STaR: Bootstrapping reasoning with reasoning. In Advances in Neural Information Processing Systems (NeurIPS), volume 35,
pages
Zhenru Zhang, Chujie Zheng, Yangzhen Wu, Beichen Zhang, Runji Lin, Bowen Yu, Dayiheng Liu, Jingren Zhou, and Junyang Lin. 2025. The lessons of developing process reward models in mathematical reasoning. arXiv preprint arXiv:2501.0730/
Shangziqi Zhao, Jiahao Yuan, Guisong Yang. and Usman Nascem. 2025. Can pruning improve reasoning? revisiting long-cot compression with capability in mind for better reasoning. arXiv preprint Xrv::2500 /4582.
Chujie Zheng. Zhenru Zhang, Beichen Zhang, Runji Lin, Keming Lu, Bowen Yu, Dayiheng Liu, Jingren Zhou, and Junyang Lin. 2024. Processbench: Identifying process errors in mathematical reasoning, arXiv preprint arXiv:2412.06559.
14

---

A Details of Parallel Search Process
We present the detailed procedure of the Parallel Search Process in Algorithm
Algorithm Parallel Search Process
Require: Input problem X. parameters (r, V, step limit Tmax
Ensure: Final Answer
Ag 4- [T, x}}=1
b Initial active partial solutions
2: Tima <-
b Collected complete solutions
3: for i to Tmax - 11 do
4:
for all T, A. do
Sample action a a(- 75)
T; Tg aa end for
7:
8:
Tama Tama U (Ty E A. <EOS> E TT)
b Add completed solutions Remove completed solutions
A. A; (T, A; <EOS> ry)
if [Timal 2 then
11:
break
12:
end if
13:
Compute PRM scores: R2 + Q(T,), for each A,
14:
Compute rollout allocation: Bj + O(R),, where .RI.... R
A4+1
16:
for j = to [A:] do
17:
Add By copies of to A
18:
end for
end for
20:
return ((Tima)
> Select final answer from complete solutions
B Proof Section
B.1 Proof of Proposition
Let P; Beta(Kw,, ss1 wz)), where wy (0, is the normalized PRM score for candidate T.. Allocating B; rollouts to candidate i, the expected failure probability is
h II (1
E
p
E
(1 pt) B3 ".]
1=1
Using the identity for Beta-distributed Pt, we have:
16(1 we) +r p
E
[11
B.
Taking the negative logarithm of the success probability, the equivalent optimization problem be- comes:
B,
log 1
KW +
min N
1=1 ==
Using the identity En-1 1 = ( + n. (K). where vp is the digamma function, the objective simplifies to:
Kt.
L(B) = Σ kw, [+> + B,) - (()))
Relaxing B, to B, Rzo, we apply the method of Lagrange multipliers with constraint
Σ, B, = N. The partial derivatives yield:
aL.
= kw, (/ + B,),
0B,
15

---

where vi is the trigamma function. The KKT condition implies that at optimality:
Kws v (N + B;) X, for all i with B; > 0, and Σ B, = N.
We now analyze three asymptotic regimes of k:
Case 1: Fixed finite 0 Using the approximation (x B,) B+B.
when B, > 1, the
optimality condition becomes:
KW
KW
B
K.
B
X
Summing both sides over and enforcing E; B N, we solve for = (N + k6), yielding:
B = (N + kn)w; n.
Case 2: oc In this regime, the Beta prior becomes increasingly concentrated at p; W/- Hence,
B[(1 - B.) > (1 w and
E
(1
p.)
p.)
B.
wi
1=1
To minimize failure probability, we solve:
min Σ B.=N N
B, log(1 w:).
Since log(1 w;) < 0, this is minimized by allocating all rollouts to the candidate with the largest W/, i.c.,
(r(w)): = N, if = arg max, Wij
0, otherwise.
Case 3: + O In this regime, the Beta distribution becomes highly uncertain:
[1.
with probability wi, with probability - w0--
pr ~ Beta(ww,, s[1 wx))
(0,
x=0
Hence,
E (1)
Ws:
if B, > 0,
1,
B, = 0.
Thus, the expected failure probability becomes:
k:
II
E [1 p.)
II (1 wi),
8:B:>0
which depends only on whether a candidate receives at least one rollout, not how many. To minimize failure, must select subset S {1,..., k}} with S < N such that:
II --:) IES
is minimized. This is achieved by choosing the top-s = min(k: (k, N) candidates with the largest ws. Then the optimal allocation is:
[1. if Top-s of ws.
0' (ur):
0 otherwise,
with remaining N rollouts arbitrarily assigned.
16

---

B.2 Proof of Proposition 2
In the + regime, Proposition shows that the expected success probability maximized by the solution:
e
B, Ws: where wa Σ e
This corresponds maximizing the log-utility objective:
C
wy log Bi.
To analyze the effect of structural redundancy, we group candidate solutions into reasoning
directions. Let direction j contain k; candidates, each with identical score Ry, and index set Ey-
The optimal direction-aware allocation follows:
e.Ry
Qj Σi= Bi
B dddirection) N. Q3-
The corresponding log-utility is:
dirr) Ej log Bddircction) llog N +
Qj log Qj.
REBASE assigns each candidate i E E rollout weight:
R, 00 Σin R
kyc
so
B Bisolutioo)
Nw; N.
Σi= kie
iEE
This induces a derection-level distribution:
kije
Q = El Rie
The resulting utility is:
Cluul
Qj log B ((solution) log N + Σ
Q log Qj.
The gap in log-utility is:
log Qj KL(Q) @) 2 0.
(din)
(sso))
Σ
Qj
1=1
Equality holds if and only if Q2; Q, for all j. i.e.,
R2
k E
ky = for all j.
Σ, ei
Thus, the solution-level allocation suboptimal unless all reasoning directions contain the same number of candidate solutions.
B.3 Proof of Theorem
Assume candidate solutions are partitioned into g reasoning directions, where direction j E {1,.... contains kj candidates indexed by E,, and all candidates in E, share the same PRM score Ry.
Under REBASE, softmax is computed at the solution level:
RR
q
for E Eg.
El Ri
17

---

Aggregating across each direction yields the induced direction- distribution:
R Ri
QREBASE
q
E1=1 keeli""
EEE
To eliminate the bias from uneven candidate counts ky, DORA reweights each by the inverse of its cluster size:
i for i Eg. kj
The normalization constant becomes:
k
Σ BB,
Z
kj Ei=1 kie!!
Σ keeBi
Normalizing gives the final corrected weight:
R2
4
Final
kj Di=1 e
for i E Eg-
Aggregating over direction j, the direction-level allocation becomes:
eR
e R
Σ
9:
final
kg
kj
E1=1 li
Ei=1 tl
Qj.
E
Thus, the final allocation satisfies
Σ iEE
B, x 22,
which exactly matches the optimal direction-level allocation given in Eq
C Details of Beta Distribution
The Beta distribution is a standard choice for modeling random variables on the unit interval, and its parameters (a, 3) (sww, x(1 w:)) are interpretable: the mean is E[p:] we, and the variance is inversely related to k. Specifically:
When x is small, the distribution is diffuse and uncertain.
When x is large, the distribution is sharply peaked around we, indicating high confidence.
Figure visualizes the effect of different x values with wy fixed at 0.7.
D More Experiments
D.1 DORA provides larger gains on harder problems
Figure shows that while DORA remains the top-perforr perfoorfrrming strategy across the entire MATH500 benchmark, the size of its advantage depends sharply on difficulty. On easier Level 1-2 problems, most methods perform well given moderate rollout budgets, so the accuracy curves for all methods converge closely. On the other hand, on harder Level 3-5 problems. the gap between DORA and solution-level methods widens steadily with budget, with DORA achieving clear lead at higher rollout levels. We hypothesize that harder problems amplify DORA's strength as they typically require longer reasoning chains (Wu et al., 2025b), which allows more opportunities for rollout allocation across search steps. As the number of allocation rounds increases, principled strategy like DORA could compound its advantage by continually prioritizing promising directions and avoiding wasted computation.
18

---

20.0
Beta Prior
17.5
3
15.0
== 10
12.5
Density
10.0
7.5
5.0
2.5
0.0
0.0
0.2
0.8
1.0
Success Probability pi
Figure 4: Effect of the concentration parameter & on the Beta prior. All curves are plotted with fixed mean w, 0.7. Larger yields more concentrated prior around w;, while smaller x. reflects greater uncertainty.
Temperature Samping
Beart Search
--- DVTS
REBASE
DORA
Level
Level
Level3
Levd
Level
Lisms 3.2.38 instrct
100
90
70
45-
65
40-
35
80
60
35
80
30-
50
65
45
25
20
55
35
15
16
32
64
128
236
16
32
64
128
256
16
64
128
256
14
32
64
128
236
16
32
64
120
256
3.3 inctrnct
100
80
90
75
65
60
55
128
Owen2.5 1.58 inzzuct
200
80
63-
75
10
70
50
45
65
30
16
12
64
128
256
16
32
54
128
255
25A Number of Samples In)
16
64 120
16
32
64
120
256
16
12
61
128
258
Figure 5: Comparison of method accuracy MATH500 across different difficulty levels.
D.2 Ablation on Clustering Design
To better isolate the effect of DORA's semantic clustering mechanism, we conduct an ablation study comparing several alternative clustering strategies before finalizing the soft clustering design.
KMeans clustering. KMeans requires predefining the number of clusters K. However, the actual number of distinct reasoning directions can vary substantially across problems and reasoning steps, making a fixed K a poor approximation and often leading to suboptimal clustering performance.
Hierarchical clustering. We experiment with hierarchical clustering, which avoids setting K by merging solutions based on fixed cosine similarity threshold C. However, the optimal value of C should ideally vary with the depth and complexity of reasoning, which differ significantly across problems. This sensitivity made hierarchical clustering even less effective than KMeans our experiments.
19

---

Table 4: Ablation study of different clustering methods on MATH500 with N=64 rollouts, using M--A-,,--I--nnttrre Results are averaged over 5 runs.
Cluster Method
K=3
K=5
K=10
C=0.95
C=0.90
C=0.80
Soft (default)
Accuracy
67.6
68.0
67.8
67.0
66.6
66.0
68.7
Soft clustering (ours). Based on these findings, we adopted soft clustering approach in DORA, which avoids hard assignment boundaries and allows for more adaptive and robust semantic grouping across diverse reasoning structures.
As shown in Table the soft clustering variant achieves the best performance, outperforming all hard clustering alternatives. This demonstrates that allowing soft, overlapping group assignments enables DORA to better adapt to the variable structure of reasoning paths, improving robustness and accuracy across diverse problem types.
D.3 DORA generalizes across model scales and PRM families
As shown in Table 5 we further test DORA with a larger policy-PRM pair: LLaMA-331-8B-Instte guided by 1wwe2..--Math-PRM-2220 on MATH500 with 6 rollouts. DORA attains the highest accuracy (80.6), outperforming Beam Search (78.2), DVTS (78.4). and REBASE (79.2). We also replace the reward model with different PRM family (Skywork-PRMs gains across all policy models (Table surpassing the strongest baseline in each case. These results indicate that DORA's advantages persist when scaling to larger models and when switching across distinct reward-model families, underscoring its robustness as a reliable test-time search strategy.
and observe consistent
Table 5: Accuracy on MATH500 with a larger policy model and PRM: LLaMA-3. 10--3.1-8B... the policy and -attn..---M as the PRM (N=64 rollouts). Best results are in bold.
as
PRM
Policy Model
Temperature Sampling
Beam Search
DVTS
REBASE
DORA
Wwen2.5-Mtth-RM--22
70.5
78.2
78.4
79.2
80.6
Table 6: Accuracy on MATH500 with an alternative PRM family (Skywork-PRM-7BB at N=64 rollouts. Best results are in bold.
Method
L.aMA-3.2-1B-Innste
LLaMA-3.233B-Isstru
D.we2.55-1.B--Instie
Temperature Sampling
58.5
69.5
73.0
Beam Search
69.0
75.5
79.7
DVTS
66.2
74.2
78.9
REBASE
70.8
76.2
80.2
DORA
71.8
76.6
81.0
D.4 DORA is robust hyperparameter choices
We further study the temperature parameters T. (softmax over directions) and T, (semantic similarity) on MATH500 with N 7). Both REBASE and DORA perform well at Tù E {0.01, 0.1) but degrade at =3=1.0, where the softened distribution weakens PRM guidance and approaches unguided sampling. Importantly, DORA is stable across a wide range of T' values (0.001-1.0) indicating low sensitivity to the clustering threshold. To further investigate DORA's robustness across retriever families, we compared our default retriever (bge-m² 568M parameters) with two popular alternatives from the MTEB leaderboard (Muennighoff et al. (023) that support long inputs (2048 tokens): 45-base-4k (1M) and gte- gte-multin multilingual deliver comparable performance across all policy models, while E5 slightly worse- likely due to its smaller capacity and thus weaker clustering in high-dimensional embedding space. Together, these results show that DORA's gains are not brittle: it maintains strong accuracy under reasonable choices of temperatures and retrievers, reinforcing its practicality for real-world deployment.
(305M). As shown in Table 8 BGE and GTE
20

---

Table Sensitivity analysis of temperature hyperparameters Tu and T, on MATH500 with N=64 rollouts using LLaMA-3.2- 11--2-1B-Instie Instrucct. All results are averaged over runs.
Tb
T.
Method
0.01
0.1
1.0
0.001
0.01
0.1
1.0
REBASE
64.8
65.9
55.4
DORA
67.4
68.7
57.2
67.8
68.7
68.0
67.5
Table 8: Ablation embedding (retriever) models on MATH500 with N-64 rollouts. We compare
our default BGE-M3 to GTE-G mult-iiuliiilll---ea base and E5-base-4k Results are averaged over runs.
Policy Model
BGE
GTE
E5
LLaMA-3.2-1B Instrrcctt
68.7
68.2
66.8
a. Instructtt
77.6
77.4
Owen-2.5-11.5B-Instme
80.8
80.2
79.2
E
Implementation Details
E.1
Experimental Hyperparameters
All experiments use temperature sampling with temperature 0.8 and top_p 1.0. We set the token limit to 256 per step and 2048 tokens in total for each solution. For Beam Search and DVTS, we use beam width of 4 following Snell et al. (2024). For REBASE, we set T5, to 0.1, consistent with its original implementation. For DORA, employ the open-source BGE-M3 embedding model (Chen et al., 2024a) to compute semantic similarity between trajectories, chosen for its lightweight architecture, strong empirical performance, and ability to handle long input sequences. We set the Ti for quality scores 0.1 (matching REBASE), and the semantic similarity temperature T. to 0.01. All experiments are executed in parallel on a cluster with 32 NVIDIA A100 GPUs (40G), where each individual run is allocated to a single GPU.
E.2 Details of Prompt
Following Beeching al. (2024), employ the prompt below for LLM mathematical reasoning:
Solve the following math problem efficiently and clearly:
For simple problems (two steps fewer): Provide concise solution with minimal explanation.
For complex problems (three steps or more): Use this step- format:
## Step 1: [Concise description]
[Brief explanation and calculations]
## Step 2:
Regardless of problem complexity, always conclude with: Therefore, the final answer is: \anwed(answer).
21

---

NeurIPS Paper Checklist
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 substantiate our claims with both experimental evidence and theoretical
analysis.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in 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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations of our work in the conclusion section.
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 a separate "Limitations" section 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 well-specification, asymptotic approximations only holding locally). The authors should reflect 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 on few datasets or 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 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 to 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
We have included detailed assumptions and proof in the appendix.
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 the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to 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 supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibiliyy
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have provided detailed experimental settings in the experiments section and detailed module designs of our method.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS 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 reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a 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 or 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?
23

---

Answer: [Yes]
Justification:
We have provided the code of our work.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc)
Staili/cguuiees/ddddudiiiisssss ssioololiiiii 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 NeurIPS code and data submission guidelines (https //nips. phiips.cc/ubb... ic/i wetiiiiigdeeeoeeeeiieeeeeeeeeee
wwwissssioonyyyyooo for more details.
The authors should provide instructions on data access and preparation, including how 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. If 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).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: 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?
Answer: [Yes]
Justification:
We have provided detailed experimental settings in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For each setting, we run 5-10 times and report the average results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support 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, 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).
should be clear whether the error bar is the standard deviation the standard error of the mean.
24

---

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 enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in 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 execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have provided corresponding details in Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
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 of 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 NeurIPS Code of Ethics https:
Answer: [Yes]
Justification:
We have read the NeurIPS Code of Ethics and followed it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
25

---

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 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 or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks.
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 we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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?
Question:
Answer: [Yes]
Justification:
We have correctly cited all the assets we use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if 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 use in the package should be provided. For popular datasets, papersii thcode. com commdatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
26

---

Answer:
[NA]
Justification: No new assets released.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part 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 an 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 as details about compensation (if any)?
Answer: [NA]
Justification: Does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, 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 or Equivalent for Research with Human Subjects
Question: 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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not 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 expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "bmTev3ZOb0", "reviewer": "Reviewer_N3ut", "summary": "The paper presents a critical analysis of rollout allocation efficiency in Test-Time Scaling for Large Language Models (LLMs) focused on mathematical reasoning, leveraging Process Reward Models (PRMs). It identifies limitations in prior methods by demonstrating that the assumption of independence between rollout allocations fails in practical scenarios, leading to suboptimal performance. To address this, the authors propose a theoretical framework that incorporates embedding similarity scores to mitigate the breakdown of independence, thereby achieving optimality under the proposed conditions. The framework is rigorously evaluated on three standard mathematical reasoning benchmarks using a 7B-parameter PRM and 1 to 3B-parameter generative models, demonstrating its effectiveness in improving scalability and performance for mathematical tasks. The work contributes a novel approach to optimizing test-time scaling in LLMs through both theoretical justification and empirical validation.", "questions": "1. How much sensitive could the proposed method be towards the choice of retriever (E5/GTE instead of  BGE)?\n2. Which chat template is used for Llama models as  there seems to be an issue related to it[1]?\n3. The quality score parameter T_b is not well ablated in the REBASE paper. How much are the results in the proposed paper sensitive to this parameter?\n\n\nReferences:\n\n1. https://huggingface.co/spaces/HuggingFaceH4/blogpost-scaling-test-time-compute", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. Theoretical Justification: The method derives the sub-optimal conditions for REBASE and proposes more effective method based on an additional score from embedding similarity. The theoretical result establishes the optimality of the direction-level allocation schema proposed in the paper.\n\n2. Performance: The proposed framework achieves superior performance at lower computer cost in comparison to the baseline, for example, 3.5 times  fewer flop in MATH500, resulting in a lower latency as well.\n\n### Weaknesses\n1. The generalization of the presented results are limited. First, the  improvement is mainly visible for MATH500, but for AIME task, there is a good amount of overlap with baselines for statistical significance. Next, the range of policy models are limited as it covers only 1-3B models. Evaluating larger model classes such as 8B and 32B could further establish the significance of the proposed methods. Similarly, only single PRM is evaluated. The results for larger PRMs (72B) and other families (e.g., Skywork) could clarify the scalability of the  proposed method.\n\n2. Motivation of  some design choices are  unclear. For example, semantic similarity temperature is chosen as 0.01. It is unclear how is it tuned and the sensitivity of the results due  to this parameter.\n\n3. The proposed method introduces an additional model dependency for Test-Time Scaling which could hinder its future extension.  For example, it the retriever model is not  trained with code data, the scaling method will  face bottleneck for coding benchmarks.\n\n4. Table 1 does not include the error bars (deviation) and statistics for AIME tasks. Including these metrics could further clarify the scalability of the proposed framework.", "was_revised": true, "final_justification": "All the major concerns have been addressed:\n- More benchmarks to demonstrate generalization.\n- Ablated hyperparameters related to temperature.\n- Discussed potential practical bottlenecks.\n- The method shines irrespective of the choice of retriever.", "rebuttal": "Dear Reviewer N3ut, we sincerely appreciate you taking the time to read our manuscript and provide valuable feedback. Below are our responses to the concerns you raised, which will be incorporated into the updated version to further enhance the quality of our submission.\n\n### **W1: Regarding the Generalization of the Presented Results**\n\nWe understand your concern and agree with your suggestion that conducting experiments on larger policy and PRM models, and across different PRM families would better validate the generalizability of DORA. Regarding the AIME tasks, we note that the observed overlap with baseline performance is primarily due to the small dataset sizes of AIME24 and AIME25 (only 30 problems each), which makes the Accuracy metric more prone to high variance and less statistically stable. To enhance the statistical reliability of the results, we followed [1] and conducted 10 independent runs with different random seeds, reporting the averaged performance (see lines 214–215). To further demonstrate the generality and scalability of DORA, we conducted the following three sets of additional experiments (All results are averaged over 5 independent runs to ensure statistical stability):\u000b\n\n(1) Broader Benchmark Coverage: We incorporated four additional standard math reasoning benchmarks: HMMT24, HMMT25, AMC23, and AMC24. Under a rollout budget of N=64, the results are summarized as follows:\n\n|Policy Model|Method|HMMT24|HMMT25|AMC23|AMC24|\n|------------|------|--------|--------|--------|--------|\n|LLaMA-3.2-1B|Temperature Sampling |0.0|0.0|28.0|13.3|\n||Beam Search |2.0     |0.0     |43.0|15.5|\n||DVTS  |1.3     |0.0     |41.0    |18.0|\n||REBASE|2.0     |0.0     |43.0    |18.2 |\n||DORA  |**3.3** |0.0 |**45.0**|**20.0**|\n|LLaMA-3.2-3B|Temperature Sampling |0.7|0.0|48.5    |21.7    |\n||Beam Search  |2.0     |0.7     |55.5 |25.3    |\n||DVTS  |2.0     |0.0     |57.0    |26.2    |\n||REBASE|4.7     |0.0     |**59.0**|27.5    |\n||DORA  |**6.7** |**2.0** |**59.0**|**31.1**|\n|Qwen-2.5-1.5B|Temperature Sampling   |4.0     |0.0     |42.0    |16.4    |\n||Beam Search  |4.7     |1.3     |53.0    |31.1    |\n||DVTS  |4.7     |2.0     |51.5    |24.9    |\n||REBASE|5.3     |2.7     |54.0    |32.0    |\n||DORA  |**6.7** |**4.0** |**55.0**|**34.2**|\n\n\n(2) Larger Policy Models and PRM: We evaluated DORA with more powerful models by using Qwen2.5-Math-PRM-72B as the PRM to guide the LLaMA-3.1-8B-Instruct policy model on the MATH500 benchmark with N=64. The performance is reported below:\u000b\n\n|PRM |Policy Model|Temperature Sampling|Beam Search|DVTS|REBASE|DORA|\n|-----|-----|----|----|-----|------|-----|\n|Qwen2.5-Math-PRM-72B|LLaMA-3.1-8B|70.5|78.2|78.4|79.2|**80.6**|\n\n(3) Different PRM Families: To evaluate generalization across PRM families, we additionally tested **Skywork-PRM-7B** on the MATH500 benchmark with N=64. The results are shown below:\n\n|Method|LLaMA-3.2-1B|LLaMA-3.2-3B|Qwen-2.5-1.5B|\n|------|------------|------------|-------------|\n|Temperature Sampling|58.5|69.5|73.0|\n|Beam Search|69.0|75.5|79.7|\n|DVTS|66.2|74.2|78.9|\n|REBASE|70.8|76.2|80.2|\n|DORA|**71.8**|**76.6**|**81.0**|\n\nAbove experiments demonstrate that DORA generalizes well across a broader range of benchmarks, scales to larger policy models and PRMs, and is compatible with PRMs from different families. Specifically, the experiments with Qwen2.5-Math-PRM-72B were executed in parallel on a cluster with 100 H20 GPUs (96GB each), using 2 GPUs per run, and were completed in approximately 4 days. We sincerely thank you for this insightful suggestion and will include the results and analysis in the revised version.\n\n### **W2 & Q3: On the Design Choice of Hyperparameters $T_s$ and $T_b$**\n\nWe fully understand your concern regarding the motivation and sensitivity of certain hyperparameters. For the quality score temperature $T_b$, we default to $T_b=0.1$ to align with REBASE, ensuring a fair and consistent comparison. For the semantic similarity temperature $T_s$, which determines how close two solutions should be to be considered as belonging to the same reasoning direction, we conducted an ablation study to select a suitable value. We apologize for the oversight in not including this ablation result in the original submission. We performed a detailed sensitivity analysis of both $T_s$ and $T_b$ on the MATH500 benchmark with rollout budget N=64, using LLaMA-3.1-8B-Instruct as the policy model. All results are averaged over 5 independent runs to ensure statistical stability. The results are summarized as follows:\n\n|$T_b$   |0.01|0.1|1.0|\n|------|----|----|----|\n|REBASE|64.8|65.9|55.4|\n|DORA  |67.4|68.7|57.2|\n\n|$T_s$  |0.001|0.01|0.1|1.0|\n|-----|-----|----|----|----|\n|DORA|67.8 |68.7|68.0|67.5|\n\nThese results show that DORA is relatively robust to the choice of $T_s$. As for $T_b$, both REBASE and DORA achieve strong performance when $Tb=0.01$ or $0.1$, but exhibit a clear performance drop when $T_b=1.0$. This degradation occurs because a high temperature in the softmax weakens the guidance of the PRM. In the extreme case where $T_b \\to \\infty$, REBASE degenerates into temperature sampling without PRM guidance.  We will include these results and discussion in the later version.\n\n### **W3: About Potential Bottlenecks for Test-Time Scaling**\n\nWe understand and appreciate your concern regarding the additional model dependency introduced by Test-Time Scaling (TTS), particularly the reliance on an embedding model for retrieval. We acknowledge that if the embedding model is trained on data with limited coverage of a target domain, its ability to cluster reasoning chains in that domain could indeed be suboptimal. This is a valid concern when considering the broader applicability of TTS.\n\nHowever, recent advances in embedding model development have increasingly moved toward general text embeddings, as demonstrated in [2]. Modern retrievers such as GTE-Qwen and E5-Mistral are designed to inherit rich linguistic and domain knowledge from large pre-trained language models (e.g., Qwen2-1.5B), which cover a wide range of reasoning and generation scenarios. Based on this trend, we believe that the inclusion of an embedding model in TTS is unlikely to become a bottleneck for extending TTS to other domains, as many embedding models today possess sufficient generalization capabilities to support effective clustering across diverse tasks.\n\nRespectfully, in our view, the more significant limitation to extending TTS beyond math currently lies in the lack of high-quality, open-source PRMs for domains such as code generation. Most existing PRMs are tailored for math reasoning [3], while open-source PRMs for code tasks remain scarce. To the best of our knowledge, Skywork-PRM is among the few publicly available options, but recent work [4] has shown that it offers relatively weak step-level supervision on code-related tasks. While one alternative is to use open-source language models prompted as critic models, this introduces substantial computational overhead and time delay at test time, which undermines the efficiency advantages of TTS.\n\n\n### **W4: About Including Error Bars and Statistics for AIME on Table 1**\n\nWe sincerely thank the reviewer for this helpful suggestion. The completed results are shown below, which will be incorporated into the later version:\u000b\n\n|Dataset|Method|Rollout|FLOPS|Latency(s)|Accuracy|\n|--------|------------|-------|----------------------|----------|-----------|\n|MATH500 |Beam Search |256|2.86(0.03)×10¹⁵ |345(7) |63.6(0.8) |\n||DVTS |256|3.03(0.03)×10¹⁵ |253(8)    |62.0(0.9)  |\n||REBASE|256    |3.11(0.03)×10¹⁵ |490(10)    |67.4(0.8)  |\n||DORA|64     |8.92(0.05)×10¹⁴ |124(8)    |68.7(0.8)|\n|AIME24|Beam Search |256|5.67(0.17)×10¹⁵|816(16)         |11.3(2.8) |\n||DVTS|256    |3.99(0.05)×10¹⁵  |734(9)         |11.6(2.4)  |\n||REBASE|256    |5.67(0.05)×10¹⁵ |978(14)         |14.7(2.3) |\n||DORA|64     |1.72(0.19)×10¹⁵|240(10)         |14.7(2.3)|\n\n\n\n\n### **Q1: About sensitive of different retrievers**\n\nWe understand your concern about the potential sensitivity of DORA to different retriever models. To further investigate DORA’s robustness across retriever families, we compared our original retriever (bge-m3, 568M parameters) with two popular alternatives from the MTEB leaderboard [5] that support long inputs (≥2048 tokens): e5-base-4k (110M) and gte-multilingual-base (305M).\u000bAll experiments were conducted on MATH500 with N=64, and all other settings were kept consistent with the main experiments. All results are averaged over 5 independent runs to ensure statistical stability. The results are summarized below:\n\n|Policy Model|bge |gte|e5|\n|-----------------|-----|-----|-----|\n|LLaMA-3.2-1B |68.7 |68.2 |66.8 |\n|LLaMA-3.2-3B |77.6 |77.4 |76.8 |\n|Qwen-2.5-1.5B |80.8 |80.2 |79.2 |\n\n\nThe results show that GTE and BGE yield comparable performance, indicating that DORA is robust to retriever changes within similar capacity ranges. However, E5 exhibits certain performance degradation, which we hypothesize is due to its smaller model size and thus weaker clustering capability in high-dimensional embedding space.\nWe will include these results and analysis in the revised version to clarify DORA’s sensitivity to retriever choices.\n\n### **Q2: About chat template used for Llama models**\n\nWe confirm that the chat template used for LLaMA models in our experiments is exactly aligned with the configuration described in [6] (see Appendix D.2). In fact, our codebase is directly built upon the official open-source implementation provided by [6].\u000b\u000b\n\n[1] A sober look at progress in language model reasoning: Pitfalls and paths to reproducibility.\n\n[2] Towards General Text Embeddings with Multi-Stage Contrastive Learning.\n\n[3] PROCESSBENCH: Identifying Process Errors in Mathematical Reasoning, ACL2025.\n\n[4] CodePRM: Execution Feedback-enhanced Process Reward Model for Code Generation, ACL2025.\n\n[5] MTEB: Massive Text Embedding Benchmark, EACL2023.\n\n[6] blogpost-scaling-test-time-compute, HuggingFace."}, {"review_id": "9UZuZcN68V", "reviewer": "Reviewer_asTA", "summary": "This paper tackles the problem of efficiently allocating a fixed computational budget during test-time search with Large Language Models. The authors reframe Test-Time Scaling as a constrained resource-allocation problem, providing a novel theoretical lens through which to analyze existing search strategies. Using a Bayesian framework with a Beta prior to model uncertainty in reward estimates, they derive the form of the optimal allocation. This analysis reveals that popular methods like Beam Search and REBASE are suboptimal because they allocate resources at the individual solution level, favoring \"reasoning directions\" that are overrepresented with many similar candidates.\n\nThe paper's core contribution is Direction-Oriented Resource Allocation (DORA), which computes semantic embeddings of candidate solutions to identify redundant paths, and then re-weights the rollout allocation to separate a direction's quality from the number of candidates representing it. Extensive experiments on challenging mathematical reasoning benchmarks show that DORA consistently achieves higher accuracy than strong baselines and requires 3.5x fewer FLOPs and 4x lower latency than the next-best method for comparable performance.", "questions": "This is an excellent submission, and my questions are mainly aimed at exploring the boundaries of the claims and the method's robustness. A strong response here could easily convince me to raise my score.\n\n1. Exploring the Limits of Optimality: Your optimality proof hinges on some key assumptions. I'd be interested to hear more about what happens when they are pushed.\n(i) How does DORA's performance hold up as the variance of PRM scores within a direction increases, violating the core assumption of Theorem 1?\n(ii) What happens in the high-confidence regime $(k → \\infty)$? When the PRM is highly reliable, the best strategy is to exploit the top candidate. Does DORA gracefully recover this behavior, or could its diversity-promoting mechanism become a liability by steering compute away from a single, truly optimal path?\n\n2. Robustness to Hyperparameters: The performance seems to depend on a very specific temperature, $T_s = 0.01$. This value makes the softmax behave almost like a hard assignment. How sensitive is the method to this choice? An ablation plot showing performance as $T_s$ is varied (e.g., across {0.001, 0.01, 0.1, 1.0}) would be very helpful for understanding if the method is stable or requires careful tuning.\n\n3. The Clustering Mechanism: DORA's effectiveness relies on its soft clustering. To better understand why it works, I have two questions:\n(i) Have you considered a simpler \"hard clustering\" baseline? For example, one could run K-means on the embeddings and then allocate the budget at the cluster level. Comparing against this would clarify whether the benefit comes simply from accounting for redundancy, or if the soft-reweighting scheme is truly superior.\n(ii) Could you provide a more direct, empirical measure of how well the clustering works? For instance, measuring the success-rate correlation between pairs of solutions before and after they are grouped by DORA would be a great way to quantify how effectively it identifies and mitigates dependencies.", "limitations": "Yes, the authors do a good job of discussing limitations. I'd encourage them to also briefly touch on the following points to make the section even stronger:\n- The gap between the theoretical assumption of identical PRM scores and the practical reality.\n- The introduction of new components (embedding model, T_s) and the potential for their selection to induce new biases or require careful tuning.\n- A brief note that the empirical validation, while strong, is confined to mathematical reasoning, and generalization to other domains (e.g., code generation) remains an open and interesting question.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I found this to be a very strong paper, with its primary strengths being its principled theory, the novelty of the method, and a compelling set of experiments.\n\nThe paper’s theoretical grounding is a major strength. By moving from simple heuristics to a formal resource allocation problem, the authors offer a unified view of the test-time search landscape. This framework elegantly explains existing methods as special cases and provides a clear motivation for why they might fail. The proposed method, DORA, is a direct and clever solution to the problem identified by the theory. Using semantic similarity to compute a \"uniqueness\" score is a fresh approach that moves beyond simple diversity-promoting heuristics.\n\nMost importantly, the method seems to work very well. The empirical results are a highlight. The gains in accuracy are consistent, but the efficiency gains are what truly make the contribution stand out. A 4x speedup, as shown in Table 1, is a significant practical achievement. The analysis is thorough, covering multiple models, benchmarks, and budget sizes, which gives me confidence in the results. The paper is also exceptionally well-written and easy to follow.\n\nThe weaknesses are minor in comparison but worth noting. The \"provably optimal\" claim rests on the simplifying assumption that all solutions within a \"direction\" have identical PRM scores, a condition that won't hold perfectly in practice. The paper doesn't explore how the guarantees degrade as this assumption is relaxed. Additionally, the method's performance is now tied to new components, the embedding model and a key temperature hyperparameter ($T_s$), whose robustness and sensitivity are not explored in an ablation study. While the chosen settings work well, understanding their stability is important for real-world deployment.", "was_revised": true, "final_justification": "I am maintaining my score.", "rebuttal": "Dear Reviewer asTA, we sincerely appreciate you taking the time to read our manuscript and provide valuable feedback. Below are our responses to the concerns you raised, which will be incorporated into the updated version to further enhance the quality of our submission.\n\n### **Q1 & L1: On Exploring the Limits of Optimality**\n\n**(i) Robustness to Intra-Directional PRM Score Variance**\n\nThank you for this thoughtful question. The assumption in Theorem 1—that all solutions in a direction are perfectly correlated with identical PRM scores—is made purely to simplify the theoretical analysis.\n\nIn practice, solutions within a direction are usually partially correlated, and PRM scores can vary. Modeling this directly would make the theoretical formulation intractable. To handle this, DORA adopts a soft clustering design and retains per-candidate PRM scores $R_i$, without collapsing them at the direction level.\n\nRollout allocation is computed as (line 195-196):\n\n$$w_i' = \\frac{w_i \\cdot \\gamma_i}{\\sum_j w_j \\cdot \\gamma_j},$$\n\nwhere $w_i$ reflects quality, and $\\gamma_i$ accounts for semantic uniqueness. This enables DORA to prioritize better solutions even within noisy directions. Thus, while the theoretical assumption simplifies analysis, DORA’s implementation is robust to score variance and operates fully at the individual solution level. We will clarify this distinction in the revised version.\n\n**(ii) DORA’s Behavior in the High-Confidence Regime**\n\nThank you for the insightful question. In the theoretical high-confidence case—where the PRM is perfectly reliable (\\$\\kappa \\to \\infty\\$)—its scores exactly reflect the true success probabilities. For example, a PRM score of 0.9 means that sampling from that solution yields success with 90% probability. In this limit, the optimal strategy is indeed to allocate all rollouts to the top-scoring candidate.\n\nHowever, this regime is unrealistic in practice: computing true posterior success rates would require resampling each solution many times, which introduces significant cost and latency—contrary to the goal of test-time efficiency. Instead, PRMs in practice are noisy estimators trained on limited data, and this noise precludes direct exploitation.\n\nIn such realistic settings, REBASE is optimal when assuming candidate independence, and DORA extends this by accounting for semantic dependencies, leading to more balanced allocations. Since DORA’s design assumes PRM noise and redundancy among solutions, it is inherently incompatible with the \\$\\kappa \\to \\infty\\$ case, and thus does not recover greedy behavior in that limit.\n\nWe will clarify this in the final version. Thank you again for encouraging this discussion.\n\n### **Q2 & L2: On the Robustness to hyperparameter \\$T\\_s\\$ and Embedding Model Choices**\n\nThank you for this important question. We fully understand your concern regarding the robustness of DORA’s semantic grouping, which relies on the soft clustering temperature \\$T\\_s\\$ and the embedding model.\n\nWe first conducted an ablation study to evaluate the sensitivity of DORA to the semantic similarity temperature \\$T\\_s\\$, which determines how close two solutions should be to be considered as belonging to the same reasoning direction. Experiments were performed on MATH500 with rollout budget \\$N = 64\\$, using LLaMA-3.1-8B-Instruct as the policy model. Results (averaged over 5 independent runs) are shown below:\n\n| \\$T\\_s\\$ |0.001|0.01|0.1|1.0|\n| -------- | ----- | ---- | ---- | ---- |\n| DORA     | 67.8  | 68.7 | 68.0 | 67.5 |\n\nThe results suggest that DORA is relatively robust to variations in \\$T\\_s\\$.\n\nTo further assess the impact of the embedding model itself, we compared our original retriever (BGE-M3, 568M parameters) with two popular alternatives from the MTEB leaderboard \\[1] that support long input lengths (≥2048 tokens): E5-base-4k (110M) and GTE-multilingual-base (305M). All experiments were conducted on MATH500 with \\$N = 64\\$, under the same experimental settings. Results are averaged over 5 runs:\n\n| Policy Model|BGE|GTE|E5|\n| ------------- | ---- | ---- | ---- |\n| LLaMA-3.2-1B  | 68.7 | 68.2 | 66.8 |\n| LLaMA-3.2-3B  | 77.6 | 77.4 | 76.8 |\n| Qwen-2.5-1.5B | 80.8 | 80.2 | 79.2 |\n\nWe observe that GTE and BGE perform comparably, showing that DORA is robust to embedding model changes within a similar capacity range. E5 does show a modest drop in performance, which we attribute to its smaller size and hence weaker ability to cluster semantically meaningful reasoning chains.\n\nWe will include these findings and discussions in the final version to better address concerns about DORA’s sensitivity to hyperparameter and embedding choices.\n\n### **Q3: On the Clustering Mechanism**\n\n**(i) Comparison to Hard Clustering Baselines**\n\nThank you for raising this insightful question. We fully agree that understanding the role of clustering is key to explaining DORA’s effectiveness.\n\nIn the early stages of our study, we systematically explored several hard clustering alternatives before adopting the final soft clustering design:\n\n* **KMeans clustering** requires predefining the number of clusters \\$K\\$. However, the actual number of distinct reasoning directions varies significantly across problems and reasoning steps. Using a fixed \\$K\\$ often led to poor alignment with the true semantic structure, resulting in suboptimal cluster quality.\n\n* We also considered **hierarchical clustering**, which avoids setting \\$K\\$ by merging solutions based on a fixed cosine similarity threshold \\$C\\$. However, we found that the optimal value of \\$C\\$ should ideally vary with the reasoning depth and problem type—factors that are highly instance-dependent. Consequently, hierarchical clustering was even less stable than KMeans in our experiments.\n\nBased on these observations, we adopted a **soft clustering** approach in DORA, which avoids hard assignment boundaries and allows for more adaptive semantic grouping. Below is our ablation comparing different clustering choices, conducted on the MATH500 benchmark with rollout budget \\$N=64\\$ using LLaMA-3.1-8B as the policy model (results are averaged over 5 independent runs):\n\n| Cluster Method | K=3  | K=5  | K=10 | C=0.95 | C=0.90 | C=0.80 | Soft (default) |\n| -------------- | ---- | ---- | ---- | ------ | ------ | ------ | -------------- |\n|Accuracy|67.6| 68.0|67.8|67.0| 66.6|66.0|**68.7**|\n\nAs shown, soft clustering consistently outperforms hard clustering baselines, highlighting the importance of flexible, non-discrete grouping in capturing subtle reasoning structures. We will include this ablation study and analysis in the updated version.\n\n**(ii) Empirical Effectiveness of Semantic Grouping**\n\nWe appreciate the reviewer’s thoughtful suggestion to quantify how effectively DORA’s clustering mitigates redundancy and improves success rates. This is indeed a highly valuable diagnostic perspective.\n\nTo better understand the effect of DORA’s semantic grouping mechanism, we conducted an additional analysis focusing on how well each method improves the intermediate success rate along the reasoning trajectory. Specifically, after each method allocates $K$ reasoning steps, we remove the search algorithm and resume temperature sampling based on the intermediate solutions obtained thus far. We then measure the pass rate of these partial trajectories to estimate the success rate at step $K$. This reflects the method’s ability to guide the policy model toward more promising reasoning directions early on.\n\nExperiments were conducted on the MATH500 benchmark with rollout budget $N=64$, using LLaMA-3.1-8B-Instruct as the policy model and Qwen2.5-Math-PRM-7B as the PRM. All results were averaged over 5 independent runs:\n\n| Step|0|5|10|15|20|25|30|35|40|\n| ----------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----|\n|Beam Search| 27.7 | 39.3 | 49.6 | 54.2 | 55.8 | 56.8| 57.3|57.5|57.5|\n|DVTS| 27.7 | 36.5 | 40.8 | 41.7 | 41.9 | 41.9 | 41.9|41.9|42.1|\n| REBASE| 27.7 | 39.5 | 51.2 | 54.5 | 56.5 | 57.1|58.0|58.3|58.3|\n| DORA| 27.7|**40.2**|**51.6**|**55.6**|**57.4**| **58.2** | **59.0** | **59.5** | **59.6** |\n\nAs shown, DORA consistently achieves the highest pass rates across intermediate steps compared to all baselines. Notably, Step 0 corresponds to the Temperature Sampling baseline (i.e., without any search intervention). Comparing this with the improvements achieved by REBASE and DORA highlights the value of clustering: while both methods significantly outperform the baseline, DORA consistently maintains a lead, suggesting that its semantic clustering mechanism not only reduces redundancy but also enhances the effectiveness of search guidance. We will include this result and analysis in the revised version.\n\n### **L3: On Generalization Beyond Mathematical Reasoning**\n\nThank you for pointing out this important limitation. We fully agree that evaluating generalization across domains is an important direction. \n\nDORA’s generalization beyond math (e.g., to code) is limited mainly by the lack of open-source step-level PRMs outside the math domain [2]. We have tested DORA and other step-level methods (Beam Search, DVTS, REBASE) on HumanEval and MBPP using Skywork-PRM—the only available PRM for programming tasks—but none significantly outperformed Temperature Sampling. This aligns with recent findings [3] showing Skywork-PRM offers weak step-level supervision. Using LLMs as critics is a potential alternative but adds considerable inference-time overhead, conflicting with TTS efficiency goals.\n\nWe will include this discussion and highlight the domain limitation. Extending DORA to code, science QA, and planning is a promising direction for future work.\n\n[1] MTEB: Massive Text Embedding Benchmark, EACL2023.\n\n[2] PROCESSBENCH: Identifying Process Errors in Mathematical Reasoning, ACL2025.\n\n[3] CodePRM: Execution Feedback-enhanced Process Reward Model for Code Generation, ACL2025."}, {"review_id": "oY5le6yhV0", "reviewer": "Reviewer_JSmU", "summary": "This paper investigates the problem of test-time rollout allocation for large language models (LLMs) under a fixed computational budget. The authors formalize the rollout allocation process as a resource optimization problem, and propose a novel method called DORA. Experiments on challenging mathematical benchmarks show consistent performance gains over existing methods.", "questions": "(1)\tAssumption of soft clustering quality: DORA relies on semantic embeddings and soft clustering via cosine similarity. However, it is unclear how robust this semantic grouping is across tasks and models. How sensitive is DORA to the choice of embedding model and the temperature parameters $T_s$?\n\n(2)\tScalability concerns: While the reported FLOPs and latency gains are encouraging, DORA introduces an extra embedding + affinity matrix computation step. How does this overhead scale with very large numbers of candidate trajectories (e.g., >10,000) which may lead to a failure case?\n\n(3)\tAssumption of shared PRM score per direction: The theoretical justification of DORA assumes that all solutions in a direction $j$ share the same PRM score $R_j$. In practice, PRM scores are noisy and not strictly aligned. How is this mismatch handled, and what is the empirical impact when intra-directional variance in PRM scores is high?\n\n(4)\tNo ablation on clustering effect: The paper does not include ablation studies comparing with other clustering methods at all. This would help isolate whether the gains come from semantic direction-aware allocation, or merely from reduced redundancy.\n\n(5)\tLimited discussion of generalization: The method is evaluated only on mathematical reasoning tasks. While these are valid and difficult benchmarks, it remains unclear whether DORA generalizes to other domains like code generation, etc.", "limitations": "While this paper tackles an important problem with an elegant solution and promising results, several key assumptions require further clarification and justification.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper tackles a practically important yet underexplored problem, the proposed direction-aware allocation strategy is novel and effectively addresses a real shortcoming in rollout allocation, showing state-of-the-art performance on multiple mathematical reasoning tasks and demonstrates superior compute efficiency.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer JSmU, we sincerely appreciate you taking the time to read our manuscript and provide valuable feedback. Below are our responses to the concerns you raised, which will be incorporated into the updated version to further enhance the quality of our submission.\n\n### **Q1: On the Sensitivity to the Embedding Model and Semantic Similarity Temperature $T_s$**\n\nThank you for this important question. We fully understand your concern regarding the robustness of DORA’s semantic grouping, which relies on the embedding model and the soft clustering temperature $T_s$.\n\nTo evaluate the impact of different retriever (embedding) models, we compared our original setup (BGE-M3, 568M parameters) with two widely used alternatives from the MTEB leaderboard [1] that support long inputs (≥2048 tokens): E5-base-4k (110M) and GTE-multilingual-base (305M). All experiments were conducted on MATH500 with $N=64$, and all other settings were kept identical to those in the main experiments. Results were averaged over 5 independent runs:\n\n|Policy Model|BGE|GTE|E5|\n|-------------|----|----|----|\n|LLaMA-3.2-1B|68.7|68.2|66.8|\n|LLaMA-3.2-3B|77.6|77.4|76.8|\n|Qwen-2.5-1.5B|80.8|80.2|79.2|\n\nThe results show that GTE and BGE yield comparable performance, indicating that DORA is robust to retriever changes within similar capacity ranges. However, E5 exhibits certain performance degradation, which we hypothesize is due to its smaller model size and thus weaker clustering capability in high-dimensional embedding space.\n\nWe further conducted an ablation study to evaluate the sensitivity of DORA to the semantic similarity temperature $T_s$, which determines how close two solutions should be to be considered as belonging to the same reasoning direction. Experiments were run on MATH500 with $N=64$, using LLaMA-3.1-8B-Instruct as the policy model. The results (averaged over 5 runs) are shown below:\n\n|$T_s$|0.001|0.01|0.1|1.0|\n|-----|-----|----|----|----|\n|DORA|67.8|68.7|68.0|67.5|\n\nThese findings demonstrate that DORA is relatively robust to the choice of $T_s$. We will include these results and corresponding discussion in the updated version to better clarify DORA’s stability with respect to embedding models and soft clustering settings.\n\n### **Q2: On the Scalability of Embedding and Affinity Computation with Very Large Candidate Sets**\n\nThank you for raising this important point. We agree that it is essential to assess the overhead introduced by embedding and affinity matrix computation, particularly at large rollout scales.\n\nFollowing \\[2–3], the total FLOPs of Test-Time Scaling (TTS) can be estimated as:\n\n$$\\text{Total FLOPs} = 2N \\cdot T_{\\text{sol}} \\cdot (P_{\\text{policy}} + P_{\\text{PRM}} + P_{\\text{emb}})$$\n\nwhere $N$ is the rollout budget, $T_{\\text{sol}}$ is the average solution length, and $P_{\\text{policy}}, P_{\\text{PRM}}, P_{\\text{emb}}$ denote parameter counts of the policy model, PRM, and embedding model respectively.\n\nThe embedding overhead ratio in TTS is caculated by:\n\n$$\\text{Ratio} = \\frac{P_{\\text{emb}}}{P_{\\text{policy}} + P_{\\text{PRM}} + P_{\\text{emb}}}$$\n\nThis ratio is **independent of $N$**, indicating that embedding cost scales linearly with rollout size and remains proportionally small. In our setup, the embedding model (e.g., BGE-M3 <600M) is significantly smaller than the policy (e.g., Qwen2.5-1.5B) and PRM (e.g., Qwen2.5-Math-PRM-7B), so its contribution to total cost remains minor.\n\nWe also analyzed **memory and runtime cost** of computing the affinity matrix (i.e., pairwise cosine similarities). When $N = 10{,}000$ (a scale well beyond most prior TTS works, which typically use $N \\leq 2048$), with 1024-dim embeddings in fp16:\n\n* Matrix size: $10^8$ entries → 200 MB\n* Embedding storage: 20 MB\n* Total memory: **\\~220 MB**, easily handled by modern CPUs\n\nFor runtime, computing 100M cosine similarities (each a 1024-dim dot product) totals \\~200 GFLOPs. On a single CPU core this takes \\~6–7 seconds, or <0.5s with 16-core parallelization. Since this is a **one-time cost per rollout**, it does not meaningfully affect overall latency.\n\nWe will include this analysis in the final version to clarify that DORA’s embedding-related steps scale efficiently even with large candidate sets.\n\n### **Q3: On the Assumption of Shared PRM Scores Within a Direction**\n\nThank you for this thoughtful question. The assumption in Theorem 1—that all solutions within a semantic direction are perfectly correlated and share the same PRM score—is introduced solely to enable a tractable theoretical analysis，which allows us to derive a clean optimality result.\n\nIn practice, solutions grouped within a direction are typically only partially correlated, and their PRM scores can differ due to modeling noise and semantic drift. Explicitly modeling this intra-directional variance would render the analysis intractable. To address this, DORA adopts a soft clustering mechanism and retains per-candidate PRM scores $R_i$, without collapsing them to a single cluster-level score.\n\nRollout allocation is computed individually for each solution using the formula (lines 195–196):\n\n$$w_i' = \\frac{w_i \\cdot \\gamma_i}{\\sum_j w_j \\cdot \\gamma_j},$$\n\nwhere $w_i$ reflects solution quality, and $\\gamma_i$ captures semantic uniqueness from the affinity matrix. This ensures that higher-quality candidates within a direction can still receive more rollouts, even when grouped with lower-scoring neighbors. By combining soft clustering with individualized scoring, DORA remains robust to intra-directional PRM variance. Our empirical results across multiple benchmarks show that DORA consistently outperforms baselines, suggesting that its design effectively handles score noise while still promoting semantic diversity. We will include above discussion in the revised version.\n\n### **Q4: On Clustering Ablation and Design Choice**\n\nThank you for raising this insightful question. We fully agree that isolating the effect of clustering is essential for understanding DORA’s improvements.\n\nIn the early stages of our study, we explored several alternative clustering strategies before finalizing the soft clustering design:\n\n* **KMeans** clustering requires predefining the number of clusters \\$K\\$. However, the actual number of distinct reasoning directions can vary across problems and reasoning steps, making fixed \\$K\\$ a poor approximation and often leading to suboptimal clustering performance.\n\n* We also experimented with **hierarchical clustering**, which avoids setting \\$K\\$ by merging solutions based on a fixed cosine similarity threshold \\$C\\$. However, the optimal value of \\$C\\$ should ideally vary with the depth and complexity of reasoning, which differ significantly across problems. This sensitivity made hierarchical clustering even less effective than KMeans in our experiments.\n\n* Based on these findings, we adopted a **soft clustering** approach in DORA, which avoids hard assignment boundaries and allows for more adaptive and robust semantic grouping across diverse reasoning structures.\n\nWe present below the ablation study comparing different clustering methods. All experiments were conducted on the MATH500 benchmark with rollout budget \\$N=64\\$ using the LLaMA-3.1-8B policy model (results averaged over 5 independent runs):\n\n|Cluster Method|K=3|K=5|K=10|C=0.95|C=0.90|C=0.80| Soft (default) |\n|--------------|----|----|----|------|------|------|--------------|\n|Accuracy| 67.6 |68.0|67.8|67.0|66.6|66.0|**68.7**|\n\nAs shown, soft clustering consistently achieves the best performance, demonstrating its effectiveness over hard clustering alternatives. We will include this ablation and discussion in the revised version.\n\n### **Q5: On Generalization Beyond Mathematical Reasoning**\n\nWe appreciate the reviewer’s thoughtful question regarding DORA’s applicability beyond math reasoning. We fully agree that evaluating generalization across domains—such as code generation—is an important direction.\n\nIn our current study, the primary obstacle to extending DORA to other domains is the lack of strong, open-source step-level Process Reward Models (PRMs) outside the math domain. Most high-quality PRMs publicly available today are specifically trained for mathematical reasoning \\[4]. For the code generation domain, we had already conducted exploratory experiments early in our study using Skywork-PRM—the only open-source PRM we are aware of that provides step-level feedback for programming tasks. We applied it to standard benchmarks such as HumanEval and MBPP, and tested all step-level search methods (Beam Search, DVTS, REBASE, and DORA). However, none of these methods were able to significantly outperform the Temperature Sampling baseline.\n\nWe believe this outcome is due to the limited step-level guidance capacity of Skywork-PRM for code tasks. This limitation has also been observed in recent work [5], which shows that Skywork-PRM provides relatively weak supervision for multi-step code generation. While using prompted open-source LLMs as critic models is a potential workaround, this approach introduces significant computational overhead and latency at inference time—undermining the efficiency goals of Test-Time Scaling.\n\nWe will include this discussion in the revised version and acknowledge the limited domain coverage of current PRMs as a key limitation. Extending DORA to broader domains—such as code, science QA, or planning—remains an exciting and important direction that we leave for future work.\n\n[1] MTEB: Massive Text Embedding Benchmark, EACL2023.\n\n[2] Scaling Laws for Neural Language Models, OpenAI.\n\n[3] Scaling LLM Test-Time Compute Optimally Can be More Effective than Scaling Parameters for Reasoning, ICLR2025.\n\n[4] PROCESSBENCH: Identifying Process Errors in Mathematical Reasoning, ACL2025.\n\n[5] CodePRM: Execution Feedback-enhanced Process Reward Model for Code Generation, ACL2025."}, {"review_id": "NTZmzFnz7h", "reviewer": "Reviewer_T3Po", "summary": "In this paper, the authors address a fundamental  aspect of TTS, specifically the optimal allocation of computational resources (rollouts) to maximise the success probability for LLM during inference. Existing approaches, including beam search, DVTS, and REBASE, tend to allocate resources at the solution level, unintentionally favouring reasoning directions with more candidate solutions. To rectify this inefficiency, the authors propose DORA, a method that allocates resources based on distinct reasoning directions rather than individual candidate solutions. DORA leverages semantic embeddings and a soft clustering approach to identify and balance resources across reasoning directions, theoretically proven optimal under certain assumptions. Extensive experiments conducted on challenging mathematical reasoning tasks (MATH500, AIME2024, AIME2025) demonstrate DORA’s superiority over baseline methods to some extent.", "questions": "1. How sensitive is DORA’s performance to the choice of hyperparameters (e.g., temperature parameters)? Is there any guidance or robustness analysis for selecting these parameters?\n2. Could you provide insights into the scalability of DORA, particularly how the embedding overhead scales with very large numbers of candidate solutions?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### **Pros:**\n\n1. The derivation of optimal strategies through Bayesian probabilistic modeling provides solid theoretical backing.\n2. Well-written and well-structured paper.\n\n### **Cons:**\n\n1. The claim \"DORA is the most effective parallel search method\" appears overly strong. The paper evaluates DORA exclusively using a single reward model (Qwen2.5-Math-PRM-7B), three relatively small-scale LLMs (<7B), and on a narrow set of benchmarks limited to mathematical reasoning datasets (MATH500, AIME2024, and AIME2025). Such a restricted evaluation setup raises concerns about the generality and robustness of the proposed method. To strengthen this claim, the authors should include additional experiments using alternative reward models and more diverse datasets. \n\n2. While DORA introduces embedding-based clustering to achieve optimal allocation, the computational overhead of embedding calculations, especially in scenarios involving a large number of candidates, is unclear.\n\n3. The reliance on soft clustering and temperature parameters (e.g., allocation temperature) suggests potential sensitivity to hyperparameter settings, yet detailed sensitivity analysis is missing.", "was_revised": true, "final_justification": "The authors have provided substantial experiments that address my major concerns. Kindly ensure these are reflected in the revision.", "rebuttal": "Dear Reviewer T3Po, we sincerely appreciate you taking the time to read our manuscript and provide valuable feedback. Below are our responses to the concerns you raised, which will be incorporated into the updated version to further enhance the quality of our submission.\u000b\n\n### **C1: On the Generality of the Evaluation**\nWe appreciate your thoughtful feedback regarding the generality and robustness of DORA. We fully agree that evaluating across more diverse PRMs, policy models, and benchmarks is crucial to substantiating the claim of DORA’s effectiveness as a parallel search method.\nTo address this, we have conducted a new series of experiments beyond the initial setup, expanding the evaluation in three directions (All results are averaged over 5 independent runs to ensure statistical stability):\n\n(1) Broader Benchmark Coverage: We incorporated four additional standard math reasoning benchmarks: HMMT24, HMMT25, AMC23, and AMC24. Under a rollout budget of N=64, the results are summarized as follows:\n\n|Policy Model|Method|HMMT24|HMMT25|AMC23|AMC24|\n|------------|------|--------|--------|--------|--------|\n|LLaMA-3.2-1B|Temperature Sampling |0.0     |0.0     |28.0    |13.3    |\n||Beam Search |2.0     |0.0     |43.0    |15.5    |\n||DVTS  |1.3     |0.0     |41.0    |18.0    |\n||REBASE|2.0     |0.0     |43.0    |18.2    |\n||DORA  |**3.3** |0.0 |**45.0**|**20.0**|\n|LLaMA-3.2-3B|Temperature Sampling   |0.7     |0.0     |48.5    |21.7    |\n||Beam Search  |2.0     |0.7     |55.5    |25.3    |\n||DVTS  |2.0     |0.0     |57.0    |26.2    |\n||REBASE|4.7     |0.0     |**59.0**|27.5    |\n||DORA  |**6.7** |**2.0** |**59.0**|**31.1**|\n|Qwen-2.5-1.5B|Temperature Sampling   |4.0     |0.0     |42.0    |16.4    |\n||Beam Search  |4.7     |1.3     |53.0    |31.1    |\n||DVTS  |4.7     |2.0     |51.5    |24.9    |\n||REBASE|5.3     |2.7     |54.0    |32.0    |\n||DORA  |**6.7** |**4.0** |**55.0**|**34.2**|\n\n\n(2) Larger Policy Models and PRM: We evaluated DORA with more powerful models by using Qwen2.5-Math-PRM-72B as the PRM to guide the LLaMA-3.1-8B-Instruct policy model on the MATH500 benchmark with N=64. The performance is reported below:\u000b\n\n|PRM |Policy Model|Temperature Sampling|Beam Search|DVTS|REBASE|DORA|\n|-----|-----|----|----|-----|------|-----|\n|Qwen2.5-Math-PRM-72B|LLaMA-3.1-8B|70.5|78.2|78.4|79.2|**80.6**|\n\n(3) Different PRM Families: To evaluate generalization across PRM families, we additionally tested **Skywork-PRM-7B** on the MATH500 benchmark with N=64. The results are shown below:\n\n|Method|LLaMA-3.2-1B|LLaMA-3.2-3B|Qwen-2.5-1.5B|\n|------|------------|------------|-------------|\n|Temperature Sampling|58.5|69.5|73.0|\n|Beam Search|69.0|75.5|79.7|\n|DVTS|66.2|74.2|78.9|\n|REBASE|70.8|76.2|80.2|\n|DORA|**71.8**|**76.6**|**81.0**|\n\nAbove experiments demonstrate that DORA generalizes well across a broader range of benchmarks, scales to larger policy models and PRMs, and is compatible with PRMs from different families. Specifically, the experiments with Qwen2.5-Math-PRM-72B were executed in parallel on a cluster with 100 H20 GPUs (96GB each), using 2 GPUs per run, and were completed in approximately 4 days. We will include these results and analysis in the later version.\n\n### **C2 & Q2: About computational overhead of embedding calculations with a large number of candidates**\n\nThank you for bringing up this important point. We agree that analyzing the computational overhead of embedding is essential, especially when scaling DORA to larger rollout budgets. According to \\[1-2], the total FLOPs incurred during Test-Time Scaling (TTS) can be calculated as:\n\n$$\\text{Total FLOPs} = 2N \\cdot T_{\\text{sol}} \\cdot \\left( P_{\\text{policy}} + P_{\\text{PRM}} + P_{\\text{emb}} \\right)$$\n\nwhere:\n\n* $N$: rollout budget (i.e., number of sampled solutions),\n* $T_{\\text{sol}}$: average number of tokens per solution,\n* $P_{\\text{policy}}, P_{\\text{PRM}}, P_{\\text{emb}}$: parameter sizes of the policy model, PRM, and embedding model, respectively.\n\nThe relative overhead of the embedding model in the total FLOPs is thus:\n\n$$Ratio = \\frac{P_{\\text{emb}}}{P_{\\text{policy}} + P_{\\text{PRM}} + P_{\\text{emb}}}$$\n\nThis fraction is constant and does **not** grow with $N$, implying that the embedding overhead scales **linearly** just like the other components and remains proportionally small.\n\nIn practice, Parameter of embedding models used in our setup (e.g., BGE-M3 <600M) are much smaller than that of the policy model (e.g., Qwen2.5-1.5B-Instruct) and the PRM (e.g., Qwen2.5-Math-PRM-7B).The additional computational burden introduced by the embedding model would not be a major concern as the rollout budget $N$ increases. We will include this analysis in the revised version.\n\n\n### **C3 & Q1: On the Sensitivity to Temperature Hyperparameters**\n\nWe appreciate your concern regarding DORA’s reliance on temperature-based mechanisms and the associated sensitivity to hyperparameter choices. To address this, we conducted a detailed ablation study on two key temperature parameters:\n\n(1) The allocation temperature $T_b$, which controls the sharpness of the softmax when allocating rollout budgets;\n\n(2) The semantic similarity temperature $T_s$, which determines how close two solutions  should be to be considered as belonging to the same reasoning direction.\n\nFor $T_b$, we default to 0.1 to align with REBASE, ensuring consistency and fairness. For $T_s$, we selected the final value via empirical study. We acknowledge that these results were not included in the original submission and apologize for the oversight. \n\nWe now report the full sensitivity analysis on the MATH500 benchmark with rollout budget N=64, using LLaMA-3.1-8B-Instruct as the policy model. Each configuration was run 5 times with different seeds, and we report the averaged accuracy:\n\n|$T_b$   |0.01|0.1|1.0|\n|------|----|----|----|\n|REBASE|64.8|65.9|55.4|\n|DORA  |67.4|68.7|57.2|\n\n|$T_s$  |0.001|0.01|0.1|1.0|\n|-----|-----|----|----|----|\n|DORA|67.8 |68.7|68.0|67.5|\n\nThese results suggest that DORA is relatively robust to the choice of $T_s$, with accuracy remaining stable across a wide range. In contrast, both DORA and REBASE show more noticeable degradation when $T_b=1.0$, as the softmax becomes too flat to leverage PRM guidance effectively. In the extreme case where $T_b \\to \\infty$, the model degenerates into temperature sampling. We will include these results and analysis in the updated version to provide clearer guidance for future applications.\n\n[1] Scaling Laws for Neural Language Models, OpenAI.\n\n[2] Scaling LLM Test-Time Compute Optimally Can be More Effective than Scaling Parameters for Reasoning, ICLR2025."}]

Author rebuttal:

Meta-review: Basically, this paper is built upon Reward Balanced Search (REBASE), and the research point is to arguing the assumption of REBASE that candidate independence. Based upon this arguement, the authors proposed DORA that introduces semantic embedding similarity to decouple rollout direction quality from candidate count, moving beyond diversity heuristics. 
The idea is interesting and sound, the work is also with solid theoretical analysis. 
After the discussion between reviewers, all reviewers are lean to accept.
I think the work is sound with solid contribution, thus champion the acceptance.
Here are some suggestions for the final version:
1). include the results and revision in the discussion to the final camera-ready;
2). include discussion of these two papers as they are highly relevant:
a). TREEBON: ENHANCING INFERENCE-TIME ALIGNMENT WITHSPECULATIVE TREE-SEARCH AND BEST-OF-N SAMPLING, Mendi Wang et. al. https://arxiv.org/pdf/2410.16033 (This prunes braches using PRM) 
b). DISC: Dynamic Decomposition Improves LLM Inference Scaling. https://openreview.net/forum?id=FFl6iyvJX2 (This also dynamically allocate resources by using ORM, thus is also doable to closed-sourced LLMs).
Decision: Accept (poster)