🤖 machine learning

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete

Cet article démontre que les encodages de position ne sont pas strictement nécessaires pour que les transformeurs atteignent la complétude de Turing, car le mécanisme de fenêtre glissante brise lui-même la symétrie de permutation et fournit suffisamment d'informations positionnelles pour simuler un calcul universel.

Auteurs originaux : Qian Li, Xinyu Mao, Shang-Hua Teng

Publié 2026-06-02

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Qian Li, Xinyu Mao, Shang-Hua Teng

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

Imaginez que vous essayiez d'apprendre à un robot à raconter une histoire ou à résoudre un problème mathématique. Pendant longtemps, les informaticiens ont cru que pour cela, le robot avait besoin d'un « carnet d'adresses » spécial attaché à chaque mot qu'il lisait. Ce carnet d'adresses, appelé Codage Positionnel (Positional Encoding - PE), indiquait au robot l'emplacement exact de chaque mot dans la phrase (1er, 2e, 3e, etc.). Sans lui, disait-on, le robot serait confus car il ne pourrait pas faire la différence entre « Le chat poursuit le chien » et « Le chien poursuit le chat ».

Cet article soutient que vous n'avez pas réellement besoin de ce carnet d'adresses si le robot travaille avec un type spécifique de mémoire : une fenêtre glissante (sliding window).

Voici l'idée centrale, décomposée avec quelques analogies de la vie quotidienne :

1. La croyance ancienne : La « photo statique »

Considérez un modèle Transformer standard (le type derrière de nombreux chatbots IA) comme un photographe prenant une photo d'une foule. Si vous donnez simplement au photographe un tas de visages sans lui dire qui se trouve où, il ne peut pas faire la différence entre une file de personnes et un tas aléatoire. Il a besoin d'une étiquette sur le front de chaque personne (le Codage Positionnel) pour connaître l'ordre.

2. La nouvelle découverte : Le « bus en mouvement »

Les auteurs ont réalisé que lorsque l'IA effectue un raisonnement complexe, étape par étape (comme la résolution d'un long problème mathématique), elle ne regarde pas l'ensemble de l'historique d'un seul coup. Au lieu de cela, elle utilise une fenêtre glissante.

Imaginez que l'IA est assise dans un bus avec une fenêtre qui ne montre que les 10 dernières personnes qui sont passées devant elle.

L'ancienne vision : Si vous regardez simplement les 10 personnes actuellement dans la fenêtre, vous ne pouvez pas savoir qui est passé en premier ou qui est sorti en dernier. C'est juste un groupe de 10 personnes.
La nouvelle vision : Les auteurs ont remarqué que le bus est en mouvement.
- Chaque seconde, une nouvelle personne monte dans le bus (entre dans la fenêtre).
- Chaque seconde, la personne la plus ancienne tombe à l'arrière (sort de la fenêtre).

Même si l'IA ne peut pas voir les « adresses de rue » des personnes à l'intérieur du bus, l'acte du bus qui se déplace crée un motif. L'IA peut voir : « Oh, une nouvelle personne vient de monter, et je sais qui vient de tomber car le groupe total a changé. »

3. Le « Histogramme Magique » (Le modèle HIST)

Pour prouver cela, les auteurs ont inventé un robot théorique appelé le modèle HIST.

Ce robot est aveugle à l'ordre. Il ne peut pas dire « La chemise rouge est la 3e ».
Il voit seulement un décompte (un histogramme). Il sait : « Il y a 3 chemises rouges, 2 bleues et 1 verte dans la fenêtre en ce moment même. »
Il possède également une petite mémoire (un « état de contrôle ») pour se souvenir des dernières choses qui se sont passées.

Le tour de magie est le suivant : En comparant le décompte avant qu'une nouvelle personne n'entre et le décompte après, le robot peut déterminer exactement qui vient de quitter le bus, même sans voir son étiquette de nom.

Avant : 3 Rouges, 2 Bleus.
Une nouvelle personne entre (Bleu).
Après : 3 Rouges, 3 Bleus.
Attendez, la taille de la fenêtre est fixe ! Si un nouveau Bleu entre, un Rouge doit être parti.
Conclusion : Le robot sait qu'une chemise Rouge vient de tomber à l'arrière, même s'il n'a jamais vu la position de la chemise Rouge.

4. Le grand résultat : La complétude de Turing

En informatique, être « Turing Complet » signifie qu'une machine peut théoriquement résoudre n'importe quel problème qu'un ordinateur peut résoudre, avec suffisamment de temps et de mémoire.

