acceptodds
Under review as a conference paper at ICLR 2027

EvoRelay: Asynchronous Online Experience Learning for Long-Horizon Agents

Abstract

Large language model (LLM) agents increasingly solve long-horizon tasks in interactive environments, where past interactions provide reusable experience for future decisions. Existing memory-based self-evolution methods commonly organize experience at the task level, retrieving historical experience by global task similarity and making newly acquired experience available only after task completion. However, long-horizon tasks typically unfold through functional stages with distinct objectives. This task-level design creates both a granularity mismatch and an efficiency bottleneck: global similarity may fail to identify experience relevant to the current stage, while newly acquired experience cannot benefit subsequent tasks until the source task completes, limiting the efficiency of online experience learning. To address these limitations, we propose Evorelay, an asynchronous online experience learning framework that unifies experience retrieval, extraction, and cross-task propagation around functional stages. Within this unified organization, historical experience is retrieved according to the current stage objective, and experience learned from completed stages becomes available to subsequent tasks while the source task continues. This asynchronous relay reduces cross-task experience propagation latency and substantially improves the efficiency of online experience learning. Across four backbone models, Evorelay improves task success over Vanilla Agent by an average of 6.0 percentage points on SWE-bench Verified and 3.8 percentage points on AppWorld. It achieves the highest average task success across the evaluated settings, with 2.6–3.4 mean end-to-end speedups over two representative memory-based self-evolution baselines.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, agent memory, long-horizon tasks, asynchronous experience learning, online self-evolution

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_jWG7OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes EvoRelay, an online experience-learning framework for long-horizon agents. It organizes experience around functional stages and asynchronously extracts and propagates stage-level memories, allowing later tasks to use them before the source task finishes. Experiments on SWE-bench Verified and AppWorld with four backbone models show moderate task-success improvements and large reductions in end-to-end stream time.

Critical strengths
  1. The paper identifies a real systems bottleneck: newly acquired experience may remain unavailable until the source task finishes.
  2. The evaluation is reasonably broad, covering two interactive benchmarks, four backbone models, multiple memory baselines, task success, runtime, ablations, and stage-wise behavior.
Critical weaknesses
  1. Limited methodological novelty. Category filtering, stage-level experience extraction, and online updates substantially overlap with the existing approach, so stage-aligned memory itself does not appear to be a new underlying principle. The more distinctive part is asynchronous visibility and pipeline scheduling, but this feels primarily like a systems-level execution optimization rather than a new experience-learning mechanism.
  2. The paper does not sufficiently establish that the asynchronous scheduling result is robust beyond the reported setting.
Questions for authors
  1. Please clarify how SASM was implemented and whether the reported baseline faithfully follows the original method. Could the authors provide a controlled comparison that keeps SASM’s stage-level memory mechanism fixed and changes only the experience-availability rule from task-completion-based to stage-update-based?
  2. How stable is the reported 2.9× runtime improvement across backbone models, task orders, numbers of workers, and experience-extraction delays? Please report repeated-run means, variance, and significance tests.
  3. Stage declarations are generated dynamically, but the experiments also rely on predefined stage categories. It would be better to report stage-declaration errors and test sensitivity to alternative stage-category definitions.
  4. Under the append-only memory design, how are duplicate, conflicting, or incorrect experiences handled as the task stream grows?
Reviewer_4BqBOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

EvoRelay reorganizes memory-based self-evolution for long-horizon LLM agents around dynamically declared functional stages (e.g., Analyze / Reproduce / Edit / Verify) instead of complete tasks: agents retrieve experience by current stage objective rather than global task similarity, and completed stages are asynchronously distilled into atomic experiences that become available to later tasks without waiting for the source task to finish. Across four backbones on SWE-bench Verified and AppWorld, it reports +6.1 and +3.8 points over a no-memory agent and 2.6–3.4× end-to-end speedups over two memory baselines.

Critical strengths
  • The motivation is clearly articulated and well grounded: the paper identifies two concrete bottlenecks of task-level experience learning — a granularity mismatch between global task similarity and stage-specific needs, and the delay before newly acquired experience becomes available across tasks — and substantiates both with targeted evidence rather than intuition alone.
  • The efficiency gains are substantial in magnitude: EvoRelay reports 2.6–3.4× end-to-end speedups over two memory-based baselines, and the controlled comparison in Table 3 isolates this gain while leaving accuracy essentially unchanged (84.4% vs. 84.2%).
  • The ablation studies are reasonably comprehensive and follow a clean single-factor substitution protocol, isolating the contributions of stage decomposition, experience representation, retrieval policy, and cross-task availability timing.
