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 samplingbased 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.
