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

AI summary

Overview

Research area: Evaluation and reliability of LLM-based, memory-driven self-improving agents, studied in the web-browsing domain.

Technical level: Intermediate. The paper is readable without deep technical background, but it assumes familiarity with agent benchmarks, pass-rate metrics, and the idea of a textual "memory bank."

Scope: A systematic re-evaluation of two memory-based self-improving agent methods (Agent Workflow Memory and ReasoningBank) across three web benchmarks, testing them under repeated runs and shuffled task orders to expose how brittle their reported gains are.

Note on source content: the appendix result tables (per-domain breakdowns) are truncated in the supplied text; all figures cited below come from the main body and the tables that are present.

What This Paper Is About

Prior work on self-improving agents usually reports a pass rate from a single self-improving run, using a fixed, pre-determined task order. This paper asks whether those reported improvements survive when the same experiments are repeated multiple times and when the task stream is shuffled, as real-world user requests would be. It finds that the improvements largely do not hold up, and it traces part of the failure to underspecification in how memories are generated.

Key Contributions

1. A broadened re-evaluation protocol. The authors upgrade the underlying model and agent harness to establish a stronger baseline, then run each experiment three times and add two randomly shuffled task orders (Shuffle-1, Shuffle-2) alongside the default order, across WebArena, VisualWebArena, and SCUBA.

2. Quantification of evaluation variance. They show that the no-memory baseline is already noisy across runs, and that stacking a self-improving loop on top amplifies that noise in 17 of 24 cases (approximately 71%), with the best-worst gap between runs reaching up to 10 percentage points.

3. Evidence that self-improvement depends on task order. They demonstrate that the default task order encodes an implicit easy-to-hard curriculum that acts as a hidden prerequisite: RBank gains +1.5% under the default order but degrades by -4.5% under shuffled orders.

4. Identification of underspecification and a partial fix. Through manual inspection of agent memories, they identify environment and task underspecification as a driver of fragility, then show that adding rubrics/scores, environment feedback, and prompt modifications closes 31% of the observed degradation, leaving a large unexplained gap.

Main Findings

• Evaluation is intrinsically noisy. On the GitLab subset of WebArena (180 tasks), the no-memory baseline's best-worst gap across three runs is 4.4%, with a standard deviation of 2.0%. In VisualWebArena and SCUBA, domain-level best-worst gaps reach 2.4% and 6.7% respectively.

• Self-improvement amplifies variance. Variance increases in 17 of 24 cases, and in 11 cases the relative increase exceeds 50%. Standard deviations reach as large as 3.9%, and best-worst gaps widen to 8.2% in the Map domain and 7.8% in the GitLab domain of WebArena.

• Gains are not statistically significant with a strong baseline. With GPT-5-mini, RBank improves WebArena by +1.5% (54.8 to 56.3), but a two-sided Welch's t-test on three runs gives p=0.23. AWM actually drops (-0.7 on WebArena, -0.4 on VisualWebArena, -1.7 on SCUBA).

• Prior gains came partly from weaker starting points. AWM with Claude-3.5-Sonnet reported 32.7 on 812 WebArena tasks and 36.3 with AWM; RBank with Gemini-2.5-Pro reported 46.7 on 684 tasks and 53.9 with RBank. The authors' own baseline reaches 54.8 (WebArena) and 55.3 (684-task subset), and 54.9 on VisualWebArena — comparable to or above those memory-enabled results without memory.

• The default order is an implicit easy-to-hard curriculum. Moving averages (window = 30) of baseline success rates start around 75% and fall below 40% once task IDs exceed 150; the pattern is more oscillatory on SCUBA.

• Shuffling the task order hurts. On WebArena under Shuffle-1, performance falls from 54.8% to 49.1% (AWM) and 49.8% (RBank). Model performance degrades significantly in 6 out of 8 cases when shuffled orders are used. On VisualWebArena, AWM is significantly affected by task order while RBank is less sensitive.

• Environment underspecification produces inapplicable memories. The memory module repeatedly recommends API-based solutions even though the environment is browser-only. Memories about "user confirmation" appear 26 times across 3 WebArena runs and 22 times across 3 VisualWebArena runs, despite the environment not supporting it.

• Memories are "contagious." In the Map domain, agents that fail to load the route engine adopt a fallback using the Haversine Formula. Because the approximation occasionally yields correct answers, the strategy is reinforced into memory, and the earlier it enters memory, the more often it is retrieved later — an effect that may contribute to variance across runs.

• Task ambiguity creates spurious memories. In WebArena task 118 ("I have jaw bruxism problem, show me something that could alleviate the problem"), the agent gives medical advice instead of finding a mouth guard on the shopping site, and then writes irrelevant memories such as "gather targeted patient/context details before giving medical guidance."

