🤖 AI

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

To address the saturation and limited tool-use coverage of existing agent benchmarks, this paper introduces TASTE, an automated method that reverses the task construction process by evolving tool sequences to generate the challenging, high-coverage $\tau^c$ -Bench, which reveals that current state-of-the-art models suffer significant performance drops when faced with these more complex and diverse tasks.

Original authors: Tomer Keren, Nitay Calderon, Asaf Yehudai, Yotam Perlitz, Michal Shmueli-Scheuer, Roi Reichert

Published 2026-05-28

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Tomer Keren, Nitay Calderon, Asaf Yehudai, Yotam Perlitz, Michal Shmueli-Scheuer, Roi Reichert

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to test how good a new robot chef is at cooking.

The Problem: The "Easy Menu" is Exhausted
Right now, we have a standard test menu (called $\tau$ -Bench) where the robot has to follow instructions like "make a sandwich" or "order a pizza." The problem is that the smartest robot chefs have already memorized this menu. They get perfect scores, but it's not because they are geniuses; it's just because the test is too easy and repetitive. It's like a student who gets an A+ on a math test because the teacher only ever asks them to add single-digit numbers.

Also, making new, harder test questions is a nightmare. It requires humans to sit down, write complex stories, figure out the exact steps the robot needs to take, and check if the story makes sense. This is slow, expensive, and limits us to only the kinds of stories humans happen to think of.

The Solution: TASTE (The "Reverse Recipe" Machine)
The authors created a new system called TASTE (Task Synthesis from Tool Sequence Evolution). Instead of starting with a story and figuring out the steps, TASTE flips the process upside down.

Think of it like this:

The "Tool Sequence" (The Steps): First, the system generates thousands of random lists of actions, like "Open fridge, grab milk, pour glass, close fridge."
The "Plausibility Filter" (The Taste Test): It uses a super-smart AI judge to look at these lists and say, "No, that's impossible. You can't pour milk before you open the fridge," or "Yes, that's a valid sequence of events." It learns from its mistakes, getting better at spotting valid vs. invalid steps.
The "Clustering" (Grouping by Flavor): It groups these valid sequences together. If one group is all about "making breakfast" and another is "making a sandwich," it picks the most representative example from each group to ensure the test covers a wide variety of scenarios.
The "Evolution" (Spicing it Up): This is the secret sauce. Once it has a basic task (e.g., "Order a pizza"), it deliberately makes it harder. It might:
- Make the customer (the simulated user) forget their order details.
- Add "decoy" options to the menu that look right but are actually wrong (like a pizza that is sold out).
- Make the customer uncooperative or confusing.

The Result: $\tau^c$ -Bench
Using this method, they built a new, much harder test called $\tau^c$ -Bench.

When they tested the "champion" robot chefs (like Gemini-3-Flash) on this new menu, the results were shocking.

On the old, easy menu, these robots scored 0.90 (almost perfect).
On the new, TASTE-generated menu, their scores dropped to 0.30 or lower.

Why This Matters
The paper argues that the high scores on the old tests were a "false alarm." The robots weren't actually that good at solving complex, messy real-world problems; they just knew the old test questions by heart.

The new method proves that:

Coverage: The new tests force robots to use a much wider variety of tools and combinations, not just the same few tricks.
Difficulty: The tests are genuinely harder because they include confusion, missing information, and tricky scenarios.
Automation: We don't need humans to write these hard tests anymore. The system can generate an endless supply of challenging, valid, and diverse tasks to keep testing robots as they get smarter.

In short, TASTE is a machine that automatically invents "boss battles" for AI agents, ensuring we can tell the difference between a robot that has memorized a script and a robot that can actually think.

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

Problem Statement

As the capabilities of tool-using agents advance, existing benchmarks (such as $\tau^2$ -Bench) are becoming increasingly saturated, with leading models achieving near-ceiling performance. However, constructing new, more challenging benchmark tasks remains a complex, costly, and labor-intensive process reliant on manual authoring. Furthermore, the standard construction approach—where authors first write natural language scenarios and then derive tool sequences—fails to explicitly explore the space of valid tool combinations. Consequently, current benchmarks often capture only a narrow subset of tool-use patterns, leading to "saturation" where high scores reflect the lack of diverse challenges rather than robust task-solving abilities. There is an urgent need for automatic benchmark generation methods that can ensure Validity (tasks are solvable and verifiable), Difficulty (tasks meaningfully differentiate agent capabilities), and Coverage (tasks span structurally diverse tool-use patterns).

Methodology: TASTE

The authors propose TASTE (Task Synthesis from Tool Sequence Evolution), an automatic method for generating challenging agent benchmark tasks by reversing the traditional construction process. Instead of starting with scenarios, TASTE starts with tool sequences and synthesizes full tasks around them. The method operates in three stages:

