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

High Scores Are Lying to You: The Case for Better Agent Benchmarks

If you have ever deployed a tool-using agent and watched it confidently hallucinate a database update, you know that high benchmark scores are often a mirage. Most current evaluations involve writing a story and then mapping it to a tool sequence. This process only explores a tiny sliver of how agents actually behave. This paper argues that we aren't measuring intelligence. We are measuring how well models have memorized the narrow, predictable patterns of existing benchmarks.

The core problem is that as agent capabilities advance, benchmarks like $\tau^2$-Bench are becoming saturated (reaching a ceiling where improvement is no longer measurable). Standard benchmark construction is a manual, labor-intensive process. Humans write natural-language scenarios first and derive tool sequences second. Because the tool-sequence space is effectively infinite, human authors oversample redundant, simple patterns. This creates a saturation effect. Leading models achieve near-perfect scores not because they are robust, but because the test is too shallow to catch their failure modes.

The Problem

Current benchmark construction is backwards. By starting with a narrative, we limit the "coverage"—the variety of tool combinations and procedural structures—that an agent actually faces. This leads to benchmarks that lack structural diversity. As shown in, existing benchmarks often exhibit skewed tool-usage distributions.

This means agents are repeatedly tested on the same few combinations.

Furthermore, benchmarks lack "difficulty" regarding interaction complexity. Most tasks are straightforward. The user asks for something, and the agent does it. There is little room for ambiguity, adversarial behavior, or environmental noise. This lack of friction means that once a model learns the "happy path" (the simplest successful sequence) for a specific domain, its score plateaus. We end up with a false sense of security. We believe an agent is production-ready when it has merely mastered a very limited subset of possible interactions.

How It Works

The authors propose TASTE (Task Synthesis from Tool Sequence Evolution). This method reverses the traditional construction process. Instead of starting with a story, TASTE starts with the tool sequences themselves. The architecture consists of three distinct stages :

1. Tool Sequence Sampling: The system uses an Adaptive Contrastive n-gram model to sample valid tool sequences. The model maintains two separate count tables ($C^+$ and $C^-$) for sequences judged as "plausible" or "implausible" by an LLM. By sampling from the contrastive ratio (the mathematical difference between these tables), the model concentrates probability mass on valid sequences. It also aggressively explores new, diverse combinations.
2. Clustering and Selection: To avoid redundant tasks, the system filters the pool using K-medoids clustering (a method that partitions data into groups and picks a central representative). Crucially, the authors use a weighted Levenshtein distance (a metric calculating the minimum changes to transform one sequence into another). This metric accounts for the semantic similarity of tools. Replacing two different "read" tools costs less than replacing a "read" tool with a "write" tool. This ensures clusters are functionally coherent .
3. Task Generation and Evolution: Each representative sequence (the "medoid") is turned into a full task. First, an LLM generates a coherent scenario and a matching database state. Then, the system enters an "evolution" phase. It analyzes the sequence to find opportunities for adversarial friction. This includes introducing decoy database records or making the user persona ambiguous. This turns a "base task" into a high-difficulty challenge .

Numbers

The results suggest that current leaderboards are significantly inflated. The authors evaluate 11 agent/user LLM pairs on their new $\tau^c$-Bench. They find that models nearing saturation on $\tau^2$-Bench suffer catastrophic performance drops. For example, Gemini-3-Flash moves from a high of 0.82–0.94 on the original benchmark to as low as 0.28–0.61 on the TASTE-generated tasks. This indicates the model's perceived competence was tied to the ease of the old benchmark.

Beyond mere difficulty, the authors demonstrate a massive leap in coverage. They report that $\tau^c$-Bench more than doubles the number of unique tool combinations. Specifically, the Type-Token Ratio (TTR)—a metric representing the proportion of unique n-grams in a sequence—increases by up to 111% . The weighted edit distance (WED) between sequences also jumps by up to 124%. This proves the benchmark covers a much wider breadth of procedural logic. The cost of this automation is relatively low. Generating the full $\tau^c$-Bench cost approximately \$725. Individual task evolution costs roughly \$2.50 per task.

What's Missing

There are gaps a practitioner should note. First, the entire pipeline relies heavily on LLM-based verifiers. The paper notes that the verifier agent has a recall of 0.75 to 0.83 .

Recall refers to the ability to find all valid tasks. While the precision is near-perfect, the system likely rejects many truly valid tasks. This happens because the "judge" LLM is not smart enough to recognize them. If your agent operates in a highly nuanced domain, you cannot rely solely on this automated gatekeeper.

Second, the "adversarial" nature of the evolution is bounded by a specific catalog of patterns. While it handles decoys and ambiguity well, it is unclear how the system handles truly novel edge cases. These are cases not explicitly modeled in the "Strategy Analysis" phase. Finally, the paper focuses on conversational tool-use. While the authors claim TASTE is domain-agnostic, moving from structured tool sequences to high-fidelity, multi-turn dialogue is a significant leap.

Should You Prototype This

Yes, but specifically for your evaluation pipeline, not your agent's logic. If you are shipping agents that interact with complex APIs, do not trust a "90% success rate" on a hand-written test suite. The TASTE approach provides a blueprint for building a custom, automated "stress tester." This tester can grow in difficulty as your models improve. The cost-to-benefit ratio is excellent. For a few hundred dollars in API credits, you can generate a benchmark that is significantly more rigorous than manual curation. Don't use this to train your models. Use it to find out exactly where they break.

Figures from the paper