PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2606.06090v1cs.AI

TL;DR

Long-horizon agents need memory that preserves interdependent execution states, but similarity-based retrieval fragments decision trajectories and mixes valid with erroneous traces. MAGE manages memory as a hierarchical state tree with four coupled operations for compression, validation, and revision. On MemoryArena, it improves task success over baselines while reducing token consumption.

  • Problem

    Similarity-based RAG and agent memory do not preserve the decision chains or rollback boundaries required for coherent state reconstruction and error isolation in interdependent long-horizon tasks.

    Source: §1 · p. 1, §2.1 · p. 3

  • Method

    MAGE stores interaction history in a two-layer hierarchical state tree and maintains it through Grow, Compress, Maintain, and Revise operations.

    Source: §1 · p. 2, §3.1 · p. 4

  • Results

    MAGE improves average task success by 7.8–20.4 percentage points over baselines and reduces token consumption by 55.1% compared with the long-context approach.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Preserving execution-state structure supports more reliable and efficient memory for long-horizon LLM agents.

    Source: §5 · p. 9

Abstract

from arXiv · show

LLM-based agents increasingly tackle long-horizon tasks with interdependent decisions, where each action reshapes future constraints and intermediate errors can cascade. Existing RAG and agent memory systems organize histories by semantic similarity, retrieving content-relevant entries at decision time. We argue that this design mismatches execution-state dependencies: it fragments decision trajectories and mixes valid and erroneous traces, hindering coherent state reconstruction and error isolation. We propose MAGE (Memory as Agent-Guided Exploration), an active execution-state manager that stores interactions in a hierarchical state tree. The agent derives its state from the active root-to-current path, combining subgoal summaries, recent traces, and hints from prior branches. Four coupled operations maintain the tree: Grow records new traces, Compress summarizes completed subgoals, Maintain validates summaries, and Revise restores a target boundary and resumes on a new branch. This design bounds context growth while preserving state integrity and isolating flawed segments from the active path. Experiments on MemoryArena show that MAGE improves the average task success rate by 7.8--20.4 pp over baselines, while reducing token consumption by 55.1%.

1 Introduction

Long-horizon agents need coherent execution-state management because each decision depends on prior outcomes, while similarity-driven memory fragments trajectories and mixes valid with erroneous traces. MAGE organizes memory as a hierarchical execution-state tree and uses coupled operations to preserve active state, isolate errors, and improve efficiency.

Problem

  • Similarity-driven memory fragments dependent decision chains, preventing complete state reconstruction and producing actions based on incomplete information.These failures arise because entries are organized by semantic relationships rather than execution dependencies.Source: §1 · p. 2
  • Similarity-driven memory also mixes valid and erroneous trajectories, making errors difficult to trace or isolate and allowing them to propagate across subsequent decisions.MAGE instead separates flawed segments into inactive branches while preserving valid progress before the revision boundary.Source: §1 · p. 2

MAGE overview

  • MAGE stores interaction history in a two-layer tree whose active root-to-current path combines compressed state, recent traces, and hints from prior branches.Boundary-aware compression reduces context without interrupting active traces or breaking execution-state integrity.Source: §1 · p. 2

MAGE operations

  • Grow extends raw traces, Compress summarizes completed subgoals, Maintain validates summaries, and Revise restores a boundary before resuming on a new branch.Together, these operations make memory an agent-manipulable object rather than a shared pool of mixed entries.Source: §1 · p. 2

Main results

  • 7.8–20.4 percentage points higher task success and 55.1% lower token consumption than baselines and the long-context approach, respectively.MAGE’s root-to-current path and four operations support these gains on MemoryArena.Source: §1 · p. 2

2 Background and Related Work

Interdependent long-horizon tasks require memory that preserves decision chains and supports rollback, unlike recall benchmarks that mainly test retrieval of past facts. Existing RAG and agent-memory systems reduce context through similarity-based storage and retrieval but lack the path structure needed for coherent state reconstruction and error isolation.

2.1 Problem Setting

  • MemoryArena shopping cases show retrieval failures when systems miss prior product constraints or combine evidence from correct and incorrect trajectories.The resulting purchases violate constraints that MAGE preserves through execution-state continuity.Source: Figure 2 · p. 3
  • Long-horizon tasks require preserving the decision chain because each action determines later states, while recovery requires locating an erroneous action and re-executing from its origin.This setting differs from recall benchmarks because actions can invalidate future environment states.Source: §2.1 · pp. 2–3

