Self-Improving Agents Are Mostly Measuring Noise

Paper: 2608.18066 Authors: Qinyuan Ye, Yu Li, Yada Pruksachatkun, Jiaxin Zhang, Chien-Sheng Wu Categories: cs.AI, cs.CL, cs.LG

The Gap

Memory-based self-improving agents have a beautifully simple pitch. Give an agent a stream of tasks, let it write a note to itself after each one, store the notes in a textual memory bank, retrieve relevant notes before the next task. No gradients, no fine-tuning, no training infrastructure — just an agent that gets better at your product by using your product. Agent Workflow Memory (AWM) does this by summarizing reusable workflows out of successful trajectories. ReasoningBank (RBank) generalizes it: memory items are free-form reasoning insights, harvested from failures as well as successes, pulled back by a retriever rather than dumped wholesale into context.

The reported numbers are good. AWM took a Claude-3.5-Sonnet WebArena agent from 32.7% to 36.3%. RBank took a Gemini-2.5-Pro agent from 46.7% to 53.9% on a 684-task subset. Both results, like essentially all web-agent evaluation, come from a single run in a single fixed task order.

That is the gap, and it is not a nitpick. A self-improving agent is a stateful system: what it writes after task 7 changes what it retrieves at task 8, which changes what it writes after task 8. Any evaluation protocol that reports one sample from such a system is reporting one draw from a distribution nobody has looked at. And the “fixed task order” part hides a second problem — if the benchmark’s default ordering happens to be easy-to-hard, the agent gets a curriculum it never asked for and no one credited.

This paper does the boring, expensive, necessary thing: re-run everything three times, shuffle the task order, and upgrade the baseline to a current model so the starting point isn’t a straw man.

[SETTING] memory-based self-improvement: task stream ->
          write memory -> retrieve -> next task
     |
     v
[HOW IT IS MEASURED TODAY] one run, one fixed task order,
     mean pass@1, compared to a same-run no-memory baseline
     |
     v
[SUSPICION] a stateful loop over a stochastic agent in a
     stochastic environment cannot be summarized by one draw;
     and "fixed order" may be smuggling in a curriculum
     |
     +---------------------+----------------------+
     v                     v                      v
[AXIS 1: 3 runs]     [AXIS 2: shuffle]     [AXIS 0: strong baseline]
 report std and       Default vs            GPT-5-mini + modern
 best-worst gap,      Shuffle-1 vs          harness, ground-truth
 not just the mean    Shuffle-2             reward not LLM judge
     |                     |                      |
     +---------------------+----------------------+
                           v
[EVIDENCE] variance up in 17 of 24 cases (~71%); best-worst
     gap reaches 10.4 points; +1.5% default-order gain has
     p = 0.23; shuffled order turns +1.5% into -4.5%
                           |
                           v
[DIAGNOSIS] read the memories by hand: they are full of
     plausible-but-impossible advice (use the API, ask the
     user) because nobody told the writer what the world is
                           |
                           v
[PARTIAL FIX] inject rubrics + environment feedback + a
     negative-constraint prompt: closes 31% of the gap.
     69% remains unexplained.

The Increment

One sentence: Before this paper, “self-improving agent” meant a method with a positive delta on a leaderboard; after it, the delta is known to be smaller than the run-to-run noise it creates, and known to flip negative when you remove the one thing nobody realized the method depended on — the order the tasks arrive in.

Core Mechanism

There is no new architecture here. The “method” is an evaluation design, and it is worth walking through because the design choices are the contribution.

The setup is deliberately generous to the methods under test. Three benchmarks: WebArena (812 tasks, six domains), VisualWebArena (910 tasks), and SCUBA (267 enterprise CRM tasks after removing ones broken by site updates). GPT-5-mini as both the agent backbone and the memory-construction model, on a modern harness — which matters enormously, because that no-memory baseline hits 54.8% on WebArena, higher than RBank’s memory-enhanced 53.9% from the original paper. The self-improvement methods are being asked to improve an agent that already beats their published result. On top of that, the authors hand the memory writer the ground-truth reward rather than an LLM-judge proxy, removing a known source of noise that the original implementations lived with. If the methods fail here, they don’t fail because they were sandbagged.

