acceptodds
Under review as a conference paper at ICLR 2027

Right Proof, Wrong Theorem: A Relational Bottleneck in Verifier-Guided Scaling

Abstract

Best-of-N selection samples N candidate solutions and returns the one preferred by a verifier. It improves only if the selected candidate solves the requested problem. A coherent proof or program may instead solve a nearby problem, a failure we call a relational mismatch. We certify such errors in code and mathematics outputs using claim neighborhoods frozen before artifact inspection. Across two frozen generators, the upper score tail of our primary verifier contains fewer local defects but more relational mismatches. For the primary generator, raw best-of-N validity first rises and then falls: from 88.41% at N=32 to 80.34% at N=256 in code, and from 82.03% at N=16 to 76.56% at N=64 in mathematics. Exact finite-pool selection weights forecast these two curves with weighted mean absolute errors of 0.71 and 1.09 percentage points. A development-frozen interior-rank selector then improves fixed-budget validity by 4.49 to 8.98 percentage points across four domain-generator settings, without additional generation or verifier calls. Finally, in the primary code setting, relational training improves held-out claim-artifact binding and natural deployment; replacing ordinary relational ranking with a crossed relational objective adds 1.65 percentage points. These results show that recognizing a good artifact is insufficient: reliable verifier-guided scaling also requires binding the artifact to the claim it must satisfy.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Verifier-Guided Scaling, Bulk Metrics, Best-of-N selection

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_V5oEOpenReview ↗
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
  1. 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

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

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

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

(1) Stronger verification

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.

VerifierValidity, N=32N=32Validity, N=128N=128Mismatches, N=128N=128
V0: trained Qwen2.5-7B verifier87.50%82.81%12.50%
V1: independently trained Llama-3.1-8B verifier91.41%91.41%3.91%
GPT-4o: gpt-4o-2024-08-0694.53%93.75%3.12%
Replay frameScoring completeness
128 forecast targets; 128 uniformly sampled candidates eachAll targets retained; 11/16,384 GPT-4o scores missing after retries

For modern mis-alignment cases with Lean verifier, please see our modern verifier failures at the top of this page.

(2) Hedging and prior work

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)\exp(\lambda r_i), with normalized midranks rir_i and λ\lambda tuned per setting on development data for certified class-AA validity. Fixed-budget comparisons reuse prospective candidates and V0 scores.

SettingNNRaw (%)Soft-BoN (%)Interior rank (%)Gap (pp)
Code/G1/V012882.4289.3189.840.53
Code/G2/V012886.7289.3391.211.88
Math/G1/V03277.7381.7686.724.96
Math/G2/V03282.4284.8487.893.05

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.

(3) V1 profiles and binding

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.

V1 measureReference bandDeepest tail
Mismatches: Qwen code4.9%4.3%
Mismatches: Llama code4.5%3.2%
Mismatches: Qwen mathematics5.5%6.2%
Mismatches: Llama mathematics4.6%4.7%
Local defects: Qwen mathematics17.2%1.3%
Validity: Qwen mathematics66.2%86.8%
VerifierJoint claim-fixed accuracyStrict paired-block accuracyMismatch despite available correct answer
V038.0%25.0%11.6%
V170.7%61.0%3.7%
GPT-4o80.7%73.7%—
Frame300 unseen-family blocksSame blocks; 3/1,200 GPT-4o scores missingFull Qwen-code forecast pools, N=128N=128

(4) Budget and cost

Training offers a stronger low-budget operating point. M4 at N=32N=32 reaches 90.71%, exceeding V0 interior selection at N=128N=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.

Qwen-generated settingVerifier and policyCandidatesValidity
CodeV0, development-selected raw budget3288.41%
CodeV0, interior rank3288.67%
CodeV0, interior rank12889.84%
CodeV1, raw maximum3289.45%
CodeM3, raw maximum3290.15%
CodeM4, raw maximum3290.71%
MathematicsV0, development-selected raw budget1682.03%
MathematicsV0, interior rank3286.72%
Original rank tuningSpecification
Development targets per domain-generator setting64 code; 32 mathematics
Fraction grid{0.875,0.90625,0.9375,0.96875,1}\{0.875,0.90625,0.9375,0.96875,1\}
Selected fractionV0: α=0.9375\alpha=0.9375; V1: α=1\alpha=1
Code: interior rank versus tuned raw budget+1.43 pp for 4× the candidates

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!

