Evolving Self-tuning Benchmarks for Long-Horizon Tool Use

Hyunji Alex Nam; Michael Dennis; Natasha Jaques; Minsuk Chang

cs.AIOct 19, 2026

Evolving Self-tuning Benchmarks for Long-Horizon Tool Use

Authors: Hyunji Alex Nam, Michael Dennis, Natasha Jaques, Minsuk Chang

Organizations: Stanford University · Google Deepmind · University of Washington

Abstract

For AI assistants to move beyond simple chat interfaces and reliably assist users with applications like Gmail, Venmo, and Slack, we need to improve their tool-use capabilities. However, existing tool use benchmarks are still limited and difficult to scale because they rely on human supervision or are too domain-specific. To make data generation scalable, we propose, TURTLE (Tool Use Related Tasks with Long-Horizon Evolution), an Unsupervised Environment Design (UED) approach to evolve existing tasks using a proposer, a solver, and a feedback generator large language model agents. The proposer is rewarded for difficult yet solvable tasks based on the solver's empirical performance, and the feedback generator summarizes the solver's execution traces for the proposer to exploit. TURTLE produces evolving, self-tuning test suites adaptable to different environment requirements, from supporting user simulators and dense document retrieval to interacting across multiple apps. Empirical results on AppWorld, $τ$ -Bench, and AutomationBench using Gemma 4 31B-it show that the evolved tasks target the desired difficulty range (e.g., a 165% increase in the percentage of hard tasks on AppWorld), increase task diversity (in terms of reasoning and simultaneous tool interactions), and elicit a broader range of failure modes than the original tasks.

Figures & tables

Figure 1: Even with the same underlying toolset, task difficulty can change depending on the instruction and the amount of reasoning and multi-step interaction required. Rather than building new benchmarks from scratch, TURTLE evolves existing tasks using a task proposer, a solver, and a feedback generator LLM without human supervision. During the evolutionary search, the proposer modifies the parent task, generating increasingly challenging but solvable tasks, while trivial or infeasible tasks are pruned based on their scores.

Figure 2: Distribution of average completion rates on the original AppWorld (orange) vs TURTLE (blue) tasks.

Figure 3: Distribution of LLM-evaluated difficulty levels on the original AppWorld vs TURTLE tasks.

Panel of Figure 4 — Figure 4: Features discovered during TURTLE .

Figure 5: Frequency of task features in the original AppWorld (orange) vs TURTLE (blue) datasets.

Figure 6: t-SNE visualization of task instruction embeddings in orange (original) and blue ( TURTLE ). The arrows show the top 10 original-evolved task pairs with the largest cosine distances. TURTLE generates new tasks that are semantically different from the original tasks, expanding the search space.

Figure 7: Co-occurrence of apps between original (left) and TURTLE (right) tasks in AutomationBench. Diagonal entries indicate the percentage of tasks that use that particular app rather than co-occurrence of two apps.

Figure 8: Task features versus error categories for the original (left) and evolved (right) tasks. Darker cells indicate higher frequency and cells with 0 errors are highlighted in red. Tasks with 100% completion rates are excluded from the numerator since they do not elicit any failure, but they remain in the denominator.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 9 — Figure 9: LLM-judge prompt to remove tasks with trivial failures caused by instruction ambiguity.

Panel of Figure 10 — Figure 10: Task template for AppWorld and $\tau$ -bench.

Panel of Figure 11 — Figure 11: Task template for AutomationBench.

Panel of Figure 12 — Figure 12: LLM-judge rating task difficulty. AppWorld Benchmark ( Trivedi et al., 2024 ) tasks are scored on a scale of 1–3 (easy to hard) by human annotators based on the amount of planning, reasoning, and interaction required to solve the task, as well as the presence of hurdles and distractors. We included these examples (two instructions for each level from Table 10 of their paper) as in-context examples in the LLM-judge prompt. We also evaluated the reliability of Gemini 3.6 Flash as a judge by checking its accuracy on the 732 human-labeled AppWorld tasks. Gemini 3.6 Flash achieved: overall accuracy of 58.74%, 34.9% on easy tasks, 64.34% on medium tasks, and 70.2% on hard tasks.

