LLM 推理是一個數十億美元的問題。 我們的新論文介紹了一種在多草稿推測取樣中的 SOTA 算法——全球解析，這在解決此問題上取得了重大進展。 以下是詳細說明 🧵👇

一種高效推理的方法稱為推測取樣。 這使用一個便宜的「草稿」模型來產生「猜測」，以預測更大目標模型的輸出。

透過利用現代 GPU 的平行運算效率，這可以最終將目標模型的前向傳遞次數減少超過 5 倍。

投機性取樣可以概括為從多個草稿模型中獲取多個猜測。 但目前尚不清楚最佳的算法是什麼，以便結合這些多個猜測。

在單步驟的情況下，先前的研究顯示，最佳解可以通過解決最佳運輸線性規劃（OTLP）來找到。

然而，隨著詞彙量的指數增長，OTLP 的近似精確解決變得極其困難。我們該如何解決它呢？

關鍵在於利用草稿樹構建中的額外結構。

先前的研究 [Hu et. al.] 顯示，當草圖樹是通過獨立同分佈抽樣形成時，通過對偶化 OTLP，可以通過子模最小化在近線性時間內計算出最佳目標值。

然而，在我們的工作之前，沒有任何方法能夠解決達到這一最佳目標值的解決方案。沒有這個缺失的部分，所有之前的工作只告訴我們區塊效率，即理論上的最大加速。它並沒有告訴我們如何實現這種加速。

我們的工作是首次顯著降低OTLP的維度，利用了三個見解。

我們利用互補鬆弛的方式，逆轉了之前工作 [Hu et. al.] 中的 OTLP 雙重化，將 OTLP 公式化為一個流可行性問題。

許多流不等式約束是多餘的。利用多重體理論中的貪婪算法，我們可以將這些合併。

這個減少流量的問題有一個解決方案，可以參數化為低維向量的 softmax，並且這個向量可以通過凸最小化來計算。 這將 V^{n+1} 變數中的 OTLP 簡化為 V 變數中的凸最小化問題。

然而，V 仍然可能相當大，因此在我們的論文中，我們應用進一步的近似，並限制目標模型的錯誤率，以進一步減少計算時間。

在許多情況下，當 V 限制為 top-k 並且 n 草稿模型時，如上所示，Global Resolution 是唯一能夠在合理時間內解決 OTLP 的求解器。

此外，使用 Global Resolution，我們可以將 Llama 和 Gemma 的接受率提高最多 6%： 簡而言之，Global Resolution 是在投機解碼中進行最佳多草稿驗證的最先進技術。

這裡仍然有很多工作要做，可以通過放寬獨立同分佈的設定，或擴展到多個步驟。