acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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.

Primary area:
optimization
Keywords:
language agents, self-evolution, skill composition, stochastic optimization, theoretical guarantees

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_tMyiOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

PROTEUS formulates self-evolution of skill-composing agents as stochastic mutation, evaluation, and selection updates. It combines bounded reflection-guided mutation, Beta competence posteriors, lower-confidence scoring, and an elite/full-candidate selection mixture. Under explicit assumptions, the paper analyzes stationarity of a reward surrogate and a pre-resampling selection-KL bound. Evaluation covers program repair, literature synthesis, and long-horizon tool use; five-seed results improve over the strongest reported baselines by 5.4, 3.9, and 6.3 percentage points, with additional ablations and diagnostics

Critical strengths

Decomposing self-evolution into mutation, evaluation, and selection with explicit noise, drift, and local-alignment conditions is a useful conceptual contribution. It provides a common framework for discussing evolutionary systems beyond their final task scores. The paper also distinguishes analysis of the reward surrogate from the full diversity-regularized objective. This formulation has merit independently of the proof concerns below.

Critical weaknesses
  1. For the stated Q=Unif(32), H=Unif(4), and Pbar=0.8Q+0.2H, elite/nonelite masses are 0.075/0.025. Hence KL(Pbar$\Vert$Q)=4×0.075×ln(2.4)+28×0.025×ln(0.8)=0.10644 nats, independent of candidate rewards at these fixed settings. Figure 2's fluctuating curve and approximately 0.78 peak, and Table A.8's 0.62 median, cannot measure this quantity. The conflict directly undermines the empirical support for controlled selection drift; being below the theoretical bound does not resolve it.
  2. The stationarity proof accumulates improvements for the pre-resampling mixture Pbar, whereas the next iteration uses a finite resampled population P. These terms do not automatically telescope without an expectation relation or a resampling-error argument, leaving applicability to Algorithm 1 insufficiently established. Also, removing nonelite support can make reverse KL(Q$\Vert$H) infinite, not forward KL(H$\Vert$Q), making the selection-drift discussion internally inconsistent
Questions for authors
  1. What quantity is actually computed in Figure 2 and Table A.8? Please provide Q, H, and Pbar probability vectors and the log base for one iteration. If implementation uses nonuniform weights, dynamic parameters, or duplicate aggregation, how does it relate to the stated algorithm and theorem?
  2. Which proof step transfers the improvement bound for Pbar to the next finite population P? Is the theorem in expectation, does it include a resampling-error term, or does it analyze only a virtual-distribution process
Reviewer_GMXFOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

PROTEUS evolves a population of agents represented as skill graphs. It combines bounded edits guided by reflection, Beta-based capability estimates, and elite selection that also considers diversity. The selected elites are mixed with the full candidate pool. The paper gives a conditional stationarity result and a bound on selection KL, then reports experiments on program repair, literature synthesis, and tool use. Ablations examine evaluator uncertainty, divergence calibration, and diversity.

Critical strengths

1. Writing out the update rule helps readers understand the method. The paper separates mutation from selection and distinguishes the reward surrogate from the diversity objective, making it easier to see which parts the analysis covers.

2. The posterior and evaluator-noise ablations ask a useful question: can noisy evaluation lead to poor edits? Reported repair performance drops from 43.6% to 36.4% without the posterior. This is promising, although the evaluation details below need to be resolved.

Critical weaknesses

1. The experiments are too briefly described to check. Section 6 is about 1.5 pages, and the combined discussion/conclusion is just one sentence. Appendices C–E still leave out the exact benchmark subsets, held-out task counts and splits, literature/tool tasks, and evaluation rubrics. Table A.4 lists prompt roles rather than actual prompts. These omissions make it hard to assess the main empirical claims.

2. I can't reconcile the selection KL with the algorithm. For Q uniform over 32 candidates, H uniform over 4 anchors, and rho=0.8, KL(0.2H+0.8Q || Q)=0.3 ln(2.4)+0.7 ln(0.8), or about 0.1064 nats, whichever anchors are chosen. Yet Figure 2 peaks at 0.78, the full-method row of Table A.8 gives 0.62, and Table A.9 gives 0.43–0.84 with other hyperparameters fixed. The distributions or estimator behind these numbers need to be explained before they can validate the stability claim.

