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

Résumé Technique : CRAB-Bench

Énoncé du Problème
L'évaluation des agents basés sur les Grands Modèles de Langage (LLM) dans des scénarios de service réalistes (ex. : planification de voyages, support client) reste un défi en raison de trois lacunes principales dans les benchmarks existants :

1. Dépendances de Tâches Complexes : Les requêtes du monde réel impliquent des dépendances multi-étapes où la satisfaction d'une sous-tâche contraint implicitement les autres, exigeant que les agents planifient à travers des entités et propagent les conséquences sans instruction explicite.
2. Comportement Utilisateur Imparfait : Les utilisateurs réels ne sont pas des modèles coopératifs ; ils divulguent l'information de manière incrémentielle, communiquent de façon ambiguë et réagissent émotionnellement aux erreurs. Les benchmarks actuels reposent souvent sur des simulateurs coopératifs de type "modèle", ce qui diverge du comportement humain.
3. Multiplicité des Solutions Valides : De nombreuses tâches admettent plusieurs issues valides, rendant insuffisantes les méthodes d'évaluation qui comparent la sortie de l'agent à un enregistrement unique de vérité terrain (ground-truth).

Les benchmarks actuels (ex. : $\tau$-bench, $\tau^2$-bench) abordent partiellement ces problèmes mais souffrent souvent de saturation, d'une évaluation rigide basée sur la vérité terrain et de l'utilisation de simulateurs d'utilisateurs basés sur des LLM qui sous-évaluent systématiquement la difficulté sur les tâches difficiles et la surestiment sur les tâches modérées.

Méthodologie
Les auteurs introduisent CRAB-Bench (Constraint-based Realistic Agent Benchmark) et RUSE (Realistic User Simulation Engine) pour combler ces lacunes. Le cadre se compose de trois composantes centrales :

