Year: 2018

Abstract:
Beam search is the most popular inference algorithm for decoding neural sequence models. Unlike greedy search, beam search allows for a non-greedy local decisions that can potentially lead to a sequence with a higher overall probability. However, previous work found that the performance of beam search tends to degrade with large beam widths. In this work, we perform an empirical study of the behavior of the beam search algorithm across three sequence synthesis tasks. We find that increasing the beam width leads to sequences that are disproportionately based on early and highly non-greedy decisions. These sequences typically include a very low probability token that is followed by a sequence of tokens with higher (conditional) probability leading to an overall higher probability sequence. However, as beam width increases, such sequences are more likely to have a lower evaluation score. Based on our empirical analysis we propose to constrain the beam search from taking highly non-greedy decisions early in the search. We evaluate two methods to constrain the search and show that constrained beam search effectively eliminates the problem of beam search degradation and in some cases even leads to higher evaluation scores. Our results generalize and improve upon previous observations on copies and training set predictions.

heading: 1 INTRODUCTION
text: Neural sequence models are among the most popular tools for modeling sequential data and have been applied to a range of applications including machine translation (Gehring et al., 2017), summarization (Chopra et al., 2016), image captioning (Vinyals et al., 2017), and conversation modeling (Vinyals & Le, 2015). The most commonly used inference algorithm for decoding neural sequence models is beam search, a search algorithm that generates the sequence tokens one-by-one while keeping a fixed number of active candidates (beams) at each step.
Recently, several works reported the problem of performance degradation in beam search. In machine translation, Koehn & Knowles (2017) found that beam search “only improves translation for narrow beams and deteriorates when exposed to a larger search space”. They chose this problem as one of six central challenges in machine translation. Ott et al. (2018) proposed the existence of training pairs in which the target is a copy of the source as an explanation for the performance degradation. For larger beams, more predictions can be classified as “copies”1 and filtering these copies reduces the performance degradation.
In image captioning, Vinyals et al. (2017) observed performance degradation for wider beams and highlighted the use of a narrower beam search as one of the most significant improvements in their model. They hypothesized that the performance degradation is either due to overfitting or that the objective function used in training (likelihood) is not aligned with human judgement. Their analysis found that wider beams exhibited more predictions that repeat training captions and fewer novel ones. They claim that this observation supports the hypothesis that the model is overfitted and therefore see the use of smaller beam width as “another way to regularize”.
In this work, we analyze the performance of beam search across multiple tasks including machine translation, abstractive summarization, and image captioning. We present an explanatory model that
1“Copies” are predictions that share at least 50% of their unigrams with their source (Ott et al., 2018).
is based on the concept of search discrepancies (deviations from greedy choices) and perform an empirical study of the distribution of such discrepancies. We make the following contributions:
1. We show that increasing the beam width leads to solutions with more and larger early discrepancies. These sequences often have lower evaluation score, leading to the observed performance degradation. As we increase the beam width, the difference between discrepancies that are associated with improved vs. degraded solutions grows substantially.
2. We show that our explanatory model generalizes the previously observed copies and predictions that repeat training set targets and accounts for more of the degraded predictions.
3. Exploiting the above insights, we propose a fix that is based on constraining the discrepancies considered by the beam search. An empirical analysis shows it successfully eliminates the performance degradation.

heading: 2 PRELIMINARIES

