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

> Memory-based self-improving agents are fragile and unreliable, amplifying evaluation variance and degrading under shuffled task orders due to task and environment underspecification.

- **Source:** [arXiv](https://arxiv.org/abs/2608.18066)
- **Published:** 2026-09-05
- **Permalink:** https://picx.dev/p/7RH28z
- **Whiteboard:** https://picx.dev/p/7RH28z/image

## Summary

## 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

| Benchmark | Description | Tasks |
|-----------|-------------|-------|
| **WebArena** | 6 domains: Shopping, Shopping Admin, GitLab, Reddit, Map, Multisite | 812 |
| **VisualWebArena** | Extends WebArena with visual element understanding; 3 domains: Classifieds, Reddit, Shopping | 910 |
| **SCUBA** | Enterprise CRM benchmark for Admin, Sales, Service roles | 267 (after exclusions) |

### 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, %)

| Method | Shopping(187) | Admin(182) | GitLab(180) | Map(109) | Reddit(106) | Multisite(48) | Classifieds(234) | Shopping(466) | Reddit(210) | Admin(158) | Sales(64) | Service(45) |
|--------|--------------|------------|-------------|----------|-------------|---------------|-----------------|---------------|-------------|------------|-----------|-------------|
| **Baseline** | 1.53 | 1.19 | 1.98 | 1.30 | 1.78 | 0.98 | 1.01 | 0.83 | 1.03 | 0.30 | 1.95 | 2.77 |
| **AWM** | 1.26(−18%) | 2.99(+152%) | 1.20(−39%) | 1.98(+53%) | 2.48(+39%) | 0.98(0%) | 1.79(+78%) | 1.01(+22%) | 2.38(+131%) | 2.09(+600%) | 1.28(−35%) | 2.77(0%) |
| **RBank** | 1.33(−13%) | 2.12(+79%) | 3.34(+69%) | 3.89(+200%) | 2.22(+25%) | 4.28(+336%) | 1.23(+22%) | 1.58(+91%) | 1.47(+43%) | 1.58(+429%) | 1.47(−24%) | 3.78(+36%) |

**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**

| AWM (Claude-3.5-Sonnet) 812 Tasks | RBank (Gemini-2.5-Pro) 684 Tasks |
|-----------------------------------|----------------------------------|
| Baseline: 32.7 | Baseline: 46.7 |
| +AWM: 36.3 | +RBank: 53.9 |
| **Our Baseline: 54.8** | **Our Baseline: 55.3** |

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)

| Method | WebArena | VisualWebArena | SCUBA |
|--------|----------|----------------|-------|
| Baseline | 54.8 | 54.9 | 49.6 |
| AWM | 54.1 (−0.7) | 54.5 (−0.4) | 50.1 (+0.5) |
| RBank | 56.3 (+1.5) | 55.6 (+0.7) | 51.1 (+1.5) |

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):

| Setting | Performance |
|---------|-------------|
| Original RBank | 49.8% |
| +Rub | Modest gain |
| +Env | Modest gain |
| +PMod | Modest gain |
| **+All** | **52.7% (+2.9%)** |

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

---

_Markdown view of https://picx.dev/p/7RH28z, served by PicX — AI-generated visual whiteboard summaries of research papers._