PaperlayerView exact revision on arXiv

Source-linked AI summary

The Right Lesson at the Right Step: Deriving Control Updates for Self-Evolving Agents

Yunhe Su, ZiYi Dong, Tong Yu, Weijian Deng, Hao Li, Bowen Jiang, Pengxu Wei

arXiv:2609.34988v1cs.CL

TL;DR

Long-workflow agents often reuse experience without controlling where a lesson acts. EvoCUE learns localized state-machine edits and tests them from matched checkpoints; it improves AppWorld success and transfers organizational requirements on PAST-Bench.

  • Problem

    In long workflows, useful lessons may need to reach a particular decision, while existing reuse methods usually leave where content acts fixed and evaluate candidates from task start.

    Source: §1 · p. 2

  • Method

    EvoCUE proposes localized controller instructions or skills from completed trajectories and tests each edit against its parent from the same checkpoint before confirmation and inheritance.

    Source: §1 · pp. 2–3

  • Results

    AppWorld Test-Normal success rises from 13.7% to 79.2% and Test-Challenge from 6.7% to 70.0%; PAST-Bench execution score improves from 0.61 to 0.77.

    Source: §1 · p. 3, §5 · p. 10

  • Takeaways & Limitations

    The results show that experience-driven adaptation can learn not only what to reuse, but where it should enter an agent’s control flow.

    Source: §5 · p. 10

    Paired trials require restorable execution states, which may not be available in all environments.

    Source: §5 · p. 10

Abstract

from arXiv · show

Self-evolving agents improve future behavior by reusing past experience, typically as global prompts, memories, or reflections. Yet these mechanisms rarely control where experience takes effect. In long tool-use workflows, the same lesson may correct one decision but distract another, making experience reuse a problem of localized control rather than memory alone. We introduce EvoCUE (Evolution through Control Updates from Evidence), a framework for learning reusable control-program updates from completed agent executions. EvoCUE represents the agent as an explicit state-machine controller, whose nodes perform model or tool calls and whose edges define where control passes next. This makes the workflow editable at precise locations, so each learned update can specify what to add, where it acts, and when it applies. From completed trajectories, EvoCUE uses residual goals and observed execution traces to propose localized instruction or skill edits. Each candidate is evaluated at the point where it would act by resuming the parent and edited controllers from the same checkpoint and comparing their final outcomes. Accepted edits are compiled with applicability rules, confirmed on held-out tasks, and inherited by later executions. We evaluate EvoCUE on long tool-use environments where learned conventions must reach the right execution step. From a minimal AppWorld controller without benchmark-specific onboarding instructions, EvoCUE learns the missing task-completion convention and substantially improves success on Test-Normal and Test-Challenge. On PAST-Bench office workflows, EvoCUE transfers organizational requirements from prior episodes to later tasks, improving task-execution quality. These results show that self-evolving agents should place experience inside the control flow, rather than only store it as text.

1 INTRODUCTION

Long-workflow experience reuse must determine not only what lesson to retain, but where it should act and how to test its effect. EvoCUE learns localized controller edits and improves performance on AppWorld and PAST-Bench.

1 INTRODUCTION

  • In AppWorld, the same task-completion instruction solves 5 of 16 development tasks when placed first, but 14 when available later.This motivates learning where a lesson enters the workflow, not just what it says.Source: §1 · p. 2
  • Existing prompt, workflow, and memory approaches mainly choose what to retain, while content placement and full-task evaluation leave location and fair-effect testing unresolved.Rerunning from task start can mix an edit’s effect with unrelated variation in earlier execution.Source: §1 · p. 2
  • EvoCUE represents the procedure as a state machine and proposes instructions or skills at specific edges, with rules controlling when they apply.It resumes parent and edited programs from the same checkpoint before the edit acts, compares final outcomes, and confirms passing edits on separate tasks before inheritance.Source: §1 · pp. 2–3
  • EvoCUE raises AppWorld Test-Normal success from 13.7% to 79.2% and Test-Challenge from 6.7% to 70.0%, while improving PAST-Bench execution score from 0.61 to 0.77.The model and tools remain fixed; adapted baselines improve by at most 4.8 points on AppWorld Test-Normal and 0.06 on PAST-Bench.Source: §1 · p. 3

