DataTerminology.comNEW
A heuristic search that expands the top-scoring partial sequences at each step, retaining a fixed number of candidates.
DESCRIPTION
Beam search approximates exhaustive search by keeping only the best B hypotheses (beam width) at each time step. It is widely used for decoding in sequence generation tasks like translation and speech recognition. Length normalization and coverage penalties mitigate length bias. While deterministic and efficient, it may miss globally optimal sequences and can reduce diversity. Sampling-based decoders offer diversity at the cost of stability.
ALTERNATIVE DEFINITIONS
Wikipedia
Beam search is a heuristic search algorithm that explores a graph by expanding the most promising nodes in a limited set.
General definition emphasizing limited-width exploration.
Stanford CS224N
Beam search keeps the top k hypotheses at each time step and expands them, pruning the rest to maintain tractable decoding.
Highlights the k-best pruning used in NLP decoding.
RELATED TERMS
Viterbi Algorithm A-star Search Best-First Search Top-k Sampling Sequence Decoding Length Normalization Language Model Hypothesis Pruning
COMPETING TERMS
Greedy Decoding Nucleus Sampling
RELATIONS
- Broader: Best-First Search Search
KNOWLEDGE AREAS
TARGET AUDIENCE
AI Engineer Data Scientist MLOps Engineer Software Developer
EXTERNAL SOURCES
- Wikipedia - Beam search
- CS224N - Lecture notes on decoding
- Jurafsky & Martin - Textbook chapter including beam search
TOP QUESTIONS
Why use Beam Search for sequence generation?
It balances quality and efficiency by exploring multiple top candidates without the cost of exhaustive search.
Category: Relevancy
How does beam width affect Beam Search results?
Larger beams improve quality but increase computation and may reduce diversity; small beams are faster but risk suboptimal outputs.
Category: Requirements
Why apply length normalization in Beam Search?
To counteract the bias toward shorter sequences arising from product of probabilities during decoding.
Category: BestPractice
What is a common mistake with Beam Search?
Using a large beam without penalties can produce repetitive or overly short outputs, harming quality.
Category: Mistakes
What alternatives to Beam Search encourage diversity?
Top-k or nucleus sampling inject controlled randomness, trading determinism for diversity.
Category: Alternatives
Is Beam Search guaranteed to find the optimal sequence?
No. It’s a heuristic that may prune globally optimal paths early.
Category: Misunderstanding
How to speed up Beam Search?
Use vectorized decoding, cache attention states, and prune aggressively with scores and constraints.
Category: HowTo
When is Beam Search preferable to greedy decoding?
When single-step greedy choices often lead to poor global sequences, typical in translation and summarization.
Category: Opinion
Can Beam Search be combined with constraints?
Yes, constrained decoding enforces required tokens or structures during hypothesis expansion.
Category: Topic