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

Overview§

This paper re-evaluates memory-based self-improving agents—agents that accumulate experience in a textual memory bank and use it to improve on a stream of tasks. The authors find that standard evaluation protocols hide severe reliability issues: (1) results are noisy across identical runs, and (2) improvement depends heavily on task order. They trace part of the problem to task/environment underspecification and show that injecting richer information (rubrics, environment feedback) into memory helps but does not fully close the gap.

Methodology§

Two representative memory-based self-improving agents are re-run under two perturbations:

• Multiple seeds/runs to quantify variance (previous work often reports a single run).
• Random task shuffles to test sensitivity to ordering (prior work uses a fixed default order that may act as an implicit curriculum).

Evaluation is performed on multi-step agent benchmarks (e.g., ALFWorld, WebShop). The authors compare: (i) baseline agent without self-improvement, (ii) agent with memory bank built from successful trajectories, and (iii) variants that add rubrics (detailed evaluation criteria) and environment feedback into memory entries.

Key Findings§

• High variance: Self-improving loops amplify existing evaluation noise. In complex multi-step tasks, the same configuration can show large performance swings across runs.
• Task-order sensitivity: Random shuffling often destroys the improvement seen with default ordering, implying that the original ordering provided a hidden curriculum.
• Underspecification: Manual inspection of memories reveals that agents struggle because task instructions and environment observations do not fully specify the goal or success criteria. Adding explicit rubrics and feedback partially recovers performance, but a residual gap remains.

Formalizing Underspecification§

Let $\mathcal{T}$ be a task distribution and $\theta$ the agent's parameters (including memory bank $M$). The agent's expected performance under an evaluation protocol $P$ is:

$$ J_P(\theta) = \mathbb{E}_{\tau \sim P} \left[ R(\text{Agent}(\theta, \tau)) \right], $$

where $\tau$ is a task ordering/seed. Standard protocols fix $\tau$ (e.g., default order, single seed), yielding a noisy estimate $\hat{J} = J_{\tau}(\theta)$. The paper shows that $\text{Var}(\hat{J})$ is large and that $J$ depends strongly on the ordering component of $\tau$.

To mitigate underspecification, each memory entry $m_i$ is augmented from $(s_i, a_i, r_i)$ to $(s_i, a_i, r_i, u_i)$, where $u_i$ contains rubric text or environment feedback. The agent then conditions on more complete specifications during inference.

Implementation Sketch§

The following pseudo-PyTorch code illustrates how memory entries are constructed and used in a self-improving loop:

class MemoryBank:
    def __init__(self, max_entries=50):
        self.entries = []
        self.max_entries = max_entries

    def add(self, trajectory, rubrics=None, env_feedback=None):
        # trajectory: list of (obs, action, reward)
        summary = f"Task: {trajectory.task}"
        if rubrics:
            summary += f"\nRubrics: {rubrics}"
        if env_feedback:
            summary += f"\nFeedback: {env_feedback}"
        self.entries.append(summary)
        if len(self.entries) > self.max_entries:
            self.entries.pop(0)

    def retrieve(self, query, k=5):
        # simple top-k by embedding similarity
        embs = model.encode(self.entries)
        q_emb = model.encode(query)
        scores = cosine_similarity(q_emb, embs)
        return [self.entries[i] for i in scores.topk(k).indices]

# Self-improving loop
agent = Agent()
memory = MemoryBank()
for task in shuffled_task_list:
    context = memory.retrieve(task.prompt)  # inject relevant past experience
    traj = agent.run(task, context)
    if traj.success:
        memory.add(traj, rubrics=task.rubrics, env_feedback=traj.feedback)

Implications§

• Evaluation protocol: Report multiple seeds and shuffled task orders; avoid relying on a single default ordering.
• System design: Human oversight interfaces must provide specifiability—agents should be able to query rubrics or receive structured feedback to reduce underspecification.
• Open problem: Since added information only partially closes the gap, other factors (e.g., memory retrieval noise, catastrophic forgetting) likely contribute to fragility.