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

• URL: http://arxiv.org/abs/2608.21496v1
• Date: Fri, 21 Aug 2026 15:18:11 GMT
• Title: The geometry of AI validation: Exact certification limits for iid best-of-N search
• Abstract summary: We represent validation and deployment rules as kernels over a reliability surface.<n>Knowing best-of-$n$ reliability through $n=m$ leaves exact ambiguity width $B_m,N=1+2sum_r=1m(-1)rcos2Nr/[(m+1)]$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots [9.539275654775706]
  Memorization in large language models is measured through a zoo of definitions whose formal relations are unknown.<n>We show that differential privacy (DP) is treated as a proxy against all of them at once.
  arXiv  Detail & Related papers  (2026-08-27T23:28:08Z)
• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• Random Parameter Noise Does Not Make Exact ReLU Verification Easy [14.270378035741404]
  We study exact verification of ReLU networks in an adversarial smoothed model.<n>We show that, under the standard assumption $mathrmNPnotsubseteqmathrmBPP$, there is no sound and complete verifier whose expected running time is embedding in network size, bit complexity, and inverse noise level for every base instance.
  arXiv  Detail & Related papers  (2026-07-15T21:26:20Z)
• Coupled Tensor-Matrix Recovery via Proximal Alternating Linearized Minimization, with an Application to Workforce Skill and Small-Business Health Estimation [0.0]
  We study recovery of a lowrank tensor $mathcalT$ and a low-rank matrix $M$ from noisy observations.<n>For the matrix only problem, we state a proven sampling-complexity result for a sequential sub-case.<n>For the fully joint, alternately-estimated case, we state a conjecture.
  arXiv  Detail & Related papers  (2026-07-11T07:06:08Z)
• Odds Law: The Decomposition Algebra On How Intelligence Organizes Itself to Solve Difficult Problems Reliably [0.5414847001704247]
  We show that reliability is bought with independent information arranged by composition, and bounded by the verifier.<n>In short, reliability is neither free nor magical: it is bought with independent information, arranged by composition, and bounded by the verifier.
  arXiv  Detail & Related papers  (2026-06-14T09:53:11Z)
• Representation Without Reward: A JEPA Audit for LLM Fine-Tuning [1.2691047660244335]
  Joint-embedding predictive architectures (JEPAs) propose that a model should learn more useful abstractions when trained to predict latent representations rather than observed outputs.<n>For autoregressive language-model fine-tuning the principle entails a stricter requirement: the induced hidden-state geometry must reach the language-model head emphand improve the decoded task metric.<n>We test that requirement under a fixed Llama-3.2-1B-Instruct LoRA harness on natural-language-to-regex generation.
  arXiv  Detail & Related papers  (2026-05-14T20:27:32Z)
• Adaptive Confidence Intervals in Efron's Gaussian Two-Groups Model [28.636700996382558]
  Motivated by noise-oblivious nature of adversaries, we study confidence intervals for the null location parameter $$ in Efron's Gaussian two-groups fraction model.<n>We characterize the minimax-optimal length among confidence intervals with a prescribed coverage level uniformly over the unknown proportion contamination and all noise-oblivious adversaries.
  arXiv  Detail & Related papers  (2026-04-28T22:40:54Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.