🤖 machine learning

Learning to Reason with Curriculum II: Compositional Generalization

Diese Arbeit zeigt, dass ein Autokurikulum-Ansatz, der lange sequentielle Berechnungsaufgaben rekursiv in kürzere Teilprobleme zerlegt, eine dramatisch bessere statistische Komplexität als direkte Methoden erreicht, indem er das Lernen aus subpolynomialen Supervisions-Token ermöglicht und die Anforderungen an die Abdeckung des Referenzmodells von der vollen Sequenzlänge auf wesentlich kürzere Blocklängen entspannt.

Ursprüngliche Autoren: Nived Rajaraman, Audrey Huang, Miroslav Dudik, Robert Schapire, Dylan Foster, Akshay Krishnamurthy

Veröffentlicht 2026-06-29

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Nived Rajaraman, Audrey Huang, Miroslav Dudik, Robert Schapire, Dylan Foster, Akshay Krishnamurthy

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

Die große Idee: Einen Turm bauen vs. einen Felsbrocken heben

Stellen Sie sich vor, Sie versuchen einem Roboter beizubringen, ein sehr langes, komplexes Rätsel zu lösen. Das Rätsel hat 1.000 Schritte.

Der alte Weg (Direktes Lernen):
Sie zeigen dem Roboter das gesamte 1.000-Schritte-Rätsel und sagen: „Finde die Lösung heraus.“ Um dies zu lernen, muss der Roboter versuchen, jeden einzelnen Schritt auf einmal auswendig zu lernen. Es ist, als würde man versuchen, einen riesigen Felsbrocken in einem einzigen Schwung zu heben. Es ist unglaublich schwer, erfordert enorme Anstrengung, und der Robot scheitert oft, weil die Aufgabe zu groß ist, um sie alle gleichzeitig in seinem „Verstand“ zu halten.

Der neue Weg (Kompositioneller Lehrplan):
Dieses Paper schlägt eine intelligentere Strategie vor: Zerlegen Sie es.
Anstatt dem Roboter das gesamte 1.000-Schritte-Rätsel zu zeigen, bringen Sie ihm zuerst bei, ein 10-Schritte-Rätsel zu lösen. Sobald er das beherrscht, bringen Sie ihm bei, ein weiteres 10-Schritte-Rätsel zu lösen. Dann bringen Sie dem Roboter bei, diese 10-Schritte-Lösungen aneinanderzureihen (chaining), um ein 100-Schritte-Rätsel zu lösen. Schließlich reiht er diese wieder aneinander, um ein 1.000-Schritte-Rätsel zu lösen.

Das Paper beweist mathematisch, dass dieser „Zerlegen-und-Wieder-Zusammenbauen“-Ansatz exponentiell effizienter ist, als zu versuchen, das Ganze auf einmal zu lernen.

Die Kernkonzepte

1. Der „Semiautomaton“ (Das Rätsel)

Die Autoren verwenden ein mathematisches Modell namens Semiautomaton, um diese Rätsel darzustellen.

Analogie: Denken Sie an einen Zustandsautomaten wie an einen Videospiel-Charakter, der sich durch Level bewegt.
- Zustand (State): Wo sich der Charakter gerade befindet (z. B. „Level 1, Raum A“).
- Eingabe (Input): Der Befehl, den Sie geben (z. B. „Springen“).
- Übergang (Transition): Die Regel, die den Charakter an den nächsten Ort bewegt.
Das Ziel: Vorhersagen, wo der Charakter nach 1.000 Bewegungen landet.
Warum das wichtig ist: Dieses Modell erfasst Dinge wie das Rechnen (Addieren von Zahlen nacheinander), das Erkennen von Mustern (wie die Überprüfung, ob ein Satz grammatikalisch korrekt ist) oder das Verfolgen eines Zustands in einem Computerprogramm.

2. Die zwei Szenarien

Das Paper testet diese „Zerlegen“-Strategie auf zwei verschiedene Arten, die zwei gängige Wege repräsentieren, wie KI heute lernt.

Szenario A: Der interaktive Tutor (iSFT)

