Висновок LLM — це багатомільярдне питання. Наша нова стаття вводить алгоритм SOTA у багаточернетковій спекулятивній вибірці — Global Resolution, який робить значний прорив у цій проблемі. Розпакування нижче 🧵👇

Один із підходів до ефективного висновку називається спекулятивним вибірковим відбором. Вона використовує дешеву «чернеткову» модель для створення «припущень» щодо того, що мала б більша цільова модель.

Використовуючи ефективність паралелізму сучасних GPU, це може зменшити кількість проходів цільової моделі вперед більш ніж у 5 разів.

Спекулятивне вибіркове відбір можна узагалювати для врахування кількох припущень із кількох чернеткових моделей. Але не зовсім зрозуміло, який алгоритм найкращий для комбінації цих множинних здогадок.

У випадку однокроків попередні дослідження показали, що оптимальне рішення можна знайти, розв'язавши оптимальну лінійну транспортну програму — OTLP.

Однак OTLP надзвичайно складно розв'язати майже точно, оскільки він експоненціально зростає у словниковому запасі. То як ми можемо це вирішити?

Ключ — використати додаткову структуру у будівництві чернеткового дерева.

Попередні дослідження [Hu et al.] показали, що коли чернеткове дерево формується шляхом i.i.d. вибірки, шляхом дуалізації OTLP, оптимальне цільове значення можна обчислити за майже лінійний час шляхом субмодульної мінімізації.

Однак до нашої роботи жоден метод не міг розв'язати рішення, яке досягло б такого оптимального цільового значення. Без цієї відсутньої частини все, що дає нам попередня робота, — це ефективність блоків, теоретичне максимальне прискорення. Він не пояснює, як досягти цього прискорення.

Наша робота перша суттєво зменшила розмірність OTLP, використавши три інсайти.

Ми звертаємо дуалізацію OTLP у попередній роботі [Hu et al.] з комплементарною слабкістю, щоб сформулювати OTLP як задачу доцільності потоку.

Багато обмежень нерівності потоку є надлишковими. Використовуючи жадібний алгоритм з теорії поліматроїдів, ми можемо об'єднати ці елементи.

Ця задача зменшеного потоку має розв'язок, який можна параметризувати як софтмакс маловимірного вектора, і цей вектор можна обчислити шляхом опуклої мінімізації. Це зводить OTLP у V^{n+1} змінних до опуклої задачі мінімізації у V-змінних.

V все ще може бути досить великою, тому у нашій статті ми застосовуємо додаткові наближення з обмеженою цільовою помилкою моделі, щоб ще більше скоротити час обчислення.

У багатьох випадках, де V обмежений моделями top-k і n, як показано вище, Global Resolution є _єдиним_ розв'язувачем, здатним розв'язати OTLP за розумний час.

Крім того, використовуючи Global Resolution, ми можемо покращити рівень прийняття Llama та Gemma до 6%: Коротко кажучи, Global Resolution — це SOTA для оптимальної багаточернетної верифікації у спекулятивному декодуванні.

Тут ще багато роботи — розслабити налаштування iid або розширити на кілька кроків.