Paper 2605.28556
A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks
- Published
- May 2026
- Research lab
- Independent
- Citations
- 0
- GitHub
- 4 stars
01 In brief
Summary
The paper introduces TASTE (Task Synthesis from Tool Sequence Evolution), an automatic method for generating challenging agent benchmarks with broader tool-use coverage.
TASTE reverses the traditional task construction process by first sampling diverse tool sequences using an Adaptive Contrastive n-gram model trained on LLM-judged validity signals, then selecting representative sequences via K-medoids clustering with a weighted edit distance, and finally instantiating and evolving these into complete tasks.
The authors construct τ^c-Bench, an extension of τ^2-Bench across Airline, Retail, and Telecom domains.
Evaluating 11 agent/user LLM pairs, they find that models nearly saturating τ^2-Bench suffer severe performance drops on τ^c-Bench (e.g., Gemini-3-Flash drops from 0.82–0.94 to 0.28–0.61).
The generated tasks also more than double the number of unique tool combinations, with weighted edit distance increasing by up to 124% and type-token ratio by up to 111%.
The results suggest high scores on existing benchmarks often reflect saturation rather than robust task-solving ability, and TASTE enables continuous, scalable evaluation of future agents.
02 From the paper
Abstract
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$ to $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.