Source-linked AI summary
On NMT Search Errors and Model Errors: Cat Got Your Tongue?
Felix Stahlberg, Bill Byrne
TL;DR
NMT decoding must search an exponentially large space, yet approximate beam search can miss the global best model score. The paper develops an exact beam-and-depth-first search procedure, finding frequent search errors and a stronger model preference for empty or very short translations. These results indicate that vanilla NMT has an adequacy problem that common length heuristics may not satisfactorily remedy.
Problem
The exponentially large NMT search space prevents exhaustive decoding, leaving unconstrained search errors difficult to quantify without exact inference.
Method
The paper combines beam search and depth-first search, pruning partial hypotheses using monotonic score bounds to find global best model scores.
Results
For 51.8% of sentences, NMT assigns the global best model score to the empty translation, while Beam-100 still produces 53.62% search errors.
Takeaways & Limitations
The findings indicate that vanilla NMT has an inherent bias toward shorter hypotheses, and simple length constraints or normalization are unlikely to remedy empty translations satisfactorily.
Takeaways & Limitations
The basic exact-pruning criterion applies to vanilla NMT but not directly to length normalization or word-reward models because they alter score monotonicity.
Abstract
from arXiv · showhide
We report on search errors and model errors in neural machine translation (NMT). We present an exact inference procedure for neural sequence models based on a combination of beam search and depth-first search. We use our exact search to find the global best model scores under a Transformer base model for the entire WMT15 English-German test set. Surprisingly, beam search fails to find these global best model scores in most cases, even with a very large beam size of 100. For more than 50% of the sentences, the model in fact assigns its global best score to the empty translation, revealing a massive failure of neural models in properly accounting for adequacy. We show by constraining search with a minimum translation length that at the root of the problem of empty translations lies an inherent bias towards shorter translations. We conclude that vanilla NMT in its current form requires just the right amount of beam search errors, which, from a modelling perspective, is a highly unsatisfactory conclusion indeed, as the model often prefers an empty translation.
1 Introduction
NMT inference seeks the most likely translation in an exponentially large search space, making exhaustive search impractical. The paper introduces exact decoding to quantify search errors and reveals that beam-search behavior is entangled with a severe tendency to prefer empty translations.
- 1 Introduction: NMT assigns a probability to each translation and seeks the most likely translation for a source sentence.This task is the decoding or inference problem.
- 1 Introduction: The translation space grows exponentially with sequence length, making complete enumeration impossible.With a vocabulary of 32,000 words, translations of 20 words or fewer already exceed 10^82 possibilities.
- 1 Introduction: Previous studies could not quantify unconstrained NMT search errors because no exact inference scheme was available for finding the global best model score.The proposed exact scheme is too slow for practical machine translation but suitable for analysis.
- 1 Introduction: The paper proposes exact decoding that exploits score monotonicity to safely prune partial hypotheses and identify global best scores.Because conditional log-probabilities are non-positive, partial hypotheses can be discarded once their score falls below a complete hypothesis's score.
- 1 Introduction: Exact search shows that beam-search errors coexist with a serious model error: the empty hypothesis often receives the global best model score.The authors connect these findings to the need for improved NMT adequacy modeling.
2 Exact Inference for Neural Models
Beam search approximates NMT decoding by retaining only a fixed number of left-to-right hypotheses, while exact inference combines score-based pruning with depth-first traversal. The approach is exact for vanilla NMT because scores decrease as hypotheses are extended, but this guarantee does not directly apply to length-normalized or word-reward models.
- 2 Exact Inference for Neural Models: Beam search builds translations left to right and retains the best n active hypotheses after each expansion.Complete hypotheses end with the end-of-sentence symbol, while partial hypotheses do not.
- 2 Exact Inference for Neural Models: Beam search is prone to search errors because its active-hypothesis set is limited by the beam size and does not compare partial hypotheses of different lengths.The beam-search model score is a lower bound on the global best model score.
- 2 Exact Inference for Neural Models: The pruning guarantee relies on vanilla NMT score monotonicity, where extending a hypothesis cannot increase its model score.The strict inequality follows because conditional probabilities are modeled with a softmax and cannot equal exactly 1.
- 2 Exact Inference for Neural Models: Exact decoding prunes any partial hypothesis whose score falls below the current complete-hypothesis score, then traverses the remaining space depth-first.The current lower bound is updated whenever depth-first search finds a better complete hypothesis.
- 2 Exact Inference for Neural Models: Length normalization and word rewards violate or alter this monotonicity, so the basic exact-search criterion does not directly apply to them.The paper extends exact search using length-dependent lower bounds for arbitrary length models.
3 Results without Length Constraints
Exact inference reveals that vanilla NMT frequently prefers empty translations, while larger beams reduce search errors only modestly and can worsen BLEU through shorter outputs.
- Larger beam sizes reduce search errors but lower BLEU because the resulting translations are too short.The BLEU decline is associated with a length ratio below 1.
- 51.8% of sentences receive the empty translation as the global best model score under exact inference.The empty translation is a single </s> token and causes a dramatic drop in length ratio and BLEU.
- Beam-10 reduces search errors from 73.58% to 57.68%, whereas Beam-100 still has 53.62% search errors despite being 10 times slower.Beam-10 yields a 15.9 percentage-point absolute reduction relative to greedy decoding, but Beam-100 improves search only slightly.
- Exact search produces an isolated peak near zero in the target/source length-ratio histogram from empty translations, unlike beam search’s roughly reference-like distribution.Beam search remains slightly too short, but it broadly follows the reference length-ratio distribution.
- The problems of search errors and empty translations also occur in other architectures, including a Transformer-Big system with 25.8% empty translations.The comparison includes recurrent LSTM, convolutional SliceNet, and Transformer-Big systems from a WMT’18 shared-task submission.
- Long source sentences are especially affected: the global best is empty for almost all sentences longer than 40 tokens, while substantial search errors remain otherwise.Figure 4 reports both Beam-10 search errors and empty global bests over source sentence length.
4 Results with Length Constraints
Length constraints show that empty translations reflect a broader bias toward short hypotheses, while length normalization corrects translation lengths without recovering Beam-10 BLEU.
- Length-constrained exact search: Constraining translations to exceed 0.25 times the source length excludes empty outputs but leaves a peak at length ratios of (0.3, 0.5].This suggests that empty translations arise from an inherent bias toward shorter hypotheses rather than from the empty output alone.
- Experimental scope: The constrained-search experiments were run on 48.3% of the test set, and decoding was stopped after one day for a single sentence on one CPU.Length constraints lower the pruning bounds and increase runtime.
- Length-constrained exact search: Exact search constrained to Beam-10 lengths does not improve over beam search, indicating that search errors at that fixed length have little BLEU impact.The experiment compares exact search with the best Beam-10 hypothesis length.
- Length-constrained exact search: An oracle exact search constrained to the reference length improves BLEU by 0.9 points.This result comes from the last row of Table 3 and uses the correct reference length.
- Length normalization: Length normalization generalizes exact inference by using length-dependent lower bounds to find best model scores for each translation length in a specified range.The generalized scheme can search lengths from zero to 1.2 times the source sentence length; its initial bounds use the Beam-10 hypothesis.
- Length normalization: Length normalization removes the length deficiency but prevents exact search from matching Beam-10's best BLEU score.The comparison was conducted on 48.3% of the test set.
5 Related Work
Prior work identified shorter translations and related modelling explanations, but this paper reports the first exact count of NMT search errors rather than relying on approximations.
- Related explanations: Prior studies linked large beam sizes with shorter translations and attributed the error to locally normalized maximum-likelihood training with regularization and finite data.Related work also discusses the difficulty of estimating the margin between correct and shorter translations.
- Novelty: This work reports the first exact number of search errors in NMT, whereas earlier studies often relied on n-best lists or constraints.The authors contrast exact counting with approximation-based analyses.
6 Conclusion
The paper uses exact inference to expose deficiencies in widely used NMT models, especially their preference for empty translations and the limits of simple length heuristics.
- Conclusion: Exact search reveals that reducing search errors can worsen BLEU because the model often prefers the empty translation, indicating a failure to model adequacy.The conclusion links deteriorating BLEU for large beams with fewer search errors.
- Conclusion: Length-constrained investigations suggest that simple heuristics such as length normalization are unlikely to remedy the modelling problem satisfactorily.The conclusion presents exact search as a diagnostic tool even though it may not be practical.