Sparse Attention

Einfach erklärt

Normale Attention in Transformern vergleicht jedes Token mit jedem anderen – das wird bei langen Texten extrem aufwändig. Sparse Attention schaut nur auf ausgewählte Tokens und spart so massiv Rechenzeit.

Das Problem mit Full Attention:

Kontext: 1.000 Tokens  → 1.000.000 Vergleiche (OK)
Kontext: 10.000 Tokens → 100.000.000 Vergleiche (langsam)
Kontext: 100.000 Tokens → 10.000.000.000 Vergleiche (unmöglich)

Komplexität: O(n²) – quadratisch!

Sparse Attention Lösung:

Statt: Jedes Token → Alle anderen Tokens
       [████████████████████████████]

Sparse: Jedes Token → Lokale + Ausgewählte Tokens
        [███░░░░░█░░░░░░░█░░░░░░░███]
        ↑ Lokal  ↑ Global    ↑ Lokal

Sparse Attention Patterns:

Pattern	Beschreibung	Beispiel
Sliding Window	Nur N Nachbarn	Longformer
Global Tokens	Spezielle Tokens sehen alles	[CLS], [SEP]
Strided	Jedes k-te Token	BigBird
Random	Zufällige Verbindungen	BigBird

Technischer Deep Dive

Attention Komplexität

Full Self-Attention:

Attention(Q, K, V) = softmax(QK^T / √d) V

Speicher: O(n²) für Attention Matrix
Compute: O(n² × d) für Matrix-Multiplikation

Sparse Attention:

Nur ausgewählte (i,j) Paare berechnen

Speicher: O(n × k) wobei k << n
Compute: O(n × k × d)

Sliding Window Attention

def sliding_window_attention(Q, K, V, window_size=512):
    """
    Jedes Token sieht nur window_size Nachbarn
    """
    n = Q.shape[0]
    output = torch.zeros_like(Q)
    
    for i in range(n):
        start = max(0, i - window_size // 2)
        end = min(n, i + window_size // 2)
        
        # Attention nur auf Fenster
        local_K = K[start:end]
        local_V = V[start:end]
        
        scores = Q[i] @ local_K.T / sqrt(d)
        weights = softmax(scores)
        output[i] = weights @ local_V
    
    return output

Longformer Pattern

Token:     [CLS] w1  w2  w3  w4  w5  w6  w7  w8  [SEP]

[CLS]:     ████████████████████████████████████  (Global)
w1:        ████████░░░░░░░░░░░░░░░░░░░░░░░░░░░░  (Lokal)
w2:        ████████████░░░░░░░░░░░░░░░░░░░░░░░░  (Lokal)
w3:        ░░████████████░░░░░░░░░░░░░░░░░░░░░░  (Lokal)
...
[SEP]:     ████████████████████████████████████  (Global)

• Lokale Attention: Sliding Window für alle Tokens
• Globale Attention: Spezielle Tokens sehen/werden von allen gesehen

BigBird Pattern

Kombiniert drei Patterns:

def bigbird_attention_mask(n, window_size, num_global, num_random):
    mask = torch.zeros(n, n)
    
    # 1. Sliding Window
    for i in range(n):
        start = max(0, i - window_size // 2)
        end = min(n, i + window_size // 2)
        mask[i, start:end] = 1
    
    # 2. Global Tokens (erste und letzte)
    mask[:num_global, :] = 1  # Global sieht alle
    mask[:, :num_global] = 1  # Alle sehen Global
    
    # 3. Random Connections
    for i in range(n):
        random_indices = torch.randint(0, n, (num_random,))
        mask[i, random_indices] = 1
    
    return mask

FlashAttention (Orthogonal)

FlashAttention ist keine Sparse Attention, sondern eine effizientere Implementierung:

Standard Attention:
1. Berechne QK^T (n×n Matrix im Speicher)
2. Softmax
3. Multipliziere mit V

FlashAttention:
1. Teile in Blöcke
2. Berechne blockweise (weniger Speicher)
3. Akkumuliere Ergebnisse

→ Gleiche Mathematik, weniger Speicher, schneller

Vergleich

Methode	Komplexität	Speicher	Qualität
Full Attention	O(n²)	O(n²)	100%
Sliding Window	O(n×w)	O(n×w)	~98%
Longformer	O(n×w + n×g)	O(n×w)	~99%
BigBird	O(n×(w+r+g))	O(n×w)	~99%
FlashAttention	O(n²)	O(n)	100%

Praktische Anwendung

from transformers import LongformerModel, LongformerTokenizer

tokenizer = LongformerTokenizer.from_pretrained("allenai/longformer-base-4096")
model = LongformerModel.from_pretrained("allenai/longformer-base-4096")

# Lange Dokumente verarbeiten
text = "..." * 4000  # 4000 Tokens
inputs = tokenizer(text, return_tensors="pt", max_length=4096)

# Global Attention für [CLS]
inputs["global_attention_mask"] = torch.zeros_like(inputs["input_ids"])
inputs["global_attention_mask"][:, 0] = 1  # [CLS] ist global

outputs = model(**inputs)