acceptodds
Under review as a conference paper at ICLR 2027

Proxy-guided Sampling for Robust Probabilistic Minimum Bayes Risk Decoding

Abstract

Minimum Bayes Risk (MBR) decoding yields superior generation quality but suffers from a severe 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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
mbr decoding, probabilistic mbr decoding, proxy-guided sampling

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_36DUOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Bootstrap Probabilistic Minimum Bayes Risk (B-PMBR) decoding to reduce the computational cost of MBR decoding. Unlike PMBR, which randomly samples candidate–pseudo-reference pairs, B-PMBR uses model log-probabilities to guide pair selection. It explores three sampling strategies: Top-k, Edge-k, and Gumbel-Top-k. The method also applies z-score normalization before ALS-based matrix completion.

The authors evaluate B-PMBR on WMT22 English–German translation using multiple utility functions, evaluation metrics, and reference sizes. The results show that B-PMBR generally outperforms PMBR, especially with small reference sets, while remaining competitive with full MBR. The paper also reports improved cross-metric evaluation scores in some settings and provides ablation studies on proxy selection and normalization.

Critical strengths

1. Simple and Practical Method

The paper addresses a clear computational bottleneck in MBR decoding. The proposed method is simple and does not require training an additional model. It achieves better generation quality than PMBR in many settings under the same utility evaluation budget, especially with small reference sets. This makes it a practical improvement for efficient MBR decoding.

2. Solid Experimental Validation

The paper evaluates multiple utility functions, sampling strategies, and reference sizes. It also includes runtime comparisons, statistical tests, and ablation studies. These experiments provide useful evidence of the method's effectiveness. The paper is also well organized and easy to follow.

Critical weaknesses

1. Unclear Definition and Justification of Informative Pairs

The paper does not clearly define what makes a pair informative for matrix completion. The proposed proxy simply adds the log-probabilities of two sequences. Why should a high proxy score indicate that a pair is more informative? The paper lacks direct evidence supporting this assumption. This weakens the justification for the main method.

2. Sensitivity to Normalization

Figure 4 shows that B-PMBR, especially Top-k and Edge-k, can have much larger reconstruction errors without z-score normalization than PMBR. Why is the proposed sampling method more sensitive to normalization? Does this suggest that proxy-guided sampling introduces additional instability into ALS? This raises concerns about the robustness of the proposed method.

Questions for authors

1. Informativeness of Proxy Scores

How is the informativeness of a candidate–reference pair defined? Why should the sum of two sequence-level log-probabilities identify informative pairs?

2. Sensitivity to Normalization

Figure 4 shows that B-PMBR can have much larger reconstruction errors without normalization, especially for Top-k and Edge-k. What causes this instability? Does proxy-guided sampling introduce additional instability into ALS?

3. Utility Metric Overfitting

The paper claims that B-PMBR mitigates utility metric overfitting. However, the generalized quality score appears to include the optimized utility metric. Can the authors clarify how this score is computed? Does the improvement remain when the optimized metric is excluded?

4. Consistency of Experimental Results

Some reported generalized quality scores differ across tables. For example, with COMET utility and four references, PMBR obtains -11.82 in Table 1 but -1.68 in Appendix Table 4. What causes this difference? Are different normalization procedures or experimental settings used?

5. Overstated Claims

Some claims appear stronger than the reported results. For example, B-PMBR does not consistently outperform PMBR across all configurations. In Table 2, the log-probability proxy is also not always the best or second-best option.

7 comments
AuthorsOpenReview ↗

Rebuttal by Authors (Part 1)

We would like to thank you for acknowledging our simple and practical approach, extensive experiments, and our easy-to-read paper.

To reduce the length of the response to the comment, some of our revisions are incorporated directly into the paper, and we specify the revision location in the corresponding response. To facilitate tracking in the revised manuscript, all changes addressing your comments have been highlighted in Pink and labeled with the corresponding comment number.

In the comment, we only include parts of the results required to answer your questions and comments. We denote our response below based on the number and category of the reviewer’s response, i.e W1 means Weakness no.1 and Q2 means Question no.2.


W1, Q1: Definition of informativeness for ALS matrix completion

Thank you for your comment. We have included our detailed discussion in Appendix I of the revised version.

As noted in Lines 138–145, our proxy scorer estimates the joint probability that a candidate and pseudo-reference pair is high-quality according to the generation model. Our goal is not perfect recovery of the full pairwise matrix because MBR only needs the argmax of u^\hat{u}, so we consider a pair informative if observing it improves the estimate of u^\hat{u} for candidates likely to compete for the argmax. In ALS, each candidate’s latent factor is fitted to that candidate’s observed entries, and with standardized scores, candidates with few observations are shrunk toward the mean utility. Therefore, the sampler determines which candidates have their expected utility estimated from actual utility scores.

