🤖 AI

Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces

Dieses Paper führt OPT* ein, eine skalierbare Familie von Optimierungsaufgaben mit expandierenden Suchräumen, die das Training und die Evaluierung von LLMs auf schrittweiser, optimierungsähnlicher Argumentation sowohl durch solver-gestützte Online-Policy-Optimierung als auch durch suchbasierte Offline-Reinforcement-Learning ermöglicht.

Ursprüngliche Autoren: Nicolás Astorga, Nabeel Seedat, Mihaela van der Schaar

Veröffentlicht 2026-06-05

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Nicolás Astorga, Nabeel Seedat, Mihaela van der Schaar

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 bringen einem sehr intelligenten, aber etwas naiven Roboter-Koch bei, ein komplexes, mehrgängiges Menü zuzubereiten.

Das Problem: Die „Gut genug“-Falle
Im Moment sind diese KI-Chefs (Large Language Models) sehr gut darin, Rezepten zu folgen, bei denen es nur eine richtige Antwort gibt, wie etwa beim Lösen einer mathematischen Gleichung oder beim Schreiben eines Code-Schnipfels, der fehlerfrei kompiliert. Wenn sie das Endergebnis richtig erhalten, bekommen sie einen goldenen Stern.

Aber das echte Leben ist nicht so. Das echte Leben gleicht eher der Planung einer Lieferroute für 50 LKWs, der Zuweisung von 20 Mitarbeitern auf 20 verschiedene Schichten oder dem Beladen eines Umzugslastwagens. In diesen Szenarien gibt es nicht nur eine einzige „richtige“ Antwort (alles funktioniert, jeder hat einen Job), sondern es gibt tausende Wege, die „valide“ sind (nichts geht kaputt, jeder bekommt eine Aufgabe), aber nur wenige Wege, die großartig sind (kürzeste Distanz, höchste Zufriedenheit, geringster Platzverbrauch).

Das Paper argumentt, dass die heutige KI hier Schwierigkeiten hat. Sie findet vielleicht einen validen Plan, bleibt aber oft an einem „gut genug“-Plan hängen und übersieht den „perfekten“ Plan, weil sie nicht weiß, wie sie vorausblicken oder schlechte Ideen frühzeitig aussortieren soll.

Die Lösung: OPT⋆ (Der unendliche Spielplatz)
Die Autoren haben einen neuen Trainingsplatz namens OPT⋆ erschaffen. Betrachten Sie dies als einen Level-Generator für Videospiele, der das Spiel immer schwieriger machen kann, ohne dass ein menschlicher Designer neue Level zeichnen muss.

Das Spiel: Sie verwenden klassische Optimierungsrätsel (wie das Problem des Handlungsreisenden, bei dem man Städte auf dem kürzesten Weg besucht, oder das Packen von Gegenständen in einen Rucksack).
Das Spickzettel-System: Das Spiel verfügt über zwei eingebaute Werkzeuge:
1. Der Regelprüfer: Sagt Ihnen sofort, ob ein Zug illegal ist (z. B. „Du kannst diese schwere Kiste nicht auf die zerbrechliche stellen“).
2. Der Punktezähler: Sagt Ihnen sofort, wie gut das Endergebnis ist (z. B. „Deine Route hat 10 Minuten gespart“).
Der Schwierigkeitsregler: Sie können einen Regler (genannt $\alpha$ ) drehen, um mehr Städte, mehr Arbeiter oder mehr Gegenstände hinzuzufügen. Dies lässt die Anzahl der möglichen Pfade exponentiell explodieren, aber die Regeln und die Bewertung bleiben einfach und automatisiert. Keine Menschen nötig, um die Hausaufgaben zu bewerten.

Wie sie die KI trainiert haben: Zwei Methoden

Das Paper testet zwei Wege, um der KI beizubringen, diese massiven, expandierenden Labyrinthe zu durchqueren:

