💬 NLP

HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization

Dieses Paper führt HeuriGym ein, einen Open-Source-Agenten-Benchmark, der die Fähigkeit von Large Language Models bewertet, iterativ heuristische Algorithmen für kombinatorische Optimierungsprobleme zu generieren und zu verfeinern, wobei durch eine neuartige Quality-Yield-Index-Metrik signifikante Einschränkungen der aktuellen Modelle in Bezug auf Werkzeugnutzung und adaptives Denken aufgezeigt werden.

Ursprüngliche Autoren: Hongzheng Chen, Yingheng Wang, Yaohui Cai, Hins Hu, Jiajie Li, Shirley Huang, Chenhui Deng, Rongjian Liang, Shufeng Kong, Haoxing Ren, Samitha Samaranayake, Carla P. Gomes, Zhiru Zhang

Veröffentlicht 2026-01-29

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Hongzheng Chen, Yingheng Wang, Yaohui Cai, Hins Hu, Jiajie Li, Shirley Huang, Chenhui Deng, Rongjian Liang, Shufeng Kong, Haoxing Ren, Samitha Samaranayake, Carla P. Gomes, Zhiru Zhang

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben ein Team aus unglaublich intelligenten, belesenen Robotern (Large Language Models, oder LLMs), die hervorragend darin sind, Essays zu schreiben, Trivia-Fragen zu beantworten und sogar einfache Computerprogramme zu schreiben. Sie möchten wissen, ob sie tatsächlich in der Lage sind, schwierige, reale Rätsel eigenständig zu lösen, und nicht nur Antworten rezitieren, die sie aus einem Lehrbuch auswendig gelernt haben.

Das Paper stellt ein neues „Gym“ namens HeuriGym vor, um dies zu testen. So funktioniert es, erklärt durch einfache Analogien:

1. Das Problem: Die „Quizshow“ vs. der „echte Job“

Aktuelle Tests für KI sind wie ein Multiple-Choice-Quiz.

Das Problem: Wenn man einer KI ein mathematisches Problem stellt, das sie bereits in ihren Trainingsdaten gesehen hat, bekommt sie eine Eins. Aber wenn man ihr eine neue Art von Problem stellt, friert sie oft ein. Es ist wie ein Schüler, der den Lösungsschlüssel auswendig gelernt hat, aber die Mathematik dahinter nicht versteht.
Der alte Weg: Einige Tests fragen die KI, einen Code zu schreiben, der eine bestimmte Prüfung besteht. Diese sind jedoch oft zu einfach oder haben nur eine einzige „richtige“ Antwort.
Der neue Weg (HeuriGym): Anstatt ein Quiz durchzuführen, ist HeuriGym eher so, als würde man einer KI ein komplexes Konstruktionsprojekt ohne Bedienungsanleitung geben. Das Ziel ist nicht bloß, einen Test zu „bestehen“; das Ziel ist es, eine Maschine zu bauen, die effizient arbeitet.

2. Die Herausforderung: Das „kombinatorische Optimierungs“-Rätsel

Das Paper konzentriert sich auf eine spezifische Art von schwierigem Problem namens kombinatorische Optimierung.

Die Analogie: Stellen Sie sich vor, Sie sind ein Logistikmanager, der versucht, 1.000 Lieferwagen einzuplanen. Sie müssen die perfekte Route für jeden Lkw festlegen, damit sie am wenigsten Benzin verbrauchen und pünktlich ankommen.
Der Haken: Es gibt mehr mögliche Routen, als es Atome im Universum gibt. Man kann nicht alle prüfen. Man muss ein „Heuristik-Genie“ sein – das heißt, man muss einen cleveren Shortcut oder eine „Faustregel“ erfinden, um schnell eine gute Lösung zu finden, auch wenn diese mathematisch nicht perfekt ist.

3. Das Setup: Der „Agentic Loop“

HeuriGym fragt die KI nicht einfach einmalig nach einem Code und bewertet ihn. Es setzt eine Feedback-Schleife auf, ähnlich wie ein Videospiel mit „Respawns“.