Furthermore, to evaluate how well normalized sequence log-probabilities guide estimation on competitive candidates, we measure

  1. the absolute expected utility error ∣Δu^(hMBR)∣=∣u^rec(hMBR)−u^MBR(hMBR)∣\lvert \Delta \hat{u}(h_{\mathrm{MBR}}) \rvert = \lvert \hat{u}_{\mathrm{rec}}(h_{\mathrm{MBR}}) - \hat{u}_{\mathrm{MBR}}(h_{\mathrm{MBR}}) \rvert, and
  2. the MBR agreement rate, i.e., the percentage of source sentences where a method selects hMBR{h}_{MBR} (representative BLEU and COMET results below; all five metrics across M∈{4,…,256}M \in \{4, \dots, 256\} are in Appendix I of the revised version):
MetricMethod∣Δu^(hMBR)∣↓\vert\Delta \hat{u}(h_{\mathrm{MBR}})\vert\downarrow M=4M=4∣Δu^(hMBR)∣↓\vert\Delta \hat{u}(h_{\mathrm{MBR}})\vert\downarrow M=32M=32∣Δu^(hMBR)∣↓\vert\Delta \hat{u}(h_{\mathrm{MBR}})\vert\downarrow M=256M=256Agreement (%)↑\uparrow M=4M=4Agreement (%)↑\uparrow M=32M=32Agreement (%)↑\uparrow M=256M=256
BLEUPMBR37.6618.404.284.04.49.9
Normed PMBR16.258.751.297.34.515.6
B-PMBR (Top-kk)6.925.054.9737.143.342.5
B-PMBR (Edge-kk)10.565.185.0027.528.919.0
B-PMBR (Gumbel-Top-kk)14.976.570.907.66.924.8
COMETPMBR0.7020.3160.0091.04.237.2
Normed PMBR0.0980.0640.0055.47.349.4
B-PMBR (Top-kk)0.0350.0270.02328.938.641.1
B-PMBR (Edge-kk)0.0800.0670.05817.317.418.5
B-PMBR (Gumbel-Top-kk)0.0900.0510.0045.49.352.2

At small reference sizes (M≤64M \leq 64), B-PMBR estimates the expected utility of hMBR{h}_{MBR} far more accurately than uniform sampling. Specifically, Top-kk achieves the lowest ∣Δu^(hMBR)∣\lvert\Delta \hat{u}(h_{\mathrm{MBR}})\rvert across all five utility functions before Gumbel-Top-kk and PMBR variants overtake it at larger MM, selecting the same candidate as MBR in 29–42% of source sentences as shown in the representative table. This low estimation error confirms that hMBR{h}_{MBR} typically carries high model probability, allowing B-PMBR to estimate its expected utility from explicit metric scores rather than latent factor extrapolation, even though B-PMBR has higher global matrix reconstruction error than PMBR and Normed PMBR. As MM grows, uniform sampling observes enough entries per row to lower its estimation error, whereas Top-kk and Edge-kk plateau because unselected candidates remain unobserved.

continued in the next part

AuthorsOpenReview ↗

Rebuttal by Authors (Part 2)

Thus, we view the utility metric and the model’s log-probability as two imperfect estimates of translation quality that approach it from different directions. Neither is reliable alone, where utility metrics can overfit to that metric bias, while model probability is known to favor inadequate outputs [1]. Because their failure modes differ, combining them is more robust than either. We examine how the two signals relate by computing Kendall’s τ\tau between each proxy matrix and the ground-truth utility matrix (WMT-22 En→De, averaged over M∈{4,…,256}M \in \{4, \dots, 256\}) (full result in Appendix I of the revised version):

ProxyBLEUchrFCOMETBLEURTBERTScore
Hypothesis-only log⁡P(hn)\log P({h}_{n})0.230.260.320.250.25
Reference-only log⁡P(ym)\log P({y}_{m})0.220.240.150.190.24
Joint (ours)0.330.370.350.330.36

While all proxies correlate positively with every utility metric, the joint proxy consistently aligns best (0.33–0.37), indicating that both sequences in a pair carry quality information (notably, COMET correlates highest under candidate-only probabilities but lowest under pseudo-reference-only probabilities, followed by BLEURT). Crucially, this moderate correlation is what makes the proxy effective. Table 2 shows that when the proxy is the utility metric itself (BLEU proxy–BLEU utility; chrF proxy–chrF utility), Top-kk selects the highest-utility pairs directly yet yields lower Zˉother{\bar{Z}}_{other} than the log-probability proxy (0.170.17 vs. 0.900.90 and −0.75-0.75 vs. 0.950.95). Selecting pairs by the metric alone reinforces its biases, whereas the model-based proxy adds an independent view of quality.

Overall, rather than strictly replicating MBR's final decision, B-PMBR bridges both estimators: pairs are pre-selected by model confidence and explicitly scored by the utility metric, ensuring the selected output is strongly supported by both signals. This explains why diverging from MBR's exact selection reduces metric overfitting in Table 1 and Figure 2—B-PMBR scores slightly lower than MBR on the targeted utility metric, but achieves higher generalized quality (Zˉother{\bar{Z}}_{other}), including on unseen evaluators such as XCOMET and COMETKiwi.


W2, Q2: Sensitivity to normalization

