Beam Search

Beam Search (빔 서치)

시퀀스 생성(디코딩)에서 매 스텝마다 확률이 높은 상위 $k$개의 후보(beam)만 남겨 가며 문장을 만들어 가는 휴리스틱 탐색 기법.
매 스텝 1등만 고르는 greedy는 근시안적이고, 모든 경로를 보는 exhaustive 탐색은 불가능하다. Beam search는 그 중간 절충으로, Seq2Seq·기계번역·LM 디코딩의 표준 방법.

beam-search decoding seq2seq search

왜 필요한가

• 길이 $T$, 어휘 크기 $V$인 시퀀스의 가능한 경우의 수는 $V^T$ → 전체를 다 보는 것은 불가능.
• 우리가 원하는 것은 전체 시퀀스 확률을 최대화하는 문장:

$$\hat{y}=\arg \underset{y}{\max }\prod _{t=1}^{T}P(y_t\mid y_{<t},x)=\arg \underset{y}{\max }\sum _{t=1}^T\log P(y_t\mid y_{<t},x)$$

• 매 스텝 가장 높은 토큰만 고르는 greedy는 이 곱(합)을 최적화한다는 보장이 없다. 지금 2등이지만 이어지는 확률이 훨씬 높은 경로를 놓칠 수 있기 때문.
• Beam search는 여러 가설을 동시에 살려 두어 이 근시안 문제를 완화한다.

동작 방식

beam width(빔 폭) $k$: 매 스텝 유지할 후보 시퀀스(가설)의 개수.

1. 시작 토큰 <sos>에서 출발, 다음 토큰의 확률 상위 $k$개를 beam으로 둔다.
2. 각 스텝마다 현재 $k$개 가설 각각을 어휘 $V$개로 확장 → 총 $k\times V$개 후보.
3. 이 $k\times V$개를 누적 log 확률(아래 점수)로 정렬해 상위 $k$개만 남긴다.
4. 가설이 <eos>에 도달하면 완성 목록에 따로 보관하고, beam은 계속 진행.
5. 모든 beam이 끝나거나 최대 길이 도달 시 종료 → 완성된 가설 중 점수 최고를 출력.

beam width k=2
            ┌ "the"  (-0.2) ──┬ "the cat" (-0.5) ✔ 유지
  <sos> ────┤                 └ "the dog" (-0.9)   탈락
            └ "a"    (-0.7) ──┬ "a cat"   (-0.6) ✔ 유지
                              └ "a dog"   (-1.4)   탈락
            → 매 스텝 k×V 후보 중 상위 k개만 살아남음

• $k=1$이면 정확히 greedy search와 같다.
• $k\to V^T$이면 exhaustive(완전 탐색)에 수렴하지만 비현실적.
• 보통 번역은 $k=4\sim 10$ 정도를 쓴다.

점수 정규화 (length normalization)

누적 log 확률은 토큰을 더할수록 항상 음수가 커진다(확률 < 1 → log < 0). 그래서 짧은 문장이 무조건 유리해지는 편향이 생긴다.

이를 보정하려고 길이로 나눈 점수를 쓴다:

$$\text{score}(y)=\frac{1}{|y{|}^{\alpha }}\sum _{t=1}^{|y|}\log P(y_t\mid y_{<t},x)$$

• $\alpha \in [0,1]$ : length penalty 강도($\alpha =0$이면 정규화 없음, 보통 $0.6\sim 0.7$).
• 일부 구현은 coverage penalty(입력을 골고루 참조했는지)도 추가.

Greedy Search와의 비교

	Greedy ($k=1$)	Beam Search ($k>1$)	Exhaustive
매 스텝 후보	1등만	상위 $k$개	전부
계산량	$O(VT)$	$O(kVT)$	$O(V^T)$
품질	근시안적	균형	최적(불가능)
최적해 보장	✗	✗ (휴리스틱)	✓

Beam search도 최적해를 보장하지 않는다

매 스텝 상위 $k$개만 남기므로, 초반에 점수가 낮지만 나중에 역전할 경로를 잘라 버릴 수 있다. 어디까지나 품질↔연산량 절충의 휴리스틱.

한계와 trade-off

• beam을 키운다고 항상 좋아지지 않음: 번역에서 $k$를 너무 키우면 오히려 짧고 일반적인(밋밋한) 문장으로 퇴화하는 beam search degradation이 알려져 있다(모델이 짧은 시퀀스에 과한 확률을 줄 때).
• 다양성 부족: 살아남은 $k$개 가설이 서로 거의 똑같은(한 토큰만 다른) 경우가 많다. → Diverse Beam Search로 그룹 간 다양성 패널티를 줘 완화.
• 결정론적: 같은 입력엔 항상 같은 출력. 창의적·개방형 생성에는 부적합 → 이럴 땐 sampling 계열을 쓴다.

샘플링 기반 디코딩과의 관계

Beam search는 **확률을 최대화(MAP-ish)**하는 방향이라, 번역·요약처럼 “정답에 가까운” 출력엔 강하지만 대화·스토리 생성처럼 다양성이 중요한 작업엔 단조롭다. 이때는 확률 분포에서 뽑는 방식이 낫다:

• Temperature sampling: Softmax 온도 $T$로 분포를 평평/뾰족하게.
• Top-k / Top-p(nucleus) sampling: 상위 확률 토큰들로 후보를 제한한 뒤 샘플링.

즉 디코딩 전략은 maximization(beam/greedy) ↔ sampling의 스펙트럼으로 이해하면 좋다.

Related

• Seq2Seq — beam search가 가장 먼저 표준이 된 인코더-디코더 디코딩.
• Language Modeling, Perplexity — 토큰 확률의 곱을 최적화한다는 같은 관점.
• Softmax — 매 스텝 토큰 분포를 만드는 출력층.
• BLEU — 디코딩 품질(특히 번역) 평가 지표.
• Monte Carlo Tree Search(MCTS) — 같은 “탐색” 가족이지만, beam은 폭 우선·결정론적인 반면 MCTS는 시뮬레이션 기반.