Wnioskowanie LLM to problem wart wiele miliardów dolarów. Nasz nowy artykuł wprowadza algorytm SOTA w zakresie wielodraftowego próbkowania spekulacyjnego, Global Resolution, który znacząco przyczynia się do rozwiązania tego problemu. Rozpakowując poniżej 🧵👇

Jednym z podejść do efektywnego wnioskowania jest tzw. próbkowanie spekulacyjne. Wykorzystuje ono tani model „szkicowy” do generowania „zgadywanek” tego, co większy, docelowy model mógłby wyprodukować.

Wykorzystując efektywność równoległości nowoczesnych GPU, można w ten sposób zmniejszyć liczbę przejść do przodu modelu docelowego o ponad 5x.

Próbkowanie spekulacyjne można uogólnić, aby uwzględnić wiele przypuszczeń z wielu modeli roboczych. Jednak nie jest jasne, jaki jest najlepszy algorytm do łączenia tych wielu przypuszczeń.

W przypadku jednego kroku wcześniejsze prace wykazały, że optymalne rozwiązanie można znaleźć, rozwiązując liniowy program transportu optymalnego, OTLP.

Jednakże, OTLP jest niezwykle trudny do rozwiązania w prawie dokładny sposób, ponieważ rośnie wykładniczo w rozmiarze słownika. Jak więc możemy to rozwiązać?

Kluczem jest wykorzystanie dodatkowej struktury w konstrukcji drzewa roboczego.

Poprzednie prace [Hu i in.] wykazały, że gdy drzewo robocze jest tworzone przez i.i.d. próbkowanie, poprzez dualizację OTLP, optymalna wartość celu może być obliczana w czasie bliskim liniowemu za pomocą minimalizacji submodularnej.

Jednak do czasu naszej pracy żadna metoda nie była w stanie znaleźć rozwiązania, które osiągnęłoby tę optymalną wartość celu. Bez tego brakującego elementu, wszystkie wcześniejsze prace dają nam jedynie efektywność bloku, teoretyczne maksymalne przyspieszenie. Nie mówi nam, jak osiągnąć to przyspieszenie.

Nasza praca jest pierwsza, która znacząco redukuje wymiarowość OTLP, wykorzystując trzy spostrzeżenia.

Odwracamy dualizację OTLP w poprzedniej pracy [Hu i in.] z wykorzystaniem komplementarnej luzności, aby sformułować OTLP jako problem wykonalności przepływu.

Wiele z ograniczeń nierówności przepływu jest zbędnych. Używając algorytmu zachłannego z teorii polimatroidów, możemy je połączyć.

Problem z redukcją przepływu ma rozwiązanie, które można parametryzować jako softmax niskowymiarowego wektora, a ten wektor można obliczyć za pomocą minimalizacji wypukłej. To redukuje OTLP w V^{n+1} zmiennych do problemu minimalizacji wypukłej w V zmiennych.

V może być nadal dość duże, jednak w naszym artykule stosujemy dalsze przybliżenia z ograniczoną stawką błędu modelu docelowego, aby dodatkowo skrócić czas obliczeń.

W wielu przypadkach, w których V jest ograniczone do top-k i n modeli roboczych, jak pokazano powyżej, Global Resolution jest _jedynym_ rozwiązaniem zdolnym do rozwiązania OTLP w rozsądnym czasie.

Co więcej, korzystając z Global Resolution, możemy poprawić wskaźniki akceptacji na Llama i Gemma o nawet 6%: Krótko mówiąc, Global Resolution to SOTA dla optymalnej weryfikacji wielodraftowej w dekodowaniu spekulacyjnym.

Wciąż jest wiele do zrobienia, poprzez złagodzenie ustawienia iid lub poprzez rozszerzenie na wiele kroków.