Thank you for your comment. We have added the explanation below to Section 3.3 of our revised manuscript.

Because Top-kk and Edge-kk only sample the extreme points, the reconstruction error is larger compared to PMBR without normalization. The cause is not proxy guidance itself but the coverage prioritizing influential pairs, leaving some candidates with only one or two observed entries.

ALS then fits those rows from very few noisy scores, and on raw metric scales this fails for two reasons: A candidate with no observations keeps a near-zero latent factor, so ALS predicts a score of about 0, far from the true values on raw metric scales. Scaling all scores by a constant cc is equivalent to dividing the ridge penalty by cc. For raw BLEU scores that span tens of points, λ=0.1\lambda = 0.1 provides almost no damping, so a sparsely observed row's predictions fall far outside the metric's range, producing the large, irregular spikes in Figure 4. On raw COMET where the score scales around 0.1, the same λ\lambda is effectively much stronger and shrinks predictions toward 0, producing a persistent offset error without spikes instead. Z-score normalization (§3.3) addresses both: a prediction of 0 corresponds to the mean utility, and λ\lambda operates on a common scale across utility functions.

This sensitivity is not specific to proxy-guided sampling. In PMBR with r=8r=8, each candidate receives on average only M/8M/8 observations, i.e., 0.5, 1, 2, and 4 at M=4,8,16,32M=4, 8, 16, 32. At small reference sizes, PMBR therefore faces the same sparse-row regime as proxy-guided sampling. This matches the result in Appendix D, where normalization improves PMBR substantially at M≤32M \leq 32 and the gain narrows at larger MM. Sparse rows also affect the decision itself, not only the reconstruction. Using BLEU as a utility function, an inflated row can spuriously win the argmax, whereas on COMET, sparsely observed candidates are shrunk out of contention regardless of quality. Proxy-guided sampling encounters this at every MM step because it deliberately concentrates the budget, which is why it relies more heavily on normalization.

Therefore, we believe that standardization is an integral component of B-PMBR rather than an optional fix, and that it also benefits PMBR when rows are sparsely observed.

AuthorsOpenReview ↗

Rebuttal by Authors (Part 3)

Q3: Utility metric overfitting

Thank you for catching this error in our text. We have revised the sentence in Lines 232-233 to clarify that “we combined all evaluation metrics into a unified score, excluding the metric used as the target utility function.” We confirm that our code and all reported Zˉother{\bar{Z}}_{other} results already follow this exact formulation, so no experimental findings are affected.


Q4: Consistency of result and calculation of Zˉother{\bar{Z}}_{other}

Thank you for your comment. The raw evaluation scores and experimental settings for PMBR are identical in both tables. The difference in Zˉother{\bar{Z}}_{other} occurs because the global mean (μ\mu) and standard deviation (σ\sigma) used for z-score standardization are computed across the specific pool of baselines and variants compared within each respective table.

Table 1 includes additional strong baselines (SVD-MBR and EnsembleMBR), which shifts the pooled mean upward and changes the group standard deviation compared to the baseline pool in Appendix Table 4. Because all methods within a single table share the exact same μ\mu and σ\sigma, all within-table comparisons remain strictly apples-to-apples. In the revision, we have clarified as a footnote in Section 4.1 that Zˉother{\bar{Z}}_{other} is standardized within each experiment's comparison group.


Q5: Overstated claims

Thank you for your comment. Regarding the target utility metric (Util. Metric), performance cannot be simplified to a strictly "higher-is-better" or "lower-is-better" dynamic. While a high utility score coupled with a low Zˉother{\bar{Z}}_{other} indicates overfitting to the utility function, a lower utility score does not inherently guarantee superior generalized quality. Furthermore, could the reviewer kindly specify which reported results suggest that B-PMBR fails to consistently outperform PMBR? In Table 2, our claims remain well-supported, as the normalized log-probability proxy (Norm. Log-Prob) consistently achieves the top two performances across all evaluated utility functions.


We want to thank you again for your constructive feedback and questions, which have helped us clarify and strengthen our manuscript. We hope our responses have addressed all of your current concerns. If you have further concerns or questions, we remain happy to discuss them with you.

Best,


References

[1] Is MAP Decoding All You Need? The Inadequacy of the Mode in Neural Machine Translation (Eikema & Aziz, COLING 2020)

Reviewer_MURjOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes B-PMBR, an efficient decoding method that improves PMBR. The main idea is to replace uniform random sampling with proxy-guided sampling using length-normalized model log-probabilities. The authors also introduce utility score normalization before ALS matrix completion and study three different sampling strategies. Experiments show improvements in translation quality and the trade-off between quality and computational cost compared to PMBR.

Critical strengths

[S1] Simple and practical method.

The paper addresses the computational problem in MBR decoding. The proposed proxy-guided sampling uses model log-probabilities that are available, without any additional model inference. It makes the method useful for efficient decoding.

[S2] Consistent experimental improvements.