1. Génération de Tâches Basée sur des Graphes de Contraintes :

   • Les tâches sont modélisées comme des graphes de contraintes où les nœuds représentent des entités (ex. : vols, hôtels) avec des propriétés discrètes et des domaines finis.
   • Les contraintes sont divisées en contraintes de domaine (règles intra-entité, ex. : une classe affaires ne peut pas être un siège du milieu) et contraintes de validité (règles inter-entités et de préférences utilisateur, ex. : limites de budget total).
   • Pipeline de Génération : Le système utilise un solveur de Problème de Satisfaction de Contraintes (CSP) pour générer des "solutions germes" (combinaisons valides). Il peuple ensuite la base de données avec des distracteurs :
     • Distracteurs de Nœud ($D_{node}$) : Objets qui satisfont les contraintes de domaine mais violent des contraintes de validité spécifiques au niveau du nœud (ex. : un vol à la mauvaise heure).
     • Distracteurs d'Arête ($D_{edge}$) : Objets qui sont individuellement valides mais incompatibles avec d'autres entités pour former une solution complète (ex. : un hôtel qui respecte le budget mais n'a pas de dates de vol correspondantes).
   • Cela crée un espace de recherche où les solutions valides ne représentent qu'une infime fraction des candidats totaux (ex. : un ratio de distracteurs de 0,05 % dans la strate la plus difficile).

2. Simulation d'Utilisateur Alignée sur l'Humain (RUSE) :

   • RUSE remplace les simulateurs de type modèle par des agents ancrés dans des études de comportement humain.
   • Il définit quatre dimensions comportementales : (D1) Style de communication (ton, émotion), (D2) Divulgation d'informations (incrémentielle, sous-spécifiée), (D3) Clarification (niveaux de confiance) et (D4) Réaction aux erreurs.
   • Ces dimensions sont instanciées à travers trois personas : Concis (Terse), Neutre et Impatient.

3. Évaluation Basée sur l'État :

   • L'évaluation évite la comparaison avec une vérité terrain unique en utilisant deux ensembles de vérificateurs basés sur des règles complémentaires :
     • Vérificateurs d'État Concret : Vérifient si l'état final de la base de données satisfait toutes les exigences de la tâche.
     • Vérificateurs d'État Abstrait : Vérifient la véracité de la communication (les actions correspondent aux plans énoncés) et l'achèvement de la tâche (l'interaction se termine correctement).
   • Une tâche est considérée comme résolue uniquement si elle passe les deux vérificateurs.

Configuration Expérimentale

• Domaine : Réservation de voyage impliquant 19 outils d'agent et 7 outils d'utilisateur à travers 4 entités requises (vol aller, vol retour, hôtel, attraction).
• Jeu de Données : 200 tâches stratifiées par difficulté (S1–S4) selon le nombre de solutions germes (1 à 4). S1 représente les tâches les plus difficiles avec le plus faible ratio de solutions valides.
• Modèles : Quatre agents LLM de pointe ont été évalués : Claude Sonnet 4.6, DeepSeek V3.2, GLM-5 et Qwen3 Coder Next.
• Lignes de Base (Baselines) : Les agents ont été testés contre un simulateur d'utilisateur générique (suivant $\tau^2$-bench) et le RUSE proposé.

Résultats Clés

• Plafond de Performance : Le modèle le plus performant (DeepSeek V3.2) a obtenu seulement 61 % de pass@1 sur CRAB-Bench avec RUSE, ce qui est nettement inférieur à sa performance sur les benchmarks existants (ex. : 78,9 % sur $\tau^2$-bench).
• Impact de la Simulation Réaliste : Le passage d'un simulateur générique à RUSE a provoqué des chutes de performance allant de 19 % à 57 % pour tous les modèles.
• Nature de l'Échec : La dégradation des performances est concentrée dans la capacité de résolution de tâches (la vérification de l'état concret a chuté de 17 à 39 %) plutôt que dans la qualité conversationnelle (la vérification de l'état abstrait est restée relativement stable, chutant de seulement 0 à 6 %).
• Sensibilité Comportementale : La Divulgation d'Informations (D2) a été identifiée comme la dimension comportementale la plus dommageable. De plus, les agents interagissant avec RUSE étaient moins enclins à admettre leurs erreurs, préférant masquer les erreurs par des corrections implicites.
• Analyse de la Complexité :
  • Les modèles plus forts (DeepSeek, Claude) ont montré une meilleure capacité à exploiter des chemins alternatifs à mesure que le nombre de solutions valides augmentait (de S1 à S4), tandis que les modèles plus faibles (Qwen) sont restés bloqués.
  • Les contraintes d'arête (dépendances entre sous-tâches) constituent un goulot d'étranglement majeur ; les tâches avec des dates flexibles (plus de contraintes d'arête actives) ont entraîné des taux de réussite nettement inférieurs (8,3 %–33,3 %) par rapport aux tâches à dates fixes, même avec des pools de distracteurs comparables.

Signification et Revendications
L'article affirme que CRAB-Bench révèle un écart critique entre les performances des benchmarks et les scénarios utilisateurs réels. Les auteurs soutiennent que les agents LLM actuels peinent non seulement avec l'utilisation d'outils, mais aussi avec le raisonnement requis pour naviguer dans des contraintes complexes et interdépendantes, ainsi qu'avec l'adaptabilité nécessaire pour gérer une communication humaine imparfaite.

L'étude souligne que :

1. Les benchmarks existants peuvent surestimer les capacités des agents en raison de simulateurs coopératifs et de métriques d'évaluation rigides.
2. La capacité à gérer des "candidats trompeurs" dans un vaste espace de recherche est un obstacle majeur pour les agents actuels.
3. Les comportements humains, particulièrement la divulgation incrémentielle d'informations, dégradent considérablement les performances des agents, suggérant que le développement futur des agents doit prioriser la robustesse du raisonnement et la gestion des erreurs plutôt que la simple fluidité conversationnelle.

Les auteurs positionnent CRAB-Bench comme un cadre évolutif pouvant être étendu à d'autres domaines, fournissant un standard plus rigoureux pour évaluer les systèmes agentiques dans des environnements de service du monde réel.