LLM-inferens er en utstedelse verdt flere milliarder. Vår nye artikkel introduserer en SOTA-algoritme i multi-draft spekulativ utvalg, Global Resolution, som gjør betydelige fremskritt i dette problemet. Pakking nedenfor 🧵👇

En tilnærming for effektiv slutning kalles spekulativ prøvetaking. Dette bruker en billig «draft»-modell for å lage «gjetninger» om hva den større, målrettede modellen ville ha utbytte.

Ved å utnytte parallellismeeffektiviteten til moderne GPU-er, kan dette redusere antall fremoverpasseringer fra målmodellen med over 5 ganger.

Spekulativ utvalgstaking kan generaliseres til å inkludere flere gjetninger fra flere utkastmodeller. Men det er uklart hva som er den beste algoritmen for å kombinere disse flere gjetningene.

I enkeltstegstilfellet har tidligere arbeid vist at den optimale løsningen kan finnes ved å løse et optimalt transportlineært program, OTLP.

Imidlertid er OTLP ekstremt vanskelig å løse nesten nøyaktig, ettersom det vokser eksponentielt i vokabularstørrelse. Så hvordan kan vi løse det?

Nøkkelen er å utnytte ekstra struktur i konstruksjonen av drafttreet.

Tidligere arbeid [Hu et al.] viste at når utkasttreet dannes ved i.i.d.-prøvetaking, ved å dualisere OTLP, kan den optimale målverdien beregnes i nær-lineær tid gjennom submodulær minimering.

Men frem til arbeidet vårt klarte ingen metode å løse løsningen som oppnådde denne optimale målverdien. Uten denne manglende brikken gir alt tidligere arbeid oss blokkeffektiviteten, den teoretiske maksimale hastighetsøkningen. Den forteller oss ikke hvordan vi skal oppnå denne hastighetsøkningen.

Vårt arbeid er det første som betydelig reduserer dimensjonaliteten til OTLP, ved å bruke tre innsikter.

Vi reverserer dualiseringen av OTLP i tidligere arbeid [Hu et al.] med komplementær slackness, for å formulere OTLP som et flytmulighetsproblem.

Mange av strømningsulikhetsbegrensningene er overflødige. Ved å bruke en grådig algoritme fra polymatroidteori kan vi samle disse.

Dette reduserte strømningsproblemet har en løsning som kan parametriseres som softmax for en lavdimensjonal vektor, og denne vektoren kan beregnes via konveks minimering. Dette reduserer OTLP i V^{n+1} variabler til et konvekst minimeringsproblem i V variabler.

V kan imidlertid fortsatt være ganske stor, så i artikkelen vår anvender vi ytterligere tilnærminger med begrenset feilrate for målmodellen for å redusere beregningstiden ytterligere.

For mange tilfeller med V begrenset til top-k og n utkastmodeller, som vist ovenfor, er Global Resolution den _eneste_ løseren som kan løse OTLP på rimelig tid.

I tillegg kan vi, ved å bruke Global Resolution, forbedre akseptratene på Llama og Gemma med opptil 6 %: Kort sagt er Global Resolution SOTA for optimal multi-draft-verifisering i spekulativ dekoding.

Det er fortsatt mye arbeid å gjøre her, enten ved å slappe av i iid-innstillingen, eller ved å utvide til flere trinn.