Hyperparameter-Free Approach for Faster Minimum B ayes Risk Decoding (2024)

Abstract: Minimum Bayes-Risk (MBR) decoding is shown to be a powerful alternative to beam search decoding for a wide range of text generation tasks. However, MBR requires a huge amount of time for inference to compute the MBR objective, which makes the method infeasible in many situations where response time is critical. Confidence-based pruning (CBP) (Cheng and Vlachos, 2023) has recently been proposed to reduce the inference time in machine translation tasks. Although it is shown to significantly reduce the amount of computation, it requires hyperparameter tuning using a development set to be effective. To this end, we propose Adaptive Minimum Bayes-Risk (AMBR) decoding, a hyperparameter-free method to run MBR decoding efficiently. AMBR is derived from the observation that the problem of computing the sample-based MBR objective is the medoid identification problem. AMBR uses the Correlated Sequential Halving (CSH) algorithm (Baharav and Tse, 2019), the algorithm with the best performance guarantee to date for the medoid identification problem, to compute the sample-based MBR objective. We evaluate AMBR on machine translation, text summarization, and image captioning tasks. The results show that AMBR achieves on par with CBP, with CBP selecting hyperparameters through an Oracle for each given computation budget.

## introduction the goal of natural language generation is to generate text representing structured information that is both fluent and contains the appropriate information. one of the key design decisions in text generation is the choice of decoding strategy. the decoding strategy is the decision rule used to generate sequences from a probabilistic language model. beam search has been widely used in many closeended sequence generation tasks including machine translation @xcite @xcite ), text summarization @xcite , and image captioning @xcite . however, beam search is known to have several degeneration problems. for example, @xcite reports that beam search can yield infinite-length outputs that the model assigns zero probability to. minimum bayes-risk (mbr) decoding has recently gained attention as a decoding strategy with the potential to overcome the problems of beam search @xcite @xcite @xcite . unlike beam search which seeks to find the most probable output, mbr decoding seeks to find the output that maximizes the expected utility. mbr decoding involves two steps. it first samples outputs from the probabilistic model and then computes the utility between each pair of outputs to find the hypothesis with the highest expected utility. one of the most important shortcomings of mbr decoding is its speed. the computational complexity of mbr decoding is o(n • g + n 2 • u ), where n is the number of samples to be used, g is the time to generate a sample, and u is the time to evaluate the utility function. as the utility function is typically a time-consuming neural metric such as bleurt and comet @xcite @xcite , o(n 2 •u ) is the dominant factor of the computational complexity. confidence-based pruning (cbp) has recently proposed to reduce the number of evaluations of the utility function @xcite . cbp is shown to be effective in machine translation tasks, significantly reducing the required computation using both lexical and neural utility functions with a negligible drop in the quality. although cbp is shown to be efficient, the performance of cbp is significantly influenced by the choice of hyperparameters. as such, cbp requires a development set for the tuning of these hyperparameters. additionally, cbp cannot dictate the speed at which it completes tasks. the hyperparameters of cbp only offer indirect control over the number of evaluations. to this end, we propose adaptive minimum bayes-risk (ambr) decoding, a hyperparameterfree algorithm to compute the sample-based mbr objective efficiently. ambr reformulates the mbr objective as the medoid identification problem (rdusseeun and @xcite and solves it using the correlated sequential halving (csh) algorithm, the best algorithm to date to solve the medoid identification problem @xcite . the strength of ambr is that it is free from hyperparameters. unlike cbp where it needs to tune the hyperparameters to empirically determine the best set of hyperparameters to achieve the desired trade-off between the speed and the quality, ambr determines the best resource allocation automatically from the computational budget specified by the user. we evaluate the performance of ambr in machine translation, text summarization, and image captioning tasks. the empirical results show that ambr is on par with cbp with oracle hyperparameters. they are roughly 4 to 8 times faster than mbr with a marginal drop in the output quality. the result indicates that using ambr, mbr decoding can be run efficiently for a given computation budget specified on the fly without hyperparameter tuning on a development set. ## background conditional text generation is the task of generating an output sequence h given an input sequence x. probabilistic text generators define a probability distribution p model (h|x) over an output space of hypotheses y. in this paper, we denote p model (h|x) by p model (h) for brevity. the goal of decoding is to find the highest-scoring hypothesis for a given input. one of the most common decision rules is maximum-a-posteriori (map) decoding. map decoding finds the most probable output under the model: although it seems intuitive to solve this map objective, prior work has pointed out two critical problems with this strategy. first, since the size of hypotheses set |y| is extremely large, solving it exactly is intractable. second, the map objective often leads to low-quality outputs @xcite @xcite . in fact, @xcite shows that h map is often the empty sequence in their experiment setting. as such, beam search is commonly used as a heuristic algorithm to solve decoding problems @xcite . beam search is known to generate higher-quality sequences than map decoding in a wide range of tasks. still, prior work has reported the degeneration issues of beam search such as repetitions and infinite-length outputs @xcite . ## confidence-based pruning (cbp) confidence-based pruning (cbp) is recently proposed by @xcite to significantly reduce the number of evaluations of the utility function. the idea is to iteratively evaluate the hypotheses with a subset of the reference set to prune the hypotheses not promising enough. cbp keeps a current candidate set h i and a current reference set r i during the run. the candidate set starts from the whole candidates (h 0 = h) and the reference set starts empty (r 0 = ∅). at every iteration i, it draws samples and adds them to the reference set until the size of the reference set reaches the limit r i , where {r i } are hyperparameters. then it computes the incumbent best solution h * i at i-th iteration: then it generates a series of bootstrap reference sets rb i which is a with-replacement size-|r| resample of r i . using a series of bootstrap reference sets, it computes the estimated win ratio of each hypothesis against h * i in h i : although cbp is shown to be significantly more efficient than the standard mbr, there are several shortcomings. first, it requires a hyperparameter tuning using the development set. the sample size scheduler r i and the confidence threshold α need to be tuned to optimize the performance. the number of bootstrap reference sets b is also a hyperparameter that needs to be tuned according to the quality and the speed trade-off. note that the optimal set algorithm 1: adaptive mbr (ambr) (correlated sequential halving for mbr) input: a set of candidates h, references r, and a budget t output: a hypothesis h ambr 1: h 0 ← h 2: r 0 ← ∅ 3: @xmath0, |r|) 4: for @xmath1: ## adaptive minimum bayes risk (ambr) decoding we propose adaptive minimum bayes-risk (ambr) decoding, a variant of mbr that can efficiently compute the mbr objective under a budget on the maximum number of evaluations that a user can specify. the advantages of ambr over cbp are twofold. first, ambr has no hyperparameter. the schedules of the number of references and the candidates are automatically determined by the algorithm. second, a user can enforce the upper bound of the computation budget to ambr. ambr enforces the budget constraint and the algorithm automatically schedules how to use the limited resource accordingly. ambr is derived from the observation that mbr decoding is the medoid identification problem @xcite : the problem of computing h mc (eq 4) is tantamount to determining the medoid of h. the medoid, denoted as y * , is defined as the point in a dataset y that minimizes the sum of distances to all other points: foot_0 let @xmath2, @xmath3, and @xmath4. then, the problem can be translated into the following: this is exactly the objective defined in eq. ( 4 ). our approach is to use the best algorithm proposed so far for solving the medoid identification problem and repurpose it for mbr decoding. the algorithm with the best performance guarantee to date for solving the medoid identification is the correlated sequential halving (csh) algorithm @xcite . we describe the procedure of ambr in algorithm 1. ambr keeps a current candidate set h i which starts with h and a current reference set r i which starts as an empty set. first, it picks t i hypotheses from r and adds them to the current reference set r i+1 where t i is automatically determined by the number of candidates and the budget. then it computes u(h, y) for all h in the current candidate set h i and for all y in the current reference set r i+1 . the average utility of @xmath5. then, it runs the halving operation, pruning the lower half of the candidates according to the current estimate û . ties are broken arbitrarily. it repeats this process for up to ⌈log n ⌉ -1 times and returns the candidate with the best estimate in h i at that point. the procedure of algorithm 1 is identical to the procedure of csh with modification to the notations to place it in the context of the decoding problem. our contribution is the reinvention of csh which is proposed as a solution to the medoid identification problem as a tool to compute the mbr objective adaptively by converting the sum of distances to the expected utility. ## experiments we evaluate the performance of the efficient mbr decoding algorithms on machine translation, text summarization, and image captioning tasks. we evaluate the performance of the mbr decoding algorithms under a budget constraint on the number of evaluations. we evaluate with a budget size of 1/32, 1/16, 1/8, 1/4, 1/2 of n (n -1), the number of evaluations of the standard n × n mbr with n samples. 2 we use epsilon sampling with ϵ = 0.02 as a sampling algorithm (hewitt et al., 2 we assume u(h, h) is a constant for all @xmath6. 2022; @xcite . temperature is fixed to 1.0. we use the same set of samples for all the algorithms. we compare the performance of (standard) mbr, n-by-s (nbys), coarse-to-fine (c2f), confidence-based pruning (cbp), and ambr. standard mbr refers to the implementation of mbr which uses the same set of samples for the candidate and reference set. we run standard mbr with the number of samples n ′ ∈ {1...n }. the number of evaluations for standard mbr is n ′ (n ′ -1). we implement n-by-s in a way that uses all the samples h as the candidate set and reduces the size of references according to the budget. that is, it randomly subsamples s ′ hypotheses from h to be the reference set so that s ′ is the smallest integer such that (n -1)s ′ ≥ t . for c2f, we set s ′ = n and n ′ to be the smallest integer such that n ′ (n -1) ≥ t . we run a hyperparameter sweep for cbp to find the best hyperparameters. we search over r 0 ∈ {1, 2, 4, 8} and α ∈ {0.8, 0.9, 0.99}. following cheng and vlachos (2023), we set the schedule of the size of the references r i to double each step: r @xmath7. the number of bootstrap reference sets is 500. we enforce the budget constraint to cbp by terminating the iteration once the number of evaluations reaches t . we run cbp with each set of hyperparameters on the test set to find the best hyperparameters. the result of the hyperparameter search is described in appendix d. we observe that the best set of hyperparameters of cbp is dependent on the size of the budget. as such, we report the oracle score, the best score over all combinations of hyperparameters for each budget. ambr is implemented as in algorithm 1 without using eq. ( 9 ). thus, lemma 1 does not apply to the algorithm we evaluate in this section. we run nbys, cbp, and ambr five times for each budget size and report the average, minimum, and maximum scores over the runs. we use huggingface's transformers library for running all the experiments @xcite . all the experiments are conducted using publicly available pretrained models and datasets for reproducibility. due to limitations in computational resources, we evaluate the first 1000 entries of each dataset. ## related work csh @xcite is not the only algorithm proposed to solve the medoid identification problem. there are several other algorithms to solve the medoid identification @xcite @xcite . we pick to use csh as it has the best theoretical performance. algorithms to solve the problem of identifying the best option out of the candidates with a budget constraint (fixed-budget best-arm identification problems) are known to be highly sensitive to the choice of the hyperparameters if they have ones @xcite . in fact, we observe that the effectiveness of cbp hinges on the appropriate selection of hyperparameters, given each budget constraint. ## conclusions we propose adaptive minimum bayes-risk (ambr) decoding, a hyperparameter-free algorithm for efficient mbr decoding. ambr considers the problem of computing the mbr objective as the medoid identification problem and uses the known best algorithm to solve it. the strength of the ambr is that it doesn't need a development set to tune the set of hyperparameters. ambr au-tomatically computes the strategy on the fly given the budget specified by the user. experimental result shows that the performance of ambr is on par with cbp with hyperparameters picked by an oracle on machine translation tasks. ambr outperforms cbp on text summarization and image captioning tasks, using the same set of hyperparameters as in machine translation tasks for cbp. we speculate that cbp requires a different set of hyperparameters for each task to perform on par with ambr. we believe that ambr will be a practical choice for future mbr decoding because of its applicability and significant performance improvements.