Inferensi LLM adalah masalah multi-miliar dolar. Makalah baru kami memperkenalkan algoritma SOTA dalam pengambilan sampel spekulatif multi-draf, Resolusi Global, yang membuat terobosan signifikan ke dalam masalah ini. Membongkar di bawah ini 🧵👇

Salah satu pendekatan untuk inferensi yang efisien disebut pengambilan sampel spekulatif. Ini menggunakan model 'draf' murah untuk menghasilkan 'tebakan' untuk apa yang akan dihasilkan oleh model target yang lebih besar.

Dengan mengeksploitasi efisiensi paralelisme GPU modern, ini dapat mengurangi jumlah lintasan maju model target lebih dari 5x.

Pengambilan sampel spekulatif dapat digeneralisasi untuk mengambil beberapa tebakan dari beberapa model draf. Tetapi tidak jelas apa algoritme terbaik untuk menggabungkan beberapa tebakan ini.

Dalam kasus satu langkah, pekerjaan sebelumnya telah menunjukkan bahwa solusi optimal dapat ditemukan dengan memecahkan program linier transportasi yang optimal, OTLP.

Namun, OTLP sangat sulit untuk diselesaikan hampir persis karena tumbuh secara eksponensial dalam ukuran kosakata. Jadi bagaimana kita bisa menyelesaikannya?

Kuncinya adalah mengeksploitasi struktur tambahan dalam konstruksi pohon draf.

Pekerjaan sebelumnya [Hu et al.] menunjukkan bahwa ketika pohon draf dibentuk oleh pengambilan sampel I.I.D., dengan menggandakan OTLP, nilai objektif optimal dapat dihitung dalam waktu yang mendekati linier melalui minimalisasi submodular.

Namun, sampai pekerjaan kami, tidak ada metode yang dapat memecahkan solusi yang mencapai nilai objektif optimal ini. Tanpa bagian yang hilang ini, semua pekerjaan sebelumnya memberi kita efisiensi blok, percepatan maksimum teoretis. Itu tidak memberi tahu kita bagaimana mencapai percepatan ini.

Pekerjaan kami adalah yang pertama secara signifikan mengurangi dimensi OTLP, menggunakan tiga wawasan.

Kami membalikkan dualisasi OTLP dalam pekerjaan sebelumnya [Hu et. al.] dengan kelonggaran komplementer, untuk merumuskan OTLP sebagai masalah kelayakan aliran.

Banyak kendala ketimpangan aliran yang berlebihan. Dengan menggunakan algoritma serakah dari teori polymatroid, kita dapat menyatukannya.

Masalah aliran yang berkurang ini memiliki solusi yang dapat diparametrisasi sebagai softmax dari vektor dimensi rendah, dan vektor ini dapat dihitung melalui minimalisasi cembung. Ini mengurangi OTLP dalam variabel V^{n+1} menjadi masalah minimalisasi cembung dalam variabel V.

V masih bisa cukup besar, bagaimanapun, jadi dalam makalah kami kami menerapkan perkiraan lebih lanjut dengan tingkat kesalahan model target terbatas untuk lebih mengurangi waktu komputasi.

Untuk banyak kasus dengan V terbatas pada model draf top-k dan n, seperti yang ditunjukkan di atas, Resolusi Global adalah _satunya_ pemecah yang mampu memecahkan OTLP dalam waktu yang wajar.

Selain itu, dengan menggunakan Resolusi Global, kami dapat meningkatkan tingkat penerimaan pada Llama dan Gemma hingga 6%: Singkatnya, Resolusi Global adalah SOTA untuk verifikasi multi-draf yang optimal dalam decoding spekulatif.

Masih banyak pekerjaan yang harus dilakukan di sini, dengan melonggarkan pengaturan iid, atau dengan memperluas ke beberapa langkah.