Das Setup: Sie haben einen „Tutor“ (ein Orakel), der die richtige Antwort für jeden Schritt des Rätsels kennt. Sie können den Tutor fragen: „Was ist der Zustand nach Schritt 50?“ oder „Was ist der Zustand nach Schritt 500?“.
Das Problem: Wenn Sie den Tutor nach der Antwort für jeden Schritt eines 1.000-Schritte-Rätsels fragen, um den Roboter zu trainieren, dauert das 1.000 Fragen pro Rätsel. Das ist zu teuer.
Die Lösung: Der Lehrplan des Roboters ist selbstgeneriert. Er fragt den Tutor nur an bestimmten „Checkpoints“ (z. B. alle 10 Schritte) nach Antworten. Er lernt, die 10-Schritte-Blöcke zu lösen, und kombiniert diese dann.
Das Ergebnis: Anstatt 1.000 Fragen zu benötigen, benötigt der Roboter nur eine winzige, sub-polynomiale Anzahl an Fragen (etwa im Zusammenhang mit der Quadratwurzel des Logarithmus der Länge). Es ist, als müsste man nur ein paar Schlüsselfragen stellen, um ein riesiges Geheimnis zu lösen, anstatt jeden Zeugen zu verhören.

Szenario B: Der schwache Coach und der Schiedsrichter (RLVR)

Das Setup: Sie haben einen „Coach“ (ein vortrainiertes Modell), der gut darin ist, kurze Rätsel (z. B. 10 Schritte) zu lösen, aber schlecht bei langen Rätseln (z. B. 1.000 Schritte). Sie haben auch einen „Referee“ (einen Verifizierer), der nur „Richtig“ oder „Falsch“ für die Endantwort sagen kann, aber nicht erklären kann, warum etwas falsch war.
Das Problem: Wenn Sie versuchen, den Coach direkt auf das 1.000-Schritte-Rätsel zu trainieren, wird er fast nie die richtige Antwort finden, sodass der Referee niemals positives Feedback gibt. Der Lernprozess gerät ins Stocken.
Die Lösung: Der Lehrplan zwingt den Coach, die 10-Schritte-Blöcke zu üben. Der Referee prüft, ob der Coach den 10-Schritte-Block richtig löst. Sobald der Coach die Blöcke beherrscht, kombiniert das System diese, um das 1.000-Schritte-Rätsel zu lösen.
Das Ergebnis: Das System kann das lange Rätsel lernen, selbst wenn der Coach nur bei kurzen Aufgaben gut ist. Es „erweitert“ die Fähigkeit des Coaches von kurzen Blöcken auf die volle Länge, ohne dass der Coach zu Beginn perfekt sein muss.

Das Geheimrezept: „Inverted Sampling“

Woher weiß der Roboter, welche 10-Schritte-Blöcke er üben soll? Wenn er einfach zufällige Blöcke wählt, übt er vielleicht nur die leichten Aufgaben.

Das Paper führt einen cleveren Trick namens Inverted Sampling ein.

Die Analogie: Stellen Sie sich vor, Sie sind ein Lehrer, der einen Stapel von 100 Prüfungen korrigiert.
- Normales Sampling (Rejection Sampling): Sie wählen eine Prüfung zufällig aus. Wenn der Schüler sie richtig gelöst hat, werfen Sie sie weg. Wenn er sie falsch gelöst hat, behalten Sie sie zum Lernen. Aber wenn er sie richtig gelöst hat, haben Sie Ihre Zeit verschwendet.
- Inverted Sampling: Sie schauen sich alle 100 Prüfungen auf einmal an. Sie markieren jede einzelne, die der Schüler falsch gelöst hat. Dann wählen Sie eine der falschen aus, um sie zu studieren.
Warum es funktioniert: Dies stellt sicher, dass der Roboter seine Energie auf die spezifischen Teile des Rätsels konzentriert, bei denen er aktuell scheitert, anstatt Zeit mit Teilen zu verschwenden, die er bereits versteht. Das macht den Lernprozess unglaublich effizient.

Die wichtigste Erkenntnis

Das Paper beweist, dass Komposition (das Kombinieren kleiner Lösungen) und Curriculum (das Lernen in der Reihenfolge der Schwierigkeit) nicht nur „nette Ideen“ sind, sondern mathematische Notwendigkeiten, um schwierige Probleme effizient zu lösen.

