Recurrent Reasoning on Symbolic Puzzles with Sequence Models

Technische Zusammenfassung: Rekurrentes Schließen auf symbolischen Rätseln mit Sequenzmodellen

Problemstellung
Große Sprachmodelle (LLMs) zeigen oft eine scheinbare Kompetenz in symbolischen und algorithmischen Aufgaben, doch diese Leistung verschleiert häufig ein brüchiges Verhalten, wenn Probleme in Länge, Schwierigkeit zunehmen oder leicht von der Trainingsverteilung abweichen. Aktuelle Reasoning-Benchmarks priorisieren oft die Produktion einer gültigen Endantwort gegenüber der Robustheit, Minimalität und Stabilität des Lösungsprozesses. Die Autoren argumentieren, dass für algorithmische Probleme Korrektheit nicht nur eine plausible Endpunktproduktion erfordert, sondern die Fähigkeit, wiederholt gültige Zwischenschritte zu wählen, illegale Übergänge zu vermeiden und Konsistenz über lange Horizonte aufrechtzuerhalten. Die Autoren postulieren, dass algorithmisches Schließen als ein entscheidendes Setting dient, um echte Robustheit von oberflächlichem Musterabgleich zu unterscheiden.

Methodik: Der RecurrReason Benchmark
Um diese Einschränkungen zu adressieren, führen die Autoren RecurrReason ein, einen mit Schwierigkeitsgrad kontrollierten Benchmark, der aus vier rekurrenten Logikrätseln besteht:

1. Block World: Umordnung von Blöcken in Stapeln.
2. Checkers Jumping: Vertauschen der Positionen von roten und blauen Spielfiguren auf einem linearen Brett.
3. Tower of Hanoi: Bewegen von Scheiben zwischen Stäben unter Einhaltung von Größenbeschränkungen.
4. River Crossing: Transport von Akteur-Agenten-Paaren über einen Fluss unter Einhaltung von Sicherheitsbeschränkungen.

Der Benchmark wurde mit folgenden Merkmalen konstruiert:

• Skalierbare Schwierigkeit: Jedes Rätsel ist durch eine einzelne Ganzzahl $N \in \{1, \dots, 10\}$ parametrisiert.
• Optimale Trajektorien: Alle Instanzen werden mittels Breitensuche (BFS) gelöst, um optimale Trajektorien zu generieren, was insgesamt 10.817 einzigartige Rätsel und 285.933 Züge umfasst.
• Aufgabenformulierung: Die Aufgabe wird als „Predict-the-next-step“-Problem formuliert. Modelle erhalten den aktuellen Zustand ($s_t$) und den Zielzustand ($g$) und müssen den nächsten Zustand ($s_{t+1}$) vorhersagen. Die Evaluierung erfolgt durch autoregressive Rollouts ohne Ground-Truth-Zwischenzustände.
• Evaluierungsprotokoll: Die Modelle werden auf Instanzen mit $N=1$ bis $7$ trainiert und auf gehaltenen In-Distribution-Instanzen ($N=1$ bis $7$) sowie Out-of-Distribution (OOD)-Instanzen ($N=8$ bis $10$) evaluiert. Die Metriken umfassen die Erfolgsrate der Trajektorie, die Legalität der Züge und die Optimallücke.

Experimenteller Aufbau
Die Studie vergleicht zwei Transformer-Familien unter konsistenten Datensplits und Trainingsbedingungen (Scratch, Zero-Shot und Fine-Tuning):

1. T5-Stil (Encoder-Decoder): Ein 60M-Parameter-Modell (T5-small), bei dem der Encoder eine bidirektionale Attention über den konkatenierten Zustand und das Ziel berechnet, wodurch das Ziel als „First-Class“-Conditioning-Signal bei jedem Schritt fungiert.
2. GPT-2-Stil (Decoder-only): Ein 124M-Parameter-Modell (GPT-2), das eine kausale Maskierung verwendet, welche verhindert, dass die Tokens des aktuellen Zustands auf die Ziel-Tokens (die später in der Sequenz erscheinen) aufmerksam nehmen, was einen strukturellen Flaschenhals für die zielgerichtete Planung schafft.

Wesentliche Ergebnisse
Die Experimente zeigen, dass die Rätselstruktur ein stärkerer Determinant für die Lernbarkeit ist als die Modellgröße oder das Pre-training:

