L'inferenza LLM è una questione da miliardi di dollari. Il nostro nuovo articolo introduce un algoritmo SOTA nel campionamento speculativo multi-draft, Global Resolution, che fa significativi progressi in questo problema. Analizziamo qui sotto 🧵👇

Un approccio per un'inferenza efficiente è chiamato campionamento speculativo. Questo utilizza un modello "bozza" economico per produrre "ipotesi" su ciò che il modello target più grande avrebbe prodotto.

Sfruttando le efficienze di parallelismo delle moderne GPU, questo può portare a ridurre il numero di passaggi in avanti del modello target di oltre 5 volte.

Il campionamento speculativo può essere generalizzato per includere più ipotesi da più modelli di bozza. Ma non è chiaro quale sia il miglior algoritmo per combinare queste molteplici ipotesi.

Nel caso a passaggio singolo, lavori precedenti hanno dimostrato che la soluzione ottimale può essere trovata risolvendo un programma lineare di trasporto ottimale, l'OTLP.

Tuttavia, l'OTLP è estremamente difficile da risolvere in modo quasi esatto poiché cresce esponenzialmente in dimensione del vocabolario. Quindi, come possiamo risolverlo?

La chiave è sfruttare una struttura aggiuntiva nella costruzione dell'albero di bozza.

Il lavoro precedente [Hu et. al.] ha dimostrato che quando l'albero di bozza è formato da campionamento i.i.d., dualizzando l'OTLP, il valore obiettivo ottimale può essere calcolato in tempo quasi lineare attraverso la minimizzazione submodulare.

Tuttavia, fino al nostro lavoro, nessun metodo è stato in grado di risolvere la soluzione che ha raggiunto questo valore obiettivo ottimale. Senza questo pezzo mancante, tutto ciò che ci offre il lavoro precedente è l'efficienza del blocco, il massimo teorico di accelerazione. Non ci dice come raggiungere questa accelerazione.

Il nostro lavoro è il primo a ridurre significativamente la dimensionalità dell'OTLP, utilizzando tre intuizioni.

Invertiamo la dualizzazione dell'OTLP nel lavoro precedente [Hu et. al.] con la complementarietà della slackness, per formulare l'OTLP come un problema di fattibilità del flusso.

Molti dei vincoli di disuguaglianza del flusso sono ridondanti. Utilizzando un algoritmo goloso dalla teoria dei polimatoidi, possiamo unire questi.

Questo problema di flusso ridotto ha una soluzione che può essere parametrizzata come il softmax di un vettore a bassa dimensione, e questo vettore può essere calcolato tramite minimizzazione convessa. Questo riduce l'OTLP in V^{n+1} variabili in un problema di minimizzazione convessa in V variabili.

V può comunque essere piuttosto grande, tuttavia, nel nostro articolo applichiamo ulteriori approssimazioni con un tasso di errore del modello target limitato per ridurre ulteriormente il tempo di calcolo.

Per molti casi con V limitato ai top-k e n modelli di bozza, come mostrato sopra, la Global Resolution è l'_unico_ risolutore in grado di risolvere l'OTLP in un tempo ragionevole.

Inoltre, utilizzando la Global Resolution, possiamo migliorare i tassi di accettazione su Llama e Gemma fino al 6%: In breve, la Global Resolution è SOTA per la verifica multi-draft ottimale nel decoding speculativo.

C'è ancora molto lavoro da fare qui, rilassando l'impostazione iid, o estendendo a più passaggi.