Verification and Self-Improvement in Agentic AI: Foundations and Limits

Chien-Ping Lu

cs.AIOct 7, 2026

Verification and Self-Improvement in Agentic AI: Foundations and Limits

Authors: Chien-Ping Lu

Abstract

Agentic AI systems can improve by searching longer, receiving additional support, or modifying how they propose and verify outputs. A performance score does not distinguish these mechanisms. We compare these changes through bounded verification with hidden terminal randomness. A stage specifies admissible transcripts, polynomial bounds, an alternating verification protocol, and a terminal checker. Its native reach uses default support; its closure frontier permits all support already admitted by the interface. Under a uniform pointwise probability gap and task-relative soundness, these are well-defined languages. We prove that independent majority amplification preserves both languages, whereas existential acceptance over random tapes can admit incorrect outputs. Exact verification is the zero-randomness case, with placement and completeness results. The randomized-verifier classes satisfy $Σ_k^{\mathrm{P}}\subseteqΣ_k^{\mathrm{RV}}\subseteqΣ_{k+1}^{\mathrm{P}}$ ; strict enlargement and depth separation require explicit complexity assumptions, while $\mathrm{BPP}=\mathrm{P}$ yields exact companions with the same frontiers. Representation analysis separates invariant acceptance from core-versus-support labels that can change under refactoring. For recursive self-improvement, uniformly bounded self-modification under a common sound interpreter and fixed verification protocol remains within the same verification class. A separate conditional-error budget controls false selection across adaptively chosen candidates. A quota-enforced XOR-synthesis family separates unbounded ratios of search success from changes in the accepted languages; exact and probabilistic audits check the resulting evidence requirements. The framework ties self-improvement claims to obligations on correctness, admissible evidence, verification resources, and selection error.

Figures & tables

Panel of Figure 1 — Figure 1: Three comparisons under a common task relation. Each shape represents task inputs ; area is schematic and does not measure probability or cardinality. Write $L=\mathrm{L}_{R}(S)$ , $F=\mathrm{F}_{R}(S)$ and use primes for the successor. Better search can preserve both languages. Internalization enlarges native reach within unchanged optional support. The illustrated frontier expansion admits an input natively that has no accepted source-frontier witness. This nested drawing is one possible transition, not an assumption that every stage change is monotone.

Panel of Figure 2 — Figure 2: The declared verification interface. Exposure and length bounds fix the admissible records; alternating moves specify the acceptance game. Only the terminal checker receives hidden random bits. Setting the coin length to zero recovers deterministic verification. The diagram specifies semantics, not the cost of solving the quantified game.

Panel of Figure 3 — Figure 3: Reliability depends on the aggregation rule. (a) The exact binomial majority map $g_{N}(p)$ sends each admissible low-probability tuple to the low side and each high-probability tuple to the high side. The shaded open interval is excluded by the pointwise gap. Preserving this classification preserves quantified acceptance and the two languages (Theorem 4.2 ). (b) For the same fixed false tuple with single-call probability $1/4$ , independent majority reduces false acceptance, whereas “any pass” gives $1-(3/4)^{N}$ . At three calls these are $5/32$ and $37/64$ . Curves are analytic, with the tuple and exposure held fixed.

Terminal rule	Incomplete patch	Full repair	Sound for $R$
Four declared tests	Accept	Accept	No
All eight declared inputs	Reject	Accept	Yes
Task-bound complete certificate	Reject	Accept	Yes

Table 1: Exact enumeration on the bounded lookup task. Acceptance is relative to the declared specification and domain. The sampled design’s apparent reach cannot be used as a sound frontier for this task.

Panel of Figure 4 — Figure 4: Enforced permission and discovery probability in the XOR family. (a) Each column represents all target vectors of one Hamming weight, with multiplicities shown below. Making quota three the default changes native reach from one to 42 inputs without changing the frontier. Raising the maximum quota to four also admits the 15 weight-four targets. (b) Both policies use the source stage with explicit optional quota $q=3$ and target $a=(1,1,1,0,0,0)$ ; under default quota zero both have success probability zero. For $M$ independent attempts the curves are $1-(1-p)^{M}$ . The solution mixture computes the correct program with probability $1/2$ and samples uniformly otherwise; it is an analytic control, not a learned RSI system. Counts and per-attempt probabilities match the exact audit of Proposition 7.1 .

Panel of Figure 5 — Figure 5: An RSI loop and two distinct guarantees. The dashed feedback indicates that an accepted revision can alter later improvement, including the improver’s inputs or inherited mechanism. It does not add a quantifier block. Under Proposition 8.1 ’s fixed admission, exposure, interpretation, and common bounds, admitted histories define a language in the same verification class. Proposition 8.2 separately controls false selection relative to an improvement criterion. Neither guarantee alone establishes that successors are empirically better.

Permitted edit	Effect in the XOR family	Contract to retain or establish
Full-support proposal policy	Changes discovery probability; $L,F$ unchanged	Same exposure, output binding, and exact core.
Default quota $0\to b$	Sets $L$ equal to the existing $F$	Both defaults belong to the same admitted quota range.
Maximum quota $b\to b+1$	$F$ gains weight- $(b+1)$ targets	New exposure bound and an all-source-witness exclusion proof; core remains sound.
Replace the checker	Depends on its accepted behavior	Re-establish gap and task soundness; syntax admission is insufficient.

