Length Generalization Bounds for Transformers

Cet article résout le problème de la calculabilité des bornes de généralisation en longueur pour les transformateurs en démontrant l'inexistence de telles bornes calculables pour la classe CRASP (déjà à deux couches), tout en établissant une borne calculable optimale exponentielle pour son fragment positif équivalent aux transformateurs à précision fixe.

L'essentiel

Imaginez que vous essayez d'enseigner à un robot (un Transformeur, le cerveau derrière des IA comme nous) comment lire et comprendre des histoires.

Le Problème : La "Mémoire" du Robot

Le défi principal est le suivant : si vous n'enseignez au robot que des phrases courtes (par exemple, des phrases de 10 mots), réussira-t-il à comprendre une phrase de 100 mots ou même de 1000 mots ? C'est ce qu'on appelle la généralisation de la longueur.

Dans le monde réel, les robots apprennent souvent sur des textes courts (à cause de la mémoire limitée), mais on s'attend à ce qu'ils fonctionnent sur des romans entiers. Parfois, ça marche, parfois ça échoue complètement. Les chercheurs se demandent : pouvons-nous prédire avec certitude jusqu'où ce robot pourra aller ?

La Grande Découverte : "Non, on ne peut pas le prédire !"

Les auteurs de ce papier ont découvert une nouvelle très surprenante, un peu comme si on découvrait qu'il est impossible de savoir si un jeu de construction est stable avant de l'avoir essayé.

1. Le Cas Général (Le Robot Complexe) :
   Pour les transformeurs standards (ceux qui sont très puissants et complexes), les chercheurs ont prouvé qu'il est mathématiquement impossible de calculer une limite de sécurité.

   • L'analogie : Imaginez que vous essayez de deviner si un labyrinthe infini a une sortie. Les auteurs montrent que pour certains types de labyrinthes (ceux que les transformeurs peuvent créer), il n'existe aucune formule magique ni aucun ordinateur capable de vous dire : "Si vous apprenez avec des phrases de moins de X mots, vous serez sûr de réussir avec des phrases de Y mots."
   • La limite pourrait être si énorme qu'elle dépasse l'âge de l'univers ou le nombre d'atomes dans le cosmos. C'est ce qu'on appelle une fonction "incomputable". En gros, on ne peut pas garantir qu'un robot apprendra bien, même si on lui donne beaucoup de données.

2. Le Cas Simplifié (Le Robot "Fixe") :
   Cependant, si on prend une version simplifiée du robot (appelée "Transformeur à précision fixe", où les calculs sont arrondis comme sur une calculatrice basique), la situation change.

   • L'analogie : C'est comme si on passait d'un ordinateur quantique mystérieux à une vieille calculatrice de poche.
   • Pour ce robot simplifié, on peut calculer la limite ! Mais attention, cette limite est exponentielle.
   • Ce que ça veut dire : Si votre robot a une taille de "mémoire" de 10 unités, il faudra peut-être lui montrer des phrases de $2^{10}$ (1024) mots pour qu'il apprenne. Si sa taille est de 20, il faudra des phrases de $2^{20}$ (plus d'un million de mots). C'est énorme, mais au moins, on sait que c'est calculable.

Pourquoi est-ce important ?

Jusqu'à présent, les ingénieurs pensaient que si on augmentait la taille du modèle ou la quantité de données, le robot deviendrait automatiquement meilleur pour comprendre les longs textes. Ce papier dit : "Non, ce n'est pas si simple."

• Pour les chercheurs : Cela explique pourquoi l'apprentissage est si difficile et imprévisible. Parfois, le robot échoue non pas parce qu'il est "bête", mais parce que la tâche demande de voir des exemples d'une longueur si astronomique qu'il est impossible de les générer pour l'entraînement.
• Pour le grand public : Cela nous rappelle que l'IA actuelle a des limites fondamentales. On ne peut pas simplement "ajouter plus de données" pour résoudre tous les problèmes de compréhension de texte long. Il faut changer la façon dont on conçoit ces robots.

En résumé

• Le problème : Peut-on garantir qu'un IA comprendra de longs textes après avoir appris sur des courts ?
• La réponse pour les IA complexes : Non, c'est impossible à calculer. C'est comme essayer de prédire le temps qu'il fera dans un million d'années avec une précision parfaite : c'est mathématiquement interdit.
• La réponse pour les IA simplifiées : Oui, on peut le calculer, mais il faudra probablement entraîner l'IA sur des textes d'une longueur astronomique (exponentielle) pour que ça fonctionne parfaitement.

C'est une découverte qui met un frein à l'optimisme naïf : pour que les robots comprennent vraiment de longs textes, nous devons soit accepter qu'ils échouent parfois, soit trouver des moyens de les entraîner sur des quantités de données qui dépassent l'entendement humain.

Résumé technique

1. Problématique

La généralisation en longueur (length generalization) est la capacité d'un algorithme d'apprentissage à faire des prédictions correctes sur des entrées de longueur arbitraire, après avoir été entraîné uniquement sur un ensemble fini de données de longueur bornée. Bien que les Transformers montrent des capacités impressionnantes, leur capacité à généraliser en longueur varie considérablement selon la tâche et reste souvent partielle ou sensible aux hyperparamètres.

Le problème central abordé par cet article est l'existence et le calcul de bornes de généralisation en longueur non asymptotiques.

• Une telle borne $N$ garantirait qu'un algorithme d'apprentissage n'a besoin que de données d'entraînement de longueur jusqu'à $N$ pour apprendre parfaitement un langage et généraliser à toutes les longueurs supérieures.
• Si une telle borne est calculable, l'apprentissage parfait est théoriquement possible.
• L'article se concentre sur la classe des langages C-RASP (Counting RASP), qui est expressivement équivalente aux Transformers (avec une précision fixe hors attention), et examine si ces bornes sont calculables pour cette classe.

