Theoretical Guarantees for Minimum Bayes Risk Decoding

• URL: http://arxiv.org/abs/2502.12685v1
• Date: Tue, 18 Feb 2025 09:43:15 GMT
• Title: Theoretical Guarantees for Minimum Bayes Risk Decoding
• Authors: Yuki Ichihara, Yuu Jinnai, Kaito Ariu, Tetsuro Morimura, Eiji Uchibe,
• Abstract summary: We show that Minimum Bayes Risk (MBR) decoding approaches the optimal solution with high probability at a rate of $Oleft(n-frac12right)$. This result helps to theoretically explain the strong performance observed in several prior empirical studies on MBR decoding.
• Score: 4.421486904657393
• License:
• Abstract: Minimum Bayes Risk (MBR) decoding optimizes output selection by maximizing the expected utility value of an underlying human distribution. While prior work has shown the effectiveness of MBR decoding through empirical evaluation, few studies have analytically investigated why the method is effective. As a result of our analysis, we show that, given the size $n$ of the reference hypothesis set used in computation, MBR decoding approaches the optimal solution with high probability at a rate of $O\left(n^{-\frac{1}{2}}\right)$, under certain assumptions, even though the language space $Y$ is significantly larger $Y\gg n$. This result helps to theoretically explain the strong performance observed in several prior empirical studies on MBR decoding. In addition, we provide the performance gap for maximum-a-posteriori (MAP) decoding and compare it to MBR decoding. The result of this paper indicates that MBR decoding tends to converge to the optimal solution faster than MAP decoding in several cases.

Related papers

• A Theoretical Perspective for Speculative Decoding Algorithm [60.79447486066416]
  One effective way to accelerate inference is emphSpeculative Decoding, which employs a small model to sample a sequence of draft tokens and a large model to validate. This paper tackles this gap by conceptualizing the decoding problem via markov chain abstraction and studying the key properties, emphoutput quality and inference acceleration, from a theoretical perspective.
  arXiv  Detail & Related papers  (2024-10-30T01:53:04Z)
• Better Instruction-Following Through Minimum Bayes Risk [48.879360919760074]
  General-purpose LLM judges capable of human-level evaluation provide a scalable and accurate way of evaluating instruction-following LLMs. One promising way of leveraging LLM judges for supervision is through Minimum Bayes Risk (MBR) decoding. MBR decoding uses a reference-based evaluator to select a high-quality output from amongst a set of candidate outputs.
  arXiv  Detail & Related papers  (2024-10-03T18:48:38Z)
• Unveiling the Power of Source: Source-based Minimum Bayes Risk Decoding for Neural Machine Translation [30.323103270892734]
  Maximum a posteriori decoding, a commonly used method for neural machine translation (NMT), aims to maximize the estimated posterior probability. Minimum Bayes Risk (MBR) decoding offers an alternative by seeking hypotheses with the highest expected utility. Our findings suggest that sMBR is a promising approach for NMT decoding.
  arXiv  Detail & Related papers  (2024-06-17T15:13:52Z)
• Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms [19.543681023903456]
  We formulate Minimum Bayes Risk (MBR) decoding as a matrix completion problem. We exploit this by only computing a random subset of the scores and efficiently recover the missing entries in the matrix. Our experimental results on machine translation tasks demonstrate that the proposed method requires 1/16 utility metric computations.
  arXiv  Detail & Related papers  (2024-06-05T00:54:03Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED) is a highly effective approach to the multi-armed bandit problem. It has been observed to empirically outperform UCB-based algorithms and Thompson Sampling. We present novel linear versions of the IMED algorithm, which we call the family of LinIMED algorithms.
  arXiv  Detail & Related papers  (2024-05-24T04:11:58Z)
• Centroid-Based Efficient Minimum Bayes Risk Decoding [38.04403087991526]
  Minimum Bayes risk (MBR) decoding achieved state-of-the-art translation performance by using COMET. MBR decoding requires quadratic time since it computes the expected score between a translation hypothesis and all reference translations. Our method clusters the reference translations in the feature space, and then calculates the score using the centroids of each cluster.
  arXiv  Detail & Related papers  (2024-02-17T05:15:12Z)
• Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
  Minimum Bayes Risk (MBR) decoding is a text generation technique that has been shown to improve the quality of machine translations. It requires the pairwise calculation of a utility metric, which has quadratic complexity. We propose to approximate pairwise metric scores with scores calculated against aggregated reference representations.
  arXiv  Detail & Related papers  (2024-02-06T18:59:30Z)
• Faster Minimum Bayes Risk Decoding with Confidence-based Pruning [8.709382540743391]
  We describe an algorithm for Minimum Bayes risk (MBR) decoding which gradually grows the number of samples used to estimate the utility. Our method requires fewer samples and drastically reduces the number of calls to the utility function compared to standard MBR. We demonstrate the effectiveness of our approach in experiments on three language pairs, using chrF++ and COMET as utility/evaluation metrics.
  arXiv  Detail & Related papers  (2023-11-25T03:38:14Z)
• Quality-Aware Translation Models: Efficient Generation and Quality Estimation in a Single Model [77.19693792957614]
  We propose to make neural machine translation (NMT) models quality-aware by training them to estimate the quality of their own output. We obtain quality gains similar or even superior to quality reranking approaches, but with the efficiency of single pass decoding.
  arXiv  Detail & Related papers  (2023-10-10T15:33:51Z)
• It's MBR All the Way Down: Modern Generation Techniques Through the Lens of Minimum Bayes Risk [57.641436861482696]
  Minimum Bayes Risk (MBR) decoding is a method for choosing the outputs of a machine learning system based not on the output with the highest probability, but the output with the lowest risk (expected error) among multiple candidates.
  arXiv  Detail & Related papers  (2023-10-02T17:47:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.