1. Die „Offline“-Methode: Die Schatzsuche
Stellen Sie sich vor, die KI wird in eine dunkle Höhle (den Suchraum) mit einer Taschenlampe gesetzt. Sie hat keine Karte.

Die Strategie: Die KI wandert umher und probiert verschiedene Pfade aus. Wenn sie einen Pfad findet, der zu einem Schatz (einem hohen Score) führt, merkt sie sich diesen Pfad.
Der Trick: Das Paper führt zwei „smarte Filter“ ein, um die Jagd effizienter zu gestalten:
- Der Türsteher (Feasibility Check): Wenn die KI versucht, durch eine Wand zu laufen (ein illegaler Zug), stoppt der Türsteher sie sofort. Sie verschwendet keine Zeit damit, diese Sackgasse weiter zu erkunden.
- Der Zwilling-Detektor (Deduplikation): Manchmal sagt die KI „Gehe nach Norden“ auf Englisch, „Kopf hoch“ auf Französisch und „Bewege nach oben“ auf Spanisch. Das sind alles dieselben Bewegungen. Der Zwilling-Detektor erkennt, dass es sich um dieselbe Aktion handelt, und behält nur eine davon, um zu verhindern, dass die KI Energie für dieselbe Idee verschwendet.
Das Ergebnis: Die KI lernt, Sackgassen zu ignorieren und doppelte Ideen zu vermeiden, wodurch sie den Schatz viel schneller findet.

2. Die „Online“-Methode: Der Coach mit dem Kristallball
In diesem Szenario hat die KI einen Coach, der die Zukunft sehen kann (einen „Solver“).

Die Strategie: Die KI macht einen Zug. Der Coach betrachtet diesen Zug und berechnet sofort: „Wenn du diesen Schritt machst, ist das Beste, was du von hier aus erreichen kannst, ein Score von 90.“
Die Belohnung: Anstatt bis zum Ende des Spiels auf einen Score zu warten, erhält die KI sofortiges Feedback zu jedem einzelnen Schritt. Wenn ein Schritt zu einem niedrigen Potenzial führt, sagt der Coach: „Schlechter Zug!“ Wenn er zu einem hohen Potenzial führt, sagt der Coach: „Guter Zug!“
Das Ergebnis: Die KI lernt, bessere Entscheidungen Schritt für Schritt zu treffen, anstatt nur auf ein gutes Ende zu hoffen.

Was sie herausgefunden haben

Der „Branching“-Engpass: Wenn das Spiel schwieriger wird (mehr Städte/Gegenstände), wächst die Anzahl der Pfade so schnell, dass eine normale Suche wie der Versuch ist, eine Nadel im Heuhaufen in der Größe einer Galaxie zu finden. Das Paper beweist mathematisch, dass die KI erfolgreich sein muss, indem sie besser darin wird, schlechte Pfade zu filtern, und nicht einfach nur härter arbeitet.
Die Filter funktionieren: Der „Türsteher“ und der „Zwilling-Detektor“ (die Offline-Methoden) machten die Suche signifikant effizienter. Die KI fand qualitativ hochwertigere Lösungen viel schneller als ohne sie.
Der Coach ist am besten (aber teuer): Die „Online“-Methode mit dem Coach (Solver) produzierte die intelligentere KI, erfordert aber einen leistungsstarken Computer, um als Coach zu fungieren. Die „Offline“-Methode ist eine großartige Alternative, wenn man keinen Supercomputer zur Hand hat.
Generalisierung: Als sie die KI auf diese Optimierungsrätsel trainierten, verbesserte sie sich tatsächlich auch bei anderen räumlichen Aufgaben (wie dem Rotieren von Formen oder dem Abdecken eines Gitters) und verbesserte sogar ihr mathematisches Denken. Es scheint, als hätte die KI eine allgemeine Fähigkeit zum „Planen“ gelernt, und nicht nur das Lösen eines spezifischen Rätsels.

