Characterizing the Expressivity of Local Attention in Transformers

1. Énoncé du problème

L'architecture Transformer repose sur un mécanisme d'attention globale, qui agrège des informations de tous les tokens précédents, entraînant une complexité computationnelle quadratique ($O(N^2)$). Pour y remédier, l'attention locale restreint l'agrégation à une fenêtre de taille fixe de prédécesseurs, réduisant la complexité à linéaire ($O(N)$).

Bien que l'attention locale soit principalement motivée par l'efficacité, des études empiriques ont montré qu'elle améliore souvent la qualité du modèle (par exemple, en traduction automatique et en modélisation du langage) même lorsque les budgets computationnels sont maintenus constants. Cela pose un puzzle théorique : Pourquoi la restriction du champ récepteur (un mécanisme apparemment « plus faible ») conduit-elle parfois à de meilleures performances ?

Les auteurs visent à résoudre cela en caractérisant formellement l'expressivité de différents motifs d'attention (globale, locale et hybride) en termes des langages formels qu'ils peuvent reconnaître.

2. Méthodologie

Le papier adopte une approche de la théorie des langages formels, reliant les architectures Transformer à la Logique Temporelle Linéaire (LTL) et à la théorie des automates algébriques.

• Cadre théorique :

  • Les auteurs analysent les Transformers à précision fixe en tant que reconnaisseurs de langages.
  • Ils mappent les mécanismes d'attention sur des fragments de LTL :
    • Attention Globale : Correspond à LTL[P] (Opérateur Passé), qui permet de regarder arbitrairement loin dans le passé mais seulement vers l'existence d'un événement passé.
    • Attention Locale (taille de fenêtre $k$) : Correspond à LTL[$Y_{\le k}$] (Opérateur Hier Borné), qui vérifie si une condition était vraie au cours des $k$ dernières étapes.
    • Attention Hybride : Correspond à LTL[P, $Y_{\le k}$], combinant les deux opérateurs.
  • Ils utilisent des caractérisations algébriques (semi-groupes syntaxiques, monoïdes syntaxiques) et des propriétés théoriques des automates (configurations d'AFD) pour prouver des séparations strictes entre ces fragments logiques.

• Validation expérimentale :

  • Reconnaissance de langages formels : Les auteurs ont entraîné des Transformers à reconnaître des classes spécifiques de langages formels (par exemple, des chaînes se terminant par 'a', des chaînes contenant 'ab', des langages de Dyck bornés) avec des longueurs variables pour tester la généralisation.
  • Modélisation du langage naturel : Ils ont mené des expériences légères de prédiction du token suivant sur le jeu de données WikiText-2 en utilisant des architectures de style GPT-2-small.
  • Variables : Ils ont comparé trois motifs d'attention (Uniquement Global, Uniquement Local, Hybride) à travers différentes tailles de fenêtres ($k \in \{1, 2, 4, \dots\}$) et encodages de position (Appris, RoPE, SiPE).

3. Contributions clés

A. Caractérisation théorique

1. Attention Globale = LTL[P] : Réaffirme que l'attention globale correspond à la logique avec un seul opérateur passé, capable de reconnaître les polynômes déterministes à gauche mais échouant sur certaines tâches basées sur les suffixes.
2. Attention Locale = LTL[$Y_{\le k}$] : Prouve que l'attention locale correspond à une logique temporelle bornée. Crucialement, ils montrent que LTL[P] et LTL[$Y_{\le k}$] sont incomparables.
   • L'attention globale ne peut pas reconnaître les langages définis par des suffixes spécifiques (par exemple, des chaînes se terminant par 'a').
   • L'attention locale ne peut pas reconnaître les langages définis par des préfixes spécifiques (par exemple, des chaînes commençant par 'a').
3. Attention Hybride = LTL[P, $Y_{\le k}$] : Démontre que la combinaison de l'attention globale et locale élargit strictement la classe des langages réguliers reconnaissables. Le modèle hybride peut reconnaître les Langages Localement Testables (un sur-ensemble des langages définis), que ni l'attention purement globale ni l'attention purement locale ne peuvent entièrement capturer.
4. Optimalité de la taille de fenêtre $k=1$ : Prouve théoriquement que, au sein de la famille de l'attention locale, une taille de fenêtre de $k=1$ (regardant uniquement le prédécesseur immédiat) est strictement plus expressive que des fenêtres plus grandes ($k > 1$) en l'absence d'encodages de position. Cela s'explique par le fait que $k=1$ introduit l'opérateur « Hier » ($Y$), qui est l'opérateur local le plus puissant.

B. Résultats empiriques

1. Généralisation sur les langages formels :

   • Les modèles hybrides (spécifiquement avec $k=1$) ont atteint une généralisation parfaite (100 % de précision) sur tous les langages définissables dans LTL[P, Y], y compris ceux qui échouaient pour les modèles uniquement globaux ou uniquement locaux.
   • Les modèles Uniquement Globaux ont échoué sur les tâches basées sur les suffixes (LTL[Y]).
   • Les modèles Uniquement Locaux ont échoué sur les tâches basées sur les préfixes (LTL[P]).
   • Taille de fenêtre : $k=1$ a systématiquement surpassé $k=2$ et $k=4$ en l'absence d'encodages de position.

2. Langage naturel (WikiText-2) :

   • L'attention hybride avec $k=1$ a systématiquement atteint la perplexité la plus faible parmi tous les schémas d'encodage de position (Appris, RoPE, SiPE).
   • L'écart de performance entre les modèles hybrides et uniquement globaux était significatif (par exemple, une réduction d'environ 69 points de perplexité avec des plongements appris).
   • Fait intéressant, les modèles uniquement locaux ont parfois surpassé les modèles uniquement globaux, soutenant la théorie selon laquelle ils sont complémentaires plutôt que l'un étant strictement « meilleur » que l'autre.

3. Rôle des encodages de position :

   • Les écarts théoriques entre l'attention locale $k=1$ et $k>1$ peuvent être comblés si les encodages de position agissent comme des « prédicats modulaires » (permettant au modèle de compter les étapes).
   • Cependant, dans la pratique, les encodages standards (RoPE, SiPE) n'ont pas entièrement compensé le manque d'attention locale, et les modèles hybrides sont restés supérieurs.

4. Signification

• Résolution du « paradoxe de l'attention locale » : Le papier fournit la première explication formelle de pourquoi l'attention locale améliore les performances. Il ne s'agit pas simplement d'une optimisation de vitesse ; elle introduit un biais inductif complémentaire (la capacité à suivre les prédécesseurs immédiats via l'opérateur $Y$) que l'attention globale ne possède pas.
• Directives de conception : Les résultats suggèrent fortement que les architectures hybrides (mélangeant des têtes globales et locales) sont théoriquement et empiriquement supérieures. De plus, ils préconisent l'utilisation d'une taille de fenêtre de 1 pour les têtes locales, car cela maximise l'expressivité en capturant le prédécesseur immédiat sans la surcharge de profondeur des fenêtres plus grandes.
• Pont théorique : Ce travail consolide le lien entre la conception d'architectures neuronales et la logique formelle, offrant une lentille rigoureuse pour prédire les capacités des modèles sur des tâches nécessitant des types spécifiques de dépendances à long terme ou locales.

En résumé, les auteurs démontrent que l'attention locale n'est pas une dégradation de l'attention globale mais un complément nécessaire. En combinant la vue globale (existence passée) avec la vue locale (histoire immédiate), les Transformers hybrides atteignent le fragment le plus riche de la reconnaissance des langages réguliers, conduisant à des performances supérieures tant dans les tâches formelles que dans la modélisation du langage naturel.