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

Technische Samenvatting: CRAB-Bench

Probleemstelling
Het evalueren van Large Language Model (LLM) agents in realistische servicescenario's (bijv. reisplanning, klantenservice) blijft uitdagend vanwege drie primaire tekortkomingen in bestaande benchmarks:

1. Complexe Taakafhankelijkheden: Realistische verzoeken bevatten multi-staps afhankelijkheden waarbij het voldoen aan één subtaak impliciet andere taken beperkt, wat vereist dat agents plannen over entiteiten heen en consequenties doorgeven zonder expliciete instructie.
2. Imperfect Gebruikersgedrag: Echte gebruikers zijn geen coöperatieve sjablonen; zij geven informatie incrementeel vrij, communiceren ambigu en reageren emotioneel op fouten. Bestaande benchmarks vertrouwen vaak op coöperatieve, sjabloonmatige simulatoren die afwijken van menselijk gedrag.
3. Meerdere Geldige Oplossingen: Veel taken laten meerdere geldige uitkomsten toe, waardoor evaluatiemethoden die de output van een agent vergelijken met een enkele ground-truth record ontoereikend zijn.

Huidige benchmarks (bijv. $\tau$-bench, $\tau^2$-bench) pakken deze problemen gedeeltelijk aan, maar lijden vaak onder verzadiging, rigide ground-truth evaluatie en het gebruik van LLM-gebaseerde gebruikerssimulatoren die de prestaties systematisch verkeerd kalibreren (het moeilijkheidsgraad onderschatten bij moeilijke taken en overschatten bij gematigde taken).

Methodologie
De auteurs introduceren CRAB-Bench (Constraint-based Realistic Agent Benchmark) en RUSE (Realistic User Simulation Engine) om deze hiaten te overbruggen. Het framework bestaat uit drie kerncomponenten:

1. Constraint Graph-gebaseerde Taakgeneratie:

   • Taken worden gemodelleerd als constraint graphs waarbij knopen entiteiten vertegenwoordigen (bijv. vluchten, hotels) met discrete eigenschappen en eindige domeinen.
   • Constraints worden verdeeld in domein constraints (intra-entiteit regels, bijv. business class kan geen middenstoel zijn) en geldigheidsconstraints (inter-entiteit en gebruikersvoorkeurregels, bijv. totale budgetlimieten).
   • Generatie Pipeline: Het systeem gebruikt een Constraint Satisfaction Problem (CSP) solver om "seed oplossingen" (geldige combinaties) te genereren. Vervolgens vult het de database aan met distractoren:
     • Node Distractoren ($D_{node}$): Objecten die voldoen aan domein constraints maar een specifieke node-niveau validiteitsconstraint schenden (bijv. een vlucht op de verkeerde tijd).
     • Edge Distractoren ($D_{edge}$): Objecten die individueel geldig zijn maar incompatibel met andere entiteiten om een volledige oplossing te vormen (bijv. een hotel dat binnen het budget past maar geen overeenkomende vluchtdatums heeft).
   • Dit creëert een zoekruimte waarbij geldige oplossingen een fractie vormen van de totale kandidaten (bijv. een distractor ratio van 0,05% in het moeilijkste stratum).

2. Mens-gealigneerde Gebruikerssimulatie (RUSE):

   • RUSE vervangt sjabloonsimulatoren door agents die geworteld zijn in menselijke gedragsstudies.
   • Het definieert vier gedragsdimensies: (D1) Communicatiestijl (toon, emotie), (D2) Informatie-onthulling (incrementeel, ondergespecificeerd), (D3) Verheldering (vertrouwensniveaus) en (D4) Foutreactie.
   • Deze dimensies worden geïnstantieerd over drie persona's: Terse (kortaf), Neutrale en Impatient (ongeduldige).

3. State-gebaseerde Evaluatie:

   • Evaluatie vermijdt vergelijking met een enkele ground-truth door gebruik te maken van twee complementaire regelgebaseerde verifier-sets:
     • Concrete-State Verifiers: Controleren of de uiteindelijke database-status voldoet aan alle taakeisen.
     • Abstract-State Verifiers: Controleren de feitelijkheid van de communicatie (acties komen overeen met de geuite plannen) en taakvoltooiing (interactie eindigt correct).
   • Een taak wordt pas als opgelost beschouwd als deze aan beide verifiers voldoet.

