IndexCache: Wie DeepSeek O(NL²)-Kosten in Sparse Attention um 75% reduziert

DeepSeek Sparse Attention (DSA) versprach eine Revolution: Statt teurer O(L²)-Aufmerksamkeit über alle Token zu berechnen, identifiziert ein effizienter Indexer nur die wichtigsten k Token (k=2048) und führt die Aufmerksamkeit nur auf diesen aus. Das reduziert die Kernkomplexität von O(L²) auf O(Lk). Doch hinter der Lösung verbirgt sich ein neuer Flaschenhals – einer, der selten diskutiert wird.

Der Indexer selbst muss für jede Schicht alle vorherigen Token bewerten, um die Top-k zu bestimmen. Obwohl er pro FLOP günstig ist, summiert sich sein Rechenaufwand über N Schichten auf O(NL²). Bei langen Kontexten wird der Indexer zum teuersten Bestandteil – nicht die Aufmerksamkeit, die er eigentlich optimieren sollte. Die Forscher hinter IndexCache haben diesen Widerspruch erkannt und eine überraschend einfache Lösung entwickelt.

Der unsichtbare Datenstrom: Warum Indexer redundant arbeiten

Die Kernidee von IndexCache basiert auf einer Beobachtung, die zunächst kontraintuitiv wirkt: Adjacent Schichten wählen fast dieselben Token aus. Eine Analyse der DeepSeek-Modelle zeigt, dass zwischen aufeinanderfolgenden Schichten eine Überschneidung von 70 bis 100% in den ausgewählten Token-Pools besteht. Selbst die Heatmaps offenbaren klare Muster – bestimmte Schichtenblöcke (z. B. Schichten 3–5 oder 17–30) konzentrieren sich auf dieselben kritischen Token.

Diese Redundanz ist kein Zufall, sondern ein inhärentes Merkmal der Modellarchitektur. Die Berechnung desselben Index mehrmals hintereinander ist reine Verschwendung von Rechenleistung. IndexCache nutzt diese Erkenntnis, indem es die Schichten in zwei Kategorien unterteilt:

• Full-Schichten (F): Führen die volle Indexer-Berechnung durch und speichern das Ergebnis im Cache.
• Shared-Schichten (S): Nutzen den Cache der letzten Full-Schicht und überspringen die Indexer-Berechnung.

Die erste Schicht ist stets eine Full-Schicht, da sie den Cache initialisieren muss. Alle anderen Schichten entscheiden dynamisch, ob sie den Cache nutzen oder eine neue Berechnung durchführen.

Einfache Implementierung, enorme Effizienzgewinne

Die Implementierung von IndexCache erfordert keine architektonischen Änderungen am Modell. Der einzige Unterschied zum Standard-DSA ist eine einfache Routing-Entscheidung in der Inferenzschleife:

for l = 1 to N:
    if c_l == F:
        I⁽ˡ⁾ ← Indexer_l(X)
        T⁽ˡ⁾ ← top-k(I⁽ˡ⁾)
        T_cache ← T⁽ˡ⁾
    else:  # c_l == S
        T⁽ˡ⁾ ← T_cache  # Cache-Nutzung
    X ← SparseAttn_l(X, T⁽ˡ⁾)
    X ← FFN_l(X)

Der T_cache-Puffer ist ein temporärer Speicher, der lediglich das aktuelle Indexergebnis hält. Er benötigt keinen zusätzlichen GPU-Speicher, da er bei jeder Full-Schicht überschrieben wird. Die einzige Änderung besteht in einer bedingten Anweisung, die entscheidet, ob der Indexer ausgeführt oder der Cache genutzt wird.

Wie der Indexer funktioniert und warum MLA entscheidend ist

Der Indexer selbst ist eine Weiterentwicklung der Lightning-Indexer-Architektur aus DeepSeek. Seine Funktionsweise ist simpel, aber effizient:

• Für jede Position i wird ein Score s_i = q · W_i + b_i berechnet.
• Eine ReLU-Aktivierung filtert negative Scores: g_i = max(0, s_i).
• Die Top-k Positionen werden durch argmax_i(g_i) bestimmt.

Der entscheidende Vorteil liegt in der Integration mit Multi-head Latent Attention (MLA). MLA komprimiert die Key-Value-Paare aller Attention-Heads in einen niedrigdimensionalen latenten Vektor. Der Indexer arbeitet auf dieser komprimierten Darstellung, was die Berechnung pro FLOP deutlich reduziert. Ohne MLA wäre der Indexer selbst zu kostspielig.

Zwei Strategien zur Schichtoptimierung: Warum naive Ansätze scheitern

Die Forscher testeten mehrere Methoden, um die Full- und Shared-Schichten zu verteilen. Ein naiver Ansatz – etwa eine feste Abfolge wie F S S S F S S S – scheiterte kläglich. Der Grund: Die Sensitivität der Schichten gegenüber der Indexer-Nutzung variiert stark. Einige Schichten, insbesondere in frühen oder Übergangsphasen, sind kritisch für die Leistung. Eine starre Abfolge kann dazu führen, dass kritische Schichten Shared werden, während redundante Full-Schichten bleiben.

Training-freie Optimierung: Greedy-Suche mit minimalem Verlust

Der einfachste Ansatz erfordert keine Gewichtsanpassungen:

1. Beginne mit allen Schichten als Full-Schichten.
2. Nutze einen kleinen Kalibrierungsdatensatz (wiederverwendete Batch-Daten aus dem Training).
3. Probiere schrittweise aus, welche Full-Schicht zu einer Shared-Schicht umgewandelt werden kann, ohne den Modellverlust signifikant zu erhöhen.
4. Wähle bei jedem Schritt die Schicht aus, deren Umwandlung den geringsten Verlustanstieg verursacht.

Der Prozess ähnelt einer Greedy-Suche und erfordert O(N²) Forward-Passes. Bei Nutzung von Pipeline-Parallelität kann die Suche jedoch beschleunigt werden, indem Schichten in Blöcken parallel evaluiert werden.

Die Ergebnisse sind beeindruckend: Die optimierte Schichtverteilung übertrifft feste Abfolgen bei gleichem Reduktionsgrad. Interessanterweise zeigt die Verlustkurve einen deutlichen Knick – die ersten 20 Schichten sind leicht zu konvertieren, während spätere Schichten kritischer sind. Diese Rangfolge ist stabil und spiegelt eine inhärente Eigenschaft des trainierten Modells wider, nicht nur eine Kalibrierungsabhängigkeit.

Praktische Auswirkungen: Bis zu 75% weniger Rechenlast

Mit IndexCache können bis zu 75% der Indexer-Berechnungen eingespart werden, ohne die Modellleistung signifikant zu beeinträchtigen. In Tests mit dem 30-Milliarden-Parameter-Modell GLM-5.2 und DeepSeek Sparse Attention zeigte sich:

• Die Effizienzgewinne sind konsistent über verschiedene Kontextlängen.
• Die Modellgenauigkeit bleibt nahezu unverändert.
• Die Implementierung erfordert keine Architekturänderungen und ist mit bestehenden DeepSeek-Modellen kompatibel.

IndexCache demonstriert, wie kleine algorithmische Optimierungen enorme Auswirkungen auf die Effizienz großer Sprachmodelle haben können. Statt auf komplexe Neuentwicklungen zu setzen, nutzt die Methode vorhandene Muster in der Modellarchitektur – und spart dabei Rechenleistung, Speicher und Energie.

Die Zukunft der effizienten Inferenz könnte in solchen subtilen, aber wirkungsvollen Ansätzen liegen. Während andere Methoden auf Quantisierung oder Pruning setzen, zeigt IndexCache, dass manchmal die einfachsten Ideen die größten Fortschritte bringen.