Speculative Tree Decoding（スペキュラティブツリーデコーディング）

Speculative Tree Decoding — ツリー構造による投機的推論の拡張

Speculative Tree Decoding（ツリー投機デコーディング）は、従来の投機的デコーディング（Speculative Decoding）をツリー構造に拡張した推論高速化手法だ。基本的な投機的デコーディングが「1本の候補系列を生成・検証する」のに対し、ツリー版は複数の候補パスを木構造で同時に生成し、一括で検証することでGPUの並列計算能力をより有効に活用する。

基本：投機的デコーディングの復習

投機的デコーディングの原理:

1. ドラフトモデル（小型・高速）がk個のトークンを順次生成
2. ターゲットモデル（大型・高精度）がk個のトークンを一括評価（並列Attention）
3. 確率分布の一致判定で受理/棄却を決定
4. 最初に棄却されたトークンまでを受理、以降を再生成

並列評価により、kステップが「ほぼ1フォワードパス」のコストで完了するのが利点。ただし、ドラフトモデルの生成がターゲットと大きく外れると棄却率が上がり効果が薄れる。

ツリー構造への拡張

ツリー形成:

ドラフトモデルがトークンを生成する際、各ステップで上位K個の候補トークンを展開してツリーを形成:

ルート（直前のコンテキスト）
  A候補 (p=0.6)
    AA (p=0.7)  → 検証候補: [A, AA, AAA], [A, AA, AAB]
    AB (p=0.3)
  B候補 (p=0.4)
    BA (p=0.8)  → 検証候補: [B, BA, BAA]
    BB (p=0.2)

ツリーAttentionによる一括検証:

ターゲットモデルはこのツリー全体を1回のフォワードパスで評価する。通常のAttentionマスクを「ツリーアテンションマスク」に変更し、各ノードが自分の祖先ノードのみを参照できるよう制御する。

効果

LLaMA 7Bを使った実験（論文値）:

MedusaとEAGLEとの関係

MedusaとEAGLEはこのツリー投機デコーディングの考え方を発展させた実装:

• Medusa: ドラフトに複数の独立した小型ヘッドを使い、並列にツリーを生成
• EAGLE: オートリグレッシブな特徴量を利用して、より品質の高いドラフトでツリーを形成

両者ともターゲットモデルのウェイトを凍結し、ドラフト生成部分のみを追加訓練するアーキテクチャ。