Figure 13: AppWorld task evolved using Gemini 3.1 Flash Lite.

Figure 14: AppWorld task evolved using Gemini 3.6 Flash.

Figure 15: AppWorld task evolved using Gemma 4 31B-it.

Panel of Figure 16 — Figure 16: Applications of TURTLE to AppWorld with different Gemini models as target solvers.

Task property	Source Dataset	Description	Examples
Specification	AppWorld	Explicitly requires the output to be formatted in an exact way that goes beyond just providing the content.	Title files as date_owner’s last name_creation date ; give comma-separated answers or write as answer: {value} (if specific formatting requirements are made in the instruction, the evaluator must check for instruction following accuracy)
Reasoning	AppWorld	Requires an additional reasoning or transformation step that is not natively handled by an API call.	Alphabetically sorting the output list; retrieving only the last four digits of a credit card; mathematical calculations.
Distractor	AppWorld, AutomationBench, SWEBench	Includes distractors or irrelevant information that are unnecessary for the main tool calls, requiring the agent to filter out the noise.	Solver needs to retrieve the most recent order, but the API returns a list containing the past $N$ items which include distractor names; adding irrelevant details or variable/ entity names that are unused in the solution.
Intermediate tool-call	AutomationBench, $\tau$ -banking	Does not explicitly state which API should be used, or it references entities where the necessary information to call the API must first be retrieved through intermediate discovery.	"Return my clothes", but the return policy document must be discovered; "Email my roommates", but the roommates’ identities and their contact information are unknown in the prompt and need to be discovered through additional API calls.
Constraint & Filter	$\tau$ -banking	Includes strict logical constraints, conditional (if-then) logic, or overriding priorities and exceptions.	Constraints: "Only download songs by the artist with N followers"; Conditionals: "If I have more than 5 friends, send them a text individually; otherwise send them a group message."; Overriding Priorities/Exceptions: e.g., A general rule exists (return items without expiration date), but a specific overriding policy applies (clothes expire after N days), and there is an exception to that override (except for certain brands).

Appendix

Table 1: Taxonomy of desirable task features. We used Gemini 3.6 Flash as an LLM judge to label whether each of the specified features is present in a given task instruction. This taxonomy was developed from human review of tasks generated with AppWorld and from error analyses provided by the following benchmarks and papers: AppWorld ( Trivedi et al., 2024 ) , AuotmationBench ( Shepard and Salimans, 2026 ) ,

\tau

-banking ( Shi et al., 2026 ) , SWEBench ( Jimenez et al., 2024 ) , GDPval ( Patwardhan et al., 2025 ) , and FactoryBench ( Merzouki et al., 2026 ) .

Panel of Figure 17 — Figure 17: Applications of TURTLE to different benchmarks with varying task difficulty levels (using the Gemma 4 31B-it solver).

Figure 18: t-SNE visualization of the task embeddings from AppWorld using the Gemini 3.1 Flash Lite solver (original versus evolved).

Figure 19: t-SNE visualization of the task embeddings from $\tau$ -banking BM25 retrieval using the Gemma solver (original versus evolved).

Figure 20: t-SNE visualization of the task embeddings from $\tau$ -banking golden retrieval using the Gemma solver (original versus evolved).

Failure type	Source Dataset	Description	Examples
Missing items	AppWorld	The agent failed to include or process some requested items.	If the instruction includes processing $N$ transactions, $N$ messages to friends, or $N$ downloads, the agent only processed a subset of $N$ successfully.
Commonsense error	AppWorld	Non-tool-call related errors	Calculation or sorting errors (e.g., asked to identify the largest item, but the agent chose the smaller item).
Constraint violation	AppWorld, Automation Bench, $\tau$ -bench, SWEBench	The agent did not respect specified constraints or priorities.	If the instruction says to only download songs by artist xyz, but songs not by this artist are downloaded; the instruction says to filter by some condition but that is not satisfied; or if the instruction has an "if-then" conditional, but the condition is not checked before executing then.
Incorrect data processing	AppWorld, GDPval	The agent processed the data incorrectly.	Incorrectly reading the last 4 digits of a credit card number; incorrect response data parsing or extraction.
Invalid APIs	AppWorld	The agent hallucinated input, made incorrect API names, or used an incorrect API	Agent uses an incorrect tool call or the returned tool call cannot be parsed into an existing tool or API name
Incompletion	AppWorld, GDPval	The agent failed to include or process some requested items, or followed some parts of the instruction while missing other details.	Agent returned the correct artist names but didn’t download their songs, when the instruction requested both answering the artist names and downloading their songs; or adding new items to the bucket list but not marking them as incomplete; or navigating to “photographs" folder instead of “pictures" after making filesystem changes

