Summary (Overview)

• Trace Evolution Bench (TEB) is a new evaluation protocol for self-evolving agents that isolates attributable improvement from evaluation noise, rather than reporting endpoint Gain alone.
• Four core controls: locked held-out identifiers (never entering evolve()), validation-gated accept/rollback (min delta = 0), repeated frozen "no evolve" rescoring (four passes), and seed-matched paired excess against each seed's own noise band.
• Key finding on coding (primary scoreboard): DeepSeek v4 Pro under "no evolve" keeps version $M_0$ yet shifts by 7.5, 5.0, and 12.5 percentage points across seeds, showing that endpoint Gain alone overstates progress.
• Cross-model reproducibility: Seven of nine DeepSeek text-update cells exceed their seed bands, but this pattern does not reproduce on GLM and MiniMax; no method remains above its own band on every seed of all three models.
• Control packs: Office DeepSeek does not exceed its seed bands (widest 17.5 pp), and manufacturing has no paired positive excess beyond its seed band.

---

Introduction and Theoretical Foundation

Most agent benchmarks freeze a policy and score static capability (e.g., SWE-bench, AgentBench, ReAct-style loops). Self-evolving systems pose a different measurement problem: whether post-update improvement is attributable to the evolution procedure rather than to evaluation noise or protocol mismatch.

The paper identifies several confounds that undermine naive Gain reporting:

• Teacher traces substituting for self-generated traces (Ross et al., 2011)
• Evaluation targeting a checkpoint different from the artifact returned by evolve()
• Held-out ids leaking into the update (Magar and Schwartz, 2022)
• Text updates and weight updates compared under one budget axis (Henderson et al., 2018)

Reporting Success % alone can hide weak round-0 baselines (Liang et al., 2023); reporting Gain from one stochastic round-0 pass can credit frozen rescoring variance as evolution (Dodge et al., 2019).

The core measurement problem is formalized as follows. Let $\text{Succ}(M) = \#\{\text{held-out pass}\}/n$ be the success rate on locked held-out ids. The Gain metric is defined as:

$$\text{Gain}(M_r) = 100 \times \left( \text{Succ}(M_r) - \text{Succ}(M_0) \right), \tag{1}$$

with this-run $M_0$ as the round-0 score. The noise band for actor $a$, pack $e$, and seed $s$ is the range of four frozen no-evolve held-out passes:

$$B(a, e, s) = 100 \times \left( \max_k \text{Succ}(M^{(0)}_{a,e,s,k}) - \min_k \text{Succ}(M^{(0)}_{a,e,s,k}) \right). \tag{2}$$

Paired excess uses the same actor, pack, and seed:

$$\text{Excess} = \text{Gain}_{\text{method}}(a, e, s) - \text{Gain}_{\text{no evolve}}(a, e, s). \tag{3}$$

An excess inside that seed's own band $B(a, e, s)$ is not reported as evolution.

---

Methodology

Protocol Structure (Three Stages)

1. Global evaluation contract: Freeze the pack (held-out never enters evolve()), score packs apart, round 0 scores $M_0$ without calling evolve().
2. Per-round mechanics (rounds $r \geq 1$): Collect a disjoint slice of evolution episodes, call evolve() once, accept the proposal iff validation success ≥ current agent's (min delta = 0), otherwise roll back, then score the accepted agent on the same held-out ids.
3. Seed-wise attribution rule: Compare each seed against its own four-pass noise band.

Key Protocol Mechanics

• Held-out lock: Held-out ids never enter evolve(); success is scored on the accepted artifact, not used as the accept test.
• Validation gate: A proposal is accepted only when validation success does not fall (min delta = 0); otherwise rolled back.
• Budget classes: B0 text updates are not ranked against B2 weight updates (including LoRA-style training).
• Evolution-token cap: 500,000 tokens per round, summed from per-step usage on evolution tasks only (validation/held-out not counted). Crossing the cap skips evolve(), marks "over budget", and skips later rounds.
• Runner eligibility: A frozen no-evolve cell can pass eligibility while agent version stays $M_0$.
• Paper-min defaults: $R=3$; at least three seeds (Bouthillier et al., 2021); at least 40 evolution ids, 10 validation, 20 held-out; $M_0$ inside $[0.10, 0.80]$ or the run is flagged; human edits = 0.

Pack Structure

