ビームサーチとは？原理・greedy decoding との比較・Python実装

「翻訳した文が短すぎる」「生成文の途中で変な単語を選んで、文全体がおかしくなった」——これらはすべて、デコーディング（decoding） の選択失敗で起きます。

言語モデルは「次のトークンの確率分布」しか返しません。その分布からどうやって最終的な文を決めるか、そのアルゴリズムがデコーディングです。最も単純な方法である greedy decoding（貪欲法） は高速ですが、局所最適に陥って全体として質の低い系列を出力することがあります。これを解消するために広く使われているのが ビームサーチ（beam search） です。

• 機械翻訳（英日など）: ビームサーチは 2016 年の Google Neural Machine Translation（GNMT）でも中心的な役割を果たし、BLEU スコアを大きく改善しました
• 音声認識の後処理: 音響モデルの出力をビームサーチで整形し、単語系列を決定します
• コード補完や要約: 確定的で品質が高い出力が求められるタスクでは現在もビームサーチが使われています

本記事の内容

• 系列生成の探索問題 — 全探索が不可能な理由
• greedy decoding（貪欲法）とは何か、なぜ失敗するのか
• ビームサーチのアルゴリズムと数式
• 対数尤度スコアの累積と長さ正規化
• 繰り返しペナルティ
• greedy vs ビーム vs サンプリングの比較
• トイ言語モデルを使った Python 実装と検証

語彙サイズが 50,000、系列長が 20 トークンになると候補数は $10^{92}$ を超えます。全探索は物理的に不可能であり、これが「どの経路を選ぶか」という探索問題の本質です。

前提知識

この記事を読む前に、以下の記事を読んでおくと理解が深まります。

言語モデルとパープレキシティを理解する

N-gramモデルからニューラル言語モデルまでの発展と、パープレキシティの数学的定義を解説します。

系列生成とは何か — 探索問題としての定式化

自己回帰生成の確率モデル

言語モデルが文を生成するとき、内部では「条件付き確率の連鎖」として計算が進んでいます。入力（プロンプト）$\bm{x}$ が与えられたとき、出力系列 $\bm{y} = (y_1, y_2, \ldots, y_T)$ の同時確率は次のように連鎖律で分解されます。

$$ P(\bm{y} \mid \bm{x}) = \prod_{t=1}^{T} P(y_t \mid y_1, y_2, \ldots, y_{t-1}, \bm{x}) $$

ここで $P(y_t \mid y_1, \ldots, y_{t-1}, \bm{x})$ が「これまでに出力したトークン列 $y_1, \ldots, y_{t-1}$ と入力 $\bm{x}$ を条件として、次のトークン $y_t$ がどれだけ自然か」を表します。Transformer デコーダはこの条件付き確率をステップごとに計算する機械です。

目標は、この確率を最大化する最良の出力系列を見つけることです。

$$ \bm{y}^* = \arg\max_{\bm{y}} P(\bm{y} \mid \bm{x}) = \arg\max_{\bm{y}} \sum_{t=1}^{T} \log P(y_t \mid y_1, \ldots, y_{t-1}, \bm{x}) $$

対数を取るのは数値的な安定性のためです（小さな確率の積はアンダーフローを起こすため）。

なぜ全探索できないのか

語彙サイズを $V$、最大系列長を $T$ とすると、可能な系列の総数は $V^T$ 通りになります。

たとえば GPT 系モデルで使われる語彙サイズ $V \approx 50{,}000$、系列長 $T = 100$ の場合：

$$ V^T = 50{,}000^{100} \approx 10^{480} $$

これは宇宙の原子の数（$\approx 10^{80}$）より遥かに多く、文字通り列挙不可能です。したがって何らかの近似探索が必要になります。

ここに計算量と品質のトレードオフが生まれます。全探索の代わりに「良さそうな候補を選びながら探索する」方法論として、大きく 3 つのアプローチがあります：決定的方法（greedy / beam）、確率的方法（sampling）、そしてその中間です。

この記事では決定的方法の中心である greedy と beam を深く掘り下げていきます。サンプリング（top-k / top-p / temperature）との違いは後の節で比較します。

greedy decoding（貪欲法）とは

アルゴリズムの直感

