Agentic AI systems can improve by searching longer, obtaining extra support, or altering how they propose and verify outputs. A single performance score does not distinguish these mechanisms. We compare these changes within a bounded‑verification framework that hides terminal randomness. A stage specifies admissible transcripts, polynomial bounds, an alternating verification protocol, and a terminal checker.
The stage’s native reach uses default support; its closure frontier permits any support already admitted by the interface. Under a uniform pointwise probability gap and task‑relative soundness, both define well‑formed languages. We prove that:
- Independent majority amplification preserves both languages;
- Existential acceptance over random tapes can admit incorrect outputs.
Exact verification corresponds to the zero‑randomness case, yielding placement and completeness results. Randomized‑verifier classes satisfy $$\Sigma_k^{\mathrm{P}} \subseteq \Sigma_k^{\mathrm{RV}} \subseteq \Sigma_{k+1}^{\mathrm{P}}$$; strict enlargement and depth separation require explicit complexity assumptions, while $$\mathrm{BPP}=\mathrm{P}$$ yields exact companions with identical frontiers.
Representation analysis separates invariant acceptance from core‑vs‑support labels that may change under refactoring. For recursive self‑improvement, uniformly bounded self‑modification under a common sound interpreter and a fixed verification protocol remains within the same verification class.
We introduce a separate conditional‑error budget to control 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.
Review