💬 NLP

Hybrid Verified Decoding: Learning to Allocate Verification in Speculative Decoding

Das Papier stellt Hybrid Verified Decoding vor, eine Methode, welche die Akzeptanzlänge von Cache-Entwürfen vorhersagt, um dynamisch zwischen Cache-Verifizierung und modellbasiertem Entwurf zu wählen und dadurch die Effizienz des spekulativen Dekodierens – insbesondere in agentischen Workflows – durch Optimierung signifikant zu steigern.

Ursprüngliche Autoren: Xin Su, Dawid Majchrowski, Fangyuan Yu, Vanshil Atul Shah, Sebastian Rogawski, Pawel Morkisz, Anahita Bhiwandiwalla, Phillip Howard

Veröffentlicht 2026-06-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Xin Su, Dawid Majchrowski, Fangyuan Yu, Vanshil Atul Shah, Sebastian Rogawski, Pawel Morkisz, Anahita Bhiwandiwalla, Phillip Howard

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 strikte Regel: Sie müssen einen sehr teuren, langsamen „Meister-Editor“ fragen, der jedes einzelne Wort, das Sie schreiben, genehmigt, bevor Sie zum nächsten Wort übergehen können. So funktionieren aktuelle Large Language Models (LLMs). Sie generieren Text Wort für Wort, und für jedes Wort muss eine schwere Berechnung durchgeführt werden. Dies macht das Generieren langer Texte langsam und teuer.

Um dies zu beschleunigen, verwenden Forscher einen Trick namens Speculative Decoding. Denken Sie an einen schnellen, günstigen „Lehrlings-Schreiber“, der die nächsten paar Wörter für Sie errät. Sie fragen dann den Meister-Editor, ob die Vermutung des Lehrlings richtig ist. Wenn die Vermutung gut ist, genehmigt der Editor all diese Wörter auf einmal, was Ihnen Zeit spart. Wenn die Vermutung schlecht ist, genehmigt der Editor nur das erste Wort (oder gar keines) und Sie müssen es erneut versuchen.

Das Problem ist: Woher wissen Sie, ob die Vermutung des Lehrlings es wert ist, überprüft zu werden?

Die zwei Arten von Lehrlingen

Das Paper stellt ein System vor, das zwei verschiedene Arten von „Lehrlingen“ und einen klugen „Manager“ verwendet, um zu entscheiden, welcher eingesetzt werden soll.

Der „Gedächtnis“-Lehrling (Cache-basiert): Dieser Lehrling lernt nichts Neues. Stattdessen schaut er sich an, was Sie bereits geschrieben oder als Prompt angegeben haben, und sagt: „Hey, ich habe dieses Muster schon einmal gesehen! Lass uns einfach den Rest dieser Geschichte kopieren und einfügen.“
- Das Gute: Er ist unglaublich schnell und kostenlos, da es nur Kopieren ist.
- Das Schlechte: Nur weil Sie ein Muster zuvor gesehen haben, bedeutet das nicht, dass es genau jetzt passt. Wenn Sie zum Beispiel eine Geschichte über einen Detektiv schreiben, und das Muster besagt: „Der Detektiv zog seine Waffe“, dann mag das für eine Szene richtig sein, aber für eine andere falsch. Wenn der Meister-Editor diese Vermutung ablehnt, haben Sie Zeit mit der Überprüfung einer schlechten Vermutung verschwendet.
Der „Gelernte“ Lehrling (Modell-basiert): Dies ist eine trainierte KI (wie EAGLE3), die tatsächlich über den Kontext nachdenkt und versucht, die nächsten Wörter intelligent zu schreiben.
- Das Gute: Er ist normalerweise sehr genau.
- Das Schlechte: Er ist langsamer und teurer im Betrieb als das bloße Kopieren aus dem Gedächtnis.

Das Problem: Die „Falsche Hoffnung“-Falle

In der Vergangenheit versuchten Systeme einfach, zuerst den „Gedächtnis“-Lehrling zu verwenden, weil er günstig ist. Aber wenn die Gedächtnis-Vermutung falsch ist, verschwendet das System Zeit mit der Verifizierung. Es ist, als würde man einen Freund bitten, das Ende eines Films zu erraten, bas_ierend auf einem ähnlichen Film, den er vor Jahren gesehen hat. Wenn er falsch rät, haben Sie Zeit mit dem Zuhören verschwendet.