「次の 1 手だけを見て最善を選ぶ」——これが greedy decoding の発想です。将棋の初心者が「今の局面で最も駒得になる手」だけを選ぶのと同じ思想です。

各ステップで、次のトークンの条件付き確率が最も高い 1 個を選びます。

$$ y_t = \arg\max_{y \in \mathcal{V}} P(y \mid y_1, \ldots, y_{t-1}, \bm{x}) $$

ステップを追うと次のようになります。

t=1: y_1 = argmax P(y | x)
t=2: y_2 = argmax P(y | y_1, x)
t=3: y_3 = argmax P(y | y_1, y_2, x)
      …

各ステップで 1 つのトークンだけを選ぶので、計算量は $O(TV)$（$T$ ステップ、各ステップで語彙 $V$ のスコアを評価）となり、非常に高速です。

greedy decoding が失敗するとき

この図が示す問題の核心は「今の 1 手の良さが、将来の選択肢の良さを決める」という依存関係です。greedy はステップ 0 で「A」（確率 0.55）を選びます。しかし「A」の後に続けられるトークンは全て確率 0.20 均等——つまり「A」を選ぶと次のステップで良い続きが期待できません。

一方「B」（確率 0.40）を選ぶと、その後に「E」（確率 0.92）という高確率のトークンが続く道が開きます。結果として：

• greedy の経路「A → A → A」の累積対数確率 = $-3.82$
• ビームが発見する最適経路「B → E → A」の累積対数確率 = $-1.08$

後ほど Python 実装でこれを実際に確認します。

これは「短期的な得」が「長期的な損」につながる典型例です。greedy decoding が特に問題を起こすのは：

1. 序盤の低確率選択が良い続きを呼ぶ場合（「良い出だしは地味に見える」）
2. 語彙が偏って分布していて、高確率トークンが「続けにくい」場合（たとえば接続詞や助動詞が高確率でも後の意味が広がらない）

この限界を克服するために、複数の候補を並列に持ち続ける方法が考案されました——それがビームサーチです。

ビームサーチとは

直感：「候補を絞りながら広く探す」

ビームサーチは、常に上位 $B$ 個の部分系列（ビーム）を保持しながら探索を進めます。$B$ をビーム幅（beam width）またはビームサイズと呼びます。

イメージとしては「登山で複数のパーティーが並行して異なるルートを歩く」ようなものです。各ステップでどのパーティーも「可能な次の一歩」を全て評価し、全パーティー合わせて最も良い $B$ ルートだけ残して次のステップへ進みます。

青いノードがビーム内の候補（上位 B=2 個）、灰色が枝刈りされたノードです。ステップを重ねるにつれて青い経路だけが生き残り、最終的に最高スコアの完成系列を選びます。

アルゴリズムの詳細

初期化

ビーム $\mathcal{B}_0 = \{(\texttt{}, 0.0)\}$（開始トークン、スコア 0）

各ステップ $t = 1, 2, \ldots, T$ での更新

1. 現在のビーム $\mathcal{B}_{t-1}$ 内の各仮説 $(\bm{y}_{1:t-1}, s)$ に対して、語彙の全トークン $v \in \mathcal{V}$ を拡張します

$$ \text{score}(\bm{y}_{1:t}) = \sum_{i=1}^{t} \log P(y_i \mid y_1, \ldots, y_{i-1}, \bm{x}) $$

このスコアは各ステップの対数確率の和です。積（確率の積）でなく和（対数確率の和）を使うのは、数値的安定性のためです。

2. $|\mathcal{B}_{t-1}| \times |\mathcal{V}|$ 個の候補から、スコア上位 $B$ 個を選んで新しいビーム $\mathcal{B}_t$ とします

$$ \mathcal{B}_t = \operatorname{top-}B\!\left(\bigcup_{(\bm{y}, s) \in \mathcal{B}_{t-1}} \left\{(\bm{y} \circ v,\ s + \log P(v \mid \bm{y}, \bm{x})) : v \in \mathcal{V}\right\}\right) $$

ここで $\bm{y} \circ v$ は系列 $\bm{y}$ にトークン $v$ を追加したもの、$\operatorname{top-}B$ はスコア上位 $B$ 個を返す操作です。