Ohne Curriculum: Das Lernen einer Aufgabe der Länge $T$ erfordert einen Aufwand, der proportional zu $T$ ist (linear). Es wird immer schwieriger, je länger die Aufgabe wird.
Mit Curriculum: Das Lernen einer Aufgabe der Länge $T$ erfordert einen Aufwand, der viel langsamer wächst (sub-polynomial). Sie können ein Rätsel lösen, das 1.000 Mal länger ist, mit nur einem winzigen Stück mehr Aufwand als bei einem 10 Mal längeren Rätsel.

Kurz gesagt: Versuchen Sie nicht, den Elefanten in einem Bissen zu schlucken. Essen Sie ihn Bissen für Bissen, und Sie werden ihn mit überraschend wenig Aufwand bewältigen.

Technisches Resümee: Lernen durch Reasoning mit Curriculum II: Kompositionale Generalisierung

1. Problemstellung

Die vorliegende Arbeit untersucht die theoretischen Grundlagen der kompositionalen Generalisierung – die Fähigkeit, komplexe Probleme durch die Kombination von Lösungen für einfachere Teilprobleme zu lösen – einen Mechanismus, der zentral für das Chain-of-Thought (CoT)-Reasoning in der künstlichen Intelligenz ist. Die Kernfrage lautet: Wann und warum liefert die Zerlegung eines Problems in Teile eine effizientere Lernleistung als das direkte Lösen des Problems?

Um dies zu beantworten, formalisieren die Autoren das Problem mittels Semiautomaten-Simulation. Ein Semiautomat wird durch eine unbekannte, Markovsche, stationäre Übergangsfunktion $\pi^*: S \times \Sigma \to S$ definiert. Gegeben sei ein Anfangszustand $s_0$ und ein Eingabewort $w_{1:T}$ , wobei das Ziel darin besteht, den Endzustand $s_T$ nach $T$ Schritten vorherzusagen. Die Zwischenzustände $s_{1:T}$ bilden eine Chain-of-Thought. Dieses Modell erfasst Zustandsverfolgung (State Tracking), die Erkennung regulärer Sprachen und modulare Arithmetik.

Die Arbeit untersucht zwei spezifische Lernsettings:

Interaktive Chain-of-Thought-Supervision (iSFT): Der Lernende hat Zugriff auf einen Orakel-Dienst, der den Zustand zu jedem beliebigen Zeitschritt $t$ einer Berechnung für Kosten von einer Einheit zurückgeben kann. Das Ziel ist es, die Anzahl der Orakel-Abfragen (Abfragekomplexität) und der Trainingsinstanzen (Stichprobenkomplexität) zu minimieren, die erforderlich sind, um ein Modell mit geringem Fehler zu lernen.
Reinforcement Learning mit verifizierbaren Belohnungen (RLVR): Der Lernende hat Zugriff auf ein vortrainiertes „schwaches“ Referenzmodell $\pi_{ref}$ , das kurze Instanzen der Länge $B \ll T$ mit einer konstanten Wahrscheinlichkeit lösen kann, sowie auf einen Ergebnis-Verifier, der die Korrektheit einer Vorhersage des Endzustands prüft. Das Ziel ist es, das Referenzmodell zu verbessern, um Instanzen der Länge $T$ effizient zu lösen, und damit den exponentiellen Abfall der Erfolgswahrscheinlichkeit zu überwinden, der auftritt, wenn ein schwaches Modell über lange Horizonte hinweg ausgeführt wird.

2. Methodik

Die Autoren schlagen Autocurriculum-basierte Ansätze vor, die lange Sequenzen rekursiv in kürzere Teilprobleme zerlegen, diese lösen und die Lösungen anschließend komponieren. Dieser Ansatz baut auf Teil I der Serie auf und nutzt ein Template aus Komposition und Boosting.

Kernkomponenten des Algorithmus

