Linear-time Minimum B ayes Risk Decoding with Reference Aggregation (2024)

Abstract: 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.

## introduction the idea of generating translations by maximizing a metric of translation quality @xcite has recently been revived in the context of neural machine translation. in sampling-based mbr decoding (eikema and aziz, 2020), many hypotheses are sampled from the model distribution, and their expected utility is estimated using monte carlo (mc) sampling. this approach has been shown to improve translation quality compared to beam search, especially when neural metrics are used for utility estimation @xcite . estimating utility through mc sampling has quadratic complexity in the number of samples, which limits practical application. previous work suggested pruning the number of samples based on a cheaper metric or a smaller number of references @xcite . in this paper, we propose reference aggregation, an alternative efficiency technique that exploits the fact that most common metrics represent text sequences in averageable form, e.g., as n-gram statistics or as embeddings. specifically, we combine representations of the references into an aggregate reference representation, which we then use for utility estimation. our proposed approximation still relies on mc sampling, but on a lower level: rather than computing an mc estimate of the expected utility, we compute an mc estimate of the "true" reference representation in the feature space of the given utility metric. since this estimate only needs to be computed once, our approach has linear complexity in the number of sampled hypotheses and references. we report empirical results for four translation directions and two utility metrics: chrf @xcite , which is based on character n-gram overlap, and comet @xcite , a neural network trained with examples of human translation quality judgments. for chrf, we find that reference aggregation reduces the time needed for computing the utility of 1024 samples by 99.5%, without affecting translation quality. for comet, metric accuracy does decrease with aggregation, but to a lesser extent than with simply reducing the number of references. depending on the comet model, computation time is reduced by 95-99%, which makes reference aggregation an efficient method for hypothesis pruning with comet. ## background and related work sampling-based mbr (eikema and aziz, 2020) selects a translation hyp * out of a set of translation hypotheses hyp 1 , . . . , hyp @xmath0: the set of hypotheses is sampled from the model distribution p(hyp|src). eikema and aziz (2020) propose to approximate the utility using mc sampling: sample a set of pseudo-references @xmath1, . . . , ref m } ∼ p(ref|src) from the model and calculate a metric against each sampled reference: utility(hyp) ≈ 1 m @xmath2, ref). (2) for machine translation, typical such metrics are chrf @xcite and bleu @xcite , which are based on n-gram statistics, or neural metrics such as comet @xcite and bleurt @xcite . a line of research has focused on improving the efficiency of sampling-based mbr. eikema and aziz (2022) propose coarse-to-fine mbr, which prunes the hypotheses based on a cheaper metric, and n-by-s mbr, which uses fewer references than hypotheses. cheng and vlachos (2023) propose confidence-based pruning, where the number of hypotheses is iteratively reduced based on an increasing number of references. @xcite interpret sampling-based mbr as an instance of medoid identification and apply an established approximation algorithm to this problem. a line of work uses mbr outputs as a training reward, avoiding the inefficiency of mbr during deployment @xcite . finally, alternative reranking approaches that do not require pairwise comparisons have been proposed @xcite . several other works investigate the aggregation of reference representations to develop a faster variant of mbr decoding. @xcite perform reference aggregation in the context of statistical machine translation (smt). since smt does not afford random sampling of pseudo-references, they aggregate references from translation forests or k-best lists. our study shows the effectiveness of reference aggregation from sampled pseudoreferences, and for neural metrics such as comet. furthermore, concurrent to our work, @xcite propose to aggregate the sentence embeddings of comet, and use k-means to group the references into multiple clusters. ## reference aggregation our approach is based on the observation that most metrics that are commonly used for mbr make use of feature representations that can be aggregated. for example, the n-gram statistics used by chrf can be aggregated by averaging the counts of the n-grams across all references; and the sentence embeddings used by comet can be aggregated by calculating an average sentence embedding. for simplicity, we re-use the above notation, where hyp is a hypothesis and ref is a reference, but we now assume that they are represented in an averageable form. we then combine the set of references refs into an aggregate representation ref: we approximate the expected the utility of a sampled hypothesis by calculating a single metric score against this aggregate representation: like with standard sampling-based mbr, it is possible to interpret this approximation as mc sampling: by averaging over representations of sampled references, we estimate a representation of the "true" reference, which we then use for approximating the expected utility of each sampled hypothesis. importantly, the computational complexity of our approach is in o(|hyps| + |refs|) rather than o(|hyps| • |refs|); see appendix d for a discussion. ## experimental setup data we use newstest21 @xcite as validation data and newstest22 @xcite as test data. ## conclusion we proposed reference aggregation, a technique that boosts the efficiency of mbr decoding by shifting the mc sampling from the utility estimation to the reference representation. experiments on machine translation showed that reference aggregation speeds up utility estimation by up to 99.5% while minimally affecting translation quality. this reduces the gap to beam search and makes mbr more practical for large-scale applications.