Accelerating Minimum Bayes Risk Decoding

36 concepts29 papers1 proposal

Standard text generation methods typically rely on Maximum A Posteriori (MAP) decoding, which searches for the single most probable sequence under the model's distribution. However, the highest-probability sequence is often not the highest-quality sequence. MAP decoding can suffer from length biases, repetitive loops, or the "beam search curse," where broader searches lead to worse human-evaluated quality.

To address this, Minimum Bayes Risk (MBR) decoding shifts the objective from finding the mode of the distribution to finding the consensus of the distribution. Originally introduced to statistical machine translation by Shankar Kumar et al. in Minimum Bayes-Risk Decoding for Statistical Machine Translation and Izhak Shafran et al. in Task-specific minimum Bayes-risk decoding using learned edit distance, MBR selects a candidate sentence that minimizes expected risk—or maximizes expected utility—relative to the true language distribution.

By using model-generated samples as a proxy for the true distribution, as explored by Nicola Ehling et al. in Minimum Bayes Risk Decoding for BLEU, MBR identifies the candidate that shares the most common ground with all other likely hypotheses. Unfortunately, this consensus-seeking process introduces a severe computational bottleneck that prevents its use in real-time applications.

The Quadratic Bottleneck

To understand why MBR decoding is computationally expensive, consider its mathematical formulation. Given a pool of $N$ generated candidate hypotheses $\mathcal{H} = \{y_1, y_2, \dots, y_N\}$, MBR selects the optimal sequence $\hat{y}$ by maximizing average utility:

$$\hat{y} = \arg\max_{y \in \mathcal{H}} \frac{1}{N} \sum_{i=1}^N U(y, y_i)$$

Here, $U(y, y_i)$ is a utility metric (such as BLEU or COMET) that evaluates the quality of a candidate $y$ against a pseudo-reference $y_i$.

To find the winner, every candidate in the pool must be compared against every other candidate. This requires computing a full $N \times N$ pairwise utility matrix. As highlighted by Zhanglin Wu et al. in Choose the Final Translation from NMT and LLM Hypotheses Using MBR Decoding: HW-TSC's Submission to the WMT24 General MT Shared Task, this process scales quadratically ($O(N^2)$) with the number of samples.

Standard MBR (O(N²)):
[ y₁ ] ---> Compares to [ y₁, y₂, y₃, ..., y_N ]
[ y₂ ] ---> Compares to [ y₁, y₂, y₃, ..., y_N ]
...
[ y_N ] --> Compares to [ y₁, y₂, y₃, ..., y_N ]

When the utility metric $U$ is a simple surface-level string match (like edit distance), the quadratic cost is noticeable but manageable. However, modern text generation relies on deep neural metrics like COMET to capture semantic alignment. Running a large neural network $N^2$ times for a single generation request introduces massive latency, making real-time deployment impossible, as noted by Baohang Li et al. in SCIR-MT's Submission for WMT24 General Machine Translation Task. This overhead is further exacerbated when ensembling multiple utility metrics to prevent reward hacking, a challenge documented by Daniel Deutsch et al. in Mitigating Metric Bias in Minimum Bayes Risk Decoding.

To make MBR practical, a growing body of research focuses on breaking this quadratic bottleneck through matrix completion, geometric clustering, and preference optimization.

Exploiting Matrix Structure via Low-Rank Completion

The core insight behind accelerating MBR via matrix completion is that the $N \times N$ utility matrix contains massive structural redundancy. If a language model samples 128 translations, many of those hypotheses will be semantically identical or minor syntactic variations of one another.

If Candidate A and Candidate B mean the same thing, their similarity scores against all other candidates in the pool will be nearly identical. Consequently, their respective rows and columns in the utility matrix will be highly correlated, meaning the full matrix has a very low effective rank.

Firas Trabelsi et al. exploit this property in Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms. Instead of calculating all $N^2$ entries, the authors compute only a sparse, random fraction of the matrix (e.g., 1/16th of the entries). They then apply an Alternating Least Squares (ALS) matrix completion algorithm to fill in the missing values. This approach achieves a 16x speedup with virtually no loss in final translation quality.

Low-Rank Matrix Completion:
[ U₁₁   ?    ?   U₁₄ ]          [ U₁₁  U₁₂  U₁₃  U₁₄ ]
[  ?   U₂₂   ?    ?  ]  --ALS-> [ U₂₁  U₂₂  U₂₃  U₂₄ ]
[  ?    ?   U₃₃   ?  ]          [ U₃₁  U₃₂  U₃₃  U₃₄ ]
[ U₄₁   ?    ?   U₄₄ ]          [ U₄₁  U₄₂  U₄₄  U₄₄ ]
 (Compute only ~1/16th)            (Reconstruct Full Matrix)