B-PMBR performs better than PMBR across different utility functions and reference sizes, especially with small sampling budgets. The experiments also show a better trade-off between quality and computational cost. The ablation studies also examine the effects of proxy selection and normalization.

Critical weaknesses

[W1] Unclear contribution of proxy-guided sampling.

The proposed method includes proxy-guided sampling, utility score normalization, and diagonal masking. Although the appendix evaluates normalization and masking separately for PMBR, it does not include a baseline that applies both modifications together. It makes me unclear how much of the reported improvements actually comes from proxy-guided sampling.

[W2] Limited validation of the proposed sampling strategy.

With my understanding, the proxy score does not directly measure pairwise utility or how useful the sampled observations are for ALS. The reconstruction MSE analysis even uses the mean and standard deviation of the full ground-truth matrix for inverse normalization. These make difficult to tell whether the proposed sampling strategy actually improves matrix reconstruction.

Questions for authors

[Q1] Contribution of proxy-guided sampling

  • First, I wonder the comparison B-PMBR with a PMBR baseline that uses both z-score normalization and diagonal masking under the same sampling budget.
  • Applying both together would also help clarify how much improvement comes from proxy-guided sampling.

[Q2] Validation of the sampling strategy

  • I want to suggest authors to report the matrix reconstruction errors using only statistics estimated from the sampled utility scores, instead of the full ground-truth matrix.

  • Also, how does B-PMBR compare with a simple baseline that directly selects candidates based on length-normalized model log-probabilities? I believe these would clarify whether the improvements come from better matrix reconstruction or simply from selecting high-probability candidates.

5 comments
AuthorsOpenReview ↗

Rebuttal by Authors

We thank you for acknowledging our simple, practical approach and the consistency of our experimental results across multiple settings.

To reduce the length of the response to the comment, some of our revisions are incorporated directly into the paper, and we specify the revision location in the corresponding response. To facilitate tracking in the revised manuscript, all changes addressing your comments have been highlighted in Yellow and labeled with the corresponding comment number.

In the comment, we only include parts of the results required to answer your questions and comments.


W1, Q1: Contribution of proxy-guided sampling

Thank you for the feedback. We have updated Table 3 and Appendix E to include these ablation rows. Below is a summary table averaged across all reduction factors (rr):

MethodBLEUchrFCOMETBLEURTBERTScoreOverall Mean
PMBR (Baseline)-1.12-1.19-0.41-0.71-0.23-0.73
+ Diag. Mask-0.53-0.610.12-0.06-0.18-0.25
+ Mask & Z-Norm-0.310.050.28-0.13-0.05-0.03
B-PMBR (Top-kk)-0.120.150.860.51-0.08+0.26
B-PMBR (Edge-kk)0.000.270.340.390.27+0.25
B-PMBR (Gumbel)-0.210.140.510.130.14+0.14

As shown by the bold value, B-PMBR consistently outperforms both ablation baselines (+ Diag. Mask and + Mask & Z-Norm). While the revised Table 3 indicates that + Mask & Z-Norm can achieve second-best results at certain reduction factors (particularly with BERTScore), proxy-guided sampling yields the strongest overall performance.


W2, Q2: Reconstruction MSE analysis using the sampled observations statistics

Thank you for the feedback. We have fixed the reconstruction and recalculated our analysis. Since this only affects Norm=True, we updated Figure 4 to a log-scale y-axis and added a Norm=True-only plot in Appendix J. The result shows that un-normalizing with sampled pairs mean & std increases MSE for Top-kk (which only samples the upper tail), whereas Edge-kk and Gumbel-Top-kk remain largely unaffected. Below is the MSE change (ground-truth matrix → sampled (%Δ)) for Norm=True with the log-prob proxy (N=256N=256, WMT22 En-De):

MethodBLEU (M=4M=4)BLEU (M=256M=256)BLEU (Mean Δ\Delta)COMET ×10−3\times 10^{-3} (M=4M=4)COMET ×10−3\times 10^{-3} (M=256M=256)COMET (Mean Δ\Delta)
PMBR157.7→158.8152.2→155.2+0.5%6.8→6.81.8→1.8+0.2%
B-PMBR Top-kk159.0→369.3184.1→386.5+128%7.4→12.27.6→11.6+62%
B-PMBR Edge-kk143.5→165.0170.2→198.7+16.8%6.0→6.25.5→5.8+4.4%
B-PMBR Gumbel156.6→160.399.8→93.9+2.1%6.8→7.02.2→2.1+1.4%

Importantly, for Edge-kk, although sampling only selects the extreme top and bottom entries, leveraging these boundary values still improves pairwise matrix reconstruction, especially at small reference sizes. This further demonstrates that sampling the distribution extremes can be sufficient for accurate matrix recovery.


Q2: Comparison against MAP decoding with normed log probs

Thank you for the feedback. The improvements in B-PMBR stem directly from the proxy-guided matrix reconstruction and utility consensus, rather than simply defaulting to high-probability candidates. We compared the existing setup from Section 4.1 against a standard Maximum a Posteriori (MAP) decoding baseline, which directly selects the candidate with the highest length-normalized model log-probability.

