Microsoft's MAGE Beats Every AI Agent Memory System by 20 Points
MAGE replaces semantic retrieval with a hierarchical execution-state tree, boosting agent task success by up to 20.4 pp while cutting token use by 55%
Takeaways
- Core claim: Semantic similarity-based memory (RAG, vector stores) actively harms long-horizon agents by fragmenting execution state and mixing correct/erroneous traces.
- MAGE replaces retrieval with a two-layer hierarchical execution-state tree; the agent always reads from the active root-to-current path, not from retrieved snippets.
- Four operations keep the tree healthy: Grow (record), Compress (summarize subgoals), Maintain (validate before committing), and Revise (branch away from errors).
- Results on MemoryArena: +7.8 to +20.4 pp task success rate over all baselines, 55.1% fewer tokens than long-context; gains hold across Qwen and Gemma backends.
- Best for: tasks with dense causal dependencies (web shopping, travel planning, progressive research); less differentiated on sparse-dependency tasks like formal math.
- No public code released yet; paper is from Microsoft, USTC, Nanjing University, and UC San Diego.
For all the progress in LLM-based agents, there is a quiet failure mode that rarely gets discussed: the memory system. When an agent is navigating a hundred-step task, buying a bundle of products where each purchase constrains the next, or planning a multi-person trip with cascading dependencies, the standard approach is to retrieve the most semantically similar past entries and inject them into context. A new paper from researchers at Microsoft, USTC, Nanjing University, and UC San Diego argues this is fundamentally the wrong abstraction, and proposes a replacement called MAGE (Memory as Agent-Guided Exploration).
The retrieval trap
Most agent memory systems, whether flat vector stores, entity-relation graphs, or hierarchical architectures, share the same core loop: store past interactions as entries, then retrieve the most relevant ones by embedding similarity when the agent needs to make a decision. This works well for question answering over static facts. It breaks down badly for long-horizon tasks where decisions are causally chained.
Existing RAG and agent memory systems organize histories by semantic similarity, retrieving content-relevant entries at decision time. The authors argue this design mismatches execution-state dependencies: it fragments decision trajectories and mixes valid and erroneous traces, hindering coherent state reconstruction and error isolation.
The paper identifies two concrete failure modes. The first is state fragmentation: because memory entries are linked by topical similarity rather than causal order, the agent may reconstruct an incoherent picture of what it has actually done. The second is error contamination: when a previous attempt went wrong, its traces sit in the same memory pool as correct ones, and similarity-based retrieval can surface the bad traces alongside the good, poisoning the current decision.

The case studies in the paper make this concrete. In a bundled shopping task where each purchase must be compatible with prior ones, each purchase must satisfy constraints induced by previously bought products. HippoRAG retrieves only Product 2 information, while MemoryOS retrieves Product 4 exploration traces but not the final purchased item; both miss that Product 4 contains gold and choose an incompatible unicorn-themed option. MAGE, reading from its execution-state tree, picks the correct wedding-themed option.
A tree, not a pool
MAGE reframes memory as an