- Dans les Transformers à long contexte, lorsque le coût de la self-attention devient un goulot d’étranglement, SPECTRE réduit la complexité par couche de O(L²) à O(L log L) grâce à un mélangeur de tokens basé sur la FFT
- Chaque tête d’attention est remplacée par une combinaison de real FFT rapide, de spectral gate adaptatif au contenu et de FFT inverse, tout en conservant l’architecture Transformer existante
- En génération autorégressive, le Prefix-FFT cache réduit le coût de recalcul de la FFT à chaque étape, et un module wavelet optionnel peut compenser la perte de caractéristiques locales
- Sur une base Llama-3.2-1B, SDPA, FlashAttention-2 et SPECTRE ont été comparés, avec des mesures de débit et de latence pour 512 à 128k tokens sur NVIDIA A100-80GB
- SPECTRE a obtenu des performances équivalentes ou supérieures sur PG-19 et ImageNet-1k, avec moins de 6 % de paramètres supplémentaires, en visant le traitement de longs contextes sur des GPU grand public
Réduire le coût quadratique de la self-attention avec la FFT
- Les Transformers à long contexte sont nécessaires pour des tâches traitant des dizaines de milliers de tokens, comme les dialogues multi-tour, le résumé à l’échelle d’un livre ou la vision haute résolution
- La self-attention classique entraîne un coût en O(n²d), ce qui augmente la latence d’inférence et l’usage mémoire à mesure que le contexte s’allonge
- SPECTRE remplace la couche de self-attention par un mélangeur de tokens dans le domaine fréquentiel utilisable comme remplacement direct
- Projection des tokens sur une base de Fourier orthonormale
- Application d’un gate diagonal adaptatif au contenu et d’un gate low-rank optionnel
- Retour dans l’espace des tokens via une transformée inverse
- L’idée clé est d’abaisser la complexité par couche à O(n log n) sans modifier l’architecture réseau environnante
Composition du mélangeur de tokens et prise en charge de la génération
- Le remplacement d’une tête d’attention dans SPECTRE repose sur une real FFT rapide, un spectral gate et une FFT inverse
- Le spectral gating opère sur n/2 + 1 coefficients de fréquence, afin de réduire calcul et mémoire tout en conservant le pouvoir de représentation
- Le Prefix-FFT cache joue un rôle similaire au KV-cache standard pour prendre en charge le décodage en streaming
- Il atténue la faiblesse des mélangeurs spectraux classiques, qui doivent recalculer la FFT à chaque pas de temps en génération autorégressive
- Il permet une génération efficace dans une enveloppe mémoire fixe
- Le Wavelet Refinement Module optionnel compense les détails locaux potentiellement perdus par une approche purement spectrale, avec un faible surcoût de calcul
Comment l’appliquer à un Transformer existant
- SPECTRE peut remplacer directement une couche de multi-head attention, sans exiger de refonte architecturale séparée
- Les modèles préentraînés existants peuvent être fine-tunés avec des couches SPECTRE
- Les paramètres mis à jour sont ceux introduits par cette modification
- Les paramètres supplémentaires représentent moins de 6 % de l’ensemble des poids
- Contrairement aux approches nécessitant des optimisations spécialisées ou des architectures non standard, la structure Transformer autour est conservée
Expériences basées sur Llama-3.2-1B
- Trois kernels d’attention ont été comparés sur la même base Llama-3.2-1B
- standard softmax-dot-product attention (SDPA)
- FlashAttention-2
- mélangeur SPECTRE
- L’environnement de mesure est NVIDIA A100-80GB, avec des longueurs de séquence L ∈ {512, 1k, 4k, 8k, 32k, 128k}
- Les métriques sont le débit en tokens par seconde et la latence en single-batch
- Plus le débit est élevé, mieux c’est
- Plus la latence est faible, mieux c’est
- SPECTRE montre un temps d’exécution proche de O(n log n) tout en conservant la précision du backbone
- Le temps d’exécution reste presque plat jusqu’à 32k tokens
- D’après le résumé, il est jusqu’à 7× plus rapide que FlashAttention-2 sur un contexte de 128k tokens
- D’après la liste des contributions du papier, il montre jusqu’à 7× plus d’inférence rapide que FlashAttention-2 à 32k tokens
Résultats de benchmark et portée pratique
- SPECTRE obtient des résultats équivalents ou supérieurs à la baseline sur la modélisation du langage PG-19 et la classification ImageNet-1k
- Il évite le coût quadratique de la self-attention sur les longs contextes tout en conservant un mélange global du contexte
- Les méthodes d’accélération de l’attention fondées sur des motifs clairsemés, des approximations par noyau ou des structures low-rank peuvent avoir des limites, comme une perte d’exactitude, le besoin d’optimisations non standard ou l’absence de génération en streaming
- SPECTRE adopte une approche fréquentielle où la FFT diagonalise la convolution circulaire pour transformer le mélange global en produit élément par élément
- En limitant les paramètres additionnels à moins de 6 %, il vise le traitement de contextes de plusieurs centaines de milliers de tokens sur des GPU grand public, sans matériel spécialisé
1 commentaires
Avis de Hacker News
En gros, c’est une façon d’exploiter le théorème de convolution : une convolution coûteuse dans l’espace d’origine devient une simple multiplication dans l’espace réciproque, et l’inverse est vrai aussi.
S’il y a une opération de convolution sur les données, il suffit de les transformer dans le domaine conjugué pour la convertir en multiplication.
Autrement dit, il faut travailler dans le domaine naturel des données.
https://en.wikipedia.org/wiki/Convolution_theorem
Pour optimiser, il suffit d’optimiser chaque étape et de faire autant de travail que possible dans l’espace le plus efficace.
Ce n’est pas simplement différent du fait que ce soit plus facile à calculer ?
En plus, il faut utiliser des nombres complexes dans les calculs, et c’est aussi moins stable numériquement. À ma connaissance, la FFT n’est pas avantageuse pour une convolution générale.
Pour la self-attention ou l’usage de cet article, n pourrait être beaucoup plus grand. Je n’ai pas lu l’article. Mais le problème des nombres complexes reste entier.
Google a introduit cette idée en 2022 avec FNet: Mixing Tokens with Fourier Transforms.
Par la suite, on s’est aperçu que, dans la plupart des cas, les performances de multiplication matricielle des TPU étaient plus rapides que la FFT.
https://arxiv.org/abs/2105.03824
« Globalement, des approches comme FNet, Performer et les transformeurs clairsemés montrent qu’un mélange de tokens fixe ou approximatif peut réduire la charge de calcul, mais notre stratégie de filtrage spectral adaptatif combine de façon unique l’efficacité de la FFT avec des filtres spectraux apprenables et dépendants de l’entrée. Cela offre une combinaison puissante de scalabilité et d’adaptabilité, essentielle pour les tâches complexes de modélisation de séquences. »
Il y a aussi une section de comparaison ensuite.
Mais les DSP disposent-ils de matériel dédié pour aider la FFT ? Je pose vraiment la question par curiosité. Je n’en ai jamais utilisé, mais j’ai vaguement l’impression que ça pourrait aider.
« Les TPU sont tellement inefficaces pour les transformées de Fourier que les chercheurs, pour les séquences de moins de 4096 éléments, n’ont pas utilisé l’algorithme FFT et ont choisi une implémentation de transformée de Fourier à échelle quadratique utilisant une matrice DFT précalculée. »
« Sur un GPU Nvidia Quadro P6000, dans l’architecture FNet, les transformées de Fourier représentaient jusqu’à 30 % du temps d’inférence. »
Cette entreprise affirmait en 2021 que si Google utilisait leurs puces optiques dans ses TPU, le temps d’inférence pourrait être réduit de 40 %. Si FFTNet prend en charge davantage de travail, la réduction pourrait être encore plus importante.
https://scribe.rip/optalysys/attention-fourier-transforms-a-...
La transformée de Fourier est appliquée le long de la dimension des « tokens ». Mais dans beaucoup d’applications, cette dimension n’a pas de signification. C’est pourquoi les transformeurs sont un bon choix pour traiter des données invariantes par permutation.
J’aimerais voir des expériences supplémentaires utilisant la transformée de Fourier sur les groupes finis, moins connue. Elle est invariante par permutation tout en partageant de nombreuses propriétés avec la transformée de Fourier standard.
Je me demande aussi, si cela devient la prochaine grande tendance des LLM, à quel point les moteurs d’inférence comme vLLM ou llama.cpp pourraient l’intégrer facilement.
https://en.wikipedia.org/wiki/Fourier_transform_on_finite_gr...
Il me semble que llama applique une rotation au vecteur selon sa position dans l’entrée.
Les maths me passent complètement au-dessus de la tête, et je comprends à peine les explications autour des formules. Quelqu’un pourrait-il expliquer en termes simples en quoi c’est équivalent au mécanisme d’attention ?
Qu’entend-on ici par fréquences, et comment les relations de position entre tokens sont-elles encodées ?
C’est le plus intuitif en analyse du signal ou en image : https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm
L’espace fréquentiel est, par nature, un espace « complexe » représenté par des nombres complexes. Les fréquences ont l’avantage de regarder le problème de manière globale
Ce mécanisme n’est pas équivalent au mécanisme d’attention, et il y a clairement un compromis. Il peut toutefois capturer une grande partie des relations importantes que capture l’attention
Je n’ai pas pour l’instant de bonne intuition sur modReLU, mais cela semble important parce qu’il modifie les fréquences tout en préservant la transformée de Fourier inverse
Ici, les « fréquences » sont probablement quelque chose d’assez abstrait. La FFT est souvent utilisée même dans des contextes où il n’y a pas d’interprétation fréquentielle claire. On l’emploie souvent pour ses propriétés mathématiques pratiques, comme le théorème de convolution
Si ça fonctionne vraiment bien, c’est assez surprenant, et très élégant
Autrement dit, chaque vecteur en sortie dépend de la transformation du vecteur d’entrée correspondant par une certaine fonction de tous les autres vecteurs d’entrée
https://medium.com/optalysys/attention-fourier-transforms-a-...
Conceptuellement, on peut voir en quoi cela ressemble à une convolution un peu simplifiée : https://openreview.net/pdf?id=8l5GjEqGiRG
Les convolutions sont souvent utilisées quand on veut tenir compte d’un état global d’une manière ou d’une autre
Pour intégrer un masquage causal dans ce framework, il me semble qu’il faudrait effectuer n FFT différentes, et il n’y a pas non plus de mention des embeddings positionnels
Donc l’implémentation de self-attention utilisée comme comparaison semble être non causale et NoPE ; si c’est le cas, c’est peut-être un exemple où la baseline a été volontairement affaiblie, et ce n’est pas si impressionnant
Si les résultats avaient été proches de l’état de l’art, l’auteur l’aurait probablement mentionné
Cela ressemble à une référence liée : https://arxiv.org/abs/2111.13587
Adaptive Fourier Neural Operators: Efficient Token Mixers for Transformers
John Guibas, Morteza Mardani, Zongyi Li, Andrew Tao, Anima Anandkumar, Bryan Catanzaro
Je me demande s’il existe une intuition expliquant pourquoi il est utile de regarder cela dans le domaine fréquentiel
Je comprends la composante continue, mais je ne m’attends pas à ce que les données d’entrée soient suffisamment périodiques pour que les autres fréquences aient un sens
Il semble manquer la mention du travail antérieur sur Hyena Operator, qui avait déjà montré il y a quelques années un mélange de contexte complet en O(n log n)
https://arxiv.org/abs/2302.10866
https://arxiv.org/abs/2111.00396
La notation grand O me donne une certaine idée, mais comme la plupart des choses liées à l’informatique ou au génie électrique, ça me passe au-dessus de la tête
Étant vraiment nul en maths, j’envie les gens capables de comprendre ce genre de choses, ou au moins de les apprendre, jusqu’à obtenir un diplôme d’ingénieur et une licence professionnelle
Ce que je sais de la FFT, c’est à peu près qu’elle transforme des signaux, qu’elle sert à certains types de traitement du signal, et que j’ai entendu dire qu’elle avait autrefois été au cœur de la détection d’explosions nucléaires
L’idée de base est la suivante : presque tout signal utile peut être représenté comme la somme de sinusoïdes de fréquences et de phases différentes. Par exemple, un signal électrique ou une onde sonore est un signal unidimensionnel dont l’axe x est le temps. Visuellement, cela peut être une ligne complexe et tortueuse, difficile à manipuler
Avec une transformée de Fourier, on peut isoler les différentes fréquences d’un signal temporel. On peut ensuite modifier certaines fréquences comme on le souhaite. Par exemple, si un signal contient beaucoup de bruit aléatoire en pics, cela apparaît comme des hautes fréquences. Pour le nettoyer, il suffit d’appliquer une transformée de Fourier, de supprimer les données dont la fréquence dépasse un certain seuil, puis d’appliquer une transformée de Fourier inverse aux données restantes pour revenir à une version plus lisse du signal d’origine. C’est ce qu’on appelle un filtre passe-bas, et c’est à peu près équivalent à prendre une moyenne glissante du signal d’origine
Ce qui est intéressant, c’est que cela s’étend assez intuitivement aux dimensions supérieures. Un signal bidimensionnel dont les axes x et y sont tous deux spatiaux, c’est une image. La compression JPEG repose sur ce concept. Pour stocker une image dans moins d’espace, on supprime les signaux de haute fréquence, au prix d’une perte de détails fins ou, si l’on en supprime trop, de l’apparition d’artefacts en forme d’anneaux. Ajoutez une troisième dimension, le temps, et vous obtenez une vidéo ; on peut continuer ainsi
Tout cela se comprend très bien visuellement, ce qui permet d’acquérir une bonne intuition sans connaître toute la théorie mathématique en profondeur. Une bonne page avec beaucoup de visualisations et d’exemples interactifs : https://www.jezzamon.com/fourier/index.html
La vidéo de 3Blue1Brown l’explique aussi très bien : https://youtu.be/spUNpyF58BY?si=dz0z-s8NftW3Htun
La transformée de Fourier, dont la FFT est la version discrète, décompose ce signal temporel unidimensionnel en composantes de magnitude et de phase en fonction de la fréquence
La fréquence correspond essentiellement à la hauteur du son. Une sinusoïde pure, ou un ton pur, ressemble au son qu’on entendait autrefois tard le soir à la fin des programmes TV ; dans ce cas, la plupart des valeurs sont à 0 et il y a un seul « pic » à l’emplacement de la fréquence de ce ton. Plus l’amplitude du signal est élevée, plus la taille du pic augmente. Si la hauteur, c’est-à-dire la fréquence, monte ou descend, l’emplacement de ce pic se déplace le long de l’axe horizontal
La phase correspond essentiellement au décalage temporel du signal. Un ton retardé d’une manière ou d’une autre apparaîtra avec une phase différente. Mais ce n’est pas une mesure absolue, c’est une mesure relative. Comme l’unité est le radian, donc un angle, elle « se réinitialise » après un tour complet de cercle ; on ne peut donc pas savoir si le signal a été décalé d’une seconde ou de deux
Ainsi, à partir d’un seul signal — l’amplitude en fonction du temps — on obtient en réalité deux informations : la magnitude et la phase en fonction de la fréquence
Si vous comprenez les nombres imaginaires ou les variables complexes, ces deux signaux ne sont en fait que la magnitude et l’argument de la sortie de la FFT, qui est une fonction complexe
À l’ère de la télémétrie, ne pas appliquer la FFT à la télémétrie cloud pour détecter les anomalies périodiques et les systèmes quasi stables avant qu’un incident n’éclate, plutôt qu’après, me semble être une grosse occasion manquée
Malheureusement, c’est quelque chose que je suis capable de repérer, mais pas de mettre en œuvre techniquement, et mon planning est déjà plein
« Les SLA ont le plus de chances d’être violés 23 à 25 minutes après le déploiement d’un service. Hmm, pourquoi donc… oh non. »
Blague à part, le domaine où cela pourrait vraiment rapporter, c’est la prévision des cycles de trafic pour augmenter ou réduire le nombre d’instances serveur et ainsi faire baisser les coûts
C’est le genre de travail qu’une entreprise n’approuverait jamais si on le faisait sur son temps personnel, mais qu’elle achèterait immédiatement si c’était emballé comme un produit prêt à l’emploi