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

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

TL;DR

SEARL is a new reinforcement learning framework that jointly optimizes an LLM agent's policy and a structured "Tool Graph Memory." By decomposing complex tasks into modular sub-tools and mapping their execution dependencies in a graph, SEARL allows smaller LLMs to continuously create, reuse, and generalize problem-solving skills. This approach addresses the long-standing challenge of sparse rewards in agent training through fine-grained, tool-anchored credit assignment.

What Problem Does This Paper Address?

While Large Language Models (LLMs) excel at single-turn tasks, they frequently stumble on complex, long-horizon problems. To solve them, agents need tools. However, most current frameworks either rely on a static, predefined list of tools (which limits adaptability) or generate tools autonomously but dump them into unstructured repositories.

Unstructured tool storage lacks connectivity, making it incredibly difficult for an agent to understand how tools depend on one another. Furthermore, asking a smaller, resource-constrained LLM to generate a single, massive "monolithic" tool to solve a complex task usually results in failure.

Figure 1: Limitations of existing paradigms. Monolithic tool synthesis overwhelms LLMs, necessitating a divide- and-conquer strategy, while current memory designs suffer from a lack of structural connectivity.

Compounding this is the classic reinforcement learning (RL) challenge of sparse rewards: an agent typically only receives feedback (success or failure) at the very end of a long trajectory, making it hard to determine which specific tool invocation or reasoning step actually helped.

Methods

SEARL introduces a co-optimization paradigm where both the agent's policy and its external memory evolve together during training. It consists of three core pillars:

  1. Tool Graph Memory ($T_G$): Instead of a flat list, tools are represented as nodes in a directed graph, where edges encode execution dependencies. When faced with a task, the agent decomposes it into a plan of subtasks, generates small, modular tools for each logical stage, and links them together.
  2. Structured Trajectory Generation: The agent's decision-making process is explicitly broken down into distinct, XML-tagged phases: Planning (formulating a high-level strategy), Retrieve (picking the right tool from $T_G$), Think (internal deliberation), and Action (executing code or returning an answer).
  3. Tool-Memory-Aware Policy Optimization: To solve the credit assignment problem, the authors implement a two-level advantage structure. Along with a global, episode-level relative advantage, they introduce a step-level relative advantage anchored on tool usage. Because open-ended environment states are too vast to match precisely, SEARL abstracts the state space by grouping actions based on the specific tool being utilized, providing a dense and stable learning signal.
Figure 1: Limitations of existing paradigms. Monolithic tool synthesis overwhelms LLMs, necessitating a divide- and-conquer strategy, while current memory designs suffer from a lack of structural connectivity.

Datasets

The framework was trained using 10,000 open-source RL training samples from Tool-star and evaluated across two primary domains:

  • Mathematical Reasoning: AIME2024, MATH500, and GSM8K.
  • Knowledge-Intensive Reasoning: WebWalker, alongside four Wikipedia-based multi-hop QA benchmarks: HotpotQA, 2WikiMultihopQA, Musique, and Bamboogle.

Key Insights and Ideas

  • Modular > Monolithic: Smaller LLMs (like the 4B model used here) lack the reasoning capacity to write complex, all-in-one scripts. Breaking tasks down into a hierarchical pipeline of simple, specialized tools dramatically improves execution success and reusability.
  • Tools as State Abstractions: In continuous or open-ended environments, traditional RL struggles because the agent rarely visits the exact same state twice. SEARL cleverly uses tool utilization as an anchor, mapping an infinite state space into a finite set of tool-interaction contexts to make step-level grouping mathematically practical.
  • Graph Structure Curbs Hallucination: In multi-hop QA, standard agents often get overwhelmed by the massive amount of irrelevant text returned by search engines. By utilizing a graph structure to isolate precise evidence step-by-step, SEARL keeps intermediate reasoning grounded.

Key Results

  • Top-Tier Performance: SEARL achieved an Average Rank of 1.43 across all tasks, consistently outperforming or matching strong RL baselines like GRPO, DAPO, and ARPO.
  • Multi-Hop QA Superiority: The framework showed substantial gains in tasks requiring the composition of disjoint information, scoring 0.3040 on Bamboogle (compared to GRPO's 0.1600) and 0.3350 on HotpotQA.
  • Complex Math Generalization: On the difficult AIME24 benchmark, SEARL matched the state-of-the-art baseline (ARPO) with a accuracy of 0.3333, proving its ability to construct novel solution paths dynamically.
  • Crucial Components: Ablation studies highlighted that Step-level Grouping was the most vital design choice; removing it led to severe performance degradation across almost all datasets.

Limitations and Future Work

Despite its success, the authors note a few key limitations:

  • Procedural Noise on Simple Tasks: On straightforward datasets like GSM8K, SEARL is slightly less competitive than pure monolithic reasoning baselines. The overhead of generating and retrieving tools introduces unnecessary procedural noise when direct text generation would suffice.
  • Trivial Tool Generation: Because of the smaller scale of the base model (Qwen-3-4B), many autonomously generated tools remain simplistic, limiting how effectively they can be shared with or reused by larger LLMs.
  • Reward Hacking: As with most dense reward structures, there remains a risk that the agent learns to optimize for superficial formatting or redundant tool calls rather than genuine reasoning depth, indicating a need for even tighter reward alignment in future iterations.

Summary updated

Abstract

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.
BibTeX
@inproceedings{feng2026searl,
  author = {Xinshun Feng and Xinhao Song and Lijun Li and Gongshen Liu and Jing Shao},
  title = {{SEARL: Joint Optimization of Policy and Tool Graph Memory for Self-Evolving Agents}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.1125},
}
Figure