🤖 machine learning

COBS: Cumulant Order Block Sparse Attention

Dieses Paper führt COBS ein, eine Block-Sparse-Attention-Methode, die die Retrieval-Performance in langen Kontexten durch den Einsatz eines neuartigen Selektors mit komprimierten statistischen Parammen zweiter Ordnung verbessert, um die Attention-Masse besser zu approximieren und dadurch die Qualitätslücke zu dichter Attention signifikant zu schließen, während die Hardware-Effizienz beibehalten wird.

Ursprüngliche Autoren: Alexander Tian, Aditya Ghai, Sanjit Neelam, Zaal Vasania, Akshay Mishra

Veröffentlicht 2026-07-13

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Alexander Tian, Aditya Ghai, Sanjit Neelam, Zaal Vasania, Akshay Mishra

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, eine ganz bestimmte Nadel in einem riesigen Heuhaufen zu finden, aber der Heuhaufen ist so groß, dass Ihr Gehirn (oder Computer) den Dienst quittiert, wenn Sie jedes einzelne Strohhalm einzeln betrachten würden. Dies ist das Problem, vor dem moderne KI-Modelle stehen, wenn sie versuchen, sehr lange Dokumente zu lesen. Sie müssen sich an alles erinnern, was sie bisher gelesen haben, und das Überprüfen jedes einzelnen Speicher-Tokens ist langsam und teuer.

Um dies zu lösen, versuchten Forscher einen Abkürzung namens Block Sparse Attention. Anstatt nach jedem einzelnen Strohhalm zu suchen, entschieden sie sich, kleine Bündel von Strohhalmen (genannt „Blocks“) zu betrachten und nur die interessantesten davon genauer zu untersuchen. Es ist, als würde man einen Scout engagieren, der einige Bündel scannt und dann sagt, welche davon die Nadel enthalten könnten.

Das Problem: Der Scout war zu einfach

Die Arbeit untersucht eine populäre Methode namens NSA (Native Sparse Attention). In diesem System schaut der Scout in ein Strohbündel und gibt eine schnelle Schätzung ab, ob es wichtig ist. Die Arbeit entdeckte, dass dieser Scout einen sehr einfachen Trick anwandte: Er betrachtete nur die durchschnittliche Position der Strohhalme im Bündel.

Stellen Sie sich das so vor: Stellen Sie sich zwei Strohbündel vor.

Bündel A hat Strohhalme, die alle eng zusammen in der Mitte gepackt sind.
Bündel B hat Strohhalme, die wild verstreut sind, einige weit links und einige weit rechts.

Wenn man nur auf die durchschnittliche Position schaut, sehen beide Bündel exakt gleich aus! Aber in Wirklichkeit ist Bündel B viel wahrscheinlicher der Ort, an dem die Nadel liegt, weil es eine größere Fläche abdeckt. Die alten Scouts (First-Order-Methoden) waren blind für diese „Verteilung“ oder „Krümmung“. Sie waren wie jemand, der versucht, die Form einer Wolke zu erraten, indem er nur auf deren Mittelpunkt schaut; sie übersahen die flauschigen Ränder, die eigentlich entscheidend sind.

Die Lösung: COBS (Der intelligentere Scout)

Die Autoren schlagen eine neue Methode namens COBS (Cumulant Order Block Sparse Attention) vor. Anstatt nur die durchschnittliche Position anzugeben, trägt der COBS-Scout eine winzige, komprimierte Karte bei sich, die nicht nur zeigt, wo die Strohhalme im Durchschnitt liegen, sondern auch, wie sie verteilt sind.

In mathematischen Begriffen nennt die Arbeit dies eine „Second-Order-Statistik“ oder „Kovarianz“. In unserer Analogie ist es so, als würde der Scout erkennen: „Hey, dieses Bündel ist breit und unordentlich, also ist die Chance höher, dass die Nadel darin steckt!“ Indem er diese zusätzliche Information beibehält (aber sie so komprimiert, dass sie nicht zu viel Platz einnimmt), kann COBS viel bessere Vorhersagen treffen.

