🤖 machine learning

Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

Ce papier démontre que, bien que les Transformers à chaîne de pensée standard échouent à généraliser à des traces de raisonnement plus longues en raison de limitations inhérentes à la copie et à la récupération, ils peuvent atteindre une complétude de Turing généralisable en longueur en employant un vocabulaire croissant avec des tokens balises uniques et des encodages de changement de valeur pour surmonter ces obstacles.

Auteurs originaux : Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn

Publié 2026-04-29

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

La vue d'ensemble : L'« élève brillant » qui oublie

Imaginez un élève très intelligent (le Transformer) qui apprend à résoudre des énigmes complexes. Pour l'aider, les enseignants lui fournissent un « brouillon » où il peut noter ses pensées étape par étape. C'est ce qu'on appelle la Chaîne de Pensée (CoT).

Des recherches antérieures ont montré qu'avec ce brouillon, l'élève pouvait théoriquement résoudre n'importe quelle énigme, aussi difficile soit-elle. C'était comme lui donner un super-pouvoir.

Cependant, les auteurs de ce papier ont découvert un défaut majeur : l'élève est excellent pour résoudre les énigmes sur lesquelles il s'est entraîné, mais il échoue lamentablement lorsque les énigmes deviennent plus longues. Si vous l'entraînez sur une énigme de 10 étapes, il ne peut pas en résoudre une de 20 étapes, même si la logique est la même. Il semble atteindre un « plafond » où son raisonnement s'effondre.

Ce papier se demande : Pourquoi cela arrive-t-il, et pouvons-nous le corriger ?

Les deux grands obstacles

Les auteurs ont découvert que le cerveau de l'élève (le Transformer) possède deux « bugs » spécifiques qui l'empêchent de généraliser à des tâches plus longues.

1. Le bug du « Photocopieur » (Copie répétée)

Imaginez que l'élève doit copier une longue liste d'instructions d'un livre sur son brouillon.

Le problème : Si la liste est courte, il peut la copier facilement. Mais si la liste est longue, il se perd. Il ne peut pas trouver de manière fiable la ligne exacte qu'il doit copier au milieu d'une longue page sans perdre le fil.
L'affirmation du papier : Les Transformers standards peinent à « copier » des chaînes d'informations arbitraires lorsque la longueur change. Ils se perdent au milieu du texte.

2. Le bug du « Dernier vu » (Récupération)

Imaginez que l'élève suit une variable, comme « La valeur de X ».

Le problème : Si l'élève écrit « X = 5 », puis plus tard « X = 7 », et ensuite « X = 5 » à nouveau, il doit connaître la valeur actuelle. Dans une longue chaîne de pensées, l'élève oublie souvent quel « 5 » était le plus récent. Il pourrait saisir un vieux « 5 » du début de la page au lieu du nouveau.
L'affirmation du papier : Le modèle a du mal à trouver la dernière mise à jour dans une longue histoire de changements. C'est comme essayer de trouver la dernière fois que vous avez mangé une pomme dans un journal qui contient 1 000 pages d'entrées.

La solution : Une nouvelle façon d'écrire le brouillon

Les auteurs proposent deux astuces ingénieuses pour corriger ces bugs. Ils ne changent pas le cerveau de l'élève ; ils changent simplement la façon dont les instructions sont écrites sur le brouillon.

Astuce n°1 : Les « Étiquettes de nom » (Jeton-poteau)

Pour corriger le bug du Photocopieur, les auteurs suggèrent de donner à chaque élément de l'énigme une carte d'identité unique ou une « Étiquette de nom ».

Comment ça marche : Au lieu de dire « Allez à la ligne 50 », l'instruction dit « Allez à l'élément avec l'Étiquette de nom n°42 ».
Pourquoi ça aide : Même si la liste s'allonge, l'élève n'a pas besoin de compter pour trouver la ligne 50. Il cherche simplement l'Étiquette de nom spécifique. C'est comme avoir une bibliothèque où chaque livre possède un code-barres unique, de sorte que vous n'avez pas à scanner tout l'étagère pour trouver celui dont vous avez besoin.

