Parity, Sensitivity, and Transformers

Sur la base du texte fourni, voici un résumé technique détaillé de l'article « Parity, Sensitivity, and Transformers ».

Énoncé du problème

L'article aborde la question fondamentale de l'expressivité des architectures Transformer, spécifiquement concernant la tâche PARITY. La PARITY est une fonction booléenne qui renvoie 1 si le nombre de 1 dans une séquence d'entrée binaire est impair, et 0 sinon. C'est un problème canonique en informatique théorique, connu pour sa haute sensibilité (inverser un seul bit change la sortie).

Alors que des recherches antérieures ont établi que les Transformers dotés de mécanismes d'attention dure (spécifiquement Unique Hard Attention ou UHAT) ne peuvent pas calculer la PARITY en profondeur constante, les capacités des Transformers avec attention douce (softmax) restent moins claires. Les constructions existantes pour des Transformers à attention douce capables de calculer la PARITY reposent sur des hypothèses « impraticables », telles que :

• Des encodages de position dépendant de la longueur totale de l'entrée ($n$).
• Des mécanismes d'attention dure.
• Une normalisation de couche avec un paramètre de régularisation $\epsilon = 0$.
• Une incompatibilité avec le masquage causal.

De plus, il restait un problème ouvert de savoir si un Transformer à couche unique pouvait calculer la PARITY.

Méthodologie

Les auteurs emploient deux approches méthodologiques distinctes pour traiter la borne inférieure et la borne supérieure (construction) de l'expressivité des Transformers pour la PARITY.

1. Borne inférieure via la sensibilité moyenne
Pour prouver qu'un Transformer à une seule couche ne peut pas calculer la PARITY, les auteurs utilisent le concept de sensibilité moyenne.

• Définition : La sensibilité moyenne d'une fonction $f$ est le nombre attendu de positions de bits d'entrée telles que l'inversion du bit change la sortie de la fonction. Pour la PARITY, cette valeur est exactement $n$ (croissance linéaire).
• Logique : Les auteurs modélisent le calcul d'un Transformer à une seule couche comme une fonction exprimable dans la logique du premier ordre des nombres réels $(\mathbb{R}, <, +, \cdot)$. En appliquant le théorème de Tarski-Seidenberg (élimination des quantificateurs), ils démontrent que toute fonction calculée par un Transformer à une seule couche peut être représentée comme une combinaison booléenne d'un nombre fixe de fonctions de seuil polynomiales de bas degré (PTF).
• Bornage : Citant un résultat de Kane, ils établissent que la sensibilité moyenne des PTF de bas degré croît à un taux de $O(\sqrt{n} \cdot (\log n)^{O(1)})$. Puisque la sensibilité moyenne de la PARITY croît linéairement ($n$), un Transformer à une seule couche ne peut pas la calculer.

2. Borne supérieure via une nouvelle construction
Pour démontrer que la PARITY est calculable par un Transformer sans hypothèses impraticables, les auteurs proposent une nouvelle construction à quatre couches.

• Mécanisme : La construction utilise une attention softmax et des encodages de position indépendants de la longueur et bornés polynomialement. Elle évite la normalisation de couche et fonctionne aussi bien avec l'attention complète qu'avec le masquage causal.
• Stratégie algorithmique :
  1. Couche 1 : Calcule une somme pondérée des bits d'entrée pour dériver une valeur $\gamma$ liée au nombre de 1 ($\Sigma$).
  2. Couche 2 : Utilise les encodages de position ($i \mapsto (\ln i, i^{10})$) et la valeur $\gamma$ pour calculer une moyenne pondérée $\Gamma$. Cette valeur approxime une fonction $f(\rho)$ qui encode des informations sur $\Sigma$.
  3. Couche 3 : Construit des poids d'attention $L_{i,n}$ fortement concentrés sur la position $i = \Sigma$. Cela est réalisé en utilisant la valeur $\Gamma$ (calculée à la couche 2) pour approximer une forme quadratique spécifique qui atteint un pic à $i = \Sigma$. Les auteurs prouvent que pour la position correcte, le poids d'attention est significativement plus grand (avec une marge de $\Omega(n^6)$) que pour toute autre position.
  4. Couche 4 : Calcule une somme pondérée de $(-1)^i$ en utilisant les poids d'attention concentrés. Le résultat est une valeur $z$ proche de $(-1)^\Sigma$, permettant à la couche finale de distinguer la parité paire et impaire.
• Gestion des grandes entrées : Pour gérer les cas où le nombre de 1 ($\Sigma$) est grand, la construction divise l'entrée en $M$ sous-séquences (où $M$ est une constante paire), calcule la parité de chacune en parallèle, et agrège les résultats.

Contributions et résultats clés

1. Résolution du problème ouvert de la couche unique : L'article répond définitivement à la question ouverte de savoir si un Transformer à une seule couche peut calculer la PARITY. Le résultat est négatif. Les auteurs prouvent que la sensibilité moyenne de toute fonction calculable par un Transformer à une seule couche est bornée par $O(\sqrt{n} \cdot (\log n)^{O(1)})$, ce qui est insuffisant pour la sensibilité linéaire de la PARITY.
2. Construction améliorée pour la PARITY : Les auteurs présentent une nouvelle construction de Transformer à quatre couches qui calcule la PARITY. Cette construction améliore les travaux antérieurs (par exemple, Chiang et Cholak, 2022 ; Yang et al., 2025) en éliminant plusieurs hypothèses restrictives :
   • Elle utilise une attention douce (softmax) plutôt qu'une attention dure.
   • Elle emploie des encodages de position indépendants de la longueur.
   • Elle ne nécessite aucune normalisation de couche (ou spécifiquement, ne repose pas sur $\epsilon=0$).
   • Elle est compatible avec le masquage causal.
   • Les encodages de position sont bornés polynomialement, les rendant réalisables pour des longueurs d'entrée pratiques.
3. Exigences de profondeur : L'article établit que si une couche est insuffisante, quatre couches sont suffisantes sous des contraintes de conception réalistes. Cela affine la compréhension des exigences de profondeur pour le calcul de fonctions hautement sensibles.

Importance

L'article fait progresser la compréhension théorique des architectures Transformer en caractérisant précisément leurs exigences de profondeur pour la tâche PARITY. En reliant l'expressivité des Transformers à la sensibilité moyenne des fonctions booléennes, les auteurs fournissent une borne inférieure rigoureuse qui exclut les modèles à une seule couche. Parallèlement, en fournissant une construction à quatre couches qui respecte les pratiques architecturales standard (attention douce, masquage causal, encodages bornés), l'article démontre que la PARITY est calculable par des Transformers sans recourir à des artefacts théoriques.

Les auteurs notent que ces résultats aident à expliquer pourquoi les Transformers pourraient avoir du mal à généraliser sur des tâches comme la PARITY lors de l'entraînement : la fonction nécessite une profondeur et une configuration architecturale spécifiques qui peuvent ne pas être facilement apprises via des méthodes standard de descente de gradient si le modèle est trop peu profond ou contraint. Ce travail complète la littérature existante sur l'expressivité des modèles à attention dure et fournit une référence plus réaliste pour les capacités des Transformers à attention douce.