On the Computational Hardness of Transformers

Diese Arbeit widerlegt die Möglichkeit einer effizienteren parallelen Berechnung von Multi-Head-Multi-Layer-Transformern im Vergleich zur unabhängigen Verarbeitung der einzelnen Aufmerksamkeitsköpfe und etabliert unter der Annahme SETH sowie durch Anwendung des Baur-Strassen-Theorems die Optimalität der bekannten Algorithmen für kleine und große Einbettungsdimensionen.

Das Wesentliche

Stellen Sie sich vor, ein Transformer (die Technologie hinter modernen KI-Modellen wie Chatbots) ist eine riesige, hochmoderne Fabrik. Diese Fabrik hat viele Stockwerke (Schichten), und auf jedem Stockwerk arbeiten viele kleine Teams (die sogenannten „Attention-Heads") parallel.

Jedes Team hat eine spezielle Aufgabe: Es muss prüfen, wie stark die verschiedenen Wörter oder Bilder in einer Eingabe miteinander zusammenhängen. Das ist wie ein riesiges „Wer-kennt-wen"-Spiel, bei dem jedes Team jede mögliche Verbindung zwischen allen Elementen überprüfen muss.

Das große Problem: Die Effizienz-Frage

Bisher dachten die Wissenschaftler: „Wenn wir 100 Teams haben, müssen wir einfach 100 Mal die gleiche Arbeit machen, nur eben nacheinander oder parallel, aber immer noch 100-mal den gleichen Aufwand."

Die Frage, die sich die Autoren dieses Papers stellen, ist jedoch: Können wir diese 100 Teams nicht irgendwie „klüger" zusammenarbeiten lassen? Vielleicht gibt es einen Trick, bei dem die Teams ihre Arbeit teilen und das Gesamtergebnis schneller erreichen, als wenn sie alle einzeln rechnen würden?

In der Informatik nennt man das das „Direct Sum"-Problem: Kann man viele Kopien desselben Problems schneller lösen, als wenn man jede Kopie einzeln bearbeitet?

Die Antwort der Forscher: Nein, es gibt keinen Abkürzungsweg

Die Autoren kommen zu einem sehr klaren Ergebnis: Nein.

Sie beweisen, dass es keine magische Abkürzung gibt. Um ein Transformer-Modell zu berechnen, müssen wir im Grunde genau so viel Rechenarbeit leisten, wie wenn wir jedes einzelne Team einzeln und unabhängig voneinander arbeiten lassen.

Hier ist die Erklärung in zwei Szenarien, je nachdem, wie „groß" die Daten sind:

1. Der kleine Datensatz (Kleine Einbettung)

Stellen Sie sich vor, die Teams arbeiten mit kleinen Notizblöcken.

• Die alte Annahme: Vielleicht können wir die Teams so organisieren, dass sie schneller fertig werden.
• Die neue Erkenntnis: Die Forscher haben bewiesen, dass das unmöglich ist. Wenn Sie versuchen, die Arbeit zu beschleunigen, stoßen Sie auf eine fundamentale Wand. Es ist so, als würden Sie versuchen, 100 Leute schneller einen Berg hinaufjagen zu lassen, indem Sie sie alle in ein einziges Auto setzen – aber das Auto ist zu klein. Die Rechenzeit wächst quadratisch mit der Anzahl der Wörter. Es gibt keinen Weg, das zu umgehen, ohne die Genauigkeit zu opfern.

2. Der große Datensatz (Große Einbettung)

Jetzt stellen Sie sich vor, die Teams arbeiten mit riesigen Tabellen und komplexen Matrizen (wie riesige Excel-Tabellen).

• Die alte Annahme: Vielleicht können wir die Tabellen cleverer addieren, um Zeit zu sparen.
• Die neue Erkenntnis: Auch hier gibt es keine Abkürzung. Die Forscher nutzen ein mathematisches Werkzeug namens Baur-Strassen-Theorem.
  • Die Analogie: Stellen Sie sich vor, Sie haben einen Kuchen, der aus vielen Schichten besteht. Um zu beweisen, dass man den Kuchen nicht schneller backen kann, schauen Sie sich nicht den fertigen Kuchen an, sondern die Zubereitung der Zutaten.
  • Die Forscher zeigen: Wenn man einen Transformer schnell berechnen könnte, könnte man damit auch viele unabhängige Multiplikationen von riesigen Tabellen gleichzeitig lösen. Aber wir wissen aus der Mathematik, dass man diese Multiplikationen nicht schneller machen kann, als die besten bekannten Algorithmen es erlauben.
  • Da der Transformer also mindestens so viel Arbeit leistet wie diese schweren Multiplikationen, kann er nicht schneller sein.

Was bedeutet das für uns?

1. Keine magische Beschleunigung: Es wird keine Software-Update geben, das Transformer-Modelle plötzlich 100-mal schneller macht, indem es die interne Struktur cleverer nutzt. Die Grenzen sind mathematisch festgelegt.
2. Bestätigung des „Naiven" Weges: Der einfache, „dumme" Weg (jedes Team einzeln rechnen zu lassen) ist tatsächlich der beste Weg, den wir haben.
3. Hoffnung auf Hardware: Da wir die Software-Seite nicht mehr drastisch verbessern können, liegt die Zukunft in der Hardware. Wir brauchen bessere Grafikkarten und Prozessoren, die diese massive Rechenarbeit einfach schneller bewältigen können (wie FlashAttention, das bereits I/O-Optimierungen nutzt).

Zusammenfassung in einem Satz

Die Forscher haben bewiesen, dass man bei der KI-Technologie „Transformer" keine Abkürzungen nehmen kann; die Rechenarbeit ist unvermeidbar und so groß, wie man es beim einfachen Zählen aller Möglichkeiten erwarten würde. Es gibt keinen „Trick", um die Mathematik zu überlisten.

Technische Zusammenfassung

1. Problemstellung

Das Transformer-Architektur-Modell hat die moderne KI revolutioniert, ist jedoch rechnerisch sehr anspruchsvoll. Der Kernmechanismus ist die Aufmerksamkeit (Attention), bei der für eine Eingabe der Länge $N$ und einer Embedding-Dimension $m$ drei Matrizen der Größe $N \times m$ multipliziert werden, gefolgt von einer Softmax-Operation.

Die naive Berechnung eines einzelnen Attention-Head benötigt $O(N^2 m)$ Zeit. Ein Transformer mit $L$ Schichten und $H$ Attention-Heads pro Schicht würde dementsprechend $O(L H N^2 m)$ Zeit benötigen.

Die zentrale Frage:
Kann die Berechnung von $L \times H$ Attention-Heads (bzw. eines gesamten Transformers) effizienter erfolgen, als wenn man jede Instanz einzeln berechnet? Dies ist eine klassische Fragestellung in der theoretischen Informatik, bekannt als das „Direct Sum"-Problem. Bisherige Arbeiten haben untere Schranken für einen Attention-Head etabliert, aber es fehlten nicht-triviale untere Schranken für die Berechnung von multi-layer multi-head Transformern. Die Autoren untersuchen, ob eine „Amortisierung" der Kosten möglich ist oder ob die naive, unabhängige Berechnung jeder Instanz im Wesentlichen optimal ist.

2. Methodik und Modell

Die Autoren analysieren die Komplexität in zwei verschiedenen Regimen der Embedding-Dimension $m$ und verwenden unterschiedliche theoretische Werkzeuge:

A. Kleines Embedding-Regime ($m = N^{o(1)}$)

In diesem Szenario (z. B. $m = \Theta(\log N)$) basieren die unteren Schranken auf Fein-granularer Komplexität (Fine-Grained Complexity).

• Hypothese: Die Ergebnisse stützen sich auf die 3-OV-Hypothese (Orthogonal Vectors) und die Strong Exponential Time Hypothesis (SETH).
• Reduktion: Die Autoren konstruieren einen Transformer, der ein unbalanciertes 3-OV-Problem löst. Sie kodieren Vektoren aus den Mengen $A, B, C$ in die Eingabe des Transformers. Durch geschickte Wahl der Embedding-Matrizen ($Q, K, V$) und der Hardmax-Attention (die durch Softmax approximiert werden kann) wird sichergestellt, dass die Ausgabe des Transformers Aufschluss darüber gibt, ob ein orthogonales Tripel existiert.
• Ergebnis: Wenn ein Transformer effizienter als $L H N^{2-o(1)}$ berechnet werden könnte, würde dies die 3-OV-Hypothese widerlegen.

B. Großes Embedding-Regime ($m = N$)

Hier ist die naive obere Schranke durch schnelle Matrixmultiplikation $O(L H N^{\omega+o(1)})$, wobei $\omega$ der Exponent der Matrixmultiplikation ist (aktuell $\approx 2,37$).

• Modell: Da Attention-Operationen Exponentiationen beinhalten, verwenden die Autoren das Modell der erweiterten arithmetischen Schaltkreise (Extended Arithmetic Circuits, eACs), die neben $+,-,\times,/$ auch $exp$- und $ln$-Gatter zulassen.
• Hauptwerkzeug: Die Autoren wenden das Baur-Strassen-Theorem neu an. Dieses Theorem besagt, dass man aus einem Schaltkreis, der eine Funktion $f$ berechnet, einen Schaltkreis ähnlicher Größe ableiten kann, der alle partiellen Ableitungen von $f$ berechnet.
• Strategie:
  1. Sie konstruieren einen Transformer, der die Summe der Zeilensummen von Exponentialen vieler unabhängiger Matrixprodukte berechnet.
  2. Durch Einführung von Hilfsvariablen in die Eingabe und Anwendung des erweiterten Baur-Strassen-Theorems können sie die partiellen Ableitungen extrahieren.
  3. Diese Ableitungen erlauben es, die Einträge der Matrixprodukte $A_k B_k^\top$ zurückzugewinnen.
  4. Da die Berechnung von $\Theta(LH)$ unabhängigen Matrixprodukten bekanntermaßen eine Größe von $\Omega(L H N^{\omega-o(1)})$ erfordert, muss auch der Transformer-Schaltkreis mindestens diese Größe haben.
  5. Ein wichtiger technischer Schritt ist der Beweis, dass eACs für Funktionen niedrigen Grades (wie Matrixprodukte) keine Vorteile gegenüber Standard-arithmetischen Schaltkreisen bieten.

3. Wichtige Beiträge und Ergebnisse

Die Arbeit liefert die ersten nicht-trivialen unteren Schranken für die Berechnung von multi-layer multi-head Transformern und zeigt, dass die naive Berechnung im Wesentlichen optimal ist.

Theorem 1.1 (Kleines Embedding):
Unter der 3-OV-Hypothese (oder SETH) erfordert jeder Algorithmus, der einen Transformer mit $L$ Schichten, $H$ Heads und Embedding-Dimension $m = \Omega(\log N)$ berechnet, eine Zeit von $L H N^{2-o(1)}$.

• Dies verbessert frühere Schranken, die nur $L H N^{1-o(1)} + N^{2-o(1)}$ ausschlossen, und zeigt, dass keine signifikante Beschleunigung durch parallele Verarbeitung möglich ist.

Theorem 1.2 (Großes Embedding):
Für $m = N$ (und $\omega > 2$) hat jeder erweiterte arithmetische Schaltkreis, der einen solchen Transformer berechnet, eine Größe von mindestens $L H N^{\omega-o(1)}$.

• Dies beweist, dass die Komplexität der Transformer-Berechnung äquivalent zur Berechnung von $\Theta(LH)$ unabhängigen Matrixmultiplikationen ist.
• Die untere Schranke gilt auch dann, wenn keine MLPs (Multi-Layer Perceptrons) verwendet werden und die Embedding-Maps linear berechnet werden können.

4. Signifikanz und Implikationen

• Optimalität der naiven Algorithmen: Die Ergebnisse zeigen, dass es im Worst-Case keine „magische" Beschleunigung gibt, wenn man viele Attention-Heads gleichzeitig berechnet. Die Kosten summieren sich direkt auf (Direct Sum Theorem für Transformer).
• Theoretische Grenzen: Dies setzt eine fundamentale Grenze für die Entwicklung von sub-quadratischen oder sub-kubischen Attention-Algorithmen für exakte Berechnungen. Subquadratische Approximationen (wie in der Praxis oft verwendet) müssen zwangsläufig Genauigkeit opfern, was durch frühere Arbeiten bereits gezeigt wurde; diese Arbeit bestätigt nun die Härte der exakten Berechnung.
• Neue Anwendung des Baur-Strassen-Theorems: Die Arbeit stellt einen innovativen theoretischen Ansatz vor, indem sie ein klassisches Werkzeug aus der algebraischen Komplexitätstheorie (ursprünglich für Backpropagation und untere Schranken in Schaltkreisen genutzt) nutzt, um die Härte von neuronalen Netzarchitekturen zu beweisen.
• Praktische Relevanz: Für große Modelle mit hoher Embedding-Dimension (wie sie in modernen LLMs vorkommen) bedeutet dies, dass die Rechenkosten durch die Matrixmultiplikation dominiert werden und nicht durch die Struktur des Transformers selbst umgangen werden können. Hardware-Optimierungen (wie FlashAttention) können die I/O-Komplexität verbessern, aber die asymptotische Rechenkomplexität bleibt bestehen.

Zusammenfassung

Das Paper widerlegt die Hoffnung, dass Transformer durch parallele Verarbeitung ihrer vielen Heads und Schichten signifikant effizienter berechnet werden können, als es die Summe der einzelnen Teile wäre. Unter standardmäßigen Komplexitätsannahmen (SETH, 3-OV) und im algebraischen Schaltkreismodell ist die naive Berechnung von $L \times H$ Attention-Heads asymptotisch optimal. Dies festigt das Verständnis der Transformer-Architektur als rechnerisch „hart" und legt nahe, dass zukünftige Fortschritte eher in Approximationen oder Hardware-Optimierungen als in fundamentalen algorithmischen Beschleunigungen liegen dürften.