mlsanityData to 7 Oct 2026

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

arXiv 2610.10611 ↗First posted 7 Oct 2026cs.AI cs.CCcited by 0

On the map: LLM agents and tool use → General LLM agent frameworks and benchmarks

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.

Key facts. No citing papers in the map yet (data through 7 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.

Builds on

20 of 27 references.

Closest ancestors · 2

Same direction, newest first

  1. 2026AI4AI-Bench: Benchmarking LLM Agents in Algorithmic Design for Recursive Self-Improvement20 Aug
  2. 2025Darwin Godel Machine: Open-Ended Evolution of Self-Improving Agents29 May

Other references · 18

  1. 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,393
  2. 2023Reflexion: Language Agents with Verbal Reinforcement Learningcited by 4,064
  3. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,928
  4. 2023Large Language Models Cannot Self-Correct Reasoning Yetcited by 965
  5. 2025Why Do Multi-Agent LLM Systems Fail?cited by 559
  6. 2025GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learningcited by 449
  7. 2024AFlow: Automating Agentic Workflow Generationcited by 395
  8. 2018AI safety via debatecited by 384
  9. 2025Agentic Context Engineering: Evolving Contexts for Self-Improving Language Modelscited by 349
  10. 2023Self-Taught Optimizer (STOP): Recursively Self-Improving Code Generationcited by 128
  11. 2026Agentic Harness Engineering: Observability-Driven Automatic Evolution of Coding-Agent Harnessescited by 119
  12. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
6 more
  1. 2026Self-Harness: Harnesses That Improve Themselvescited by 79
  2. 2026Hyperagentscited by 40
  3. 2026The Last AI Built by Humans: Toward Genuine Recursive Self-Improvementcited by 5
  4. 2026RSIAgent: Autonomous Exploration for Recursive Self-improvement in New Environmentscited by 5
  5. 2026Recursive self-improvement of AI research agentscited by 3
  6. 2026Self Improvement via Fast Tree-searchcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Viva La Vida: Verification and Accumulation Failures in Multi-Agent Proof Search
  2. 2026Towards Faithful Agentic XAI: A Verification Method and an Open-World Benchmark for Better Model Faithfulness
  3. 2026Why Agentic Theorem Prover Works: A Statistical Provability Theory of Mathematical Reasoning Models
  4. 2026Verifiable Semantics for Agent-to-Agent Communication
  5. 2025SmartSnap: Proactive Evidence Seeking for Self-Verifying Agents
  6. 2025On The Statistical Limits of Self-Improving Agents
  7. 2026Local verification cannot detect non-transportability: a cohomological theory of context preservation in agentic reasoning
  8. 2026Scaling the Scaling Logic: Agentic Meta-Synthesis of Logic Reasoning