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

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

Abstract Summary:

Long-horizon agents accumulate trajectories spanning hundreds of interleaved reasoning, action, and observation steps, where answering a query may depend on evidence buried far back in the history. External memory stores such trajectories as structured representations, yet each structure provides a distinct and incomplete view. Existing multi-memory systems either read a fixed set of structures for every query, inflating context and introducing noise, or route each query to a single structure, preventing the composition of complementary evidence. A controlled analysis on AMA-Bench shows that the optimal memory configuration is typically neither a single structure nor the full union, but a tailored composition of multiple structural memories that varies with query and task demands. Motivated by these findings, the paper formulates structure-level dynamic selection: selecting and fusing a query-adaptive subset from a library of specialized memory structures. The paper proposes MESA (a Multi-structure Evidence Selection framework for long-horizon Agent), which builds five complementary structure views of each trajectory and learns from end-to-end answer-level feedback to select and fuse a query-specific subset for a frozen answer model. To learn under this weak supervision, MESA employs harness optimization with prior-guided search and UCB-guided scheduling to balance exploration and exploitation. On AMA-Bench, MESA outperforms the strongest baseline by 8.5% while using 41% fewer evidence tokens than the all-structure alternative.

Introduction Summary:

Long-horizon agents accumulate trajectories that span hundreds of steps, where a later decision can depend on evidence produced much earlier. Unlike documents or dialogues, these trajectories interleave reasoning, actions, observations, and tool outputs, and they carry temporal and causal dependencies. Feeding the full trajectory to a long-context LLM is expensive and still does not reliably surface buried evidence, even with million-token windows. Truncation and compression cut costs but can drop details that matter later. External memory addresses this problem by transforming the history into persistent representations and retrieving a compact body of evidence for each query. Accordingly, the central question is how execution histories should be organized and dynamically consulted.

Existing agent-memory systems rely on distinct structural abstractions to manage execution histories, yet each abstraction exhibits inherent limitations when handling the heterogeneity of long-horizon agent applications. Text summaries capture high-level context but lack deterministic execution details; temporal stores preserve chronological order but may struggle when queries lack explicit temporal anchors in the query; vector databases surface semantically near fragments that can be task-irrelevant while discarding temporal-causal order; knowledge graphs facilitate entity traversal but lack step-level indexing; and raw episodic traces retain exact action steps but bury critical clues under heavy noise.

To bridge individual limitations, recent hybrid memory systems combine these structures, but their access strategies remain mismatched with query-specific demands. At one extreme, eager all-in fusion methods uniformly query a static, exhaustive set of memory views for every query. While maximizing recall, this indiscriminately bloats context windows and introduces distracting noise from unneeded structural memories. At the other extreme, single-structure routing methods select a single best-suited structure per query. However, this strictly limits expressiveness when a query demands composing complementary evidence across representations. Consequently, no existing approach dynamically selects and composes a query-adaptive subset from a library of specialized memory structures.

The paper defines a memory structure as a unified pair comprising a structural representation and its dedicated access interface. Guided by agent memory taxonomies, the paper instantiates five representative structures: text summaries, temporal stores, knowledge graphs, vector databases, and raw episodic traces. A controlled study sweeping over all non-empty structure subsets across diverse long-horizon tasks reveals two key findings: (1) Intermediate subsets are usually preferable: across most evaluated categories, the best-performing composition is neither a single structure nor the full union, but a subset of complementary structures; and (2) No fixed composition is universally optimal over tasks: the winning subset varies across domains and memory capabilities, rather than following a single global preference. These findings motivate a new problem formulation: structure-level dynamic selection, learning an executable policy to dynamically select and fuse query-dependent structural memories.

Realizing an effective structure-level selection policy entails two fundamental challenges. First, selecting dynamic memory subsets is inherently a combinatorial utility and redundancy dilemma. Complementary views can improve evidence coverage, whereas redundant or mismatched views introduce distracting context and additional cost. The selector must therefore balance evidence recall, utility and context budget. Second, policy learning faces credit assignment under weak supervision. Ground-truth subsets and per-structure utility labels are unavailable. The policy must instead be learned from sparse, end-to-end answer feedback, making individual selection decisions difficult to evaluate.

