Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms
Authors: Firas Trabelsi
David Vilar
Mara Finkelstein
Markus Freitag
Venue: NeurIPS 2024 poster (2024)
Keywords: Machine Translation
Minimum Bayes Risk
Natural Language Processing
Low-Rank Matrix Completion
Primary area: natural_language_processing

Abstract: Minimum Bayes Risk (MBR) decoding is a powerful decoding strategy widely used for text generation tasks but its quadratic computational complexity limits its practical application. This paper presents a novel approach for approximating MBR decoding using matrix completion techniques, focusing on a machine translation task. We formulate MBR decoding as a matrix completion problem, where the utility metric scores between candidate hypotheses and reference translations form a low-rank matrix. First we empirically show that the scores matrices indeed have a low-rank structure. Then we exploit this by only computing a random subset of the scores and efficiently recover the missing entries in the matrix by applying the Alternating Least Squares (ALS) algorithm, thereby enabling fast approximation of the MBR decoding process. Our experimental results on machine translation tasks demonstrate that the proposed method requires 1/16 utility metric computations compared to the vanilla MBR decoding while achieving equal translation quality measured by COMET on the WMT22 dataset (en<>de, en<>ru). We also benchmark our method against other approximation methods and we show significant gains in quality.

Efficient Minimum Bayes Risk Decoding using
Low-Rank Matrix Completion Algorithms
Firas Trabelsi Google
David Vilar Google vilar@google.com com
Mara Finkelstein
Google marafin@google..cm
firast@google.com
Markus Freitag
Google freitagggoogle.com com
Abstract
Minimum Bayes Risk (MBR) decoding powerful decoding strategy widely used for text generation tasks, but its quadratic computational complexity limits its practical application. This paper presents a novel approach for approximating MBR decoding using matrix completion techniques, focusing on the task of ma- chine translation. We formulate MBR decoding as a matrix completion problem, where the utility metric scores between candidate hypotheses and pseudo-reference translations form a low-rank matrix. First, we empirically show that the scores ma- trices indeed have low-rank structure. Then, we exploit this by only computing random subset the scores and efficiently recover the missing entries in the matrix by applying the Alternating Least Squares (ALS) algorithm, thereby enabling fast approximation
MBR decoding process. Our experimental results on machine translation tasks demonstrate that the proposed method requires 1/16 utility metric computations compared to vanilla MBR decoding while achieving equal translation quality measured by COMET22 the WMT22 dataset (en <>de, <+ru). We also benchmark our method against other approximation methods and we show gains in quality when comparing to them.
Introduction
The generation process in most conditional natural language processing tasks is usually guided by the maximum-ae a-ootuur--- (MAP) rule: given an input æ. generate the output ý that maximizes the posterior probability distribution: is optimal under a 0-1 loss criterion. However for more nuanced tasks, where different outputs be considered correct, and the quality of the output is not just binary decision between "right" and "wrong". MAP decoding is no longer optimal. Neural Machine Translation (NMT) is prominent example of these types of tasks. For NMT, system is trained to generate sentence in target language given a source sentence in another language. For given sentence, there exists variety of possible translations, each of which has different quality level. Eikema and Aziz (2020) demonstrated that MAP decoding methods are suboptimal for NMT, and showed that other generation strategies may be preferred. Furthermore, NMT models often assign human translations lower probabilities than their own beam search outputs, due to model calibration issues (Ott et al., 2018; Freitag al., 2020).
argmax, p(ylz). It can be shown that MAP decoding
As an alternative, Eikema and Aziz (2020, 2022) applied MBR decoding for NMT models. MBR decoding follows two-step approach, where model is used to generate list of candidate translations and a list of pseudo-references (which may be the same as the list of candidates). The candidates
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Pseudo-references
(2 worlds
kl. everone
(2) worldl
N. everyemel
<3
nello worter
hJ. Haltn mardy
0.85
0.70
0.82
0.85
0.70
0.79
Labels
Hypotheses H
12 1en. world
May. world!
0.81
0.80
0.81
0.80
0.65
+
0.75
Untrows Salue
Approdmaned
Wakes
Ad Halol
0.72
0.90
ta Nattel
0.72
0.70
0.90
*
0.77
MC: Natio
Figure PMBR decoding only requires a subset of the utility computations approximate the output of MBR decoding. The method approximates the unknown values by running matrix completion algorithm which exploits the low-rank nature of the MBR matrix. Once the full matrix is recovered, the method behaves similar to the vanilla MBR decoding method where the hypothesis with the highest average score is selected.
then scored with performance metric using the pscudo-reference true references, and the candidate with the maximum expected quality (or equivalently minimum risk) is then selected. In contrast to MAP decoding, MBR decoding is not designed generate the translation with the highest estimated model probability; instead aims to directly optimize a utility function. Subsequent research conducted by Freitag al. (2022a) showed that MBR decoding with neural utility metrics leads to significant improvements over beam search decoding. However, MBR computationally expensive, with time complexity of ( for candidate list containing N samples and N pseudo-references (usually the two lists coincide). According to Freitag et al. (2022a), ideally N ranges between 100 and 000, which involves thousands millions utility function computations. Note than when using neural metrics, each of the ((N2) "computation steps" is itself expensive, requiring a forward pass through large neural network.
approximation of the
In this work, we propose to reduce the number metric computations by scoring only a subset of candidate pseudo-referenee reference pairs. We then proceed to our case) to estimate the remaining utility scores. For such completion algorithms to work, the full conditions, specifically to be low-rank matrix. We empirically show that
matrix completion algorithm (ALS in
matrix has to fulfill this is indeed the case for the utility matrices for MBR decoding. Intuitively, this makes sense: akin to recommendation systems, where similar users expected have similar book movie preferences, similar pseudo-references are expected to have similar "translation preferences" Experimental results show the effectiveness of our method, where the performance of the full MBR algorithm can be matched with only a fraction of the computational cost. Compared to other approaches that also seek reduce the number of computations, our method does not compromise translation quality, as confirmed by human evaluation.
Our scientific contributions
follows: 1. We empirically show that the utility matrices for MBR decoding are low-rank.
2. We apply ALS to a subset of scores to approximate the full MBR matrix.
3. We show that using our method we can reduce the number computations by a factor of 16, while maintaining the same translation quality level.
2 Related Work
While MT research has traditionally relied on MAP decoding or generating k-best lists through beam search MBR decoding, Eikema and Aziz (2020) proposed an approximation of MBR decoding via unbiased sampling. Their method aims to address the limitations of MAP decoding (Eikema and Aziz, 2020; Müller and Sennrich, 2021; Fikema and Aziz, 2022) by demonstrating that samples drawn from the NMT model align more faithfully with training data statistics when compared to beam

---

search. Freitag et al. (2022a) showed that using neural metrics results in significant improvements in translation quality. Freitag et al. (2023a) reported that the choice of sampling approach important, and epsilon sampling (Hewitt et al., 2022) is ideal for MBR decoding and reranking.
While the improvements in translation quality afforded by MBR are widely acknowledged, its high computational cost limits its application in practice. Different approaches have been proposed to speed up MBR computation. Eikema and Aziz (2022) propose to decouple the candidate and pseudo- reference lists to allow for different sizes, and propose a coarse-to-fing fine refinement of the hypothesis space. Cheng and Vlachos (2023) speed up MBR decoding by gradually increasing the number of samples used to estimate the utility, while additionally pruning the hypothesis space. Jinnai and Ariu (2024) formulate MBR as a medoid identification problem, and apply approximate algorithms developed on this problem. Vamvas and Sennrich (2024) aggregate the set of pseudo -reuudeeefer,nces, allowing for just one utility computation per candidate. This greatly accelerates the decoding process, but the utility metric needs to fulfill certain conditions to be applicable. Finkelstein et al. (2024) use MBR decoding a wwwlledg-ddstillationn framework to simulate MBR decoding with single-pass search. Tomani et al. (2024) train quality-aware translation models in order to reduce the size of the candidate list. Similar in spirit to MBR decoding, QE-rescoring approaches (Fernandes et al., 2022) also directly optimize utility function, with linear-time cost.
Low-Rank Matrix completion is an active area of research and multiple algorithms have been developed to perform it. Nguyen et al. (2019) is an extensive survey for such methods. Some of the popular algorithms are: Singular Value Thresholding (Cai et al., 2008), Bayesian Probabilistic Matrix Factorization (Akulwar and Pardeshi, 2016), Maximum Margin Matrix Factorization (Srebro et al., 2004) and Alternating Least Squares (Zachariah al., 2012), which the one we chose for this work. To the best of our knowledge, this work is the first one to apply matrix completion algorithms for completing a partial MBR score matrix.
3 Preliminaries
We are given an NMT model (e(y)z) which serves to estimate the probability of a hypothesis segment y. given source segment x, with @ heing the learned parameters of the neural network. MAP decoding involves searching for the most probable translation under (ylzr. However, determining the hypothesis with the maximum probability is computationally intractable due to the expansive and combinatorially complex search space. Consequently, approximations like beam search (Graves, 2012; Sutskever et al., 2014) are often employed.
If we want to generate diverse hypotheses, e.g. in generative tasks where creativity is desired instead of selecting the candidate with the highest probability (or approximation thereof), we sample the output sentence following the probability distribution defined by the model. For NMT, this approach is used for generating a list of candidate translations. Specifically, epsilon sampling, by Hewitt et al. (2022), has emerged as the leading sampling technique for MBR. It was shown by Freitag et al. (2023a) to outperform other methods such as ancestral, top-k nucleus sampling (Holtzman et al., 2020). Epsilon sampling prunes away any token with a probability lower than a threshold e, thereby guarantecing that each token within sample is allocated fair probability mass.
outlined
3.1 Minimum Bayes Risk Decoding
In MBR decoding (Bickel and Doksum, 1977; Berger, 1985), given a set of candidate hypotheses H. the goal is to select the optimal hypothesis based on its expected utility, measured by a function u, with respect to the distribution over human references within the space of all references y
Since the true distribution remains unknown, resort to sampling from the model instead, which relies on the assumption that the model provides a reliable approximation for the true underlying distribution over human translations. Furthermore, the integration over the vast space of all possible references y is computationally intractable. Therefore, MBR adopts a finite sample estimate by sampling a set of pseudo-references R. from Po(+(x:) This approximation can be expressed as:
h MBR argmax
Σ u(h,r)
REH
R
FER
3

---

Usual practice is to set = R. i.e the same set of model hypotheses serves both as the candidate list H. as well as the pseudo-reference list R. The computational time complexity of MBR decoding is ((2)) with N the size of the candidate list.
Note that this quadratic expression refers the total cost will be O(S N²). Also there is hidden (multiplicative) constant, namely the cost of the computation of the utility function. For surface level metries (e.g. BLEU, ChrF), this cost is negligible, but for neural metrics it involves computing the forward pass of a large neural network. Therefore, any reduction the number of metric computations has an important effect on the total running cost.
each sentence translate, i.e. for corpus of size S,
3.2 Low-Rank Matrix Completion
Low-Rank Matrix Completion is fundamental problem in machine learning and data analysis with popular application such as Collaborative Filtering (Rennie and Srebro, 2005) and Image Denoising (Candes and Recht, 2008). The goal of matrix completion is to estimate the missing entries of a partially observed matrix, under the assumption that the underlying matrix is low-rank. This assumption implies that the matrix can be well-approximated by a product of two smaller matrices, capturing the latent factors that explain the observed data. Candes and Recht (2008) proved that perfect approximations can be achieved if the number of observed entries larger than 2.2 (N) for some positive numerical constant C. for most N x N matrices of rank r with very high probability.
One simple and efficient algorithm Alternating Least Squares (ALS) (Zachariah et al., 2012). To recover any matrix M, the algorithm approximates it by two smaller matrices M = X and then minimizes the following equation given the observed entries.
min
Σ May observed
(m²y - xf, +
Σ 12:11| +
Σ
|10
1|
The algorithm achieves this by alternatively solving for X and Y shown in Algorithm The algorithm has three hyperparameters: À regularization term, r the second dimension of the smaller matrices and the number of alternating steps performed. The main motivation for picking this algorithm in our approach is its simple implementation.
Algorithm 1 ALS for Matrix Completion
Require: X, and N
1: Initialize X, Y with shapes N x and N
2: repeat
3: for 1...... do
4: Ri = Em ysu] + ATx) 7 Emi Mighr
5: end for
6: for 1... do
7: yj = (Emyymms x, + 2Ix) Emsremus Mij3s
8: end for
9:
until convergence
4
MBR Matrix
4.1
Definition MBR matrix
Given source sentence, we use an NMT model to generate a set 76 of hypotheses such that [7[| = N. As explained in the preliminaries section, the MBR method uses two different sets of hypotheses and pseudo-references, but in practice we use the same set of samples for both H and R. The pairwise scores for all hypotheses in gives an N x N matrix M such that Mii.jl = (h, hy) for all (h,, hy) H H and utility metric U that computes some similarity between two hypotheses.

---

Table 1: Summary of the first three singular values of MBR matrices for the MetricX and chrF utility functions, with two different sizes and four different language pairs
64x64
128x128
MetricX
chrF
MetricX
chrF
LP
01
02
03
01
02
d'
01
02
03
01
02
03
45.7
2.1
1.0
39.9
2.4
1.4
91.6
3.8
1.7
76.2
4.2
2.1
Eermaan-EEnglih
47.4
2.1
1.4
47.5
1.5
1.4
94.6
3.7
2.1
93.7
3.0
2.0
47.7
2.0
1.1
36.1
1.9
1.3
95.4
3.6
1.7
76.8
3.4
2.1
Russian Meisiann>English
46.1
2.2
1.0
40.5
2.8
1.3
92.0
4.1
1.7
81.8
5.7
2.1
Average
46.7
2.1
1.1
41.0
2.15
1.35
93.4
3.8
1.8
82.1
4.1
2.1
MetricX
chrF
10a
10a
10a-
10a
Singuler: Value
Singular value
109
109
10-1-
10-1
20
40
60
100
120
100
12c
Order
Order
Figure 2: Plot the singular values of an example 124x124 MBR matrix using logscale. We observe sharp drop after the first singular value for the two utility metrics indicating that the matrix is rank-1.
With this matrix formulation, MBR decoding reduces to picking the row with the highest average (since each row maps to one sample in the hypotheses list).
4.2 MBR matrices are low rank
Intuitively, the values within the MBR matrix are highly correlated, since by definition each value Mii.j] is computing a similarity score between two hypotheses given utility metric. This is key assumption that our work is built on since low-rank matrices have theoretical bounds on the number of entries required to recover the full matrix (Candes and Recht, 2008).
We verify this assumption empirically. We generated 1024 samples for each example the WMT 2022 <>de and <tru datasets. We then generated the N x N matrices for different values of E {64, 128) by only considering a random subset of the samples using two different utility metrics: MetrieX (Freitag et al., 2022b) and ChrF (Popović, 2015). We then perform singular value decomposition and look at the distribution the singular values, shown in Figure 2 and Table I. We observe that across utility metrics and matrix dimensions, d1 d2- On average across datasets have 02/01 < 0.05, this means that most of the information within the matrix can be captured by single dominant direction component and thus be approximated rank-1 matrix.
5 The PMBR Method
We propose approximation method for MBR decoding that leverages the low-rank structure of the MBR matrix. The procedure is shown in Algorithm 2. Given an NMT model, we start by generating a set of hypotheses H similar to the vanilla MBR method. Then, instead of computing all the pairwise scores in the utility matrix, we only compute random subset of the scores that we denote with Ω. The size of Q depends the computation budget available. We define the budget the ratio of
5

---

computations performed with respect to the total amount of computations to compute the full matrix. Thus for any given budget 1/r, we end up with N2 entries observed in the matrix. The next step to apply ALS on [ as described in Algorithm 1, where M[ denotes the matrix of size N x N where only the entries of Ω2 are non-null. Finally, with all the pairwise scores recovered, we perform vanilla MBR decoding. We call this procedure PMBR for Probabilistic MBR decoding.
Algorithm 2 PMBR: MBR Approximation using ALS
Require: List of hypotheses H, reduction ratio E (0,
N +- И
2: S f- [r]
> Number of utility computations
Ω Sample S coordinate pairs (i.j) from N N
4: M < [||]x|N]
Initialize empty matrix
5: for (i,j) E Ω do
6: Mij + (i,
7: end for
8: M 4- AL,, hyperparameters)
9: return vanilla_ MBR((M)
Time Complexity The time complexity of this algorithm is dominated by the utility metrics computations. The utility metrics are deep neural networks that require a number of operations in the order of millions while ALS requires only few hundred operations. For reference, 30 steps of the ALS algorithm with r = 10 running on a CPU takes on average 0.2 seconds to while the MetrieX inference takes 3.4 seconds a TPUv4 platform. Thus, the savings in run time achieved by our approximation is close to proportional to the savings in number of utility computations. Note that this analysis focuses only on the second stage of MBR decoding, i.e. do not take the cost of generating the hypotheses into account.
Experimental Setup
6.1 Metrics
We MetricX (Juraska al., 2023) the utility function for all variants of MBR decoding has been shown that neural fine-tuned metrics outperform word-overlap metrics like BLEU (Papineni al., 2002) and ChrF (Popović, 2015) for MBR decoding (Freitag al., 2022a). MetricX is extension of BLEURT (Sellam et al., 2020), showing higher correlation with human judgment (Freitag al., 2023b) and has been designed to also work on multi-sentence segments (Deutsch al., 2023) and not only sentences in isolation. In addition, we report COMET22 (Rei et al., 2020, 2022) scores as there is risk of overfitting (Amrhein and Sennrich, 2022) on MetricX. In addition, for one selected experiment we conducted expert-based human evaluations using MQM (Freitag et al., 2021), human evaluation scheme centered on marking errors present in the translations. We report results by varying the budget available to the MBR methods. For each budget, we randomly sample from the full MBR matrix, and report the average results of 1000 trials.
6.2 Datasets and Model
We run experiments using the WMT 2022 test sets for English++German (en<>de) and English--Rusiaa (ens+ru).. The official WMT test sets (Koemi et al., 2022) are split into sen- tences but come with document information. We constructed multi-sentence (paragraph) level test sets with the following method: for each document, we concatenate sentences together as long as we do not exceed 500 sentence piece model (SPM) tokens (given the MetricX SPM model). We respect sentence boundaries and do not truncate sentences. In WMT22, there are four different domains. Some domains lack document context, so segments remain as single sentences, even within multi-sentence test sets. Test data statisties can be seen in Appendix 5. We use PaLM8B (Chowdhery et al., 2022) translation model and sample 1024 examples for each sentence using epsilon sampling with e = 0.02 (Freitag et al., 2023a) and using 3-shot prompting with examples taken from the FLORES corpus (Guzmán et al., 2019)

---

paragraph level
Menoo
1el. mar
full mor
72.2
approx(215)
asproxtSiS1
apseun(Nes)
esproctloa
2024
2038
4036
$152
10386
212
3024
2049
4096
9.92
16204
budget
1/32
1/16
1/8 2048
1/4 4096
1/2 8192
1/1 16384
utility calls
512
1024
PMBR ((22)
512
1024
2 048
096
192
16 384
Matrix size
Nx K
128
4
128 X 8
128 16
128 x 32
128 x 64
128 X 128
SXS
22 x 22
32 x 32
45 x 45
64 x 64
90 x 90
128 x 128
Figure 3: We scored WMT22 DeEn dataset 1000 times for each budget available. Each scoring picks without replacement 128 samples from the 1024 samples available for each sentence. The highlighted area shows the standard deviation of the scores.
6.3 Decoding Methods
compare our approximation PMBR against three other decoding methods. To enable a fair comparison, we adapt each method that the number of utility function computations is the same for each method. (Recall that for given budget 1/r, we only observe N /²/r entries in the matrix when performing PMBR.) We compare PMBR with the following methods:
FMBR: This is the full MBR method. This is the only method that is not affected by the budget i.c the full matrix is observed.
Nx K: This method was proposed by Eikema and Aziz (2022) and works by shrinking the preudo-references list size. For budget 1 /r the MBR matrix gets reduced an N K matrix with K = N/r. The K pseudo-references are randomly sampled.
SxS: This method corresponds to FMBR, but reduces the total size of the utility matrix to size of S S, where the total number of entries corresponds to the available budget, i.c. S / /r. The S examples are randomly sampled.
6.4 Hyperparameter Tuning
The ALS algorithm has three hyperparameters X, n and r as described in Algorithm 1. We perform grid search optimize these hyperparameters, setting respect to the vanilla MBR method. Concretely, for each example sentence we rank all samples by running the vanilla MBR. Let denote with bIBER the hypothesis selected by the full MBR method, and let рoSPMBR (AMRR) the rank the position of lMMr after ordering the hypotheses according to the scores predicted by PMBR. The loss function then just the sum of p0SpMBR (MMBR) for all the hypotheses in subset of the data. We minimize this loss per language pair on 10 examples that we hold from the data generated with the WMT 2022 datasets with this search space {} (0.1, 0.15, 0.2}} x {r E (5,6, 14, 15)} x {n {10, 11, 29, 30}}
loss function to be the accuracy with
7 Results
The main experimental results are summarized Table and Table In Table we fix N 128 and study the behaviour of each approximation method by limiting their budget fraction of the

---

Table 2: Results on the four translation directions on the WMT22 data. Each number (except for FMBR) is the average of 000 runs with different random values taken from the full MBR matrix. N is set to 128, and the budget is allocated according the description in Section 6.3. 'C' denotes C0MET22 scores and 'X' MetricX scores.
budget
1/32
1/16
1/8
1/4
1/2
C
C
C
C
FMBR
83.52
77.01
83.52
77.01
83.52
77.02
83.52
77.02
83.52
77.01
PMBR
83.53
75.94
83.63
76.50
83.63
76.81
83.60
76.96
83.56
Nx K
82.18
74.96
82.90
75.99
83.28
76.59
83.45
76.84
83.48
76,93
SxS
83.39
76.12
83.52
76.43
83.57
76.63
83.59
76.79
83.57
76.91
FMBR
79.97
73.52
79.97
73.52
79.97
73.52
79.97
73.52
79.97
73.52
PMBR
80.00
80.01
73.44
73.53
Nx K
79.75
72.93
79.87
73.24
79.92
73.39
79.95
73.45
79.96
73.49
SxS
79.87
73.17
79.91
73.29
79.94
73.37
79.96
73.44
79.97
73.49
FMBR
83.52
77.01
83.52
77.01
83.52
77.02
83.52
77.02
83.52
77.01
PMBR
83.53
75.94
83.63
76.50
83.63
83.60
83.56
Nx K
82.18
74.96
82,90
75.99
83.28
76.59
83.45
76.84
83.48
76.93
SxS
83.39
76.12
83.52
76.43
83.57
76.63
83.59
76.79
83.57
76.91
FMBR
79.17
75.57
79.17
75.57
79.17
75.57
79.17
75.57
79.17
75.57
PMBR
79.15
75.15
79.23
75.40
79.22
75.48
79.19
75.51
79.18
75.56
Nx K
78.71
74.68
78.99
75.21
79.08
75.41
79.14
75.52
79.15
75.54
SxS
78.98
75.01
79.06
75.20
79.10
75.34
79.13
75.43
79.15
75.52
Table Summary average scores of the full DeEn WMT 2022 pairs scored 1000 times using MetricX and COMET22 evaluation metrics while varying the size of the hypothesis list
budget
1/32
1/16
1/8
1/4
1/2
C
C
C
C
FMBR
NA
NA
79.91
73.29
79.91
73.29
79.91
73.29
79.91
73.29
PMBR
NA
NA
79.87
73.01
79.97
73.26
79.99
73.36
79.95
73.34
NxK
NA
NA
79.46
72.27
79.74
72.84
79.84
73.09
79.88
73.22
SxS
NA
NA
79.61
72.56
79.73
72.82
79.82
73.04
79.87
73.17
OFMBR
79.97
73.45
79.97
73.45
79.97
73.45
79.96
73.45
79.97
73.45
N=64
PMBR
79.90
73.07
79.98
73.30
80.02
73.44
80.02
73.47
80.00
73.47
NxK
79.43
72.25
79.76
72.91
79.88
73.20
79.93
73.35
79.96
73.40
SxS
79.73
72.80
79.82
73.04
79.88
73.19
79.92
73.30
79.95
73.38
FMBR
79.97
73.52
79.97
73.52
79.97
73.52
79.97
73.52
79.97
73.52
N=128
PMBR
80.00
73.32
80.01
73.44
80.03
73.52
80.02
73.53
80.00
73.54
NxK
79.75
72.93
79.87
73.24
79.92
73.39
79.95
73.45
79.96
73.49
SxS
79.87
73.17
79.91
73.29
79.94
73.37
79.96
73.44
79.97
73.49
FMBR
79.96
73.60
79.96
73.60
79.96
73.60
79.96
73.60
79.96
73.60
N=256
PMBR
80.02
73.44
80.03
73.53
80.02
73.55
80.01
73.58
80.00
73.61
NxK
79.86
73.28
79.90
73.42
79.94
73.49
79.95
73.52
79.96
73.56
SxS
79.94
73.36
79.96
73.45
79.97
73.49
79.98
73.54
79.97
73.56
8

---

Table 4: Summary of the average scores of the full EnDe WMT 2022 with N=256 and r=1/16 pairs scored 1000 times using MetricX and COMET22. The MQM scores are limited to 65 examples where all systems disagreed.
COMET22
MetricX
MQM
FMBR
83.33
77.15
1.169
PMBR
83.51
76.95
1.370
NxK
83.11
76.75
1.746
SxS
83.59
76.79
1.566
full computational cost each language pair. The top comprises the results obtained with the full MBR method (FMBR) running on the complete list of N=128 candidates, and can be considered upper bound for the performance of each approximation method. The number of utility calls for FMBR is 128 = 16 384. In Figure 3, we plot the data for the for de->en from Table 2. In Table 3, fix the language pair to (de<+en) and we N to different values. This simulates the behavior of approximation methods as the candidate list grows. Similar results for (en+>dee are shown in Appendix 6. MQM human evaluation results are summarized Table
As measuring performance with the same metric we are optimizing for has the risk of overfitting, we mainly focus COMET22 to assess translation quality. These are the main findings:
(1) PMBR outperforms all other tested approximation methods PMBR outperforms both the NxK and SxS approximation methods across language pairs, sample sizes and budgets. The gap between the approximation methods closes as the budget increases. Moreover the results in Table ?? show that the same pattern holds when the size of the hypotheses list changes.
(2) PMBR is competitive to FMBR We can reduce the computational cost by up to - = 1/32 with PMBR without any loss in translation quality measured by COMET22. Interestingly, observe that MetricX scores slightly drop when reducing the budget. As this does not affect the final translation quality measured by COMRT22, argue that this is good sign and PMBR acts as some kind of regularization.
(3) Human Evaluation confirms (1) and (2) To verify findings based on COMET22, do run a MQM human evaluation with professional translators. Results are summarized in Table 4. The results confirm our previous findings: (1) PMBR is the best approximation method when compared to NxK and SxS, and (2) PMBR is getting close to the performance of FMBR.
8 Conclusions
In this paper we have shown the inherent low-rank structure of Minimum Bayes Risk (MBR) score matrices which we leveraged to develop an approximation method for MBR decoding that achieves competitive performance while significantly reducing computational complexity. Our empirical results demonstrate the efficacy of this approach across diverse language pairs and evaluation metrics, suggesting its potential for wider application in machine translation and other natural language generation tasks.
Future research could explore the efficacy of alternative matrix completion algorithms further enhance the low-rank approximation. In addition, the observed low-rank property could be exploited inform sampling strategies, potentially leading more efficient and informative data collection for MBR decoding. Another promising avenue is to investigate the applicability of this work to domains beyond natural language generation tasks.
Limitations
While we have verified that the MBR matrices are low-rank, we did not conduct an empirical analysis on their coherence. A low-rank matrix is easier to complete its energy spreads evenly across different coordinates. This property is captured by the notion of coherence (Candes and Recht, 2008).

---

In this paper, we only run experiments with MetricX as utility function. The computational costs for computing all pairwise utility scores is expensive. However, we showed that the low-rank matrix structure holds for both MetricX and chrF which gives us confidence that PMBR will generalize regardless of the utility function.
Our human evaluation is limited in size because it is costly. With automatic metrics, we can simulate multiple runs of scoring the datasets but this is not feasible with human evaluations. Thus, we put less statistical significance on our human evaluation.
10

---

References
Pooja Akulwar and Sujata Pardeshi. 2016. Bayesian probabilistic matrix factorization - dive to- wards recommendation. In 2016 International Conference on Inventive Computation Technologies (ICICT), volume 3, pages 1-5.
Chantal Amrhein and Rico Sennrich. 2022. Identifying weaknesses in machine translation metrics through minimum Bayes risk decoding: A case study for COMET. In Proceedings of the 2nd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 12th International Joint Conference on Natural Language Processing (Volume 1: Long Pupers), pages 1125-1141, Online only. Association for Computational Linguistics.
James O Berger. 1985. Statistical decision theory and Bayesian analysis; 2nd ed. Springer series in statistics. Springer, New York.
Peter Bickel and Kjell A Doksum. 1977. Mathematical statistics: Basic ideas and selected topics. Holder-Day Series in Probability and Statisties, Holder-Day, San Francisco.
Jian-Feng Cai, Emmanuel Candes, and Zuowei Shen. 2008. singular value thresholding algorithm for matrix completion.
Emmanuel J. Candes and Benjamin Recht. 2008. Exact matrix completion via convex optimization.
Julius Cheng and Andreas Vlachos. 2023. Faster minimum bayes risk decoding with confidence- pruning.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay. Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Sacta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Seiier-elllstenn, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. 2022.
Palm: Scaling language modeling with pathways.
Daniel Deutsch, Juraj Juraska, Mara Finkelstein, and Markus Freitag. 2023. Training and meta- evaluating machine translation evaluation metrics at the paragraph level. In Proceedings of the Eighth Conference Machine Translation, pages 996-1013, Singapore. Association for Computational Linguistics.
Bryan Eikema and Wilker Aziz. 2020. Is MAP decoding all you need? the inadequacy of the mode in neural machine translation. In Proceedings of the 28th International Conference on Computational Linguistics, pages 4506-4520, Barcelona, Spain (Online). International Committee on Computational Linguistics.
Bryan Eikema and Wilker Aziz. 2022. Sampling-based approximations to minimum Bayes risk decoding for neural machine translation. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 10978-10993, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
Patrick Fernandes, António Farinhas, Ricardo Rei, José G. C. de Souza, Perez Ogayo, Graham Neubig, and Andre Martins. 2022. Quality-aware decoding for neural machine translation. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1396-1412, Seattle, United States. Association for Computational Linguistics.
Mara Finkelstein, Subhajit Naskar, Mehdi Mirzazadeh, Apurva Shah, and Markus Freitag. 2024. Mbr and qe finetuning: Training-timg time distillation of the best and most expensive decoding methods.
11

---

Markus Freitag, George Foster, David Grangier, Viresh Ratnakar, Qijun Tan, and Woligang Macherey. 2021. Experts, errors, and context: A large-scale study of human evaluation for machine translation. Transactions of the Association for Computational Linguistics, 9:1460-1474.
Markus Freitag, Behrooz Ghorbani, and Patrick Fernandes. 2023a. Epsilon sampling rocks: Investi- gating sampling strategies for minimum Bayes risk decoding for machine translation. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 9198-9209, Singapore. Association for Computational Linguistics.
Markus Freitag, David Grangier, and Isaac Caswell. 2020. BLEU might be guilty but references are not innocent. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 61-71, Online. Association for Computational Linguistics.
Markus Freitag, David Grangier, Qijun Tan, and Bowen Liang. 2022a. High quality rather than high model probability: Minimum bayes risk decoding with neural metrics. Transactions of the Association for Computational Linguistics, 10.8118825..
Markus Freitag, Nitika Mathur, Chi-kiu Lo, Eleftherios Avramidis, Ricardo Rei, Brian Thompson, Tom Kocmi, Frederic Blain, Daniel Deutsch, Craig Stewart, Chrysoula Zerva, Sheila Castilho, Alon Lavie, and George Foster. 2023b. Results of wmn23 metries shared task: Metries might be guilty but references are not innocent, In Proceedings of the Eighth Conference on Machine Translation, pages 578 628, Singapore. Association for Computational Linguistics.
Markus Freitag, Ricardo Rei, Nitika Mathur, Chi-kiu Lo, Craig Stewart, Eleftherios Avramidis, Tom Koemi, George Foster, Alon Lavie, and André F. 'T. Martins. 2022b. Results of WMT22 metrics shared task: Stop using BLEU - neural metrics are better and more robust. In Proceedings of the Seventh Conference on Machine Translation (WMT), pages 46-68, Abu Dhabi, United Arab Emirates (Hybrid). Association for Computational Linguistics.
Alex Graves. 2012. arXiv:1211.3711.
Sequence transduction with recurrent neural networks. arXiv preprint
Francisco Guzmán, Peng-Jen Chen, Myle Ott, Juan Pino, Guillaume Lample, Philipp Koehn, Vishrav Chaudhary, and Marc' Aurelio Ranzato. 2019. The FLORES evaluation datasets for low-resource machine translation:
and Sinhala- Engiish In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 6098-6111, 6111, Hong Kong, China. Association for Computational Linguistics.
John Hewitt, Christopher Manning, and Percy Liang. 2022. Truncation sampling as language model desmoothing. Findings of the Association for Computational Linguistics: EMNLP 2022, pages 3414-3427, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020. The curious case of neural text degeneration. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net.
Yuu Jinnai and Kaito Ariu. 2024. Hyperparameter-ffee approach for faster minimum bayes risk decoding.
Juraj Juraska, Mara Finkelstein, Daniel Deutsch, Aditya Siddhant, Mehdi Mirzazadeh, and Markus Freitag. 2023. MetricX-23: The Google submission to the WMT 2023 metrics shared task. In Proceedings of the Eighth Conference on Machine Translation, pages 756-767, Singapore. Association for Computational Linguistics.
Tom Koemi, Rachel Bawden, Ondfej Bojar, Anton Dvorkovich, Christian Federmann, Mark Fishel, Thamme Gowda, Yvette Graham, Roman Grundkiewicz, Barry Haddow, Rebecca Knowles, Philipp Koehn, Christof Monz, Makoto Morishita, Masaaki Nagata, Toshiaki Nakazawa, Michal Novák, Martin Popel, and Maja Popović. 2022. Findings of the 2022 conference machine translation (WMT22). In Proceedings of the Seventh Conference on Machine Translation (WMT), pages 1-45, Abu Dhabi, United Arab Emirates (Hybrid). Association for Computational Linguistics.
12

---

Mathias Müller and Rico Sennrich. 2021. Understanding the properties of minimum Bayes risk de- coding in neural machine translation. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume Long Papers), pages 259-272, Online. Association for Computational Linguistics.
Luong Trung Nguyen, Junhan Kim, and Byonghyo Shim. 2019. Low-rank matrix completion: A contemporary survey. IEEE Access, 7:94215-94237
Myle Ott, Michael Auli, David Grangier, and Marc' Aurelio Ranzato. 2018. Analyzing uncertainty in neural machine translation. In International Conference on Machine Learning, pages 3956-3965.
PMLR.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. Bleu: method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 31 3-1-188, Philadelphia, Pennsylvania, USA. Association for Computational Linguisties.
Maja Popović. 2015, chrF: character n-gram F-score for automatic MT evaluation. In Proceedings of the Tenth Workshop Statistical Machine Translation, pages 392-395, Lisbon, Portugal. Association for Computational Linguistics.
Ricardo Rei, José G. C. de Souza, Duarte Alves, Chrysoula Zerva, Ana C Farinha, Taisiya Glushkova, Alon Lavie, Luisa Coheur, and André F. T. Martins. 2022. COMET-22: Unbabel-IST 2022 submission for the metrics shared task. In Proceedings of the Seventh Conference on Machine Translation (WMT), pages 578-585, Abu Dhabi, United Arab Emirates (Hybrid). Association for Computational Linguistics.
Ricardo Rei, Craig Stewart, Ana C Farinha, and Alon Lavie. 2020. COMET: A neural framework for MT evaluation. In Proceedings the 2020 Conference on Empirical Methods Natural Language Processing ( (EMNLP), pages
Online. Association for Computational Linguistics.
Jasson D. M. Rennic and Nathan Srebro. 2005. Fast maximum margin matrix factorization for collab- orative prediction. In Proceedings of the 22nd International Conference on Machine Learning, ICML '05, page 713-719, New York, NY, USA. Association for Computing Machinery.
Thibault Sellam, Dipanjan Das, and Ankur Parikh. 2020. BLEURT: Learning robust metrics for text generation. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7881-7892, Online. Association for Computational Linguistics.
Nathan Srebro, Jason Rennie, and Tommi Jaakkola. 2004. Advances in Neural Information Processing Systems, volume 17. MIT Press.
matrix factorization. In
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014. Sequence sequence learning with neural networks. Advances in neural information processing systems, 27.
Christian Tomani, David Vilar, Markus Freitag, Colin Cherry, Subhajit Naskar, Mara Finkelstein, Xavier Garcia, and Daniel Cremers. 2024. Quality- -wwlie translation models: Efficient generation and quality estimation in a single model.
Jannis Vamvas and Rico Sennrich. 2024. Linear-time time minimum bayes risk decoding with reference aggregation.
Dave Zachariah, Martin Sundin, M. Jansson, and Saikat Chatterjee. 2012. Alternating least-squares for low-rank matrix reconstruction. IEEE Signal Processing Letters, 19:231-234.
13

---

A Appendix supplemental material
A.1 DeEn graphs for all hypothesis size lists
Figures 7, and show the performance of PMBR for different hypothesis list sizes. The number are represented in the main results section in Table 3. PMBR outperforms all the other methods measured by both COMET22 and MetricX.
A.2 WMT 2022 paragraph level data statistics
We provide the statistics of the dataset used after combining the sentences from the same document in Table 5. The procedure to create paragraph level data is described details in the data section.
A.3 Scores for EnDE while varying the hypotheses list size
In Table 6, we summarize all COMET22 and MetricX scores after varying the hypotheses list size. We see similar results as shown in the main results sections. PMBR outperforms all the other approximation methods in most cases.
A.4 Standard deviations for DeEn and significance test values
In Table 7, we present the standard deviation for values presented in Table 3. We also p-value significance test to verify that the gap in performance between PMBR and the other systems is significant.
A.5 Other matrix completion algorithms
We experimented with running Singular Value Thresholding (SVT) instead of Alternating Least Square (ALS) algorithm perform the matrix completion. SVT under performed compared ALS as shown in Figure 8. This behavior might be caused by a mistuning of the SVT hyperparameters, but it highlights the importance of the matrix completion algorithm in the PMBR procedure.
A.6 Different samples for the hypotheses and pseudo-references lists
In all our experiments, we have used the same of samples for both hypotheses and pseudo- references which is common practice for MBR decoding in the NMT use case. In Figure 9, we verify that the matrices are still low rank even when the two set of samples are different. We also run an experiment to benchmark the performance of PMBR in this case. The results are shown in Figure 10
paragraph scored
73.6
80.0
79.
73,
COMETT
39
72.
796
f_8_mar
mir
4ppros/MM5
39.4
approsifat)
azpmec/Re5)
aporosiMeei
793
255
522
64
125
522
2024
UEitty Cats
by Cafls
Figure 4: We scored WMT22 DeEn dataset 1000 times for each budget available. Each scoring picks without replacement 32 samples from the 1024 samples available for each sentence. The highlighted area shows the standard deviation of the scores.
14

---

paragraph wph-hpheeeeeee
1530
7500
72.75
72.30
79.4
(p2rcs/MMER)
#2prox|PMRR)
aparcstSi5))
e2proslGc5))
72.00
aparos/iion)
#opmot/kok)
128
296
912
1924
2045
4296
128
296
512
1924
2045
4036
UMiltty
Figure 5: We scored WMT22 DeEn dataset 1000 times for each budget available. Each scoring picks without replacement 64 samples from the 1024 samples available for each sentence. The highlighted area shows the standard deviation of the scores.
WMT22
level DeCn scored 1000 times wit' N=256
736
734
70.9
73.
72.0
11.
29.7
72.8
4pprce/ba5) aporoxtNeki
aporuni5151
sporesthoat
1024
2018
4096
6192
16304
22700
60536
1024
2048
4396
0192
19304
32708
65536
Calls
Figure 6: We scored WMT22 DeEn dataset 1000 times for each budget available. Each scoring picks without replacement 256 samples from the 1024 samples available for each sentence. The highlighted area shows the standard deviation of the scores.
A.7
Compute Resources
We give a high level estimate of the resources to run the experiments:
Samples Generation: We used around 500 TPUv5 for 5 hours per language pair to generate the samples.
MetricX pairwise computations: We used around 2000 TPUv4 for 24 hours per language pair to compute all the scores.
Scoring simulations: These were run on CPUs parallel on cluster of 1000 machines. Each setting (budget, hypothesis length) takes around 15 minutes to run.
15

---

Table 5: Statistics of the WMT 2022 dataset and its paragraph level transformation.
LP
# segments
Avg. #words/segment
Avg. #sent/segment
wmt 22
2037
16.7
1.01
En-De
+ paragraph
219
154.6
7.99
wmt 22
2037
16.7
1.01
En-Ru
+ paragraph
219
154.6
7.99
wmt 22
1984
14.6
1.01
De-En
+ paragraph
309
93.2
5.73
wmt__ 22
2016
13.6
1.01
Ru-En
paragraph
258
106.0
7.32
Table 6: Summary of the average scores of the full EnDe WMT 2022 pairs scored 1000 times using MetricX and COMET as evaluation metries while varying the size of the hypothesis list
budget
1/32
1/16
1/8
1/4
1/2
C
X
C
X
C
X
C
X
C
X
FMBR
NA
NA
0.8352
0.7641
0.8352
0.7641
0.8352
0.7641
0.8352
0.7641
N=32
PMBR
NA
0.8294
0.7489
0.8347
0.7571
0.8357
0.7615
0.8356
0.7634
NxK
NA
NA
0.8072
0.7262
0.8229
0.7445
0.8297
0.7541
0,8335
0.7595
SxS
NA
NA
0.8255
0.7463
0.8291
0.7525
0.8323
0.7577
0.8339
0.7611
FMBR
0.8361
0.7679
0.8360
0.7679
0.8360
0.7679
0.8361
0.7679
0.8359
0.7679
N=
PMBR
0.8304
0.7504
0.8354
0.7587
0.8366
0.7637
0.8366
0.7662
0.8365
0.7676
NxK
0.8057
0.7266
0,8226
0.7472
0.8299
0.7577
0.8338
0.7633
0,8354
0.7659
SxS
0.8293
0.7525
0.8323
0.7578
0.8340
0.7612
0.8352
0.7642
0.8356
0.7662
FMBR
0.8352
0.7701
0.8352
0.7701
0,8352
0.7702
0,8352
0.7702
0,8352
0.7701
N=
PMBR
0,8353
0.7594
0.8363
0.7650
0.8363
0.7681
0.8360
0.7696
0.8356
0.7701
NxK
0,8218
0.7496
0,8290
0.7599
0,8328
0.7659
0,8345
0.7684
0.8348
0.7693
SxS
0.8339
0.7612
0.8352
0.7643
0.8357
0.7663
0.8359
0.7679
0.8357
0.7691
FMBR
0.8332
0.7715
0,8333
0.7715
0,8332
0.7715
0.8332
0.7715
0.8332
0.7715
N=256
PMBR
0.8354
0.7659
0,8351
0.7695
0.8347
0.7711
0.8341
0.7714
0,8338
0.7717
NxK
0.8274
0.7617
0,8311
0.7675
0,8326
0.7699
0,8332
0.7710
0.8332
0.7712
SxS 0.8357
0.7662
0.8359
0.7679
0.8357
0.7692
0.8351
0.7702
0.8344
0.7709
p-Value significance test for DeEn N=128 for PMBR all other systems
MetricX
COMET
mbr
mbr
0.00
0.00
0.00
0.00
0.00
0.00
16
Significance
16
Significance
8
0.03
0.00
0.00
8 0.00 0.00
0.00
0.42
0.00
0.00
0.00
0.00
0.00
2
0.00
Figure 7: A matrix representing the p-value significance test that checks if PMBR is better than the approximation methods as shown in Table 3. A green boxes means PMBR is significantly better than the other system
16

---

Table 7: Summary of the standard deviations of the full DeEn WMT 2022 pairs scored 1000 times using MetricX and COMET22 evaluation metries while varying the size of the hypothesis list as shown in Table
budget
1/32
1/16
1/8
1/4
1/2
C
X
C
X
FMBR
NA
0.0014
0.0019
0.0014
0.0018
0.0014
0.0018
0.0014
0.0019
PMBR
NA
NA
0.0016
0.0027
0.0015
0.0023
0.0014
0.0022
0.0013
0.0020
NxK
NA
0.0021
0.0032
0.0017
0.0026
0.0014
0.0022
0.0013
0.0020
SxS
NA
NA
0,0015
0.0025
0.0015
0.0022
0.0013
0.0021
0.0013
0.0019
FMBR
0.0012
0.0017
0.0012
0.0017
0.0012
0.0017
0.0012
0.0017
0.0012
0.0017
N=64
PMBR
0.0016
0.0026
0.0015
0.0022
0.0013
0.0021
0.0013
0.0018
0.0012
0.0017
NxK
0.0023
0.0034
0.0016
0.0025
0.0014
0.0021
0.0013
0.0018
0.0012
0.0018
SxS
0.0014
0.0022
0,0013
0.0021
0.0012
0.0019
0.0013
0.0019
0.0012
0.0017
FMBR
0.0011
0.0015
0.0011
0.0015
0.0011
0.0015
0.0011
0.0015
0.0011
0.0015
N=128
PMBR
0.0014
0.0023
0.0013
0.0020
0.0012
0.0019
0.0011
0.0016
0.0012
0.0016
NxK
0.0015
0.0024
0.0014
0.0020
0.0013
0.0018
0.0012
0.0016
0.0011
0.0016
SxS
0.0013
0.0020
0.0013
0.0019
0.0012
0.0017
0.0012
0.0017
0.0012
0.0017
FMBR
0.0011
0.0015
0.0011
0.0015
0.0011
0.0015
0.0011
0.0015
0.0011
0.0015
N=256
PMBR
0.0013
0.0019
0.0011
0.0017
0.0011
0.0016
0.0012
0.0015
0.0011
0.001.5
NxK
0.0014
0.0021
0.0013
0.0018
0.0012
0.0016
0.0012
0.0015
0.001
0.0015
SxS
0.0012
0.0017
0,0012
0.0016
0.0011
0.0016
0.0011
0.0016
0,001
0.0015
par paregraph scored
80.0
154
COMET
23.9
22.2
78.0
T1C
Milmmrr RpprosoFMBR 5VT)
Umb
RpprosuTMDR SVT)
HBR, ALSI
78.7
Sppr2w//BK__00 ALSI uppr c013a5)
72.8
spprosc3vd))
approsctee)
72.6
2024
2013
4036
9152
10384
212
1024
2049
4096
9.92
19284
my
Figure 8: We scored WMT22 DeEn dataset 1000 times for each budget available. Each scoring picks without replacement 128 samples from the 1024 samples available for each sentence. The highlighted area shows the standard deviation of the scores. In this setup, we compare ALS and SVT as matrix completion algorithms.
17

