KAPITEL 7.3 · SELF-ATTENTION

Attention Komplexität: Das O(n²) Problem

Warum Attention quadratisch skaliert und wie das alle modernen Optimierungen motiviert. Von 2K-Token-Limits zu 1M+ mit DSA und Sparse Attention.

Das O(n²) Problem der Self-Attention ist die fundamentale Herausforderung, die alle modernen LLM-Optimierungen antreibt. Von 2K-Token-Limits 2020 zu 1M+ heute – diese Visualisierung zeigt, wie quadratische Skalierung gelöst wurde.

📖 Lern-Kontext ▼
🎯

Lernziele

  • Verstehen, warum Self-Attention O(n²) ist
  • Die praktischen Auswirkungen auf Kontextfenster kennen
  • Lösungsansätze (Sparse Attention, DSA) einordnen
🗺️

Kontext: Wo sind wir?

Schritt 1/2 Trends & Zukunft

Scaling & Komplexität (1/2) zeigt die fundamentalen Grenzen, bevor wir zu emergenten Fähigkeiten (2/2) kommen.

💡

Warum wichtig

Die quadratische Skalierung bestimmt, was mit LLMs möglich ist. 1M-Token-Kontexte brauchen Sparse Attention – ohne dieses Wissen sind moderne Architekturen nicht verständlich.

📌

Key Takeaways

  • O(n²): Verdopplung der Sequenz = 4× mehr Compute
  • Memory: KV-Cache wächst linear, Attention-Matrix quadratisch
  • Lösung: Sparse Attention, Flash Attention, DSA
8K Tokens
📊 Memory Komplexität
Memory benötigt (GB) | Log-Scale
Std. Attention O(n²)
Flash Attention O(n)
GQA + Sparse O(n×k)
⚡ Compute Komplexität
Relative Compute Zeit (normalized zu 2K)
Std. Attention
Sliding Window
DSA (Sparse)
🎯 Attention Matrix
-
Größe der Attention-Matrix für aktuelle Sequenz
💾 KV-Cache (Llama 3 70B)
-
Speicher für Key-Value Caches
⏱️ Relative Time
-
vs. 2K-Token Baseline (theoretisch)
🚀 Speedup mit DSA
-
Speedup durch Sparse Attention
📐
Warum O(n²)?
Jedes Token fragt "auf Ähnlichkeit hin" jeden anderen Token in der Sequenz. Das sind n × n Vergleiche. Mit n = 128K sind das 16 Milliarden Operationen pro Layer!
📦
KV-Cache Bottleneck
Für jeden Token müssen Key- und Value-Vektoren gespeichert werden. Mit d=8192 Dimensionen und 80 Layers sind das schnell 100+ GB für 1M Tokens.
🔧
Flash Attention (2022)
IO-aware Algorithmus: Speichern in GPU-SRAM, nicht HBM. Gleiche Ergebnisse, aber O(n) Memory statt O(n²). Nur 2x Speedup real, aber Memory-Einsparung ist enorm.
🎯
GQA Reduktion
query-attention" class="glossary-term">Grouped Query Attention: KV-Heads teilen sich (64 Query / 8 KV = 8x Reduktion). Llama 3 70B nutzt das. Der KV-Cache wird 8x kleiner ohne große Qualitätsverluste.
⚡
Sliding Window (2024)
Nur lokale Attention: Token schaut nur auf die letzten W Tokens (z.B. W=4096). Komplexität wird O(n×W) statt O(n²). Mit großem Window praktisch ähnlich, aber VRAM ist viel kleiner.
🌟
DSA / Sparse (2025)
Deep Sparse Attention: Router wählt nur Top-k relevante Tokens aus (z.B. k=256 von 1M). Komplexität wird O(n×k). Llama 4 Scout & Maverick erreichen 1M+ Context damit praktisch.

Schlüssel-Erkenntnisse

1
2x Sequenzlänge = 4x mehr Ressourcen: Das ist nicht linear, es ist quadratisch. Mit 2K Tokens brauchst du vielleicht 4GB RAM, mit 8K bereits 64GB. Das ist der Grund, warum GPT-3 nur 2K-Token hatte.
2
Memory ist das echte Limit: Nicht Compute (mit GPUs/TPUs), sondern VRAM. Modern GPUs haben 40-80GB (H100/A100), 1M Tokens mit O(n²) bräuchten Petabytes.
3
Flash Attention ist nicht "schneller", nur speichereffizienter: Dieselbe Anzahl von Operationen, aber besser im GPU-Memory-Hierachie. Praktischer Speedup: 2-3x, Memory-Einsparung: bis zu 10x.
4
GQA ist der "Low-Hanging Fruit": 8x KV-Cache Reduktion ohne große Qualitätsverluste. Fast alle modernen Modelle nutzen das jetzt (Llama, Mixtral, Deepseek).
5
Sliding Window funktioniert überraschend gut: Mit 4K Window macht man wenig Qualität Verlust, aber Memory/Compute wird O(n×W) statt O(n²). LLaMA 2 nutzte das, Mistral auch.
6
DSA ist der Game-Changer für 1M+: Statt alle n Tokens ansehen, nur Top-256 (oder 512). Ermöglicht 1M Context praktisch. DeepSeek-V3.2 (2025) zeigt das live mit DSA.