# Faster Minimum Bayes Risk Decoding with Confidence-based Pruning

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 24 references that are in the map.
- First posted on arXiv 25 Nov 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [A Call for Clarity in Reporting BLEU Scores](https://mlsanity.com/paper/1804.08771/) (2018)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (2019)
- [COMET: A Neural Framework for MT Evaluation](https://mlsanity.com/paper/2009.09025/) (2020)
- [Is MAP Decoding All You Need? The Inadequacy of the Mode in Neural Machine Translation](https://mlsanity.com/paper/2005.10283/) (2020)
- [Natural Language to Code Translation with Execution](https://mlsanity.com/paper/2204.11454/) (2022)
- [Truncation Sampling as Language Model Desmoothing](https://mlsanity.com/paper/2210.15191/) (2022)
- [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)
- [Follow the Wisdom of the Crowd: Effective Text Generation via Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2211.07634/) (2022)
- [It's MBR All the Way Down: Modern Generation Techniques Through the Lens of Minimum Bayes Risk](https://mlsanity.com/paper/2310.01387/) (2023)

## Built on by (most cited first, 30 of 34)

- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [Regularized Best-of-N Sampling with Minimum Bayes Risk Objective for Language Model Alignment](https://mlsanity.com/paper/2404.01054/) (2024)
- [Linear-time Minimum Bayes Risk Decoding with Reference Aggregation](https://mlsanity.com/paper/2402.04251/) (2024)
- [Mitigating Metric Bias in Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2411.03524/) (2024)
- [Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2401.02749/) (2024)
- [Regression-aware Inference with LLMs](https://mlsanity.com/paper/2403.04182/) (2024)
- [Don't Rank, Combine! Combining Machine Translation Hypotheses Using Quality Estimation](https://mlsanity.com/paper/2401.06688/) (2024)
- [Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms](https://mlsanity.com/paper/2406.02832/) (2024)
- [Improving Minimum Bayes Risk Decoding with Multi-Prompt](https://mlsanity.com/paper/2407.15343/) (2024)
- [mbrs: A Library for Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2408.04167/) (2024)
- [Centroid-Based Efficient Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2402.11197/) (2024)
- [Generating Diverse and High-Quality Texts by Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2401.05054/) (2024)
- [Uncertainty-Aware Decoding with Minimum Bayes Risk](https://mlsanity.com/paper/2503.05318/) (2025)
- [Introducing the NewsPaLM MBR and QE Dataset: LLM-Generated High-Quality Parallel Data Outperforms Traditional Web-Crawled Data](https://mlsanity.com/paper/2408.06537/) (2024)
- [Don't Throw Away Data: Better Sequence Knowledge Distillation](https://mlsanity.com/paper/2407.10456/) (2024)
- [Diversity Explains Inference Scaling Laws: Through a Case Study of Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2410.15021/) (2024)
- [Test-Time Scaling in Reasoning LLMs: Inference Regimes, Evaluation, and Reproducibility](https://mlsanity.com/paper/2608.04001/) (2026)
- [Theoretical Guarantees for Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2502.12685/) (2025)
- [On the True Distribution Approximation of Minimum Bayes-Risk Decoding](https://mlsanity.com/paper/2404.00752/) (2024)
- [A Bayesian Optimization Approach to Machine Translation Reranking](https://mlsanity.com/paper/2411.09694/) (2024)
- [Early-Exit and Instant Confidence Translation Quality Estimation](https://mlsanity.com/paper/2502.14429/) (2025)
- [Optimal Policy Minimum Bayesian Risk](https://mlsanity.com/paper/2505.17242/) (2025)
- [Re-evaluating Minimum Bayes Risk Decoding for Automatic Speech Recognition](https://mlsanity.com/paper/2510.19471/) (2025)
- [Structure-Conditional Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2510.20700/) (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)
- [Minimum Bayes Risk Decoding for Error Span Detection in Reference-Free Automatic Machine Translation Evaluation](https://mlsanity.com/paper/2512.07540/) (2025)
- [Consensus Group Relative Policy Optimization for Text Generation](https://mlsanity.com/paper/2602.03102/) (2026)
- [Uncertainty-Aware Generation and Decision-Making Under Ambiguity](https://mlsanity.com/paper/2606.30578/) (2026)
- [Unveiling the Power of Source: Source-based Minimum Bayes Risk Decoding for Neural Machine Translation](https://mlsanity.com/paper/2406.11632/) (2024)

## Abstract (arXiv)

Minimum Bayes risk (MBR) decoding outputs the hypothesis with the highest expected utility over the model distribution for some utility function. It has been shown to improve accuracy over beam search in conditional language generation problems and especially neural machine translation, in both human and automatic evaluations. However, the standard sampling-based algorithm for MBR is substantially more computationally expensive than beam search, requiring a large number of samples as well as a quadratic number of calls to the utility function, limiting its applicability. We describe an algorithm for MBR which gradually grows the number of samples used to estimate the utility while pruning hypotheses that are unlikely to have the highest utility according to confidence estimates obtained with bootstrap sampling. Our method requires fewer samples and drastically reduces the number of calls to the utility function compared to standard MBR while being statistically indistinguishable in terms of accuracy. We demonstrate the effectiveness of our approach in experiments on three language pairs, using chrF++ and COMET as utility/evaluation metrics.