2. Méthodologie

Les auteurs utilisent une approche basée sur la théorie de l'apprentissage computationnel et la théorie de la complexité, reliant la généralisation en longueur à la décidabilité de problèmes logiques.

• Équivalence Fondamentale : Ils s'appuient sur le résultat de Chen et al. (2025) établissant que la généralisation en longueur non asymptotique est équivalente à la décidabilité du problème d'équivalence de langages pour une classe de langages donnée. Si l'on ne peut pas décider si deux programmes définissent le même langage, on ne peut pas calculer la borne de longueur nécessaire pour l'apprentissage.
• Réduction à l'Hypothèse de Hilbert : Pour prouver l'impossibilité de calculer ces bornes, les auteurs réduisent le problème de l'emptiness (langage vide ou non) des programmes C-RASP au 10ème problème de Hilbert (solvabilité des équations diophantiennes), qui est connu pour être indécidable (résultat de Matiyasevich).
• Analyse de Fragments Positifs : Pour contrebalancer ce résultat négatif, ils étudient un sous-ensemble restreint de C-RASP, noté C-RASP+, où les constantes et les opérations sont limitées de manière à ne permettre que le comptage jusqu'à un seuil. Ils établissent une équivalence entre C-RASP+ et la logique temporelle TL[-3] (logique temporelle avec opérateur "strictement passé").
• Modélisation des Transformers : Ils distinguent deux variantes de Transformers :
  1. Les Transformers standards (précision finie hors attention, mais attention non arrondie).
  2. Les Transformers à précision fixe (fixed-precision), où l'attention elle-même est arrondie.

3. Contributions Clés et Résultats

A. Impossibilité pour les Transformers Généraux (et C-RASP)

Le résultat principal est une preuve de non-existence de bornes calculables pour la généralisation en longueur.

• Théorème 1.1 : Il n'existe aucun algorithme capable d'apprendre parfaitement un programme C-RASP (même avec seulement deux couches) à partir de données d'entraînement de longueur bornée.
• Preuve : Le problème de l'emptiness pour C-RASP est indécidable (réduction depuis le 10ème problème de Hilbert). Par conséquent, le problème d'équivalence de langages est indécidable, ce qui implique que la complexité en longueur n'est pas bornée par une fonction calculable (elle croît plus vite que toute fonction calculable, y compris la fonction d'Ackermann).
• Conséquence pour les Transformers : Puisque les Transformers (même à 2 couches) sont expressivement équivalents à C-RASP, aucun algorithme d'apprentissage ne peut garantir de savoir si un Transformer a vu assez de données pour généraliser parfaitement.

B. Bornes Calculables pour le Fragment Positif (C-RASP+)

Pour le fragment restreint C-RASP+ (équivalent aux Transformers à précision fixe), les auteurs obtiennent un résultat positif.

• Théorème 1.2 : Pour apprendre parfaitement un programme C-RASP+, il est nécessaire et suffisant de voir des chaînes d'entraînement dont la longueur est exponentielle par rapport à la taille du programme.
• Méthode : Ils montrent que C-RASP+ peut être réduit à la logique temporelle TL[-3]. Bien que cette traduction entraîne un gonflement exponentiel de la taille de la formule, la logique TL[-3] possède la propriété que tout langage non vide contient une chaîne témoin dont la longueur est polynomiale par rapport à la taille de la formule.
• Optimalité : Ils prouvent que cette borne exponentielle est optimale dans le pire des cas (ex: langage $\{a^n\}$ où $n$ est encodé en binaire).

C. Implications pour les Transformers à Précision Fixe

• Théorème 5.2 : Les Transformers à précision fixe admettent une généralisation en longueur avec une complexité exponentielle.
• Résultat : Tout algorithme d'apprentissage pour ces modèles doit potentiellement vérifier des chaînes de longueur exponentielle avant d'identifier la solution vraie capable de généraliser.

4. Signification et Impact

• Explication Théorique des Échecs Empiriques : Ces résultats offrent une explication fondamentale à la difficulté observée de la généralisation en longueur. Ce n'est pas seulement un problème d'optimisation ou d'initialisation, mais une limitation théorique inhérente : pour apprendre parfaitement certaines tâches, un modèle pourrait avoir besoin de voir des séquences de longueur infiniment grande (au-delà de toute fonction calculable) ou au moins exponentiellement grande.
• Distinction Cruciale : L'article met en lumière une différence fondamentale entre les Transformers standards (indécidables pour la généralisation parfaite) et les Transformers à précision fixe (décidables mais avec des coûts exponentiels).
• Limites des Lois d'Échelle (Scaling Laws) : Les auteurs soulignent que les lois d'échelle conventionnelles, qui prédisent la perte en fonction de la taille du modèle et des données, échouent à prédire la généralisation en longueur. Une nouvelle cadre théorique est nécessaire pour comprendre ces limites.
• Implications Pratiques : Cela suggère que l'amélioration de la généralisation en longueur ne peut pas être résolue uniquement par l'augmentation de la taille des modèles ou des données, mais nécessite peut-être des changements d'architecture (comme la restriction de la précision) ou des méthodes d'apprentissage spécifiques qui exploitent la structure du problème.

En résumé, l'article démontre que la généralisation parfaite en longueur pour les Transformers généraux est théoriquement impossible à garantir algorithmiquement, tandis que pour des versions à précision fixe, elle est possible mais nécessite des ressources d'entraînement exponentielles.