Recurrent Reasoning on Symbolic Puzzles with Sequence Models

Résumé Technique : Raisonnement Récurrent sur des Puzzles Symboliques avec des Modèles de Séquence

Énoncé du Problème
Les grands modèles de langage (LLM) font souvent preuve d'une apparente compétence dans les tâches symboliques et algorithmiques, mais cette performance masque fréquemment un comportement fragile lorsque la complexité ou la longueur des problèmes augmente, ou lorsqu'ils s'écartent légèrement de la distribution d'entraînement. Les benchmarks de raisonnement actuels privilégient souvent la production d'une réponse finale valide au détriment de la robustesse, de la minimalité et de la stabilité du processus de solution. Cet article soutient que pour les problèmes algorithmiques, la correction ne nécessite pas seulement un point final plausible, mais la capacité de choisir de manière répétée des actions valides, d'éviter les transitions illégales et de maintenir une cohérence sur de longs horizons. Les auteurs postulent que le raisonnement algorithmique constitue un cadre critique pour distinguer la véritable robustesse du simple appariement de motifs superficiels (shallow pattern matching).

Méthodologie : Le Benchmark RecurrReason
Pour remédier à ces limitations, les auteurs introduisent RecurrReason, un benchmark à difficulté contrôlée comprenant quatre puzzles logiques récurrents :

1. Block World (Monde des Blocs) : Réorganiser des blocs dans des piles.
2. Checkers Jumping (Sauts de Dames) : Échanger les positions de pions rouges et bleus sur un plateau linéaire.
3. Tower of Hanoi (Tour de Hanoï) : Déplacer des disques entre des piquets sous des contraintes de taille.
4. River Crossing (Traversée de Rivière) : Transporter des paires acteur-agent à travers une rivière avec des contraintes de sécurité.

Le benchmark est construit avec les caractéristiques suivantes :

• Difficulté Évolutive : Chaque puzzle est paramétré par un entier unique $N \in \{1, \dots, 10\}$.
• Trajectoires Optimales : Toutes les instances sont résolues à l'aide d'un parcours en largeur (BFS) pour générer des trajectoires optimales, totalisant 10 817 puzzles uniques et 285 933 mouvements.
• Formulation de la Tâche : La tâche est formulée comme un problème de « prédiction de l'étape suivante ». Les modèles reçoivent l'état actuel ($s_t$) et l'état cible ($g$) et doivent prédire l'état suivant ($s_{t+1}$). L'évaluation se fait par déploiements (rollouts) autoregressifs sans états intermédiaires de vérité terrain.
• Protocole d'Évaluation : Les modèles sont entraînés sur des instances où $N=1$ à $7$ et évalués sur des instances en distribution (in-distribution) non vues ($N=1$ à $7$) et sur des instances hors distribution (out-of-distribution, OOD) ($N=8$ à $10$). Les métriques incluent le taux de succès de la trajectoire, la légalité des mouvements et l'écart d'optimalité.

Configuration Expérimentale
L'étude compare deux familles de Transformers sous des divisions de données et des conditions d'entraînement cohérentes (à partir de zéro, zero-shot, et fine-tuné) :

1. Type T5 (Encodeur-Décodeur) : Un modèle de 60M de paramètres (T5-small) où l'encodeur calcule une attention bidirectionnelle sur l'état et l'objectif concaténés, faisant de l'objectif un signal de conditionnement de « premier rang » à chaque étape.
2. Type GPT-2 (Décodeur uniquement) : Un modèle de 124M de paramètres (GPT-2) utilisant un masque causal, ce qui empêche les jetons de l'état actuel d'être attentifs aux jetons de l'objectif (qui apparaissent plus tard dans la séquence), créant ainsi un goulot d'étranglement structurel pour la planification orientée vers un but.

Résultats Clés
Les expériences révèlent que la structure du puzzle est un déterminant plus fort de l'apprentissage que l'échelle du modèle ou le pré-entraînement :

