PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Fragility of Self-Improving Agents: Variance, Task Order, and Underspecification

Qinyuan Ye, Yu Li, Yada Pruksachatkun, Jiaxin Zhang, Chien-Sheng Wu

arXiv:2608.18066v1cs.AIcs.CLcs.LG

TL;DR

Memory-based self-improving agents are often evaluated without sufficient reliability testing. This paper re-evaluates them across multiple runs and shuffled task orders, finding substantial variance and strong order sensitivity that additional specification only partly reduces.

  • Problem

    Reliability evidence for memory-based self-improving agents remains limited, despite the low tolerance for errors in practical and high-stakes deployments.

  • Method

    The paper re-evaluates two memory-based methods across web-browsing benchmarks using multiple runs, shuffled task orders, and additional environment feedback and task-rubric information.

  • Results

    Self-improvement exhibits significant run-to-run variance and task-order sensitivity, while added specification reduces shuffled-order performance degradation by 31% but leaves substantial gaps.

  • Takeaways & Limitations

    Reliable evaluation should report multiple runs and stress-test task order, while effective oversight and better specification remain important for preventing unforeseeable failures.

  • Takeaways & Limitations

    The study covers only web-browsing agents and does not evaluate other self-improvement methods, alternative domains, or the newest memory-management techniques.

Abstract

from arXiv · show

Memory-based self-improving agents--those that learn from an online stream of tasks and improve over time by maintaining a textual memory bank--have shown great promise in recent literature. However, the reliability aspects of these methods have been critically overlooked. In this work, we conduct a comprehensive re-evaluation of two memory-based methods, broadening the scope of evaluation along two axes: (1) including multiple runs to quantify variance, and (2) randomly shuffling the tasks to investigate the effect of task order. Through these experiments, we make two observations that expose the fragility of current methods: First, agent evaluation is inherently noisy in complex environments and on multi-step tasks, and stacking a self-improving loop on top can further amplify this noise. Second, the agent's improvement is highly dependent on task order. Prior works often adopt default orderings that impose an implicit curriculum, acting as a hidden prerequisite for success. To better understand this fragility, we manually examine the agents' memory and hypothesize that task and environment underspecification contribute to this fragility. We validate this hypothesis by incorporating information that enables better specification, such as detailed rubrics and environment feedback, into the memory construction process. While this added information partially closes the performance degradation in previous experiments, significant gaps still remain, suggesting that other uncharacterized factors contribute to this fragility. Looking ahead, our work advocates for more rigorous evaluation protocols for self-improving agents by reporting results across multiple runs and stress-testing them under challenging conditions. Moreover, our findings on underspecification call for systems and interfaces that enable effective human oversight, preventing agents from failing in unforeseeable ways.

1 Introduction

This work re-evaluates memory-based self-improving agents and finds that their reliability is fragile: performance varies substantially across runs and depends strongly on task order. Underspecification contributes to these failures, while additional context only partially mitigates degradation.

  • Motivation: Self-improving agents require reliability stress-testing because errors can silently cascade into costly or irreversible impacts in high-stakes deployments.The introduction emphasizes minimal tolerance for error and risks to user trust in practical settings.
  • Evaluation scope: The study re-evaluates Agent Workflow Memory and ReasoningBank on WebArena, VisualWebArena, and SCUBA using multiple runs and shuffled task orders.Both systems are evaluated with upgraded language models and agent harnesses to establish a stronger baseline.
  • Variance: Run-to-run variance is substantial for the no-memory baseline and can be amplified by adding a self-improving procedure.Prior single-run web-agent evaluations largely conceal this variability.
  • Task-order sensitivity: ReasoningBank gains 1.5% under the default task order but degrades 4.5% under randomly shuffled orders.The default ordering imposes an implicit easy-to-hard curriculum that acts as a hidden prerequisite for success.
  • Underspecification: Environment and task underspecification can produce plausible but unexecutable memories, such as API-use suggestions in browser-only environments.The agents’ memories were manually examined to identify these potential drivers of variance and degraded performance.
  • Mitigation and implications: Additional environment feedback, task rubrics, and clearer specifications close 31% of shuffled-order performance degradation, but a remaining gap indicates other unknown factors.The findings motivate rigorous evaluation and human-intervention interfaces for identifying and correcting wrong lessons.

2 Background: Memory-Based Self-Improving Agents