Astuce n°2 : Le « Journal des modifications » (Encodage des changements de valeur)

Pour corriger le bug du Dernier vu, les auteurs suggèrent de changer ce que l'élève note.

Ancienne méthode : L'élève écrit l'état complet actuel à chaque fois (par exemple, « X vaut 5 », puis « X vaut 7 », puis « X vaut 5 »). Cela crée beaucoup de bruit et rend difficile de savoir quelle est la plus récente.
Nouvelle méthode : L'élève n'écrit que ce qui a changé.
- Au lieu d'écrire « X vaut 7 », il écrit « X est passé de 5 à 7 ».
- Au lieu d'écrire « X vaut 5 » à nouveau, il écrit « X est passé de 7 à 5 ».
Pourquoi ça aide : Pour trouver la valeur actuelle, l'élève compte simplement les changements. S'il voit « 5 à 7 » puis « 7 à 5 », il sait que la valeur actuelle est 5. C'est comme tenir un livre de comptes des transactions plutôt que de réécrire tout votre solde bancaire à chaque fois que vous dépensez un dollar.

Les résultats : Théorie vs Réalité

Le papier teste ces idées de deux manières :

La preuve mathématique (Théorie) :
- Mauvaise nouvelle : Si vous vous en tenez à un ensemble fixe de mots (un alphabet fini) et à des styles d'écriture standards, l'élève ne peut pas apprendre à résoudre des énigmes plus longues qu'une certaine complexité (spécifiquement, il ne peut pas dépasser une classe de problèmes appelée TC0). Il est mathématiquement coincé.
- Bonne nouvelle : Si vous permettez à l'élève d'utiliser un approvisionnement infini d'Étiquettes de nom uniques (Poteaux) et d'utiliser la méthode du « Journal des modifications », il peut théoriquement résoudre n'importe quelle énigme, quelle que soit sa longueur.
Les expériences (Réalité) :
- Les auteurs ont entraîné de petits modèles informatiques à partir de zéro sur trois tâches difficiles :
  - Parité : Compter si une chaîne de nombres contient un nombre impair ou pair de 1.
  - Évaluation booléenne : Résoudre des énigmes logiques complexes (Vrai/Faux).
  - Permutation S5 : Suivre le mouvement de 5 objets qui sont échangés.
- Le résultat :
  - Les modèles entraînés avec la méthode standard ont échoué lorsque les énigmes sont devenues plus longues.
  - Les modèles entraînés avec les Étiquettes de nom et les Journaux de modifications étaient beaucoup meilleurs pour résoudre des énigmes plus longues qu'ils n'avaient jamais vues auparavant.
- Ils ont également testé cela sur d'énormes modèles d'IA pré-entraînés (comme Llama et Mistral). Même sans les réentraîner, le simple fait de les inciter à utiliser des Étiquettes de nom et des Journaux de modifications dans leurs réponses les a rendus considérablement plus intelligents pour résoudre des problèmes longs et difficiles.

L'essentiel

Le papier conclut que la Chaîne de Pensée n'est pas magique. Dire simplement à une IA de « réfléchir étape par étape » ne suffit pas si la façon dont elle pense est sujette à se perdre dans de longues listes.

Pour rendre l'IA vraiment fiable dans le raisonnement à long terme, nous devons formater les « pensées » d'une manière qui évite les deux principaux pièges :

Donnez à chaque étape une Étiquette de nom unique afin que rien ne se perde.
Enregistrez uniquement les Changements afin que le modèle ne soit pas confus par les anciennes informations.

En corrigeant le format du raisonnement, nous pouvons aider les modèles d'IA à briser leurs limites actuelles et à résoudre des problèmes beaucoup plus difficiles.

1. Énoncé du problème

Bien que l'incitation par la chaîne de pensée (CoT) ait empiriquement amélioré les performances des Transformers et que la théorie ait démontré qu'elle augmente leur expressivité jusqu'à la complétude de Turing, un écart critique subsiste : Les Transformers peuvent-ils apprendre à généraliser le raisonnement par CoT à des longueurs supérieures à celles observées pendant l'entraînement ?

