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

arXiv: https://arxiv.org/abs/2406.02832 · HTML: https://mlsanity.com/paper/2406.02832/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 39 references that are in the map.
- First posted on arXiv 5 Jun 2024.

## Builds on (most cited first, 22 of 22)

- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [BLEURT: Learning Robust Metrics for Text Generation](https://mlsanity.com/paper/2004.04696/) (2020)
- [COMET: A Neural Framework for MT Evaluation](https://mlsanity.com/paper/2009.09025/) (2020)
- [Experts, Errors, and Context: A Large-Scale Study of Human Evaluation for Machine Translation](https://mlsanity.com/paper/2104.14478/) (2021)
- [Is MAP Decoding All You Need? The Inadequacy of the Mode in Neural Machine Translation](https://mlsanity.com/paper/2005.10283/) (2020)
- [Analyzing Uncertainty in Neural Machine Translation](https://mlsanity.com/paper/1803.00047/) (2018)
- [Truncation Sampling as Language Model Desmoothing](https://mlsanity.com/paper/2210.15191/) (2022)
- [BLEU might be Guilty but References are not Innocent](https://mlsanity.com/paper/2004.06063/) (2020)
- [High Quality Rather than High Model Probability: Minimum Bayes Risk Decoding with Neural Metrics](https://mlsanity.com/paper/2111.09388/) (2021)
- [Sampling-Based Approximations to Minimum Bayes Risk Decoding for Neural Machine Translation](https://mlsanity.com/paper/2108.04718/) (2021)
- [Epsilon Sampling Rocks: Investigating Sampling Strategies for Minimum Bayes Risk Decoding for Machine Translation](https://mlsanity.com/paper/2305.09860/) (2023)
- [Understanding the Properties of Minimum Bayes Risk Decoding in Neural Machine Translation](https://mlsanity.com/paper/2105.08504/) (2021)
- [Low-Rank Matrix Completion: A Contemporary Survey](https://mlsanity.com/paper/1907.11705/) (2019)
- [Identifying Weaknesses in Machine Translation Metrics Through Minimum Bayes Risk Decoding: A Case Study for COMET](https://mlsanity.com/paper/2202.05148/) (2022)
- [Faster Minimum Bayes Risk Decoding with Confidence-based Pruning](https://mlsanity.com/paper/2311.14919/) (2023)
- [MBR and QE Finetuning: Training-time Distillation of the Best and Most Expensive Decoding Methods](https://mlsanity.com/paper/2309.10966/) (2023)
- [Linear-time Minimum Bayes Risk Decoding with Reference Aggregation](https://mlsanity.com/paper/2402.04251/) (2024)
- [Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2401.02749/) (2024)
- [Training and Meta-Evaluating Machine Translation Evaluation Metrics at the Paragraph Level](https://mlsanity.com/paper/2308.13506/) (2023)
- [Quality-Aware Translation Models: Efficient Generation and Quality Estimation in a Single Model](https://mlsanity.com/paper/2310.06707/) (2023)

## Built on by (most cited first, 13 of 13)

- [Mitigating Metric Bias in Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2411.03524/) (2024)
- [mbrs: A Library for Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2408.04167/) (2024)
- [Diversity Explains Inference Scaling Laws: Through a Case Study of Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2410.15021/) (2024)
- [A Bayesian Optimization Approach to Machine Translation Reranking](https://mlsanity.com/paper/2411.09694/) (2024)
- [A Context-aware Framework for Translation-mediated Conversations](https://mlsanity.com/paper/2412.04205/) (2024)
- [Early-Exit and Instant Confidence Translation Quality Estimation](https://mlsanity.com/paper/2502.14429/) (2025)
- [Re-evaluating Minimum Bayes Risk Decoding for Automatic Speech Recognition](https://mlsanity.com/paper/2510.19471/) (2025)
- [Agreement-Constrained Probabilistic Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2512.01316/) (2025)
- [Case-Based Decision-Theoretic Decoding with Quality Memories](https://mlsanity.com/paper/2509.12677/) (2025)
- [Document-Level Text Generation with Minimum Bayes Risk Decoding using Optimal Transport](https://mlsanity.com/paper/2505.23078/) (2025)
- [Enhancing Factuality through Consensus and Consistency in Summarization Using Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2605.29336/) (2026)
- [Quit While You're Ahead: Quit for Efficient Candidate Generation in Machine Translation Reranking](https://mlsanity.com/paper/2609.00588/) (2026)
- [Overfitting Mitigation via Singular Value Decomposition in Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2609.01135/) (2026)

## Abstract (arXiv)

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 the task of machine 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 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 a 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 vanilla MBR decoding while achieving equal translation quality measured by COMET22 on the WMT22 dataset (en<>de and en<>ru). We also benchmark our method against other approximation methods and we show gains in quality when comparing to them.