💬 NLP

Cost-Aware Diffusion Draft Trees for Speculative Decoding

Dieses Paper führt CaDDTree ein, eine kostenbewusste spekulative Dekodierungsmethode, die sowohl die Struktur des Entwurfbaums als auch das Knotenbudget dynamisch optimiert, um den Token-Durchsatz durch die Nutzung der unimodalen Natur der Durchsatzfunktion zu maximieren, wodurch die Notwendigkeit einer Offline-Budgetabstimmung entfällt und gleichzeitig bestehende Oracle-optimierte Baselines erreicht oder übertrifft.

Ursprüngliche Autoren: Shuai Zhang, Huachuan Qiu, Hongliang He, Yong Dai

Veröffentlicht 2026-06-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Shuai Zhang, Huachuan Qiu, Hongliang He, Yong Dai

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 lange Geschichte zu schreiben, aber Sie haben eine sehr strenge Regel: Sie dürfen immer nur ein Wort auf einmal schreiben, und nach jedem einzelnen Wort müssen Sie anhalten, tief nachdenken und prüfen, ob dieses Wort Sinn ergibt. Genau so funktionieren aktuelle KI-Sprachmodelle. Es ist genau, aber es ist unglaublich langsam, weil der „Prüfpart“ sehr viel Zeit in Anspruch nimmt.

Um dies zu beschleunigen, nutzen Forscher einen Trick namens Speculative Decoding. Stellen Sie sich das wie einen schnellen, etwas weniger vorsichtigen Freund (den „Entwerfer“) vor, der für Sie die nächsten Wörter rät. Dann prüft der langsame, vorsichtige Experte (das „Zielmodell“) all diese Vermutungen auf einmal. Wenn der Experte diesen Worten zustimmt, erhalten Sie diese Wörter sofort. Wenn nicht, verwerfen Sie die falschen Wörter und versuchen es erneut.

Das Problem bei bisherigen Methoden war, dass sie wie ein Koch waren, der immer versucht, ein riesiges Bankett zuzubereiten, ungeachtet dessen, wie hungrig die Gäste tatsächlich sind. Sie haben versucht, eine große Anzahl von Wörtern zu raten (einen großen „Baum“ an Möglichkeiten), in der Hoffnung, Glück zu haben. Aber ein riesiges Bankett zuzubereiten, kostet Zeit. Manchmal wollen die Gäste nur ein Sandwich, und der Koch hat Zeit verschwendet, indem er ein Festmahl zubereitet hat, das niemand gegessen hat.

Hier ist, wie die neue Methode, CaDDTree, dies behebt:

1. Der alte Weg: „Mehr ist immer besser“

Vorherige Werkzeuge versuchten, so viele Wörter wie möglich zu raten, um die Chance zu maximieren, richtig zu liegen. Es war ihnen egal, wie viel Zeit die Überprüfung dieser Vermutungen kostete.

Die Analogie: Stellen Sie sich vor, Sie spielen ein Videospiel, bei dem Sie mehr „Leben“ kaufen können, um weiterspielen zu können. Die alte Strategie war, jedes Mal 1.000 Leben zu kaufen, selbst wenn Sie nur 2 brauchten, um das Level zu schaffen. Sie haben zu viel Geld (Zeit) für Leben ausgegeben, die Sie nie benutzt haben.

2. Die neue Erkenntnis: Es kommt auf den Moment an

Die Autoren stellten fest, dass der „schnelle Freund“ manchmal sehr selbstbewusst ist (er rät die richtigen Wörter leicht) und manchmal sehr verwirrt ist (er rät wild drauf los).

Die Analogie:
- Selbstbewusste Runde: Der Freund sagt: „Ich bin zu 99 % sicher, dass das nächste Wort ‚Der‘ ist.“ Sie benötigen nur eine winzige Prüfung. Ein massiver Baum an Vermutungen ist hier übertrieben und verschwendet Zeit.
- Verwirrte Runde: Der Freund sagt: „Ich habe keine Ahnung, es könnte ‚Der‘, ‚Ein‘, ‚Eine‘, ‚Aber‘... sein...“ Sie benötigen einen riesigen Baum an Vermutungen, um sicherzustellen, dass Sie das Richtige nicht verpassen.

Die alten Methoden verwendeten jedes Mal eine feste Größe für den Baum. Die neue Methode, CaDDTree, ändert die Größe des Baums jedes einzelne Mal basierend darauf, wie selbstbewusst der Freund ist und wie teuer die Überprüfung ist.

3. Das Gleichgewicht zwischen „Geschwindigkeit vs. Größe“

Die Arbeit führt ein neues Ziel ein: Durchsatz (Throughput). Anstatt nur zu fragen „Wie viele Wörter haben wir richtig bekommen?“, fragen sie: „Wie viele Wörter haben wir pro Sekunde richtig bekommen?“

