On the Fragility of Self-Improving Agents: Variance, Task Order, and Underspecification
Qinyuan Ye, Yu Li, Yada Pruksachatkun, Jiaxin Zhang, Chien-Sheng Wu
cs.AI, cs.CL, cs.LG
2026-08-19
Salesforce re-evaluates AWM and ReasoningBank: +1.5 points in default order, -4.5 when tasks are shuffled. Variance rises in 71% of settings, with best-worst gaps up to 10 points.
Memory-based self-improving agents write textual notes after each task and retrieve them later. AWM stores reusable workflows from successes. ReasoningBank stores broader tips from both wins and losses. Prior papers usually run the default task order once and report a few points of gain.
That protocol assumes two things production does not: an easy-to-hard curriculum, and a single run as the method. Users do not submit tickets by task ID. One ugly run is not averaged away. Salesforce AI Research replugs AWM and ReasoningBank into a stronger GPT-5-mini harness, repeats every setting three times, and shuffles the task stream.
Two extra axes: three identical runs for variance; Shuffle-1 and Shuffle-2 besides the default order. The no-memory web agent is the baseline (WALT-style on WebArena / VisualWebArena, the original harness on SCUBA). Memory methods sit on top. Memory writers get ground-truth rewards, not an LLM judge, so judge noise does not leak into the analysis.
WebArena has 812 tasks, VisualWebArena 910, SCUBA 267 after dropping pages broken by site updates. A full WebArena run costs about $25; SCUBA about $29.
To explain the drop, the authors inspect ReasoningBank items by hand and then add three signals at memory-write time:
The no-memory baseline is already noisy. On WebArena GitLab (180 tasks) the best-worst gap is 4.44 points, std 1.98%. VisualWebArena domains reach 2.4%; SCUBA reaches 6.7%. A 3-point method win from one run can be luck.
Self-improvement makes that worse in 17 of 24 comparisons (about 71%), 11 of them by more than 50% relatively. ReasoningBank's best-worst gap hits 7.78% on GitLab, 8.26% on Map, 10.42% on Multisite. Early coin-flips get written down and then reused.
Under the default order the gains are already thin:
| Method | WebArena | VisualWebArena | SCUBA |
| No-memory baseline | 54.8 | 54.9 | 49.6 |
| AWM | 54.1 (-0.7) | 54.5 (-0.4) | 50.1 (+0.5) |
| ReasoningBank | 56.3 (+1.5) | 55.6 (+0.7) | 51.1 (+1.5) |
The +1.5 on WebArena for ReasoningBank has p=0.23 over three runs. Older numbers: AWM on Claude-3.5-Sonnet 32.7 to 36.3; ReasoningBank on Gemini-2.5-Pro, 684-task subset, 46.7 to 53.9. GPT-5-mini with no memory already sits at 54.8 (full) / 55.3 (684-task subset). The old headroom is gone. Appendix pass rate on SCUBA is 29.7%; the 49.6 in the main table is milestone.
The default order hides a curriculum. A 30-task moving average starts near 75% and falls below 40% after task ID 150. On Shuffle-1, WebArena falls from 54.8% to 49.1% (AWM) and 49.8% (ReasoningBank). Six of eight shuffled settings get worse. The abstract's headline is +1.5% in default order, -4.5% when shuffled.
The bad memories are specific. If nobody says "browser only", the writer recommends APIs and waiting for a human. The eval cannot do either, so the agent waits out the clock. In Map, a slow page load leads the agent to the Haversine formula; a few lucky hits get stored, and earlier storage means more later retrievals. Task 118 asks for a product that helps bruxism; the agent answers "see a dentist", then writes a medical-intake tip that has nothing to do with shopping.
Adding all three signals on Shuffle-1 lifts ReasoningBank from 49.8% to 52.7%, recovering about 31% of the drop. Shuffle-2 +All reaches 51.8%. Shuffled runs still sit below the no-memory baseline.
Self-improvement papers should report multiple runs and a shuffled stream. A +1.5 on the default order can flip to -4.5. A 3-point win on one run can be variance.
In production, a text memory is an unchecked hypothesis, not a lesson. Bad entries spread. Being able to read, delete, and edit memories matters more than another auto-summarizer. On a strong browsing agent, classic AWM / ReasoningBank no longer clear a statistical bar.
The authors stay inside web browsing and two memory methods. Newer memory managers are untested. Memory audit is a qualitative sample, not a full pass. The repair ablations run only on ReasoningBank.
Three runs are still a thin sample for a standard deviation. SCUBA's main table uses milestone; pass lives in the appendix. +Rub feeds the official rubric to the memory writer, which a live user will not do. About 69% of the shuffle drop is still unexplained.