Memory-based self-improving agents complete an online task stream while maintaining a textual memory that is updated from task trajectories and optionally rewards. The section introduces this setting and the two evaluated methods, AWM and RBank.

  • Problem setting: Agents process an online stream of N tasks while a language model selects actions from prior observations, actions, memory M, and action space A.For each task q_i, the policy generates actions at each timestamp from the preceding trajectory and maintained memory.
  • Representative methods: The evaluation considers Agent Workflow Memory (AWM) and ReasoningBank (RBank) as two established memory-based self-improving methods.The overview identifies AWM and RBank as the two representative approaches used in the evaluation.
  • Problem setting: After each task, the agent receives reward r ∈[0, 1], with reward 1 indicating that the task is passed.A memory construction module updates M using the task trajectory and, optionally, the reward.
  • Representative methods: AWM summarizes reusable workflows from successful trajectories, removes duplicates, and includes all workflows in subsequent task contexts.This follows the original implementation described in the passage.

3 Exposing Fragility with Broadened Re-evaluation

The re-evaluation broadens testing across repeated runs and task orders, revealing substantial variance, amplified instability from self-improvement, limited gains with stronger baselines, and strong sensitivity to task order. The default ordering itself embeds an easy-to-hard curriculum that shuffled orders disrupt.

  • Evaluation design: The evaluation uses three identical runs, reporting average pass@1, standard deviation, and best-worst gaps, plus alternative task orderings.The study evaluates WebArena, VisualWebArena, and SCUBA using baseline harnesses, with AWM and RBank built on top.
  • Run variance: 4.4%: the best-worst run gap reaches this level on WebArena’s GitLab subset, demonstrating substantial baseline evaluation noise.Prior work commonly reports pass@1 from a single run, despite performance varying across runs.
  • Performance gains: 1.5%: RBank’s average improvement over the baseline is not statistically significant, with p-value 0.23 across three runs.The stronger GPT-5-mini baseline achieves 55.3% on a WebArena subset, compared with RBank’s prior memory-enhanced result of 53.9% using Gemini-2.5-Pro.
  • Run variance: 17 of 24 cases: self-improvement increases variance, including 11 cases with relative increases exceeding 50%.The stateful memory-construction process conditions later behavior on earlier task outcomes, contributing to instability.
  • Task-order sensitivity: 54.8% to 49.1% (AWM) and 49.8% (RBank): Shuffle-1 causes these WebArena performance drops, while RBank is less sensitive on VisualWebArena.The default order begins with pass rates around 75% and declines below 40% after task ID 150, indicating an implicit easy-to-hard curriculum.

4 Indentifying Underspecification as a Potential Cause of Fragility

Manual inspection identifies environment and task underspecification as potential causes of amplified variance and order-sensitive performance drops. Adding rubrics, scores, and other information to memory construction yields modest gains but does not eliminate degradation relative to the no-memory baseline.

  • Environment underspecification: Environment underspecification causes memories to recommend unsupported actions, such as API-based solutions unavailable in the web browsing environment.These memories can recur across domains and distract or confuse the agent.
  • Environment underspecification: User-confirmation memories appeared 26 times in 3 runs of WebArena and 22 times in 3 runs of VisualWebArena, despite unsupported confirmation actions causing repeated “wait” behavior.The resulting waits may continue until the time limit is reached.
  • Task underspecification: Task underspecification can produce misunderstanding, overthinking, and irrelevant memories, while evaluator bugs can create false negatives that induce spurious memories.The jaw bruxism example illustrates how ambiguous queries can lead agents toward unintended interpretations.
  • Contagious memories: Haversine-based fallback strategies became contagious in map tasks when the website failed to load or respond, amplifying an unintended strategy throughout self-improvement.The agent used Haversine estimation instead of relying on the website’s route engine.
  • Addressing underspecification: Combining additional information improved original RBank performance by 2.9% (49.8% →52.7%) under Shuffle-1 and by 1.1% on Shuffle-2, while maintaining Default-order performance.The modifications included information intended to reduce underspecification during memory construction.
  • Addressing underspecification: Despite these enhancements, the agent still underperformed the no-memory baseline under Shuffle-1 and Shuffle-2, indicating that additional information does not capture all fragility sources.The original memory-construction prompt was minimal and generic, potentially insufficient for meaningful improvement.

5 Related Works

