🤖 AI

Beyond Semantic Organization: Memory as Execution State Management for Long-Horizon Agents

The paper introduces MAGE, a novel memory architecture that replaces semantic similarity-based retrieval with a hierarchical state tree to manage execution states, thereby improving long-horizon agent performance by isolating errors, bounding context growth, and significantly boosting task success rates while reducing token consumption.

Original authors: Yaoqi Chen, Haibin Lai, Yuru Feng, Chuyu Han, Qianxi Zhang, Baotong Lu, Menghao Li, Xinjiang Wang, Zhirui Wang, Shusen Xu, Zengzhong Li, Zewen Jin, Hao Wu, Cheng Li, Qi Chen

Published 2026-06-05

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yaoqi Chen, Haibin Lai, Yuru Feng, Chuyu Han, Qianxi Zhang, Baotong Lu, Menghao Li, Xinjiang Wang, Zhirui Wang, Shusen Xu, Zengzhong Li, Zewen Jin, Hao Wu, Cheng Li, Qi Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, 100-step puzzle where every move you make changes the rules for the next move. If you make a mistake early on, it can ruin the rest of the puzzle. This is what "long-horizon agents" (AI assistants) face when doing complex tasks like planning a trip or shopping for a bundle of compatible items.

The paper argues that current AI memory systems are like bad librarians, and the authors propose a new system called MAGE that acts more like a smart project manager.

Here is the breakdown using simple analogies:

The Problem: The "Keyword Librarian"

Most current AI memory systems work like a librarian who only remembers things based on keywords.

How it works: If you ask, "What did I buy?" the librarian looks for words like "buy," "red," or "shoes."
The Flaw: This is like trying to rebuild a story by grabbing random pages from a book that happen to contain the word "red." You might get a page about a red car from Chapter 1 and a red shirt from Chapter 50, but you miss the sequence of events.
The Result: The AI gets confused. It might mix up a correct path with a wrong one, or forget that a specific decision depended on a previous step. It's like trying to drive a car while only looking at scattered road signs rather than the actual road ahead.

The Solution: MAGE (The "Project Manager")

The authors propose MAGE (Memory as Agent-Guided Exploration). Instead of a library, MAGE treats memory like a growing family tree or a choose-your-own-adventure book.

Instead of just storing facts, MAGE stores the state of the journey. It organizes the AI's history into a two-layer tree:

The Bottom Layer (The Raw Footsteps): This records every single step the AI took, like a detailed diary of "I walked here, then I saw this."
The Top Layer (The Summaries): When the AI finishes a small goal (a "subgoal"), MAGE summarizes those steps into a single, neat note. This keeps the "diary" from getting too long and messy.

How MAGE Works: The Four Moves

MAGE manages this tree with four specific actions, similar to how a human manages a complex project:

Grow (Keep Walking): As the AI takes a new step, MAGE adds it to the bottom of the tree. If the AI tries a path it already explored, it just moves to that existing branch instead of starting a new one.
Compress (Summarize): When a mini-goal is done, MAGE takes all those messy steps and turns them into one clean summary. This saves space (like compressing a video file) without losing the important plot points.
Maintain (The Quality Check): Before the AI accepts a summary as "truth," MAGE double-checks it. Did we actually finish the goal? Is the summary accurate? If not, it flags an error immediately.
Revise (The "Undo" Button): This is the superpower. If the AI makes a mistake, MAGE doesn't just delete the whole memory. It branches off. It cuts the tree at the point where the mistake happened, keeps the good parts before the error, and starts a new branch to try again. This isolates the mistake so it doesn't poison the rest of the journey.

Why It Matters: The Results

The authors tested this on a benchmark called MemoryArena, which simulates complex tasks like shopping for items that must match each other or planning travel for a group.

Better Success: MAGE solved tasks 7.8% to 20.4% more often than other systems. It didn't get lost in its own history.
Cheaper to Run: Because MAGE summarizes old steps and only keeps the relevant "current path" in its active memory, it used 55% fewer computer tokens (the "fuel" AI needs to think) compared to systems that try to remember everything at once.

The Takeaway

The paper claims that for AI to handle long, complex tasks, it shouldn't just be a "search engine" for past facts. It needs to be an execution manager that understands the flow of its own actions. By organizing memory as a tree of states rather than a pile of similar facts, MAGE keeps the AI on the right track, catches errors early, and saves money by not wasting energy on irrelevant history.

Technical Summary: Beyond Semantic Organization: Memory as Execution State Management for Long-Horizon Agents

1. Problem Statement

The paper addresses the challenge of managing memory for Large Language Model (LLM) agents tackling long-horizon tasks with interdependent decisions. In these scenarios, such as multi-step web shopping or complex planning, each action reshapes future constraints, and intermediate errors can cascade to invalidate subsequent progress.

The authors argue that existing memory systems (including RAG and various agent memory architectures) suffer from a fundamental design mismatch:

Semantic vs. State Dependency: Current systems organize history based on semantic similarity (content relevance to the current query) rather than execution-state dependencies (the causal chain of decisions).
State Fragmentation: By retrieving semantically similar but structurally disconnected entries, these systems fragment the decision trajectory. Critical context binding steps together is often discarded, preventing the reconstruction of a coherent execution state.
Error Contamination: Similarity-based retrieval mixes valid and erroneous traces from different exploration attempts. Without explicit path structures, errors cannot be isolated, leading to their propagation and accumulation.
Inefficiency: Paradoxically, many memory systems consume more tokens than simply retaining the full history (long-context approach) while still underperforming in task success rates.

2. Methodology: MAGE

The authors propose MAGE (Memory as Agent-Guided Exploration), a framework that reframes memory from a passive semantic archive to an active execution-state manager. MAGE is inspired by cognitive mechanisms in human complex task execution, specifically hierarchical chunking, error monitoring, and selective correction.

Core Architecture: Hierarchical Execution State Tree

MAGE organizes the agent's history as a two-layer hierarchical state tree:

Bottom Layer (Raw Trace): Records step-by-step action-observation pairs ( $a_t, o_t$ ) in execution order. This preserves fine-grained state dependencies.
Top Layer (Compressed Subgoals): Stores summary nodes generated at subgoal or decision boundaries. These compress contiguous bottom-layer segments into compact states.

The agent's current execution state is derived strictly from the active root-to-current path of this tree, rather than assembling disconnected entries via retrieval. This path combines:

Compressed State ( $C$ ): Summaries of completed subgoals.
Raw State ( $R$ ): Recent, uncompressed action-observation traces.
Execution Hints ( $H$ ): Information from sibling branches (failed alternatives) and diagnostic notes to guide future decisions.

Four Coupled Operations

MAGE maintains this tree through a closed-loop cycle of four operations:

Grow: Appends new action-observation pairs to the bottom layer. If a node with identical content exists (from a prior exploration), the pointer merges to it; otherwise, a new node is created. This extends the raw trace and updates execution hints.
Compress: Triggered when a subgoal is complete or the raw trace exceeds a threshold. It replaces a completed bottom-layer segment with a top-layer summary node. This bounds context growth while preserving the decision boundary needed for future recovery.
Maintain: A validation step performed immediately after compression. An LLM verifies the summary and its underlying trace against the task instructions. If errors or missing information are detected, it records diagnostic feedback and signals a failure.
Revise: Triggered by a validation failure or proactive error detection. It restores the active pointers ( $p_b, p_t$ ) to a target boundary (the state before the error), discards the erroneous segment, and resumes execution as a new branch (sibling path). This isolates the error from the active path while preserving valid progress.

3. Key Contributions

Paradigm Shift: The proposal of MAGE, which shifts agentic memory from similarity-driven retrieval to compact execution-state management via a two-layer hierarchical tree.
Closed-Loop State Management: The design of four coupled operations (Grow, Compress, Maintain, Revise) that treat memory as an agent-manipulable object. This cycle isolates errors into separate branches, ensuring the active execution state remains free of erroneous traces.
Empirical Validation: Demonstration on the MemoryArena benchmark that MAGE achieves superior task performance with significantly lower token consumption compared to both long-context baselines and existing memory/RAG systems.

4. Experimental Results

Experiments were conducted on MemoryArena, a benchmark featuring interdependent long-horizon tasks across four domains: Bundled Web Shopping, Group Travel Planning, Progressive Web Search, and Formal Reasoning.

Task Success Rate (SR): MAGE improved the average task success rate by 7.8–20.4 percentage points over baselines (including long-context, HippoRAG2, MemoRAG, Mem0, etc.).
Token Efficiency: MAGE reduced token consumption by 55.1% on average compared to the long-context approach. Unlike other memory systems that often incur overhead from extraction and query rewriting, MAGE's deterministic tree maintenance and boundary-aware compression minimize auxiliary LLM calls.
Ablation Studies: Removing any of the three core mechanisms (Compress, Maintain, or Revise) resulted in significant performance drops, confirming that the full closed-loop cycle is necessary for reliable state management.
Generalization: Results held across different backend models (Qwen3.6-27B, Qwen3.6-35B, and Gemma4-31B), indicating the approach is not tied to a specific model architecture.

5. Significance and Claims

The paper claims that the key to reliable and efficient long-horizon agents lies in preserving execution-state structure rather than optimizing for semantic retrieval.

State Integrity: By constructing the current state from a single active path in a hierarchical tree, MAGE prevents the fragmentation that plagues similarity-based systems.
Error Isolation: The tree structure allows for explicit branching and revision, enabling the agent to quarantine flawed segments without discarding valid historical progress.
Efficiency: The boundary-aware compression strategy bounds context growth without breaking state dependencies, achieving a "sweet spot" of high task success and low token cost (the "upper-left" region in performance-efficiency plots).

The authors conclude that treating memory as an active execution-state manager is a fundamental principle for building robust LLM agents capable of handling complex, real-world tasks where decisions are interdependent and errors are costly.