TL;DR
This paper introduces WikiTrace, an evidence-linked memory system that prevents LLM agents from being misled by their own past experiences. By linking distilled "lessons" back to their original raw trajectories, WikiTrace allows agents to verify and refine memory items during task execution, significantly reducing "memory-induced degradation" and setting new performance bars across multiple agentic benchmarks.
What Problem Does This Paper Address?
Large Language Model (LLM) agents typically improve by storing "lessons" or "insights" from past tasks in an external memory. However, the authors identify a counterintuitive phenomenon called memory-induced degradation: sometimes, adding memory makes an agent fail at a task it could previously solve perfectly well without it.
This happens because most memory systems provide distilled insights without the context of the original "source code" (the raw trajectory of actions and observations). If a distilled lesson is slightly wrong, applied out of its original scope, or comes from a failed run where the agent drew the wrong conclusion about why it failed, the agent has no way to double-check the advice. It blindly follows a flawed map, leading to what the authors call Regression—turning a success into a failure.
Methods
The core contribution is WikiTrace, a hierarchical, evidence-linked memory structure organized into three layers:
- Insights: Concise, actionable lessons (e.g., "Always check the lamp is plugged in first").
- Compilations: A diagnostic summary explaining why a specific past run succeeded or failed.
- Raw Trajectories: The complete, unedited log of every action and observation from that past run.
During a new task, the agent doesn't just read the insights. It is prompted to "descend" through the links to the compilations or raw trajectories if:
- An insight lacks the specific details needed to act.
- Two insights conflict with each other.
- The insight originated from a failed past run.
- A current action fails, triggering a need for deeper troubleshooting.
By using terminal tools like grep or read on these linked files, the agent can "fact-check" its memory and revise its plan on the fly.
Datasets
The authors evaluated WikiTrace across five diverse benchmarks comprising eight different suites:
- Simulated Text Worlds: ALFWorld (household tasks), ScienceWorld (elementary science experiments), and PlanCraft (Minecraft-style crafting).
- Tool-Use Environments: AppWorld (interacting with web-style APIs) and $\tau^3$-bench (retail customer service interactions).
These benchmarks cover a wide range of reasoning requirements, from physical spatial logic to complex API orchestration.
Key Insights and Ideas
- The "Evidence Rule" for Failures: The authors found that 52% of memory-induced failures can be traced back to a specific memory item the agent followed. Most often, the item itself was simply wrong or applied out of scope.
- Failed Runs are High-Risk, High-Reward: Insights drawn from failed runs are surprisingly useful for teaching agents what not to do, but they are also the most likely to cause regression if provided without evidence. WikiTrace makes it safe to learn from failure.
- Strategic Descent: Agents naturally "descend" to check source evidence more often on harder tasks (44% of the time on "Hard" tasks vs. 22% on "Easy" ones). This suggests that the ability to verify memory is most critical when the reasoning overhead is highest.
- Plan Revision: In 43% of cases where an agent looked at the source evidence, it ended up changing its plan—either by refining a vague insight or catching a flat-out error in a stored lesson.
Key Results
WikiTrace consistently outperformed both "No Memory" baselines and existing state-of-the-art memory methods (like AWM, ExpeL, and ReasoningBank).
- Overall Performance: WikiTrace improved average scores by 10.7 points over the no-memory baseline.
- Reducing Regression: It reduced the regression rate (turning successes into failures) from 6.5% to 4.5% compared to a baseline that had access to the same insights but no source links.
- Gain vs. Regression: As shown in Figure 5, WikiTrace achieves a significantly higher "Gain" (turning failures into successes) while keeping "Regression" lower than prior works.
Limitations and Future Work
- Memory Scaling: Currently, WikiTrace places all insights in the initial prompt. As the number of past experiences grows, this will hit context window limits. The authors note that a more sophisticated retrieval system for insights will be necessary for long-term lifelong learning.
- Cost: Checking source evidence adds a modest overhead (about 1.17x the cost of just using insights). While the performance gains justify this, optimizing the "when to descend" logic could improve efficiency.
- Verification vs. Linkage: While the agent can check the run, the system doesn't guarantee the insight is correct; it only provides the evidence for the agent to decide. Future work could involve automated verification of insights before they are even stored.
Summary updated