🤖 AI

When Does Memory Help Multi-Trajectory Inference for Tool-Use LLM Agents?

This paper introduces a unified framework to evaluate multi-trajectory inference for tool-use LLM agents, revealing that the effectiveness of memory methods is heavily dependent on the inference strategy used, with specific techniques like reflection, within-expansion injection, and atomic fact extraction yielding distinct benefits only under MCTS, beam search, and tasks with reusable structure, respectively.

Original authors: Xinzhe Li, Yaguang Tao

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xinzhe Li, Yaguang Tao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a very tricky puzzle, like finding a specific file on a computer or writing a complex database query. You have a super-smart assistant (an AI) who can try to solve it, but sometimes it gets stuck or makes mistakes.

The paper asks a simple question: If we let the AI try the puzzle multiple times, how should we help it remember what happened in the previous tries so it doesn't make the same mistakes again?

The researchers set up a "memory system" for the AI and tested it in different ways. They found that there is no single "best" way to give the AI a memory. Instead, the best method depends entirely on how the AI is trying to solve the puzzle.

Here is the breakdown of their findings using everyday analogies:

1. The Two Ways to Give the AI a Memory

The researchers identified two main ways to help the AI remember:

The "Diary" (Reflection): After the AI fails, a second, smarter AI reads the whole story of what went wrong and writes a summary note.
- Analogy: It's like a coach watching a soccer player miss a goal, then writing a note saying, "You kicked too hard; aim lower next time."
The "Fact Sheet" (Atomic Facts): Instead of a story, the AI just pulls out specific, tiny facts from the environment.
- Analogy: It's like a cheat sheet that says, "The file is in the 'Documents' folder," or "The database has a table called 'Users'." It doesn't give advice; it just gives raw data.

2. The Three Ways the AI Tries to Solve the Puzzle

The researchers tested these memories against three different "search strategies" the AI uses to find the answer:

The "Rollercoaster" (Best-of-N): The AI tries to solve the puzzle 5 times from scratch, side-by-side, and picks the best result at the end. It doesn't talk to itself between tries.
The "Tree Climber" (Beam Search): The AI branches out like a tree. At every step, it keeps the top 3 most promising paths and drops the rest.
The "Explorer" (MCTS): The AI explores many paths deeply, simulating the future to see which path looks best, then backtracks to try the most promising one again.

3. The Big Discovery: "One Size Does Not Fit All"

The paper's main conclusion is that the memory method only works if it matches the search strategy. If you mix them up, the memory might actually make things worse or do nothing.

The "Diary" (Reflection) only works for the "Explorer" (MCTS).
- Why? The Explorer is constantly checking its progress. If the "Diary" says, "Don't go down that path," the Explorer listens and cuts that branch off immediately.
- The Rollercoaster (Best-of-N) doesn't listen. It just runs all 5 tries to the end, even if the "Diary" says they are doomed. The memory is ignored until it's too late.
The "Raw Sibling" trick only works for the "Tree Climber" (Beam Search).
- What is this? This is a new method where the AI's different branches talk to each other while they are growing. If Branch A tries a move and fails, Branch B sees that immediately and tries something different.
- Why? The Tree Climber often gets "stuck" where all its branches try the exact same wrong move. This trick forces them to be different. The "Explorer" (MCTS) is already good at being different, so this trick doesn't help it.
The "Fact Sheet" (Atomic Facts) is a speed booster, not a magic fix.
- The Result: Giving the AI a list of facts didn't make it more correct (accuracy stayed the same).
- The Benefit: It made the AI much faster. Because the AI already knew "The file is in the Documents folder," it didn't waste time looking for it again. It skipped the boring discovery steps.
- The Catch: This only works if the puzzle environment is stable (like a database). If the environment changes every time (like a fresh computer terminal), the facts are useless because they don't apply to the new situation.

4. The "Confusing" Finding

On one specific, very hard puzzle (Knowledge Graph QA), the researchers found that the "Diary" and the "Raw Sibling" methods performed exactly the same.