Reviewer_RiDoOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces relational mismatches, i.e., generated proofs or programs that fail the requested task but satisfy a neighboring claim. It finds that these errors become more common in the highest-score region of a primary verifier, causing best-of-N selection accuracy to decline as sampling increases. The authors use finite-pool selection weights to forecast deployment performance and evaluate two repairs: selecting an interior score rank and training the verifier on matched and mismatched claim-solution pairs. Experiments cover code and mathematics, with the training intervention evaluated in one code setting.

Critical strengths
  1. The paper identifies a useful distinction between internally defective solutions and coherent solutions to the wrong problem. Certifying an unchanged artifact against a predeclared neighboring claim makes this distinction more concrete than simply labeling an answer as incorrect. Connecting these errors to the outputs actually selected at different budgets is practically relevant.
  2. Several aspects of the evaluation are carefully controlled. Neighbors are frozen before output inspection, related tasks are grouped across splits, forecasts precede prospective evaluation, and comparisons preserve paired candidate sets. Independent certification audits and explicit treatment of unresolved mathematics cases strengthen the evidence.
  3. The intervention studies provide useful evidence beyond descriptive error analysis. Interior-rank selection improves fixed-budget validity across four domain-generator settings, while relational training improves both natural selection performance and controlled claim-sensitivity tests. The matched M2-M4 comparison helps distinguish the benefit of relational examples from the smaller additional benefit of the crossed objective.
Critical weaknesses
  1. The methodological novelty is limited relative to the diagnostic contribution. Best-of-N overoptimization is already established, and the forecasting machinery applies classical order-statistic and sampling identities. Interior-rank selection is a simple development-calibrated heuristic, while relational training follows a contrastive supervision principle. The crossed objective adds 1.65 percentage points over ordinary relational ranking, compared with the larger gain from introducing relational examples. I would therefore assess the paper primarily as a diagnostic and evaluation study, rather than a major advance in selection or verifier training.
  2. The evidence for generality is narrower than the number of reported settings suggests. All four headline selection gains use the same primary verifier V0. For V1, development selects maximum-score selection, so the interior-rank repair makes no change. The full training intervention is restricted to Code/G1/V0. These results support a verifier-dependent failure and repair, but leave unclear how often the same behavior appears across other verifiers and reasoning systems. Fixed-budget gains also differ from compute-efficiency gains: in code, interior selection reaches 89.84% with 128 candidates, versus 88.41% for ordinary selection with 32.
  3. Neighbor construction is central to the interpretation but is not fully specified in the paper. Appendix lists transformation families, but does not provide a complete operational grammar, neighbor-count distribution, or detailed admissibility rules. Freezing neighbors prevents post-hoc selection, but does not establish that the neighborhood is representative. In particular, hypothesis strengthening and conclusion weakening require safeguards against overly permissive or vacuous alternatives. Sensitivity to neighborhood size and construction would alsohelp establish how stable the measured mismatch prevalence is.
  4. The forecasting and mechanistic claims should remain distinct. Binary correctness labels yield the same validity estimator, so the relational taxonomy is useful for explaining selected errors but is not necessary for forecasting success. Moreover, the flexible binary predictor has lower forecast error in ten of twelve settings. The forecasting contribution is therefore its principled estimation and prospective validation, rather than uniformly better prediction. Likewise, fewer selected mismatches and improved binding diagnostics support the proposed interpretation, but do not uniquely establish that correcting this mechanism explains the intervention gains. The authors should appropriately acknowledge this limitation.
Questions for authors
  1. How many neighbors are registered per target, and what rules exclude vacuous hypotheses or excessively weak conclusions? Are existing sensitivity results available for alternative neighborhood sizes or transformation subsets?
  2. How are the two solutions in each relational block obtained and filtered, and which transformation families are excluded from training?
  3. Is M1 matched to M2-M4 in training exposure and tuning budget?
  4. What development search selected the interior-rank fraction, and how sensitive are the gains to nearby fractions?
  5. Do the existing results show whether M4 improves performance across the full budget curve, rather than only at the primary deployment budget, and whether it benefits from interior-rank selection as well?
