Rethinking Optimal Verification Granularity for Compute-Efficient Test-Time Scaling
Authors: Hao Mark Chen
Guanxi Lu
Yasuyuki Okoshi
Zhiwen Mo
Masato Motomura
Hongxiang Fan
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Models
Test-Time Scaling
Efficient Machine Learning
Primary area: deep_learning
TL;DR: We explore the role of verification granularity in sampling-based test-time scaling.

Abstract: Test-time scaling (TTS) has proven effective in enhancing the reasoning capabilities of large language models (LLMs). Verification plays a key role in TTS, simultaneously influencing (1) reasoning performance and (2) compute efficiency, due to the quality and computational cost of verification. In this work, we challenge the conventional paradigms of verification, and make the first attempt toward systematically investigating the impact of verification granularity—that is, how frequently the verifier is invoked during generation, 
beyond verifying only the final output or individual generation steps.
To this end, we introduce Variable Granularity Search (VG-Search), a unified algorithm that generalizes beam search and Best-of-N sampling via a tunable granularity parameter $g$. Extensive experiments with VG-Search under varying compute budgets, generator-verifier configurations, and task attributes reveal that dynamically selecting $g$ can improve the compute efficiency and scaling behavior. Building on these findings, we propose adaptive VG-Search strategies that achieve accuracy gains of up to 3.1\% over Beam Search and 3.6\% over Best-of-N, while reducing FLOPs by over 52\%. We will open-source the code to support future research.

