CoChat
Sign Up
PreprintCited by 2Evolutionary Algorithms and ApplicationsSoftware Engineering ResearchAdvanced Software Engineering Methodologies

Self-Evolving Agents with Anytime-Valid Certificates

Open access
Sengupta, Biswa·2026·arXiv
DOI 10.48550/arxiv.2607.00871arXiv 2607.00871
Open this paper in CoChat — free accountOpen PDF

Abstract

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 \textbf{SEA}, an architecture that confines self-modification to a small steering adapter and a versioned harness around a \emph{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 \emph{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$ (\textsc{Glm}~5.2 $24\to28$; \textsc{Gpt} $29\to34$, 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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2607.00871

Cites

2 of 2 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

  • Performative Reinforcement Learning

    Mandal, D., Triantafyllou, S., & Radanovic, G. (2022) · arXiv · doi:10.48550/arxiv.2207.00046 · cited 3×

    “Whether unbiasedness and these rates carry to the performative MDP [Mandal et al., 2023] across rounds is a conjecture we do not prove: a fully-predictive ˜ U must be learnable, the recency-weighted contribution estimate reintroduces a bias their theorem does not cover, and the regret statement is…”
    Influential

  • SGM: A Statistical Godel Machine for Risk-Controlled Recursive Self-Modification

    Wu, X., Yin, S., Kang, Y., Zhang, X., Xu, Q., Chen, Z., & Zhang, W. (2025) · arXiv · doi:10.48550/arxiv.2510.10232 · cited 4×

    “…with familywise control under Ville’s inequality [Ramdas et al., 2023], the confirm-triggered harmonic spending of the Statistical Gödel Machine [Wu et al., 2025], the time-uniform confidence sequence of Howard et al. [2021], and the abstention semantics of safe policy improvement [Thomas et…”
    Influential

Flagged first, then by citations

Research works printed but not linked: 38

  1. Mehdi Abbana Bennani, Thang Doan, and Masashi Sugiyama. Generalisation guarantees for continual learning with orthogonal gradient descent. In 4th Lifelong Machine Learning Workshop at ICML, 2020. arXiv:2006.11942. · arXiv
  2. Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. In Proceedings of the 25th International Conference on Artificial Intelli- gence and Statistics (AISTATS), volume 151 of PMLR, pages 1805-1845, 2022. arXiv:2201.08905. · arXiv
  3. Vivek S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, 2008.
  4. Matthew Bowers, Theo X. Olausson, Lionel Wong, Gabriel Grand, Joshua B. Tenenbaum, Kevin Ellis, and Armando Solar-Lezama. Top-down synthesis for library learning. Proceedings of the ACM on Programming Languages, 7(POPL):41:1-41:32, 2023. arXiv:2211.16605. · arXiv
  5. Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024. · arXiv
  6. Yash Chandak, Scott M. Jordan, Georgios Theocharous, Martha White, and Philip S. Thomas. Towards safe policy improvement for non-stationary MDPs. In Advances in Neural Information Processing Systems (NeurIPS), 2020. arXiv:2010.12645. · arXiv
  7. Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian-Guang Lou, and Weizhu Chen. CodeT: Code generation with generated tests. In International Conference on Learning Representations (ICLR), 2023. arXiv:2207.10397. · arXiv
  8. Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language mod- els to self-debug. In International Conference on Learning Representations (ICLR), 2024. arXiv:2304.05128. · arXiv
  9. Ben Chugg, Hongjian Wang, and Aaditya Ramdas. A unified recipe for deriving (time-uniform) PAC- Bayes bounds. Journal of Machine Learning Research, 24(372):1-61, 2023. arXiv:2302.03421. · arXiv
  10. Antoine Cully and Yiannis Demiris. Quality and diversity optimization: A unifying modular framework. IEEE Transactions on Evolutionary Computation, 22(2):245-259, 2018.
  11. Ashok Cutkosky. Parameter-free, dynamic, and strongly-adaptive online learning. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of PMLR, 2020.
  12. Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt, Luc Cary, Armando Solar-Lezama, and Joshua B. Tenenbaum. DreamCoder: Bootstrapping inductive program synthesis with wake-sleep library learning. In Proceedings of the 42nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2021. arXiv:2006.08381. · arXiv
  13. Mehrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li. Orthogonal gradient descent for continual learning. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108 of PMLR, pages 3762-3773, 2020. arXiv:1910.07104. · arXiv
  14. Lior Friedman and Ron Meir. Data-dependent and oracle bounds on forgetting in continual learning. In Conference on Lifelong Learning Agents (CoLLAs), 2025. arXiv:2406.09370. · arXiv
  15. Shi Fu, Yingjie Wang, Yuzhu Chen, Xinmei Tian, and Dacheng Tao. A theoretical perspective: How to prevent model collapse in self-consuming training loops. In International Conference on Learning Representations (ICLR), 2025. arXiv:2502.18865. · arXiv
  16. Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202 of PMLR, pages 10835-10866, 2023. arXiv:2210.10760. · arXiv
  17. Matthias Gerstgrasser, Rylan Schaeffer, Apratim Dey, Rafael Rafailov, et al. Is model collapse inevitable? breaking the curse of recursion by accumulating real and synthetic data. In Conference on Language Modeling (COLM), 2024. arXiv:2404.01413. · arXiv
  18. Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, et al. Reinforced self-training (ReST) for language modeling. arXiv preprint arXiv:2308.08998, 2023. · arXiv
  19. Anna Harutyunyan, Will Dabney, Thomas Mesnard, Mohammad Gheshlaghi Azar, Bilal Piot, Nicolas Heess, Hado van Hasselt, Greg Wayne, Satinder Singh, Doina Precup, and Rémi Munos. Hindsight credit assignment. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
  20. Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparamet- ric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055-1080, 2021.
  21. Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations (ICLR), 2022. arXiv:2106.09685. · arXiv
  22. Carlos E. Jiménez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. SWE-bench: Can language models resolve real-world GitHub issues? In International Conference on Learning Representations (ICLR), 2024. arXiv:2310.06770. · arXiv
  23. Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2021. arXiv:2104.08691. · arXiv
  24. Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics (ACL), 2021. arXiv:2101.00190. · arXiv
  25. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, et al. Self-refine: Iterative refinement with self-feedback. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
  26. Alexander Meulemans, Simon Schug, Seijin Kobayashi, Nathaniel Daw, and Greg Wayne. Would I have gotten that reward? long-term credit assignment by counterfactual contribution analysis. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
  27. Jean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909, 2015. · arXiv
  28. Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
  29. Anastasia Pentina and Christoph H. Lampert. A PAC-Bayesian bound for lifelong learning. In Proceedings of the 31st International Conference on Machine Learning (ICML), volume 32 of PMLR, pages 991-999, 2014.
  30. Juan C. Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of PMLR, pages 7599-7609, 2020. arXiv:2002.06673. · arXiv
  31. Aaditya Ramdas, Peter Grünwald, Vladimir Vovk, and Glenn Shafer. Game-theoretic statistics and safe anytime-valid inference. Statistical Science, 38(4):576-601, 2023. arXiv:2210.01948. · arXiv
  32. Jürgen Schmidhuber. Gödel machines: Self-referential universal problem solvers making provably optimal self-improvements. arXiv preprint cs/0309048, 2003. · arXiv
  33. Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
  34. Ilia Shumailov, Zakhar Shumaylov, Yiren Zhao, Nicolas Papernot, Ross Anderson, and Yarin Gal. AI models collapse when trained on recursively generated data. Nature, 631(8022):755-759, 2024.
  35. Philip S. Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High confidence policy improvement. In Proceedings of the 32nd International Conference on Machine Learning (ICML), volume 37 of PMLR, pages 2380-2388, 2015.
  36. Philip S. Thomas, Bruno Castro da Silva, Andrew G. Barto, Stephen Giguere, Yuriy Brun, and Emma Brunskill. Preventing undesirable behavior of intelligent machines. Science, 366(6468):999-1004, 2019.
  37. Daniil Tiapkin, Daniele Calandriello, Denis Belomestny, Eric Moulines, Alexey Naumov, Kashif Rasul, Michal Valko, and Pierre Ménard. Proximal point nash learning from human feedback. arXiv preprint arXiv:2505.19731, 2025. v1 titled "Accelerating Nash Learning from Human Feedback via Mirror Prox (Nash-MP)". · arXiv
  38. Mingzhi Wang, Chengdong Ma, Qizhi Chen, Linjian Meng, Yang Han, Jiancong Xiao, Zhaowei Zhang, Jing Huo, Weijie J. Su, and Yaodong Yang. Magnetic preference optimization: Achieving last-iterate convergence for language model alignment. In International Conference on Learning Representations (ICLR), 2025. arXiv:2410.16714. · arXiv

Cited by

Sorted by citations

Authors
Sengupta, B.
Corresponding author
Sengupta, Biswa
ORCID
Sengupta, Biswa
Venue
arXiv
Publisher
arXiv
Published
2026
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2607.00871
arXiv
2607.00871
OpenAlex
W7167043588
Cited by
0
References
2
Type
posted content
Language
en
Open access
Licence
Locations
  • arXiv (Cornell University) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
  • Physical Sciences › Computer Science › Information Systems › Software Engineering Research
  • Physical Sciences › Computer Science › Artificial Intelligence › Advanced Software Engineering Methodologies
Keywords
self-evolving agents, self-modification, error budget, SWE-bench Verified, code generation, self-healing, reproducibility

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review