Critical weaknesses
  • Organizing experience around procedural phases closely resembles prior work on workflow- and subtask-level memory — most notably Agent Workflow Memory (AWM, ICML 2025) and SASM (Structurally Aligned Subtask-Level Memory for Software Engineering Agents), both of which induce reusable, phase-structured memory without any training. The paper never clarifies how its "functional stages" differ from SASM's "subtasks", so the actual delta over the closest prior work reduces largely to the asynchronous availability rule, which is itself contested (see below).
  • Although SWE-bench Verified and AppWorld differ on the surface, both are code/API-centric environments with short, automatically verifiable episodes, and — more importantly — both use a stage taxonomy hand-designed per benchmark (Table 8). There is no evidence that the functional-stage abstraction transfers to domains without an obvious phase structure (e.g., web navigation, GUI control, or embodied tasks), nor any attempt to induce the taxonomy automatically instead of specifying it manually.
  • Performance is reported only as end-of-stream aggregates. No learning curve — task success as a function of position in the task stream — is provided, so one cannot tell whether EvoRelay improves, saturates, or degrades as experience accumulates; the retrieval-distance statistics in Appendix D.5 are not a substitute. A per-task regression analysis (tasks solved by the Vanilla Agent but failed by EvoRelay) and an analysis of cases where retrieved experience is misleading would likewise strengthen the paper.
Questions for authors
  • Could the authors clarify how their "functional stages" differ substantively from the "subtasks" in SASM (Structurally Aligned Subtask-Level Memory for Software Engineering Agents) and from the reusable workflows in AWM? Concretely: if SASM's memory were plugged into EvoRelay's asynchronous propagation schedule, how much of the reported gap over SASM would remain?
  • Both benchmarks are code/API-centric, and the stage taxonomy is hand-designed per benchmark (Table 8). Could the authors evaluate on a domain without an obvious phase structure — e.g., web navigation (WebArena), GUI control, or an embodied setting? If a full new benchmark is out of scope for the rebuttal, a taxonomy-sensitivity ablation (random, coarser, and finer stage sets) and an attempt to induce stages automatically rather than specifying them manually would already address the concern.
  • Could the authors report results beyond end-of-stream aggregates? Specifically: (i) a learning curve of task success as a function of position in the task stream, to show whether performance improves, saturates, or degrades as experience accumulates; (ii) a breakdown of how many tasks actually benefit — Figure 7 suggests the gain is concentrated in Hard tasks (+7.2 pp) while Easy and Medium see only +1.1 and +0.6 pp; and (iii) a regression analysis of tasks solved by the Vanilla Agent but failed by EvoRelay.
Reviewer_RzFROpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes EvoRelay, which organizes experience retrieval, distillation, and cross-task propagation around functional stages without updating the parameters of the backbone model. Experience from a completed stage can be used by subsequent tasks before the source task finishes. This enables pipelined execution across tasks. The paper evaluates four backbone models on SWE-bench Verified and AppWorld. It reports average gains of 6.1 and 3.8 percentage points, respectively, over a no-memory baseline. In the evaluated online task-stream setting, EvoRelay achieves average end-to-end speedups of about 2.6× over ReasoningBank and 3.4× over SASM.

Critical strengths
  1. The paper is well-motivated, easy to follow and read.
  2. The paper combines stage-level experience reuse with asynchronous propagation. It presents a clear design that addresses both experience matching and propagation latency.
  3. The experiments cover two benchmarks and four models. The ablations cover stage structure, experience representation, retrieval, and release timing.
Critical weaknesses

The authors use asynchronous execution to overlap different tasks as much as possible and to make experience available earlier. However, asynchrony introduces a potential problem: the experience needed at a task’s current stage may not be available yet, because no earlier task has completed that stage. This can happen in EvoRelay: slower preceding stages may delay subsequent tasks and weaken the speedup from asynchronous execution. In other words, when stage durations vary widely across tasks, this waiting may reduce execution overlap between tasks and degrade efficiency. The paper reports overall speedups but discusses the waiting overhead and its impact only briefly, so it is unclear how significant this factor is in practice.

Questions for authors

In practice, how often do tasks have to wait for experience updates from preceding stages? Please briefly explain how this waiting affects the overall runtime.

1 comment

I appreciate the authors' efforts in reporting the new statistics. I am inclined to keep my original score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.