PaperlayerView exact revision on arXiv

Source-linked AI summary

SEARL: Joint Optimization of Policy and Tool Graph Memory for Self-Evolving Agents

Xinshun Feng, Xinhao Song, Lijun Li, Gongshen Liu, Jing Shao

arXiv:2604.07791v3cs.AIcs.LG

TL;DR

Direct prompting and static tool sets remain limited for complex, long-horizon tasks, while agentic reinforcement learning also faces sparse feedback and underused external memory. SEARL jointly evolves policy and structured tool memory, and experiments report gains in multi-hop reasoning and competitive mathematical-task performance.

  • Problem

    Direct prompting remains insufficient for complex, long-horizon tasks, while existing approaches can overlook tool dependencies, step-level feedback, or external-memory growth.

    Source: §1 · pp. 1–2

  • Method

    SEARL jointly optimizes policy and dynamic Tool Graph memory, using tool-memory-aware policy optimization to navigate and leverage the growing graph.

    Source: §1 · p. 2

  • Results

    Experiments report substantial improvements in multi-hop reasoning and competitive performance in mathematical tasks, with small LLMs gaining robust self-evolving capabilities.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The authors conclude that agents can build and refine Tool Memory over time, moving toward autonomous, open-ended generalist capabilities.

    Source: §6 · p. 9

    A performance gap remains on GSM8K and MATH500, and the learned toolset may limit adaptation to direct search or specialized domains.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Recent advances in Reinforcement Learning with Verifiable Rewards (RLVR) have demonstrated significant potential in single-turn reasoning tasks. With the paradigm shift toward self-evolving agentic learning, models are increasingly expected to learn from trajectories by synthesizing tools or accumulating explicit experiences. However, prevailing methods typically rely on large-scale LLMs or multi-agent frameworks, which hinder their deployment in resource-constrained environments. The inherent sparsity of outcome-based rewards also poses a substantial challenge, as agents typically receive feedback only upon completion of tasks. To address these limitations, we introduce a Tool-Memory based self-evolving agentic framework SEARL. Unlike approaches that directly utilize interaction experiences, our method constructs a structured experience memory that integrates planning with execution. This provides a novel state abstraction that facilitates generalization across analogous contexts, such as tool reuse. Consequently, agents extract explicit knowledge from historical data while leveraging inter-trajectory correlations to densify reward signals. We evaluate our framework on knowledge reasoning and mathematics tasks, demonstrating its effectiveness in achieving more practical and efficient learning.

1 Introduction

SEARL addresses the difficulty of complex, long-horizon tasks by jointly evolving an agent’s policy and structured tool memory. Its Tool Graph records tool dependencies, while memory-aware training assigns finer-grained credit; experiments report robust self-evolving capabilities for small LLMs.

1 Introduction

  • Direct prompting remains insufficient for complex, long-horizon tasks, and fixed tool lists may limit adaptability and generalization across diverse tasks.Source: §1 · p. 1
  • Prior tool-generation methods store tools without structure, while experience-driven approaches often overlook dependencies needed for complex reasoning.The paper proposes a Tool Graph with tools as nodes and execution dependencies as edges.Source: §1 · p. 1
  • SEARL jointly evolves the agent’s policy and tool-based memory, rather than optimizing either component in isolation.Its dynamic graph supports continuous tool creation and reuse, while policy optimization uses trajectory- and step-level credit.Source: §1 · p. 2
  • Tool-Memory-Aware training extends step-level advantages with memory-anchored clustering to assign fine-grained credit for tool creation and execution.Source: §1 · p. 2
  • The Tool Graph formalizes tool knowledge and inter-tool dependencies; its growth is reported to improve generalization and planning in complex tasks.Source: §1 · p. 2
  • Experiments report that SEARL empowers small LLMs with robust self-evolving capabilities driven by an expanding tool memory.Source: §1 · p. 2

2 Preliminary

The preliminary section defines self-evolving agents and formalizes an MDP augmented with graph-structured tool memory. It describes the agent’s reward-maximizing objective and a trajectory process that retrieves, reuses, and creates tools before transitioning to a new state.