To tackle these challenges, the paper proposes MESA (Multi-structure Evidence Selection for long-horizon Agent). MESA maintains the five independent memory structures: text summary, temporal store, knowledge graph, vector database, and raw episodic trace. Each with its own builder and retrieval interface. For each query, its selector dynamically choose query-dependent memory structures. Evidence from the selected structures are composed for a frozen answer-generating LLM. To optimize the selection policy under the weak supervision, MESA restricts candidate selection to prior directions and balances the exploration-exploitation.

Contributions:

(1) Problem formulation and empirical analysis: The paper formulates structure-level dynamic selection for agent memory and shows through an exhaustive subset sweep that intermediate subsets typically outperform the single-structure and all-structure alternatives, while the best composition varies across task categories.

(2) The MESA framework: The paper introduces a multi-structure memory framework that learns query-adaptive structure selection policy from sparse answer-level feedback through prior-guided harness optimization.

(3) Empirical results: MESA outperforms the strongest baseline by 8.5% on AMA-Bench. Results on LoCoMo extend the framework to conversational memory. Extensive ablations further validate the effectiveness of the learned task-adaptive selection.

Related Work Summary:

Equipping LLM agents with memory beyond a fixed context window has been approached from several angles. MemGPT manages the working context itself, paging information in and out like an operating system. A reflection-based line distills raw interaction into reusable knowledge: Generative Agents' retrieve–reflect memory and Reflexion's verbal self-feedback across trials, while embodied agents such as Voyager accumulate a growing library of skills mined from long trajectories. A parallel line builds long-term memory for cross-session dialogue and multi-hop QA, and several of these systems already maintain more than one index over the same history, pairing a graph store with dense or timestamped retrieval. Even where multiple indices coexist, however, each system reads them through a fixed interface; how an agent should select among heterogeneous evidence forms per query, as long-horizon multi-task settings demand, is left unaddressed.

A growing body of work organizes agent memory into explicit structures, but differs from MESA along three axes: how memory is organized (by semantic role or a single unified schema versus by access pattern), how it is read (a fixed policy or a single structure versus a query-specific complementary subset), and what the read returns (broad or single-source evidence versus a fused subset of heterogeneous structures). One line reads its structures through a fixed policy: Hindsight partitions memory into four networks (world facts, experiences, opinions, and observations) but answers every query with the same four-way parallel retrieval fused by reciprocal rank fusion, and SEEM combines a graph layer and an episodic layer through a deterministic pipeline; the read never adapts to what a query needs. A second line makes selection adaptive but returns a single winner: StructRAG reconstructs documents into the single best-fit format per query, Learning-to-Route dispatches each query to one external source, and FluxMem learns a context-aware selector that assigns each memory unit one structure among linear, graph, and hierarchical forms, supervised offline on conversational data. A third line, closest to MESA, also selects compact evidence: S3Mem writes heterogeneous histories into a single unified scene–event schema and routes a small evidence pack to the reader, but its selection operates within one representation rather than across structures with distinct access patterns. MESA differs on all three axes: it keeps heterogeneous structures distinguished, reads a query-specific complementary subset rather than one structure or the full union, and refines the selection policy through answer-level optimization.

Analysis of Memory Structure Selection Summary:

A long interaction history admits several forms of storage and access. The paper uses memory structure to denote a memory representation together with its access mechanism, which jointly determine what information is retained and what evidence can be retrieved. Given a history τi, the paper constructs K memory structures: Mi = Mi(k) = Bk(τi) k=1 K, where Bk is the builder for structure k, and Γk is its fixed access mechanism. The paper instantiates K = 5 representative structures widely used in agent-memory systems: a compressed summary, a temporal key–value store, a relational graph, a dense vector index, and sparse retrieval over raw episodic traces.

Reading memory requires choosing which structures to access. A selection is represented as a non-empty binary vector z ∈ 0, 1 K, where z(k) = 1 indicates that structure k is selected. The action space is Z = z ∈ 0, 1 K ∥z∥0 ≥ 1, which contains 2 5 − 1 = 31 non-empty compositions for K = 5.

The paper evaluates all non-empty subsets of the five memory structures on AMA-Bench. This controlled sweep reveals two observations:

• Intermediate subsets are usually preferable: Across the domains and QA capabilities, most categories are best served by subsets containing multiple structures, indicating that they benefit from complementary evidence. However, adding every available structure is generally unnecessary and can introduce redundant or distracting context. The appropriate selection granularity therefore lies between route-to-one and read-all.

• No fixed composition is universally optimal over tasks: A composition performing well for one domain or QA type may be suboptimal for another. No single fixed subset consistently provides the most useful evidence across tasks. The selected subset should therefore adapt to the current query rather than remain fixed.