1 comment

Thank you. NN denotes candidate count, and pp denotes percentage points.

(1) Contribution

We connect certified wrong-task selection to a controlled training intervention. Each mismatch certificate requires the unchanged artifact to fail the requested task and satisfy a neighbor frozen before output inspection; nested selections show these errors displacing available correct answers (point 4). This motivates claim-swapped supervision: validity rises from 82.42% (M0) to 87.46% with relational classification (M2) and 90.32% with M4, while exposure-matched defect training (M1) does not improve deployment. With data and resources fixed, the crossed loss is invariant to additive claim-only and artifact-only score terms and adds 1.65 pp over ordinary ranking (M4–M3, and one-sided 95% lower bound: +0.47 pp). Please see our discussion at the page-top for the practical importance of claim–proof alignment.

(2) Generality

The failure depends on the verifier, and training gains transfer across generators. Frozen M4 checkpoints trained on Qwen2.5-7B-Instruct outputs transfer to Llama-3.1-8B-Instruct outputs without tuning. The added crossed-loss gain is tested in Code/G1.

TestV0Comparison
Deep-tail mismatches, Qwen code14.80%4.3% with Llama verifier
Deep-tail mismatches, Qwen mathematics15.8%6.20% with Llama verifier
Generator transfer: validity, 128 targets, N=128N=12887.5%91.41% with M4; three-seed SD: 0.78 pp

(3) Neighborhoods

One typed edit (d=1d=1) uses predefined templates and finite parameter whitelists: six code families, eight mathematics families. Neighbors are normalized, deduplicated, then frozen. Mean counts are ≈4.1 in code and ≈6.0 in mathematics, and medians are 4 and 6. Strengthened assumptions must be satisfiable with nonempty domains. Whitelisted weakenings exclude tautologies, empty conclusions, and restated assumptions, retaining nontrivial proof obligations. Removing both strengthening and weakening retains tail-minus-reference mismatch enrichment:

GeneratorCodeMathematics
Qwen9.44 pp8.87 pp
Llama4.37 pp6.06 pp

(4) Forecasting and ranking failure

Binary labels suffice for validity forecasts. Paired switches establish selection failure, without identifying training's internal mechanism. Prospective evaluation uses 192 targets with four repetitions each.

EvidenceResult
Flexible binary predictor has lower forecast error10 of 12 comparisons
Forecast-pool coverage, N=32N=32 to 12812898.84% → 99.21%
Mismatch selected despite an available correct answer6.74% → 11.64%
Prospective switches across 768 nested sets44 correct-to-mismatch; 10 reverse

(5) Blocks and held-out families

Each solution satisfies its own request and fails the other. We generate separately with Qwen2.5-7B-Instruct, certify all four pairings, check types and duplicates, and group related tasks within splits. Mathematical proofs are human-assessed. Withheld code families: Domain substitution and Neighboring object or contract.

EvaluationSizeM4 minus M3
Unseen-family blocks300—
Held-out-family natural selection384 selections per seed+1.74 pp; one-sided 95% lower bound: +0.38 pp

(6) Training exposure

M4–M3 isolates the loss change, not its internal mechanism. M2–M4 share data, exposure, steps, class proportions, checkpoint rules and tuning budgets. M1 is matched in training exposure and tuning budget.

(7) Rank tuning and cost

Rank tuning preceded evaluation, and nearby ranks retain fixed-budget gains. α\alpha counts upward from the lowest score. Smaller raw budgets remain competitive.

Development searchSpecification
Targets per domain-generator setting64 code; 32 mathematics
Fraction grid{0.875,0.90625,0.9375,0.96875,1}\{0.875,0.90625,0.9375,0.96875,1\}
Selected fractionV0: α=0.9375\alpha=0.9375; Llama verifier: α=1\alpha=1
Qwen-generated settingCandidatesRankValidity
Code128117 / 119 / 12187.76% / 89.45% / 89.84%
Code, development-selected raw budget32Maximum88.41%
Mathematics3230 / 31 / 3286.33% / 86.72% / 77.73%
Code: interior versus tuned raw budget4× candidates—+1.43 pp

(8) Full curves and combined repairs