As shown in the table below (256×256256 \times 256 matrix, 12.5% budget), MAP consistently underperforms B-PMBR across generalized quality ( Zˉother{\bar{Z}}_{other} ).

MethodBLEUchrFCOMETBLEURTBERTScore
MAP0.088-0.197-1.264-1.119-0.370
MBR0.7870.7320.378-0.1240.664
PMBR-1.482-1.7560.145-0.154-1.017
B-PMBR (Top-kk)-0.0620.315*0.9051.152-0.601
B-PMBR (Edge-kk)0.5610.315-0.6350.0700.584
B-PMBR (Gumbel-Top-kk)0.1080.5900.4700.1770.740

By leveraging high log-probability pairs, B-PMBR ensures the final selection is supported by both high model confidence and high utility consensus. To make this distinction clear in the paper, we have updated Figure 2, 7, and 8 in the revised manuscript to include the MAP decoding baseline, highlighting the performance gap between purely probability-based selection and proxy-guided MBR.


Once again, we would like to thank you for your constructive feedback and questions. They have helped in strengthening our manuscript. We hope our responses have addressed all of your current concerns. If you have further concerns or questions, we remain happy to discuss them with you.

Best,

Thank you for the detailed rebuttal. I really appreciate the authors' efforts to address my concerns through additional experiments.

The new ablation and comparison with MAP decoding addressed my questions well.

One remaining concern is the interpretation of the reconstruction results. The revised experiments suggest that proxy-guided sampling does not necessarily improve global matrix reconstruction accuracy, but may instead provide better estimates for candidates that are important for the final selection. I hope authors revise manuscript considering this.

Overall, I believe the rebuttal has adequately addressed most of my concerns, and I will increase my score.

AuthorsOpenReview ↗

Additional Rebuttal by Authors

Thank you very much for your quick response and for reconsidering your initial score. We are glad that our efforts have addressed most of your concerns.

We also want to thank you for giving us the opportunity to further clarify and improve our manuscript through your additional comment. We will denote your current concerns as Additional Questions (AQ) with the number in this response and in the paper.

AQ1: Interpretation of reconstruction results

We have added additional experiments to empirically measure whether the proxy-guided sampling improves the reconstruction accuracy specifically for candidates that are important (highly likely to win).

To evaluate this empirically, we measure:

  1. the absolute expected utility error ∣Δu^(hMBR)∣=∣u^rec(hMBR)−u^MBR(hMBR)∣\lvert \Delta \hat{u}(h_{\mathrm{MBR}}) \rvert = \lvert \hat{u}_{\mathrm{rec}}(h_{\mathrm{MBR}}) - \hat{u}_{\mathrm{MBR}}(h_{\mathrm{MBR}}) \rvert, and
  2. the MBR agreement rate, i.e., the percentage of source sentences where a method selects hMBRh_{\mathrm{MBR}}

We show the representative BLEU and COMET results below and all five metrics across M∈{4,…,256}M \in \{4, \dots, 256\} are in Appendix I of the revised version:

MetricMethod∣Δu^(hMBR)∣↓\vert\Delta \hat{u}(h_{\mathrm{MBR}})\vert\downarrow M=4∣Δu^(hMBR)∣↓\vert\Delta \hat{u}(h_{\mathrm{MBR}})\vert\downarrow M=32∣Δu^(hMBR)∣↓\vert\Delta \hat{u}(h_{\mathrm{MBR}})\vert\downarrow M=256Agreement (%) M=4Agreement (%) M=32Agreement (%) M=256
BLEUPMBR37.6618.404.284.04.49.9
Normed PMBR16.258.751.297.34.515.6
B-PMBR (Top-k)6.925.054.9737.143.342.5
B-PMBR (Edge-k)10.565.185.0027.528.919.0
B-PMBR (Gumbel-Top-k)14.976.570.907.66.924.8
COMETPMBR0.7020.3160.0091.04.237.2
Normed PMBR0.0980.0640.0055.47.349.4
B-PMBR (Top-k)0.0350.0270.02328.938.641.1
B-PMBR (Edge-k)0.0800.0670.05817.317.418.5
B-PMBR (Gumbel-Top-k)0.0900.0510.0045.49.352.2

By assuming that the MBR selected candidates is a high quality candidate, we find that at small reference sizes (M≤64M \le 64), B-PMBR estimates the expected utility of hMBRh_{\mathrm{MBR}} far more accurately than uniform sampling. Specifically, Top-k achieves the lowest ∣Δu^(hMBR)∣|\Delta \hat{u}(h_{\mathrm{MBR}})| across all five utility functions before Gumbel-Top-k and PMBR variants overtake it at larger M, selecting the same candidate as MBR in 29–42% of source sentences as shown in the representative table.

This low estimation error confirms that hMBRh_{\mathrm{MBR}} typically carries high model probability, allowing B-PMBR to estimate its expected utility from explicit metric scores rather than latent factor extrapolation, even though B-PMBR has higher global matrix reconstruction error than PMBR and Normed PMBR. As M grows, uniform sampling observes enough entries per row to lower its estimation error, whereas Top-kk and Edge-kk plateau because unselected candidates remain unobserved.

