Beam Search & Decoding Strategies

Greedy vs Beam Search

  GREEDY SEARCH (Myopic local choice):
  Step 1: Pick "The" (P=0.9) ──► Step 2: "cat" (P=0.1) ──► Total Joint Log Prob = -2.4 (Poor!)

  BEAM SEARCH (Beam Width B = 2):
  Path A: "The" (P=0.9)  ──► "cat" (P=0.1)  ──► Joint Log Prob = -2.4
  Path B: "A"   (P=0.4)  ──► "swift" (P=0.8) ──► "fox" (P=0.9) ──► Joint Log Prob = -0.5 (WINNER!)

Greedy search picked "The" because $0.9 > 0.4$, but was trapped in a bad continuation. Beam Search kept "A" alive in Path B, discovering a higher joint probability sequence!

Beam Search Algorithm Steps

Given Beam Width $B = 3$:

1. Initialize: Beam = { ( [EOS], log_prob = 0.0 ) }
2. For step t = 1 ... Max_Length:
   a. Expand each of the B candidate paths against all |V| vocabulary tokens (B × |V| candidates).
   b. Score candidate path: Score(x_{1..t}) = Score(x_{1..t-1}) + ln P(x_t | x_{1..t-1})
   c. Retain top B candidates with highest cumulative score.
   d. Move completed sequences (ending in [EOS]) to Final Candidates set.
3. Apply Length Normalization to Final Candidates and output highest scoring sequence.

Length Normalization Formula

Un-normalized log likelihoods naturally decay with length $L$:

$$\text{Score}{\text{unnorm}}(X) = \sum{t=1}^L \ln P(x_t \mid x_{<t}) < 0$$

Length-normalized score using penalty exponent $\alpha \in [0.5, 1.0]$:

$$\text{Score}{\text{norm}}(X) = \frac{1}{L^\alpha} \sum{t=1}^L \ln P(x_t \mid x_{<t})$$

Dividing by $L^\alpha$ prevents the search algorithm from always selecting short 2-word sentences over complete 15-word translations.

Say this out loud

"Beam Search maintains B parallel sequence hypotheses (Beam Width B) to find global high-probability output sequences. Unlike myopic Greedy Decoding, Beam Search tracks top cumulative log-probability paths at each step. We use length normalization Score / L^α to prevent negative log-probabilities from penalizing longer, more complete output sequences."

Follow-ups to expect

• Why is Beam Search rarely used for open-ended LLM chat? Beam Search tends to produce repetitive, generic, and unnatural text in open-ended chat generation. Stochastic sampling (Temperature + Top-p) produces far more natural and creative conversational output.
• When IS Beam Search still used? Machine translation, speech-to-text (Whisper), image captioning, and code syntax generation, where exact structural accuracy and deterministic translation fidelity are paramount.