2.2 Memory and Retrieval Systems for Agents

  • Existing RAG and agent-memory systems span flat, graph-based, hierarchical, hybrid, and reflective designs, but commonly organize memories through semantic similarity.Retrieved corpora are typically static or independent of the agent’s action-conditioned state.Source: §2.2 · pp. 3–4
  • Similarity-driven storage reduces context length but scatters the decision chain across fragments and leaves valid and erroneous trajectories without structural rollback boundaries.These shortcomings produce state fragmentation and insufficient error isolation in long-horizon tasks.Source: §2.2 · p. 4

3 Method

MAGE shifts agent memory from similarity-driven retrieval to active execution-state management through a hierarchical tree and four coupled operations. Its active path combines compressed subgoal summaries, recent traces, and execution hints while preserving revision boundaries and isolating erroneous branches.

3 Method

  • The method organizes execution history as an agent-manipulable state object rather than a passive pool of semantically retrieved entries.Its closed-loop cycle is designed to address state fragmentation and ineffective error isolation in interdependent long-horizon tasks.Source: §3 · p. 4, §3.1 · p. 4

3.1 Overview

  • MAGE derives the current execution state from one tree path, combining compressed summaries, recent raw traces, and hints from prior branches.This avoids reconstructing state from disconnected similarity-retrieved entries.Source: §3.1 · p. 4, §3.2 · p. 5

3.2 Hierarchical Execution State Tree

  • MAGE stores raw action-observation nodes in a bottom layer and completed subgoal summaries in a top layer, preserving dependencies while bounding context.The root-to-current path represents the execution trajectory, while top-layer nodes compress contiguous completed segments.Source: §3.1 · p. 4, §3.2 · p. 5, Figure 3 · p. 5

3.3 State-Transition Operations

  • Grow appends action-observation pairs to the raw trace, reusing an identical explored child when available and otherwise creating a new branch node.Execution hints expose prior continuations to help avoid repeating failed strategies.Source: §3.3 · pp. 5–6
  • Compress replaces completed raw segments with top-layer summaries at subgoal boundaries, freeing context without discarding dependencies needed for later recovery.It can be triggered by subgoal completion or when the raw state exceeds a length threshold.Source: §3.3 · p. 6
  • Maintain validates each new summary against the covered subtree and task instruction before allowing it into trusted memory.Failures record diagnostic feedback and identify a revision target when information is missing or dependencies are broken.Source: §3.3 · p. 6
  • Revise restores compressed and raw state to a target boundary, updates hints with diagnostics and alternatives, and resumes execution as a sibling branch.This isolates the affected segment while preserving valid progress on other branches.Source: Figure 3 · p. 5, §3.3 · p. 6

4 Experiments

Experiments evaluate MAGE across four MemoryArena domains, comparing its execution-state management with long-context, RAG, and memory baselines. MAGE improves task performance while reducing token use, and ablations show that compression, validation, and revision each support reliable execution.

4.1 Experimental Setup

  • MemoryArena tests action-conditioned tasks across Web Shopping, Travel Planning, Progressive Web Search, and Formal Reasoning with SR, PS, and token-consumption metrics.The benchmark requires tracking evolving execution state because actions reshape future constraints.Source: §4.1 · pp. 6–7

4.2 Main Results

  • 7.8 pp SR and 8.7 pp PS average gains over long context establish MAGE as the strongest overall approach on MemoryArena.MAGE models trajectories as active paths, reuses prior exploration, and quarantines flawed segments in inactive branches.Source: §4.2 · p. 8, Table 3 · p. 8

4.3 Token Efficiency

  • MAGE reduces token usage by 32.9–71.4% across domains, whereas baseline savings vary by environment and can reverse on Web Shopping.MAGE limits auxiliary model calls to Compress and Maintain at subgoal boundaries while maintaining the tree deterministically.Source: §4.3 · p. 8

4.4 Ablation Study

  • Removing Compress lowers SR by 7.3 pp and 6.7 pp while raising token use to 2.4× and 1.8×, showing that raw traces alone dilute active state.Removing Maintain lowers SR by 5.2–6.7 pp, while removing Revise lowers SR by 4.0–5.2 pp, demonstrating the roles of validation and branching recovery.Source: §4.4 · pp. 8–9

5 Conclusion

The conclusion presents MAGE as active execution-state management built around a hierarchical tree and four coupled operations. Across MemoryArena domains, this design improves task success while reducing token consumption, supporting execution-state structure as a principle for reliable and efficient agent memory.

5 Conclusion

  • MAGE preserves the active root-to-current path while compressing completed subgoals and exposing hints from previously explored branches.Its four operations extend traces, bound context growth, validate compressed states, and isolate errors through branching.Source: §5 · p. 9
  • Experiments show improved task success across diverse long-horizon domains alongside substantially lower token consumption.Source: §5 · p. 9
  • Preserving execution-state structure is proposed as a key principle for reliable and efficient memory systems for real-world LLM agents.Source: §5 · p. 9

