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

MemGPT pages information in and out of working context; Generative Agents and Reflexion use reflection; HippoRAG2 and Hindsight exploit graph, vector, or multi-network memory. Agent trajectories, however, interleave reasoning, actions, observations, and tools with temporal and causal dependencies. Summaries preserve global context but lose steps; vector retrieval may find semantically similar but irrelevant fragments; graphs lack step ordering; raw traces preserve detail but create noise.

Given trajectory τ, query q, and observable context c, the system must select a non-empty subset of five structures rather than always reading all or routing to one. The action space has 2^5−1=31 choices. Complementary views improve coverage, whereas redundant or mismatched views increase distraction and token cost. No gold subset or per-structure utility label exists, so learning must rely on sparse end-to-end answer feedback.

MESA contributes four ideas: a formal structure-level selection problem; preservation of heterogeneous representations and dedicated access mechanisms; answer-level optimization of an executable selector; and a cost-regularized objective J−λC. Prior directions bias the search toward meaningful routing mechanisms, while UCB scheduling allocates trials between exploitation and exploration. This differs from fixed fusion, single-source routing, and selection inside one unified schema.

• �� Build: apply builders Bk to τi, producing Summary, Temporal, Graph, Vector, and Raw memories.
• �� Select: compute z=Sρ(qi,ci), where z∈{0,1}5 and ||z||0≥1.
• �� Retrieve: invoke Γk only for selected structures and compose Ei(z).
• �� Answer: use frozen F to produce ŷ=F(q,E).
• �� Optimize: initialize with ρall; an LLM proposer generates exploitation, exploration, and failure-repair candidates, fits them on training traces, and scores validation.
• �� Schedule: use UCB(a)=Ĵval(a)+β√[log(N+2)/(na+1)]; return the archive policy maximizing validation accuracy minus λ times token cost.

AMA-Bench contains 208 real-world episodes and 2,496 questions across Web, Open-World QA, Text2SQL, Software, Gaming, and Embodied AI, plus four memory capabilities. LoCoMo contributes 1,540 non-adversarial questions. Baselines include Long-context, BM25, Qwen3-Emb-4B, MemGPT, HippoRAG2, Mem0, MemoRAG, A-Mem, EMem, Hindsight, and AMA-Agent. AMA uses LLM-judged accuracy; LoCoMo uses F1. AMA splits episodes 2:2:6, repeats five times, and runs 30 optimization iterations.

With Qwen3-32B, MESA scores 65.1%, compared with AMA-Agent's 56.6% and long-context's 52.6%. It leads on Recall (69.2%), State Updating (65.8%), and State Abstraction (57.8%), while Causal Inference reaches 63.6% versus AMA-Agent's 65.0%. With Gemma-4-31B, MESA reaches 69.4% versus 63.0%. Domain gains over the strongest baseline include 15.5 points in Software and 8.9 in Text2SQL. LoCoMo F1 is 49.0, above MemGPT's 46.8 and EMem's 47.2.

The method suits debugging agents, Text2SQL systems, web automation, tool-using question answering, and embodied agents. Before deployment, teams must build the five indexes, expose stable retrieval interfaces, and optimize the selector on representative trajectories. The immediate benefit is lower context length, latency, and inference cost, while reducing irrelevant evidence that can mislead the answer model.

The approach assumes that five useful structures and their access mechanisms are known in advance; it cannot automatically invent new views. LLM proposal and UCB search require repeated validation and GPU resources. Causal Inference still trails AMA-Agent, suggesting that selection alone does not guarantee long causal-chain reconstruction. The paper gives limited analysis of latency, construction cost, λ/β sensitivity, privacy, and memory contamination. Online learning, attribution, adaptive budgets, and broader environments are natural next steps.