Stage 1: Tool Sequence Sampling

To address Coverage and Validity, TASTE employs an Adaptive Contrastive n-gram model trained on the space of tool sequences.

Model Architecture: The model maintains separate count tables ( $C^+$ and $C^-$ ) for n-grams observed in "plausibly valid" and "implausibly valid" sequences, respectively.
Training: It uses an iterative generate-and-validate loop. Sequences are sampled autoregressively and judged by a Large Language Model (LLM) for plausibility. Valid sequences update $C^+$ , while invalid ones update $C^-$ .
Contrastive Sampling: The sampling probability for the next tool is derived from the ratio of the positive and negative scores, penalizing n-grams associated with invalid sequences. This allows the model to explore the tool-combination space while concentrating probability mass on valid sequences.

Stage 2: Clustering and Selection

To ensure the benchmark represents diverse patterns without redundancy, TASTE selects a representative subset of sequences from the sampled pool.

Clustering: The authors use K-medoids clustering to partition the pool of thousands of candidate sequences into $K$ clusters (where $K$ is the target benchmark size).
Distance Metric: A weighted Levenshtein distance is used instead of standard edit distance. Substitution costs are lower for tools with similar functions or types (e.g., two search tools) and higher for tools with different types (read vs. write). This ensures clusters are semantically coherent.
Selection: The medoid (central sequence) of each cluster is selected as a representative. Invalid medoids are replaced by the next closest valid member of the cluster.

Stage 3: Task Generation and Evolution

Each selected tool sequence is instantiated into a complete benchmark task and then evolved to increase Difficulty.

Base Task Generation: An LLM constructs a coherent real-world scenario (user instruction $u$ ) and initializes the database state ( $s_0$ ) to support the specific tool sequence.
Validity Verification: Tasks undergo rule-based checks and a hint-assisted verifier agent simulation. The verifier attempts to solve the task using a shuffled and partially masked version of the gold tool sequence. Success confirms the task is solvable.
Difficulty Evolution: To simulate realistic, adversarial conditions, the base task is evolved through three steps:
1. Strategy Analysis: Identifying opportunities for confusion (e.g., policy violations, ambiguous requests).
2. Environment Perturbation: Adding "decoy" database records (e.g., a fully booked flight on a desired route) that look similar to the target but are invalid.
3. Scenario Rewriting: Rewriting the user instruction to be less cooperative, ambiguous, or adversarial, forcing the agent to navigate confusion while adhering to policy.

Key Contributions

Desiderata for Benchmarks: The paper articulates and operationalizes three critical properties for tool-using agent benchmarks: Validity, Difficulty, and Coverage. Crucially, it defines Coverage in terms of the diversity of gold tool sequences rather than superficial linguistic variation.
TASTE Framework: The proposal of TASTE, a fully automated pipeline that explores the tool-sequence space directly to generate tasks that satisfy the three desiderata without manual curation.
$\tau^c$ -Bench: The construction of $\tau^c$ -Bench, a challenging extension of $\tau^2$ -Bench across three domains (Airline, Retail, Telecom). This dataset features significantly higher difficulty and broader coverage than its predecessor.

Results

The authors evaluated 11 agent/user LLM pairs on $\tau^c$ -Bench and compared them to performance on the original $\tau^2$ -Bench (Verified version, $\tau_{BV}$ ).

Performance Drop: Models that nearly saturated $\tau_{BV}$ suffered severe performance drops on $\tau^c$ -Bench. For example, Gemini-3-Flash dropped from a score of 0.82–0.94 on $\tau_{BV}$ to 0.28–0.61 on $\tau^c$ -Bench (a relative drop of up to 80%).
Increased Difficulty: The evolved tasks were significantly harder, with success rates dropping by 16–55% depending on the evolution model used.
Expanded Coverage: $\tau^c$ $τ^{c}$ -Bench more than doubled the number of unique tool combinations agents must execute.
- Weighted Edit Distance (WED): Increased by up to 124%.
- Type-Token Ratio (TTR): Increased by up to 111%, indicating a much higher diversity of n-gram tool sequences.
- Entropy: Tool-frequency distribution entropy increased by 35%, showing a less skewed, more diverse usage of tools.

Significance and Claims

The paper claims that high scores on existing benchmarks often reflect saturation rather than robust task-solving ability. By demonstrating that state-of-the-art models struggle significantly with the TASTE-generated tasks, the authors argue that current benchmarks fail to capture the full complexity of tool-use patterns.

The significance of TASTE lies in its ability to automate the generation of difficult, high-coverage benchmarks, enabling continuous and scalable evaluation of future agents. By reversing the construction process to prioritize tool sequences, TASTE ensures that benchmarks explore the structural diversity of agent behaviors rather than relying on arbitrary author choices. The authors position this work as a necessary step to prevent evaluation stagnation as agent capabilities continue to advance.