The paper situates its inference-only approach within broader research on agent continual learning, self-improvement, textual memory, skills, and agent evaluation. Related work spans math, reasoning, coding, personalization, supervised fine-tuning, reinforcement learning, and diverse real-world agent benchmarks.

  • Agent Continual Learning and Self-Improvement: Inference-only agent self-improvement is positioned as a practically useful setting for exploring forward-pass-only agent limitations.The work focuses on an accessible interface motivated by practical utility and extends beyond web-browsing tasks.
  • Agent Continual Learning and Self-Improvement: Prior self-improvement research covers math, reasoning, coding, and long-term personalization agents, alongside supervised fine-tuning and reinforcement learning paradigms.Continual learning and self-improvement, including self-play, predate the inference-only paradigm.
  • Agent Skill and Memory: Agent continual learning increasingly uses memories, with this work focusing on non-parametric textual memory and related workflow memories called skills.Parametric approaches include sparse memory fine-tuning, while textual memory has recently gained substantial traction.
  • Agent Evaluation and Reliability: Agent evaluation research includes benchmarks for tool use, computer use, and web browsing, with newer benchmarks targeting economically valuable tasks.These domains include coding, customer service, customer relationship management, and enterprise operations.

6 Conclusion

The paper re-evaluates memory-based self-improving agents under multiple runs and shuffled task orders, revealing fragility in challenging settings. It attributes this fragility partly to task and environment underspecification and recommends more rigorous evaluation and memory-validation mechanisms.

  • Conclusion: The re-evaluation broadens testing to multiple runs and shuffled task orders while using a stronger base model and agent harness baseline.These changes expose fragility under more challenging settings.
  • Conclusion: Task and environment underspecification emerge as a key limitation, and adding better specification to memory generation reduces prior performance degradation by 31%.The limitation is supported through manual memory examination, case studies, and analyses.
  • Recommendations for Evaluation: Single-run results should be treated cautiously; evaluations should report multiple runs and randomized task orders, pilot on well-specified tasks, and then stress-test underspecified tasks.These recommendations target the stability issues identified in the study.
  • Recommendations for System Development: Without proper validation, agent memories remain unverified hypotheses that can be erroneous and cascade negatively into later tasks.Future work should investigate mechanisms that filter problematic memories to ensure long-term robustness.

A Limitations

The evaluation is limited to web-browsing memory-based self-improving agents and omits other methods, domains, and the newest memory-management techniques. Memory inspection was qualitative and sampled, so additional undocumented failure patterns may remain.

  • A Limitations: The study evaluates only web-browsing memory-based self-improving agents, excluding other self-improvement methods, alternative domains, and recently introduced memory-management techniques.These exclusions reflect the tractable scope of the experimental design and the field’s rapid development.
  • A Limitations: Manual memory inspection was qualitative and covered only a subset of entries, leaving other undocumented failure patterns potentially undiscovered.The volume of memories made exhaustive review infeasible; future work should analyze memories at scale and develop scalable human-oversight methods.

B Additional Experiment Details · C Extended Related Works

The paper reports experiment costs, licensing and LLM-use details, and situates its findings within broader work on monitorability and reliability across emerging learning paradigms.

  • B Additional Experiment Details: A single GPT-5-mini run costs around $25 for all 812 WebArena tasks and $29 for all 267 SCUBA tasks.Memory-based methods add costs for generating and including memories, but the authors expect both additions to be minimal.
  • B Additional Experiment Details: WebArena and SCUBA are Apache-2.0 licensed, VisualWebArena is MIT licensed, and the revised baseline agents use MIT and Apache-2.0 licenses.The baselines were revised from WALT and SCUBA.
  • B Additional Experiment Details: Coding agents supported experimentation, while LLMs assisted with paper editing and proofreading without contributing original ideas.The code was largely based on existing implementations from prior work.
  • C Extended Related Works: The work relates to chain-of-thought monitorability research, including observations of reward hacking in coding agents.The authors report similar reward-hacking cases during learning, including the Haversine Formula example in Table 9.
  • C Extended Related Works: Because memory-based continual learning exposes an agent’s textual learning process, it enables scalable monitoring and intervention interfaces.The inspectable memory interface creates opportunities to explore scalable monitoring methods and intervene during learning.
  • C Extended Related Works: Reliability and stability have been studied across deep reinforcement learning, meta-learning, fine-tuning, prompting, in-context learning, and self-correction.Self-improving agents are described as a nascent paradigm enabled by increasingly capable language models.

D Additional Result Tables … 2. Limitations

