Verification and Self-Improvement in Agentic AI: Where Are the Theoretical Limits?

When Agentic AI Claims to Have Gotten Smarter, How Do We Verify It?

Agentic AI systems are "evolving" in multiple ways: some by extending search time, some by gaining additional external support, and others by directly modifying how they propose and verify outputs. The problem is that a single performance score tells us nothing about which mechanism is responsible for any improvement — the score went up, but was it because the system computed longer, relied on external resources, or actually learned something? This has been a long-overlooked blind spot.

A new paper on arXiv titled Verification and Self-Improvement in Agentic AI: Foundations and Limits attempts to build a rigorous analytical framework for such self-improvement claims, grounded in computational complexity theory. Its central argument is direct: performance gains are not the same as capability gains. Each type of improvement mechanism must be examined separately, with clearly defined "verification obligations" attached to each.

Redefining Improvement via "Bounded Verification"

The paper introduces an analytical model called bounded verification, which incorporates hidden terminal randomness. In this framework, a "stage" is defined by several components: admissible transcripts, polynomial resource bounds, an alternating verification protocol, and a terminal checker.

Two key concepts deserve distinction. A system's native reach refers to the capabilities achievable under default support. The closure frontier refers to the boundary reachable when all support permitted by the interface is fully utilized. In short, the former is "what the model can do on its own," and the latter is "what it can achieve with all legitimate external resources." Under assumptions of a uniform pointwise probability gap and task-relative soundness, both can be defined as well-defined languages.

The significance of this distinction lies in mathematically separating "the model's intrinsic capability" from "the system's overall performance achieved through external resources" — preventing borrowed capability from being credited to the model itself.

---

The Polynomial Hierarchy is a central concept in computational complexity theory, best understood as a layered generalization of classical NP/co-NP. The first level, Σ₁ᴾ, is simply NP — problems whose answers can be "guessed and verified" in polynomial time. The second level, Σ₂ᴾ, allows an additional universal quantifier nested on top of an existential one, and so on. The paper employs this hierarchy to precisely measure how much computational complexity each verification mechanism "consumes." An alternating protocol refers to a verification process that alternates between existential steps (finding a witness) and universal steps (holding for all counterexamples) — the very computational model underlying the polynomial hierarchy. Understanding this context helps clarify the paper's later sandwiching results for randomized verifier classes: introducing randomness places verification capability strictly between two adjacent deterministic levels, rather than leaping across entire levels.

---

Majority Voting Is Reliable, But "Existential Acceptance" Can Go Wrong

One of the paper's most illuminating results is a comparison between two common verification amplification mechanisms.

The first is independent majority amplification — improving reliability by taking multiple independent samples and accepting the majority result. The paper proves this approach preserves both the native reach and the closure frontier. In other words, it doesn't change the system's true capability boundaries; it simply makes results more consistent.

The second is existential acceptance over random tapes — passing an output if there exists at least one random path that leads to acceptance. The paper shows this mechanism can accept incorrect outputs. This is an important warning: many agentic strategies that seem to follow a "just try enough times and you'll succeed" logic actually carry a systematic risk of passing wrong answers.

As a zero-randomness special case, exact verification corresponds to deterministic checking, for which the paper provides placement and completeness results.

Randomized Verifier Classes and Their Place in the Complexity Hierarchy

At the complexity theory level, the paper establishes a sandwiching relationship between randomized verifier classes and the classical polynomial hierarchy:

$$\Sigma_k^{\mathrm{P}}\subseteq\Sigma_k^{\mathrm{RV}}\subseteq\Sigma_{k+1}^{\mathrm{P}}$$

This result shows that randomized verifier classes are cleanly sandwiched between two adjacent levels of the polynomial hierarchy. However, the paper honestly acknowledges that proving strict enlargement or depth separation requires invoking explicit complexity assumptions — a persistent challenge in complexity theory. Under the assumption that BPP = P, these randomized classes collapse into exact counterparts with identical frontiers.

