PROTEUS: Provable Self-Evolution for Skill-Composing Language Agents

Self-evolving language agents continuously rewrite their own skills, prompts, and tool repertoires in response to feedback collected during deployment. Existing systems demonstrate strong empirical gains, but their mutation, evaluation, and selection steps are usually specified operationally rather than as analyzable stochastic updates, making long-run drift, reward hacking, or collapse difficult to characterize. We introduce PROTEUS, a framework that recasts agent self-evolution as constrained stochastic optimization over a structured space of skill graphs. PROTEUS contributes three coupled advances. First, Reflection-Guided Mutation (RGM) uses an LLM-conditioned mutation operator whose proposal is divergence-calibrated against a trace-suppressed reference proposal, limiting abrupt edits without requiring model logits or weight access. Second, a Capability-Map Posterior tracks per-skill competence with explicit uncertainty, replacing the unbiased-evaluation assumption made by prior work. Third, we analyze a support-preserving selection update that mixes a high-scoring elite-anchor distribution with the full proposal distribution; under smoothness, bounded-noise, divergence-calibration, and local update-alignment assumptions, PROTEUS satisfies a conditional stationarity-neighborhood bound for a smooth reward surrogate. Separately, the selection step admits a controlled KL-drift guarantee on the pre-resampling mixture distribution. We instantiate PROTEUS on an agent runtime API-compatible with widely deployed personal-agent platforms, and document an experimental protocol and evaluation suite spanning repository-level program repair, scientific literature synthesis, and long-horizon tool use.