heading: 2.1 NEURAL SEQUENCE MODELS
text: Given a model parameterized by θ and an input x, the problem of sequence generation consists of finding a sequence ŷ such that ŷ = argmaxy∈Y Pθ(y | x), where Y is the set of all sequences. y is a sequence of tokens y = {y0, ...yT−1} from vocabulary V , where T is the length of the sequence y. The expression Pθ(y | x) can then be factored as Pθ(y | x) = ∏T−1 t=0 Pθ(yt | x; {y0, ..., yt−1}),
or for convenience using log-probability as ∑T−1 t=0 logPθ(yt | x; {y0, ..., yt−1}).
It is common to model logPθ(yt | x; {y0, ..., yt−1}) using a Recurrent Neural Network (RNN), where the sequence {y0, ..., yt−1} conditioned on is expressed by a fixed length hidden state ht. This hidden state is updated using a non-linear function f : ht+1 = f(ht, yt).
Exhaustive search to find the globally optimal sequence is not tractable. A greedy algorithm that selects the best candidate at each time step yt = argmaxy∈V logPθ(y | x; {y0, ..., yt−1}) makes a sequence of locally optimal decisions, but can lead to a globally sub-optimal sequence. Beam search, in contrast, extends the B most probable partial solutions at each step, where B is called beam width. Following Vijayakumar et al. (2018), we denote the set of B solutions held by the beam search at step t − 1 as Y[t−1]={y1,[t−1], ..., yB,[t−1]}. At each step, beam search selects the top scoring B candidates from the set of all possible one token extensions of its beams Yt={y[t] | y[t−1] ∈ Y[t−1] ∧ yt ∈ V}. Formally, the beam search candidates are updated as follows:
Y[t] = argmax y[1,t],...,y[B,t]∈Yt ∑ b∈[1..B] logPθ(yb,t | x)
s.t. yi 6= yj ∀i 6= j; i, j ∈ [1..B] (1)

heading: 2.2 SEARCH DISCREPANCIES IN NEURAL SEQUENCE GENERATION
text: In combinatorial search, a search discrepancy is a decision made by the search algorithm that is not the most highly rated one according to the heuristic (Harvey & Ginsberg, 1995). In the context of search for neural sequence generation, we define a search discrepancy as extending a partial sequence with a token that is not the most probable one (i.e., different than the greedy algorithm). More formally, a sequence y is considered to have a search discrepancy at time step t if
logPθ(yt | x; {y0, ..., yt−1}) < max y∈V logPθ(y | x; {y0, ..., yt−1}). (2)
We denote the ratio between the most probable token and the chosen token as discrepancy gap. We measure the gap based on the difference in log-probability, i.e., the discrepancy gap at step t is
max y∈V
log Pθ(y | x; {y0, ..., yt−1})− log Pθ(yt | x; {y0, ..., yt−1}). (3)

heading: 3 EXPERIMENTAL SETUP
text: We perform an extensive empirical evaluation over multiple tasks, models, datasets, toolkits, and evaluation metrics. Following is a description of the experimental setup for each task.
Machine Translation. We use the convolutional model by Gehring et al. (2017) implemented in the fairseq-py toolkit. We present results for two models, trained on WMT’14 En-Fr and En-De datasets and evaluated on newstest2014 En-Fr and En-De, respectively.
Summarization. We use the abstractive summarization model by Chopra et al. (2016) implemented in OpenNMT toolkit (Klein et al., 2017). The model is trained and evaluated using Rush et al.’s (2015) test split of the Gigaword corpus (Graff et al., 2003).
Image Captioning. We use the model by Vinyals et al. (2017), trained on the MSCOCO dataset (Lin et al., 2014). The test set includes 5000 images based on Karpathy & Fei-Fei’s (2015) splits.
In machine translation and summarization, we apply length normalization on the hypotheses loglikelihood, as it was shown to reduce the performance degradation by not prioritizing short sentences (Koehn & Knowles, 2017; Gehring et al., 2017). For image captioning, consistent with previous works, we do not use length normalization (we also found it reduces the overall performance).

heading: 3.1 EVALUATION METRICS
text: While beam search finds the (approximately) most probable sequence, the quality of a sequence is evaluated based on human references using a task-specific evaluation metric. For machine translation and image captioning we use BLEU-n (Papineni et al., 2002), a geometric average of precision over 1- to n-grams multiplied by a brevity penalty for short sentences. As in recent literature, we present results for BLEU-4. Corpus-level BLEU is reported without smoothing, while for sentencelevel BLEU we use smoothed n-gram counts for n > 1 (Lin & Och, 2004). For image captioning, we also evaluated the performance using CIDEr (Vedantam et al., 2015) and SPICE (Anderson et al., 2016b) and report these metrics in Appendix E.
For summarization, we use ROUGE (Lin, 2004), the n-gram recall between candidate summary and a reference. We report the F-score of ROUGE-1, however similar trends were observed for the F-score of ROUGE-L (for longest common subsequence).