Das Paper nennt dies das „Payoff“-Problem. Sie müssen wissen, ob die Vermutung ein „hoher Payoff“ (viele akzeptierte Wörter) oder ein „niedriger Payoff“ (wenige akzeptierte Wörter) ist, bevor Sie den Meister-Editor bitten, sie zu überprüfen.

Die Lösung: Hybrid Verified Decoding

Die Autoren haben einen Smart Manager (einen kleinen, leichtgewichtigen KI-Prädiktor) entwickelt, der zwischen den beiden Lehrlingen und dem Meister-Editor sitzt. So funktioniert er im Alltag:

Das Setup: Der „Gedächtnis“-Lehrling erstellt eine Vermutung basierend auf vergangenen Mustern.
Die Prüfung des Managers: Bevor der Meister-Editor gebeten wird, die Vermutung zu verifizieren, schaut der Smart Manager auf die aktuelle Situation. Er fragt: „Basierend auf dem Kontext, wie viele dieser kopierten Wörter glaubst du, dass der Meister-Editor tatsächlich akzeptieren wird?“
Die Entscheidung:
- Hohe Payoff-Vorhersage: Wenn der Manager denkt: „Ja, das sieht nach einer perfekten Übereinstimmung aus! Der Editor wird wahrscheinlich 5 oder 6 Wörter akzeptieren“, schickt er die „Gedächtnis“-Vermutung an den Editor.
- Niedrige Payoff-Vorhersage: Wenn der Manager denkt: „Nein, das sieht riskant aus. Der Editor wird wahrscheinlich nur 1 Wort oder gar keines akzeptieren“, dann ignoriert er die Gedächtnis-Vermutung. Stattdessen wechselt er zum „Gelernten“ Lehrling, der sich einen Moment Zeit nimmt, um nachzudenken und eine bessere Vermutung zu schreiben.

Warum das wichtig ist

Das Paper hat dieses System bei 16 verschiedenen Arten von Aufgaben getestet, vom Schreiben von Code und Editieren von Dokumenten bis hin zum Beantworten komplexer Fragen.

Das Ergebnis: In Aufgaben, in denen sich Muster oft wiederholen (wie beim Programmieren oder beim Editieren von Dokumenten), war dieses System im Durchschnitt 2,73 Mal schneller als die bisher besten Methoden.
Die Analogie: Stellen Sie sich vor, Sie packen für eine Reise.
- Alte Methode: Sie greifen nach einem Koffer aus einem Stapel ähnlicher Koffer (Gedächtnis) und hoffen, dass er zu Ihrer Kleidung passt. Wenn er nicht passt, müssen Sie ihn wieder auspacken und einen anderen probieren.
- Neue Methode: Sie werfen einen kurzen Blick auf den Koffer (Manager). Wenn er aussieht, als würde er zu Ihrem Outfit passen, packen Sie ihn. Wenn er aussieht, als wäre er die falsche Größe, überspringen Sie ihn sofort und greifen stattdessen zu einem maßgeschneiderten Karton (Gelernter Lehrling). Sie sparen Zeit, indem Sie nicht die Zeit mit dem falschen Koffer verschwenden.

Wichtige Erkenntnisse aus dem Paper

Es geht um das Timing: Das System rät nicht einfach nur; es sagt die Erfolgsrate einer Vermutung voraus, bevor es den teuren Schritt macht.
Es funktioniert am besten mit Struktur: Es glänzt in „agentischen“ Arbeitsabläufen (wie Coding oder Tool-Nutzung), in denen der Text strengen Regeln und Mustern folgt, was „Gedächtnis“-Vermutungen oft sehr gut macht, aber nur, wenn der Kontext exakt stimmt.
Es schont den teuren Teil: Indem es die „schlechten“ Gedächtnis-Vermutungen herausfiltert, stellt das System sicher, dass der teure Meister-Editor nur Zeit mit der Verifizierung von Vermutungen verbringt, die wahrscheinlich erfolgreich sind.

