Linear-time Minimum Bayes Risk Decoding with Reference Aggregation

Minimum Bayes Risk (MBR) decoding is a text generation technique that has been shown to improve the quality of machine translations, but is expensive, even if a sampling-based approximation is used.Besides requiring a large number of sampled sequences, it requires the pairwise calculation of a utility metric, which has quadratic complexity.In this paper, we propose to approximate pairwise metric scores with scores calculated against aggregated reference representations.This changes the complexity of utility estimation from O(n 2 ) to O(n), while empirically preserving most of the quality gains of MBR decoding.We release our source code. 1