Die Ergebnisse: Ein riesiger Sprung nach vorn

Das Team testete dies in einer berühmten Herausforderung namens 32k RULER Benchmark (ein Test für 11 verschiedene Long-Context-Retrieval-Aufgaben). Hier ist, was sie herausfanden:

Der alte Weg (NSA MLP): Der einfache Scout erreichte einen Wert von 0,2999. Er hatte Schwierigkeiten, die Nadeln zu finden.
Der perfekte Weg (OSA): Wenn man magisch die exakte Antwort wüsste, ohne irgendwelche Abkürzungen zu nutzen (genannt „Oracle“), würde man einen Wert von 0,9040 erreichen.
Der neue Weg (COBS): Der intelligente Scout mit der Verteilungs-Karte erreichte einen Wert von 0,8195.

Das bedeutet, dass COBS etwa 86 % der Lücke zwischen der kämpfenden alten Methode und der perfekten Methode geschlossen hat. Das ist eine enorme Verbesserung!

Die Kosten: Ist es das wert?

Normalerweise bedeutet klüger zu werden auch, mehr Arbeit zu leisten. Aber COBS ist effizient.

Die alte Methode las eine bestimmte Menge an Daten.
Die perfekte Methode (die alles liest) liest 15,15-mal mehr Daten als COBS.
COBS liest nur 1,21-mal mehr Daten als die alte, einfache Methode.

Somit erreicht COBS fast die Perfektion, während es nur einen winzigen Bruchteil mehr Arbeit verlangt als die alte, einfache Methode.

Wogegen die Arbeit „Nein“ sagt

Die Autoren waren sehr sorgfältig dabei, einige Ideen auszuschließen, die wie gute Abkürzungen erscheinen könnten, aber tatsächlich nicht funktionieren:

Einfach mehr Komplexität zum Durchschnitt hinzufügen: Sie versuchten, einen schicken neuronalen Netzwerk-Ansatz (MLP) zu verwenden, um die „Durchschnitts“-Vorhersage intelligenter zu machen, aber es half nicht viel. Das Problem war nicht die Komplexität des Durchschnitts; das Problem war, dass der Durchschnitt an sich das falsche Werkzeug war. Man benötigt die Information über die „Verteilung“, nicht einen besseren Durchschnitt.
Die „Verteilung“ in einer einfachen Box betrachten: Eine andere Methode versuchte, die Verteilung zu erraten, indem sie das Minimum und Maximum der Strohhalme betrachtete (eine Box). Dies half ein wenig, war aber nicht so präzise wie die Karte der Verteilung von COBS.
Noch komplexere Mathematik hinzufügen (Third-Order): Die Autoren testeten das Hinzufügen einer „Schiefe“ (ein Maß dafür, wie asymmetrisch die Verteilung ist). Überraschenderweise machte dies die Dinge bei geringer Komplexität sogar schlechter und führte dazu, dass das Modell verwirrt wurde. Es half nur, wenn das Modell bereits sehr komplex war und versagte, wirkte also eher wie ein Pflaster als wie eine echte Lösung. Sie entschieden sich dafür, bei der „Verteilung“ (Second-Order) als dem optimalen Mittelweg zu bleiben.

Wie sicher sind sie?

Die Autoren sind sehr zuversichtlich bei diesen Zahlen, da sie kontrollierte Experimente durchgeführt haben. Sie haben nicht nur geraten; sie haben die Leistung im 32k RULER-Test gemessen und festgestellt, dass COBS die alten Methoden konsistent übertrifft. Sie prüften auch, dass dies die Fähigkeit des Modells, kurze Sätze zu verstehen, nicht beeinträchtigte (tat es nicht), und dass es dem Modell tatsächlich half, das nächste Wort in langen Texten besser vorherzusagen als die alten Methoden.

Dennoch sind die Autoren ehrlich über die Grenzen:

