Résumé Technique : Interpolation de Séquences Exactes avec des Transformers

1. Énoncé du Problème

L'article aborde le problème d'interpolation exacte pour les transformers dans le contexte de la mise en correspondance séquence-à-séquence. Plus précisément, étant donné un ensemble de données de $N$ paires entrée-sortie de séquences $\{(X_j, Y_j)\}_{j=1}^N$, où $X_j \in (\mathbb{R}^d)^{n_j}$ et $Y_j \in (\mathbb{R}^d)^{m_j}$ avec $m_j \le n_j$, l'objectif est de construire une architecture de transformer $T$ telle que $T(X_j) = Y_j$ pour tout $j$.

Un aspect critique de la formulation du problème est la définition de l'égalité entre les séquences. Les auteurs traitent les séquences comme des ensembles non ordonnés (équivariants par permutation), ce qui signifie que $T(X_j) = Y_j$ est vérifié si l'ensemble des tokens de la séquence de sortie correspond à l'ensemble des tokens de la séquence cible $Y_j$ (mesuré via la distance de Hausdorff). Cette formulation prend en charge des tâches où la longueur de sortie est strictement inférieure à la longueur d'entrée (par exemple, la modélisation du langage masquée ou l'inpainting d'images), un scénario où les modèles séquence-à-séquence standards préservant la longueur font face à un décalage.

L'étude suppose :

1. Les séquences d'entrée sont distinctes deux à deux.
2. Les tokens au sein de chaque séquence d'entrée sont distincts deux à deux.
3. Les tokens au sein de chaque séquence de sortie sont distincts deux à deux.

L'analyse est menée pour des dimensions $d \ge 2$ (spécifiquement $d \ge 20$ pour les preuves constructives principales) et considère les mécanismes d'attention hardmax (limite du softmax lorsque la température $\tau \to 0$) et softmax.

2. Méthodologie

Les auteurs fournissent une preuve constructive démontrant que des architectures de transformers spécifiques peuvent interpoler exactement n'importe quel tel ensemble de données. La méthodologie repose sur l'alternance de couches feed-forward (FF) et de couches d'attention (SA) pour manipuler géométriquement les positions des tokens.

2.1 Architecture

Le transformer est composé de $L$ blocs, où chaque bloc est une composition d'une couche FF et d'une couche SA.

• Couches Feed-Forward : Définies par $FF(x) = \eta x + W\sigma(Ux + b)$, où $\sigma$ est l'activation ReLU. Les auteurs soulignent l'importance du paramètre résiduel ajustable $\eta$ et de la capacité à utiliser des réseaux de faible largeur ($d' \le 4$).
• Couches d'Attention : Définies par $SA_i(X) = \rho x_i + V \sum_{\ell} \pi_{i\ell}(X, A) x_\ell$.
  • Configuration Hardmax : Les poids d'attention $\pi_{i\ell}$ sélectionnent les tokens ayant le produit scalaire maximal $\langle A x_i, x_\ell \rangle$. Les auteurs utilisent une structure spécifique pour la matrice $A$ (matrice de rang un ou multiples scalaires de l'identité) pour induire des comportements de regroupement spécifiques.
  • Configuration Softmax : L'attention softmax standard est utilisée. Les auteurs montrent que bien que le softmax ne permette pas un « effondrement » exact en une seule étape (contrairement au hardmax), une interpolation exacte peut tout de même être obtenue en combinant l'attention softmax avec des constructions spécifiques de couches FF.

2.2 Stratégie Géométrique

La construction procède par quatre phases géométriques distinctes, utilisant des lemmes spécifiques pour manipuler la configuration des tokens :

