Experience-Evolving Multi-Turn Tool-Use Agent with Hybrid Episodic-Procedural Memory

AI summary

Overview

Research area: LLM agent architectures — specifically multi-turn tool-use agents, memory systems, and reinforcement learning for long-horizon decision making.

Technical level: Intermediate. The paper assumes familiarity with LLM agents, tool calling, reinforcement learning basics (policy optimization, rollouts), and notions of episodic versus procedural memory.

Scope: The paper proposes and evaluates H-EPM, a hybrid memory framework that stores past tool-use experience in a state-annotated tool graph and uses it both to guide inference-time tool selection and to steer exploration during RL training.

What This Paper Is About

Multi-turn tool-use agents operate in settings where user intent unfolds over time and each tool call changes the environment, making early decisions error-prone. Reusing past experience is appealing but current approaches fail: whole-trajectory retrieval is too context-specific to transfer, while tool-only graphs ignore dialogue context and environment state. H-EPM addresses this by decomposing experience into episodic fragments (context-conditioned tool choices) and procedural routines (recurring tool-to-tool transitions), then adaptively reusing whichever is appropriate at each decision point.

Key Contributions

1. A hybrid episodic–procedural memory structure. Successful trajectories are consolidated into a state-annotated tool-transition graph where nodes are tools, edges carry procedural transition weights, and edges are additionally annotated with compact episodic state summaries capturing decision-relevant context.

2. An adaptive retrieval mechanism for inference. At each step, the agent decides whether to summarize the current state; if so, it retrieves the top-k most similar stored states from connected edges (episodic memory), otherwise it ranks candidates by edge weights (procedural memory). Both paths return two candidate tools rather than one, preserving flexibility.

3. A memory-guided RL paradigm. H-EPM is integrated into the rollout process of GRPO to bias exploration toward historically successful tool transitions, addressing ineffective exploration over long trajectories. A skip rate controls how often procedural suggestions are ignored, injecting stochasticity for exploration.

4. An efficiency-aware edge weighting scheme. Edge weights combine transition success counts with a per-trajectory efficiency term (inverse of rollout length), preventing the "tool overuse trap" where harmless but irrelevant tools accumulate high frequency.

Main Findings

• Consistent inference-time gains across benchmarks and backbone models. H-EPM improved performance on τ-Bench, τ²-Bench, and ToolSandbox for GPT-4.1-mini, GPT-4.1, GPT-4o, Qwen3-4B-Instruct, and Qwen3-8B, with relative improvements reaching over 50% on τ²-Bench (Qwen3-8B: 0.201 to 0.309, +53.7%).

• Weaker models benefit most. GPT-4.1-mini and Qwen3-4B-Instruct gained more than stronger models, suggesting the memory mechanism compensates for limited reasoning and instruction-following capability.

• Even a highly capable model improves. GPT-5.1 with H-EPM scored 0.921 versus 0.842 on τ²-Bench, 0.791 versus 0.739 on τ-Bench, and 0.670 versus 0.647 on ToolSandbox.

• Step-level methods beat trajectory-level retrieval. ToolNet (tool-graph navigation) outperformed ReasoningBank (whole-trajectory retrieval), because in multi-turn settings relevant information is revealed incrementally and coarse trajectory recall injects incomplete or misleading context early on.

• RL gains are substantial on out-of-distribution tasks. With GRPO plus H-EPM, τ²-Bench rose from 0.178 to 0.223 (+41.1% relative), τ-Bench from 0.510 to 0.558 (+28.3%), and ToolSandbox from 0.503 to 0.522 (+9.2%). H-EPM also beat AgentEvolver and standard GRPO.

• Supervised fine-tuning on H-EPM trajectories overfits. SFT on successful H-EPM rollouts degraded performance on τ-Bench (−14.3%), indicating that imitating trajectories is inferior to learning a policy with memory-guided exploration.

• Optimal skip rate depends on domain tool coupling. ToolSandbox, with strong sequential tool dependencies, performed best at a skip rate of 0.8; τ-Bench, with weaker coupling, at 0.9; and τ²-Bench, dominated by state-dependent error checking, at 1.0 (procedural suggestions fully skipped).

• Ablations confirm both memory types matter. Removing state summaries, removing edge weights, or removing adaptive switching all degraded performance. The efficiency term in the weight contributed additional gains beyond accuracy-only weighting, and top-2 candidate selection outperformed top-1 and top-3.

• Applying H-EPM to all rollouts beats applying it to half. Because suggestions are invoked on demand, unguided actions remain frequent, so full deployment preserves exploration while improving outcomes.

Methodology in Plain English

The researchers first collect successful tool-use trajectories by rolling out a base model with an autonomous summarization tool the agent can invoke whenever it judges summarization necessary. Each trajectory is compressed into a sequence of tool invocations plus occasional state summaries.

