When Does Memory Help Multi-Trajectory Inference for Tool-Use LLM Agents?
Xinzhe Li, Yaguang Tao · 2026
Read When Does Memory Help Multi-Trajectory Inference for Tool-Use LLM Agents? by Xinzhe Li, Yaguang Tao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-28224.txt.
Introduction
Xinzhe Li and Yaguang Tao ask when memory truly helps tool-using agents that try many reasoning paths. They test four memory methods under three search styles on four benchmarks. The search style confounds the verdict. Reflection counts only under one style, sibling injection helps only starved beam search, and fact extraction shortens runs with no accuracy change.
Catalog record
| CREATOR | Xinzhe Li, Yaguang Tao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78421 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.28224
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
When Does Memory Help Multi-Trajectory Inference for Tool-Use LLM Agents? Xinzhe Li, Yaguang Tao Abstract Multi-trajectory inference for tool-use LLM agents — generating multiple reasoning attempts and selecting among them — benefits from transferring knowledge across attempts so that later ones avoid the pitfalls of earlier ones. Existing cross-trajectory memory methods (trajectory-level reflection, atomic fact extraction, raw observation injection) are each evaluated under a single inference strategy on a single task, making it unclear whether reported gains reflect properties of the memory abstraction or of the inference method. We propose a unified framework that decomposes memory along two axes — the scope of transfer (within an expansion vs. across trajectories) and the abstraction of the transferred content — and evaluate four methods under three inference strategies (best-of- N N , beam search, MCTS) on four tool-use benchmarks spanning SQL, knowledge-graph, and CLI environments, in a verifier-free setting that matches the deployment regime of practical agents. The experiment matrix identifies the inference method as a confound: the same memory method produces statistically distinct results under different inference strategies on the same examples. Reflection reaches significance only under MCTS (not under best-of- N N ); within-expansion injection (conditioning each candidate on prior siblings’ outcomes) helps only diversity-starved beam search; and atomic fact extraction is accuracy-neutral but shortens trajectories by 19–26% on tasks with reusable environmental structure. 1 Introduction Multi-trajectory inference — generating many candidate reasoning paths and selecting among them ( 19 ; 8 ; 7 ) — consistently improves accuracy over single-trajectory agents on tool-use benchmarks. One way to further improve multi-trajectory inference is to explicitly transfer information across attempts (e.g., avoiding repeated mistakes, reusing discovered environmental knowledge, or diversifying exploration), so that later attempts are informed by earlier ones rather than sampling independently. Memory augmentation provides this information channel. Existing methods, however, span a heterogeneous design space: Reflexion-style trajectory-level summaries of failed attempts ( 18 ) , LATS-style reflections injected during tree search ( 25 ) , and Re-TRAC’s structured state combining evidence, plans, and failed-attempt records ( 27 ) . These methods vary in the abstraction at which transferred content is represented (strategy-level reflection vs. structured facts), but all operate at the same scope : transferring knowledge across complete trajectories. We identify scope as a second axis — within-expansion transfer (conditioning each sibling candidate on prior siblings’ outcomes) — and show that the combination of scope and abstraction interacts nontrivially with the inference strategy (best-of- N , beam search, MCTS) and with task properties (serializable vs. non-serializable environment, presence or absence of an inline verifier). We focus on tool-use agents: multi-step interactive reasoning where the agent issues structured calls (e.g., SQL queries, shell commands) to an external environment. This setting supports both memory abstractions (observational feedback for fact extraction; error signals for reflection) and exposes a structural constraint: when the environment is non-serializable ( 21 ) (state cannot be forked), beam search and MCTS are infeasible, leaving memory-augmented best-of- N as the only viable multi-trajectory strategy. We propose a unified framework that decomposes memory along the scope \times abstraction axes, derives four memory methods as concrete instantiations, and evaluates them in an experiment matrix ( 4 memory methods \times 3 inference strategies \times 4 benchmarks spanning 3 tool-use environments, minus structurally inadmissible combinations). Our setting is verifier-free : the task verifier is offline, applied at evaluation time only, matching the deployment regime of practical tool-use agents. This distinguishes our analysis from prior memory-augmented multi-trajectory work that relies on inline binary verifiers (exact match, unit-test pass) ( 18 ; 25 ) . Our contributions: • A unified scope \times abstraction framework for memory in tool-use tree search, from which existing methods and a new one (Raw Sibling) are derived as instantiations (§ 3 ). • A systematic empirical study under a verifier-free, deployment-faithful setup, covering memory \times inference \times task cells (§ 4 ). • Three findings on when memory helps: (F1) memory’s accuracy effect is search-method-dependent — Reflection reaches significance only under MCTS, while cross-sibling injection helps only diversity-starved beam search; (F2) under MCTS on the harder benchmark (KGQA), Reflection and Raw Sibling produce statistically indistinguishable accuracy despite operating on different memory abstractions; (F3) fact extraction is accuracy-neutral but improves efficiency on tasks with reusable environmental structure (§ 5 ). 2 Background and Related Work LLM tree search and multi-trajectory inference. Recent work applies search algorithms to LLM inference, generating multiple reasoning trajectories and selecting the best. Tree-of-Thoughts 19 uses BFS/DFS with LLM-generated evaluations. RAP 8 formulates reasoning as MCTS with an LLM world model. ReST-MCTS* 22 combines MCTS with process reward models for step-level guidance. Best-of- N sampling 7 generates best-of- N and selects via a verifier or reward model. 21 formalize non-serializable environments where state cannot be forked, showing that MCTS is infeasible in such settings and proposing trajectory selection as an alternative. Reflection and verbal memory in LLM agents. Reflexion 18 stores verbal reflections from failed trials in episodic memory to improve subsequent attempts. LATS 25 integrates reflection into MCTS, generating self-reflections after failed rollouts. Re-TRAC 27 compresses each trajectory into a structured state (evidence, uncertainties, plans) and conditions subsequent attempts on it — a unified representation combining our reflection and fact extraction abstractions. RoT 26 extracts guidelines from prior search trees to reduce repeated mistakes in future searches. ExpeL 24 accumulates cross-task insights from success and failure trajectories. R-MCTS 20 adds contrastive reflection to MCTS for web navigation agents. MC-DML 17 uses MCTS with a dynamic memory library that stores reflections as PUCT priors for text game agents. Atomic fact extraction. Fact-based memory has been explored in conversational and planning settings. mem0 ( 5 ) extracts and consolidates atomic facts from multi-session dialogues using vector-indexed storage and similarity-based retrieval. 9 apply atomic fact augmentation to lookahead search in environment-grounded planning (ALFWorld, TextFrozenLake), extracting task-critical facts from interaction trajectories. Our LiTS-Fact adapts the mem0 extraction pipeline to the multi-attempt tool-use search setting and provides the first controlled comparison against trajectory-level reflection. These works each propose a specific memory mechanism; none systematically compares different memory abstractions (raw observations vs. reflections vs. extracted facts) within the same experimental setup. Multi-agent memory sharing. Cross-agent memory collaboration has been explored via shared memory pools 6 , contrastive trajectory distillation across heterogeneous models 3 , swarm-inspired role specialization 11 , and off-trajectory reasoning where injected partial traces can act as distraction rather than guidance 10 . These approaches use model ensembles; our work studies the same exploration-exploitation tradeoff within a single agent across multiple attempts. Connection to reinforcement learning. Our framework can be viewed as an inference-time analogue of experience replay 13 : processed experience (reflections, extracted facts) is injected into the policy prompt rather than used for gradient updates. We discuss connections to in-context learning and hindsight experience replay in Appendix A . 3 A Unified Memory Framework We formalize context augmentation for LLM-based multi-trajectory reasoning. Let \pi_{\theta}(a\mid s) denote the base policy (an LLM generating candidate actions given state s ). A context augmentor modifies the policy by conditioning on additional context: \pi_{\theta}(a\mid s,\mathcal{C}),\quad\text{where}\quad\mathcal{C}=\bigcup_{k=1}^{K}f_{k}\!\bigl(\mathcal{H}_{k}\bigr). (1) Here f_{k} is the k -th augmentor’s analyze function, and \mathcal{H}_{k} is the history accessible to augmentor k . In practice, \mathcal{C} is concatenated