heading: 4 EMPIRICAL ANALYSIS OF SEARCH DISCREPANCIES IN BEAM SEARCH
text: In this section we present an empirical analysis of the search discrepancies. We analyze and compare the most likely hypotheses found by a beam search for the following beam widths: {1, 3, 5, 25, 100, 250}. Due to space, we present detailed results for one of the tasks and summarize the results for the others. The results for all tasks and metrics can be found in Appendix A.

heading: 4.1 BASELINE RESULTS
text: Table 1 presents the performance of beam search with different beam widths, based on the chosen evaluation metrics. The performance degradation for larger beam widths appears for all tested tasks based on their task-specific evaluation metric. These results are consistent with the existing reports of such performance degradation (Koehn & Knowles, 2017; Ott et al., 2018; Vinyals et al., 2017).

heading: 4.2 THE DISTRIBUTION OF SEARCH DISCREPANCIES
text: In this section, we analyze the distribution and size of search discrepancies vs. their position (index) in sequence. Figure 1 shows the number of discrepancies per position for the most likely hypotheses generated by a beam search on the WMT’14 En-De test set for different beam widths (all graphs
are based on the same number of solutions, however the total number of discrepancies in the generated solutions is not necessarily the same for different beam widths). In general, the majority of discrepancies happen in early positions. More interestingly, for larger beams, the number of early discrepancies grows significantly while the number of later discrepancies stays approximately the same. Larger beams seem to allow the search to find solutions with higher overall probability by exploring less probable early tokens, however they do not seem to lead to more probable sequences that share a prefix with solutions found for a smaller beam width. Similar results for the other tasks are reported in Appendix A. For image captioning (MSCOCO), we find the majority of early search discrepancies appear on the second token due to the first token being “a” with high probability in almost all sentences (in greedy search, for example, 99% of the generated captions start with “a”).
Next, we analyze the discrepancy gap vs. sequence position. Figure 2 presents the mean gap per position for WMT’14 En-De for different beam widths. Again, we can see that the changes are mainly in the early positions: as we increase the beam width, the search tends to find solutions with larger early discrepancy gap, i.e., the early tokens are relatively less likely. The discrepancy gap of the other tokens remains similar. Similar results for the other tasks are reported in Appendix A.
The increase in count and size of early discrepancies for larger beams means that the search manages to find solutions with higher overall probability when starting from a large discrepancy. However, these solution are not necessarily better according to the evaluation metric. The observed performance degradation suggests that the more probable solutions found by larger beams are, in fact, worse. Identifying discrepancies that are likely to lead to a worse solution is therefore a key task in addressing the performance degradation. In the next section, we analyze the differences between discrepancies in solutions with higher evaluation vs. solutions with lower evaluation.

heading: 4.3 IMPROVED VS. DEGRADED SOLUTIONS
text: We now compare the solutions generated by a greedy search with the solutions generated by beam search with different widths. We then analyze the discrepancies in solutions that were improved by increasing the beam width (with respect to the evaluation metric) vs. solutions that were degraded.
Figure 3 shows the number of discrepancies per position for WMT’14 En-De, comparing solutions that were improved vs. solutions that were degraded. For B=5 there are 386 solutions in which the first token is not based on a greedy decision. Of those, 200 have a better evaluation than the greedy solution and 169 have a worse evaluation. However, as we increase the beam width, we see that the increase in early discrepancies observed in Figure 1 is associated almost entirely with degraded
solutions. This result explains the observed performance degradation for larger beam widths. Similar results for the other tasks are reported in Appendix A.
Next, we compare the discrepancy gaps in degraded vs. improved solutions. Figure 4 presents the mean discrepancy gap per position for the WMT’14 En-De dataset, for both the improved and the degraded solutions. Interestingly, we find that the additional early discrepancies that are associated with degraded solutions tend to have a much higher discrepancy gap compared to the ones associated with improved solutions. Similar results for the other tasks are reported in Appendix A.

