Beam Search › Diverse Beam Search

Standard beam search tends to produce hypotheses that are very similar to each other. When the model is confident about the first few tokens, all $k$ beam hypotheses will start with the same token, diverging only in later positions. The beam is homogeneous rather than diverse.

This is a problem in applications that need multiple distinct outputs, such as generating several translation candidates for a human post-editor to choose from, or generating multiple image captions and selecting the best one. When a human reviewer receives five near-identical outputs, the "top-k best" functionality provides little benefit. What is needed is outputs that represent clearly different ways of completing the task.

Diverse beam search (Vijayakumar et al., 2018) addresses this by partitioning the $k$ beams into $G$ groups, each of size $k/G$. Within each group, standard beam search runs. Between groups, a diversity penalty discourages groups from producing similar tokens.

At each step $t$, for group $g$, the score for token $w$ is:

$$\text{score}_{g}(w) = \log P(w \mid \cdot) - \lambda \cdot \mathcal{D}(w, \mathcal{B}_{1:g-1})$$

where:

• $\log P(w \mid \cdot)$: the model's log-probability for token $w$
• $\lambda$: the diversity strength hyperparameter
• $\mathcal{D}(w, \mathcal{B}_{1:g-1})$: a diversity penalty measuring how many hypotheses in earlier groups already chose token $w$ at this step

The penalty encourages each group to select tokens that prior groups have not chosen, spreading the search across different parts of the output space. The first group runs without penalty. The second group is penalized for tokens chosen by the first group. The third group is penalized for tokens chosen by the first two, and so on.

With $\lambda = 0$, diverse beam search reduces to standard beam search. Larger values of $\lambda$ force more diversity but may reduce the individual quality of each output.

The grouping mechanism has an intuitive interpretation. Think of each group as a different "opinion" about how the sequence should start. Group 1 follows the most probable path. Group 2 is forced to explore a different starting direction. Group 3 explores a third direction. By the end of decoding, you have $G$ distinct hypotheses, one from each group, that cover a broader range of the output space than $k$ hypotheses from standard beam search.

Another approach to diversity is stochastic beam search, which introduces randomness into the candidate selection step. Instead of deterministically keeping the top $k$ candidates, stochastic beam search samples the $k$ survivors according to their scores, using a Gumbel noise perturbation. Concretely, it adds i.i.d. Gumbel noise $g_i \sim \text{Gumbel}(0, 1)$ to each candidate score before selecting the top $k$:

$$\tilde{s}_i = s_i + g_i$$

This corresponds to sampling without replacement from the categorical distribution defined by the candidates' scores. The result is a diverse set of hypotheses while still being biased toward high-scoring candidates. Stochastic beam search interpolates between deterministic beam search (no noise) and pure sampling (infinite noise).