Beam Search › Beam Width: The Quality-Compute Tradeoff

The beam width $k$ is the central hyperparameter of beam search. It controls a direct tradeoff between the quality of the search and the computational cost.

With $k = 1$, beam search reduces exactly to greedy decoding. With $k = |V|^T$, it becomes exhaustive search. In practice, values between 4 and 10 are common for machine translation; some summarization models use 4, and neural machine translation systems often use 5 or 6.

Increasing beam width has diminishing returns in practice. The gain from going from $k = 1$ to $k = 4$ is typically much larger than from $k = 4$ to $k = 10$. Beyond a certain width, the model has already found most of the high-probability paths, and adding more beams just increases computation without improving output quality.

More surprisingly, very large beam widths can degrade output quality on some tasks. Researchers have found that in neural machine translation, BLEU scores sometimes peak around $k = 4$ to $k = 8$ and then decline for larger beams. The reason is related to the model's training distribution: a model trained with maximum likelihood estimation (MLE) learns to assign high probability to sequences that start similarly to the training data. When the beam is large enough to explore low-probability starts, the model encounters territory far from its training distribution, and the output quality degrades. This phenomenon is sometimes called the "beam search curse".

The beam search curse reveals a deep tension in how neural sequence models are trained and how they are evaluated. During training, the model's objective is to assign high probability to the correct next token given the ground-truth prefix. This is a local, next-step objective. At test time, beam search tries to find the globally most probable sequence, which is a different objective. The model was not trained to optimize global sequence probability; it was trained to optimize step-wise conditional probabilities. For well-distributed training data, these two objectives are roughly aligned. But at the edges of the distribution, they diverge, and beam search with a very wide beam will faithfully optimize the wrong objective.

A related concern is that for certain models, specifically language models trained on extremely large corpora, even greedy decoding may produce excellent outputs because the model has learned such a well-calibrated distribution over text. For these models, beam search still helps but the margin over greedy is smaller than for older, weaker models.

Each step of beam search requires $k$ decoder forward passes (one per hypothesis in the beam). With a vocabulary of size $|V|$, you compute $k \times |V|$ scores at each step, then sort to find the top $k$. The total computation is $O(k \cdot T \cdot d)$ where $d$ is the cost of a single decoder forward pass. In practice, the $k$ forward passes are batched together, so the overhead relative to greedy is roughly $k \times$ the cost per step.

The memory overhead is also non-trivial. Each beam hypothesis maintains its own key-value cache (in transformer models, this stores the attention key and value tensors for all previous tokens). With $k$ hypotheses, you hold $k$ separate KV caches simultaneously. For long sequences and large models, this can dominate memory usage. Some systems reduce this overhead by sharing computation across hypotheses when they share a common prefix, a technique called hypothesis sharing or tree-structured KV caching.