We have detailed this discussion in Appendix I. (Note that Appendix I is colored differently because it is used to answer a different question from another reviewer. However, we believe the experiment also answers your additional concern.)

Once again, we would like to thank you for your quick response and your additional feedback. We hope that our response has also resolved your current concern, and we are happy to discuss further concerns should you have any.

Best,

Reviewer_ectZOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper addresses the issue of the high cost of computing pairwise utility across the hypothesis set for MBR decoding. Prior work estimates the utility from a subset of the pairwise values chosen at randomly; this paper improves on that by using log-probs as a proxy metric and bootstrapping a set of comparisons, a method they name B-PMBR. B-PMBR is more Pareto optimal than PMBR or vanilla MBR, shows stable performance even at small comparison budgets, and reduces utility metric overfitting. The authors demonstrate B-PMBR's effectiveness on German-English machine translation.

Critical strengths

S1. The paper presents a nicely motivated, mathematically justified, and clearly explained approach to improve the efficiency of MBR decoding. The method appears effective in increasing efficiency while maintaining more of the accuracy of vanilla MBR than prior approximations.

S2. The proposed approach also reduces the overfitting to the utility metric, which has been a persistent problem with MBR-based approaches. This is (to me) a somewhat surprising benefit, and quite exciting.

Critical weaknesses

W1. My most significant concern is some overlap with a prior work (which I assume the authors were not aware of): Faster Minimum Bayes Risk Decoding with Confidence-based Pruning. While the papers approach the problem from different framings, both develop a bootstrapping-based approach for more efficient MBR.

W2. The work focuses on a single task, machine translation, with relatively older metrics. I know this is standard for MBR literature, so I don't think this is a dealbreaking concern. However, I do think that this method would likely be more beneficial in cases where the utility metric is very expensive (e.g. an LM-as-a-judge), and so I think the work would be strengthened by considering a different task or setting where that kind of evaluation is more common (e.g. abstractive summarization). (while something like BertScore is technically an LM-as-a-judge, it's extremely inexpensive compared to more recent LM judges that compute pairwise preference.)

W1 is my main concern, while W2 is more of a nice to have; if W1 is sufficiently addressed, I will raise my score.

Minor comment: the claim on 423-425 that " Because this preliminary step demands substantial computation before the actual subsampling even begins, the total execution cost will not be any better than simply utilizing PMBR." Isn't this dependent on the relative cost of the utility metrics used for the first-pass and actual scoring? If the scoring utility metric is very expensive relative to the first-pass metric and the first-pass metric reduces the number of samples necessary to get a good estimate, it seems like using a first-pass metric will be better in execution cost than directly using PMBR.

Questions for authors

Q1. Could you discuss your primary contributions that differ from Cheng and Vlachos 2023? (To be clear, I think there are benefits of each approach that could justify both being published! But I'm curious for the authors' thoughts on this.)

Q2. If possible, can you also provide a comparison to the Cheng and Vlachos approach as a baseline?

4 comments
AuthorsOpenReview ↗

Rebuttal by Authors (Part 1)

Thank you for acknowledging the strengths of our paper, specifically our approach that tackled both efficiency and overfitting and we are glad that it is easy to read.

To reduce the length of response on the comment, some of our revisions are added to the paper directly and we specify the revision location in the respective response. To facilitate tracking in the revised manuscript, all changes addressing your comments have been highlighted in Blue and labeled with the corresponding comment number.

In the comment, we only include parts of the results required to answer your questions and comments.


W1,Q1: The difference of approach and contribution against Cheng and Vlachos 2023

Thank you for your suggestion. We have added PruningMBR’s explanation in the Related Works section of our main text. We acknowledge PruningMBR and agree that both methods adopt fundamentally different framing of "confidence." From what we understand, PruningMBR defines confidence via bootstrap resampling over the pseudo-reference set to measure empirical hypothesis stability, which is to say, pruning candidates that are statistically unlikely to win. In contrast, our method uses the generative model's sequence confidence (length-normalized log-probability) to guide pair selection, replacing uniform random sampling in PMBR.

Furthermore, as its original authors noted, PruningMBR is sensitive to the initial step size of its sampling scheduler. Because it was not evaluated on small pseudo-reference sets, applying it there requires non-trivial hyperparameter tuning. Conversely, B-PMBR substantially outperforms standard PMBR and remains competitive with MBR even in small-reference regimes.

Another confusion may come from the name “Bootstrap”. Our method does not perform bootstrap resampling. Instead, it acts more as a deterministic “warm start” in choosing the sampled pairs. We want to eliminate this confusion for future readers; however, we are not sure what the best alternative would be. One option is to rename our proposed method to Proxy-guided PMBR (PG-PMBR) in the camera-ready version (to avoid extensive diff changes during the review phase). Would the reviewer find PG-PMBR clearer, or do you have another naming suggestion that better reflects this mechanism? We would greatly appreciate your thoughts on this.