Sie haben dies an einem Modell mit etwa 1,2 Milliarden Parametern getestet. Sie wissen nicht mit Sicherheit, ob es bei den massiven Modellen, die von großen Tech-Unternehmen verwendet werden, exakt gleich funktioniert, obwohl die Mathematik nahelegt, dass es das sollte.
Sie haben das Modell auf einer spezifischen Art von synthetischen Daten (RULER-Stil) trainiert, um die Long-Context-Fähigkeit zu testen. Obwohl dies ein Standardverfahren zur Testung der Long-Context-Fähigkeit ist, könnten reale Daten sich etwas anders verhalten.

Das Fazit

Die Arbeit zeigt, dass man, um Nadeln effizient in einem Heuhaufen zu finden, nicht nur auf die Mitte des Bündels schauen darf. Man muss wissen, wie das Bündel verteilt ist. Durch das Hinzufügen einer winzigen, komprimierten Karte dieser Verteilung ermöglicht COBS es KI-Modellen, lange Dokumente viel genauer zu lesen, ohne sie zu verlangsamen – und schließt damit die Lücke zwischen „gut genug“ und „perfekt“ mit minimalem zusätzlichem Aufwand.

Technisches Resümee: COBS (Cumulant Order Block Sparse Attention)

1. Problemstellung

Die Inferenz von Large Language Models (LLMs) bei langen Kontextlängen wird durch die Speicherbandbreite und nicht durch die Rechenleistung begrenzt. Speziell die Leseoperation des Key-Value (KV)-Caches, die für die dichte Attention erforderlich ist, begrenzt die Dekodierungsgeschwindigkeit und führt zu einer Unterauslastung der Hardware. Während Block-Sparse-Attention eine hardwarefreundliche Lösung bietet, indem sie nur zusammenhängende Token-Blöcke liest, bleibt sie in führenden Open-Weight-Modellen untergenutzt. Bestehende Methoden verlassen sich oft auf dichte Attention, feinkörnige Token-Selektion oder KV-Eviction.

Die primäre Herausforderung bei der Block-Sparse-Attention ist die Block-Selektion: die Identifizierung der Blöcke im KV-Cache, die die relevantesten Informationen für einen gegebenen Query enthalten, ohne die vollständigen Keys und Values jedes Blocks lesen zu müssen. Aktuelle State-of-the-Art-Methoden, wie DeepSeeks Native Sparse Attention (NSA), nutzen eine „First-Order“-Selektionsstrategie. Diese Methoden fassen Blöcke in einem query-unabhängigen Vektor zusammen (z. B. via MLP oder Mean-Pooling) und bewerten diese linear gegen den Query. Die Arbeit postuliert, dass diese First-Order-Approximationen die nichtlineare Krümmung der Attention-Masse nicht erfassen können, was zu signifikanten Leistungsunterschieden gegenüber der dichten Attention führt.

2. Methodik

2.1 Theoretische Grundlage: Der Selektions-Oracle

Die Autoren formalisieren die Block-Selektion als das Problem der Rekonstruktion von dichten Attention-Outputs aus einer Teilmenge von Blöcken. Sie leiten ab, dass das optimale Selektionskriterium darin besteht, Blöcke nach ihrer Attention-Masse ( $m_b$ ) zu ranken, definiert als die Summe der Attention-Scores innerhalb eines Blocks:
$m_b = \sum_{r \in b} e^{q^T k_r}$
Ein „Oracle Sparse Attention“ (OSA), das Blöke basierend auf der exakten Attention-Masse auswählt (was das Lesen aller Keys erfordert), erreicht nahezu die Leistung der dichten Attention, was beweist, dass das Selektionskriterium an sich fundiert ist. Der Engpass liegt in der Schätzung dieser Masse aus einer kompakten, query-unabhängigen Zusammenfassung.

2.2 Die Kumulanten-Expansion

Die Arbeit analysiert die Schätzung der Attention-Masse mittels einer Kumulanten-Expansion (äquivalent zur Taylor-Entwicklung der Log-Momentengenerierenden Funktion). Die Log-Masse wird wie folgt expandiert:
$\ln m_b = \ln L + q^T \kappa_1 + \frac{1}{2} q^T \kappa_2 q + \dots$
Wobei:

$\kappa_1$ der Block-Mittelwert der Keys ( $\bar{k}_b$ ) ist.
$\kappa_2$ die Kovarianz der Keys innerhalb des Blocks ( $\Sigma_b$ ) ist.

Existierende First-Order-Selektoren (wie der MLP oder Mean-Pool von NSA) erfassen nur den linearen Term ( $q^T \bar{k}_b$ ) und vernachlässigen den Second-Order-Krümmungsterm ( $\frac{1}{2} q^T \Sigma_b q$ ). Dieses Auslassen führt dazu, dass sie versagen, wenn die Verteilung der Keys innerhalb eines Blocks eine signifikante Streuung relativ zur Query-Richtung aufweist, selbst wenn der Mittelwert ähnlich ist.

2.3 Die COBS-Methode

COBS (Cumulant Order Block Sparse Attention) adressiert dies, indem es den Second-Order-Term in den Selektionsprozess integriert. Die Methode baut auf der NSA-Architektur auf (die Kompression, Selektion und Sliding-Window-Zweige umfasst) und führt folgende Innovationen ein:

Second-Order Scoring: Anstatt nur eines Mittelwert-Vektors speichert der Block-Selektor den Block-Mittelwert der Keys ( $\bar{k}_b$ ) und eine komprimierte Repräsentation der Kovarianzmatrix innerhalb des Blocks ( $\Sigma_b$ ). Der Selektions-Score wird zu:
$\text{score}_b \approx q^T \bar{k}_b + \frac{1}{2} q^T \Sigma_b q$
Kovarianz-Kompression: Da das Speichern einer vollständigen $D \times D$ $D \times D$ Kovarianzmatrix speichertechnisch prohibitiv ist, nutzt COBS drei Kompressionstechniken:
- Low-Rank-Faktorisierung: Speicherung nur der obersten $r$ Eigenvektoren und Eigenwerte von $\Sigma_b$ .
- Subraum-Projektion: Projektion der Kovarianz in einen niederdimensionalen Query-Subraum (gespannt durch die obersten Eigenvektoren des zweiten Moments des Queries), was den Speicherbedarf von $rD$ auf $rs$ reduziert.
- Quantisierung: Speicherung der skalierten Eigenvektoren im FP4 (E2M1)-Format, während der Block-Mittelwert in BF16 gehalten wird.
NoPE (No Position Encoding): Die Kompressions- und Selektionszweige entfernen das Rotary Position Encoding (RoPE), um sicherzustellen, dass die Block-Zusammenfassungen ausschließlich von Inhalten abhängen und verhindert, dass Positionsrauschen die Zusammenfassung korrumpiert.

3. Zentrale Beiträge

Formalisierung der Selektion: Die Arbeit reduziert die Block-Selektion auf das Ranking nach der Attention-Masse und zeigt, dass ein Oracle mit exakten Massen nahezu die gesamte Leistung der dichten Attention wiederherstellt.
Kumulanten-Ordnungs-Analyse: Sie liefert eine theoretische Erklärung für die Einschränkungen bestehender First-Order-Selektoren, indem sie die verworfene Kovarianz innerhalb des Blocks als Quelle der Performance-Lücke identifiziert.
COBS-Algorithmus: Schlägt eine praktische Methode vor, die komprimierte Second-Order-Statistiken (Kovarianz) pro Block speichert, was eine genauere Approximation der Attention-Masse ermöglicht, ohne die vollständigen Keys lesen zu müssen.
Empirische Validierung: Zeigt, dass die Second-Order-Selektion die Lücke zwischen Sparse- und Dense-Attention in Long-Context-Benchmarks signifikant schließt.

4. Experimentelle Ergebnisse

4.1 Long-Context Retrieval (32k RULER)

Evaluierung auf einem 11-Aufgaben umfassenden 32k RULER-Benchmark:

NSA Baseline (MLP): Mittelwert Score von 0.2999.
NSA Mean-Pool (NoPE): Mittelwert Score von 0.5554 (zeigt den Nutzen von NoPE).
COBS (Subspace, $r=4$ , FP4): Mittelwert Score von 0.8195.
Dense Attention: Mittelwert Score von 0.9040.
Geschlossene Lücke: COBS schließt etwa 86 % der Lücke zwischen dem NSA-Baseline-Wert und der dichten Attention.
Verkehrseffizienz: COBS nutzt nur das 1,21-fache des KV-Cache-Lese-Traffics der NSA-Baseline und 15,15-mal weniger Traffic als die dichte Attention.

4.2 Short-Context und Sprachmodellierung

Short-Context Reasoning: COBS bewahrt die Leistung beim Kurzkontext-Common-Sense-Reasoning und erreicht Parität mit der dichten Attention in Standard-Benchmarks (OpenBookQA, PIQA, etc.).
Position-wise NLL: COBS erreicht die niedrigste durchschnittliche Next-Token Negative Log-Likelihood (NLL) von 1.633 (im Vergleich zu 1.727 bei Dense), was darauf hindeutet, dass die Verbesserungen beim Retrieval nicht zu Lasten der Long-Context-Sprachmodellierungsfähigkeiten gehen.

4.3 Ablationsstudien

Rank Sweep: Die Leistung erreicht ihren Höhepunkt bei $r=8$ und sinkt bei höheren Rängen ( $r=16$ ) aufgrund der Akkumulation von ungerichteter Varianzmasse von Distraktoren. Die Autoren empfehlen $r \le 8$ .
Subspace vs. Global: Adaptive pro-Layer Subraum-Dimensionen ( $s \approx 85$ ) performen vergleichbar zu einer globalen Dimension von 128, während sie die Speicherkosten senken.
Quantisierung: Es wurde gezeigt, dass die FP4-Quantisierung der Eigenvektoren im Wesentlichen verlustfrei ist.

5. Bedeutung und Behauptungen

Die Arbeit behauptet, dass die Kumulanten-Ordnung sowohl als diagnostisches Instrument für bestehende Sparse-Attention-Methoden als auch als praktischer Design-Parameter zur Verbesserung dient. Durch den Übergang von First-Order- (Mittelwert) zu Second-Order- (Kovarianz) Zusammenfassungen demonstriert COBS, dass Block-Sparse-Attention die Qualität der dichten Attention erreichen kann, während gleichzeitig eine signifikante Reduktion des Speicherbandbreiten-Verbrauchs beibehalten wird.

Die Autoren betonen, dass dies eine Mechanismus-Studie ist, die auf einer $\approx 1,2$ B Parameter-Skala mit spezifischen Trainingsprotokollen (RULER-artiges SFT) durchgeführt wurde. Sie behaupten nicht, dass dies ein einsatzbereites System für alle LLMs ist, sondern ein Beweis dafür, dass die theoretische Lücke in der Block-Selektion geschlossen werden kann. Die Arbeit legt nahe, dass Block-Sparsity, die in führenden Modellen oft fehlt, praktikabel ist, wenn der Selektionsmechanismus ausreichend expressiv ist (d. h. eine höhere Kumulanten-Ordnung besitzt).

Vom Autor angemerkte Limitationen:

Die Studie ist auf eine spezifische Backbone-Skala und Pretraining-Sequenzlänge beschränkt.
Der Vergleich verwendet eine kontrollierte NSA-Baseline mit spezifischen Hyperparametern (z. B. nicht überlappende Blöcke, große MLPs), die von den ursprünglichen NSA-Berichten abweichen.
Die Verwendung von NoPE in den Sparse-Zweigen gegenüber RoPE in den Dense-Zweigen führt zu einer Störvariable in den Long-Context-Vergleichen.
Die Ergebnisse stützen sich auf RULER-artiges Fine-Tuning, welches sich möglicherweise nicht perfekt auf alle Long-Context-Szenarien generalisiert.