3. 終了トークン <EOS> を生成した仮説は完成リストに移します

終了条件

• 全ての活性なビームが <EOS> を生成した
• または最大生成長 $T_{\max}$ に到達した

完成リストから長さ正規化スコア（次節で説明）が最も高い系列を最終出力とします。

具体的な計算例（語彙 3 個・ビーム幅 2）

語彙 $\{A, B, C\}$、ビーム幅 $B = 2$ の場合を追ってみましょう。

ステップ 1（$\mathcal{B}_0 = \{\texttt{}\}$ から拡張）

上位 2 個を保持：$\mathcal{B}_1 = \{A,\ B\}$（C は枝刈り）

ステップ 2（$\mathcal{B}_1 = \{A, B\}$ から拡張、各 3 通り計 6 候補）

上位 2 個を保持：$\mathcal{B}_2 = \{AA\ (-0.8),\ AB\ (-1.1)\}$

このプロセスを終了条件まで繰り返します。

対数尤度スコアの累積

左のグラフは各ステップで追加される対数確率 $\log P(y_t \mid \cdot)$ を示しています。この値は必ず負です（確率 $\in (0, 1]$ なので対数は 0 以下）。右の累積スコアは步数が増えるにつれ単調に下がっていきます。

これが重要な含意をもたらします。長い系列は短い系列より必ず累積スコアが低くなるのです。スコアがすべて負の値の足し算なので、長くなれば必ず総和は下がります。この「短い系列への偏り」を補正するために長さ正規化が必要です。

長さ正規化

問題：短い系列への系統的なバイアス

具体例で確認しましょう。各ステップの対数確率が全て $-0.2$ とすると：

3 トークン系列：$(-0.2) + (-0.2) + (-0.2) = -0.6$

8 トークン系列：$(-0.2) \times 8 = -1.6$

仮に 8 トークン系列のほうが意味的に完結していても、スコアだけ見ると 3 トークン系列が圧倒的に有利です。これではビームサーチが常に短い文を優先してしまいます。

グラフを見ると $\alpha = 0$（正規化なし）では短い系列（青）のスコアが長い系列（赤）を大幅に上回っています。$\alpha$ を大きくすると交差点が生まれ、$\alpha = 0.6$ 付近（オレンジゾーン）では合理的なバランスが取れています。

解決策：長さ正規化スコア

Google Neural Machine Translation (GNMT) で提案された長さ正規化式は次のとおりです。

$$ \text{score}(\bm{y}) = \frac{1}{|\bm{y}|^\alpha} \sum_{t=1}^{|\bm{y}|} \log P(y_t \mid y_1, \ldots, y_{t-1}, \bm{x}) $$

パラメータ $\alpha$ の効果：

実用では $\alpha = 0.6 \sim 0.7$ が標準的です（GNMT の推奨値）。より精密な式として GNMT 論文では次の形式も提案されています。

$$ \text{lp}(|\bm{y}|) = \frac{(5 + |\bm{y}|)^\alpha}{(5 + 1)^\alpha} $$

これは $|\bm{y}| = 1$ で分母と等しくなる正規化の工夫で、極端に短い系列が過度に優遇されるのを防ぎます。

長さ正規化を入れることで、ビームサーチは意味的に完結した長めの系列も公平に評価できるようになります。

ビーム幅の効果

ビーム幅を変えると何が起きるか

$B=1$（greedy）から始まり、幅を大きくするほど最終スコアは上昇します。ただし 収益は逓減します——$B=1$ から $B=2$ への改善は大きいですが、$B=8$ から $B=10$ への改善はほとんどありません。これはビームが確率的に良い経路をある程度網羅すると、残りの経路が本質的に低品質であるためです。

ビーム幅と計算量のトレードオフ

各ステップで $B$ 個の候補それぞれに対して語彙 $V$ 個の次トークンを評価するため、計算量は $O(T \cdot B \cdot V)$ です。greedy の $O(T \cdot V)$ に対して $B$ 倍のコストです。

青線（スコア）は $B=4$ を超えたあたりで頭打ちになる一方、赤の点線（計算量）は線形に増え続けます。実用的な機械翻訳・要約モデルでは $B = 4 \sim 8$ が最もバランスが良く、多くの実装でこの範囲がデフォルト値として採用されています。

