τ-bench

Full title: τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains Authors: Shunyu Yao, Noah Shinn, Pedram Razavi, Karthik Narasimhan (Sierra) Venue/year: arXiv preprint, June 2024 — arXiv:2406.12045 Links: arXiv · local PDF: research-papers/2406.12045-tau-bench.pdf

Why this paper matters

τ-bench is the benchmark that made reliability — not capability — the headline metric for language agents. Earlier agent benchmarks (WebShop, WebArena, SWE-bench, AgentBench) hand the agent a fully specified task upfront and let it act autonomously; τ-bench instead drops the agent between a simulated human user (an LM playing a persona with hidden intent) and database-backed API tools, under a domain policy document it must obey — i.e., the actual shape of customer-service deployment. Two design choices became standard practice: (1) grading by comparing the final database state against a unique annotated goal state, which replaces subjective trajectory judging with an objective, automatable check (§4.2); and (2) the pass^k metric — the chance that all k i.i.d. trials of a task succeed — which measures the consistency real deployments need, dual to pass@k's "at least one" (§3). The headline finding reframed the field's self-image: gpt-4o, the best function-calling agent tested, succeeds on <50% of tasks on average, and its τ-retail pass^8 falls below 25% (abstract, §5).

The problem

Deployed agents must (1) gather information incrementally from humans over long horizons, (2) adhere to domain-specific policies and rules, and (3) behave consistently "across millions of interactions" (§1). Existing benchmarks tested none of this: they "feature simplified instruction-following setups, where the agent autonomously interacts with an environment... given all the information upfront, without any human-in-the-loop interaction and without the need to consult any domain-specific guidelines" (§1). Tool-use suites (BFCL, ToolBench, MetaTool) are single-step: the human's first message contains everything (§2). Classic task-oriented dialogue datasets are static pre-collected trajectories or rule-based simulators (§2). And single-run success metrics hide stochastic flakiness — an agent that solves a task once out of eight runs looks identical, under pass@1-style reporting averaged over trials, to serious inconsistency in production.

The mechanism

The POMDP framing (§3)

Each task is a partially observable MDP (S, A, O, T, R, U) where the state factors into a database state s_db and a user state s_user; the agent's action space is A_db ∪ A_user — call an API tool or send the user a message. The agent never sees the database directly, only tool outputs; it also never sees the task annotation.

• Databases and APIs: each domain ships JSON databases whose contents are the hidden state; tools (tool_name(**kwargs)) read or write it, and the database transition is deterministic Python (§3 "Databases and APIs", Figure 2a–b).
• Domain policy: a Markdown document in the agent's system prompt, e.g. "an order can only be exchanged if its status is 'delivered'". Some rules are enforced as API checks; others are not — the agent must uphold them itself, "similar to the freedom given real-world agents" (§3 "Domain policy", Figure 2c).
• User simulation: an LM (gpt-4-0613) role-plays the user from a hidden textual instruction (identity, intent, preferences, personality — "You are mia_li_2017... You are reticent..."-style). The user transition is stochastic; the episode ends when the user emits ###STOP### (§3 "User simulation", Figure 2d).

Database-state grading (§3 "Reward")

The reward of an episode is binary and two-factor:

r = r_action × r_output ∈ {0, 1}

• r_action: the final database equals the unique ground-truth outcome database implied by the annotated write actions. Dialogue variation is free; read calls are free; but the set of writes must land the DB exactly on the goal state.
• r_output: the agent's messages to the user contain all necessary information (checked as substrings — e.g. the two refund amounts "54.04", "41.64" in Figure 2d).

Each task's user instruction is deliberately engineered so that only one final database outcome is possible under the policy — that uniqueness is what makes rule-based grading faithful (§4, Stage III; §4.2). The paper is explicit that r=1 is "a necessary but not sufficient condition" for a truly successful episode (the agent might skip a required confirmation), trading a little completeness for fast, objective evaluation (§3 "Reward").

Benchmark construction (§4)

Three stages: (I) manual design of the simplest realistic schemas, APIs, and policies; (II) LM-generated database entries at scale (gpt-4-written sampling code, manually debugged); (III) manual task annotation validated by agent runs — each τ-retail task was run >40 times with a gpt-4-turbo agent, and instructions were iteratively de-ambiguated until a unique outcome was certain (§4, Figure 7 ref). Two domains result:

(Table 1.) τ-retail covers canceling/modifying pending orders, returns/exchanges of delivered orders, and address/info updates, with one-shot constraints (each pending order can be modified only once, §4.1). τ-airline is deliberately gnarlier: booking/changing/canceling reservations under ad-hoc rules — baggage allowance by membership tier and cabin, payment-method combination constraints, change/cancellation windows — "creating challenging multi-hop reasoning puzzles for the agent" (§4.1).

