Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms

Authors: firas  trabelsi
david  vilar
mara  finkelstein
markus  freitag
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 21:09:50

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.

Main paper: 
 introduction: 
 The generation process in most conditional natural language processing tasks is usually guided by the maximum-a-posteriori (MAP) rule: given an input x, generate the output ŷ that maximizes the posterior probability distribution: ŷ = argmax y p(y|x). It can be shown that MAP decoding is optimal under a 0-1 loss criterion. However for more nuanced tasks, where different outputs can be considered correct, and the quality of the output is not just a binary decision between "right" and "wrong", MAP decoding is no longer optimal. Neural Machine Translation (NMT) is a prominent example of these types of tasks. For NMT, a system is trained to generate a sentence in a target language given a source sentence in another language. For a given sentence, there exists a variety of possible translations, each of which has a 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 et al., 2020) .As an alternative, Eikema and Aziz (2020, 2022) applied MBR decoding for NMT models. MBR decoding follows a two-step approach, where a model is used to generate a list of candidate translations and a list of pseudo-references (which may be the same as the list of candidates). The candidates Figure 1 : PMBR decoding only requires a subset of the utility computations to approximate the output of MBR decoding. The method approximates the unknown values by running a 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.are then scored with a performance metric using the pseudo-references as an approximation of the 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 to generate the translation with the highest estimated model probability; instead it aims to directly optimize a utility function. Subsequent research conducted by Freitag et al. (2022a) showed that MBR decoding with neural utility metrics leads to significant improvements over beam search decoding. However, MBR is computationally expensive, with a time complexity of O(N 2 ) for a 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 1 000, which involves thousands to millions of utility function computations. Note than when using neural metrics, each of the O(N 2 ) "computation steps" is itself expensive, requiring a forward pass through a large neural network.In this work, we propose to reduce the number of metric computations by scoring only a subset of candidate-pseudo-reference pairs. We then proceed to use a matrix completion algorithm (ALS in our case) to estimate the remaining utility scores. For such completion algorithms to work, the full matrix has to fulfill some conditions, specifically to be a low-rank matrix. We empirically show that this is indeed the case for the utility matrices for MBR decoding. Intuitively, this makes sense: akin to recommendation systems, where similar users are expected to have similar book or 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 to reduce the number of computations, our method does not compromise translation quality, as confirmed by human evaluation.Our scientific contributions are as 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 of computations by a factor of 16, while maintaining the same translation quality level. 
related work: 
 While MT research has traditionally relied on MAP decoding or generating k-best lists through beam search for 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; Eikema 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 is 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 pseudoreference lists to allow for different sizes, and propose a coarse-to-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-references, 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. 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 et al., 2012) , which is 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. 
preliminaries: 
 We are given an NMT model P Θ (y|x) which serves to estimate the probability of a hypothesis segment y, given a source segment x, with Θ being the learned parameters of the neural network. MAP decoding involves searching for the most probable translation under P Θ (y|x). 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 an 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, as outlined 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 or nucleus sampling (Holtzman et al., 2020) . Epsilon sampling prunes away any token with a probability lower than a threshold ε, thereby guaranteeing that each token within a sample is allocated a fair probability mass.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, we 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 P θ (•|x). This approximation can be expressed as:EQUATIONUsual practice is to set H = 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 O(N 2 ) with N the size of the candidate list.Note that this quadratic expression refers to each sentence to translate, i.e. for a corpus of size S, the total cost will be O(S • N 2 ). Also there is a hidden (multiplicative) constant, namely the cost of the computation of the utility function. For surface level metrics (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 in the number of metric computations has an important effect on the total running cost.Low-Rank Matrix Completion is a 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 is larger than CN 1.2 r log(N ) for some positive numerical constant C, for most N × N matrices of rank r with very high probability.One simple and efficient algorithm is Alternating Least Squares (ALS) (Zachariah et al., 2012) . To recover any matrix M , the algorithm approximates it by two smaller matrices M ≈ X T Y and then minimizes the following equation given the observed entries.EQUATIONThe algorithm achieves this by alternatively solving for X and Y as shown in Algorithm 1 The algorithm has three hyperparameters: λ a regularization term, r the second dimension of the smaller matrices and n the number of alternating steps performed. The main motivation for picking this algorithm in our approach is its simple implementation.Require: λ, r and N 1: Initialize X, Y with shapes N × r and r × N 2: repeat 3:for i = 1 . . . n do 4:x i = mij ∈mi * y j y j + λI k -1 mij ∈mi * m ij y r 5:end for 6:for j = 1 . . . n do 7:y j = mij ∈m * j x r x r + λI k -1 mij ∈m * j m ij x i 8:end for 9: until convergence 
definition of mbr matrix: 
 Given a source sentence, we use an NMT model to generate a set H of hypotheses such that |H| = 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 H gives an N × N matrix M such that M [i, j] = U (h i , h j ) for all (h i , h j ) ∈ H × H and a utility metric U that computes some similarity between two hypotheses. Figure 2 : Plot the singular values of an example 124x124 MBR matrix using logscale. We observe a 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).Intuitively, the values within the MBR matrix are highly correlated, since by definition each value M [i, j] is computing a similarity score between two hypotheses given a utility metric. This is a 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 in the WMT 2022 en ↔de and en ↔ru datasets. We then generated the N × N matrices for different values of N ∈ {64, 128} by only considering a random subset of the samples using two different utility metrics: MetricX (Freitag et al., 2022b) and ChrF (Popović, 2015) . We then perform singular value decomposition and look at the distribution of the singular values, shown in Figure 2 and Table 1 . We observe that across utility metrics and matrix dimensions, σ 1 σ 2 . On average across datasets we have σ 2 /σ 1 < 0.05, this means that most of the information within the matrix can be captured by a single dominant direction or component and thus can be approximated by a rank-1 matrix. 
