Verification and Self-Improvement in Agentic AI: Foundations and Limits
Computer Science > Artificial Intelligence arXiv:2610.10611 (cs) [Submitted on 7 Oct 2026] Title: Verification and Self-Improvement in Agentic AI: Foundations and Limits Authors: Chien-Ping Lu.
计算机科学 > 人工智能 arXiv:2610.10611 (cs) [提交于 2026 年 10 月 7 日] 标题：代理人工智能中的验证与自我提升：基础与局限 作者：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 $\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 the same frontiers.
精确验证是零随机性的情况，并具有放置和完备性结果。随机验证器类满足 $\Sigma_k^{\mathrm{P}}\subseteq\Sigma_k^{\mathrm{RV}}\subseteq\Sigma_{k+1}^{\mathrm{P}}$；严格的扩大和深度分离需要明确的复杂性假设，而 $\mathrm{BPP}=\mathrm{P}$ 则产生了具有相同边界的精确伴随类。
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.
该框架将自我提升的主张与正确性、可接受证据、验证资源和选择错误的义务联系起来。