Self-Evolving Agents with Anytime-Valid Certificates
06:00 · July 2, 2026 · arXiv cs.AI RSS
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.
Summary
Self-evolving agents create an endogenous loop in which the policy under update also generates its training data, evaluators, components, and hypothesis space, violating the fixed-environment assumptions that underpin most learning-theoretic guarantees. SEA addresses this by freezing the base model and restricting all self-modification to a low-dimensional steering adapter plus a versioned harness. Every change must pass through an anytime-valid gate that issues an auditable certificate against a pre-allocated error budget, preserving the applicability of published stability and regret bounds even when the distribution shifts with the policy.
Five loop controllers manage distinct failure modes—stability-plasticity trade-offs, self-referential collapse, credit assignment, verifiable self-modification, and hypothesis-space growth—by composing existing guarantees with performative-stability and anytime-valid inference machinery. Because gates can only select among behaviors already latent in the frozen base, the architecture supplies dense, grader-free signals through five verifier-in-the-loop mechanisms: best-of-N sampling, micro-step search, self-authored reproduction oracles, search-layer control, and self-repair. These mechanisms operate from issue text alone and are admitted only when they demonstrably fail on the unpatched base.
On a 52-instance subset of SWE-bench Verified, base-model capability remains the dominant factor across four evaluated models. When a deliberate no-op composite isolates the contribution of the controller suite on two strong bases, the reported single-run lifts are +4 for GLM 5.2 (24 to 28) and +5 for GPT (29 to 34, the top 65 % of instances). Event logs confirm that the gates fire as intended and block regressions. The authors note that run-to-run variance and per-task algorithm adaptation remain open for subsequent measurement.
Why it matters
This research is highly relevant for Dutch AI researchers and practitioners because it addresses the critical need for auditable and safe autonomous agents, aligning perfectly with the EU AI Act's emphasis on transparency and risk management. The introduction of anytime-valid certificates provides a mathematically grounded approach to deploying self-evolving AI in enterprise environments.