• Additional information helps only partially. Under Shuffle-1, combining rubrics (+Rub), environment feedback (+Env), and prompt modification (+PMod) improves RBank by 2.9% (49.8% to 52.7%). Under Shuffle-2 the gain is 1.1%, and the default order is maintained. Overall, these interventions close 31% of the degradation, leaving a 69% gap.

• Task-level inconsistency is also large. For the no-memory baseline, the gap between pass@3 and pass^3 frequently exceeds 20% (WebArena: pass@3 65.4 vs pass^3 43.3, with average pass 54.8).

Methodology in Plain English

The researchers took two published memory-based self-improvement methods — Agent Workflow Memory (AWM), which summarizes reusable workflows from successful trajectories, and ReasoningBank (RBank), which stores more general reasoning insights from both successful and failed trajectories and retrieves relevant ones — and rebuilt them on top of a stronger baseline agent. The baseline uses the WALT harness for WebArena and VisualWebArena, and the SCUBA harness for SCUBA, with GPT-5-mini as both the agent model and the memory-construction model at default (medium) reasoning effort and temperature 1.0.

Instead of running each experiment once, they ran it three times identically to measure run-to-run variance, and they also ran it with two randomly shuffled task orders to test sensitivity to ordering. They deliberately fed the ground-truth reward into memory construction, rather than the noisy LLM-Judge proxy reward used in prior work, to avoid confounding their analysis. They compared the baseline, AWM, and RBank using run-level statistics: average pass@1 per domain, its standard deviation across three runs, and the best-worst gap among the three.

When results degraded, they manually read through the memories the agents wrote and categorized the failure modes. From that inspection they proposed three concrete fixes to the memory-construction step: supplying task rubrics and evaluator scores (+Rub), supplying environment feedback about failed actions (+Env), and rewriting the prompt to discourage unsupported strategies such as API use or human confirmation (+PMod). They then tested these individually and combined under shuffled and default orderings. Additional experiments with two other models, a filesystem-based method, an enterprise tool-use benchmark, and more runs are reported in the appendix.

Why This Matters

Impact on research. The paper challenges a widely used evaluation practice: reporting a single self-improving run under a fixed task order. It shows that such numbers can be misleading in either direction, that the fixed order itself is a hidden advantage, and that memory-based self-improvement can hurt rather than help once the baseline model is strong. It aligns with the view that reliability should be treated as a primary evaluation axis alongside capability, extending that argument from single-session agents to multi-session self-improving ones.

Real-world applications:

• Enterprise workflow automation. The SCUBA benchmark covers platform administrators, sales representatives, and service agents working in web-based CRM software — settings where an initial failure can cost user trust and errors can cascade silently.
• E-commerce and shopping agents. WebArena's Shopping and Shopping Admin domains represent agents acting on retail sites, where an agent that "learns" an unsupported strategy such as calling an API will fail repeatedly.
• Customer service and support systems. The SCUBA Service domain (45 tasks) and the broader customer-service benchmarking trend make the variance findings directly relevant to deployment decisions.
• Navigation and logistics-style tasks. The Map domain case study shows agents inventing a Haversine-distance approximation when the website fails to respond, a behavior that gets reinforced into memory and would be risky in production routing systems.

Industry relevance. The paper frames the problem in deployment terms: enterprise settings have minimal tolerance for error, and initial mistakes can cascade over the long term with irreversible or prohibitively costly effects in high-stakes domains. It also reports practical cost figures for planning — with GPT-5-mini, one run over all 812 WebArena tasks costs about $25 and one run over all 267 SCUBA tasks costs $29 (no-memory baselines), run on a standard 64-CPU server — which matters because the paper's core recommendation is to run experiments multiple times.

Future Directions

• Memory validation mechanisms. The paper argues that without validation, agent memories are unverified hypotheses rather than lessons learned. Designing filters that catch and discard problematic memories before they propagate is left open.

• Explaining the remaining 69% gap. Underspecification explains only part of the degradation. The authors suggest the rest likely arises from interacting factors — task quality, the design of the self-improvement and memory mechanisms, and the base LLM's characteristics — and that attributing blame would require large-scale memory analysis, benchmark re-annotation, and isolating experiments.

• Human oversight interfaces. Because underspecification cannot be fully foreseen and real-world deployments unfold as a single irreversible run, the authors call for interfaces that let humans review large volumes of agent memories and intervene before failures occur.

• More rigorous evaluation protocols. The recommendation is to report results across multiple self-improving runs and randomized task orders, and to pilot new methods on well-specified tasks before stress-testing on underspecified ones to estimate worst-case performance.

Target Audience

Researchers and engineers working on LLM agents, agent memory, and continual or self-improving systems; benchmark and evaluation designers who need to know why single-run numbers are unreliable; and practitioners planning enterprise deployments of browsing or tool-using agents, who will find the reliability framing, the case studies, and the cost figures directly actionable. Readers looking for a new self-improvement algorithm will not find one here — the contribution is diagnostic and methodological.

Authors’ abstract

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.