The algorithm

The tool-agent-user simulation loop (reconstructed from §3, Figure 1)

# Setup per episode
agent.system_prompt = domain_policy + tool_schemas          # what the agent knows
user.system_prompt  = task.instruction (hidden from agent)  # persona + intent
db = load_domain_database()                                 # hidden state s_db

msg = user.first_message()
while msg != "###STOP###" and n_agent_actions < 30:         # cap: 30 actions (§5)
    act = agent.step(history)                # temperature 0.0 (§5)
    if act is ToolCall:                      # a ∈ A_db
        obs = execute(db, act)               # deterministic Python; may WRITE db
        history += [act, obs]
    else:                                    # a ∈ A_user: natural-language reply
        msg = user.respond(history_visible_to_user, act)    # LM, temperature 1.0
        history += [act, msg]                # stochastic transition T_user

# Grading (no judge model)
r_action = (db == task.ground_truth_db)             # unique goal DB state
r_output = all(s in agent_messages for s in task.required_outputs)  # substrings
r = r_action * r_output                             # ∈ {0,1}

Walkthrough: the agent alternates freely between querying/updating the database and conversing; the user LM only ever sees the conversation (not the DB, not the tools); grading afterward touches only the DB snapshot and the agent's utterances. Because reads don't affect grading, agents can explore safely — only the write set must be exactly right.

The pass^k estimator (§3 "Pass^k metric")

Run each task n ≥ k i.i.d. trials; let c = number of successful trials. The paper's unbiased estimators:

pass^k = E_task[ C(c, k) / C(n, k) ]           # ALL k trials succeed
pass@k = 1 − E_task[ C(n − c, k) / C(n, k) ]   # AT LEAST ONE of k succeeds

where C(·,·) is the binomial coefficient. Read C(c,k)/C(n,k) as: of all C(n,k) ways to draw k trials from your n, the fraction drawn entirely from the c successes — an unbiased estimate of p^k if the task's true per-trial success rate is p, without ever computing p (this mirrors the pass@k estimator from the Codex paper, which τ-bench cites and inverts). pass@k rewards discovery (sampling more helps); pass^k measures reliability (stochastic agents are punished). Note pass^1 = pass@1 = E[c/n], the paper's default headline metric.