Komposition: Ein Modell, das darauf trainiert wurde, Instanzen der Länge $\tau$ zu lösen, kann $\ell$ mal komponiert werden (wobei $T = \ell\tau$ ), um Instanzen der Länge $T$ zu lösen. Da sich Fehler unter Komposition jedoch akkumulieren, müssen die kurzreichweitigen Modelle mit hoher Genauigkeit trainiert werden.
Boosting: Um die notwendige hohe Genauigkeit bei kurzen Teilproblemen zu erreichen, setzen die Autoren eine multiskalige Boosting-Strategie ein. Dies beinhaltet das Training eines Ensembles schwacher Lerner auf umgewichteten Verteilungen, die sich auf „schwere“ Instanzen (wo das aktuelle Ensemble scheitert) konzentrieren, und deren Aggregation (z. B. via Pluralitätswahl).
Selbstgeneriertes Curriculum: Anstatt eines festen Zeitplans wählt der Lernende adaptiv aus, für welche Teilprobleme er trainiert, basierend auf den Fehlern der Modelle, die auf feineren Skalen trainiert wurden.

Zentrale technische Innovationen

Invertiertes Sampling (Inverted Sampling): Ein zentraler technischer Beitrag ist eine neue Sampling-Technik, um den durch Boosting inhärenten Distribution Shift zu handhaben. Standardmäßiges Rejection Sampling aus umgewichteten Mischungen von Marginalen ist ineffizient (erfordert im Worst Case $\Omega(\ell)$ Samples). Die Autoren führen Invertiertes Sampling ein, welches zuerst das Rejection Sampling unabhängig auf alle $\ell$ Teilinstanzen innerhalb einer langen Sequenz anwendet und dann eine der akzeptierten Instanzen gleichmäßig auswählt. Dies erreicht eine Akzeptanzwahrscheinlichkeit, die proportional zur Anzahl der Teilinstanzen ist, wodurch die Stichprobenkomplexität signifikant reduziert wird, während ausreichende Approximationsgarantien für den Lernalgorithmus gewahrt bleiben.
Multiskalige Rekursion: Der Algorithmus (AutoLearn) wendet das Boosting- + Kompositions-Template rekursiv an. Er zerlegt Instanzen der Länge $T$ in Teilprobleme der Länge $\tau$ , die wiederum bis zur Länge 1 (Next-Token-Prediction) zerlegt werden. Dies schafft eine Hierarchie, in der Modelle, die kürzere, leichtere Probleme lösen, komponiert werden, um schwierigere Probleme zu lösen.
Guess-and-Check für RLVR: Im RLVR-Setting, in dem Zwischenzustands-Labels nicht direkt verfügbar sind, simulieren die Autoren das interaktive Orakel mithilfe des schwachen Referenzmodells und des Verifiers. Durch das Generieren von Rollouts für jeden Block und die Verifizierung des Endzustands des Blocks können sie die Zwischenzustände effektiv „labeln“, um das Curriculum aufzubauen.

3. Zentrale Beiträge und Ergebnisse

Setting I: iSFT (Interaktive Supervision)

Die Arbeit präsentiert AutoLearn, einen Algorithmus, der Semiautomaten mit subpolynomialer Abfrage- und Stichprobenkomplexität in der Sequenzlänge $T$ lernt.

Ergebnis: Die Abfrage- und Stichprobenkomplexität ist durch $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$ nach oben beschränkt.
Vergleich: Dies durchbricht die $\Omega(T)$ $Ω (T)$ -Barriere, die bei direkten Simulationsmethoden inhärent ist.
- Full CoT Supervision: Erfordert $\Omega(T)$ Abfragen pro Instanz, um jeden Zustand zu labeln.
- End-to-End Feedback: Erfordert $\Omega(T)$ Stichprobenkomplexität aufgrund der Unfähigkeit, ohne Zwischengrundierung von Endzuständen zu generalisieren.
Mechanismus: Durch die adaptive Auswahl von Teilproblemen und die Verwendung von invertiertem Sampling zur Handhabung des Distribution Shift erreicht AutoLearn eine Komplexität, die subpolynomial in $T$ ist, spezifisch $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$ .

Setting II: RLVR (Verifizierbare Belohnungen)

Die Arbeit präsentiert AutoLearn.RL, welches ein schwaches Referenzmodell $\pi_{ref}$ von der Kompetenz auf Blockebene ( $B$ ) zur vollen Kompetenz der Länge $T$ verbessert.

