Proxy-guided Sampling for Robust Probabilistic Minimum Bayes Risk Decoding

Minimum Bayes Risk (MBR) decoding yields superior generation quality but suffers from a severe $O(N^2)$ computational bottleneck due to pairwise matrix calculation between candidates and pseudo-references. Probabilistic MBR (PMBR) mitigates this by randomly sampling several candidate–pseudo-reference pairs and utilizing Alternating Least Squares (ALS) to approximate the full pairwise matrix. However, randomly sampling the pairs may select uninformative data and starve the ALS of critical pairs. We introduce Bootstrap PMBR (B-PMBR), a framework that utilizes proxy-guided sampling to address this inefficiency. By leveraging model log-probabilities as a proxy score, B-PMBR selects the most influential pairs for evaluation by the utility function. Our extensive experiments demonstrate that B-PMBR consistently exceeds PMBR, especially at low reference sizes, and remains highly competitive with standard MBR. This competitiveness is driven by B-PMBR's ability to mitigate utility metric overfitting, which degrades generalization quality in standard MBR. Finally, ablation studies validate that utilizing model log-probabilities and normalizing the sampled utility scores prior to ALS are critical stabilizing steps for creating a robust, low-error approximation of the ground-truth matrix.