2 RELATED WORK

Prior work reuses experience through prompts, memories, skills, or workflow changes, while EvoCUE makes the location where content acts part of the learned update. Its paired trials and confirmation process distinguish it from methods that optimize from task start or intervene only for attribution.

Self-evolving agents and experience reuse

  • Experience-reuse methods distill reflections, rules, workflows, context, or skills, typically delivering them through a fixed prompt or retrieval channel; EvoCUE learns where content acts.EvoCUE keeps the underlying model fixed.Source: §2 · p. 3

Prompt and program optimization

  • Prompt and program optimizers generally compare candidates from task start, whereas EvoCUE edits an episode location and compares against its parent from that checkpoint.The distinction concerns both edit location and the point from which candidate evaluation begins.Source: §2 · p. 3

Automated design of agents and workflows

  • Workflow-design methods search agent code or structures, while EvoCUE shares explicit control representations with state-machine approaches but learns edits across tasks and inherits them after confirmation.Passing edits are tested from matched checkpoints and fitted with applicability rules.Source: §2 · pp. 3–4

Interventions and attribution on agent traces

  • Trace-intervention methods test repair hypotheses or attribute skill effects, while EvoCUE turns edit evidence into persistent controller changes with fitted applicability rules.Successful edits are compiled for future tasks.Source: §2 · p. 4

3 EVOCUE: EVOLUTION THROUGH CONTROL UPDATES FROM EVIDENCE

EvoCUE learns localized controller updates from completed tasks, tests their effects from matched checkpoints, and inherits only confirmed changes. Its state-machine representation makes edit location, scope, and applicability explicit.

3 EVOCUE: EVOLUTION THROUGH CONTROL UPDATES FROM EVIDENCE

  • Each learning round proposes localized edits, tests them where they act, then compiles passing edits, confirms the candidate program on separate tasks, and inherits it if accepted.Accepted and rejected trial records remain available to later proposals.Source: §3 · p. 4, §3.4 · p. 6

3.1 PRELIMINARY: LEARNING CONTROL PROGRAMS FROM EXPERIENCE

  • The controller combines a fixed model and tools with a graph of call nodes and routing edges; the same node can receive different edge-specific instructions at different episode points.The initial AppWorld controller omits the benchmark’s hand-written onboarding conventions, and learned programs are frozen before evaluation.Source: §3.1 · pp. 4–5

3.2 PROPOSING LOCALIZED EDITS

  • A candidate edit specifies its content, edge location, scope, and expected effect, and may add an instruction or insert a short executable skill.Proposer feedback explains which entries an attachment reaches and what each operator reads and writes.Source: §3.2 · p. 5

3.3 TESTING EDITS WHERE THEY ACT

  • Paired trials resume parent and edited programs from the same checkpoint before an edit acts, so their final-score difference measures downstream effect without variation in the shared prefix.Applicability rules are selected from categorical pre-edit state features; an edit passes only with sufficient task coverage, positive mean effect, and a positive penalized score.Source: §3.3 · pp. 5–6

3.4 COMPILING, CONFIRMING, AND INHERITING

  • Passing edits are compiled into a candidate program and compared with the parent from task start on a disjoint confirmation batch, which evaluates combined edits and their interactions.Accepted and rejected trial records can guide later proposals to revise content or location or avoid failed directions.Source: §3.4 · p. 6

4 EXPERIMENTS

Experiments test whether EvoCUE can learn missing conventions, place them at the right control step, and transfer earlier office requirements to later tasks. AppWorld and PAST-Bench evaluations compare frozen learned programs with baselines and test performance on later tasks.

4.1 SETUP

  • AppWorld learning used a 32-task training subset, eight paired tasks per candidate, and eight separate confirmation tasks before frozen evaluation on 168 Test-Normal and 417 Test-Challenge tasks.Baselines used the same model, tools, interface, and budgets, but learned from all 90 AppWorld training tasks.Source: §4.1 · p. 7

