EvoTool: Self-Evolving Tool-Use Policy Optimization in LLM Agents via Blame-Aware Mutation and Diversity-Aware Selection

Shuo Yang; Soyeon Caren Han; Xueqi Ma; Yan Li; Mohammad Reza Ghasemi Madani; Eduard Hovy

cs.AIMar 5, 2026

EvoTool: Self-Evolving Tool-Use Policy Optimization in LLM Agents via Blame-Aware Mutation and Diversity-Aware Selection

Authors: Shuo Yang, Soyeon Caren Han, Xueqi Ma, Yan Li, Mohammad Reza Ghasemi Madani, Eduard Hovy

Organizations: School of Computing and Information Systems, The University of Melbourne

Abstract

LLM-based agents depend on effective tool-use policies to solve complex tasks, yet optimizing these policies remains challenging due to delayed supervision and the difficulty of credit assignment in long-horizon trajectories. Existing optimization approaches tend to be either monolithic, which are prone to entangling behaviors, or single-aspect, which ignore cross-module error propagation. To address these limitations, we propose EvoTool, a self-evolving framework that optimizes a modular tool-use policy via a gradient-free evolutionary paradigm. EvoTool decomposes agent's tool-use policy into four modules, including Planner, Selector, Caller, and Synthesizer, and iteratively improves them in a self-improving loop through three novel mechanisms. Trajectory-Grounded Blame Attribution uses diagnostic traces to localize failures to a specific module. Feedback-Guided Targeted Mutation then edits only that module via natural-language critique. Diversity-Aware Population Selection preserves complementary candidates to ensure solution diversity. Across four benchmarks, EvoTool outperforms strong baselines by over 5 points on both GPT-4.1 and Qwen3-8B, while achieving superior efficiency and transferability. The code will be released once paper is accepted.

Figures & tables

Figure 1: Limitations of monolithic and single-aspect tool-use policy optimization, and how EVOTOOL enables targeted, blame-aware policy updates.

Figure 2: Overall architecture of EvoTool . EvoTool optimizes a modular tool-use policy through a self-evolving loop consisting of (1) trajectory collection from the tool environment, (2) trajectory-grounded blame attribution to identify the responsible module, (3) feedback-guided targeted mutation to update that module using natural language feedback, and (4) diversity-aware population selection over candidate policies to retain complementary candidates.

Model / Method		ToolBench				RestBench			$\tau$ -Bench			BFCL			Overall
		G1	G2	G3	Avg	TM	SP	Avg	Ret	Air	Avg	Sin	Mul	Avg	Avg
GPT-4.1	Hand-crafted policies
	ReAct	68.2	64.7	57.9	63.6	72.4	74.3	73.4	59.8	35.9	47.9	74.8	37.2	56.0	60.6
	CoT	53.5	50.8	48.4	50.9	59.8	63.5	61.7	34.2	25.3	29.8	43.2	21.4	32.3	44.5
	Plan-and-Solve	63.3	59.2	55.3	59.3	64.8	69.2	67.0	58.4	36.7	47.6	57.2	25.3	41.3	54.4
	Monolithic optimization

Table 1: Main results on two backbone models. We report benchmark-standard metrics on ToolBench (G1/G2/G3), RestBench (TMDB/Spotify),

\tau

-Bench (Retail/Airline), and BFCL (Single/Multi-turn), with the overall average. TM = TMDB, SP = Spotify, Ret = Retail, Air = Airline, Sin = Single-turn, Mul = Multi-turn.

Panel of Figure 3 — Figure 3: Learning dynamics and efficiency comparison. (a) Learning curves across evolution iterations on four benchmarks. (b) Performance versus log token cost under GPT-4.1.

Figure 4: Module-level error progression across evolution iterations diagnosed by the Blamer LLM.