ビーム幅と多様性

「ビームを増やせば多様な出力が得られる」という直感はしばしば裏切られます。確率分布が偏っている（一部のトークンが高確率）場合、上位 $B$ 個のビームはどれも似た系列に収束しがちです。この図では $B=8$ にしてもユニーク系列率が低いままで、多くのビームが重複した経路を辿っていることがわかります。

多様性が必要なタスク（対話生成、ブレインストーミング支援など）では、ビームサーチより後述のサンプリング手法の方が適しています。

繰り返しペナルティ

ビームサーチの実用上の欠陥として、退化（degeneration）——同じフレーズやトークンが繰り返し生成される現象——があります。たとえば「the the the …」や「私は、私は、私は…」のような出力です。

これは累積スコアの観点から説明できます。ある時点で「the」が高確率になると、「the」の後もまた「the」が高確率になる（文脈上連続しやすい）という正のフィードバックが生まれます。

この問題への対処として、繰り返しペナルティ（repetition penalty）が用いられます。既に生成したトークンのロジットを罰則として下げる方法です。

トークン $v$ がこれまでに $c_v$ 回出現した場合、調整後のスコアは：

$$ \log \tilde{P}(v \mid \cdot) = \frac{\log P(v \mid \cdot)}{r^{c_v}} $$

ここで $r > 1$ は繰り返しペナルティ係数です（Hugging Face の transformers では repetition_penalty パラメータで制御、デフォルト $r = 1.0$ で無効）。$r = 1.2 \sim 1.5$ 程度が実用的な範囲です。

別の実装として、既出トークンのロジットに固定値 $\delta$ を加算する方法もあります：

$$ \text{logit}'(v) = \begin{cases} \text{logit}(v) – \delta & \text{if } v \in \text{generated tokens} \\ \text{logit}(v) & \text{otherwise} \end{cases} $$

ここで $\delta > 0$ はペナルティの強さです。

Python 実装：greedy vs ビームサーチの比較検証

トイ言語モデルの設計

greedy decoding が失敗し、ビームサーチが最適解を発見する具体例を Python で実装して検証します。

語彙 5 個 $\{A, B, C, D, E\}$、3 ステップの文脈依存言語モデルを手動設計します。

• ステップ 0: $A$ が確率 0.55 で最高（greedy は $A$ を選ぶ）、$B$ は 0.40 で 2 番手
• ステップ 1 | 前が $A$: 全トークン均等（次の良い続きがない）
• ステップ 1 | 前が $B$: $E$ が確率 0.92 で圧倒的に高い
• ステップ 2 | 前が $E$: $A$ が確率 0.92 で高い

設計の意図：greedy は step 0 で $A$（最高確率）を選ぶが、$A$ の後の展開は貧弱で最終的に損をする。$B$ を保留しておくと step 1 で $E$、step 2 で $A$ という高品質経路が開ける。

import numpy as np

np.random.seed(42)

# --- 語彙とトイ言語モデルの定義 ---
VOCAB = ["A", "B", "C", "D", "E"]
log = np.log

# step 0 の確率（文脈なし）
p0 = {"A": 0.55, "B": 0.40, "C": 0.02, "D": 0.02, "E": 0.01}

# step 1 の確率（前のトークンを条件として）
p1 = {
    "A": {"A": 0.20, "B": 0.20, "C": 0.20, "D": 0.20, "E": 0.20},
    "B": {"A": 0.02, "B": 0.02, "C": 0.02, "D": 0.02, "E": 0.92},  # B → E が圧倒的
    "C": {"A": 0.20, "B": 0.20, "C": 0.20, "D": 0.20, "E": 0.20},
    "D": {"A": 0.20, "B": 0.20, "C": 0.20, "D": 0.20, "E": 0.20},
    "E": {"A": 0.20, "B": 0.20, "C": 0.20, "D": 0.20, "E": 0.20},
}

