# Trace Evolution Bench: Measuring Whether Agents Improve from Their Own Environment Traces

> Trace Evolution Bench isolates attributable self-evolution gains from evaluation noise via frozen rescoring and seed-matched excess, revealing endpoint gains alone overstate progress.

- **Source:** [arXiv](https://arxiv.org/abs/2610.15055)
- **Published:** 2026-11-07
- **Permalink:** https://picx.dev/p/aLSshX
- **Whiteboard:** https://picx.dev/p/aLSshX/image

## Summary

## 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):

| Property | Office | Coding | Manufacturing |
|---|---|---|---|
| Source | Product-usage workflows | 142 merged PRs rewritten as functions | 12 real tables; 31 real questions, 109 generated |
| Items | 10 families | One family, fix bug | 13 families |
| Outside evolution | 12/40 | None on held-out | 12/40 |
| Tools | list files, read file, write file, publish artifact, grant access, submit | list dir, read file, write file, run tests, submit | list tables, describe table, execute sql, submit answer |
| Success | Every terminal check passes | Hidden unit tests pass | Score ≥ 80 (SQL 40, result 40, answer 20) |
| Step cap | 20 | 12 | 12 |

### 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):

| Method | Injected Text |
|---|---|
| gepa_llm | One revised instruction; validation gate accepts or rolls back |
| ace_llm | A grow-and-refine playbook from a generator, reflector, and curator |
| expel_llm | A deduplicated pool of insights from success and failure |

---

## 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:

| Seed | r0 | r1 | r2 | r3 | Gain | Range (Band) |
|---|---|---|---|---|---|---|
| 42 | 67.5 | 67.5 | 65.0 | 60.0 | −7.5 | 7.5 |
| 43 | 62.5 | 65.0 | 62.5 | 60.0 | −2.5 | 5.0 |
| 44 | 62.5 | 62.5 | 65.0 | 52.5 | −10.0 | 12.5 |

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

| Method | Seed | Gain | Frozen | Excess | Band | Against Band |
|---|---|---|---|---|---|---|
| gepa | 42 | +7.5 | −7.5 | **+15.0** | 7.5 | outside |
| gepa | 43 | +12.5 | −2.5 | **+15.0** | 5.0 | outside |
| gepa | 44 | −22.5 | −10.0 | −12.5 | 12.5 | equal, down |
| ace | 42 | +12.5 | −7.5 | **+20.0** | 7.5 | outside |
| ace | 43 | +7.5 | −2.5 | **+10.0** | 5.0 | outside |
| ace | 44 | 0.0 | −10.0 | +10.0 | 12.5 | inside |
| expel | 42 | +7.5 | −7.5 | **+15.0** | 7.5 | outside |
| expel | 43 | +5.0 | −2.5 | **+7.5** | 5.0 | outside |
| expel | 44 | +10.0 | −10.0 | **+20.0** | 12.5 | outside |

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.

---

_Markdown view of https://picx.dev/p/aLSshX, served by PicX — AI-generated visual whiteboard summaries of research papers._