2 Preliminary

  • A self-evolving agent improves problem-solving through experience, using tool-based evolution, memory-based evolution, or both to adapt to novel states.The definition describes generalization without manual retraining as an ideal.Source: §2 · p. 2
  • The Tool Memory-Enhanced MDP is a tuple of state space, action space, transition dynamics, reward function, and graph memory.Its graph nodes store interaction tuples, and its edges encode trajectory-derived correlations.Source: §2 · p. 2
  • The agent follows an LLM-based policy conditioned on state, task, and tool memory, with training maximizing expected reward while regularizing deviation from a reference policy.Source: §2 · p. 2
  • A trajectory proceeds through tool retrieval, a decision to reuse the retrieved tool, possible tool creation, and a state transition.The retrieved tool is selected from the graph memory for the current state.Source: §2 · p. 2

3 Self-Evolving Agent Reinforcement Learning

SEARL structures agent decisions as explicit planning, retrieval, reasoning, and action steps, and combines task-completion rewards with process feedback. It uses episode- and tool-anchored advantages for credit assignment and maintains a graph memory of tools and their dependencies.

3.1 Structured Trajectory Generation

  • Tasks are represented as structured meta-reasoning sequences: a global plan precedes tool retrieval, internal deliberation, and an answer or tool-call action.MCP tool creation is treated as a regular tool call.Source: §3.1 · p. 3

3.2 Reward Shaping

  • Training combines a binary terminal reward for task completion with dense step-level rewards for planning, tool creation, tool execution, and output format.The terminal reward is 1 for a correct completed task and 0 otherwise.Source: §3.2 · p. 3

3.3 Advantage Estimation with Tool-Memory-Aware Policy Optimization

  • Tool-based anchors address the difficulty of matching identical states in vast, continuous environments, where state-based step-level grouping is impractical.The section also notes that basic step-level rewards can be vulnerable to reward hacking and may not reliably correlate with reasoning quality.Source: §3.3 · pp. 3–4
  • Tool-anchored step advantages group actions across trajectories by MCP tool, complementing episode-level advantages with fine-grained credit for tool-related decisions.Grouping actions by memory anchor abstracts the state space into a finite set defined by the toolset, while episode-level advantages provide a trajectory-wide signal.Source: §3.3 · pp. 4–5

3.4 Tool-Based Memory

  • The Tool-Based Memory is a directed graph of registered MCP tools and step-level dependencies, updated through subgraph extraction, registration, retrieval, and memory consolidation.Consolidation merges tools whose embedding similarity meets a threshold and incorporates precedence edges, redirecting incident edges when tools are merged.Source: §3.4 · pp. 5–6

4 Experiment

SEARL is evaluated on long-horizon mathematical and knowledge-intensive reasoning tasks against trajectory-level RL baselines. Its reported results, ablations, and tool-graph analyses examine performance as well as how the method learns and reuses tools.

4.1 Datasets

  • The evaluation covers mathematical reasoning and knowledge-intensive reasoning, including multi-hop Wikipedia QA tasks.The named mathematical benchmarks are AIME2024, MATH500, and GSM8K; QA datasets include HotpotQA, 2WikiMultihopQA, Musique, and Bamboogle.Source: §4.1 · p. 6

4.2 Baselines

  • SEARL is compared with TIR Prompting, GRPO, DAPO, REINFORCE++, and ARPO; GiGPO is excluded as incompatible with the task settings.Source: §4.2 · p. 6

4.3 Training Settings

  • Training uses 10,000 Tool-star samples and equips the agent with a Python interpreter and a local Wikipedia search interface.Source: §4.3 · p. 6

4.4 Evaluation Metrics

  • All benchmarks use Qwen3-32B as an LLM judge for binary correctness, with results reported as pass@1 accuracy.Predictions are post-processed by extracting answers from the designated tags and boxed content.Source: §4.4 · p. 6

