🤖 machine learning

Trees from Marginals: Autoregressive drafting with factorized priors

Das Paper stellt Weaver vor, einen leichtgewichtigen autoregressiven Adapter, der bedingte Abhängigkeiten aus faktorisierte Entwurfs-Marginalen rekonstruiert, um effizientes baumbasiertes spekulatives Dekodieren zu ermöglichen, wobei durch einen neuartigen Rollback-freien Verifizierungsalgorithmus und optimierte CUDA-Kernel eine 4,37-fache Beschleunigung gegenüber dem Standard-Autoregressiven Dekodieren erreicht wird.

Ursprüngliche Autoren: Yuma Oda, Ryan Mathieu, Roman Knyazhitskiy, Artur Chakhvadze

Veröffentlicht 2026-07-09

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Yuma Oda, Ryan Mathieu, Roman Knyazhitskiy, Artur Chakhvadze

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 Geschichte mit einem sehr klugen, aber langsamen Bibliothekar (dem KI-Modell) zu schreiben. Jedes Mal, wenn Sie nach dem nächsten Wort der Geschichte fragen, muss der Bibliothekar innehalten, intensiv nachdenken, seine gesamte riesige Bibliothek an Büchern prüfen und Ihnen dann das nächste Wort zuflüstern. So funktioniert die heutige KI: ein Wort nach dem anderen, Schritt für Schritt. Es ist präzise, aber langsam.

Das Paper stellt eine neue Methode vor, um diesen Bibliothekar viel schneller zu machen, ohne die Genauigkeit zu verlieren. Sie nennen ihre Methode „Trees from Marginals“ (oder DFlash-TfM). Hier ist die Funktionsweise, unterteilt in einfache Analogien.

Das Problem: Die Grenze des „Rate-Spiels“

Um die Geschwindigkeit zu erhöhen, erfanden Forscher einen Trick namens Speculative Decoding.

Der alte Weg: Ein schneller, junioriger Assistent (der „Drafter“) rät die nächsten paar Wörter. Dann prüft der langsame Bibliothekar (der „Verifier“), ob diese Vermutungen richtig sind. Wenn sie stimmen, akzeptiert der Bibliothekar sie alle auf einmal. Wenn nicht, korrigiert der Bibliotheker den Fehler und beginnt von vorn.
Das Problem mit „faktorisierten“ Draftern: Einige Assistenten sind super schnell, weil sie alle nächsten Wörter gleichzeitig erraten, wobei sie ignorieren, wie diese miteinander zusammenhängen. Es ist wie ein Koch, der die nächsten drei Zutaten einer Suppe rät, ohne die vorherigen probiert zu haben.
- Der Haken: Je länger die Liste der Vermutungen wird, desto schlechter wird der Koch darin, die Sequenz zu erraten. Die erste Vermutung mag richtig sein, aber die dritte ist meistens falsch, weil sie die ersten beiden nicht berücksichtigt hat. Dies begrenzt die Anzahl der Wörter, die gleichzeitig akzeptiert werden können.

Die Lösung: Der „Weaver“-Assistent

Die Autoren entwickelten ein neues System, das die Geschwindigkeit des schnellen Kochs mit der Logik eines sorgfältigen Editors kombطiniert. Sie nennen den neuen Editor Weaver.

Die „Top-K“-Shortlist: Zuerst erstellt der schnelle Assistent (DFlash) eine schnelle, grobe Vermutung und liefert eine Shortlist der 512 wahrscheinlichsten Wörter für die nächste Stelle. Es ist wie ein Koch, der sagt: „Ich denke, die nächste Zutat ist wahrscheinlich eines dieser 512 Gewürze.“
Die Aufgabe des Weavers: Anstatt blind zu raten, betrachtet der Weaver (eine winzige, leichtgewichtige KI) diese Shortlist. Er fungiert wie ein kluger Editor, der sagt: „Okay, wenn das erste Wort ‚Salz‘ war, dann ist das nächste Wort fast sicher ‚Pfeffer‘ und nicht ‚Zucker‘.“
Das Bauen eines Baums: Der Weaver erstellt nicht nur eine gerade Linie von Vermutungen. Er baut einen Baum.
- Stellen Sie sich einen Stammbaum vor. Die Wurzel ist der aktuelle Satz.
- Der Weaver verzweigt sich und erschafft verschiedene mögliche Pfade für die Geschichte (z. B. „Die Katze saß auf der Matte“ vs. „Die Katze saß auf dem Boden“).
- Da der Weaver klein ist und nur die vom schnellen Assistenten bereitgestellte Shortlist betrachtet, ist er unglaublich schnell darin, diesen Baum aus Möglichkeiten aufzubauen.

