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

arXiv: https://arxiv.org/abs/2610.10611 · HTML: https://mlsanity.com/paper/2610.10611/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 20 of its 27 references that are in the map.
- First posted on arXiv 7 Oct 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 20 of 20)

- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Why Do Multi-Agent LLM Systems Fail?](https://mlsanity.com/paper/2503.13657/) (2025)
- [GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning](https://mlsanity.com/paper/2507.19457/) (2025)
- [AFlow: Automating Agentic Workflow Generation](https://mlsanity.com/paper/2410.10762/) (2024)
- [AI safety via debate](https://mlsanity.com/paper/1805.00899/) (2018)
- [Agentic Context Engineering: Evolving Contexts for Self-Improving Language Models](https://mlsanity.com/paper/2510.04618/) (2025)
- [Darwin Godel Machine: Open-Ended Evolution of Self-Improving Agents](https://mlsanity.com/paper/2505.22954/) (2025)
- [Self-Taught Optimizer (STOP): Recursively Self-Improving Code Generation](https://mlsanity.com/paper/2310.02304/) (2023)
- [Agentic Harness Engineering: Observability-Driven Automatic Evolution of Coding-Agent Harnesses](https://mlsanity.com/paper/2604.25850/) (2026)
- [Self-Harness: Harnesses That Improve Themselves](https://mlsanity.com/paper/2606.09498/) (2026)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Hyperagents](https://mlsanity.com/paper/2603.19461/) (2026)
- [AI4AI-Bench: Benchmarking LLM Agents in Algorithmic Design for Recursive Self-Improvement](https://mlsanity.com/paper/2608.20318/) (2026)
- [The Last AI Built by Humans: Toward Genuine Recursive Self-Improvement](https://mlsanity.com/paper/2609.11873/) (2026)
- [Recursive self-improvement of AI research agents](https://mlsanity.com/paper/2609.26457/) (2026)
- [RSIAgent: Autonomous Exploration for Recursive Self-improvement in New Environments](https://mlsanity.com/paper/2609.15364/) (2026)
- [Self Improvement via Fast Tree-search](https://mlsanity.com/paper/2609.19526/) (2026)

## Abstract (arXiv)

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 SigmakPsubseteqSigmakRVsubseteqSigmak+1P; strict enlargement and depth separation require explicit complexity assumptions, while BPP=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.