4.5 Main Results

  • SEARL outperforms policy-gradient methods on knowledge-intensive reasoning and shows stronger generalization on complex mathematical problems across the reported benchmark comparison.Source: §4.5 · p. 6, Table 1 · p. 7

4.6 Ablation Study and Analysis

  • SEARL maintains higher training rewards and entropy than GRPO, while removing Step-level Grouping degrades performance most and removing Step Rewards also causes a drop.Rewards remain predominantly negative because strict penalties deter redundant tool calls and failed creation attempts.Source: Figure 3 · p. 7, §4.6 · p. 7, Figure 4 · p. 7

4.7 Implementation of the Tool Graph

  • For geometric-sequence optimization, modular tools organize constraints into a dependency graph and filter invalid candidates earlier than monolithic O(n^2) brute force.The figure contrasts the modular tool chain with a monolithic baseline that times out under brute-force search.Source: §4.7 · pp. 7–8, Figure 5 · p. 8

4.8 Evolving Dynamics of Tool Graph

  • Across four snapshots, initially disjoint tool subgraphs connect through reuse and merging, growing in complexity and integrating cross-domain experience.Source: Figure 6 · p. 8, §4.8 · p. 8

5 Related Work

Prior work explores self-evolution through parameter updates, memory expansion, and tool creation or reuse, while agentic RL develops trajectory feedback and planning. The paper positions SEARL as coupling policy optimization with persistent structured memory.

  • Self-evolving-agent research spans parameter updates, long-term memory expansion, and autonomous tool creation or reuse, but most approaches treat tool evolution and policy learning independently.Source: §5 · pp. 8–9
  • Agentic RL has advanced from trajectory-level feedback toward group-based advantage estimation, structured rewards, longer horizons, and hierarchical planning.Source: §5 · p. 9
  • SEARL addresses the stated gap by coupling policy optimization with a growing Tool Graph Memory that accumulates durable capabilities.Source: §5 · p. 9

6 Conclusion

The conclusion presents SEARL as a self-evolving-agent framework combining autonomous tool creation with fine-grained credit assignment. It attributes generalization to a Tool Graph Memory that records tools, dependencies, and usage contexts alongside anchor-based advantage estimation and process rewards.

  • The Tool Graph Memory stores executable tools and captures their causal dependencies and usage contexts.Source: §6 · p. 9
  • Coupled with anchor-based advantage estimation and process rewards, the memory is reported to support efficient generalization of learned skills to novel tasks.Source: §6 · p. 9
  • The authors report that joint optimization of policy and memory yields significant gains and frame iterative tool-memory refinement as a step toward open-ended generalist agents.Source: §6 · p. 9

Limitations

SEARL has remaining limitations in mathematical performance, adaptability, tool reuse, and reward alignment. These constrain its performance on some tasks and the portability of its generated tools.

Limitations

  • A performance gap remains on GSM8K and MATH500, and tool-generation overhead for simple problems may hinder basic reasoning.The authors identify this as a possible explanation for the gap.Source: Limitations · p. 9
  • The training-developed toolset may limit adaptation to contexts such as direct search or highly specialized domains.Source: Limitations · p. 9
  • Many generated tools are trivial and too simplistic for effective reuse by other LLMs, given the model scale.Source: Limitations · p. 9
  • The reward function may still incentivize superficial reward hacking, motivating further alignment with task correctness and reasoning depth.Source: Limitations · p. 9

A.1 Mathematical Reasoning Benchmarks

The mathematical benchmarks span grade-school multi-step word problems, a 500-problem subset covering varied mathematical fields, and 30 challenging AIME problems.

A.1 Mathematical Reasoning Benchmarks

  • AIME24 comprises 30 challenging problems spanning domains including algebra and geometry.Source: §A.1 · p. 12
  • MATH500 is a curated subset of 500 MATH problems covering algebra, geometry, calculus, and number theory, from high-school to collegiate difficulty.Source: §A.1 · p. 12
  • GSM8K contains grade-school math word problems typically requiring 2 to 8 reasoning steps involving basic arithmetic.Source: §A.1 · p. 12

