Rethinking Optimal Verification Granularity for Compute-Efficient Test-Time Scaling

We thank the reviewer for the helpful feedback and will clarify the points of confusion as follows.

Q1: Example of infinite monkey might not be the best choice for demonstration.

We 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.

Our 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.

To 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.

Q2: Section 2.3 could have been shorter

We 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.

Q3: The motivation for the choice of generator and verifier pairings isn’t clear, and more pairings are needed

We 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.

In the next version of the paper, our main results will feature a complete set of pairings:

• Qwen-Math-1.5B + Skywork-1.5B-PRM (New Experiment)
• Qwen-Math-7B + Skywork-7B-PRM (New Experiment, addressing your specific request)
• Qwen-Math-1.5B + Skywork-7B-PRM (Original Paper)
• Qwen-Math-7B + Skywork-1.5B-PRM (Original Paper)

Results on Qwen-Math-1.5B + Skywork-1.5B-PRM

Results on Qwen-Math-7B + Skywork-7B-PRM

Across 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.
This 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.

Q4: Clarity on Section 5

Thank 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.

Q5: Convergence of AM-g and CM-g and computational overhead of finding optimal $g\*$

To 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.

Our findings show that the search for an effective $g\*$ is highly sample-efficient and converges very quickly.

The 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\*$.

When n=256

When n=64

The optimal granularity g∗ converges quickly with minimal validation data, across different compute budgets:

• 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.

• 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.

The 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.

Q6: Fairness and overhead of finding $g\*$

Our 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.

This ensures that the FLOPs comparisons in Section 5 are fair, as the "burn-in cost" is insignificant in any practical scenario:

• 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.

• Amortized Use: Once found, g∗ is reused, making the cost insignificant over time.

We will include these analyses and discussions in the next version of the paper as requested. Thank you for helping us improve the paper.

Q7: When to Recompute or Reuse $g\*$

The general guideline for applying $g\*$ in practice is:

1. 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.
2. 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).

For 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.

We 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.

Q8: How different granularities are optimal across different pairings/baselines

We 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.

Q9: The clarity of variable names

Thank you for the helpful suggestions on presentation and clarity. We will revise the variable names used in our search parameters.

Q10: Why rejected intermediate steps in beam search get expanded on in Fig. 2

You 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.

Q11: How to decide whether to accept or reject a reasoning step

We keep the top K reasoning steps according to their scores from PRM. We will make it clearer in our next version.

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?

Yes, this is the motivation of our approach. We want to catch incorrect beams early, before spending more compute (extending) on them.

Q13: How epsilon is selected (line 256)

The 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.

Q14: overhead required during the g* search process?

Please refer to Q5, Q6, and Q7.

I think the work can be greatly strengthened with additional clarity and analysis and my score will reflect that

We 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.

We appreciate the reviewer’s thoughtful feedback and will clarify the points of confusion as follows.

Q1: Scaling model sizes

To 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.

Our new findings, summarized below, align well with our paper's main conclusions:

Here is a complete table of results:

These 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.

We 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.

Q2: Multiple trials of experiments

We thank the reviewer for the suggestion to include results from multiple trials. We agree that this provides a more robust evaluation.

Following 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.

The 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.

We 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.

We appreciate the reviewer’s thoughtful feedback and will clarify the points of confusion as follows.

Q1: Semantically relevant notion of a “step”

We 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.

For this work, we adopted the newline character delimiter for the following reasons:

1. Comparability: It follows the convention of prior work [1], allowing for a direct and fair comparison with existing methods.
2. 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.

In 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.

$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.

Q2: Varying granularity dynamically

We 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.

Following 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.

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.

Based on this finding, a dynamic strategy could be implemented as follows:

• Use a larger verification granularity ($g$>1) when verifier confidence is high, saving compute when the path is stable.
• Use a denser verification ($g$=1) when confidence is low to catch potential errors immediately.

While 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.

Q3: Open-ended questions performance

We 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.

These 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.

$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.

Q4: Change of the best granularity with a noisy PRM

We thank the reviewer for this insightful question about how verifier quality affects the optimal granularity.

To 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.

Results on MATH-500

Results on AIME

Our 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).

In 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.

Thank you for your time and for the thoughtful suggestions.

As we approach the conclusion of the discussion period, could you please let us know if all your questions have been fully addressed?

We thank the reviewer for the helpful feedback. We will clarify your doubts as follows.

Q1: More details on the PRM

We 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.

We will ensure that the description of the PRM is made clearer and more prominent in the next version.

[1] He, Jujie, et al. Skywork-O1 Open Series. 2024.
[2] Edward Beeching, Lewis Tunstall, and Sasha Rush. Scaling test-time compute with open models. 2024.

Q2: Comparison with alternative verifiers

To 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.

A complete table of results:

We 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.

Regarding 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.

We 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.

[3] Lifshitz S, McIlraith SA, Du Y. Multi-agent verification: Scaling test-time compute with multiple verifiers. 2025.

Q3: How does VG-Search handle tasks that provide outcome-level feedback?

For 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.

These 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.

Thank you once again for your time and the insightful feedback.

As we near the end of the discussion period, may I kindly ask if our responses have fully addressed all of your questions?