Technical Summary: MESA – Task-Adaptive Multi-Structure Evidence Selection for Long-Horizon Agent Memory

1. Problem Formulation

Long-horizon agents accumulate trajectories comprising hundreds of interleaved reasoning, action, observation, and tool-output steps. Answering a query often requires retrieving evidence buried deep within this history. While external memory systems transform these histories into structured representations (e.g., summaries, graphs, vector stores), existing approaches face a fundamental dilemma:

• Fixed All-Structure Fusion: Systems that query a static, exhaustive set of memory views for every query maximize recall but inflate context windows with redundant or distracting noise, increasing cost without guaranteeing performance.
• Single-Structure Routing: Systems that route each query to a single "best" structure limit expressiveness, preventing the composition of complementary evidence (e.g., combining high-level summaries with exact episodic steps) required for complex tasks.

The authors argue that the optimal memory configuration is neither a single structure nor the full union, but a tailored composition of multiple structural memories that varies dynamically with the specific query and task demands. However, learning such a selection policy is challenging due to the combinatorial nature of structure subsets and the lack of ground-truth labels for per-structure utility (weak supervision), where feedback is only available at the final answer level.

2. Methodology: The MESA Framework

The paper proposes MESA (Multi-structure Evidence Selection for long-horizon Agent), a framework that learns a query-adaptive policy to select and fuse a subset of specialized memory structures.

2.1 Multi-View Structural Memory Construction

MESA maintains five independent, complementary memory structures for each trajectory $\tau_i$, constructed offline:

1. Summary (S): A compressed state memory preserving salient state changes and sub-goal transitions.
2. Temporal Store (T): A turn-indexed store preserving the exact chronological sequence of actions and observations.
3. Knowledge Graph (G): A relational graph capturing entity connections and causal links across steps.
4. Vector Database (V): A dense, step-level index for semantic similarity retrieval.
5. Raw Episodic (R): Uncompressed, overlapping windows of the original trajectory for exact surface-form evidence.

2.2 Structure-Level Dynamic Selection

For a given query $q_i$ and context $c_i$, a selector $S_\rho$ outputs a non-empty binary vector $z_i \in \{0,1\}^5$, indicating which structures to access. The retrieved evidence from selected structures is composed and fed to a frozen answer model $F$ to generate an answer. The goal is to learn the policy $\rho$ that maximizes answer accuracy while minimizing evidence token cost.

2.3 Prior-Guided Harness Optimization

To learn $\rho$ under weak supervision (sparse answer-level feedback), MESA employs a Prior-Guided Harness Optimization strategy:

• Restricted Search Space: Instead of searching the entire space of possible policies, the optimization is constrained to a set of prior directions ($A$). These directions define mechanism classes for routing, such as inferring demand from query type, estimating backend value, or controlling subset construction (e.g., cardinality-first, complementarity selection).
• UCB-Guided Scheduling: The system balances exploration and exploitation using an Upper Confidence Bound (UCB) scheduler. Each prior direction acts as a "bandit arm." The scheduler selects directions that have historically produced strong policies (exploitation) or those that have been evaluated less frequently (exploration).
• Iterative Refinement: An LLM proposer generates executable policy candidates based on the selected direction and current error analysis. These candidates are fitted on training traces, evaluated on a validation set, and the best policy is selected based on a regularized objective: $J_{val}(\rho) - \lambda C_{val}(\rho)$, where $C$ is the token cost.

3. Key Contributions

1. Problem Formulation & Empirical Analysis: The authors formalize "structure-level dynamic selection" and demonstrate through a controlled sweep of all non-empty structure subsets on AMA-Bench that:
   • Intermediate subsets (combinations of 2–4 structures) typically outperform single structures or the full union.
   • No single fixed composition is universally optimal; the best subset varies by domain and capability.
2. The MESA Framework: A novel framework that learns a query-adaptive selection policy from sparse answer-level feedback using prior-guided harness optimization and UCB scheduling, without modifying the underlying memory builders or the answer model.
3. Empirical Validation: Extensive experiments showing MESA's superiority over state-of-the-art baselines in both long-horizon agent tasks and conversational memory.

4. Experimental Results

Experiments were conducted on AMA-Bench (2,496 questions across 6 agentic domains) and LoCoMo (long-term conversational memory).

• Performance on AMA-Bench: Using a Qwen3-32B backbone, MESA achieved 65.1% overall accuracy, outperforming the strongest baseline (AMA-Agent) by 8.5% and the long-context reader by 12.5%. MESA was the top performer in three of the four memory capability categories: Recall (69.2%), State Updating (65.8%), and State Abstraction (57.8%). In the Causal Inference category, MESA achieved 63.6%, ranking second behind AMA-Agent (65.0%).
• Efficiency: MESA achieved these gains while using 41% fewer evidence tokens (11.0k vs. 18.7k) compared to the "all-structure" alternative, demonstrating that adaptive selection reduces noise and cost.
• Generalization: On LoCoMo, MESA achieved an F1 score of 49.0%, outperforming the specialized baseline by 1.8%, proving the framework extends beyond agent trajectories to conversational memory.
• Ablation Studies:
  • Removing the learning component (using random or zero-shot selection) resulted in significant accuracy drops.
  • Restricting selection to a single structure ("Route-to-one") reduced accuracy to 57.0%, confirming the necessity of composing complementary structures.
  • Removing prior guidance or UCB scheduling degraded performance and stability, highlighting the importance of structured search and exploration balance.

5. Significance and Claims

The paper claims that MESA addresses a critical gap in agent memory systems: the inability to dynamically adapt memory access strategies to specific query needs. By demonstrating that intermediate, task-adaptive subsets are superior to fixed strategies, the work shifts the paradigm from "more memory is better" to "the right memory composition is better."

The authors emphasize that MESA achieves these results by learning a selection policy that is explicit and interpretable (e.g., keyword-based routing rules learned during optimization), rather than a black-box neural selector. The framework offers a practical trade-off, improving both accuracy and efficiency without requiring retraining of the underlying large language models or memory construction pipelines. The paper concludes that future work should explore jointly optimizing memory construction and selection, as well as modeling cross-structure dependencies more explicitly.