Inferența LLM este o problemă de miliarde de dolari. Noul nostru articol introduce un algoritm SOTA în eșantionarea speculativă multi-draft, Global Resolution, care face progrese semnificative în această problemă. Despachetăm mai jos 🧵👇

O abordare pentru inferența eficientă se numește eșantionare speculativă. Acesta folosește un model ieftin de tip "draft" pentru a produce "presupuneri" despre ce ar putea avea modelul țintă, mai mare.

Prin exploatarea eficienței paralelismului ale GPU-urilor moderne, acest lucru poate reduce numărul de treceri înainte ale modelului țintă cu peste 5x.

Eșantionarea speculativă poate fi generalizată pentru a include mai multe presupuneri din mai multe modele de draft. Dar nu este clar care este cel mai bun algoritm pentru a combina aceste multiple presupuneri.

În cazul cu un singur pas, lucrări anterioare au arătat că soluția optimă poate fi găsită prin rezolvarea unui program liniar de transport optim, OTLP.

Totuși, OTLP-ul este extrem de dificil de rezolvat aproape exact, deoarece crește exponențial ca dimensiune a vocabularului. Deci, cum putem rezolva asta?

Cheia este exploatarea structurii suplimentare în construcția arborelui de draft.

Lucrări anterioare [Hu et al.] au arătat că atunci când arborele de draft este format prin eșantionarea i.i.d., prin dualizarea OTLP-ului, valoarea obiectivului optimă poate fi calculată în timp aproape liniar prin minimizare submodulară.

Totuși, până la munca noastră, nicio metodă nu a putut rezolva soluția care a atins această valoare obiectivă optimă. Fără această piesă lipsă, tot ce ne oferă munca anterioară este eficiența blocului, accelerarea teoretică maximă. Nu ne spune cum să obținem această viteză.

Munca noastră este prima care reduce semnificativ dimensionalitatea OTLP, folosind trei perspective.

Inversăm dualizarea OTLP din lucrări anterioare [Hu et al.] cu flexibilitate complementară, pentru a formula OTLP ca o problemă de fezabilitate a fluxului.

Multe dintre constrângerile inegalității fluxului sunt redundante. Folosind un algoritm lacom din teoria polimatroizilor, putem coagula acestea.

Această problemă de curgere redusă are o soluție care poate fi parametrizată ca softmax-ul unui vector de dimensiune joasă, iar acest vector poate fi calculat prin minimizare convexă. Aceasta reduce OTLP în variabilele V^{n+1} la o problemă de minimizare convexă în variabilele V.

Totuși, V poate fi destul de mare, așa că în lucrarea noastră aplicăm aproximări suplimentare cu rata de eroare a modelului țintă limitată pentru a reduce și mai mult timpul de calcul.

Pentru multe cazuri cu V restricționat la modele top-k și n draft, așa cum s-a arătat mai sus, Global Resolution este singurul solver capabil să rezolve OTLP într-un timp rezonabil.

Mai mult, folosind Global Resolution, putem îmbunătăți ratele de acceptare pentru Llama și Gemma cu până la 6%: Pe scurt, Rezoluția Globală este SOTA pentru verificarea optimă multi-draft în decodarea speculativă.

Mai este mult de lucru aici, relaxând setarea iid sau extinzând mai mulți pași.