Appendix

Table 2: Taxonomy of solver failure modes. We used Gemini 3.6 Flash as an LLM judge to identify the most likely failure mode, based on the task instruction and a summary of the solver’s execution trace. This taxonomy was developed from human review of the original AppWorld benchmark, tasks generated using TURTLE , and from error analyses provided in prior benchmarks/papers: AppWorld ( Trivedi et al., 2024 ) , AuotmationBench ( Shepard and Salimans, 2026 ) ,

\tau

-banking ( Shi et al., 2026 ) , SWEBench ( Jimenez et al., 2024 ) , GDPval ( Patwardhan et al., 2025 ) , and FactoryBench ( Merzouki et al., 2026 ) .

AI Agent Benchmarks

AI agent benchmarks measure how reliably autonomous systems plan, use tools, interact, and complete tasks across controlled and real-world settings.

See all 1,497 papers

A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks
May 27, 2026Tomer Keren, Nitay Calderon, Asaf Yehudai +3Computer-Use Agent Benchmarks Tool-Use Evaluation
Faculty of Data and Decision Science Technion · IBM Research
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
The World Won't Stay Still: Programmable Evolution for Agent Benchmarks
Mar 6, 2026Guangrui Li, Yaochen Xie, Yi Liu +11AI Agent Benchmarks Agent Evaluation
Amazon · UC Berkeley

May 27, 2026J/K move · Enter open · S save

A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks

Tomer Keren, Nitay Calderon, Asaf Yehudai, Yotam Perlitz+2

Faculty of Data and Decision Science Technion · IBM Research

Computer-Use Agent Benchmarks Tool-Use Evaluation Tool-Augmented Language Model Agents Benchmark Construction LLM Agent Evaluation Synthetic Benchmark Generation+1

Open paper AskPDF arXiv

As agent capabilities advance, existing benchmarks, such as

τ^2

-Bench, are becoming increasingly saturated. Yet constructing new benchmark tasks remains complex, costly, and labor-intensive. Moreover, the standard approach, in which scenarios are first written in natural language and then mapped to tool sequences, captures only a narrow subset of the tool-use patterns agents exercise. In this paper, we address these problems by reversing the task construction process. We propose TASTE: Task Synthesis from Tool Sequence Evolution, an automatic method that generates challenging tasks with broader tool-use coverage. TASTE utilizes an Adaptive Contrastive

n

-gram model trained on LLM-judged validity signals. This enables sampling valid tool sequences that cover a vast range of tool combinations. TASTE then selects representative sequences from the pool via clustering, instantiates them into complete benchmark tasks, and refines them through iterative difficulty evolution. Using TASTE, we construct

τ^c

-Bench, a challenging extension of the three domains of

τ^2

-Bench. We evaluate

11

agent/user LLM pairs and find that models nearly saturating

τ^2

-Bench suffer severe performance drops on our tasks (e.g., Gemini-3-Flash falls from

0.82\!-\!0.94

0.28\!-\!0.61

). Beyond increasing difficulty, our generated tasks more than double the number of unique tool combinations agents must execute. Our results suggest high scores on existing benchmarks often reflect saturation rather than robust task-solving ability. By automating the generation of difficult, high-coverage benchmarks, TASTE enables continuous, scalable evaluation of future agents.

Abstract

AI Agent Benchmarks

Explore similar work

A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks

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

The World Won't Stay Still: Programmable Evolution for Agent Benchmarks