Faster Minimum Bayes Risk Decoding with Confidence-based Pruning
Authors: Julius Cheng
Andreas Vlachos
Venue: EMNLP 2023 Main (2023)
Keywords: Machine translation
minimum Bayes risk decoding
TL;DR: Minimum Bayes risk decoding is accurate but very costly. We propose an algorithm that speeds up MBR decoding significantly compared to the standard method used in the literature.

Abstract: Minimum Bayes risk (MBR) decoding outputs the hypothesis with the highest expected utility over the model distribution for some utility function. It has been shown to improve accuracy over beam search in conditional language generation problems and especially neural machine translation, in both human and automatic evaluations. However, the standard sampling-based algorithm for MBR is substantially more computationally expensive than beam search, requiring a large number of samples as well as a quadratic number of calls to the utility function, limiting its applicability. We describe an algorithm for MBR which gradually grows the number of samples used to estimate the utility while pruning hypotheses that are unlikely to have the highest utility according to confidence estimates obtained with bootstrap sampling. Our method requires fewer samples and drastically reduces the number of calls to the utility function compared to standard MBR while being statistically indistinguishable in terms of accuracy. We demonstrate the effectiveness of our approach in experiments on three language pairs, using chrF++ and COMET as utility/evaluation metrics.

Faster Minimum Bayes Risk Decoding with Confidence-based Pruning
Julius Cheng, Andreas Vlachos
Department of Computer Science and Technology
University of Cambridge (jncc3,av308] cacmmac.... ac.uk
Abstract
and Eikema and Aziz (2020) propose an sampling- based approximation algorithm.
Minimum Bayes risk (MBR) decoding outputs the hypothesis with the highest expected util- ity over the model distribution for some utility function. has been shown to improve accu- racy over beam search in conditional language generation problems and especially neural ma- chine translation, both human and automatic evaluations. However, the standard sampling- based algorithm for MBR is substantially more computationally expensive than beam search, requiring large number of samples well as a quadratic number of calls to the utility func- tion, limiting its applicability. We describe an algorithm for MBR which gradually grows the number of samples used to estimate the utility while pruning hypotheses that unlikely to have the highest utility according to confidence estimates obtained with bootstrap sampling. Our method requires fewer samples and drasti- cally reduces the number of calls to the utility function compared to standard MBR while be- ing statistically indistinguishable in terms of accuracy. We demonstrate the effectiveness of our approach in experiments three lan- guage pairs, using chrF++ and COMET as util- itylevaluation metrics.
MBR has been shown to outperform MAP beam search in both automatic and qualitative evaluation in a diverse range of tasks (Suzgun et al., 2023), including NMT (Freitag et al., 2022a) and code generation (Shi et al., 2022). MBR also generalizes other previously proposed decoding methods and explains their success (Bertsch al., 2023).
The accuracy improvement from MBR comes at a heavy cost: the number of samples used can reach thousands (Freitag et al., 2023), and the number of calls to the utility function required is quadratic in the number of samples. Often, the utility func- tion itself is a deep neural model, rendering MBR prohibitively expensive for many cases.
In this work, we address the computational ef- ficiency of MBR with an iterative pruning algo- rithm where low-performing hypotheses are re- moved while the number of samples used to esti- mate utilities grows. Hypotheses are pruned based on their estimated probability of being the true best hypothesis under the MBR objective, thus avoid- ing making expensive fine- fine-graing grained utility estimates for hypotheses which are unlikely be the final prediction.
1 Introduction
In NMT experiments on three language pairs using chrF++ (Popović, 2015), and COMET (Rei et al., 2020) as MBR utility and evaluation metrics, we show that our method maintains the same level of accuracy standard MBR while reducing the number of utility calls by factor of least 7 for chrF++ and 15 for COMET. Our algorithm can also use fewer samples to reach a prediction by terminating early, unlike standard MBR.
Minimum Bayes risk (MBR) decoding (Bickel and Doksum, 1977; Goel and Byrne, 2000) has recently gained renewed attention as decision rule for conditional sequence generation tasks, especially neural machine translation (NMT). In MBR, the sequence with the highest expected utility with re- spect to thez model distribution is chosen as the output, where the utility is usually some measure of text similarity. This contrasts with the more com- monly used maximum posteriori (MAP) decision rule, which returns the sequence with the highest probability under the model. MAP is generally in- tractable, and beam search is typically used to find an approximation. MBR is likewise intractable,
Minimum Bayes risk decoding
Conditional sequence generation problems such neural machine translation (NMT) model the prob- ability of the next token yt given a source sequence x and prefix yer with a neural network po- This

---