1. Séparation : En utilisant $O(N)$ blocs, le transformer sépare les tokens de différentes séquences d'entrée qui pourraient se chevaucher dans la configuration initiale. Cela implique de déplacer les tokens pour s'assurer que les séquences deviennent des ensembles disjoints deux à deux.
2. Sélection de Leaders : Le transformer déplace tous les tokens dans une région géométrique spécifique (le premier orthant). Il sélectionne ensuite $m_j$ tokens « leaders » pour chaque séquence $X_j$ et les positionne soigneusement :
   • Un leader est placé dans une région spécifique $P$ (loin de l'origine).
   • Les $m_j - 1$ leaders restants sont placés sur une hypersphère dans l'orthant négatif.
   • Les tokens non leaders sont positionnés de manière à être attirés par les leaders.
3. Effondrement :
   • Hardmax : Une seule couche SA avec des paramètres spécifiques provoque l'effondrement exact de tous les tokens non leaders sur leurs leaders respectifs en raison de l'effet de regroupement de l'attention hardmax.
   • Softmax : Puisque le softmax produit une combinaison convexe stricte, un effondrement exact est impossible en une seule étape. Les auteurs introduisent un supplément de $O(N)$ blocs utilisant des couches FF non résiduelles avec des activations ReLU pour effondrer itérativement de petits voisinages de tokens sur les leaders.
4. Interpolation : Une fois les séquences effondrées en $m_j$ tokens uniques, des couches FF standard (agissant comme des « fonctions chapeau ») déplacent individuellement ces tokens vers leurs positions finales cibles dans $Y_j$.

3. Contributions Clés

3.1 Interpolation Exacte avec Sorties à Valeurs Réelles

L'article prouve que les transformers peuvent interpoler exactement des applications arbitraires de séquence-à-séquence à vecteurs réels. Cela surmonte les limitations précédentes de la littérature qui étaient restreintes à des sorties discrètes ou ne fournissaient qu'une interpolation approximative.

3.2 Complexité Indépendante de la Longueur d'Entrée

Une découverte centrale est que la taille requise du transformer dépend uniquement de la longueur totale de sortie ($\sum m_j$) et de la dimension d'encodage $d$, mais pas des longueurs des séquences d'entrée ($n_j$).

• Nombre de Paramètres : $P = O(d \sum_{j=1}^N m_j)$.
• Nombre de Blocs : $L = O(\sum m_j + N)$.
  Cela contraste avec les approches traditionnelles (comme les ResNets) où la complexité évolue généralement avec la longueur d'entrée $n$. Cela explique l'efficacité des transformers dans des tâches comme le résumé où $m_j \ll n_j$.

3.3 Efficacité des Paramètres via une Attention de Rang Faible

La construction utilise des matrices de paramètres de rang faible dans le mécanisme d'attention (spécifiquement, $A$ est la somme d'une matrice de rang un et d'un multiple de l'identité). Cela s'aligne avec les conceptions de transformers efficaces pratiques et garantit que le nombre de paramètres croît linéairement avec $d$.

3.4 Implications pour l'Entraînement Régularisé

L'existence de transformers interpolant exactement fournit une base théorique pour l'entraînement régularisé. Les auteurs montrent que si un minimiseur global existe pour un objectif régularisé de Tikhonov, la perte d'entraînement évolue linéairement avec le paramètre de régularisation $\varepsilon$ lorsque $\varepsilon \to 0$. Les écarts par rapport à cette évolution peuvent servir de diagnostic pour déterminer si l'optimisation a convergé vers un minimum global ou local.

4. Résultats Principaux

Théorème 1.6 (Transformers Hardmax)

Pour tout ensemble de données satisfaisant les hypothèses de distinctivité, il existe un transformer hardmax avec :

• Largeur $d' \le 4$.
• Blocs $L = 2 \sum_{j=1}^N m_j + 2N + 1$.
• Paramètres $P = O(d \sum_{j=1}^N m_j)$.
  Tel que $T_0(X_j) = Y_j$ pour tout $j$.

Théorème 1.8 (Transformers Softmax)

Pour le même ensemble de données, il existe une température $\tau^* > 0$ telle que pour tout $0 < \tau < \tau^*$, il existe un transformer softmax avec :

• Largeur $d' \le 4$.
• Blocs $L = 2 \sum_{j=1}^N m_j + 3N$.
• Paramètres $P = O(d \sum_{j=1}^N m_j)$.
  Tel que $T_\tau(X_j) = Y_j$ pour tout $j$.
  Note : La preuve pour le softmax nécessite un supplément de $N-1$ blocs par rapport au hardmax pour gérer l'absence d'effondrement exact dans la couche d'attention.

5. Importance et Revendications

L'article revendique fournir le premier résultat d'interpolation exacte pour des transformers softmax profonds avec des sorties à valeurs réelles dans des tâches séquence-à-séquence.

• Insight Théorique : Les résultats éclairent le double rôle de l'attention : agir comme un mécanisme de réduction de dimensionnalité via le regroupement (effondrement des tokens) et exploiter la non-localité pour désintriquer les tokens à travers différentes séquences.
• Comparaison avec les ResNets : Les auteurs démontrent que pour des tâches où les séquences de sortie sont plus courtes que les séquences d'entrée ($m_j < n_j$), les transformers sont strictement plus efficaces en termes de paramètres que les ResNets. Alors qu'un ResNets nécessiterait des paramètres évoluant avec la longueur d'entrée $n$ (par exemple, $O(d N n)$), le transformer évolue avec la longueur de sortie ($O(d \sum m_j)$).
• Pertinence Pratique : La construction reflète des caractéristiques pratiques, notamment l'alternance des couches FF et SA et l'utilisation d'une attention de rang faible, suggérant que la capacité théorique des transformers n'est pas simplement un artefact d'architectures idéalisées mais inhérente à leur conception standard.

Les auteurs reconnaissent que leur construction représente une borne dans le pire des cas et que les modèles pratiques atteignent souvent de bonnes performances avec beaucoup moins de blocs. Ils notent également que le coût computationnel de l'attention (quadratique par rapport à la longueur d'entrée) reste un compromis non abordé par l'analyse de la complexité des paramètres. Les directions de travail futures identifiées incluent l'optimisation du nombre de blocs, l'analyse des normes des paramètres, et l'extension des résultats à l'attention multi-têtes et aux contextes causaux masqués.