4.2 ONE LEARNED INSTRUCTION IMPROVES HUNDREDS OF LATER TASKS

  • 13.7% to 79.2% Test-Normal task success and 6.7% to 70.0% Test-Challenge task success; only the completion convention at the recurring entry improved outcomes.Table 1 also reports scenario success rising from 5.4% to 57.1% on Test-Normal and from 2.2% to 44.6% on Test-Challenge.Source: §4.2 · p. 7, Figure 3 · p. 8

4.3 HOW THE LEARNER FOUND THE EDIT

  • Residual-goal evidence located the completion failure after plausible edits tied; the selected edit improved five of eight matched-prefix pairs, and a fresh run raised Test-Normal success from 11.9% to 76.2%.The first fresh run had 110 task improvements and two regressions.Source: §4.3 · p. 8

4.4 WHERE LEARNED CONTENT MUST ACT

  • With content fixed, recurring-entry or every-step availability solved 14 development tasks, versus five at the first entry; node-specific prompts explain why first-entry text misses later completion.Eight of the ten newly solved tasks left the answer unset instead of submitting a summary.Source: §4.4 · pp. 8–9

4.5 TRANSFERRING ORGANIZATIONAL REQUIREMENTS TO LATER OFFICE TASKS

  • On 16 later pilot tasks, task-execution score rose from 0.608 to 0.772, 2.6 times the largest baseline gain; on unseen families it rose from 0.35 to 0.73, while baselines gained at most 0.14.Pilot results included 11 improvements, one regression, and four ties; with only two improvable confirmation tasks on unseen families, paired confirmation accepted none of those edits.Source: Table 2 · p. 9, §4.5 · p. 9

4.6 SIX FURTHER DOMAINS

  • On six further domains, EvoCUE accepted no updates where initial programs already scored high or tasks were short; the largest baseline change was GEPA’s +3.1 points on MATH.Apart from EvoClawBench runs with execution errors, baselines also changed little.Source: §4.6 · p. 9

5 DISCUSSION AND CONCLUSION

EvoCUE learns localized control-program edits from completed executions, using residual goals and matched-checkpoint trials before confirmation on separate tasks. The conclusion reports gains on AppWorld and PAST-Bench, while noting transfer, state-restoration, and deployment-safety boundaries.

5 DISCUSSION AND CONCLUSION

  • From a minimal AppWorld controller, EvoCUE learned the completion convention, raising Test-Normal success from 13.7% to 79.2%; on PAST-Bench it transferred organizational requirements to later office tasks.The same instruction solved 14 of 16 development tasks when available at every later step, versus five at the first step.Source: §5 · p. 10
  • Applicability rules are inferred from finite observed tasks; broader transfer and systematic exception handling remain open, and paired trials require restorable execution states.The evaluation freezes learned programs after training rather than testing online learning over long task streams.Source: §5 · p. 10

AI USE STATEMENT

  • Generative AI assisted implementation and manuscript polishing; language models also served as evaluated agent and learner components.The Figure 1 icons were generated with an image-generation model.Source: AI USE STATEMENT · p. 11

ETHICS STATEMENT

  • Regressions remain possible, and inspection and whole-program confirmation do not establish deployment safety beyond the evaluated settings.Experiments use benchmark software environments and simulated office tasks.Source: ETHICS STATEMENT · p. 11

REPRODUCIBILITY STATEMENT

  • Appendices document data roles, configurations, edit semantics, learned programs, and additional results; reported numbers are tied to recorded configurations and data roles.Frozen evaluation is kept separate from learning.Source: REPRODUCIBILITY STATEMENT · p. 11

A.1 DATA ROLES AND PUBLIC OBSERVATIONS

The reported setup limits learning to public task evidence and uses matched trials, confirmation, and compiled updates to learn a recurring AppWorld completion instruction.

