EvoTool: Self-Evolving Tool-Use Policy Optimization in LLM Agents

+5.7

Overall over the strongest baseline

GPT-4.1 backbone: 70.6 vs 64.9

+5.2

Overall over the strongest baseline

Qwen3-8B backbone: 57.0 vs 51.8

4 / 4

Best average score on all four benchmarks

ToolBench · RestBench · τ-Bench · BFCL — with both backbones

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 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 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.

Learning Curve & Efficiency

Panel (a): learning curves of average score versus evolution iteration on ToolBench, RestBench, tau-Bench, and BFCL — EvoTool climbs above DRAFT, EvoPrompt, OPRO, AdaPlanner, and the static ReAct line on all four. — 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.

Panel (b): success rate versus log total token cost under GPT-4.1 on the same four benchmarks — EvoTool occupies the upper-left (higher performance at lower cost) relative to DRAFT, EvoPrompt, OPRO, AdaPlanner, and ReAct. — 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.

Illustrative genealogy tree of EvoTool's evolutionary search: from a seed population, coloured edges mark which module each accepted mutation edited; grey boxes are gate-rejected children, red dashed boxes are candidates discarded by diversity selection, green boxes survive in the final population, and the highlighted path ends at the gold returned policy. — Search process: An illustrative genealogy of the evolutionary search behind these curves (scores are illustrative). Each generation samples one parent (∝ win frequency) and mutates exactly one module (edge colour); the gate keeps a child only if it beats its parent (grey = gate-rejected), and diversity-aware selection drops population members that win no held-out instance (red). Green candidates survive in the final population; the highlighted lineage ends at the returned policy (gold).

Method

EvoTool architecture: (1) trajectory collection — the modular tool-use policy agent (Planner, Selector, Caller, Synthesizer) interacts with the tool environment and records an episode; (2) the Blamer LLM performs trajectory-grounded blame attribution over the four modules; (3) the Mutator LLM applies feedback-guided targeted mutation to the blamed module; (4) diversity-aware population selection updates probabilities, identifies instance-wise winners, and retains complementary candidates in the population pool. — 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.

Trajectory-Grounded Blame Attribution

Supervision in long-horizon tool use is delayed, making credit assignment hard. EvoTool uses diagnostic traces from the rollout to localize each failure to a specific module — Planner, Selector, Caller, or Synthesizer — turning a trajectory-level outcome into a module-level signal.

Feedback-Guided Targeted Mutation

Given the blamed module, a mutator edits only that module’s prompt specification, guided by a natural-language critique of the failure. Edits stay targeted, avoiding the entangled behaviors that monolithic rewrites are prone to.

Diversity-Aware Population Selection

Rather than greedily keeping a single best candidate, the population preserves complementary candidates to ensure solution diversity, so distinct strengths survive across generations of the self-improving loop.

Gradient-free by design: only the four module prompt specifications evolve — the LLM weights stay frozen.

Case Study & Interactive Replay

Reference testbed run — Qwen3-4B backbone on curated 150-instance demo subsets

Learning curve of a reference EvoTool testbed run: held-out score rising over generations as targeted mutations are accepted.

The curve shows EvoTool’s loop at work on a small controllable testbed: blame attribution localizes each failure to one module, targeted mutations accumulate module-by-module fixes, and the held-out score rises in steps as stronger policies take over. In the interactive replay you can step through every generation — which module was blamed, the exact prompt edit, and whether the child was accepted.

Open the Interactive Replay Read the full case study (CASE_STUDY.md) →

Main Results

EvoTool is evaluated on four tool-use benchmarks — ToolBench, RestBench, τ-Bench, and BFCL — against prompting, prompt-evolution, and tool-use-specific baselines, with two backbones.

GPT-4.1 backbone
Method	ToolBench Avg	RestBench Avg	τ-Bench Avg	BFCL Avg	Overall
ReAct	63.6	73.4	47.9	56.0	60.6
CoT	50.9	61.7	29.8	32.3	44.5
Plan-and-Solve	59.3	67.0	47.6	41.3	54.4
OPRO	65.2	75.1	47.5	58.9	62.1
PromptBreeder	63.2	74.7	43.9	58.8	60.5
EvoPrompt	66.4	76.9	48.6	62.1	63.8
AdaPlanner	56.5	68.2	50.5	55.2	57.5
EasyTool	73.9	82.5	40.6	56.1	64.4
DRAFT	75.8	84.8	38.8	54.9	64.9
AnyTool	67.7	76.8	48.3	58.2	63.3
EvoTool (ours)	77.7	86.2	52.0	63.1	70.6

Qwen3-8B backbone
Method	ToolBench Avg	RestBench Avg	τ-Bench Avg	BFCL Avg	Overall
ReAct	54.2	63.5	23.8	52.0	49.0
CoT	43.3	53.3	11.4	31.1	35.7
Plan-and-Solve	50.4	57.9	23.5	39.8	43.7
OPRO	55.5	64.9	23.5	54.4	50.2
PromptBreeder	53.9	64.6	21.0	54.2	49.0
EvoPrompt	56.5	66.5	24.3	55.8	51.4
AdaPlanner	48.1	59.0	25.6	51.6	46.3
EasyTool	62.3	69.8	15.6	51.0	51.1
DRAFT	64.5	73.3	13.4	49.8	51.8
AnyTool	57.7	66.4	19.1	51.1	49.6
EvoTool (ours)	66.2	74.6	25.8	56.7	57.0