The Lesson: This is a warning to other scientists. If you only test one method on one type of puzzle, you might think your method is the "winner." But this paper shows that the "winner" changes depending on how you play the game. You can't compare results from different studies unless they use the same search strategy.

Summary

Think of the AI as a student taking a test.

If the student is guessing wildly (Best-of-N), giving them a summary of past mistakes (Reflection) doesn't help because they don't stop to read it.
If the student is stuck in a loop (Beam Search), telling them "Hey, your brother just tried that and failed" (Raw Sibling) helps them break the loop.
If the student is exploring deeply (MCTS), a coach's summary (Reflection) helps them prune bad paths.
If the student just needs to stop wasting time looking for things they already know, a cheat sheet of facts (Fact Extraction) speeds them up, even if it doesn't make them smarter.

The Bottom Line: You cannot just add "memory" to an AI and expect it to work. You have to match the type of memory to the type of thinking the AI is doing.

Technical Summary: When Does Memory Help Multi-Trajectory Inference for Tool-Use LLM Agents?

1. Problem Statement

Multi-trajectory inference—generating multiple reasoning paths and selecting among them—has been shown to improve accuracy for tool-use Large Language Model (LLM) agents compared to single-trajectory approaches. A promising avenue for further improvement is cross-trajectory memory, where information from failed or partial attempts is transferred to subsequent attempts to avoid repeated mistakes or reuse discovered environmental knowledge.

