Skip to content

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

🕒 Published (v1): 2026-04-09 04:38 UTC · Source: Arxiv · Venue: ACL 2026 · link

Why this paper was selected

Joint optimization of policy and tool graph memory for self-evolving agents [ACL 2026]

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

SEARL introduces a reinforcement learning framework that jointly optimizes an LLM policy and a graph-structured external tool memory (\(T_G\)), enabling self-evolving agents that accumulate and reuse decomposed problem-solving tools. Unlike prior RL approaches that treat memory as static, SEARL's Tool Graph grows continuously during training, with merging and deduplication maintaining semantic coherence. Evaluated on math and multi-hop QA benchmarks, SEARL achieves the best average rank (1.43) across seven tasks vs. five baselines.

Problem

Existing agentic RL methods face two compounding issues: (1) outcome-based rewards are sparse—agents receive feedback only at trajectory end—making credit assignment in multi-step tool-use settings unreliable; (2) tool-generation methods (e.g., Alita, STELLA) store tools in flat, unstructured repositories, precluding structural reuse and causing monolithic tool generation that overwhelms small LLMs. No prior method jointly evolves both the policy parameters and a structured external tool memory.

Method

SEARL formalizes the agent as a Tool Memory-Enhanced MDP \(\langle S, A, P, R, T_G \rangle\), where \(T_G = (V, E)\) is a directed graph with MCP tool nodes and execution-dependency edges. Each trajectory is decomposed into four XML-tagged phases: Plan (global strategy), Retrieve (select tool \(T_t\) from \(T_G\) via alignment scoring), Think (deliberate on tool reuse vs. direct answer), Action (emit <answer> or <tool_call>).

Reward shaping combines a sparse binary outcome reward \(R(\tau) \in \{0, 1\}\) with dense step-level behavioral rewards for: successful plan parsing (\(r_\text{planning}\)), valid tool registration (\(r_\text{creation}\)), successful tool execution (\(r_\text{execution}\)), and format conformance (\(r_\text{format}\)). Strict negative penalties discourage redundant tool calls.

Advantage estimation uses a two-level structure: - Episode-level: normalized return \(A^E(\tau_i) = \frac{R(\tau_i) - \bar{R}}{\sigma_R}\) across \(N\) rollouts of the same task. - Step-level: actions grouped by the MCP tool anchor \(g\) they interact with across all trajectories. The step advantage \(A^S(a_t^{(i)})\) normalizes discounted return-to-go within each tool group \(G^S(g)\), providing cross-trajectory credit for tool-level decisions without requiring state re-visitation.

Tool Graph evolution: task-specific subgraphs \(T_G^{(i)}\) are extracted by mapping subtask dependency graphs into tool space. New tools are registered only if they yield top cumulative rewards among rollout candidates. At merge time, semantic embeddings (cosine similarity \(\geq \delta\)) determine node merging; edges are redirected to consolidated nodes, accumulating dependency patterns across all trajectories.

Key Contributions

  • SEARL framework: first paradigm to jointly optimize policy parameters \(\theta\) and external tool-based memory \(T_G\) within a single RL loop.
  • Tool-Memory-Aware Policy Optimization: step-level advantage groups anchored to MCP tool identities rather than raw environment states, enabling cross-trajectory credit assignment in open-ended state spaces.
  • Tool Graph Memory: directed persistent graph encoding tool semantics (nodes) and execution precedence (edges), with semantic deduplication and structural edge consolidation across training iterations.
  • Composite reward: dense process-level rewards (planning, creation, execution, format) combined with sparse outcome signal to densify feedback.

Results

All results use pass@1 accuracy with Qwen3-32B as LLM judge. Baselines: TIR Prompting, GRPO, DAPO, REINFORCE++, ARPO. Training data: 10k Tool-star samples.

  • Average Rank: SEARL 1.43 vs. GRPO 2.43, DAPO 3.00, ARPO 3.57, REINFORCE++ 4.57, TIR 5.29
  • AIME24: SEARL 0.3333 (tied with ARPO; GRPO/DAPO 0.1333, REINFORCE++ 0.1000, TIR 0.0000)
  • Bamboogle: SEARL 0.3040 vs. DAPO 0.2480, GRPO 0.1600
  • 2WikiMultihopQA: SEARL 0.3600 vs. DAPO 0.3500, GRPO 0.3450
  • HotpotQA: SEARL 0.3350 (tied with DAPO)
  • Musique: SEARL 0.0900 (tied with GRPO; best among baselines)
  • GSM8K / MATH500: SEARL competitive (0.8620 / 0.6820) but not always top—monolithic reasoning suffices for easier tasks
  • Ablation: removing Step-level Grouping causes the largest accuracy drop (e.g., AIME24, Bamboogle); removing Step Rewards is next most damaging; Single Vanishing has smaller but stabilizing effect

Limitations

  • Autonomous tool decomposition introduces procedural overhead for simple problems where direct reasoning suffices, causing marginal performance loss on GSM8K/MATH500 relative to ARPO.
  • Semantic merging threshold \(\delta\) is a fixed hyperparameter; its sensitivity is not analyzed.
  • The approach is evaluated only on math and Wikipedia-based QA; generalization to GUI, code, or embodied tasks is untested.
  • Requires MCP-compatible tool registration infrastructure; portability to other tool frameworks is unaddressed.
  • Step-level grouping relies on tools appearing across multiple trajectories; rare or novel tools may form singleton groups, triggering Single Vanishing bypass and losing step-level signal.

Relevance to Harnesses / Meta-Harnesses

SEARL is directly relevant as an adaptive meta-harness that bootstraps its own sub-tool library during training—the Tool Graph \(T_G\) is a living registry of composable MCP tools with explicit dependency wiring, the computational analogue of a harness maintaining a growing catalog of reusable pipeline stages. The four-phase trajectory structure (Plan → Retrieve → Think → Act) mirrors the orchestration pattern common in meta-harnesses: decompose the task, look up existing handlers, decide on reuse vs. creation, then dispatch. The key advance for this topic is the joint RL signal that simultaneously improves the harness policy and the tool library: rather than designing tool graphs by hand or via one-shot synthesis, SEARL shows that tool-graph structure can emerge from reward-shaping over trajectory outcomes, providing a principled recipe for self-improving harness architectures.