A.1 Prompt Templates

The prompt templates specify task instructions, available actions, search or reasoning workflows, and completion constraints for the four MemoryArena domains. They require grounded interaction with tools, compact reasoning, and explicit use of Compress or Revise where applicable.

A.1 Prompt Templates

  • The templates define domain-specific action spaces and constraints for Bundled Web Shopping, Group Travel Planning, Progressive Web Search, and Formal Reasoning.Source: §A.1 · pp. 12–13
  • Web Shopping requires searching every option, checking compatibility and budget constraints, comparing candidates, and purchasing exactly one product per task.Source: §A.1 · p. 12
  • Group Travel Planning requires grounded selections from returned search ids, propagation of group dependencies, and completion of all itinerary slots.Source: §A.1 · pp. 12–13
  • Progressive Web Search requires corpus evidence for each sub-question, focused query variation, document reading, and compact one-action outputs.Source: §A.1 · p. 13
  • Formal Reasoning requires at least one reasoning step before completion and provides SymbolicReasoning, CodeExecutor, Compress, and Revise tools.Source: §A.1 · p. 13

A.2 Baseline Evaluation Protocol

Baseline evaluation follows MemoryArena’s protocol by initializing each method’s memory per task, writing completed-subtask traces into storage, and retrieving entries before each action.

A.2 Baseline Evaluation Protocol

  • Each RAG and memory baseline starts every task with empty storage and updates it using the full interaction trace after each subtask.Source: §A.2 · p. 13
  • Before each action, baselines query memory with the current subtask trace and append retrieved content to the agent context.Source: §A.2 · p. 13

A.3 Dataset Statistics

MemoryArena contains four domains with long interaction traces and many execution steps, making sustained state management essential for reliable performance.

A.3 Dataset Statistics

  • Table 5 reports the number of tasks, average trace length, and average execution steps for each of four MemoryArena domains.Trace length covers full-task actions and observations, while execution steps count agent-environment interactions.Source: §A.3 · p. 13, Table 5 · p. 13
  • Long-context rollouts show that MemoryArena tasks require agents to operate over long traces with many steps.Source: §A.3 · p. 14

B Results on Other Backend Models

MAGE generalizes across two additional backend models on the representative Bundled Web Shopping domain, improving success rates and reducing token use versus baselines.

B Results on Other Backend Models

C Bounded Context Growth

MAGE bounds context growth by compressing completed subgoals into boundary-aware summaries while retaining recent unfinished traces, unlike long-context accumulation.

C Bounded Context Growth

  • Compress chunks completed bottom-layer subgoal segments into compact top-layer summaries while retaining only the recent unfinished trace.Source: C Bounded Context Growth · p. 14
  • MAGE reduces token consumption while improving task performance relative to the long-context approach, indicating that compressed state preserves dependencies needed for downstream decisions.Source: C Bounded Context Growth · p. 14
  • MAGE bounds context growth through boundary-aware compression, whereas the long-context approach grows approximately linearly with execution steps.Source: Figure 4 · p. 14, C Bounded Context Growth · p. 14

D Case Studies

The case studies show that similarity-based retrieval can reconstruct the wrong active state, whereas MAGE follows the active execution path and selects purchases consistent with prior decisions.

Case Study A

  • The first case study contrasts stale frosting and non-final Mermaid memories with the correct AmeriColor Tulip Red purchase state.Source: D Case Studies · p. 15
  • In the Red-to-Gold example, MAGE’s final purchase is Gold Heart Sprinkles at $14.95 with rating 4.4.Source: D Case Studies · p. 15
  • MAGE preserves the active Red state and selects Gold Heart Sprinkles, while SimpleMem follows an incorrect Mermaid-to-Silver transition after retrieving fragmented memories.Source: D Case Studies · pp. 14–15

Case Study B

  • The second case study contrasts candidate seating memories with the final Blackjack Leather Loveseat purchase that determines the Leather-to-Leather transition.Source: D Case Studies · p. 15
  • In the Leather-to-Leather example, MAGE’s final purchase is a PU leather ottoman storage chest at $343.89.Source: D Case Studies · p. 16
  • MAGE preserves the active Leather state and purchases the correct PU leather ottoman, while Mem0 reconstructs Velvet from candidate memories and selects a grey velvet ottoman.Source: D Case Studies · pp. 15–16

Related papers

Loading 2606.06090v1…