- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies why best-of-N selection with a learned verifier can get worse as N grows. It focuses on “relational mismatches”, which are proofs or programs that are correct for a nearby claim but wrong for the one asked - such as proving the converse of a requested implication. To detect these, each target gets a set of nearby claims that is fixed before any outputs are seen, and each output is labeled as (1) valid, (2) valid only for a nearby claim, (3) locally broken, or (4) other. With 2 small generators (code and math tasks) and a trained verifier, the paper finds that the verifier’s top scores contain fewer local bugs, but more relational mismatches. As a result, best-of-N validity peaks at a middle budget and then drops (in code, 88.41% at N=32 down to 80.34% at N=256). The paper forecasts these curves accurately from separate labeled pools and proposes 2 fixes: (1) selecting a candidate slightly below the top score (which gains 4.49 to 8.98 percentage points) and (2) training the verifier on paired claim/artifact examples
Critical strengths
Strength 1: Careful measurement design: labeling errors after looking at outputs makes it very easy to invent a nearby claim that explains any mistake. This paper, however, avoids that by fixing the nearby claims in advance and requiring the unchanged output to pass one of them. Smaller budgets reuse the same candidates as larger ones, so when validity falls from N=32 to N=256, the cause has to be the ranking - since the good candidates are still in the pool. Independent audits confirm about ~95% of the mismatch labels, and the audit accuracy is similar in the top scores and the middle scores (tables 13, 14 and 15) - all of this makes the main tail results in table 1 believable
Strength 2: bulk metrics fail to predict deployment, with the forecast catching it: V0 and V1 pass a "pre-registered" test for matching accuracy and AUROC, and yet V1 is about 8 percentage points better at the deployment budget ( table 17). The forecasts - fixed before generation - predict the rise and fall of V0’s curve within about 1 p.p. (figure 2). All of this then gives practitioners a usable way to check a verifier at their actual budget
Critical weaknesses
- The effect is shown for 1 verifier, and the comparison verifier seems not to have it.
All class profiles in Table 11 are for V0. For V1, development tuning chooses plain top1 selection (section I.6) and a monotone curve fits V1 almost as well as the exact forecast (seen in table 21) - which suggests V1’s validity never declines (?). So the decline may come from how V0 was trained - rather than from verifier-guided scaling in general as the title implies. The setup is also a bit dated: 7B to 8B generators from 2024 and a simple scalar-head verifier, while the paper’s own GPT-4o judge already binds claims much better (77% vs 28% strict block accuracy, as seen in table 16). I think this is fixable by reporting V1’s profile, testing a stronger verifier, or narrowing the claims
- The fixes are compared against a weak baseline and miss related work.
Prior work already shows that best-of-N can degrade with large N because of reward hacking, and proposes methods that avoid this. For example, Khalaf et al (NeurIPS 2025) show the rise-then-fall pattern is expected for a broad class of selection methods and propose tuning a hedging parameter. The interior-rank selector is a version of this idea - but the paper does not cite or compare against this work. It's gains are also measured against top1 selection at a budget already past the peak. So simply using the best smaller budget closes most of the gap in code (1.43 p.p. left, seen in section I.6).
Questions for authors
-
What do V1’s score band class profile and binding scores look like? I mention this because if V1 top scores also fill with mismatches but its validity does not drop, the link between binding and deployment is weaker than claimed.
-
How does the interior-rank selector compare with choosing N on development data - at the same generation cost? I think this is probably the comparison a practitioner would make first
3 comments
Thanks for the extra V1, GPT-4o & Soft-BoN results. They make it clear the drop depends on the verifier and the gain over just picking a smaller budget is pretty small - so I’ll keep my 3 but I think the title should be narrowed to match.
Following your suggestion, we will revise the title to “Right Proof, Wrong Theorem: A Verifier-Dependent Bottleneck in Best-of-N Scaling” to make clear that whether performance declines as the search budget grows depends on the verifier. Thanks again!
Thank you. N denotes candidate count, and pp denotes percentage points. A mismatch fails the requested task but satisfies a neighbor frozen before output inspection, with the solution unchanged. Added analyses are post-review.
Stronger verifiers select fewer wrong-task answers from the same candidates. This replay uses Qwen2.5-7B-Instruct code on forecast targets, separate from the prospective tests. GPT-4o sees only the request and unchanged solution. Its small change across two budgets supports a failure that depends on the verifier, and we have clarified this scope in the abstract.
For modern mis-alignment cases with Lean verifier, please see our modern verifier failures at the top of this page.
Interior rank exceeds tuned Soft-BoN by 0.53–4.96 pp in all four settings (point estimates). We add development-tuned budget selection (point 4) and rank-based Soft-BoN to address budget and fixed-budget hedging. Soft-BoN uses weights exp(λri), with normalized midranks ri and λ tuned per setting on development data for certified class-A validity. Fixed-budget comparisons reuse prospective candidates and V0 scores.
Soft-BoN reports expected validity; gaps are interior rank minus Soft-BoN.
Our contribution is certifying which wrong task a selected solution solves, showing when it displaces an available correct answer, and testing relational training as a repair.
V1 clarifies why mismatch enrichment need not reduce validity. In Qwen mathematics, its drop in local defects outweighs the rise in mismatches. We therefore measure whether a wrong-task answer is chosen when a correct answer is available. Joint claim-fixed accuracy requires the right choice under both requests, and request-specific score offsets do not affect it. Strict paired-block accuracy requires both valid pairings to outrank both invalid pairings. Llama outputs use Llama-3.1-8B-Instruct, and incomplete GPT-4o blocks count as failures.
Training offers a stronger low-budget operating point. M4 at N=32 reaches 90.71%, exceeding V0 interior selection at N=128 by 0.87 pp with one-quarter the candidates. M3 already reaches 90.15%, leaving a 0.56 pp crossed-objective increment. Training costs are excluded. For selection alone, smaller raw budgets remain competitive. Original rank tuning preceded forecast and prospective generation, and budget selection and Soft-BoN were added after review.