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

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