Kurz gesagt: Das Paper lehrt den Computer, ein besserer Richter über seine eigenen Abkürzungen zu sein, indem es sicherstellt, dass er nur den schnellen Weg nimmt, wenn er sich fast sicher ist, dass er funktioniert, und stattdin auf den vorsichtigen Weg wechselt, wenn die Abkürzung riskant aussieht.

Technisches Resümee: Hybrid Verified Decoding

Problemstellung
Die Generierung durch Large Language Models (LLMs) ist durch die sequentielle Natur des autoregressiven Dekodierens beschränkt, bei dem für jedes neue Token ein vollständiger Forward-Pass über das aktuelle Präfix und den Key-Value (KV)-Cache erforderlich ist. Spekulatives Dekodieren adressiert dies, indem Kandidaten-Token über eine „Draft“-Quelle vorgeschlagen werden, die dann in einem einzigen Schritt mit dem Zielmodell verifiziert werden. Die Effizienz des spekulativen Dekodierens hängt jedoch von der „Akzeptanzrate“ ab – der Anzahl der vom Zielmodell akzeptierten vorgeschlagenen Token.

Parameterfreie Draft-Quellen (z. B. Suffix-Caches, Retrieval) bieten kostengünstige Vorschläge durch die Wiederverwendung von Fortsetzungen aus Prompts oder der Generierungshistorie, leiden jedoch unter einer kritischen Einschränkung: Ein Cache-Match, der zu einem bestimmten Generierungsschritt vielversprechend erscheint, kann beim nächsten Schritt aufgrund zustandsabhängiger Variationen (z. B. unterschiedliche Argumente für einen ähnlichen Tool-Aufruf) nur ein sehr kurzes akzeptiertes Präfix liefern. Die Verifizierung eines Cache-Drafts mit geringem Ertrag verursacht Overhead, ohne signifikanten Geschwindigkeitsgewinn zu bieten. Bestehende adaptive Methoden passen oft die Draft-Strukturen oder Budgets an, prognostizieren jedoch nicht explizit den Ertrag (die akzeptierte Länge) eines parameterfreien Drafts vor der Entscheidung zur Verifizierung.

Methodik: Hybrid Verified Decoding
Die Autoren schlagen Hybrid Verified Decoding vor, ein Framework, das die Draft-Selektion als eine ertragsgesteuerte Verifizierungsallokations-Aufgabe behandelt. Anstatt blind jeden Cache-Draft oder ausschließlich einen gelernten modellbasierten Drafter zu verifizieren, prognostiziert das System die erwartete akzeptierte Länge eines Cache-Drafts vor der Verifizierung.

Dual-Source Drafting: Das System unterhält zwei Draft-Quellen:
- Cache-Based Drafter ( $D_C$ ): Ein parameterfreier Mechanismus (instanziiert als SuffixDecoding), der Fortsetzungen durch das Matching von Suffixen im Input-Prompt und der Generierungshistorie vorschlägt.
- Model-Based Drafter ( $D_m$ ): Ein gelernter Drafter (speziell EAGLE3), der als Fallback dient.
Ertragsprognose (Payoff Prediction): Vor der Verifizierung schätzt ein leichtgewichtiger Ertragsprognostikator ( $g_\theta$ $g_{θ}$ ), implementiert als Multilayer-Perzeptron (MLP), die akzeptierte Länge ( $\hat{y}_t$ $\overset{y}{^}_{t}$ ) des aktuellen Cache-Drafts.
- Merkmale: Der Prädiktor nutzt einen Laufzeit-Merkmalsvektor ( $\phi_t$ ), der den Suffix-Match, die Draft-Länge, die aktuelle Dekodierposition, die jüngste Historie und Token-Struktur-Indikatoren umfasst.
- Entscheidungsregel: Wenn der vorhergesagte Ertrag $\hat{y}_t$ einen Schwellenwert $\tau$ überschreitet, wird der Cache-Draft zur Verifizierung gesendet. Andernfalls fällt das System auf den modellbasierten Drafter zurück.
Training via Trace Replay: Der Prädiktor wird durch ein Replay-basiertes Verfahren trainiert. Für jede Token-Position in einem Generierungs-Trace des Zielmodells rekonstruiert das System den Zustand, generiert einen Cache-Draft und berechnet die „Oracle“-akzeptierte Länge ( $y_t$ ), indem der Draft mit der tatsächlichen Fortsetzung des Zielmodells verglichen wird. Das Modell wird mittels Regression trainiert, um den quadratischen Fehler zwischen der vorhergesagten und der tatsächlichen akzeptierten Länge zu minimieren.

