Verification and Self-Improvement in Agentic AI: Foundations and Limits
Chien-Ping Lu
cs.AI
Oct 7, 2026 · v2
cs.CC
TL;DR
Ancillary Lean 4/Mathlib project machine-checks bounded semantic replacement, an evaluator recurrence, and adaptive-selection error-budget propositions using Mathlib probability.
Abstract
A self-improving agent can find accepted solutions more often without expanding the tasks its verification interface can accept. We extend task-relative verification with explicit support and transcript interfaces to distinguish search gains from changes in accepted-task coverage. A stage's native reach contains tasks accepted with default support; its closure frontier contains tasks accepted with any support the declared interface permits. A semantic containment criterion identifies the authority or exposure condition that every verified escape must violate, while guard-transfer invariance prevents a change of representation from being counted as a capability expansion. An executable Boolean-program repair agent makes the distinction concrete: over 36,864 paired runs, counterexample feedback reduces verifier calls without changing coverage, whereas an enforced permission change admits a new target with a proof excluding every old-interface program. Exact and uniformly gapped randomized verification share this account; independent majority amplification improves reliability while preserving the accepted language. Separate adaptive-selection contracts state what is additionally required to interpret a proposed successor's score as evidence of deployment improvement. Classical hierarchy results and finite audits provide supporting boundaries. The framework specifies the evidence needed to establish improved search, wider accepted capability, and reliable successor selection.
Problem
Self-improving agents may raise benchmark scores either by finding accepted solutions more efficiently or by actually widening the set of tasks their verification interface can accept. Standard evaluations do not separate these mechanisms, and they do not say what evidence is needed to treat a successor's score as deployment improvement.
Approach
The paper defines task-relative verification stages with explicit support, exposure predicates and a terminal checker. From these it derives native reach and a closure frontier, a semantic containment criterion that any verified escape must violate, and guard-transfer invariance. An executable Boolean-program repair agent illustrates the framework, and further results cover randomized-verifier amplification and adaptive-selection contracts. Selected parts are formalized in a Lean 4 project pinned to a Mathlib commit, including the probability-based selection propositions.
Results
Over 36,864 paired runs, counterexample feedback reduces verifier calls without changing coverage. An enforced permission change admits a new target, with a proof excluding every old-interface program. Independent majority amplification preserves the accepted language and reduces pointwise error to at most e^{-N/18}.
| d | Edit mask | \ | F\ | | Blind calls | Guided calls |
|---|
| 4 | M_leaf | 9 | 5.00 | 2.94 |
| 4 | M_all | 27 | 14.00 | 4.27 |
| 8 | M_leaf | 81 | 41.00 | 5.56 |
| 8 | M_all | 2,187 | 1,094.00 | 10.42 |
Frontier size and mean verifier calls for blind vs. counterexample-guided search