---

MetricX Candidate == Ref
MetricX Candidate != Ret
10a
102
104
Sing tler Voluee
Value
10
10a
10-1
10-1-
10-2
10-3
10:4
10
10
0
20
40
60
80
100
120
20
40
60
80
100
120
Order
Figure 9: Plot the singular values of an example 124x 124 MBR matrix using logscale. The plot on the left shows the where both the samples for hypotheses and pseudo-references lists, while the right shows the case when they are different. Both plots follow a similar pattern.
WMMT22 paragraph level DeFn sconnd 1000 times with N-12R, with [H] R
80.0
COOET
730
75.8
fall mor ApprociPMrR)
72.8
79-7
Mbli Calls
0.li Calb
Figure 10: We scored WMT22 DeEn dataset 1000 times for each budget available. Each scoring picks without replacement 128 samples from the 1024 samples available for each sentence. In this setup, pick different samples for the hypotheses and pseudo-references lists.
18

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes].
Justification: Our experimental results show the claims made the abstract.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper includes Limitations section that discusses this.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA].
Justification: The answer NA means that the paper does not include theoretical results.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The PaLM64B is avaialble through the cloud API. MetrieX and COMENT are publicaly avaialble. The PMBR algorithm code is submitted supplemental.
Justification:
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We share the code all the approximation methods used including our new algorithm. We also open dataset WMT22. We working on clearing internal Google policies to release the generated data and scores.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ye]]
Justification: We share our hypeparameter search space and optimizer. We also share data splits for eval and train.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report 1-sigma error bars in our graphs.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Answer: [Yes]
19