Rethinking Optimal Verification Granularity for Compute-Efficien Test-Time Scaling
Hao (Mark) Chen' Guanxi Lu
Yasuyuki Okoshi?
Zhiwen Mo!
Masato Motomura" Hongxiang Fan
1mperial College London, UK
Institute of Science Tokyo, Japan
(hao.chen20, gu22 lu22, chiwen.mo25. hongxiang, imperial.ac.uk (okoshi. yasuyuki, motomura @ parttic..r.tttech.e..
Abstract
Test-time scaling (TTS) has proven effective in enhancing the reasoning capa- bilities of large language models (LLMs). Verification plays key role in TTS, simultaneously influencing (1) reasoning performance and (2) compute efficiency, due to the quality and computational cost of verification. In this work, we chal- lenge the conventional paradigms verification, and make the first attempt toward systematically investigating the impact of verification granularity that is, how frequently the verifier is invoked during generation, beyond verifying only the final output individual generation steps. To this end, we introduce Variable Granu- larity Search (VG-Search), a unified algorithm that generalizes beam search and Best-of-N sampling via tunable granularity parameter g. Extensive experiments with VG-Search under varying compute budgets, generator-verifet configurations, and task attributes reveal that dynamically selecting g can improve the compute efficiency and scaling behavior. Building on these findings, we propose adaptive VG-Search strategies that achieve accuracy gains of up to 3.1% over Beam Search and 3.6% over Best-of-N, while reducing FLOPs by over 52%. Our code is avaiblae giggtih...ommnc Satiaaub.ooommmaaa/////-----
Introduction
The past few years have witnessed the rapid advancement of large language models (LLMs), driven by scaling model size and training data [6] 17 28). However, further training-time scaling is increasingly constrained by prohibitive computational costs and the limited availability of high-quality human genuumeeee data [34]. Test-time scaling (TTS) [33 5 32 offers a promising alternative by enhancing performance through additional compute at inference time. TTS techniques generally
fall into two categories: internal scaling (33 25),, which focuses on optimizing single generation trajectory, and sampling-hasee scaling (5
32 35 which improves performance by exploring multiple candidate generations. These two approaches are orthogonal and can be combined to achieve higher performance [22]. Sampling-basee methods are typically training-frre and easy to integrate with internal scaling approaches in plug-and-play manner.
Verification, commonly implemented learned reward model or scoring function, plays key role in both TTS paradigms. State-of-the-art (SOTA) sampling-bass -baeed methods, such as Diverse Verifier Tree Search (DVTS) [4] and verifier- guideed Beam Search (32), leverage separate verifier LLM to guide the generation of a generator LLM, improving sampling efficiency and accuracy. In these methods, generation step typically defined as a chunk of text delimited by special tokens (e.g., newline characters), which serves as the atomic unit of verification. However, this verification granularity choice is heuristic 32 22) and remains static [3)] with guarantee of optimality. As
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1.30
Popece
S-Step
Namber of Ganerei
(b) Verification Cost
6-Step AScorn
waro
00
vatte
86
10.2%
055
sear
Desoodn
200
intverce Compus Prodlen (PLOPG
(a) Score Stability
grandattyy
(d) Optimized Performance
(c) Inference Latency
Motivations for Optimizing Verification Granularity g. (a) Small PRM score deltas 1LLLMM3.1-8--PP.. across generation steps indicate redundant verification. (b) Verification incurs notable latency overheads.
Figure 1:
(c) Increasing verification granularity lowers the latency of both Proposer and Verifier. (d) Optimizing y improves the accuracy-compll tradeoff over graeularaalrrttyy baselines (Qwen2.5-Math-- as generator, Skywork-ol-1.35 -1155B as verifier).
shown in Figure Ta our profiling results show that verifier scores often remain stable across multiple generation steps (e.g., over 50% of 2-step score differences are below 1% of score range), suggesting redundancy in the current verification granularity. This inefficiency causes verification to account for an increasingly large proportion of the overall inference latency, as illustrated in Figure 1b] These insights and observations motivate us explore the following two research questions (RQs):
RQI. Is the conventional verification granularity optimal for the accuracy compute scaling?
RQ2. If not, how can we optimize it to achieve a better accuracy-compon frontier?
To explore RQI, we introduce Variable Granularity Search (VG-Search), a unified algorithm that generalizes verifier-guided Beam Search and Best-of-N methods. VG-Search employs granular- ity parameter that controls the verification granularity (Section 2). Our hardware performance profiling (Figure Icc shows that g has significant impact the latency contributions of both the generator LLM and the verifier. To further investigate the accuracy-compute trade-off under varying g. conduct extensive experiments with VG-Search across different values of g, models, compute budget, and datasets (Section 4). Building on top of the insights from RQI, we propose an adaptive VG-Search approach which dynamically adjusts the verification granularity based on the compute budget and task attributes (Section 5) to further address RQ2. As shown in Figure [d] our results demonstrate better performance compute frontiers than previous sampling-basd -based TTS methods. Overall, our main contributions are:
We propose Variable Granularity Search (VG-Search), enabling systematic analysis of how verifica- tion granularity affects performance and compute scaling.
Through extensive experiments, we show that the conventional static verification granularity is sub-optimal, limiting the performance scaling of verifier-guided search methods.
We develop adaptive VG-Search strategies that dynamically tune granularity, achieving up to 3.1 % higher accuracy than Beam Search, 3.6 % over Best-of-N, with over 52% % compute reduction.
2 Exploring Verification Granularity for Reasoning
2.1 Verification Granularity in Verifier-Guided Search
In verifier-guided search, generator model proposes candidate steps and verifier model evaluates them to guide the search process. The task of generating a correct solution can be framed collaboration between two components:

---

Variable Granularity Search
Beam Search
Best-of-N
Question
Question
Question
Granulerity (g=2)
Verification
Beam Width
(B1=2)
Branch-Out (82:2)
Rejected
Rejected Final Step
Selected Final Step
Extend Step
Select
Internediate Step
Intermediate Step
Figure 2: Variuble-Gramularity Search (VG-Search). VG-Search unifies verifier-guides Beam
Search and Best-of-N via the granularity parameter g. At each step. B1 B2 candidates are verified and B1 = 2 candidates are selected. B₂ continuations are generated per selected path. Only the Bj selected candidates proceed to the Extend Step, redueing proposer FLOPs by pruning early.
Generator (Proposer) G: A probabilistic model, typically an LLM,, responsible for generating a partial complete candidate sequence St.t+g. where g denotes the number of the generation steps. The generation process is governed by the distribution P(S 9).
Verifier V: A scoring function (((e:c+g) + that assigns scalar score to each partial or complete candidate sequence St.t+g. The verifier is invoked after every g generation steps. This score is intended to correlate with the expected quality or correctness of the sequence prefix.
The goal of the search process is to generate correct or high-quality solution si.r of length T via interaction between the generator and verifier. A key hyperparameter in this process is the verification granularity g. which controls how frequently the verifier can intervene and guide the generator. To illustrate the impact of we link the verifier- verifier-guided guided search to an edge case, the Infinite Monkey Theorem (IMT) (3), where a random generator (monkey) tries reproduce a target sequence (e.g., Shakespeare's ' work) under perfect verifier invoked every characters. When verification is infrequent (large g). the expected number attempts grows exponentially as E[[A), making success computationally infeasible. In contrast, with frequent verification, early error pruning reduces the expected cost E[A*], at the expense of higher verification overhead. This toy setting underscores fundamental trade-off between verification cost and exploration efficiency. Optimizing g is thus critical for effective collaboration between generator G and verifier under compute constraints.
The most common approach to defining relies on heuristics and remains static. However, this convention might be neither consistent nor optimal: the model distribution varies widely-some some generators are more verbose, others more structured-an the number of tokens required to concep- tualize coherent "thinking step" can differ significantly across tasks. This motivates a systematic study of how performance scales with different granularity g.
2.2 Variable-Granularity Search
Beam Search (5] and Best-of-N sampling [32 are two prevalent methods for scaling large language model (LLM) performance at test-time by leveraging additional computation. These methods represent two opposing extremes within the spectrum of verifier-guided search, primarily differing in the frequency with which the verifier V checks the outputs from the proposer G. In Beam Search, verification is highly fine-graineed V actively guides candidate selection at each generation step, enabling the early pruning of less promising paths. Conversely, Best-of-N sampling employs coarse- grained approach, where the verification is performed on an entire candidate solution. While this allows for broader exploration, it lacks the intermediate guidance provided by frequent verification.
To bridge this gap and enable a continuous exploration of verification granularity, we introduce Mariable-Granulan Search (VG-Search). VG-Search unifies Beam Search and Best-of-N N sam-
3

---

pling through the concept of verification granularity (g). By varying VG-Search allows for continuous control over the trade-off between fine-grained guidance and broad exploration. Key hyperparameters of VG-Search include:
Beam Width (B1): The number of top-scoring candidate sequences (beams) retained after verification and selection.
Branch-Our Factor (Ba): The number of alternative continuations generated by 9 from each of the B1 retained beams before the next verification phase.
Verification Granularity (g): The number of generation steps evaluated per verifica- tion-i.e., the interval between verifier (V) calls.
As illustrated Figure single cycle of VG-Search advances the search from a candidate length to 8 g. The full algorithm proceeds as follows:
1. Start: Initialize with B1 B2 candidates from the initial prompt.
2. Verify & Select: Evaluate B1 B2 candidates using V, and retain the top Bı beams.
3. Extend: For each of the B₁ selected beams, produce
generation steps using G.
4. Branch: For each extended beam, produce B2 seneleegenerationn- continuations using
5. Repeat: Go back Step 2 and iterate until termination criteria are met.
Omitting Step 3 (Extend) or setting 9 reduces VG-Search to standard Beam Search. At the other extreme, when L (the number of generation steps in full solution), VG-Search becomes equivalent to Best-of-N sampling. One alternative design to produce g - 1 generation steps in Branch, mimicking Beam Search but with variable verification granularity. However, prior work [32] shows that rolling out multiple future tokens, as Look Search, does not yield the best performance. We therefore adopt simpler, more compute- efffciette design: Branch generates just one step per candidate, and early pruning via the verifier occurs before Extend, As a result, only the top B1 candidates continue in Extend, instead of the full B₁ B2 set used in Beam Search or Besttof-NNleadinne
to significantly lower proposer FLOPs. Larger further amplifies savings for both verifier and proposer. We validate this design in Section 4.1 A case study of VG-Search is illustrated in Appendix A.8
2.3 Compute Cost Model for Generator and Verifier
To analyze and optimize g. we define compute cost model in FL.OPs with the following parameters: (1) average solution length generation steps, (2) Pg- Pe: parameter counts of the generator and verifier, (3) Fg: FLOPPs per generation step. (4) F.: FLOPs verifier call. The number of VG-Search cycles approximately Noyeles L/g. Following prior work [31], we approximate Fg R 27 where 7' is the average number of tokens per generation step. Similarly, F, s 2aP.. where is verifier-speciffe variable.
The total compute for generation, Cg, includes extending the BN primary beams and generating BN branches across all cycles:
_.
Cg = Bi
Neyeles F2= Bi 1 B2)
(I)
Extending
Branching
The total compute for verification, Cy. accounts for scoring B1 B2 candidates across all cycles:
C BB Neyoles F. =2-a a Bi B2 L P.
(2)
g
The total compute cost Cronal becomes:
L B,
Cintal CG + Cv =
- 1+ Bτ) Pg - a B2 Po] g
(3)
We adopt the proposed cost model to study the scaling behavior of VG-Search (Section which provides reliable proxy for measured inference latency as demonstrated in Figure Ic

---

3
Experiment Setup
To investigate the optimality of the conventional verification granularity mentioned in RQI, we conduct experiments on mathematical reasoning benchmarks.
Task and Datasets. We evaluate on the MATH-500 [2]] and AIME 2 datasets. MATH-500 samples 500 problems from the MATH []6] benchmark, with difficulty levels labelled. AIME comprises 90 advanced high school mathematics problems from the past three years (AIME24, AIME23, AIME22). Additionally, we sample 250 problems from the MATH [16] benchmark as a validation set for Section 5 referred as MATH-250. It consists of 50 problems per difficulty level.
Policy and Reward Models. For Proposer, we use both general- model (Llama-3.2-3B-
Instruct [1] and models with internal scaling ability, fine-tuned to generate Chain-of- of-oouhhhhh (CoT) for math tasks, Qwen2.5-Math-78 and Qwen2.5-Math- 1.55 [40]. All models are prompted to generate step-by-step solutions. For the Llama models, official evaluation, which explicitly states the response template. For the Qwen models, is suggested use simple prompt template. Following the community convention and prior work [22 32 4 use AnAn to delimit each generation step, which serves as the smallest unit of verification granularity. For Verifier, employ discriminative Process Reward Models (PRMs), including Skywork-o1-1.55t and Skywork-ol--7 10- [27], as verifiers. Following [4, we use Last (final) scores for selection. Details of FLOPs calculation are in Appendix (A.2
the same prompt template as the
4 Understanding the Limits of the Verification Granularity Convention
4.1 Test-Time Scaling Law with Verification Granularity
In this section, we aim to answer RQI, investigating how the optimal verification granularity varies with both the compute budget and the capabilities of the Popoose--Verifier pair. To explore different operating points on the accuracy-computc trade-off curve (Figure we vary and adjust the number of generations to modulate the total compute budget. We analyze three representative generator -vr-verr (V) pairs, specifically chosen to probe the interplay between model capability and compute allocation:
1. Strong G (Qwen2.5-Math-7BB with a Small V (Skywork-ol-1.5B)
Weak G -Llama-3.2-3B-Insttee not math-finetuned) with a Small V (Skywork-ol-1.5B),
Medium 9 (Qwen2.5-Math-1155B with a Large V (Skywork-ol-7B).
Our findings in Figure 3 indicate that the optimal verification granularity depends on both the generator's ' capability and the available compute budget:
Strong Generators Prefer Sparse Verification, while weak ones need frequent checks. For the strong Owen2.5-Math-77 generator paired with small verifier, while standard Beam Search (g = 1) is effective at lower compute costs, sparser verification (g E {2, 3, 4}) achieves superior accuracy at medium to high compute budgets, as shown in the first column Figure Notably, 9 = 3 reaches the highest peak accuracy, outperforming a strong generator can reliably produce longer correct partial solutions, making frequent verification less critical and allowing compute to be reallocated (e.g., to wider beams via B,) for better overall performance. As shown the second column of Figure moderately strong -wwen.55-Math- when paired with a large verifier, also benefits from sparser verification, with g = 2 consistently outperforming g = from mid-to-high compute and achieving the best peak accuracy. However, excessively sparse verification (g = 4) becomes detrimental, indicating an optimal balance point. In contrast, as shown in the last column of Figure 3 the non-specialized Llama-3B generator has peak performance with frequent verification (g or less task-aligned generators require continuous guidance. Interestingly, on the more challenging AIME dataset, all Proposer- Verifier pairs show tendency for sparser verification (g 1, sometimes even g = 4) to outperform = at medium and high compute budgets. This might be because AIME problems benefit more from the broader exploration encouraged by sparser verification (which
by approximately 4% on MATH-500. This suggests that
on MATH-500 and MATH-250. implying that weaker
SlywookkSSywoorko00 PRM Qwen-2.5-7B
5

---

g=1 (beam)
9F2
g=3
Strong Small
Medium G, Large
Weak Small
MATH-500
825
Acqurscy
90
75.0
213
2.4
2
2
26
2
90
MATH-250
186)
90
80
80
86
75
84
84
82
20
30
20.0
18
25
17.5
AIME
Accurasy
16
15.0
20
84
12
10.0
10
FLOPS
FLOPS
FLOPs
Figure 3: Accuracy compute (FLOPs) across different verification granularities g-
makes the search resemble Best-of-N), or the PRM's step-wise utility is less consistently high on AIME, reducing the benefit of frequent checks.
Optimal Granularity Varies with Compute Budget. Across most models and datasets, sparser verification (g 1) tends become more competitive as the total compute budget increases. At very low compute budgets, the aggressive pruning of standard Beam Search (g 1) often provides more robust performance baseline. This aligns with the intuition that investing in more extended generation phases between verifications is more viable when more overall compute is available to support wider exploration or more candidate paths.
Optimal Granularity Saves Computation Significantly. A key advantage of using sparser verifi- cation (g >> 1) is the potential for substantial FLOPs savings while maintaining- even improv- ing performance. For example, in the Strong G. Small V setting on MATH-500, setting g = 3 achieves approximately 88% accuracy at 213 FLOPs, whereas g requires 2 FLOPs to reach a slightly lower accuracy of around 87.5%. Similarly, on AIME, = 4 attains comparable peak accuracy to g = 1, but with noticeably lower FLOPs cost across several configurations, This efficiency gain arises from fewer verifier invocations and reduced branching operations overall, as detailed in our cost model (Section 2.3 Moreover, the reduction in FLOPs effectively translates into
decreased latency, as shown in Figure 1c
Rethinking the Optimal "Thinking Step". The observation that increasing y (sparser verification) can improve accuracy while reducing compute budget is significant. This challenges the conventional verification granularity (g 1). where verification typically occurs arbitrary delimiter boundaries (c.g., newlines), which may not always align with meaningful reasoning steps. First, as shown in Figure Ta consecutive PRM score differences are often negligible, indicating that the current definition of a "thinking step" is overly fine-gme -neigniiedd Second, a larger g can be interpreted as defining more substantial and semantically coherent "thinking step". Delaying verification and branching until the end of these extended segments may avoid injecting noise by evaluating incomplete reasoning fragments, thus enabling more effective search. Thus, response to RQ1, we conclude that current convention for verification granularity is sub-optimal, motivating more flexible definition of verification canularity-beyore fixed token-level delimiters- and highlighting the need for more sophisticated approach to optimizing (Section))

---

1-1
9P?
7B-Aieey
60-
17.9
MATH-500
14
12
2
20 20
25.0
17.5
AIME
FL0%
TLOP
FLOTS
Fo0Ps
TLOPs
Figure 4: Ablation on verifier quality and model sizes.
4.2
Ablation Studies on Verifier Quality and Model Scale
We conducted two ablation studies to investigate the impact of verifier quality and model scale the optimal granularity, with results shown in Figure 4 To simulate a worst-case scenario for verifier quality, replaced the standard verifier with maximally noisy PRM that assigned random score to each generation step. As hypothesized, when the verifier provides no useful signal, the optimal strategy consistently shifts to sparser verification (g > 1), frequent but unreliable guidance degrades search performance (Figure
We validated our findings at different model scales by pairing various generators from the Qwen-2.5 series with Skywork- SyyMor-PPRM verifiers different sizes. The results (Figure 4 confirm that the optimal verification granularity remains dynamic across all tested scales.
4.3 Trade-offs: Granularity, Verifier Parameter, and Branching
This section further explores how interacts with other key hyper-parameters: the verifier's model parameter and the branch-out factor B2 to optimize compute allocation under fixed total compute budgets. All experiments in this section utilize Qwen2.5-Mathh
as the generator.
Granularity vs. Verifier Parameter. We investigate whether is more beneficial use strong verifier sparsely (larger larger verifier model) or a weaker verifier frequently (smaller smaller verifier model). Bagure55acoompree two configurations: (1) g = (frequent verification) with Small Verifier (Skywork-ol-1.53)
and (2) g = 2 (sparser verification) with a Large Verifier (Skywork- o1-7B). As shown in Figure 5a lower compute budgets, sparse verification with a larger verifier yields low accuracy. However, as the compute budget increases, employing larger verifier more sparsely achieves higher peak accuracy. This suggests a clear preference for leveraging stronger, more discerning verifiers less frequently when sufficient computational resources are available.
Granularity vs. Branch-Out Factor Next, we explore the trade-off between the verification granularity and the branch-out factor B2, at matched total compute FLOPs. Increasing means fewer verification calls and longer generation segments, while increasing B3 means exploring more alternatives at each verification point. The verifier used in this experiment is Skywork-o1-11558 Figure 55 shows that configurations with a small granularity (g to outperform other configurations at low or mid-range compute budgets. However, all configurations converge at very high compute. Comparing the above findings, a clear pattern emerges: investing saved compute in the verifier parameter appears to be more effective scaling strategy than simply increasing the number of branches.
B 2) with low branching tend
4.4 Optimal Verification Granularity vs. Task Difficulty and Number of Samples
To assess the practical limits of sparse verification, we define the largest effective as the maximum verification granularity that retains at least 95% of the accuracy achieved at 9=1. 1. We also analyze the accuracy gain of g=2 over 9=1 across varying sample budgets and task difficulty levels. Figure 5d 5e show that the optimal is strongly influenced by both difficulty and sampling budget.
7

---

Owen2.5-Mailn
86
Accuaayy O Oftecti minus g-3
g-2
Largest Effective Vallue
60
hartor Commentionn 220
Nocuraty
Number Caneration
10
++-
ned
0.7
pH25
128
f-128
fifcutly Level
(n)
(a)
Small V VS g Large V
OwenZ 5-Math-1
(d) Acc. diff. Majority Voting
081
Largest Effective Value
Acharagg (deigttetge))
Aoculooo Socuroo//ittoo Ditoord 0: nE 9-12
Nartor of Cannestarre
Aocurrt
85
Mumber of Generations
84
mn
g=3, B20g
g22,
1m54
n-16
126
23
1.0
15
82-8
1
2
3
Inferanca Compute per Probiem (FLOPS)
Difficulty Level
fiiuuiyy
(b) Matched FLOPPs with diff. and B2 (c) Largest effective values
(c) Acc. diff. Weighted Voting
Figure 5: (a) shows 2 with strong verifier outperforms 1 with a weak verifier at high compute budget. (b) demonstrates limited performance gain from increasing branch factor Bg. (c) plots the largest effective y across difficulty levels for different generators. (d).(e) show the accuracy gain of sparser verification with a stronger verifier across difficulty levels and number of generations.
Increased Task Difficulty Demands Denser Verification. Across all models and compute budgets, we observe a consistent trend: as task difficulty increases, the largest effective g decreases. For the hardest problems (Levels 4-5), 9-1 g-2 is often required to maintain performance at lower compute budget. Likewise, the advantage of g-2 over g=1 diminishes with difficulty, likely because harder tasks involve more reasoning errors, necessitating more frequent verifier intervention to stay on track.
Higher Number of Samples Tolerates Sparser Verification. In general, larger sample budgets allow for sparser verification, especially on easy to moderately difficult tasks. Higher budgets also amplify the performance gain of g=2 over g=1, as the generator can explore wider search space, increasing likelihood finding a correct path despite less frequent verification.
Towards Adaptive Redefinition of the Verification Granularity
5.1 Adaptive Granularity Strategies
Our results (Figures 5) show that the optimal g in VG-Search depends on task difficulty, compute budget, and model capability. This motivates more systematic approach to defining the search step, addressing RQ2. We formulate an optimization dual for selecting verification granularity: minimizing compute for target accuracy vs. maximizing accuracy under compute budget. For each, propose a corresponding adaptive granularity strategy:
Strategy 1: Compute Minimization with Performance Parity (CM-g) CM-g finds the largest g" that maintains accuracy within a tolerance e of = 1, reducing compute. Given generator, difficulty d, and number of generations 1. Compute baseline accuracy Acc(g=1, d, n). 2. Increase while Aco(g, d, n) 2 Acc(g=1,d, d, n) return the largest g" satisfying the accuracy constraint.
Strategy 2: Accuracy Maximization with Budget Constraint (AM-g) AM-g selects g that maximizes accuracy under fixed compute budget (as in number of generations): g" arg max.e Acc(g, n.).

---

Adaptive VG-Search
Beam Search
Metric
DVTS
Best-of-N
Oracle
CM-g
AM-g
CM-g
AM-g
Acc.
89.2
90.1
88.6
90.1
87.0
89.2
89.5
64
FLOPs
5393
5844
5543
6145
12010
12010
11952
Acc.
90.5
90.6
89.9
90.1
89.3
89.7
89.3
128
FLOPs
15899
16200
11086
12290
24021
24021
23904
Acc.
90.7
90.8
90.4
90.4
88.8
89.5
89.2
256
FLOPS
21572
22775
28189
28189
48042
48042
47808
Table Performance of adaptive granularity strategies (CM-g, AM-g) vs. baselines on MATH-500, using Qwen2.5-Math-77 as the proposer and Skywork-ol- 1.5B as the verifier. Best accuracy and Lowest FLOPs bold underlined, is the number of generations per question.
Budget
Strategy
samples
samples
100 samples
200 samples
CM-g AM-g
87.03%
88.57%
88.57%
88.57%
n 64
87.03%
88.57%
89.19%
90.09%
CM-g
88.76%
90.37%
90.37% 90.37%
90.43%
n1 256
AM-g
88.76%
90.37%
90.43%
Table 2: Test accuracy on MATH- 500 vs. number of validation samples used to select g". Performance converges rapidly for both medium (n 64) and high (n 256) compute budgets.
We compare against Beam Search, DVTS, and Best-of-N baselines on the MATH-500 test set. "val" indicates y was tuned on validation set MATH-250, while strategies under "oracle" use oracle selected on the test set. We set e for CM-g. shows that both AM-g and CM-g improve performance and efficiency. AM-g consistently achieves higher accuracy, with gains up to 3.1 % over Beam Search, while CM-9 provides substantial FLOPs savings, reducing compute by over 64 and 256 while maintaining improving accuracy. For instance, CM-g (val) at n = 128 achieves 89.9% accuracy using just 11086 FLOPs-ore 46% the baseline budget. Although oracle-tuned variants perform slightly better, validation-tun -unee versions (CM-g g (val), AM-g (val)) still outperform fixed-g methods, demonstrating strong generalization and practicality. Under cost model, CG dominates, most FL.OPs savings come from pruning candidate paths during the Extend Step (Section 2.2). In summary, adapting verification granularity g to task difficulty and compute budget offers simple yet effective way, enabling efficient and performant L.LM reasoning.
50%
5.2 Practicality and Convergence of Optimal Granularity Search
key practical consideration is the overhead finding the optimal granularity g² We analyzed its sample efficiency by selecting g on validation subsets of increasing size and evaluating the performance on the MATH-500 test set. The results, shown Table demonstrate that the search converges rapidly. For both high (n 256) and medium (n 64) compute budgets, using just validation samples achieves most of the possible accuracy gains over the baseline, confirming the minimal overhead of our adaptive approach.
This search constitutes negligible, one-time cost that amortized over all subsequent uses, ensuring our FLOPs comparisons are fair. The practical guideline is to reuse a pre-computed g" for given model, task, and budget, and recompute only when a core component, like the generator model, changes. For tasks with distinct subsets (e.g., varying difficulty levels), different g values can be pre-computed and selected at inference time, making this a practical and effective alternative the fixed- toreddraaularity convention.

---

6
Related Work
Test-Time Scaling (TTS). Recent work on scaling test-time compute can be broadly categorized into two approaches 43 [9]: i) Internal scaling and fi) sampling-baser TTS. Internal scaling methods enable models to scale their test-time compute by adapting their parameters through Supervised Fine-tuning (SFT)
42 24 or Reinforcement Learning (RL) [3 23 41. However, without explicit
compute budget control I 3 these approaches often result in unnecessarily long CoT, even for simple queries, leading to inefficient inference costs. Sampling-base -aaed TTS, by contrast, dynamically allocates test-time computation during deployment, without requiring additional tuning to modify the model's parameters offfine. Sampling-based TTS [10, 32 29 []] orthogonal to internal scaling approaches, allows for more fine- sane-graine control over compute usage and can further improve algorithmic performance. As noted by 22). multi-step lookahead approaches, such as Monte Carlo Tree Search (MCTS) [4], adaptive thought rollback [8), and hierarchical multi-step verification [3), incur substantial sampling overhead during inference, we do not consider such methods in this work.
IifficationGuuidel Search. Verifying the quality of generated outputs to guide campling-based TTS has been shown to significantly improve the efficiency of test-time computation [22 32 Based on the granularity of verification, existing approaches can be broadly classified into two categories: (i) outcome verification and (ii) process verification. Outcome verification [TO] evaluates the entire response after the generation of complete sample. This approach is widely used in sampling-base TTS, such Best-of-N strategy [9], where verifier selects the most promising answer from a set of full samples. While simple and effective, outcome verification provides no intermediate feedback, which can lead to wasted computation on low-quality completions. Process verification [2 44], often implemented as process reward model (PRM), evaluates intermediate reasoning steps during generation. These models assign scores to partial outputs, allowing the inference process to be guided. PRMs have been shown to improve sample efficiency and enable early pruning of unpromising token paths, leading to more compute-efficient search. Despite their promise, both outcome and process verification methods treat the verifier as fixed component and typically apply it at a pre-defined granularity. In contrast, our work introduces adaptive approach that dynamically optimizes verification granularity to maximize performance. Due to the verification inefficiency of Generative PRMs 44 under matched compute budgets [31], we leave their investigation to future work.
Compute Optimal Scaling. Previous research 332 indicates that the optimal choice between Best- of-N and Beam Search often depends on factors such the available compute budget and the problem characteristics. Yet, restricting selection to these two discrete options limits flexibility and expressiveness in identifying an optimal compute scaling strategy. By introducing variable granularity (g), VG-Search spans a continuous spectrum of search behaviors between these extremes, offering potentially greater expressiveness for the optimal TTS strategy.
Prior work has investigated how test-time strategies, compute budgets, and problem difficulty interact, showing that optimal allocation of interence-time compute can be more effective than merely scaling model parameters [32]. Scaling the number of verification attempts per candidate has been shown to improve verification accuracy and overall task performance [30]] Recent work [31 also explores compute-optimal strategies for deciding when to generate new solutions versus verifying existing ones, taking into account the number of verification and output samples. [20] demonstrates that employing multiple diverse verifiers can enhance performance, as different verifiers are likely to messisteney-basee model switching method that
detect different types of errors. 77] proposes leverages multiple generator models to efficiently scale test-time compute, showing that a diverse generator pool can more effectively explore the solution space. [ introduces adaptive thought rollback, but does not consider verification granularity. Despite the progress, optimally adapting the verifier's invocation frequency during test-time scaling remains key unanswered question.
7 Conclusion
This paper investigates the critical role of the verification granularity g in verifier-guided test-time scaling, introducing VG-Search to facilitate exploration. Our experiments show that the optimal verification granularity is highly compute budget. Building on these insights, we challenge the current convention and propose adaptive strategies for selecting y to optimize efficiency and performance. This work motivates future research that explores more advanced approaches optimizing the verification granularity g.
on generator capability, task difficulty, and
10

---

References
[1] Pranjal Aggarwal and Sean Welleck, LI: Controlling how long a reasoning model thinks with reinforcement learning. arXiv preprint arXiv:2503.046977 2025.
[2] AI-MO. Aime 2024, 2024.
URL httpa://uuugginnacccc.c/attttttt
aimo validationnn aime
[3] Daman Arora and Andrea Zanette. Training language models to reason efficiently, arXiv preprint arXiv:2502.04466 2025.
[4] Edward Beeching, Lewis Tunstall, and Sasha Rush. Scaling test-time compute with open models, 2024. URL https: httpp://hhuggnggfac. co/ http://ce//uugggggaaaaaaaoo
Slogpost-saaling test - time--immmutette compute
[5] Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXi::240.221787, 2024.
[6] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[7] Jianhao Chen, Zishuo Xun, Bocheng Zhou, Han Qi, Qiaosheng Zhang, Yang Chen, Wei Hu, Yuzhong Qu, Wanli Ouyang, and Shuyue Hu. Do we truly need so many samples? multi-llm repeated sampling efficiently scale test-time compute. arXiv preprint (XXi::5504000722 2025.
[8] Sijia Chen and Baochun Li. Toward adaptive reasoning large language models with thought rollback. arXiv preprint arXiv:2412.19707, 2024.
[9] Yinlam Chow, Guy Tennenholtz, Izzeddin Gur, Vincent Zhuang, Bo Dai, Sridhar Thiagarajan, Craig Boutilier, Rishabh Agarwal, Aviral Kumar, and Aleksandra Faust. Inference-aware fine-tuning for best-of-n sampling in large language models. arXiv preprint arXiv:2412.15287, 2024.
[10] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2 /0. /4/68, 2021.
[11] NVIDIA Corporation. Nvidia a100 tensor core gpu architecture. Technical report, NVIDIA Corporation, 2020. URL httpp::/imaaees...... www.seiiiiiiiiiiii com/ aem- dam/ eaam//en-a en /z/luuuionss///////o pdd
[12] NVIDIA Corporation. Nvidia h100 tensor core gpu architecture. Technical report, NVIDIA Corporation, 2023. URL htt.tttt:///eeuurreeee nvidia. wtt.d/ia..commaaamommmmm wwt.e/coommmme--eeooeeeoo tos-ooo-oooooooooorr
[13] NVIDIA Corporation. Nvidia tools extension library (nvtx). NVTX 2025, Version 3.2.0.
[14] Xidong Feng, Ziyu Wan, Muning Wen, Stephen Mareus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309. 17179, 2023.
[15] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783 2024.
[16] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03874 2021.
[17] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbi, Aidan Clark, al. Training compute-optimal large language models. arXiv preprint arXiv:2203.15550 2022.
11

---

[18] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang. Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 61 1-666, 2023.
[19] Zhong-Zhi Zhi Li, Duzhen Zhang. Ming-LLang Zhang, Jiaxin Zhang, Zengyan Liu, Yuxuan Yao, Haotian Xu, Junhao Zheng, Pei-Jie Wang, Xiuyi Chen, et al. From system 1 to system 2: A survey of reasoning large language models. arXiv preprint arXiv:2502.1741, 2025.
[20] Shalev Lifshitz, Sheila A Mcllraith, and Yilun Du Multi-agent verification: Scaling test-time compute with multiple verifiers. arXiv preprint arXiv:2502.20377 2025.
[21] Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike. John Schulman, llya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2023.
[22] Runze Liu, Junqi Gao, Jian Zhao, Kaiyan Zhang, Xiu Li, Biqing Qi, Wanli Ouyang, and Bowen Zhou. Can 1b IIm surpass 405b Ilm? rethinking compute-optimal test-time scaling. arXiv preprint arXiv:2502.06700
2025.
[23] Michael Luo, Sijun Tan, Justin Wong, Xiaoxiang Shi, William Y Tang, Manan Roongta, Colin Cai, Jeffrey Luo, Tianjun Zhang, Li Erran Li, et al. Deepscaler: Surpassing ol- ol-preview with 1.5 b model by scaling rl. Notion Blog, 2025.
[24] Trung Quoe Luong, Xinbo Zhang, Zhanming Jie, Peng Sun, Xiaoran Jin, and Hang Li. Reft: Reasoning with reinforced fine-tuning, arXiv preprint arXiv:2401. 0.9667, 3, 2024.
[25] Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Perey Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling. arXiv preprint arXiv:2501.19393, 2025.
[26] NVIDIA Corporation. Nvidia nsight systems, 2025. URL https::/ddeelloprr.vvve .vidia
com/ hom//siightssysteen
Accessed: 2025-04-15.
[27] Skywork ol Team. Skywork-ol open series, 2024. URL https://nuggingface co/
Skywork
[28] OpenAL. Gpt-4 technical report. arXiv:2303.08774 [cs.CL].
2023.
[29] Amrith Setlur, Chirag Nagpal, Adam Fisch, Xinyang Geng, Jacob Eisenstein, Rishabh Agarwal, Alekh Agarwal, Jonathan Berant, and Aviral Kumar. Rewarding progress: Scaling automated process verifiers for Ilm reasoning. arXiv preprint arXiv:2410.08146, 2024.
[30] Wenlei Shi and Xing Jin. Heimdall: test-time scaling on the generative verification. arXiv preprint arXiv:2504. 10337, 2025.
[31] Nishad Singhi, Hritik Bansal, Arian Hosseini, Aditya Grover, Kai-Wei Chang, Marcus Rohrbach, and Anna Rohrbach. When to solve, when verify: Compute-optimal problem solving and generative verification for Ilm reasoning. arXiv preprint arXiv:2504.01005. 2025.
[32] Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling I1m test-time compute opti- mally can be more effective than scaling model parameters. arXiv preprint 2rXhv:2408.03311, 2024.
[33] DeepSeek Team et al. Deepseek-rl: Incentivizing reasoning capability in Ims via reinforcement learning. https://arxiv. http:p::/aaaxi..og/abbbb.s/ wwtp://w..w.ww///.....////// 12948 2025. arXiv:2501. 12948 [cs. CL).
[34] Pablo Villalobos, Anson Ho, Jaime Sevilla, Tamay Besiroglu, Lennart Heim, and Marius Hobbhahn. Will we run out of data? limits of Il scaling based on -aman-generated data. arXiv preprint arXiv:2211.04325, 2022.
[35] Jun Wang, Meng Fang, Ziyu Wan, Muning Wen, Jiachen Zhu, Anjie Liu, Ziqin Gong, Yan Song, Lei Chen, Lionel M Ni, et al. Openr: An open source framework for advanced reasoning with large language models. arXiv preprint arXiv:2410.09677 2024.
12

---

[36] Teng Wang, Zhangyi Jiang, Zhenqi He. Wenhan Yang, Yanan Zheng, Zeyu Li, Zifan He, Shenyang Tong, and Hailei Gong. Towards hierarchical multi- step reward models for enhanced reasoning in large language models. arXiv preprint arXiv:2503: /3551, 2025.
[37] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11177 2022.
[38] Wikipedia. Infinite monkey theorem. URL /ttpt/////////....oooooo.o.////a thnkey_theorem
[39] Wei Xiong, Hanning Zhang, Nan Jiang, and Tong Zhang, An implementation of generative prm. https://githen com RoHHFot/RLHF-RRR -ee-ll--ewwarddd-dedeeee--
2024.
[40] An Yang. Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412. 15 2024.
[41] Edward Yeo, Yuxuan Tong, Morry Niu, Graham Neubig, and Xiang Yue. Demystifying long chain-of-thought reasoning in Ilms, 2025.
h5tp://ww..rrg/bbb/5....... 03373
[42] Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35:15476-15488, 2022.
[43] Qiyuan Zhang, Fuyuan Lyu, Zexu Sun, Lei Wang, Weixu Zhang, Zhihan Guo, Yufei Wang, Irwin King, Xue Liu, and Chen Ma. What, how, where, and how well? a survey on test-time scaling in large language models. arXiv preprint arXiv:2503.24433. 2025.
[44] Jian Zhao, Runze Liu, Kaiyan Zhang, Zhimu Zhou, Junqi Gao, Dong Li, Jiafei Lyu, Zhouyi Qian, Biqing Qi, Xiu Li, et al. Genprm: Scaling test-time compute process reward models via generative reasoning, arXiv preprint 20XX::250040009,,, 2025.
13

---

A Appendix
A.1 Optimal Compute Allocation between Proposer and Verifier
Optimizing the allocation of computational resources between proposers and verifiers is crucial for maximizing overall system performance. While previous work [31] under fixed compute budget has primarily focused on varying the ratio of samples generated by the proposer to those evaluated by the verifier, the impact of asymmetric model capabilities- ceciiiiiees-sssiicallllll specifically, how distributing model parameters differently between the proposer and verifier affects performance- has remained largely unexplored. This section addresses this gap by investigating the optimal allocation of model parameters between these components, while adhering to constant total compute budget, to determine how performance scales with their relative complexities.
We evaluate two configurations: Small Proposer, Large Verifier (S-P, L-V) and Large Proposer, Small Verifier (L-P, S-V), using DVTS and Beam Search. Performance is measured by accuracy against the number of samples (ri on tasks of varying difficulty (Level I, Level 5) and averaged (Figure (6)
Level 1
Level
Average Accuracy
100
80.0
77.5
98
Accuracy (%)
Accuracy (%6
75.0
96
72.5
88
67.5
92
65.0
62.5
22
Number of samples (n)
Number of samples (n)
Number of samples (n)
SP.VV
LP.
(a) DVTS
Level
Level
Average Accuracy
100
90
Accuracy (96)
Accuracy (%6
96
Accuracy
72
88
94
70
86
66
64
22
2'
2
2
2'
2'
2'
2
2
27
2'
2
2 2'
2
Number samples
Number samples
samples (n)
SR,
LP,, S.V
(b) Beam Search
Veriffer Figure 6: Comparison of Proposer- Verifier configurations under (a) DVTS and (b) Beam Search strategies. Accuracy (%) is plotted against the number of samples (n) for Level Level 5, and Average Accuracy. Blue line: Small Proposer, Large Verifier (S-P, L-V). Orange line: Large Proposer, Small Verifier (L-P, S-V).
Key observations include:
Verifier Quality Dictates Scaling: With both DVTS and beam search (Figure 6), L-P, S-V starts strong on easier tasks but scales poorly with more samples (n1), especially on harder tasks, suggesting that more samples without effective verification is counterproductive. S-P, L-V shows more robust scaling, indicating a strong verifier better utilizes increased compute for broader exploration. A weak verifier bottlenecks the scaling.
14

---

Strategy Determines Optimal Configuration: The best Proposer- Verifier pairing is strategy- dependent. For DVTS, S-P, L-V generally achieves higher peak performance or scales better for complex tasks. For Beam Search (Figure L.PP, S-V consistently and significantly outperforms. DVTS's diverse exploration of the solution space benefits more from a strong verifier, making simpler proposer adequate.
Task Difficulty Modulates Preference: On easier tasks (Level 1), S-P, L-V can be competitive, probably because the proposer's performance is not a bottleneck for easier tasks. However, for harder tasks (Level 5), a strong proposer becomes more critical for beam search.
These results highlight that optimal compute allocation between proposer and verifier not fixed but depends the search strategy, task complexity, and available budget. The observation motivates more advanced compute allocation between verifiers and proposers.
A.2 FLOPs Calculation using the Cost Model
Following prior work [1], for discriminative PRMs, we assume that Cy 2P... since the verifier outputs single score per evaluation. Under this assumption, Equation simplifies Simplifesss to:
L Gotal 2 Bi
B2) ...))Pp-. 1 B2 P.).
1
g
where L is the average solution length in generation steps, T is the average number of tokens per generation step. To simplify compute tracking across experiments, define normalized compute proxy:
C(g. B2) X B1 (g 1 B2) B1 B2
where X = T-Pa P. captures the relative cost of generation versus verification. This proxy is proportional to the actual total compute budget and is used throughout all experiments in the paper.
A.3 Experiment Details for VG-Search
Experiment Setup.
To investigate the optimal for a given difficulty level and computational budget, conduct experiments assessing both the oracle and the validation- tuned accuracies for the CM-g
and AM-g strategies. We use Qwen2.5-Math-77 [40] as proposer, and Skywork-ol-1.511 [27] as verifier. The number of generations is
E {4, 16, 64, 128, 256), with Branch-Out Factor B2 = 4, temperature 0.8, and Top-p 1.0. For each generation step, the maximum token number is set to 2, 048, employing Last scoring and majority voting. The number of iterations T corresponds g: for E {1, 2, 3, 4}, we set / E {12, 6, 4, 3} to ensure equal compute budget. The prompt template from Qwen [40] adopted. DVTS, Best-of-N (BoN), and Beam Search are used baselines, configured with the same parameters as VG-Search.
Prompt Template for Qwen:
(question}
Please reason step by step, and put your final answer within \boxed(]
For ideal accuracy, we search for optimal g in test dataset for every combination of number of genera- tions and difficulty level, and compute two accuracies for each number of generation: unweighted and weighted, the former corresponds to the dataset having equal number of questions in different difficulty levels, and the latter corresponds to actual difficulty distribution in the dataset. For the searched accuracy, the only difference is that we search g in the validation dataset, and obtain the accuracy in the test dataset for searched g.
Baselines and Voting Methods. Our codebase is based on HuggingFace's es search-and-leant [4.
We adopt three mainstream TTS strategies: Best-of-N [5), Beam Search (32), and DVTS 44. For all strategies we explore the number of samples of 4, 16, 64, 128, and 256. For Beam Search and DVTS, we use fixed Branch-Ou Factor B2 following 33). For all strategies, we use majority voting 37]. Temperature is set to 0.8 for all problems following HuggingFace's setup.
15

---

Hardware and Frameworks. We conduct our experiments on NVIDIA H100 [2 and A100 [ GPUs, using CUDA 12.8 Ubuntu 22.04. The vLLM library (v0.6.3) [8] is employed for model execution. The experiments for VG-Search on MATH-500 take from to 5 hours, depending on the candidate number. To obtain accurate system-level runtime measurements, we use Nsight Systems [26] and employ the NVIDIA NVTX [13 extension to categorize execution time across different models. For the latency measurement in Figure Ic we use Qwen2.5-Math-I..5 as generator, while using MLHFloo/Llamman 1-
------------e---------- PRM-Deepseek-DEe Data the verifier.
A.4 Evaluation with an Ensemble Verifier
To broaden the scope of our evaluation, we conducted additional experiments using a multi-verifier ensemble. This approach can enhance verification quality by aggregating signals from diverse models [20]. For these experiments, we used Qwen-2.5-Matt-LL.5t as the generator. The verifier was an ensemble of two different Process Reward Models (PRMs): Skywork-1.5B [27] and RLHFlow's Llama3.1-8B-P
[39]. The final verification score for each reasoning step was computed by averaging the scores from these two models.
The results. presented Table align with and reinforce the main conclusion of our paper. We observe that the optimal verification granularity (g) is dynamic and highly dependent the compute budget (i.e., the number of generations, v)). While dense verification (g 1) sometimes preferable at low sample counts, sparser verification (g > 1) consistently achieves the highest accuracy on both the MATH-500 and AIME datasets the compute budget increases. This confirms that our findings on adaptive verification granularity generalize even when using stronger, ensembled verifier.
MATH-500 (%)
AIME
(%)
g=1
g=2
g=3
g=4
g=1
g=2
g=3
g=4
4
76.0
73.2
71.6
69.6
12.22
8.89
11.11
13.33
16
80.0
77.4
76.4
78.4
13.33
13.33
16.67
14.44
64
79.4
80.4
80.8
81.0
16.67
16.67
16.67
18.89
128
80.8
82.2
82.2
80.8
15.56
24.44
23.33
18.89
256
80.2
80.0
80.2
81.2
23.33
23.33
23.33
23.33
Table 3: Accuracy of VG-Search with ensemble verifier across MATH-500 and AIME datasets. For each number of generations (n), the highest accuracy in each row is bolded, indicating the performance achieved at the optimal granularity g.
A.5 Applicability to Tasks with Outcome-Leeve Feedback
VG-Search is applicable to tasks with outcome-level feedback, provided PRM can be trained on intermediate generation steps. In such scenarios, the core search algorithm remains unchanged. However, for open-ended generation tasks like code synthesis where outputs are diverse, standard majority voting is not feasible for final answer selection. A practical alternative is to select the single candidate trajectory with the highest cumulative or final PRM score.
To demonstrate this, we evaluated VG-Search on the HumanEval benchmark using LLaMA-3.2- 1B as the generator and Skywork-o1-1.5B-PRR as the verifier. We used newline characters to delimit generation steps. The results, reported as pass @ scores in Table 4 show that sparser verification (g > 1) can outperform dense verification (g 1), particularly as the compute budget (n) increases. This confirms that our central conclusion-thor the optimal verification granularity is to open-ended generation tasks.
A.6 Standard Deviation with Multiple Trials
To evaluate the robustness of our results, we conducted experiments over multiple trials using different random seeds. This analysis provides more rigorous assessment of variance and confirms the stability of our conclusions. The following results were generated using the Qwen-Math-7B generator and the Skywork-ol-1.5B PRM on the MATH-500 dataset, averaged over three distinct runs.
16

---

g=1
g=2
g=3
g=4
0.250
0.274
0.238
0.220
16
0.335
0.305
0.268
0.311
64
0.256
0.335
0.274
0.305
Table 4: Pass@1 scores on HvmanBval using VG-Search, selecting the highest-scoring candidate. The best performance for each compute budget (n) is bolded.
Table shows the mean accuracy and standard deviation for this experiment. The results from multiple trials are consistent with our original findings, demonstrating the stability of the observed trends. The low standard deviations across all configurations reinforce this conclusion. While dense verification (g 1) performs well at smaller compute budgets, sparser verification (g > 1) consistently achieves higher accuracy as the number of samples increases (n 2 64).
g=1
g=2
g=3
g=4
4
84.13 + 0.50
82.27 + 0.24
81.73
0.39
80.40 0..3
16
86.80 + 0.28
86.13 + 0.22
86.13 + 0.25
86.40 + 0.16
64
86.20 + 0.33
87.27 + 0.15
88.27 + 0.34
87.87 + 0.19
128
86.67
+ 0.19
87.60 + 0.57
88.27
0.21
88.47 0.32
256
86.67 + 0.19
87.93 + 0.34
89.13 + 0.27
88.73 + 0.19
Table 5: Mean accuracy + standard deviation over 3 runs with different seeds on MATH-500. The highest mean accuracy for each sample count (n) bolded.
A.7 Limitations
While our proposed adaptive strategies to optimize the verification granularity g based on overall problem characteristics like difficulty and compute budget, key limitation is that the chosen remains fixed throughout the generation process for a single problem instance. This approach does not account for potential variations in reasoning complexity generator confidence within different stages of solving a single problem. more sophisticated approach, potentially offering further efficiency gains, would involve dynamically adjusting the granularity g step-by-step basis during inference, adapting verification frequency based on real-time signals. Developing such fine-grained, intra-problem adaptive granularity remains important direction for future research.
17

---

A.8 Case Study of VG-Search
Question:
Compute: 4 +.............
2.4
campute the sum
compute the sum 2
2-33 3 4 + 5-
the
problem
can
99 100
group pairs.
sueuecce
group
peries. The perits altornates
dbserve the patrirn in the
into amaller, manages parts.
between adaing and
score: 0.9942
tokens
cuberacting g consecutive the terms in pains to simplify the calculation
0.9894
integers We can
64 takens score: 0,9965
(1 2)
+
4)
+
(5 6)
4) (00 100)
(3
(5 6)
H-..- (90 100)
[36 cobens
(36 takens
Each consecutive
Each pair (2k 1)
1,2...., Simpiffies Therefore, the of is: 151 tokens
there the
ends at 100, and each
pair of two
the number of pairs cakana
(-11 (-1)+((1)
-1+ tokens score: 0.9776
100
# (-1) (80 timoss
2
tokene poore: 0,9813
tokens score: 0.9996
(duplicated)
This is equivaient to: 7 tokens
Therefore, the sum of the peries is: (f tokens
-1 50
-50
50 x (-1) -00
16 tokens
16 tokens
Thus, the value the -2 3 -1-- 4+5
Sa, the value of the sum
So. the value of the 2 5-11- 1+5 -... 100
1-2+3 -1+ tokens score: 0.9991
tokens
is 50
tokens score: 0.9963
tokens score: 0.9991
50 tokena score: 0.9966
Answer:
50
Figure 7: A case study of VG-Search. =, B2 2, 3
18

---

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: Our abstract and introduction accurately reflect the paper's contributions, evidenced by the following sections.
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 not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
See Appendix A.7
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 sell-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: [NA]
19

---

Justification:
Our work does not include theoretical results.
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 reproducibility
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 our code as the supplementary material, as well as experi- ment details and instructions.
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?
20

---

Answer: [Yes]
Justification: We have provided our code as the supplementary material, as well as experi- ment details and instructions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is 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 to reproduce the results. See the NeurlPS code and data submission guidelines (https
wtt.ggiddde/eeSSSuunnrnn ssionlolicy) for more details. hetpolliicggiddeeCoooooo
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
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 our code as the supplementary material, as well experi- ment details and instructions. We also describe experiment details.
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 a 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, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification: Our main results do not contain randomness as fixed the seed.
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, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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).
21

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables 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 the text how they were calculated and reference the corresponding figures 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: See Appendix A.3
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 as well as 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 't make it 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
Answer:
[Yes]
Justification:
We conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact 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.
22

---

The conference expects that many papers will be foundational research and not tied 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 an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
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: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses 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 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have made the citations.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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, paperswi thcode. com com/datasets 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 it has changed) should be provided.
23

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: They are well documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is 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. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We do not use LLMs for method development.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy hattps://neuripe: o / for what should or should not be described.
25


Reviews:
[{"review_id": "glbKLDGTnb", "reviewer": "Reviewer_SNq5", "summary": "This paper proposes Variable Granularity Search (VG-Search), a verifier-guided decoding algorithm that introduces a tunable granularity parameter g to control how often a reward model is queried.\nIt groups candidate sequences into segments, queries the verifier only at segment boundaries, and enables budget-aware tuning of verification frequency.\nExperiments on MATH-500, AIME, and a validation subset shows that the optimal g depends on compute budget and generator-verifier strength; an adaptive strategy gains up to 3.1 pp accuracy over beam search and 3.6 pp over Best-of-N while cutting FLOPs by more than 52%.", "questions": "Q1: How would VG-Search handle tasks that supply only outcome-level natural-language feedback rather than deterministic unit tests?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Proven scaling and effective extended framework. VG-Search generalizes two popular test time scaling methods with a single hyperparameter and supplies an explicit FLOPs model, enabling great trade-off analysis across budgets and model pairs.\n2. Complete and comprehensive evaluation. The study sweeps g, branch factor, verifier size, task difficulty, and sample count, and validates both compute savings and accuracy gains with clear ablations and an adaptive policy that outperforms strong baselines on multiple datasets.\n3. Detailed design analysis via experiments. The profiling further reveals that strong generators prefer sparse verification whereas weaker ones need dense checks, and that investing saved compute in a larger verifier is more beneficial than raising the branch factor.\n\nWeaknesses:\n1. This paper just names its checker “Skywork-o1 PRM” and states it keeps the last score, but it never tells its model size, training data, or prompt, making the speed and bias unclear.\n2. No comparison with alternative verification paradigms. Although the related-work section recognises outcome-level verifiers, step-wise PRMs, generative PRMs and multi-verifier ensembles, the experiments test just a single discriminative PRM. Nevertheless, it's still positive to observe the test-time scaling on it.", "was_revised": true, "final_justification": "Dear authors, Thanks for the response! After reading the rebuttal, I feel more confident in the strengths of the paper. I updated my score to 5.", "rebuttal": "We thank the reviewer for the helpful feedback. We will clarify your doubts as follows.\n\n> Q1: More details on the PRM\n\nWe thank the reviewer for the suggestion and will include the requested details in the revised version of the paper. As cited in lines 152–154, the Skywork-o1 PRM used in our experiments is taken from [1]. Specifically, we use the 1.5B and 7B variants: *Skywork-o1-Open-PRM-Qwen-2.5-1.5B* and *Skywork-o1-Open-PRM-Qwen-2.5-7B*. For detailed training information, please refer to [1]. Our prompt for Llama models follows [2], and our prompt for Qwen models is stated in line 494 of the appendix.\n\nWe will ensure that the description of the PRM is made clearer and more prominent in the next version.\n\n[1] He, Jujie, et al. Skywork-O1 Open Series. 2024.  \n[2] Edward Beeching, Lewis Tunstall, and Sasha Rush. Scaling test-time compute with open models. 2024.\n\n> Q2: Comparison with alternative verifiers\n\nTo enrich our evaluation scope, we included additional experiments with multi-verifier ensemble [3], as mentioned by the reviewer. We used the Qwen-2.5-Math-1.5B as a generator and an ensemble of two different verifiers (Skywork-1.5B and RLHFLow’s LLAMA3.1-8B-PRM) by averaging their scores.\n\n| n | Optimal g (MATH-500) | Top Accuracy (MATH-500) | Optimal g (AIME) | Top Accuracy (AIME) |\n| :---- | :---- | :---- | :---- | :---- |\n| 4 | 1 | 76.0 | 4 | 13.33 |\n| 16 | 1 | 80.0 | 3 | 16.67 |\n| 64 | 4 | 81.0 | 4 | 18.89 |\n| 128 | 3 | 82.2 | 2 | 24.44 |\n| 256 | 4 | 81.2 | 4 | 23.33 |\n\nA complete table of results:\n\n| n | MATH-500 |  |  |  | AIME |  |  |  |\n| :---: | ----: | ----: | ----: | ----: | ----: | ----: | ----: | ----: |\n|  | **g \\= 1** | **g \\= 2** | **g \\= 3** | **g \\= 4** | **g \\= 1** | **g \\= 2** | **g \\= 3** | **g \\= 4** |\n| 4 | **76.0** | 73.2 | 71.6 | 69.6 | 12.22 | 8.89 | 11.11 | **13.33** |\n| 16 | **80.0** | 77.4 | 76.4 | 78.4 | 13.33 | 13.33 | **16.67** | 14.44 |\n| 64 | 79.4 | 80.4 | 80.8 | 81.0 | 16.67 | 16.67 | 16.67 | **18.89** |\n| 128 | 80.8 | **82.2** | **82.2** | 80.8 | 15.56 | **24.44** | 23.33 | 18.89 |\n| 256 | 80.2 | 80.0 | 80.2 | **81.2** | **23.33** | **23.33** | **23.33** | **23.33** |\n\nWe observe that the results align with our conclusion: the optimal verification granularity $g$ is dynamic. While dense verification ($g$=1) is sometimes best at lower sample counts, sparser verification ($g$ > 1) consistently achieves top performance on both datasets as the compute budget (n) increases.\n\nRegarding other paradigms, outcome-level methods like ORM are not suitable for our experiments, which require step-level verification. As noted in the paper, we deferred comparison with generative PRMs due to their verification inefficiency under matched compute budgets and the limited availability of open-source models, though we agree this remains an important direction for future work.\n\nWe will incorporate the new ensemble results and this discussion into the final manuscript to better address the scope of verification paradigms. Thank you for helping us strengthen the paper.\n\n[3] Lifshitz S, McIlraith SA, Du Y. Multi-agent verification: Scaling test-time compute with multiple verifiers. 2025.\n\n> Q3: How does VG-Search handle tasks that provide outcome-level feedback?\n\nFor tasks with outcome-level natural language feedback, if a PRM can be trained on intermediate generation steps, VG-Search remains directly applicable. The main difference lies in selecting the final answer, as majority or weighted majority voting isn’t feasible due to the open-ended nature of outputs. A practical alternative is to select the candidate with the highest PRM score. To illustrate this, we evaluated VG-Search on HumanEval using LLaMA-3.2-1B as the generator and Skywork-o1-1.5B-PRM as the verifier, with newline characters serving as the step delimiter.\n\n|  | $g$=1 | $g$=2 | $g$=3 | $g$=4 |\n| :---- | :---- | :---- | :---- | :---- |\n| n=4 | 0.250 | **0.274** | 0.238 | 0.220 |\n| n=16 | **0.335** | 0.305 | 0.268 | 0.311 |\n| n=64 | 0.256 | **0.335** | 0.274 | 0.305 |\n\nThese results support our main conclusion: **$g$=1 is not always optimal**, and with increased compute budget, **sparser verification granularity tends to perform better**. This proves the generalizability of our conclusion on optimal verification granularity to open-ended tasks."}, {"review_id": "TnPudxZjCz", "reviewer": "Reviewer_vtyM", "summary": "The paper makes the observation that the two most prominent Test-Time-Scaling methods, Beam Search, and Best-Of-N, can be unified into a single framework, where the “granularity” (or frequency of verification steps) is varied. Beam Search invokes the verifier at each step (granularity 1), and Best-Of-N invokes the verifier at the end of each generation. The paper very reasonably questions whether a verification frequency between the two might yield more cost effective TTS, and introduces VG-Search, which parametrizes the granularity. The main findings are that stronger generators, easier tasks, and larger sample budgets tolerate higher granularity.", "questions": "- Could you give more detail on how a dynamic adjustment of granularity might be implemented? For instance, could the verifier's confidence score on a partial solution be used as signal to determine he length of the next generation segment before the next verification?\n- Your experiments are focused on mathematical reasoning. How do you expect your findings on optimal verification granularity to generalize to other domains, such as creative writing, code generation, or long-form question answering?\n- The analysis assumes an accurate Process Reward Model (PRM). How would the best granularity change if the verifier itself is noisy or poorly calibrated?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper addresses a novel and significant aspect of verifier-guided test time scaling, which is the frequency of verification steps (granularity.) It frames existing methods (Beam-Search and Best-Of-N) as two extremes of a unified perspective, and introduces VG-Search to interpolate between the methods.\n- VG-Search gives a practical way to improve the accuracy-compute trade-off, with up to a 3.6% accuracy gain or a 52% reduction in FLOPs.\n\nWeaknesses:\n- The \"atomic unit\" of generation and verification is based on newline characters, whereas it may be useful to consider more semantically meaningful notions of a \"step\" (this is acknowledged by the authors.)\n- Beyond varying granularity by task difficulty, it would be interesting to consider varying granularity dynamically during execution of a task or within a generation process.", "was_revised": true, "final_justification": "Thank you to the authors for the thoughtful rebuttal and followup experiments. I will keep my score (5) of Accept.", "rebuttal": "We appreciate the reviewer’s thoughtful feedback and will clarify the points of confusion as follows.\n\n> Q1: Semantically relevant notion of a “step”\n\nWe thank the reviewer for this insightful suggestion. We fully agree that defining a “step” based on semantic meaning is both valuable and promising—a perspective that also serves as the core motivation of this paper.\n\nFor this work, we adopted the newline character delimiter for the following reasons:\n\n1. **Comparability:** It follows the convention of prior work [1], allowing for a direct and fair comparison with existing methods.  \n2. **Motivation:** Our findings strongly support the reviewer's intuition. The key result that sparser verification (g\\>1) is often optimal suggests that the conventional newline-delimited \"thinking step\" is indeed too fine-grained and not always meaningful.\n\nIn essence, VG-Search with g\\>1 acts as a simple but effective method to create larger, more substantial steps by grouping the atomic newline-delimited ones. We see our work as providing the motivation and the framework for future research into more sophisticated, semantic-aware verification steps. \n\n\\[1\\] Snell, Charlie Victor, et al. \"Scaling LLM test-time compute optimally can be more effective than scaling parameters for reasoning.\" *The Thirteenth International Conference on Learning Representations*. 2025\\.\n\n> Q2: Varying granularity dynamically\n\nWe thank the reviewer for this thoughtful question. Dynamically adjusting the verification granularity $g$ during generation is a promising direction for future work, as mentioned in our Limitation section, and we are happy to share our thoughts and preliminary findings on how this could be implemented.\n\nFollowing your suggestion, we investigated the relationship between the verifier's confidence (in this case, its score on the current step) and the magnitude of the score change on the subsequent step.\n\n**Our results show a clear inverse correlation:** the higher the verifier's confidence in the current step, the smaller the expected score change for the next step.\n\n| Verifier Confidence | 0-0.2 | 0.2-0.4 | 0.4-0.6 | 0.6-0.8 | 0.8-1 |\n| :---- | ----: | ----: | ----: | ----: | ----: |\n| Avg. consecutive-step Δscore | 0.290 | 0.274 | 0.190 | 0.110 | 0.020 |\n\nBased on this finding, a dynamic strategy could be implemented as follows:\n\n* Use a **larger verification granularity ($g$\\>1)** when verifier confidence is high, saving compute when the path is stable.  \n* Use a **denser verification ($g$=1)** when confidence is low to catch potential errors immediately.\n\nWhile a full evaluation is an exciting direction for future work, we will include this preliminary analysis and discussion in the revised version. Thank you for helping us improve the paper.\n\n> Q3: Open-ended questions performance\n\nWe focus on mathematical reasoning tasks in this paper to stay comparable with prior work \\[1\\] and because most open-source PRMs are trained primarily on MATH. To test the generalizability of our conclusions beyond this domain, we applied VG-Search to HumanEval using LLaMA-3.2-1B as the generator and Skywork-o1-1.5B-PRM as the verifier, using newline characters as step delimiters.\n\n|  | $g$=1 | $g$=2 | $g$=3 | $g$=4 |\n| :---- | :---- | :---- | :---- | :---- |\n| n=4 | 0.250 | **0.274** | 0.238 | 0.220 |\n| n=16 | **0.335** | 0.305 | 0.268 | 0.311 |\n| n=64 | 0.256 | **0.335** | 0.274 | 0.305 |\n\nThese results reinforce our main conclusion: **$g$=1 is not always optimal**, and with increased compute budget, **sparser verification granularity tends to perform better**. This demonstrates the applicability of our findings to open-ended code generation tasks as well.\n\n\\[1\\] Snell, Charlie Victor, et al. \"Scaling LLM test-time compute optimally can be more effective than scaling parameters for reasoning.\" *The Thirteenth International Conference on Learning Representations*. 2025\\.\n\n> Q4: Change of the best granularity with a noisy PRM\n\nWe thank the reviewer for this insightful question about how verifier quality affects the optimal granularity. \n\nTo investigate this, we conducted a \"worst-case\" ablation study where the verifier was maximally \"noisy and poorly calibrated\"—it was a **purely random PRM** that assigned a random score to each step. We tested this with both our 1.5B and 7B generators.\n\nResults on MATH-500\n\n| n | Qwen-1.5B |  |  |  | Qwen-7B |  |  |  |\n| :---- | ----: | ----: | ----: | ----: | ----: | :---- | :---- | :---- |\n|  | **$g$=1** | **$g$=2** | **$g$=3** | **$g$=4** | **$g$=1** | **$g$=2** | **$g$=3** | **$g$=4** |\n| 4 | 71.4 | 70.8 | 68.4 | **71.8** | 74.8 | 76.2 | 78.2 | **78.6** |\n| 16 | 68.0 | 73.2 | **73.8** | 73.2 | 78.8 | 79.6 | 77.8 | **80.6** |\n| 64 | 76.0 | 78.6 | 78.2 | **79.4** | 80.6 | 82.0 | 84.0 | **85.0** |\n| 128 | 77.4 | 78.4 | 79.0 | **80.4** | 80.0 | 84.4 | **85.8** | 85.4 |\n| 256 | 78.8 | 79.8 | 79.2 | **81.0** | 80.6 | 85.0 | 86.4 | **86.4** |\n\nResults on AIME\n\n| n | Qwen-1.5B |  |  |  | Qwen-7B |  |  |  |\n| :---- | ----: | :---- | :---- | :---- | ----: | ----: | :---- | :---- |\n|  | **$g$=1** | **$g$=2** | **$g$=3** | **$g$=4** | **$g$=1** | **$g$=2** | **$g$=3** | **$g$=4** |\n| 4 | 8.9 | 5.6 | 8.9 | **11.1** | 10.0 | **10.0** | 7.8 | 8.9 |\n| 16 | 11.1 | **12.2** | 6.7 | 11.1 | 12.2 | **20.0** | 11.1 | 13.3 |\n| 64 | 6.7 | 8.9 | 11.1 | 11.1 | 12.2 | 15.6 | **17.8** | 16.7 |\n| 128 | 12.2 | **14.4** | 11.1 | 11.1 | 13.3 | 15.6 | 15.6 | **17.8** |\n| 256 | 12.2 | 10.0 | 13.3 | **13.3** | 16.7 | 16.7 | **17.8** | 16.7 |\n\nOur hypothesis was that a noisy verifier would favor sparser checks to avoid corrupting the search with bad guidance. The results strongly confirm this intuition. Across both models and datasets, when the verifier provides no useful signal, **the optimal strategy consistently shifts to sparser verification (g \\> 1\\)**.\n\nIn essence, with an unreliable verifier, the best strategy is to trust the generator more and the verifier less. VG-Search with a larger g naturally adapts to this by shifting the search strategy away from fine-grained guidance and towards a more robust Best-of-N style exploration."}, {"review_id": "Mziis5fYG1", "reviewer": "Reviewer_RT2j", "summary": "This work studies LLM test-time scaling for reasoning tasks by repeated sampling and verification.\nThe authors argue that dense verification in standard beam search can be wasteful,\nand propose a generalized variant that allows verification at variable granularity:\nfor each branch, generate $g \\ge 1$ steps before verification and pruning.\nEmpirical results confirm that higher accuracy and efficiency can be achieved by selecting the granularity properly.", "questions": "None", "limitations": "Yes, the authors discussed in Appendix A.4 that the hyperparameter g (granularity) is chosen once (e.g., by optimizing performance on a validation set) and then fixed throughout at inference time.\nFinding a way of adaptively setting this hyperparameter may require further work.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n* The proposed method is sensible, simple yet effective.\n* The empirical results are promising.\n* The overall writing is clear.\n* There are some good explanations, intuitions and insights, for example:\n    * The authors spot redundant verification in beam search, as shown in Figure 1;\n    * Lines 168 - 184 explain why stronger generators can benefit more from sparse verification;\n    * Lines 202 - 213 explains why dense verification at each step is likely sub-optimal.\n\n\n**Weaknesses:**\n\nThere is room for improvement in experiments, for example:\n\n* Empirical evaluation is done with limited model scale, up to 7B. Nonetheless, the rationale of the proposed method seems to hold regardless of model scale.\n* Each experimental result is obtained with a single trial, rather than averaged over multiple independent trials. As a result, some curves are a bit messy (e.g., Fig 1(d) and Fig 3), and small differences (e.g., 1% in accuracy) might be partially due to randomness of experiments.\n* A related issue is that, for Question 7 in the checklist regarding statistical significance, the authors say \"Our main results do not contain randomness as we fixed the seed\". This is obviously not a valid argument (as the choice of seed itself can be random); otherwise, any empirical study can refrain from running multiple trials and reporting statistical significance, by the same argument.\n\n\nNonetheless, it is understandable that computational costs can be high for additional experiments with larger model scales or larger number of trials.", "was_revised": true, "final_justification": "The authors have addressed my concerns, and I would maintain my rating.", "rebuttal": "We appreciate the reviewer’s thoughtful feedback and will clarify the points of confusion as follows.\n\n> Q1: Scaling model sizes\n\nTo enrich the evaluation scope with additional model scales, we conducted experiments using a larger model **Qwen-2.5-14B-Instruct**, paired with the Skywork-o1-7B PRM. Given the time constraints of the rebuttal period, we prioritized this 14B model.\n\nOur new findings, summarized below, align well with our paper's main conclusions:\n| n | Optimal g (MATH-500) | Top Accuracy | Optimal g (AIME) | Top Accuracy |\n| :---- | :---- | :---- | :---- | :---- |\n| 4 | 1 | 81.6 | 1 | 11.11 |\n| 16 | 3 | 84.2 | 2 | 13.33 |\n| 64 | 1 | 86.6 | 4 | 17.78 |\n| 128 | 4 | 87.0 | 2 | 18.89 |\n| 256 | 2 | 87.2 | 3 | 20.00 |\n\nHere is a complete table of results:\n\n| n | MATH-500 |  |  |  | AIME |  |  |  |\n| ----- | ----: | ----: | ----: | ----: | ----: | ----: | ----: | ----: |\n|  | **g \\= 1** | **g \\= 2** | **g \\= 3** | **g \\= 4** | **g \\= 1** | **g \\= 2** | **g \\= 3** | **g \\= 4** |\n| 4 | **81.6** | 76.7 | 77.0 | 76.6 | **11.11** | 10.00 | 8.89 | 6.67 |\n| 16 | 83.6 | 82.8 | **84.2** | 81.2 | 12.22 | **13.33** | 10.00 | 10.00 |\n| 64 | **86.6** | 85.4 | 86.2 | 84.2 | 14.44 | 13.33 | 13.33 | **17.78** |\n| 128 | **87.0** | 85.40 | 84.20 | **87.0** | 15.56 | **18.89** | 14.44 | 14.44 |\n| 256 | 86.4 | **87.2** | 86.2 | 86.8 | 18.89 | 15.56 | **20.00** | 15.56 |\n\nThese results confirm that our main conclusion holds at a larger scale. Specifically, we observe that the optimal verification granularity varies with the number of samples, with larger sample sizes favoring sparser verification. This reinforces our central claim that the optimal granularity is dynamic and not fixed at $g$=1.\n\nWe will integrate these new 14B-scale results into the main body of the paper to strengthen our empirical evaluation. If the reviewer believes that further experiments with models of specific sizes would be valuable for the final version, we would be happy to include them.\n\n> Q2: Multiple trials of experiments\n\nWe thank the reviewer for the suggestion to include results from multiple trials. We agree that this provides a more robust evaluation.\n\nFollowing this recommendation, we have conducted new experiments with multiple seeds to analyze the variance of our results. Below are the updated accuracies (mean ± std. dev. over 3 runs with different seeds) for the Qwen-Math-7B generator with Skywork-o1-1.5B PRM on the MATH-500 dataset.\n\n| n | $g$=1 | $g$=2 | $g$=3 | $g$=4 |\n| :---- | :---- | :---- | :---- | :---- |\n| 4 | 84.13 ± 0.50 | 82.27 ± 0.24 | 81.73 ± 0.39 | 80.40 ± 0.43 |\n| 16 | 86.80 ± 0.28 | 86.13 ± 0.22 | 86.13 ± 0.25 | 86.40 ± 0.16 |\n| 64 | 86.20 ± 0.33 | 87.27 ± 0.15 | 88.27 ± 0.34 | 87.87 ± 0.19 |\n| 128 | 86.67 ± 0.19 | 87.60 ± 0.57 | 88.27 ± 0.21 | 88.47 ± 0.32 |\n| 256 | 86.67 ± 0.19 | 87.93 ± 0.34 | 89.13 ± 0.27 | 88.73 ± 0.19 |\n\nThe results averaged over multiple runs confirm our original conclusions. While dense verification ($g$=1) is effective at lower compute budgets, sparser verification ($g$\\>1) consistently leads to higher accuracy as the compute budget increases (for n ≥ 64). The small standard deviations across runs also highlight the stability of these trends.\n\nWe will make our best effort to conduct additional multi-trial experiments in future versions to improve the robustness of our evaluation. If the reviewers would like to see multi-trial results for any specific experiments, we will do our best to include them."}, {"review_id": "W9dDHOM2n5", "reviewer": "Reviewer_jWiE", "summary": "The authors raise a new line of tuning during test-time compute inference for large language models: the frequency and strength of a *verifier*, which assigns a score to a reasoning step performed by an LLM (often from a pretrained reward model.) The authors demonstrate that existing methods of verification in TTC lead to a number of inefficiencies, most salient of which is a computational inefficiency where verification steps at too fine a granularity lead to wasted FLOPs with little information gain (since consecutive reasoning steps often highly correlate with correctness). To address this, the authors systematically analyze how varying verification granularities within their search technique, VG-Search, can impact computational efficiency and accuracy. The authors show that a granularity in-between every-step and once at the end often leads to the best performance in trading off compute available to the LLM itself v. the verifier. The authors also introduce adaptive VG-search, where compute or accuracy constraints can guide the search for the optimal verification granularity, and show that these found granularity values effectively trade off less compute or higher accuracy in comparison to existing (naive) methods.", "questions": "* Can you explain why rejected intermediate steps in beam search get expanded on in Fig. 2? I thought that rejected steps shouldn't be further expanded on by beam search.\n* The usage of the verifier is not fully clear to me (as mentioned in the intro and then again on line 67.) What threshold do you use to decide whether to accept or reject a reasoning step?\n* Can you provide more intuition in line 116 regarding the choice of the simpler algorithmic design: is it because some solutions just start out as incorrect and you want to catch these early?\n* Line 256: How does epsilon get selected? \n* See questions regarding section 5. Do the reported numbers don't report the computational overhead required during the g* search process?", "limitations": "The limitations are briefly spelled out in the appendix. One of the limitations discussed brings about the same (similar) point I made in my comments on Section 5.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n* I find that the introduction of the new axis of verification granularity is valuable as a standalone contribution and important in test-time compute optimization. This parameter is something that the community should focus on and bring into existing TTC optimization methods to further analyze and improve performance.\n* The paper is broadly quite well written and easy to follow. The contribution is straightforward, but I view this as a strength: an intuitive insight into further optimizing TTC can bring about expected and desired tradeoffs in compute and accuracy.\n* The experimental results do tell a good story that backs up the claims of the authors. I found especially interesting that there was not always a consistently best granularity in Figure 3 when fixing the strength of the generator which strongly motivates the methods developed in section 5.\n* Sections 3-4 (and most of 2) are very detailed and clear from a technical standpoint without becoming pedantic or unnecessarily rigorous.\n\nWeaknesses:\n* There are some details that still lead to confusion on my end that I'd like to have clarified (see questions section.)\n* I felt the toy example in line 74 is not the demonstrably best choice. With infinite monkeys, there is almost certainly a need for a very fine granularity when it comes to verification since they’ll probably get the next step wrong - perhaps a different example would more strongly motivate the need for a tradeoff.\n* Section 2.3 is not particularly insightful and could probably be condensed to just a few lines. it’s pretty easy to follow how a reduction of verifier calls can scale down test time compute.\n* The choice of generator and verifier pairings in section 4 don't make a ton of sense to me and I'd like to see more pairings. At the very least, seeing performance by the most performant generator paired with the most performant verifier would be valuable here.\n* The biggest issue I have is with section 5, which I think is much too short given its significance with respect to the rest of the paper and lacks many clarifying details. More analysis here would really strengthen the paper. Namely: how long do the AM-g and CM-g methods take to converge? What is the computational overhead of finding the optimal g* before actually deploying that on the test/validation set? I assume that the reported numbers are all after g* is actually found, but finding this g* always practical? Is it a fair comparison if these numbers don’t include that burn-in cost to find the optimal g*? And if the reported numbers don't report the computational overhead required during the g* search process, there should be a thorough discussion and analysis on when and how to use g* during actual execution. When do we reuse g* during live inference? When do we compute a new g*? Is it for each finetuned model? What if a finetuning dataset has subsets that may require different g*?\n\nMinor:\n* Lines 100-102: Variable names B1 and B2 are somewhat obscuring naming choices\n* The lead takeaway in line 168 isn't the most insightful. I'd instead lead with the takeaway regarding how different granularities are optimal across different pairings/baselines and characterize why this might be the case.\n\nOverall, I think the new line of insight presented by the authors is something that the NeurIPS and broader community should pay attention to. With that being said, I think the work can be greatly strengthened with additional clarity and analysis and my score will reflect that.", "was_revised": true, "final_justification": "The additional experiments and points raised by the authors to help clarify and further robustify the claims made in the paper are satisfactory to me and as such I will maintain my score.", "rebuttal": "We thank the reviewer for the helpful feedback and will clarify the points of confusion as follows.\n\n> Q1: Example of infinite monkey might not be the best choice for demonstration.\n\nWe appreciate your opinion. We agree with you that the infinite monkey problem does not represent the general scenario of verifier-guided search with capable LLMs.\n\nOur intention with this example, as we briefly touch on in the paper, is to motivate the importance of verification granularity that balances verification cost and exploration cost. The \"infinite monkey\" case illustrates this in its most extreme form. The rest of our paper then explores how the optimal balance of this trade-off shifts away from dense verification when the generator is not random but a powerful LLM.\n\nTo avoid confusion, we will revise this section to more clearly frame the example as a simplified illustration of this fundamental trade-off, explicitly stating that the optimal strategy changes for capable models.\n\n> Q2: Section 2.3 could have been shorter\n\nWe appreciate your opinion as a thoughtful reader. We will minimize the length of Section 2.3 in our next version to make it more information-dense and concise.\n\n> Q3: The motivation for the choice of generator and verifier pairings isn’t clear, and more pairings are needed \n\nWe agree that a more comprehensive set of pairings strengthens our claims. Our initial pairings were chosen to study the optimal granularity with comparable compute FLOPs. However, based on your feedback, we have conducted new experiments to provide a full grid analysis of generator and verifier strength.\n\nIn the next version of the paper, our main results will feature a complete set of pairings:\n\n* **Qwen-Math-1.5B \\+ Skywork-1.5B-PRM** *(New Experiment)*  \n* **Qwen-Math-7B \\+ Skywork-7B-PRM**  *(New Experiment, addressing your specific request)*  \n* **Qwen-Math-1.5B** \\+ **Skywork-7B-PRM**  *(Original Paper)*  \n* **Qwen-Math-7B** \\+ **Skywork-1.5B-PRM**  *(Original Paper)*\n\nResults on **Qwen-Math-1.5B \\+ Skywork-1.5B-PRM**\n\n| n | MATH-500 |  |  |  | AIME |  |  |  |\n| :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- |\n|  | **$g$=1**  | **$g$=2**  | **$g$=3**  | **$g$=4**  | **$g$=1**  | **$g$=2**  | **$g$=3**  | **$g$=4**  |\n| 4 | 73.8 | 75.2 | 71.4 | **73.90** | 11.11% | **11.11%** | **11.11%** | 8.89% |\n| 16 | **77.2** | 77.0 | 75.8 | 78.16 | 13.33% | **16.67%** | 11.11% | 12.22% |\n| 64 | **79.6** | 78.8 | 79.4 | 79.4 | 21.11% | 21.11% | **22.22%** | 16.67% |\n| 128 | 79.0 | 80.2 | **81.4** | 81.05 | 20.00% | 21.11% | **23.33%** | 22.22% |\n| 256 | 80.16 | **81.6** | 81.0 | 81.0 | 22.22% | **25.56%** | 23.33% | 22.22% |\n\nResults on **Qwen-Math-7B \\+ Skywork-7B-PRM**\n\n| n | MATH-500 |  |  |  | AIME |  |  |  |\n| :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- |\n|  | **$g$=1**  | **$g$=2**  | **$g$=3**  | **$g$=4**  | **$g$=1**  | **$g$=2**  | **$g$=3**  | **$g$=4**  |\n| 4 | **85.8** | 83.6 | 81.49 | 80.56 | **12.22%** | 11.11% | 11.11% | 7.78% |\n| 16 | 88.38 | **88.55** | 86.6 | 85.71 | 15.56% | 14.44% | 14.44% | **16.67%** |\n| 64 | **88.8** | 86.95 | 86.6 | 88.0 | 15.56% | **21.11%** | 18.89% | 15.56% |\n| 128 | 88.2 | 88.2 | **88.8** | 88.0 | **22.22%** | **22.22%** | 17.78% | 16.67% |\n| 256 | 88.6 | **88.6** | **89.0** | 87.8 | 18.89% | **24.44%** | 17.78% | 20.00% |\n\nAcross all four pairings, the data consistently shows that the optimal verification granularity is not fixed but is a dynamic parameter that depends on the intricate interplay among compute budget, task, and the specific generator-verifier pair. We also include results using Qwen-2.5-14B-Instruct as the generator in the response to Q1 of Reviewer RT2j.  \nThis comprehensive analysis will be integrated into the main results section of our revised paper, providing a much stronger empirical foundation for our claims. Thank you for helping us improve our work.\n\n> Q4: Clarity on Section 5\n\nThank you for emphasizing the importance of Section 5 and for your constructive questions. We agree that a deeper analysis of the adaptive strategies strengthens the paper and will clarify the settings and implementation details in the revision. Please see our responses below.\n\n> Q5: Convergence of AM-g and CM-g and computational overhead of finding optimal $g\\*$  \n\nTo clarify how many validation samples are needed to find a good granularity $g\\*$, we conducted a convergence analysis. We simulated finding $g\\*$ on subsets of our validation set (MATH-250) of increasing size and then evaluated the performance on the MATH-500 test set.\n\nOur findings show that the search for an effective $g\\*$ is highly sample-efficient and converges very quickly.\n\nThe tables below show the test accuracy for n=256 and n=64 as a function of the number of validation samples used to select $g\\*$.\n\nWhen **n=256**\n\n|  | 0 sample (Beam Search) | 5 samples | 100 samples | 250 samples |\n| :---- | :---- | :---- | :---- | :---- |\n| CM-g | 88.76 | 90.37 | 90.37 | 90.43 |\n| AM-g | 88.76 | 90.37 | 90.37 | 90.43 |\n\nWhen **n=64**\n\n|  | 0 sample (Beam Search) | 5 samples | 125 samples | 200 samples |\n| :---- | :---- | :---- | :---- | :---- |\n| CM-g | 87.03 | 88.57 | 88.57 | 88.57 |\n| AM-g | 87.03 | 88.57 | 89.19 | 90.09 |\n\nThe optimal granularity g∗ converges quickly with minimal validation data, across different compute budgets:\n\n* **High compute budget (n \\= 256):** Accuracy improves from 88.76% to 90.37% with just 5 validation samples. Increasing to 250 samples yields only a marginal gain (90.43%), indicating rapid convergence.\n\n* **Medium compute budget (n \\= 64):** A similar pattern holds. Accuracy rises from 87.03% to 88.57% using 5 samples. While AM-g benefits slightly from more data (up to 90.09%), most of the gain comes early.\n\nThe fast convergence aligns with our main conclusion that dense verification is often not optimal, especially under a high compute budget. It demonstrates that the additional compute overhead is minimal and finding $g\\*$ is practical.\n\n> Q6: Fairness and overhead of finding $g\\*$\n\nOur adaptive approach finds the optimal granularity $g\\*$ once per task and generator-verifier pair using a very small number of validation samples (Q5). This is a one-time cost that is negligible compared to live inference and can be reused across all future test cases.\n\nThis ensures that the FLOPs comparisons in Section 5 are fair, as the \"burn-in cost\" is insignificant in any practical scenario:\n\n* **Minimal Overhead:** Validation requires few samples, incurring negligible cost. In practice, it takes less than **5 minutes** on a single H100 for our experiments in Section 5\\.\n\n* **Amortized Use:** Once found, g∗ is reused, making the cost insignificant over time.\n\nWe will include these analyses and discussions in the next version of the paper as requested. Thank you for helping us improve the paper.\n\n> Q7: When to Recompute or Reuse $g\\*$ \n\nThe general guideline for applying $g\\*$ in practice is:\n\n1) Reuse $g\\*$: For a given fine-tuned model, verifier, task domain, compute-budget, and problem characteristic (in this case, problem difficulty), the same $g\\*$ can be reused indefinitely.  \n2) Recompute $g\\*$: A new $g\\*$ should be computed only when one of the core components changes (e.g., you switch to a new generator model).\n\nFor datasets with distinct subsets (e.g., varying difficulty levels), a more fine-grained strategy can be employed, depending on the characteristics of the task. As in Table 1, one can compute a different $g\\*$ for each difficulty subset and switch between them at inference time based on the problem's difficulty level.\n\nWe agree that more advanced methods for selecting g are a promising future direction. As we note in our limitations section and our response to Reviewer vtyM, dynamically adapting $g\\*$ during a single generation based on real-time signals (like model confidence) is an exciting next step. The methods proposed in this paper represent an attempt to challenge the fixed-granularity convention and provide a simple, practical, and effective alternative.\n\n> Q8: How different granularities are optimal across different pairings/baselines\n\nWe added a fully random verifier as a special case study. Please see our response to Reviewer vtyM’s Q4. We observed that for unreliable verifiers, sparser verification is preferred in most cases. We will refine the takeaways in Section 4.1 to better emphasize the trends across different experimental pairings.\n\n> Q9: The clarity of variable names\n\nThank you for the helpful suggestions on presentation and clarity. We will revise the variable names used in our search parameters.\n\n> Q10: Why rejected intermediate steps in beam search get expanded on in Fig. 2\n\nYou are absolutely correct—we do not expand rejected steps. The node in Figure.2 is the step generated for verification (before extending). We will make it clearer.\n\n> Q11: How to decide whether to accept or reject a reasoning step\n\nWe keep the top K reasoning steps according to their scores from PRM. We will make it clearer in our next version.\n\n> Q12: Why do we early prune the beam? is it because some solutions just start out as incorrect and you want to catch these early?\n\nYes, this is the motivation of our approach. We want to catch incorrect beams early, before spending more compute (extending) on them.\n\n> Q13: How epsilon is selected (line 256)\n\nThe hyperparameter epsilon controls the trade-off between accuracy and compute savings. It is user-defined and depends on the task’s sensitivity to error. In Section 5, we set it to 0.\n\n> Q14: overhead required during the g* search process?\n\nPlease refer to Q5, Q6, and Q7.\n\n> I think the work can be greatly strengthened with additional clarity and analysis and my score will reflect that\n\nWe hope that the new experiments and clarifications provided have offered the additional analysis and clarity needed to strengthen the paper as you suggested. Please feel free to let us know if you have further questions."}]

Author rebuttal:

Meta-review: This paper proposes Variable Granularity Search (VG-Search), a verifier-guided decoding algorithm that introduces a tunable granularity parameter g to control how often a reward model is queried. It groups candidate sequences into segments, queries the verifier only at segment boundaries, and enables budget-aware tuning of verification frequency. 

All the reviewers were positive at the end about our paper and wanted to accept it. I concur with their decision.
Decision: Accept (poster)