heading: 4.4 SEARCH DISCREPANCIES AND THE MOST LIKELY HYPOTHESIS
text: In order for a sequence with early large discrepancy to be selected by a beam search as (approximately) the most likely hypothesis, it has to be followed by tokens with higher (conditional) probability. Figure 5 shows the average (conditional) token probability for WMT’14 En-De (we use log-scale on the x axis to highlight the early positions). For larger beam widths, the average probability of early tokens decreases (due to larger discrepancy gaps) while the average probability of later tokens increases explaining the overall higher probability.2 Figure 5 also shows the same graph for the improved vs. degraded solutions (compared to greedy search). For improved solutions, we do not see significant change as we increase the beam width. For degraded solutions, however, as we increase the beam width we find more and more early discrepancies that lead to an overall higher probability but a worse evaluation metric value. For all tasks, we found the differences for the degraded solutions to be larger than the improved solutions (see Appendix A).
Ott et al. (2018) observed the same pattern for copies, i.e., they have low first token probability and higher probabilities for subsequent tokens. Our analysis accounts for this behavior and suggests that copies are one instance of a more general pattern that leads to degraded sequences. In the next section, we show that our analysis generalizes copies, as well as training set predictions, and even accounts for additional degraded sequences.

heading: 4.5 GENERALIZING COPIES AND TRAINING SET PREDICTIONS
text: Table 2 shows the number of copies in machine translation and training set predictions in summarization and image captioning. For larger beams, the number of copies and training set predictions grows. Table 2 also reports the mean discrepancy gap of the first token (second token for MSCOCO, see Section 4.2). As our analysis predicts, the early gap of these predictions also grows significantly.
2When length normalization is not used, we should compare the product of token probabilities rather than the average token probabilities. See Appendix A.3 for results on the unnormalized image captioning task.
Note that copies and training set predictions only partially account for the beam performance degradation. In WMT’14 En-De machine translation withB = 25, we find that copies account for≈ 40% of degraded solutions with first token gap. In Gigaword summarization with similar beam width, we find that training set examples account for ≈ 68% of degraded solutions with first token gap. Furthermore, in MSCOCO, since many of the solutions in the greedy search, as well as many of the improved sequences, are training set captions, eliminating them all together is not desired. Instead, we are interested in avoiding the training set captions in the larger beam widths that led to the performance degradation. These, as Table 2 shows, have larger difference in the discrepancy gap.

heading: 4.6 AN ILLUSTRATIVE EXAMPLE
text: Consider the following example of training set predictions in Gigaword summarization. As we increase the beam width, we find more predictions with the structure: “〈weekday〉’s sports scoreboard” (Table 3).3 As expected, these predictions have a large early discrepancy, followed by highly (conditionally) probable tokens. For B = 100, the average first token discrepancy gap for these summaries is ≈ 3.63 compared to ≈ 0.39 in the full test set. As none of the test references includes “sports scoreboard”, these summaries have low evaluation score.
As a potential explanation for this phenomenon, we find that all texts that were summarized as “〈weekday〉’s sports scoreboard” included the corresponding weekday. In the training set, we found
3Without length normalization, the numbers are higher as this sequence is shorter than most summaries.
that in 2962 of the 2971 texts that were summarized to “〈weekday〉’s sports scoreboard” included the corresponding weekday. This can lead to the weekday’s token suggested as a first token with a low, but sufficiently high, probability to get into the top B tokens. Followed by high probability tokens, it can, in some cases, have an overall probability that is higher than the alternatives.