M4 beats M3 in every seed at every tested N≥2N\ge2. At N=32N=32, mean M4 validity exceeds V0 interior selection at N=128N=128 by 0.87 pp with one-quarter the candidates, and training costs are separate. Hedging remains budget-dependent.

NNM3 validityM4 validityInterior-rank effect on M4
265.97%66.32%—
3290.15%90.71%−0.52 pp
12888.67%90.32%+0.48 pp
25688.06%90.15%+0.91 pp
Reviewer_mCgHOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Please see above

Critical strengths

Please see above

Critical weaknesses

Please see above

Questions for authors

Please see above

1 comment
AuthorsOpenReview ↗

Thank you and in-error review submitting?

Thank you for your feedback. The substantive review fields visible to us contain only “Please see above,” and we cannot locate the referenced comments, so we wonder whether part of the review may have been pasted in error. Could you kindly check and share the intended comments? We would be grateful for the clarification and will carefully consider and respond to all of your suggestions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Right Proof, Wrong Theorem: A Basic Reliability Problem Across Modern AI Systems

Dear AC and Reviewers:

Our paper identifies and systematically studies a fundamental failure of inference scaling: more search can displace an available correct answer with a convincing solution to the wrong task. Recent official disclosures and independent evaluations observe similar failures of "right proof, wrong theorem" beyond our experimental models, supporting that frontier judges in a wide range may still approve faulty formalizations, and proof checking verifies the encoded statement, not its fidelity to the intended claim.

SourceSystem or settingDocumented evidence
OpenAI formalization scope notes245 scope notes inspectedOur conservative count identifies at least 12 result families with explicitly disclosed substantive gaps between manuscript claims and formalized conclusions.
OpenAI, family 266Mutually unbiased bases in dimension sixManuscript bound: 3. Formalized bound: 5. OpenAI explicitly states that the selected formalization does not establish the manuscript’s bound.
Anthropic official system card, §6.2Claude Opus 5Reward hacking: 14.7% attempted, 1.0% successful.
Same official system cardClaude Mythos 5.1Reward hacking: 10.5% attempted, 0.7% successful.
Same official system cardClaude Opus 5.5Reward hacking: 10.0% attempted, 0.6% successful.
Same official system cardClaude Mythos 5.2Reward hacking: 9.2% attempted, 1.0% successful.

The Anthropic figures are classifier estimates on sampled RL episodes. They document related failures of task alignment, under a different definition from our certified relational mismatches.

Beyond LLM Judge, first posted on 14 October 2026, after our September submission, directly evaluates frontier judges on formal statements.

JudgeIncorrect among accepted FLMF statements
GPT-5.515.7% (28/178)
Claude Opus 4.631.0% (72/232)

Source: Table 2. FLMF is a 471-pair diagnostic panel containing historical errors and deliberate mutations. These are errors among judge acceptances, rather than deployment error rates.

These records expose the practical stakes of separating verification success from task success. Frontier judges can still approve incorrect formalizations, while formal proof checking establishes the encoded statement and leaves its correspondence to the intended claim as a separate obligation. Our contribution makes this relation an explicit target of measurement, explanation, and training. We certify when an unchanged artifact fails the requested task but satisfies a predeclared neighbor, establish how selection can displace correct answers, and demonstrate interventions. Across 768 prospective nested sets, we observe 44 correct-to-mismatch switches versus 10 reversals. In Code/G1 at N = 128, our relational training intervention reduces selected mismatch from 12.37% to 6.16%. The implications extend to automated mathematics, coding agents, and learning from verifier feedback. Reliable scaling requires verification to remain tied to the task that was actually requested.

Paper Revision

Our revision adds:

  • Certification: Clarified neighborhood admissibility and added robustness analyses.
  • Verifier evaluation: Added V1/GPT-4o comparisons and direct evidence of wrong-task selections displacing available correct answers.
  • Selection baselines: Added development-selected budgets, rank-based Soft-BoN, and rank-sensitivity comparisons.
  • Training evidence: Clarified matched comparisons and block construction; added results across budgets and generator-transfer evaluation.
  • Positioning and clarity: Sharpened the diagnostic contribution, incorporated relevant hedging literature, and kept the main text concise.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.