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

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.

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. - I believe that framing this as matrix completion problem is a novel approach. - 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. - 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

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.

Rating

7

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.

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

Strengths

- the method they propose is a simple yet effective one to shrink the computational cost for MBR decoding in NMT task - 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 - 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

- 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?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

- yes the authors addressed the limitations - and there is no potential societal impact

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.

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]. - 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. [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. - 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: - 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.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

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.

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.

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. - The observation that the utility matrix is low rank is interesting and is a contribution to the community. - Human evaluation is nice to have.

Weaknesses

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

- 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?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

4

Limitations

I think the paper does not explicitly explain the critical limitations of the method.