VitaBench: Benchmarking LLM Agents with Versatile Interactive Tasks in Real-world Applications

ArXiv: 2509.26490

🎯 Pitch

Even the most advanced LLM agents fail at 70% of real-world tasks that span multiple apps like food delivery and travel booking. VitaBench reveals these failures stem from modeling real human unpredictability—not just tool counts—by having agents coordinate 66 interdependent tools while managing scattered, impatient, and withholding users.

---

1. Executive Summary

This paper introduces VitaBench, a challenging benchmark for evaluating LLM-based agents on versatile interactive tasks grounded in real-world life-serving applications across delivery, in-store consumption, and online travel agency domains. VitaBench operationalizes a three-dimensional agentic task complexity framework comprising reasoning complexity (entropy of the observation space and partial observability, e.g., integrating spatiotemporal constraints across multi-faceted environmental information), tool complexity (graph cardinality and edge density encoding inter-tool dependencies, e.g., navigating 66 tools with 512 dependency edges in cross-scenario settings), and interaction complexity (user profiles and behavior attributes introducing dynamic conversational uncertainty, e.g., managing impatient or scattered personas who progressively reveal requirements). The paper evaluates numerous state-of-the-art models against 100 cross-scenario and 300 single-scenario tasks using a rubric-based sliding window evaluator, finding that even the best-performing model, o3 (high), achieves only 30.0% success rate on cross-scenario tasks and 53.5% on single-scenario tasks, establishing that current agents face fundamental reasoning, tool-use, and interaction management deficiencies that manifest most severely when navigating expanded action spaces across multiple domains.

2. Context and Motivation

The Core Problem: Existing Benchmarks Don't Capture Real-World Agentic Complexity

The central gap this paper addresses is a benchmarking crisis in LLM agent evaluation. As LLMs transition from research artifacts to deployed systems handling real-world tasks—booking restaurants, coordinating deliveries, purchasing train tickets—the evaluation frameworks meant to assess them have failed to keep pace with the complexity these deployments demand. The paper frames this explicitly as a question (Section 1):

"What constitutes task complexity for agents in real-world applications?"

This is not merely an academic exercise. Organizations deploying LLM agents in customer-facing applications need to know whether their systems can handle the messy reality of human interaction: users who are impatient or scattered, who reveal constraints only when asked, who have dietary restrictions they don't explicitly state, and whose requests span multiple service domains that must be coordinated (e.g., "book my usual hotel with a river view and a romantic dinner near where we first met"). A benchmark that tests only whether an agent can call the right API function with the right parameters captures nothing about whether it can navigate this kind of scenario.

The practical urgency comes from the growing deployment gap. The paper notes (Section 1) that LLMs are already being deployed in real-world applications for food delivery, in-store consumption, and online travel services—the very domains VitaBench is built from. If evaluation frameworks systematically underestimate task difficulty, organizations may deploy agents prematurely, resulting in frustrated users, lost revenue, and eroded trust. Conversely, if frameworks overestimate difficulty through unrealistic constraints, they may prevent deployment of capable systems. The benchmark needs to be faithful to real-world complexity, and this paper argues existing benchmarks fail that test.

Three Dimensions of Missing Complexity

Drawing on task complexity theories from organizational psychology (Liu and Li, 2012), the paper identifies three fundamental dimensions of agentic complexity that prior benchmarks fail to comprehensively address (Section 3.1). These dimensions are not arbitrary—they emerge from analyzing what makes real-world tasks genuinely difficult for both humans and AI systems:

1. Reasoning complexity ($C_{reason}$): The cognitive load of partial observability. In real applications, agents never see the full state of the world. They must reason under uncertainty about what information exists, what constraints apply, and how different pieces of information relate. The paper formalizes this through the entropy of the observation space $H(O)$ and a partial observability coefficient $\eta = 1 - \frac{|O|}{|S|}$—the fraction of the true state that is hidden from the agent. A task like "book my usual hotel with a river view for our anniversary" requires the agent to: (a) determine which hotel is "usual" by querying transaction history, (b) verify that the hotel has river-view rooms by querying hotel details, (c) check weather conditions for outdoor-adjacent planning, (d) ensure the date aligns with the user's stated timeline, and (e) coordinate this with other requests the user may make. None of these reasoning steps are explicitly enumerated in the instruction—they must be inferred.

2. Tool complexity ($C_{tool}$): Navigating interconnected action spaces. Real-world tasks require not just calling individual tools, but understanding dependencies between tools—what information must be gathered before an action can be taken. The paper models the toolset as a directed graph $G = (V, E)$ where vertices are tools and edges encode pre-condition/post-condition relationships. For instance, modify_order requires prior execution of get_order_detail to obtain the necessary order ID and confirmation details. A toolset with high graph density (many edges relative to vertices) demands sophisticated planning: agents must reason about execution order, handle cases where pre-conditions are unsatisfied, and recover when a tool call fails. The cross-scenario setting amplifies this by expanding the action space to 66 tools across three domains, forcing agents to select the right tool from a much larger pool where most tools are irrelevant to the current task.

3. Interaction complexity ($C_{interact}$): Managing dynamic, uncertain human behavior. Prior benchmarks often treat users as passive instruction-givers or, at best, as simple question-answerers. Real users have personas (personality traits, emotional states, communication styles, patience levels) and reveal information progressively—they don't state all constraints upfront, either because they assume the agent will infer them or because they don't realize certain constraints matter. A user described as "cold and concise in expression, lacks emotional communication and patience" (Appendix C example) will respond very differently to clarifying questions than a "detail-oriented, cooperative" user. Agents must adapt their interaction strategy dynamically, knowing when to proactively ask for clarification versus when to infer from context, and must handle cases where user state evolves (e.g., becoming impatient after repeated questions).

Where Prior Benchmarks Fall Short

The paper provides a detailed taxonomy of existing benchmarks against these three dimensions (Table 1), and the pattern is stark: no prior benchmark simultaneously addresses all three dimensions fully, and most address only one or two partially.

Early tool-use benchmarks (ToolLLM, BFCL): Single-turn simplicity. Benchmarks like ToolLLM (Qin et al., 2024) and the Berkeley Function Calling Leaderboard (Patil et al., 2025) focus primarily on function-calling accuracy—"given this instruction, can you call the right API with the right parameters?" They introduce difficulty through increased tool counts or distractor tools, but operate in single-turn or very short multi-turn settings where:

• There is no state that persists between tool calls, so agents don't need to reason about how one action affects subsequent options.
• There are no inter-tool dependencies—each call is independent.
• Users are absent or completely passive, so there is no interaction complexity whatsoever.
• Environmental information is minimal—typically just the tool schemas and the immediate query.

These benchmarks test tool syntax, not agentic reasoning. An agent can score perfectly on BFCL while being completely incapable of handling a real user who says "I want the usual" and expects the agent to figure out what "usual" means.

The τ-bench family: Policy documents replace genuine exploration. τ-bench (Yao et al., 2024) and τ²-bench (Barres et al., 2025) were significant advances—they introduced stateful environments, multi-turn user interactions (30-80 turns), and user profiles. However, the paper identifies a fundamental limitation: these benchmarks constrain agents through verbose domain-specific policy documents rather than allowing truly autonomous exploration. The policies explicitly tell agents what rules to follow, what pre-conditions exist, and what actions are permissible. This shifts the challenge from reasoning about the environment to reading comprehension of policy text—a useful skill, but not the same as the autonomous exploration required in real deployments where such documentation rarely exists or is incomplete.

Additionally:

• τ-bench lacks composite objectives and goal ambiguity. Tasks are well-specified with clear success criteria, so agents rarely need to proactively clarify ambiguous user intent or balance multiple interdependent sub-goals.
• User profiles exist but behavior attributes are limited. τ²-bench introduces some user variability, but the paper argues (Table 1) that the interaction complexity remains only partially addressed compared to the diverse personas and emotional dynamics in real interactions.
• No cross-scenario composition. Both τ-bench and τ²-bench operate within single domains (airline booking, retail, etc.), so agents never face the challenge of switching between distinct tool sets and domain contexts mid-task.

Conversational benchmarks without tool complexity. ToolTalk (Farn and Shin, 2023) introduced multi-step tool execution through conversation but relied on predefined dialogue trajectories, limiting agent autonomy and making it a test of following a script more than autonomous problem-solving. MINT (Wang et al., 2024a) emphasized natural language feedback to guide agents but operated in constrained environments with only 8 tools and no meaningful inter-tool dependencies. IN3 (Qian et al., 2024) focused on detecting implicit user intentions—a valuable aspect of interaction complexity—but entirely omitted tools, making it irrelevant for evaluating real-world agent capabilities. UserBench (Qian et al., 2025) uniquely captured preference-driven interactions but with only 5 tools and no inter-tool dependencies or cross-scenario challenges, severely limiting reasoning and tool complexity.

DialogTool and ToolSandbox: Partial progress, partial gaps. DialogTool (Wang et al., 2025) explored role-playing for engaging users with 31 tools and cross-scenario composition, but the paper characterizes its interaction complexity as only partially addressed (Table 1, "✓⁻"). The user roles are scripted rather than dynamically responsive, and behavior attributes like patience or emotional state are not systematically varied. ToolSandbox (Lu et al., 2025) provides stateful execution with 34 tools and inter-tool dependencies, but lacks cross-scenario composition and has essentially no interaction complexity—its 10-30 turn range reflects tool execution rather than genuine dialogue with simulated users.

The Pattern of Systematic Neglect

When all existing benchmarks are mapped against the three complexity dimensions (Table 1), a clear pattern emerges:

• Reasoning complexity: Partially addressed by the τ-bench family (multifaceted information) and ToolSandbox/DialogTool (composite objectives), but goal ambiguity—the need to proactively clarify underspecified instructions—is almost entirely absent except partially in IN3 and τ²-bench.
• Tool complexity: Inter-tool dependencies and cross-scenario composition appear in some benchmarks but never together at scale. ToolTalk and ToolSandbox have dependencies but no cross-scenario; DialogTool has cross-scenario but only partially addresses dependencies. No benchmark simultaneously has high tool count, dense dependencies, and cross-domain composition.
• Interaction complexity: User profiles appear in τ-bench and its descendants, but dynamic behavior attributes (patience that degrades, emotional states that shift, cooperation that varies based on agent performance) are essentially absent until τ²-bench, and even there, only partially realized.

The consequence is that existing benchmarks provide a systematically distorted picture of agent capability. A model might score 80% on τ-bench but fail catastrophically on a VitaBench task where it must (a) navigate an unfamiliar tool graph without explicit policy guidance, (b) infer which of 9,693 products satisfies complex cross-domain constraints, and (c) manage a user who becomes impatient when asked the same question three times. The paper's core argument is that this gap is not incidental—it reflects a fundamental mismatch between how the field evaluates agents and what real deployment demands.

How VitaBench Positions Itself

VitaBench is not proposing a new algorithm or model architecture. Its contribution is redefining the evaluation landscape to create a benchmark that is simultaneously challenging, faithful to real-world complexity, and theoretically grounded in a formal framework that explains why tasks are difficult.

The theoretical contribution: A formal complexity framework. By casting agentic tasks through the lens of task complexity theory and the POMDP formalism (Section 3.1), the paper provides a language for reasoning about benchmark design itself. The three-dimensional complexity vector $C_{task} = \langle C_{reason}, C_{tool}, C_{interact} \rangle$ is not just descriptive—it is prescriptive. It says: if you want to evaluate whether an agent can handle real-world tasks, your benchmark must simultaneously challenge all three dimensions. A benchmark strong in only one or two dimensions will produce misleadingly optimistic results.

This theoretical framing also enables validating that complexity metrics actually predict difficulty. Section 5.2 demonstrates that reasoning point count and search space size (proxies for $C_{reason}$) and tool graph density (proxy for $C_{tool}$) correlate strongly with model performance degradation across domains. This is not taken for granted—it is empirically verified, lending credibility to the framework.

The practical contribution: A benchmark built from the ground up to embody all three dimensions simultaneously. The construction pipeline (Section 3.2, Figure 3) is designed specifically to fill the gaps in prior work:

• No domain-specific policy documents. Instead of telling agents what rules to follow, the rules are encoded in the tool graph structure itself through pre-conditions and post-conditions. Agents must discover constraints through exploration—for example, learning that modify_order fails unless get_order_detail has been called first, not because a policy document says so, but because the tool pre-conditions enforce it. This makes the task about reasoning rather than reading comprehension.
• Composite objectives with genuine ambiguity. Each task synthesizes multiple real user requests into a compound instruction where sub-goals interact. The example in Appendix C—booking a restaurant for a three-generation family gathering and ordering elderly care items for delivery to the restaurant and purchasing a train ticket for a relative to arrive in time—requires coordinating temporal constraints (all on July 27th, with the train arriving before 11 AM, the restaurant at noon, the delivery around 12, and boarding at 3 PM), spatial constraints (restaurant near the port, train station to restaurant route suitable for elderly and children), and personal constraints (dietary restrictions inferred from profile, accessibility needs).
• Progressive information revelation. The user simulator (powered by gpt-4.1) is explicitly instructed to "break down information from instructions into multiple independent points, mentioning them separately in different rounds" and to "avoid revealing all needs in the first round." Combined with user profiles that include patience levels and communication styles, this creates genuinely challenging interaction dynamics where agents must decide when to proactively ask versus when to wait for the user to volunteer information.
• Cross-scenario composition with expanded action spaces. The 100 cross-scenario tasks present agents with all 66 tools simultaneously—20 from delivery, 24 from in-store, 38 from OTA, plus 6 general tools. An agent booking a restaurant and ordering delivery must select the right tools from each domain, navigate their separate dependency graphs, and coordinate between them. No prior benchmark tests this kind of domain-hopping capability.

The empirical contribution: A reliable evaluation methodology for long trajectories. Long-form agent trajectories with multiple valid solution paths pose a fundamental evaluation challenge. State-based evaluation (used by τ-bench: compare final database state to expected state) fails to capture requirements that don't modify state, such as recommending a restaurant based on preferences or planning a route. It also cannot provide intermediate supervision, making it hard to understand where failures occur. The paper's rubric-based sliding window evaluator (Section 3.3) addresses this by decomposing tasks into atomic criteria tracked across overlapping trajectory windows, validated against human judgments with Cohen's κ ≥ 0.81. This is a methodological contribution that enables studying agent failures at granularity beyond pass/fail.

The Stakes

The paper's motivation implicitly rests on a broader claim about where the field is heading. As LLMs improve at narrow benchmarks, there is a growing temptation to deploy them in increasingly autonomous roles—customer service agents, personal assistants, travel coordinators. But narrow benchmark performance does not translate to real-world competence if those benchmarks fail to capture the structural, resource, and interaction complexity of actual tasks.

VitaBench establishes a performance ceiling that is dramatically lower than what simpler benchmarks suggest: even o3 (high), representing the frontier of current capability, achieves only 30% on cross-scenario tasks. This is not a failure of any particular model—it is evidence that the benchmarks the field has been optimizing against are not measuring what we think they are. The gap between VitaBench performance and simpler benchmark performance quantifies the invisible failure surface that current evaluation frameworks systematically miss, and the paper's motivation is to make that surface visible so the field can start climbing it.

3. Technical Approach

3.1 Reader Orientation

VitaBench is a benchmark construction and evaluation framework—not a model or algorithm—that operationalizes a formal theory of agentic task complexity to create the most comprehensive test suite to date for evaluating LLM-based agents in real-world interactive scenarios. The system solves the problem of faithful evaluation: how do you test whether an LLM agent can genuinely handle the messiness of real-world deployments—users who are impatient, tasks that span multiple service domains, tools with hidden dependencies, and constraints that must be inferred rather than read from a policy document—without relying on benchmarks that systematically distort capability estimates by addressing only one or two dimensions of complexity at a time? The "shape" of the solution is a three-part architecture: (1) a POMDP formalism that defines what task complexity means along three orthogonal dimensions (reasoning, tool, interaction), (2) a construction pipeline that instantiates this formalism into concrete tasks with environments, tools, users, and databases, and (3) a rubric-based sliding window evaluator that can assess long-horizon trajectories against atomic success criteria without requiring a single "correct" solution path.

3.2 Big-Picture Architecture (Diagram in Words)

The VitaBench system comprises five major components connected in a pipeline that flows from theoretical framework → task construction → environment simulation → agent interaction → trajectory evaluation:

1. Agentic Task Complexity Framework (Section 3.1): A formal POMDP-based definition that decomposes task difficulty into three independent dimensions—reasoning complexity $C_{reason}$ (how much partial-observability reasoning is required), tool complexity $C_{tool}$ (how dense and large the inter-tool dependency graph is), and interaction complexity $C_{interact}$ (how dynamic and uncertain the simulated user's behavior is). This is not a runtime component but a design constraint: every task, environment, and user profile is constructed to embody all three dimensions simultaneously.

2. Construction Pipeline (Section 3.2, Figure 3): A two-stage process that transforms real-world application data into evaluation tasks. Stage I abstracts actual service platforms (food delivery apps, in-store consumption systems, online travel agencies) into simplified but faithful API tools, models their dependencies as a directed graph, and builds comprehensive databases of service providers, products, and transaction histories. Stage II creates task instances by synthesizing multiple real user requests into compound instructions, assigning user profiles with diverse personality traits and communication styles, embedding target options among distractor options, and defining atomic rubric criteria for evaluation.

3. Environment Simulator (Section 3.1, implemented per-task): For each of the 400 tasks, an independent simulation environment consisting of a database (service providers, products, transactions), a tool execution layer that enforces pre-conditions and post-conditions deterministically through Python functions ($T_{db}$), and a user simulator powered by gpt-4.1 that implements stochastic transitions ($T_{user}$) based on user profiles and progressive information revelation rules. The environment maintains the ground-truth state $S = S_{db} \otimes S_{user}$ that the agent never fully observes.

4. LLM Agent (Section 4.1, external): The model under test, implemented as a function-calling agent receiving tools in OpenAI tool schema format. The agent operates under partial observability, receiving only database feedback from tool calls and conversation history from user interactions. It must decide at each step whether to call a tool or engage in dialogue, when to proactively ask clarifying questions, and when to terminate the interaction by outputting ###STOP###.

5. Rubric-based Sliding Window Evaluator (Section 3.3): A post-interaction assessment component that processes the complete trajectory $\tau$ in overlapping windows of $w$ consecutive turns, maintaining a persistent binary state vector over $k$ atomic rubrics. It uses claude-3.7-sonnet as a judge, propagating rubric-satisfaction information forward across windows to handle trajectories that exceed context length limits. The final score is strict all-or-nothing: $score = \mathbb{1}[\sum_j s_j = k]$.

Information flows as follows: the complexity framework guides construction → each task receives a unique environment with database, tools, user profile, and rubrics → the agent interacts with the environment through multi-turn dialogue and tool calls → the complete trajectory is fed to the sliding window evaluator → the evaluator produces a binary success/failure judgment plus per-rubric scores for fine-grained analysis.

3.3 Roadmap for the Deep Dive

• First, the formal POMDP formulation and complexity framework—because these define the design principles that explain why every subsequent component is built the way it is.
• Second, the construction pipeline (Stage I: tool graph design, and Stage II: task instance creation)—because this is where the theoretical framework becomes concrete environments, and understanding how tools, databases, user profiles, and rubrics are created is essential for interpreting evaluation results.
• Third, the user simulator and environment dynamics—because the stochastic user behavior and deterministic tool execution are the "physics" of the benchmark, and understanding their implementation explains what agents are actually interacting with.
• Fourth, the rubric-based sliding window evaluator—because evaluating long trajectories with multiple valid solution paths is a non-trivial methodological contribution that directly affects result reliability.
• Fifth, the experimental methodology (models, metrics, run counts)—because the choices of temperature (0.0), number of runs (4), metrics (Avg@4, Pass@4, Passˆ4), and model configurations (thinking vs. non-thinking) are deliberate and affect how results should be interpreted.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a benchmark construction and evaluation methodology paper whose core idea is that evaluating real-world agent capability requires simultaneous challenge along reasoning, tool, and interaction complexity dimensions, operationalized through a formal POMDP framework and implemented via a systematic two-stage construction pipeline with a novel trajectory evaluation method.

---

The POMDP Formalism and Task Complexity Framework

The paper grounds its entire approach in a formal definition of the agent interaction problem (Section 3.1), which serves both as an implementation specification for the environment and as the theoretical basis for its complexity framework.

The environment family. The benchmark consists of a set of distinct environments $\mathcal{E}$. For each specific environment $e \in \mathcal{E}$, the agent's task is modeled as a Partially Observable Markov Decision Process (POMDP)—a standard framework for sequential decision-making under uncertainty where the agent never sees the full state of the world but receives observations that partially reveal it.

The POMDP tuple. The POMDP is defined by the tuple $(U, S, A, O, T, r)_e$:

• $U$ is the instruction space: the space of possible initial task descriptions the user might give. Each task $u \in U$ is a single compound instruction synthesized from multiple real user requests (e.g., "book my usual hotel with a river view and a romantic dinner for him and his wife with a budget of $200...").
• $S$ is the state space, which decomposes into two orthogonal subspaces: $S = S_{db} \otimes S_{user}$. The database state $S_{db}$ includes all mutable information—which orders exist, their statuses, which reservations are made, payment states, product inventory conceptually. The user state $S_{user}$ includes the user's current knowledge state (what they've revealed, what they haven't), emotional state (patience level, satisfaction), and conversation history context.
• $A$ is the action space, comprising two distinct action types: tool invocations (calling one of the available API functions with specific parameters) and interactive dialogue (generating natural language responses to the user). This dual action space is what makes the problem agentic rather than purely functional—the agent must decide not just what to do but how to communicate about it.
• $O$ is the observation space, decomposing as $O = O_{db} \otimes O_{user}$. Database observations are the structured feedback returned by tool calls (search results, order confirmations, error messages). User observations are the conversation history—both what the user has said and what the agent has said.
• $T: S \times A \to S$ is the state transition function, which decomposes along the same lines: $T_{db}$ implements deterministic transitions via Python functions (a tool call with specific parameters always produces the same database state change, given the same starting state), while $T_{user}$ implements stochastic transitions via a language model (the same agent question can elicit different user responses depending on the user's persona, patience state, and conversation history).
• $r: S \times A \to \mathbb{R}$ is the reward function, computed after the interaction ends, that returns a value in $[0, 1]$ based on how many of the task's atomic rubric criteria were satisfied.

The interaction loop. The formal interaction proceeds as follows. Given an instruction $u \in U$ and initial state $s_0$ (the prompt tokens plus the initial database state), the agent receives an initial observation $o_0 \in O$ that typically includes the first-round user request and the available tool set. The LLM-based agent, parameterized by $\theta$, generates an action $a_1 \sim \pi_\theta(\cdot \mid o_0)$ from its policy $\pi_\theta$. The state transitions to $s_1 \in S$, and the agent receives feedback $o_1 \in O$. At each step $t$, the agent acts based on the observable history up to that point—$(o_0, a_1, o_1, \ldots, a_{t-1}, o_{t-1})$—generating action $a_t \sim \pi_\theta(\cdot \mid o_0, a_1, o_1, \ldots, a_{t-1}, o_{t-1})$. This continues until either the agent outputs the termination marker ###STOP### or a maximum step limit is reached. From the environment's perspective, the complete trajectory is:

$\tau = (s_0, a_1, s_1, a_2, s_2, \ldots, a_T, s_T) \sim \pi_\theta(\tau \mid e, u)$

where $T$ denotes the total number of interaction rounds.

Why POMDP: The POMDP formalism is not just descriptive—it clarifies what makes the benchmark hard. The partial observability means agents cannot simply "read off" the correct actions from the state—they must infer missing information, decide when to gather more observations via tool calls or user questions, and reason under irreducible uncertainty. The decomposition of state and observation spaces into database and user components directly motivates the three-dimensional complexity framework: database-oriented challenges map to reasoning and tool complexity, user-oriented challenges map to interaction complexity.

The three-dimensional complexity vector. The paper formalizes task complexity as a vector:

$C_{task} = \langle C_{reason}, C_{tool}, C_{interact} \rangle$

where each component quantifies a distinct source of difficulty.

Reasoning complexity $C_{reason}$: This quantifies the cognitive demands of processing extensive environmental information under partial observability. The paper characterizes it through two formal proxies:

• The entropy of the observation space $H(O)$: when many possible observations could occur, the agent faces higher uncertainty about what it will perceive, increasing the difficulty of planning.
• The degree of partial observability $\eta = 1 - \frac{|O|}{|S|}$: this measures the fraction of the true state that is hidden from the agent at any moment. When $\eta$ is close to 1 (the observation space is tiny relative to the full state), agents must maintain extensive internal beliefs about what might be true and reason about when to gather more information. When $\eta$ is close to 0 (observations reveal nearly everything), reasoning becomes straightforward.

In practice, VitaBench increases $C_{reason}$ by constructing large-scale databases with many distractor options (the search space column in Table 5 shows in-store tasks have 3,916 options on average while OTA tasks have 11,284), creating composite tasks with multiple explicit and implicit reasoning points (Table 5 shows cross-scenario tasks average 10.3 reasoning points), and requiring agents to integrate information across temporal dimensions (what time is it now? when does the train arrive? when does the delivery need to leave?), spatial dimensions (how far is the restaurant from the port? which train station is closest?), and common-sense knowledge (what does "suitable for three generations" imply about accessibility and menu requirements?).

Tool complexity $C_{tool}$: This quantifies the structural intricacy of navigating interconnected action spaces. The toolset is modeled as a directed graph $G = (V, E)$ where vertices represent individual tools and edges encode inter-tool dependencies. Three graph-theoretic properties drive complexity:

• Graph cardinality $|V|$: the raw number of available tools. More tools mean a larger search space for selecting the right tool at each step.
• Edge density $\rho = \frac{|E|}{|V|(|V|-1)}$: the proportion of possible tool pairs that actually have a dependency relationship. High density means tools are tightly coupled—calling one tool typically requires having called another first, and sequencing errors cascade. Table 5 shows OTA has the highest density at 22.0%, corresponding to the lowest single-domain performance (20.7%).
• Coverage ratio $\frac{|V_{task}|}{|V|}$: the fraction of the full toolset that is actually relevant to a specific task. In cross-scenario settings, this ratio is low because most of the 66 tools are irrelevant to any given sub-task—the agent must filter aggressively.

The graph-based design serves a crucial dual purpose: it encodes domain rules into tool structures rather than policy documents. For instance, the tool modify_order specifies in its definition that it has a pre-condition of "valid order_id" and a post-condition of "updated order (unpaid)." The agent discovers that it needs get_order_detail before modify_order not because a policy document says so, but because attempting to call modify_order without a valid order_id fails. This shifts the challenge from reading comprehension to environmental reasoning—the same skill required in real deployments where comprehensive policy documentation rarely exists.

Cross-scenario settings amplify $C_{tool}$ by expanding the action space across multiple domains simultaneously. The 100 cross-scenario tasks present all 66 tools at once (20 from delivery, 24 from in-store, 38 from OTA, plus 6 general tools used across domains), creating 512 dependency edges. The agent must switch between distinct tool graphs mid-task—booking a restaurant uses in-store tools with their dependency structure, then ordering delivery uses delivery tools with a different structure, then purchasing a train ticket uses OTA tools with yet another structure. No prior benchmark tests this kind of domain-hopping capability.

Interaction complexity $C_{interact}$: This reflects the challenges of managing dynamic multi-turn conversations with users who have persistent personas and evolving states. Three factors contribute:

• User profiles encode personal attributes—gender, age, occupation, dietary restrictions, relationship status—that influence task requirements but may not be directly stated. In the Appendix C example, the user profile specifies "Avoid high purine foods (organ meats/seafood soup), avoid fried foods," but the instruction does not explicitly restate this—the agent must infer it from the profile or discover it through questioning. Profiles also specify communication styles (e.g., "Cold and concise in expression, lacks emotional communication and patience") that affect how users respond to agent questions.
• Behavior attributes introduce variability in cooperation levels, patience, and goal ambiguity. The paper's user simulator is configured with distinct personality types (impatient, anxious, scattered, dependent, cooperative) that manifest through language style, decision patterns, and emotional expressions. Crucially, behavior is dynamic: "reduced willingness to respond when receiving repetitive answers" is explicitly encoded in the user simulator prompt (Appendix B), meaning agents that ask the same question repeatedly will encounter escalating resistance.
• Dynamic user state $S_{user}$ evolves throughout the interaction. As the user reveals information, their knowledge state changes (they've told the agent about dietary restrictions, so they won't repeat them). As the agent performs well or poorly, the user's patience and cooperation levels shift. This requires agents to continuously adapt their interaction strategy rather than following a fixed script.

What makes this framework operational rather than merely descriptive: The paper does not just define these dimensions—it builds the entire benchmark to instantiate them, then validates that the dimensions actually predict difficulty. Section 5.2 demonstrates that reasoning point count, search space size, tool graph density, and user interaction configuration all correlate with model performance in the expected directions, providing an empirical grounding that transforms the framework from taxonomy to testable theory.

---

Stage I: Framework Design—Building the Tool Ecosystem

The first stage of VitaBench's construction pipeline (Section 3.2) abstracts real-world life-serving platforms into a simplified but faithful simulation environment. This stage produces three artifacts: the tool definitions, the tool dependency graph, and the supporting databases.

Domain selection. The paper selects three domains grounded in actual deployed applications:

• Delivery: food and product delivery services. This domain involves searching for stores and products, creating orders with delivery addresses and time specifications, managing payment, and tracking order status.
• In-store Consumption: dining and other in-person services. This involves searching for restaurants and other service providers, making reservations, managing seating preferences, and processing payments.
• Online Travel Agency (OTA): hotel bookings, attraction reservations, and flight/train ticket management. This involves searching across providers, checking availability, comparing options against constraints, and creating and paying for reservations.

The choice of these three domains is deliberate: they represent the most common real-world agent deployment scenarios, they have complementary tool structures (delivery emphasizes logistics coordination, in-store emphasizes preference matching, OTA emphasizes constraint satisfaction across temporal and spatial dimensions), and their combination in cross-scenario tasks creates genuinely novel coordination challenges.

Tool derivation from real applications. The paper derives simplified API tools by "referencing existing application implementations" and "capturing essential functionalities" (Section 3.2). This is not a random or synthetic toolset—it reflects the actual capabilities that deployed agents need. The resulting toolset contains 66 functions across the three domains plus general utilities (Table 2):

Write tools include operations like create_delivery_order, pay_delivery_order, instore_book, create_train_order, and modify_order. Read tools include operations like delivery_product_search_recommand (sic), get_nearby, train_ticket_search, get_weather, and user_history. General tools include utilities like address_to_longitude_latitude and longitude_latitude_to_distance that are used across all domains.

The distinction between read and write tools is functionally important. Read tools gather information without side effects—they can be called speculatively without consequence. Write tools modify the database state—calling them incorrectly (wrong product, wrong time, wrong user) creates consequences that may be difficult or impossible to undo. An agent that misunderstands when to transition from information-gathering (reads) to action-execution (writes) will fail tasks in ways that reflect real deployment failures.

Tool dependency graph construction. Each tool is augmented with explicit pre-conditions (states required before execution) and post-conditions (expected outcomes after execution). These are not just documentation—they are enforced by the environment's transition function $T_{db}$. If an agent attempts to call modify_order without having first called get_order_detail to obtain a valid order_id, the tool call fails because its pre-condition is unsatisfied.

The pre-condition/post-condition pairs naturally encode inter-tool dependencies as a directed graph $G = (V, E)$. An edge exists from tool $v_i$ to tool $v_j$ if the post-conditions of $v_i$ satisfy the pre-conditions of $v_j$—in other words, if calling $v_i$ enables calling $v_j$. The resulting graph structures vary by domain:

• Delivery has 20 tools, 50 edges, and density $\rho = \frac{50}{20 \times 19} = 13.2\%$. The moderate density reflects workflows like: search for product → create order → pay order, with some branching for modifications and cancellations.
• In-store has 24 tools, 68 edges, density 12.3%. The slightly lower density reflects simpler workflows (search → book → pay) with fewer modification paths.
• OTA has 38 tools, 309 edges, density 22.0%. This dramatically higher density reflects the complexity of travel booking: searching for hotels involves multiple sub-queries (by location, by price, by amenities), checking availability requires cross-referencing dates, and booking often involves packages that span multiple providers. The high density means tool sequencing errors are more likely and more consequential.
• Cross-scenario combines all 66 tools with 512 total edges, density 11.2%. The lower overall density (compared to OTA alone) reflects that most edges are within-domain—cross-domain edges are relatively rare, meaning agents must recognize when to switch between disconnected subgraphs and cannot rely on a single coherent dependency structure.

Why the graph-based design over policy documents: The paper explicitly frames this as a departure from τ-bench and τ²-bench, which "constrain agents through verbose policy documents rather than allowing truly autonomous exploration" (Section 2). By encoding rules in tool pre-conditions and post-conditions rather than in natural language policy text, VitaBench:

1. Forces agents to discover constraints through interaction with the environment rather than by reading documentation—this is closer to real deployment where comprehensive policies rarely exist.
2. Makes the reasoning challenge about causal understanding (what happens if I call this tool without that prerequisite?) rather than reading comprehension (what does paragraph 7 of the policy say?).
3. Enables cross-domain composition naturally—the delivery dependency graph and the OTA dependency graph coexist without requiring a unified cross-domain policy, just as in real life you don't need a "meta-policy" to both order food and book a train.

The paper's example is modify_order requiring prior execution of get_order_detail. In a policy-document approach, the agent would read "Section 3.2: Before modifying an order, you must obtain the order details using get_order_detail." In VitaBench, the agent calls modify_order with an order_id it guessed—and it fails. The agent must then reason backward: "Why did this fail? What information am I missing? What tool would provide it?" This is a qualitatively different cognitive demand.

Database construction. For each task, the environment includes a structured database containing service providers, products, and transaction histories. Table 2 provides aggregate statistics:

• Service providers: 1,324 across all tasks (410 delivery, 611 in-store, 1,437 OTA). Individual tasks involve 5-20 providers.
• Products: 6,946 across all tasks (788 delivery, 3,277 in-store, 9,693 OTA). Individual tasks can include over 100 products in certain cases.
• Transactions: 447 delivery, 48 in-store, 28 OTA, 154 cross-scenario. Transaction histories are included to support requirements involving consumption patterns—for example, "order the same meal as last time" or "book my usual hotel" requires the agent to query past transactions and identify patterns.

The databases are constructed by combining "service provider and product information from real-world life-serving platforms with model-generated synthetic augmentation under human supervision" (Section 3.2). This hybrid approach ensures realism (the distributions of prices, locations, categories reflect actual platform data) while enabling controlled difficulty (the ratio of target to distractor options, the specificity of constraints, the ambiguity of historical patterns).

Database annotation for distractor design. A key design decision is the deliberate intermixing of target options (service providers/products that satisfy all constraints) with distractor options (those that violate specific requirements). The paper states that each task maintains "only a handful of valid solutions per task" within search spaces containing "numerous candidates." For instance, a hotel search might return 20 results where only 2 have river-view rooms at the right price range for the right dates—the other 18 are distractors that superficially match some criteria but fail on others. This creates a needle-in-haystack dynamic where agents must systematically verify all constraints rather than assuming the first plausible-looking result is correct.

Tool definitions as the interface. Each tool is provided to the agent in OpenAI tool schema format (Section 4.1), which includes the tool name, a natural language description, and a JSON schema for parameters. The pre-condition and post-condition information is included in the tool description—but agents must use this information to plan, not just read it. The difference from policy documents is one of granularity and location: constraints are attached to the specific tools they govern rather than centralized in a separate document, making them accessible only when the agent is considering that specific tool.

---

Stage II: Task Creation—From Raw Data to Evaluation Instances

The second stage of the pipeline (Section 3.2, bottom portion of Figure 3) transforms the framework components into concrete, evaluable task instances. Each task is a bundle of four components: user profile, task instruction, environmental information, and rubrics.

User profile construction. User profiles derive from "authentic platform data, which we anonymize and enrich to create distinct personas with varied personal attributes and communication styles" (Section 3.2). The Appendix C example illustrates the richness: a user profile specifies user ID, profession (blue-collar worker), gender (male), age range (30-35), residence and work addresses (specific apartment and industrial park in Harbin), dietary restrictions (avoid high purine foods, avoid fried foods), relationship status (married with children), and personality ("Cold and concise in expression, lacks emotional communication and patience").

These profiles are not just background flavor—they directly determine task constraints. The dietary restriction "avoid high purine foods" means the agent should not recommend seafood-heavy restaurants. The personality "lacks emotional communication and patience" means the user will provide minimal responses and become frustrated quickly if the agent asks redundant questions. The relationship "married with children" combined with "three-generation family" from the instruction implies the presence of both elderly and young children, which the agent should use to infer accessibility and menu requirements even if not explicitly stated.

Knowledge boundaries between agent and user profile. An important design nuance: while user profiles are accessible to agents, the paper establishes "knowledge boundaries to reflect realistic scenarios—for example, agents cannot directly access dietary restrictions but must infer them from order history or user responses" (Section 3.2). This means the agent could look up the user profile to see basic demographics, but sensitive or preference-based information (dietary restrictions, relationship status, even some address details) is not directly queryable—it must be inferred from behavior (past orders, stated preferences) or elicited through dialogue. This creates a natural interaction requirement: the agent cannot simply database-query its way to all constraints but must engage the user in conversation.

User behavior attributes. Beyond static profiles, each simulated user is configured with behavioral attributes that affect conversational dynamics. The paper lists examples (Section 3.2):

• Emotional expressions: impatient, anxious, indifferent, cooperative
• Interaction patterns: detail-oriented (provides extensive information but expects thoroughness in return), dependent (relies heavily on agent recommendations, asks "what do you think?"), logical (proceeds step-by-step, expects clear reasoning), scattered (jumps between topics, mentions constraints out of order)

These attributes are not just labels—they are implemented through the user simulator's prompt (Appendix B), which instructs the simulator to "reflect the personality traits described in <persona>, through language style, emotional expression, word choice, etc." The prompt includes specific behavioral rules that operationalize these traits:

• "If the agent repeats the same question you have already answered in the past 3 times, show impatience and refuse to answer the question" — this directly implements the patience attribute.
• "When the agent tries to persuade you to change your needs, pay attention to sticking to the corresponding needs in <instructions>" — this implements resistance to agent manipulation.
• "Use expressions like 'What do you think would be more suitable?', 'Which one would you recommend?' to seek the agent's advice" — this implements the dependent interaction pattern.

Task instruction synthesis. Each task instruction synthesizes "multiple real user requests into composite objectives" (Section 3.2). This is a crucial design choice: rather than artificial single-goal tasks (e.g., "book a hotel"), VitaBench instructions capture the reality that real user requests often bundle multiple interdependent sub-goals. The paper manually reviews and refines these synthesized instructions to "ensure clarity and feasibility" while preserving the inherent complexity of coordinating multiple objectives.

The Appendix C example demonstrates what this looks like in practice. The instruction bundles four interlocking sub-goals:

1. Find a restaurant near Dalian Port suitable for a three-generation family gathering, with accessibility facilities and dishes suitable for elderly and children, and book it for 6 people at noon on July 27th.
2. Order delivery of a walking cane and adult diapers to arrive at the restaurant around noon.
3. Purchase a high-speed train ticket from Beijing to Dalian for the user's aunt, arriving before 11 AM on July 27th, first class.
4. Arrange transportation from the train station to the restaurant (preferably by taxi, considering elderly and children).

These sub-goals are not independent. The train must arrive before the restaurant booking (temporal constraint). The delivery must arrive at the restaurant (spatial coordination). The restaurant must be near the port because the family boards a cruise ship at 3 PM (temporal-spatial chain). The aunt's arrival must be coordinated with the family gathering (social coordination). An agent that treats each sub-goal as an independent task will fail—for instance, booking a restaurant far from the port because it has better reviews would violate the implicit boarding-time constraint.

Single-scenario vs. cross-scenario tasks. The paper constructs 100 tasks per domain for single-scenario evaluation (delivery-only, in-store-only, OTA-only) and 100 cross-scenario tasks that span multiple domains. The single-scenario tasks present agents with only the tools from that domain (20, 24, or 38 tools respectively), while cross-scenario tasks present all 66 tools simultaneously. This design enables measuring the marginal cost of cross-domain navigation: the performance drop from single-scenario to cross-scenario (visible in Table 3, where even o3 drops from 53.5% on in-store single-scenario to 30.0% on cross-scenario) isolates the specific difficulty of expanded action spaces and domain-context switching.

Environmental information construction. For each task, the environment is populated with:

• Service provider and product data: combining real-world platform data with synthetic augmentation. The paper deliberately intermixes "target options that satisfy all constraints with distractor options that violate specific requirements." Distractors are not random—they are designed to be plausible but wrong, testing whether agents check all constraints or settle for the first match. For instance, a restaurant might be near the port and have good reviews, but lack accessibility facilities. A train might arrive before 11 AM but be second-class rather than first-class. A walking cane might be the right type but from a store too far for timely delivery.
• Transaction histories: generated to support requirements involving consumption patterns. These are essential for tasks where users reference past behavior ("order the same as last time," "book my usual hotel"). The agent must query the transaction history, identify the relevant pattern, and apply it to the current context.
• Temporal context: the current system time (e.g., "June 24" in Figure 3, though the example in Appendix C uses July 27th) and any date-specific constraints. The time is provided in the environment prompt (Appendix B agent system prompt: "Current time: {time}"), establishing the temporal frame for all scheduling decisions.
• Spatial context: geographic coordinates of all relevant locations (restaurants, train stations, delivery addresses), enabling tools like address_to_longitude_latitude and longitude_latitude_to_distance to function. The Appendix C example shows the agent converting "Dalian Port" to coordinates (121.650595, 38.92656), searching for nearby services within 2000m, and computing the 1573m distance to a candidate restaurant.

Iterative refinement pipeline. The paper emphasizes that each task undergoes "multiple trials with human verification, eliminating ambiguities while preserving multiple valid solution pathways" (Section 3.2). This is a critical quality control step. The goal is not to create tasks with exactly one correct sequence of actions—that would be brittle and unrealistic—but to ensure that the rubric criteria correctly identify successful task completion regardless of the specific path taken. The refinement process involves:

1. Running the task with model agents to identify failure modes that are task problems rather than agent problems (ambiguous instructions, contradictory constraints, impossible requirements).
2. Adjusting instructions and database content to eliminate these while preserving the intended complexity.
3. Verifying that multiple different approaches can succeed—for instance, an agent might book the restaurant first then order delivery, or order delivery first then book the restaurant, and both should be valid as long as all constraints are ultimately satisfied.

Language and localization. The paper notes that "the majority of data is originally in Chinese" because the tasks are grounded in real-world Chinese life-serving platforms, but "we are also preparing an English version of the dataset to facilitate broader research use" (Section 3.2, footnote). The example in Appendix C is presented in English, demonstrating that the task structure and complexity are language-independent even if the original platform data was Chinese. This is relevant for interpreting results: models may perform differently on Chinese vs. English versions of the same task, and the current leaderboard presumably reflects the original language distribution of the data.

Data statistics summary. Table 2 provides aggregate counts across all 400 tasks. The important numbers are not just the totals but the distribution across domains, which explains why certain domains are harder:

• Delivery has the fewest products (788) but the second-highest reasoning points (7.4 per task, per Table 5). The difficulty comes not from search space size but from coordinating multiple items under strict temporal and spatial constraints (delivery time windows, address accuracy, product availability).
• In-store has the most products (3,277) but the fewest reasoning points (5.6 per task). The large search space is primarily a filtering challenge—find the restaurant matching the constraints—rather than a coordination challenge. This explains the counterintuitive finding that in-store has the highest single-domain performance (42.1%) despite the largest product database.
• OTA has the most service providers (1,437), the most products (9,693), and the most reasoning points (9.7 per task). It combines large search spaces with complex constraint satisfaction (dates, prices, seat types, locations), producing the lowest single-domain performance (20.7%).
• Cross-scenario combines everything and adds the challenge of domain switching, producing the worst performance (16.2%).

---

The User Simulator and Environment Dynamics

The user simulation is implemented by gpt-4.1-2025-04-14 (Section 4.1) using a detailed system prompt (Appendix B) that operationalizes the interaction complexity dimension. Understanding how this simulator works is essential for interpreting what agent failures actually mean—if the simulator is unreliable, benchmark results are uninformative; if it is too predictable, interaction complexity is not actually being tested.

Simulator architecture. The user simulator receives two key inputs wrapped in XML-like tags:

• <persona>: Contains the user's profile information (demographics, dietary restrictions, personality description) and behavioral instructions. For the Appendix C example, this would include age, gender, occupation, dietary restrictions, and the "cold and concise" personality descriptor.
• <instructions>: Contains the full task description with all requirements, constraints, and sub-goals. Critically, the simulator is told everything upfront—but instructed NOT to reveal everything at once.

The simulator operates under a set of rules organized into four categories:

Conversation Style Rules. These govern how the user expresses themselves, not what information they convey:

• "Generate only one line of content each time to simulate user messages" — this prevents the simulator from dumping all requirements in a single long message, creating natural turn-taking.
• "Use a combination of context description + need expression, first describe the background situation, then express specific needs" — this creates realistic conversational framing rather than bullet-point requirement lists.
• "When you need to make decisions, provide the conditions and preferences from instructions, and let the agent help you choose" — this implements the "dependent" behavior pattern: the user provides constraints but defers the actual selection to the agent.
• "Use expressions like 'What do you think would be more suitable?', 'Which one would you recommend?' to seek the agent's advice" — this creates natural dialogue patterns that agents must interpret as implicit requests for action.
• "Must reflect the personality traits described in <persona>, through language style, emotional expression, word choice, etc." — this is the mechanism by which behavioral attributes become observable in conversation. A "cold and concise" user will give terse responses; an "anxious" user will express urgency and concern; a "detail-oriented" user will ask follow-up questions about specifics.

Information Disclosure Rules. These are the core mechanism for creating progressive information revelation—the property that makes interaction genuinely complex:

• "Break down information from instructions into multiple independent points, mentioning them separately in different rounds" — this is the fundamental rule preventing information dumping. The simulator must parse the compound instruction into atomic requirements and dole them out over time.
• "Directly convey the original information content from instructions, but adjust the conversation style and expression according to the personality traits in <persona>" — the facts must be accurate to the instruction, but the presentation varies by persona.
• "Must ensure every detail from instructions is mentioned during the conversation, even seemingly background information should be mentioned, as this information may affect the agent's recommendations and arrangements" — this ensures that all constraints are eventually communicated, preventing tasks from being impossible. The challenge is when they are mentioned, not whether they are mentioned.
• "Avoid revealing all needs in the first round, let information unfold gradually" — the explicit instruction to delay, creating the need for agents to actively elicit information across multiple turns.

Information Processing Rules. These govern how the simulator responds to agent questions:

• "Answer the agent's questions based on <persona> and <instructions>. If there's no corresponding answer, reply that you don't remember or don't know" — this is the fidelity constraint: the simulator cannot hallucinate information not provided in the original instruction. If the agent asks about something the instruction doesn't cover, the user says "I don't know" rather than inventing an answer.
• "When the agent asks for information, provide the answer immediately" — users don't play games with direct questions. If the agent asks "how many people?", the user answers. The difficulty is not in extracting answers to direct questions but in knowing which questions to ask.
• "Don't fabricate information not provided in the instructions" — a second fidelity constraint, preventing the simulator from being "helpful" in ways that reduce task difficulty.
• "Strictly provide needs according to requirements explicitly stated in instructions, don't assume, expand, substitute, or generalize" — this prevents the simulator from filling in gaps that would make the task easier. If the instruction says "first class," the simulator won't accept "business class" as equivalent even if the agent suggests it.
• "If the agent asks whether you need help placing an order, answer 'Yes, please help me place the order'" — a standardization rule to ensure consistent task progression across runs.
• "Maintain dependence on the agent's service, keep the conversation going until the task is completed" — prevents the user from prematurely ending the conversation.
• "When the agent tries to persuade you to change your needs, pay attention to sticking to the corresponding needs in <instructions>" — this implements resistance to agent manipulation, testing whether agents respect constraints versus trying to talk users out of them.
• "If the agent repeats the same question you have already answered in the past 3 times, show impatience and refuse to answer the question" — this is the patience mechanism. It creates a direct cost for redundant questioning, forcing agents to track what information they've already gathered and avoid re-asking. The "refuse to answer" behavior changes the interaction dynamic from cooperative to adversarial, which agents must recognize and adapt to.

Conversation Ending Rules. These define when the interaction can terminate:

• The user should NOT end the conversation before all needs are expressed and all tasks completed, or if the agent's execution results are incorrect or incomplete.
• The user CAN end the conversation only when all tasks are correctly completed, or when all needs are expressed but the system explicitly states it cannot complete due to technical limitations.

Environment tool execution ($T_{db}$). The database side of the environment implements deterministic transitions through Python functions. When an agent calls a tool:

1. The environment validates that all required parameters are present and of correct types.
2. It checks pre-conditions against the current database state—if modify_order requires a valid order_id, and the provided ID doesn't exist or isn't associated with the current user, the call fails with an appropriate error.
3. If pre-conditions are satisfied, the environment executes the tool logic (searching databases, creating records, updating statuses) and returns structured feedback.
4. Post-conditions are applied to the database state—a successful create_delivery_order adds a new order with status unpaid, while a successful pay_delivery_order transitions that order to paid.

The deterministic nature of $T_{db}$ is important: given the same database state and the same tool call, the outcome is always the same. This makes the benchmark reproducible in its environmental dynamics, with stochasticity entering only through the user simulator ($T_{user}$) and the agent's own sampling ($\pi_\theta$).

Reliability validation of the user simulator (Section 5.1). The paper validates the simulator along two dimensions:

• Information fidelity: Two human annotators assessed 100 conversations for (a) adherence to task instructions and user profiles, (b) absence of hallucinations (the simulator making up information not in the original instruction), and (c) contextual relevance. The simulator achieved an average score of 9.48/10, with "minor deviations" manifesting as natural conversational variations (e.g., "cannot eat spicy" vs. "prefer non-spicy food") that "enhance dialogue authenticity without compromising task requirements." Crucially, the simulator "appropriately responds 'I don't know' when queried about unprovided information, maintaining strict source fidelity."
• Persona consistency: Five distinct personality types were tested across 100 conversations, measuring "behavioral alignment through language style, decision patterns, and emotional expressions." The average score was 9.34/10. Cooperative personas exhibited the highest consistency (9.8/10), which the paper attributes to LLMs' inherent collaborative tendencies. Scattered personas showed lower controllability (8.9/10), suggesting that inconsistent, topic-jumping behavior is harder for the simulator to maintain convincingly.

These validation results establish that the user simulator is reliable enough for benchmark use—it rarely fabricates information, it consistently expresses the assigned persona, and deviations are natural variations rather than task-compromising errors. The remaining 9.2% of errors attributed to the user simulator in the failure analysis (Figure 9) represent inherent stochastic behavior that the paper mitigates through multiple runs (Section 5.3).

---

The Rubric-Based Sliding Window Evaluator

Evaluating agent trajectories on VitaBench presents a unique challenge that existing methods cannot address: trajectories are long (50-100 turns per Table 1), have multiple valid solution paths (different sequences of tool calls and dialogue that satisfy the same constraints), and include requirements that don't modify database state (recommendations, planning, preference explanations). The paper's evaluator (Section 3.3) addresses these challenges through a combination of rubric decomposition, sliding window processing, and persistent state tracking.

Why state-based evaluation fails. Prior benchmarks, notably τ-bench (Yao et al., 2024), evaluate success by comparing the final database state to an expected state—did the agent create the right order with the right parameters? This approach has two fundamental limitations that make it unsuitable for VitaBench:

1. It cannot capture requirements that leave the database unchanged. If the task requires the agent to recommend a restaurant based on complex preferences but does not require booking it, the database state doesn't change regardless of whether the recommendation was correct. Similarly, planning tasks (like the Appendix C taxi route recommendation from the train station to the restaurant) are purely informational—the agent provides advice, but no database record is created. State-based evaluation would mark such tasks as trivially successful (no harmful state changes occurred) or impossible to evaluate (nothing to check).

2. It cannot provide intermediate supervision or partial credit. Knowing only that an agent failed is far less useful than knowing which of the 10+ constraints it violated. State-based evaluation produces a single binary judgment; rubric-based evaluation produces a vector $s \in \{0, 1\}^k$ showing exactly which criteria were satisfied and which weren't. This is essential for failure analysis and for providing the "dense signals for reinforcement learning" that the paper notes in Section 3.3.

Rubric decomposition. For each task, human annotators manually design a set of atomic rubric criteria $R = \{r_1, r_2, \ldots, r_k\}$. Each rubric $r_j$ is a specific, verifiable requirement derived from the task information. The Appendix C example would have rubrics like:

• "Restaurant is near Dalian Port" (spatial constraint)
• "Restaurant has accessibility facilities" (explicit constraint from instruction)
• "Restaurant is suitable for three generations (elderly and children)" (implicit constraint requiring inference)
• "Restaurant reservation is for 6 people at 12:00 on July 27th" (temporal and quantity constraint)
• "Delivery order includes one walking cane" (product constraint)
• "Delivery order includes adult diapers" (product constraint)
• "Delivery is to Harbor Family Feast Restaurant" (spatial coordination)
• "Delivery arrives around noon" (temporal constraint)
• "Train ticket is from Beijing to Dalian on July 27th" (spatial-temporal constraint)
• "Train is high-speed rail, first class" (service class constraint)
• "Train arrives before 11:00 AM" (temporal constraint)
• "Route recommendation from train station to restaurant" (informational requirement)
• "Reminders are set for departure and arrival" (service requirement)

Note the diversity: some rubrics check database state (order exists with correct parameters), some check conversation content (did the agent recommend a suitable route?), some check inference quality (did the agent recognize that "three generations" implies elderly and children needs?), and some check purely informational outputs (were reminders set?). State-based evaluation would capture only the database-modifying rubrics (orders, reservations, payments), missing the recommendation, planning, and communication requirements entirely.

Why LLM-as-a-Judge for rubric evaluation. The paper uses claude-3.7-sonnet as the evaluator, following the precedent of recent rubric-based evaluation methods (Arora et al., 2025; Ruan et al., 2025) that showed LLMs can "effectively replace fine-grained human judgments while maintaining high accuracy." The rationale is practical: evaluating each of the 400 tasks × 4 runs × number of models manually would be prohibitively expensive, and the rubric structure provides sufficient constraint that an LLM evaluator can make reliable binary judgments per criterion. The paper validates this assumption in Section 5.1.

The sliding window mechanism. The core technical challenge is that long trajectories (50-100 turns) exceed the context length limits of evaluator models, or at least degrade their performance when processed in full. The paper's solution is to process trajectories in overlapping windows while maintaining persistent state:

1. Window segmentation: Each trajectory is divided into windows $W_i$ of $w$ consecutive turns (where $w = 10$ per the evaluator prompt in Appendix B), with adjacent windows sharing $\delta$ overlapping turns ($\delta = 2$ per the prompt). The overlap ensures that information spanning window boundaries is not lost—a constraint mentioned by the user in turn 9 and satisfied by the agent in turn 11 will appear in both window $W_1$ (turns 1-10) and window $W_2$ (turns 9-18).

2. Persistent rubric state: The evaluator maintains a state vector $s \in \{0, 1\}^k$ where $s_j = 1$ means rubric $r_j$ has been satisfied at some point in the trajectory (up to and including the current window). This state is initialized to all zeros and is passed forward from window to window as <current_rubrics> in the evaluator prompt.

3. Monotonic satisfaction with reversal allowed: Once a rubric is marked as satisfied ($s_j = 1$), it generally stays satisfied—the principle being that if the agent correctly performed an action earlier, later failures shouldn't erase that success. However, the evaluator prompt includes an important exception: "You can also update true back to false, if and only if the assistant overturned a previous correct conclusion in this window." This handles cases where the agent initially makes a correct booking but then incorrectly modifies or cancels it—the rubric satisfaction is genuinely reversed.

4. Window processing: For each window $W_i$, the evaluator receives:

   • The current window's conversation content (<window_content>)
   • The current state of all rubrics (<current_rubrics>)
   • The full user instruction for context (<user_instruction>)
   • The environmental information (database, providers, products)

   The evaluator's task is to update the rubric state based on what occurred in this window. The output is a JSON array where each element specifies the rubric key, a restatement of the rubric, a justification for the status change, and the updated meetExpectation boolean.

5. Final scoring: After all windows are processed, the final score is strict all-or-nothing:

$\text{score} = \mathbb{1}\left[\sum_{j=1}^k s_j = k\right]$

This is an indicator function $\mathbb{1}[\cdot]$ that returns 1 if all rubrics are satisfied and 0 otherwise. The paper emphasizes that while the benchmark uses this strict scoring, the fine-grained rubric-level data enables "detailed scoring analysis for identifying trajectory differences" and could support partial-credit evaluation in other contexts.

Why strict all-or-nothing: The paper's choice of strict scoring reflects a deployment-oriented perspective: in real applications, a task that is 90% complete is still a failure if the missing 10% is "purchased the correct train ticket" rather than "sent a follow-up reminder." Partial credit metrics would obscure the fact that agents are failing in ways that would be unacceptable in production. The rubric-level data provides the granularity for understanding how close agents got to success without diluting the binary success metric.

Evaluator validation (Section 5.1). The paper conducts ablation experiments comparing four evaluator configurations on GLM-4.5's cross-scenario trajectories:

The key findings:

• Both the sliding window and the rubric structure are essential. Removing the rubric (configurations 3 and 4) causes Cohen's κ to plummet below 0.07, indicating near-zero agreement with human judgments. The evaluator, lacking structured criteria, defaults to being overly generous—marking 91% and 82% of trajectories as successful when human annotators identified failures.
• The sliding window improves agreement quality over full trajectory processing. While the full-trajectory-with-rubric configuration yields a similar final score (19% vs. 20%), its Cohen's κ of 0.604 is substantially lower than the baseline's 0.828. The paper attributes this to "the evaluation model's limited long-context capability hindering accurate assessment of all rubrics in the full trajectory"—the evaluator LLM loses track of earlier rubric criteria when processing very long contexts. The sliding window's decomposition into manageable segments with persistent state tracking mitigates this.
• The baseline's 0.828 Cohen's κ indicates "strong" inter-rater agreement (conventionally, κ > 0.8 is considered strong agreement). This validates that the rubric-based sliding window evaluator produces judgments consistent with human evaluation, establishing it as a reliable automated evaluation method.

The paper also reports 95% task-level accuracy for the baseline (the fraction of tasks where the evaluator's binary success/failure judgment matches the human annotator's judgment), indicating that disagreements are concentrated in specific edge cases rather than uniformly distributed.

Statistical reliability of evaluation (Section 5.1). Beyond evaluator accuracy, the paper addresses a second source of variance: agent stochasticity. Even with temperature set to 0.0 (Section 4.1), "cumulative perturbations in multi-turn interactions amplify into divergent trajectories." To determine the optimal number of evaluation runs, the paper conducts a resampling analysis:

• 32 independent trials were run for representative models.
• For each $k \in [1, 20]$, the Mean Squared Error (MSE) of $k$-run average estimates relative to the expected value (32-run average) was computed by sampling different $k$-combinations from the 32 trials.
• $k = 4$ runs achieved "optimal balance between statistical precision and computational cost," reducing MSE by 77.5% compared to $k = 1$. Increasing to $k = 8$ provided only marginal additional reduction despite doubling computational overhead.

This analysis justifies the paper's choice of 4 runs for main experiments (Section 4.1). The finding that even temperature-0.0 models produce divergent trajectories highlights a subtle but important property of multi-turn agent benchmarks: determinism at the token level does not guarantee determinism at the trajectory level, because small differences in early turns compound through the user simulator's state-dependent responses.

---

Experimental Methodology: Models, Metrics, and Run Configuration

The experimental setup (Section 4.1) involves careful choices about which models to evaluate, how to configure them, and how to measure performance. These choices reflect the benchmark's difficulty and the paper's goal of comparing thinking vs. non-thinking model behaviors.

Model selection and categories. The paper evaluates "various state-of-the-art proprietary and open language models" across two categories:

• Non-thinking models: Standard autoregressive LLMs without explicit chain-of-thought reasoning mechanisms enabled. This includes GPT-4.1, GPT-5 (minimal), Claude-4-Sonnet, Claude-4.1-Opus, Gemini-2.5-Flash, DeepSeek-V3 series, Qwen3 series (non-thinking configurations), Doubao-Seed-1.6, Kimi-K2, GLM-4.5, and LongCat-Flash-Chat.
• Thinking models: Models with explicit reasoning mechanisms—either built-in (o3, o4-mini, DeepSeek-R1) or toggled on via configuration (Claude and Gemini series with "thinking on," Qwen3-Thinking, GLM-4.5 with thinking, LongCat-Flash-Thinking, Doubao-Seed-1.6-Thinking). For these models, the paper follows "official guidelines to enable high reasoning efforts" (Section 4.1, footnote 4).

The paper explicitly excludes "small models (< 32B parameters) due to the difficulty of our benchmark" (Section 4.1). This is a practical recognition that the benchmark's complexity makes it unsuitable for evaluating smaller models that would score near zero—the benchmark is designed to discriminate among frontier models, not to provide a universal difficulty gradient.

Model configurations. Several important configuration details:

• Thinking mode toggling: For hybrid models (Claude, Gemini, Qwen3, GLM) that support both thinking and non-thinking modes, the paper evaluates both configurations separately. This enables measuring the marginal benefit of reasoning mechanisms on the same base model—for instance, Claude-4.1-Opus improves from 21.8% to 29.0% with thinking enabled.
• DeepSeek-V3.1 and V3.2 limitation: The paper notes that these models "only support tool calling in non-thinking mode" (Table 3 footnote), meaning they are evaluated only in the non-thinking category.
• Temperature: 0.0. All models are run with temperature 0.0 "to promote deterministic outputs" (Section 4.1). However, as noted in the statistical reliability analysis, this does not guarantee trajectory-level determinism because the user simulator's stochastic responses create divergent paths even from identical agent actions.
• Unlimited interaction rounds. The paper does not limit the number of interaction rounds; the task terminates only when the agent outputs ###STOP### or encounters a failure. This means agents can take as many turns as they need, creating an inherent tradeoff between thoroughness and efficiency (visible in Figure 5's performance-vs-turns analysis).

Agent implementation. All agents are implemented as "function-calling agents, with all tools provided in the OpenAI tool schemas" (Section 4.1). This means:

• The agent receives the full list of 66 tools (or domain-specific subset) in the format expected by OpenAI's function-calling API, including tool names, descriptions, and parameter schemas.
• At each turn, the agent outputs either a tool call (with function name and parameters in JSON) or a text response to the user.
• The environment executes tool calls and returns structured feedback, which is appended to the conversation history.
• The agent's policy $\pi_\theta$ is the model's native function-calling behavior, not a custom agent framework—the benchmark evaluates the model's built-in capabilities without architectural modifications.

User simulator model. The user simulator is implemented using gpt-4.1-2025-04-14 (Section 4.1). This is a deliberate choice to avoid overlap with evaluated models (using a different model family for simulation prevents self-play artifacts where the agent and simulator share inductive biases). The specific version pinning (gpt-4.1-2025-04-14 rather than a generic "gpt-4.1") indicates commitment to reproducibility—future version changes could alter simulator behavior.

Evaluator model. The evaluator uses claude-3.7-sonnet (Section 4.1), again to avoid overlap with agent models. The choice of a different model family for evaluation (Claude) versus simulation (GPT) further reduces the risk of systematic biases from shared model properties.

Metrics. Three complementary metrics are reported (Section 4.1):

• Avg@4: The average success rate across 4 independent runs. For each task, this is the fraction of the 4 runs that succeeded, averaged across all tasks. This is the primary metric used for leaderboard ranking (Table 3 is sorted by Avg@4 on cross-scenario tasks).
• Pass@4: The probability that at least one out of 4 i.i.d. task trials is successful. Formally, for tasks where each run succeeds independently with probability $p$, $\text{Pass}@4 = 1 - (1-p)^4$. This metric captures whether the model has any capability of solving the task—a high Pass@4 but low Avg@4 indicates that the model sometimes succeeds but is inconsistent.
• Passˆ4: The probability that all 4 i.i.d. task trials are successful. Formally, $\widehat{\text{Pass}}@4 = p^4$. This metric captures reliability—a high Passˆ4 indicates that the model consistently succeeds, while a low Passˆ4 (which is common, with even top models dropping to near-zero on cross-scenario tasks) indicates that success is rare and unrepeatable.

Why these three metrics: The combination of Avg@4, Pass@4, and Passˆ4 provides a richer picture of model capability than any single metric. A model with Avg@4 = 25%, Pass@4 = 60%, Passˆ4 = 1% (roughly Claude-4.5-Sonnet on cross-scenario) tells a specific story: the model succeeds on a task about 25% of the time, on 60% of tasks it succeeds at least once in 4 tries, but on almost no tasks does it succeed all 4 times. This pattern indicates that success is possible but unreliable—the model has the capability but cannot execute it consistently. This insight is critical for deployment decisions: a model with high Pass@4 but low Passˆ4 might be useful with a voting or retry mechanism, while a model with high Avg@4 but low Pass@4 would indicate that success is concentrated on a specific subset of tasks.

Pass@k and Passˆk analysis (Section 4.2, Figure 4). The paper extends the analysis to $k = 32$ for two representative models (Claude-4-Sonnet and GPT-4.1), revealing several patterns:

• Pass@k (the probability of at least one success in k trials) increases with k, eventually reaching approximately 73% for Claude-4-Sonnet at k=32. This confirms that exploration helps—more attempts increase the chance of stumbling onto a successful trajectory.
• Passˆk (the probability of all k trials succeeding) drops rapidly, approaching near-zero by k=10 for both models. This confirms that fundamental stability challenges exist—models cannot reliably reproduce success even given many attempts.
• The gap between Pass@k and Passˆk widens dramatically with k, illustrating that increased sampling reveals the underlying inconsistency rather than resolving it.

This analysis supports the paper's conclusion that "exploration improves performance but reveals stability issues" and suggests that "complex environments reward exploration, which suggests promising directions for RL approaches" (Section 4.2).

Task run count justification. As discussed in the statistical reliability analysis, the paper settles on 4 runs per task based on MSE minimization: "k = 4 runs achieve optimal balance between statistical precision and computational cost" (Section 5.1). With 400 tasks × 4 runs = 1,600 total evaluations per model, and approximately 30 models evaluated (counting both thinking and non-thinking configurations), the total evaluation budget is substantial—roughly 48,000 task runs—motivating the careful econometric justification for the run count choice.

Prompt templates (Appendix B). Three prompt templates are provided:

• Agent system prompt: Includes the current time, tool usage guidelines (determine if all parameters are known before calling tools, ask user for missing parameters, complete tasks based on pre-conditions and post-conditions), and conversation guidelines (only use information from context, focus on completing user needs, ask if there are other needs after completion, generate ###STOP### when done).
• User simulation prompt: Contains the persona, instructions, and the four categories of rules (conversation style, information disclosure, information processing, conversation ending) discussed earlier.
• Sliding window evaluator prompt: Contains the environmental information, user complete instruction, background on sliding window evaluation, task description (update rubric status based on current window content), and format requirements (JSON output with rubric key, restatement, justification, and meetExpectation field).

These prompts are reproduced in full in Appendix B, providing the complete specification needed for reproduction. The agent prompt's instruction to "only use information from the above context, prohibit constructing information without basis" is notable—it explicitly instructs against hallucination, testing whether models can comply with this constraint during complex multi-turn interactions.

---

Design Choices and Their Justifications (Summary)

VitaBench's design reflects a coherent philosophy about what constitutes meaningful agent evaluation:

• POMDP formalism over ad-hoc task definition: Grounding the benchmark in a formal framework ensures that complexity dimensions are systematically varied rather than haphazardly accumulated, and enables the validation that complexity metrics predict difficulty (Section 5.2).
• Tool graph encoding over policy documents: Shifts the reasoning challenge from reading comprehension to environmental exploration, better matching real deployment conditions where comprehensive documentation is unavailable.
• Authentic platform data with synthetic augmentation over purely synthetic data: Ensures ecological validity (the distributions of products, prices, locations reflect real user experiences) while enabling controlled difficulty through distractor ratios and constraint specificity.
• Three complementary metrics (Avg@4, Pass@4, Passˆ4) over single-metric reporting: Provides a multi-faceted view of model capability that distinguishes between models that sometimes succeed (high Pass@4) from models that consistently succeed (high Passˆ4).
• Rubric-based sliding window evaluation over state-based comparison: Captures recommendation, planning, and communication requirements that leave database state unchanged, and provides the granular failure signal needed for diagnosis and improvement.
• Temperature 0.0 with multiple runs over temperature > 0: Attempts to maximize reproducibility while acknowledging that multi-turn interaction amplifies small perturbations, using multiple runs to characterize the resulting variance rather than pretending it doesn't exist.
• Separate model families for agent, simulator, and evaluator: Prevents shared inductive biases from inflating performance estimates (e.g., a GPT-based agent might perform artificially well with a GPT-based simulator due to shared conversational patterns).

4. Key Insights and Innovations

Innovation 1: Operationalizing a Formal Complexity Theory as a Benchmark Design Principle, Not Just a Taxonomy

The most intellectually distinctive contribution of VitaBench is not the benchmark itself but the theoretical architecture that produced it. The paper takes a step that almost no prior agent benchmark has taken: it begins with a formal definition of what task complexity means—the POMDP-grounded three-dimensional vector $C_{task} = \langle C_{reason}, C_{tool}, C_{interact} \rangle$—and then uses that definition as a design constraint rather than a post-hoc descriptive label. This inverts the typical benchmark construction workflow, where tasks are created ad-hoc from domain expertise and complexity is analyzed retrospectively (if at all).

What the field did before: Prior benchmarks accumulate difficulty haphazardly. ToolLLM (Qin et al., 2024) increases tool count. τ-bench (Yao et al., 2024) adds statefulness and user profiles. ToolSandbox (Lu et al., 2025) adds inter-tool dependencies. Each benchmark identifies some missing element of prior work and adds it, but without a theoretical framework for determining whether the resulting combination adequately captures real-world complexity. The consequence, as Table 1 demonstrates, is that every existing benchmark has at least one dimension where it addresses complexity only partially or not at all—not because the authors were negligent, but because they lacked a completeness criterion for benchmark design. The field had no language for saying "this benchmark tests tools but fails to test interaction, and here is why that matters."

Why the formal complexity framework is a fundamental advance, not incremental: The three-dimensional complexity vector $C_{task}$ transforms benchmark design from an art into a science by providing:

1. A completeness check: Given a candidate benchmark, one can ask: does it instantiate all three dimensions simultaneously? Prior benchmarks fail this check not because they are "bad" but because they were designed without it. VitaBench passes because it was designed with it.

2. A falsifiable theory of difficulty: The paper does not merely assert that reasoning, tool, and interaction complexity matter—it operationalizes them with measurable proxies (reasoning points, search space size, tool graph density, presence/absence of behavior attributes) and then empirically validates that these proxies predict model performance across domains (Section 5.2, Table 5). The finding that OTA's 22.0% graph density corresponds to the lowest single-domain performance (20.7%), while in-store's 12.3% density corresponds to the highest (42.1%), despite in-store having far more products, is evidence that the framework captures something real about difficulty rather than merely redescribing it.

3. A vocabulary for diagnosing model failures: The error pattern analysis (Section 5.3, Figure 9) directly uses the three dimensions to categorize failures: reasoning errors (61.8%), tool-use errors (21.1%), interaction errors (7.9%). This is not post-hoc labeling—the dimensions were defined before evaluation, enabling the analysis to reveal which complexity sources dominate real failure modes.

Comparison to prior theoretical frameworks: The paper draws on Liu and Li's (2012) task complexity theory from organizational psychology, which examines structural, resource, and interaction dimensions. But that framework was developed for human task analysis in industrial settings—it had never been adapted to LLM agent evaluation. The paper's translation of "structural complexity" into tool graph metrics (cardinality, edge density, coverage ratio), "resource complexity" into reasoning metrics (observation space entropy, partial observability coefficient), and "interaction complexity" into user profile and behavior attribute modeling is a genuine intellectual synthesis, not a borrowed label. The POMDP formalism provides the mathematical scaffolding that makes these translations precise rather than metaphorical.

The significance beyond raw performance: The complexity framework's value is not measured by how well models score on VitaBench—it is measured by whether it changes how other researchers think about benchmark design. A researcher building a new agent benchmark after reading this paper should ask: "Does my benchmark simultaneously challenge reasoning, tool, and interaction complexity? Can I measure how much of each dimension I'm testing? Can I validate that my difficulty metrics predict actual model performance?" Prior to VitaBench, these questions had no established vocabulary. After VitaBench, they do. That is the mark of a conceptual contribution: it provides tools for thinking that outlast the specific instantiation.

The evidence anchor: Table 1 is the most important exhibit for this innovation, not because it shows VitaBench scores high on all dimensions (though it does) but because it makes the incompleteness of prior work visible in a systematic way. The pattern of "✓⁻" and "✗" across the three dimensions for every prior benchmark is not cherry-picked criticism—it is a structural diagnosis that explains why the field's understanding of agent capability has been systematically distorted: benchmarks strong on tools but weak on interaction make models look more capable than they are, while benchmarks strong on interaction but weak on reasoning miss fundamental planning deficiencies. VitaBench's simultaneous ✓ across all dimensions is not an incremental improvement—it is a qualitative shift in evaluation philosophy.

---

Innovation 2: Encoding Domain Rules in Tool Dependency Graphs Rather Than Policy Documents—A Shift from Reading Comprehension to Environmental Reasoning

VitaBench's most concrete design innovation is its elimination of domain-specific policy documents in favor of encoding all operational constraints directly into the tool dependency graph through pre-condition and post-condition annotations. This is not a minor implementation detail—it fundamentally changes what skill the benchmark measures.

The dominant prior approach and why it's problematic: The τ-bench family (Yao et al., 2024; Barres et al., 2025) provides agents with verbose natural language policy documents that specify, for example, "When a user requests a flight change, first verify the ticket is refundable by checking the fare class in the booking details. Then calculate the change fee according to the table in Section 4.2..." This approach tests whether an agent can read, comprehend, and follow explicitly stated rules—a skill that is certainly useful but that does not correspond to the primary challenge of real-world deployment. In production environments, comprehensive policy documentation is rarely available, and when it exists, it is often incomplete, out of date, or written for human operators rather than AI agents. An agent that excels at reading policies but cannot autonomously discover constraints through interaction will fail in practice, regardless of benchmark scores.

What VitaBench does instead: The tool dependency graph $G = (V, E)$, where edges encode pre-condition/post-condition relationships, makes the environment itself the source of constraint information. The agent who attempts modify_order without first calling get_order_detail does not fail because a policy document was violated—it fails because the tool's pre-condition is unsatisfied, and the environment returns an error. The agent must then reason backward from the failure: "Why did this call fail? What information am I missing? Which tool would provide it?" This is environmental reasoning—discovering the rules of the world through interaction—rather than reading comprehension.

Why this is a fundamental shift, not a superficial tweak:

1. It changes what failure looks like and what recovery requires. In a policy-document benchmark, failure from policy violation means the agent didn't read carefully enough—recovery means re-reading the relevant section. In VitaBench, failure from pre-condition violation means the agent made an incorrect assumption about the environment—recovery means forming and testing a new hypothesis. These are qualitatively different cognitive processes, and the latter is far more relevant to autonomous deployment.

2. It naturally enables cross-scenario composition. Policy documents are domain-specific by nature—an airline booking policy and a restaurant reservation policy are separate documents with separate rules. An agent switching between domains must context-switch between entirely different textual rule sets. In VitaBench, all tools across all domains share the same underlying mechanism (pre-conditions, post-conditions, graph edges), so domain-switching is a matter of recognizing that the agent has entered a different region of the tool graph rather than consulting a different document. The cross-scenario setting's 512 dependency edges across 66 tools would be almost impossible to specify coherently as a unified policy document—but as a unified graph, it emerges naturally from the per-tool annotations.

3. It makes difficulty a property of the environment structure rather than the documentation complexity. The tool graph metrics—cardinality, edge density, coverage ratio—quantify how hard it is to discover the right sequence of actions. These are objective properties of the tool definitions that can be computed without reference to any specific task. In contrast, policy document difficulty is subjective—it depends on writing clarity, document length, and the agent's reading comprehension capability, making it impossible to separate "the task is hard" from "the documentation is poorly written."

What this reveals about prior benchmarks: The paper's framing (Section 2) suggests that τ-bench and similar benchmarks have been measuring a confounded mixture of agent capability and documentation quality. A model that performs well on τ-bench might genuinely understand airline booking workflows, or it might simply be good at reading policy documents. VitaBench disentangles these by removing the documentation layer entirely, forcing agents to rely on the same capability they would need in deployment: learning through interaction.

The subtlety that makes this innovative rather than obvious: The tool graph design is not merely "removing policy documents and adding pre-conditions"—it is recognizing that the pre-condition/post-condition structure is a more faithful representation of how real-world constraints actually manifest. In a real food delivery platform, there is no centralized policy document stating "you must call get_order_detail before modify_order." Instead, the modify_order API endpoint simply requires a valid order_id parameter and returns an error if one isn't provided. Developers learn this constraint not by reading documentation but by encountering the error and reasoning backward. VitaBench's alignment with this reality means that agent performance on the benchmark is more predictive of agent performance in production—the benchmark measures the skill it claims to measure.

Evidence from the results that supports this claim: The catastrophic performance drop in cross-scenario settings—from ~50% single-scenario to 30% for even the best model—is partially attributable to the tool graph design. In single-scenario tasks, agents face a manageable dependency graph (20-38 tools, 50-309 edges) from a single domain. In cross-scenario, they face all 66 tools with 512 edges, and must determine which subgraph is relevant to each phase of the task. An agent that had learned to rely on policy documents for navigation would be completely lost. An agent that understands graph-structured dependencies can, in principle, navigate the expanded space—but the results show that current agents cannot do this reliably, confirming that the tool graph design is testing a capability that prior benchmarks left untested.

---

Innovation 3: The Rubric-Based Sliding Window Evaluator as a General-Purpose Solution for Evaluating Long-Horizon Trajectories with Multiple Valid Solution Paths

The third major innovation is methodological rather than theoretical: the rubric-based sliding window evaluator solves a practical evaluation problem that has bedeviled the field—how to assess long (50-100 turn) agent trajectories that have no single "correct" sequence of actions and include requirements that don't modify environment state. This is an engineering contribution, but one with conceptual depth: it requires rethinking what it means for a trajectory to be "correct."

The problem that prior approaches cannot solve: The paper identifies two failure modes of existing evaluation methods (Section 3.3):

• State-based evaluation (used by τ-bench): Compare the final database state to an expected state. This captures only actions that leave persistent records—orders placed, reservations made, payments processed. It completely misses informational requirements: "Did the agent recommend a suitable restaurant?" "Did the agent set up reminders?" "Did the agent provide a coherent rationale for why one option is better than another?" In the Appendix C example, the taxi route recommendation from Dalian North Station to Harbor Family Feast Restaurant, and the text message template the agent composed for the aunt, are central task requirements that modify no database state whatsoever. State-based evaluation would treat them as irrelevant.

• Full-trajectory LLM-as-Judge (increasingly common in recent work): Feed the entire conversation to an LLM and ask "did the agent succeed?" This approach fails empirically—the paper's ablation (Table 4) shows that full-trajectory evaluation with rubrics achieves only 0.604 Cohen's κ compared to human judgments, versus 0.828 for the sliding window approach. The evaluator model's limited long-context capability causes it to miss or misremember rubric criteria scattered across 75 turns of conversation.

What makes the sliding window design non-obvious: The key insight is that evaluation context should be segmented and state should persist, not that context should be compressed or summarized. The naive approach to long-context evaluation would be summarization—feed the full trajectory to a model with a large context window, or summarize earlier parts into a compressed representation. The sliding window approach does neither. Instead, it:

1. Maintains a binary state vector $s \in \{0,1\}^k$ over rubric criteria that accumulates across windows. This is a form of lossy compression optimized for the evaluation task: the only information that needs to be preserved from earlier windows is "which rubrics have been satisfied so far," not the full conversational detail. The rubric state vector is the minimal sufficient statistic for the evaluation task.

2. Processes each window with access to the full detail of its 10 turns plus the 2-turn overlap from the previous window, ensuring that information spanning window boundaries is not lost.

3. Allows monotonic satisfaction with explicit reversal: once a rubric is marked satisfied, it stays satisfied—unless the agent actively overturns a previous correct conclusion in the current window. This rule encodes a sensible evaluation philosophy (success is cumulative, not fragile) while preventing gaming (an agent can't "check the box" for a constraint early and then violate it later).

Why this is generalizable beyond VitaBench: The sliding window evaluator is not tied to the specific domains, tools, or tasks of VitaBench. Any long-horizon agent trajectory that can be decomposed into atomic, verifiable rubric criteria can be evaluated using this approach. The design parameters—window size $w$, overlap $\delta$, rubric granularity—are tunable based on the specific evaluation context. The paper's validation that this approach achieves Cohen's κ ≥ 0.81 with human judgments establishes it as a reliable methodology that other benchmark designers can adopt.

The significance beyond the specific implementation: The sliding window evaluator represents a solution to a more general problem: how to decompose complex evaluation into atomic, tractable sub-judgments without losing cross-context dependencies. This is the evaluation analog of chain-of-thought reasoning for generation—by breaking a large, ambiguous judgment ("did the agent succeed?") into many small, specific judgments ("was the restaurant within 500m of the port?" "Was the delivery scheduled for around noon?" "Was the train first class?"), the evaluator achieves reliability that holistic evaluation cannot match.

Evidence from the ablation (Table 4): The ablation results are striking not just for what works but for what fails catastrophically. Removing the rubric structure (configurations 3 and 4) causes Cohen's κ to collapse to 0.018 and 0.067—essentially random agreement. The evaluator, without structured criteria, defaults to being wildly over-generous, marking 82-91% of trajectories as successful. This is not a minor calibration error—it demonstrates that LLM evaluators without structured rubrics are not merely noisy but systematically biased toward false positives, a finding with implications for the entire field's evaluation practices. The sliding window mechanism alone (without rubrics) is insufficient; the rubric structure alone (without sliding windows) produces only moderate agreement (κ = 0.604). Both are necessary, and their combination achieves the strong agreement (κ = 0.828) that justifies the benchmark's reliability.

---

Innovation 4: The Empirical Discovery That Cross-Scenario Navigation Is a Distinct, Severely Underdeveloped Capability—What the Performance Cliff Reveals

The most empirically striking finding in the paper is not the overall low scores (30% on cross-scenario tasks) but the shape of the performance degradation when moving from single-scenario to cross-scenario settings. This pattern reveals something about current LLM capabilities that was invisible in prior benchmarks because no prior benchmark tested cross-scenario navigation at scale.

The quantitative evidence: Table 3 shows that even the best model (o3, high) drops from 53.5% on single-scenario in-store tasks to 30.0% on cross-scenario tasks—a ~44% relative decline. This drop is consistent across all models and all single-scenario domains. The cross-scenario average across all models is 16.2% (Table 5), compared to 42.1% for in-store single-scenario (the easiest domain). This is not simply the result of harder tasks—it is the result of a qualitatively different capability demand that current models are not equipped to handle.

What makes cross-scenario navigation a distinct capability rather than just "harder tasks": In single-scenario tasks, the agent operates within a single tool dependency graph with a coherent semantic domain. The tools all relate to delivery, or all relate to travel booking, or all relate to in-store services. The agent can develop a mental model of what is possible within that domain and plan within it. In cross-scenario tasks, the agent must:

1. Recognize domain boundaries from the instruction: The user's compound request ("book a restaurant, order delivery, buy a train ticket") implicitly spans three domains, but the agent receives no explicit signal that domain-switching is required—it must parse the instruction and map sub-goals to tool domains.

2. Switch between disconnected dependency graphs: The delivery subgraph, the in-store subgraph, and the OTA subgraph are largely disconnected (only 512 edges across 66 tools, density 11.2%—lower than OTA's within-domain density of 22.0%). The agent cannot carry forward reasoning from one subgraph to the next; each domain-switch is a cold start into a new dependency structure.

3. Coordinate across domains: The sub-goals are not independent—the delivery must arrive at the restaurant, so spatial coordinates from the in-store domain must be passed to the delivery domain. The train must arrive before the restaurant booking, so temporal information from the OTA domain constrains the in-store domain. The agent must maintain cross-domain consistency of constraints while operating in tool environments that have no built-in awareness of each other.

4. Filter the expanded action space: With 66 tools available, the agent must determine that delivery_product_search_recommand is relevant to the delivery sub-goal but train_ticket_search is not—and then later, that train_ticket_search becomes relevant when the user shifts to the train-booking sub-goal. The coverage ratio $|V_{task}| / |V|$ is low in cross-scenario tasks, meaning most tools are distractors at any given moment.

Why prior benchmarks didn't reveal this: No prior benchmark (Table 1) has the combination of (a) cross-scenario composition and (b) large tool counts with dense interdependencies. DialogTool (Wang et al., 2025) has cross-scenario composition but only partially addresses inter-tool dependencies. ToolSandbox (Lu et al., 2025) has inter-tool dependencies but no cross-scenario composition. The τ-bench family operates within single domains. The result is that the field had no empirical evidence about how agents handle domain-switching—it was an entirely untested dimension of capability. VitaBench provides the first systematic measurement of this skill, and the measurement reveals a severe deficit.

What the performance cliff implies about model architecture: The finding that thinking models generally outperform non-thinking models on cross-scenario tasks (Table 3, cross-scenario column) but the absolute scores remain low—even o3 at "high" reasoning effort achieves only 30%—suggests that domain-switching is not merely a matter of "more reasoning." It may require:

• Better tool selection mechanisms: The expanded action space makes tool selection errors more likely (21.1% of errors in Figure 9). Models may need explicit tool-routing architectures that can map sub-goals to tool domains before selecting specific tools.

• Structured state representations: The agent must maintain separate mental models for what has been accomplished in each domain, what constraints cross domain boundaries, and what remains to be done. The flat conversation history that current models use as their only state representation may be insufficient for this multi-domain tracking.

• Meta-planning capabilities: The agent must decompose the compound instruction into domain-specific sub-plans, execute them in an order that respects cross-domain dependencies, and recognize when a sub-plan is complete and it's time to switch domains. This is a higher-level planning skill than what is required for single-domain tasks.

The negative result as an innovation: This finding is an innovation in the sense that it identifies a capability frontier that was previously invisible. The field has been optimizing models for narrow benchmarks, assuming that improvements would generalize. VitaBench shows that there is a specific, measurable capability—cross-scenario navigation—where even the most advanced models are profoundly deficient, and where improvements on simpler benchmarks have not translated. Identifying this gap is itself a contribution: it tells the field where to focus next.

The evidence is not just the numbers but the pattern: The consistency of the cross-scenario degradation across all model families and configurations (thinking and non-thinking) rules out model-specific explanations. No model bucks the trend—every model performs substantially worse on cross-scenario tasks. This universality is what elevates the finding from "models struggle with this benchmark" to "cross-scenario navigation is a fundamental, underdeveloped capability in current LLMs." The fact that Claude-4.1-Opus improves from 21.8% to 29.0% with thinking enabled, while o3 achieves 30.0%, suggests that reasoning mechanisms help but do not solve the underlying deficit—the performance ceiling is determined by something more fundamental than reasoning capacity alone.

---

Innovation 5: Passˆk as a Diagnostic for Deployment Reliability—Revealing That Even "Capable" Models Are Unacceptably Brittle

The paper's use of Passˆ4 (the probability that all 4 independent trials succeed) alongside traditional Pass@4 and Avg@4 metrics reveals a previously underappreciated dimension of agent capability: reliability. While Pass@k answers "can the model ever succeed?" and Avg@k answers "how often does it succeed on average?", Passˆk answers "can the model succeed consistently?"—and the answer, for current frontier models, is a resounding no.

The quantitative evidence: Table 3 shows that for cross-scenario tasks, the best model (o3, high) achieves Pass@4 = 61% (it succeeds at least once on 61% of tasks across 4 attempts) but Passˆ4 = 6% (it succeeds all 4 times on only 6% of tasks). For non-thinking models, Passˆ4 is often 0-2% even when Avg@4 reaches ~20%. This extreme gap—a factor of ~10 between Pass@4 and Passˆ4—is not a quirk of one model but a universal pattern. It tells a specific story: when an agent succeeds on a cross-scenario task, that success is mostly luck. The agent does not have a reliable policy for solving the task; it has a policy that occasionally stumbles into a successful trajectory.

Why this metric is a conceptual innovation, not just a reporting choice: The agent evaluation literature has historically focused on average success rates or Pass@k (the best-of-k perspective). These metrics implicitly assume a deployment model where the agent can be run multiple times and the best output selected—a reasonable assumption for offline generation tasks but deeply problematic for interactive deployment. In an interactive setting, the user experiences exactly one trajectory. There is no "best of 4" selection; the user either gets a successful interaction or a failure. Passˆ4 directly measures the probability that a randomly selected trajectory will succeed—it is the metric that corresponds to user experience in deployment.

The paper's Figure 4 (Pass@k vs. Passˆk as k increases to 32) makes this point visually: Pass@k climbs to ~73% for Claude-4-Sonnet at k=32, suggesting that with enough attempts, the model can eventually solve most tasks. But Passˆk plummets to near-zero by k=10, confirming that the model cannot reliably reproduce success. The two curves diverge so dramatically that they tell opposite stories: from the Pass@k perspective, the model is "73% capable"; from the Passˆk perspective, the model is "essentially never consistently capable." Both perspectives are true, but they answer different questions. The paper's contribution is recognizing that the Passˆk question is the one that matters for deployment and that the field has been systematically ignoring it.

What this reveals about the nature of agent failures: The high Pass@4 / low Passˆ4 pattern is consistent with a model whose success depends on fragile, path-dependent reasoning rather than robust strategy. If the model makes a lucky early tool call or happens to ask the right clarifying question in the right way at the right time, the trajectory converges toward success. If it makes a slightly different early decision, the trajectory diverges toward failure, and the model lacks the error recovery capability to correct course. The failure pattern analysis (Section 5.3) confirms this interpretation: "agents show limited error recovery when facing tool failures or unclear user responses, with most repeating failed attempts rather than adapting other strategies."

Connection to the "exploration vs. stability" framing: The paper explicitly frames the Pass@4 vs. Passˆ4 gap as evidence that "complex environments reward exploration, which suggests promising directions for RL approaches" (Section 4.2). This is a subtle but important claim: the gap indicates that success is possible (the model has the underlying capability) but not reliable (the model cannot consistently access that capability). This is precisely the situation where reinforcement learning—training the model to prefer trajectories that lead to success—could convert occasional capability into consistent policy. The paper's suggestion is not just "RL might help" but a specific diagnostic: the Pass@k/Passˆk gap quantifies the room for improvement that RL could potentially capture.

Why this matters beyond VitaBench: The reliability gap is not specific to these domains or tasks—it is a general property of current LLM agents that becomes visible only when evaluated at sufficient scale (multiple runs across many tasks) with the right metrics. Prior benchmarks that report only average success rates or single-run results literally cannot reveal this pattern. The paper's contribution is demonstrating that reliability is a distinct dimension of agent capability that must be measured separately from best-case performance, and that current models are severely deficient on this dimension even when their best-case performance appears promising. This reframes the agent development challenge: the goal is not just to make models that can succeed but to make models that reliably succeed—and Passˆk provides the metric for measuring progress toward that goal.

5. Experimental Analysis

Evaluation Methodology

• Dataset. VitaBench consists of 400 tasks across four settings: 100 cross-scenario tasks (the main results benchmark), 100 delivery tasks, 100 in-store consumption tasks, and 100 online travel agency (OTA) tasks (Table 2). Each task is derived from multiple real user requests on life-serving platforms, with environments containing annotated user profiles, spatiotemporal contexts, and comprehensive service databases comprising 1,324 service providers, 6,946 products, and 447 transactions across all tasks (Table 2). Individual tasks typically involve 5-20 service providers and can include over 100 products, with target options that satisfy all constraints deliberately intermixed among distractor options that violate specific requirements (Section 3.2).

• Base model(s). The paper evaluates a wide range of state-of-the-art proprietary and open models spanning multiple families: OpenAI GPT series (GPT-4.1, GPT-5), OpenAI o1 series (o3, o4-mini), Anthropic Claude series (Claude-4-Sonnet, Claude-4.1-Opus), Google Gemini series (Gemini-2.5-Flash, Gemini-2.5-Pro), DeepSeek series (DeepSeek-V3-0324, DeepSeek-R1-0528, DeepSeek-V3.1, DeepSeek-V3.2), Qwen3 series (Qwen3-32B, Qwen3-235B-A22B-2507, Qwen3-Max), plus Kimi-K2, Doubao-Seed-1.6, GLM-4.5, and LongCat-Flash (Section 4.1). Small models below 32B parameters are excluded due to benchmark difficulty. Models are divided into thinking and non-thinking categories, with hybrid models evaluated in both configurations where supported. The key finding—that even the best model achieves only 30.0% on cross-scenario tasks (Figure 1, Table 3)—motivates the breadth of model coverage to establish this as a universal challenge rather than a model-specific weakness.

• Metrics. Three complementary metrics are reported per task across 4 independent runs (Section 4.1): Avg@4 (the average success rate across the 4 runs, used as the primary metric for leaderboard ranking), Pass@4 (the probability that at least one out of 4 independent trials succeeds, capturing whether the model has any capability of solving the task), and Passˆ4 (the probability that all 4 independent trials succeed, capturing reliability—whether the model can consistently reproduce success). Final success is determined by the rubric-based sliding window evaluator's strict all-or-nothing judgment: score = 1[∑_j s_j = k] where s_j is the binary satisfaction state of rubric r_j and k is the total number of rubrics for that task (Section 3.3).

• Baselines. This is a benchmark paper rather than a method paper, so there is no proposed method to compare against baselines. Instead, the paper establishes a leaderboard (Figure 1, Table 3) where all models are compared against each other. The implicit baseline is the performance ceiling itself—the gap between current model performance (30.0% best cross-scenario Avg@4) and the theoretical maximum (100%) represents the capability frontier the benchmark is designed to measure. Within the error analysis (Section 5.3, Figure 9), failure modes are categorized into reasoning errors (61.8%), tool-use errors (21.1%), interaction management failures (7.9%), and user simulator errors (9.2%), providing a baseline distribution of failure types for future methods to improve upon.

• Generation budget / compute accounting. Tasks have no fixed turn limit—agents interact until they output ###STOP### or encounter a failure (Section 4.1). The implicit "budget" is therefore variable: agents can take as many turns as they need, creating a natural tradeoff between thoroughness and efficiency. Figure 5 plots model performance against average number of turns, revealing that thinking models achieve higher performance (23.8% average cross-scenario Avg@4) with fewer turns on average (61.1 turns) compared to non-thinking models (17.9% Avg@4, 69.9 turns). The user simulator (gpt-4.1-2025-04-14) and evaluator (claude-3.7-sonnet) use separate models from the agents being evaluated to avoid shared inductive biases inflating performance estimates (Section 4.1).

• Cross-validation / statistical protocol. The paper does not use cross-validation for model selection (since no model training occurs) but does conduct substantial statistical reliability analysis. The choice of 4 evaluation runs per task is justified by a resampling analysis based on 32 independent trials: for each k ∈ [1, 20], the Mean Squared Error (MSE) of k-run average estimates relative to the expected value (32-run average) was computed by sampling different k-combinations from the 32 trials (Section 5.1). Using k = 4 runs reduced MSE by 77.5% compared to k = 1, while increasing to k = 8 provided only marginal additional reduction despite doubling computational overhead (Figure 7). All models are run with temperature 0.0 to promote deterministic outputs, though the paper acknowledges that "cumulative perturbations in multi-turn interactions amplify into divergent trajectories" even at temperature 0.0 (Section 5.1).

Main Quantitative Results

Overall Performance Reveals a Severe Capability Deficit (Table 3, Figure 1)

The headline finding is that all current models perform poorly on VitaBench, with the best model (o3, high) achieving only 30.0% Avg@4 on cross-scenario tasks and 53.5% on the easiest single-scenario domain (in-store). Table 3 presents the comprehensive leaderboard:

• Cross-scenario tasks (main results): The top five models are o3 (high) at 30.0% Avg@4, Claude-4.1-Opus with thinking at 29.0%, LongCat-Flash-Thinking at 24.3%, Gemini-2.5-Pro at 23.5%, and Claude-4-Sonnet with thinking at 23.0%. At the bottom, GPT-5 (minimal) and Qwen3-32B without thinking achieve only 4.0%, and DeepSeek-V3-0324 achieves 3.8%. The performance spread of ~26 percentage points between best and worst indicates that model choice matters substantially, but the absolute ceiling of 30% indicates that even frontier models are fundamentally inadequate for reliable deployment.

• Single-scenario tasks: Performance varies dramatically by domain. In-store consumption is the easiest domain, with top models achieving 50-57% (LongCat-Flash-Thinking at 56.8%, GPT-5 high at 52.5%, Claude-4.1-Opus with thinking at 52.5%). Delivery is intermediate, with GPT-5 high at 54.0% and o3 high at 53.5%. OTA is the hardest single domain, with GPT-5 high at 37.5% and o3 high at 37.8%. The domain ordering (in-store > delivery > OTA) is consistent across models, confirming that domain characteristics rather than model-specific weaknesses drive the difficulty gradient.

• Thinking vs. non-thinking: Thinking models generally but not universally outperform their non-thinking counterparts. Claude-4.1-Opus improves from 21.8% to 29.0% with thinking on cross-scenario, GLM-4.5 from 20.0% to 22.8%, and GPT-5 from 4.0% (minimal) to 22.8% (high). However, some thinking models underperform expectations—Gemini-2.5-Flash with thinking achieves only 5.3%, worse than its non-thinking configuration at 5.8%, and Qwen3-32B with thinking barely improves to 5.0% from 4.0%. This suggests that thinking mechanisms help only when the base model has sufficient underlying capability to benefit from additional reasoning.

Pass@4 and Passˆ4 Reveal Profound Reliability Problems (Table 3, Figure 4)

The three-metric reporting exposes a critical pattern: models can sometimes succeed but almost never succeed consistently. For cross-scenario tasks:

• o3 (high) achieves Pass@4 = 61.0% but Passˆ4 = 6.0%—the model succeeds at least once on 61% of tasks across 4 attempts, but succeeds all 4 times on only 6% of tasks.
• Claude-4.1-Opus with thinking achieves Pass@4 = 56.0% but Passˆ4 = 6.0%.
• At the lower end, DeepSeek-V3-0324 achieves Pass@4 = 12.0% but Passˆ4 = 0.0%—the model occasionally succeeds but never reliably.

For single-scenario tasks, the gap is narrower but still substantial. On in-store tasks, GPT-5 (high) achieves Pass@4 = 86.0% but Passˆ4 = 21.0%. On OTA tasks, o3 (high) achieves Pass@4 = 66.0% but Passˆ4 = 10.0%.

Figure 4 extends this analysis to k = 32 for Claude-4-Sonnet and GPT-4.1, showing that Pass@k continues to climb (reaching approximately 73% for Claude-4-Sonnet at k=32), confirming that exploration helps—more attempts increase the chance of stumbling onto a successful trajectory. However, Passˆk drops rapidly to near-zero by k=10 for both models, confirming that fundamental stability challenges persist even for models that "can" solve tasks. The divergence between the two curves illustrates that increased sampling reveals underlying inconsistency rather than resolving it.

Thinking Mechanisms Improve Both Effectiveness and Efficiency (Figure 5)

Figure 5 plots performance (Avg@4) against average number of turns per task, color-coding thinking (blue) and non-thinking (red) models. Two patterns emerge:

• Thinking models cluster in the upper-left region (higher performance, fewer turns), with o3 (high) and GPT-5 (high) achieving the best performance-turn tradeoff. The overall trend shows that higher-performing models require fewer interaction turns on average.
• Non-thinking models cluster in the lower-right region (lower performance, more turns), with models like DeepSeek-V3.1 and Qwen3-235B-Instruct taking 70-85 turns while achieving only 14-16% cross-scenario Avg@4.

The paper attributes this efficiency gain to two factors: "better decomposition of complex multi-step plans and more targeted user interactions through precise clarifying questions" (Section 4.2). Thinking models waste fewer turns on redundant tool calls or unfocused user queries, compressing their trajectories while improving outcomes.

Ablation Studies and Robustness Checks

User simulator information fidelity: Two human annotators assessed 100 conversations for adherence to task instructions and user profiles, absence of hallucinations, and contextual relevance. The simulator achieved an average score of 9.48/10 across all scenarios (Figure 6a). Minor deviations manifested as natural conversational variations (e.g., "cannot eat spicy" vs. "prefer non-spicy food") that "enhance dialogue authenticity without compromising task requirements." The simulator appropriately responds "I don't know" when queried about unprovided information, maintaining strict source fidelity (Section 5.1).

User simulator persona consistency: Five distinct personality types (impatient, anxious, scattered, dependent, cooperative) were tested across 100 conversations, measuring behavioral alignment through language style, decision patterns, and emotional expressions. The average score was 9.34/10 (Figure 6b). Cooperative personas exhibited the highest consistency (9.8/10), which the paper attributes to LLMs' inherent collaborative tendencies. Scattered personas showed lower controllability (8.9/10), suggesting that inconsistent, topic-jumping behavior is harder for the simulator to maintain convincingly. This has implications for benchmark difficulty: the hardest-to-simulate personas may also be the hardest for agents to handle, creating a potential confound where simulator fidelity limits vary with the interaction complexity dimension.

Evaluator component ablation (Table 4): Four configurations were compared against human-annotated ground truth on GLM-4.5's cross-scenario trajectories:

• Baseline (sliding window + rubric): Accuracy 20.0%, task accuracy 95.0%, rubric accuracy 88.5%, Cohen's κ = 0.828.
• Full trajectory + rubric (no sliding window): Accuracy 19.0%, task accuracy 90.0%, rubric accuracy 87.6%, Cohen's κ = 0.604.
• Sliding window without rubric: Accuracy 91.0%, task accuracy 22.0%, Cohen's κ = 0.018.
• Full trajectory without rubric: Accuracy 82.0%, task accuracy 32.0%, Cohen's κ = 0.067.

The critical finding is that both the sliding window and the rubric structure are individually necessary and their combination is sufficient for reliable evaluation. Removing the rubric structure (configurations 3 and 4) causes Cohen's κ to collapse to near-zero—the evaluator, lacking structured criteria, defaults to being wildly over-generous, marking 82-91% of trajectories as successful when humans identified failures. The full-trajectory-with-rubric configuration (configuration 2) achieves similar final scores to the baseline (19% vs. 20%) but with substantially lower agreement (κ = 0.604 vs. 0.828), which the paper attributes to "the evaluation model's limited long-context capability hindering accurate assessment of all rubrics in the full trajectory." The baseline's κ = 0.828 indicates strong agreement with human judgments, validating the evaluation methodology.

Statistical reliability of run count (Figure 7): Resampling analysis based on 32 independent trials for representative models shows that the MSE of k-run average estimates drops sharply from k=1 to k=4 (77.5% reduction) and then flattens. The paper chooses k=4 as the optimal balance between statistical precision and computational cost. This analysis is important because it quantifies a subtle source of variance: even at temperature 0.0, the multi-turn nature of interactions amplifies small perturbations into divergent trajectories, meaning that single-run evaluations would produce unreliable estimates.

Interaction complexity ablation (Figure 8): Two models (Claude-4-Sonnet and GPT-4.1-Mini) were evaluated under three conditions: (1) default user simulator with full persona and behavioral attributes, (2) user simulator without these attributes (neutral user), and (3) solo agent setting where complete instructions are provided upfront without user interaction. The performance gap between default and neutral users is relatively small for Claude-4-Sonnet compared to GPT-4.1-Mini, suggesting that conversational styles primarily challenge weaker models. Conversely, Claude-4-Sonnet gains more in solo agent mode, indicating that it excels at processing complex instructions when all information is available upfront but struggles with progressive information revelation. This validates interaction complexity as a fundamental dimension of task difficulty with model-dependent impact.

Reasoning and tool complexity analysis (Table 5): The paper computes domain-level complexity characteristics and correlates them with model performance:

• In-store: 5.6 reasoning points, 3,916 search space, 24 tools, 68 edges, 12.3% density → 42.1% performance (highest).
• Delivery: 7.4 reasoning points, 1,246 search space, 20 tools, 50 edges, 13.2% density → 38.0% performance.
• OTA: 9.7 reasoning points, 11,284 search space, 38 tools, 309 edges, 22.0% density → 20.7% performance.
• Cross-scenario: 10.3 reasoning points, 8,717 search space, 66 tools, 512 edges, 11.2% density → 16.2% performance.

The counterintuitive finding is that search space size does not dominate difficulty—in-store has the largest search space (3,916) but the highest performance, while OTA has a large search space (11,284) combined with high tool graph density (22.0%) and the most reasoning points (9.7), producing the lowest single-domain performance. Tool graph density and reasoning point count appear to be stronger predictors of difficulty than raw database scale. Cross-scenario tasks add domain-switching overhead on top of OTA-level reasoning demands, producing the worst performance despite lower graph density (11.2%) than OTA alone—the low density reflects that cross-domain edges are rare, making each domain switch a cold start into a disconnected subgraph.

Critical Assessment

Claim: "Even the most advanced models achieve only 30% success rate on cross-scenario tasks." This claim is solidly supported. Table 3 and Figure 1 show o3 (high) at 30.0% Avg@4 on cross-scenario. However, a nuance: Avg@4 is an average of 4 runs, so the expected success rate on any single deployment is lower than 30% for most models. The distinction between Avg@4 (the primary reported metric) and Pass@4 (the probability of at least one success in 4 tries) matters practically: an organization considering deployment would care more about single-run reliability, which for even the best model corresponds to the fact that Passˆ4 is only 6%—meaning consistent, repeatable success is essentially non-existent.

Claim: "Performance varies significantly across domains and correlates strongly with environmental complexity." Supported with an important qualification. Table 5 demonstrates clear domain ordering (in-store > delivery > OTA > cross-scenario) and shows correlations with complexity metrics. However, the "search space" metric shows the opposite pattern from what one might expect—in-store has the largest search space but highest performance. The paper's explanation (in-store requires simpler coordination despite more candidates) is plausible but post-hoc. A stronger demonstration would involve systematically varying search space size while holding other complexity dimensions constant to establish causal relationships rather than observational correlations. The current analysis shows correlation but cannot distinguish between complexity dimensions that are confounded in the benchmark design.

Claim: "Thinking mechanisms improve both effectiveness and efficiency." Supported with qualifications. Figure 5 shows the overall trend (thinking models cluster in upper-left), and Table 3 shows specific improvements (Claude-4.1-Opus: 21.8% → 29.0%, GPT-5: 4.0% → 22.8%). However, the counterexamples are notable: Gemini-2.5-Flash with thinking performs worse (5.3%) than without (5.8%), and Qwen3-32B barely improves (4.0% → 5.0%). The paper does not investigate why thinking sometimes fails to help. Possible explanations—insufficient base model capability to benefit from extended reasoning, thinking mechanisms that interfere with function-calling formats, or thinking that consumes context budget without producing useful plans—are unexplored. The claim that thinking "improves efficiency" (fewer turns) could be partially tautological if thinking models tend to terminate earlier because they give up sooner rather than because they solve tasks more efficiently. The data cannot distinguish between efficient success and efficient failure without per-task success-conditioned turn counts.

Claim: "Exploration improves performance but reveals stability issues." Supported by Figure 4 and the Pass@4 vs. Passˆ4 gap in Table 3. The finding that Pass@k increases with k while Passˆk drops to near-zero is robust and important. However, the paper's suggestion that this "suggests promising directions for RL approaches" (Section 4.2) is speculation rather than demonstrated—no RL experiment is run. The stability issue could equally indicate that models lack the architectural capacity to represent reliable policies for these tasks, meaning RL would fail to improve reliability regardless of training. The paper provides a diagnostic (the reliability gap) but not a solution.

Genuine weaknesses in the experimental design:

• Single simulator model (gpt-4.1-2025-04-14) and single evaluator model (claude-3.7-sonnet): The paper argues this avoids overlap with evaluated agent models, but it introduces a different concern: benchmark difficulty may be partially determined by the specific interaction patterns and evaluation standards of these particular models. A different simulator or evaluator model might produce systematically different difficulty estimates. No sensitivity analysis across simulator/evaluator model choices is performed.

• No within-task difficulty variation analysis: The paper reports aggregate performance per domain and per difficulty bin but does not analyze which specific task characteristics (number of sub-goals, number of constraints, user persona type, temporal complexity) most strongly predict failure. The complexity framework provides theoretical proxies (reasoning points, search space, tool graph density) but these are domain-level aggregates. Task-level analysis would be more informative for understanding what specifically makes individual tasks hard.

• Language confound: The paper notes that "the majority of data is originally in Chinese" (Section 3.2 footnote) and that an English version is being prepared. The current results presumably reflect performance on Chinese-language tasks, but this is not explicitly stated for all models. If some models are stronger in Chinese than English (or vice versa), the leaderboard rankings may partially reflect language capability rather than agentic capability per se. The paper does not report or control for base model performance differences between languages.

• No cost analysis: The benchmark's practical utility depends on how expensive it is to run. With 400 tasks × 4 runs = 1,600 evaluations per model, and each evaluation potentially involving 50-100 turns of LLM calls (agent + simulator + evaluator), the total API cost per model could be substantial. The paper does not report or estimate this cost, making it difficult for researchers with limited budgets to assess feasibility.

• Missing baselines: The paper evaluates models as zero-shot function-calling agents but does not compare against: (1) agents augmented with explicit planning modules, (2) agents with retrieval-augmented generation for tool selection, (3) fine-tuned variants of the same base models on agent task data, or (4) multi-agent architectures where separate models handle different domains. These comparisons would help distinguish between "the task is inherently hard" and "the zero-shot function-calling paradigm is insufficient." The paper's framing as a benchmark rather than a methods paper justifies some of these omissions, but including even one structured agent baseline (e.g., ReAct-style reasoning with explicit plan-then-execute decomposition) would contextualize the raw model scores.

• Temperature 0.0 may suppress beneficial exploration: Setting temperature to 0.0 promotes reproducible outputs but may underestimate model capability if the deterministic output corresponds to a suboptimal reasoning path. The paper's own finding that Pass@4 substantially exceeds Avg@4 indicates that stochastic variation discovers successful strategies that deterministic decoding misses. A fairer evaluation of model capability might include both temperature-0.0 and temperature-0.7 configurations, since real deployments can use non-zero temperature with multiple samples.

• No human performance baseline: The paper does not establish human performance on VitaBench tasks. Without knowing whether humans find these tasks easy or difficult, it is impossible to distinguish between "the benchmark is unrealistically hard" and "the benchmark captures genuine difficulty that AI should be able to handle." If human experts also struggle with cross-scenario coordination, the 30% ceiling might reflect inherent task ambiguity rather than AI deficiency.

Missing experiments that would strengthen the paper:

• Fine-grained failure correlation with complexity metrics at the task level: The domain-level analysis (Table 5) shows correlations, but task-level regression (predicting per-task success rates from reasoning point count, search space size, tool graph density, and user persona type) would provide much stronger evidence that the complexity framework captures genuine difficulty drivers.
• Cross-model failure agreement analysis: Do different models fail on the same tasks, suggesting task-intrinsic difficulty, or do they fail on different tasks, suggesting model-specific weaknesses? This would inform whether the benchmark primarily measures task difficulty or model capability.
• Ablation of progressive information revelation: The solo agent condition in Figure 8 shows substantial improvement when all information is provided upfront, but this is only tested on two models. Extending this to the full model set would quantify how much of the benchmark's difficulty comes from interaction complexity specifically.
• Scaling analysis within model families: The paper's claim about the gap between simpler benchmarks and VitaBench would be strengthened by showing how models that saturate simpler benchmarks (e.g., achieving 90%+ on BFCL or τ-bench) still perform poorly on VitaBench. Without this, the argument that VitaBench measures something distinct is asserted rather than demonstrated through cross-benchmark correlation analysis.

6. Limitations and Trade-offs

The Difficulty Estimation Gap: Complexity Metrics Are Post-Hoc Correlates, Not Deployable Predictors

The assumption or constraint: The paper's three-dimensional complexity framework (C_reason, C_tool, C_interact) is presented as a formal theory that explains task difficulty—and Section 5.2 demonstrates that complexity metrics (reasoning point count, search space size, tool graph density) correlate with observed model performance across domains. However, these metrics are computed after task construction, not before. The framework cannot predict how hard a new, unseen task will be without first running models on it and measuring their failure patterns. A benchmark designer constructing a new task cannot use the framework to forecast whether that task will discriminate between models or be trivially easy—the framework is descriptive (explaining observed difficulty) rather than predictive (forecasting future difficulty).

The paper acknowledges this implicitly in how it reports the complexity analysis—as a validation that the constructed tasks embody the intended complexity dimensions, not as a generative tool for task design. Section 5.2 states that "reasoning point count, search space size, tool graph density, and user interaction configuration all correlate with model performance in the expected directions," but the correlation is domain-level (four data points: delivery, in-store, OTA, cross-scenario) rather than task-level. There is no regression model, difficulty prediction function, or even proposed formula for combining the three dimensions into a scalar difficulty score.

The consequence: Without a predictive difficulty model, VitaBench tasks can only be validated retrospectively—build the task, run models on it, check whether performance matches expectations. This makes iterative benchmark construction expensive (requiring full model evaluations to verify difficulty) and prevents systematic difficulty calibration. A researcher wanting to create a benchmark with a specific difficulty profile (e.g., "tasks that non-thinking models solve 30% of the time but thinking models solve 60% of the time") has no guidance from the framework on how to achieve that target. The three-dimensional complexity vector provides vocabulary for describing what went into a task but no equation for predicting what will come out.

Furthermore, the domain-level granularity masks within-domain variance. The paper reports that in-store tasks average 5.6 reasoning points (Table 5), but individual in-store tasks likely range from 2-3 reasoning points (trivial lookup tasks) to 8-10 (complex multi-constraint coordination). The framework provides no method for distinguishing these without running models. A benchmark user who wants to understand which specific tasks a model fails cannot use complexity metrics to identify failure-prone tasks a priori—they must run the model, observe failures, then retroactively note that failed tasks happened to have more reasoning points.

What evidence exists in the paper: Table 5 provides the only complexity-performance correlation evidence. With n=4 data points (four domains), no statistical test of the correlation is possible or reported. The observed ordering (in-store > delivery > OTA > cross-scenario for performance, with corresponding increases in reasoning points and graph density) is suggestive but not conclusive—with so few data points, the observed pattern could arise from other confounded factors (task instruction clarity, user persona difficulty distribution, domain-specific model knowledge). The paper does not conduct task-level regression analysis that would demonstrate within-domain predictive power of the complexity metrics.

Mitigation status: The paper does not address this limitation. Section 3.1 presents the complexity framework as a tool for "systematic guidance for benchmark design and evaluation," but the guidance operates at the level of design philosophy (make tasks with many reasoning points, dense tool graphs, and dynamic user interactions) rather than engineering specification (compute these metrics to predict difficulty level). The framework successfully guides what kinds of complexity to include, but fails to specify how much of each dimension produces a target difficulty level. This is a fundamental tension in the paper's dual goals: the complexity framework is a theoretical contribution meant to shape thinking about benchmark design, but it cannot serve as the operational difficulty calibration tool that practitioners would need to build benchmarks at scale.

---

The User Simulator Is a Single Model with Fixed Behavioral Parameters—Interaction Complexity Is Not Truly Sampled from a Distribution

The assumption or constraint: All 400 tasks in VitaBench use the same user simulator model (gpt-4.1-2025-04-14) with the same system prompt template (Appendix B). While the <persona> descriptions vary across tasks—creating different personality types (impatient, anxious, scattered, dependent, cooperative) and communication styles—the underlying generative model producing user behavior is identical. This means that the "distribution" of user interaction complexity is not sampled from a diverse population of independent user simulators with genuinely different behavioral tendencies, but rather from a single language model prompted to role-play different personas.

The paper's own validation data (Section 5.1) reveals an asymmetry that underscores this concern: cooperative personas exhibit the highest consistency (9.8/10 in Figure 6b), while scattered personas show lower controllability (8.9/10). The paper attributes this to "LLMs' inherent collaborative tendencies"—but this is precisely the problem. The simulator cannot perfectly suppress its default helpful, cooperative behavior when prompted to be difficult. The scattered persona's lower consistency means that the hardest-to-simulate personas are also the ones where simulator fidelity is weakest, and consequently where the measured interaction complexity may deviate most from the intended complexity.

The consequence: An agent's interaction performance on VitaBench may partly reflect the specific conversational patterns of gpt-4.1-2025-04-14 rather than generalizable interaction capability. A different simulator model—say, one with less inherent cooperativeness or different default conversational patterns—might produce systematically different difficulty estimates. The "impatient" persona as simulated by GPT-4.1 may express impatience in a particular way (certain linguistic patterns, certain turn-taking behaviors) that some agent models happen to handle well and others poorly, not because those models have genuinely better interaction capabilities, but because their training distributions overlap differently with GPT-4.1's output distribution.

This concern is amplified by the shared lineage between simulator and agent models. Several evaluated agent models are from the GPT family (GPT-4.1, GPT-5), sharing architecture and training methodology with the simulator. While the paper deliberately uses separate model families for evaluation (Claude) and simulation (GPT) to avoid overlap, the leaderboard includes GPT-based agents that are evaluated against a GPT-based simulator. Any shared inductive biases—conversational patterns, handling of ambiguity, response to impatience signals—would inflate these models' scores relative to models from different families.

More subtly, the performance gap between default and neutral users in Figure 8 (the interaction complexity ablation) is measured against the same underlying simulator model with and without persona attributes. This measures the marginal effect of persona prompts on a single base model, not the effect of genuinely different interaction partners. A truly neutral user simulated by a different model might produce different baseline performance, changing the estimated interaction complexity contribution.

What evidence exists in the paper: Figure 6 provides the only reliability analysis of the user simulator, and it reveals both strengths (high fidelity and consistency overall) and the specific weakness (degraded consistency for scattered personas). Figure 8 shows that removing persona attributes produces different performance than including them, validating that the persona prompts matter—but it does not test whether different simulator models with the same persona prompts would produce different performance gradients. Section 4.1 explicitly notes the simulator model version pinning (gpt-4.1-2025-04-14), indicating awareness of reproducibility concerns, but does not conduct sensitivity analysis across simulator versions or families.

Mitigation status: The paper partially mitigates this by validating simulator reliability (Figure 6) and by using a simulator model (GPT-4.1) that is separate from the evaluator model (Claude-3.7-Sonnet). The 9.48/10 information fidelity score and 9.34/10 persona consistency score demonstrate that the single simulator is reliable—it consistently produces the intended behavior—but do not demonstrate that it is representative—that its behavior covers the space of possible human interaction patterns. The paper does not suggest or conduct experiments with alternative simulator models, leaving the generalizability of interaction complexity findings contingent on the specific simulator choice. The 9.2% of errors attributed to user simulator stochasticity in Figure 9 is acknowledged as "inherent stochastic behavior that we mitigate through multiple runs," but mitigation via repeated sampling does not address systematic biases from simulator model choice.

---

All Tasks Grounded in Chinese Life-Serving Platforms—A Single Language, Culture, and Service Domain Family

The assumption or constraint: VitaBench's tasks are "grounded in real-world life-serving platforms where the majority of data is originally in Chinese" (Section 3.2, footnote 2). The three domains—food and product delivery, in-store consumption, and online travel services—represent a specific class of consumer-facing service interactions common in Chinese super-app ecosystems (Meituan, the authors' affiliation, operates one such platform). The user profiles, service provider databases, product catalogs, and transaction histories all derive from these Chinese platforms, with English versions "being prepared" but not yet evaluated.

This means VitaBench tests agent capability in one specific cultural and linguistic context where interaction norms, user expectations, service workflows, and domain knowledge reflect Chinese consumer behavior. The implicit communication patterns (how users express preferences, what constitutes politeness, when users expect proactivity from service agents), the domain assumptions (delivery logistics, payment flows, reservation norms), and the linguistic patterns all embed cultural defaults that may not generalize.

The consequence: A model that performs well on VitaBench may owe its success partly to Chinese cultural and linguistic competence rather than general agentic capability. Conversely, a model that performs poorly may fail due to unfamiliarity with Chinese service norms rather than fundamental reasoning or tool-use deficiencies. The paper's finding that the in-store domain has the highest performance (42.1% average) despite the largest search space (3,916 options, Table 5) could reflect that in-store consumption patterns (restaurant booking, meal preferences) are the most culturally universal of the three domains, or that the specific Chinese restaurant data happened to be easier—the cause is not distinguishable without cross-cultural comparison.

The leaderboard rankings (Figure 1, Table 3) may partially reflect model-specific Chinese language capabilities. Models developed primarily by Chinese organizations (Qwen3, DeepSeek, GLM, Doubao, Kimi-K2, LongCat-Flash) may have systematic advantages in processing Chinese-language service interactions compared to primarily English-developed models (Claude, Gemini, GPT). The observed performance hierarchy—with o3 (OpenAI) at the top but substantial representation from Chinese-developed models throughout the upper tier—could reflect a mix of agentic capability and language-specific competence that the benchmark cannot disentangle.

Furthermore, the specific service patterns encoded in the tool dependency graphs reflect Chinese platform architectures. The delivery_product_search_recommand [sic] tool naming, the specific workflow of create_delivery_order → pay_delivery_order, and the OTA tool chain for train ticket booking all mirror how Chinese super-apps structure these interactions. An agent that has internalized non-Chinese service patterns (e.g., Western e-commerce where delivery and in-store are entirely separate platforms with different authentication flows) may face an additional adaptation burden that is not an agentic reasoning deficit but a domain-transfer challenge.

What evidence exists in the paper: Section 3.2 explicitly states the Chinese-language data provenance and mentions that an English version is being prepared. However, no analysis compares Chinese vs. English task performance for any model, no attempt is made to control for base language competence when ranking models, and no discussion acknowledges that the leaderboard may conflate language and agentic capabilities. The paper evaluates both Chinese-developed and Western-developed models side by side without language normalization.

Mitigation status: The paper acknowledges the limitation through the footnote disclosure but treats it as a temporary artifact ("we are also preparing an English version") rather than a fundamental design constraint. The English version's preparation suggests awareness of the generalizability concern, but until that version is released and evaluated, the current leaderboard reflects performance on Chinese-language tasks with Chinese-cultural service patterns. The mitigation is planned but not implemented, leaving the current results language- and culture-bound. A stronger approach would have been to release both Chinese and English versions simultaneously with cross-language performance comparisons, enabling measurement of the language competence confound.

---

Strict All-or-Nothing Scoring Ignores Partial Progress and Masks Gradations of Capability

The assumption or constraint: The rubric-based evaluator produces a binary success/failure judgment: score = 1[∑_j s_j = k], requiring that all k rubric criteria be satisfied for a task to count as successful (Section 3.3). A trajectory that satisfies 9 of 10 rubrics scores 0.0—identical to a trajectory that satisfies 0 of 10 rubrics. The paper acknowledges that "the fine-grained rubrics enable detailed scoring analysis for identifying trajectory differences" and that the per-rubric data provides "valuable dense signals for reinforcement learning," but these per-rubric scores are not aggregated into the benchmark's headline metrics. The leaderboard (Table 3, Figure 1) reports only the binary strict success rate via Avg@4, Pass@4, and Passˆ4.

This choice encodes a deployment-oriented philosophy: "a task that is 90% complete is still a failure if the missing 10% is 'purchased the correct train ticket' rather than 'sent a follow-up reminder.'" The paper explicitly defends this in the prior sections as reflecting real-world consequences where partial completion is often indistinguishable from total failure. But this philosophy discards information that is critical for understanding how close models are to succeeding and where the capability frontier lies.

The consequence: The strict scoring produces a compressed, low-resolution performance landscape. The best model scores 30.0% on cross-scenario tasks and the worst scores 3.8%—a range of only 26.2 percentage points across 25+ models spanning multiple orders of magnitude in parameter count, training compute, and architectural sophistication. This compression makes it difficult to distinguish between models that are genuinely similarly capable and models that fail in different ways that the binary metric equates.

Consider two hypothetical models: Model A satisfies 9 of 10 rubrics on 80% of tasks but never achieves all 10 (scoring 0% strict success). Model B satisfies 5 of 10 rubrics on 40% of tasks and all 10 on 20% of tasks (scoring 20% strict success). The binary metric ranks Model B above Model A, but Model A is arguably closer to deployment readiness—it consistently handles almost everything, failing only on a specific sub-class of requirements. The strict metric cannot capture this distinction, and the paper's current reporting does not surface per-rubric or partial-credit statistics that would reveal it.

The 9.2% of errors attributed to user simulator stochasticity (Figure 9) highlights a related issue: a model can fail a task because of a single simulator noise event (e.g., the simulator hallucinating a constraint or misinterpreting a question) at any point in the trajectory. Since all rubrics must be satisfied, a single simulator error anywhere in a 75-turn interaction dooms the entire trajectory—even if the agent's behavior was otherwise flawless. The Pass@4 metric partially addresses this by allowing success in any of 4 attempts, but a single fluke error in each of 4 attempts still produces a 0% Avg@4 for a model that is, in expectation, nearly perfect. The strict scoring amplifies the impact of simulator noise in a way that partial-credit aggregation would not.

What evidence exists in the paper: The paper reports the 9.2% user simulator error rate (Figure 9) but does not analyze how these errors interact with strict scoring. The ablation of evaluator components (Table 4) validates that the rubric-based approach is reliable in its binary judgments (κ = 0.828), but does not explore whether a continuous or partial-credit scoring scheme would maintain similar reliability while providing richer information. The Per-rubric accuracy of 88.5% in the baseline evaluator configuration indicates that individual rubric judgments are reliable, supporting the feasibility of partial-credit reporting—the data exists and is reliable, but is not used in headline metrics.

Mitigation status: The paper explicitly acknowledges that per-rubric scores can provide "detailed scoring analysis" and "dense signals for reinforcement learning," suggesting that the binary scoring is a benchmark reporting choice rather than an inherent limitation of the evaluation methodology. The data for partial-credit analysis exists in the per-rubric state vectors—it simply is not reported in the leaderboard or main results tables. The paper does not explain why per-rubric statistics are omitted from the main results, nor does it provide per-rubric or partial-credit analyses even in appendices. The mitigation is technically feasible (the data is collected) but not implemented in the paper's reporting, leaving the headline numbers as a compressed and potentially misleading representation of model capability.

---

The Benchmark Provides No Human Performance Baseline—The 30% Ceiling Cannot Be Calibrated Against Achievable Performance

The assumption or constraint: VitaBench reports model performance in absolute terms (e.g., "o3 achieves 30.0% on cross-scenario tasks") but provides no human performance data for calibration. The paper constructs tasks from "authentic user requests" and claims they represent "real-world applications" (Section 1), implying that competent human performance would be high—but this is an assumption, not a measurement. Human performance on these same tasks, under the same interface constraints (function-calling through tool schemas, interaction through text chat, same information boundaries), is unknown.

This matters because the paper's central rhetorical claim—that the 30% ceiling represents a "severe capability deficit" requiring fundamental advances—depends on the premise that these tasks are solvable by humans at rates substantially above 30%. If human experts also struggle with VitaBench's cross-scenario coordination under the same constraints, the 30% ceiling reflects inherent task difficulty (ambiguity, underspecification, irreducible complexity) rather than AI deficiency. The benchmark would still be useful for comparing models, but the interpretation of absolute scores would shift from "models are far from capable" to "these tasks are genuinely hard for any agent, human or artificial."

The consequence: Without a human baseline, the paper cannot distinguish between three interpretations of the low absolute scores:

1. AI deficiency: The tasks are human-solvable at high rates, but current LLMs lack fundamental reasoning, tool-use, or interaction capabilities needed to solve them.
2. Task inherent difficulty: The tasks are genuinely difficult for any agent operating under the same interface constraints, and human performance would also be modest (e.g., 50-60% rather than 90%+).
3. Interface-imposed difficulty: The function-calling paradigm, tool schema format, text-chat interaction, and information boundaries create artificial difficulty that does not reflect real human performance (where humans would use richer interfaces, prior knowledge, or different communication patterns).

The correct interpretation has direct implications for research prioritization. If the bottleneck is interpretation (1), the field should invest in better reasoning, planning, and interaction architectures. If the bottleneck is interpretation (2), the benchmark is appropriately calibrated and the 30% ceiling is a reasonable target for gradual improvement. If the bottleneck is interpretation (3), the benchmark may be measuring interface compatibility rather than agentic capability, and the low scores may not predict real-world deployment performance where agents would have different interface affordances.

The paper's claim that VitaBench captures "the inherent complexity of real-world applications" is an assertion about ecological validity that human baseline data would either support or challenge. If humans achieve 90%+ on these tasks, the claim is validated—the tasks are clearly solvable, and models genuinely fall short. If humans achieve 40-50%, the claim is weakened—the benchmark may be imposing artificial difficulty beyond what real-world deployment entails.

What evidence exists in the paper: None. The paper does not report, conduct, or even propose human evaluation of VitaBench tasks. The task construction pipeline includes "human verification" to "eliminate ambiguities while preserving multiple valid solution pathways" (Section 3.2), but this verification checks task correctness (are the rubrics well-formed? are there unintended contradictions?) rather than task solvability under the evaluation interface. The human annotators who validated the evaluator (Table 4) assessed trajectory quality, not task difficulty. No human was asked to actually solve VitaBench tasks as an agent would—receiving the same tool schemas, interacting with the same simulator, and being evaluated by the same rubrics.

Mitigation status: Not addressed. The paper does not acknowledge the absence of human baselines as a limitation, nor does it discuss what human performance would imply for benchmark interpretation. The omission is significant because human baselines are standard practice for challenging benchmarks in related domains—MATH (Hendrycks et al., 2021), the benchmark from which this paper draws its task complexity inspiration, reports human performance. The paper's claim that VitaBench tests "whether LLM-based agents can handle the inherent complexity of real-world applications" implicitly assumes the answer should be "yes, eventually," but without knowing whether humans can handle that same complexity under the same constraints, the "should" is ungrounded.

---

Cross-Scenario Tasks Are Evaluated Without Cross-Scenario Baselines—No Evidence That Domain-Switching Itself Is the Bottleneck

The assumption or constraint: The paper's central empirical claim is that cross-scenario tasks expose a "severe capability deficit" distinct from single-scenario difficulty—that "fundamental deficiencies in navigating expanded action spaces and coordinating across distinct domains" (Section 4.2) represent a qualitatively different challenge. This claim is supported by the performance drop from single-scenario to cross-scenario settings (e.g., o3 drops from 53.5% in-store to 30.0% cross-scenario).

However, this comparison confounds two distinct sources of difficulty: (1) cross-scenario tasks genuinely require domain-switching and cross-domain coordination, and (2) cross-scenario tasks present agents with 66 tools (vs. 20-38 in single-scenario), creating a larger action space regardless of whether domain-switching is required. The performance drop could reflect tool selection difficulty in a larger action space (choosing the right tool among 66 options is harder than among 24) rather than domain-switching coordination specifically. The two factors are not separately manipulated or measured.

The consequence: Without a baseline that controls for tool count while eliminating domain-switching—for instance, single-domain tasks with 66 tools where 28-46 are irrelevant distractors—the paper cannot attribute the cross-scenario performance degradation to domain-switching specifically. The degradation could be entirely explained by the expanded action space, with domain-switching contributing nothing beyond what additional distractors would produce. The paper's tool complexity metrics (Table 5) show that cross-scenario tasks have 66 tools and 512 edges with 11.2% density—compared to OTA's 38 tools and 309 edges at 22.0% density. The edge count is higher but the density is lower, meaning the graph is sparser. Whether the higher absolute tool/edge count or the lower density (or both) causes the difficulty is unresolved.

Furthermore, the coverage ratio |V_task| / |V|—the fraction of available tools relevant to a task—differs between single-scenario and cross-scenario settings but is not reported. Cross-scenario tasks require agents to use tools from multiple domains, but at any given point in the trajectory, only a subset of the 66 tools is relevant. If a cross-scenario task can be cleanly decomposed into sequential single-domain phases (first use delivery tools, then OTA tools, then in-store tools), the effective action space at each step may be comparable to single-scenario tasks. The agent's difficulty would then come from recognizing when to switch domains, not from filtering a larger action space per step. The paper's data cannot distinguish between these two mechanisms.

What evidence exists in the paper: Table 5 reports tool counts, edge counts, and density for each domain including cross-scenario, but does not report coverage ratios or phase-level tool relevance distributions. The error pattern analysis (Figure 9) shows that tool selection errors constitute 21.1% of failures, but does not break these down by whether the error involved selecting a tool from the wrong domain vs. selecting the wrong tool within the correct domain. The reasoning error category (61.8%) could include domain-switching failures (failing to realize that the task requires switching to a different tool subgraph), but this is not separately identified.

Mitigation status: Not addressed. The paper does not include a "single-domain with expanded tool set" baseline that would isolate the effect of tool count from the effect of domain-switching. The ablation studies (Section 5.1-5.3) focus on user interaction complexity (Figure 8) and evaluator reliability (Table 4, Figure 7) rather than on decomposing the cross-scenario difficulty into constituent factors. The paper's interpretation that cross-scenario performance reveals "fundamental deficiencies in navigating expanded action spaces and coordinating across distinct domains" (Section 4.2) treats these as a unified challenge without attempting to measure their separate contributions. A simple baseline—evaluate models on delivery tasks with all 66 tools available but no cross-domain requirements—would have resolved this ambiguity at modest experimental cost.

---

7. Implications and Future Directions

How This Work Changes the Landscape

VitaBench introduces a new diagnostic lens for the field: it operationalizes a formal theory of agentic task complexity—reasoning, tool, and interaction dimensions—as a benchmark design principle rather than a post-hoc descriptive label. This is not a paradigm shift in how agents are built (no new architecture or training method is proposed), but it is a conceptual reframing of how agent capability is measured. The paper changes the evaluation conversation from "can the model call the right API?" to "can the model navigate an environment where constraints are discovered through interaction, users reveal information progressively and unpredictably, and success requires coordinating across disconnected tool ecosystems?"

The methodological shift: from documentation-dependent to environment-dependent evaluation. The paper's most consequential design choice—encoding domain rules in tool pre-condition/post-condition graphs rather than policy documents—directly challenges the dominant evaluation paradigm established by τ-bench (Yao et al., 2024) and τ²-bench (Barres et al., 2025). Those benchmarks test whether agents can read, comprehend, and follow explicitly stated rules. VitaBench tests whether agents can discover rules through interaction with an environment that enforces them. This shifts the measured capability from reading comprehension to environmental reasoning—a skill far more predictive of real-world deployment success, where comprehensive policy documentation is the exception rather than the rule. The 4× performance gap between single-scenario and cross-scenario settings (o3: 53.5% in-store → 30.0% cross-scenario; all-model averages: 42.1% in-store → 16.2% cross-scenario, Table 5) quantifies the cost of this paradigm shift: agents that appeared moderately capable under single-domain, documentation-rich evaluation collapse when forced to navigate without explicit guidance.

Reconciling prior contradictions. The paper's three-dimensional complexity framework provides a unified explanation for why prior benchmarks produced inconsistent and often misleadingly optimistic assessments of agent capability. Benchmarks strong on tool complexity but weak on interaction complexity (ToolSandbox, ToolLLM) made models look competent at function-calling but invisible to their dialogue management failures. Benchmarks strong on interaction but weak on tool complexity (IN3, UserBench) revealed conversational nuance but missed fundamental planning deficiencies. The τ-bench family addressed reasoning and interaction partially but relied on policy documents that made the reasoning task about reading rather than exploration. VitaBench's simultaneous challenge across all three dimensions—and its demonstration that cross-scenario composition is a distinct, severely underdeveloped capability—explains why a model could score 80%+ on simpler benchmarks while achieving only 30% on VitaBench's main results. The contradiction is not that prior benchmarks were "wrong" but that they were measuring different, partial components of agentic capability, and the field lacked a framework for recognizing that the components were incomplete.

Which research directions become more attractive. The paper's findings redirect research attention in several specific ways:

• Verifier and environment design becomes as important as agent architecture. The paper's tool graph design—where constraints are enforced by the environment rather than documented in text—is a form of automated verification: the environment tells the agent when it has violated a constraint by returning an error. Improving the quality and informativeness of this environmental feedback (e.g., error messages that explain why a pre-condition failed and what tool would satisfy it) could substantially improve agent performance without any change to the agent architecture. This makes environment engineering a first-class research direction rather than a benchmark implementation detail.

• Reliability (Passˆk) becomes a distinct optimization target. The paper's most striking empirical finding—that Passˆ4 drops to near-zero even when Pass@k reaches 73% (Figure 4)—reframes the agent development challenge. The field has optimized for best-case capability (can the model ever succeed?). VitaBench shows that deployment requires optimizing for consistency (can the model succeed every time?). This suggests that techniques specifically targeting variance reduction—ensemble methods, verification-at-runtime, explicit uncertainty estimation and clarification-seeking when confidence is low—may yield larger practical gains than techniques targeting peak capability.

• Cross-scenario navigation emerges as a critical bottleneck. The performance cliff from single-scenario to cross-scenario settings (Table 3, Table 5) is the paper's most actionable finding for research prioritization. Improving within-domain performance is valuable but incremental; solving cross-scenario coordination would unlock larger absolute gains. This directs attention toward meta-planning architectures that can decompose compound instructions into domain-specific sub-plans, tool-routing mechanisms that can map sub-goals to tool subgraphs, and state representations that maintain cross-domain consistency without conflating information from disconnected domains.

Which research directions become less attractive. The paper's findings also suggest diminishing returns for certain approaches:

• Scaling model size within current paradigms. The leaderboard (Table 3) shows that model capability correlates with general frontier status—o3, GPT-5, and Claude-4.1-Opus occupy the top positions—but the absolute ceiling of 30% on cross-scenario tasks suggests that simply scaling parameters or training data within existing architectures will not close the gap. The performance compression (30% best vs. 3.8% worst across models spanning orders of magnitude in scale) indicates that fundamental architectural or algorithmic limitations, not just capacity, are the bottleneck.

• Policy-document-based benchmarks as proxies for real-world capability. The paper's design philosophy—and the validation that tool-graph-based difficulty correlates with performance while policy-document difficulty is confounded with reading comprehension—weakens the case for using documentation-heavy benchmarks as primary evaluation tools. A model that excels at reading and following explicit policies may be learning a skill that does not transfer to deployment environments where such policies are unavailable or incomplete.

• Single-run evaluation as sufficient for model comparison. The paper's statistical reliability analysis (Figure 7) demonstrates that even at temperature 0.0, multi-turn interaction amplifies small perturbations into divergent trajectories, making single-run estimates unreliable. The 77.5% MSE reduction from 1 to 4 runs establishes that multi-run evaluation is not a luxury but a necessity for benchmarks with interactive environments—a finding that increases the cost of rigorous evaluation but is unavoidable for producing meaningful comparisons.

---

Follow-Up Research This Work Enables

1. Cheap difficulty estimation for adaptive compute allocation during inference. The paper's complexity framework identifies reasoning point count and tool graph density as strong correlates of task difficulty (Table 5), but these metrics are computed from full task specifications and cannot be observed by an agent before attempting the task. A natural follow-up would train a lightweight classifier—operating only on the initial user instruction and available tool schemas—to predict the likely difficulty bin of a task before the agent begins interaction. This would enable adaptive compute allocation: easy tasks (few reasoning points, low graph density) could be handled by a smaller, faster model or with fewer reasoning tokens, while hard tasks could be routed to larger models or allocated more test-time compute. The training signal would come from VitaBench's per-task average success rates across all evaluated models (available from the 4-run evaluations already conducted for Table 3), providing a difficulty ground truth. A strong result would demonstrate that such a classifier can predict difficulty at sufficient accuracy to improve the cost-performance Pareto frontier compared to uniform model routing—specifically, achieving >80% of the best-model performance at <50% of the cost by routing only genuinely hard tasks to expensive models.

2. Tool graph curriculum learning for agent fine-tuning. VitaBench provides a natural curriculum: single-scenario tasks with small tool graphs (delivery: 20 tools, 50 edges) through progressively larger graphs (OTA: 38 tools, 309 edges) to cross-scenario tasks (66 tools, 512 edges). The finding that tool graph density strongly correlates with performance degradation (OTA's 22.0% density → 20.7% performance vs. in-store's 12.3% density → 42.1% performance, Table 5) suggests that agents struggle specifically with navigating dense dependency structures. A fine-tuning experiment could train an agent model on VitaBench tasks in order of increasing graph density, measuring whether curriculum-ordered training produces better cross-scenario generalization than training on randomly ordered tasks or on cross-scenario tasks directly. The key measurement would be cross-scenario Passˆ4 (reliability) after curriculum training vs. after direct training, testing whether learning to navigate simpler dependency graphs first builds transferable skills for handling complex graphs. A negative result—curriculum training producing no benefit over direct training—would suggest that graph density difficulty is not a learnable skill but reflects fundamental architectural limitations in how current models represent structured action spaces.

3. Cross-model user simulator sensitivity analysis to measure interaction complexity generalizability. The paper validates its user simulator (gpt-4.1-2025-04-14) for fidelity and persona consistency (Figure 6: 9.48/10 fidelity, 9.34/10 persona consistency), but all 400 tasks use this single simulator model. A critical robustness check would evaluate the same set of agent models against the same tasks but with the user simulator replaced by a different model family—for instance, using Claude-4-Sonnet or Gemini-2.5-Pro as the simulator while keeping all task specifications, rubrics, and environment configurations identical. The research question is: do agent model rankings change when the interaction partner changes? If Claude-4.1-Opus (top-performing agent) maintains its rank when the simulator is switched from GPT-4.1 to Claude-4-Sonnet, interaction capability generalizes across simulator models. If rankings shift substantially—for instance, if GPT-series agents perform better with GPT-series simulators due to shared conversational patterns—then the benchmark's interaction complexity measurement is partially confounded with simulator-agent model similarity. The experiment would also quantify the variance in absolute performance attributable to simulator choice, providing a confidence interval around VitaBench's headline numbers that accounts for simulator model uncertainty.

4. Per-rubric partial credit analysis to identify the capability frontier. The paper collects per-rubric satisfaction data (the state vector s ∈ {0,1}^k for each trajectory) but reports only the strict all-or-nothing aggregate (Section 3.3). A deep follow-up analysis would compute, for each of the 400 tasks, the distribution of rubric satisfaction counts across all evaluated models—revealing which rubrics are universally satisfied (ceiling effects), which are universally failed (floor effects), and which discriminate between models. This analysis would identify the specific capability frontier: the set of rubrics that top models consistently satisfy but weaker models consistently fail, representing the skills that differentiate frontier from non-frontier agents. For example, if "correctly inferred dietary restrictions from user profile" is a rubric that o3 satisfies 90% of the time but Qwen3-32B satisfies 10% of the time, it identifies implicit constraint inference as a key discriminating capability. Conversely, if "correctly called pay_delivery_order after create_delivery_order" is a rubric that even the weakest models satisfy >90% of the time, it indicates that basic tool sequencing is not the bottleneck and research should focus elsewhere. This analysis is feasible with the paper's existing data (the per-rubric state vectors exist from the sliding window evaluator) and would transform the benchmark from a single-score leaderboard into a diagnostic instrument that tells researchers what to work on.

5. Human performance baseline with interface-matched constraints. The paper's claim that the 30% cross-scenario ceiling represents a "severe capability deficit" is uncalibrated without knowing whether humans can solve these tasks under the same constraints. A human study would recruit participants to solve a representative sample of VitaBench tasks using the same tool schemas, the same text-chat interface, and the same user simulator (with the simulator unaware of whether it is interacting with a human or an AI). The key measurement is human Avg@4 on cross-scenario tasks. If human performance is >80%, the 30% AI ceiling is clearly a capability deficit. If human performance is 40-60%, the tasks contain inherent difficulty (ambiguity, information boundaries, interface constraints) that affects all agents, and the AI ceiling should be interpreted relative to human performance rather than to 100%. If human performance is <30%, the benchmark is harder for humans than for the best AI—a surprising but informative result that would reframe VitaBench as measuring a capability where AI has already surpassed humans under these specific interface constraints. The study would also collect qualitative data on human strategies (how do humans handle domain-switching? when do they decide to ask clarifying questions?), providing a source of training signal and architectural inspiration that is currently absent from the paper.

6. Cross-benchmark correlation analysis to quantify the uniqueness of VitaBench's difficulty signal. The paper argues that prior benchmarks test only partial components of agentic capability and therefore produce misleadingly optimistic assessments, but this claim is asserted rather than empirically demonstrated. A correlation study would evaluate the same set of 10-15 models on VitaBench and on 3-4 prior benchmarks (e.g., τ-bench, ToolSandbox, BFCL, UserBench) and compute rank correlations and absolute performance correlations. If VitaBench rankings correlate strongly (Spearman's ρ > 0.8) with τ-bench rankings, then VitaBench is measuring similar capability through a harder lens and the unique contribution is primarily increased difficulty rather than qualitatively different evaluation. If correlations are weak (ρ < 0.4), then VitaBench is genuinely measuring different capabilities—supporting the paper's claim that prior benchmarks miss critical dimensions. The analysis would also identify which specific prior benchmarks have the strongest and weakest correlations with VitaBench, providing guidance for practitioners on which simpler benchmarks (if any) can serve as reasonable proxies for VitaBench-style complexity and which produce capability estimates that are essentially uncorrelated with real-world agentic performance as VitaBench measures it.

---

Practical Applications and Downstream Use Cases

1. Agent capability certification for customer-facing deployment decisions. Organizations developing or deploying LLM agents for life-serving applications (food delivery, travel booking, in-store services—the exact domains VitaBench is built from) can use the benchmark as a gatekeeping evaluation before production rollout. The paper's finding that Passˆ4 drops to 6% for even the best model on cross-scenario tasks (Table 3, o3 high) provides a concrete reliability threshold: if an agent cannot achieve Passˆ4 > 50% on a representative sample of VitaBench tasks matching its deployment domain, it will fail on more than half of user interactions in production—an unacceptable rate for customer-facing deployment. The rubric-level data (which the paper collects but does not report in aggregate) enables fine-grained certification: an organization could require that the agent achieves >90% satisfaction on "safety-critical" rubrics (correct payment processing, accurate order creation) even if overall success rates are lower. The 4-run evaluation protocol established by the paper's statistical reliability analysis (Figure 7, 77.5% MSE reduction at k=4) provides a validated testing protocol that balances statistical precision with cost.

2. Targeted fine-tuning data generation from failure patterns. The error distribution in Figure 9 (61.8% reasoning errors, 21.1% tool-use errors, 7.9% interaction errors) provides a prioritization map for data generation efforts. An organization that observes similar error distributions in their own agent's VitaBench performance can generate targeted fine-tuning data focusing on the dominant failure mode. For reasoning errors specifically—which constitute nearly two-thirds of all failures—the paper's complexity framework identifies the specific reasoning sub-types that cause difficulty: spatial-temporal coordination (the Appendix C example requires coordinating train arrival time, restaurant booking time, delivery arrival time, and cruise boarding time), constraint integration (synthesizing dietary restrictions from user profiles, accessibility requirements from "three-generation family" context, and budget constraints from explicit instructions), and implicit inference (recognizing that "suitable for elderly and children" implies accessibility facilities and specific menu requirements). Synthetic data generation could focus on creating training examples that specifically exercise these reasoning sub-types, using VitaBench's task structure (tool graphs, user profiles, composite instructions) as a template for producing diverse training instances. The tight feedback loop—evaluate on VitaBench, identify dominant failure mode, generate targeted training data, re-evaluate—is made possible by the benchmark's granular rubric structure and categorized error analysis.

3. Multi-model deployment architectures with difficulty-based routing. VitaBench's domain-level performance stratification (Table 5: in-store 42.1% average, delivery 38.0%, OTA 20.7%, cross-scenario 16.2%) provides a natural routing taxonomy for multi-model deployment. An organization could deploy a smaller, cheaper model for in-store and delivery tasks (where even non-thinking models achieve 30-50% success rates) while reserving a larger, more expensive thinking model for OTA and cross-scenario tasks (where the performance gap between model tiers is largest—GPT-5 goes from 4.0% minimal to 22.8% high on cross-scenario, a 5.7× improvement, vs. 30.0% to 54.0% on delivery, a 1.8× improvement). The specific routing decision would be: if a user's initial instruction maps primarily to in-store or delivery domains (determined by a lightweight classifier or keyword match on the instruction text), route to the cheaper model; if it maps to OTA or spans multiple domains, route to the expensive thinking model. The paper's finding that thinking models achieve better performance with fewer turns (Figure 5: 23.8% average performance at 61.1 turns for thinking vs. 17.9% at 69.9 turns for non-thinking) further supports this architecture: the expensive model is not just more capable but more efficient, reducing latency for the hardest tasks that users are already most frustrated by.

4. Reinforcement learning reward design using rubric-level success signals. The paper notes that the rubric-based evaluator provides "dense signals for reinforcement learning" (Section 3.3), and the per-rubric satisfaction data (collected but not aggregated in the paper) enables a specific RL training setup. Rather than training an agent with a sparse binary reward (1 if all rubrics satisfied, 0 otherwise), which would suffer from the credit assignment problem across 50-100 turn trajectories, the per-rubric state vector s ∈ {0,1}^k provides intermediate rewards: each time a previously unsatisfied rubric becomes satisfied (a transition from s_j = 0 to s_j = 1 in a sliding window), the agent receives a positive reward. This creates a natural curriculum where early rewards are easier to achieve (rubrics satisfied early in the trajectory, such as "correctly identified the user's dietary restrictions") and later rewards require coordination of earlier sub-goals (rubrics like "delivery arrives at the correct restaurant at the correct time"). The paper's own failure analysis (Section 5.3) notes that "agents show limited error recovery when facing tool failures or unclear user responses, with most repeating failed attempts rather than adapting other strategies"—an RL approach with per-rubric rewards could directly train error recovery by rewarding agents that try alternative strategies after a tool failure rather than repeating the failed call. The infrastructure for this training exists: VitaBench provides 400 diverse training environments with automated evaluation, and the rubric state vectors provide shaped rewards without human annotation. A strong RL result would demonstrate that an agent fine-tuned with per-rubric rewards on VitaBench training tasks achieves substantially higher Passˆ4 (reliability) than the same base model evaluated zero-shot, closing the gap between Pass@k and Passˆk that the paper identifies as the key deployment barrier.