Der Gegenschlag der FFT: Eine effiziente Alternative zu Self-Attention

 (arxiv.org)
3 Punkte von GN⁺ 2025-02-27 | 1 Kommentare | Auf WhatsApp teilen
  • In Long-Context-Transformern, bei denen die Kosten von Self-Attention zum Flaschenhals werden, senkt SPECTRE mit einem FFT-basierten Token-Mixer die Komplexität pro Layer von O(L²) auf O(L log L)
  • Jeder Attention-Head wird durch die Kombination aus schneller Real-FFT, inhaltsadaptivem spektralem Gate und inverser FFT ersetzt, während die bestehende Transformer-Struktur erhalten bleibt
  • Bei der autoregressiven Generierung reduziert der Prefix-FFT-Cache die Last wiederholter FFT-Neuberechnungen pro Schritt, und ein optionales Wavelet-Modul kann den Verlust lokaler Merkmale ausgleichen
  • Auf Basis des Llama-3.2-1B-Backbones wurden SDPA, FlashAttention-2 und SPECTRE verglichen; auf einer NVIDIA A100-80GB wurden Durchsatz und Latenz für 512 bis 128k Tokens gemessen
  • SPECTRE erreichte auf PG-19 und ImageNet-1k die gleiche oder eine bessere Basisleistung und zielt mit weniger als 6 % zusätzlicher Parameter auf Long-Context-Verarbeitung auf gewöhnlichen GPUs ab

Wie die quadratischen Kosten von Self-Attention mit FFT reduziert werden

  • Long-Context-Transformer werden für Aufgaben benötigt, die Zehntausende von Tokens verarbeiten, etwa Multi-Turn-Dialoge, buchlange Zusammenfassungen oder hochauflösende Vision-Anwendungen
  • Herkömmliche Self-Attention erhöht wegen der Kosten von O(n²d) mit wachsender Kontextlänge die Inferenzlatenz und den Speicherverbrauch
  • SPECTRE ist ein Drop-in-Ersatz, der Self-Attention-Layer durch einen Token-Mixer im Frequenzbereich ersetzt
    • Tokens werden auf eine orthonormale Fourier-Basis projiziert
    • Ein inhaltsadaptives diagonales Gate und optional ein Low-Rank-Gate werden angewendet
    • Anschließend erfolgt die Rücktransformation in den Token-Raum
  • Der Kern besteht darin, die Komplexität pro Layer auf O(n log n) zu senken, ohne die umgebende Netzwerkarchitektur zu verändern

Aufbau des Token-Mixers und Unterstützung für Generierung

  • Der Ersatz eines Attention-Heads in SPECTRE besteht aus schneller Real-FFT, spektralem Gate und inverser FFT
  • Das spektrale Gating arbeitet auf n/2 + 1 Frequenzkoeffizienten und ist so ausgelegt, Rechen- und Speicheraufwand zu verringern, ohne die Ausdrucksstärke zu verlieren
  • Der Prefix-FFT-Cache erfüllt eine ähnliche Rolle wie ein standardmäßiger KV-Cache und unterstützt Streaming-Decoding
    • Er reduziert die Schwäche herkömmlicher spektraler Mixer, bei autoregressiver Generierung in jedem Zeitschritt die FFT neu berechnen zu müssen
    • Die Struktur ermöglicht effiziente Generierung innerhalb eines festen Speicherbudgets
  • Das optionale Wavelet Refinement Module ergänzt lokale Details, die bei rein spektralen Verfahren verloren gehen könnten, bei geringem Rechen-Overhead

Anwendung auf bestehende Transformer

  • SPECTRE kann Multi-Head-Attention-Layer direkt ersetzen und erfordert keine separate Architekturüberarbeitung
  • Bereits vortrainierte Modelle können mit SPECTRE-Layern feinabgestimmt werden
    • Aktualisiert werden nur die neu eingeführten Parameter
    • Die zusätzlichen Parameter machen weniger als 6 % der Gesamtgewichte aus
  • Im Unterschied zu Ansätzen, die spezielle Optimierungen oder nicht standardisierte Architekturen benötigen, bleibt die umgebende Transformer-Struktur erhalten