Zentrale Beiträge

Formulierung: Die Arbeit formuliert die zustandsabhängige Draft-Selektion als eine ertragsgesteuerte Verifizierungsallokations-Aufgabe und definiert die „akzeptierte Länge“ als primäre Ertragsvariable.
Algorithmus: Sie führt Hybrid Verified Decoding ein, das dynamisch zwischen Cache-basiertem und modellbasiertem Drafting wechselt, basierend auf einer Vor-Verifizierungs-Ertragsschätzung.
Trainingsverfahren: Es schlägt eine leichtgewichtige, Replay-basierte Trainingsmethode vor, die Signale direkt aus Generierungs-Traces ableitet, ohne dass zusätzliches Modelltraining für den Prädiktor erforderlich ist.
Umfassende Evaluierung: Die Methode wird über drei LLMs (Qwen3-8B, Qwen3-4B, Llama3.1-8B) und sechzehn Datensätze hinweg evaluiert, die agentische Workflows, Coding, strukturierte Generierung und Open-Ended Chat abdecken.
Systemintegration: Die Autoren bieten eine systematische Analyse von Cache-Opportunitäten, Verifizierungserträgen und Ausführungskosten sowie einen vLLM-Serving-Prototyp zur Validierung der Implementierung.

Ergebnisse

Leistung: Über 48 Modell-Datensatz-Paare hinweg übertrifft Hybrid Verified Decoding Greedy Decoding in 47 Fällen und SuffixDecoding in 46 Fällen.
Geschwindigkeitsgewinn: Die Methode erreicht eine durchschnittliche Beschleunigung von 2,73x gegenüber EAGLE3 (einer starken modellbasierten Baseline) über alle Einstellungen hinweg.
Agentische Workloads: Der Ansatz ist besonders effektiv in agentischen Aufgaben und Workflow-Editing-Aufgaben (z. B. Delegate-52, InstructEdit), wo er EAGLE3 und andere Baselines konsistent übertrifft. Diese Workloads profitieren von wiederkehrenden strukturellen Mustern, die der Cache ausnutzt, während der Prädiktor zustandsabhängige Mismatch-Szenarien herausfiltert.
Effizienz: Die Analyse zeigt, dass die Methode die Anzahl der Dekodierzyklen pro 1.000 Token signifikant reduziert (z. B. von 571 bei EAGLE3 auf 200 bei Hybrid Verified Decoding für Llama3.1-8B), während die Kosten pro Zyklus vergleichbar mit modellbasiertem Drafting bleiben.
Prädiktor-Genauigkeit: Der Ertragsprognostikator identifiziert High-Payoff-Drafts (definiert als akzeptierte Länge $\ge 6$ ) mit einer Präzision zwischen 78,2 % und 8,76 % und einem Recall zwischen 61,4 % und 79,8 % über verschiedene Modelle hinweg.

Bedeutung und Behauptungen
Das Paper argumentiert, dass der primäre Flaschenhals beim spekulativen Dekodieren nicht nur die Qualität des Drafts ist, sondern das Timing der Verifizierungsentscheidung. Durch die Vorhersage des Ertrags eines parameterfreien Drafts vor der Verifizierung vermeidet Hybrid Verified Decoding den Overhead der Verifizierung von geringwertigen Cache-Matches.

Die Autoren behaupten, dass dieser Ansatz auf die Runtime Draft Selection als vielversprechende Richtung für das spekulative Dekodieren hinweist. Sie demonstrieren, dass die Prompt-Struktur Cache-Opportunitäten schafft, aber High-Payoff-Drafts in einem kleinen Teil des Draft-Raums konzentriert sind. Der gelernte Prädiktor isoliert diese wertvollen Gelegenheiten effektiv, was es dem System ermöglicht, die Verifizierungskosten über längere akzeptierte Präfixe zu amortisieren. Die Ergebnisse legen nahe, dass für strukturierte und agentische Workloads ein hybrider Ansatz, der durch Ertragsschätzung geleitet wird, rein modellbasierte oder rein Cache-basierte Strategien signifikant übertreffen kann.