Figure 5: Transferability across datasets and backbone models. (a) Cross-dataset transfer between ToolBench and RestBench. (b) Cross-model transfer between Qwen3-8B and GPT-4.1.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Stage	Artifact	Content
Benchmark	Task instruction	I’m planning a hiking trip… (omitted for brevity) Fetch nearby places for 39.5501 N, 105.7821 W using TrueWay Places . Get geocode for ‘987 Oak Street’ using Census Bureau .
Benchmark	Ground solution	R1: findplacesnearby (TrueWay) R2: geocoding (Census Bureau) R3: Provide Answer
Episode 100 (failure)	Selector Spec v0	[Selector Spec v0 — minimal] - Choose next tool based on semantic relevance. - Prefer tools that directly answer the question. - Pick most common/general tool if unsure.
Episode 100	Incorrect selection	Tool=Weather; API=getForecast; Rationale=Geocoding seems related to location context.
Episode 100	Feedback	Error: required tool not used. Expected: Geocoder - US Census Bureau. Observed: Weather.
EvoTool	Evolved prompt	[Selector Spec v1] HARD CONSTRAINTS: 1) If user explicitly requires tools, you MUST select them. 2) Preserve required tool order. SELECTION HEURISTIC: A) Identify missing variable (subgoal). B) Pick required tool producing that variable.

Appendix

Table 5: ToolBench Case

Policy Optimization

Policy optimization develops algorithms for improving decision rules in reinforcement learning, language models, and sequential decision systems.

See all 215 papers

From Atomic Actions to Standard Operating Procedures: Iterative Tool Optimization for Self-Evolving LLM Agents
Jul 8, 2026Haipeng Ding, Yuexiang Xie, Zhewei Wei +2LLM Agent Self-Improvement LLM Agent Skill Learning
Renmin University of China · Alibaba Group
Tool-R0: Self-Evolving LLM Agents for Tool-Learning from Zero Data
Feb 24, 2026Emre Can Acikgoz, Cheng Qian, Jonas Hübotter +3LLM Agent Training Self-Evolving Agents
UIUC · ETH Zurich
Self-Evolving Agents via Likelihood-Guided Tool-Space Optimization
Sep 28, 2026Xuanqi Zhang, Ruinan Jin, Running Yang +4Continual Learning for LLM Agents LLM Agent Self-Improvement
University of British Columbia · Vector Institute · Columbia University

Jul 8, 2026J/K move · Enter open · S save

From Atomic Actions to Standard Operating Procedures: Iterative Tool Optimization for Self-Evolving LLM Agents

Haipeng Ding, Yuexiang Xie, Zhewei Wei, Yaliang Li+1

Renmin University of China · Alibaba Group

LLM Agent Self-Improvement LLM Agent Skill Learning Tool-Using Agents Self-Evolving Agents

Open paper AskPDF arXiv

Tool utilization enables Large Language Model (LLM) agents to interact with the real world and resolve complex tasks. However, existing agent frameworks predominantly rely on static toolsets composed of granular atomic actions (e.g., basic file I/O or single-turn search), which forces agents to reinvent low-level logic for every recurring workflow, leading to increased reasoning overhead and failure rates. In this study, we propose that agents can achieve self-evolution by synthesizing these atomic actions into reusable Standard Operating Procedures (SOPs), which function as callable higher-order tools that encapsulate multi-step logic. We further introduce EvoSOP, a framework that empowers agents to extract SOPs from execution trajectories and iteratively optimize the toolset through a systematic lifecycle of construction, merging, evaluation, and pruning. Extensive experiments demonstrate that EvoSOP significantly boosts task success rates while substantially reducing the number of interaction rounds compared to baselines. Our analysis also reveals that iterative tool optimization fosters reliable and efficient tool-use patterns, providing a scalable pathway for the development of self-evolving agents.

Abstract

Policy Optimization

Explore similar work

From Atomic Actions to Standard Operating Procedures: Iterative Tool Optimization for Self-Evolving LLM Agents

Tool-R0: Self-Evolving LLM Agents for Tool-Learning from Zero Data

Self-Evolving Agents via Likelihood-Guided Tool-Space Optimization