Goose: Anisotropic Speculation Trees for Training-Free Speculative Decoding

1. Il Problema

Il decoding speculativo accelera l'inferenza dei Large Language Models (LLM) generando più token candidati in una singola passata in avanti (forward pass) e verificandoli simultaneamente. I candidati sono organizzati in una struttura ad albero per mitigare il rischio di rigettamenti: un albero più profondo accetta più token se le previsioni sono corrette, mentre un albero più ampio offre più opzioni di fallback.

Le sfide principali identificate dagli autori sono:

• Limiti delle strutture bilanciate: I metodi esistenti (come Sequoia) costruiscono alberi isotropi (simmetrici) assumendo che tutti i token candidati abbiano la stessa probabilità di accettazione, indipendentemente dalla loro origine.
• Eterogeneità delle fonti: Esistono due fonti principali di token "training-free" (senza addestramento aggiuntivo):
  1. Match di contesto (PLD): Copia di n-grammi dal contesto di input. Questi hanno un tasso di accettazione molto alto.
  2. Transizioni statistiche (TR): Token derivati dalle logits del modello precedente. Questi hanno un tasso di accettazione significativamente più basso.
• Il divario: Gli autori osservano che i token basati sul contesto sono accettati 2-18 volte più spesso (mediana ~6x) rispetto ai token di transizione. Costruire alberi simmetrici che mescolano queste fonti senza distinzione spreca il budget di nodi, limitando la profondità dell'albero e non sfruttando appieno l'affidabilità delle fonti di contesto.

2. Metodologia: GOOSE

Gli autori propongono GOOSE, un framework training-free che introduce una struttura ad albero anisotropica (asimmetrica) chiamata Spine Tree (Albero a Schiena).

Concetto Chiave: L'Albero a Schiena (Spine Tree)

Invece di distribuire uniformemente i nodi, GOOSE organizza l'albero in base alla qualità della fonte:

1. La Schiena (Spine): Una catena lineare profonda composta esclusivamente da token corrispondenti al contesto (PLD). Poiché questi token hanno un'alta probabilità di accettazione ($p_s$), è vantaggioso spingerli in profondità.
2. I Rami (Branches): Ad ogni nodo della "schiena", si diramano rami ampi composti da token di transizione (TR) a bassa affidabilità ($p_t$). Questi rami fungono da opzioni di fallback se la catena principale fallisce.

Costruzione e Verifica

• Costruzione Dinamica: L'algoritmo assegna il budget totale dei nodi ($B$) tra la schiena e i rami. La proporzione è adattiva: se la fiducia nel match di contesto è alta, l'albero diventa più profondo; se è bassa, si sposta il budget verso rami più ampi.
• Tabella di Adiacenza: Per migliorare la qualità dei rami, GOOSE utilizza una tabella di adiacenza basata su bigrammi (invece di unigrammi come in metodi precedenti come TR), migliorando la precisione delle previsioni statistiche.
• Verifica Unificata: Un singolo passaggio in avanti del modello target verifica l'intero albero. Un "cammino greedy" (greedy walk) con priorità alle fonti seleziona il percorso più lungo accettato:
  • Priorità alla schiena (PLD).
  • Se la schiena fallisce, il cammino continua su un ramo (TR) nello stesso punto, creando un fenomeno chiamato "Spine Continuation" (continuità della schiena), che recupera token che nessuna delle due fonti avrebbe potuto trovare da sola.
• Modalità Bypass: Se il match di contesto è molto lungo e sicuro, GOOSE salta la costruzione dell'albero e verifica linearmente la catena, riducendo l'overhead.

3. Contributi Chiave

1. Teoria dell'Anisotropia Ottimale: Gli autori dimostrano matematicamente che, in presenza di fonti con tassi di accettazione eterogenei ($p_s > p_t$), la struttura dell'albero ottimale non è bilanciata ma anisotropica: allocare profondità ai token affidabili e larghezza a quelli inaffidabili supera i limiti degli alberi isotropi.
2. Garanzia di Non-Degradazione: Viene provato che l'yield atteso (numero di token accettati per ciclo) di GOOSE è sempre almeno pari a quello ottenuto usando una singola fonte (solo PLD o solo TR) con lo stesso budget totale.
3. Framework Training-Free: GOOSE non richiede modelli ausiliari o addestramento specifico, rendendolo immediatamente applicabile a qualsiasi LLM.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su 5 modelli LLM (da 7B a 33B parametri) e 5 benchmark (codice, matematica, dialogo).

• Velocità: GOOSE ottiene un'accelerazione lossless (senza perdita di qualità) compresa tra 1.9x e 4.3x rispetto al decoding autoregressivo standard.
• Confronto con Baseline:
  • Supera le baseline a albero bilanciato (isotropo) del 12-33% a parità di budget di nodi.
  • In termini di velocità reale (tok/s), supera o eguaglia metodi che richiedono addestramento come EAGLE-2 su alcuni modelli (es. Llama-3-8B), pur essendo completamente training-free.
• Sinergia: L'analisi mostra che la struttura a schiena genera un "guadagno di sinergia" del 16-45% rispetto alla somma dei risultati delle singole fonti, confermando che la combinazione asimmetrica è più della somma delle parti.

5. Significato e Impatto

Il lavoro di GOOSE è significativo perché:

• Ridefinisce l'ottimizzazione degli alberi: Sposta il paradigma dalla ricerca di alberi bilanciati a strutture adattive che sfruttano l'eterogeneità intrinseca delle fonti di previsione.
• Efficienza senza costi: Dimostra che è possibile ottenere accelerazioni massicce (fino a 4x) senza il costo computazionale e di memoria dell'addestramento di modelli "drafter" (come EAGLE o Medusa).
• Generalizzabilità: Il framework anisotropico può essere applicato a qualsiasi coppia di strategie di previsione con tassi di accettazione diversi, offrendo una direzione futura per l'ottimizzazione dell'inferenza LLM su hardware limitato.

In sintesi, GOOSE risolve il compromesso tra profondità e larghezza negli alberi di speculazione riconoscendo che non tutti i token sono uguali: i token affidabili meritano profondità, mentre quelli incerti meritano ampiezza, e la combinazione intelligente di entrambi rompe i limiti attuali delle tecniche di decoding speculativo.