Die Verifizierung: Den Baum prüfen

Nun muss der langsame Bibliothekar diesen Baum an Wörter prüfen.

Das alte Problem: Wenn der Bibliothekar ein standardmäßiges „rekurrentes“ Gedächtnissystem verwendet (wie die Gated Delta Net-Schichten in moderner KI), ist das Prüfen eines Baums normalerweise ein Albtraum. Es ist, als müsste man jeden einzelnen Zweig eines Baumes nacheinander abwandern, um zu sehen, welcher Pfad real ist. Das ist langsam.
Der neue Trick: Die Autoren haben einen speziellen mathematischen Shortcut (einen „Rollback-freien“ Algorithmus) erfunden.
- Anstatt jeden Zweig abzuwandern, verwenden sie ein maskiertes triangulares Lösen (masked triangular solve). Denken Sie an eine magische Karte, die es dem Bibliothekar ermöglicht, die gesamte Baumstruktur auf einmal zu betrachten und sofort zu wissen, welcher Pfad der richtige ist, ohne den Speicherzustand für jeden einzelnen Zweig neu berechnen zu müssen.
- Dies ist wie ein GPS, das die korrekte Route auf einer komplexen Karte sofort hervorhebt, ohne dass man erst jede Sackgasse abfahren muss.

Das Ergebnis: Geschwindigkeit und Effizienz

Durch die Kombination dieser Ideen erzielt das System zwei große Erfolge:

Mehr akzeptierte Wörter: Da der Weaver die Logikfehler des schnellen Assistenten korrigiert, akzeptiert der Bibliothekar längere Wortketten (bis zu 77 % mehr als die bisher beste Methode).
Massiver Geschwindigkeitsvorteil: Der gesamte Prozess ist so effizient, dass die KI Text 4,37-mal schneller generiert als die standardmäßige langsame Methode. Sie schlägt auch die bisher „schnellste“ Methode um etwa 25 %.

Zusammenfassende Analogie

Standard-KI: Eine Schnecke, die eine Geschichte schreibt, einen Buchstaben nach dem anderen, während sie jeden Buchstaben mit einem Wörterbuch abgleicht.
Alte schnelle Methode: Ein Schnellleser, der den nächsten Absatz rät, aber oft den mittleren Teil des Absatzes falsch macht, weil er dem Anfang nicht genügend Aufmerksamkeit geschenkt hat.
Diese neue Methode (Weaver): Ein Schnellleser, der schnell die 500 Wörter auswählt, die passen könnten, und ein winziger, super-schlauer Editor (Weaver), der diese Wörter sofort zu einer verzweigenden Baumstruktur der logischsten Sätze anordnet. Eine spezielle „magische Karte“ (der neue Kernel) prüft dann den gesamten Baum sofort, um zu sehen, welcher Pfad real ist.

Das Ergebnis ist eine KI, die so schnell schreibt wie ein Schnellleser, aber die Genauigkeit eines sorgfältigen Editors besitzt, wodurch Interaktionen viel unmittelbarer und reaktionsschneller wirken.

Technisches Resümee: Bäume aus Marginalen (DFlash-TfM)

Problemstellung

Autoregressive Large Language Models (LLMs) sind inhärent sequenziell und generieren pro Schritt einen Token. Diese sequenzielle Natur erzeugt einen speichergebundenen Flaschenhals, bei dem die Latenz eher durch die DRAM-Bandbreite als durch die Rechenleistung dominiert wird, was zu einer schlechten Energieeffizienz und begrenzter Interaktivität (dekodierte Token pro Sekunde pro Sequenz) führt. Während spekulatives Dekodieren eine Lösung bietet, indem ein schnelles „Drafter“-Modell mehrere Token zur parallelen Verifizierung durch das Haupt-„Verifier“-Modell vorschlägt, stehen bestehende Ansätze vor Trade-offs:

Faktorisierte Drafter: Modelle wie DFlash sagen zukünftige Token als konditionell unabhängige Marginale parallel voraus. Obwohl sie effizient sind, führt ihre Unabhängigkeitsannahme dazu, dass die Akzeptanzraten mit zunehmendem spekulativen Budget (Draft-Länge) stark sinken, da sie die konditionellen Abhängigkeiten zwischen den vorgeschlagenen Token nicht erfassen können.
Autoregressive Drafter: Diese erfassen Abhängigkeiten korrekt, verursachen jedoch einen hohen Overhead durch Full-Vocabulary-Projektionen bei jedem Schritt, was die Geschwindigkeitsgewinne zunichtemacht.
Verifizierung auf rekurrenten Modellen: Standardmäßige Baum-Verifizierungsalgorithmen verlassen sich auf Attention-Masks. Moderne Modelle, die jedoch Gated Delta Net (GDN)-Layer verwenden (z. B. Qwen3.6), nutzen nicht-kommutative Zustandsübergänge, die keine einfache, durch Vorfahren eingeschränkte Maskierung unterstützen, was eine effiziente Single-Pass-Baumverifizierung zu einem offenen Problem macht.

Methodik: DFlash-TfM

Die Autoren schlagen DFlash-TfM (Trees from Marginals) vor, eine hybride Architektur, die die parallele Effizienz faktorisierter Drafter mit der konditionellen Genauigkeit autoregressiver Modelle kombiniert, zusammen mit einem neuartigen System-Level-Verifizierungskernel.

1. Der Weaver-Adapter

Die zentrale Innovation ist Weaver, ein leichtgewichtiger autoregressiver Adapter (56,7 Mio. Parameter), der auf einem beschränkten Vokabular operiert.

Input: Weaver nimmt die Hidden States eines vortrainierten faktorierten Drafters (DFlash) und des Verifiers entgegen.
Mechanismus: Anstatt auf das volle Vokabular zu projizieren, extrahiert Weaver die durch DFlash vorhergesagten Top- $K$ marginalen Token. Es sagt dann die residuelle Verteilung über dieses kleine Kandidatenset ( $K=512$ ) autoregressiv voraus.
Vorteil: Dies stellt die konditionellen Abhängigkeiten zwischen den Token wieder her (z. B. hängt Token $t+1$ vom realisierten Token $t$ ab), ohne die Speicherbandbreitenkosten einer Full-Vocabulary-Projektion zu verursachen. Das Modell konstruiert einen Vorschlagstree, dessen Zweige aus diesen konditionierten Residuen gesampelt werden.

2. Baumerstellung

Die Autoren modifizieren den DySpec-Baumerstellungsalgorithmus, um den Durchsatz zu verbessern. Anstatt einer streng sequenziellen Best-First-Expansion extrahieren sie die Top- $w$ Knoten aus dem Kandidaten-Heap und führen $w$ Expansionen gleichzeitig aus. Dies balanciert Speicherbandbreite und Rechenlast, sodass der vollständige Draft-Tree in $\lceil B/w \rceil$ sequenziellen Operationen konstruiert werden kann.

3. Rollback-freie Baumverifizierung für GDN

Um Modelle mit Gated Delta Net-Layern zu unterstützen, leiten die Autoren einen Rollback-freien Baumverifizierungsalgorithmus her:

Herausforderung: GDN-Layer aktualisieren den Zustand via $S_t = \alpha_t(I - \beta_t k_t k_t^\top)S_{t-1} + \beta_t k_t v_t^\top$ . Die nicht-kommutative Natur der Matrixaktualisierung verhindert die Verwendung standardmäßiger kumulativer Produktoptimierungen, wie sie bei diagonalen State-Space-Modellen üblich sind.
Lösung: Die Autoren nutzen eine Chunked-Form der linearen Rekurrenz. Sie formulieren die Verifizierung als eine maskierte dreieckige Lösung (masked triangular solve) über die Baumstruktur.
- Der Baum wird topologisch sortiert.
- Der Algorithmus berechnet Interaktionsmatrizen ( $X$ und $Y$ ), die die Vorfahren-Beziehungen repräsentieren.
- Er löst ein lineares System $(I+X)U = \beta V$ , um Ausgaben zu berechnen, ohne den rekurrenten Zustand spekulativ zu aktualisieren.
- Die Zustandsbindung (State Commitment) wird bis zur nächsten Dekodierungsiteration verzögert, sobald der akzeptierte Zweig bekannt ist. Dies eliminiert die Notwendigkeit eines State-Rollbacks.
Implementierung: Dies wird als fusionierter CUDA-Kernel in SGLang implementiert, der die Gram-Matrix berechnet, das System via Tiled Forward Substitution löst und die Output-Phase in einem einzigen Durchgang anwendet.