Then two axes open up. Axis one: run every configuration three times identically and report the standard deviation and the best-worst gap per domain, not just the mean. Axis two: in addition to the default task order (ascending task ID, exactly what prior work used), run two random shuffles. Those two axes are the whole experiment, and they are enough.

Then the forensics. When the numbers come back bad, the authors read the memory banks by hand and count keywords. That is where the mechanism of failure actually shows up — not in an aggregate metric but in a memory item recommending an API call in an environment with no API.

  THE LOOP UNDER TEST (per run)

   task q_1 ---> [ agent, backbone L ] ---> trajectory ---> reward r
                        ^                                     |
                        | retrieve                            | write
                        |                                     v
                  +----------------------------------------------+
                  |          MEMORY BANK  M  (plain text)        |
                  |  no validation. no expiry. no retraction.    |
                  +----------------------------------------------+
                        |                                     ^
                        v                                     |
   task q_2 ---> [ agent ] ---> trajectory ---> reward ------ +
        ...
   task q_N

  WHERE THE NOISE ENTERS AND WHY IT COMPOUNDS

   LLM sampling  ~~>  trajectory differs  ~~>  reward differs
                                                    |
                                                    v
                                    memory written differs
                                                    |
                        (retrieved for every later task)
                                                    |
                                                    v
                     run A and run B diverge permanently
                     ==> variance of the loop > variance of the agent

  THE BROADENED PROTOCOL

   old:   [ 1 run ][ default order ]  ==>  one number, one delta

   new:   [ run 1 ][ run 2 ][ run 3 ]  x  [ Default   ]
                                          [ Shuffle-1 ]
                                          [ Shuffle-2 ]
          ==> mean, std, best-worst gap, and order sensitivity

The metaphor: an unmoderated team wiki. The memory bank is a wiki that every engineer can write to after closing a ticket. The memory-construction module is the post-mortem each engineer types up. The retriever is the search box you hit before starting your next ticket. So far, so good — this is how real teams actually accumulate competence.

Now remove three things that real wikis have. Remove the editor: nothing anyone writes is ever reviewed. Remove retraction: nothing is ever deleted or marked obsolete. And remove the onboarding doc, so nobody writing a page knows what the team is actually allowed to do — which internal systems exist, which are off-limits, whether you can even call an API.

You get exactly the pathologies the paper documents. Someone hits a slow map service, eyeballs the distance with a formula from memory, happens to get an answer close enough to pass, and writes a page: “if the route engine is flaky, estimate distance directly.” Nobody reviews it. It surfaces in search. It gets used again, cited again, and by mid-quarter it is house style — the paper watches the word “Haversine” climb monotonically through the retrieved-memory counts. Someone else, never told the team is browser-only, writes a page recommending the API route; the agent later burns turns trying to follow it. Someone writes “get user confirmation before destructive actions,” which is genuinely good advice in the real world and, in an environment with no user to ask, means the agent issues wait until it times out — 26 such memories across three WebArena runs, 22 across three VisualWebArena runs.

And the curriculum point falls out of the same picture. A wiki built by juniors who were handed easy tickets first is a decent wiki. A wiki built by juniors thrown at random-difficulty tickets from day one is full of confident speculation written by people who were lost, and everyone after them reads it.

Key Concepts