AuthorsOpenReview ↗

Rebuttal by Authors (Part 2)

Q2: Comparison to Cheng and Vlachos 2023 as baseline

Thank you for the suggestion. We have added a Pareto frontier comparison against PruningMBR in Appendix G of the revised version. Because PruningMBR's iterative doubling scheduler is sensitive to small pseudo-reference sets, we evaluate all methods at N \= M \= 256 following the original PruningMBR hyperparameters (starting at 16 references for BLEU and 8 for COMET/BLEURT, doubling up to 256 across confidence thresholds $\alpha \in $ {$ 0.80, 0.90, 0.95, 0.98, 0.99$} with 500 bootstrap resamples). Below is a summary comparing PruningMBR against PMBR and B-PMBR at matching low-budget regimes ($r \in $ {40,20,1040,20,10}):

Method (Budget / Config)BLEU Zˉother↑{\bar{Z}}_{other}\uparrowBLEU Calls / TimeCOMET Zˉother↑{\bar{Z}}_{other}\uparrowCOMET Calls / TimeBLEURT Zˉother↑{\bar{Z}}_{other}\uparrowBLEURT Calls / Time
PrunedMBR (α=0.80\alpha =0.80)-0.766,285 / 1,828s+0.473,280 / 445s-0.553,347 / 2,463s
PrunedMBR (α=0.95\alpha =0.95)-0.718,185 / 1,930s+0.663,754 / 445s-0.554,206 / 2,948s
PrunedMBR (α=0.99\alpha =0.99)-0.6310,512 / 2,036s+0.594,305 / 446s-0.515,191 / 3,534s
PMBR (r=40r=40, 2.5%)-2.641,639 / 381s-0.691,639 / 303s-1.211,639 / 1,606s
PMBR (r=20r=20, 5.0%)-2.333,277 / 390s-0.313,277 / 303s-0.983,277 / 3,138s
PMBR (r=10r=10, 10.0%)-1.796,554 / 492s+0.186,554 / 322s-0.556,554 / 6,191s
B-PMBR Top-kk (r=40r=40, 2.5%)-0.791,639 / 505s+1.171,639 / 405s+0.631,639 / 1,660s
B-PMBR Top-kk (r=20r=20, 5.0%)-0.903,277 / 624s+1.113,277 / 529s+0.543,277 / 3,246s
B-PMBR Top-kk (r=10r=10, 10.0%)-0.956,554 / 844s+1.176,554 / 797s+0.506,554 / 6,392s
B-PMBR Edge-kk (r=40r=40, 2.5%)-0.401,638 / 496s+0.391,638 / 408s+0.321,638 / 1,681s
B-PMBR Edge-kk (r=20r=20, 5.0%)-0.563,276 / 618s+0.283,276 / 535s+0.273,276 / 3,313s
B-PMBR Edge-kk (r=10r=10, 10.0%)-1.016,554 / 833s+0.036,554 / 791s-0.176,554 / 6,513s
B-PMBR Gumbel (r=40r=40, 2.5%)-1.501,639 / 477s+0.281,639 / 402s-0.331,639 / 1,729s
B-PMBR Gumbel (r=20r=20, 5.0%)-1.343,277 / 613s+0.593,277 / 527s-0.283,277 / 3,374s
B-PMBR Gumbel (r=10r=10, 10.0%)-1.346,554 / 834s+0.746,554 / 791s-0.196,554 / 6,673s

The summary table shows several takeaways. First, B-PMBR Edge-kk on BLEU and Top-kk on COMET and BLEURT at the smallest budget substantially outperform PrunedMBR even at its highest threshold α=0.99\alpha=0.99, while requiring fewer utility calls and computation time. In addition, PrunedMBR requires more computation time at each scheduler iteration due to the bootstrap resampling. However, PrunedMBR achieves higher BLEU Zˉother{\bar{Z}}_{other} than B-PMBR at intermediate budgets (r∈{8,10}r\in \{8,10\}) and outperforms vanilla PMBR on BLEU and COMET. Regardless, B-PMBR dominates the overall Pareto frontier across both computation time and utility evaluations.

AuthorsOpenReview ↗

Rebuttal by Authors (Part 3)

W2: Performance result on Abstractive Summarization task

Thank you for the suggestion. We have added the results in Appendix H. We reported the analysis on abstractive summarization with CNN/DailyMail (CNN/DM) and XSum. The setup follows the main experiments:

  • ϵ\epsilon-sampling with ϵ=0.02\epsilon = 0.02
  • candidate set size fixed at N=256N = 256
  • pseudo-reference sizes M∈{4,8,16,32,64,128,256}M \in \{4, 8, 16, 32, 64, 128, 256\}
  • reduction factor r=8.0r = 8.0 for PMBR and all B-PMBR variants

We evaluate with BERTScore and ROUGE-1/2/L. The summary table below uses BERTScore as the utility function and reports Zˉother{\bar{Z}}_{other}. We have added the full results in the revised version of the paper. The best value in each column is in bold, the second best in italics.