A.1 DATA ROLES AND PUBLIC OBSERVATIONS

  • AppWorld uses 32 training tasks and 16 development tasks for the reported run, with frozen-program evaluation on 168 Test-Normal and 417 Test-Challenge tasks.The official checker determines task success, and a scenario succeeds only if all its task instances do.Source: §A.1 · p. 16
  • Learning uses public instructions, supervisor information, and printed code output; private checker details, reference answers, and hidden tests are excluded.Unprinted API returns are not automatically exposed, while final scalar scores become available after training tasks finish.Source: §A.1 · p. 16

A.2 MODEL AND EXECUTION SETTINGS

  • All model calls use deepseek-v4-flash, and initial and learned AppWorld controllers share the same model configuration, observation protocol, and budgets.AppWorld allows 40 environment actions and 400 controller steps; the PAST pilot allows 900 controller steps.Source: §A.2 · p. 16

A.3 THE REPORTED APPWORLD RUN

  • AppWorld accepts an edit after positive mean paired task-score difference on confirmation tasks, while PAST also requires multiple improvements and robustness to removing the largest gain.Within a round, confirmation tasks are disjoint from proposal and trial tasks; tasks reused across rounds remain training data.Source: §A.3 · p. 16

B.1 PRIMITIVE OPERATIONS

  • Prepare and Commit separate action generation from execution so edits can act between them, without adding a generation call, default check, or retry when no edit is present.Commit executes the stored draft and appends its public observation.Source: §B.1 · p. 17

B.2 CANDIDATE FORMS

  • Instruction candidates define an edge, text, and scope; structural candidates specify operations, branches, returns, and failure returns, with compiler checks enforcing valid forms.Cited tasks guide trial sampling but never become routing conditions.Source: §B.2 · p. 17

B.3 EFFECT RECORDS AND RULES

  • Trial records distinguish matched-prefix from task-start evidence, while applicability rules use typed pre-edit state features and allow at most two equality tests.Task IDs and private scores cannot enter runtime conditions.Source: §B.3 · pp. 17–18

C.1 APPWORLD: A RECURRING COMPLETION INSTRUCTION

  • Eight matched-prefix trials produced five improvements and three ties; separate task-start confirmation produced four improvements, one regression, and three ties.The accepted instruction distinguishes questions from actions and is attached to a recurring entry without a non-empty applicability rule.Source: §C.1 · p. 18

C.2 PAST: ORGANIZATIONAL REQUIREMENTS AT TWO ENTRIES

The PAST pilot transfers requirements from historical office episodes into instructions for later tool execution.

C.2 PAST: ORGANIZATIONAL REQUIREMENTS AT TWO ENTRIES

  • The accepted PAST update attaches instructions to both the first and recurring entries of the action-generation node, with empty applicability rules and no new skill.A first candidate was rejected after a mean confirmation difference of −0.030; the second had mean paired improvement 0.151 and confirmation improvement 0.144.Source: §C.2 · p. 18
  • The learned instructions encode requirements derived from historical office tasks for later executions.The pilot collects 16 public historical episodes and creates eight knowledge cards that cite their source episodes.Source: §C.2 · p. 18
  • The PAST update demonstrates that a learned program change need not add graph structure to become a reusable instruction.The accepted update adds instructions but no callable skill or non-empty applicability rule.Source: §C.2 · p. 18

D BASELINES

The baseline runs compare methods learning from the same minimal prompt and public information, with outcomes scoped to that protocol rather than published-system performance.

D BASELINES

  • GEPA, AFlow, AWM, and MaAS used the same endpoint, tools, observation interface, budgets, and public information as EvoCUE, but learned different objects.They used their own initial programs on the same minimal prompt and followed native stopping rules.Source: D BASELINES · p. 19
  • Learned baselines reached at most 7.1% Test-Normal and 2.2% Test-Challenge scenario success, while EvoCUE’s learned program achieved higher success in the reported comparison.The baselines learned different objects and had different outcomes: GEPA and AFlow selected their initial programs, while AWM and MaAS made learned updates.Source: D BASELINES · p. 19
  • These runs test learning from a minimal prompt, not reproductions of published systems that start with official benchmark prompts.The paper makes no claim about the original methods beyond the stated protocol.Source: D BASELINES · p. 19
  • On PAST-Bench, methods use the same 16 historical episodes and frozen-program evaluation on the same 16 later pilot tasks.The comparison with text-based experience learning must let that method discover and revise its own experience from public histories.Source: D BASELINES · p. 19

