LLM-Inferenz ist ein Multi-Milliarden-Dollar-Problem. Unser neues Papier stellt einen SOTA-Algorithmus im Bereich des mehrstufigen spekulativen Samplings, Global Resolution, vor, der bedeutende Fortschritte bei diesem Problem erzielt. Im Folgenden erläutern wir 🧵👇

Ein Ansatz für effiziente Inferenz wird als spekulatives Sampling bezeichnet. Dabei wird ein günstiges ‚Entwurf‘-Modell verwendet, um ‚Vermutungen‘ darüber anzustellen, was das größere Zielmodell ausgegeben hätte.

Durch die Ausnutzung der Parallelitätseffizienzen moderner GPUs kann dies die Anzahl der Vorwärtsdurchläufe des Zielmodells um über das 5-fache reduzieren.

Spekulatives Sampling kann verallgemeinert werden, um mehrere Vermutungen aus mehreren Entwurfmodellen zu berücksichtigen. Aber es ist unklar, welcher Algorithmus der beste ist, um diese mehreren Vermutungen zu kombinieren.

Im Ein-Schritt-Fall hat frühere Arbeit gezeigt, dass die optimale Lösung durch die Lösung eines optimalen Transport-Linearprogramms, des OTLP, gefunden werden kann.

Das OTLP ist jedoch extrem schwierig nahezu genau zu lösen, da es exponentiell in der Wortschatzgröße wächst. Wie können wir es also lösen?

Der Schlüssel besteht darin, zusätzliche Strukturen im Entwurf des Baumaufbaus auszunutzen.

Frühere Arbeiten [Hu et. al.] zeigten, dass, wenn der Entwurfbaum durch i.i.d. Sampling gebildet wird, durch Dualisierung des OTLP der optimale Zielwert in nahezu linearer Zeit durch submodulare Minimierung berechnet werden kann.

Bis zu unserer Arbeit war jedoch keine Methode in der Lage, die Lösung zu finden, die diesen optimalen Zielwert erreicht. Ohne dieses fehlende Puzzlestück gibt uns die gesamte vorherige Arbeit nur die Blockeffizienz, die theoretische maximale Beschleunigung. Sie sagt uns nicht, wie wir diese Beschleunigung erreichen können.

Unsere Arbeit ist die erste, die die Dimensionalität des OTLP erheblich reduziert, indem sie drei Erkenntnisse nutzt.

Wir kehren die Dualisierung des OTLP in der vorherigen Arbeit [Hu et. al.] mit komplementärer Schlappheit um, um das OTLP als ein Flussfeasibilitätsproblem zu formulieren.

Viele der Flussungleichheitsbeschränkungen sind überflüssig. Mit einem gierigen Algorithmus aus der Polymatroidtheorie können wir diese zusammenfassen.

Dieses reduzierte Flussproblem hat eine Lösung, die als Softmax eines niederdimensionalen Vektors parametrisiert werden kann, und dieser Vektor kann durch konvexe Minimierung berechnet werden. Dies reduziert das OTLP in V^{n+1} Variablen auf ein konvexes Minimierungsproblem in V Variablen.

V kann jedoch immer noch ziemlich groß sein, daher wenden wir in unserem Papier weitere Annäherungen mit einer begrenzten Zielmodell-Fehlerrate an, um die Rechenzeit weiter zu reduzieren.

In vielen Fällen, in denen V auf die Top-k und n Entwurfmodelle beschränkt ist, wie oben gezeigt, ist die Globale Auflösung der _einzige_ Solver, der in angemessener Zeit das OTLP lösen kann.

Darüber hinaus können wir durch die Verwendung von Global Resolution die Akzeptanzraten bei Llama und Gemma um bis zu 6 % verbessern: Kurz gesagt, Global Resolution ist SOTA für optimale Multi-Draft-Verifizierung im spekulativen Decoding.

Hier gibt es noch viel zu tun, indem man die iid-Einstellung entspannt oder auf mehrere Schritte erweitert.