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

TL;DR

EvoTool is a self-evolving framework that optimizes how LLM agents use tools by breaking the agent's policy into four distinct modules: Planner, Selector, Caller, and Synthesizer. By using a "Blamer" LLM to pinpoint exactly which module caused a failure and a "Mutator" LLM to provide targeted natural-language fixes, it achieves significant performance gains and better token efficiency than monolithic "all-at-once" optimization methods.

What Problem Does This Paper Address?

Building LLM agents that can reliably use external tools (APIs, databases, etc.) is notoriously difficult. Most current agents rely on complex, hand-crafted prompts. When these agents fail during a long-horizon task—like booking a multi-leg flight—it creates a credit assignment problem.

If the final answer is wrong, was it because the Planner made a bad step? Did the Selector pick the wrong tool? Did the Caller format the arguments incorrectly? Or did the Synthesizer fail to interpret the tool's output?

Existing optimization methods usually fall into two traps:

  1. Monolithic Optimization: They try to update the entire agent prompt at once. This often "entangles" behaviors, where fixing a planning error might accidentally break the agent's ability to format arguments.
  2. Single-Aspect Optimization: They focus on refining just one part (like planning) in isolation, ignoring how errors propagate across the different stages of tool use.

Methods

EvoTool introduces a modular, gradient-free evolutionary loop to iteratively refine agent policies. It treats the agent's prompt as a collection of four evolvable modules: Planner, Selector, Caller, and Synthesizer.

The framework operates through three core mechanisms:

  • Trajectory-Grounded Blame Attribution: Instead of just looking at the final "Success/Failure" signal, a specialized "Blamer LLM" analyzes the entire execution trace. It assigns a "blame score" to each module to identify the most likely culprit for a failure.
  • Feedback-Guided Targeted Mutation: Once a module is blamed, a "Mutator LLM" generates a natural-language critique based on the failure. It then edits only that specific module's prompt while keeping the others frozen. This prevents the "regression" issues seen in monolithic methods.
  • Diversity-Aware Population Selection: Rather than just keeping the single "best" prompt based on average scores, EvoTool maintains a population of candidates. It uses an "instance-wise winner" criterion, ensuring that "specialist" prompts—which might excel at specific, tricky tasks even if their average is lower—are preserved to maintain solution diversity.

Datasets

The authors evaluated EvoTool across four diverse benchmarks to test different agent competencies:

  • ToolBench: Tests large-scale API generalization (over 16,000 REST APIs).
  • RestBench: Focuses on sequential tool use for TMDB (movies) and Spotify.
  • $\tau$-Bench: Evaluates stateful, long-horizon user interactions in retail and airline domains.
  • BFCL (Berkeley Function Calling Leaderboard): Assesses the precision of function calling and argument generation.

Key Insights and Ideas

  • Modularity is the Key to Stability: By decoupling the agent into four roles, the system can perform "surgical" updates. This mirrors software engineering principles where you debug a specific function rather than rewriting the whole program.
  • The "Blamer" Solves Credit Assignment: The most significant "aha moment" is using an LLM as a diagnostic judge. By providing the Blamer with structured diagnostic events (e.g., "tool execution failed due to missing ID"), it can effectively localize errors that are otherwise buried in long trajectories.
  • Preserving Specialists Prevents Mode Collapse: Standard evolutionary strategies often converge on a single "safe" strategy. EvoTool’s diversity-aware selection keeps prompts that solve unique edge cases, leading to a more robust final policy that handles a wider variety of tasks.
  • Natural Language as a Gradient: Since we can't backpropagate through discrete prompts, the natural-language feedback from the Mutator acts as a "semantic gradient," guiding the search toward better prompt configurations.

Key Results

EvoTool was tested using GPT-4o (referred to as GPT-4.1 in the paper) and Qwen3-8B as backbones.

  • Performance: It consistently outperformed strong baselines (like OPRO and DRAFT) by over 5 points on average across all benchmarks.
  • Robustness: On the complex, stateful $\tau$-Bench, EvoTool reached a score of 52.0, significantly higher than single-aspect methods like DRAFT (38.8), which struggled with cross-module dependencies.
  • Efficiency: EvoTool achieved higher success rates with lower token costs during the optimization phase compared to monolithic optimizers, which often require massive amounts of text to describe global changes.
  • Transferability: Policies evolved on one dataset (e.g., ToolBench) showed strong "zero-shot" performance when moved to another (e.g., RestBench), suggesting the framework learns generalizable tool-use principles rather than just over-fitting to specific tasks.

Limitations and Future Work

  • Inference Latency: The evolutionary process requires multiple iterations of "rollout, blame, and mutate," which can be time-consuming and computationally expensive during the training/optimization phase.
  • Text-Centric Focus: The current study focuses on text-based APIs and environments. The authors note that extending this modular evolution to multi-modal tools or embodied agents (robots) is a promising but unexplored direction.
  • LLM-in-the-loop: The system relies on a "Blamer" and "Mutator" LLM. The quality of the evolution is inherently tied to the reasoning capabilities of these supervisor models. Using smaller, specialized models for blaming/mutating could be an interesting area for cost reduction.

Summary updated

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.
BibTeX
@inproceedings{yang2026evotool,
  author = {Shuo Yang and Soyeon Caren Han and Xueqi Ma and Yan Li and Mohammad Reza Ghasemi Madani and Eduard Hovy},
  title = {{EvoTool: Self-Evolving Tool-Use Policy Optimization in LLM Agents via Blame-Aware Mutation and Diversity-Aware Selection}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.2016},
}
Figure