Croyance précédente : Les Transformers avaient besoin de Codages Positionnels pour être Turing Complètes.
La preuve de cet article : Un Transformer avec une fenêtre glissante n'a pas besoin de Codages Positionnels pour être capable de calcul universel. Le mouvement de la fenêtre elle-même fournit suffisamment d'« informations séquentielles » pour simuler un ordinateur universel.

Les auteurs ont construit un pont mathématique montrant que :

Une machine qui ne fait que compter des types de jetons (le modèle HIST) peut simuler un ordinateur universel (spécifiquement, une « Machine de Post », qui est comme un ordinateur avec une file d'attente).
Un Transformer standard (sans Codages Positionnels) peut parfaitement imiter cette machine de comptage.

5. Ce que cela signifie (et ce que cela ne signifie pas)

Les bonnes nouvelles :
Il s'avère que le « mouvement » du traitement des données étape par étape est assez puissant pour créer de l'ordre. Vous n'avez pas besoin de marquer manuellement chaque mot avec un numéro pour obtenir un calcul universel. L'action de « glissement » brise la symétrie par elle-même.

Les nuances (ce que l'article ne dit pas) :

Ce n'est pas une question de vitesse : C'est une preuve de possibilité, pas d'efficacité. Ce n'est pas parce qu'un robot peut résoudre un problème sans le carnet d'adresses qu'il le fera rapidement ou facilement dans la réalité.
Il ne lit pas les positions exactes : Le robot ne peut toujours pas dire « Le 5e mot est 'pomme' ». Il peut seulement déduire « Quelqu'un est parti du groupe ». C'est un tour de déduction astucieux, pas une carte directe.
Cela nécessite un peu de magie mathématique : La preuve repose sur le fait que le robot puisse compter très précisément (tests de parité) pour savoir exactement qui est sorti de la fenêtre. Dans le monde réel, cela pourrait nécessiter des mathématiques de très haute précision, un détail technique que les auteurs reconnaissent.

Résumé

Considérez le Codage Positionnel comme les coordonnées GPS de chaque mot. Cet article dit : « Vous n'avez pas besoin de GPS si vous marchez dans une rue et que vous regardez les gens entrer et sortir d'un magasin. Le flux de personnes entrant et sortant vous raconte l'histoire, même si vous ne connaissez pas leurs adresses de rue exactes. »

La fenêtre glissante elle-même est le « GPS » de l'IA, rendant le carnet d'adresses externe inutile pour que la machine soit capable de calcul universel.

Résumé technique : Repenser le rôle du codage positionnel dans les Transformers à fenêtre glissante

1. Énoncé du problème

Le codage positionnel (PE) est considéré depuis longtemps comme une composante nécessaire aux architectures Transformer pour traiter des séquences ordonnées. L'intuition prédominante est que, sans information positionnelle explicite, le mécanisme d'auto-attention est invariant par permutation, rendant le modèle incapable de distinguer différents ordonnancements d'un même ensemble de jetons de contexte. Cette hypothèse sous-tend les résultats théoriques antérieurs établissant la complétude de Turing des Transformers avec raisonnement de type Chaîne de Pensée (CoT), qui reposent largement sur le PE pour simuler un calcul séquentiel.

Cependant, ces résultats d'universalité supposent souvent que le modèle prête attention à l'intégralité de l'historique. Dans les scénarios réels de raisonnement à long terme, les modèles opèrent avec une fenêtre de contexte glissante finie. À mesure que la fenêtre glisse vers l'avant, des jetons entrent et sortent, introduisant une asymétrie temporelle. La question centrale abordée par cet article est la suivante : Les codages positionnels sont-ils réellement nécessaires pour le calcul universel dans les Transformers à fenêtre glissante ? Les auteurs cherchent à savoir si le mécanisme de la fenêtre glissante fournit en soi une structure séquentielle suffisante pour atteindre la complétude de Turing sans PE explicite.

2. Méthodologie et cadre

Le modèle HIST

Pour isoler la puissance de calcul dérivée de la fenêtre glissante, les auteurs introduisent un modèle autoregressif abstrait appelé le modèle HIST.

Définition : Une machine HIST génère le jeton suivant en se basant uniquement sur un état de contrôle fini et l'histogramme du compte de jetons de la fenêtre actuelle (le vecteur des fréquences de jetons indexé par l'alphabet).
Contrainte : Le modèle n'a pas accès aux positions spécifiques des jetons individuels au sein de la fenêtre ; sa fonction de transition est invariante par permutation par rapport au contenu de la fenêtre.
Variante Parity-HIST : Une version restreinte où la fonction de transition dépend uniquement de la parité de l'histogramme (c'est-à-dire si le compte de chaque type de jeton est pair ou impair).

Stratégie théorique

La preuve de la complétude de Turing procède en deux étapes principales :

