ツリー投機的デコーディング（ツリートウキテキデコーディング）
投機的デコーディングを木構造に拡張した手法。ドラフトモデルが1つの線形シーケンスではなく複数の分岐候補を木構造で生成し、ターゲットモデルがTree Attention（木構造注意機構）で全分岐を同時検証する。SequoiaやMedusa v2が代表的な実装で、線形方式と比べて受理トークン数の期待値を40〜80%向上させる。
ツリー投機的デコーディングとは
ツリー投機的デコーディング（Tree Speculative Decoding）は、投機的デコーディングの発展形で、ドラフトモデルの出力を1本の線形シーケンスではなく木構造（ツリー）で管理する手法である。通常の投機的デコーディングでは、ドラフトモデルがK個のトークンを1本のパスで生成し、最初の却下位置以降はすべて破棄される。ツリー方式では各位置で複数の候補トークンを分岐させることで、却下時にも別の分岐パスが受理される可能性を維持し、1ステップあたりの受理トークン数を増加させる。
線形方式との比較
| 項目 | 線形投機的デコーディング | ツリー投機的デコーディング |
|---|---|---|
| ドラフト構造 | 1本のシーケンス（K個） | 木構造（B分岐 × D深さ） |
| 検証トークン数 | K個 | B^1 + B^2 + ... + B^D 個 |
| 受理パス数 | 1本 | 最大B^D本（最良パスを選択） |
| 受理トークン期待値 | Σ(i=1→K) α^i | 線形方式の1.4〜1.8倍 |
| 検証コスト | K個のフォワードパス相当 | ツリーサイズ分のフォワードパス相当 |
| メモリ使用量 | K × d × L | ツリーサイズ × d × L |
| 注意機構 | 標準の因果マスク | Tree Attention（専用マスク） |
具体例
受理率α=0.7、投機トークン数K=5の場合。
線形方式: 受理トークン期待値 = 0.7 + 0.7² + 0.7³ + 0.7⁴ + 0.7⁵ ≈ 2.17
ツリー方式（2分岐×3深さ、ノード数14）: 最良パスの受理トークン期待値 ≈ 3.5（線形の約1.6倍）
Tree Attention（木構造注意機構）
注意マスクの設計
通常の因果的注意（Causal Attention）は下三角行列のマスクを使用し、各トークンが自身より前の全トークンに注意を向ける。ツリー投機的デコーディングでは、木構造のパス関係に基づく注意マスクを使用する。
あるノードが注意を向けるのは、ルートから自身までのパス上にある祖先ノードのみ。兄弟ノードや他のパスのノードには注意を向けない。
マスクの構築例
3分岐×2深さのツリー（ノード数: ルート1 + 子3 + 孫9 = 13）の場合。
ノード配置: [root, c1, c2, c3, c1-1, c1-2, c1-3, c2-1, c2-2, c2-3, c3-1, c3-2, c3-3]
注意マスク（1=注意可能、0=マスク）:
root: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
c1: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
c2: [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
c3: [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
c1-1: [1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
...
GPU実装の最適化
Tree Attentionの注意マスクは疎（sparse）であるため、FlashAttention v2の変形カーネルや専用のCUDAカーネルが必要。主要な最適化手法は以下の通り。
- Sorted Tree Linearization: ツリーノードをDFS（深さ優先探索）順に並べ替え、注意マスクをブロック対角行列に近づける
- Shared Prefix Caching: 共通の祖先パスのKVキャッシュを全分岐で共有し、メモリ使用量を削減
- Dynamic Tree Pruning: 受理確率が低い分岐を検証前に枝刈りし、計算コストを削減
主要な実装
Sequoia（2024年）
Carnegie Mellon大学が発表。動的にツリー構造を最適化する手法。
- ドラフトモデルの出力確率に基づいて、各位置の分岐数を動的に決定
- 高確率のトークンが多い位置では分岐を増やし、不確実な位置では分岐を減らす
- ハードウェア特性（メモリ帯域幅、演算能力）も考慮してツリーサイズを自動チューニング
- 線形方式と比べて1.3〜1.6倍の追加高速化を達成
Medusa v2（2024年）
Meta Researchが発表。Medusa v1の複数ヘッド予測をツリー構造に拡張。
- 各Medusaヘッドがtop-k個の候補トークンを出力
- 全ヘッドの候補の直積（Cartesian Product）からツリーを構築
- Tree Attentionで全候補を同時検証
- ヘッド数3、top-k=3の場合、ツリーサイズは最大27ノード
- 線形Medusa v1と比べて1.4〜1.8倍の高速化
EAGLE-2（2024年）
Microsoft Researchが発表。EAGLE v1の自己回帰ドラフトヘッドをツリー化。
- ドラフトヘッドの出力から信頼度の高い分岐を選択的に展開
- Confidence-based pruning: 確率が閾値以下の分岐を早期に枝刈り
- 動的な分岐数（1〜5）で計算コストとリターンのバランスを最適化
- Llama 2 70B + Chat でベンチマーク、線形EAGLE v1比で25〜40%の追加高速化
ツリー構造の設計パターン
固定ツリー（Static Tree）
事前に定義した固定のツリー構造を全ステップで使用する。
| ツリー形状 | ノード数 | 検証コスト | 用途 |
|---|---|---|---|
| 2分岐×3深さ | 14 | 低 | メモリ制約のある環境 |
| 3分岐×2深さ | 12 | 低 | 浅い探索で十分なタスク |
| 4分岐×3深さ | 84 | 高 | 受理率が低いタスク |
| 2分岐×5深さ | 62 | 中 | コード生成（深い推測が有効） |
動的ツリー（Dynamic/Adaptive Tree）
ドラフトモデルの出力確率に基づいてステップごとにツリー構造を動的に変更する。
- 高エントロピー位置（文の先頭、選択肢が多い箇所）: 分岐を多くして候補を広く探索
- 低エントロピー位置（助詞、閉じ括弧、明確な続き）: 分岐を1つに絞り深く探索
- 全体のノード数はハードウェアの計算能力に合わせた上限（通常16〜64）内で配分
トークン予算の配分
GPUの処理能力に応じて、1ステップで検証可能なトークン数には実用的な上限がある。
- NVIDIA A100 80GB: 最大64ノード（性能低下なし）
- NVIDIA H100 80GB: 最大128ノード
- Apple M2 Ultra 192GB: 最大32ノード
この予算をツリーの幅（分岐数）と深さに配分するのが設計のポイント。
検証後のパス選択
ツリー内の複数パスが（部分的に）受理された場合、最終出力として1つのパスを選択する必要がある。
選択基準
- 最長受理パス: 受理されたトークン数が最も多いパスを選択（最も一般的）
- 最高確率パス: 受理されたトークンの累積確率が最も高いパスを選択
- ハイブリッド: 長さが同じ場合に確率でタイブレーク
よくある質問（FAQ）
Q1: ツリー投機的デコーディングは常に線形方式より速いですか？ A: 受理率が非常に高い場合（α>0.9）は線形方式でもほぼ全トークンが受理されるため、ツリー方式の追加コスト（メモリ、Tree Attention計算）が相対的に大きくなり、線形方式が有利。受理率0.5〜0.8の範囲でツリー方式の優位性が最大化する。
Q2: ツリーサイズの上限はどう決めますか？ A: GPUのメモリ帯域幅と演算能力から決まる。実用的にはA100で64ノード、H100で128ノードが目安。ノード数を増やしすぎるとTree Attentionの計算時間がターゲットモデルのフォワードパスより長くなり、逆に遅くなる。
Q3: 既存のフレームワークでツリー方式を使うにはどうしますか？ A: SGLang（v0.2+）がEAGLE-2のツリー投機的デコーディングをネイティブサポート。vLLM（v0.5+）もMedusa v2のツリー検証に対応。llama.cppは2025年時点で線形方式のみだが、ツリー対応のPRが進行中。
Q4: 複数のドラフトモデルの出力を1つのツリーに統合できますか？ A: 可能。異なるドラフトモデル（例: n-gram + 小型LLM + Medusaヘッド）の候補を1つのツリーに統合し、Tree Attentionで一括検証する手法が提案されている（Hybrid Tree Speculative Decoding, 2025年）。各ドラフトソースの強み（n-gramは繰り返しに強い、LLMは新規文脈に強い）を相補的に活用できる。
まとめ
- ツリー投機的デコーディングはドラフトを木構造に拡張し、受理トークン数の期待値を線形方式の1.4〜1.8倍に向上
- Tree Attention（木構造注意機構）により全分岐を1回のフォワードパスで同時検証
- Sequoia（動的ツリー最適化）、Medusa v2（複数ヘッドの直積ツリー）、EAGLE-2（信頼度ベース枝刈り）が主要実装
- 受理率0.5〜0.8の範囲で線形方式に対する優位性が最大化
- ツリーサイズはGPUメモリ帯域幅に依存し、A100で64ノード、H100で128ノードが実用上限