Les preuves empiriques existantes suggèrent que la précision des Transformers se dégrade fortement à mesure que la longueur de la trace CoT augmente, même sur des tâches algorithmiques et logiques. L'article examine si l'affirmation théorique de la complétude de Turing tient sous l'exigence plus stricte de l'apprenabilité généralisable en longueur. Plus précisément, il se demande :

Les formats CoT standards permettent-ils aux Transformers de résoudre des problèmes au-delà de la classe de complexité $\text{TC}^0$ (circuits à seuil de profondeur constante) lors de la généralisation vers des séquences plus longues ?
Quelles barrières structurelles spécifiques empêchent cette généralisation ?
Ces barrières peuvent-elles être surmontées par des stratégies de formatage spécifiques ?

2. Méthodologie

Les auteurs utilisent une combinaison de formalisme théorique et de validation empirique :

Cadre théorique

L'étude utilise des cadres théoriques récents pour la généralisation en longueur des Transformers :

C-RASP : Un formalisme pour raisonner sur les Transformers avec des alphabets finis et des encodages positionnels. L'appartenance implique des garanties de généralisation en longueur.
C-RASP :* Une extension de C-RASP qui permet un alphabet infini (spécifiquement, des tokens de repère non bornés) et des prédicats de correspondance locale.
Modèle d'apprentissage : Les auteurs adoptent un modèle d'apprentissage idéalisé où une séquence de Transformers entraînés sur des longueurs d'entrée croissantes converge vers un algorithme sous-jacent unique. La généralisation est garantie si la tâche peut être exprimée dans ces formalismes.

Configuration empirique

Tâches : Trois tâches de raisonnement algorithmique ont été sélectionnées :
1. Parité : Déterminer si le nombre de 1 dans une chaîne binaire est pair ou impair.
2. Évaluation booléenne : Évaluer la valeur de vérité de formules logiques imbriquées.
3. Permutation S5 : Suivre l'état de 5 objets après une série d'opérations d'échange.
Modèles :
- À partir de zéro : Des modèles GPT-2 (25 millions de paramètres) entraînés sur des traces CoT avec et sans formatage spécifique.
- LLM pré-entraînés : Expériences d'incitation en zéro-shot et few-shot sur Qwen2.5-7B, Mistral-Small-24B et Llama-3.3-70B.
Variantes de formatage :
- CoT naïf : Raisonnement séquentiel standard.
- Tokens de repère : Attribution d'identifiants uniques (par exemple, <34>) à des positions ou opérations spécifiques pour permettre un adressage arbitraire.
- Encodage des changements de valeur : Au lieu d'enregistrer l'état complet à chaque étape, le modèle ne consigne que les changements de valeurs (par exemple, 1 -> 0) ou enregistre explicitement lorsqu'une valeur reste inchangée.

3. Contributions clés et résultats théoriques

Contribution 1 : La limite des alphabets finis (Le résultat négatif)

Les auteurs prouvent que sous des encodages positionnels standards et un alphabet fini, les Transformers avec CoT ne peuvent pas généraliser en longueur pour résoudre des problèmes en dehors de $\text{TC}^0$ .

Théorème 3.4 : Si un langage $L$ possède une trace CoT exprimable en C-RASP (avec des primitives positionnelles), alors $L$ est définissable dans $\text{TC}^0$ .
Implication : Bien que le CoT permette théoriquement la complétude de Turing, l'apprenabilité de telles simulations est bornée par $\text{TC}^0$ si le vocabulaire est fixe. Les bénéfices d'expressivité ne se traduisent pas par une apprenabilité généralisable en longueur.

Contribution 2 : Surmonter les barrières avec des alphabets infinis (Le résultat positif)

L'article identifie deux barrières fondamentales à la généralisation en longueur :

Copie répétée : La difficulté de copier des chaînes arbitraires vers de nouvelles positions.
Récupération de la dernière occurrence : La difficulté de récupérer la valeur la plus récente d'une variable lorsque plusieurs mises à jour se produisent (récupération non unique).

Pour surmonter ces obstacles, les auteurs proposent une construction utilisant C-RASP* :

