  Minimum Bayes risk (MBR) decoding outputs the hypothesis with the highest
expected utility over the model distribution for some utility function. It has
been shown to improve accuracy over beam search in conditional language
generation problems and especially neural machine translation, in both human
and automatic evaluations. However, the standard sampling-based algorithm for
MBR is substantially more computationally expensive than beam search, requiring
a large number of samples as well as a quadratic number of calls to the utility
function, limiting its applicability. We describe an algorithm for MBR which
gradually grows the number of samples used to estimate the utility while
pruning hypotheses that are unlikely to have the highest utility according to
confidence estimates obtained with bootstrap sampling. Our method requires
fewer samples and drastically reduces the number of calls to the utility
function compared to standard MBR while being statistically indistinguishable
in terms of accuracy. We demonstrate the effectiveness of our approach in
experiments on three language pairs, using chrF++ and COMET as
utility/evaluation metrics.
