Hybrid Verified Decoding: Learning to Allocate Verification in Speculative Decoding

Sintesi Tecnica: Hybrid Verified Decoding

Problematica
La generazione dei Large Language Model (LLM) è limitata dalla natura sequenziale della decodifica autoregressiva, dove ogni nuovo token richiede un intero passaggio in avanti (forward pass) sull'attuale prefisso e sulla cache Key-Value (KV). La decodifica speculativa affronta questo problema proponendo token candidati tramite una sorgente di "bozza" (draft) e verificandoli in un unico passaggio con il modello target. Tuttavia, l'efficienza della decodifica speculativa dipende dal "tasso di accettazione" (acceptance rate), ovvero il numero di token proposti che il modello target accetta.

Le sorgenti di bozza prive di parametri (ad esempio, cache di suffissi o recupero/retrieval) offrono proposte a basso costo riutilizzando le continuazioni da prompt o dalla cronologia di generazione, ma soffrono di un limite critico: una corrispondenza nella cache che appare promettente in una fase di generazione può produrre un prefisso accettato molto breve nella fase successiva a causa di variazioni dipendenti dallo stato (ad esempio, argomenti diversi per una chiamata a un tool simile). Verificare una bozza da cache a basso rendimento comporta un overhead senza un significativo aumento di velocità. I metodi adattivi esistenti spesso regolano le strutture o i budget delle bozze, ma non prevedono esplicitamente il rendimento (payoff, ovvero la lunghezza accettata) di una bozza priva di parametri prima di impegnare la verifica.

Metodologia: Hybrid Verified Decoding
Gli autori propongono il Hybrid Verified Decoding, un framework che tratta la selezione della bozza come un problema di allocazione della verifica guidata dal rendimento. Invece di verificare ciecamente ogni bozza della cache o fare affidamento esclusivamente su un drafter basato su un modello appreso, il sistema prevede la lunghezza accettata attesa di una bozza della cache prima della verifica.

1. Drafting a Doppia Sorgente: Il sistema mantiene due sorgenti di bozza:
   • Cache-Based Drafter ($D_C$): Un meccanismo privo di parametri (istanziato come SuffixDecoding) che propone continuazioni facendo il matching di suffissi nel prompt di input e nella cronologia di generazione.
   • Model-Based Drafter ($D_m$): Un drafter appreso (specificamente EAGLE3) utilizzato come fallback.
2. Previsione del Rendimento (Payoff Prediction): Prima della verifica, un leggero predittore di rendimento ($g_\theta$), implementato come un MLP (multilayer perceptron), stima la lunghezza accettata ($\hat{y}_t$) della corrente bozza della cache.
   • Feature: Il predittore riceve un vettore di feature a runtime ($\phi_t$) che include il matching del suffisso, la lunghezza della bozza, la posizione di decodifica corrente, la cronologia recente e gli indicatori della struttura del token.
   • Regola Decisionale: Se il rendimento previsto $\hat{y}_t$ supera una soglia $\tau$, la bozza della cache viene inviata per la verifica. Altrimenti, il sistema passa al drafter basato sul modello.
3. Addestramento tramite Trace Replay: Il predittore viene addestrato tramite una procedura di replay. Per ogni posizione di token in una traccia di generazione del modello target, il sistema ricostruisce lo stato, genera una bozza della cache e calcola la lunghezza accettata "oracle" ($y_t$) confrontando la bozza con la continuazione effettiva del modello target. Il modello viene addestrato tramite regressione per minimizzare l'errore quadratico tra la lunghezza prevista e quella effettivamente accettata.

Contributi Chiave

• Formulazione: Il documento formula la selezione della bozza dipendente dallo stato come un problema di allocazione della verifica guidata dal rendimento, definendo la "lunghezza accettata" come la variabile di rendimento primaria.
• Algoritmo: Introduce l'Hybrid Verified Decoding, che passa dinamicamente tra il drafting basato su cache e quello basato su modello in base a una stima del rendimento pre-verifica.
• Procedura di Addestramento: Propone un metodo di addestramento leggero e basato sul replay che deriva segnali di supervisione direttamente dalle tracce di generazione senza richiedere l'addestramento di modelli aggiuntivi per il predittore.
• Valutazione Esaustiva: Il metodo è valutato su tre LLM (Qwen3-8B, Qwen3-4B, Llama3.1-8B) e sedici dataset che spaziano da flussi di lavoro agentici, coding, generazione strutturata e chat aperta.
• Integrazione di Sistema: Gli autori forniscono un'analisi sistematica delle opportunità di cache, dei rendimenti di verifica e dei costi di esecuzione, incluso un prototipo di serving vLLM per la validazione del deployment.

Risultati

• Performance: In 48 coppie modello-dataset, l'Hybrid Verified Decoding supera la Greedy Decoding in 47 casi e la SuffixDecoding in 46 casi.
• Speedup: Il metodo ottiene uno speedup medio di 2.73x rispetto a EAGLE3 (un forte baseline basato su modello) in tutti i setting.
• Carichi di Lavoro Agentici: L'approccio è particolarmente efficace nei compiti agentici e di editing di workflow (ad esempio, Delegate-52, InstructEdit), dove supera costantemente EAGLE3 e altri baseline. Questi carichi di lavoro beneficiano di pattern strutturali ricorrenti che la cache sfrutta, mentre il predittore filtra i mismatch dipendenti dallo stato.
• Efficienza: L'analisi mostra che il metodo riduce significativamente il numero di cicli di decodifica per 1.000 token (ad esempio, da 571 per EAGLE3 a 200 per Hybrid Verified Decoding su Llama3.1-8B) mantenendo costi per ciclo comparabili al drafting basato su modello.
• Accuratezza del Predittore: Il predittore di rendimento identifica con successo le bozze ad alto rendimento (definite come lunghezza accettata $\ge 6$) con una precisione compresa tra il 78.2% e l'87.6% e una recall tra il 61.4% e il 79.8% attraverso diversi modelli.

Significatività e Rivendicazioni
Il documento sostiene che il collo di bottiglia principale nella decodifica speculativa non è solo la qualità della bozza, ma il timing della decisione di verifica. Prevedendo il rendimento di una bozza priva di parametri prima della verifica, l'Hybrid Verified Decoding evita l'overhead di verificare corrispondenze della cache di scarso valore.

Gli autori affermano che questo approccio indica la selezione della bozza a runtime come una direzione promettente per la decodifica speculativa. Dimostrano che la struttura del prompt crea opportunità di cache, ma le bozze ad alto rendimento sono concentrate in un piccolo sottoinsieme dello spazio delle bozze. Il predittore appreso isola efficacemente queste opportunità di alto valore, permettendo al sistema di ammortizzare i costi di verifica su prefissi accettati più lunghi. I risultati suggeriscono che per i carichi di lavoro strutturati e agentici, un approccio ibrido guidato dalla stima del rendimento può superare significativamente le strategie puramente basate su modelli o puramente basate su cache.