Tokens de repère : Attribution d'un token unique et non borné (provenant d'un alphabet infini) à chaque position de ruban ou étape d'opération. Cela résout la barrière de copie en permettant un indexage arbitraire sans mémoriser des identités absolues.
Encodage des changements de valeur : Au lieu d'enregistrer l'état complet, la CoT ne consigne que les transitions (par exemple, "valeur changée de $x$ à $y$ "). L'état actuel est récupéré en comptant les changements nets par rapport à l'état initial. Cela résout la barrière de récupération en faisant de la valeur actuelle une fonction de comptes plutôt qu'une recherche de la dernière occurrence.
Théorème 3.8 : Les Transformers avec CoT peuvent généraliser en longueur pour simuler n'importe quelle machine de Turing s'ils utilisent un alphabet infini de tokens de repère et encodent les calculs via des changements de valeur. La longueur de la trace CoT reste linéaire par rapport au temps d'exécution simulé.

4. Résultats empiriques

Entraînement à partir de zéro

Parité : Le CoT standard a échoué à généraliser au-delà des longueurs d'entraînement. L'encodage des changements de valeur a permis une généralisation robuste jusqu'à $2\times$ la longueur d'entraînement.
Évaluation booléenne et Permutation S5 : Ces tâches plus difficiles (en dehors de $\text{TC}^0$ ) ont échoué avec un CoT naïf. L'ajout de tokens de repère a considérablement amélioré la généralisation en longueur, bien que S5 soit resté difficile en raison de possibles "raccourcis" (heuristiques) que le modèle pourrait exploiter.
Permutation binaire : Une variante de S5 avec une forte répétition. Les CoT naïfs et uniquement basés sur les repères ont échoué en raison d'erreurs de "récupération non unique". La combinaison Repères + Changements de valeur a donné les meilleurs résultats, confirmant la nécessité théorique des deux mécanismes.

Incitation des LLM pré-entraînés

Repères : L'utilisation de nombres naturels comme indices de repère dans les incitations few-shot a amélioré les performances sur les tâches booléennes et S5 pour tous les LLM testés (de 7B à 70B), en particulier pour des longueurs de séquence plus grandes.
Changements de valeur : Dans une tâche d'exécution de code (suivi des affectations de variables), fournir des commentaires en ligne enregistrant explicitement les changements de valeur (par exemple, # nœud a : 9 -> 0) a considérablement amélioré la précision de la réponse finale par rapport au formatage de code standard, même sans étapes de raisonnement intermédiaires.

5. Importance et conclusion

Redéfinition du succès du CoT : L'article soutient que le succès du CoT n'est pas inhérent au processus de "pensée" lui-même, mais dépend fortement du formatage de la trace. Les formats CoT standards échouent souvent à généraliser car ils violent les contraintes requises pour l'apprenabilité (localité et invariance par translation).
Limites théoriques : Il clarifie que la complétude de Turing pour les Transformers est conditionnelle. Elle vaut pour l'expressivité (coder en dur une solution) mais pas pour l'apprenabilité (entraîner un modèle à généraliser) sauf si des aides structurelles spécifiques (alphabets infinis/repères) sont fournies.
Lignes directrices pratiques : Les résultats offrent des principes actionnables pour améliorer les performances des LLM sur des tâches de raisonnement difficiles :
1. Utiliser des indices d'index : Marquer explicitement les positions ou les étapes avec des identifiants uniques pour faciliter la récupération.
2. Enregistrer les changements, pas les états : Formater les traces de raisonnement pour mettre en évidence les transitions d'état plutôt que des vidages complets d'état afin d'éviter l'ambiguïté de récupération.
Perspectives futures : Ce travail suggère que les futures données de pré-entraînement et les schémas de CoT devraient être conçus en tenant compte de ces contraintes théoriques pour débloquer le potentiel computationnel complet des Transformers sur des tâches de raisonnement à long horizon.

En résumé, l'article démontre que si les Transformers sont théoriquement capables de raisonnement universel, la réalisation de cette capacité de manière généralisable en longueur nécessite de surmonter des barrières architecturales et de formatage spécifiques grâce à l'utilisation de tokens de repère et d'encodages de changements de valeur.