Der Prompt: Die KI erhält eine Problembeschreibung (z. B. „Plane diese elektronischen Schaltkreise so, dass sie so schnell wie möglich laufen“).
Der Versuch: Die KI schreibt ein Programm (eine Heuristik), um das Problem zu lösen.
Der Realitätscheck: Das System führt den Code aus.
- Ist er abgestürzt? (Syntaxfehler)
- Hat er gegen Regeln verstoßen? (Constraint-Verletzung)
- War er zu langsam? (Timeout)
Das Feedback: Das System sagt der KI: „Du hast versucht, eine Library zu verwenden, die nicht existiert“, oder „Deine Lösung verletzt das Zeitlimit“.
Der erneute Versuch: Die KI liest den Fehler, lernt daraus und versucht, den Code neu zu schreiben, um den Fehler zu beheben.

Dieser Zyklus wiederholt sich, wodurch die KI durch Versuch und Irrtum „lernen“ kann, das Problem zu lösen, genau wie ein menschlicher Ingenieur.

4. Die Bewertung: Der „Quality-Yield Index“ (QYI)

Wie bewertet man einen Roboter, der versucht, einen neuen Weg zu finden, um ein Rätsel zu lösen? Die Autoren haben einen neuen Score entwickelt, den QYI.

Yield (Ertrag): Hat der Roboter die Aufgabe tatsächlich abgeschlossen, ohne abzustürzen? (Hat er eine funktionierende Lösung gefunden?)
Quality (Qualität): Wie gut war die Lösung im Vergleich zu einem menschlichen Experten?
Der Score: Ein Wert von 1,0 bedeutet, dass der Roboter exakt so gut performt wie ein menschlicher Experte. Ein Wert von 0 bedeutet, dass er komplett versagt hat.

5. Die Ergebnisse: Der „Reality Check“

Die Autoren haben neun der klügsten verfügbaren KI-Modelle getestet (wie GPT-o4-mini und Gemini-2.5-Pro).

Das Urteil: Selbst die „klügsten“ Modelle erreichten nur etwa 0,6.
Was das bedeutet: Die besten KI-Modelle sind nur etwa 60 % so effektiv wie ein menschlicher Experte bei diesen Aufgaben. Sie können oft Code schreiben, der zwar läuft, aber sie haben Schwierigkeiten, Code zu schreiben, der effizient genug oder kreativ genug ist, um menschliche Lösungen zu schlagen.
Die Schwierigkeit: Die Modelle gerieten oft in Endlosschleifen, halluzinierten (erfanden) fiktive Computer-Libraries oder scheiterten am Verständnis komplexer Einschränkungen. Sie waren gut darin, Anweisungen zu befolgen, aber schlecht darin, „out of the box“ zu denken, um eine neue Strategie zu entwickeln.

6. Warum das wichtig ist

Das Paper argumentiert, dass wir aufhören müssen, KI mit einfachen Quizfragen zu testen, und stattdessen mit echten Ingenieursherausforderungen beginnen müssen.

Das Ziel: Die KI-Entwicklung dahin voranzutreiben, dass Modelle wirklich fähig sind zu argumentieren, sich anzupassen und neue Lösungen für Wissenschaft und Technik zu erfinden, anstatt nur Muster auswendig zu lernen.
Das Fazit: Wir haben ein mächtiges Werkzeug gebaut (HeuriGym), um diesen Fortschritt zu messen. Momentan ist die KI ein vielversprechender Lehrling, aber noch kein Meisterhandwerker, wenn es um die Lösung komplexer, realer Optimierungsprobleme geht.

Kurz gesagt: HeuriGym ist ein Fitnessstudio, in dem KI-Roboter versuchen, ihre eigenen Werkzeuge zu bauen, um unmögliche Rätsel zu lösen. Sie werden besser, aber sie machen immer noch viele Fehler und haben das Niveau eines menschlichen Experten noch nicht erreicht.

Technisches Resümee: HeuriGym: Ein agentisches Benchmark für von LLMs entwickelte Heuristiken in der kombinatorischen Optimierung

Problemstellung