heading: 5 DISCREPANCY-CONSTRAINED BEAM SEARCH
text: Building on our empirical analysis, we propose to constrain the beam search to avoid considering highly unlikely discrepancies. To do so, we evaluate two methods of constraining the beam search:
1. Discrepancy gap: Given a thresholdM, we modify beam search to only consider candidates with a discrepancy gap smaller or equal toM. Formally, we modify Eq. 1 to include the constraint maxy∈V log Pθ(y | x; {y0, ..., yt−1})−log Pθ(yt | x; {y0, ..., yt−1}) ≤M.
2. Beam candidate rank: Given a thresholdN , we modify Yt to only include the topN one token extensions in each beam. Note that the beam search still retains the topB candidates, however it will not consider more than N candidates from the same beam.
Using the setup in Section 4.1, we compare these methods to the baseline. Although the analysis in Section 4 was done on the test set (to account for the performance degradation that was previously observed on the test set),M and N are tuned on a held-out validation set and no information from the test set was used to tune our methods.
As shown in Table 4, both methods significantly reduce, and in some cases completely eliminate, the performance degradation. In translation and summarization, we improve performance compared to baseline with the best test beam width. In general, the gap constraint seems to be perform better (most notably, for MSCOCO). The gap constraint allows for a finer-grained control over the accepted discrepancies, however the rank constraint is simpler and easier to tune.
We also compared the number of copies and training set predictions in the baseline vs. the two discrepancy-constrained variants of beam search. We find that the constrained methods reduce the growth in the number of copies and training set predictions that happen as we increase the beam width. The detailed comparison can be found in Appendix B.
Finally, we repeated our analysis above and find that both constrained beam search variations substantially reduce the discrepancy phenomena observed in Section 4. Complete results and graphs for both constrained methods on WMT’14 En-De are in Appendix C (other tasks exhibited similar results).

heading: 6 DISCUSSION
text: Our results show that larger beam width leads to increasingly large early discrepancies. These very unlikely early tokens are later compensated by subsequent tokens with a much higher (conditional) probability compared to the subsequent tokens of the more probable early tokens. The large difference in the conditional probability of the subsequent tokens is at the heart of the observed performance degradation. Previous work has highlighted two potential biases that can account for this difference. Exposure bias (Ranzato et al., 2015) occurs since the model is only exposed to the training data and can be biased towards the training set distribution (our illustrative example demonstrates such bias due to a repetitive pattern in the training data). Label bias (Wiseman & Rush, 2016) occurs since token probabilities at each time step are locally normalized and therefore the successors of incorrect histories receive the same probability mass as the successors of a correct history.
These above biases help explain the observed behavior with large beam width: a biased (conditional) probability that concentrates high probability mass on one token and is locally normalized to sum to one compensates for earlier low probability tokens. The negative effects of these biases have been discussed before, however the described connection to the performance degradation in beam search and the explanatory framework to allow such analysis is, to our best knowledge, novel.
The use of the search discrepancy concept from heuristic and combinatorial search views the probabilities predicted by the neural network as a heuristic to guide the search. Early mistakes in such search have been shown to have a large negative effect on performance (Gent & Walsh, 1994). Substantial work has analyzed and proposed techniques to mitigate the phenomenon (Gomes et al., 2005; Cohen & Beck, 2018), including limited discrepancy search (Harvey & Ginsberg, 1995). Further investigation of the connection between such work and neural decoding may lead to further insight.

heading: 7 RELATED WORK
text: Search discrepancies have been the base of many search techniques in combinatorial search and optimization (e.g., Harvey & Ginsberg, 1995; Walsh, 1997; Beck & Perron, 2000). Furcy & Koenig (2005) proposed BULB, a complete variant of beam search that backtracks based on search discrepancies, as a memory-efficient alternative to best-first heuristic search for path-finding problems.
Several works have modified or constrained beam search for different purposes. Vijayakumar et al. (2018) changed the objective to allow diverse decoding. Hokamp & Liu (2017) proposed grid beam search to support lexical constraints. Anderson et al. (2016a) proposed a constrained beam search that forces inclusion of selected tokens in the output. Freitag & Al-Onaizan (2017) analyzed pruning techniques for beam search in machine translation. Their strategy of limiting “maximum candidates per node” is similar to the rank constraint in our work, however their analysis is focused on speeding up beam search rather than addressing the phenomenon of performance degradation.
A recent line of work in machine translation suggested the performance degradation is due to length bias (Yang et al., 2018; Murray & Chiang, 2018). For larger beams, an end-of-sentence token with a lower probability that leads to an overall more probable hypothesis is more likely to be considered by the beam search. However, we showed peformance degradation above even when using length normalization and in tasks where length bias does not appear (see Appendix D for more details).