Together, these findings motivate a selector Sρ(qi, ci) that predicts a non-empty subset zi ∈ Z from the query and its observable context. The selector should exploit complementary structures when needed while avoiding the redundant evidence cost of the full composition.

Task-Adaptive Memory Structure Selection Summary:

MESA learns an executable policy that selects a query-specific subset of five complementary memory structures, while keeping all other components fixed.

Problem Formulation: Given the memory structures Mi = Mi(k) k=1 K constructed from history τi, the structure selector takes a query qi and a compact description ci of its interaction context and outputs a non-empty selection: zi = Sρ(qi, ci), zi ∈ Z, where ρ is an executable selection policy and Z is the action space. The context ci may contain task, domain, and QA-type information, but excludes the gold answer, evaluation score, and other outcome-revealing variables. MESA invokes the access mechanisms selected by zi and composes their retrieved evidence: Ei(zi) = Compose Γk(qi, Mi(k)) zi(k) = 1. A frozen answer model F then performs inference over the selected evidence: ŷi(zi) = F(qi, Ei(zi)), and the resulting utility is ri(zi) = Eval(ŷi(zi), yi). The dataset is split into training, validation and test sets Dtr, Dval and Dtest. For a split D, the evaluation score of policy ρ is JD(ρ) = (1/D) Σi∈D ri(Sρ(qi, ci)). Let CD(ρ) denote the mean number of evidence tokens retrieved from the selected structures. Candidate policies are compared using the regularized validation objective Jeval(ρ) = Jval(ρ) − λCval(ρ), where λ controls the trade-off between answer accuracy and evidence cost.

Prior-Guided Harness Optimization: Feedback-driven optimizers can search over textual prompts or complete executable harnesses, but such broad spaces are poorly directed under the coarse, answer-level feedback available here. Since MESA keeps the builders, retrievers, composer, and answer model fixed, the paper restricts optimization to a small set of prior directions A = a1,..., aA. The search archive is initialized with the all-structure policy ρall. An LLM proposer then generates executable selection policies under a prior direction of reflecting the selection mechanisms. These mechanisms capture how a policy infers query demand, estimates structure utility, constructs a subset, and balances robustness against evidence cost.

MESA balances exploration and exploitation using an Upper Confidence Bound (UCB)-guided scheduling. Each prior direction a ∈ A defines a way to generate or modify a selection policy and serves as one UCB arm. Let na be the number of candidate policies evaluated under direction a. The paper computes UCB(a) = Jeval(a) + β√(log(N + 2)/(na + 1)), where na is the number of evaluated candidates generated under direction a, N = Σa na, and Jeval(a) is their mean validation objective. The first term favors directions that have previously produced strong policies, whereas the second encourages directions that have been evaluated less frequently. At each iteration, the LLM proposer receives the policy archive, the UCB statistics of all directions, and the recurring errors of the current policy. It then generates three executable candidates: an exploitation candidate based on a previously effective direction, an exploration candidate based on an under-explored direction, and a failure-repair candidate targeting a recurring error. Each candidate is evaluated on the validation set, and its result updates the corresponding direction's Jeval(a) and na. After the search budget is exhausted, MESA returns the policy with the highest objective score on the validation set in the archive. After optimization, the selected policy ρ* is frozen and tested on the held-out test set.

Experiment Summary:

Datasets: AMA-Bench contains long agent–environment trajectories in which later questions require evidence produced during earlier reasoning, actions, observations, or tool calls. The paper uses its real-world subset, consisting of 208 episodes with 12 expert-curated question–answer pairs per episode, for a total of 2,496 questions. The episodes cover six agentic domains: web task execution, open-world tool question answering, text-to-SQL, software engineering, gaming, and embodied AI. The questions additionally span four memory capabilities: recall, causal inference, state updating, and state abstraction. The paper further evaluates on LoCoMo to test whether the same framework extends beyond agent trajectories to long-term conversational memory. LoCoMo contains 10 mu…

Based on the paper, here are the specific improvements I can make to AI systems:

• What I can do: Instead of always reading all memory structures or picking one, I can learn to select a query-specific subset of complementary memory structures (e.g., summaries, knowledge graphs, vector stores, temporal logs, raw traces) on-the-fly.

• Improved capability: When answering a question like What was the exact command executed after the user's last database error?, I can automatically choose the raw episodic trace + temporal store, avoiding noise from irrelevant structures like the knowledge graph. This reduces context bloat by 41% while improving accuracy.