• Block World Erfolg: Das feinjustierte vortrainierte T5-Modell erreichte eine Validierungsgenauigkeit von 97,27 % und eine OOD-Genauigkeit von 81,00 %. Dieser Erfolg wird auf die lokale Übergangsfunktion des Rätsels (Prüfung nur der Oberseite eines Stapels, $O(1)$-Komplexität), das lineare Wachstum der Lösungslänge ($L(N) = O(N)$) und dichte Trainingssignale zurückgeführt.
• Scheitern bei anderen Rätseln:
  • River Crossing: Alle Modelle erzielten unter allen Bedingungen 0,00 %. Das Rätsel erfordert eine globale Constraint-Verifizierung ($O(N)$) bei jedem Schritt und besitzt einen kombinatorischen Aktionsraum, was alle Architekturen überforderte.
  • Tower of Hanoi: Die Modelle erreichten höchstens 11,11 % Validierungsgenauigkeit (nur bei trivialen $N=1$ Fällen) und 0,00 % OOD. Die exponentielle Lösungslänge ($2^N - 1$) führt zu kumulativen Fehlern, die eine Generalisierung über $N=1$ hinaus verhindern.
  • Checkers Jumping: Die Modelle erreichten höchstens 1,11 % Validierungsgenauigkeit und lösten nur triviale Instanzen, bei denen der Startzustand dem Zielzustand entspricht. Die quadratische Lösungslänge und die Notwendigkeit, Sackgassen zu vermeiden, erwiesen sich als unüberwindbar.
• Architektur vs. Skalierung: Das kleinere T5-Modell (60M) schnitt signifikant besser ab als das größere GPT-2-Modell (124M). Die Autoren führen dies auf die Fäh Fähigkeit des Encoder-Decoder-Architektur zurück, bidirektional auf das Ziel aufmerksam zu nehmen, während die kausale Maskierung in Decoder-only-Modellen einen strukturellen Flaschenhals erzeugt, der effektive Planung selbst bei größeren Parameterzahlen verhindert.
• Pre-training Transfer: Vorteile durch Pre-training wurden nur bei Rätseln mit lokal strukturierten Übergangsfunktionen beobachtet (Block World). Es bot keinen Transfer für Rätsel, die globale Constraints (River Crossing) oder rekursive Dekomposition (Tower of Hanoi) erfordern.

Fehlermodi-Analyse
Die Autoren identifizieren spezifische Fehlermodi, die mit der Rätselstruktur korrelieren:

• Ungültige Züge: Dominierten die Fehler in global beschränkten Rätseln (Tower of Hanoi, River Crossing), was auf ein Versagen bei der Generalisierung von Constraints hindeutet.
• Loops (Schleifen): Der primäre Fehlermodus für Block World in Decoder-only-Modellen, was auf ein partielles Erlernen von Regeln ohne zielgerichtete Auswahl hindeutet.
• Vorzeitiger Abbruch: Beobachtet bei GPT-2 im Tower of Hanoi, verknüpft mit der statistischen Überrepräsentation von Stop-Tokens in den Trainingsdaten.

Bedeutung und Behauptungen
Das Paper behauptet, dass architektonische Induktions-Biases wichtiger sind als die Skalierung für systematisches algorithmisches Schließen. Speziell:

1. Strukturelle Determinierung: Die Lernbarkeit eines Rätsels wird durch drei strukturelle Eigenschaften bestimmt: Lokalisierung des Übergangs, Größe des Aktionsraums und Wachstum der Lösungslänge. Die Autoren formalisieren ein Modell für kumulative Fehler, das zeigt, dass die Erfolgswahrscheinlichkeit exponentiell mit der Lösungslänge sinkt ($P \approx e^{-\epsilon L(N)}$).
2. Ziel-Conditioning: Bidirektionales Ziel-Conditioning (wie bei T5) ist entscheidend für die zielgerichtete Planung, während kausale Attention (wie bei GPT-2) einen strukturellen Flaschenhals schafft, der effektive Planung selbst mit höheren Parameterzahlen verhindert.
3. Grenzen des Pre-trainings: Pre-training verleiht einen hierarchischen Induktions-Bias, der nur auf Aufgaben mit lokal dekomponierbaren Strukturen transferierbar ist. Es befähigt Modelle nicht inhärent dazu, globale Constraints oder rekursive Tiefe zu handhaben.
4. Zukünftige Richtung: Die Ergebnisse legen nahe, dass zuverlässiges mehrstufiges Schließen in LLMs entweder architektonische Suchkapazitäten oder explizite symbolische Constraint-Prüfungen erfordert, anstatt lediglich die Modellgröße zu skalieren.

Die Autoren kommen zu dem Schluss, dass RecurrReason ein kontrolliertes Testfeld für zukünftige Arbeiten zu Längengeneralisierung, zielgerichteter Planung und den architektonischen Anforderungen für systematisches algorithmisches Schließen bietet.