# step 2 の確率（前のトークンを条件として）
p2 = {
    "E": {"A": 0.92, "B": 0.02, "C": 0.02, "D": 0.02, "E": 0.02},  # E → A が圧倒的
    "A": {"A": 0.20, "B": 0.20, "C": 0.20, "D": 0.20, "E": 0.20},
    "B": {"A": 0.20, "B": 0.20, "C": 0.20, "D": 0.20, "E": 0.20},
    "C": {"A": 0.20, "B": 0.20, "C": 0.20, "D": 0.20, "E": 0.20},
    "D": {"A": 0.20, "B": 0.20, "C": 0.20, "D": 0.20, "E": 0.20},
}

def path_score(y0, y1, y2):
    """系列 (y0, y1, y2) の累積対数確率を返す"""
    return log(p0[y0]) + log(p1[y0][y1]) + log(p2[y1][y2])

次に greedy decoding を実装します。

# --- greedy decoding ---
def greedy_decode():
    # step 0: p0 から最大確率を選ぶ
    y0 = max(p0, key=p0.get)
    # step 1: p1[y0] から最大確率を選ぶ
    y1 = max(p1[y0], key=p1[y0].get)
    # step 2: p2[y1] から最大確率を選ぶ
    y2 = max(p2[y1], key=p2[y1].get)
    score = path_score(y0, y1, y2)
    return [y0, y1, y2], score

greedy_path, greedy_score = greedy_decode()
print(f"Greedy: {' → '.join(greedy_path)}")
print(f"  累積対数確率: {greedy_score:.4f}")
print(f"  正規化スコア: {greedy_score / 3:.4f}")

Greedy: A → A → A
  累積対数確率: -3.8167
  正規化スコア: -1.2722

step 0 で $A$（確率 0.55）を選び、step 1 でも $A$ を選び（全て均等 0.20 なのでどれを選んでも同じ）、step 2 も $A$ というパターンになります。対数確率の累積は $-3.82$ と非常に低い値です。

次に ビームサーチ（$B = 2$）を実装します。

# --- ビームサーチ (beam width B=2) ---
def beam_search(beam_width=2):
    # step 0: 全トークンを候補として追加
    beams = [(log(p0[v]), [v]) for v in VOCAB]
    beams.sort(key=lambda x: -x[0])
    beams = beams[:beam_width]  # 上位 B=2 を保持

    print(f"\nStep 0 後のビーム（上位{beam_width}個）:")
    for score, tokens in beams:
        print(f"  {' → '.join(tokens)}: score={score:.4f}")

    # step 1: 各ビームから全トークンを拡張
    candidates = []
    for score, tokens in beams:
        y0 = tokens[-1]
        for v in VOCAB:
            new_score = score + log(p1[y0][v])
            candidates.append((new_score, tokens + [v]))
    candidates.sort(key=lambda x: -x[0])
    beams = candidates[:beam_width]

    print(f"\nStep 1 後のビーム（上位{beam_width}個）:")
    for score, tokens in beams:
        print(f"  {' → '.join(tokens)}: score={score:.4f}")

    # step 2: 各ビームから全トークンを拡張
    candidates = []
    for score, tokens in beams:
        y1 = tokens[-1]
        for v in VOCAB:
            new_score = score + log(p2[y1][v])
            candidates.append((new_score, tokens + [v]))
    candidates.sort(key=lambda x: -x[0])
    beams = candidates[:beam_width]

    print(f"\nStep 2 後のビーム（上位{beam_width}個）:")
    for score, tokens in beams:
        print(f"  {' → '.join(tokens)}: score={score:.4f}")

    best_score, best_tokens = beams[0]
    return best_tokens, best_score

beam_path, beam_score = beam_search(beam_width=2)
print(f"\nBeam(B=2): {' → '.join(beam_path)}")
print(f"  累積対数確率: {beam_score:.4f}")
print(f"  正規化スコア: {beam_score / 3:.4f}")

Step 0 後のビーム（上位2個）:
  A: score=-0.5978
  B: score=-0.9163

Step 1 後のビーム（上位2個）:
  B → E: score=-0.9997
  A → A: score=-2.2073

Step 2 後のビーム（上位2個）:
  B → E → A: score=-1.0831
  A → A → A: score=-3.8167

Beam(B=2): B → E → A
  累積対数確率: -1.0831
  正規化スコア: -0.3610