Zusammenfassend
Das Paper stellt einen Weg vor, um KI durch den Einsatz von Spielen, die sich automatisch unendlich schwerer gestalten lassen, beim komplexen Planen besser zu machen. Indem man der KI beibringt, illegale Züge schnell zu erkennen und die Vermeidung desselben Ideen zu vermeiden, kann man ihr helfen, die besten Lösungen in massiven, komplizierten Problemen zu finden – selbst ohne einen menschlichen Lehrer, der über ihre Schulter blickt.

Technisches Resümee: Schrittweise Optimierungsähnliche Argumentation in LLMs über expandierende Suchräume hinweg

1. Problemstellung

Obwohl Large Language Models (LLMs) durch verifizierbares Belohnungstraining Erfolge in mathematischer und kodierender Argumentation erzielt haben, bleiben sie bei beschränkten schrittweisen Entscheidungsaufgaben fragil. In diesen Szenarien kann ein lokal plausibler Schritt dazu führen, dass der verbleibende Teil des Problems unlösbar wird oder eine qualitativ minderwertige Vervollständigung erzwingt. Im Gegensatz zu Standard-Settings zur Korrektheit einer Antwort, in denen eine einzige richtige Antwort existiert, beinhalten viele reale Aufgaben (z. B. Ressourcenallokation, Zeitplanung, Routing) viele machbare Lösungen, wobei das Ziel darin besteht, eine hochwertige Lösung unter Nebenbedingungen zu konstruieren.

Aktuelle Skalierungsmethoden stehen vor zwei Hindernissen:

Die Generierung diverser Aufgaben, die zuverlässig nicht-triviales Denken erfordern, ist schwierig.
Die Supervision für Zwischenschritte ist kostspielig, da man identifizieren muss, welche Teilaktionen zu optimalen Ergebnissen führen.

Die Arbeit adressiert die Herausforderung, LLMs darauf zu trainieren, optimierungsähnliche Argumentation über expandierende Suchräume durchzuführen, wobei die Schwierigkeit durch einen Komplexitätsparameter $\alpha$ gesteuert wird, ohne dass neue menschliche Annotationen erforderlich sind.

2. Methodik: Das OPT⋆ Framework

Die Autoren führen OPT⋆ (OPTimization-based Scalable Tasks for Auto-verifiable Reasoning) ein, eine Familie von Aufgaben, die darauf ausgelegt sind, schrittweise Argumentation zu trainieren und zu evaluieren.

2.1 Aufgabendefinition

Eine OPT⋆-Aufgabeninstanz $t$ ist ein beschränkter Entscheidungsprozess, definiert durch:

Skalierbare Generierung: Instanzen werden durch ein Verfahren $Build_\alpha(\cdot)$ generiert, das durch einen Komplexitätsparameter $\alpha$ gesteuert wird (z. B. Anzahl der Städte im TSP, Anzahl der Artikel im Knapsack-Problem). Eine Erhöhung von $\alpha$ erweitert den Suchraum $M(t)$ , erhöht jedoch nicht den Annotationsaufwand.
Günstige Verifizierung: Jede Aufgabe stellt zwei kostengünstige Routinen bereit:
- Machbarkeitsprüfer ($chkt$): Validiert Teilaktionen (z. B. Sicherstellung, dass Lastgrenzen nicht überschritten werden).
- Ergebnis-Evaluator ($evalt$): Bewertet vollständige terminale Lösungen (z. B. Gesamttourlänge).
Auto-Verifizierbarkeit: Sowohl $chkt$ als auch $evalt$ sind in Polynomialzeit berechenbar, selbst wenn das Finden der optimalen Lösung schwer ist.

2.2 Trainingsregime

Die Arbeit schlägt zwei komplementäre Trainingsansätze vor, basierend auf der Verfügbarkeit von Solvern:

A. Solver-gestützte Online-Policy-Optimierung (Online RL)

Wenn ein schneller Solver verfügbar ist, um den besten Vervollständigungswert aus einem Teilzustand zu berechnen:

Mechanismus: Der Solver funget als Value-Oracle. Für einen gegebenen Zustand werden Kandidaten-Schritte gesampelt und jeder wird durch den besten erreichbaren terminalen Wert unter einem festen Solver-Budget bewertet.
Reward Shaping: Die Policy wird unter Verwendung rangbasierter Belohnungen aktualisiert (z. B. GRPO, GSPO, PPO), wobei Aktionen, die zu Lösungen mit höherem Wert führen, höhere Ränge erhalten.
Ziel: Verstärkung von Schritten, die zu besseren Endergebnissen führen, wodurch Solver-Heuristiken effektiv in die Policy destilliert werden.

B. Suchbasierte Offline-RL

Wenn Solver nicht verfügbar oder für Teilzustände zu teuer sind:

Mechanismus: Das Modell generiert Kandidaten-Trajektorien. Ein Suchalgorithmus (z. B. MCTS, Beam Search) exploriert den Raum und nutzt $chkt$, um ungültige Pfade zu beschneiden, sowie $evalt$, um terminale Knoten zu bewerten.
Wichtige Suchkomponenten:
1. Machbarkeits-Pruning: Verwerfen von Kindern, bei denen $chkt(s, a) = 0$ gilt.
2. Duplikat-Zusammenführung: Gruppierung distinkter Textausgaben, die auf dieselbe strukturierte Aktion abbilden, um die Suchressourcen nicht zu verschwenden.
Training: Das Modell wird auf den durch den Suchprozess entdeckten besten Trajektorien feinjustiert (SFT), wodurch es lernt, hochwertige Argumentationspfade nachzuahmen.

2.3 Theoretische Grundlage

Die Arbeit etabliert eine informationstheoretische Schranke (Theorem A.3), die den Erfolg in großen Suchräumen mit der pro Einheit Suchbudget extrahierten Information in Beziehung setzt. Wenn die Komplexität $\alpha$ steigt, wächst die Anzahl der effektiven Optima. Um eine feste Erfolgswahrscheinlichkeit aufrechtzuerhalten, muss ein Reasoner entweder das Suchbudget erhöhen oder mehr Information pro Schritt extrahieren. Der effektive Verzweigungsfaktor ( $b_{eff}$ ) wird als Metrik zur Messung der Sucheffizienz eingeführt; ein niedrigeres $b_{eff}$ zeigt an, dass ein Suchbudget mehr Masse auf hochwertige terminale Zustände legt.

3. Kernbeiträge

Konzeptionell (OPT⋆): Formalisierung einer skalierbaren, auto-verifizierbaren Aufgabenfamilie für optimierungsähnliche Argumentation. Dieses Framework entkoppelt die Argumentationsschwierigkeit vom Annotationsaufwand, indem es Komplexitätsparameter nutzt, um Suchräume zu erweitern, während die Verifizierung kostengünstig bleibt.
Algorithmisch:
- Entwicklung von Plug-and-Play-Suchkomponenten (Machheitsprüfung und Duplikat-Zusammenführung), die die Sucheffizienz in Offline-Umgebungen signifikant verbessern.
- Einführung von $\nu$ PO (Solver-Guided Policy Optimization), einer Methode, die Solver nutzt, um schrittweise Belohnungen für Online-RL bereitzustellen, was das Training auf Teilzuständen ermöglicht.
Empirisch:
- Nachweis, dass das Training auf OPT⋆ die schrittweise Argumentation in Optimierungsaufgaben verbessert.
- Beleg dafür, dass Curriculum Learning (Training von leichtem $\alpha_1$ zu schwerem $\alpha_4$ ) eine bessere Generalisierung liefert als das Training auf schweren Aufgaben allein.
- Aufzeigen, dass das Optimierungstraining auf räumliche Argumentationsfähigkeiten (z. B. Rotation, Reflexion, Überdeckung) transferiert und die Leistung auf mathematischen Benchmarks (AMC, AIME) verbessert.

4. Experimentelle Ergebnisse

Die Autoren evaluierten das Framework auf Aufgaben wie Role Assignment, MaxSAT, Single-machine Scheduling, TSP, 2D Packing und Quadratic Assignment Problem (QAP).