Benchmark-level averages; per-subset numbers (ToolBench G1/G2/G3, RestBench TMDB/Spotify, τ-Bench Retail/Airline, BFCL Single/Multi) are reported in the paper. Metrics — ToolBench: Pass Rate · RestBench: Success Rate · τ-Bench: Pass@1 · BFCL: Accuracy.

Ablations

Where to mutate: blame attribution (Qwen3-8B)
Variant	ToolBench	RestBench	τ-Bench	BFCL	Avg
Static (no evolution)	55.9	65.5	21.0	52.0	48.6
Random module	45.8	52.7	15.9	43.6	39.5
Planner-only	51.2	58.6	24.7	50.1	46.2
Selector-only	63.1	70.8	20.4	48.2	50.6
Caller-only	57.4	66.3	20.2	55.6	49.9
Synthesizer-only	55.0	65.1	21.2	50.7	48.0
Monolithic	59.6	67.2	20.6	48.8	49.1
EvoTool (blame-aware)	66.2	74.6	25.8	56.7	57.0

Blame-aware targeting beats random, single-module, and monolithic mutation.

What guides the mutation (Success Rate; benchmark context in the paper)
Variant	Trajectory τ	Feedback F	Success Rate	Δ
EvoTool (full)	✓	✓	74.6	—
w/o τ	✗	✓	70.2	−4.4
w/o F	✓	✗	65.2	−9.4
w/o τ & F	✗	✗	62.8	−11.8

Both the trajectory τ and the feedback F matter: removing them costs −4.4 / −9.4 / −11.8 points.

How to select survivors (Qwen3-8B)
Variant	ToolBench	RestBench	τ-Bench	BFCL	Avg
Static (no evolution)	56.0	65.5	21.0	52.0	48.6
Greedy	61.1	69.0	23.6	54.3	52.0
Top-k	62.7	71.4	22.1	54.6	52.7
EvoTool (diversity)	66.2	74.6	25.8	56.7	57.0

Diversity-aware selection > top-k > greedy > static.

Blame-driven error progression

Why does blame-aware targeting win? Decomposing errors by module over iterations shows targeted mutation fixing the most correctable failures first: on ToolBench the total error rate falls from 77.6% to 20.2%, driven early by Caller/Selector fixes, while on τ-Bench the residual errors stay Planner-heavy, reflecting its long-horizon demands.

Stacked bar charts of module-level error rates (Caller, Selector, Synthesizer, Planner) with a total-error line over eight evolution iterations: (a) ToolBench, total error falling from 77.6% to 20.2%; (b) tau-Bench, total error falling from 87.6% to 33.3%. — Module-level error progression across evolution iterations diagnosed by the Blamer LLM.

Efficiency & Transferability

Superior efficiency

EvoTool achieves its gains with superior efficiency: comparing methods by performance versus (log) token cost — Figure 3(b) above — EvoTool sits on the favorable side of that trade-off. See the paper for the full analysis.

Two transfer matrices with zero-shot reference rows: (a) dataset transferability between ToolBench and RestBench under GPT-4.1, with in-domain and transfer cells all above the reference; (b) model transferability between Qwen3-8B and GPT-4.1, with transfer gains of +4.7 and +12.7 over the reference. — 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.

Evolved policies transfer

Across datasets (GPT-4.1): a policy evolved on ToolBench transfers strongly to RestBench, and the same pattern holds in the reverse direction.

Across models: a Qwen3-8B-evolved policy remains effective on GPT-4.1, beating the baseline by 4.7 points, while a GPT-4.1-evolved policy transfers back to Qwen3-8B by a significant 12.7 points.

BibTeX

@inproceedings{yang-etal-2026-evotool,
    title = "{EVOTOOL}: Self-Evolving Tool-Use Policy Optimization in {LLM} Agents via Blame-Aware Mutation and Diversity-Aware Selection",
    author = "Yang, Shuo  and
      Han, Caren  and
      Ma, Xueqi  and
      Li, Yan  and
      Ghasemi Madani, Mohammad Reza  and
      Hovy, Eduard",
    editor = "Liakata, Maria  and
      Moreira, Viviane P.  and
      Zhang, Jiajun  and
      Jurgens, David",
    booktitle = "Proceedings of the 64th Annual Meeting of the {A}ssociation for {C}omputational {L}inguistics (Volume 1: Long Papers)",
    month = jul,
    year = "2026",
    address = "San Diego, California, United States",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/2026.acl-long.2016/",
    doi = "10.18653/v1/2026.acl-long.2016",
    pages = "43553--43572",
    ISBN = "979-8-89176-390-6"
}