Table 2: A concrete update contract. All quota languages here remain in

\mathsf{P}

; these edits are not claims of learned recursive improvement.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Research line	Reported mechanism	Stage comparison and evidence needed
Autonomy and inherited improvement	Duan et al. organize RSI by control over execution, strategy, experience, deployment adaptation, and inherited improvement mechanisms. They separate structural from effective recursion [ 1 ] .	An autonomy level does not determine $k$ . Record accepted-language changes separately from proposal efficiency and successor quality. A fixed enclosing class can accommodate both inherited meta-updates and empirical gains.
Prompt and context adaptation	GEPA reflects on execution traces to evolve prompts; ACE incrementally maintains playbooks; RSIAgent carries frozen memory into evaluation [ 21 , 23 , 14 ] .	Declare which context was already available through optional support. Compare memory admissibility and use under matched task and output contracts.
Workflow search	AFlow uses Monte Carlo tree search over code-represented workflows and execution feedback [ 22 ] .	Separate a better policy over existing traces from a changed trace grammar. Adding a critic node does not establish universal challenge semantics.
Agent and harness code	DGM retains an archive of self-modified agents. AHE exposes editable components and records predicted effects; Self-Harness validates proposed edits with regression tests [ 12 , 20 , 26 ] .	Version the permitted programs, tool behavior, and terminal checker. An edit may affect exposure, acceptance, or only search efficiency; its file location does not determine its semantic role.
Editable improvers	STOP optimizes the improver’s own program. Hyperagents jointly exposes task and meta-agent code to modification. AIDE 2 explores research-agent improvement across successive versions [ 18 , 19 , 13 ] .	Version $S_{i}$ , $U_{i}$ , and $J_{i}$ separately. Measure the updated improver on common starting agents and budgets, and identify any fixed outer search or evaluation process.
Search evaluation	SIFT aggregates pairwise judge preferences through a Bradley–Terry model to guide parent selection and evaluation priority [ 24 ] .	Treat ranking feedback as a search signal unless its separate acceptance contract is established. Include all selection calls in the error and cost accounting.

Appendix

Table 3: Mechanism-level comparison of self-improvement research.

Explore similar work

Self-Authored Verification Is Unreliable in Heuristic Self-Improving Agents
Jul 27, 2026Diandian Guo, Cong Cao, Fangfang Yuan +3AI Agent Evaluation LLM Agent Self-Improvement
Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China · School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
A Relative-Computability Theory of Self-Improving Agents
Apr 9, 2026Chien-Ping LuSelf-Improving Agents Recursive Self-Improvement
Who Verifies the Verifier? Co-Evolving Inspectable Graders with Self-Improving Agents
Oct 8, 2026Xing Zhang, Guanghui Wang, Yanwei Cui +4
AWS Forward Deployed Engineering · HSBC Holdings Plc., HSBC Technology Center, China

Jul 27, 2026, cs.CLJ/K move · Enter open · S save

Self-Authored Verification Is Unreliable in Heuristic Self-Improving Agents

Diandian Guo, Cong Cao, Fangfang Yuan, Yingqi Wang+2

Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China · School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

AI Agent Evaluation LLM Agent Self-Improvement LLM Agent Verification Self-Improving Agents

Open paper AskPDF arXiv

Self-improving agents accumulate capability by repeatedly rewriting procedural policies, controllers, or heuristic rules. They typically rely on self-authored tests or metrics to decide whether to accept subsequent edits. The agent controls both the optimized object and its verifier. As a result, self-assigned scores can remain near perfect while real deployment performance degrades or stays low. We study this problem through the verifier--deployment gap. This gap refers to the discrepancy between an agent's self-authored verification signal and a sealed deployment evaluation that the agent cannot observe or access. We ask how self-authored verification fails under iterative policy-and-test rewriting, how the failure changes with capability, and how little exogenous trust is sufficient to prevent real regressions from being deployed. To address this problem, we introduce a Sealed Exogenous Acceptance Loop (SEAL). SEAL retains self-authored tests but compares each candidate with the incumbent through a fixed harness-side audit. The agent cannot author or inspect the audit, receives only accept/reject, and the whole incumbent state is retained after a clear regression. Our experiments show that this problem often appears in heuristic learning settings. These settings require trial-and-error discovery of the target objective. We further find that failures of self-written verification are stratified by capability. Weaker agents tend to damage previously acquired strategies behind easy self-tests. Stronger agents are more stable, but they still mismeasure the deployment distribution. Standard self-written constraints do not reliably close this gap. In contrast, SEAL outperforms unprotected baselines across six models and three random seeds. Reliable self-improvement need not abandon self-verification, but it requires at least one deployment-acceptance signal outside the agent's control.

Abstract

Explore similar work

Self-Authored Verification Is Unreliable in Heuristic Self-Improving Agents

A Relative-Computability Theory of Self-Improving Agents

Who Verifies the Verifier? Co-Evolving Inspectable Graders with Self-Improving Agents