step 0 では greedy と同様に $A$ がトップですが、ビームサーチは $B$ がスコア 2 位として温存されます。step 1 で $B$ から $E$（確率 0.92）が展開されると「$B \to E$」系列のスコアが $A$ 系列を逆転します。その結果 step 2 では B → E → A が最高スコアを獲得します。

最後に比較をまとめます。

# --- 全経路を列挙して最適解を確認 ---
all_paths = []
for y0 in VOCAB:
    for y1 in VOCAB:
        for y2 in VOCAB:
            s = path_score(y0, y1, y2)
            all_paths.append((s, y0, y1, y2))
all_paths.sort(key=lambda x: -x[0])

print("=== 全経路の上位5 ===")
for i, (s, y0, y1, y2) in enumerate(all_paths[:5]):
    marker = ""
    if [y0, y1, y2] == greedy_path:
        marker = "  ← greedy の選択"
    if [y0, y1, y2] == beam_path:
        marker = "  ← beam(B=2) の選択"
    print(f"{i+1}. {y0}→{y1}→{y2}: {s:.4f} (norm={s/3:.4f}){marker}")

print(f"\nまとめ:")
print(f"  Greedy:   {' → '.join(greedy_path)}  スコア={greedy_score/3:.4f}")
print(f"  Beam B=2: {' → '.join(beam_path)}  スコア={beam_score/3:.4f}")
print(f"  改善幅:   {(beam_score - greedy_score)/3:.4f}")

=== 全経路の上位5 ===
1. B→E→A: -1.0831 (norm=-0.3610)  ← beam(B=2) の選択
2. A→E→A: -2.2907 (norm=-0.7636)
3. A→A→A: -3.8167 (norm=-1.2722)  ← greedy の選択
4. A→A→B: -3.8167 (norm=-1.2722)
5. A→A→C: -3.8167 (norm=-1.2722)

まとめ:
  Greedy:   A → A → A  スコア=-1.2722
  Beam B=2: B → E → A  スコア=-0.3610
  改善幅:   0.9112

ビームサーチは最良の経路「$B \to E \to A$」を確実に発見し、greedy より正規化スコアで +0.91 という大幅な改善を達成しました。「最高確率のトークンを選ぶ」greedy は 3 位にも入れない経路しか見つけられていません。

この結果から、前節で示した「短期最大化が長期損失を生む」という問題が具体的に確認できます。

greedy vs ビームサーチ vs サンプリングの比較

デコーディング手法の選択は、タスクによって大きく変わります。

200 試行の平均で、ビーム幅を増やすほどスコアが向上します。ただし $B=2 \to B=4$ の差は $B=1 \to B=2$ より小さく、収益逓減が示されています。

サンプリング手法との根本的な違い

ビームサーチは決定的（deterministic）です。同じ入力に対して常に同じ出力を返します。一方、サンプリング手法は確率的（stochastic）で、実行のたびに異なる出力が得られます。

この図は同じ確率分布に対して 4 つの方法がどう扱うかを示しています。

元の分布（左上）: greedy もビームサーチも、この分布の上位トークンを評価します。高確率トークンが明確に存在します。

Top-k サンプリング（右上）: 上位 $k$ 個（この例では 3 個）のトークンのみに確率を再配分し、確率的に選びます。低確率トークンは完全に除外されます。

Top-p（Nucleus）サンプリング（左下）: 累積確率が閾値 $p$（例：0.9）に達するまでのトークン集合から確率的に選びます。Top-k より動的で、確率分布の形状に応じて候補数が変わります。

Temperature サンプリング（右下）: すべてのトークンに確率を与えますが、Temperature $T > 1$ では分布が均一になり（多様性増加）、$T < 1$ では最高確率トークンにさらに集中します。

各サンプリング手法の確率 $P_\text{sample}$ は次の式で定義されます（Temperature の場合）：

$$ P_\text{sample}(y_t) = \frac{\exp(\text{logit}(y_t) / T)}{\sum_{v} \exp(\text{logit}(v) / T)} $$

$T \to 0$ の極限がまさに greedy decoding です（最大ロジットに確率 1 が集中）。

手法の使い分け表

$T$ は系列長、$B$ はビーム幅、$V$ は語彙サイズです。

