# Self-Evolving Agents with Anytime-Valid Certificates

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 45 references that are in the map.
- First posted on arXiv 1 Jul 2026.

## Builds on (most cited first, 30 of 34)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [Reinforced Self-Training (ReST) for Language Modeling](https://mlsanity.com/paper/2308.08998/) (2023)
- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [CodeT: Code Generation with Generated Tests](https://mlsanity.com/paper/2207.10397/) (2022)
- [Orthogonal Gradient Descent for Continual Learning](https://mlsanity.com/paper/1910.07104/) (2019)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Game-theoretic statistics and safe anytime-valid inference](https://mlsanity.com/paper/2210.01948/) (2022)
- [Is Model Collapse Inevitable? Breaking the Curse of Recursion by Accumulating Real and Synthetic Data](https://mlsanity.com/paper/2404.01413/) (2024)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Quality and Diversity Optimization: A Unifying Modular Framework](https://mlsanity.com/paper/1708.09251/) (2017)
- [Hindsight Credit Assignment](https://mlsanity.com/paper/1912.02503/) (2019)
- [A PAC-Bayesian bound for Lifelong Learning](https://mlsanity.com/paper/1311.2838/) (2013)
- [Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent](https://mlsanity.com/paper/2006.11942/) (2020)
- [Top-Down Synthesis for Library Learning](https://mlsanity.com/paper/2211.16605/) (2022)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Performative Reinforcement Learning](https://mlsanity.com/paper/2207.00046/) (2022)
- [Towards Safe Policy Improvement for Non-Stationary MDPs](https://mlsanity.com/paper/2010.12645/) (2020)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Model Alignment](https://mlsanity.com/paper/2410.16714/) (2024)
- [A Theoretical Perspective: How to Prevent Model Collapse in Self-consuming Training Loops](https://mlsanity.com/paper/2502.18865/) (2025)

## Built on by (most cited first, 6 of 6)

- [Self-Evolving Coding Agents](https://mlsanity.com/paper/2608.03392/) (2026)
- [Propose, Don't Judge: An Anytime-Valid Referee for LLM Agents That Mine Investment Factors](https://mlsanity.com/paper/2609.27051/) (2026)
- [Which Self-Improvements Should We Trust? Reliable Self-Improvement When Agents Reuse Their Benchmarks](https://mlsanity.com/paper/2609.33180/) (2026)
- [Protected Cores Are Not Enough: Certifying AI-Proposed Revisions of Temporal Specifications](https://mlsanity.com/paper/2609.33461/) (2026)
- [EvoSteer: Online Self-Evolving Graph Orchestration via Reference-Anchored Credit Assignment](https://mlsanity.com/paper/2609.38661/) (2026)
- [Authorization for Self-Modifying AI Agent Populations: Conserving Authority across Replacement, Forking, and Rollback](https://mlsanity.com/paper/2610.00347/) (2026)

## Abstract (arXiv)

Self-evolving agents violate the assumption behind most learning-theoretic guarantees: the data, evaluator, components, and hypothesis space are produced by the policy being updated. We present SEA, an architecture that confines self-modification to a small steering adapter and a versioned harness around a frozen base model and admits each modification only through an anytime-valid gate that emits an auditable certificate against a fixed error budget. Five loop controllers compose published guarantees; because such gates can only select among behaviors the frozen base already produces, five verifier-in-the-loop mechanisms -- best-of-N, micro-step search, self-authored reproduction oracles, search-layer control, and self-repair -- supply the dense, grader-free signal the gates require, computed from the issue text alone. On a 52-instance SWE-bench Verified subset across four base models, base capability is the dominant, confound-free effect, and on two strong base models a deliberate no-op-composite control isolates the suite's contribution at +4 and +5 (textscGlm~5.2 24→28; textscGpt 29→34, the 65% best), with event logs confirming that its mechanisms fire and prevent regressions. Results are single-run on expensive evaluations; confirming run-to-run variance and adapting the per-task algorithm mix are future work.