Worked example (numbers ours, formula the paper's): a task run n=8 times with c=6 successes gives

pass^1 = 6/8                 = 0.750
pass^2 = C(6,2)/C(8,2) = 15/28 ≈ 0.536
pass^4 = C(6,4)/C(8,4) = 15/70 ≈ 0.214

— a "75% agent" is barely a coin flip at 2 consecutive successes and fails 4-in-a-row most of the time. That compounding is the whole argument for the metric. The stochasticity across trials comes only from LM sampling of the user and agent — same task prompt, same DB — so pass^k isolates behavioral (in)consistency under semantically identical conversations (§3).

Experimental protocol (§5)

• Models: gpt-4o / gpt-4-turbo / gpt-4-32k / gpt-3.5-turbo (OpenAI), claude-3-opus / -sonnet / -haiku (Anthropic), gemini-1.5-pro / -flash (Google), mistral-large, open-mixtral-8x22b (Mistral), meta-llama-3-70B (AnyScale). No small 7/13B models — "due to the difficulty of the benchmark."
• Agent constructions: native function calling (FC) as the main method (system prompt = domain policy; the model freely emits either a user message or a tool call), plus text-formatted ReAct and its Act-only ablation. Self-reflection and planning-heavy methods are excluded on realism grounds: a deployed agent gets one shot with a live user, and slow planners can't serve users in real time (§5 "Methods").
• Budgets: ≤30 agent actions per task; ≥3 trials per task for Table 2; agent temperature 0.0, user temperature 1.0.

Results that matter

(Table 3's airline baseline is 33.2 vs Table 2's 35.2 — different runs in the paper itself.) Hallucinated IDs quantify model quality crisply: gpt-4o makes 0.46 tool calls with non-existent IDs per retail task; gpt-3.5-turbo makes 2.08 (FC) / 6.34 (Act) (§5.2).

The three failure families (§5.2), each pointing at a different agent-engineering gap:

1. Wrong argument / wrong info (~55% combined) — complex database reasoning: right tool, wrong arguments (e.g. failing to find the unique lamp satisfying "less bright, AC adapter over battery" in a big inventory); or omitting/miscalculating information the user needs, sending the conversation off course.
2. Wrong decision (25%) — rule following: the agent knows the tools but violates the policy, e.g. exchanging items one call at a time when the policy requires collecting all items into a single exchange call because the tool "can only be called once."
3. Partial resolution (19.4%) — compound requests: with more ground-truth database writes per task, success drops sharply (Figure 6); agents forget explicit early requests (long-context/memory) or skip implicit ones (checking all orders, not just one).

Limitations & how to defend the findings

• "The graded reward misses policy violations." Conceded upfront: r=1 is necessary, not sufficient — an agent could write the right DB state while skipping a required user confirmation (§3 "Reward"). Defense: even this lenient bar already breaks SOTA agents (<50% pass^1), so the finding survives; adding LM rule-checks is listed as future work (§6).
• "The simulated user is imperfect." The paper's own audit found it: of 40 failed gpt-4o retail trajectories, 4 traced to user-instruction typos/ambiguity (then fixed), and §6 lists user-LM failure modes (limited reasoning/memorization, over-compliance with agent suggestions). Defense from §6: imperfect users are realistic — "the onus is on the agents to handle diverse users" — and the >40-trial validation stage bounds ambiguity.
• "Only two domains, 165 tasks — small." Deliberate: "we trade off quantity for quality" — a small set of heavily validated tasks run for multiple trials yields richer signal (pass^k curves) than many noisy tasks run once (§4.2). The framework is modular for adding domains (§4.2).
• "Curation used gpt-4-turbo agents — bias toward OpenAI models?" Acknowledged verbatim in §6: "some element of implicit bias during the task curation process since we use the gpt-4-turbo FC agent to tune the user's system prompt." Cross-vendor results (claude-3-opus nearly ties gpt-4o on airline: 34.7 vs 35.2, Table 2) suggest the ranking isn't an artifact, but this is a genuine caveat.
• "Is the policy doing anything, or are tasks just common sense?" The ablation answers it: removing the policy costs gpt-4o only 4.4 points on retail (rules ≈ common sense there) but 22.4 points on airline (rules are ad-hoc and binding) — and gpt-3.5 barely drops on airline (−1.2), implying it never really used the policy at all (Table 3, §5.2). The benchmark's difficulty is genuinely rule-driven where designed to be.
• "Function calling might just be under-trained; ReAct-style scaffolds could close the gap." Tested: FC beats ReAct and Act at every model tier (Figure 3), and adding a "think" tool to FC agents didn't help (§5.1 "Method comparison"). The gap is model capability, not prompting format.

Connections

• Reliability engineering: pass^k is the agent-world analogue of an SLO — pass^1 is average quality, pass^k-vs-k is the reliability curve. τ-bench's Figure 4 (pass^k falling, pass@k rising with k) is the cleanest published picture of capability vs consistency being different axes.
• pass@k lineage: the estimator is the direct combinatorial dual of the unbiased pass@k estimator from Chen et al.'s Codex paper (cited as [5] in §3) — same trick, opposite quantifier.
• AgentBench (sibling page): AgentBench measures breadth of autonomous capability across 8 environments with fully specified tasks; τ-bench holds domain breadth at 2 and instead varies the human. Together they span the capability-vs-reliability benchmarking axis.
• Let's Verify (sibling page): τ-bench diagnoses inconsistency; verifier-style selection (PRM-scored best-of-N) is a candidate remedy, though τ-bench notes agents can't do best-of-N against a live user — "only have one chance to serve the user" (§5 "Methods") — which is exactly why per-step verification matters more than post-hoc selection in interactive settings.
• ReAct / Reflexion: ReAct is a baseline (Figure 3); Reflexion-style retry is explicitly ruled unrealistic for user-facing episodes (§5 "Methods") — an important negative design note for agent-loop architecture.
• MemGPT (sibling shelf): τ-bench's Failure 3 (forgetting early user requests in compound tasks, §5.2) is precisely the long-context/memory failure MemGPT-style architectures target.

Reading guide

• Read first: Abstract → §1 → §3 (the POMDP, reward, and pass^k — the technical core, ~2 pages) → §5.1 with Table 2 and Figure 4.
• Then: §4 (construction stages — Stage III's ">40 trials per task" validation is the benchmark's quality secret) and §5.2 (failure taxonomy + the Table 3 policy ablation).
• Skimmable: §2 (related work), §6 (discussion — but read the "Directions for improvement" paragraph: it's the authors' own critique list), Figure 2 (component anatomy; worth 60 seconds).
• Appendices, only as needed: A (task difficulty distribution, Figure 7), B.1–B.2 (domain/schema details), C.2/D.2 (example trajectories — read one full τ-airline trajectory once; it conveys the difficulty better than any table).
• The one figure to study: Figure 4 — pass^k (falling) and pass@k (rising) vs k on τ-retail. It is the paper's thesis in one plot: sampling more trials makes agents look better under discovery metrics and worse under reliability metrics, and the gap between those curves is the deployment risk everyone had been ignoring.