• What I can do: I can optimize my selection policy using only end-to-end answer correctness as feedback, without needing ground-truth labels for which memory structure was useful.

• Improved capability: I can learn to route queries to the right memory combination through iterative self-improvement, guided by structured prior directions (e.g., infer query demand, estimate structure utility) and UCB-based exploration/exploitation to balance trying new strategies vs. refining known-good ones. This makes me robust across domains without manual tuning.

• What I can do: I can fuse evidence from heterogeneous memory structures (e.g., combining a knowledge graph for entity relationships with a temporal store for event ordering) into a single, coherent context for the answer model.

• Improved capability: For a software engineering question like Which commit introduced the bug that caused the test failure at step 42?, I can compose the knowledge graph (file dependencies) + raw trace (exact commit actions) to produce a precise answer, rather than relying on a single structure that misses either the dependency or the action detail.

• What I can do: I can explicitly trade off answer accuracy against evidence token cost during policy learning, using a regularized objective (accuracy − λ × cost).

• Improved capability: I can automatically decide when to read 2 structures vs. 4 based on query complexity—e.g., simple recall questions read only the summary (5.7k tokens), while complex causal inference questions read 3–4 structures (11k tokens)—keeping my context window efficient without sacrificing correctness.

• What I can do: I can learn explicit, human-readable routing rules (e.g., if query contains 'after' and 'error', use temporal + raw trace) rather than opaque neural selectors.

• Improved capability: Users can inspect and debug why I chose certain memory structures for a query, making my behavior transparent and trustworthy in high-stakes applications like autonomous coding or embodied agents.

• What I can do: I can adapt my memory selection strategy across diverse domains (web tasks, text-to-SQL, software engineering, gaming, embodied AI) and even extend to conversational memory (LoCoMo), without retraining the underlying memory builders or answer model.

• Improved capability: I can be deployed as a drop-in memory layer for any long-horizon agent, automatically learning which structures matter for each new task type—e.g., prioritizing knowledge graphs for entity-heavy QA and raw traces for step-level debugging—with only answer-level feedback.

• What I can do: I can explicitly generate repair candidates targeting recurring errors from my current policy (e.g., if I keep missing temporal evidence, I generate a policy variant that always includes the temporal store for time-anchored queries).

• Improved capability: I can systematically fix systematic weaknesses in my memory access, leading to steady accuracy gains (e.g., +8.5% over the strongest baseline on AMA-Bench) rather than plateauing.

The improved AI system can:

• Answer long-horizon questions (spanning hundreds of reasoning/action steps) with higher accuracy (65.1% vs. 56.6% for best prior system) while using 41% fewer evidence tokens than reading everything.

• Automatically discover which memory structures to combine per query—e.g., for causal inference, it learns to fuse summaries + temporal stores; for state abstraction, it uses knowledge graphs + summaries—without manual feature engineering.

• Self-optimize from sparse, end-to-end feedback (just correct/incorrect on answers), making it applicable to any agent task where ground-truth memory labels are unavailable.

• Extend beyond agents to conversational memory, improving multi-session dialogue QA by 1.8% F1 over specialized baselines.

• Remain interpretable, allowing developers to audit and refine the learned selection rules for safety-critical deployments.

Long-horizon agents accumulate trajectories spanning hundreds of interleaved reasoning, action, and observation steps, where answering a query may depend on evidence buried far back in the history. External memory stores such trajectories as structured representations, yet each structure provides a distinct and incomplete view. Existing multi-memory systems either read a fixed set of structures for every query, inflating context and introducing noise, or route each query to a single structure, preventing the composition of complementary evidence. A controlled analysis on AMA-Bench shows that the optimal memory configuration is typically neither a single structure nor the full union, but a tailored composition of multiple structural memories that varies with query and task demands. Motivated by these findings, we formulate structure-level dynamic selection: selecting and fusing a query-adaptive subset from a library of specialized memory structures. We propose MESA (a Multi-structure Evidence Selection framework for long-horizon Agent), which builds five complementary structure views of each trajectory and learns from end-to-end answer-level feedback to select and fuse a query-specific subset for a frozen answer model. To learn under this weak supervision, MESA employs harness optimization with prior-guided search and UCB-guided scheduling to balance exploration and exploitation. On AMA-Bench, MESA outperforms the strongest baseline by 8.5% while using 41% fewer evidence tokens than the all-structure alternative.