Die Analogie: Stellen Sie sich einen Lieferwagen vor.
- Wenn Sie ihn mit 100 Paketen beladen, aber nur 2 geliefert werden, weil der Rest falsch war, haben Sie Treibstoff verschwendet.
- Wenn Sie ihn mit 5 Paketen beladen und alle 5 geliefert werden, waren Sie effizient.
- CaDDTree berechnet für jede Fahrt die „perfekte Ladung“. Wenn die Straße holprig ist (die KI ist unsicher), lädt es mehr Pakete. Wenn die Straße glatt ist (die KI ist sicher), lädt es weniger, um Treibstoff (Zeit) zu sparen.

4. Wie es funktioniert (Der „Gierige“ Stopp)

Das Paper beweist mathematisch, dass es einen „Sweet Spot“ dafür gibt, wie viele Vermutungen man anstellen sollte.

Die Analogie: Stellen Sie sich vor, Sie füllen einen Eimer mit Wasser aus einem Schlauch.
- Zuerst füllt das Hinzufügen von mehr Wasser den Eimer schnell auf.
- Aber schließlich verstopft der Schlauch oder der Eimer wird so voll, dass das Hinzufügen von mehr Wasser einfach überläuft und Mühe verschwendet.
- CaDDTree hat einen intelligenten Sensor, der sagt: „Okay, wir haben gerade genug Wasser. Hör auf zu füllen!“ Er stoppt genau dann, wenn das Hinzufügen weiterer Vermutungen Sie mehr bremsen würde, als es Ihnen nützt.

5. Die Ergebnisse

Die Forscher haben diese Methoden bei verschiedenen Aufgaben getestet, wie zum Beispiel mathematischen Problemen, Programmierung und dem Schreiben von Geschichten.

Das Ergebnis: CaDDTree war genauso gut wie die „perfekte“ Methode mit fester Größe (die viel Ausprobieren erfordert, um die richtige Größe zu finden), benötigte aber keinerlei Ausprobieren. Es fand die richtige Größe von selbst, jedes einzelne Mal.
Der Vorteil: Es machte die KI schneller (geringere Latenz), ohne die Genauigkeit zu opfern. Es sparte Zeit, indem es nicht zu viel geraten hat, wenn es nicht nötig war, und nicht zu wenig, wenn es nötig war.

Kurz gesagt: CaDDTree ist wie ein intelligenter Koch, der den Appetit der Gäste betrachtet, bevor er entscheidet, wie viel Essen er zubereitet. Manchmal bereitet er einen kleinen Snack zu; manchmal ein großes Festmahl. Das Ergebnis ist, dass die Gäste schneller satt werden und die Küche nicht mit verschwendeten Zutaten überfordert wird.

Technisches Resümee: Kostensensible Diffusions-Entwurf-Bäume für Spekulative Dekodierung

Problemstellung
Spekulative Dekodierung beschleunigt die autoregressive Inferenz von Sprachmodellen, indem ein leichtgewichtiges Entwurfsmodell (Drafter) Kandidaten-Token vorschlägt, die anschließend parallel vom Zielmodell verifiziert werden. Während die baumbasierte Verifizierung die gleichzeitige Verifizierung mehrerer Kandidaten-Fortsetzungen ermöglicht, stehen die Optimierungsziele bestehender Methoden zur Konstruktion dieser Entwurfsbäume in einem grundlegenden Missverhältnis.

Aktuelle Ansätze, wie etwa DDTree, konstruieren Entwurfsbäume, um die erwartete Akzeptanzlänge unter einem festen Knotenbudget zu maximieren. Die Autoren stellen jedoch fest, dass die Akzeptanzlänge in Bezug auf das Budget nicht monoton steigend ist; größere Bäume liefern immer längere Akzeptanzlängen, was keine fundierte Basis für die Auswahl einer optimalen Budgetgröße bietet. Zudem ist das optimale Budget nicht statisch; es variiert je nach Dekodierungsrunde erheblich, abhängig von der Konfidenz des Entwurfsmodells und der aktuellen Kontextlänge. Bestehende Methoden, die die Baumstruktur pro Schritt anpassen, verlassen sich jedoch weiterhin auf ein festes, offline ausgewähltes Gesamtknotenbudget und versäumen es so, auf die Variabilität pro Runde im Hinblick auf den Kompromiss zwischen Abdeckung und Verifizierungskosten zu reagieren.

Methodik: CaDDTree
Das Paper stellt CaDDTree (Cost-aware Diffusion Draft Tree) vor, ein Framework, das direkt den Token-Durchsatz (erwartte generierte Token pro Zeiteinheit) statt der Akzeptanzlänge optimiert. Die Methode arbeitet mit Block-Diffusions-Entwürfen (z. B. DFlash), die in einem einzigen Vorwärtspass pro Position marginale Verteilungen erzeugen.