E.1 TASK AND SCENARIO SUCCESS

The learned controller improves AppWorld results, and further runs show rediscovery of the completion convention without earlier hypotheses.

E.1 TASK AND SCENARIO SUCCESS

  • 47 of 57 development tasks succeeded with the learned program, compared with 13 of 57 for the initial controller.The development results support diagnosis and are reported separately from test-set results.Source: §E.1 · p. 19

E.2 REDISCOVERY WITHOUT EARLIER HYPOTHESES

  • 128 of 168 Test-Normal tasks succeeded in one rediscovery run, versus 20 for concurrent C0; two further runs learned the convention without earlier hypotheses.The first program improved 110 tasks and regressed two; three seeds of an earlier learner version each learned the same convention and solved 98 to 114 of 168 tasks, versus 16 to 19 for their initial controllers.Source: §E.2 · p. 19

E.3 PAST-BENCH: UNSEEN TASK FAMILIES

Across ten unseen PAST-Bench families, installing EvoCUE’s distilled knowledge raises the score from 0.31 to 0.47. On six further domains, EvoCUE accepts no update; the resource records report learning and evaluation call and token totals.

E.3 PAST-BENCH: UNSEEN TASK FAMILIES

  • 0.31 to 0.47: installing all of EvoCUE’s distilled knowledge raises the score across ten unseen PAST-Bench families.The study selects ten families not used during development; six have preloaded memories or earlier sessions the adapter cannot load, and the table reports four fully supported families.Source: §E.3 · pp. 19–20

E.4 SIX FURTHER DOMAINS

  • EvoCUE accepts no update on six further domains; its unchanged controller equals C0 on four, while it was not re-evaluated on HumanEval and MATH.On τ 2-bench and EvoClawBench, score differences reflect repeated execution; apart from execution-error runs, the largest baseline change is GEPA’s +3.1 points on MATH.Source: §E.4 · p. 20, Table 4 · p. 20

E.5 MEASURED RESOURCES

  • The resource records report 1,300 AppWorld learning calls and 555 PAST pilot learning calls, with known token totals of 15.88 million and 2.57 million, respectively.The AppWorld record omits earlier exploration and includes 21 calls with unavailable usage; the PAST record has no missing usage.Source: §E.5 · p. 20

F.1 APPWORLD DEVELOPMENT BEHAVIOR

In AppWorld development behavior, the learned program solves 14 tasks versus four for the initial program, with completion behavior changing on most newly solved tasks. In the separate PAST frozen pilot, eleven task-execution scores improve, one declines, and four remain unchanged.

F.1 APPWORLD DEVELOPMENT BEHAVIOR

  • Four to 14 tasks: the AppWorld initial and learned programs solve those respective numbers on the 16-task development comparison.Among ten improvements, eight change action-task completion from a summary string to an unset answer; one newly invokes the completion API with an unset answer, and one returns the requested value without extra wording.Source: §F.1 · p. 20
  • The AppWorld initial and learned programs use 242 and 263 model calls and 117 and 131 environment actions, respectively, in complete 16-task runs.Budgets are fixed, but realized inference costs can differ between programs; trajectories can also differ in earlier actions and length.Source: §F.1 · p. 20

F.2 PAST FROZEN PILOT

  • Eleven PAST frozen-pilot task-execution scores improve, one declines, and four are unchanged; the learned program scores 0.772 versus 0.767 for the same learned text given at every step.The learned text is used 65 times across the 16-task evaluation.Source: §F.2 · p. 21
  • A PAST data-sharing task’s score changes from 0.676 to 0.851, while a far-transfer task regresses from 0.796 to 0.510.A shared-outage workflow changes from 0.404 to 0.864, so reuse is not uniformly beneficial.Source: §F.2 · p. 21
Loading 2609.34988v1…