3. The explanation of the support guarantee uses the wrong KL direction. Restricting H to a subset of Q's support does not make KL(H || Q) infinite: for 4 anchors from 32 uniform candidates, it is ln(8). It is KL(Q || H) that becomes infinite. The upper bound itself is valid under the stated assumptions, but the claim that the mixture prevents infinite forward KL needs to be corrected.

4. The stationarity result is explicitly conditional, but I couldn't tell whether it gives a useful guarantee for the implemented agent. Assumption 4 requires gradient-aligned updates, while the concrete analysis map, reward surrogate, and diagnostic proxy are not specified. Figure A.1 labels the gradient of F(P), although Theorem 1 analyzes f(u). The relationship between these quantities and the alignment constants needed to evaluate the bound are still unclear.

5. I couldn't reconstruct the proposal-divergence calibration, which is central to the mutation operator. Section 4.1 cites Cheng et al. (2024) for a bias-corrected Jensen–Shannon estimator, but I couldn't find it in the cited BPO paper. Appendix C.3 gives a tuning procedure, but not the estimator or number of samples used to estimate JS. The targets 0.85 and 0.92 also need a stated log base or normalization, since natural-log JS is bounded by ln(2). Without these details, it is unclear how proposal drift is measured and controlled.

Questions for authors

1. Can you identify the exact evaluation datasets, held-out counts and splits, and literature/tool rubrics, and provide the actual prompts used for generation and evaluation? Which artifacts reproduce Table 1?

2. Which probability vectors and estimator produced Figure 2, the full-method row of Table A.8, and Table A.9? Could you provide one iteration's distributions and reconcile the values with 0.1064 nats? Does the argument about preventing infinite KL concern reverse KL instead?

3. What feature map, reward surrogate, and gradient proxy produced Figure A.1, and how does the plotted F(P) relate to the theorem's f(u)? How are gamma and the alignment error estimated or bounded, and does Equation 3 give a useful bound at the reported settings?

4. Could you provide the exact Jensen–Shannon estimator and its correct reference, the number of samples from each proposal, and the log base or normalization? How were these used to calibrate the 0.85 and 0.92 targets?

Reviewer_fyFnOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper addresses the lack of formal guarantees in self-evolving language agents, whose mutation, evaluation, and selection steps are usually heuristic. It proposes PROTEUS, which frames self-evolution as constrained stochastic optimization over skill graphs. The framework combines an LLM mutation operator calibrated to a divergence target, Bayesian per-capability competence posteriors used for lower-confidence-bound selection, and a support-preserving elite-anchor mixture. Under explicit assumptions, this yields a conditional stationarity bound and a KL-drift bound. On program repair, literature synthesis, and long-horizon tool use, PROTEUS beats six baselines, including the Darwin Gödel Machine, by 3.9 to 6.3 points. Ablations show the competence posterior contributes most to the gains.

Critical strengths
  • Self-evolving agents are spreading quickly, and the lack of formal analysis of drift, reward hacking, and collapse is a real gap
  • Framing self-evolution as constrained stochastic optimization over skill graphs gives a clean, analyzable structure. The solution allows for an easy deployment as an inference-time solution in API-based models.
Critical weaknesses
  • The main theorem assumes the LLM’s updates already move in a gradient-like direction, which is the hard part. Smoothness, bounded noise, and especially the alignment assumption can’t really be verified for an LLM-driven system. Additionally, the divergence target η*, presented as a main contribution, appears in neither bound.
  • The experiments lack robustness. The benchmarks aren’t named, the compute budget seems too small for the number of evaluations claimed, the synthesis task may be graded by the same kind of LLM judge used for selection.
  • The improvements could come from simple engineering choices (smaller edits, less noisy scoring) rather than anything the analysis captures. There’s no experiment linking the bounds to performance.
  • Presentation-wise, the paper feels unfinished. A one-sentence conclusion, an empty appendix section, and results described only in words suggest it was rushed.I would suggest polishing the paper and resubmitting to the next venue.
Questions for authors
  • Which exact benchmarks and splits were used for program repair, literature synthesis and tool use? How many task instances does each contain?
  • How were baselines like OpenClaw-RL, an RL training method, run “as published” under a fixed 4-hour inference budget?
  • Is the rubric judge used for final scoring in literature synthesis separate from the judge used during selection? If not, how do you rule out the method overfitting to the judge?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.