• Variance amplification in a stateful loop: A plain agent evaluated once has variance from LLM sampling plus environment flakiness — already larger than people admit. On WebArena’s GitLab subset (180 tasks) the no-memory baseline’s best and worst of three runs differ by 4.4 points, with a standard deviation of 1.98. That is already the size of a publishable improvement. Now wrap the self-improving loop around it: a coin flip at task 3 changes a memory that is retrieved by tasks 4 through 180, so early randomness doesn’t average out, it branches. Empirically, variance grows in 17 of 24 domain-method cells (about 71%), with 11 cells showing a relative increase above 50%. RBank’s best-worst gap reaches 7.8 points on GitLab, 8.3 on Map, and 10.4 on Multisite. Concretely: if your method’s headline gain is 1.5 points and its best-worst spread is 8, a single run tells you approximately nothing.

• The implicit curriculum hidden in task IDs: Benchmarks are built by annotators who write easy tasks first and harder ones later, so task ID correlates with difficulty. Plot the baseline agent’s moving-average pass rate along the default order and you see it start near 75% and fall below 40% past task 150 on both Shopping Admin and GitLab. Prior work ran self-improvement in exactly this order. So the agent spends its first fifty tasks succeeding, which is precisely the regime where the memory writer produces clean, correct workflow notes — and only then meets the hard tasks, armed. That is a curriculum, and it was free and uncredited. Take it away and the direction of the effect reverses: averaged over settings, +1.5% under the default order becomes -4.5% under shuffled orders. On WebArena Shuffle-1, both methods land near 49% against a 54.8% baseline. Note carefully what the failure is: not “improves less,” but improves less than nothing. The memory is actively worse than no memory. Six of eight order-shuffled comparisons degrade.

• Underspecification, and why memories are hypotheses rather than lessons: The memory-construction prompt in the original RBank implementation is roughly “extract useful insights from the trajectory.” It is never told what the environment supports, and the agent’s task query is often ambiguous to begin with. WebArena task 118 asks the agent to “show me something that could alleviate” jaw bruxism; the intended answer is a mouth guard on the shopping site, but the agent reads it as a medical question, replies “consult your dentist,” fails, reflects on the failure, and writes the memory “gather targeted patient/context details before giving medical guidance” — a sentence that will now be retrieved and will help nobody. The paper’s sharpest formulation, from the conclusion: without validation, agent memories are unverified hypotheses, not lessons learned. Every reflection loop currently in production has this property.

Framework Shift

Before (mainstream practice):        After (this paper):

 [ agent + method ]                   [ agent + method ]
        |                                    |
    1 run, default order            3 runs x 3 orders
        |                                    |
        v                                    v
   pass@1 = 53.9                     mean 56.3, std up to 3.9
   baseline  = 46.7                  best-worst gap up to 10.4
        |                            p = 0.23 at n = 3
        v                                    |
   delta = +7.2  ==> "it works"              v
                                     is the delta bigger than
                                     the spread it created?
   memory = knowledge                            ...often no

   task order = incidental           memory = unverified
                                              hypothesis
   baseline = whatever the           task order = a hidden
   original paper used                   prerequisite

                                     baseline = current SOTA,
                                       or the result is moot

From “does the delta exist” to “is the delta larger than the instability the method introduces, and does it survive removing the ordering nobody declared,” the core shift is treating reliability as a first-class axis rather than an afterthought that a mean pass rate quietly averages away.

Expert Assessment

Problem choice: Excellent, and unglamorous in the way that good reliability work usually is. Self-improving agents are one of the loudest directions in the field right now, and the entire evidence base rests on single-run, single-order comparisons. The task-order finding in particular is the kind of thing that is obvious in retrospect and that nobody checked — benchmark task IDs correlating with difficulty is not a subtle artifact, it is a natural consequence of how humans write benchmarks, and it has been silently subsidizing an entire method family. The baseline-drift point is nearly as valuable: both methods were validated against agents roughly twenty points weaker than what you would deploy today, and the gains do not survive the model upgrade. That is a general warning about any method whose job is to compensate for a weak base model.

