Machine Translation Decoding beyond Beam Search (2021)

Abstract: Beam search is the go-to method for decoding auto-regressive machine translation models. While it yields consistent improvements in terms of BLEU, it is only concerned with finding outputs with high model likelihood, and is thus agnostic to whatever end metric or score practitioners care about. Our aim is to establish whether beam search can be replaced by a more powerful metric-driven search technique. To this end, we explore numerous decoding algorithms, including some which rely on a value function parameterised by a neural network, and report results on a variety of metrics. Notably, we introduce a Monte-Carlo Tree Search (MCTS) based method and showcase its competitiveness. We provide a blueprint for how to use MCTS fruitfully in language applications, which opens promising future directions. We find that which algorithm is best heavily depends on the characteristics of the goal metric; we believe that our extensive experiments and analysis will inform further research in this area.

## introduction sequence to sequence model decoding remains something of a paradox. the most widely adopted training method for these models is maximum likelihood estimation (mle), which aims at maximising the probability of the ground truth outputs provided in the training datasets. consequently, decoding from mle-trained models is done by trying to find the output to which the model assigns maximum likelihood. unfortunately, as models usually predict tokens one by one, exact search is not feasible in the general case and practitioners resort to heuristic mechanisms instead. the most popular of these heuristics is beam search @xcite , which maintains several hypotheses in parallel and is guaranteed to find a more likely output than the more basic greedy decoding. this approach has some obvious flaws: for one, it is completely agnostic to the actual metrics (or scores) practitioners actually want to optimise. even more crucially, in most cases beam search fails at the one thing it is supposed to do: finding the optimal output sequence (w.r.t the model), as shown by @xcite . also alarming are the findings of @xcite , proving that traditional search mechanisms can yield infinite-length outputs, to which the model assigns zero probability. finally, the use of likelihood as a training objective has a spectacular sideeffect: it causes trained models to have an inordinate fondness for empty outputs. by using exact search on the output likelihood in machine translation, @xcite show that in more than half of cases the highest scoring output according to the model is the empty sentence! all told, we rely on models placing a surprising emphasis on empty outputs, and on a decoding mechanism which usually fails to find optimal outputs; and both ignore the relevant metrics. one can then justifiably wonder why we observe impressive mt results. @xcite provide an apparently paradoxical explanation: it is precisely because the decoding mechanisms are imperfect that models produce outputs of high quality. @xcite elaborate on this assumption; they show that beam search optimises for a slightly modified likelihood objective, promoting uniform distribution probability inside sentences. this state of affairs seems highly unsatisfactory. while a whole body of work has been devoted to alleviating these issues, most approaches have been concerned with training @xcite @xcite @xcite @xcite , or making the search mechanism differentiable @xcite . these have resulted in performance increase, but they still rely on likelihood as an objective for decoding. further, @xcite shows that performance improvements using rl are limited and poorly understood. in this paper, we focus instead on contrasting the performance of beam search to alternative decoding algorithms aimed at optimising various metrics of interest directly, via a value function (or the metric itself when available). notably, we experiment with variants of the powerful monte carlo tree search (mcts) @xcite mechanism, which has a proven track record in other sequential applications @xcite . we investigate whether, by optimising the metric of interest at test time, one can obtain improved performance compared to likelihood-based approaches, and whether performance scales with the amount of computation -as opposed to that of beam search which has been shown to degrade with large beam sizes @xcite . we concentrate on machine translation (mt), an emblematic, well-studied sequence to sequence task, with readily available data and benchmarks. contributions. (i) we recall that there are two different types of metrics: reference-based scores, which rely on ground truth translations, in contrast to reference-less ones. we design a new score, multilingual bertscore, as an imperfect but illustrative example of the latter. (ii) we introduce several new decoding algorithms, detailing their implementation and how best to use them for mt. we provide a blueprint for how to use mcts profitably in nlp (with pseudocode for a batched numpy-based @xcite implementation), which opens the door for many exciting applications. (iii) we run extensive experiments to study the performance of decoding mechanisms for different metrics. we show that beam search is the best option only for reference-based metrics. for those, value-based alternatives falter as the value problem is too hard -since it ultimately relies on reconstructing hidden information. for reference-less scores, beam search is outperformed by its competitors, including mcts. outline. we go over the related work in section 2. in section 3, we contrast several types of metrics, and introduce illustrative examples. we review beam search and introduce alternative algorithms in section 4. we explain how we train the required value function for value-based methods in section 5. in section 6 go over experimental details and results. finally, we discuss our results, their limitations and possible next steps in section 7. ## related work autoregressive models for sequence generation typically output more coherent sequences @xcite , as each token prediction takes into account its predecessors. however, this gain comes at a cost: finding the sequence with maximum probability according to the model -argmax @xmath0. given the size of the (token) action space a, exact search appears out of the realm of possibility. so we resort to incremental prediction; picking individual tokens, without knowing how these choices will impact the final likelihood. we describe the three most widely used methods, which all pick tokens one by one from left to right. the sampling method predicts tokens by directly sampling from the model policy π(y t+1 |x, y 1 ...y t ), computed via a softmax operator applied to the model logits @xcite -possibly with a temperature parameter. the greedy search method incrementally picks the tokens with highest probability according to the model (akin to sampling with very low temperature). this inexpensive approach can be seen as a special case of the sampling method, with very low temperature. finally, beam search maintains a beam of k possible translations, updating them incrementally by ranking their extensions via the model likelihood. while k times more expensive than the previous approaches, beam search has stood the test of time, resulting in steady performance improvements on mt tasks. building on these methods, a number of improvements have been proposed. @xcite explore out-of-order decoding, where the model additionally learns the order in which to decode tokens. this provides benefits in a variety of tasks, but unfortunately not mt. @xcite use look-ahead in the beam search to take into account future likelihood, which yields improvements on low-data tasks, but again does not outperform beam search on mt. @xcite speeds up beam search for monotonous scores. several works focus on the interplay between the incremental models and beam search. @xcite shows that performance is not monotonically increasing with beam size, but degrades after a fairly small value of k. @xcite devise a clever exact search mechanism, relying on the fact that likelihoods are monotonically decreasing with size. while still prohibitively expensive, this approach underlines several key facts. first, beam search does not recover argmax @xmath1, whatever the computational budget. second, argmax @xmath2. @xcite propose an interesting explanation for this observation: while models are good at spreading probability mass over a large quantity of acceptable outputs, they are unable to effectively pick the best one. indeed, the mode of the distribution might even be disjoint from the area where the models assigns the majority of probability mass. they propose using minimum bayes risk decoding, which leverages the whole distribution rather than only its mode, and can outperform vanilla beam search in low-resource scenarios. @xcite , in a similar vein, develop an additional voting-based step on top of beam search to select more representative sequences, based on similarity measures. a large body of work has been dedicated to improving sampling diversity, which plays a key role in many nlp applications -though not usually in machine translation. @xcite propose only sampling from the top k tokens according to the policy to avoid sampling from the tail of the distribution. @xcite adopt a similar approach, but instead of fixing k they fix p, the size of the 'nucleus' of the distribution from which sampling is allowed to select tokens. this performs better on open-ended tasks. @xcite propose a search mechanism in-between sampling and beam search, which produces provably unique samples by leveraging the gumbel-max trick @xcite . @xcite use a different, much more expensive flavor of mcts to add diverse samples to a larger nmt system: instead of relying on direct value estimation, they rely on (expensive) rollouts to estimate node values. finally, the most closely related method to our proposed mcts decoding is value-guided beam search, as developed by @xcite ; @xcite for mt and image captioning. contrary to all other methods presented in this section, this approach does not solely rely on model likelihood. in both papers a value network -estimating the eventual score from an unfinished sample -is trained in addition to the policy network. then instead of following the likelihood to select the hypothe-ses on the beam, one uses a linear combination of the policy logits and the value. this approach has shown improved performance compared to vanilla beam search; notably, it is less sensitive to the chosen beam size. while this method uses the value exclusively for one-step look-aheads, mcts can be leveraged to explore further in the future. additionally, it requires evaluating the value score of all tokens at each step, which can be prohibitively expensive if the action space is big (in mt, one routinely uses vocabularies of size larger than 30000). ## machine translation metrics there are two main evaluation strategies for mt outputs. the first one crucially relies on having access to a held-out test set of high quality (input, output) sentence pairs (x, y x ) @xmath3. one can then compute a monolingual similarity score between the system's outputs (ŷ x ) @xmath4. common metrics include bleu @xcite , meteor @xcite which takes into account synonyms; or bertscore @xcite . this type of metrics are referred to as reference-based, as they require access to ground truth translations. the second is concerned with assessing translation quality for source sentences for which one does not have reference translations. to determine whether machine-generated outputs are accurate enough or require human modification, one relies on multilingual quality estimation metrics @xcite . these do not rely on ground truth sequences; instead comparing produced samples to sources sentences directly. expert human evaluation is perhaps the most relevant such score, but many automated alternatives exist @xcite ; see e.g. @xcite . these metrics are referred to as reference-less. reference-based metrics provide high quality evaluation signal, and are well-suited to comparing average model performance (trusting that results on the unseen test set generalise to other domains of interest). however, they rely on the quality of the test set translations (which are usually unique, hence somewhat arbitrary), and cannot be used to evaluate the quality of models' prediction for specific unseen inputs. in contrast, reference-less metrics are harder to access or approximate but can be used without ground truth translations. we use two reference-based metrics in our experiments: bleu and bertscore. we intro-duce another, reference-less metric: multilingual bertscore. note that while a translation model likelihood can be considered a reference-less metric, it comes with the unusual property that it is decomposable. we thus treat it as a special case. bleu @xcite . the bleu score computes modified precisions for n-grams (typically 1 ≤ @xmath5. these precisions are averaged geometrically, and multiplied by a brevity penalty. this metric is meant to be used at the corpus level; it is unstable at the sentence level. it is the de facto gold standard for comparing mt algorithms, though as it crucially relies on access to a dataset of reference translations, it is not available to assess translation quality at decoding time. bertscore @xcite . by contrast, bertscore is a sentence-level metric to compare a candidate sentence to a reference translation. it relies on several consecutive steps: first, computing contextual embeddings for each token in both sentences with a shared bert @xcite model; second, computing all pairwise cosine similarities between embeddings of the two sentences; third, greedily aligning tokens based on these similarities; finally, averaging the similarities of the aligned tokens. compared to bleu, bertscore is found to correlate slightly better with human judgement. importantly for decoding purposes, it is a sentence-level metric (which is averaged to produce a corpus-level statistic). multilingual bertscore. while bertscore is designed as a monolingual metric, we repurpose it as a multilingual one by using it to compare a candidate to its source sentence (instead of reference translation). both sentences are in different languages, but this is fine as long as the underlying bert model is itself multilingual. 1 we call this new metric multilingual bertscore. its performance relies on the underlying bert model's ability to map related tokens in different languages to similar embeddings. because of the one-to-one nature of the alignment phase, we expect it to score more highly translation pairs that have a one-toone token correspondence, rather than syntactically different pairs. we thus expect it to make sense for pairs of syntactically similar languages. we stress that we do not advocate widespread adoption of this ## decoding algorithms in this section, we go over the details of each algorithm, and its adaptations to better suit referencebased or reference-less metrics. we separate them in three categories: (i) algorithms based on likelihood maximisation, (ii) value-based mechanisms which rely on approximating metrics via a value function, and (iii) ranking-based methods which access the metrics directly and pick the highestscoring example out of a pool of finished candidates. of course, ranking-based methods are only usable for reference-less metrics, as referencebased metrics are not computable at test time. we provide a high-level comparison of all algorithms in ## training a value network several of the algorithms we detail in section 4 make use of a value network. we train these by: the second step is mandatory to obtain a score distribution to train the value model on, in the case of reference-based metrics. indeed, the scores of the optimal supervised policy are all perfect (comparing y x to y x ), thus uninformative, making it impossible to train a value network on. relying on a sample rather than on the ground truth sentence to compute the score has another advantage: the samples follow the policy π sup so the value will be the one associated with a trained policy, as the one we use during decoding, rather than with the optimal supervised policy. losses. we train the policy by minimising its kullback-leibler divergence with the initial supervised policy π sup : l π = d kl (π||π sup ). we reframe the value regression problem as classification by discretising the score interval into buckets. we emulate training our value function on unfinished samples by adding a value loss term at every step, and reusing the transformer decoder causality mask. the prediction target is the same across all time-steps: the one-hot vector indicating in which bucket the final score m falls. we use the cross-entropy loss function. the trouble with reference-based metrics. in practice, we find that learning a value function for reference-based metrics (such as bleu or bertscore) is difficult. to understand why, we run an ablation to distinguish between the three subtasks a value function must perform: (i) approximate the score, (ii) predict the end of a trajectory from an unfinished prefix, and (iii) assess the translation quality of a pair of finished sentences in different languages. to separate concerns, we run the following experiments: for (i), we train decoder inputs encoder inputs sample prefix finished sample source 0.112 (full setup) 0.111 (iii) reference target 0.065 (ii) 0.002 (i) our network to predict bleu given ground truth targets (rather than source sentences) and finished samples (instead of prefixes). for (ii), we give the network ground truth targets and unfinished samples. finally, for (iii), we give the network source sentences and finished samples (thus removing the need to predict the future of trajectories). we observe that: the error is very low for (i); higher, but significantly improved over the full setup for (ii); and surprisingly, roughly identical to the full setup for (iii). thus the real difficulty lies in (iii). one possible explanation for this result is that the value network is missing a key input. indeed, in the case of reference-based metrics, the score is computed between a sample ŷx and a ground truth reference y x ; but the value network only has access to the source sentence x and a prefix of ŷx . thus before it can compute a precise score approximation, it first has to infer y x from x. but of course, inferring y x from x is exactly the original machine translation problem, which makes the value problem empirically harder than its policy counterpart on our dataset. ## experiments we detail our general setup, then report results for all 3 metrics we consider, and finally study how they scale with increasing search budget. detailed tuning methodology can be found in appendix b. ## discussion the main takeaway from our experiments is that which algorithm is best depends heavily on the metric to optimise. this reinforces the notion that one should carefully consider when picking a decoding mechanism for a machine translation pipeline, rather than default to beam search. second, we find that optimising reference-based metrics (e.g. bleu) via a value function is surprisingly hard. while distinguishing large gaps in quality is easier than modelling the policy, discriminating between good candidates is in practice as hard as the policy problem, since a first required step is estimating the ground truth sentence. indeed, empirically we observe relatively low quality value networks, and comparatively little improvements with value-based decoding methods (especially on the small ende dataset). using a value function to optimise reference-less metrics is more promising. third, we show that mcts is not only a valid way of decoding for machine translation tasks, but also the best option in some use cases. we study its strengths and weaknesses, and demonstrate that its performance is crucially linked to the ease of learn-ing a good value function. we include pseudo-code for an easily reproducible numpy implementation in appendix f. all told, we provide a blueprint for how to use mcts efficiently in nlp with state-ofthe-art transformer models. finally and somewhat surprisingly, we find that whenever access to the score is possible, the simple s+r method performs well. more experimentation is required to understand why; but at any rate, it should be a strong contender in this specific setup. future directions. we have shown that optimising for reference-less metrics is easier than for reference-based ones. the ultimate reference-less metric for machine translation is human translation assessment. thus it seems natural to consider training a score directly from human evaluation of translation pairs, and to later focus on optimising it via mcts. another natural extension is a full-blown rl algorithm; iteratively improving policies via valueguided search and training value functions on search-improved policies, getting closer to the optimal policy and value at each step.