the pmbr method: 
 We propose an 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 a random subset of the scores that we denote with Ω. The size of Ω depends on the computation budget available. We define the budget as the ratio of 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 N 2 /r entries observed in the matrix. The next step is to apply ALS on M [Ω] as described in Algorithm 1, where M [Ω] denotes the matrix of size N × N where only the entries of Ω 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 r ∈ (0, 1)1: N ← |H| 2: S ← |N | 2 • r Number of utility computations 3: Ω ← Sample S coordinate pairs (i, j) from N × N 4: M ← 0 |N |×|N |Initialize empty matrix 5: for (i, j) ∈ Ω do 6:M ij ← U (i, j) 7: end for 8: M ← ALS(M, 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 floating-point operations in the order of millions while ALS requires only a 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 run while the MetricX inference takes 3.4 seconds on 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. we do not take the cost of generating the hypotheses into account.6 Experimental Setup 
metrics: 
 We use MetricX (Juraska et al., 2023) as the utility function for all variants of MBR decoding as it has been shown that neural fine-tuned metrics outperform word-overlap metrics like BLEU (Papineni et al., 2002) and ChrF (Popović, 2015) for MBR decoding (Freitag et al., 2022a) . MetricX is an extension of BLEURT (Sellam et al., 2020) , showing higher correlation with human judgment (Freitag et al., 2023b) and has been designed to also work on multi-sentence segments (Deutsch et al., 2023) and not only sentences in isolation. In addition, we report COMET22 (Rei et al., 2020 (Rei et al., , 2022) ) scores as there is a 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) , a 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.We run experiments using the WMT 2022 test sets for English↔German (en↔de) and English↔Russian (en↔ru). The official WMT test sets (Kocmi et al., 2022) are split into sentences 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 statistics can be seen in Appendix 5. We use PaLM8B (Chowdhery et al., 2022) as translation model and sample 1024 examples for each sentence using epsilon sampling with = 0.02 (Freitag et al., 2023a) We compare our approximation PMBR against three other decoding methods. To enable a fair comparison, we adapt each method so that the number of utility function computations is the same for each method. (Recall that for a given budget 1/r, we only observe N 2 /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.e the full matrix is observed. • N×K: This method was proposed by Eikema and Aziz (2022) and works by shrinking the pseudo-references list size. For a budget 1/r the MBR matrix gets reduced to an N × K matrix with K = N/r. The K pseudo-references are randomly sampled. • S×S: This method corresponds to FMBR, but reduces the total size of the utility matrix to a size of S • S, where the total number of entries corresponds to the available budget, i.e. S = N 2 /r. The S examples are randomly sampled.The ALS algorithm has three hyperparameters λ, n and r as described in Algorithm 1. We perform a grid search to optimize these hyperparameters, setting our loss function to be the accuracy with respect to the vanilla MBR method. Concretely, for each example sentence we rank all samples by running the vanilla MBR. Let us denote with h MBR the hypothesis selected by the full MBR method, and let pos PMBR (h MBR ) the rank the position of h MBR after ordering the hypotheses according to the scores predicted by PMBR. The loss function is then just the sum of pos PMBR (h MBR ) for all the hypotheses in a 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}} × {r ∈ {5, 6, . . . 14, 15}} × {n ∈ {10, 11, . . . , 29, 30}} 