From these trajectories they build a directed graph. Nodes are tools (excluding the summarization tool). A directed edge is added whenever tool A is followed by tool B in a successful trajectory. Each edge receives a weight combining how often that transition appears in successful trajectories with how short those trajectories were — so efficient success is rewarded, not just frequent success. Weights are normalized per source tool so they reflect relative preference among next-tool options. When the summarization tool is invoked between two tool calls, the resulting state summary is attached to that edge as an episodic annotation; multiple summaries can accumulate on the same edge.

At inference, after each tool call, the agent locates the current tool node. It then decides whether to summarize the current state. If it does, it compares the new summary against stored summaries on outgoing edges and proposes the two most similar next tools. If it does not, it ranks outgoing edges by weight and proposes the top two. The agent sees both candidates as suggestions rather than forced choices.

For RL, the same graph guides exploration during GRPO rollouts. Procedural suggestions are activated only a fraction of the time controlled by a skip rate, keeping some actions unguided so the policy still explores. The memory graph is updated online as new successful trajectories appear, so the guidance improves alongside training. Training used 500 tasks from the τ-bench Retail set with Qwen3-4B-Instruct-2507 as the backbone in a multi-turn user-interactive setup built on VeRL.

Why This Matters

Impact on research. The paper reframes agent memory as a decomposition problem rather than a storage problem. Instead of asking how to retrieve whole past trajectories or how to navigate a tool graph in isolation, it shows that context-conditioned fragments and context-free tool routines serve different roles and should be selected adaptively. It also makes a case that memory belongs inside the RL loop, not just at inference, because the bottleneck in long-horizon agent RL is exploration, and past success can guide it.

Real-world applications:

• Customer service automation. Telecom and retail agents that handle multi-turn troubleshooting, returns, or plan changes where the correct tool depends on what the user has said so far.

• Enterprise workflow assistants. Agents that orchestrate CRM, ticketing, and database tools across many steps, where efficient tool sequencing matters as much as correctness.

• Software engineering and DevOps copilots. Agents that chain code search, test execution, and deployment tools, reusing known-good sequences while adapting to changed repository state.

• Scientific or data-analysis pipelines. Agents that invoke domain tools in recurring orders, benefiting from procedural routines while adapting to dataset-specific context.

Industry relevance. The approach requires no additional model training to deliver inference gains, works with both proprietary and open-weight backbones, and adds only negligible RL training overhead. Both properties lower the barrier to deployment. Its ability to generalize to unseen tasks and tools at inference, without collecting domain-specific experience, matters for products that must operate across heterogeneous customer environments.

Future Directions

• Automatic or learned skip rates. The optimal skip rate currently depends on manually matched domain tool coupling. A mechanism that infers the right degree of procedural guidance from observed tool-graph statistics or online performance would remove a tuning burden.

• Memory staleness and graph maintenance. As environments, tool schemas, and user behaviors drift, stored episodic summaries and edge weights may become misleading. Policies for pruning, decaying, or validating memories remain open.

• Scaling to much larger tool spaces and multi-agent settings. The current graph is built from per-task trajectories in bounded domains. How the framework behaves with thousands of tools, overlapping subgraphs, or multiple cooperating agents is untested.

• Learning when to summarize. The agent currently decides summarization timing heuristically. Treating summarization as a learned action with its own cost-benefit tradeoff could improve both efficiency and memory quality.

Target Audience

Researchers and engineers working on LLM agents, tool-augmented reasoning, and reinforcement learning for long-horizon decision making. It is also useful for practitioners building production multi-turn assistants who need a memory layer that improves tool selection without retraining the underlying model. Readers with a basic grasp of RL rollouts and tool-calling APIs will get the most out of it.

Authors’ abstract

As intents unfold and environments change, multi-turn agents face continuously shifting decision contexts. Although reusing past experience is intuitively appealing, existing approaches remain limited: full trajectories are often too context-specific to transfer, while tool-level reuse ignores the surrounding context and environment. In this paper, we introduce a hybrid episodic-procedural memory strategy (H-EPM) that enables experience-induced self-evolution of multi-turn tool-use policies by adaptively reusing partially overlapping successful experiences during both inference and training. Inspired by human episodic-procedural integration, we construct a tool graph from accumulated trajectories, where recurring tool-to-tool dependencies capture procedural routines and each edge is augmented with compact episodic summaries of relevant context. At inference time, the agent dynamically balances episodic recall for contextual reasoning with procedural execution for routine steps. Beyond inference, H-EPM introduces a memory-guided reinforcement learning paradigm that directly addresses a core challenge in multi-turn agent reinforcement learning, namely ineffective exploration over long trajectories. By biasing exploration toward historically successful tool transitions, H-EPM learns a stronger policy that generalizes at inference time without relying on domain-specific experience collection. Experiments show that H-EPM consistently delivers substantial inference-time gains over strong baselines across multi-turn tool-use benchmarks, reaching improvements of up to fifty percent. It also improves reinforcement learning policy performance, achieving gains of up to forty percent on out-of-distribution tasks.