Beam search is a decoding strategy used by language models to build a sequence of text. Rather than blindly picking the single most likely word at each step (as greedy search does), it keeps track of a small number of competing paths — like an explorer who follows several promising trails at once before deciding which truly leads to the summit.
How it works
At each generation step, the model retains the k most probable partial sequences, where k is the beam width. For each, it evaluates possible continuations, computes their cumulative scores, and keeps only the k best across all combinations. A sequence's score is its cumulative log-probability:
$$\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log P(y_i \mid y_{1:i-1}, x)$$
The logarithm prevents the product of many probabilities (all below 1) from collapsing toward zero.
Comparing strategies
| Strategy | Paths explored | Quality | Cost |
|---|---|---|---|
| Greedy search | 1 | Variable | Low |
| Beam search | k (e.g. 4–10) | Often better | Moderate |
| Sampling | 1 (random) | Creative, diverse | Low |
Strengths and limits
- Strengths: yields more coherent text for machine translation, summarization, and image captioning.
- Limits: tends to favor short, repetitive phrasing, lacks diversity, and costs more than greedy decoding.
In short, beam search trades extra computation for better global coherence — a balance between exploration and exploitation.