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
📐 Mathematical Definition
⚡ One-Sentence Core Answer
Beam search maintains the top- 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 hypotheses, expanding candidates and pruning to top by cumulative log-probability
- •Length bias: ; each additional token adds a negative term, unfairly penalizing longer sentences
- •Length normalization: score is divided by length penalty (typically )
📐 Mathematical Derivations
Mathematical Formulation (Wu et al., Google NMT 2016):
Objective: Approximate .
- Greedy Search ($B=1$): Takes . Misses globally optimal paths hidden behind low-probability initial tokens.
- Beam Search ($B > 1$): Retains active candidates . Expands each to vocabulary size , ranks extensions by cumulative score, and retains the top .
The Length Bias Defect:
Since , . The cumulative sum is monotonically decreasing with length . Unnormalized beam search heavily favors short or incomplete sentences (e.g., 3-word fragments) over complete 20-word translations.
Google NMT Length Penalty Normalization:
, where .
When , no normalization. When , standard average log-probability. Default strikes an optimal balance.
Objective: Approximate .
- Greedy Search ($B=1$): Takes . Misses globally optimal paths hidden behind low-probability initial tokens.
- Beam Search ($B > 1$): Retains active candidates . Expands each to vocabulary size , ranks extensions by cumulative score, and retains the top .
The Length Bias Defect:
Since , . The cumulative sum is monotonically decreasing with length . Unnormalized beam search heavily favors short or incomplete sentences (e.g., 3-word fragments) over complete 20-word translations.
Google NMT Length Penalty Normalization:
, where .
When , no normalization. When , standard average log-probability. Default 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- / Top- / 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- (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.
📚