M4-011M4: Sequences & TransformersSeq2Seq & Attention OriginsHard
⚡Flashcard Drill➔Mastery:

Beam Search Decoding and Length Bias Normalization

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M4-012 →
📐 Mathematical Definition
score(y)=∑tlog⁡p(yt∣y<t);normalized=score∣y∣α, α≈0.6–1.0\text{score}(y)=\sum_{t}\log p(y_t|y_{<t});\qquad \text{normalized}=\frac{\text{score}}{|y|^{\alpha}},\ \alpha\approx0.6\text{--}1.0
⚡ One-Sentence Core Answer
Beam search maintains the top-kk most probable sequence hypotheses; because joint log-probability decreases monotonically with length, length normalization is required to prevent favoring short outputs.

📌 Key Takeaways

  • •
    Beam Search: tracks beam width BB hypotheses, expanding B×VB \times V candidates and pruning to top BB by cumulative log-probability
  • •
    Length bias: ∑t=1Tlog⁡P(yt∣y<t)≤0\sum_{t=1}^T \log P(y_t \mid y_{<t}) \le 0; each additional token adds a negative term, unfairly penalizing longer sentences
  • •
    Length normalization: score is divided by length penalty LP(Y)=(5+∣Y∣)α(5+1)α\text{LP}(Y) = \frac{(5 + |Y|)^\alpha}{(5 + 1)^\alpha} (typically α∼0.6−0.8\alpha \sim 0.6-0.8)

📐 Mathematical Derivations

Mathematical Formulation (Wu et al., Google NMT 2016):
Objective: Approximate arg⁡max⁡Ylog⁡P(Y∣X)=arg⁡max⁡Y∑t=1∣Y∣log⁡P(yt∣y<t,X)\arg\max_Y \log P(Y \mid X) = \arg\max_Y \sum_{t=1}^{|Y|} \log P(y_t \mid y_{<t}, X).
- Greedy Search ($B=1$): Takes yt=arg⁡max⁡P(y∣y<t)y_t = \arg\max P(y \mid y_{<t}). Misses globally optimal paths hidden behind low-probability initial tokens.
- Beam Search ($B > 1$): Retains BB active candidates Ht={Y1,…,YB}\mathcal{H}_t = \{Y_1, \dots, Y_B\}. Expands each to vocabulary size VV, ranks B×VB \times V extensions by cumulative score, and retains the top BB.
The Length Bias Defect:
Since P(yt)≤1P(y_t) \le 1, log⁡P(yt)≤0\log P(y_t) \le 0. The cumulative sum ∑t=1Tlog⁡P(yt)\sum_{t=1}^T \log P(y_t) is monotonically decreasing with length TT. Unnormalized beam search heavily favors short or incomplete sentences (e.g., 3-word fragments) over complete 20-word translations.
Google NMT Length Penalty Normalization:
Score(Y)=∑t=1∣Y∣log⁡P(yt∣y<t,X)LP(∣Y∣)\text{Score}(Y) = \frac{\sum_{t=1}^{|Y|} \log P(y_t \mid y_{<t}, X)}{\text{LP}(|Y|)}, where LP(∣Y∣)=(5+∣Y∣)α(5+1)α\text{LP}(|Y|) = \frac{(5 + |Y|)^\alpha}{(5 + 1)^\alpha}.
When α=0\alpha = 0, no normalization. When α=1\alpha = 1, standard average log-probability. Default α=0.6−0.7\alpha = 0.6-0.7 strikes an optimal balance.

🏭 Production Trade-offs

Open-Ended Generation Failure: While Beam Search excels in constrained translation and summarization, it causes repetitive, dull, and generic loops in open-ended creative generation. Modern LLMs use stochastic sampling (Top-pp / Top-kk / Temperature).
⚠️ Common Interview Pitfalls
  • ✕
    Comparing candidate beam sequences of different lengths without length normalization, resulting in premature generation truncation
  • ✕
    Using Beam Search for creative open-ended text generation, producing repetitive degenerate responses
🎯 Interviewer Follow-up Inquiries
  • ?
    Why does Beam Search produce degenerate repetitive loops in open-ended language generation?
  • ?
    How does Top-pp (nucleus) sampling differ fundamentally from Beam Search?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM4-010: Teacher Forcing and Exposure Bias in Autoregressive Sequence Generation📋 Back to BankNext →M4-012: Architectural Paradigms: Encoder-Decoder vs Decoder-Only vs Encoder-Only