Aktuelle Evaluierungsmethoden für Large Language Models (LLMs) stehen vor einer dualen Krise bei der Bewertung ihrer Problemlösungsfähigkeiten. Erstens basieren grund wahrheitsorientierte Benchmarks (z. B. AIME, HumanEval) auf geschlossenen Fragen, die anfällig für Datenkontamination und Leistungs-Sättigung sind und dadurch nicht in der Lage sind, reale Szenarien abzubilden, in denen Lösungen nicht eindeutig oder vordefiniert sind. Zweitens führen urteilersubjektive Präferenzbewertungen (z. B. Chatbot Arena) eine hohe Varianz ein und priorisieren oft oberflächliche Faktoren gegenüber substanzieller Denkqualität.

Es besteht eine kritische Lücke bei der Bewertung, ob LLMs über bloße Mustererkennung hinausgehen und echte Problemlösungskompetenz in komplexen, iterativen Engineering-Workflows zeigen können. Speziell scheitern bestehende Benchmarks daran, die Fähigkeit zu bewerten, neuartige Heuristiken für kombinatorische Optimierungsprobleme (CO) zu entwerfen, welche das Navigieren in riesigen Lösungsräumen, die Einhaltung strenger Nebenbedingungen und die Anpassung von Strategien basierend auf Laufzeit-Feedback erfordern.

Methodik

Die Autoren führen HeuriGym ein, ein agentisches Framework, das darauf ausgelegt ist, LLMs in der Generierung, Ausführung und iterativen Verfeinerung heuristischer Algorithmen für kombinatorische Optimierungsprobleme zu evaluieren.

Framework-Übersicht

HeuriGym operiert durch eine interaktive agentische Schleife, die aus drei Stufen besteht:

Problembeschreibung: Das LLM erhält einen strukturierten Prompt, der einen natürlichen Sprachhintergrund, eine mathematische Formalisierung des Ziels und der Nebenbedingungen sowie spezifische Eingabe-/Ausgabedateiformate enthält. Im Gegensatz zu bisheriger Arbeit, die Teilimplementierungen oder Gerüste bereitstellt, liefert HeuriGym lediglich die Funktionsschnittstelle, was das LLM dazu zwingt, Datenstrukturen und Algorithmen von Grund auf neu zu entwerfen.
Ausführung und Verifizierung: Der generierte Code wird innerhalb einer Sandboxed-Umgebung kompiliert oder interpretiert. Ein domänenspezifischer Verifizierer prüft die Einhaltung von Nebenbedingungen (z. B. Erhaltung von Abhängigkeiten), während ein Evaluator die Kosten basierend auf dem Optimierungsziel berechnet.
Iterative Verfeinerung: Ausführungsprotokolle, Verifizierungsergebnisse und Leistungsmetriken aus einem kleinen Demonstrationssatz werden an den Prompt angehängt. Diese Feedbackschleife ermöglicht es dem LLM, Fehler zu debuggen, Nebenbedingungsverletzungen zu korrigieren und seine heuristischen Strategien über mehrere Iterationen hinweg zu verfeinern.

Benchmark-Konstruktion

Der Benchmark umfasst neun kombinatorische Optimierungsprobleme aus den Bereichen Computersysteme, Logistik und computergestützte Biologie (z. B. Operator-Scheduling, Technologie-Mapping, Fluggesellschaft-Crew-Pairing, Proteinsequenzdesign).

Selektionskriterien: Die Probleme wurden ausgewählt, weil sie in der Literatur nur begrenzt vorkommen (weniger als 1.000 Zitationen für das meistzitierte Paper), um das Risiko der Auswendiglernung zu minimieren. Sie zeichnen sich durch klar definierte natürliche Sprachspezifikationen, große Lösungsräume und skalierbare Dateninstanzen aus.
Datensatz: Jedes Problem enthält einen kleinen Demonstrationssatz (~5 Instanzen) für Few-Shot-Prompting und iterative Verfeinerung sowie einen größeren Evaluationssatz (Dutzende von Instanzen) für das finale Testen.

Evaluierungsmetriken

Um die Einschränkungen von Standardmetriken wie PASS@k zu adressieren, schlagen die Autoren vor:

