What Our MBR Decoding Guarantee Says

Guide to Theoretical Guarantees for Minimum Bayes Risk Decoding .

Minimum Bayes Risk (MBR) decoding selects an output by maximizing expected utility under a target distribution. In practice, that expectation is estimated using a finite reference set sampled from a language model. Our paper studies how close this finite-sample decision is to the ideal MBR decision.

The question

Empirically, MBR tends to improve as the reference set grows. The central theoretical question is whether we can quantify that improvement even though the set of possible language outputs is vastly larger than the sampled reference set.

The main result

Under the assumptions stated in the paper, MBR decoding approaches the optimal solution with high probability at a rate of O(n^−1/2), where n is the size of the reference hypothesis set. The bound does not scale directly with the total number of possible language outputs.

Comparison with MAP decoding

The paper also derives a performance gap for maximum-a-posteriori (MAP) decoding within the same framework. The comparison identifies several cases in which the MBR bound converges faster than the MAP bound. This provides a theoretical explanation for part of the empirical advantage previously observed for MBR.

What the result does—and does not—say

The result quantifies how reference-set size affects the finite-sample MBR decision under explicit assumptions. It does not say that every utility function or sampling distribution will work equally well. Those choices still determine which notion of output quality is being optimized and how closely the practical setup matches the theory.

For the assumptions, theorem statements, proofs, and full MAP comparison, see the ACL 2025 paper.