However, existing research on cross-trajectory memory suffers from a lack of systematic comparison. Current methods (e.g., Reflexion-style trajectory reflection, LATS-style tree search reflections, Re-TRAC's structured state) operate under different inference strategies (best-of-N, beam search, MCTS) and on different tasks. This heterogeneity makes it unclear whether reported performance gains stem from the specific memory abstraction (e.g., raw observations vs. strategic summaries vs. atomic facts) or the inference method itself. Furthermore, many prior works rely on inline binary verifiers (e.g., exact match, unit tests) during the search process, which does not reflect the deployment regime of practical tool-use agents where verification is often offline.

2. Methodology

2.1 A Unified Framework

The authors propose a unified framework that decomposes memory along two orthogonal axes:

Scope of Transfer:
- Cross-sibling (Within-expansion): Conditioning each candidate action on the outcomes of previously sampled siblings within the same expansion step. This requires interleaved expansion and is applicable only to beam search and MCTS.
- Cross-trajectory (Within-search): Transferring knowledge across complete, sequential attempts (iterations) of the same search. This applies to all inference methods, including best-of-N.
Abstraction Level:
- Raw: Injecting verbatim action-observation pairs without summarization.
- Reflection: Generating a natural-language, strategy-level summary of a failed trajectory (e.g., "The C compilation failed; try Python").
- Atomic Fact Extraction: Extracting discrete, reusable factual statements from observations (e.g., "Config file is at /etc/app/config.yaml").

2.2 Experimental Design

The study evaluates four concrete memory methods derived from the framework:

No Memory (Baseline): Standard multi-trajectory inference without context augmentation.
Raw Sibling (Novel): Cross-sibling scope with raw abstraction.
Reflection: Cross-trajectory scope with reflection abstraction (adapted from Reflexion/LATS).
LiTS-Fact (Novel): Cross-trajectory scope with atomic fact extraction (adapted from mem0).

These methods are evaluated across three inference strategies:

Best-of-N: Sequential generation of $N$ trajectories.
Beam Search: Maintaining top- $B$ candidates at each step.
MCTS (Monte Carlo Tree Search): UCT-based selection, expansion, simulation, and backpropagation.

The evaluation spans four tool-use benchmarks:

WikiSQL & WikiTQ: SQL agents querying relational databases (serializable environments).
KGQA: Knowledge Graph agents traversing Freebase via SPARQL (serializable).
Terminal-Bench 2.0: CLI agents executing shell commands (non-serializable; state cannot be forked, restricting viable strategies to Best-of-N).

Crucial Constraint: The experiments are conducted in a verifier-free setting. The task verifier is applied only at evaluation time, not during the search loop. This matches the deployment regime of practical agents and removes the confound of inline binary signals (e.g., unit tests) that might artificially boost performance in prior works.

3. Key Contributions

Unified Taxonomy: A formal scope $\times$ abstraction framework for memory in tool-use tree search, deriving existing methods and a new "Raw Sibling" method as specific instantiations.
Systematic Empirical Study: A controlled experiment matrix (4 memory methods $\times$ 3 inference strategies $\times$ 4 benchmarks) under a verifier-free, deployment-faithful setup.
Identification of Confounds: The study identifies the inference method as a critical confound. The same memory method produces statistically distinct results under different inference strategies on the same examples.

4. Key Results and Findings

The analysis yields three primary findings regarding when memory aids multi-trajectory inference:

F1: Memory's Accuracy Effect is Search-Method Dependent

Memory does not universally improve accuracy; its efficacy depends heavily on the inference strategy.

Reflection: Reaches statistical significance only under MCTS, not under Best-of-N.
- Mechanism: MCTS utilizes a per-step reward model (PRM) that filters out bad expansions suggested by reflections before they reach a terminal state. In Best-of-N (pass@N), bad reflections run to completion, often resulting in regressions that cancel out gains.
Raw Sibling: Helps only diversity-starved Beam Search.
- Mechanism: In beam search with standard sampling, sibling candidates often converge to identical actions or apologies (diversity collapse). Raw Sibling's interleaved expansion conditions each candidate on prior siblings' outcomes, forcing diversity. This effect disappears in MCTS, where UCT-driven re-expansion already supplies sufficient action variation.

F2: Convergence of Memory Abstractions on Hard Tasks

On the harder benchmark (KGQA) under MCTS, Reflection and Raw Sibling produce statistically indistinguishable accuracy results (34.8% for both), despite operating on different abstractions (strategy-level vs. raw data) and scopes (cross-trajectory vs. cross-sibling).

Implication: On difficult tasks where the policy is far from the solution, any non-i.i.d. context may suffice for recovery, making the specific abstraction choice less critical. This suggests that single-abstraction evaluations in prior literature may have attributed gains to the wrong cause.

F3: Fact Extraction Trades Accuracy for Efficiency

LiTS-Fact (atomic fact extraction) is accuracy-neutral across all evaluated cells (no statistically significant gain or loss). However, it significantly improves efficiency:

It shortens trajectory lengths by 19–26% on tasks with reusable environmental structure (WikiSQL, WikiTQ, KGQA).
Mechanism: Extracted facts (e.g., database schemas, relation types) allow subsequent attempts to skip redundant discovery steps (e.g., sql_db_list_tables).
Limitation: This efficiency gain does not transfer to non-serializable environments (Terminal-Bench) where each task instance has a unique environment, rendering cached facts non-reusable.
Interaction: Combining Reflection and Fact extraction is detrimental. The explicit step-by-step plan generated by Reflection overrides the implicit shortcuts offered by Fact memory, causing the agent to re-perform discovery steps and reducing both accuracy and efficiency.

5. Significance and Claims

The paper claims that previous literature on cross-trajectory memory effectiveness is not directly comparable across studies because each evaluates under a different inference method, which acts as a confound. By controlling for this variable, the authors demonstrate that:

Reflection is not a universal fix; it requires the pruning capabilities of MCTS to be effective.
Cross-sibling injection is a remedy for specific diversity failures in beam search, not a general enhancement.
Fact extraction is primarily an efficiency tool for structured environments, not an accuracy booster.

The authors conclude that claims about memory effectiveness must be contextualized by the inference strategy and task properties (serializability, presence of reusable structure). The study provides a controlled matrix to disentangle these factors, suggesting that future work must explicitly account for the interaction between memory abstractions and search algorithms rather than treating them as independent variables.

Limitations: The study evaluates a single policy model per benchmark (Haiku 3.5 for SQL, Sonnet 4.6 for KGQA) and does not investigate cross-task memory (knowledge transfer across different questions). The sample sizes are sufficient to detect effects of $\gtrsim 6$ percentage points but may miss smaller effects.