Source-linked AI summary
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
LLM agents struggle to optimize long-horizon tool-use policies because delayed terminal supervision makes credit assignment difficult, while existing global or isolated updates miss important interactions. EvoTool evolves a four-module policy with blame attribution, targeted mutation, and diversity-aware selection, outperforming state-of-the-art baselines by more than 5 points across four benchmarks on GPT-4.1 and Qwen3-8B.
Problem
Delayed terminal supervision in long-horizon tool use makes it difficult to assign failures to the responsible policy component.
Method
EvoTool uses gradient-free evolution over Planner, Selector, Caller, and Synthesizer modules, combining blame attribution, targeted mutation, and diversity-aware population selection.
Results
More than 5 points of improvement over state-of-the-art baselines are reported across ToolBench, RestBench, τ-Bench, and BFCL on GPT-4.1 and Qwen3-8B.
Takeaways & Limitations
The framework achieves superior token efficiency and robust transferability across datasets and models.
Takeaways & Limitations
Iterative inference may introduce latency for strictly real-time applications, and evaluation currently covers textual and API-based environments.
Abstract
from arXiv · showhide
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.
1 Introduction
EVOTOOL addresses delayed supervision and credit-assignment problems in long-horizon tool use with modular, blame-aware evolutionary updates. It combines targeted module editing with diversity-preserving selection and reports consistent gains, efficiency, and transferability across four benchmarks.
- Motivation: Long-horizon tool-use failures are difficult to diagnose because terminal supervision collapses multiple planning, selection, invocation, and synthesis errors into one signal.This obscures the responsible component and hinders targeted policy improvement.
- Limitations of prior work: Existing optimization either entangles heterogeneous behaviors through global edits or refines components in isolation while ignoring cross-module error propagation.Neither paradigm simultaneously provides targeted correction and multi-module coordination.
- EVOTOOL: Trajectory-Grounded Blame Attribution and Feedback-Guided Targeted Mutation localize failures and edit only the responsible module using trace-grounded natural-language feedback.The remaining modules stay fixed during the targeted update.
- EVOTOOL: Diversity-Aware Population Selection retains complementary policy variants through instance-level wins instead of greedily choosing one global-average leader.This discourages premature convergence to a narrow strategy.
- Results: Over 5 points of improvement are reported on both open-source and closed-source models across four diverse benchmarks, alongside superior token efficiency and transferability.The reported gains span datasets and models.
- EVOTOOL: EVOTOOL optimizes a modular tool-use policy comprising Planner, Selector, Caller, and Synthesizer through a gradient-free evolutionary paradigm.The framework is self-evolving and updates policy specifications rather than model weights.
2 Related Work
Prior tool-use systems range from manually engineered and training-based approaches to training-free self-improvement, but automated methods face trade-offs in adaptability and policy-edit scope. Self-evolving systems use repeated acting, evaluation, and updating, yet the supplied passage does not state a complete resolution of these trade-offs.
- Agent Tool-Use Policy Learning: Hand-crafted prompting and fixed heuristics require substantial manual effort and can generalize poorly across domains and tools.They may also fail when unanticipated errors disrupt rigid execution flows.
- Agent Tool-Use Policy Learning: Training-based tool-use approaches internalize behavior through supervised fine-tuning or reinforcement learning but face costly adaptation because weights are static and data requirements are large.The passage contrasts these methods with online, training-free refinement from interaction feedback.
- Agent Tool-Use Policy Learning: Training-free optimization refines tool-use behavior online without weight updates, but the related-work discussion identifies a trade-off involving global policy edits.The supplied passage truncates the remainder of that trade-off.
- Self-Evolving Agent Systems: Self-evolving agent systems repeatedly act, evaluate outcomes, and update decision policies, including through self-reflection, self-correction, and continual improvement loops.These systems convert failures into natural-language or structured feedback and may accumulate skills or update components.
3 Preliminaries
The paper formulates tool use as interaction between an LLM agent and an external environment, with success evaluated on terminal predictions. Its policy is a four-module composition whose specifications evolve while the base model weights remain frozen, targeting sparse-outcome credit assignment.
- Task and Environment Formulation: A task instance is drawn from D, and the agent interacts with tools through textual states, actions, and environment observations to form a trajectory.Actions may reason, invoke a tool, or terminate with an answer.
- Task and Environment Formulation: Each rollout terminates in a prediction y-hat, and performance is measured by a task-dependent success function instantiated by metrics such as pass@1, success rate, and F1.The rollout is summarized as an episode containing the task, trajectory, prediction, and reward.
- Modularized Tool-Use Policy: The modular policy contains a planner for subgoal decomposition, selector for tool choice, caller for argument construction and execution, and synthesizer for integrating tool outputs.These roles operate sequentially on intermediate states.
- Modularized Tool-Use Policy: The modules share a base LLM with frozen weights W, while evolvable specifications Θ contain prompts, tool templates, or lightweight formatting rules.Learning updates Θ only; W remains fixed.
- Optimization Objective: The optimization objective is to maximize expected task success by evolving Θ under frozen weights W.This setup frames the challenge as localizing failures and updating only the responsible component from sparse end-of-trajectory outcomes.
4 Methods
EVOTOOL evolves a modular tool-use policy through blame-guided, single-module mutations and diversity-aware population selection. Its loop collects trajectories, diagnoses responsibility, generates feedback, and retains complementary candidates.
- Self-Evolving Optimization Loop: EVOTOOL maintains a population of modular policy specifications and iteratively improves them through trajectory collection, blame attribution, targeted mutation, and population selection.The policy modules are Planner, Selector, Caller, and Synthesizer.
- Population Selection: A child candidate is added only when it outperforms its parent on the mini-batch, after which diversity-aware selection updates parent sampling using held-out evaluation.The loop returns the best-performing candidate in the population after a fixed budget.
- Trajectory-Grounded Blame Attribution: Trajectory-grounded blame attribution extracts diagnostic events and assigns module-wise blame scores, selecting the highest-scoring module as the mutation target.Diagnostics include tool-choice outcomes, argument validity, execution outcomes, and synthesis-grounding signals.
- Feedback-Guided Targeted Mutation: Feedback-guided mutation edits only the blamed module specification while freezing the remaining components.A reflective mutator converts the blamed episode into natural-language feedback for the selected module.
5 Experiment
EVOTOOL is evaluated across four established tool-use benchmarks and compared with hand-crafted, monolithic, and single-aspect policy baselines. It shows consistent gains, monotonic learning, and stronger broad-task performance than representative alternatives.
- Experiment Setup: EVOTOOL is evaluated on ToolBench, RestBench, τ-Bench, and BFCL using their benchmark-standard metrics.The evaluation covers API generalization, sequential REST tool use, stateful long-horizon interactions, and single- or multi-turn function calling.
- Baselines: The comparison includes hand-crafted prompting, monolithic black-box prompt optimization, and single-aspect policy-design baselines.These baseline streams include fixed heuristics, global prompt search, and component-focused optimization.
- Main Results: EVOTOOL consistently outperforms all baselines across both backbone models and four benchmarks.On GPT-4.1, it reaches an overall average of 70.6, nearly 6 points above DRAFT and roughly 7 points above EvoPrompt; on Qwen3-8B, it exceeds the second-best baseline by 5.2 points.
- Learning Dynamics and Efficiency: EVOTOOL delivers the most consistent gains across evolution iterations and sustains a monotonic upward trajectory to the highest final scores.DRAFT and AdaPlanner show domain brittleness, while OPRO and EvoPrompt struggle with broad API generalization.
6 Ablation
Ablations support all three design mechanisms: blame-based targeting, trajectory- and feedback-guided mutation, and diversity-aware selection. The gains are especially evident on harder long-horizon tasks.
- Blame Targeting: Random mutation reduces the average by over 9 points relative to the static baseline, while EVOTOOL achieves the best overall average among blame-targeting variants.Monolithic updates yield only modest gains, whereas blame-based targeting supports robust multi-task learning.
- Mutation Guidance: Removing both trajectory evidence and explicit feedback produces the lowest success rate, while the full model performs best with both signals.Dropping explicit feedback causes a larger degradation than dropping trajectory evidence, indicating that the signals are complementary.
- Population Diversity Preservation: Learning-based parent selection improves performance over the static baseline, and EVOTOOL performs best across all benchmarks.The diversity-aware rule retains high-quality parents while preserving complementary variants, with the clearest advantage on τ-Bench and BFCL.
7 Analysis
Analysis shows that EVOTOOL reduces different error types at different rates and transfers across datasets and models. Remaining bottlenecks concentrate on planning in stateful tasks, while evolved prompts become more explicit and executable.
- Error Progression Diagnosis: On ToolBench, total error falls from 77.6% to 38.0% over three iterations and reaches 20.2% by iteration 8.Caller and Selector errors decline first, leaving synthesis and planning as residual error sources.
- Error Progression Diagnosis: On τ-Bench, Planner failures remain dominant even after total error falls to 33.3%.The persistent profile identifies multi-step dependency tracking and state maintenance as the key bottleneck in this setting.
- Transferability: Policies evolved on ToolBench and RestBench transfer strongly across datasets, while cross-model transfer improves performance by 4.7 and 12.7 points in the reported directions.These results indicate that the learned behaviors are not narrowly coupled to one benchmark or model.
- Qualitative Prompt Evolution: EVOTOOL’s evolved Planner prompt adds explicit executable constraints, including tool-index grounding and restrictions against hallucinated identifiers or parameters.The prompt also enforces atomic planning steps and a tool-interface contract.
8 Conclusion
EVOTOOL is a self-evolving framework that optimizes modular tool-use policies through gradient-free evolution and three mechanisms addressing credit assignment under delayed supervision. Across four benchmarks, it outperforms state-of-the-art baselines by more than 5 points on GPT-4.1 and Qwen3-8B while achieving superior token efficiency and transferability.
- EVOTOOL optimizes modular tool-use policies with a gradient-free evolutionary paradigm to address credit assignment under delayed supervision.
- Its policy decomposition uses four modules: Planner, Selector, Caller, and Synthesizer.
- Trajectory-grounded blame attribution localizes failures, feedback-guided targeted mutation applies module-specific updates, and diversity-aware selection prevents mode collapse.
- More than 5 points of improvement over state-of-the-art baselines appears on both GPT-4.1 and Qwen3-8B across four benchmarks.
- EVOTOOL also achieves superior token efficiency and robust transferability across datasets.
Limitations
EVOTOOL remains subject to latency and scope limitations despite robust performance and efficiency. Its iterative inference process may constrain strictly real-time use, and its evaluation does not yet cover multimodal tools or embodied agents.
- Iterative inference steps may introduce latency for strictly real-time applications.
- The current evaluation focuses on textual and API-based environments rather than multimodal tools or embodied agents.
A.1 Algorithm Overview
Algorithm 1 describes EVOTOOL’s iterative optimization loop over a population of modular prompt specifications with frozen LLM weights. Each generation collects trajectories, attributes blame, and applies a targeted mutation to the responsible module.
- The optimization starts with prompt specifications for Planner, Selector, Caller, and Synthesizer while keeping LLM weights frozen.
- Each iteration collects execution trajectories and rewards from a training mini-batch.
- Trajectory-grounded blame attribution identifies the module most responsible for observed failures.
- Module-specific feedback is generated and used to mutate only the identified module.
A.2 Datasets
The evaluation covers four tool-use benchmarks spanning API selection, sequential REST interactions, stateful dialogue, and function calling. It also specifies controlled comparison procedures and an evolutionary optimization pipeline with blame attribution, targeted mutation, and diversity-aware selection.
- Datasets: Four benchmarks evaluate complementary tool-use capabilities: ToolBench, RestBench, τ-Bench, and BFCL.They cover large API inventories, sequential REST calls, stateful customer-service interactions, and schema-valid function calling.
- Datasets: ToolBench tests multi-step API execution across 3,451 tools and 16,464 REST APIs in three difficulty regimes.Its G1, G2, and G3 settings emphasize tool selection, call ordering, and schema-valid arguments.
- Datasets: RestBench uses gold solution paths for sequential REST tasks, while τ-Bench evaluates policy-compliant, long-horizon interactions with backend databases.RestBench includes TMDB and Spotify scenarios; τ-Bench includes retail and airline domains.
- Datasets: BFCL measures function selection and schema-valid arguments with deterministic checking across 5,551 instances and a multi-turn suite.It also evaluates clarification and consistency across iterative tool-use turns.
- Evaluation setup: EVOTOOL compares against hand-crafted, monolithic, and single-aspect policy designs under matched backbones, environments, budgets, and held-out selection procedures.Its evolutionary loop collects trajectories, attributes blame, mutates the blamed module, and selects diverse candidates.