Résumé Technique : Combien de Sorties Différentes un Transformer Peut-Il Générer ?

Énoncé du Problème

Malgré le succès empirique des Transformers dans le traitement du langage naturel et la vision par ordinateur, ces modèles présentent des défaillances fondamentales sur des tâches algorithmiques simples, telles que la copie ou la répétition de séquences, dès que la longueur de l'entrée dépasse un certain seuil. Alors que des travaux antérieurs ont attribué ces échecs à des problèmes de données d'entraînement ou d'optimisation, cet article postule qu'ils découlent de contraintes architecturales intrinsèques. Plus précisément, les auteurs investiguent l'accessibilité des séquences de sortie : l'ensemble de toutes les séquences de tokens qu'un Transformer peut générer étant donné n'importe quel prompt possible (y compris des prompts souples optimisés) et une longueur de contexte arbitraire. La question centrale est : Combien de séquences distinctes un Transformer peut-il réellement produire, et comment cette capacité évolue-t-elle avec la longueur du prompt et l'architecture du modèle ?

Méthodologie

Les auteurs abordent le problème en analysant les contraintes géométriques imposées par la précision numérique finie et la nature bornée des représentations internes au sein de l'architecture Transformer.

1. Formulation de Champ Moyen : Pour gérer des longueurs de prompt arbitraires, les auteurs interprètent les Transformers comme des applications entre mesures de probabilité (extension de champ moyen) plutôt que des séquences finies. Cela exploite l'équivariance par permutation des couches d'attention.
2. Partitionnement de l'Espace d'Embedding : L'espace d'embedding est partitionné en régions ($E_t$) correspondant au token suivant (ou à la séquence de tokens) le plus probable, basé sur la projection de sortie du décodeur.
3. Analyse des Nombres de Recouvrement (Packing Numbers) : Les auteurs utilisent le concept de nombres de recouvrement (le nombre maximal de boules disjointes d'un rayon donné pouvant tenir dans un espace) pour quantifier le nombre d'entrées distinctes qu'un Transformer peut distinguer.
   • Hypothèse de Précision Finie : Ils supposent que le Transformer possède une précision finie $\epsilon$, ce qui signifie qu'il ne peut pas distinguer des entrées plus proches que $\epsilon$ (modélisées comme des cubes alignés sur les axes ou des boules).
   • Support Borné : Ils supposent que le support de l'embedding est contenu dans une région bornée (par exemple, une boule de rayon $r$).
4. Déduction Théorique : En bornant le nombre de recouvrement de l'espace d'entrée par rapport au volume du support de l'embedding, ils dérivent des bornes supérieures sur le nombre de séquences accessibles.
5. Validation Empirique : Les prédictions théoriques sont testées à l'aide de la tâche "Cramming" (Kuratov et al., 2025), où un Transformer figé est conditionné par des prompts souples optimisés pour générer des séquences cibles spécifiques. Ils évaluent également des tâches de copie pour observer des échecs de généralisation dépendants de la longueur.

Contributions Clés

1. Accessibilité Finie des Séquences

L'article démontre qu'un Transformer ne peut produire qu'un ensemble fini de séquences distinctes, quelle que soit la longueur du prompt ou la stratégie d'inférence.

• Théorème 4.5 : Pour un Transformer de précision $\epsilon$, de rayon d'embedding $r$ et de longueur de prompt $m$, le nombre de séquences accessibles distinctes est borné supérieurement par $(1 + 2r/\epsilon)^{dm}$.
• Implication : La plupart des séquences sont fondamentalement inaccessibles ; aucun choix de prompt ne peut amener le modèle à les générer.

2. Échelle Linéaire et Décroissance Exponentielle

Les auteurs établissent une relation précise entre la longueur du prompt et la longueur maximale des séquences accessibles :

• Croissance Linéaire : La longueur maximale $n$ des séquences accessibles croît linéairement avec la longueur du prompt $m$ ($n \propto m$).
• Décroissance Exponentielle : Au-delà d'un seuil critique $N$, la proportion de séquences accessibles de longueur $n$ décroît exponentiellement avec $n$.
• Seuil Théorique : Ils dérivent une formule explicite pour ce seuil : $n^* \approx C \cdot m$, où $C$ dépend de la dimension de l'embedding $d$, de la taille du vocabulaire $|V|$, de la précision $\epsilon$ et du rayon du support $r$.

3. Explication des Échecs Empiriques

L'analyse fournit une explication théorique à l'"échec abrupt" observé en pratique (par exemple, une copie parfaite jusqu'à la longueur $L$, puis un échec total). L'article soutient qu'il ne s'agit pas d'une dégradation graduelle mais d'une conséquence de la décroissance exponentielle des séquences accessibles au-delà du seuil critique.

4. Bornes Raffinées par la Géométrie

Les auteurs affinent leurs bornes supérieures théoriques en assouplissant l'hypothèse d'un support d'embedding uniforme en forme de boule. Ils proposent :

• Supports Anisotropes : Modéliser le support comme des cônes ou des ellipsoïdes pour mieux capturer la distribution réelle des embeddings.
• Volumes de Cellules Non Uniformes : Prendre en compte le fait que les tokens courants occupent des régions plus vastes dans l'espace d'embedding que les tokens rares.
  Ces raffinements réduisent l'écart entre les bornes supérieures théoriques et les observations empiriques (d'un facteur d'environ 10 à environ 5–6).

Résultats

Prédictions Théoriques

• Corollaire 4.6 : Pour un budget de prompt fixe $m$, l'accessibilité reste élevée jusqu'à une longueur $n^*(m)$ puis chute exponentiellement. La pente de cette relation linéaire est bornée par $C \leq \frac{d \ln(1 + 2r/\epsilon)}{\ln(|V|)}$.
• Corollaire 4.10 : Même avec un contexte et un calcul illimités, il existe un seuil $N$ au-delà duquel presque toutes les séquences sont inaccessibles.

Validation Empirique

• Tâche Cramming : Les expériences sur des modèles (Pythia, Qwen-2.5, Llama-3.2, Gemma-3) montrent que la longueur $n_{50}$ (où l'accessibilité chute à 50 %) évolue linéairement avec le nombre de vecteurs de mémoire entraînables $m$ ($R^2 > 0,99$).
• Comparaison des Pentes : Les pentes observées empiriquement sont systématiquement inférieures aux bornes supérieures théoriques, le rapport entre théorie et expérience variant de 4,5 à 20,4 selon le modèle et les hypothèses géométriques utilisées.
• Tâche de Copie : Les modèles entraînés à copier des séquences jusqu'à la longueur 50 échouent abruptement lorsqu'ils sont testés sur des séquences plus longues, confirmant l'existence d'un seuil d'accessibilité net indépendant de la longueur du prompt.
• Distribution des Volumes de Cellules : L'analyse révèle que les volumes des cellules du décodeur sont fortement asymétriques ; un petit ensemble de tokens fréquents (par exemple, espaces, ponctuation) occupe une fraction disproportionnée de l'espace d'embedding, ce qui resserre les bornes d'accessibilité par rapport aux hypothèses uniformes.

Importance et Revendications

L'article revendique fournir la première explication théorique rigoureuse des limitations intrinsèques des Transformers sur les tâches de génération de séquences. Son importance réside dans :

1. Limites Architecturales : Démontrer que l'incapacité à copier de longues séquences est une propriété fondamentale de la précision finie et des représentations bornées de l'architecture, et non simplement un artefact d'entraînement.
2. Pouvoir Prédictif : Offrir une formule pour prédire les limites de performance d'un Transformer uniquement sur la base de la géométrie de son espace d'embedding (dimension, taille du vocabulaire, précision et forme du support), sans avoir besoin d'examiner l'ensemble complet des paramètres.
3. Généralisabilité : Les résultats s'étendent au-delà des Transformers à toute architecture possédant des représentations internes bornées et une précision finie (par exemple, les modèles à espace d'état comme Mamba, bien que les états cachés divergents posent des défis).

Les auteurs concluent que l'espace d'embedding, bien qu'il ne représente qu'une fraction des paramètres du modèle, porte des informations significatives sur les capacités et les limitations fondamentales du modèle.