acceptodds
Under review as a conference paper at ICLR 2027

EvoTrace: Benchmarking Self-Evolving Agents on Procedural Tasks through Experience-to-Behavior Tracing

Abstract

Large language model (LLM) agents deployed in professional domains repeatedly encounter requests governed by the same underlying procedure, where a missed operation, conditional decision, or dependency can invalidate an execution. For self-evolving agents that seek to improve from experience, effective evolution requires extracting reusable procedural knowledge from prior task interactions and correctly applying it to new requests. However, existing benchmarks mainly reveal aggregate performance changes or the quality of retained knowledge, leaving it unclear which procedural requirements are actually learned and where the experience-to-behavior pathway breaks down. We introduce EvoTrace [GitHub](https://anonymous.4open.science/r/EvoTrace-20271), a benchmark that uses Agent-Executable Standard Operating Procedures (AE-SOPs) as a common reference to track each procedural requirement across actual experience, explicit retention, and held-out execution. EvoTrace comprises 115 AE-SOPs across seven professional domains and 10,792 executable instances. Experiments across *eleven* representative self-evolution methods show that effective evolution cannot be inferred from either the form or the coverage of retained knowledge alone: similar forms can accompany substantially different gains, while broader coverage does not necessarily translate into more reliable execution. Instead, different mechanisms exhibit distinct bottlenecks in how procedural requirements progress through the experience-to-behavior pathway, and these vulnerabilities vary across requirement types. Targeting the identified bottlenecks with lightweight interventions improves subsequent execution.

Primary area:
datasets and benchmarks
Keywords:
Procedural Task, Self-Evolving Agents

Reviews

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

This paper proposes EVOTRACE, a benchmark for evaluating self-evolving LLM agents on procedural tasks. The core concept, AE-SOP (Agent-Executable Standard Operating Procedure), formalizes standard operating procedures as a graph structure with operation nodes, decision nodes, and dependency edges, hidden from the agent and used only as evaluation ground truth. The benchmark covers 115 AE-SOP families and 10,792 executable instances, drawn from six major procedural sources (τ-bench, SOPBench, etc.) and seven application domains. The core contribution is an "experience → retention → execution" three-stage tracing framework that can pinpoint whether a specific procedural requirement was never encountered in experience, encountered but not retained, or retained but incorrectly executed, accompanied by a metric suite (FSR, AMR, KP/KR/KC, K2B). The authors evaluate 11 representative self-evolving mechanisms on two backbones, GPT-5.6-Terra and Qwen3.8-Flash-Next.

Critical strengths

This paper establishes a requirement-level pathway tracing mechanism (experience → retention → execution), supported by theory. Theorems H.1-H.4 prove that aggregate metrics cannot uniquely determine the execution success rate distribution of retained requirements, providing formal justification for the necessity of fine-grained diagnosis rather than relying on intuition alone. The experiments show that broader coverage ≠ more reliable execution and validate the actionability of diagnostic conclusions through targeted interventions.

Critical weaknesses
  1. In the experiment, the false acceptance rate for execution-based judgments was as high as 34.5%, the inconsistency rate between native and procedural successful judgments was 20.5%, and the AMR corrections showed opposite signs on the two backbones. The authors should provide more discussion on these biases.

  2. The paper does not provide a sensitivity analysis of the errors on downstream diagnostic conclusions, making it difficult for readers to determine how many specific "bottleneck attributions" are reliable.

  3. The diagnostic framework is essentially more of a descriptive association than a causal mechanism. Although the intervention experiments showed positive effects, there was a lack of control over confounding variables (e.g., retention repair might simultaneously improve product quality and trigger better in-context inference on the backbone). The authors should supplement this with more ablation experiments or case studies.

Questions for authors
  1. Could you provide an estimate of the propagated uncertainty of measurement error on core diagnostic metrics such as K2B and KC?

  2. AE-SOP extraction uses Claude Opus 4.8, GPT-5.6-sol, and Qwen3.8-2.4T-A95B, while the evaluation backbones are GPT-5.6-Terra and Qwen3.8-Flash-Next from the same families. Could this model-family overlap cause the extracted AE-SOPs to implicitly favor the procedural reasoning patterns of the same model family, thereby affecting the relative ranking of different methods?

  3. Do you plan to conduct causal mediation analysis to verify which stage truly causes execution failure, rather than merely identifying bottlenecks at the correlational level?

6 comments
AuthorsOpenReview ↗

Response to Reviewer nR1o – 1

Thank you for your review and helpful comments.

W1/W2/Q1: Measurement errors, diagnostic metrics, and bottleneck attribution reliability

Concern: Further explanation is needed for errors in execution-based judgments, disagreement between native and procedural success judgments, and the opposite signs of AMR corrections on the two backbones. The propagated uncertainty of measurement error on K2B and KC needs to be estimated. Sensitivity analysis is also needed to assess the reliability of downstream diagnostic conclusions and bottleneck attributions.

Response: We add analyses of measurement errors, metric corrections, and conclusion stability (Appendix P). We use 60 complete trajectories and 50 linked records per backbone. Based on measurement errors, we recompute calibrated metrics and learning profiles for all 13 conditions, both backbones, and all five checkpoints. The corrections change some diagnostic states and reduce specific gaps between methods, while the key bottleneck contrasts and the association between diagnostic metrics and execution performance retain their original directions. Below, we address the biases, error propagation, and the reliability of diagnostic conclusions.

1. Error sources and discussion of biases (W1: execution-based judgments, native–procedural disagreement, and AMR corrections).

Two independent reviewers and one adjudicator establish the human reference. We calculate precision and recall for artifact extraction, and false acceptance and false rejection for exposure, artifact matching, and execution judgments (Table 23).

  • Execution-based judgment 34.5%: This is the conditional false-acceptance rate for dependency-execution judgments. Incorrectly accepting a prerequisite or dependency conceals an execution violation and may inflate the requirement completion rate of the corresponding trajectory. This can affect AMR, FSR, K2B, and the associated diagnostic states.
  • Inconsistency rate 20.5%: This is the disagreement rate between native success judgments and automatic procedural success judgments before the audit. This measures agreement between the two judgments at the trajectory level, but does not directly mean the error rate of either evaluator.
  • Opposite signs of AMR corrections: The net AMR correction depends on the relative contributions of false acceptance and false rejection, and on how errors are distributed across trajectories and applicable requirements. Correcting false acceptance lowers AMR, while correcting false rejection raises it. Opposite signs in a limited audit sample alone do not establish systematic biases in opposite directions on the two backbones.

2. Error propagation, metric correction, and intervals (Q1: propagated uncertainty; KC/K2B and FSR/AMR).

  • We map seven sources of measurement error to the references, evidence matching, metric computation, and diagnostic conclusions they affect (Table 24). We apply the corrections to KP, KR, KC, K2B, FSR, and AMR using the original metric definitions. We report paired changes in the audit sample and conditional calibration results across all experimental conditions separately.
  • For the 60 complete trajectories per backbone, we use 10,000 paired resamples to estimate 95% intervals for changes in FSR and AMR:
Audit sample: corrected minus original (pp, 95% interval)GPTQwen
FSR+3.3 [−6.7, 13.3]−1.7 [−11.7, 8.3]
AMR+0.5 [−2.9, 4.2]−2.4 [−5.0, 0.2]
  • Figures 36 and 38–39 present calibrated results for all six metrics across all 13 conditions, both backbones, and all five checkpoints. The main average changes across evolving methods are:
Conditional calibration: calibrated minus original (pp)GPTQwen
Final KC+3.2+3.2
Final K2B−2.8−4.0
Final FSR+0.7−1.5
Final AMR−2.1−3.3
FSR learning gain−1.5−1.8
  • Across evolving methods, the point estimates of K2B corrections range from −4.0 to −1.8 pp on GPT and from −5.0 to −3.3 pp on Qwen. The mean AMR correction across evolving methods is negative on both backbones.
AuthorsOpenReview ↗

Response to Reviewer nR1o – 2

3. Corrected states and the reliability of conclusions (W2: bottleneck attributions; Q1: downstream diagnostic conclusions).

  • Record-level changes. For the 50 linked records per backbone, the percentages of diagnostic-state and retained-miss changes are:
Record changes (%, 95% interval)GPTQwen
Changes in diagnostic states18.0 [8.0, 30.0]22.0 [12.0, 34.0]
Changes in retained-miss states22.0 [12.0, 34.0]18.0 [8.0, 30.0]
  • Method-level comparisons. We recompute artifact-absent execution misses and execution misses for operation, decision, and dependency requirements across all methods (Figure 37). The direction of the method-specific contrast remains stable on both backbones. For example, we compare decision artifact-miss rates for MemP-online and ReasoningBank:
BackboneGap before correctionCorrected MemP-onlineCorrected ReasoningBankGap after correction
GPT55.2 pp41.6%8.5%33.1 pp
Qwen57.8 pp43.0%7.9%35.1 pp
  • Process–outcome associations. After calibration, we report changes in the Pearson and Spearman correlations between the four process metrics and FSR/AMR, together with their intervals (Table 25). K2B remains the process metric with the strongest positive association with FSR and AMR on both backbones.
Pearson r: corrected minus original (interval)GPTQwen
K2B–FSR+0.077 [0.046, 0.109]+0.080 [0.050, 0.104]
KC–FSR+0.048 [0.021, 0.130]+0.043 [0.019, 0.117]
  • Together with the record-level changes, specific method comparisons, and learning curves across all five checkpoints, these analyses show how measurement errors affect states and effect sizes. They support the stability of the reported key diagnostic comparisons under the calibration.

Revision: §4.1, §6.6; Appendix P, Tables 23–25, Figures 36–39.

AuthorsOpenReview ↗

Response to Reviewer nR1o – 3

Q2: Model-family overlap and relative ranking

Concern: Model-family overlap between AE-SOP extraction and the evaluation backbones may cause the extracted AE-SOPs to favor the procedural reasoning patterns of the same model family, affecting the relative ranking of different methods.

Response: We add a leave-one-family-out reference sensitivity analysis. For each evaluation backbone, we exclude the proposer from the same model family when constructing the references, then evaluate the same 11 methods using the newly extracted references. The reference content changes, while the rankings for FSR, KC, and K2B remain highly consistent. All four core contrasts retain their directions on both backbones. Thus, extracted AE-SOPs generally do not favor the same model family or affect the relative ranking of different methods.

Main results:

MetricGPT backbone / No-GPTQwen backbone / No-Qwen
FSR ranking ρ0.9820.982
KC ranking ρ1.0001.000
K2B ranking ρ0.9910.991
FSR pairwise reversals2/552/55

The Jaccard similarity between the family-excluded and original references is approximately 0.86.

Revision: Appendix N.1, Table 21, Figure 28.

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

This paper presents EvoTrace, a benchmark for evaluating self-evolving agents on procedural tasks by leveraging AE-SOPs that represent procedural requirements as executable operations, conditional decisions, and dependencies. The benchmark traces individual procedural requirements across three stages: what the agent encounters in prior experience, what it explicitly retains in persistent artifacts, and what it subsequently realizes in held-out execution. The authors evaluate eleven representative self-evolution methods spanning case memories, knowledge banks, guidance documents, and skill libraries, using two backbone models. The study also shows that persistent representation type or knowledge coverage alone does not reliably predict downstream improvement.

Critical strengths

First, EvoTrace provides a useful requirement-level view of the self-evolution process. The most important contribution is the ability to align the same procedural requirement across experience, persistent artifacts, and downstream execution. This allows the benchmark to distinguish failures caused by insufficient exposure, failed retention, and failed realization, which cannot be determined from aggregate success rates alone.

Second, the cross-method study also produces meaningful findings rather than only a new leaderboard. The paper evaluates eleven representative methods spanning several persistent-representation paradigms and finds substantial variation even within the same artifact class. It also shows that knowledge coverage alone is a poor proxy for effective learning, while Knowledge-to-Behavior is much more strongly associated with downstream execution improvement.

Critical weaknesses

The paper does not provide sufficiently strong empirical evidence that existing benchmarks are inadequate relative to EvoTrace. The authors motivate EvoTrace by arguing that prior benchmarks typically evaluate task outcomes, artifact quality, or execution-time reuse separately and therefore cannot trace individual requirements across the complete learning pathway. This is good, but the paper would be substantially stronger if it directly demonstrated that conclusions drawn using existing benchmarks or their original evaluation metrics differ from those enabled by EvoTrace.

Questions for authors

Please provide a more direct comparison between EvoTrace and existing benchmark methodologies.

The paper is generally well structured, but the motivation in the introduction could be made more direct. For example, Figure 1 contains several task instances, states, interactions, and persistent artifacts at once, so the reader needs substantial effort to reconstruct the example before understanding the intended problem.

1 comment
AuthorsOpenReview ↗

Response to Reviewer navZ

Thank you for your review and helpful comments.

W1/Q1: Direct comparison with existing benchmarks

Concern: Stronger empirical evidence is needed to directly show how conclusions drawn using existing benchmarks or their original evaluation metrics differ from those enabled by EvoTrace.

Response: We add an evaluation-scope comparison table (Table 1), a comparison of running examples on the same case (Appendix A), and an empirical comparison of evaluation outcomes (Appendix L.5) for direct and empirical comparison. These show which conclusions each evaluation approach can reveal. For example, ReMe and AWM-online have nearly identical FSR and AMR, while EvoTrace reveals a clear difference in their decision artifact-absent miss rates. This identifies requirement-level failures that are not reflected in these aggregate metrics.

The revision covers four levels of comparison:

  1. Illustrative comparison (Figure 1): We add an illustration in Figure 1 to make the comparison more intuitive.
  2. Metric comparison (Tables 1, 18): We compare the coverage of procedural requirements and evolution stages, as well as the metric design, scoring rules, and evaluation protocols of existing benchmarks.
  3. Running example (Figure 9): We use the same refund case to compare how Evo-Memory, SkillEvolBench, and SkillLearnBench evaluate the same requirement. EvoTrace aligns the user confirmation requirement across the complete experience–retention–execution pathway, yielding the state (1,1,0). The requirement is encountered in experience and retained, but omitted during held-out execution. In this case, the other evaluation approaches establish correspondence across only some of these stages.
  4. Empirical comparison (Table 19): We compare evaluation metrics that can be adapted to the same AE-SOP tasks and held-out traces. We examine whether similar task-level scores conceal different requirement-level failures; we also discuss metrics that are not comparable on the current dataset.

Representative results:

MetricReMeAWM-online
FSR58.4%58.3%
AMR90.8%90.7%
Decision artifact-absent miss36.0%66.8%

For each method, the decision artifact-absent miss rate is the proportion of failed executions in which at least one applicable decision requirement is both absent from retained knowledge and incorrectly executed. This comparison shows that similar task-level performance can accompany different gaps in retained knowledge. EvoTrace's requirement-level tracing can distinguish these differences.

Revision: §1, Figure 1; §2.2, Table 1; Appendix A.2, Figure 9; Appendix L.5, Tables 18–19.


Q2: Introduction motivation and Figure 1

Concern: The motivation in the introduction can be more direct. Figure 1 presents several task instances, states, interactions, and persistent artifacts at once. Readers need substantial effort to reconstruct the example before understanding the intended problem.

Response: We focus Figure 1 on a single refund scenario and organize it into User Interaction and Agent's Knowledge to streamline the target scenario. We then incorporate an Evolution Evaluation column to directly reveal the intended problem. It directly compares what existing benchmarks and EvoTrace can reveal to help readers connect the example to the motivation for requirement-level tracing. The introduction links the motivation to Figure 1 to clarify the central question. Table 1, which follows, further clarifies EvoTrace's positioning by comparing the scope of evaluation.

Revision: §1, Figure 1; §2, Table 1; Appendix A.1–A.2, Figures 8–9.

Reviewer_bwVEOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

EvoTrace tracks procedural requirements across an agent’s experience, stored knowledge, and later execution. It contains 115 procedures and 10,792 instances across seven domains. Experiments evaluate eleven self-evolution methods on 60 procedures, showing that retaining more knowledge does not necessarily improve execution. The paper also tests interventions targeting retention and retrieval.

Critical strengths

EvoTrace connects what an agent encounters, what it stores, and what it actually does. This gives more useful feedback than a single success score. The broad method comparison and explicit human audit also help assess both the benchmark’s value and its limitations.

Critical weaknesses
  • Measurement errors affect the main diagnostic claims. Table 19 reports only 74.2% extraction recall for skill artifacts, compared with 91.3% for case memories, which could bias comparisons of retained knowledge. Dependency judgments also have a 34.5% false-acceptance rate. Human correction changes 18.8–25.0% of the audited diagnostic states, based on only 16 linked records per backbone. The audit is welcome, but it leaves uncertainty about whether the reported method-specific bottlenecks remain stable after correction.

  • The intervention experiments do not isolate the benefit of diagnosis. Section 6.4 and Appendix M add three-model voting or an extra applicability review, then compare against the original agent. These improvements could come from additional model calls or generally better retrieval. Without a control using the same computation but choosing interventions independently of the diagnosis, the results do not establish that EvoTrace identified the right intervention.

Questions for authors

See Weakness.

3 comments
AuthorsOpenReview ↗

Response to Reviewer bwVE – 1

W1/Q1: Measurement errors and main diagnostic claims

Concern: Differences in extraction recall between skill artifacts and case memories may bias comparisons of retained knowledge. The false-acceptance rate for dependency judgments and 16 linked records per backbone in the audit leave it unclear whether the method-specific bottlenecks remain stable after correction.

Response: We expand the audit from 16 to 50 linked records per backbone. Based on measurement errors, we apply the corrections to the relevant metrics and diagnostic states (Appendix P). The corrections change some diagnostic states and reduce specific gaps between methods, while the key comparisons between forms of retained knowledge and the reported method-specific bottlenecks remain consistent. Below, we report the measurement errors, the changes in metrics, and the stability of specific diagnostic conclusions.

1. Measurement errors and how they propagate.

  • Error quantification (Table 23): Two independent reviewers and one adjudicator establish the human reference. We report extraction precision and recall for each artifact type, along with false acceptance and false rejection for exposure, artifact matching, and execution judgments.
  • Error propagation and correction (Table 24): We map seven sources of error to the reference sets, knowledge matching, execution judgments, and diagnostic states they affect. We then recompute the calibrated results using the original metric definitions.
  • Diagnostic stability (Figures 36–39): We present calibrated metrics, learning curves, and method comparisons for all 13 conditions, both backbones, and all five checkpoints. These examine the comparisons between forms of retained knowledge and the method-specific bottlenecks.

2. Effects of correction on metrics and diagnostic states. For each backbone, we use 60 complete trajectories for paired comparisons of FSR and AMR, and 50 linked records to examine diagnostic states, obtaining 95% intervals from 10,000 paired resamples:

Audit traces: corrected minus original (pp)GPTQwen
FSR+3.3 [−6.7, 13.3]−1.7 [−11.7, 8.3]
AMR+0.5 [−2.9, 4.2]−2.4 [−5.0, 0.2]
Records with changes (%)GPTQwen
Changes in diagnostic states18.0 [8.0, 30.0]22.0 [12.0, 34.0]
Changes in retained-miss states22.0 [12.0, 34.0]18.0 [8.0, 30.0]

The correction is directly related to retained knowledge and execution performance:

Corrected minus original (pp)GPTQwen
Final KC (Evolving mean)+3.2+3.2
Final K2B (Evolving mean)−2.8−4.0
Final FSR (equal-method mean)+0.7−1.5
Final AMR (equal-method mean)−2.1−3.3
FSR learning gain (Evolving mean)−1.5−1.8

3. Method-specific bottlenecks after correction.

  • The complete curves for all five checkpoints show the same learning trends before and after correction (Figures 38–39).
  • Recomputing the process–outcome associations also preserves the finding that K2B has the strongest positive association with FSR and AMR (Table 25).
  • The method-specific comparisons are preserved after correction. E.g., KC remains higher for case memories than for skill artifacts (Figure 39). Decision artifact-miss rates for MemP-online and ReasoningBank (Figure 37) are:
BackboneGap before correctionCorrected MemP-onlineCorrected ReasoningBankGap after correction
GPT55.2 pp41.6%8.5%33.1 pp
Qwen57.8 pp43.0%7.9%35.1 pp
  • The requirement-level diagnosis remains consistent. The gap decreases on both backbones, while the direction of the comparison is preserved. This supports the stability of the method-specific contrast under the correction (Figure 37).

See Appendix P: Measurement Errors, Correction, and Learning Profile Stability for full statistics and analyses.

Revision: §4.1, §6.6; Appendix P, Tables 23–25, Figures 36–39.

AuthorsOpenReview ↗

Response to Reviewer bwVE – 2

W2/Q2: Isolating the benefit of diagnosis

Concern: The intervention gains may come from additional model calls or generally better retrieval, leaving the contribution of diagnosis unclear. A control using the same computation but selecting intervention targets independently of the diagnosis is needed.

Response: We add a computation-matched random-selection control; both groups use the same repair implementation, model-call budget, and held-out evaluation. Under this control, diagnosis-guided selection achieves higher KC/K2B and FSR gains on both backbones for both repair types. This supports the contribution of diagnosis to selecting effective intervention targets.

Main results: (Guided − Random, pp)

RepairGPT ΔKC / ΔK2BGPT ΔFSRQwen ΔKC / ΔK2BQwen ΔFSR
RetentionKC +4.0+5.5KC +3.7+3.1
RetrievalK2B +0.73+3.1K2B +1.03+4.6

See full results in Figures 7 and 26.

Revision: §6.4, Figure 7; Appendix M.4, Figure 26.

Thanks for the author rebuttal. I have increased my score to 3.

Comments on the paper

1 comment

Dear Reviewers,

I hope this message finds you well.

I would like to remind you that we are currently in the rebuttal phase of the paper review process. During this stage, authors may respond to the comments and feedback you provided. If you receive any responses from the authors, please consider providing your feedback to ensure a smooth review process.

Thank you for your hard work and dedication throughout this review process. Your insights are invaluable in enhancing the quality of the submissions, and we truly appreciate your involvement.

If you have any questions or need further assistance, please do not hesitate to reach out.

Best regards,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.