The core thesis is simple but devastating: there is no single scientific method to verify whether an autonomous AI agent actually possesses a claimed capability. The right verification strategy depends entirely on the agent's computational model and strategic posture (honest vs. potentially deceptive). Current AI practice (relying on fixed benchmarks)applies cooperative statistical tools to adversarial problems, creating a widespread category error that makes most capability claims for untrusted agents (API-based LLMs, tool-using systems) scientifically unsound.This 2026 paper bridges 1999 theoretical computer science to 2026 AI deployment reality. It does not claim AI is impossible to trust only that current dominant methods are mismatched to the threat model. The path forward is regime-aware design: honest/cooperative agents get efficient statistical verification; adversarial agents require stronger assumptions (class restrictions, computational hardness, or perpetual monitoring). Organizations and societies that internalize this distinction will deploy AI more safely and effectively; those that don't will continue to be surprised by capability cliffs and silent failures.AbstractHow many black-box queries does a challenger need to verify that an autonomous agent has a claimed capability? We identify three regimes based on the agent's computational model and strategic posture. For deterministic agents, VC dimension governs query complexity: $n = O\!\bigl((d/\epsilon)\log(1/\epsilon) + (1/\epsilon)\log(1/\delta)\bigr)$. For cooperative stochastic agents attesting a fixed configuration, Chernoff bounds give $n = \Theta\!\bigl((1/\epsilon^{2})\log(1/\delta)\bigr)$. For adversarial stochastic agents, where the adversary selects the worst-case configuration pair to attest, query complexity depends on a behavioral indistinguishability gap that the adversary controls. We give two lower bounds: (i) no non-adaptive protocol with a fixed query set known to the adversary can succeed, and (ii) no polynomial-query adaptive protocol succeeds when the agent class can embed pseudorandom functions (computational hardness). The taxonomy identifies a category error in current AI evaluation practice: benchmark-based attestation is a Regime 2 method applied to Regime 3 problems. We discuss what sound attestation requires for each regime.
capability attestation · agent verification · query complexity · VC dimension · behavioral indistinguishability · pseudorandom functions · AI safety · black-box evaluation · frontier models