Summary (Overview)

• This paper conducts a comprehensive re-evaluation of two memory-based self-improving agents (Agent Workflow Memory and ReasoningBank) across three web-browsing benchmarks (WebArena, VisualWebArena, SCUBA), broadening evaluation along two axes: multiple runs to quantify variance and shuffled task orders to investigate task order effects.
• Key finding 1: Agent evaluation is inherently noisy, and self-improving loops amplify this noise—variance across runs increased in 71% of cases, with best-worst gaps reaching up to 10.42 percentage points.
• Key finding 2: Agent improvement is highly dependent on task order; the default ordering imposes an implicit easy-to-hard curriculum that acts as a hidden prerequisite for success. Under shuffled orders, performance degrades by 4.5% instead of improving by 1.5%.
• Key finding 3: Task and environment underspecification during memory construction is identified as a key driver of fragility—agents generate plausible yet inapplicable memories (e.g., recommending API usage in a browser-only environment).
• Mitigation: Adding rubric information, environment feedback, and prompt modifications closes 31% of the performance degradation observed under shuffled task orders, but significant gaps remain, suggesting other uncharacterized factors contribute to the fragility.

---

Introduction and Theoretical Foundation

Background and Motivation

The paper addresses the emerging field of self-improving agents—systems designed to learn from past experiences and autonomously refine their performance over time. While recent works show promise in this direction, the authors note that little focus has been placed on stress-testing the reliability of such systems. In practical settings like enterprise deployments, there is minimal tolerance for error; initial failures risk losing user trust, and mistakes can cascade silently over the long term.

Problem Setting

The formal setting follows prior literature. The agent must complete an online stream of $N$ tasks, $\mathcal{Q} = \{q_0, q_1, ..., q_N\}$, while maintaining a textual memory $\mathcal{M}$. For each task $q_i$, the agent backed by a language model $L$ generates an action at each timestamp:

$$a_t \gets \pi_L(o_{0:t-1}, a_{0:t-1}; \mathcal{M}, \mathcal{A})$$

At the end of each task, the agent receives a reward $r \in [0, 1]$, where 1 indicates a "pass." A memory construction module $C$ updates the memory $\mathcal{M}$ based on the task trajectory and optionally the reward.

Representative Approaches

Two established methods are evaluated:

• Agent Workflow Memory (AWM): Summarizes reusable workflows from successful trajectories, checks for duplication, and includes all workflows in the agent's context for subsequent tasks.
• ReasoningBank (RBank): Stores more generic reasoning traces and insights from both successful and failed trajectories, using a retriever to select relevant past memories.

---

Methodology

Benchmarks

Evaluation Protocol

The evaluation was broadened along two axes:

1. Multiple runs: Three identical runs per experiment, reporting run-level statistics (average pass@1 per domain, standard deviation, best-worst gap).
2. Task order: Two shuffled task orders (Shuffle-1, Shuffle-2) in addition to the default order used in prior works.

Experiment Details

• Agent backbone: GPT-5-mini for both the agent and memory construction model
• Baseline harness: From [20] for WebArena/VisualWebArena, from [15] for SCUBA
• Key design choice: Ground-truth reward $r$ is provided during memory construction (rather than noisy LLM-judge proxy rewards $\hat{r}$ used in prior works)

Interventions for Underspecification

Three types of additional information were incorporated during memory construction:

1. Rubrics and Scores (+Rub): Function-based evaluation rubrics (e.g., must_include, exact_match, fuzzy_match) provided to clarify intended task interpretation
2. Environment Feedback (+Env): Web environment feedback (e.g., action errors from failed clicks or input operations)
3. Prompt Modification (+PMod): Explicitly discouraging unsupported strategies (APIs, human confirmation) and encouraging procedural knowledge

---

Empirical Validation / Results

3.2 Variance Results

Table 1: Variance-related metrics across 3 runs (standard deviation of pass@1, %)

Key findings:

• The no-memory baseline already exhibits significant variance (best-worst gap up to 4.4% on GitLab)
• Self-improvement methods amplify variance in 17 of 24 cases (≈71%), with 11 cases showing >50% relative increase
• Best-worst gaps widened to 8.26% (Map) and 7.78% (GitLab) with RBank, and 10.42% (Multisite)

Diminishing Effects with Stronger Baselines

Table 2: Contextualizing results with prior works

The no-memory baseline (GPT-5-mini) already outperforms the memory-enhanced results from prior works, demonstrating that self-improvement methods struggle to yield consistent gains when the base model is already capable.

Table 3: Overall results (average pass@1 across 3 runs)

RBank's 1.5% improvement on WebArena corresponds to a p-value of 0.23 (unpaired t-test over 3 runs), indicating limited statistical significance.

3.3 Task Order Results

• The default task order exhibits an implicit easy-to-hard curriculum (moving average of pass rates starts ~75%, drops below 40% after task ID 150)
• Under shuffled task orders, performance degrades significantly in 6 out of 8 cases:
  • WebArena Shuffle-1: AWM drops from 54.8% → 49.1%, RBank → 49.8%
  • VisualWebArena: AWM is significantly affected; RBank is less sensitive

4.1 Failure Modes in Memory Construction

Three notable findings from manual inspection:

1. Environment underspecification: Agents frequently reference "API" solutions (unsupported in browser-only environments), creating distraction. "User confirmation" appears 26 times in 3 WebArena runs and 22 times in VisualWebArena—leading to repeated "wait" actions until time limits are reached.

2. Task underspecification: Ambiguous queries (e.g., WebArena task 118 about jaw bruxism) lead to literal interpretations, overthinking, and irrelevant memories like "gather targeted patient/context details before giving medical guidance."

3. Memory "contagion": In Map tasks, agents adopt the Haversine Formula as a fallback distance calculation strategy when the map website fails to load. When correct answers occasionally result, this unintended strategy is amplified through self-improvement—the earlier it enters memory, the more frequently it's retrieved.

4.2 Mitigation Results

Figure 5 results (RBank under Shuffle-1):

Under Shuffle-2, +All improves by 1.1%; performance under Default order is maintained. The interventions close 31% of the performance degradation observed under shuffled orders, but significant gaps remain.

---

Theoretical and Practical Implications

Implications for Evaluation Methodology

The paper advocates for more rigorous evaluation protocols:

1. Single-run results should be interpreted with caution
2. Reporting outcomes across multiple runs and randomized task orders should be encouraged
3. Pilot new methods on well-specified benchmarks first, then stress-test on underspecified tasks to estimate worst-case performance

Implications for System Development

The analysis reveals that agent memories are merely unverified hypotheses rather than true lessons learned. They can be erroneous and cascade negatively into subsequent tasks. Key recommendations:

• Develop memory validation mechanisms to filter problematic memories
• Recognize that underspecification cannot be fully foreseen—real-world deployments unfold as a single, irreversible run
• Develop interfaces enabling effective human oversight and timely intervention before agents fail unintentionally

Broader Significance

This work extends the reliability-focused evaluation perspective from single-session agents to multi-session self-improving agents, where reliability becomes even more critical and harder to measure. The findings connect to growing concerns in the community regarding the "evaluation sciences of agents" [10, 50, 51, 52].

---

Conclusion

This work reveals the fragility of memory-based self-improving agents under more challenging settings:

1. Variance: Self-improving experiments exhibit significant variance across runs, making single-run evaluations potentially misleading
2. Task order sensitivity: Agents degrade rather than improve when tasks arrive in random order or when the baseline is already strong
3. Underspecification: Task and environment underspecification is a key limitation, with agents generating plausible-but-inapplicable memories

While incorporating additional information (rubrics, environment feedback, prompt modifications) reduces performance degradation by 31%, the remaining 69% gap suggests fundamental issues still to be uncovered.

Future Directions

• Investigating other uncharacterized factors contributing to fragility
• Developing memory validation mechanisms for long-term robustness
• Creating interfaces for effective human oversight and intervention
• Establishing more rigorous evaluation standards for self-improving agent systems