一般的な指針としては： – 翻訳・要約・穴埋め → ビームサーチ（品質と再現性が重要） – チャットボット・創作 → Top-p または Temperature（多様性が価値を持つ） – コード補完 → ビームサーチまたは小さい Temperature（正確性重視） – 超高速推論（エッジデバイス等） → Greedy（計算コスト最小）

ビームサーチの変種と発展

Diverse Beam Search

通常のビームサーチが似た系列を生成してしまう問題に対して、Diverse Beam Search (DBS)（Vijayakumar et al., 2016）は、ビームをグループに分けて各グループ内で多様性を促すペナルティを加えます。

$$ \text{score}(y_t, g) = \log P(y_t \mid \bm{y}_{

ここで $d(\cdot)$ は前のグループのビームとの距離（類似度ペナルティ）、$\lambda$ は多様性の強さを制御するハイパーパラメータです。

Minimum Bayes Risk (MBR) デコーディング

ビームサーチの目標「最高確率の系列を見つける」に対して、MBR デコーディングは「期待効用（utility）が最大の系列を見つける」という別の目標を持ちます。

$$ \hat{\bm{y}}_{\text{MBR}} = \arg\max_{\bm{y}} \mathbb{E}_{\bm{y}’ \sim P(\cdot | \bm{x})} [\mathcal{U}(\bm{y}, \bm{y}’)] $$

$\mathcal{U}$ はタスク固有の評価関数（BLEU、BERTScore など）です。実用では複数のサンプルを生成してそれらの間の評価関数スコアを平均します。

最近のLLMのデコーディング研究では、ビームサーチより MBR や best-of-N（多数サンプルから最良を選ぶ）が品質で有利なケースが報告されています。

並列ビームサーチ（バッチ処理）

実際のシステムでは、ビーム内の $B$ 個の候補を 1 つのバッチとして GPU で並列計算します。これにより計算グラフの構成が変わり、効率的に実装できます。Hugging Face transformers ライブラリの generate() メソッドはこのバッチ実装を採用しています。

from transformers import AutoModelForSeq2SeqLM, AutoTokenizer

model_name = "Helsinki-NLP/opus-mt-en-jap"  # 英日翻訳モデル
tokenizer = AutoTokenizer.from_pretrained(model_name)
model = AutoModelForSeq2SeqLM.from_pretrained(model_name)

text = "Beam search finds better translations than greedy decoding."
inputs = tokenizer(text, return_tensors="pt")

# ビームサーチ（デフォルト）
outputs = model.generate(
    **inputs,
    num_beams=5,              # ビーム幅
    length_penalty=0.6,       # 長さ正規化パラメータ α
    repetition_penalty=1.3,   # 繰り返しペナルティ
    max_new_tokens=100,
)
print(tokenizer.decode(outputs[0], skip_special_tokens=True))

# greedy decoding（比較用）
outputs_greedy = model.generate(**inputs, num_beams=1, max_new_tokens=100)
print(tokenizer.decode(outputs_greedy[0], skip_special_tokens=True))

generate() の num_beams=1 が greedy decoding に相当します。num_beams を増やすだけでビームサーチに切り替わります。

まとめ

本記事ではビームサーチと greedy decoding の仕組みを詳しく解説しました。

• greedy decoding: 各ステップで最高確率のトークン 1 個だけを選ぶ。高速だが局所最適に陥りやすく、「greedy が選んだ序盤のトークン」が「良い続き」を閉ざすことがある
• ビームサーチ: 各ステップで上位 $B$ 個の候補を保持して並列探索。スコアは対数尤度の累積和。長さ正規化パラメータ $\alpha$（推奨 0.6〜0.7）で短い系列への偏りを補正
• 繰り返しペナルティ: 既出トークンのスコアを下げることで退化（degeneration）を抑制
• ビーム幅のトレードオフ: $B = 4 \sim 8$ が品質と計算量のバランスが良い実用範囲
• サンプリング vs ビームサーチ: 確定的・高品質なタスク（翻訳・要約）はビームサーチ、多様性が重要なタスク（創作・対話）はサンプリングが向く

言語モデルとパープレキシティを理解する

言語モデルの基礎とパープレキシティによる評価指標を N-gram からニューラル LM まで解説します。