Average Attention Transformers and Arithmetic Circuits

Résumé technique : Transformeurs à attention moyenne et circuits arithmétiques

Énoncé du problème
Les analyses théoriques existantes de l'expressivité des Transformeurs se sont principalement concentrées sur les problèmes de décision sur des alphabets finis, comparant les Transformeurs à des classes de circuits booléens (par exemple, $AC^0$, $TC^0$) ou à des formalismes logiques. Ces résultats se limitent à la reconnaissance de langages. Cet article comble une lacune dans la compréhension de la puissance computationnelle des Transformeurs en tant que fonctions séquence-à-séquence opérant sur des vecteurs de nombres réels ou rationnels. Les auteurs visent à caractériser l'expressivité des encodeurs de Transformeurs en les comparant directement aux circuits arithmétiques, qui calculent des fonctions sur des semi-anneaux en utilisant des opérations telles que l'addition, la multiplication et la fonction signe.

Méthodologie
Les auteurs adaptent un modèle de Transformeur généralisé (basé sur Hao et al., 2022) pour opérer sur des semi-anneaux arbitraires. Les choix méthodologiques clés incluent :

1. Définition du modèle : Ils définissent des « transformeurs de circuits à attention moyenne », où les réseaux de neurones feed-forward standards sont remplacés par des circuits arithmétiques, et le mécanisme d'attention utilise une « attention dure moyenne » (portant attention à tous les vecteurs ayant les scores d'attention maximaux).
2. Familles de circuits : Ils analysent trois classes de familles de circuits arithmétiques à profondeur constante et taille polynomiale :
   • $FNC^0_R$ : Entrées limitées (fan-in borné).
   • $FSAC^0_R$ : Entrées semi-illimitées (addition illimitée, multiplication binaire).
   • $FAC^0_R$ : Entrées illimitées (addition et multiplication illimitées).
     Ces classes sont étendues avec la fonction sign pour gérer les opérations discontinues.
3. Construction de la simulation :
   • Circuits vers Transformeurs : Pour simuler un circuit, les auteurs encodent la structure du graphe du circuit (portes et arêtes) dans une séquence de vecteurs. Chaque vecteur représente une arête ou une porte, contenant des indices pour les prédécesseurs/successeurs, les types de portes et les valeurs.
   • Mécanismes d'attention : Ils conçoivent des fonctions d'attention spécifiques ($f^{att}_E$ et $f^{att}_V$) permettant aux vecteurs de porter attention à leurs prédécesseurs sur la base d'une correspondance d'indices.
   • Regroupement et activation : Ils utilisent un regroupement par attention dure moyenne pour agréger les valeurs des prédécesseurs. Crucialement, ils construisent des fonctions d'activation qui sélectionnent l'opération appropriée (addition, multiplication ou identité) en fonction du type de porte encodé dans le vecteur.
   • Gestion de la mise à l'échelle : Puisque l'attention moyenne met à l'échelle les résultats par $1/k$ (où $k$ est le nombre de vecteurs auxquels on porte attention), la construction inclut des mécanismes pour compter les prédécesseurs et re-mettre à l'échelle la sortie afin de retrouver la valeur arithmétique correcte.

Résultats clés
L'article établit une correspondance précise entre la puissance computationnelle de ces Transformeurs spécifiques et les classes de circuits arithmétiques :

1. Majoration : Pour tout semi-anneau $R$, les fonctions calculées par les transformeurs de circuits à attention moyenne sont contenues dans la classe $FSAC^0_R[\text{sign}]$. Cela vaut même pour les Transformeurs standards avec une attention moyenne typique, à condition que leurs fonctions d'activation soient restreintes à la même classe de circuits.
2. Minoration (Simulation) : Si le semi-anneau sous-jacent $R$ est une extension d'anneau ordonné par $\mathbb{Z}$ des rationnels ($\mathbb{Q}$), alors pour toute famille de circuits dans $FSAC^0_R[\text{sign}]$ de profondeur $K$, il existe un Transformeur à $2K$ couches capable de simuler l'ensemble de la famille.
   • La simulation fonctionne pour les circuits à entrées illimitées en utilisant l'attention moyenne.
   • Pour les circuits à entrées semi-illimitées, la construction peut être adaptée pour utiliser l'attention par produit scalaire standard.
   • Pour les circuits à entrées limitées, la construction peut être davantage restreinte pour utiliser une attention dure gauche ou droite.
3. Théorèmes spécifiques :
   • Théorème 4.5 : Un Transformeur de dimension 7 et $2K$ couches peut simuler tout circuit $R$ à entrées illimitées de profondeur $\le K$ (où $R$ est une extension ordonnée par $\mathbb{Z}$ de $\mathbb{Q}$).
   • Théorème 4.11 : Un Transformeur de dimension 9 et $2K$ couches peut simuler tout circuit $FSAC^0_R[\text{sign}]$.

Portée et affirmations
Les auteurs affirment que leurs résultats offrent une nouvelle perspective sur l'expressivité des Transformeurs en faisant le pont entre les domaines de la théorie de l'apprentissage automatique et du calcul algébrique.

• Équivalence théorique : Ils démontrent que les Transformeurs à attention moyenne sont computationnellement équivalents à la classe des circuits arithmétiques à profondeur constante avec addition illimitée, multiplication binaire et portes signe ($FSAC^0_R[\text{sign}]$).
• Limites : L'article note explicitement que cette équivalence repose sur l'utilisation par le Transformeur de circuits arithmétiques (ou de fonctions équivalentes) comme fonctions d'activation. Les Transformeurs standards avec des réseaux feed-forward ne peuvent pas simuler ces circuits car les réseaux feed-forward ne peuvent pas intrinsèquement effectuer la multiplication de deux entrées arbitraires requise pour la simulation.
• Non-uniformité : Les auteurs précisent que, bien que les Transformeurs puissent simuler des familles de circuits spécifiques, cela n'implique pas que chaque fonction dans $FSAC^0_R[\text{sign}]$ soit calculée par un seul Transformeur, car les familles de circuits constituent un modèle de calcul non uniforme.
• Potentiel futur : L'article suggère que les avancées théoriques en calcul algébrique pourraient bénéficier à la théorie de l'apprentissage automatique et vice versa, et que les résultats théoriques pourraient inspirer des développements pratiques, bien qu'aucune application spécifique ne soit proposée.

Le travail est présenté sous forme d'un prépublication (mai 2026) de l'Institut d'informatique théorique de l'Université Leibniz de Hanovre.