Minimum Bayes Risk Decoding

Stahlberg and Byrne built an exact decoder for a trained Transformer on WMT15 English-German, one that provably finds the highest-scoring output rather than approximating it with a beam. For more than 50% of the sentences, the model assigned its global best score to the empty translation (Stahlberg & Byrne, EMNLP 2019, arXiv:1908.10090). Beam search never finds that optimum, which is the only reason the system works at all.

That result reframes the decoding problem. If the mode of the distribution is degenerate, then better search makes output worse, and every improvement attributed to a smarter beam is an improvement in failing to find what the model actually prefers. The obvious response is to stop looking for the mode.

The decision rule

MBR comes from statistical decision theory and predates neural sequence models by decades. Fix a utility function \(u(h, y)\) measuring how good hypothesis \(h\) is if \(y\) turns out to be the true output. Choose the hypothesis with the highest expected utility under the model's own distribution:

The expectation is intractable, so approximate it by sampling. Draw \(N\) sequences from the model as pseudo-references, and score each candidate against them:

In the common form the candidate pool is the sample set itself, so the procedure reduces to: sample \(N\) outputs, compute the pairwise utility matrix, and return the sample most similar to all the others. Nothing about the model changes. The change is entirely in which output you keep.

The interpretation is worth stating plainly. Beam search asks which single string the model considers most likely. MBR asks which string is most representative of what the model believes, measured by a similarity metric you choose. Eikema and Aziz showed this approximation has no equivalent of the beam search curse: quality does not degrade as the hypothesis space grows, which is exactly the pathology that makes beam sizes above about five harmful (Eikema & Aziz, EMNLP 2022, arXiv:2108.04718).

The utility function is the whole design

MBR with a surface metric such as BLEU gives modest gains. MBR with a learned neural metric changes the picture: Freitag and colleagues used BLEURT as the utility and reported significant improvement in human evaluation, while noting that the chosen translations had lower model likelihood than beam output and scored worse on BLEU (Freitag et al., TACL 2022, arXiv:2111.09388).

That is the clearest available demonstration that model probability and output quality are different quantities, and that a decoder is free to optimise the second directly.

The framing generalises. Self-consistency voting over chain-of-thought answers is MBR with an exact-match utility on the final answer. Best-of-N reranking with a reward model is MBR where the utility ignores the other samples entirely. Bertsch and colleagues work through this correspondence for a family of modern techniques and argue the connection explains empirical results previously reported as unrelated tricks (Bertsch et al., 2023, It is MBR All the Way Down, arXiv:2310.01387).

When it breaks

Quadratic cost. The naive estimator needs \(N^2\) utility evaluations. At \(N = 100\) that is 9,900 metric calls per input, and if the metric is a neural model each call is a forward pass. Confidence-based pruning and hyperparameter-free approximations reduce this substantially (Jinnai & Ariu, 2024, arXiv:2401.02749), but MBR is never cheap relative to a single greedy pass. It buys quality with inference compute.

No streaming. The output cannot be emitted until all \(N\) samples exist and the matrix is scored. For an interactive product with a time-to-first-token budget, MBR is disqualified regardless of quality.

Goodhart on the utility. Selecting from \(N\) samples by a learned metric is an optimisation against that metric, and larger \(N\) searches harder for its blind spots. Measured utility rises while true quality can fall. The effect is the same one that limits best-of-N against a reward model.

Outputs must be comparable. The utility needs to compare two full outputs meaningfully. For translation, summarisation, and captioning that works. For open-ended creative generation, "most similar to the other samples" selects for blandness, because the consensus of a diverse sample set is its least distinctive member.

Sample diversity is the hidden dependency. MBR estimates an expectation, so it needs unbiased samples from the model. Ancestral sampling at temperature 1.0 is the theoretically correct source; truncated sampling biases the estimator. Practitioners routinely use nucleus samples anyway, which works but is no longer the estimator the theory describes.