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

Ricardo Fitas

Source-linked AI summary

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

Ricardo Fitas

arXiv:2608.21496v1Aug 21, 2026cs.LGmath.STstat.ML

TL;DR

The paper frames AI validation as a target-relative problem governed by the span of validation interventions. It makes this geometry exact for iid best-of-N search, derives structural ambiguity limits, and connects them to audit design and illustrative empirical studies.

Problem
AI search can expand selectable decisions faster than evaluation expands intervention coverage, allowing apparent precision while scientific identification deteriorates.
Method
The paper represents validation and deployment rules as kernels, analyzes their span geometry for iid best-of-N search, and extends the framework to known or independently estimated kernels.
Results
Reliability-mean audits confined to widths at most m cannot certify deployment beyond the exact best-of-N structural limit, while regularity changes magnitude without removing the competition between m^-2 audit resolution and N^-1 deployment concentration.
Takeaways & Limitations
Audits should first expand structural coverage, then use independent tasks to improve precision; deployment families, assumptions, and frozen design choices should be specified and stress-tested.
Takeaways & Limitations
Beyond iid search, the framework requires a known or independently estimated policy-induced kernel on a state space containing relevant history; otherwise it supplies no certificate.

Abstract

from arXiv · show

AI systems increasingly generate alternatives, inspect evidence, and deploy a selected output. Validation is therefore target-relative: evidence certifies deployment only in directions resolved by the interventions that produced it. We represent validation and deployment rules as kernels over a reliability surface. Their span geometry separates replication, which reduces sampling noise, from new intervention directions, which reduce structural blindness. We make this principle exact for iid best-of-$N$ search. Under scalar ranking, randomized ties, maximum selection, bounded binary truth, and a stable rank-truth relation, knowing best-of-$n$ reliability through $n=m$ leaves exact ambiguity width $B_{m,N}=1+2\sum_{r=1}^{m}(-1)^r\cos^{2N}{rπ/[2(m+1)]}$. Explicit bounded worlds attain the entire interval, and the complete prefix is information-maximal among reliability-mean audits confined to $n\le m$. The governing scale is $m^2/N$: when $m$ is proportional to $\sqrt{N}$, ambiguity remains about 0.83, while width $\varepsilon$ requires $m$ of order $\sqrt{N\log(1/\varepsilon)}$. Monotonicity gives an exact uniform-approximation frontier; a Lipschitz bound gives an exact capped-tail dual and order-sharp $L/m^2$ ambiguity. These results yield a two-gate audit rule: establish structural coverage, then add independent tasks for precision. Retrospective studies of mathematical reasoning and code selection construct compatible deployment values with wide separation and show that a score-tail audit rule frozen on 82 discovery tasks substantially reduces held-out error. Beyond iid search, the geometry applies only to known or independently estimated kernels; the empirical analyses are illustrative rather than prospective interventions.

Validation is a target-relative inverse problem

Validation identifies deployment reliability only when the deployment kernel lies in the span of audited interventions; otherwise, exact structural ambiguity remains even with noiseless evidence. For iid best-of-N search, the complete reliability prefix through m yields a sharp finite frontier whose scale is m^2/N.

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.
Target-relative geometry: 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.
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.
Finite best-of-N frontier: 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.
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.

Robustness: the degree-squared law survives shape constraints

Shape constraints preserve the degree-squared endpoint-resolution phase while changing ambiguity’s magnitude. Monotone and Lipschitz restrictions admit exact frontiers, constructive bounds, and numerically accessible dual formulations.

Figure 2 shows complementary Chebyshev-sign worlds matching the first six audits before separating maximally beyond the audited range.
Monotonicity: Theorem 3 converts the monotone validation problem into uniform monomial approximation, with worst-case worlds represented by step functions.
Lipschitz regularity: Lipschitz constraints replace unrestricted oscillatory witnesses with a capped-density measure representation and an exact finite dual.
Lipschitz regularity: Regularity changes ambiguity to order L/m^2 while preserving the competition between m^-2 endpoint resolution and N^-1 deployment concentration.
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].

From geometry to an audit decision

The finite-task planner separates structural breadth from sampling precision. Auditors should first test whether the audited widths cover deployment, then choose among broader audits, more tasks, or deployment-direction labels.

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.
The structural gate asks whether B_m,N ≤ ε; if it fails, added independent tasks cannot achieve full width ε within audited widths n ≤ m.
The sampling gate is assessed only after structural breadth is adequate, and its failure can be repaired by more independent tasks.
For N = 100 and 95% confidence, full width 0.10 requires at least m = 19 before sampling error is considered.
Audit planning offers three noninterchangeable actions: widen the audited search range, increase independent task count, or collect deployment-direction labels.

Retrospective illustrations of the same geometry

The empirical studies illustrate that changing search width changes the reliability target, while compatible deployment values can remain widely separated under limited audits. A frozen score-tail audit rule reduced held-out replay error, but the evidence is retrospective and bounded in scope.

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

S1. Exact inverse geometry of validation

The inverse geometry identifies exactly which deployment reliabilities are determined by validation interventions. Its sharp interval is the distance of the target kernel from the validated span, with simultaneous selection requiring family-level coverage.

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.
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.
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.
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.
Post-selection coverage: 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.

S3. Noisy validation capacity and intervention design

Noisy validation combines structural approximation error with sampling noise. Replication reduces the latter, whereas feasible new intervention kernels can reduce the former, yielding a finite-task audit-design tradeoff.

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.
Bias–noise geometry: 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.
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.
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.
Finite-task certification: 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.

S4. Exact best-of-N frontier

The first m best-of-n reliability kernels span the degree-(m−1) polynomial space, yielding an exact deployment ambiguity frontier for iid best-of-N search. Explicit bounded binary worlds attain the full identified interval, and the complete low-width prefix is optimal among the stated reliability-mean audits.

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

S5. Jacobi-theta phase transition and audit law

The asymptotic frontier is governed by the phase coordinate m^2/N, with a theta-function limit that captures the transition from under-audited to well-audited regimes. Inverting the limiting frontier gives the audit-depth law, subject to an essential iterated order of limits.

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.
Audit law: 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.
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.
Phase transition: At τ=1, B(1)≈0.8305, whereas e^−1≈0.3679, demonstrating the large discrepancy between the exact and exponential frontiers.

S6. Shape-constrained validation frontier

Adding monotonicity or a Lipschitz constraint replaces unrestricted oscillatory witnesses with exact shape-constrained frontiers. The Lipschitz case yields a computable capped-tail dual and sharp ambiguity of order L/m^2.

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.
Monotone frontier: 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.
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.
Lipschitz frontier: 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.
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.

S7. Extensions and scope

The kernel-span framework extends beyond iid best-of-N only when alternative selection mechanisms share a known or independently estimated reliability surface. The paper also emphasizes that shape assumptions and transport across changing surfaces require separate justification.

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.
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.
Beyond iid search: 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.
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.
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.

S8. Mathematical-reasoning search experiment

The experiment tests whether search changes reliability targets in mathematical reasoning using fixed empirical candidate populations and exact best-of-n evaluation. Aggregate improvements coexist with task-level reversals that persist across reference/deployment splits.

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.
Data and estimand: 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.
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.

S9. Finite and asymptotic efficiency of validation interventions

The section compares validation interventions by their efficiency for estimating a best-of-N target. Score-matched tail audits reduce finite-sample error, while structural coverage and prospective validation remain separate requirements.

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

S10. Code-generation replication and reproducibility

The CodeRM/HumanEval+ study changes the domain, verifier, truth mechanism, and search range while preserving the iid score-and-select estimand. It constructs reproducible compatibility analyses showing that empirical audited prefixes can leave deployment truth nonidentified.

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.
Data and estimand: 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.
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.
Compatibility construction: 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.
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.
Uncertainty and reproducibility: 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.

S11. Relation to adjacent literatures and contribution boundary

The paper positions its contribution at the boundary between established moment, approximation, and order-statistic tools and a validation-specific theory of selected-output reliability. Its claims are deliberately limited to the stated identification objects and empirical scope.

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