ビームサーチデコーディング（ビームサーチデコーディング）

ビームサーチデコーディングとは

ビームサーチ（Beam Search）はダイナミックプログラミングを応用した確率的探索アルゴリズムで、1970年代の音声認識研究に起源を持つ。Seq2Seqモデル（翻訳・要約）の台頭とともにNLPの主流デコーディング手法となり、LLMの時代にも継続して使われている。

アルゴリズムの動作

k=3（ビーム幅）の場合:

• ステップT: ビーム候補A・B・Cを保持
• ステップT+1: 各候補から全語彙（例:32,000トークン）を展開→3x32,000=96,000個の部分シーケンス→スコア順上位3個を新ビームとして保持

スコアは各ステップの対数確率を累積合算して計算する。

グリーディデコーディングとの比較

グリーディデコーディングはk=1のビームサーチと等価で、常に最高確率トークン1個だけを選択する。局所最適を選ぶため全体最適を見逃すことがある。ビームサーチはk>1で複数の仮説を維持することでこの問題を緩和する。

繰り返しと短文バイアス問題

繰り返し（Repetition）: 同一フレーズの繰り返しが高スコアを得やすい。no_repeat_ngram_sizeパラメータで既出n-gramを禁止して緩和。

短文バイアス（Length Bias）: 対数確率の累積は文が長くなるほど減少するため短いシーケンスが有利。length_penalty（αパラメータ）で補正。α>1で長文優遇、α<1で短文優遇。

ダイバースビームサーチ（DBS）

通常のビームサーチでは複数の候補が似たシーケンスに収束する問題がある。DBSはビームをグループに分割し、グループ間の多様性を強制するペナルティを加えることで複数の異なる回答を生成できる。

LLMでの現在の位置づけ

GPT-4等の対話型LLMでは、決定論的なビームサーチよりもニュークリアスサンプリングが主流。翻訳・要約等の単一正解タスクにはビームサーチが向き、対話・創作では多様性のある確率的サンプリングが好まれる。HuggingFace: generate(num_beams=4)。