Each of three packs has 140 tasks split 80/20/40 (so held-out $n = 40$, 2.5 pp per task):

Method Adapters (Text Updates)

Three scored methods were fixed before held-out reading via an office validation screen (mean screen gains were 0, −5.6, and −11.1 pp, none positive):

---

Empirical Validation / Results

Coding (Primary Scoreboard)

DeepSeek no-evolve noise bands (Table 6): Version stays $M_0$ at every round, yet Gain is negative on all three seeds:

DeepSeek paired excess (Table 8): Seven of nine cells are positive and larger than their seed's own band:

All seven cells above their bands have final regression at or below 0.20. gepa_llm seed 44 moves down by the width of its band (excess −12.5, regression 0.48).

GLM and MiniMax do not reproduce the pattern (Table 9). On GLM: only expel_llm seeds 43 and 44 clear their bands (+10.0 and +22.5 against bands 7.5 and 15.0). MiniMax: only expel_llm seed 44 clears its 12.5 band (+15.0), with final regression 0.30. GLM expel_llm seed 42 is unpaired (round-0 gap of 67.5 pp), as are MiniMax gepa_llm and ace_llm seed 43.

Manufacturing (Control Pack)

No finished DeepSeek manufacturing cell has a positive excess larger than its seed band. All three ace_llm excesses are −2.5. expel_llm seed 44 is +2.5 (equal to the 2.5 band). MiniMax has two excesses outside seed bands (ace_llm seed 43 and gepa_llm seed 44), but both are not the same starting draw (round-0 gaps ≥ 10 pp), and all nine MiniMax method cells have final regression above 0.20.

Office (Control Pack)

No DeepSeek office cell has a positive excess larger than its own seed band. Mean excesses: −2.5 pp (gepa_llm), −3.3 pp (ace_llm), +4.2 pp (expel_llm), all inside the widest 17.5 pp range. The incident track, postmortem, and onboarding families stay at zero solved tasks on every pass. MiniMax expel_llm excess is +7.5 pp (2.5 pp past its 5.0 pp band) on one seed at final version $M_1$ — not a confirmed evolution result.

---

Theoretical and Practical Implications

1. Endpoint Gain conflates evolution with noise: The DeepSeek no-evolve result is the clearest demonstration — version $M_0$ stays fixed while scores move 7.5–12.5 pp. Any benchmark reporting raw Gain without a frozen rescore band is vulnerable to this confound.

2. Attribution-first contract: TEB provides a falsifiable protocol where self-evolution claims must be measured as paired excess against a per-seed noise band, not as an endpoint delta. This separates "scoring evidence" from "ranking policy."

3. Cross-model generalizability is limited: The seven-of-nine pattern on DeepSeek does not reproduce on GLM or MiniMax. This suggests that evolution method effectiveness is model-dependent, and a single-model result should not be over-generalized.

4. Strict controls eliminate false positives: Round-0 pairing checks (10 pp cutoff) remove cells where the method and no-evolve draw start from different points. Unpaired cells (e.g., GLM expel_llm seed 42 with a 67.5 pp gap) must be excluded from attribution claims.

5. Practical methodology for the community: The four controls (locked held-out, validation gate, frozen rescoring, seed-matched excess) constitute a reusable template for evaluating self-evolving agents, applicable across domains with different success criteria (unit tests, rule-based checks, deterministic scoring).

---

Conclusion

TEB's main result is attribution, not a single global winner. The separation between observed Gain and attributable Excess is the core contribution: TEB turns self-evolution claims into a falsifiable protocol with explicit controls rather than a single endpoint delta.

Key takeaways:

• Endpoint Gain includes frozen rescoring variance — DeepSeek no-evolve shifts 7.5–12.5 pp across seeds while keeping version $M_0$.
• Seven of nine DeepSeek text-update cells lie above their own bands on coding, but this pattern does not reproduce on GLM and MiniMax.
• No method stays above its own band on every seed of all three models.
• Office and manufacturing serve as independent control packs; neither shows consistent attributable improvement.

Limitations: Coding held-out is one family (n=40); GLM adapters and MiniMax ace_llm crossed the evolution-token cap; closed hosted models were not weight-updated; effects under the 17.5 pp DeepSeek office band are unresolved by this design.

Future directions implied by the paper include: broader held-out families, more seeds per model, open-weight B2 cards, and extending the contract to additional evolution methods and domains.