A.2 Knowledge-Intensive reasoning benchmarks

The section describes knowledge-intensive benchmarks for multi-hop reasoning and summarizes four reinforcement-learning baselines used for comparison.

A.2 Knowledge-Intensive reasoning benchmarks

  • HotPotQA (Yang et al., 2018) evaluates multi-hop question answering using Wikipedia-sourced information across supporting documents.Source: §A.2 · p. 12
  • 2WikiMultihopQA (Ho et al., 2020) requires evidence integration across disjoint Wikipedia articles; MuSiQue discourages shortcuts and demands semantic and logical synthesis.Source: §A.2 · p. 12
  • Bamboogle (Press et al., 2022) uses “Google-proof” questions requiring information combined across distinct sources rather than direct search lookup.Source: §A.2 · p. 12

B Baseline Descriptions

C Implementation Details

Implementation uses Qwen3-4B with a Python sandbox and local Wikipedia search, and limits tool outputs and time to support training efficiency.

C Implementation Details

  • Tool execution results are excluded from loss calculation, which is restricted to reasoning and tool-invocation tokens.Source: C Implementation Details · p. 13
  • The environment uses a Python sandbox and local Wikipedia search, capped at the top 3 results and a 10-second tool-call timeout.Source: C Implementation Details · p. 13
  • Experiments use Qwen3-4B in non-thinking generation mode on NVIDIA H200 GPUs, with each training epoch taking approximately 10 hours.Source: C Implementation Details · p. 13
  • Table 2 lists the agentic RL training hyperparameters.Source: Table 2 · p. 13

D Training Algorithms

SEARL evolves a tool graph from tool-creation trajectories while optimizing policy with episode- and tool-anchored advantages. Its retrieval and prompting procedures organize tool reuse and stepwise execution.

D Training Algorithms

  • Each iteration samples tasks, rolls out planned actions with retrieved tools, registers filtered new tools, and updates the policy using combined episode- and tool-anchored advantages.The combined advantage adds episode-relative and tool-anchored step advantages, weighted by λ.Source: D Training Algorithms · p. 13

E Policy Optimization

  • Episode-relative and analogous-tool step advantages provide hierarchical credit assignment; ω balances them, while clipped policy optimization includes a β-scaled KL penalty to πref.Episode advantage evaluates an episode against others in its group, while step advantage assigns finer credit to actions under analogous tool-use conditions.Source: E Policy Optimization · pp. 13–14

F Tool Creation and Retrieval Details

  • The MCP creation-and-execution tool takes tool metadata, code, inputs, and a timeout, and returns a JSON-formatted creation status and execution result.The listed signature gives the timeout a default value of 15 seconds.Source: F Tool Creation and Retrieval Details · p. 14

F.1 Tool Creation

  • A predefined MCP creation tool immediately executes generated tools, saving LLM reasoning steps and filtering failed creations.Tools are registered only after trajectories for the sample are aggregated; the highest cumulative-reward trajectory supplies the sub-plan graph and tools, with tools as nodes and dependencies as edges.Source: §F.1 · p. 14

F.2 Tool Retrieval

  • After deriving a subtask plan, SEARL retrieves top-k relevant tools from the Tool Graph and appends them to the system prompt as recommendations, not constraints.The agent retains autonomy over whether to invoke a retrieved tool.Source: §F.2 · pp. 14–15

F.3 Retrieval Model

  • Hybrid retrieval combines TF-IDF keyword matching with MiniLM embedding-based semantic retrieval, using α = 0.5 to balance lexical precision and semantic generalization.The dense component uses sentence-transformers/all-MiniLM-L6-v2 and cosine similarity.Source: §F.3 · p. 15

G Prompt

  • The prompt asks the agent to plan concrete subtasks and dependencies, solve them stepwise, create at most one reusable MCP per step, and verify its answer.The prompt also directs the agent to include a verification plan.Source: G Prompt · pp. 16–17

Related papers

Loading 2604.07791v3…