When To Solve, When To Verify: Compute-Optimal Problem Solving and Generative Verification for LLM Reasoning

We thank the reviewer for their feedback and are pleased they found our study (a) useful to the community & helpful for obtaining better results, and (b) backed by solid & extensive experiments.

New Insights
We respectfully disagree about limited technicality & highlight several technical nuances & novel insights from our work:

• Firstly, the original GenRM paper [1] doesn’t release their models & conducts experiments on the relatively simpler GSM8K dataset. In contrast, we reproduce GenRM on the more challenging MATH dataset, which required substantial technical effort. We’ll make our data, models, & code publicly available. Additionally, we’ll release all inference outputs from larger models like QwQ-32B, whose generation is technically demanding. This will be a valuable resource for the community.
• Overall, our motivation is that as GenRMs gain popularity, it’s important to shed light on their high costs, & encourage research toward making them efficient.
• As shown in Fig. 1a, prior work [1] shows that GenRM outperforms SC at a fixed number of solutions, giving the false impression that GenRM is more efficient. However, this neglects the high cost of scaling verifications. More prior work [2] used GenRM to double the performance of SC on AIME24, but required 10K LLM calls, costing $650 per problem, to do so.
• Prior work lacked a method for comparing different test-time scaling strategies (such as GenRM & SC) in terms of inference cost. Our work is the first to develop a novel framework for such comparisons.
• Using this framework, we show that contrary to previous findings, SC outperforms GenRM under most practical budgets. To our knowledge, our work is the first to shed light on the high cost of scaling verifications.
• Prior work has also not studied the tradeoff between scaling solutions & verifications in GenRM to obtain the best performance for a compute budget. Our work is the first to perform a novel scaling law analysis, & shows that solutions should be scaled more rapidly than verifications.

[1] Generative Verifiers: Reward Modeling as Next-Token Prediction
[2] Sample, Scrutinize & Scale: Effective Inference-Time Search by Scaling Verification

Analysis Beyond Final Performance
We highlight diverse analyses from the paper that go beyond performance:

• Firstly, we highlight that the focus of our analyses is the computational efficiency of GenRMs, unlike prior works [1,2], which only focus on their performance.
• In Fig. 3 (left) we show that GenRM benefits difficult problems more. This would help practitioners to choose between SC & GenRM depending on task difficulty.
• In Fig. 3 (right) we show that a fine-tuned verifier can match the performance of the base verifier with 16x less compute, giving insight into the role of high-quality verifiers, and encouraging practitioners to fine-tune verifiers whenever possible.
• We also provide a qualitative example in Appendix K, showing how generating a verification CoT improves the final verdict & makes it more interpretable.

[1] Generative Verifiers: Reward Modeling as Next-Token Prediction [2] Critique-out-loud Reward Models

Upper Bound on Performance

• We thank the reviewer for the question. The performance upper bound is given by pass@k (i.e., coverage), the probability that at least one of k sampled solutions is correct, assuming an oracle verifier.
• In https://postimg.cc/2VLHVMHB, Llama 8B achieves 100% pass@k at k=$10^4$, consistent with [1]. Fig. 1b shows that performance saturates for both SC & GenRM: SC peaks at 55% ($2^7$ FLOPs) and GenRM at 59% ($2^{14}$ FLOPs).

[1] Large Language Monkeys: Scaling Inference Compute with Repeated Sampling

Impact of verification length

• We thank the reviewer for the insightful question. In L159-160, we highlight that the inference compute of GenRM is proportional to the product of the solution & verification lengths. In a hypothetical scenario, assuming fixed solution length & GenRM-FT performance, the reduction in the verification length will make GenRM-FT more compute-efficient.
• To understand the effect of verification length in this hypothetical scenario, we evaluate the compute required to match SC & compute required to outperform SC by 4% (Figure 1) when the verification length is varied from 2048 to 512:

• We find that current verifiers would have to reduce their response length by 8x, while maintaining their performance, to match SC. It remains unclear if it would be possible to achieve such gains in the efficiency of GenRMs.
• We hope that the shortcomings of current GenRMs highlighted by our work encourage the community to focus on the efficiency of GenRMs. We believe that this is an important direction for future research.

Hi Reviewer CSkR! Just a reminder that the discussion period for COLM papers has begun. Could you please take a look at the author response to review and let them know whether it addresses any of your outstanding questions?

Thanks, Your AC

We thank the reviewer for their feedback and are excited they found our findings (a) insightful, (b) of practical relevance, & (c) supported by extensive experiments.

Technical Component
We respectfully disagree about limited technicality & highlight several technical nuances & novel insights from our work:

• Firstly, the original GenRM paper [1] doesn’t release their models & conducts experiments on the relatively simpler GSM8K dataset. In contrast, we reproduce GenRM on the more challenging MATH dataset, which required substantial technical effort. We’ll make our data, models, & code publicly available, and release all outputs from larger models like QwQ-32B, whose inference is technically demanding. This will be a valuable resource for the community.
• Overall, our motivation is that as GenRMs gain popularity, it’s important to shed light on their high costs, & encourage research toward making them efficient.
• As shown in Fig. 1a, prior work [1] shows that GenRM outperforms SC at a fixed number of solutions, giving the false impression that GenRM is more efficient. However, this neglects the high cost of scaling verifications. More prior work [2] used GenRM to double the performance of SC on AIME24, but required 10K LLM calls, costing $650 per problem, to do so.
• Prior work lacked a method for comparing different test-time scaling strategies (such as GenRM & SC) in terms of inference cost. Our work is the first to develop a novel framework for such comparisons.
• Using this framework, we show that contrary to previous findings, SC outperforms GenRM under most practical budgets. To our knowledge, our work is the first to shed light on the high cost of scaling verifications.
• Prior work has also not studied the tradeoff between scaling solutions & verifications in GenRM to obtain the best performance for a compute budget. Our work is the first to perform a novel scaling law analysis, & shows that solutions should be scaled more rapidly than verifications.

[1] Generative Verifiers: Reward Modeling as Next-Token Prediction
[2] Sample, Scrutinize & Scale: Effective Inference-Time Search by Scaling Verification

Fine-tuning Smaller GenRMs

• We thank the reviewer for this suggestion! Prior work [1-4] used models of the same size for generating solutions & verifications, which is why we studied this setting. The ability to use small verifiers & large generators is an open question, largely unanswered in the literature.
• We ran an additional experiment on the reviewer's suggestion. Specifically, we fine-tuned LLaMA-8B (small GenRM-FT) on solutions generated by LLaMA-70B. We then compared its performance against LLaMA-70B (large GenRM-base) on solutions from LLaMA-70B on MATH test set here: https://postimg.cc/G4VX9XJ2.
• We find that SC outperforms the small verifier across the low compute regime, & small GenRM requires 4x compute to match SC. This indicates that while small verifiers are efficient, their performance still lags behind SC for most practical budgets. We’ll add this discussion to the camera-ready.

[1] Generative Verifiers: Reward Modeling as Next-Token Prediction
[2] Sample, Scrutinize & Scale: Effective Inference-Time Search by Scaling Verification
[3] V-STaR: Training Verifiers for Self-Taught Reasoners
[4] Training Verifiers to Solve Math Word Problems

Analysis of Thinking Models

• We believe there might be a misunderstanding. An analysis of thinking models (QwQ-32B) is available in L281-288 of the paper. Fig. 4b shows that our findings hold true for thinking models: on AIME25, GenRM requires 4× more compute to match SC, & achieves a 2.5% improvement with 16× more compute.
• This highlights that while thinking models can scale test-time compute sequentially in a single CoT, scaling compute parallelly by SC can provide further gains (+12%).
• Further, these results show that while thinking models are capable of self-reflection, adding a separate verification step by GenRM can further improve performance.
• Guidance to practitioners: while thinking models can scale test-time compute via longer CoT, scaling solutions & verifications can provide additional gains.

Relevance in open-ended domains

• Most LLM reasoning research focuses on math & science tasks, where final answers are available, like MATH, AIME, & GPQA.
• Even for coding, benchmarks like LiveCodeBench (LCB) contain test cases with a verifiable answer (i.e., expected output from the code) [1]. This allows us to apply SC, as done by [2].
• We run an additional experiment on 128 problems from LCB using Llama-3.1-8B here: https://postimg.cc/7GgDB1Kt. We find that GenRM-Base requires ~16x more compute to match SC.
• We agree that SC might not be applicable in all scenarios. We will add this limitation & the coding results in the camera-ready.

[1] LiveCodeBench: Holistic & Contamination Free Evaluation of Large Language Models for Code
[2] Universal Self-Consistency for Large Language Model Generation

Hi Reviewer Kdvi! Just a reminder that the discussion period for COLM papers has begun. Could you please take a look at the author response to review and let them know whether it addresses any of your outstanding questions?

Thanks, Your AC

We thank the reviewer for their feedback & are motivated that they found our work (a) timely, (b) practical, & (c) extensive.

GenRM scaling laws

• We clarify that our findings about scaling laws are robust across model families (Qwen; Fig. 10) & sizes (Llama 70B; Fig. 11).

Low/high-compute regimes

• Across multiple models & benchmarks (Figs. 1, 4, 5a, 7), SC outperforms GenRM up to ~$2^{10}$ FLOPs. We term this regime, of less than $2^{10} = 1024$ solutions, as low compute. Most papers generate solns within this regime [1,2]. We’ll add this to camera-ready.

