Research map / Learning theory and algorithms / Matrix and tensor methods
Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PMBR, which approximates MBR decoding for machine translation by computing a random subset of pairwise utility scores and recovering the rest via ALS low-rank matrix completion.
Problem
MBR decoding has quadratic cost in the number of candidates, and each pairwise utility computation is an expensive neural-metric forward pass, limiting practical use in machine translation.
Approach
Treat the pairwise MBR utility matrix as approximately low-rank, observe only a random subset of its entries (a fraction of the full cost), complete the matrix with alternating least squares, and then run vanilla MBR on the completed matrix.
Key results
- PMBR matches full MBR COMET-22 quality (en-de 83.63 vs 83.52 FMBR at 1/16 budget with N=128) using 1/16 of utility computations.
- PMBR outperforms N x K and S x S approximation baselines at every budget tested on COMET-22.
- Singular value analysis shows sigma_2/sigma_1 < 0.05 on average, supporting a near rank-1 structure of MBR matrices.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PMBR instead of full MBR with a 1/16 computation budget | PaLM8B translation on WMT22 en→de · WMT22 en→de | COMET22: 83.52 -> 83.63 | No clear effect |
| Use PMBR instead of N×K at a 1/16 computation budget | PaLM8B translation on WMT22 en→de · WMT22 en→de | COMET22: 82.90 -> 83.63 | Helped |
| Use PMBR instead of S×S at a 1/16 computation budget | PaLM8B translation on WMT22 en→de · WMT22 en→de | COMET22: 83.52 -> 83.63 | Helped |
| Use PMBR instead of full MBR with a 1/16 computation budget | PaLM8B translation on WMT22 de→en · WMT22 de→en | COMET22: 79.97 -> 80.01 | No clear effect |
| Use PMBR instead of N×K at a 1/16 computation budget | PaLM8B translation on WMT22 de→en · WMT22 de→en | COMET22: 79.87 -> 80.01 | Helped |
| Use PMBR instead of S×S at a 1/16 computation budget | PaLM8B translation on WMT22 de→en · WMT22 de→en | COMET22: 79.91 -> 80.01 | Helped |
| Use PMBR instead of full MBR with a 1/16 computation budget | PaLM8B translation on WMT22 en→ru · WMT22 en→ru | COMET22: 83.52 -> 83.63 | No clear effect |
| Use PMBR instead of N×K at a 1/16 computation budget | PaLM8B translation on WMT22 en→ru · WMT22 en→ru | COMET22: 82.90 -> 83.63 | Helped |
| Use PMBR instead of S×S at a 1/16 computation budget | PaLM8B translation on WMT22 en→ru · WMT22 en→ru | COMET22: 83.52 -> 83.63 | Helped |
| Use PMBR instead of full MBR with a 1/16 computation budget | PaLM8B translation on WMT22 ru→en · WMT22 ru→en | COMET22: 79.17 -> 79.23 | No clear effect |
| Use PMBR instead of N×K at a 1/16 computation budget | PaLM8B translation on WMT22 ru→en · WMT22 ru→en | COMET22: 78.99 -> 79.23 | Helped |
| Use PMBR instead of S×S at a 1/16 computation budget | PaLM8B translation on WMT22 ru→en · WMT22 ru→en | COMET22: 79.06 -> 79.23 | Helped |
Surprising findings
- MetricX scores slightly drop as the budget shrinks while COMET-22 holds, which the authors interpret as a regularization effect.
- The MBR utility matrices are close to rank-1, so a dominant single component captures most of the information.
Limitations
- Only MetricX was used as the utility function for the main experiments.
- Human MQM evaluation is small (65 examples), limiting statistical significance.
- Coherence of the MBR matrices was not analyzed empirically.
Experimental setup
Datasets: WMT22 en-de WMT22 de-en WMT22 en-ru WMT22 ru-en FLORES (few-shot examples)
Benchmarks: WMT22
Metrics: COMET-22 MetricX MQM chrF
Baselines: FMBR NxK MBR SxS MBR
Builds on: minimum bayes risk decoding epsilon sampling alternating least squares
Closest papers by meaning
- Model-Based Minimum Bayes Risk Decoding for Text Generation (ICML 2024 · similarity 0.90)
- Uncertainty-Aware Decoding with Minimum Bayes Risk (ICLR 2025 · similarity 0.87)
- MBR and QE Finetuning: Training-time Distillation of the Best and Most Expensive Decoding Methods (ICLR 2024 · similarity 0.86)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.83)
- Approximately Aligned Decoding (NeurIPS 2025 · similarity 0.83)
- A Theoretical Perspective for Speculative Decoding Algorithm (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.