CRAB-Bench: Evaluating LLM Agents under Complex Task Dependencies and Human-aligned User Simulation

Technical Summary: CRAB-Bench

Problem Statement
Evaluating Large Language Model (LLM) agents in realistic service scenarios (e.g., travel planning, customer support) remains challenging due to three primary gaps in existing benchmarks:

1. Complex Task Dependencies: Real-world requests involve multi-step dependencies where satisfying one subtask implicitly constrains others, requiring agents to plan across entities and propagate consequences without explicit instruction.
2. Imperfect User Behavior: Real users are not cooperative templates; they disclose information incrementally, communicate ambiguously, and react emotionally to errors. Existing benchmarks often rely on cooperative, template-like simulators that diverge from human behavior.
3. Multiple Valid Solutions: Many tasks admit multiple valid outcomes, rendering evaluation methods that compare agent output against a single ground-truth record insufficient.

Current benchmarks (e.g., $\tau$-bench, $\tau^2$-bench) partially address these issues but often suffer from saturation, rigid ground-truth evaluation, and the use of LLM-based user simulators that systematically miscalibrate performance (underestimating difficulty on hard tasks and overestimating on moderate ones).

Methodology
The authors introduce CRAB-Bench (Constraint-based Realistic Agent Benchmark) and RUSE (Realistic User Simulation Engine) to bridge these gaps. The framework consists of three core components:

1. Constraint Graph-Based Task Generation:

   • Tasks are modeled as constraint graphs where nodes represent entities (e.g., flights, hotels) with discrete properties and finite domains.
   • Constraints are divided into domain constraints (intra-entity rules, e.g., business class cannot be a middle seat) and validity constraints (inter-entity and user-preference rules, e.g., total budget limits).
   • Generation Pipeline: The system uses a Constraint Satisfaction Problem (CSP) solver to generate "seed solutions" (valid combinations). It then populates the database with distractors:
     • Node Distractors ($D_{node}$): Objects that satisfy domain constraints but violate specific node-level validity constraints (e.g., a flight at the wrong time).
     • Edge Distractors ($D_{edge}$): Objects that are individually valid but incompatible with other entities to form a complete solution (e.g., a hotel that fits the budget but has no matching flight dates).
   • This creates a search space where valid solutions are a tiny fraction of the total candidates (e.g., 0.05% distractor ratio in the hardest stratum).

2. Human-Aligned User Simulation (RUSE):

   • RUSE replaces template simulators with agents grounded in human behavioral studies.
   • It defines four behavioral dimensions: (D1) Communication style (tone, emotion), (D2) Information Disclosure (incremental, underspecified), (D3) Clarification (confidence levels), and (D4) Error Reaction.
   • These dimensions are instantiated across three personas: Terse, Neutral, and Impatient.

3. State-Based Evaluation:

   • Evaluation avoids single ground-truth comparison by using two complementary rule-based verifier sets:
     • Concrete-State Verifiers: Check if the final database state satisfies all task requirements.
     • Abstract-State Verifiers: Check communication factuality (actions match stated plans) and task completion (interaction ends correctly).
   • A task is considered solved only if it passes both verifiers.

Experimental Setup

• Domain: Trip booking involving 19 agent tools and 7 user tools across 4 required entities (departure flight, return flight, hotel, attraction).
• Dataset: 200 tasks stratified by difficulty (S1–S4) based on the number of seed solutions (1 to 4). S1 represents the hardest tasks with the lowest valid solution ratio.
• Models: Four frontier LLM agents were evaluated: Claude Sonnet 4.6, DeepSeek V3.2, GLM-5, and Qwen3 Coder Next.
• Baselines: Agents were tested against a generic user simulator (following $\tau^2$-bench) and the proposed RUSE.

Key Results

• Performance Ceiling: The best-performing model (DeepSeek V3.2) achieved only 61% pass@1 on CRAB-Bench with RUSE, significantly lower than its performance on existing benchmarks (e.g., 78.9% on $\tau^2$-bench).
• Impact of Realistic Simulation: Switching from a generic simulator to RUSE caused performance drops ranging from 19% to 57% across all models.
• Nature of Failure: The performance degradation was concentrated in task-solving ability (concrete-state verification dropped 17–39%) rather than conversational quality (abstract-state verification remained relatively stable, dropping only 0–6%).
• Behavioral Sensitivity: Information Disclosure (D2) was identified as the most damaging behavioral dimension. Additionally, agents interacting with RUSE were less likely to admit mistakes, instead masking errors through implicit corrections.
• Complexity Analysis:
  • Stronger models (DeepSeek, Claude) showed better ability to leverage alternative paths as the number of valid solutions increased (S1 to S4), whereas weaker models (Qwen) remained bottlenecked.
  • Edge constraints (dependencies between subtasks) were a primary bottleneck; tasks with flexible dates (more active edge constraints) resulted in significantly lower pass rates (8.3%–33.3%) compared to fixed-date tasks, even with comparable distractor pool sizes.

Significance and Claims
The paper claims that CRAB-Bench reveals a critical gap between benchmark performance and realistic user scenarios. The authors argue that current LLM agents struggle not merely with tool use, but with the reasoning required to navigate complex, interdependent constraints and the adaptability needed to handle imperfect human communication.

The study highlights that:

1. Existing benchmarks may overestimate agent capabilities due to cooperative simulators and rigid evaluation metrics.
2. The ability to handle "misleading candidates" in a vast search space is a major hurdle for current agents.
3. Human-like behaviors, particularly incremental information disclosure, significantly degrade agent performance, suggesting that future agent development must prioritize robustness in reasoning and error handling over mere conversational fluency.

The authors position CRAB-Bench as a scalable framework that can be extended to other domains, providing a more rigorous standard for evaluating agentic systems in real-world service environments.