results: 
 The main experimental results are summarized in Table 2 and Table 3 . In Table 2 , we fix N = 128 and we study the behaviour of each approximation method by limiting their budget to a fraction of the full computational cost on each language pair. The top row comprises the results obtained with the full MBR method (FMBR) running on the complete list of N =128 candidates, and can be considered as an upper bound for the performance of each approximation method. The number of utility calls for FMBR is 128 2 = 16 384. In Figure 3 , we plot the data for the for de→en from Table 2 . In Table 3 , we fix the language pair to (de↔en) and we set N to different values. This simulates the behavior of approximation methods as the candidate list grows. Similar results for (en↔de) are shown in Appendix 6. MQM human evaluation results are summarized in Table 4 .As measuring performance with the same metric we are optimizing for has the risk of overfitting, we mainly focus on COMET22 to assess translation quality. These are the main findings:(1) PMBR outperforms all other tested approximation methods PMBR outperforms both the N xK 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 r = 1/32 with PMBR without any loss in translation quality as measured by COMET22. Interestingly, we observe that MetricX scores slightly drop when reducing the budget. As this does not affect the final translation quality as measured by COMET22, we argue that this is a good sign and PMBR acts as some kind of regularization.(3) Human Evaluation confirms (1) and (2) To verify our findings based on COMET22, we 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 N xK and SxS, and (2) PMBR is getting close to the performance of FMBR. 
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 to further enhance the low-rank approximation. In addition, the observed low-rank property could be exploited to inform sampling strategies, potentially leading to 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 if 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.A Appendix / supplemental material A.1 DeEn graphs for all hypothesis size lists Figures 7, 5 and 6 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. 
 
 Appendix: 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 in details in the data section.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.In Table 7 , we present the standard deviation for values presented in Table 3 . We also run a p-value significance test to verify that the gap in performance between PMBR and the other systems is significant.We experimented with running Singular Value Thresholding (SVT) instead of Alternating Least Square (ALS) algorithm to perform the matrix completion. SVT under performed compared to 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.In all our experiments, we have used the same set of samples for both hypotheses and pseudoreferences which is a 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 10We 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 in parallel on a cluster of 1000 machines.Each setting (budget, hypothesis length) takes around 15 minutes to run.  


Decision: 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".

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: The paper brings an interesting new idea to MBR decoding. However, their contribution is claimed ambiguously. 

- 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.
- 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.
questions: 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.
- 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.
- What is the definition of O(millions) and O(hundreds)?  (Line 171)
- 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.
- 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.

Typos
- Line 51: effectiveness of out method → effectiveness of our method
- Line 91: a NMT model → an NMT model
- Line 155: Figure A.6 and Table 4.2 → I guess Figure 5 and Table 1
- Line 196: SPM tokens → no definition of SPM
- Line 197: Note:
- Line 414 Algorithm 2: There are N and n that I believe they both refer to the same parameter.
- Line 431: The sentence is incomplete.
- Line 513, 522: Doesn’t MQM involve human subjects?
limitations: limitations: I think the paper does not explicitly explain the critical limitations of the method.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 
- 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.
questions: questions: Questions:
- 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.

Suggestions:
- 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. 
- line 155: Figure A.6 and Table 4.2 (?)  -> please check the references.
- 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: 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.
paper_summary: paper_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 
- the authors first justify the use of their method by showing that the utility matrix in MBR decoding is indeed low rank
- 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
strength_weakness: strength_weakness: - 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 
- using matrix completion method to lower the cost for computation intensive tasks itself is not a novel approach 
- PMBR is compared against other MBR decoding related methods but not compared against e.g. naive beam search
questions: 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: limitations: - yes the authors addressed the limitations
- and there is no potential societal impact
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
- See my questions below for other things.

Tower: An Open Multilingual Large Language Model for Translation-Related Tasks (Alves et al., 2024)

Quality-Aware Decoding for Neural Machine Translation (Fernandes et al., 2022)
questions: questions: Comments and questions:
- 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. 
- 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.
- 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.
- The results in the tables are averaged over 1000 trials. Can you please provide standard deviations too?

Minor comments:
- Fix citation style in L84 (no parenthesis) and L86 (missing whitespace).
- Missing punctuation in Eq. 2.
- Missing whitespace in L202.
limitations: limitations: Yes.

Comments: comment: Thank you for your response and the additional experimental results with SVT and the greedy decoding baseline. i agree that ALS  is a simple yet efficient matrix completion algorithm for this use case. I will raise my score to 6.
Thank you for extra experiments.

I feel this work is solid enough with meaningful comparisons.
Thank you very much for the clarification.

My position is unchanged. The paper brings an interesting new idea to the field of MBR decoding. Yet, it is not compared against the recent algorithms which makes it unclear if it is on par with the existing work in benchmarks. I think the comparison should not be future work and this is the paper that should conduct the comparison if it is to be claimed as a state-of-the-art method.
Thank you for answering my questions. After reading the rebuttal and the other reviews, I think that incorporating some of this discussion in the updated version of the paper, including the limitations you mentioned above, is a good idea.