The supplementary sections provide additional baseline evaluations, specify the memory-construction prompts, illustrate failure modes, and document checklist statements about claims and limitations. Together, they emphasize evaluation coverage, prompt design, ambiguous or flawed supervision, and explicit discussion of limitations.

  • D Additional Result Tables: Tables 5–6 report no-memory baseline evaluations on WebArena, VisualWebArena, and SCUBA.
  • E Prompts: The AWM prompt asks agents to summarize reusable workflows from action trajectories as simple, task-oriented textual guidelines.Workflows describe tasks and action trajectories, and may contain two to five steps.
  • E Prompts: ReasoningBank’s successful-task prompt extracts at most three non-overlapping, generalizable insights from trajectories that successfully completed tasks.The prompt requires first analyzing why the trajectory succeeded and excludes specific websites, queries, and string contents.
  • E Prompts: ReasoningBank’s failed-task prompt reflects on unsuccessful trajectories and records generalizable lessons or strategies intended to prevent future failures.It likewise limits extraction to at most three non-overlapping memory items.
  • F Failure Modes: The failure-mode examples include an ambiguous WebArena query that the agent interprets as question answering rather than web navigation.
  • F Failure Modes: A WebArena evaluator bug can reject a correct answer through strict string matching and subsequently create irrelevant memories.
  • 1. Claims: The checklist states that the abstract and introduction accurately reflect the paper’s contributions and scope.The checklist guidance says claims should include contributions and important assumptions or limitations and should match theoretical and experimental results.
  • 2. Limitations: The checklist asks whether the paper discusses its limitations and encourages a separate limitations section addressing strong assumptions and robustness to their violations.

3. Theory assumptions and proofs

The paper does not involve theoretical analysis or theoretical results, so the theory-assumptions-and-proofs assessment is not applicable. Consequently, no assumptions, theorems, formulas, or proofs are reported for evaluation.

  • The paper explicitly states that it does not involve theoretical analysis.
  • Therefore, the paper provides no theoretical assumptions, numbered theorems, formulas, or proofs to assess.The guidelines specify these requirements for papers containing theoretical results.
  • The assessment is N/A because the paper does not include theoretical results.The guidelines define N/A as meaning that the paper does not include theoretical results.

6. Experimental setting/details

The paper states that it describes the dataset and discusses experimental details in Section 3.1, but the supplied passage does not enumerate those details.

  • Experimental setting/details: The supplied passages do not establish whether all requested training and test details are specified.The question specifically concerns data splits, hyperparameters, optimizer type, and how these choices were made.
  • Experimental setting/details: The paper describes the dataset used and discusses experiment details in §3.1.The supplied passage does not specify the data splits, hyperparameters, optimizer, or selection procedures.
  • Experimental setting/details: The evaluation criteria require enough experimental-setting detail to understand and interpret the results.Such details may be provided in the paper, code, appendix, or supplemental material.

7. Experiment statistical significance … 14. Crowdsourcing and research with human subjects

The paper reports multi-run variability with error bars and discusses broader implications, while stating that it introduces no new models, does not involve human subjects, and releases code and data under Apache-2.0.

  • 7. Experiment statistical significance: The experiments report error bars whenever possible, including Figures 3 and 5, to support responsible multi-run statistics.The authors identify responsible reporting of multi-run statistics as a main goal.
  • 7. Experiment statistical significance: The paper discusses implications and practical recommendations arising from its findings in the conclusion.These discussions address the work’s broader impacts.
  • 11. Safeguards: The paper states that it does not introduce new datasets or models, so additional safeguards for high-risk releases are not applicable.The safeguards justification is based on the absence of new datasets or models.
  • 12. Licenses for existing assets: The paper does not specify separate licensing details for existing assets in the provided passage.The checklist requests citations, versions, URLs, licenses, and terms of use for existing assets.
  • 13. New assets: The authors release their code and data under the Apache-2.0 license.This is the paper’s stated documentation and release information for new assets.
  • 14. Crowdsourcing and research with human subjects: The paper does not involve crowdsourcing or research with human subjects.Consequently, participant instructions, screenshots, compensation details, and related human-subject requirements are not applicable.
  • 14. Crowdsourcing and research with human subjects: The authors did not recruit study participants, making IRB approval or equivalent review not applicable.The paper also declares LLM usage as an important component of the core methods and refers readers to §B.
Loading 2608.18066v1…