SOLVEs@i: Verfolgt die Wahrscheinlichkeit, ein problem mit Nebenbedingungen innerhalb von $i$ Iterationen zu lösen, und misst den Erfolg beim Bestehen von drei Stufen: Ausführung (Stufe I), Lösungsgenerierung (Stufe II) und Verifizierung (Stufe III).
Quality-Yield Index (QYI): Eine vereinheitlichte Metrik, definiert als das harmonische Mittel aus Qualität (wie nah die Lösung an einer Experten-Baseline liegt) und Ertrag (der Anteil der Instanzen, die die Verifizierung bestehen).
- $Quality = \frac{1}{\hat{N}} \sum \min(1, \frac{c^*_n}{c_n})$ , wobei $c_n$ die Kosten des LLM und $c^*_n$ die Kosten des Experten sind.
- $Yield = \frac{\hat{N}}{N}$ , wobei $\hat{N}$ die Anzahl der verifizierten Lösungen ist.
- $QYI = \frac{(1 + \beta^2) \cdot Quality \cdot Yield}{(\beta^2 \cdot Quality) + Yield}$ (mit $\beta=1$ ).

Kernergebnisse

Die Autoren evaluierten neun State-of-the-Art-Modelle (einschließlich GPT-o4-mini-high, Gemini-2.5-Pro, DeepSeek-R1 und LLaMA-Varianten) auf dem HeuriGym-Benchmark.

Leistungslücke: Selbst Top-Modelle haben Schwierigkeiten, Expertenniveau zu erreichen. Das leistungsstärkste Modell, Gemini-2.5-Pro, erreichte einen QYI-Score von etwa 0,62, was darauf hindeutet, dass seine Lösungen im Durchschnitt nur 60 % so effektiv sind wie Experten-entwickelte Heuristiken. Andere Modelle schnitten signifikant schlechter ab (z. B. LLaMA-3.3 und LLaMA-4-Maverick unter 0,30).
Iterative Verbesserung: Eine Erhöhung der Anzahl der Iterationen verbessert die Leistung erheblich. Beispielsweise stieg die Erfolgsrate (SOLVEIII) von GPT-o4-mini-high von 53,2 % bei Iteration 1 auf 74,8 % bei Iteration 10, was die Bedeutung der iterativen Verfeinerung hervorhebt.
Fehlermodi: Die Analyse deckte häufige Fehlertypen auf, darunter halluzinierte APIs, fehlerhafte algorithmische Logik, Missverständnisse von Nebenbedingungen und Timeouts.
Evolutionäre Frameworks: Standardmäßige evolutionäre Suchframeworks (z. B. ReEvo, HSEvo) schnitten schlecht ab im Vergleich zum Baseline-Modell, da sie oft nicht in der Lage waren, die Ausführungs-Feedback effektiv zu integrieren und den Kontext über Iterationen hinweg aufrechtzuerhalten.

Bedeutung und Beiträge

Das Paper beansprucht drei primäre Beiträge:

Eine Open-Source-Benchmark-Suite: Eine Sammlung von neun realistischen, hochwirksamen kombinatorischen Optimierungsproblemen, die mehrstufiges Denken und algorithmische Designfähigkeiten evaluieren und über das bloße Auswendiglernen von Mustern hinausgehen.
Ein End-to-End agentisches Framework: Ein System, das Lösungsgenerierung, automatisierte Verifizierung und iterative Verfeinerung unterstützt und als Testfeld für fortgeschrittene Prompting-Techniken und evolutionäre Strategien dient.
Empirische Erkenntnisse: Eine umfassende Studie, die zeigt, dass aktuelle LLMs trotz ihrer Denkfähigkeiten hartnäckige Einschränkungen bei der Werkzeugnutzung, der Planung und dem adaptiven Denken aufweisen, wenn sie auf komplexe, reale wissenschaftliche und technische Probleme angewendet werden.

Die Autoren positionieren HeuriGym als notwendigen Schritt, um die Entwicklung von LLMs hin zu effektiverem, realistischem Problemlösen in Domänen zu lenken, in denen optimale Lösungen nur für kleine Instanzen handhabbar sind und in denen die Entdeckung von Heuristiken essenziell ist. Der Benchmark zielt darauf ab, die Lücke zwischen aktuellen Modellkapazitäten und den Anforderungen praktischer Engineering-Workflows aufzuzeigen und die Entwicklung von Modellen zu fördern, die zu echter heuristischer Erfindung statt bloßer Mustererkennung fähig sind.