The geometry of AI validation: Exact certification limits for iid best-of-N search

Target-relative geometry

• The target reliability is identified if and only if the deployment kernel lies in the span of validation kernels.When it lies outside the span, validation-equivalent worlds can have different deployment values.Source: Validation is a target-relative… · p. 2
• Replication reduces sampling uncertainty but cannot reduce structural blindness without adding a new intervention direction.The blind residual is unchanged when more observations are collected inside existing interventions.Source: Validation is a target-relative… · p. 2, Selection after evidence requires… · p. 3

Finite best-of-N frontier

• For iid best-of-N search, auditing widths 1 through m spans the polynomial space P_m−1, while deployment at width N concentrates farther into the upper tail.The finite-prefix theorem gives the exact worst-case identified width, with explicit worlds attaining the interval.Source: Making the geometry exact: the finite… · pp. 3–4
• The complete low-width prefix is information-maximal among exact reliability-mean audits whose kernels use widths at most m.The same lower bound applies to sequential schedules confined to that query class.Source: Making the geometry exact: the finite… · p. 4

Phase law

• When m^2/N approaches a fixed positive value, ambiguity has a nontrivial phase limit; at m^2/N = 1, the limiting width is approximately 0.83.Width ε requires m of order sqrt(N log(1/ε)) in the stated asymptotic regime.Source: Making the geometry exact: the finite… · p. 4

• Figure 2 shows complementary Chebyshev-sign worlds matching the first six audits before separating maximally beyond the audited range.Source: Figure 2 · p. 5

Monotonicity

• Theorem 3 converts the monotone validation problem into uniform monomial approximation, with worst-case worlds represented by step functions.Source: Robustness: the degree-squared law… · p. 5

Lipschitz regularity

• Lipschitz constraints replace unrestricted oscillatory witnesses with a capped-density measure representation and an exact finite dual.Source: Robustness: the degree-squared law… · p. 5
• Regularity changes ambiguity to order L/m^2 while preserving the competition between m^-2 endpoint resolution and N^-1 deployment concentration.Source: Robustness: the degree-squared law… · p. 6

Numerical validation

• At (m, N, L) = (4, 16, 1), primal and continuum-dual estimates are 0.046130661 and 0.046130667, while rigorous brackets are [0.01409, 0.27015].At (8, 64, 1), the corresponding estimates are 0.020791486 and 0.020791501, with brackets [0.00449, 0.08482].Source: Robustness: the degree-squared law… · p. 6

• As the number of independent tasks grows, twice the planner’s optimized certificate approaches B_m,N, while outcome-dependent coefficient choice requires sample splitting or uniform concentration.Source: From geometry to an audit decision · p. 6
• The structural gate asks whether B_m,N ≤ ε; if it fails, added independent tasks cannot achieve full width ε within audited widths n ≤ m.Source: From geometry to an audit decision · p. 6
• The sampling gate is assessed only after structural breadth is adequate, and its failure can be repaired by more independent tasks.Source: From geometry to an audit decision · p. 6
• For N = 100 and 95% confidence, full width 0.10 requires at least m = 19 before sampling error is considered.Source: From geometry to an audit decision · p. 6
• Audit planning offers three noninterchangeable actions: widen the audited search range, increase independent task count, or collect deployment-direction labels.Source: From geometry to an audit decision · p. 6

Scope

• The empirical analyses are mechanism demonstrations in fixed public populations, not prevalence estimates or prospective randomized interventions.The evidence concerns 127 problems and 164 tasks, with compatible worlds conditional on the audited prefix.Source: Retrospective illustrations of the… · p. 6, Discussion · p. 8

Mathematical reasoning

• 0.907 macro within-problem AUC for 8B and 0.962 for 70B coexisted with selected-truth losses on some problems as search width increased.Mean selected truth rose from 0.768 to 0.882 for 8B and from 0.931 to 0.968 for 70B between n = 1 and n = 4096.Source: Retrospective illustrations of the… · pp. 6–7

Code selection

• 10 8B and four 70B HumanEval+ tasks lost more than one point as search increased from n = 1 to 100, with worst losses of 0.722 and 0.600.The reversal persisted across task, verifier, ground-truth, and search-range changes.Source: Retrospective illustrations of the… · p. 7

Compatible worlds

• 0.186 and 0.992 were compatible best-of-100 deployment values for 8B despite matching all eight plug-in audits; 70B witnesses reached 0.305 and 0.996.These are feasible lower-bound witnesses, not exact unrestricted continuum endpoints.Source: Retrospective illustrations of the… · p. 7

Audit design

• 3.67 and 2.15 were the held-out replay-error reduction factors for a frozen score-tail rule versus uniform labels at 500 labels.The 5% tail rule was selected using 82 discovery tasks before held-out outcomes were evaluated.Source: Retrospective illustrations of the… · p. 7

Span identity

• A target kernel is identified if and only if it lies in the span of the validation kernels.If it lies outside that span, validation-equivalent reliability worlds can disagree on its target value.Source: S1.1. Setup and notation · p. 11, S1.2. Proof of the span identity · p. 12

Sharp ambiguity

• The identified interval is exactly [ (1 − b(k; V ))/2, (1 + b(k; V ))/2 ], and convex scaling attains every intermediate value.The result is an attainable interval rather than only an upper bound.Source: S1.2. Proof of the span identity · pp. 11–12

Metric and scope

• The L1 metric follows from L∞-bounded reliability perturbations, while other norm or shape restrictions would induce a different support function.For noncentral evidence, box constraints may narrow the interval asymmetrically; the stated width is the largest over feasible evidence.Source: S1.3. Interpretation and variants · p. 12

Post-selection coverage

• Selected-target coverage for every measurable selector is equivalent to simultaneous coverage over the target family.The proof uses a first-failure selector; it does not require analysts to know or implement that selector.Source: S2.1. Exact equivalence for a finite… · p. 12
• 0.95 pointwise Gaussian coverage can fail after selecting the largest of M independent estimates, motivating simultaneous coverage over selectable targets.The example has no structural blind residual because each coordinate is observed directly.Source: S2.2. Gaussian selected-target example · p. 12, Table S1 · p. 13

Bias–noise geometry

• L1 approximation controls worst-case structural bias, while Euclidean/Gaussian geometry controls noise amplification.The two terms represent distinct geometries in universal confidence-band construction.Source: S3.1. A simultaneous bias–noise… · p. 13
• As n →∞, the optimal universal confidence-band half-width approaches B(K; V )/2, and no honest central-evidence band can improve that asymptotic floor.At finite n, the closest target approximation may be suboptimal if its coefficients amplify noise.Source: S3.1. A simultaneous bias–noise… · p. 13

Intervention design

• The remaining structural width after q new interventions is dist1{k, span(SV , d1, . . . , dq)}, which decreases to zero when the augmented span contains every target kernel.Feasibility and execution costs constrain which mathematical directions can actually be added.Source: S3.2. Adding realizable interventions · p. 14

Finite-task certification

• Across T independent tasks, Hoeffding’s inequality bounds sampling noise using coefficient range ∥a∥1 even when widths within a task are dependent.The finite-task certificate optimizes a bias–noise tradeoff over outcome-independent coefficients.Source: S3.3. A distribution-free finite-task… · p. 14
• A direct best-of-N audit sets the new intervention equal to kN, making the structural term zero and giving a full 1 −α interval when the stated task condition holds.The prefix breadth is necessary for structural ambiguity, but is not itself sufficient at finite T because sampling error remains.Source: S3.3. A distribution-free finite-task… · p. 14

Kernel span

• The first m kernels span Pm−1, so low-width reliability means resolve exactly the corresponding polynomial directions.Nonzero scalar multiples do not change the span.Source: S4.1. Rank normalization and winner… · p. 15

Orthogonal witness

• Lemma S2 constructs a degree-m orthogonal-signature witness that annihilates every polynomial in Pm−1.The proof uses Chebyshev roots, a sine-series representation, and orthogonality.Source: S4.2. A Chebyshev-sign annihilator · p. 15

Identified set

• Every audited reliability through m can agree across two valid iid worlds while deployment at N differs by Bm,N, and mixtures fill the entire interval [(1−Bm,N)/2, (1+Bm,N)/2].The interval is an identified set, not merely a pair of separated witnesses.Source: S4.4. V1–V2: bounded-reliability… · p. 16

Exact frontier

• The exact L1 distance is attained by the sign of the Chebyshev polynomial of the second kind, while the primal extremizer interpolates at its roots.This distinguishes the solved minimax frontier from the smooth Legendre lower-bound construction.Source: S4.5. Why Chebyshev improves the… · p. 16

Audit optimality

• The complete prefix is information-maximal within reliability-mean audits confined to widths n≤m, including adaptive query rules that remain in the same polynomial span.Audits outside this class, including direct width-N labels or other intervention kernels, may expand the span.Source: S4.6. Optimality among low-width… · p. 17

Audit law

• The limiting frontier admits a positive, cancellation-free theta representation that supports inversion for small target width.The representation follows from Jacobi’s imaginary transformation.Source: S5. Jacobi-theta phase transition and… · pp. 17–18
• The audit law requires m of order sqrt(N log(1/ε)) after first taking the fixed-τ limit and then sending ε downward.It does not establish a uniform approximation for arbitrary joint sequences ε=εN.Source: S5. Jacobi-theta phase transition and… · p. 18

Phase transition

• When m^2/N→τ, the normalized ambiguity converges to a Jacobi-theta frontier B(τ), while the simpler exponential approximation converges to e^−τ.The exponential captures the order in the well-audited regime but misses the exact prefactor and under-audited behavior.Source: S5. Jacobi-theta phase transition and… · p. 18
• At τ=1, B(1)≈0.8305, whereas e^−1≈0.3679, demonstrating the large discrepancy between the exact and exponential frontiers.Source: S5. Jacobi-theta phase transition and… · p. 18

Monotone frontier

• Monotonicity produces an exact identified set and worst-evidence frontier through uniform approximation of t^N by degree-m polynomials.The result has no duality gap and the primal maximum is attained.Source: S6. Shape-constrained validation… · p. 18, S6.1. Evidence-specific programs and… · p. 19, S6.2. Exact worst-evidence frontier… · pp. 19–20
• Extremal monotone worlds may be chosen as step functions with at most m+2 jumps each.Carathéodory’s theorem gives the finite atomic representation.Source: S6.2. Exact worst-evidence frontier… · p. 20

Lipschitz frontier

• For finite Lipschitz constant L, the exact frontier is a convex dual whose support functional is evaluated by thresholding a one-dimensional tail residual.The dual is a finite-dimensional optimization over audit coefficients plus a scalar threshold.Source: S6.3. Exact capped-tail dual under… · p. 20
• The Lipschitz ambiguity has order-sharp rate L/m^2, with lower and upper bounds differing only by phase-dependent constants.The lower bound uses smooth monotone worlds, while the upper bound uses endpoint-concentrated polynomial audits.Source: S6.4. Explicit smooth… · p. 21, S6.5. Positive-polynomial recovery and… · p. 22

Scope and sensitivity

• The audited prefix does not validate the local Lipschitz assumption, which should be justified independently or varied as a sensitivity parameter.The percentile coordinate makes L invariant to monotone score transformations.Source: S6.6. Numerical evaluation and… · pp. 22–23

Outcome generality

• The geometry can accommodate bounded continuous outcomes and multiclass outcomes by rescaling or applying the construction coordinatewise.Multiclass identified sets may additionally exploit the simplex constraint.Source: S7.1. Bounded and categorical outcomes · p. 23

Beyond iid search

• For non-iid selection mechanisms, the span theorem remains applicable when audit and deployment kernels act on a common stable state space and are known or independently estimated.It does not transfer the iid best-of-N formula Bm,N to those mechanisms.Source: S7.2. Known-kernel selection laws… · p. 23
• Adaptive generation requires a state containing relevant history and a policy-induced kernel that is known or independently estimated.Without those conditions, the framework supplies no certificate for the adaptive generator.Source: S7.2. Known-kernel selection laws… · p. 24

Shape assumptions

• Monotonicity, Lipschitzness, bounded variation, analyticity, and parametric tail laws reduce ambiguity only as scientifically justified, stress-tested restrictions.Replication at the same interventions cannot create these assumptions.Source: S7.3. Structural assumptions can… · p. 24

Surface stability

• If deployment changes the underlying reliability surface, kernel geometry alone is insufficient and must be supplemented by a transport or invariance model.Kernel-perturbation bounds address estimation error on a shared surface, not changes between surfaces.Source: S7.4. Unknown kernels and distribution… · p. 24

Data and estimand

• The analysis uses 127 GSM8K problems with 10,000 generated solutions per problem and disjoint 2,000-solution reference and 8,000-solution deployment sets.Consensus scores are computed from normalized final-answer frequencies, with unparsable answers ranked below parsed answers.Source: S8.1. Dataset and pinning · p. 24, S8.2. Consensus score and disjoint… · p. 24
• Exact with-replacement best-of-n reliability is evaluated for n ∈ {1, 2, 4, . . . , 4096}, with uniform tie averaging and problem-bootstrap intervals.The design avoids Monte Carlo simulation of search and treats problems as the sampling unit.Source: S8.2. Consensus score and disjoint… · p. 24, S8.3. Uncertainty and robustness · p. 25

Interpretation

• The data establish target change, favorable aggregate scaling with local reversals, and reversal persistence, but not that extremal Chebyshev worlds are typical.The empirical analysis tests these narrower claims rather than the distribution-free worst case itself.Source: S8. Mathematical-reasoning search… · p. 24, S8.3. Uncertainty and robustness · p. 25

Intervention efficiency

• A width-s audit samples percentile density q_s(u) = s u^(s−1), while deployment-winner sampling at s = N has unit importance weight and variance θ_N(1 − θ_N).The variance-equivalent label ratio compares labels from an audit design with one deployment-winner label under the same estimator class.Source: S9.1. Winner-distribution importance… · p. 26

Tail audits

• For a top fraction a of percentiles, the audit targets a truncated functional and omits a nonnegative tail mass that can be bounded explicitly.At a = 0.05 and N = 4096, the omitted mass is 0.954096 = 5.70 × 10^-92.Source: S9.2. Top-tail design · p. 26

Finite replay

• At 500 labels, top-tail acquisition reduces the 95th-percentile best-of-100 error by factors 3.89 and 2.89 for the 8B and 70B models.The comparison uses 5,000 masked-label retrospective replays, with scores determining allocation and full labels scoring the emulation afterward.Source: S9.3. Retrospective masked-label… · p. 27, Table S7 · p. 27

Scope and planning

• The replay conclusion is narrower than prospective effectiveness: covered search widths and independent task count address different failure modes and must be planned separately.The retrospective dataset does not measure collection cost, distribution shift, or a causal effect of assigning a real evaluation program.Source: S9.3. Retrospective masked-label… · p. 27, S9.4. Frozen-rule held-out audit test · p. 28, S9.5. Asymptotic GSM8K calculation · p. 28

Held-out rule selection

• A top-5% rule selected on 82 discovery tasks and frozen before evaluation reduces held-out q95 error by factors 3.67 and 2.15.The held-out comparison uses another 82 tasks and uniform acquisition as comparator.Source: S9.4. Frozen-rule held-out audit test · pp. 27–28, Table S8 · p. 28

Data and estimand

• The replication uses 164 HumanEval+ tasks and 100 candidate programs per task for each Llama-3 model, with verifier scores from generated unit tests and correctness from plus_status.The resulting data contain 32,800 programs and 3.28 million candidate–unit-test executions, while inference remains across 164 tasks.Source: S10.1. CodeRM/HumanEval+ data and… · pp. 28–29
• Exact tie-averaged best-of-n curves are computed for n ∈ {1, 2, 4, 8, 16, 32, 64, 100}, using task-bootstrap intervals and treating tasks as independent units.All 164 tasks contain both truth classes and enter both macro AUCs.Source: S10.1. CodeRM/HumanEval+ data and… · p. 29

Compatibility construction

• Spreading tie-group truth uniformly over score-rank intervals reproduces every macro best-of-n mean exactly, including widths beyond those plotted.The construction uses the average task law without treating candidates from different tasks as exchangeable.Source: S10.2. Retrospective compatibility… · p. 29
• The empirical partial-identification programs retain only best-of-n audits through m and optimize best-of-100 truth over bounded rank–truth laws constant on 1,000 percentile bins.The resulting witnesses are nonidentification constructions rather than fitted forecasts.Source: S10.2. Retrospective compatibility… · pp. 29–30

Uncertainty and reproducibility

• The reported ranges condition on empirical score/rank construction and use tasks as the sampling unit, so they are not distribution-shift guarantees.Bootstrap bands propagate finite task uncertainty separately from the compatibility construction.Source: S10.2. Retrospective compatibility… · p. 30, Table S11 · p. 30
• Numerical checks agree with the closed form to a maximum absolute difference of 1.887 × 10^-15 across 32 cases, but they do not replace the proof.The checks target sign, indexing, interpolation-node, and phase-scaling errors.Source: S10.3. Independent theorem checks · p. 30, Figure S2 · p. 31

Adjacent mathematical literatures

• The audit prefix is framed as a truncated Hausdorff moment problem, with polynomial-span geometry linked to optimal-recovery duality and canonical L1 approximation.These mathematical results are treated as established ingredients rather than the paper’s sole contribution.Source: S11. Relation to adjacent literatures… · p. 32

Adjacent AI literature

• Related AI work studies opposite infinite-compute limits or static benchmark coverage, whereas this paper studies exact finite-prefix identification of selected-output truth under an explicit deployment kernel.The comparison delimits the submitted object rather than claiming a broader theory.Source: S11. Relation to adjacent literatures… · p. 32

Statistical neighbors

• Expected-order-statistic and truncated-moment results clarify feasibility and recovery, but are distinguished from the paper’s bounded-binary best-of-width interval and residual frontiers.The stated distinction concerns the specific validation objects claimed here.Source: S11. Relation to adjacent literatures… · p. 32

Contribution boundary

• The paper claims validation-specific exact attainable identification objects, including monotone and capped-Lipschitz duals, reliability-mean audit laws, and finite planning consequences.Complete proofs are given in Sections S1–S7 with executable numerical checks for finite calculations.Source: S11.2. Exact claim · p. 32, Table S13 · p. 32

Empirical boundary

• Empirical analyses cover 127 problems and 164 tasks and demonstrate target change, reversals, compatible witnesses, and within-pool acquisition contrasts rather than prevalence or prospective effectiveness.The 82/82 split protects held-out labels from rule selection but remains a public-data replay.Source: S11.2. Exact claim · p. 32