[1] Beyond Human Data: Scaling Self-Training for Problem-Solving with Language Models.
[2] Smaller, Weaker, Yet Better: Training LLM Reasoners via Compute-Optimal Sampling.

Performance of our GenRM-FT & ProcessBench

• Our GenRM-FT outperforms SC by 4-5.4% (Fig. 1 & 7). Also, while the original GenRM reports a relative improvement of 2% over SC (Fig. 5c in [1]), our GenRM-FT achieves a relative improvement of 6.9% (Fig. 1b in our draft). This shows that our GenRM-FT is well-trained.
• GenRM-FT significantly outperforms GenRM-Base (Fig. 3b), & also generalizes to the much harder AIME 24 (Fig. 4).
• On ProcessBench (w/ outcome labels), our GenRM-FT significantly outperforms GenRM-Base on MATH & OlympiadBench, showing easy-to-hard generalization. We'll add these results to camera-ready.

[1] Generative Verifiers: Reward Modeling as Next-Token Prediction.

Comment on GenRM-Base

• GenRM-base is only considered for stronger models like LLama 70B & QwQ-32B, which are top performers on ProcessBench.
• Finetuning models of this size is difficult with academic budgets, making it common to use them without finetuning, validated by [1], which achieves good performance using GenRM-Base. Hence, studying them in a non-fine-tuned setting is highly relevant.

[1] Sample, Scrutinize, and Scale: Effective Inference-Time Search by Scaling Verification.

Comments on GenPRMs

• We focus on outcome reward models (ORMs), since the original GenRM paper uses ORMs, & they are more widely adopted. We defer more complex strategies like PRM due to the need for extensive process-level data & training complexity.
• We thank the reviewer for sharing ThinkPRM, but it is unfair to consider it since ThinkPRM [1] is a non-peer-reviewed paper released after the COLM deadline & lacks a compute-matched analysis against SC.
• Further, GenPRMs will incur high computational costs. The inference FLOPs for $N$ beams, $M$ steps per solution, & $L$ CoTs per PRM verification will be $O(NML)$. It’s unclear how well they perform with lower budgets.

[1] Process Reward Models That Think.

Future Longevity of our work

• Our framework & findings will play a crucial role in how practitioners evaluate GenRMs in compute-critical situations.
• Prior work didn’t consider the cost of verification, suggesting that GenRMs are more efficient than existing methods [1]. As GenRMs gain popularity, shedding light on their high cost is a timely contribution.
• Moreover, we provide a framework to study the inference cost & scaling behavior of GenRM-based methods, which will still be relevant as GenRMs evolve, & will catalyze progress toward efficient GenRMs.

[1] Generative Verifiers: Reward Modeling as Next-Token Prediction.

Clarification on SC vs GenRM takeaway

• Our motivation is not to claim that GenRMs can never be efficient. Rather, we aim to highlight a shortcoming of current models & spur research toward efficient GenRMs.
• We don’t suggest that SC is always better than GenRM. GenRM achieves relative improvements of 7% & 8.3% over SC in Figs. 1 & 7, & doubles its performance in Fig. 4a. This is also stated in our takeaway (L248).

Relevance in open-ended domains

• Most LLM reasoning research focuses on math & science tasks, where final answers are available, like MATH, AIME, & GPQA.
• Even for coding, benchmarks like LiveCodeBench (LCB) contain test cases with a verifiable answer (i.e., expected output from the code) [1]. This allows us to apply SC, as done by [2].
• We run an additional experiment on 128 problems from LCB using Llama-3.1-8B here: https://postimg.cc/7GgDB1Kt. We find that GenRM-Base requires ~16x more compute to match SC.
• We agree that SC might not be applicable in all scenarios. We will add this limitation & the coding results in the camera-ready.

[1] LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code.
[2] Universal Self-Consistency for Large Language Model Generation.

Compute-optimal strategy for scaling GenRM

• Overall, more compute should be spent on scaling solutions vs. verifications.
• Gains from scaling verification saturate at around 16-32 verifs, while scaling solns up to 256-512 helps.
• Fig. 9a compares scaling verifs (left) to scaling solns (right), & shows that performance increases more steeply with scaling solns (right)

Hi Reviewer hnKb! Just a reminder that the discussion period for COLM papers has begun. Could you please take a look at the author response to review and let them know whether it addresses any of your outstanding questions?

Thanks, Your AC

Thank you for the rebuttal. The results on ProcessBench have helped contextualize the findings with GenRM-FT. After carefully reading your rebuttal, I remain unsure about the long-term impact of these findings. However, I will update my assessment to 6 since I believe the paper could stir nice discussions related to scaling verifier compute and efficient GenRM.