To further refine this reconstruction, Koki Natsumi et al. developed Agreement-Constrained Probabilistic MBR (AC-PMBR) in Agreement-Constrained Probabilistic Minimum Bayes Risk Decoding. Instead of sampling entries purely at random, the authors use a computationally cheap, non-neural metric (like BLEU) to compute a complete proxy matrix instantly. They use the geometric structure of this cheap matrix as a prior constraint to guide the low-rank completion of the expensive neural metric (like COMET), maximizing both speed and semantic accuracy.

Geometric Pruning and Clustering

Another strategy avoids computing the full matrix by grouping similar hypotheses together in a continuous embedding space, transforming the problem from exhaustive pairwise comparison to geometric search.

In Centroid-Based Efficient Minimum Bayes Risk Decoding, Hiroyuki Deguchi et al. propose projecting all candidate sentences into a latent feature space and clustering them. Instead of evaluating every single candidate against every other candidate, the utility of each hypothesis is computed only against the centroids of these clusters. This reduces the computational complexity from $O(N^2)$ to $O(N \cdot K)$, where $K$ is the number of clusters ($K \ll N$).

Centroid-Based MBR (O(N · K)):
Candidates       Clusters & Centroids
[ y₁ ] ------->  Centroid 1 (Group of similar sentences)
[ y₂ ] ------->  Centroid 2 (Group of alternative phrasings)
[ y₃ ] ------->  ...

Alternatively, MBR can be framed as a medoid identification problem—finding the most central point in a spatial cluster of data points. Yuu Jinnai et al. leverage this perspective in Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decoding by introducing Adaptive MBR (AMBR).

Using sequential elimination techniques borrowed from multi-armed bandits, AMBR evaluates candidates against a small subset of random references first. If a candidate performs poorly in these initial rounds, it is statistically impossible for it to become the ultimate consensus winner. The algorithm adaptively prunes these low-performing candidates early, avoiding the need to compute their remaining pairwise utilities. This builds upon the coarse-to-fine sampling frameworks pioneered by Bryan Eikema et al. in Sampling-Based Approximations to Minimum Bayes Risk Decoding for Neural Machine Translation, ensuring that computational resources are spent only on distinguishing between the top-tier consensus candidates.

Amortizing Risk via Direct Preference Optimization

While matrix completion and clustering significantly reduce the runtime overhead of MBR, they still require generating multiple samples and performing test-time calculations. The most radical acceleration strategy eliminates the test-time overhead entirely by moving the computational burden to the training phase.

Guangyu Yang et al. introduce this concept in Direct Preference Optimization for Neural Machine Translation with Minimum Bayes Risk Decoding. Instead of running MBR at inference time, the authors use MBR as an offline teacher during model training.

Offline Training Phase (Amortization):
[Model Samples] ---> Run Expensive MBR ---> Winner (Preferred) vs Loser (Dispreferred)
                                                    |
                                        Direct Preference Optimization (DPO)
                                                    |
                                                    v
Inference Phase:
[Input Text] -------> [Fine-Tuned Model] -------> Single Greedy Pass (O(1) MBR Overhead)

For a given training prompt, the model generates a pool of candidates, and the expensive, standard $O(N^2)$ MBR process is executed offline to identify the consensus winner. The MBR winner is labeled as the "preferred" sequence, while the remaining candidates are labeled as "dispreferred."

The model is then fine-tuned on this dataset using Direct Preference Optimization (DPO). This process directly updates the model's weights to assign higher probability to consensus-style outputs. At inference time, the model internalizes the MBR selection criteria, allowing it to generate high-quality, consensus-aligned text in a single, standard greedy or beam search pass—reducing the operational overhead of MBR to $O(1)$.

Key Foundational Work

Task-specific minimum Bayes-risk decoding using learned edit distance (2004) — contributed 3 concept elements to this direction.
Minimum Bayes-Risk Decoding for Statistical Machine Translation (2004) — contributed 1 concept elements to this direction.
Minimum Bayes Risk Decoding for BLEU (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quadratic_decoding_complexity_a1f71c09,
  title = {quadratic decoding complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-decoding-complexity/rdr_a1f71c098cc348ce9f8f38e42c4fb985},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_quadratic_decoding_complexity_a1f71c09_v1,
  title = {quadratic decoding complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-decoding-complexity/rdr_a1f71c098cc348ce9f8f38e42c4fb985/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake