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

• URL: http://arxiv.org/abs/2605.28556v2
• Date: Tue, 02 Jun 2026 10:20:59 GMT
• Title: A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks
• Abstract summary: We propose TASTE: Task Synthesis from Tool Sequence Evolution, an automatic method that generates challenging tasks with broader tool-use coverage.<n> TASTE selects representative sequences from the pool via clustering, instantiates them into complete benchmark tasks, and refines them through difficulty evolution.<n>Our results suggest high scores on existing benchmarks often reflect saturation rather than robust task-solving ability.
• Score: 25.713629634281077
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• When Tools Fail: Benchmarking Dynamic Replanning and Anomaly Recovery in LLM Agents [48.32450507410869]
  Existing benchmarks evaluate Tool-Integrated Reasoning in LLMs on idealized ''happy paths''<n>We introduce ToolMaze, a benchmark for dynamic path discovery and error recovery in TIR agents.
  arXiv  Detail & Related papers  (2026-06-04T07:38:46Z)
• ComplexMCP: Evaluation of LLM Agents in Dynamic, Interdependent, and Large-Scale Tool Sandbox [61.862814740220806]
  $textbfComplexMCP$ is a benchmark designed to evaluate agents in rigorous conditions.<n>Built on the Model Context Protocol (MCP), $textbfComplexMCP$ provides over 300 meticulously tested tools.
  arXiv  Detail & Related papers  (2026-05-11T16:20:51Z)
• Complete Cyclic Subtask Graphs for Tool-Using LLM Agents: Flexibility, Cost, and Bottlenecks in Multi-Agent Workflows [0.0]
  We study complete cyclic subtask graphs in which executable subtask nodes are fully connected.<n>We evaluate task-specific (Spec-Cyc) and benchmark-generic (Gen-Cyc) graphs on TextCraft, ALFWorld, and Finance-Agent.
  arXiv  Detail & Related papers  (2026-04-17T15:31:20Z)
• Agent psychometrics: Task-level performance prediction in agentic coding benchmarks [24.348135523715815]
  We present a framework for predicting success or failure on individual tasks tailored to the agentic coding regime.<n>Our approach augments Item Response Theory (IRT) with rich features extracted from tasks, including issue statements, repository contexts, solutions, and test cases.
  arXiv  Detail & Related papers  (2026-04-01T07:59:59Z)
• MagicAgent: Towards Generalized Agent Planning [73.21129030631421]
  We present textbfMagicAgent, a series of foundation models specifically designed for generalized agent planning.<n>We introduce a lightweight and scalable synthetic data framework that generates high-quality trajectories across diverse planning tasks.<n>We show that MagicAgent-32B and MagicAgent-30B-A3B achieve superior performance across diverse open-source benchmarks.
  arXiv  Detail & Related papers  (2026-02-22T01:39:16Z)
• ADAPT: Learning Task Mixtures for Budget-Constrained Instruction Tuning [1.0039548765955955]
  ADAPT is a meta-learning algorithm that emphlearns task sampling proportions under an explicit token budget for instruction tuning.<n>We conduct evaluations on 11 out-of-domain benchmarks spanning reasoning, reading comprehension, code generation, and instruction following.
  arXiv  Detail & Related papers  (2025-12-04T08:17:05Z)
• ML-Tool-Bench: Tool-Augmented Planning for ML Tasks [23.54937738755734]
  We introduce a benchmark for evaluating tool-augmented machine learning agents.<n>Our benchmark goes beyond traditional tool-use evaluation by incorporating an in-memory named object management.<n>Our approach improves over ReAct by 16.52 percentile positions, taking the median across all Kaggle challenges.
  arXiv  Detail & Related papers  (2025-11-29T23:59:40Z)
• AgentSynth: Scalable Task Generation for Generalist Computer-Use Agents [60.881609323604685]
  Agent Synth is a scalable and cost-efficient pipeline for automatically synthesizing high-quality tasks and trajectory datasets.<n>Our pipeline achieves a low average cost of $0.60 per trajectory, orders of magnitude cheaper than human annotations.
  arXiv  Detail & Related papers  (2025-06-17T05:46:52Z)
• Runaway is Ashamed, But Helpful: On the Early-Exit Behavior of Large Language Model-based Agents in Embodied Environments [54.67512489842682]
  Large language models (LLMs) have demonstrated strong planning and decision-making capabilities in complex embodied environments.<n>We take a first step toward exploring the early-exit behavior for LLM-based agents.
  arXiv  Detail & Related papers  (2025-05-23T08:23:36Z)
• TaskBench: Benchmarking Large Language Models for Task Automation [82.2932794189585]
  We introduce TaskBench, a framework to evaluate the capability of large language models (LLMs) in task automation. Specifically, task decomposition, tool selection, and parameter prediction are assessed. Our approach combines automated construction with rigorous human verification, ensuring high consistency with human evaluation.
  arXiv  Detail & Related papers  (2023-11-30T18:02:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.