Inference LLM je otázka v hodnotě několika miliard dolarů. Náš nový článek představuje algoritmus SOTA v multi-draftovém spekulativním vzorkování, Global Resolution, který významně posouvá tento problém. Rozbalování níže 🧵👇

Jedním z přístupů k efektivní inferenci je spekulativní vzorkování. Používá levný "draft" model k vytvoření "odhadů" toho, co by větší cílový model měl výstup.

Využitím efektivity paralelismu moderních GPU lze snížit počet průchodů cílovým modelem vpřed více než 5×.

Spekulativní výběr lze zobecnit tak, aby zahrnoval více odhadů z různých návrhových modelů. Není však jasné, jaký algoritmus je nejlepší pro kombinaci těchto vícenásobných odhadů.

V případě jednokrokového vývoje předchozí práce ukázala, že optimální řešení lze najít řešením optimálního transportního lineárního programu, tzv. OTLP.

OTLP je však extrémně obtížné vyřešit téměř přesně, protože jeho slovní zásoba exponenciálně roste. Jak to tedy můžeme vyřešit?

Klíčem je využít další strukturu při konstrukci návrhu stromu.

Předchozí práce [Hu et al.] ukázaly, že když je návrhový strom vytvořen i.i.d. vzorkováním, dualizací OTLP lze optimální hodnotu cíle vypočítat téměř lineárním časem pomocí submodulární minimalizace.

Nicméně až do naší práce žádná metoda nedokázala vyřešit řešení, které by dosáhlo této optimální hodnoty cíle. Bez tohoto chybějícího dílku nám předchozí práce poskytuje pouze blokovou efektivitu, tedy teoretické maximální zrychlení. Neříká nám, jak tohoto zrychlení dosáhnout.

Naše práce je první, která výrazně snižuje dimenzionalitu OTLP, a to pomocí tří poznatků.

Obracíme dualizaci OTLP v předchozí práci [Hu et al.] s komplementární volností, abychom formulovali OTLP jako problém proveditelnosti toku.

Mnoho omezení nerovnosti toku je redundantních. Pomocí chamtivého algoritmu z teorie polymatroidů je můžeme spojit.

Tento problém redukovaného toku má řešení, které lze parametrizovat jako softmax nízkorozměrného vektoru, a tento vektor lze vypočítat pomocí konvexní minimalizace. To redukuje OTLP ve V^{n+1} proměnných na problém konvexní minimalizace v V proměnných.

V však může být stále poměrně velký, proto v našem článku aplikujeme další aproximace s omezenou cílovou chybovostí modelu, abychom dále snížili výpočetní čas.

V mnoha případech, kdy je V omezeno na top-k a n návrhové modely, jak je uvedeno výše, je globální rozlišení _jediným_ řešičem schopným vyřešit OTLP v rozumném čase.

Navíc díky Global Resolution můžeme zvýšit míru přijetí na Llama a Gemma až o 6 %: Stručně řečeno, Global Resolution je SOTA pro optimální vícenávrhové ověření ve spekulativním dekódování.

Stále je tu spousta práce, ať už uvolněním nastavení iid, nebo rozšířením do více kroků.