R-ConstraintBench: Neue Benchmark für LLMs bei NP‑Vollständigen Planungsaufgaben

Die Planung von Projekten unter engen Ressourcen-, Zeit- und Betriebseinschränkungen ist in vielen Bereichen – von Bauvorhaben über Fertigung bis hin zu Logistik und IT‑Migrationen – von entscheidender Bedeutung. Trotz der zunehmenden Verbreitung großer Sprachmodelle (LLMs) ist ihre Zuverlässigkeit bei der Lösung solcher hochgradig eingeschränkten Aufgaben noch nicht ausreichend untersucht.

Um diese Lücke zu schließen, wurde R‑ConstraintBench entwickelt. Dabei handelt es sich um ein skalierbares Framework, das LLMs anhand von Resource‑Constrained Project Scheduling Problems (RCPSP) bewertet – einer NP‑vollständigen Klasse von Planungsproblemen. Die Schwierigkeit wird dabei systematisch erhöht, indem die Anzahl der nicht redundanten Präzedenzrestriktionen in gerichteten azyklischen Graphen (DAGs) linear gesteigert wird.

Im Rahmen des Benchmarks werden zunächst Präzedenzrestriktionen hinzugefügt, gefolgt von weiteren Einschränkungen wie Ausfallzeiten, zeitlichen Fensterbedingungen und disjunktiven Beschränkungen. Als konkretes Beispiel wurde die Benchmark in einer Datenzentrums‑Migrationssituation implementiert. Mehrere LLMs wurden hinsichtlich ihrer Lösungsfähigkeit und Fehlerquoten getestet, wobei Schwellenwerte für die Leistungsabnahme und die am häufigsten fehlerhaften Restrikttypen identifiziert wurden.

Die Ergebnisse zeigen, dass leistungsstarke Modelle bei ausschließlich Präzedenz‑DAGs nahezu die optimale Leistung erreichen. Sobald jedoch Ausfallzeiten, zeitliche Fenster und disjunktive Einschränkungen zusammenwirken, verschlechtert sich die Lösungsfähigkeit dramatisch. Dies legt nahe, dass die Interaktion zwischen Restriktionen – nicht die Tiefe des Graphen – der Hauptengpass ist. Zudem demonstriert die Analyse, dass gute Leistungen bei rein synthetischen Rampen nicht automatisch auf domänenspezifische Szenarien übertragbar sind, was die begrenzte Generalisierbarkeit unterstreicht.

R‑ConstraintBench bietet damit einen systematischen Ansatz, um die Fähigkeiten von LLMs in hochgradig eingeschränkten Planungsaufgaben zu bewerten. Die Erkenntnisse betonen die Notwendigkeit, die Interaktion komplexer Restriktionen besser zu verstehen und zu adressieren, um die Zuverlässigkeit von KI‑gestützten Planungssystemen zu erhöhen.