In other words, whether randomness truly confers additional capability depends on open complexity conjectures that remain unsolved. This reflects an intellectually honest stance: the framework tells you "what follows if a given assumption holds," but doesn't overreach with unconditional strong claims.

---

BPP (Bounded-error Probabilistic Polynomial time) is the standard complexity class describing "efficient randomized algorithms": a problem is in BPP if there exists a polynomial-time randomized algorithm that gives the wrong answer with probability at most 1/3. The long-standing conjecture that BPP = P — meaning randomness doesn't fundamentally surpass deterministic algorithms — remains unproven. When the paper states that "randomized classes collapse to exact counterparts under BPP = P," it draws on this conjecture: if randomness provides no essential advantage for polynomial-time computation, then any capability gain from randomized verifiers also vanishes. This means some of the paper's conclusions are conditionally dependent rather than unconditionally proven theorems — an honest and standard practice in complexity theory.

---

Recursive Self-Improvement Has a Ceiling: You're Still in the Same Class

The section most directly relevant to the agentic AI discourse concerns recursive self-improvement (RSI).

The conclusion is sobering: under a common sound interpreter and fixed verification protocol, uniformly bounded self-modification leaves a system within the same verification class. Simply put, having an agent continuously rewrite its own code does not automatically break through the fundamental boundary of its verification capability — drawing a clear theoretical line against optimistic narratives about "AI endlessly self-improving."

The paper also introduces an independent conditional-error budget to control the mis-selection rate when adaptively choosing candidate solutions. It further constructs a quota-enforced XOR-synthesis family to distinguish between "unbounded proportional improvements in search success rates" and "genuine changes to the accepted language" — reinforcing once again that searching harder is not the same as becoming genuinely more capable.

---

Recursive Self-Improvement (RSI) holds a special place in AI safety and capability research: it is the central mechanism behind the "intelligence explosion" hypothesis. If a system can improve itself, and the improved version can more efficiently improve the next generation, capability could grow at a superlinear rate, ultimately exceeding human control. The paper's theoretical brake on this is: under a fixed verification protocol and sound interpreter, self-modified systems remain within the same verification complexity class. A "sound interpreter" means the runtime environment executing the modified code does not introduce new computational capabilities (e.g., it cannot secretly invoke resources beyond budget). This conclusion doesn't deny the engineering value of self-improvement — it says: the boundary of verification capability cannot be automatically broken through by code-level self-modification. To genuinely expand verifiable capability, you must fundamentally change the verification protocol itself, not merely iterate on code.

---

Representation Analysis: Refactoring Changes the "Core" vs. "Support" Labels

The paper also performs a representation analysis, distinguishing invariant acceptance behavior from core-versus-support labels, which can shift when a system undergoes refactoring. This means that when we reorganize an agentic system's internal structure, what counts as "core capability" versus "external support" may change — but what the system actually accepts and rejects should remain invariant. This provides yet another dimension for evaluating the authenticity of claimed improvements.

The Value and Limitations of This Research

The paper's core contribution is anchoring the vague claims of agentic AI self-improvement to four auditable obligations: correctness, admissible evidence, verification resources, and selection error. It provides both exact and probabilistic auditing approaches to check the resulting evidence requirements.

For the industry, this is a sobering reminder. As more products claim their agents "can self-optimize," this framework prompts us to ask: where does the improvement actually come from? More compute and search time? External tools? Or a genuine change to the verifiable capability boundary?

It's worth noting that this is highly theoretical work, with conclusions heavily dependent on complexity assumptions and still some distance from engineering practice. It functions more as mathematical language for future evaluation standards and capability claims than as a directly deployable tool. But in an era when agentic AI narratives are broadly optimistic and metrics are broadly imprecise, this insistence on rigorously defining the "limits of verification" is precisely what's in short supply.