Durchsatz-Zielsetzung: Die Autoren modellieren die Rundenkosten als $C(T; \ell) = C_d + C_v(|T|; \ell)$ , wobei $C_d$ die Entwurfs-Kosten sind und $C_v$ die Verifizierungskosten, die von der Baumgröße $|T|$ und der Kontextlänge $\ell$ abhängen. Das Ziel ist es, das Verhältnis der erwarteten akzeptierten Token ( $1 + \Phi(T)$ ) zu den Gesamtkosten zu maximieren.
Zerlegung: Die Autoren beweisen, dass die Maximierung des Durchsatzes über alle gültigen Bäume auf eine eindimensionale Suche über das Knotenbudget $n$ reduziert wird. Für ein festes $n$ ist die optimale Baumstruktur der „Greedy Best-First“-Baum (der Knoten mit den höchsten Präfix-Wahrscheinlichkeiten auswählt), was bereits der Konstruktionsansatz von DDTree ist.
Unimodalität und Greedy-Stoppen: Ein wesentlicher theoretischer Beitrag ist der Beweis, dass das Ersatz-Durchsatzziel unter einer milden Konvexitätsbedingung der Verifizierungskostenfunktion unimodal bezüglich der Baumgröße ist. Diese Eigenschaft ermöglicht einen effizienten Greedy-Algorithmus: Der Algorithmus fügt inkrementell Knoten zum Baum hinzu und stoppt, sobald der Grenznutzen des Durchsatzes nicht mehr positiv ist.
Adaptives Budget: Im Gegensatz zu bisherigen Arbeiten benötigt CaDDTree keine Offline-Gittersuche für ein festes Budget. Stattdessen passt es das Budget $n^*$ für jede Dekodierungsrunde basierend auf den aktuellen pro-Position Verteilungen und den geschätzten Verifizierungskosten (die sich mit der Kontextlänge ändern) an.
Kosten-Profilierung: Die Verifizierungskostenfunktion $C_v(n; \ell)$ wird einmalig offline mittels konvexer Regression auf gemessenen Latenzen über verschiedene Kontextlängen und Knotenzahlen geschätzt. Dies stellt sicher, dass das Kostenmodell konvex und monoton bleibt, was die Unimodalitätsgarantie erfüllt.

Zentrale Beiträge

Zielsetzung-Wechsel: Schlägt die direkte Durchsatzoptimierung als primäres Kriterium für die Konstruktion von Entwurfsbäumen vor und ersetzt damit die fehlgeleitete Maximierung der Akzeptanzlänge.
Theoretische Garantie: Beweist, dass das Durchsatzziel unter konvexen Verifizierungskosten unimodal ist, was eine effiziente, trainingsfreie Greedy-Stopp-Regel ermöglicht.
Adaptiver Mechanismus: Führt eine Methode ein, die das optimale Baum-Budget pro Runde dynamisch auswählt, wodurch die Notwendigkeit einer manuellen oder Offline-Budgetabstimmung entfällt.
Implementierung: Instanziiert das Framework unter Verwendung von Block-Diffusions-Entwürfen und nutzt deren Single-Pass-Marginalverteilungen, um Bäume effizient aufzubauen.

Experimentelle Ergebnisse
Die Methode wurde auf Qwen3-4B und Qwen3-8B über acht Benchmarks evaluiert, die Reasoning (MATH-500, GSM8K, AIME 2025), Coding (HumanEval, MBPP, LiveCodeBench) und Instruktionsfolgen (MT-Bench, Alpaca) abdecken.

Leistung: CaDDTree erreicht nahezu alle Aufgaben auf demselben Niveau wie DDTree mit Oracle-Budget-Selektion (das beste mögliche feste Budget, das via Gittersuche ermittelt wurde) oder übertrifft dieses sogar.
Effizienz: Die Methode erzielt niedrigere Zeiten pro generiertem Token (höherer Durchsatz) im Vergleich zu autoregressiven Baselines und dem Fixed-Budget-DDTree. Beispielsweise erreicht CaDDTree bei Qwen3-8B auf MATH-500 eine Zeit von 4,60 ms pro Token gegenüber 5,83 ms der autoregressiven Baseline.
Adaptivität: Die Analyse zeigt, dass das optimale Budget je nach Runde signifikant variiert. Bei Reasoning-Aufgaben wie MATH-500 schwankt das gewählte Budget stark (Standardabweichung $\approx 42$ ), abhängig von der Konfidenz des Entwurfsmodells, und weicht oft erheblich vom festen Oracle-Budget ab. Bei Instruktionsfolgen-Aufgaben ist das Budget stabiler, aber dennoch deutlich von festen Gittersuchpunkten verschieden.
Robustheit: Ablationsstudien zeigen, dass die Methode robust gegenüber Störungen in den Schätzungen der Kostenparameter ist, was darauf hindeutet, dass eine präzise Offline-Kalibrierung nicht zwingend erforderlich ist.

Bedeutung
Das Paper behauptet, dass CaDDTree einen prinzipienbasierten, kostensensiblen Ansatz für die spekulative Dekodierung bietet, der das Spannungsfeld zwischen Baum-Abdeckung und Verifizierungs-Latenz auflöst. Durch den Beweis der Unimodalität des Durchsatz-Ziels ermöglicht die Arbeit einen effizienten, trainingsfreien Algorithmus, der sich automatisch an die spezifische Schwierigkeit jedes Dekodierungsschritts anpasst. Dies eliminiert die Notwendigkeit einer heuristischen Budgetwahl und demonstriert, dass eine dynamische, kostenbewusste Baumkonstruktion konsistent besser als statische, Oracle-getunte Baselines über diverse Aufgaben und Modellgrößen hinweg abschneidet.