Sucheffizienz (Offline RL):
- Die Aktivierung von Machbarkeits-Pruning und Duplikat-Zusammenführung reduzierte den effektiven Verzweigungsfaktor ( $b_{eff}$ ) erheblich. Beispielsweise erreichte $\nu$ MCTS bei QAP ein $b_{eff} \approx 24$ mit diesen Komponenten, verglichen mit einem $b_{eff} \approx 728$ für eine Solver-Referenz-Baseline, die keine LLM-Vorschläge nutzt.
- Diese Komponenten waren die primären Treiber der Sucheffizienz und steigerten pass@16 von ~13% auf ~85% in QAP.
Modellverbesserung:
- Modelle, die auf OPT⋆-Aufgaben trainiert wurden (Role Assignment, MaxSAT), zeigten substantielle Verbesserungen gegenüber Basismodellen. Beispielsweise verbesserte sich Qwen2.5-3B bei Role Assignment pass@1 von 32,5% auf 44,5% (Level 1) und von 17,8% auf 31,1% (Level 4).
- Solver-gestütztes Online-RL übertraf konsistent Domain-Transfer-Baselines (z. B. transferierte das Training auf Math- oder Code-Aufgaben nicht gut auf Optimierungsaufgaben).
Generalisierung:
- Das Training auf Optimierungsaufgaben verbesserte die Leistung bei Out-of-Distribution (OOD) räumlichen QA-Aufgaben (z. B. Rotation, Symmetrie, Überlappung) und Standard-Mathematik-Benchmarks (AMC'23, AIME'24/25).
- Curriculum-Effekte: Ein gemischtes Curriculum-Training ( $\alpha_1 \to \alpha_4$ ) übertraf sowohl "Easy-only"- als auch "Hard-only"-Trainingsstrategien, insbesondere bei schwierigeren Levels und OOD-Aufgaben.

5. Bedeutung und Ansprüche

Die Arbeit behauptet, dass OPT⋆ ein fundiertes Testfeld für die Untersuchung der schrittweisen Argumentation unter Nebenbedingungen bietet und die Lücke zwischen verifizierbarem Belohnungstraining (effektiv für Mathe/Code) und realen Optimierungsaufgaben schließt.

Wissenschaftlicher Wert: Es bietet eine kontrollierte Umgebung, um zu untersuchen, wie expandierende Suchräume die Argumentationsfähigkeiten beeinflussen, gestützt durch eine informationstheoretische Analyse, die zeigt, dass Erfolg erfordert, mehr Information pro Budgeteinheit zu extrahieren, wenn die Komplexität steigt.
Praktischer Wert: Die vorgeschlagenen Methoden (Plug-and-Play-Suchkomponenten und Solver-gestütztes RL) bieten skalierbare Wege, um Modelle auf komplexen Workflows (Zeitplanung, Routing) zu trainieren, bei denen exakte Solver möglicherweise nicht verfügbar oder zu langsam für wiederholte Aufrufe sind.
Begrenzter Umfang: Die Autoren merken an, dass Solver zwar spezifische Instanzen verifizieren oder lösen können, das Ziel jedoch die Destillation wiederverwendbarer Heuristiken in allgemeine Modelle ist. Die Arbeit konzentriert sich auf synthetische Optimierungsaufgaben, die von traditionellen Problemen inspiriert sind, und räumt ein, dass zukünftige Arbeiten die Aufgabengenerierung mittels LLM-Priors skalieren könnten, um noch diversere und komplexere Szenarien zu schaffen.

Zusammenfassend zeigt die Arbeit, dass LLMs durch die Nutzung von auto-verifizierbaren Optimierungsaufgaben und komplementären Offline-/Online-RL-Strategien lernen können, durch expandierende Suchräume effektiver zu navigieren, was sowohl ihre Optimierungsleistung als auch ihre zugrunde liegenden räumlichen und logischen Argumentationsfähigkeiten verbessert.