Zentrale Beiträge

Hybride Architektur: Einführung von DFlash-TfM, das einen leichtgewichtigen autoregressiven Adapter (Weaver) verwendet, um faktorisierte Marginale zu konditionieren, wodurch die Akzeptanzraten-Obergrenze reiner faktisierter Drafter bei langen Tiefen angehoben wird.
Theoretische Erkenntnis: Analyse, die zeigt, dass die Akzeptanzrate faktisierter Drafter durch die Total Variation (TV) Distanz zwischen marginalen und konditionellen Verteilungen begrenzt ist und dass die Konditionierung auf realisierte Token (via Weaver) es dem Hybridmodell ermöglicht, die theoretischen Grenzen eines reinen Marginal-only Drafters zu übertreffen.
Systemoptimierung: Ableitung eines neuartigen, Rollback-freien Baumverifizierungsalgorithmus für Gated Delta Net-Layer, der die effiziente spekulative Dekodierung für Modelle wie Qwen3.6 ermöglicht, die zuvor schwer zu optimieren waren.
Implementierung: Optimierte CUDA-Kernel für SGLang, die die Verifizierungsschritte fusionieren und so die Latenz im Vergleich zu pro-Zweig rekurrenten Baselines signifikant reduzieren.

Experimentelle Ergebnisse

Evaluierung auf Qwen3.6-27B (bfloat16) unter Verwendung einer NVIDIA B200 GPU über Chat-, Math- und Code-Benchmarks:

Speedup: DFlash-TfM erreicht einen 4,37× Speedup gegenüber dem Standard-autoregressiven Dekodieren.
Baseline-Vergleich: Es übertrifft eine hochoptimierte DFlash-Baseline um 24,7 % und eine DDTree-Baseline um 10–30 %, abhängig vom Datensatz.
Akzeptanzlänge: Die Methode erhöht die mittlere Akzeptanzlänge (Mean Acceptance Length, MAL) um 77 % im Vergleich zur Chain-DFlash-Baseline und um 32 % im Vergleich zu DDTree bei gleicher Baumgröße.
Verifizierungseffizienz: Der fusionierte Kernel skaliert signifikant besser als die pro-Zweig rekurrenten Verifizierungen. Bei einer Baumgröße von 128 Token ist der fusionierte Kernel 7,1× schneller als die rekursive Baseline. Der Verifizierungsschritt macht nur etwa 12 % der gesamten Dekodierzeit aus.

Bedeutung und Behauptungen

Das Paper behauptet, dass die primäre Limitierung faktisierter Drafter struktureller Natur ist (Unabhängigkeitsannahme) und nicht ein Mangel an Modellkapazität. Durch die Einführung eines leichtgewichtigen autoregressiven Adapters, der auf einem beschränkten Vokabular operiert, zeigen die Autoren, dass es möglich ist, die bedingten Abhängigkeiten wiederherzustellen und hohe Akzeptanzraten zu erzielen, ohne den Overhead von Full-Vocabulary-Projektionen zu verursachen.

Darüber hinaus adressiert die Arbeit eine kritische Systemlücke: die Ermöglichung effizienten spekulativen Dekodierens für Modelle mit nicht-diagonalen rekurrenten Layern (GDN). Der vorgeschlagene Rollback-freie Verifizierungskernel eliminiert die Notwendigkeit eines State-Rollbacks, was das Baum-basierte spekulative Dekodieren für eine breitere Klasse moderner Architekturen praktikabel macht. Die Autoren kommen zu dem Schluss, dass diese kombinierten Modell- und Systembeiträge eine State-of-the-Art-Verbesserung der Interaktivität für lokale und serverseitige LLM-Inferenz darstellen.