A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks
Tomer Keren, Nitay Calderon, Asaf Yehudai, Yotam Perlitz, Michal Shmueli-Scheuer, Roi Reichart · 2026
Read A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks by Tomer Keren, Nitay Calderon, Asaf Yehudai, Yotam Perlitz, Michal Shmueli-Scheuer, Roi Reichart (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-28556.txt.
Introduction
Tomer Keren and five colleagues reverse agent-benchmark construction to beat saturation: instead of writing scenarios then mapping them to tools, they start from tool sequences. Their TASTE method samples valid tool sequences with an adaptive contrastive n-gram model fit on language-model validity judgments, clusters representatives, and evolves difficulty iteratively. The resulting tau-c-Bench extends three domains of tau-2-Bench with far broader tool coverage. Models near saturation on the old benchmark drop sharply on the new tasks, suggesting high scores reflected saturation more than robust skill.
Catalog record
| CREATOR | Tomer Keren, Nitay Calderon, Asaf Yehudai, Yotam Perlitz, Michal Shmueli-Scheuer, Roi Reichart |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94064 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.28556
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks Tomer Keren, Nitay Calderon, Asaf Yehudai, Yotam Perlitz, Michal Shmueli-Scheuer, Roi Reichart Abstract As agent capabilities advance, existing benchmarks, such as τ 2 \tau^{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 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 \tau^{c} -Bench, a challenging extension of the three domains of τ 2 \tau^{2} -Bench. We evaluate 11 11 agent/user LLM pairs and find that models nearly saturating τ 2 \tau^{2} -Bench suffer severe performance drops on our tasks (e.g., Gemini-3-Flash falls from − 0.94 0.82\!-\!0.94 to − 0.61 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. 1 1 1 The code for TASTE and the τ c \tau^{c} -Bench data are available at GitHub repo . 1 Introduction Tool-using agents interact with and modify external environments through tool invocations [ 24 ] , such as executing code [ 36 , 2 ] , legal complaint drafting, managing customer accounts, or placing orders [ 30 , 9 , 35 ] . Unlike standard input-output systems, tool-using agents operate through multi-step actions that evolve the world state, making evaluation dependent not on any single response but on the cumulative effect of the entire interaction [ 38 ] . A natural evaluation paradigm, adopted by benchmarks such as \tau -Bench [ 37 , 1 ] , is final-state evaluation: a task is solved if the world state at termination matches a target state induced by a gold tool-call sequence. Constructing benchmarks under this paradigm is particularly demanding. Authoring even a single task involves writing natural-language instructions, configuring the environment, deriving the correct sequence of tool calls, and verifying that the target state is both consistent and reachable [ 5 , 42 ] . At the same time, agent capabilities are advancing rapidly, and leading models are approaching the ceiling of existing benchmarks [ 38 , 37 , 1 , 22 , 20 , 40 , 8 ] . The combination of costly manual construction and accelerating saturation creates an urgent need for automatic benchmark generation [ 4 , 19 ] . However, effective automation first requires identifying the properties a good benchmark should satisfy and how to measure them. Our paper begins by proposing three desiderata for benchmarks of tool-using agents. Validity requires every task to be both automatically verifiable and correct in that the gold final state is reachable from the task specification. Difficulty requires tasks to meaningfully separate agents of different capability levels. Coverage requires benchmark tasks to span structurally diverse patterns of tool use rather than oversampling redundant scenarios. Among these three, coverage has received the least attention and lacks a clear operationalization [ 17 ] . In this paper, we define it through the lens of tool sequences: the ordered list of tool names in the gold trajectory leading to the target state. Framing coverage in terms of tool sequences also opens a constructive pathway: if the space of valid tool sequences can be explored and sampled directly, it becomes possible to design an automatic method for task generation that explicitly targets all three desiderata. Figure 1: Illustration of TASTE, our three-stage method for synthetic task generation. We demonstrate the method across the three domains of \tau^{2} -Bench (Verified, \tau\text{BV} ). Evaluating a Gemini-3-Flash agent (averaged over two different user LLMs) shows that, unlike \tau\text{BV} , \tau^{c} -Bench is non-saturated. Besides being more challenging, \tau^{c} -Bench exhibits broader coverage, requiring agents to exercise a more diverse set of tool combinations, as quantified by the type-token ratio (TTR; see § 5 ). We propose to reverse the task construction process entirely. The prevailing approach involves an author who first writes a natural-language scenario and then derives the corresponding tool sequence. Because the tool-sequence space is never explicitly explored, the resulting benchmarks exercise only arbitrary tool combinations that vary with author choice [ 17 ] . Accordingly, rather than starting from scenarios and recovering tool sequences, we sample a diverse set of tool sequences and synthesize the full tasks around them. We instantiate this idea and propose TASTE ( Ta sk S ynthesis from T ool Sequence E volution) , an automatic method for task generation comprising three stages, each targeting one or more of these desiderata. TASTE is illustrated in Figure 1 . In the first stage, we train an Adaptive Contrastive n -gram model over the space of tool sequences. The model maintains separate count tables for n -grams (units are tools) observed in plausibly valid and implausibly valid sequences, as judged by an LLM, and computes sampling probabilities from their contrastive ratio. Counts are updated online through iterative sample-and-validate loops, progressively refining the distribution. This targets validity by concentrating probability mass on valid tool sequences, and coverage by exploring regions of the tool-combination space. The second stage selects a representative subset of K (the benchmark size) sequences from the sampled pool using K -medoids clustering [ 18 ] . We employ a weighted Levenshtein distance that reflects semantic and functional similarity between tools. In the third stage, each selected tool sequence is instantiated into a complete benchmark task (user instruction, database records, tool arguments). Following rule-based checks, we employ a hint-assisted verifier agent to ensure the task is actually solvable: we provide a corrupted version of the gold tool-call sequence (tools are shuffled, arguments are masked), requiring the agent to cooperate with the simulated user to reach the target state. A final evolution step targets interaction difficulty : making the user ambiguous and less cooperative, and introducing confusing decoy records to the database (e.g., a fully booked flight on the desired route). Using TASTE, we construct \tau^{c} -Bench, a challenging extension of the three domains of \tau^{2} -Bench [ 1 ] : Airline, Retail, and Telecom ( K\!=50\!/114\!/114 respectively). We then evaluate 11 agent/user LLM pairs across all three domains. We find performance on our \tau^{c} -Bench is consistently and substantially lower than on the original \tau^{2} -Bench, with agents scoring up to 80\% worse. The degradation is particularly striking for models that appear to have nearly saturated the \tau^{2} -Bench: Gemini-3-Flash achieves 0.82\!-\!0.94 on the original yet drops to 0.28\!-\!0.61 on ours. Beyond increased difficulty, our benchmark more than doubles the number of