DatasetMethodM=4M=4M=8M=8M=16M=16M=32M=32M=64M=64M=128M=128M=256M=256
CNN/DMMAP-2.28-2.28-2.28-2.28-2.28-2.28-2.28
MBR0.040.670.891.061.151.211.24
PMBR-2.10-2.16-1.39-0.860.230.690.89
B-PMBR Top-kk-0.350.190.450.670.911.011.02
B-PMBR Edge-kk-0.87-0.51-0.210.120.240.390.46
B-PMBR Gumbel-Top-kk-0.88-0.55-0.37-0.190.130.510.98
XSumMAP0.620.620.620.620.620.620.62
MBR-0.120.320.630.710.830.890.91
PMBR-2.15-2.25-1.57-1.340.070.460.66
B-PMBR Top-kk-0.090.240.670.660.730.730.70
B-PMBR Edge-kk0.110.380.750.830.850.870.83
B-PMBR Gumbel-Top-kk-0.74-0.59-0.35-0.110.210.510.91

Some key takeaways are as follows:

  • For both datasets, B-PMBR is much stronger than PMBR when few pseudo-references are available, as in MT. PMBR only catches up as MM grows.
  • On CNN/DM, B-PMBR Top-kk is consistently second only to full MBR and stays close to it as MM grows.
  • On XSum, B-PMBR (Edge-kk) is competitive with MBR and even outperforms it for 16≤M≤6416 \leq M \leq 64. However, the comparison with MBR depends on the utility function. With ROUGE-1 or ROUGE-2 as the utility, B-PMBR still clearly beats PMBR at small MM, but it falls short of MBR from M=16M=16 onward.

Overall, the main conclusion carries over from MT to summarization: B-PMBR keeps most of MBR's quality at a fraction of the cost and substantially outperforms PMBR when the reference budget is small.


Minor Comment about our claim in Line 423-425

Thank you for the comment. Our original statement on lines 423–425 was specifically scoped on two implicit assumptions from our Table 2 setup: (1) that PMBR and B-PMBR are compared at the same reduction factor (r=8.0), and (2) that the evaluation is conducted on a large pairwise matrix ( 256×256256 \times 256 ), where uniform random sampling already has sufficient observations to reconstruct the matrix reasonably well.

However, a first-pass proxy metric can theoretically lower total execution cost under two conditions:

  • High, non-cacheable target metric cost: When the target utility metric is non-cacheable and much more expensive than the first-pass metric, and the proxy improves quality enough to allow a smaller target-metric budget (such as the BLEU proxy with BLEURT under Top-kk in Table 2)
  • Data-sparse regimes: When the candidate/pseudo-reference pool or sampling budget is too small for uniform random sampling to capture enough observations per row for accurate matrix approximation, making guided selection necessary.

Outside of such cases, Table 2 shows that when sufficient data are available for uniform random sampling (256×256256 \times 256, r=8.0r=8.0), BLEU and chrF rarely improve sample efficiency over PMBR. We have revised the claim in lines 465–469 in the manuscript to explicitly state these two assumptions and clarify when a first-pass metric can theoretically reduce execution cost.


We would like to thank you for your constructive feedback and questions, which have helped us clarify and strengthen our manuscript. We hope our responses have addressed all of your current concerns. If you have further concerns or questions, we remain happy to discuss them with you.

Best,

AuthorsOpenReview ↗

Reminder to response

Dear Reviewer ectZ

Thank you again for your time and constructive feedback on our manuscript. As the discussion period is nearing its deadline, we would like to follow up to see if you have had the opportunity to review our rebuttal.

We have carefully addressed your comments and hope our explanations have resolved your initial concerns. If you have any remaining questions or if further clarification is needed before the deadline, please let us know. Thank you for your time and consideration.

Best,

Comments on the paper

2 comments
AuthorsOpenReview ↗

Official Comment by Authors

Dear Reviewers,

Thank you very much for your time and thoughtful feedback and suggestions.

We have carefully revised the manuscript based on your valuable comments.

  • The blue-highlighted areas correspond to revisions for Reviewer ectZ.
  • The yellow-highlighted areas correspond to revisions for Reviewer MURj.
  • The pink-highlighted areas correspond to revisions for Reviewer 36DU.

We sincerely appreciate your constructive suggestions. We believe that the revisions have substantially improved the clarity and quality of the manuscript, and we hope that our updates address all of your concerns. If you have further concerns, we are happy to discuss them with you.

Thank you again for your careful review.

Best,

AuthorsOpenReview ↗

Thank you for the Reviews

Dear Reviewers,

As the discussion period nears its end, we sincerely thank you for the time and effort you have dedicated to review our work. We appreciate your acknowledgements on the strengths of our proposed method and we are glad that our manuscript manages to convey it as we intended.

We really appreciate the different perspectives in each reviewer’s feedback which has given us the opportunity to improve our manuscript furthermore. We believe that we have resolved most of the reviewers’ concerns and integrated them into the revised manuscript. We will further solidify these additions in the final version.

Best,

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.