Method maturity: The protocol is right, but thin in one respect that matters. Three runs is the minimum that lets you say the word “variance” at all, and a standard deviation estimated from n = 3 is itself extremely noisy — the paper is measuring instability with an unstable instrument. Similarly, “17 of 24 cases” sounds strong but under a coin-flip null you’d expect 12; the claim is really carried by the magnitudes (11 cells above +50% relative) rather than the count. Two shuffles is likewise the smallest number that isn’t one. None of this overturns the conclusions — the effects are large and the direction is consistent — but the honest reading is “clear qualitative signal, imprecise quantitative estimates,” and I would rather the paper had said that itself.

Experimental integrity: Unusually good, and deliberately biased against the paper’s own thesis, which is the right direction to lean. They upgraded the baseline instead of inheriting a weak one. They handed the memory writer ground-truth rewards instead of a noisy LLM judge, which is more generous than the original implementations. They reported the p-value on their own headline gain (0.23) rather than burying it. One point cuts both ways and deserves flagging: with n = 3 you have almost no statistical power, so p = 0.23 is weak evidence of no effect, not evidence of absence — a reader should take it as “unresolved,” which is also what the authors say. The one place I would push back is the +Rub intervention: feeding the evaluator’s rubric into memory construction leaks grading signal into the method. The authors are careful that the agent never sees rubrics while acting, and as a diagnostic for underspecification it is exactly the right probe, but it is not a deployable technique, and the derived “closes 31% of the gap” headline rests on a small number of runs at one shuffle.

Writing quality: Clean and well-organized; the case studies (Haversine, jaw bruxism, “user confirmation” causing timeout loops) are the best part of the paper and do more persuasive work than any table. The section I would rewrite is the variance analysis, which reports std and best-worst gap without ever stating uncertainty on those estimates or the number of runs needed to make them meaningful. A short power analysis — “to detect a 1.5-point effect against this observed spread you need roughly N runs” — would convert the paper’s central recommendation from an exhortation into a usable number, and that is the one thing practitioners will actually want.

Verdict: strong accept — the field is publishing self-improvement gains that are smaller than the noise those methods create, and this paper demonstrates it carefully, on strong baselines, with a mechanistic diagnosis rather than just a negative result.

Takeaways

• Shuffle the task order. It is the cheapest, most diagnostic ablation you are not running. If your online-learning agent depends on an ordering you did not choose deliberately, you have a benchmark artifact, not a method. This transfers directly to curriculum learning, RAG systems that accumulate corpora, personalization loops, anything with a stream.
• Report the best-worst gap, not just the standard deviation. At n = 3 a std is nearly meaningless, but “best run minus worst run” is a concrete, honest, hard-to-misread statement about what a reader would have seen if they ran it once. Put your method’s gain and this gap in the same sentence and let people judge.
• Re-validate against a current baseline before believing any compensatory method. AWM and RBank were measured against agents around 20 points weaker. Methods that patch a weak model’s failure modes have a natural expiry date; check whether yours has passed.
• Tell the memory writer what the world does not allow. The +PMod intervention is a prompt edit listing what to include (procedural knowledge, navigation structure, UI tips) and what to strictly avoid (API-based solutions, external sites, requesting human confirmation, task-specific details). This is a one-line change to any reflection loop, and it directly kills the plausible-but-impossible memory class.
• Separate what the actor sees from what the reflector sees. Rubrics and grader output are unavailable during the attempt but available during the post-mortem. That asymmetry is a clean, general design pattern for reflection systems, and it is more useful than the specific numbers around it.
• Watch for lucky-shortcut lock-in. The Haversine story is the transferable failure mode: a workaround adopted because the real tool was momentarily broken, occasionally rewarded, written to memory, then retrieved forever with monotonically increasing frequency. Any self-improving system that writes on success and never validates will canonize its luckiest accidents. The earlier the accident lands, the more it dominates — which is also why runs diverge.
• The open problem is stated plainly and is worth stealing: memory validation. Nothing in the current stack ever asks whether a stored memory is true, whether it has expired, or whether it should be retracted. Filtering, verification, and lifecycle management for agent memory is an unclaimed and obviously necessary piece of infrastructure.