On the Fragility of Self-Improving AI Agents: Variance, Task Order, and Underspecification
> "We must learn to navigate in uncertainty rather than wait for the map to be complete." — Karl Popper
This post is a deep-dive commentary on the Salesforce AI Research paper *"On the Fragility of Self-Improving Agents: Variance, Task Order, and Underspecification"* (arXiv:2608.18066). The study dissects two memory-based self-improving systems—Agent Workflow Memory (AWM) and ReasoningBank (RBank)—and identifies three structural weaknesses behind their apparent gains.
What Are Self-Improving Agents?
Self-improving agents learn from a stream of online tasks by extracting reusable "workflows" or reasoning patterns into a memory bank:
- AWM extracts full workflows from successful trajectories (e.g., search → filter → compare → order) and injects them into context.
- RBank also learns from failures, extracting general reasoning insights retrieved by a retriever for later tasks.
- The authors ran each configuration 3 times, reporting means, standard deviations, and best-worst gaps.
- Baseline variance is already large: best-worst gap of 4.4% on WebArena's GitLab subset and 6.67% on SCUBA's Service subset—identical setups, different outcomes.
- Memory mechanisms amplify noise: RBank widened the GitLab best-worst gap to 7.8%; Map-domain standard deviation rose from 1.30% to 3.89% (+200% relative).
- In 17 of 24 (71%) domain-method combinations, variance increased with self-improvement. Best-vs-worst runs of the same experiment can differ by up to 10 percentage points.
- Prior work reported only single runs, so reported gains may reflect a "lucky run."
- Default benchmark task ID orderings (e.g., WebArena) are implicitly sorted easy-to-hard: pass rates drop from ~75% in early segments to below 40% late—effectively a hidden curriculum.
- Experiments with two shuffled orderings showed: RBank gained +1.5% on average under default order, but lost 4.5% under shuffled orders.
- Conclusion: much of the previously reported "improvement" stems from ordering, not from memory itself. The agents are not truly self-improving; they are sliding down a preset slope.
- Environment underspecification: memory audits found many plausible-but-infeasible memories, e.g., "call an API" or "ask the user to confirm" in browser-only environments. These "dead memories" are repeatedly retrieved and corrupt decisions.
- Task underspecification: WebArena task 118 ("I have jaw bruxism problem...") is meant to be a shopping-navigation task, but the agent interpreted it as open-domain medical Q&A, generating irrelevant bruxism-treatment memories.
- Memory contagion: a lucky success (using the Haversine formula due to page-load latency) was stored and then wrongly reused in tasks requiring precise navigation.
- 🚦 Is your evaluation based on a single run? Results may not be reproducible.
- 🚦 Are tasks in a fixed order? "Improvement" may be an order effect.
- 🚦 Does your agent know what the environment can and cannot do? Otherwise memory becomes poison.
- Ye, Q., Li, Y., Pruksachatkun, Y., Zhang, J., & Wu, C. S. (2026). On the Fragility of Self-Improving Agents: Variance, Task Order, and Underspecification. *arXiv preprint arXiv:2608.18066*.
- Zhou, S., et al. (2024). Agent Workflow Memory. *NeurIPS 2024*.
- Yu, L., et al. (2024). ReasoningBank. *ICLR 2025*.
- Zhou, S., et al. (2024). WebArena: A Realistic Web Environment for Building Autonomous Agents. *ICLR 2024*.
- Koh, J. Y., et al. (2024). VisualWebArena: Evaluating Multimodal Agents on Realistic Visual Web Tasks. *ACL 2024*.
The promise: agents get smarter over time. The reality: memory can be a liability.
Key points
1. The curse of variance
2. The illusion of task order
3. Underspecification: the deepest cause
Agents lack explicit specifications of (a) what the environment can do and (b) what tasks require:
4. Mitigation attempts
| Intervention | Content | Effect | |---|---|---| | +Rub | Provide the evaluator rubric and scores to memory construction | Partial relief | | +Env | Provide environment execution feedback (failed clicks, missing elements) | Partial relief | | +PMod | Explicitly forbid memory-API calls, external sites, human confirmation | Partial relief | | +All | All combined | Closes 31% of the performance gap |
A significant gap remains, indicating other uncharacterized factors (retrieval noise, context-window limits, delayed reward attribution).
Takeaways
For researchers: 1. Report multi-run statistics (variance, std, confidence intervals)—single runs are nearly meaningless. 2. Randomize task order when evaluating self-improvement methods. 3. Model environment constraints explicitly and feed them to memory construction. 4. Develop task-clarification mechanisms so agents ask rather than guess.
For practitioners—three red lights:
Recommended evaluation protocol: at least 3 runs per setting; stress tests under adversarial/shuffled conditions; periodic human audits of memory banks to remove dead memories; systems designed for effective human oversight.
Key numbers at a glance
| Metric | Value | |---|---| | Combinations where variance increased | 71% (17/24) | | Max best-worst gap in same experiment | 10 points | | RBank gain, default order | +1.5% | | RBank change, shuffled order | -4.5% | | Gap closed by underspecification interventions | 31% |
Conclusion
The point is not to abandon self-improving agents but to confront their fragility—like aviation engineering, robustness comes from understanding every failure mode and designing redundancy around it. As Popper put it, we must learn to navigate with incomplete maps.