Beam Search › Beam Search for Machine Translation

Machine translation is the canonical application of beam search. The encoder reads the source sentence and produces hidden states. The decoder generates the translation token by token, and beam search determines which partial translations to keep exploring. The combination of a strong encoder-decoder model and beam search was the backbone of Google Translate, Microsoft Translator, and virtually every production neural MT system from 2016 onward.

In practice, the beam search procedure is tightly integrated with the encoder-decoder architecture.

At inference time, the encoder runs once to produce the source representations. These are then queried by the decoder's attention mechanism (which we will explore in depth in the Attention Intuition chapter) at every step for every beam hypothesis. Since all beam hypotheses share the same source representation, the encoder computation is not repeated. Only the decoder must be run repeatedly.

The decoder, however, must run $k$ times per step (once per beam hypothesis), or equivalently, the decoder is batched with a batch size of $k$. Each batch element corresponds to a different beam hypothesis. The $k \times |V|$ score matrix is computed in one batched forward pass, exploiting GPU parallelism to keep the overhead manageable.

At the end, the beam contains up to $k$ completed translations (or partial translations if the maximum length was reached). After applying length normalization, the highest-scoring translation is returned as the system output. Some systems also return the top-N translations (n-best list) for downstream reranking: a separate reranker model can score the n-best candidates using additional features (e.g., a language model score, a roundtrip translation score) and select the best one.

The importance of beam search to machine translation is hard to overstate. The first widely deployed neural MT systems achieved competitive quality in part because beam search found translations that greedy decoding missed. The gap between greedy and beam search output quality was large enough that early practitioners considered beam width a first-class hyperparameter alongside learning rate and model size.

Beam width has a measurable impact on BLEU scores in machine translation. The relationship is roughly: wider beams improve BLEU up to a point, then plateau or slightly decline. For English-German translation with a strong transformer model, going from $k = 1$ (greedy) to $k = 4$ typically improves BLEU by 1-2 points. Going from $k = 4$ to $k = 10$ may add another 0.2-0.5 BLEU. The marginal gain diminishes rapidly.

BLEU is a reference-based metric that compares the model's output to human-written reference translations. The fact that beam search improves BLEU does not mean it produces the "best" translation in some objective sense; it means it produces translations more similar to human references. For tasks where the reference distribution is highly multimodal (many equally valid outputs), BLEU may not fully capture quality differences between decoding strategies, and human evaluation often shows a different picture than automatic metrics.

Beam search extends naturally to other seq2seq tasks, though the optimal hyperparameter settings vary. For abstractive summarization, models like BART and PEGASUS typically use beam widths of 4 to 8, with no-repeat-ngram-size set to 3 to prevent repetitive phrases. The length penalty is often set lower than in translation, because summaries should be concise and the model may need less encouragement to generate longer outputs.

For image captioning, beam search with width 3 to 5 is standard. The encoder here is a visual feature extractor (a convolutional network or a vision transformer) rather than a text encoder, but the decoder runs identically to the text case. Beam search ensures that the caption is coherent and grammatically complete rather than trailing off after the first few high-probability words.

For question answering with extractive or generative models, the situation differs. Extractive QA systems that select spans from a passage do not need beam search. Generative QA systems do, but the beam is often narrow (width 2 to 4) because the answer space is more constrained and the model is typically more confident.