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

arXiv: https://arxiv.org/abs/2605.28556 · HTML: https://mlsanity.com/paper/2605.28556/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Tool learning and function calling, one of 16 directions in LLM agents and tool use.
- Builds on 38 of its 111 references that are in the map.
- First posted on arXiv 27 May 2026.

## Placed in

- LLM agents and tool use / [Tool learning and function calling](https://mlsanity.com/agents/tool-learning-and-function-calling/)

## Builds on (most cited first, 30 of 38)

- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Self-Instruct: Aligning Language Models with Self-Generated Instructions](https://mlsanity.com/paper/2212.10560/) (2022)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [WizardLM: Empowering large pre-trained language models to follow complex instructions](https://mlsanity.com/paper/2304.12244/) (2023)
- [τ2-Bench: Evaluating Conversational Agents in a Dual-Control Environment](https://mlsanity.com/paper/2506.07982/) (2025)
- [API-Bank: A Comprehensive Benchmark for Tool-Augmented LLMs](https://mlsanity.com/paper/2304.08244/) (2023)
- [Unnatural Instructions: Tuning Language Models with (Almost) No Human Labor](https://mlsanity.com/paper/2212.09689/) (2022)
- [ToolAlpaca: Generalized Tool Learning for Language Models with 3000 Simulated Cases](https://mlsanity.com/paper/2306.05301/) (2023)
- [ToolSandbox: A Stateful, Conversational, Interactive Evaluation Benchmark for LLM Tool Use Capabilities](https://mlsanity.com/paper/2408.04682/) (2024)
- [ToolQA: A Dataset for LLM Question Answering with External Tools](https://mlsanity.com/paper/2306.13304/) (2023)
- [Survey on Evaluation of LLM-based Agents](https://mlsanity.com/paper/2503.16416/) (2025)
- [APIGen: Automated Pipeline for Generating Verifiable and Diverse Function-Calling Datasets](https://mlsanity.com/paper/2406.18518/) (2024)
- [APIGen-MT: Agentic Pipeline for Multi-Turn Data Generation via Simulated Agent-Human Interplay](https://mlsanity.com/paper/2504.03601/) (2025)
- [Evaluation and Benchmarking of LLM Agents: A Survey](https://mlsanity.com/paper/2507.21504/) (2025)
- [Evaluating the Evaluation of Diversity in Natural Language Generation](https://mlsanity.com/paper/2004.02990/) (2020)
- [How much do language models copy from their training data? Evaluating linguistic novelty in text generation using RAVEN](https://mlsanity.com/paper/2111.09509/) (2021)
- [Establishing Best Practices for Building Rigorous Agentic Benchmarks](https://mlsanity.com/paper/2507.02825/) (2025)
- [TOUCAN: Synthesizing 1.5M Tool-Agentic Data from Real-World MCP Environments](https://mlsanity.com/paper/2510.01179/) (2025)
- [SkyRL-Agent: Efficient RL Training for Multi-turn LLM Agent](https://mlsanity.com/paper/2511.16108/) (2025)
- [DeepScholar-Bench: A Live Benchmark and Automated Evaluation for Generative Research Synthesis](https://mlsanity.com/paper/2508.20033/) (2025)
- [AutoCodeBench: Large Language Models are Automatic Code Benchmark Generators](https://mlsanity.com/paper/2508.09101/) (2025)
- [Evaluating n-Gram Novelty of Language Models Using Rusty-DAWG](https://mlsanity.com/paper/2406.13069/) (2024)
- [SABER: Small Actions, Big Errors -- Safeguarding Mutating Steps in LLM Agents](https://mlsanity.com/paper/2512.07850/) (2025)
- [MCPVerse: An Expansive, Real-World Benchmark for Agentic Tool Use](https://mlsanity.com/paper/2508.16260/) (2025)
- [Trajectory2Task: Training Robust Tool-Calling Agents with Synthesized Yet Verifiable Data for Complex User Intents](https://mlsanity.com/paper/2601.20144/) (2026)
- [Unlocking Implicit Experience: Synthesizing Tool-Use Trajectories from Text](https://mlsanity.com/paper/2601.10355/) (2026)
- [L-MARS: Legal Multi-Agent System with Agentic Search and Citation-Faithfulness Audit](https://mlsanity.com/paper/2509.00761/) (2025)

## Abstract (arXiv)

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.