LLM-inferentie is een probleem van meerdere miljarden dollars. Ons nieuwe paper introduceert een SOTA-algoritme in multi-draft speculatieve sampling, Global Resolution, dat aanzienlijke vooruitgang boekt in dit probleem. Uitpakken hieronder 🧵👇

Een benadering voor efficiënte inferentie wordt speculatieve sampling genoemd. Dit gebruikt een goedkope 'concept'-model om 'gissingen' te produceren voor wat het grotere, doelmodel zou hebben uitgegeven.

Door gebruik te maken van de parallelisme-efficiënties van moderne GPU's, kan dit het aantal vooruitgangen van het doelformulier met meer dan 5x verminderen.

Speculatieve sampling kan worden gegeneraliseerd om meerdere gissingen van meerdere conceptmodellen op te nemen. Maar het is niet duidelijk wat het beste algoritme is voor het combineren van deze meerdere gissingen.

In het geval van een enkele stap heeft eerder onderzoek aangetoond dat de optimale oplossing kan worden gevonden door een optimaal transport lineair programma op te lossen, de OTLP.

Echter, de OTLP is extreem moeilijk bijna exact op te lossen naarmate de vocabulairegrootte exponentieel toeneemt. Dus hoe kunnen we het oplossen?

De sleutel is om extra structuur te benutten in de constructie van de conceptboom.

Eerder werk [Hu et. al.] toonde aan dat wanneer de conceptboom wordt gevormd door i.i.d. sampling, door de OTLP te dualiseren, de optimale doelwaarde in bijna-lineaire tijd kan worden berekend via submodulaire minimalisatie.

Echter, tot ons werk was er geen enkele methode in staat om de oplossing te vinden die deze optimale doelwaarde bereikte. Zonder dit ontbrekende stuk geeft al het eerdere werk ons alleen de blokefficiëntie, de theoretische maximale versnelling. Het vertelt ons niet hoe we deze versnelling kunnen bereiken.

Ons werk is het eerste dat de dimensionaliteit van de OTLP aanzienlijk vermindert, met behulp van drie inzichten.

We keren de dualisatie van de OTLP in eerder werk [Hu et. al.] om met complementaire slackness, om de OTLP te formuleren als een doorstroom haalbaarheidsprobleem.

Veel van de stroomongelijkheidbeperkingen zijn overbodig. Door een hebzuchtig algoritme uit de polymatroidtheorie te gebruiken, kunnen we deze samenvoegen.

Dit gereduceerde stroomprobleem heeft een oplossing die kan worden geparametriseerd als de softmax van een laag-dimensionale vector, en deze vector kan worden berekend via convexe minimalisatie. Dit reduceert de OTLP in V^{n+1} variabelen tot een convex minimalisatieprobleem in V variabelen.

V kan echter nog steeds behoorlijk groot zijn, dus in ons paper passen we verdere benaderingen toe met een begrensde foutenmarge van het doelmodel om de rekentijd verder te verminderen.

Voor veel gevallen waarbij V beperkt is tot top-k en n conceptmodellen, zoals hierboven weergegeven, is Global Resolution de _enige_ oplosser die in staat is om de OTLP in redelijke tijd op te lossen.

Bovendien kunnen we met Global Resolution de acceptatiepercentages op Llama en Gemma met tot 6% verbeteren: Kortom, Global Resolution is SOTA voor optimale multi-draft verificatie in speculatieve decodering.

Er is hier nog veel werk te verzetten, door de iid-instelling te versoepelen of door uit te breiden naar meerdere stappen.