Empirical Analysis of Beam Search Curse and Search Errors with Model Errors in Neural Machine Translation (2023)

Abstract: Beam search is the most popular decoding method for Neural Machine Translation (NMT) and is still a strong baseline compared with the newly proposed sampling-based methods. To better understand beam search, we investigate its two well-recognized issues, beam search curse and search errors, at the sentence level. We find that only less than 30% of sentences in the test set experience these issues. Meanwhile, there is a related phenomenon. For the majority of sentences, their gold references have lower probabilities than the predictions from beam search. We also test with different levels of model errors including a special test using training samples and models without regularization. We find that these phenomena still exist even for a model with an accuracy of 95% although they are mitigated. These findings show that it is not promising to improve beam search by seeking higher probabilities in searching and further reducing its search errors. The relationship between the quality and the probability of predictions at the sentence level in our results provides useful information to find new ways to improve NMT.

## introduction beam search has been the most popular decoding (inference) method for neural machine translation (nmt) @xcite . @xcite foot_0 and our experimental results (in appendix a) show that the beam search is still a very strong baseline compared with the recently proposed sampling-based methods, including top-k sampling, nucleus (top-p) sampling @xcite and minimum bayes risk (mbr) decoding @xcite . this is verified with different evaluation methods: bleu, meteor, and comet @xcite . meanwhile, there are still open issues deserving further exploration for the beam search. one widely recognized issue is a phenomenon called beam search curse @xcite @xcite . beam search tends to get worse performance when the beam size increases. this issue is counterintuitive. usually, it is expected that using a larger beam size finds a sequence with higher probability in the search space and gets better quality. another issue is search error @xcite , which means that the beam search as a heuristic method is not guaranteed to find the sequence with the largest probability in the search space. @xcite implement exact search which can find the global maximum for experiments. they use it to assess the search errors in the beam search. this paper aims to better understand these two issues via empirical analysis. we look into beam search curse at the sentence level. although the beam search curse is consistently verified on the whole test set at the corpus level, only a small portion of sentences suffer from this issue. one-sixth of sentences in wmt17 en-de and de-en test sets get worse translations when the beam size increases, meanwhile a similar number of sentences get better translations. one of the reasons for the beam search curse is model error, which means that the model is not well fitted to the data. we investigate the beam search curse using the model checkpoints with different validation accuracies. we find that there is no strong correlation between the beam search curse and model accuracy if the corpus bleu score is used for evaluation. but there is an obvious correlation using the oracle bleu score. we assess search error using exact search with a length constraint. exact search can be regarded as a beam search with its beam size as large as the size of vocabulary. we find that only less than 30% of sentences suffer from search errors using the beam search even with a small beam size like 5. for the majority of sentences, beam search can generate the sequences with the largest probability. we also compare exact search with beam search in terms of the quality of the predictions. exact search gets significantly worse bleu scores than beam search at the corpus level. at the sentence level, the number of sentences with worse quality from exact search is only slightly larger than those with better quality. this result is consistent with the experiments in the beam search curse issue. our experiments also demonstrate one phenomenon that is related to these two issues. the majority of the gold references get lower probabilities than the predictions from beam search. although beam search seeks the sequences with high probability in principle, this result shows that it is the wrong direction to further pursue larger probabilities and smaller search errors. to investigate how beam search performs under very low model errors, we test a special case. we use models without regularization which have an accuracy of around 95% on training data. the test data in this case are samples from training sets to reduce the mismatch of data distributions between training and testing. in this case, the phenomena about exact search and gold references are still observed. these findings may contribute to future improvements in decoding and training methods. ## related work there are two approaches for decoding today: mode-seeking decoding and samplingbased stochastic decoding. mode-seeking is also known as maximum-a-posteriori (map) decoding @xcite . its objective is to predict a translation by searching a sequence y that maximizes log p (y|src; θ), where src is the source sentence and θ is the model parameter set. exact search @xcite aims to find the global maximum in the whole search space. due to the vast search space, exact search is intractable in real application. beam search @xcite is used as a viable approximation by extending the n most probable partial solutions at each decoding step, where n is called beam size. beam search is widely used for nmt. recently the sampling-based stochastic decoding @xcite @xcite is actively investigated. sampling methods are used in decoding to get a set of candidate sequences, then a decision rule is used to choose the final prediction among these candidates. although these methods are used for open-ended text generation tasks such as story generation, fernandes et al. (2022) and our experimental results (in appendix a) show that beam search is still a very strong baseline compared with these sampling-based methods for nmt. beam search curse is recognized as one of six challenges in nmt @xcite . @xcite and @xcite attribute its root cause to the length ratio problem via empirical study. with beam size increasing, beam search tends to get shorter predictions and results in lower bleu due to the brevity penalty in the definition of bleu scores. but it is a usual practice using length normalization methods and the issue of short predictions is significantly mitigated. on the other hand, the beam search curse also consistently exists with other evaluation methods such as meteor and comet. @xcite investigate the discrepancy gap which is defined as the difference in log-probability between the most likely token and the chosen token. they find that the majority of discrepancy happen in early positions and increasing the beam width leads to more early discrepancies. we investigate the beam search curse at the sentence level, which is orthogonal to their conclusion about the position of tokens. search error in nmt is intensively investigated by @xcite . they use an algorithm based on the deep first search to explore whether there is a sequence with a higher probability than the prediction from beam search. they also implement the exact search to find the sequence with the largest probability in the search space. in these research, the beam search curse and the search error are mainly investigated on the whole test set at the corpus level, not at the sentence level. and it's not investigated how these issues are related to model errors. the model error means that the model is not well fitted to the data. ## methodology we choose the widely used language pairs: en-de and de-en. besides a standard test, we conduct a special cleanroom test to investigate the issues with very low model errors. figure 1 depicts the distribution of sentence length in all test sets. comparing it with our experimental results, it shows that the sentence length is not an influential factor in the conclusions. ## zero search error gets worse quality we compare the bleu scores from exact search with beam5 at both the corpus level and the sentence level. in our experiments, we find that a zero gap of the sentence bleu score usually implies a zero probability gap as well, which means zero search error for beam5. the results at the sentence level in ## gold references get lower probability than predictions from beam search the experiments above show that sequences with higher log-probabilities do not necessarily get better bleu scores. this leads us to investigate the log-probabilities of gold references. we find that gold references get lower log-probability than the predictions from the beam search even with very low model errors. figure 5a illustrates the gap of log-probability between the gold references and beam5 for en-de. only for a few sentences, the gold references have higher log-probabilities than the predictions of beam5. figure 5b demonstrates the strong correlation between the gap of log-probability (as the x-axis) and the sentence bleu scores of beam5 (as the y-axis). when the gold references get lower log-probabilities than beam5, the sentence bleu scores of beam5 decrease. these two figures are results from the standard test with the big model. we also test using the training samples with models without regularization. results are illustrated in figure 5c and figure 5d . comparing these two test cases, we find that the gaps are reduced when the model errors are smaller in the latter case. however, the correlation between the log-probability and the sentence bleu still exists even for a model with an accuracy of 95% in the cleanroom test. case study and analysis prediction although action plans established by the high -level working group aim to limit migratory flows in the future , these plans do nothing to improve human rights , civil liberties and the economic situation of the countries concerned . log probablity: