🤖 machine learning

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

This paper establishes exact certification limits for iid best-of-N search by modeling validation as kernel geometry over a reliability surface, deriving a precise ambiguity width formula that scales with $m^2/N$ and proposing a two-gate audit rule to distinguish structural coverage from precision.

Original authors: Ricardo Fitas

Published 2026-08-25

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Ricardo Fitas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Modern artificial intelligence has evolved beyond simply answering a single question with a single answer. Today's systems often generate a wide array of possibilities, compare them against one another, and then select the single best option to present to a user. This process, known as search, is used to solve complex math problems, write computer code, or design new molecules. Because the system is choosing from many alternatives, the reliability of its final output depends entirely on how that selection was made. If a system picks the best answer from a hundred attempts, the quality of that answer is different from the quality of an answer picked from just one attempt. The central challenge for scientists is figuring out how to verify that these selected answers are actually correct, especially when the system has been trained to pick the "best" one rather than a random one.

This verification problem is tricky because the act of selection changes the nature of the truth being measured. Imagine a scientist who checks a model's performance on a few specific types of questions and finds it is very accurate. If that model is then used to solve a completely different kind of problem, or if the selection process changes to look for a different type of "best" answer, the previous checks might no longer apply. The reliability of the system is not a fixed number that stays the same; it is tied to the specific method used to find the answer. If the method used to check the system does not cover the same ground as the method used to deploy it, the system might appear reliable while actually being blind to its own errors in the new context.

Ricardo Fitas, a researcher at the Technical University of Darmstadt, has developed a precise way to measure exactly how much uncertainty remains when we try to validate these AI systems. His work focuses on a common scenario where an AI generates many candidates and picks the top one based on a score. The study asks a fundamental question: if we know how reliable the system is when it picks the best answer from a small number of attempts, can we be certain how reliable it will be when it picks the best answer from a much larger number? The answer, according to the research, is often no. There is a hard limit to how much we can know without changing the way we test the system.

The research demonstrates that knowing the performance of a system on small search sizes does not guarantee knowledge of its performance on large search sizes. Even if a system performs perfectly when choosing the best answer from ten attempts, it could theoretically perform very poorly when choosing from a hundred, and both scenarios would be consistent with the same test data. This is not because the tests were done poorly, but because the tests simply did not look in the right direction. The study proves that there is a specific, unbridgeable gap in knowledge that exists whenever the search size in the real world is larger than the search size used during testing. This gap represents a form of structural blindness: the system might be working exactly as the tests suggest, yet still fail in ways the tests could never predict.

To understand this, consider that validation is like shining a flashlight into a dark room. If you only shine the light in a few specific spots, you can be sure what is in those spots, but you cannot know what is in the dark corners. If the AI system is then deployed in a way that requires looking into those dark corners, your previous checks provide no safety. The researcher calculated the exact size of this uncertainty. For a system that searches through a hundred candidates, if you have only tested it on searches of up to sixteen candidates, the uncertainty about its true performance can be as high as eighty-three percent. This means two completely different versions of the system could pass all your tests, yet one could be nearly perfect while the other is nearly useless when faced with the larger search.

The study also shows that simply repeating the same tests over and over does not fix this problem. Running a test a thousand times on the same small search size only reduces random noise; it does not illuminate the dark corners. To reduce the uncertainty, you must change the test itself to look at a different kind of search. The research provides a clear rule for how to do this: you must expand the range of your tests to cover the same ground as the real-world deployment. If you want to certify a system that searches through a hundred candidates, you must include tests that involve searching through a hundred candidates, or at least a number close to it.

The paper validates these findings using real-world data from two different domains: mathematical reasoning and computer programming. In the math experiments, the researchers looked at how well AI models solved problems when selecting the best answer from thousands of generated solutions. They found that while the average performance improved as the system searched more candidates, specific problems actually got worse. Some problems that were solved correctly with a small search became incorrect when the system searched more broadly. Similarly, in the programming experiments, the researchers analyzed code generation tasks. They discovered that even when the overall success rate looked good, individual tasks could fail dramatically when the search width changed. These real-world examples confirmed that the theoretical limits of uncertainty were not just mathematical abstractions but were present in actual AI behavior.

Furthermore, the study offers a practical solution for how to design better evaluations. It suggests a two-step approach. First, researchers must ensure their tests cover the structural breadth of the real-world task. This means testing the system on the same scale of search that it will face in practice. Second, once that structural coverage is established, they can add more independent tasks to reduce random noise and improve precision. The research shows that collecting more labels or data is only effective if the data is collected in the right direction. For instance, in the programming experiments, collecting labels specifically for the top-scoring candidates reduced the error rate significantly more than collecting labels for random candidates. This highlights that the direction of the test matters more than the sheer volume of data.

The findings serve as a warning against assuming that a system is safe just because it has passed a battery of standard tests. If those tests do not match the specific way the system will be used, the system may harbor hidden failures that only appear when it is deployed. The study does not claim that AI search is broken or that it cannot be improved; rather, it clarifies that the rules for proving a system works are stricter than previously thought. It establishes that validation is not a one-time check but a continuous process that must evolve alongside the system's capabilities. By understanding the geometry of these limits, developers can design audits that truly certify the reliability of AI systems, ensuring that the answers they provide are trustworthy not just in the lab, but in the real world.

Technical Summary: The Geometry of AI Validation

Problem Statement
Modern AI systems increasingly rely on inference-time search (e.g., best-of- $N$ selection) to generate and select alternatives. This paper argues that such selection mechanisms fundamentally alter the population whose reliability matters. Consequently, validation becomes target-relative: a model's reliability is not an intrinsic scalar but a property of the specific inference produced by a deployment rule.

The core problem is structural blindness. If a deployment target (e.g., the reliability of the best-of- $N$ output) lies outside the "span" of directions observed by validation interventions (e.g., best-of- $m$ audits for $m < N$ ), then no amount of additional sampling within the existing validation framework can resolve the ambiguity. Two distinct reliability worlds can agree perfectly on all audit data yet disagree arbitrarily on the deployment target. This paper formalizes the exact certification limits of this phenomenon for the canonical iid best-of- $N$ search problem.

Methodology and Theoretical Framework
The paper models validation as a geometric inverse problem involving three kernels:

$f$ : The unknown reliability surface ( $0 \le f \le 1$ ).
$v_j$ : Validation kernels representing the directions observed by audits.
$k$ : The deployment kernel representing the target of interest.

The author defines the blind residual $b(k; V)$ as the $L^1$ distance between the deployment kernel $k$ and the span of validation kernels $V = \text{span}\{v_1, \dots, v_p\}$ .

The Span Theorem (Theorem 1): The maximum separation between two validation-equivalent worlds (worlds agreeing on all audits) is exactly $b(k; V)$ . If $k \notin \text{span}(V)$ , exact identification is impossible regardless of sample size.
Post-Selection Inference: The paper establishes that when a deployment target is selected after inspecting evidence, validity requires simultaneous protection over the entire selectable family, not just pointwise confidence.
Best-of- $N$ Specialization: For iid candidates with scalar ranking and randomized ties, the best-of- $n$ reliability corresponds to the moment $\theta_n = \langle k_n, f \rangle$ where $k_n(u) = n u^{n-1}$ . The validation problem reduces to determining the worst-case width of the identified set for $\theta_N$ given exact knowledge of $\theta_1, \dots, \theta_m$ .

Key Contributions and Results

Exact Certification Limits (Theorem 2):
The paper derives a closed-form expression for the worst-case identified width $W_{m,N}$ when auditing through $n=m$ to certify $N$ :
$B_{m,N} = 1 + 2 \sum_{r=1}^m (-1)^r \cos^{2N} \left( \frac{r\pi}{2(m+1)} \right)$
This value is the exact attainable ambiguity. The paper constructs explicit "Chebyshev-sign" worlds ( $f_\pm$ ) that agree on all audits $n \le m$ but achieve the endpoints of this interval at $N$ .
Information Maximality (Proposition 2):
Among all audit schedules confined to widths $n \le m$ (including randomized mixtures or sequential choices), the complete prefix ( $n=1, \dots, m$ ) is information-maximal. No other combination of low-width audits can reduce the worst-case ambiguity below $B_{m,N}$ .
Phase Law and Scaling (Corollary 1):
The governing scale for ambiguity is the ratio $m^2/N$ .
- At $m \sim \sqrt{N}$ , the limiting ambiguity remains approximately 0.83, meaning auditing up to $\sqrt{N}$ still permits reliability near opposite ends of the unit interval.
- To achieve a small ambiguity $\epsilon$ , the required audit depth scales as $m \sim \sqrt{N \log(1/\epsilon)}$ .
Robustness to Shape Constraints (Theorem 3):
The paper investigates whether structural blindness persists under regularity constraints (monotonicity and Lipschitz continuity).
- Monotonicity: Reduces the problem to uniform monomial approximation, with ambiguity scaling as $O(L/m^2)$ .
- Lipschitz Bounds: The ambiguity remains of order $L/m^2$ . While regularity reduces the magnitude of the error, it does not eliminate the fundamental competition between the $m^{-2}$ audit resolution and the $N^{-1}$ deployment concentration.
Two-Gate Audit Rule:
The author proposes a practical decision framework:
- Structural Gate: First, ensure $B_{m,N} \le \epsilon$ . If this fails, no amount of additional independent tasks (replication) can achieve the target precision; new intervention directions are required.
- Sampling Gate: Once structural coverage is adequate, increase task counts to reduce sampling noise.

Empirical Illustrations
The paper provides retrospective analyses on two public datasets to demonstrate the geometry, explicitly stating these are not prospective interventions or prevalence estimates:

Mathematical Reasoning (GSM8K): Using 127 problems and 2.54 million solutions, the study shows that while aggregate ranking is high (AUC $\approx$ 0.9), specific problems exhibit "reversals" where increasing search width ( $n=1 \to 4096$ ) decreases truth.
Code Generation (CodeRM/HumanEval+): Using 164 tasks and 32,800 programs, the study constructs feasible "compatible worlds" that match the first 8 audit moments but predict best-of-100 truth values ranging from 0.186 to 0.992 (for 8B) and 0.305 to 0.996 (for 70B), despite the observed truth being 0.715 and 0.788 respectively.
Label Acquisition: A retrospective replay shows that collecting labels in the deployment direction (top-tail scores) significantly reduces estimation error compared to uniform sampling, validating the "structural gate" principle.

Significance and Scope
The paper claims to provide the exact attainable identification objects for the specific setting of iid best-of- $N$ search with bounded truth. Its significance lies in:

Formalizing validation as a target-relative inverse problem where structural blindness is distinct from sampling noise.
Proving that replication cannot fix structural blindness; only expanding the span of interventions (e.g., auditing the deployment winner directly) can.
Providing exact, non-asymptotic bounds ( $B_{m,N}$ ) that serve as a lower bound on certification difficulty.

Limitations and Claims
The author is explicit about the boundaries of their claims:

The closed-form results apply strictly to iid candidates, scalar ranking, randomized ties, and maximum selection.
The geometry applies to known or independently estimated kernels. It does not provide certificates for adaptive generators where the policy or history is unmodeled.
The empirical analyses are illustrative demonstrations of the mechanism in fixed public populations, not estimates of how often these "worst-case" worlds occur in practice, nor do they claim prospective effectiveness of the proposed audit rules.
The paper does not assert new theorems in moment spaces or optimal recovery but rather specializes established mathematical tools (Hausdorff moments, Chebyshev approximation) to the specific geometry of AI validation.

Technical Summary: The Geometry of AI Validation

More like this