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

Summary

TASTE names three desiderata for tool-agent benchmarks — validity (verifiable and correct: the gold final state is reachable from the stated task), coverage (tasks span structurally distinct gold tool sequences, not near-duplicates), and difficulty (split into structural, from sequence length and read/write mix, and interaction, from ambiguity, distractors and user behaviour) — and argues that authoring a scenario first and deriving the tool calls afterwards leaves the tool-sequence space unexplored. It inverts the process: sample tool sequences from an adaptive contrastive trigram model trained online on LLM plausibility labels, pick K structurally distinct medoids by K-medoids over a semantically weighted Levenshtein distance, instantiate each into a task (initial DB, user instruction, arguments), then evolve it adversarially. The n-gram design lifts the validity rate of sampled sequences from 6.7% (uniform tool sampling) to 86.7%, a ~13× gain, with adaptive training and negative evidence each contributing. The resulting τᶜ-Bench, built over the three τ²-Bench domains at $725total($2.50 per task), drops 11 agent/user pairs by 5–80% relative against τ-Bench-Verified — Gemini-3-Flash falls from 0.82–0.94 to 0.28–0.61 — while raising weighted edit distance up to 124%, type-token ratio up to 111%, and tool-frequency entropy 35%. The headline claim is that near-ceiling scores on τ² reflect saturation rather than robustness.

Key points

• Coverage is operationalised, which is the paper’s main contribution: the gold tool sequence (tool names, arguments stripped) is the unit, and diversity is measured with NLP n-gram metrics — weighted edit distance between sequences, type-token ratio of tool n-grams (n=2..6), tool-frequency entropy — computed on both gold sequences and sequences recovered from successful trajectories. Prior benchmarks report domain/tool counts or capability tags, which say what tools exist but not whether the tasks exercise varied procedures.
• The sampler is a temperature-annealed log-odds between two Dirichlet-smoothed trigram tables, C⁺ from LLM-judged plausible sequences and C⁻ from implausible ones. Negative evidence matters because some local patterns are diagnostic of invalidity (e.g. modifying a reservation after cancelling it): it adds 10 points of validity at k=400 and 20 at k=800; untrained-but-seeded is only 16.7%.
• Validity is enforced by a two-layer gate, not assumed. Deterministic rule checks first (entities referenced exist in s₀, gold calls conform to schema, the gold sequence executes); then a hint-assisted verifier agent must actually solve the task while talking to the simulated user, given the gold tool calls shuffled with a fraction ⌈p·|kwargs|⌉ of arguments masked — enough to guide, not enough to replay.
• The verifier is itself validated against ground truth, which is rare: labelling τ²-Bench tasks by whether τ-Bench-Verified had to fix them (50 Airline with 8 invalid, 86 Retail with 9 invalid), it scores precision 1.00/0.97 and recall 0.75/0.83. So it rejects some good tasks but almost never passes a bad one — the right asymmetry for a benchmark builder. A manual pass over the 15 τᶜ tasks that no agent-user pair solved found all 15 valid; the failures were agent mistakes.
• Difficulty evolution is three LLM calls over the base task while holding the gold tool-call sequence fixed: strategy analysis over write actions against a hand-curated catalogue of adversarial patterns (user demands a policy-forbidden action, user supplies wrong information), environment perturbation that merges decoy records into s₀ (a flight on the right route with no seats), and scenario rewriting. Failed evolutions fall back through simpler variants to the base task.
• Evolution is the dominant difficulty lever: success rates fall 36–55% when Gemini-3 does the evolving vs 16–37% for GPT-5.2. Structural knobs also work — long-sequence tasks are 30% harder on average and write-heavy tasks 43% harder — so the generator has headroom when τᶜ itself saturates.
• Grading is final-state only. The authors explicitly note this overlooks trajectory properties (efficiency, intermediate rewards, interaction quality) and that τ-Bench’s optional action and communication checks are excluded from the main reward, as is standard practice.
• Limitations: the base tasks are invented scenarios with no external realism check — nothing verifies the generated task resembles work anyone does, only that it is executable and solvable; plausibility labels are LLM judgments; the recall gap means valid-but-unusual sequences are discarded, which cuts against the coverage goal; and Telecom gold sequences encode only write actions, so coverage there is measured over writes.

Relevance

• ITSMBench — the most directly reusable piece for V2 is the measurement kit: gold-tool-sequence coverage metrics (WED, TTR over n-grams, tool-frequency entropy) give a cheap, automatic way to ask whether V2’s ~53–89 tasks exercise the ITSM API surface broadly or cluster in a few procedures, and the same metrics could be computed over BPI activity sequences to compare the benchmark’s procedural distribution against the log’s. Also directly portable: the hint-assisted verifier agent as a solvability gate before a task enters the suite, and its precision/recall validation protocol against known-bad tasks. What it does not cover: coverage here is intrinsic (diversity of tool combinations) with no ground-truth distribution to match — it cannot tell you whether a covered sequence matters, which is exactly what the event logs are for; and there is no practitioner realism check, no multi-agent or team structure, and no trajectory-level grading.
• WorldSmith — a fully automated benchmark-extension pipeline (as opposed to environment building) with an honest cost figure ($725 for 278 tasks) and, unusually, a measured validity gate whose false-pass rate is near zero. It is evidence that the hard part of automation is not generation but the accept/reject decision, and that an agent can be a trustworthy rejector even when it is a mediocre solver.
• Benchmark Research — supplies the validity/coverage/difficulty triad, the split between structural and interaction difficulty, and the saturation argument: relative drops of 5–80% on regenerated tasks in the same environment mean high τ² scores measure the task set, not the agent.
• Environment Generation — home concept since 2026-09-10

Questions it raises for ITSMBench:

• Can BPI activity sequences seed the C⁺ table directly, so the sampler explores real ITSM procedure space rather than LLM-judged plausibility? That would fuse this method with the log-grounding claim instead of choosing between them.
• The verifier’s recall of 0.75–0.83 means roughly a fifth of valid tasks are thrown away. For a coverage-weighted benchmark, does that discard bias the distribution toward easy-to-verify procedures, and would a human review of rejects be cheap enough to check?
• Their difficulty evolution deliberately makes the user adversarial and the DB full of decoys. For ITSM, do those perturbations survive the practitioner-realism yardstick, or do they produce tasks that are hard but not the kind of hard a real service desk faces?

Notes

(Our take: to add after reading; drafted 2026-09-09, not yet discussed)