Ergebnis: Der Algorithmus erreicht eine hohe Genauigkeit auf Instanzen der Länge $T$ mit Kosten, die durch die Coverage des Referenzmodells auf der kürzeren Blocklänge $B$ bestimmt werden, statt durch die volle Länge $T$ .
Expansion der Coverage: Standardmäßige RLVR-Methoden erfordern eine nicht-triviale Coverage des Referenzmodells bei Länge $T$ , was exponentiell unwahrscheinlich ist, wenn es nur bei Länge $B$ Coverage besitzt (d. h. $C^{(T)}_{seq} \approx (C^{(B)}_{seq})^{T/B}$ ). AutoLearn.RL reduziert diese Anforderung auf die Coverage bei Länge $B$ .
Komplexität:
- Stichprobenkomplexität: $\tilde{\mathcal{O}}(d/\varepsilon)$ .
- Abfragekomplexität: $\tilde{\mathcal{O}}(d/\varepsilon) + \tilde{\mathcal{O}}(\frac{T}{B} \cdot d C^{(B)}_{ans} + d C^{(B)}_{seq})$ .
- Rechenaufwand: $\tilde{\mathcal{O}}(dT/\varepsilon) + \tilde{\mathcal{O}}(dT C^{(B)}_{ans} + dB C^{(B)}_{seq})$ .
Bedeutung: Die „Burn-in“-Kosten hängen von der Coverage auf der kurzen Skala $B$ ab, was es ermöglicht, dass sich die effektive Coverage bei Länge $T$ von exponentiell klein zu konstant ausdehnt.

4. Bedeutung und Behauptungen

Die Arbeit behauptet, dass Komposition kombiniert mit einem selbstgenerierten Curriculum eine superpolynomielle Reduktion der Supervision und der Rechenkosten im Vergleich zu Nicht-Curriculum-Baselines erreichen kann.

Theoretische Fundierung: Sie liefert einen rigorosen theoretischen Rahmen, der erklärt, warum die Zerlegung von Problemen hilft: Sie erlaubt es dem Lernenden, die Sequenzlänge gegen die Genauigkeitsanforderungen via Komposition abzuwägen, während Boosting die notwendige Genauigkeit bei den Teilproblemen sicherstellt.
Effizienz: Die Ergebnisse zeigen, dass für Aufgaben wie die Semiautomaten-Simulation ein Lernen mit $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$ Komplexität möglich ist, was eine dramatische Verbesserung gegenüber der linearen $\Omega(T)$ -Komplexität von Standardansätzen darstellt.
Generalisierung: Die Erkenntnisse legen nahe, dass Autocurricula, bei denen der Lernende seine eigenen Probleme entwirft, nicht nur Heuristiken sind, sondern theoretisch als Mechanismus zur Überwindung statistischer und computationaler Barrieren des Langzeit-Reasonings gerechtfertigt werden können.
Limitierungen und zukünftige Arbeit: Die Autoren räumen Vereinfachungen ein, wie etwa die Beschränkung der Modellklasse auf Markovsche Modelle (was Full-History-Attention wie Transformer ausschließt) und die Annahme deterministischer Übergänge. Sie merken an, dass die Erweiterung dieser Ergebnisse auf nicht-Markovsche Modelle und stochastische Übergänge eine wichtige Richtung für zukünftige Arbeiten ist. Zudem weisen sie darauf hin, dass während ihre aktuellen Ergebnisse eine subpolynomielle Abhängigkeit von $T$ erreichen, das Erreichen einer polylogarithmischen Abhängigkeit eine offene Frage bleibt, was potenziell stärkere Annahmen wie endliche Fehlergrenzen (finite mistake bounds) erfordert.

Zusammenfassend lässt sich sagen, dass die Arbeit etabliert, dass kompositionale Generalisierung, wenn sie durch ein adaptives Curriculum geleitet und durch Techniken wie invertiertes Sampling unterstützt wird, einen beweisbar effizienten Pfad zum Lernen komplexer sequentieller Aufgaben bietet, die für direkte Lernmethoden unzugänglich sind.