Recurrent Reasoning on Symbolic Puzzles with Sequence Models

Technische Samenvatting: Recurrente Redenering op Symbolische Puzzels met Sequentiemodellen

Probleemstelling
Grote taalmodellen (LLM's) vertonen vaak een schijnbare bekwaamheid in symbolische en algoritmische taken, maar deze prestaties maskeren frequent bros gedrag wanneer problemen toenemen in lengte, moeilijkheidsgraad of licht afwijken van de trainingsdistributie. Huidige benchmarks voor redeneren geven vaak de voorkeur aan de productie van een geldig eindantwoord boven de robuustheid, minimaliteit en stabiliteit van het oplossingsproces. Dit artikel betoogt dat voor algoritmische problemen correctheid niet alleen een plausibel eindpunt vereist, maar ook het vermogen om herhaaldelijk geldige tussenliggende acties te kiezen, illegale transities te vermijden en consistentie te behouden over lange horizonten. De auteurs stellen dat algoritmische redenering een kritieke setting vormt om werkelijke robuustheid te onderscheiden van oppervlakkige patroonherkenning.

Methodologie: De RecurrReason Benchmark
Om deze beperkingen aan te pakken, introduceren de auteurs RecurrReason, een benchmark met gecontroleerde moeilijkheidsgraad bestaande uit vier recurrente logische puzzels:

1. Block World: Het herordenen van blokken in stapels.
2. Checkers Jumping: Het wisselen van posities van rode en blauwe checkers op een lineair bord.
3. Tower of Hanoi: Het verplaatsen van schijven tussen palen onder beperkingen van grootte.
4. River Crossing: Het transporteren van actor-agent paren over een rivier met veiligheidsrestricties.

De benchmark is geconstrueerd met de volgende kenmerken:

• Schaalbare Moeilijkheidsgraad: Elke puzzel is geparametriseerd door een enkele integer $N \in \{1, \dots, 10\}$.
• Optimale Trajecten: Alle instanties worden opgelost met behulp van Breadth-First Search (BFS) om optimale trajecten te genereren, wat in totaal 10.817 unieke puzzels en 285.933 zetten oplevert.
• Taakformulering: De taak wordt geformuleerd als een "voorspel-de-volgende-stap"-probleem. Modellen ontvangen de huidige staat ($s_t$) en de doelstaat ($g$) en moeten de volgende staat ($s_{t+1}$) voorspellen. Evaluatie vindt plaats via autoregressieve rollouts zonder grondwaarheid van tussenliggende staten.
• Evaluatieprotocol: Modellen worden getraind op instanties waar $N=1$ tot $7$ en geëvalueerd op uit de distributie gehouden (held-out) in-distributie instanties ($N=1$ tot $7$) en out-of-distribution (OOD) instanties ($N=8$ tot $10$). De metrieken zijn de succesrate van het traject, de legaliteit van de zetten en de optimaliteitskloof.

Experimentele Opzet
De studie benchmarkt twee Transformer-families onder consistente data-splits en trainingscondities (vanaf nul, zero-shot, en fine-tuned):

1. T5-stijl (Encoder-Decoder): Een model van 60M parameters (T5-small) waarbij de encoder bidirectionele aandacht berekent over de geconcateneerde staat en het doel, waardoor het doel een "first-class" conditioneringssignaal is bij elke stap.
2. GPT-2-stijl (Decoder-Only): Een 124M parameter model (GPT-2) dat een causale maskering gebruikt, wat voorkomt dat de tokens van de huidige staat aandacht besteden aan de doel-tokens (die later in de sequentie verschijnen), wat een structurele bottleneck creëert voor doelgerichte planning.

Belangrijkste Resultaten
De experimenten onthullen dat de puzzelstructuur een sterkere determinant is voor leerbaarheid dan modelgrootte of pre-training:

• Block World Succes: Het gefinetunede pre-trained T5-model bereikte 97,27% validatienauwkeurigheid en 81,00% OOD-nauwkeurigheid. Dit succes wordt toegeschreven aan de lokale transitiefunctie van de puzzel (het controleren van alleen de bovenkant van een stapel, $O(1)$ complexiteit), lineaire groei van de oplossinglengte ($L(N) = O(N)$), en dichte trainingssignalen.
• Falen op Andere Puzzels:
  • River Crossing: Alle modellen scoorden 0,00% onder alle condities. De puzzel vereist globale constraint-verificatie ($O(N)$) bij elke stap en heeft een combinatorische actieruimte, wat alle architecturen versloeg.
  • Tower of Hanoi: Modellen bereikten maximaal 11,11% validatienauwkeurigheid (alleen op triviale $N=1$ gevallen) en 0,00% OOD. De exponentiële oplossinglengte ($2^N - 1$) veroorzaakt cumulatieve fouten die generalisatie voorbij $N=1$ verhinderen.
  • Checkers Jumping: Modellen bereikten maximaal 1,11% validatienauwkeurigheid, waarbij ze alleen triviale instanties oplosten waarbij de begintoestand gelijk is aan de doelstaat. De kwadratische oplossinglengte en de noodzaak om doodlopende paden te vermijden bleken onoverkomelijk.
• Architectuur vs. Schaal: Het kleinere T5-model (60M) presteerde significant beter dan het grotere GPT-2-model (124M). De auteurs schrijven dit toe aan het vermogen van de encoder-decoder architectuur om bidirectioneel naar het doel te attentioneren, terwijl de causale maskering in decoder-only modellen een structurele bottleneck creëert die effectieve planning verhindert, zelfs met meer parameters.
• Pre-training Transfer: Voordelen van pre-training werden alleen waargenomen voor puzzels met lokaal gestructureerde transitiefuncties (Block World). Het bood geen transfer voor puzzels die globale constraints vereisen (River Crossing) of recursieve decompositie (Tower of Hanoi).

Analyse van Foutmodi
De auteurs identificeren specifieke foutmodi die correleren met de puzzelstructuur:

• Ongeldige Zetten: Dominante fouten in globaal geconstraineerde puzzels (Tower of Hanoi, River Crossing), wat wijst op een falen in het generaliseren van constraints.
• Loops (Lussen): De primaire foutmodus voor Block World in decoder-only modellen, wat duidt op gedeeltelijk regel-leren zonder doelgerichte selectie.
• Voortijdige Stops: Waargenomen bij GPT-2 op Tower of Hanoi, gelinkt aan de statistische oververtegenwoordiging van stop-tokens in de trainingsdata.

Betekenis en Claims
Het paper claimt dat architecturale inductieve biases belangrijker zijn dan schaal voor systematische algoritmische redenering. Specifiek:

1. Structurele Determinisme: De leerbaarheid van een puzzel wordt bepaald door drie structurele eigenschappen: transitie-lokaliteit, de grootte van de actieruimte en de groei van de oplossinglengte. De auteurs formaliseren een model van cumulatieve fouten dat laat zien dat de succeswaarschijnlijkheid exponentieel afneemt met de oplossinglengte ($P \approx e^{-\epsilon L(N)}$).
2. Doel-Conditionering: Bidirectionele doel-conditionering (zoals in T5) is cruciaal voor doelgerichte planning, terwijl causale aandacht (zo als in GPT-2) een structurele bottleneck creëert die effectieve planning verhindert, zelfs met grotere parameter-aantallen.
3. Limieten van Pre-training: Pre-training geeft een hiërarchische inductieve bias die alleen overdraagbaar is naar taken met lokaal decomponeerbare structuren. Het rust de modellen niet inherent uit om globale constraints of recursieve diepte aan te pakken.
4. Toekomstige Richting: De resultaten suggereren dat betrouwbare meerstaps-redenering in LLM's ofwel architecturale zoekcapaciteiten of expliciete symbolische constraint-controle vereist, in plaats van enkel het opschalen van de modelgrootte.

De auteurs concluderen dat RecurrReason een gecontroleerde testomgeving biedt voor toekomstig werk op het gebied van lengte-generalisatie, doelgerichte planning en de architecturale vereisten voor systematische algoritmische redenering.