🤖 AI

Forge: Quality-Aware Reinforcement Learning for NP-Hard Optimization in LLMs

Das Papier stellt OPT-BENCH vor, ein umfassendes Framework, das qualitätsbewusstes Reinforcement Learning mit verifizierbaren Belohnungen (RLVR) nutzt, um Large Language Models auf NP-schwere Optimierungsprobleme zu trainieren, und dabei im Vergleich zu bestehenden Modellen und binären Belohnungsansätzen signifikante Verbesserungen der Lösungsqualität und Generalisierung über diverse Schlussfolgerungsaufgaben hinweg demonstriert.

Ursprüngliche Autoren: Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Yang Li, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen

Veröffentlicht 2026-05-12

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Yang Li, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen

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 einen sehr intelligenten Roboterassistenten (ein Large Language Model, oder LLM), der hervorragend Fragen wie „Ist dieses Matheproblem korrekt gelöst?" oder „Habe ich dieses Wort richtig geschrieben?" beantworten kann. Seit langem trainieren wir diese Roboter, indem wir bei einer richtigen Antwort „Gut gemacht!" sagen und bei einer falschen „Versuch es noch einmal". Das ist vergleichbar mit der Benotung eines Multiple-Choice-Tests, bei dem es nur eine richtige Antwort gibt.

Aber was ist, wenn es bei der Aufgabe nicht nur darum geht, die Antwort richtig, sondern die Antwort am besten zu bekommen?

Genau dieses Problem behandelt die Arbeit FORGE. Es ist so, als würde man den Roboter nicht nur bitten, einen Weg zum Lebensmittelgeschäft zu finden, sondern den kürzesten, schnellsten möglichen Weg, selbst wenn es Millionen anderer gültiger Wege gibt, die nur länger dauern.

Hier ist eine einfache Aufschlüsselung, wie sie es gemacht haben:

1. Das Problem: „Gut genug" versus „Das Beste"

Stellen Sie sich vor, Sie packen einen Koffer.

Der alte Weg (Binäre Belohnungen): Sie bitten den Roboter zu packen. Wenn alles in den Koffer passt, sagen Sie „Erfolg!". Wenn er überquillt, sagen Sie „Fehler". Der Roboter lernt, die Gegenstände nur so zu packen, dass sie hineinpassen, selbst wenn er die Hälfte des Koffers leer lässt oder schwere Gegenstände auf zerbrechliche legt.
Die FORGE-Methode (Qualitätsbewusste Belohnungen): Sie sagen dem Roboter: „Erfolg ist gut, aber wenn Sie mehr Sachen in denselben Raum packen oder sie so anordnen können, dass es leichter wird, erhalten Sie eine größere Belohnung." Der Roboter lernt, weiterhin zu versuchen, das Packen zu verbessern, bis es perfekt ist.

Die Arbeit argumentiert, dass aktuelle KI-Modelle hervorragend darin sind, „gültige" Lösungen zu finden (wie einen Weg, der funktioniert), aber schrecklich darin, „optimale" Lösungen zu finden (den absolut besten Weg). Das ist ein großes Problem für reale Herausforderungen wie Logistik, Planung und Netzwerkdesign, die als NP-schwere Probleme bekannt sind (Matheprobleme, die unglaublich schwer perfekt zu lösen sind).

2. Die Lösung: Die „Forge"-Fabrik

Die Autoren bauten eine Fabrik namens FORGE-ENGINE, um diese Roboter zu besseren Optimierern zu trainieren. Stellen Sie es sich als ein Fitnessstudio für das Gehirn der KI vor, aber anstatt Gewichte zu heben, löst es komplexe Rätsel.

Die Fabrik verfügt über drei Hauptmaschinen:

Der Generator: Diese Maschine erstellt Millionen von Übungsrätseln. Sie kann sie einfach (wie ein 5-Teile-Puzzle), mittel oder schwer (wie ein 1.000-Teile-Puzzle) gestalten.
Der Validator: Dies ist der strenge Schiedsrichter. Er prüft, ob die Lösung des Roboters tatsächlich den Regeln folgt (z. B. „Haben Sie jede Stadt genau einmal besucht?").
Der Heuristische Löser (Das Geheimrezept): Dies ist der wichtigste Teil. Es ist ein superschnelles, traditionelles Computerprogramm, das das Rätsel fast perfekt löst. Es fungiert als „Goldstandard" oder Trainer.
- Die Analogie: Stellen Sie sich vor, der Roboter ist ein Schüler, der einen Test schreibt. Der Validator prüft, ob die Antwort korrekt geschrieben ist. Der Heuristische Löser ist der Lehrer, der den Lösungsschlüssel hat. Wenn der Roboter 80 % der Punkte erhält, sagt der Lehrer nicht einfach „Falsch". Der Lehrer sagt: „Sie haben 80 %. Versuchen Sie, auf 90 % zu kommen." Dies gibt dem Roboter eine kontinuierliche Punktzahl anstelle eines einfachen „Bestanden/Nicht bestanden".

3. Die Trainingsmethode: „Den Berg hinaufklettern"

Man kann einen Roboter nicht sofort in ein 1.000-Teile-Puzzle werfen; er würde verwirrt sein und aufgeben. Daher verwendet die Arbeit eine Curriculum-Learning-Strategie:

Leichte Phase: Der Roboter löst kleine, einfache Rätsel, um die Regeln zu lernen.
Mittlere Phase: Die Rätsel werden größer. Der Roboter lernt, vorauszuplanen.
Schwere Phase: Der Roboter bewältigt massive, komplexe Rätsel.
Der Wiederholungs-Trick: Die Autoren stellten fest, dass der Roboter vergisst, wie man die leichten Dinge macht, wenn man sich nur vorwärts bewegt (Leicht → Schwer). Daher ließen sie den Roboter die leichten und mittleren Levels periodisch wiederholen. Dies hält seine Fähigkeiten scharf, während er die schwierigen Dinge lernt.

4. Die Ergebnisse: Ein intelligenteres Gehirn

Sie testeten ihren neuen Roboter (namens FORGE) an 10 verschiedenen Arten schwieriger Rätsel (wie die Planung des kürzesten Weges für einen Lieferwagen oder die Terminierung von Meetings ohne Konflikte).

Die Punktzahl: Der Roboter fand nicht nur eine Lösung; er fand großartige Lösungen. Er schlug das berühmte GPT-4o-Modell mit großer Deutlichkeit. Während GPT-4o etwa 62 % der Zeit gültige Lösungen fand, fand FORGE sie in 93 % der Fälle. Noch wichtiger: FORGEs Lösungen waren der „perfekten" Antwort viel näher.
Der Bonus-Effekt: Hier kommt der coolste Teil. Als sie den Roboter an diesen schwierigen Optimierungs-Rätseln trainierten, wurde er nicht nur besser in Rätseln. Er wurde auch in allem anderen besser.
- Er wurde besser in Mathe.
- Er wurde besser in Logik.
- Er wurde besser im Befolgen von Anweisungen.
- Die Analogie: Es ist wie das Trainieren eines Schachspielers zum Großmeister. Im Prozess werden sie nicht nur besser im Schach; sie werden besser in Strategie, Geduld und Planung im täglichen Leben. Die Arbeit legt nahe, dass das Lernen zu „optimieren" (die beste Lösung zu finden) der KI eine allgemeine Fähigkeit des tiefen Denkens und Verfeinerns ihrer Antworten beibringt, was ihr bei allen Arten von Aufgaben hilft.

Zusammenfassung

Die Arbeit stellt FORGE vor, eine neue Art, KI zu trainieren. Anstatt der KI nur beizubringen, die „richtige" Antwort zu geben, bringen sie ihr bei, die beste mögliche Antwort zu finden, indem sie ihr eine ständige Bewertung dafür geben, wie gut ihre Lösung ist. Dies verwandelt die KI in einen Meister-Optimierer, der nicht nur schwierige Mathe-Rätsel besser löst als aktuelle Top-Modelle, sondern auch intelligenter im allgemeinen Schlussfolgern, in der Logik und beim Befolgen von Anweisungen wird.

Technische Zusammenfassung: FORGE-ENGINE

Problemstellung

Während Large Language Models (LLMs) durch Reinforcement Learning mit verifizierbaren Belohnungen (RLVR) in Reasoning-Benchmarks (Mathematik, Programmierung, Logik) erhebliche Erfolge erzielt haben, leiden bestehende Evaluierungsparadigmen unter einer kritischen Einschränkung: Sie konzentrieren sich ausschließlich auf Korrektheit (Durchführbarkeit) statt auf Optimalität. In vielen realen Szenarien, wie etwa in der Logistik oder Ressourcenallokation, ist eine bloß „gültige" Lösung unzureichend; das Ziel besteht darin, die Lösung zu finden, die eine Zielfunktion maximiert oder minimiert. Aktuelle Benchmarks verlassen sich häufig auf binäre Belohnungen (bestanden/nicht bestanden), die das für die Führung von Modellen zu optimalen Lösungen notwendige dichte, kontinuierliche Feedback nicht liefern können. Darüber hinaus fehlt es bestehenden NP-schweren Benchmarks an Mechanismen zur Generierung von wahren optimalen Werten (Ground Truth), was die Berechnung fein abgestufter Belohnungen verhindert und das Training in ineffiziente binäre Feedback-Schleifen zurückwirft.

Methodik: FORGE-ENGINE

Die Autoren schlagen FORGE-ENGINE vor, ein umfassendes Framework, das entwickelt wurde, um LLMs bei NP-schweren Optimierungsproblemen mittels Qualitätsbewusstem RLVR zu trainieren und zu evaluieren. Das Framework besteht aus drei Kernkomponenten:

1. Pipeline zur Datenkonstruktion

Das Framework nutzt eine skalierbare, vierstufige Pipeline zur Generierung von Trainingsdaten über 10 verschiedene NP-schwere Aufgaben hinweg, die fünf Kategorien abdecken: Graph-Clustering, Ressourcenplanung, Graph-Partitionierung, Teilmengenauswahl und Pfadplanung.

Steuerbare Generatoren: Erzeugen unendliche Instanzen mit abgestuften Schwierigkeitsgraden (Einfach, Mittel, Schwer) unter Verwendung eines „Construction-by-Design"-Ansatzes, um die Existenz durchführbarer Lösungen zu garantieren.
Regelbasierte Verifizierer: Validieren automatisch die Einhaltung von Constraints und berechnen Zielfunktionswerte, wodurch absolute Korrektheit ohne menschliche Kennzeichnung sichergestellt wird.
Heuristische Löser: Eine kritische Innovation, bei der aufgaben spezifische heuristische Algorithmen (z. B. Multi-Start-Nächster-Nachbar mit 2-opt für das TSP) nahezu optimale Baselines für jede Instanz berechnen. Diese Baselines dienen als Ground Truth für die Belohnungsberechnung.
Curriculum-Kalibrierung: Die Schwierigkeitsgrade werden empirisch kalibriert, um Ziel-Erfolgsquoten zu erreichen (z. B. Einfach: 70–90 %, Schwer: 10–40 %), um progressives Lernen zu erleichtern.

2. FORGE-BENCH

Ein rigoroses Evaluierungs-Benchmark, das aus 1.000 hochkomplexen Instanzen besteht (100 pro Aufgabe) und so konzipiert ist, dass es während des Trainings nicht gesehen wird. Im Gegensatz zu früheren Arbeiten bewertet es Modelle unter Verwendung zweier komplementärer Metriken:

Erfolgsrate (SR): Der Prozentsatz der Instanzen, bei denen das Modell eine gültige Lösung generiert, die alle Constraints erfüllt.
Qualitätsverhältnis (QR): Eine kontinuierliche Metrik, die die Lösungsqualität relativ zur heuristischen Baseline misst (z. B. $QR = \text{Heuristik} / \text{Modell}$ für Minimierung). Dies unterscheidet zwischen bloß durchführbaren und nahezu optimalen Lösungen.

3. Qualitätsbewusstes RLVR-Framework

Die Trainingsstrategie ersetzt spärliche binäre Signale durch fein abgestufte, kontinuierliche Belohnungen, die von den heuristischen Baselines abgeleitet werden.

Belohnungsfunktion: Ein hierarchisches Belohnungssystem bewertet Ausgaben in drei Dimensionen:
1. Format-Belohnung ( $R_{format}$ ): Stellt strukturiertes Reasoning sicher (z. B. <thought>-Tags).
2. Durchführbarkeits-Belohnung ( $R_{feasibility}$ ): Bestraft Constraint-Verletzungen (z. B. -1,5) und übergibt den Optimalitäts-Score für gültige Lösungen.
3. Optimalitäts-Belohnung ( $R_{optimal}$ ): Ein kontinuierlicher Score, der auf dem Verhältnis des Zielfunktionswerts des Modells zur heuristischen Baseline basiert und dichtes Feedback für die Optimierung liefert.
Multi-Stufen-Curriculum-Replay: Um das „Cold-Start"-Problem und katastrophales Vergessen zu mildern, employs das Training eine zyklische Strategie (Einfach $\to$ Mittel $\to$ Schwer), die mehrfach durch die Schwierigkeitsgrade iteriert, grundlegende Fähigkeiten festigt und gleichzeitig komplexe Optimierung schrittweise angeht.

Hauptergebnisse

Experimente wurden an Qwen2.5-7B-Instruct-1M durchgeführt, trainiert an 15.000 Beispielen (insgesamt 15K über drei Stufen).

In-Domain-Leistung: Das resultierende Modell, FORGE, erreichte auf FORGE-BENCH eine Erfolgsrate von 93,1 % und ein Qualitätsverhältnis von 46,6 %. Dies übertrifft GPT-4o (62,1 % SR, 36,2 % QR) signifikant und übersteigt die Leistung des Basismodells (29,6 % SR, 14,6 % QR) erheblich.
Out-of-Domain (OOD) Generalisierung: Das Training auf FORGE-ENGINE übertrug sich auf diverse Reasoning-Aufgaben und erzielte Zuwächse in:
- Instruktionsbefolgung: +6,1 %
- Wissensbasiertes Reasoning: +4,1 %
- Mathematik: +2,2 %
- Logik: +1,2 %
Ablationsstudien:
- Belohnungsdesign: Qualitätsbewusste Belohnungen verbesserten die Lösungsqualität um 28,8 % gegenüber binären Belohnungen, verhinderten Reward-Hacking und führten das Modell zu echter Optimalität.
- Curriculum-Strategie: Multi-Stufen-Curriculum-Replay übertraf lineare Single-Pass-Strategien, durchbrach Leistungsgrenzen und verhinderte Stagnation.
- Aufagenvielfalt vs. Menge: Die Studie ergab, dass das Training auf einer diversen Menge von 10 Aufgaben eine bessere Generalisierung bewirkte als das Training auf weniger Aufgaben mit mehr Daten, was darauf hindeutet, dass die Exposition gegenüber varied Problembstrukturen ein Schlüsselfaktor für Reasoning-Fähigkeiten ist.
- RLVR vs. SFT: Während Supervised Fine-Tuning (SFT) auf optimalen Lösungen die In-Domain-Leistung verbesserte, litt es unter katastrophalem OOD-Verfall (-12,0 Punkte). Im Gegensatz dazu förderte RLVR robuste, übertragbare Strategien zur Constraint-Einhaltung.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass FORGE-ENGINE das erste umfassende Framework ist, das RLVR erfolgreich auf NP-schwere Optimierungsprobleme anwendet, indem es heuristische Löser integriert, um fein abgestufte Optimalitäts-Belohnungen bereitzustellen.

Die Autoren behaupten, dass diese Arbeit die Lücke zwischen Durchführbarkeit und Optimalität im LLM-Reasoning schließt. Indem das Framework über binäre Korrektheit hinausgeht, ermöglicht es Modellen, iterative Optimierungssuche zu betreiben. Entscheidend liefert die Arbeit empirische Belege dafür, dass Optimierungstraining eine übertragbare „Optimierungs-Mentalität" fördert – die Fähigkeit, Kandidaten zu generieren und sich selbst zu verfeinern –, was übergeordnete Reasoning-Fähigkeiten über die spezifischen Optimierungsaufgaben hinaus verbessert. Die Ergebnisse deuten darauf hin, dass für das Skalieren von RLVR Aufagenvielfalt und qualitätsbewusste Belohnungen kritischere Faktoren sind als reine Datenmenge.

Die Arbeit wird als fundamentaler Schritt für die Integration von LLMs mit optimierungsbasiertem Reasoning präsentiert und bietet eine skalierbare Infrastruktur sowie ein Benchmark für zukünftige Forschung im Bereich komplexes Reasoning.