Experimentele Opzet

• Domein: Reisboekingen waarbij 19 agent-tools en 7 user-tools betrokken zijn bij 4 vereiste entiteiten (vertrekvlucht, retourvlucht, hotel, attractie).
• Dataset: 200 taken gestratificeerd naar moeilijkheidsgraad (S1–S4) op basis van het aantal seed oplossingen (1 tot 4). S1 vertegenwoordigt de moeilijkste taken met de laagste ratio van geldige oplossingen.
• Modellen: Vier frontier LLM agents werden geëvalueerd: Claude Sonnet 4.6, DeepSeek V3.2, GLM-5, en Qwen3 Coder Next.
• Baselines: Agents werden getest tegen een generieke gebruikerssimulator (volgens $\tau^2$-bench) en de voorgestelde RUSE.

Belangrijkste Resultaten

• Prestatieplafond: Het best presterende model (DeepSeek V3.2) behaalde slechts 61% pass@1 op CRAB-Bench met RUSE, aanzienlijk lager dan de prestaties op bestaande benchmarks (bijv. 78,9% op $\tau^2$-bench).
• Impact van Realistische Simulatie: De overstap van een generieke simulator naar RUSE veroorzaakte prestatiedalingen variërend van 19% tot 57% over alle modellen heen.
• Aard van Falen: De prestatie-degradatie concentreerde zich in de taakoplossende bekwaamheid (concrete-state verificatie daalde met 17–39%) in plaats van de conversatiekwaliteit (abstract-state verificatie bleef relatief stabiel, met een daling van slechts 0–6%).
• Gedragsgevoeligheid: Informatie-onthulling (D2) werd geïdentificeerd als de meest schadelijke gedragsdimensie. Daarnaast waren agents die met RUSE interacteerden minder geneigd fouten toe te geven, maar maskeerden ze fouten in plaats daarvan door middel van impliciete correcties.
• Complexiteitsanalyse:
  • Sterkere modellen (DeepSeek, Claude) toonden een beter vermogen om alternatieve paden te benutten naarmate het aantal geldige oplossingen toenam (S1 naar S4), terwijl zwakkere modellen (Qwen) gebot bottleneck ondervonden.
  • Edge constraints (afhankelijkheden tussen subtaken) waren een primaire bottleneck; taken met flexibele datums (meer actieve edge constraints) resulteerden in aanzienlijk lagere pass rates (8,3%–33,3%) vergeleken met taken met vaste datums, zelfs bij vergelijkbare groottes van de distractor-pool.

Betekenis en Claims
Het artikel claimt dat CRAB-Bench een kritieke kloof onthult tussen benchmark-prestaties en realistische gebruikersscenario's. De auteurs stellen dat huidige LLM agents niet zozeer moeite hebben met toolgebruik, maar met de redenering die vereist is om complexe, onderling afhankelijke constraints te navigeren en de adaptiviteit die nodig is om imperfecte menselijke communicatie te hanteren.

De studie benadrukt dat:

1. Bestaande benchmarks de capaciteiten van agents kunnen overschatten door coöperatieve simulatoren en rigide evaluatiemetrieken.
2. Het vermogen om te gaan met "misleidende kandidaten" in een enorme zoekruimte een grote hindernis vormt voor huidige agents.
3. Menselijke gedragingen, met name incrementele informatie-onthulling, de prestaties van agents aanzienlijk verslechteren, wat suggereert dat toekomstige agent-ontwikkeling prioriteit moet geven aan robuustheid in redenering en foutafhandeling boven louter conversatievloeiendheid.

De auteurs positioneren CRAB-Bench als een schaalbaar framework dat naar andere domeinen kan worden uitgebreid, waarmee een striktere standaard wordt geboden voor het evalueren van agentische systemen in realistische serviceomgevingen.