heading: 8 CONCLUSION
text: In this work, we perform an empirical analysis of the performance degradation in beam search across three neural sequence decoding tasks. We find that the performance degradation for large beam widths is due to the increasing number of early and large search discrepancies. Our analysis generalizes previous results including the existence of copy predictions in machine translation and the training set predictions in image captioning, and accounts for additional degraded sequences. Based on our analysis, we propose two constrained variants of beam search that avoid large discrepancy gaps and successfully eliminate the performance degradation in beam search.
This work provides a deeper understanding of beam search behavior and an analytical framework to study search discrepancies. We believe the analysis, the framework, and the proposed solutions can support the development of better training methods and decoding algorithms.

heading: A FULL EMPIRICAL ANALYSIS
text: A.1 MACHINE TRANSLATION ON WMT’14 EN-FR
A.2 SUMMARIZATION ON GIGAWORD
A.3 IMAGE CAPTIONING ON MSCOCO

heading: B COPIES AND TRAINING SET PREDICTIONS IN DISCREPANCY-CONSTRAINED BEAM SEARCH
text: Table 6 compares the number of copies in the baseline vs. the discrepancy-constrained methods for the machine translation tasks for each beam width. For the baseline, we can see that as we increase the beam width, the number of copies grows significantly. However, both discrepancy-constrained methods significantly reduce this growth.
Table 7 compares the number of training set predictions in the baseline vs. the discrepancyconstrained methods for the summarization and image captioning tasks for each beam width. For
the baseline, we can see that as we increase the beam width, the number of training set predictions grows significantly. However, as with copies, both discrepancy-constrained methods significantly reduce the growth in training set predictions.

heading: C RESULTS FOR CONSTRAINED BEAM SEARCH ON WMT’14 EN-DE
text: C.1 RESULTS FOR DISCREPANCY GAP CONSTRAINED BEAM SEARCH (M = 1.5)
C.2 RESULTS FOR RANK CONSTRAINED BEAM SEARCH (N = 2)

heading: D ANALYSIS OF LENGTH BIAS
text: Table 8 shows the mean length of generated sentences for different beam widths for the baseline, normalized to the best tested beam width. All values are very close 1.0, which suggest that the observed performance degradation is not due to length bias. We note that for machine translation and summarization this is due to the use of length normalization on the hypotheses log-likelihood, as suggested by Koehn & Knowles (2017) (without normalization, the performance degradation would have been worse).4 In image captioning, however, there is no observed length bias even when length normalization is not used.5
In Section 4.1, we showed substantial performance degradation as we increase the beam width. As the results in Table 8 demonstrate that there is no significant change in the length of generated sequences, the observed performance degradation cannot be attributed to length bias.
E IMAGE CAPTIONING: CIDER AND SPICE
Table 9 compares the baseline vs. the constrained beam search methods on the MSCOCO image caption task using the metrics CIDEr and SPICE. The results show similar trends to those observed for BLEU in Section 5. In particular, we see that the performance degradation for larger beams also occurs for CIDEr and SPICE in the baseline, and that our gap constraint method eliminates this degradation. Similar to our results for BLEU, we note that our rank constraint is not as effective as our gap constraint for the image captioning task.

Review summaries:
This paper addresses issues with the beam search decoding algorithm that is commonly applied to recurrent models during inference. In particular, the paper investigates why using larger beam widths, resulting in output sequences with higher log-probabilities, often leads to worse performance on evaluation metrics of interest such as BLEU. The paper argues that this effect is related to ‘search discrepancies’ (deviations from greedy choices early in decoding), and proposes a constrained decoding mechanism as a heuristic fix. 

- The paper generalizes upon past observations by Ott et al. that NMT models might decode "copies" (of the source sentence) when using large beam widths, which results in degraded results. In particular, the present paper observes similar shortcomings in two additional tasks (summarization and captioning), where decoding with large beam widths results in "training set predictions." It's unclear if this observation is novel, but in any case the connection between these observations across NMT and summarization/captioning tasks is novel.