KAIST's WikiTrace: Provenance-Linked Memory Boosts Agent Performance by 10 Points

Introduction

Researchers from KAIST (Yukyeong Lee, Yumin Choi, Jinheon Baek, Sung Ju Hwang) propose WikiTrace , a memory architecture that equips LLM agents with experiences tied to their original execution traces. The system is evaluated on eight tasks spanning five environments, using the deepseek-v4-flash model (2026-04-23 release, high reasoning effort). With WikiTrace the agent reaches an average score of 90.2 , compared to 79.5 when given no memory at all.

Methodology: Three-Layer Memory Construction

Memory is built once from a batch of non-memory training runs and never updated afterwards. Each execution is processed by a compiler that receives the task, the full execution trace, and a success/failure flag. The compiler produces three linked layers:

Summary – a narrative of key decisions and observations, written from a success or failure template. The paper notes this remains an interpretation, not a verified cause.

Experiences – up to three per execution, each recording what to do , when to apply , source execution ID , and whether that execution succeeded . Experiences are immutable; conflicting statements are retained for the acting agent to resolve.

Raw execution trace – the complete record: task, step-by-step reasoning, actions, observations, and outcome. Experiences point to both the summary and the raw trace.

Retrieval and Drill-Down at Inference

When a new task starts, the agent receives all stored experiences plus the three most similar past runs (by task similarity). The agent can drill down from an experience to its summary and then to the raw trace when:

the experience lacks actionable detail,

the experience originates from a failed run,

two experiences conflict, or

a step fails during execution.

The raw trace is read-only; the agent uses file-reading and command-line tools to locate decisive facts (e.g., correct command syntax). The acting agent is Pi's terminal agent with environment-specific ReAct prompts.

Experimental Setup

Environments (8 tasks): Household (seen/unseen), Science experiments (seen/unseen), Minecraft crafting (text-world), Retail dialogue with tools, AppWorld (normal and challenge splits).

Protocol: Three random seeds, averaged. Memory built once from non-memory runs; no re-verification allowed.

Baselines: No memory; three prior methods that compress executions into procedural rules (average ~80); short-sentence-only ablation (experiences without provenance links).

Main Results

WikiTrace achieves the highest score on every one of the eight tasks and is the only method that never falls below the no-memory baseline.

Overall average: 90.2 (WikiTrace) vs 79.5 (no memory) vs ~80 (prior rule-based methods) vs 87.0 (short sentences only).

Largest gains in text worlds: Minecraft crafting 56.3 → 81.3; unseen science experiments 72.3 → 93.3.

Retail dialogue: 86.8 → 88.2.

AppWorld: improvements on both normal and challenge splits (exact numbers in paper tables).

Ablation: Provenance Links Matter

Removing the link to raw traces (short-sentence-only) drops the average by 3.2 points to 87.0. The regression rate (solvable tasks turned into failures) is 4.5% for WikiTrace, 6.5% for short sentences, and 9.7% for a no-memory rerun.

Drill-Down Behavior

Across the three text-world environments, agents drill down to raw traces in approximately 22% of episodes on simple tasks and 44% on hard tasks. The decision to drill is made autonomously by the agent.

Recovery vs. Regression Analysis

Measuring previously unsolved tasks that become solved (recovery) and previously solved tasks that become failures (regression), relative to a no-memory rerun:

WikiTrace recovers 35 percentage points more tasks.

Short sentences recover 27 pp more.

Prior rule-based methods recover only 7–14 pp more.

WikiTrace simultaneously achieves the highest recovery and the lowest regression.

References

Paper: https://arxiv.org/abs/2611.14320 Code:

https://github.com/yukyeongleee/wikitrace

Illustrative Diagrams

The paper includes three core diagrams:

Failure case comparison: same task solved without memory, failed with a wrong experience; drill-down path from experience → summary → raw trace.

Three-column architecture: compiler writing summary/experiences, memory files with backward links, new-task retrieval and drill-down flow.

Results table and recovery/regression scatter plot across all eight tasks.

}