Source-linked AI summary
A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks
Tomer Keren, Nitay Calderon, Asaf Yehudai, Yotam Perlitz, Michal Shmueli-Scheuer, Roi Reichart
TL;DR
Existing tool-agent benchmarks are costly to construct, increasingly saturated, and limited in their coverage of tool-use patterns. TASTE reverses task construction by sampling and clustering tool sequences before generating and evolving tasks; on τ c-Bench, nearly saturated models show substantial performance drops while tool-combination coverage expands.
Problem
Existing benchmarks face costly manual construction, accelerating saturation, and limited coverage because natural-language-first authoring does not explicitly explore tool-sequence space.
Method
TASTE samples tool sequences with an Adaptive Contrastive n-gram model, selects representatives by clustering, and instantiates and evolves them into validated tasks.
Results
τ c-Bench is consistently harder and broader than τ 2-Bench, with Gemini-3-Flash dropping from 0.82–0.94 to 0.28–0.61 and coverage metrics increasing substantially.
Takeaways & Limitations
TASTE provides an automatic route to generating difficult benchmarks with broader tool-use coverage and exposes performance gaps in saturated evaluations.
Takeaways & Limitations
The evaluation uses final-state reward alone, which overlooks trajectory-level properties such as efficiency, intermediate rewards, and interaction quality.
Abstract
from arXiv · showhide
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.
1 Introduction
Existing tool-using-agent benchmarks are costly to construct and increasingly saturated, while natural-language-first authoring explores only arbitrary tool combinations. TASTE reverses construction by sampling tool sequences first, then synthesizing and refining tasks to improve validity, difficulty, and coverage.
- Manual benchmark construction requires writing instructions, configuring environments, deriving tool calls, and verifying reachable target states.
- Coverage is defined through structurally diverse gold tool sequences rather than superficial variation in instructions or initial states.
- TASTE samples diverse tool sequences before instantiating them into complete benchmark tasks, reversing the prevailing scenario-first process.
- Its Adaptive Contrastive n-gram model uses LLM-judged plausibility signals and online count updates to explore valid regions of tool-sequence space.
- K-medoids clustering selects representative sequences, after which tasks are instantiated and evolved to increase challenge while preserving benchmark construction goals.
- Agents scored up to 80% worse on τ c-Bench than τ 2-Bench, while weighted edit distance, TTR, and tool-frequency entropy increased by up to 124%, 111%, and 35%.
2 Evaluating Conversational Tool-Using Agents
Conversational tool-using agents jointly shape action trajectories, environment state, and final outcomes, making evaluation more demanding than standard input-output assessment. The benchmark framework therefore formalizes tasks, final-state rewards, and desiderata for validity, coverage, and difficulty.
- Conversational tool use replaces static prompts with continuous interaction between an evaluated agent and a simulated user.
- Task success is evaluated from the resulting world state after both agents’ tool calls and messages have shaped the trajectory.
- Validity requires automatic verifiability and a correct, reachable gold final state consistent with the task specification.
- Invalid tasks can penalize agents for benchmark defects rather than genuine capability limitations.
- Coverage focuses on structurally different gold tool sequences and can be quantified with tool-edit distance or unique tool n-grams.
- Difficulty should distinguish capability levels without making all tasks either too easy or too hard.
3 TASTE: Task Synthesis from Tool Sequence Evolution
TASTE generates benchmark tasks around sampled tool sequences through adaptive validity modeling, representative selection, task instantiation, and difficulty evolution. The pipeline combines diverse candidate generation with validation and correctness-preserving refinement.
- TASTE is a three-stage pipeline targeting benchmark validity, coverage, and difficulty through tool-sequence-centered task generation.
- Tool Sequence Sampling: The Adaptive Contrastive n-gram model learns from plausible and implausible sequences, updating online with LLM-judged validity labels.
- Tool Sequence Sampling: Negative evidence penalizes local tool patterns associated with invalidity, while temperature-annealed contrastive scores guide sampling.
- Clustering and Selection: From N = 2000 candidates, K-medoids selects K representative sequences, using weighted edit distance to reflect semantic and functional tool similarity.
- Validation: Invalid medoids are replaced or reclustered, and evolved tasks are revalidated with simpler variants or base-task fallback when necessary.
- Task Generation and Evolution: Each selected sequence becomes a verifiable base task, and task evolution increases difficulty while preserving the gold tool-call sequence.
4 Experimental Setup
The evaluation extends τ 2-Bench Verified across Airline, Retail, and Telecom, using the original task counts and conversational agent–user pairings. Results are reported with final-state pass scores, while generation and evaluation incur distinct costs.
- τ c-Bench extends Airline, Retail, and Telecom using 50, 114, and 114 tasks respectively from τ 2-Bench Verified.
- TASTE trains a trigram model for 3,000 iterations and samples unique sequences with lengths capped at 15.
- The evaluation pairs six agent LLMs with two user simulators and reports final-state pass^1 scores, plus pass^3 for Airline.
- Stages 1 and 2 cost approximately $10 per domain, while Stage 3 costs approximately $2.50 per task.
- Generating τ c-Bench costs $725 in total, and evaluation costs $520 across agent–user pairs.
5 Results
TASTE produces τ c-Bench tasks that are substantially harder and more diverse than τBV, while its validation and evolution procedures support reliable, controllable benchmark construction.
- Main Results: Performance drops by 5%–80% relative to τBV across 11 agent–user pairs and three domains.Gemini-3-Flash falls from 0.82–0.94 on τBV to 0.28–0.61 on τ c-Bench.
- Harder Tasks with Broader Coverage: WED increases by up to 124%, TTR by up to 111%, and tool-frequency entropy by 35% over τBV.These gains indicate more varied execution paths and less-skewed tool usage.
- Method Analysis: The full Adaptive Contrastive n-gram Model reaches 86.7% validity versus 6.7% for uniform tool sampling.Adaptive training and contrastive negative evidence each improve validity during ablation.
- Method Analysis: Figure 3 compares sequence acceptance across model stages with agent success on base versus evolved tasks.The left panel concerns the Airline domain, and the right panel uses Gemini-3-Flash as the user simulator.
- Method Analysis: The verifier has near-perfect precision but lower recall, achieving precision of 1.0 and 0.97 and recall of 0.75 and 0.83 in Airline and Retail.Manual examination found all 15 tasks where no evaluated pair succeeded to be valid.
- Creating Difficult Tasks: Evolved tasks reduce success rates by 36–55% when evolved by Gemini-3 and 16–37% when evolved by GPT-5.2.Longer tasks are 30% harder on average, while write-heavy tasks are 43% harder.
6 Related Work
Related benchmarks span single-turn tool selection, persistent multi-turn environments, and conversational agents evaluated through final environment states. TASTE instead measures procedural diversity directly through tool sequences, addressing limitations of tool- and schema-level summaries.
- Benchmark Scope: Tool-use benchmarks range from single-turn API selection and argument grounding to multi-turn interactions in persistent environments.This paper focuses on conversational agents interacting with simulated users over mutable environments.
- Synthetic Generation: Synthetic task generation has used seed bootstrapping, tool-description synthesis, insertion filtering, verification, blueprints, simulation, role-playing, and trajectory feedback.TASTE is positioned among methods that automate multi-turn tool-use benchmark construction.
- Coverage Definition: Existing benchmark summaries often count domains, tools, or schemas without showing whether tasks exercise diverse procedural tool-use patterns.Such summaries indicate available tools but not the diversity of required execution sequences.
- Coverage Definition: Sequence-level coverage measures whether a benchmark explores varied agent behaviors rather than repeatedly testing similar patterns.The paper applies diversity measures from NLP to gold tool sequences instead of words.
7 Conclusions
The paper introduces TASTE for automatically generating difficult, broad-coverage tool-use benchmarks and demonstrates its value with τ c-Bench. The approach is focused on conversational agents but can extend to other settings.
- Conclusions: TASTE automatically generates benchmark tasks that are difficult and cover a broad range of tool-use patterns.It constructs tasks from tool sequences and environment specifications.
- Conclusions: τ c-Bench extends τ 2-Bench, and models nearly saturating the original benchmark show performance drops on the generated tasks.The evaluation focuses on conversational tool-using agents.
- Scope and Future Work: TASTE is readily adaptable to single-turn and non-conversational settings because it operates on tool sequences and environment specifications.The paper also identifies future applications to training-data generation and additional coverage and difficulty axes.
A Additional Results
Additional analyses show that τ c-Bench uses broader, more even tool distributions and that sequence structure provides meaningful difficulty controls. The diagnostics also compare gold action lists with representative successful agent trajectories and show weighted clustering improves semantic coherence.
- Sequence-level diagnostics: Table 2 compares gold action lists with GoldSim sequences, selecting the shortest successful trajectory per task and falling back to gold when no successful run exists.GoldSim pools simulations across agents, user simulators, and trials, filters unsuccessful runs, and preserves one sequence per task.
- Difficulty controls: 13–20 pp accuracy gaps separate short from long golden-sequence buckets across all three domains.Tasks are bucketed using µ ± 0.5σ thresholds, with the middle band dropped.
- Difficulty controls: 16–31 pp accuracy gaps separate read-heavy from write-heavy buckets in airline and retail, while telecom is excluded because every task has write-ratio 1.0.Write-ratio therefore functions as a difficulty axis only where the evaluation criteria distinguish read and write actions.
- Tool-usage coverage: τ c-Bench spreads tool usage more evenly than τBV, increasing normalized entropy across the retail and telecom comparisons.Telecom compares only 21 of 43 write-action tools, with both distributions re-normalized over that subset.
- Clustering quality: Weighted edit distance yields semantically coherent clusters, whereas regular edit distance mixes unrelated tool subsequences.Under weighted distance, inter-medoid distances are 3.66–4.66 and nearest neighbors remain close in intent.
B Implementation Details
Stage 1 trains an adaptive contrastive trigram sampler by repeatedly generating and validating tool sequences. Valid sequences reinforce positive n-grams, while invalid sequences contribute targeted negative evidence, with deduplication and seed initialization supporting iterative refinement.
- Stage 1 overview: TASTE’s Stage 1 is implemented as a separate process whose trained sampler and count tables feed later stages.The overall pipeline uses separate artifact-communicating processes, and the training loop runs for 3,000 generation attempts.
- Model: The sampler uses a trigram model with Dirichlet smoothing λ0 = 0.1 and negative-evidence weight λneg = 1.Tool identifiers are the available tokens, while BOS and EOS are reserved and never emitted.
- Temperature schedule: An exponentially decaying temperature starts at T0 = 3.0 with τdecay = 1500, and the iteration counter advances once per generation attempt.The schedule controls sampling temperature over the training loop.
- Sequence generation: Candidate lengths follow a skew-normal distribution with location 7, scale 5, skewness 2.0, and hard clipping to integers in [1, 15].Sequences are generated autoregressively after prepending two BOS tokens until the sampled length is reached.
- Validation and updates: An LLM plausibility validator labels each candidate valid or invalid and identifies problematic indices for invalid sequences.Valid candidates increment every extracted n-gram in C+, while invalid candidates increment only windows ending at problematic indices in C−.
- Initialization: Before training, original-task gold sequences are validated and ingested as seeds into the positive or negative count tables.Duplicate generated sequences are skipped without updating either table, although the iteration counter still advances.
B.2 Stage 2: Clustering and Selection
Stage 2 samples a large pool of unique sequences, clusters them with a type-aware weighted edit distance, and validates representative medoids. Invalid representatives are replaced or reclustered while accepted medoids remain fixed.
- Pool generation: Stage 2 samples 2,000 unique sequences at temperature Tpool = 1.5 before clustering.The pool uses the same skew-normal length distribution as Stage 1.
- Distance metric: Weighted Levenshtein distance assigns insertion and deletion cost 1 and substitution costs from 0 to 1 according to tool identity, type, and group.Matching tools cost 0; same-type same-group substitutions cost 0.33, same-type different-group substitutions 0.66, and different-type substitutions 1.00.
- Distance metric: Tool types are READ, WRITE, or GENERIC, with GENERIC treated as READ for type comparison, while groups use the prefix before the first underscore.For example, search_direct_flight belongs to the search group.
- Clustering quality: On airline examples, weighted distance keeps within-cluster distances at 1.0–3.98 while the smallest between-medoid distance is 5.31.The resulting clusters align with service intents and absorb cosmetic sequence variants.
- Clustering: K-medoids uses K = 50 for airline and K = 114 for retail and telecom, matching the domains’ seed-task counts.Initialization uses k-medoids++, followed by PAM-style assignment and update iterations.
- Medoid validation: Each medoid is validated, replaced by the nearest plausible cluster member when invalid, or handled through constrained reclustering if no plausible member exists.Previously accepted medoids are frozen during reclustering, while new free centers are selected for unusable clusters.
B.3 Stage 3: Task Generation and Evolution
Stage 3 turns plausible medoids into validated base tasks and harder evolved variants through scenario construction, database initialization, adversarial strategy, and repair-driven validation. The implementation specifies reproducible algorithms, verifier settings, and fallback behavior for failed evolution.
- Pipeline: Each plausible medoid is instantiated as a base task and then evolved into an adversarial variant, with both stages passing through validity checks.The stage emits one evolved task per cluster in the τ2-Bench task schema.
- Base task generation: Base-task generation uses one LLM call for a coherent scenario and user instruction, followed by another that initializes the required database entities.The entities are merged into the base environment state s0.
- Validation: Validity checks require specified arguments, existing entities, schema-conforming state, successful gold execution, policy coherence, and verifier-agent simulation.The pipeline combines rule-based, LLM-based, and simulation-based checks and short-circuits on failure.
- Validation: The verifier shuffles gold tool calls and drops a random 30% of arguments, accepting tasks when hinted simulation achieves reward 1.0.This avoids both direct transcription from fully specified hints and the difficulty of running without hints.
- Task evolution: Evolution selects techniques for each WRITE action, defines conditional user branches, and constructs database decoys before rewriting the user instruction.The catalog includes DB-grounded misdirection and policy-enforcement patterns.
- Repair and fallback: Failed checks trigger feedback-driven repair, while repeated evolution failures invoke a lite fallback and ultimately retain the original base task.This graduated fallback keeps the final task set complete while allowing partial difficulty enhancement.
- Configuration: The reported implementation uses fixed algorithmic stages and records verifier-agent redaction p = 0.3, two simulation attempts, and three lite-fallback retries.Hyperparameters and model/API mappings are consolidated in the implementation tables.
Airline task#1
The Airline task tests an agent’s ability to handle a complex sequence involving multiple reservations, airport availability, and delay compensation.
- The task combines reservation modifications, airport-availability checks, and delay-compensation processing.
Retail task#113
The Retail task tests an agent’s ability to coordinate profile updates, order inquiries, and product comparisons.
- The task combines multiple profile updates with order inquiries and product comparisons.
Telecom task#3
The Telecom task tests service-interruption handling by combining device-side troubleshooting with backend billing management. Its construction pipeline validates action sequences against domain policies and tool specifications.
- The task combines device-side troubleshooting with backend billing management for a service interruption.
- The sequence is designed around the cluster labeled “Search, Book, and Update.”
- One representative sequence searches for a direct flight, lists airports, books a reservation, and updates passenger information.
- The validation pipeline checks action names, sequence structure, logical ordering, policy compliance, and solvability.
- Scenario generation requires exact tool arguments, valid system limits, correct actor assignments, and properly formatted calculations.
- Structural validation also checks referential integrity, required fields, exact enums, numeric types, economic consistency, dynamic entities, and dual-database consistency.
NeurIPS Paper Checklist
The checklist review reports that the paper’s claims and limitations are addressed, while also considering reproducibility, statistical reporting, compute resources, ethics, and societal impact.
- The paper’s stated contributions and scope are judged to match its abstract, introduction, formalization, pipeline, and three-domain evaluation.
- The paper discusses its limitations in the Method and Results sections.
- The checklist recommends articulating strong assumptions, robustness to violations, claim scope, and factors influencing empirical performance.
- The paper is expected to provide reproducibility instructions, access and preparation details, and scripts for experimental results.
- The statistical-significance guidance requires suitable error bars, confidence intervals, or significance tests with clearly stated variability and calculation methods.
- The review states that experiments use external LLM APIs and therefore identifies API cost as the relevant resource.
- The paper is described as involving synthetic data, no human subjects, no personally identifiable or scraped data, and no prohibited application areas.
- The checklist asks authors to consider possible negative societal impacts and mitigation strategies.