---
# System prepended metadata

title: Speculative Decoding
tags: [NLU, NLP, LLM, speculative decoding, ML]

---

Speculative Decoding
===
###### tags: `LLM`
###### tags: `ML`, `NLP`, `NLU`, `speculative decoding`

<br>

[TOC]

<br>

## Intro
- [Speculative Decoding: When Two LLMs are Faster than One](https://www.youtube.com/watch?v=S-8yr_RibJ4)

<br>

## 參考資料
- [Medusa（美杜莎）](https://blog.csdn.net/qq_29788741/article/details/132820178)
    - Karpathy曾多次提出，大模型「投機採樣」對於推理時間優化是一個出色的方案。 但是，儘管投機解碼能夠加速生成速度，但因其太過複雜，並沒有被許多開發者採用。
    - 為什麼LLM生成效率低？
        - 從系統角度來看，LLM生成遵循一種「以記憶體為限制」的計算模式，主要的延遲瓶頸來自記憶體讀取/寫入，而非算術計算。
- [[github] Medusa: Simple Framework for Accelerating LLM Generation with Multiple Decoding Heads](https://github.com/FasterDecoding/Medusa)
- [A Hitchhiker’s Guide to Speculative Decoding](https://pytorch.org/blog/hitchhikers-guide-speculative-decoding/)

<br>

## 討論

### Speculative Decoding 原理為何？
- **ChatGPT4**
    ### Speculative Decoding 原理

    Speculative Decoding 是一種在自然語言處理領域，尤其是在機器翻譯和自動文字生成中使用的技術。 這種方法主要用於提高解碼速度和效率，尤其是在生成文字時。 Speculative Decoding 的核心概念是事先預測可能的輸出序列，然後基於這些預測進行更有效率的運算資源分配。

    #### 原理與工作方式

    1. **並行預測**：
        - Speculative Decoding 透過在解碼過程中並行地預測多個可能的候選序列來運作。 這意味著系統不是逐步地一個接一個地產生序列，而是同時探索多個可能的序列擴展。

    2. **機率評估**：
        - 每個產生的候選序列都會根據其可能性（通常是基於模型輸出的機率分佈）被評估。 這些評估可以基於語言模型的得分，也可以結合其他標準，如語意相容性、語法正確性等。

    3. **最佳序列選擇**：
        - 在預測的序列中，根據定義的標準選擇最佳序列。 這可以透過比較每個序列的綜合得分來完成，得分最高的序列被認為是最有可能的正確輸出。

    4. **資源優化**：
        - 透過預測多個序列，系統可以更好地分配計算資源。 例如，對於那些初步評估得分較低的序列路徑，可以提前停止進一步的計算，從而將資源集中用於更有前景的候選項。

    #### 應用場景

    - **機器翻譯**：在機器翻譯中，Speculative Decoding 可以用來快速產生多個翻譯選項，然後從中選擇最佳的翻譯結果。
    - **文字生成**：在自動文字生成，如新聞生成、內容創作等應用程式中，透過並行產生多個文字片段，加速文字的創作過程。

    #### 優點

    - **速度提升**：透過平行處理與預測，Speculative Decoding 能顯著提昇文字產生的速度。
    - **效率提高**：有效地使用計算資源，避免在不太可能的候選項上浪費計算力。
    - **品質最佳化**：透過比較多個候選項，能夠提高生成文字的質量，選擇出最佳的輸出。

    #### 缺點

    - **複雜度增加**：管理和實作 Speculative Decoding 需要複雜的演算法和最佳化技巧，可能增加系統的實作複雜度。
    - **資源消耗**：雖然提高了單次產生的效率，但預測多個序列可能會增加整體的資源消耗，特別是在資源受限的環境中。

    總的來說，Speculative Decoding 是一種旨在提高解碼階段效率和速度的技術，透過並行產生和選擇最佳候選，使得在需求快速反應的應用情境中特別有用。

<br>

### [[arxiv][pdf] Fast Inference from Transformers via Speculative Decoding](https://arxiv.org/pdf/2211.17192)

- ### 附件是關於大語言模型(LLM)的相關技術，請再協助整理重點。針對關鍵的地方，請詳細說明。
    [ChatGPT4o]
    ### 主要重點整理：大語言模型（LLM）技術
    1. **背景與挑戰**
        - ==大型自回歸模型如 Transformers 在**進行推理時速度緩慢**，因為生成每個新的token都需要序列化地運行模型多次。==
        - 為了解決這個問題，提出了推測性解碼（Speculative Decoding）技術，以加速自回歸模型的解碼過程。
    2. **推測性解碼技術**
        - 推測性解碼是一種算法，用於通過並行計算多個 token 來加速自回歸模型的解碼過程，而不改變模型的輸出。
        - 該方法基於以下觀察：
            1. 許多困難的語言模型任務包含可被更高效模型近似的簡單子任務。
            2. 使用推測性執行和新穎的取樣方法，可以加速大型模型的精確解碼。
    3. **技術細節**
        - 推測性執行：這是一種優化技術，允許並行執行任務以提高效率。
        - 推測性取樣：使用更高效的草稿模型生成多個token，然後用目標模型並行驗證這些token，並接受那些能保持相同分佈的token。
    4. **算法步驟**
        1. 草稿生成：使用草稿模型 $M_q$ 自回歸地生成 $γ$ 個token。
        2. 並行計算：對這些草稿 token 進行並行計算，生成 $γ+1$ 組logits。
        3. 拒絕取樣：接受的概率為 $\min \left( 1, \frac{q(x)}{p(x)} \right)$，如果被拒絕，則重新從調整後的分佈中取樣。
    5. **實驗結果**
        - 在多個任務和模型尺寸下測試了該方法，包括無條件文本生成、英德翻譯和新聞摘要等任務。
        - 實驗結果顯示，該方法能顯著加速模型推理速度，例如，在T5-XXL模型上展示了2至3倍的速度提升。
    6. **公式推導與分析**
        - 接受率公式：
            $\alpha = E(\min(p, q))$
            其中，$α$ 為接受率，$p$ 和 $q$ 分別為目標模型和草稿模型的分佈。
        - 改進的牆時間公式：
            $\text{改善因子} = \frac{1 - \alpha^{\gamma+1}}{(1 - \alpha)(\gamma c + 1)}$
            其中， $γ$ 為草稿生成的 token 數量，$c$ 為草稿模型與目標模型運行時間的比率。
    7. **推測性取樣與拒絕取樣比較**
        - 推測性取樣的接受概率更高，從而更高效。
        - 標準拒絕取樣：
            $P(x = x') = P(\text{guess accepted}, x = x') + P(\text{guess rejected}, x = x')$
            其中，
            - $P(\text{guess accepted}, x = x') = q(x') \min \left(1, \frac{p(x')}{q(x')} \right)$
            - $P(\text{guess rejected}, x = x') = (1 - \beta)p'(x')$
    8. **未來研究方向**
        - 進一步研究推測性解碼與束搜索（beam search）的兼容性。
        - 探索定制近似模型以獲得更大的改進。
        - 在其他領域（如圖像生成）中的應用。
    9. **結論**
        - 推測性解碼為加速自回歸模型推理提供了一種有效的方法，特別是在可用的計算資源充足的情況下。
        - 該方法不僅簡單易行，且不需要對模型進行重新訓練，是一種實用且強大的技術改進。

<br>

<hr>

<br>

### [[arxiv][pdf] Accelerating Large Language Model Decoding with Speculative Sampling](https://arxiv.org/pdf/2302.01318)

- ### 附件是關於大語言模型(LLM)的相關技術，請再協助整理重點。針對關鍵的地方，請詳細說明。
    [ChatGPT4o]
    ### 主要重點整理：加速大型語言模型解碼技術
    1. **背景與挑戰**
        - 大型Transformer模型如Chinchilla具有數百億參數，在自然語言處理、電腦視覺和強化學習任務上展現出色的性能。
        - 然而，==這些模型的解碼過程高度**耗時且效率低下**，尤其是隨著模型參數數量的增加，解碼時間顯著增加。==
    2. **推測性取樣技術**
        - ==**推測性取樣（Speculative Sampling, SpS）**== 是一種用於加速Transformer解碼的算法。
        - 核心思想是使用一個較小且更快的草稿模型生成短期續接，並利用修改後的拒絕取樣方法保證生成的樣本分佈與目標模型一致。
    3. **技術細節**
        - 步驟1：生成一個長度為K的草稿序列，可以通過並行模型或較快的自回歸模型實現。
        - 步驟2：使用較大的目標模型對草稿進行評分。
        - 步驟3：使用修改的拒絕取樣方法，從左到右接受草稿中的一部分token，從而恢復目標模型的分佈。
    4. **算法步驟**
        - **草稿生成**：使用草稿模型 $p(.∣.)$ 自回歸地生成K個token。
        - **並行計算**：對草稿進行並行計算，生成K+1組logits。
        - **拒絕取樣**：對每個草稿token進行拒絕取樣，接受的概率為 $\min \left( 1, \frac{q(x_{n+1} | x_1, \ldots, x_n)}{p(x_{n+1} | x_1, \ldots, x_n)} \right)$ ，如果被拒絕，則重新從目標模型的調整後分佈中取樣。
    5. **實驗結果**
        - 在不同任務和模型尺寸下測試了該方法，包括XSum摘要生成和HumanEval代碼生成。
        - 實驗結果顯示，在不改變模型參數和架構的情況下，該方法能顯著加速解碼速度，例如在Chinchilla 70B模型上達到了2到2.5倍的速度提升。
    6. **接受率與性能**
        - 接受率依賴於應用領域和解碼方法。對於HumanEval任務，由於代碼中包含許多常見子序列，較小的模型可以較高的接受率生成這些序列。
        - 隨著 $K$ 值（草稿 token 數量）的增加，總體速度增益會達到一個平台或甚至回落。
    7. **草稿模型選擇**
        - 使用較小的目標語言模型作為草稿模型，可以獲得較高的接受率，並且從工程和工作流程角度來看更為方便。
        - 草稿模型可以是目標模型的簡化版本，訓練較少層數以減少通信開銷。
    8. **結論**
        - 推測性取樣提供了一種有效的解碼加速方法，不需要修改目標模型參數或架構，並且能與其他現有的降低延遲技術互補。
        - 在Chinchilla 70B上驗證了該方法的有效性，實現了顯著的速度提升，且在下游任務中的樣本分佈與原始模型保持一致。
    9. **未來研究方向**
        - 探索更高效的草稿生成方法和其他解碼技術的結合。
        - 進一步優化草稿模型和拒絕取樣過程，以提升接受率和整體效率。
    
    ---
    
    ### 詳細說明關鍵技術
    1. **推測性取樣**
        推測性取樣主要包括生成草稿序列、並行評分和修改的拒絕取樣三個步驟。具體過程如下：

        1. **草稿生成**：
            草稿模型自回歸生成一系列token，每次生成一個token，直到生成K個token。
        2. **並行評分**：
            並行計算這些草稿token的logits，目標模型計算的logits與草稿模型的logits進行比較。
        3. **拒絕取樣**：
            按照一定的概率接受或拒絕草稿token。如果草稿token被拒絕，則從調整後的目標模型分佈中重新取樣。

    2. **修改的拒絕取樣方法**
        這種方法確保了目標模型分佈的準確恢復，即使在拒絕了一部分草稿token的情況下，仍然能保證最終生成的樣本分佈與目標模型一致。

    3. **草稿模型選擇**
        草稿模型可以是目標模型的簡化版本，通常選擇較少層數以減少通信開銷，從而實現快速取樣和高接受率。

    ### 性能評估
    實驗結果表明，推測性取樣能顯著提高大型語言模型的解碼速度，同時保持樣本質量和分佈的一致性。這在各種任務和設定中得到了驗證，展示了其廣泛的應用潛力。