model can be used to assign probabilities full sequences po(y]æ) via the chain rule.
be achieved if low-performing hypotheses are re- moved from considcration based on coarse utility estimates obtained from a subset of the pseudo- references. In other words, we can save time by not computing precise utility estimates for hypotheses which are unlikely to be chosen in the end.
At test time, a decision rule is employed to se- lect a single "best" sequence. The most common decision rule is to return the highest probability sequence YMP arg maxy po(y|z). The exact solution is generally intractable, and beam search is used to find an approximation.
We propose an iterative algorithm for MBR where the hypothesis set is gradually shrunk while the pseudo-reference list grows. The procedure is shown in Algorithm 1. We start with an ini- tial hypothesis set H1, and at each time step I, a pruning function uses a pseudo-reference list R₂ of size r to select H4 11 S H4. After the maximum time step is reached when the current hypothe- sis set contains one element, terminate and return the highest utility hypothesis under all available pseudo-references, The size of R, grows accord- ing to a pre-defined "schedule" T1, TT.
In contrast, minimum Bayes risk decoding (MBR) (Goel and Byrne, 2000) outputs:
y MBR arg max (1) v)]
max U (v, Po([
(1)
for some utility function u, a measure of similarity between sequences, and U (y. = Eg~y[u(v. ū)), where y is either probability distribution or an array of samples. We call U the expected utility function. Eikema and Aziz (2020) propose pling method for neural language models where hy- potheses and pseudo-references R. are generated with unbiased sampling, and yMBR is estimated as:
A Algorithm 1 Pruning MBR
Input:
Source sentence x.
Constants: sample size schedule r = T1, TT, expected utility function U, model parameters 0, pruming function prune, hypothesis genera- tion function gen 8).
MBR ~U arg max UY, 1
(2)
DEH
Output: An MBR prediction.
This method, which we refer to as "standard" MBR, requires [H] + | samples (assuming H + R) and [| calls to u. The latter is the main computa- tional bottleneck which we address in this work. Recent works on MBR focus identifying ac- curate and efficient generation methods (Eikema and Aziz, 2021; Freitag al., 2023; Yan et al., 2022), and pruning H to a smaller size with a faster method prior to running standard MBR (Eikema and Aziz, 2021; Fernandes et al., 2022).
Ro < []
2: ++1
3: H1 < --en(1r 0)
4: while l < and [741 > 1 do
5:
R, + R--1
while (Rel <r, do
Append po(-1z) to R.
end while
9: Ho+1 f prune (Hz R₂)
10: t +-1+1
Freitag et al. (2022a) and Eikema and Aziz (2021) show that MBR is more effective relative to MAP when the utility metric has high segment- level accuracy as measured by Freitag al. (2021). So, we use COMET (Rei et al., 2020), one of the best available metrics for NMT, and chrF++ (Popović, 2015), as a simpler and faster yet rea- sonably good lexical metric. We heed the call of Freitag et al. (2022b) and do not use BLEU, which is obsoleted by newer metrics as both an evaluation and utility metric (Freitag et al., 2022a).
11: end while
12: return arg max R(-))
The goal of the pruning function is to exclude many hypotheses possible reduce the num- ber of utility calls made in the future without excluding the true top-ranking MBR hypothesis arg maxyeH, U(y p=(+)=)), the true "winner".
We propose to prune hypotheses in He with low probability of being the truc winner and to estimate this probability using nonparametrie bootstrap re- sampling (Efron, 1979; Koehn, 2004); given ini- tial collection of i.i.d. samples S from an unknown distribution X, our beliefs about the true value of any statistic T(X') are represented by the distribu-
3 Confidence-based hypothesis pruning Sampling- MBR returns the highest-utility hypothesis from a set measured over pseudo- references sampled from the model. Speedups can

---

tion (T()))) where S ~ boot(S). and boot(8) returns a with-replacement size-[S] resample of S.
Algorithm 2 Confidence- pruning function
Input: Hypothesis set H. pseudo-reference list R. Constants: Expected utility function U, confi- dence threshold a, number of bootstrap sam- ples n.
In our case, we want to estimate the probability that is the true winner in H4:
p( A (o(-z)) 2 (V..pollaa (3)
Output: A subset of H.
DEN
1: Hnew < 0
2: 7 < arg max U
which we estimate the chance that y wins in bootstrap resample. Let R2 ~ boot(R,). Then the bootstrap estimator is:
3: Hi + gen een(x, f)
4: for i +- 110 do
R' - boot(R)
end for
E R2 (.)
[1
A (U),.RA) U(, R.)]. (4) JEHH
for y E H do
w t 1 Σ. (U, R$) 2 U(ū R'))
This estimator can be high variance because the probability y winning in a bootstrap sample is very small when Hi is large, so instead we use the prob- ability that y outranks a particular ÿ E H.y
9: if w > 1 - a then
10:
Hnew < Hnew U (y)
11: end if
12: end for
13: return Hnew
E (2-
[1(U(,, Ra) 2 U(J,RR))
(5)
bottom-33 proportion. At 3 = 0, no pruning oc- curs and standard MBR decoding is recovered. We refer to this baseline as prune; and our confidence- based method as prunc
This statistic is invariant to the size of He be- cause it only considers utility estimates of y and V. It is an upper bound of Equation 4 because the probability of y winning against all E H4 cannot be higher than the probability of winning against a particular ÿ E H4. ÿ can be any element in He but we set to the winner under R., i.e. ū - arg maxzeM, U (J, R2), to achieve a tighter upper bound.
4 Experiments
We perform our experiments on NMT models which we train on the German- English (de-en), English-Estoniaan (en-et), and Turkish-English (tr- en) news datasets from WMT18. 18. We use the data preprocessing steps provided by the WMT18 orga- nizers, except that exclude Paracrawl from the de-en dataset following Eikema and Aziz (2021). The final training sets have 5.8 million, 1.9 mil- lion, and 207 thousand sentence pairs respectively. All models are transformers of the base model size from Vaswani et al. (2017) and are trained without label smoothing until convergence.
We propose to prune if its estimated proba- bility of beating ÿ is less than 1 a, where is confidence threshold 0 I S 1. In summary, this procedure prunes some but not necessarily all y C Hi which are estimated to have less than 1 a chance of being the true winner. Algorithm 2 shows the procedure in detail.
Note that bootstrapped utility estimates do not require additional utility function calls because they reuse utility values already computed over He, R.. Also note that the bootstrap estimator is always biased because R, never equal to Po(- and the bias worse when R₂ is small. Nonetheless, we show empirically that bootstrapping is effective in our pruning algorithm for modest sizes of R,
For all language pairs and validation/test datasets, generate Hi with beam top-k with 256 We generate 1024 pseudo-references R with epsilon sampling (Hewitt al., 2022) with E = 0.02, following Freitag et al. (2023). In order to run multiple random trials efficiently, we simu- late sampling pseudo-references by sampling from R" without replacement. The experiments in Sec- tions 4.1 and 4.2 show averaged results from 10 trials. We use chrF++ and COMET utility func-
Another benefit of our pruning method compared standard MBR is that it can terminate early if He has only one remaining hypothesis, reducing the total number of pseudo-references needed.
As a baseline pruning function for comparison, we rank each y E 74. by Uy. R,) and prune the
'Different sequences may have the same detokenization result, so we have fewer than 256 hypotheses on average.

---

tions and always match the evaluation metric to the utiliiy. chrF++ is computed using SacreBLEU (Post, 2018) with default settings. COMET com- puted with the COMET-22 model from Rei et al. (2022). We use 500 bootstrap samples for prunc For the pseudo-reference sample size schedule "1...,/T ,T, the choice of r1 is pivotal in the speed- accuracy trade-off; [Hi||R is lower bound the number of utility calls needed, but the boot- strap estimate is more biased when the sample
Utility: chrf+++
Utility: COMET
56.60
56.55
79.60
56.50
79.58
79.56
56.40
70.54
56.35
10000
2500
3000
0.75
0.85
size is small. In a preliminary experiment on the validation set, we measure the "false prun- ing rate", the rate that the estimated true winner, arg maxgen (ū, R²) is pruned under different choices of and [R]. Based results shown in Figure we set T1 to 8 for COMET and 16 for chrF++ for all experiments. r2,..., PV set by doubling at each time step until reaching 256.
Exact accuracy
0.85
0.75
0.70
0.50
0.55
0.40
4000
6000
8000
10000
2000
2500
3000
3500
4000
More experimental details and figures for lan- guage pairs not shown here are in the Appendix.
Reciprocal rank
0.85
Our code is publicly available?.
0.75
0.60
prune,
ce-ar, chrF444
do-an, COMET
0.55
pruney
0.65
0.3
3000 Utility calls
Utilty
07
Figure 2: Speed-accuracy trade-off curves of pruning functions for a E 0.8, 0.9, 0.95, 0.98, 0.99 and 3 e {0.05, ..., 0.95) on the de-en validation set. The x-axes are truncated for better visual comparison.
0.1
0.1
Figure 1: False pruming rates for different choices and [R] measured on the validation set.
4.2 Test results
4.1 Speed-accuracy trade-off
prune, and pruney allow control over the speed- accuracy trade-off with single parameter. We ob- serve this trade-off over the validation set by com- paring the number of utility function calls made against various measures of accuracy. High eval- uation score is underlying goal, but we find that the score changes very little across settings, so we also evaluate pruning quality in terms of how well final predictions match those under standard MBR with R*. We use exact accuracy, whether the pre- diction y equals arg maxycH Uū, R*), and recip- rocal rank (RR), equal to (EyeR ((U(y, (U,Ry))) R*) Uly -1 as a soft accuracy measure adapted from the mean reciprocal rank used in search (Craswell, 2009). Figure 2 shows that prune, gen- erally outperforms prunc on all metries.
We evaluate our methods on the test set with 0.99 and 0.9 and compare them to stan- dard MBR on the accuracy metrics described in Section 4.1 as well the number of utility calls and pseudo-references used. Table shows that across all language pairs and metries, our method achieves similar evaluation scores as standard MBR while using much less computation, with the most dra- matic case being en-et and COMET with a 0.9 which uses 3.5% as many utility calls and 32% many pseudo-referenee as the baseline.
When comparing 0.99 with 0.9, we see that while exact accuracy and RR differ, the evaluation score differs very little if all, suggest- ing that high-ranking hypotheses are often equally good as one another, and finely discriminating be- tween them has diminishing returns.
Battps://githun ctw.ub..com/////////

---

Metric: chrf++
de-cn
en-et
tr-cn
B 0
0.99
a = 0.9
8
a 0.99
a 0.9
=
a 0.99
a = 0.9
Score
62.18
62.19
62.11
46.47
46,48
46.44
42.63
42,63
42.64
Accuracy
0.749
0.736
0.648
0.741
0.728
0.639
0.761
0.751
0.660
RR
0.850
0.840
0.769
0,843
0.833
0.762
0.857
0.850
0.779
# Pscudo-ref's
256.0
234.9
185.2
256.0
235.3
188.5
256.0
238.7
185.7
# Utility calls
65082
9542
5402
63898
9644
5386
65356
8761
5275
Metric: COMET
de-en
B 0
0.99
0.9
8 0
0.99
0.9
=
a 0.99
0: 0.9
Score
78.37
78.37
78.41
82.75
82,74
82.74
73.70
73.68
73.65
Accuracy
0.872
0.844
0.742
0.924
0.898
0.830
0.897
0.878
0.791
RR 0.930
0.911
0.838
0.959
0.943
0.898
0.944
0.932
0.873
# Pseudo-ref's
256.0
200.3
120.4
256.0
151.4
82.6
256.0
177.8
100.8
#
Utility calls
65082
3831
2533
63898
2813
2250
65356
3244
2394
Table 1: Statistics for MBR decoding on the test for all language pair and metric settings. / indicates
standard MBR. All values are averaged across 10 random trials.
4.3 Human evaluation
implementation details are given in Appendix A.2. Table 2 provides detailed breakdown run times. As expected, our method achieves the greatest time savings on utility computation. However, it is still substantially slower than beam search.
We confirm that our method is indistinguishable from standard MBR in human evaluation. On the de-en test set, for each instance, we sample 256 pseudo-references without replacement from R* and use this pool to decode with both standard MBR and prune,; a 0.99. 85% of the predic- tions are the same, and for the rest, we asked bilin- gual readers of German and English state which prediction they preferred. We obtained 125 ratings. The standard MBR prediction won in 48 cases, lost in 42, and tied in 35. This fails the significance test of Koehn (2004),
Run time (scconds)
Prune MBR
Std. MBR
Beam
Generate Generate R
36.56
36.56
26.79
$9.92
Embed sentences
100.50
108.33
Compute utilities
12.96
193.01
Bootstrap pruning
0.63
conclude that prune, with a 0.99 is not significantly different from standard MBR on de-en.
Total
210.57
397.82
26.79
Table 2: Summary run times for decoding methods on 100 sentences from the de-en test set for pruning MBR (a = 0.99), standard MBR, and beam search with beam size 10, averaged over trials.
4.4
Run times
To measure realistic run times, implement practical version of our algorithm and compare our method against standard MBR decoding and beam search. We run our algorithm with COMET as the utility function and a = 0.99. With COMET, sentence embeddings can be cached, which greatly speeds up utility function calls. Some of the the- oretical gains seen in Section 4.2 are diminished in practice due to iterative algorithm dividing computations smaller batches. Our best im- plementation samples all 256 pseudo-references once but generates pseudo-reference sentence em- beddings as needed. We run each algorithm on a set of 100 randomly sampled test instances. Further
Conclusion
We propose an iterative pruning algorithm for MBR along with a pruning criterion based on confidence estimates derived from bootstrap resampling. experiments across diverse language pairs and met- ries, we show that our method consistently outper- forms proposed bascline and achieves signifi- cant computational savings over standard sampling- based MBR without sacrificing accuracy. Our method is drop-in substitute for standard MBR that requires no knowledge about the model pa- how Hi is generated, or the utility function.

---

Limitations
Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1396-1412, Seattle, United States. Association for Computational Lin- guistics.
Even with our pruning algorithm, MBR is many times more costly to run than beam search. More An important hyperparameter in our method is the sample size schedule. We show why it is impor- tant to carefully choose the size of the first sample, but not how the remaining schedule should be set, opting to simply double the size at each step. We leave this issue to future work.
Markus Freitag, Behrooz Ghorbani, and Patrick Fer- nandes. 2023. Epsilon sampling rocks: Investigating sampling strategies for minimum bayes risk decoding for machine translation.
Markus Freitag, David Grangier, Qijun Tan, and Bowen Liang. 2022a. High quality rather than high model probability: Minimum Bayes risk decoding with neu- ral metries. Transactions of the Association for Com- putaational Linguistics, 10:811-88 1-825.
Methods such as MBR and reranking that di- rectly optimize metric may exploit noise in the metric to improve the score without actually im- proving quality (Fernandes et al., 2022). In these settings, automatic evaluation is less trustworthy and should ideally be combined with human evalu- ation. However, human evaluation is difficult and expensive to obtain.
Markus Freitag, Ricardo Rei, Nitika Mathur, Chi-kiu Lo, Craig Stewart, Eleftherios Avramidis, Tom Koemi, George Foster, Alon Lavie, and André F. T. Martins. 2022b. Results of WMT22 metrics shared task: Stop using BLEU neural metrics are better and more robust. Proceedings of the Seventh Conference on Machine Translation (WMT), pages 46-68, Abu Dhabi, United Arah Emirates (Hybrid). Association for Computational Linguistics.
Acknowledgements
Julius Cheng is supported by a scholarship from Huawei. The authors would like to thank the bilin- gual readers who helped with the human evaluation and the anonymous reviewers for their helpful sug- gestions.
Markus Freitag, Ricardo Rei, Nitika Mathur, Chi-kiu Lo, Craig Stewart, George Foster, Alon Lavie, and Ondfej Bojar. 2021. Results of the WMT21 metrics shared task: Evaluating metrics with expert- basert human evaluations on TED and news domain. In Proceed- ings of the Sixth Conference Machine Translation, pages 733-774, Online. Association for Computa- tional Linguistics.
References
Amanda Bertsch, Alex Xie, Graham Neubig, and Matthew R. Gormley. 2023. It's mbr all the way down: Modern generation techniques through the lens of minimum bayes risk.
Vaibhava Goel and William J Bymee 2000. Minimum bayes-risk automatic speech recognition. Computer Speech & Language, 14()):15-133..
P. J. Bickel and K. A. Doksum. 1977. Mathematical Statistics: Basic Ideas and Selected Topics. Holden- Day Company, Oakland, California.
John Hewitt, Christopher Manning, and Percy Liang, 2022. Truncation sampling as language model desmoothing. In Findings of the Association for Com- putational Linguistics: EMNLP P 2022, pages 3414- 3427, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
Nick Craswell. 2009. Mean Reciprocal Rank, pages 1703-1703. Springer US, Boston, MA.
Another Look at the Jackknife. The Annals of Statistics, 7(1):1 26.
Efron. 1979. Bootstrap Methods:
Philipp Koehn. 2004, Statistical significance tests for machine tramslation evaluation. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, pages 388-395, Barcelona, Spain. Association for Computational Linguisties.
Bryan Tikema and Wilker Aziz. 2020. Is MAP decoding all you need? the inadequacy of the mode in neural machine translation. In Proceedings of the 28th Inter- national Conference on Computational Linguistics, pages 4506-4520, Barcelona, Spain (Online). Inter- national Committee on Computational Linguistics.
Myle Oit, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier. and Michael Auli. 2019. fairseq: A fast, extensible toolkit for sequence modeling. In Proceedings of the 2019 Con- ference of the North American Chapter of the Associa- tion for Computational Linguistics (Demonstrations), pages 48-53, Minneapolis, Minnesota. Association for Computational Linguistics.
Bryan Eikema and Wilker Aziz. 2021. Sampling- based minimum bayes risk decoding for neural machine translation. CoRR,
Patrick Fernandes, António Farinhas, Ricardo Rei, José De Souza, Perez Ogayo, Graham Neubig, and Andre Martins. 2022. Quality-aware decoding for neural machine translation. In Proceedings of the 2022
Maja Popović. 2015. chrF: character n-gram F-score for automatic MT evaluation. In Proceedings of the Tenth Workshop on Statistical Machine Translation,

---

pages 392-395, Lisbon, Portugal. Association for Computational Linguistics.
obtain the corpus-level score of a of predictions by simple averaging.
All experiments are implemented on top of our fork of Fairseq (Ott al., 2019).
Matt Post. 2018. A call for clarity in reporting BLEU scores. Proceedings of the Third Conference on Machine Translation: Research Papers, pages 186- 191, Brussels, Belgium. Association for Computa- tional Linguistics.
A.2 Run times
This section contains additional details for the ex- periment Section 4.4.
Ricardo Rei, José G. C. de Souza, Duarte Alves, Chrysoula Zerva, Ana C Farinha, Taisiya Glushkova, Alon Lavie, Luisa Coheur, and André Martins. 2022. COMET-22: Unbabel-IST 2022 submission for the metrics shared task. In Proceedings of the Seventh Conference on Machine Translation (WMT), pages 578-585, Abu Dhabi, United Arab Emirates (Hybrid). Association for Computational Linguistics.
For both the standard and pruning MBR al- gorithms, deduplicate and cache computa- tions whenever possible. For each unique pseudo- reference, its sentence embedding and utility scores against each E Hl are only computed once.
Ricardo Rei, Craig Stewart, Ana C Farinha, and Alon Lavie. 2020. COMET: A neural framework for MT evaluation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Process- ing (EMNLP), pages 2685-2702, Online. Association for Computational Linguistics.
For simplicity, all decoding methods one sequence at a time. Batching across sequences would likely affect the relative performance char- acteristics of each method.
on
All experiments are conducted on the same ma- chine with one Nvidia Quadro RTX 8000 GPU.
Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, and Sida I. Wang. 2022. Natural lan- guage to code translation with execution. In Proceed- ings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 3533-3546, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
B False pruning rates for en-et, tr-en
Figure shows the false pruning rates for en-et and tr-en.
Mirac Suzgun, Luke Helas-Kyriazi, and Dan Jurafsky. 2023. Follow the wisdom of the crowd: Effective text generation via minimum Bayes risk decoding. In Findings of the Association for Computational Linguistics: ACT. 2023, pages 4265-4293, Toronto, Canada, Association for Computational Linguisties.
chifl+
en-eL.COMET COMET
0.00
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, F. ukasz Kaiser, and Illia Polosukhin. 2017. Attention all you need. In Advances in Neural Information Pro- cessing Systems, volume 30. Curran Associates, Inc.
6:38
0-3.
tn-01 chrf
thee 1 COMET
m-3.55
0.5
0.35
0*3.94
0.20
0.5
Jianhao Yan, Jin Xu, Fandong Meng, Jie Zhou, and Yue Zhang. 2022. De-mbr: Distributional cooling for minimum bayesian risk decoding. arXiv preprint arXiv:2212.04205.
0.0
0.0
0.00
60
40
02
P5zudoicfs
PScoudords
Figure 3: False pruning rates for different choices of and [ measured on the validation set.
A
Additional experimental details
A.1
All experiments
Preliminary experiments showed no significant dif- ference between 500 and 1000 bootstrap samples when running prunc.. so we use 500 for all exper- iments.
C Hypotheses remaining per time step
Figure 4 shows the distribution of the number of remaining hypotheses after each time step when running our method on the de-en validation set, following the experimental setup of Section 4.1 where l4l = 256. This is provided to further illustrate the pruning process.
For efficiency, we use average sentence-level chrF++ instead of corpus-level chrF++ for corpus- level evaluations. This allows us to pre-compute the sentence-level chrF++ for each hypothesis and

---

D Speed-accuracy trade-off for en-et,
chif++
tr-en
120
derce
08
0.9
100
chrf++
Utilt::
hygroteee remsiiin
44.523
0.99
14.00
01.00
0.75
0.90
32
64 pasttberleeercee
120
256
0.70
0.65
0.00
de-en. COMET
0.55
0.75
0.
0.20
180
0.
4000
0000
0000
33300
2000
2500
typptreie remaaring
120
0..5
100
0.50
0.75
0.000
0.15
0.65
0.60
0.25
0.55
0.000
2500
preuddontference
32
120
Figure 5: Speed-accuracy trade-off curves of pruning functions for 0.8, 0.9, 0.95, 0.98, 0.99 and B e (..5......95)) on the en-et validation set.
Figure 4: Number of remaining hypotheses after each time step while running the pruning MBR algorithm for various choices x-axis is the number of pseudo-references at a time step, and the y-axis is the number of hy potheses remaining after pruning. Colored bars show the mean, and error bars show the interquartile range.
on the de-en validation set. The
Jtilit: chiff++
Utiltt: COMEET
40.325
04.11
40.755
40350
71,000
1000
8900
2350
3010
0.75
0.90
0.50
0..5
0.00
0.00
0.75
0.55
035
0.7
0.5
0.40
0.9
1050
W550
11091
7000
7520
0.53
0.00
0.75
(0/09)
Utity
Figure 6: Speed-accuracy trade-off curves of pruning functions for a E 0.8, 0.9, 0.95, 0.98, 0.99 and 3 e (0.05,.. ..., 0.95) on the tr-en validation set.


Reviews:
[{"review_id": "kOoFr5Kzb4", "reviewer": "Reviewer_GsRs", "summary": "", "questions": "1. About Equation 5: How is this a lower bound for Equation 4? If I understand your notation correctly, equation 4 checks the number of resamples that y has a higher value of utility than any of y in the hypothesis set. Equation 5 checks the number of resamples that y has a higher value of utility than the highest utility -> y has the highest utility. Two equations look the same to me. I don't really understand this notation. \n2. Descriptions about your methods and baseline methods are too short to understand. I would recommend an pseudo-code at least in your appendix to improve the readability. \n3. how do you choose your hyper-parameter? Do you directly tune on the test set? If not, please clarify.", "limitations": "", "rating": 4, "confidence": 5, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review! To respond:\n\n1\\. Equations 4 and 5 do indeed look the same, but in the text immediately after Equation 5, we define $\\bar{y}$ as the highest utility hypothesis under the current pseudo-reference set, as you describe. We see that using $\\bar{y}$ in both equations but defining them differently in the text can be misleading, and we would modify Equation 4 to the following: \n\n$\\frac{1}{n}\\sum^{n}_{i=1}{1 \\bigwedge\\_{\\bar{y}\\in\\mathcal{H}_t}{U(y,\\hat{\\mathcal{R}^i_t})\\geq U(\\bar{y},\\hat{\\mathcal{R}^i_t})}}$\n\nand Equation 5 to:\n\n$\\frac{1}{n}\\sum^{n}\\_{i=1}{1({U(y,\\hat{\\mathcal{R}^i_t})\\geq U(\\tilde{y},\\hat{\\mathcal{R}^i_t})})}$ where $\\tilde{y}=\\arg\\max_{\\bar{y}\\in\\mathcal{H}_t}U(\\bar{y}, \\mathcal{R}_t)$\n\nThis makes explicit that Equation 4 compares $y$ against all $\\bar{y}\\in\\mathcal{H}_t$ while Equation 5 only compares $y$ against a particular hypothesis.\n\nIn response to why Equation 5 is an upper bound on Equation 4, in the former, y has to “win” against all other hypotheses in a bootstrap trial for that trial to contribute probability mass, and in the latter, y only has to win against a single other hypothesis. The probability of beating all hypotheses in a set cannot be higher than the probability of beating a single hypothesis in that same set. We will include this intuitive justification in the camera ready if accepted.\n\n2\\. We agree that pseudocode would greatly help readability, and if accepted, we would include two pseudocode boxes, one for iterative pruning MBR in general, and one for our proposed pruning function. Here is a preview. For iterative pruning, let $x$ be the source sentence, $p$ be the language model, $\\mathcal{H}$ the starting hypothesis, $r=r_1,...,r_t$ the sample size schedule, and $\\text{prune}$ a pruning function:\n\n$\\text{PruningMBR}(x, p, \\mathcal{H}_1, r, \\text{prune}):$\n\n$\\mathcal{R}_0 \\leftarrow \\\\{\\\\}$\n\nfor $t$ from 1 to $|r|$:\n\n&emsp; $\\mathcal{R}_t \\leftarrow \\mathcal{R}\\_{t-1}$\n\n&emsp; while $|\\mathcal{R}_t| < r_t$:\n\n&emsp;&emsp; append $y\\sim p(\\cdot|x)$ to $\\mathcal{R}_t$\n\n&emsp; $\\mathcal{H}\\_{t+1} \\leftarrow \\text{prune}(\\mathcal{H}_t,\\mathcal{R}_t)$\n\n&emsp; if $|\\mathcal{H}|=1$:\n\n&emsp; &emsp; break\n\nreturn $\\arg\\max\\_{y\\in\\mathcal{H}\\_{t+1}}U(y, \\mathcal{R}_t)$\n\nOur proposed function, given utility functions $u$ and $U$ as defined in the paper, number of bootstraps $n$, and confidence $\\alpha$, is defined as:\n\n$\\text{prune}_\\alpha(\\mathcal{H}, \\mathcal{R})$:\n\n$ \\tilde{\\mathcal{H}} \\leftarrow \\\\{\\\\}$\n\n$\\tilde{y} \\leftarrow \\arg\\max\\_{y\\in\\mathcal{H}}U(y, \\mathcal{R})$\n\nfor $i$ from 1 to $n$:\n\n&emsp; $\\hat{\\mathcal{R}}^i \\leftarrow \\text{boot}(\\mathcal{R})$\n\nfor each $y\\in\\mathcal{H}$:\n\n &emsp; if $\\frac{1}{n}\\sum^{n}\\_{i=1}{1({U(y,\\hat{\\mathcal{R}^i})\\geq U(\\tilde{y},\\hat{\\mathcal{R}^i})})} \\geq 1 - \\alpha$:\n \n&emsp;&emsp; $\\tilde{\\mathcal{H}} \\leftarrow \\tilde{\\mathcal{H}} \\cup \\\\{y\\\\} $\n\nreturn $\\tilde{\\mathcal{H}}$\n\n3\\. There are two classes of hyperparameters. The first one contains those that are shared between the baseline and our method, and these are MT model training hyperparameters, methods for generating H and R, and utility function hyperparameters. The paper includes descriptions of non-standard choices for reproducibility.\n\nThe second class contains those hyperparameters that are specific to our pruning method, namely the sample size schedule, the confidence threshold, and the number of bootstrap samples n. For the sample size schedule, we pick R_1 by balancing the false pruning rate seen in Figure 1 against how many utility calls are made on the validation set. The confidence threshold was not tuned as we show results for the full sweep. The number of bootstrap samples n is not critical; we tried n=500 and n=1000 in early experiments and the results were similar, and the runtime difference is small. We will make sure to include this information, especially the fact that the sample size schedule was tuned on the validation set.\n\nRe: the missing reference, this paper also pertains to MBR and we will include it in our overview of recent work on MBR.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The problem authors addressed in this paper is crucial for real-world applications with MBR decoding. \nThe idea is inspiring and convincing, which simultaneously shrinks the hypothesis space and grows the reference space. The bootstrapping resample method fits well to the application and does not introduce extra computations. \nThe experiments show that their methods achieve significant speedup and maintain almost the same decoding performance.", "reasons_to_reject": "I have some minor concerns about your methods and experiments. Please see the questions below. \nIf my questions and missing references are well-addressed, I am willing to give a higher score of soundness.", "questions_to_authors": "1. About Equation 5: How is this a lower bound for Equation 4? If I understand your notation correctly, equation 4 checks the number of resamples that y has a higher value of utility than any of y in the hypothesis set. Equation 5 checks the number of resamples that y has a higher value of utility than the highest utility -> y has the highest utility. Two equations look the same to me. I don't really understand this notation. \n2. Descriptions about your methods and baseline methods are too short to understand. I would recommend an pseudo-code at least in your appendix to improve the readability. \n3. how do you choose your hyper-parameter? Do you directly tune on the test set? If not, please clarify.", "paper_topic_and_main_contributions": "This paper addresses one of the important problems for Minimum Bayesian Risk decoding, the efficiency problem. \nThey propose a novel bootstrapping-based method to dynamically truncate the hypothesis set. \nExperiments show that their methods achieve similar results with standard MBR and require much less computational cost.", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "Here's another paper discussing the MBR in MT: \nDC-MBR: Distributional Cooling for Minimum Bayesian Risk Decoding\nhttps://arxiv.org/pdf/2212.04205.pdf", "Typos_Grammar_Style_and_Presentation_Improvements": "NA"}, "extra_text": {}}, {"review_id": "X28lciEXnQ", "reviewer": "Reviewer_JEUK", "summary": "", "questions": "One thing that is not crystal clear to me is why the pseudo-reference list grows. Is it because that the initial list contains not so good translations (the ones that will get pruned)? Is H1 and R1 the same? Does sampling more references and adding them to R improve the quality of the reference set? If so, why not also prune away those sentences that get pruned away?\n\nAnother question is about Figure 2, top-right sub-figure. Why do the scores go down in the end? Do I understand correctly that the final hypothesis has to come from H1 because no new hypothesis is ever added in later iterations? If so, does that mean at utility call 3500 for prune_alpha, the best hypothesis so far still gets somehow thrown away with more utility calls? How often is the true reference included in your pseudo reference set? I think one more curve in the same figure which is the number of remaining hypotheses (or maybe also add the current reference set size) would help better understand the process.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 5, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review, and we're glad to hear that you liked our paper! We'll respond point-by-point:\n\n> One thing that is not crystal clear to me is why the pseudo-reference list grows. Is it because the initial list contains not so good translations (the ones that will get pruned)? Is H1 and R1 the same? Does sampling more references and adding them to R improve the quality of the reference set? If so, why not also prune away those sentences that get pruned away?\n\nThe literature is mixed on whether $\\mathcal{H}$ and $\\mathcal{R}$ should be the same, so for maximum generality, we don’t assume so. \n\nThe larger $\\mathcal{R}$ is, the higher the quality of approximation of the utility of each hypothesis, and it has been observed in practice that better approximations mean better test evaluation scores (Freitag et. al., 2022). So, our algorithm, like standard MBR, seeks fine-grained utility estimates for hypotheses, except that we prune away hypotheses which are statistically unlikely to be the final winner. We hope this answers your questions, and we'll incorporate these clarifications into the text.\n\n> Another question is about Figure 2, top-right sub-figure. Why do the scores go down in the end? Do I understand correctly that the final hypothesis has to come from H1 because no new hypothesis is ever added in later iterations? If so, does that mean at utility call 3500 for prune_alpha, the best hypothesis so far still gets somehow thrown away with more utility calls? \n\nYou are correct that no new hypotheses are added in later iterations, and the reason for this downward curve is that utility scores and evaluation scores are highly but not perfectly correlated.  Some of the equivalent figures in the appendix for en-et and tr-en show similar phenomena. The dip mostly occurs on the right side of the graph, and we believe that this is because as the evaluation score converges, the randomness in the evaluation score sometimes exceeds the expected improvement for more utility calls. We will add more points on these graph as well as confidence bands on these graphs to illustrate this point if accepted.\n\n> How often is the true reference included in your pseudo reference set? \n\nIn Freitag et. al., 2022, the true reference is shown to have very low probability under their model, so we assume that the true reference is almost never in our pseudo-reference sets for sentences over a certain length.\n\n> I think one more curve in the same figure which is the number of remaining hypotheses (or maybe also add the current reference set size) would help better understand the process.\n\nWe agree that such a figure that shows the average number of hypotheses remaining per pseudo-reference list size would provide insight and intuition into the process, and we will add this in the main text for de-en and in the appendix for en-et and tr-en. \n\nLastly, thank you for the suggestions for style and presentation, which we will incorporate.\n\nMarkus Freitag, David Grangier, Qijun Tan, and Bowen Liang. 2021a. High quality rather than high model probability: Minimum bayes risk decoding with neural metrics. arXiv preprint arXiv:2111.09388.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The paper is very well-written. The problem -> motivation -> existing solutions -> proposed solution -> explaining the solution -> making compromises for practical uses -> showing automatic results -> extending to human evaluations logic line is super clear and easy-to-follow.\n\nThe experiments show convincing results which clearly support the claims of the authors, that the proposed pruning method significantly reduces utility calls without hurting the translation accuracy.", "reasons_to_reject": "Can't think of any. I like this paper.", "questions_to_authors": "One thing that is not crystal clear to me is why the pseudo-reference list grows. Is it because that the initial list contains not so good translations (the ones that will get pruned)? Is H1 and R1 the same? Does sampling more references and adding them to R improve the quality of the reference set? If so, why not also prune away those sentences that get pruned away?\n\nAnother question is about Figure 2, top-right sub-figure. Why do the scores go down in the end? Do I understand correctly that the final hypothesis has to come from H1 because no new hypothesis is ever added in later iterations? If so, does that mean at utility call 3500 for prune_alpha, the best hypothesis so far still gets somehow thrown away with more utility calls? How often is the true reference included in your pseudo reference set? I think one more curve in the same figure which is the number of remaining hypotheses (or maybe also add the current reference set size) would help better understand the process.", "paper_topic_and_main_contributions": "This paper proposes an iterative pruning algorithm to reduce the number of hypotheses considered in minimum Bayes risk decoding (MBR) while gradually growing the number of candidate samples for utility estimation, for the task of neural machine translation.\n\nThe authors estimate the probability of a hypothesis being the winner among all hypotheses in question with nonparametric bootstrap resampling. In Layman's terms, at a certain iteration of the algorithm, a hypothesis has a chance to be pruned when it does not beat a certain other hypothesis often enough, when comparing with different sets of references.\n\nThe proposed algorithm significantly reduces the number of utility calls, while maintaining similar scores under the same utilitiy function. This is especially useful if each utility call gets expensive, e.g. querying a neural model to compare two translations.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "L085 and L090, maybe not use italic for MAP and MBR in the superscript.\n\nFigure 2, maybe legends in each subplot? maybe add current hypotheses set size curves.\n\nTable 1, I would prefer if three vertical bars are added to separate the test sets, I was confused to read beta, alpha, alpha and again beta the first time I saw the table. Also, why not include a row with the actual run times? I would expect linear reductions in runtimes with reductions in number of utility calls, but would be nice to see it. For that matter, maybe also add a column for a typical beam search setup for a more complete comparison?"}}, {"review_id": "oyrS9bRyIE", "reviewer": "Reviewer_urSQ", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": 5, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and for the encouraging words!\n\n> The only thing that I found somewhat dissatisfying was that it would have been nice to have a wall-clock time comparison [...]\n\nThe current set of experiments were done in a simulated mode where hypothesis, pseudo-references, and utilities are all generated in advance (in a way that doesn’t affect the validity of our work) but we agree that this would be important to include, so we implemented a practical version of our algorithm and logged timings. Due to time constraints, we executed our yet-unoptimized implementation on 60 random examples from the de-en test set using COMET as the utility metric. \n\n|                | Standard | Pruning | Beam search (k=5) |\n| -------------- | -------- | ------- | ----------------- |\n| Generate $\\mathcal{H}$        | 20.7     | 20.4    | 14.5              |\n| Generate $\\mathcal{R}$        | 33.1     | 74.7    |                   |\n| Get sentence embeddings | 61.7     | 48.3    |                   |\n| Compute utilities      | 116.5    | 5.0     |                   |\n| Compute bootstrap      |          | 0.3     |                   |\n| Total               | 232.1    | 148.7   | 14.5              |\n\nAs expected, the most dramatic gains are in the “compute utilities” row which is linearly related to the number of utility calls shown in Table 1. There are some optimizations that we will make: 1) we have not deduplicated sequences in the utility computation, and 2) the source-side encoding is recomputed for each iteration in the iterative pruning algorithm, which is why generating $\\mathcal{R}$ is slower in pruning than in standard MBR. If accepted, we will make these changes and run it on the full test set for the camera-ready.\n\n> There was no mention of whether the code would be released. Hopefully the authors will release the code to improve reproducibility.\n\nThis was an oversight on our part. We will release the code if accepted.\n\n>I have one major suggestion for a presentation improvement. I was actually quite confused at first by Equations (3) and (4) due to their unusual notation [...]\n\nReviewer GsRs04 also found this confusing, and in response to both of your suggestions, we would change Equation 3 to:\n\n$p\\bigl(\\bigwedge\\_{\\bar{y}\\in\\mathcal{H}} U (y, p_\\theta(·|x)) ≥ U (\\bar{y}, p_\\theta(·|x))\\bigr)$\n\nand Equation 4 to:\n\n$\\frac{1}{n}\\sum^{n}_{i=1}{1 \\bigwedge\\_{\\bar{y}\\in\\mathcal{H}_t}{U(y,\\hat{\\mathcal{R}^i_t})\\geq U(\\bar{y},\\hat{\\mathcal{R}^i_t})}}$\n\nand Equation 5 to:\n\n$\\frac{1}{n}\\sum^{n}\\_{i=1}{1({U(y,\\hat{\\mathcal{R}^i_t})\\geq U(\\tilde{y},\\hat{\\mathcal{R}^i_t})})}$ where $\\tilde{y}=\\arg\\max_{\\bar{y}\\in\\mathcal{H}_t}U(\\bar{y}, \\mathcal{R}_t)$", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Overall the work is:\n1. tackling an important problem of improving the efficiency of MBR. MBR is a very effective and flexible method to improve accuracy of systems but its time efficiency is a major downside.\n2. the formulation of this is elegant and statistically well grounded.\n3. experimentation is thorough and covers the important bases given that the paper is short.\n\nI think this is a very nice paper, and could be considered for an outstanding paper award.", "reasons_to_reject": "I do not have any reason to reject this paper. It is well written and solid, especially for a short paper. I will likely advocate strongly for its acceptance (unless I'm missing something).\n\nThe only thing that I found somewhat dissatisfying was that it would have been nice to have a wall-clock time comparison, but there are so many factors that can go into that (how well the decoding algorithms are optimized, and how well the utility function calculations are implemented), so I think the paper is justified without these.\n\nThere was no mention of whether the code would be released. Hopefully the authors will release the code to improve reproducibility. However, the methodology is straightforward enough that I think the methods could be reproduced without.", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper proposes a new iterative algorithm for performing minimum Bayes risk decoding, and does experiments on machine translation.\n\nThe basic idea behind the algorithm is to use bootstrapping to estimate the probability that a particular hypothesis will end up being the final winner.", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "I have one major suggestion for a presentation improvement. I was actually quite confused at first by Equations (3) and (4) due to their unusual notation. Normally (I think) the \"for all\" sign normally comes before the term it is applied to, so I would rearrange the equation for clarity."}}]

Author rebuttal:

Meta-review: This paper presents a bootstrapping method to dynamically truncate the hypothesis set in Minimum Bayesian Risk decoding.
The reviewers found this paper very exciting, appreciating the problem, the solution, the results, and the writing. There were very minor concerns raised and they were addressed.
Decision: Accept-Main