---

Justification: We provide an estimate of the resources in the appendix.
9. Code Of Ethies
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The paper adheres to the NeurIPS Code of Ethics.
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer:
[NA].
Justification:
The answer NA means that there no societal impact of the work performed.
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The answer NA means that the paper poses no such risks.
Licenses existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes].
Justification: The PaLM model is cited. The MetricX and Comet metrics models are cited. The WMT22 dataset cited.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: The answer NA means that the paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [Yes].
Justification: We used humans to collect MQM annotations as described in the original paper.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects. and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]-
Justification: The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
20


Reviews:
[{"review_id": "q36L0cjP4B", "reviewer": "Reviewer_D2EM", "summary": "The paper proposes yet another method for speeding up the utility computation of MBR decoding. The algorithm exploits the structure of the problem that the utility matrix tends to be lower rank as the utility is kind of a similarity metric. The experiments are compared against the standard MBR and show that it achieves a good speedup over the standard MBR.", "questions": "- Figure 5 shows that the utility matrices are likely to be rank-1. My understanding is that in theory it requires a single comparison per each candidate is enough to estimate the quality of the candidate, assuming that we can ignore the noise. I was thinking if this observation would rather motivate the Linear time MBR (Vamvas and Sennrich 2024) as they use a single comparison against the mean of the references, which we expect to have the least noise.\n- Although the rank of the matrix is estimated to be 1, the ranks of the matrices are set to 5 to 15 (Line 224) in the experiment. Why is it better to set it larger than 1? I’m assuming r in Line 224 refers to the rank of the matrix. r is used as the rank and also the reduction ratio in Algorithm 1.\n- What is the definition of O(millions) and O(hundreds)?  (Line 171)\n- Does the method require that candidates and references are the same set of samples? I see several papers in MBR using different sets of samples (Cheng and Vlachos 2023; Ohashi+2024) so it would be better if it works with both cases. I don’t see it as a reason to reject it, but I think it needs to be clearly mentioned that the proposed method can’t use a different set of samples, if so.\n- It would be nice to have a comparison of the overall walltime, including the time for sample generation to show in the end how much it improves the speed of the NMT system.\n\nTypos\n- Line 51: effectiveness of out method → effectiveness of our method\n- Line 91: a NMT model → an NMT model\n- Line 155: Figure A.6 and Table 4.2 → I guess Figure 5 and Table 1\n- Line 196: SPM tokens → no definition of SPM\n- Line 197: Note:\n- Line 414 Algorithm 2: There are N and n that I believe they both refer to the same parameter.\n- Line 431: The sentence is incomplete.\n- Line 513, 522: Doesn’t MQM involve human subjects?", "limitations": "I think the paper does not explicitly explain the critical limitations of the method.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- The proposed algorithm is interesting. Prior works do not consider the structure of the utility matrix and rather seek to optimize the computation via hyperparameter tuning or to optimize the worst-case complexity.\n- The observation that the utility matrix is low rank is interesting and is a contribution to the community.\n- Human evaluation is nice to have.", "weaknesses": "The paper brings an interesting new idea to MBR decoding. However, their contribution is claimed ambiguously. \n\n- The experiment does not compare any of the recent algorithms on efficient MBR decoding: Confidence-based pruning (Cheng and Vlachos 2023), Adaptive MBR (Jinnai and Ariu 2024), Linear time MBR (Vamvas and Sennrich 2024), and Centroid-based MBR (Deguchi et al. 2024). Thus, the paper does not show evidence that their method is state-of-the-art with respect to the empirical performance, which will not be a reason for rejection.\n- Empirical evaluation of concurrent work is too much to ask, but I would say that they should be explained fairly. Vamvas and Sennrich (2024) are mentioned that “the utility metric needs to fulfill certain conditions to be applicable.” (Line 77). This is true but I would say that “certain conditions” should be explained clearly in this paper, because the proposed method is only effective when these “certain conditions” are not satisfied, if I understand it correctly. Also note that the proposed method also exploits the structure of the utility metric that results in a low-rank matrix, which may not be universally true. The proposed method also requires that certain conditions are satisfied. I believe this will not be a reason to reject, only if this limitation is clarified in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the insightful review.\n\nWe definitely agree that performing a survey across all the efficient MBR methods will be beneficial for the community and we are interested in running this for future research. We will point this out in the limitations section.\n\nWe address your questions in order:\n* This is a great observation. During our work, we were trying to theorize what this first singular vector semantically means and as you point out one comparison against this vector should be enough to tell us the quality of the candidate. We think it’s interesting to compare this vector against the reference aggregation embedding (Vamvas and Sennrich 2024) proposed in their work. One key advantage of their approach is the linear-time complexity, but they require the utility metric to produce an intermediate sentence embedding. On the other hand, our approach is slower and requires that the MBR matrices have a low-rank structure. Exploring how these two methods overlap is definitely an interesting direction for future research. We will include this insight in the discussion section of the paper and we will emphasize the low-rank condition in the limitation section. \n* Correct, there are two ranks. The true rank r of the matrix and the rank r’ which is a hyperparameter specific to ALS. We’ve run a hyperparamter sweep and we found that using r=5 worked best to minimize the training loss.\nWe do not see any reason that this method requires candidates and references to be the same. Looking at the singular values structure we see that both settings exhibit similar behaviors [fig .3]. We promise to run more experiments to validate this setting and report in the final paper.\n* Regarding the time complexity, the paper states O(millions) and O(hundreds) matrix multiplications but `floating point operations` is more accurate. We will update the paper. The O(millions) is used as an abbreviation for 10^6 order of magnitude, this is an abuse of the big O notation and we will update the paper accordingly too. We did not compute or report actual wall clock time because the experiments are run on a mixture of hardware and configurations (different TPUs, different CPUs) and the walltime will heavily depend on this. However, measuring the number of MBR computations as shown in our paper is in our opinion a fairer and more straightforward measure.\n\nThank you again for your review and thanks for catching all typos. We will make the adjustments accordingly in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8W4pG8TSLj", "reviewer": "Reviewer_GHFT", "summary": "This work proposes an approximate method for minimum Bayes risk (MBR) decoding by employing matrix completion. Basic idea is to fill-in only a fraction of the score matrix to compute MBR scores, and to leverage alternating least squares (ALS) algorithm to estimate the empty slots assuming that the utility score matrix is low rank. This work empirically show that the utility score matrix is actually low rank for MetricX and chrF under some language directions. Empirical results also show that the proposed approximate MBR decoding is a better approximation method when compared with other approximation method, e.g., shrinking the dimension of pseudo-reference list size and sampling-based method.", "questions": "Questions:\n- It is not clear how many iterations are needed for the convergence in general. Also, it would be good to show the average differences and variances of the score matrices by the approximated methods, i.e., prediction performance for the missing values, to quantify the impact of the approximation.\n\nSuggestions:\n- I think Figure 1 is not mentioned anywhere in the paper, and please describe what is indicated by the plots. Also, do not use a bitmap format but use a vector format for clarity. \n- line 155: Figure A.6 and Table 4.2 (?)  -> please check the references.\n- Better to run statistical significance tests on the numbers in Table 2 and 3 to make sure the differences are statistically significant or not.", "limitations": "This paper has discussion on the limitations, e.g., measuring only MetricX, but this work is actually running experiments for COMET as a utility function.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed method is interesting in that it leverages the low-rank matrix completion to estimate the full utility score matrix for MBR decoding assuming that utility score matrices are low rank. The singular values of MT metrics empirically show that the low-rank property holds for some language directions. I think the finding somewhat agrees withe the matrix completion for human assessment [1].\n- Empirical results show that the proposed method is better than other approximation methods even with only a small number of samples, and achieving comparable performance to the non-approximation method even the budget for 1/4. Human judgement also shows that the proposed method is closer to the non-approximation method.\n\n[1] https://aclanthology.org/P13-2025/", "weaknesses": "- This work needs further analysis on the utility score matrices after convergence since there exist some gaps when compared with the non-approximation method under the budget of 1/32. In particular, the true scores filled by the metric might be changed after completion, and I'm curious how that will impact MBR decoding. Also, it would be good to analyze the deltas of the completed scores to see how that will impact the end accuracies. \n- In addition to random sapling to determine the position to fill-in by the true score, I'd like to see a more controlled setting in which the positions are skewed, in which some columns or rows are completely empty and thus complemented by ALS, and how that will impact the estimated scores and the final MBR decoding.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the insightful review.\n\nWe agree that a further analysis on the convergence of the matrix completion algorithm will help us understand better the behavior of our approach and potentially optimize it further. We think this is an interesting future direction of research and we we will point this out in the paper.\n\nThe number of iterations needed for convergence is a hyperparameter that we tune. In general, the required number of steps is less than 15. We included a graph [fig 4] that shows the true loss and training loss during the approximation (true_loss = ((M-A)**2), train_loss = mean(M[omega]-A)**2) with M : original matrix, Omega: sampling mask and A : the approximation at every step). We will include this graph in the paper.\n\nA more sophisticated sampling is an interesting approach to optimize our method further. We definitely want to explore this behavior in future research, one promising approach is adaptive sampling[1] where we pick the samples that give us the most information about the matrix.\n\nWe run a significance test for PMBR against all other systems for the values shown in (Table 3, row 3) in the paper. We see that the gap between PMBR and all the other systems is significant except for one setting [fig 5]. (Note, that greens denote the significance test and not that PMBR is better). We will include these numbers in the paper.\n\nThank you again for your review and thanks for pointing out the missing references. We will make the adjustments accordingly in the paper.\n\n\n[1] https://arxiv.org/abs/1304.4672", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wOVlub1adG", "reviewer": "Reviewer_PUED", "summary": "- this paper uses alternating least square method for matrix completion when only a small part of the utility matrix in MBR decoding is calculated to decrease the computational cost for full MBR decoding and at the same time guarantee the translation quality \n- the authors first justify the use of their method by showing that the utility matrix in MBR decoding is indeed low rank\n- by conducting experiments on WMT dataset and four translation directions, they show that PMBR achieved the best COMET22 score and MetricX on most of the settings", "questions": "- there are other matrix completion methods that also focus on picking the most representative matrix entries for completion. Why did you not compare against those methods?", "limitations": "- yes the authors addressed the limitations\n- and there is no potential societal impact", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- the method they propose is a simple yet effective one to shrink the computational cost for MBR decoding in NMT task \n- Across all the experimental settings the metric score is indeed better than other baseline methods while keeping the cost lower", "weaknesses": "- ALS is one method for matrix completion, ablations should be done using other matrix completion methods to see if the cost can be further reduced by using less examples \n- using matrix completion method to lower the cost for computation intensive tasks itself is not a novel approach \n- PMBR is compared against other MBR decoding related methods but not compared against e.g. naive beam search", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the insightful review.\n\nWe mainly focused on ALS because of its simple implementation and efficiency. We agree that optimizing the matrix completion algorithm further could potentially improve the performance. As you suggested, using an adaptive sampling[1] approach to pick the most representative matrix entries is a promising future direction but we chose the simplest approach to make it easy for others to adopt our work.  \n\nWe run ablations with SVT(singular value thresholding) on one experiment (Lp= DeEn, N=128) which is another elementary matrix completion algorithm. On average, ALS outperforms SVT in particular for tighter budgets [fig1]. This emphasizes that investigating the performance of the matrix completion algorithm is certainly an interesting future direction. We will add this comparison and a discussion in the paper.\n\nWe added results for greedy decoding [fig2]  (metricx:70.19, comet=76.74) and the results are in line with previous work[2]. Greedy decoding falls behind with almost 3 points on both Comet and MetricX. We will add these results to the paper.\n\nThanks again for this great and insightful review.\n\n[1] https://arxiv.org/abs/1304.4672\n\n[2] https://arxiv.org/abs/2111.09388", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JK5vOYx9o7", "reviewer": "Reviewer_Xkoo", "summary": "Minimum Bayes risk (MBR) decoding is a widely used technique for machine translation (MT) that involves generating $N$ candidate translations that are then scored according to a utility function, typically an automatic reference-based MT metric. In practice, this is done by comparing each candidate in the set to all the other candidates (that are used as pseudo-references), which is computationally very expensive, with a time complexity of O(N^2). This paper focuses on improving the efficiency of MBR decoding by reducing the number of metric computations. Based on the assumption that the MBR utility matrix is low-rank, they score only a subset of the candidate-pseudo-reference pairs and use the ALS algorithm to estimate the missing values.  Their experiments show that their method does not compromise translation quality.", "questions": "Comments and questions:\n- Although the definition of MBR matrix is presented in Section 4, it would be beneficial to briefly explain this a bit better earlier in the paper (e.g., in the paragraph in L44-54). It may not be straightforward to all readers to understand where this matrix comes from and why it can be assumed to be low-rank. \n- Where is Figure A.6 and Table 4.2, mentioned in L155? This is pointing to the sections… After a closer look, Table 1 and Figure 5 seem to be the ones that you are referring to.\n- What happens if you fill in the missing values in the MBR matrix with random numbers instead of using ALS? I believe this is an important baseline.\n- The results in the tables are averaged over 1000 trials. Can you please provide standard deviations too?\n\nMinor comments:\n- Fix citation style in L84 (no parenthesis) and L86 (missing whitespace).\n- Missing punctuation in Eq. 2.\n- Missing whitespace in L202.", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper offers a simple solution to a problem that remains unsolved so far (making MBR faster/cheaper) without compromising the final translation quality.\n- I believe that framing this as matrix completion problem is a novel approach.\n- The experimental results are good and confirmed with human evaluation.", "weaknesses": "- The experiments are only performed on two language pairs (EN-DE and EN-RU). Can we expect the same findings for other languages, including lower resource ones? The WMT test sets include other languages, so it shouldn’t be hard to validate this. Also, only PaLM8B is used. It would be good to try other models such as Tower (Alves et al., 2024) with a varying number of samples.\n- There is a lot of discussion about related work on making MBR decoding more efficient in Section 2 but the comparison to some of these efficient MBR approaches is missing in the experimental part. Also, it would be good to compare with linear-time cost approaches such as QE-reranking (Fernandes et al., 2022) since this is a clear baseline.\n- See my questions below for other things.\n\nTower: An Open Multilingual Large Language Model for Translation-Related Tasks (Alves et al., 2024)\n\nQuality-Aware Decoding for Neural Machine Translation (Fernandes et al., 2022)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed feedback.\n\nWe limited the paper to 4 different language pairs because precomputing the full 1024x1024 utility metrics is very expensive (It requires around 2000 TPUs for a full day per language pair). We definitely agree that performing a survey across all the efficient MBR methods will be beneficial for the community and we are interested in running this for future research. We will point this out in the limitations section of our paper.\n\nWe address your questions in order:\n1) Thanks for the suggestion. We agree that the MBR matrix definition is not straightforward and that’s why we included a dedicated section to introduce it. We will update paragraph 4 to give a high level overview and point out to section 4 for the full definition. \n2) Table 1 and Figure 5 are the correct artifacts. Figure 5 was in the main paper but we moved it to the appendix when we were trimming down the paper to fit in the page limit. We will correct the labels and move figure 5 back to the main paper.\n3) We believe that this method should be in practice very similar to the NxS if we assume that on average the random values will add the same value to each row.\n4) We attach table 7 that contains all the standard deviations from table 3 shown in our submission. All methods showed similar trends in standard deviation values. We will add the numbers to the paper.\n\nThank you again for your review and thanks for catching all the minor style issues. We will make the adjustments accordingly in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you all for the reviews. We attach a pdf that includes more results and details that were requested. The plots in the pdf are referenced in the individual replies with [fig #number] format.

Meta-review: This paper proposes a method to improve the efficiency of MBR decoding by reducing the number of metric computations. They show that the utility matrices for MBR decoding are indeed low-rank,  and they score only a subset of the candidate-pseudo-reference pairs and use the ALS algorithm to estimate the missing values to approximate the full MBR matrix. Experiments  on WMT dataset show that this method  achieves a good speedup over vanilla MBR and does not compromise translation quality. 

Some reviewers raised concerns regarding to the comparison with the recent algorithms on efficient MBR decoding, such as Confidence-based pruning, Linear time MBR, Centroid-based MBR,  QE-reranking and the naive beam search, to make it more clear if this work is on par with the existing work. The authors provided some clarifications and limitations in their rebuttal with some extra results. Finally, all reviewers feel positive to the work. My comment is that this work brings an interesting new idea and makes a good contribution to the field of MBR decoding, with minor issues that can be solved in the revision. Therefore, I recommend an "acceptance".
Decision: Accept (poster)