Experimente auf Basis von Llama-3.2-1B

  • Auf demselben Llama-3.2-1B-Backbone wurden drei Attention-Kernels verglichen
    • standard softmax-dot-product attention (SDPA)
    • FlashAttention-2
    • SPECTRE-Mixer
  • Die Messumgebung war eine NVIDIA A100-80GB; die Sequenzlängen waren L ∈ {512, 1k, 4k, 8k, 32k, 128k}
  • Die Metriken waren der Durchsatz in Tokens pro Sekunde und die Latenz bei Single-Batch-Verarbeitung
    • Je höher der Durchsatz, desto besser
    • Je niedriger die Latenz, desto besser
  • SPECTRE zeigte bei erhaltener Backbone-Genauigkeit eine Laufzeit nahe O(n log n)
    • Bis 32k Tokens blieb die Laufzeit nahezu flach
    • Laut Abstract war SPECTRE bei einem 128k-Token-Kontext bis zu 7× schneller als FlashAttention-2
    • Laut der Liste der Contributions im Haupttext war die Inferenz bei 32k Tokens bis zu 7× schneller als mit FlashAttention-2

Benchmark-Ergebnisse und praktischer Einsatzbereich

  • SPECTRE zeigte bei Sprachmodellierung auf PG-19 und Klassifikation auf ImageNet-1k Ergebnisse auf oder über Basisniveau
  • Bei der Verarbeitung langer Kontexte vermeidet es die quadratischen Kosten von Self-Attention und behält dennoch globales Context-Mixing bei
  • Auf Sparse-Mustern, Kernel-Approximationen oder Low-Rank-Strukturen basierende Verfahren zur Beschleunigung von Attention können Einschränkungen wie den Verzicht auf Exaktheit, nicht standardisierte Optimierungen oder fehlende Unterstützung für Streaming-Generierung haben
  • SPECTRE nutzt einen Ansatz im Frequenzbereich, bei dem FFT die zirkuläre Faltung diagonalisiert und globales Mixing in ein elementweises Produkt überführt
  • Mit weniger als 6 % zusätzlichen Parametern zielt es ohne spezialisierte Hardware auf die Verarbeitung von Kontexten im Bereich von Hunderttausenden Tokens auf commodity GPUs ab

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-02-27
Hacker-News-Kommentare

  • Im Grunde nutzt der Ansatz den Faltungssatz: Eine teure Faltung im ursprünglichen Raum wird im reziproken Raum zu einer einfachen Multiplikation, und umgekehrt gilt das ebenfalls.
    Wenn es in den Daten eine Faltungsoperation gibt, transformiert man sie in den konjugierten Bereich und macht daraus eine Multiplikation.
    Anders gesagt: Arbeite in dem Bereich, der für die Daten natürlich ist.
    https://en.wikipedia.org/wiki/Convolution_theorem

    • So formuliert klingt das sehr gut, aber dass der strukturierte Attention-Raum in LLMs der Frequenzbereich ist, war für mich keineswegs offensichtlich.
    • Das ist ein grundlegendes mathematisches Raumtransformations-Sandwich: 1) die Daten in einen anderen Raum überführen, 2) in diesem Raum Operationen ausführen und 3) zurück in den ursprünglichen Raum transformieren.
      Zum Optimieren optimiert man jeden Schritt und erledigt möglichst viel Arbeit in dem effizientesten verfügbaren Raum.
    • Bei „Arbeite in dem Bereich, der für die Daten natürlich ist“ verstehe ich nicht, warum Multiplikation in irgendeinem Bereich natürlicher sein soll als Faltung.
      Ist das nicht etwas anderes, als dass sie einfach leichter zu berechnen ist?
    • Ist der reziproke Raum immer einfach von der Form 1/Raum, so wie Frequenz = 1/Zeit?
    • Stimmt, aber die Einsparung ist vor allem theoretischer Natur. Eine O(n²)-Operation in O(n log n) zu verwandeln klingt gut, bis man merkt, dass das durchschnittliche n bei 3 liegt.
      Außerdem muss man für die Berechnung komplexe Zahlen verwenden, und numerisch ist sie weniger stabil. Soweit ich weiß, bringt FFT bei allgemeinen Faltungen keinen Vorteil.
      Bei Self-Attention oder dem Anwendungsfall dieses Papers könnte n deutlich größer sein. Ich habe das Paper nicht gelesen. Das Problem mit den komplexen Zahlen bleibt trotzdem.

  • Google hat diese Idee 2022 mit FNet: Mixing Tokens with Fourier Transforms eingeführt.
    Danach stellte sich heraus, dass die Matrixmultiplikationsleistung von TPUs in den meisten Situationen schneller ist als FFT.
    https://arxiv.org/abs/2105.03824

    • Wird auch in diesem Paper zitiert:
      „Insgesamt zeigen Ansätze wie FNet, Performer und Sparse Transformer, dass feste oder approximative Token-Mischung den Rechenaufwand reduzieren kann; unsere Strategie des adaptiven spektralen Filterns kombiniert jedoch auf einzigartige Weise die Effizienz der FFT mit lernbaren, eingabeabhängigen spektralen Filtern. Das bietet eine starke Kombination aus Skalierbarkeit und Anpassungsfähigkeit, die für komplexe Aufgaben der Sequenzmodellierung wichtig ist.“
      Danach gibt es auch einen Vergleichsabschnitt.
    • Der Vergleich, dass spezialisierte Hardware besser sei, wirkt etwas merkwürdig.
      Haben DSPs eigentlich dedizierte Hardware, die FFT unterstützt? Ich frage aus echtem Interesse. Ich habe sie nie benutzt, aber vage würde ich erwarten, dass das hilft.
    • GPUs zeigten gegenüber TPUs eine Verbesserung um 10 %.
      „TPUs sind bei Fourier-Transformationen so ineffizient, dass die Forschenden bei Sequenzen mit weniger als 4096 Elementen nicht den FFT-Algorithmus verwendeten, sondern eine Fourier-Transformationsimplementierung mit quadratischer Skalierung über eine vorberechnete DFT-Matrix wählten.“
      „Auf einer Nvidia Quadro P6000 GPU machte die Fourier-Transformation in der FNet-Architektur bis zu 30 % der Inferenzzeit aus.“
      Dieses Unternehmen behauptete 2021, Google könne die Inferenzzeit um 40 % senken, wenn es in seinen TPUs deren optische Chips einsetzte. Wenn FFTNet mehr Arbeit übernimmt, könnte die Reduktion noch größer ausfallen.
      https://scribe.rip/optalysys/attention-fourier-transforms-a-...
    • Je mehr man die Zahl der Tokens im Kontextfenster erhöht, desto besser dürfte die Skalierung der FFT werden. Interessant ist, dass Google-Modelle bei der Kontextgröße vor der Konkurrenz liegen.
    • Es geht nicht nur darum, schneller als FFT zu sein; die FFT-Unterstützung von TPUs war immer nur Best-Effort. Als ich es zuletzt ausprobierte, gab es gravierende Präzisionsprobleme.

  • Die Fourier-Transformation wird entlang der „Token“-Dimension angewendet. In vielen Anwendungen hat diese Dimension jedoch keine Bedeutung. Deshalb sind Transformer eine gute Wahl für die Verarbeitung permutationsinvarianter Daten.
    Ich würde gern weitere Experimente mit der weniger bekannten Fourier-Transformation auf endlichen Gruppen sehen. Sie ist permutationsinvariant und teilt zugleich viele Eigenschaften mit der Standard-Fourier-Transformation.
    Außerdem frage ich mich, falls das der nächste große Trend bei LLMs wird, wie leicht Inferenz-Engines wie vLLM oder llama.cpp das integrieren könnten.
    https://en.wikipedia.org/wiki/Fourier_transform_on_finite_gr...

    • Ich bin kein Experte auf diesem Gebiet, aber werden die Tokens in den meisten Modellen nicht zusammen mit positionsabhängiger Information transformiert?
      Soweit ich weiß, wendet llama je nach Position in der Eingabe eine Rotation auf den Vektor an.
    • Was ist in diesem Fall die endliche Gruppe?

  • Die Mathematik geht völlig über meinen Kopf hinweg, und selbst die Erklärungen rund um die Formeln verstehe ich nur knapp. Kann jemand in einfachen Worten erklären, inwiefern das dem Attention-Mechanismus gleichwertig ist?
    Was ist hier mit Frequenz gemeint, und wie werden Positionsbeziehungen zwischen Tokens kodiert?

    • Die Fourier-Transformation ist ein invertierbarer Operator. Das heißt, sie wirkt auf Funktionen; bei Matrizen können sowohl Funktionen als auch Operatoren als Matrizen dargestellt werden. Sie transformiert sie in das, was wir Frequenzraum nennen.
      Bei Signalanalyse oder Bildern ist das am intuitivsten: https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm
      Der Frequenzraum ist im Wesentlichen ein „komplexer“ Raum, der durch komplexe Zahlen dargestellt wird. Frequenzen haben den Vorteil, ein Problem global zu betrachten.
      Dieser Mechanismus ist nicht gleichwertig mit dem Attention-Mechanismus, und es gibt klare Trade-offs. Er könnte allerdings viele der wichtigen Beziehungen erfassen, die Attention erfasst.
      Zu modReLU habe ich momentan keine gute Intuition, aber es scheint wichtig zu sein, weil es Frequenzen verändert und zugleich die inverse Fourier-Transformation erhält.
    • Der eigentliche Mechanismus selbst ist ziemlich einfach. Man wendet FFT auf die Input-Embeddings an, multipliziert elementweise mit Gewichten, die per MLP aus den Input-Embeddings gewonnen wurden, addiert einen konstanten, aber lernbaren Bias, schickt das durch eine Aktivierungsfunktion und wendet am Ende die inverse FFT an.
      „Frequenz“ ist hier vermutlich etwas ziemlich Abstraktes. FFT wird häufig auch auf Weisen eingesetzt, die keine klare Frequenzinterpretation haben. Oft nutzt man sie wegen praktischer mathematischer Eigenschaften wie dem Faltungssatz.
      Wenn das wirklich gut funktioniert, ist das ziemlich überraschend und sehr elegant.
    • Ich bin absolut kein Experte, aber als kleine Intuition: Self-Attention ist letztlich ein parametrisierter Token-Mixer.
      Das heißt, jeder Vektor im Output hängt davon ab, wie der entsprechende Input-Vektor durch irgendeine Funktion aller anderen Input-Vektoren transformiert wird.
      https://medium.com/optalysys/attention-fourier-transforms-a-...
      Konzeptionell kann man sehen, wie das einer etwas vereinfachten Faltung ähnelt: https://openreview.net/pdf?id=8l5GjEqGiRG
      Faltungen werden oft verwendet, wenn man auf irgendeine Weise den globalen Zustand berücksichtigen möchte.

  • Um kausales Masking in dieses Framework einzubauen, müsste man vermutlich n verschiedene FFTs machen; außerdem gibt es keine Erwähnung von Position Embeddings.
    Daher scheint die Self-Attention-Implementierung zum Vergleich eine nicht-kausale NoPE-Variante zu sein. Wenn das stimmt, wäre das ein Fall einer absichtlich schwach gewählten Baseline und damit möglicherweise nicht besonders beeindruckend.
    Wenn die Ergebnisse nahe am State of the Art gelegen hätten, hätten die Autoren das vermutlich erwähnt.

    • Im Long Range Arena(LRA)-Benchmark zeigen sie immerhin, dass ihr Modell in allen Kategorien gewinnt. Ich hoffe, sie haben keine Kategorien, in denen es verloren hat, oder bessere Modelle ausgelassen.

  • Scheint einschlägige Literatur dazu zu sein: 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

  • Ich frage mich, ob es eine Intuition dafür gibt, warum die Betrachtung im Frequenzbereich hier hilfreich ist.
    Die Gleichkomponente verstehe ich, aber ich würde nicht erwarten, dass die Eingabedaten periodisch genug sind, damit andere Frequenzen Bedeutung haben.

  • Die frühere Arbeit zum Hyena Operator, die schon vor einigen Jahren vollständiges Kontext-Mixing in O(n log n) gezeigt hat, scheint nicht erwähnt zu werden.
    https://arxiv.org/abs/2302.10866

  • Die Big-O-Notation bekomme ich halbwegs eingeordnet, aber wie bei den meisten Dingen rund um Informatik oder Elektrotechnik geht mir auch das über den Kopf.
    Aus der Perspektive von jemandem, der wirklich schlecht in Mathe ist, beneide ich Leute, die so etwas verstehen oder es zumindest so weit lernen können, dass sie einen Ingenieurabschluss und eine Berufszulassung bekommen.
    Über FFT weiß ich ungefähr nur, dass sie Signale transformiert, für bestimmte Arten der Signalverarbeitung verwendet wird und früher, wie ich gehört habe, ein zentraler Bestandteil der Erkennung von Nuklearexplosionen war.

    • Eine brauchbare Intuition für die Fourier-Transformation ist ein sehr nützliches Werkzeug, selbst wenn man die Fourier-Transformation nicht von Hand herleiten oder den FFT-Algorithmus nicht selbst schreiben kann.
      Die Grundidee ist: Fast jedes nützliche Signal lässt sich als Summe von Sinuswellen mit unterschiedlichen Frequenzen und Phasen darstellen. Elektrische Signale oder Schallwellen sind zum Beispiel eindimensionale Signale, bei denen die x-Achse die Zeit ist. Auf den ersten Blick können sie wie eine komplizierte, schwer handhabbare Zickzacklinie wirken.
      Mit der Fourier-Transformation kann man die einzelnen Frequenzen eines zeitbasierten Signals isolieren. Danach kann man bestimmte Frequenzen nach Wunsch verändern. Wenn ein Signal zum Beispiel viel zufälliges, spitzes Rauschen enthält, zeigt sich das als hohe Frequenzen. Zum Bereinigen führt man eine Fourier-Transformation durch, verwirft Daten mit Frequenzen oberhalb eines bestimmten Schwellenwerts und wendet dann auf die verbleibenden Daten die inverse Fourier-Transformation an, um zu einer glatteren Version des ursprünglichen Signals zurückzukehren. Das nennt man Tiefpassfilter und es ist in etwa damit vergleichbar, einen gleitenden Mittelwert des ursprünglichen Signals zu bilden.
      Interessant ist, dass sich das ziemlich intuitiv auf höhere Dimensionen erweitern lässt. Ein zweidimensionales Signal, bei dem sowohl x- als auch y-Achse räumlich sind, ist ein Bild. JPEG-Kompression basiert auf diesem Konzept. Um ein Bild kleiner zu speichern, entfernt man hochfrequente Signale und nimmt dafür in Kauf, feine Details zu verlieren oder, wenn man zu viel entfernt, ringförmige Artefakte zu erzeugen. Fügt man als dritte Dimension die Zeit hinzu, wird daraus Video, und das lässt sich weiter fortsetzen.
      All das lässt sich visuell gut verstehen, sodass man eine gute Intuition bekommen kann, ohne die gesamte Mathematik im Detail zu kennen. Eine gute Seite mit vielen Visualisierungen und interaktiven Beispielen: https://www.jezzamon.com/fourier/index.html
      Auch das Video von 3Blue1Brown erklärt es gut: https://youtu.be/spUNpyF58BY?si=dz0z-s8NftW3Htun
    • Kurz gesagt: Nehmen wir an, man hat ein eindimensionales Zeitbereichssignal, etwa ein mit einem Mikrofon gemessenes Audiosignal. Wenn das Mikrofon fest steht, misst es an einem bestimmten Punkt die Luftauslenkung über die Zeit.
      Die Fourier-Transformation, deren diskrete Version die FFT ist, zerlegt dieses eindimensionale Zeitbereichssignal in Komponenten aus Betrag und Phase über der Frequenz.
      Frequenz ist im Grunde Tonhöhe. Eine reine Sinuswelle oder ein reiner Ton ähnelt dem Ton, den man früher spätabends beim Sendeschluss im Fernsehen hörte; in diesem Fall ist fast alles null, und an der Frequenzposition dieses Tons entsteht ein einzelner „Spike“. Je größer die Signalamplitude, desto größer ist auch dieser Spike. Wenn die Tonhöhe, also die Frequenz, steigt oder fällt, wandert die Position dieses Spikes entlang der horizontalen Achse nach oben oder unten.
      Phase ist im Grunde der zeitliche Offset des Signals. Ein auf irgendeine Weise verzögerter Ton erscheint mit einer anderen Phase. Allerdings ist das keine absolute, sondern eine relative Messung. Die Einheit sind Radiant, also Winkel; nach einer vollen Umrundung des Kreises wird sie wieder „zurückgesetzt“, daher kann man nicht erkennen, ob ein Signal um 1 Sekunde oder 2 Sekunden verschoben wurde.
      Aus einem Signal, also Amplitude über Zeit, gewinnt man tatsächlich zwei Informationen: Betrag und Phase über der Frequenz.
      Wenn man imaginäre Zahlen oder komplexe Variablen versteht, sind diese beiden Signale eigentlich nur Betrag und Argument der FFT-Ausgabe, die eine komplexwertige Funktion ist.

  • Im Zeitalter der Telemetrie scheint es eine große verpasste Chance zu sein, FFT nicht auf Cloud-Telemetrie anzuwenden, um periodische Anomalien und metastabile Systeme zu finden, bevor etwas schiefgeht, statt erst danach.
    Leider liegt das zwar auf einem Niveau, auf dem ich es erkennen kann, aber nicht auf einem Niveau, auf dem ich es implementieren könnte, und mein Kalender ist ohnehin schon voll.
    „SLAs werden 23–25 Minuten nach dem Deployment eines Dienstes am wahrscheinlichsten verletzt. Hm, warum wohl … oh nein.“

    • „Es tut mir leid, Dave, aber deine Anwendung kann nicht deployt werden.“
      Spaß beiseite: Der Bereich, in dem sich damit wirklich Geld verdienen ließe, wäre die Vorhersage von Traffic-Zyklen, um Server-Instanzen hoch- und herunterzufahren und so Kosten zu sparen.
      So etwas würde eine Firma nie genehmigen, wenn man es in der Freizeit macht; als fertiges Produkt verpackt wäre es aber genau die Art von Arbeit, die eine Firma sofort kaufen würde.