• Succès de Block World : Le modèle T5 pré-entraîné et fine-tuné a atteint une précision de validation de 97,27 % et une précision OOD de 81,00 %. Ce succès est attribué à la fonction de transition locale du puzzle (vérification uniquement du sommet d'une pile, complexité $O(1)$), à la croissance linéaire de la longueur de la solution ($L(N) = O(N)$) et à des signaux d'entraînement denses.
• Échec sur les autres puzzles :
  • River Crossing : Tous les modèles ont obtenu un score de 0,00 % dans toutes les conditions. Le puzzle nécessite une vérification de contrainte globale ($O(N)$) à chaque étape et possède un espace d'action combinatoire, ce qui a vaincu toutes les architectures.
  • Tower of Hanoi : Les modèles ont atteint au maximum 11,11 % de précision de validation (uniquement sur les cas triviaux $N=1$) et 0,00 % en OOD. La longueur de solution exponentielle ($2^N - 1$) provoque des erreurs cumulatives qui empêchent la généralisation au-delà de $N=1$.
  • Checkers Jumping : Les modèles ont atteint au maximum 1,11 % de précision de validation, ne résolvant que des instances triviales où l'état de départ est égal à l'état cible. La longueur de solution quadratique et la nécessité d'éviter les impasses se sont révélées insurmontables.
• Architecture vs Échelle : Le plus petit modèle T5 (60M) a nettement surperformé le modèle GPT-2 plus grand (124M). Les auteurs attribuent cela à la capacité de l'architecture encodeur-décodeur à porter une attention bidirectionnelle à l'objectif, tandis que le masque causal des modèles de type décodeur seul crée un goulot d'étranglement pour la planification.
• Transfert de Pré-entraînement : Les bénéfices du pré-entraînement n'ont été observés que pour les puzzles ayant des fonctions de transition localement structurées (Block World). Il n'a apporté aucun transfert pour les puzzles nécessitant des contraintes globales (River Crossing) ou une décomposition récursive (Tower of Hanoi).

Analyse des Modes de Défaillance
Les auteurs identent des modes de défaillance spécifiques corrélés à la structure du puzzle :

• Mouvements Invalides : Dominent les échecs dans les puzzles à contraintes globales (Tower of Hanoi, River Crossing), indiquant un échec de la généralisation des contraintes.
• Boucles : Le principal mode de défaillance pour Block World dans les modèles de type décodeur seul, suggérant un apprentissage partiel des règles sans sélection orientée vers un but.
• Arrêts Prématurés : Observés sur GPT-2 pour Tower of Hanoi, liés à la surreprésentation statistique des jetons d'arrêt (stop tokens) dans les données d'entraînement.

Signification et Revendications
L'article affirme que les biais inductifs architecturaux comptent plus que l'échelle pour le raisonnement algorithmique systématique. Plus précisément :

1. Déterminisme Structurel : L'apprentissage d'un puzzle est déterminé par trois propriétés structurelles : la localité de la transition, la taille de l'espace d'action et la croissance de la longueur de la solution. Les auteurs formalisent un modèle d'erreur cumulée montrant que la probabilité de succès décroît exponentiellement avec la longueur de la solution ($P \approx e^{-\epsilon L(N)}$).
2. Conditionnement par l'Objectif : Le conditionnement bidirectionnel par l'objectif (comme dans T5) est critique pour la planification orientée vers un but, tandis que l'attention causale (comme dans GPT-2) crée un goulot d'étranglement structurel qui empêche une planification efficace, même avec un nombre de paramètres plus élevé.
3. Limites du Pré-entraînement : Le pré-entraînement confère un biais inductif hiérarchique qui ne se transfère qu'aux tâches ayant des structures localement décomposables. Il n'équipe pas intrinsèquement les modèles pour gérer les contraintes globales ou la profondeur récursive.
4. Direction Future : Les résultats suggèrent que le raisonnement multi-étapes fiable dans les LLM nécessite soit des capacités de recherche architecturale, soit une vérification explicite des contraintes symboliques, plutôt qu'une simple augmentation de la taille du modèle.

Les auteurs concluent que RecurrReason offre un banc d'essai contrôlé pour les travaux futurs sur la généralisation de la longueur, la planification conditionnée par un but et les exigences architecturales du raisonnement algorithmique systématique.