Simulation de machines de Post : Les auteurs prouvent qu'une machine Parity-HIST peut simuler une machine de Post (un automate basé sur une file d'attente connu pour être Turing-complet).
- Insight clé : Bien que la machine Parity-HIST n'observe que la parité de la fenêtre, la nature FIFO (First-In-First-Out) de la fenêtre glissante lui permet d'inférer le jeton qui vient de quitter la fenêtre. En comparant l'histogramme de parité avant et après une mise à jour de la fenêtre (et en utilisant l'état de contrôle fini pour stocker le jeton nouvellement entré), la machine peut déduire l'identité du jeton "déposé" à l'avant. Cela simule efficacement l'opération de défilement (dequeue) d'une file sans adressage positionnel explicite.
Simulation de Parity-HIST par des Transformers : Les auteurs construisent un Transformer à fenêtre glissante sans PE capable de simuler le modèle Parity-HIST.
- Mécanisme : Le Transformer utilise un alphabet de jetons de taille constante et un bit de mise à jour adaptatif. Pour récupérer les comptes bruts de jetons (et donc leur parité) à partir du mécanisme d'attention, la construction introduit un symbole marqueur (#) spécial.
- Dynamique d'attention : En utilisant une attention uniforme (obtenue via des matrices Query et Key nulles), les poids d'attention deviennent $1/m$ (où $m$ est la taille de la fenêtre). La présence d'un marqueur unique permet au modèle d'inférer la taille de la fenêtre $m$ et de convertir les masses d'attention normalisées en comptes entiers bruts.
- Extraction de parité : Avec une précision arithmétique suffisante (logarithmique par rapport à la taille de la fenêtre), la couche MLP calcule la parité des comptes de jetons, répliquant ainsi la fonction de transition Parity-HIST.

3. Contributions et résultats clés

Théorème 1 (Haut niveau) : Le modèle Parity-HIST est Turing-complet. Les auteurs démontrent que l'évolution temporelle d'une fenêtre glissante, combinée à un résumé permutation-invariant (parité de l'histogramme) et un état fini, est suffisante pour simuler des machines de Post.
Théorème 2 (Haut niveau) : Chaque machine Parity-HIST peut être simulée par un Transformer à fenêtre glissante sans codage positionnel.
Corollaire : Les Transformers à fenêtre glissante sans PE sont Turing-complets.
Détails de la construction :
- La construction utilise un vocabulaire de taille constante et un nombre constant de paramètres apprenables.
- Elle emploie un mécanisme de mise à jour de fenêtre adaptatif où les jetons portent un bit de contrôle pour soit faire glisser la fenêtre (standard), soit l'étendre (en conservant le jeton le plus ancien), évitant ainsi de devoir spécifier une taille de fenêtre maximale par défaut.
- La simulation nécessite une précision logarithmique ( $O(\log S)$ ) pour les opérations arithmétiques afin de calculer les parités, où $S$ est la longueur maximale de la fenêtre.

4. Signification et affirmations

L'article affirme séparer fondamentalement les concepts de codage positionnel et de structure séquentielle dans le contexte du calcul universel.

Le PE n'est pas indispensable : Les résultats démontrent que les codages positionnels explicites ne sont pas un prérequis pour que les Transformers puissent effectuer un calcul universel. Le mouvement de type "FIFO" de la fenêtre glissante brise elle-même la symétrie de permutation et fournit le signal séquentiel nécessaire.
Raffinement de l'universalité : Ce travail clarifie que, bien que le calcul universel nécessite une certaine source de structure séquentielle, cette structure n'a pas besoin d'être fournie par un système d'adressage positionnel externe. Elle peut émerger naturellement de la dynamique temporelle du processus de génération.
Distinction par rapport aux travaux antérieurs : Contrairement aux preuves d'universalité précédentes qui utilisent le PE pour stocker des structures de circuits ou identifier des jetons spécifiques, cette construction fait passer la simulation par un modèle de résumé de fenêtre invariant par permutation.
Limites et portée :
- Cette construction est un résultat d'expressivité, et non une affirmation sur l'apprenabilité ou l'efficacité pratique. Elle n'implique pas que les Transformers standards apprendront naturellement ces algorithmes.
- Le modèle ne récupère pas les positions exactes des jetons au sein de la fenêtre ; il infère seulement l'identité des jetons entrant et sortant.
- La construction repose sur un primitif de parité nécessitant une précision logarithmique, qui est isolée comme une exigence numérique plutôt que comme une limitation architecturale fondamentale de la réduction.

En résumé, l'article établit que le mécanisme de la fenêtre glissante seul, même en l'absence de codages positionnels, dote les Transformers de la capacité de calcul universel en exploitant l'asymétrie temporelle de l'entrée et de la sortie des jetons.