Title: (UNCONSTRAINED) BEAM SEARCH IS SENSITIVE TO LARGE SEARCH DISCREPANCIES

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.

1. INTRODUCTION:

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 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.

2. PRELIMINARIES:

2.1 NEURAL SEQUENCE MODELS Given a model parameterized by θ and an input x, the problem of sequence generation consists of finding a sequence ŷ such that ŷ = arg max y∈Y P θ (y | x), where Y is the set of all sequences. y is a sequence of tokens y = {y 0 , ...y T -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 θ (y t | x; {y 0 , ..., y t-1 }), or for convenience using log-probability as

T -1 t=0 logP θ (y t | x; {y 0 , ..., y t-1 }).

It is common to model logP θ (y t | x; {y 0 , ..., y t-1 }) using a Recurrent Neural Network (RNN), where the sequence {y 0 , ..., y t-1 } conditioned on is expressed by a fixed length hidden state h t . This hidden state is updated using a non-linear function f :

h t+1 = f (h t , y t ).

Exhaustive search to find the globally optimal sequence is not tractable. A greedy algorithm that selects the best candidate at each time step y t = arg max y∈V logP θ (y | x; {y 0 , ..., y t-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] ={y 1,[t-1] , ..., y B,[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

Y t ={y [t] | y [t-1] ∈ Y [t-1] ∧ y t ∈ V}.

Formally, the beam search candidates are updated as follows:

EQUATION

2.2. SEARCH DISCREPANCIES IN NEURAL SEQUENCE GENERATION:

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 θ (y t | x; {y 0 , ..., y t-1 }) < max y∈V logP θ (y | x; {y 0 , ..., y t-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; {y 0 , ..., y t-1 })log P θ (y t | x; {y 0 , ..., y t-1 }).

(3)

3. EXPERIMENTAL SETUP:

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).

3.1. EVALUATION METRICS:

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).

4. EMPIRICAL ANALYSIS OF SEARCH DISCREPANCIES IN BEAM SEARCH:

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.

4.1. BASELINE RESULTS:

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) . 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.

4.3. IMPROVED VS. DEGRADED SOLUTIONS:

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. 

4.4. SEARCH DISCREPANCIES AND THE MOST LIKELY HYPOTHESIS:

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.

4.5. GENERALIZING COPIES AND TRAINING SET PREDICTIONS:

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. Note that copies and training set predictions only partially account for the beam performance degradation. In WMT'14 En-De machine translation with B = 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.

4.6. AN ILLUSTRATIVE EXAMPLE:

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.

Table 3 : Frequency of predicted summary for different beam widths. 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 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.

5. DISCREPANCY-CONSTRAINED BEAM SEARCH:

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 threshold M, we modify beam search to only consider candidates with a discrepancy gap smaller or equal to M. Formally, we modify Eq. 1 to include the constraint max y∈V log P θ (y | x; {y 0 , ..., y t-1 })-log P θ (y t | x; {y 0 , ..., y t-1 }) ≤ M.

2. Beam candidate rank: Given a threshold N , we modify Y t to only include the top N one token extensions in each beam. Note that the beam search still retains the top B 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).

6. DISCUSSION:

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.

7. RELATED WORK:

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).

8. CONCLUSION:

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.

A FULL EMPIRICAL ANALYSIS:

A.1 MACHINE TRANSLATION ON WMT'14 EN-FR 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. 

:

"Copies" are predictions that share at least 50% of their unigrams with their source(Ott et al.,

2018).

When 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.

Without length normalization, the numbers are higher as this sequence is shorter than most summaries.

This is consistent withOtt et al.'s (2018) results on performance degradation even when using length normalization.

In fact, as we stated earlier, we found that length normalization reduces the overall performance.

Figures and Tables:

Figure 1: WMT'14 En-De: Distribution of discrepancy positions for different beam widths.

Figure 2: WMT'14 En-De: Mean discrepancy gap per position for different beam widths.

Figure 3: WMT'14 En-De: Distribution of discrepancy positions for different beam widths.

Figure 4: WMT'14 En-De: Mean discrepancy gap per position for different beam widths.

Figure 5: Average token probability per position for different beam widths.

B = 3 B = 5 B = 25 B = 100 B = 250 " weekday 's sports scoreboard"

Figure 6: WMT'14 En-Fr: Distribution of discrepancy positions for different beam widths.

Figure 7: WMT'14 En-Fr: Mean discrepancy gap per position for different beam widths.

Figure 8: WMT'14 En-Fr: Distribution of discrepancy positions for different beam widths.

Figure 9: WMT'14 En-Fr: Mean discrepancy gap per position for different beam widths.

Figure 10: WMT'14 En-Fr: Average token probability per position for different beam widths.

Figure 12: Gigaword: Mean discrepancy gap per position for different beam widths.

Figure 13: Gigaword: Distribution of discrepancy positions for different beam widths.

Figure 14: Gigaword: Mean discrepancy gap per position for different beam widths.

Figure 15: Gigaword: Average token probability per position for different beam widths.

Figure 16: MSCOCO: Distribution of discrepancy positions for different beam widths.

Figure 17: MSCOCO: Mean discrepancy gap per position for different beam widths.

Figure 20: WMT'14 En-De: Distribution of discrepancy positions (M = 1.5).

Figure 21: WMT'14 En-De: Mean discrepancy gap per position (M = 1.5).

Figure 22: WMT'14 En-De: Distribution of discrepancy positions (M = 1.5).

Figure 23: WMT'14 En-De: Mean discrepancy gap per position (M = 1.5).

Figure 24: WMT'14 En-De: Average token probability per position (M = 1.5).

Figure 25: WMT'14 En-De: Distribution of discrepancy positions (N = 2).

Figure 26: WMT'14 En-De: Mean discrepancy gap per position (N = 2).

Figure 27: WMT'14 En-De: Distribution of discrepancy positions (N = 2).

Figure 28: WMT'14 En-De: Mean discrepancy gap per position (N = 2).

Figure 29: WMT'14 En-De: Average token probability per position (N = 2).

Baseline results for different beam widths (higher values are better, best results in bold).

Table content: <table><tr><td>Task</td><td>Dataset</td><td>Metric</td><td colspan="4">B=1 B=3 B=5 B=25 B=100 B=250</td></tr><tr><td>Translation</td><td>En-De</td><td colspan="2">BLEU4 25.27 26.00 26.11</td><td>25.11</td><td>23.09</td><td>21.38</td></tr><tr><td/><td>En-Fr</td><td colspan="2">BLEU4 40.15 40.77 40.83</td><td>40.52</td><td>38.64</td><td>35.03</td></tr><tr><td colspan="3">Summarization Gigaword R-1 F</td><td>33.56 34.22 34.16</td><td>34.01</td><td>33.67</td><td>33.23</td></tr><tr><td>Captioning</td><td colspan="3">MSCOCO BLEU4 29.66 32.36 31.96</td><td>30.04</td><td>29.87</td><td>29.79</td></tr><tr><td colspan="4">4.2 THE DISTRIBUTION OF SEARCH DISCREPANCIES</td><td/><td/></tr></table>

Number of copies and training set examples and the average first token discrepancy gap.

Table content: <table><tr><td>B=1 B=3 B=5 B=25 B=100 B=250</td></tr></table>

A comparison of the baseline results vs. the constrained beam search methods (higher values are better, best baseline results in bold).

Table content: <table><tr><td>Dataset</td><td>Method</td><td>Threshold</td><td colspan="4">B=1 B=3 B=5 B=25 B=100 B=250</td></tr><tr><td>En-De (BLEU-4)</td><td colspan="2">Baseline Constr. Gap Constr. Rank N = 2 M = 1.5</td><td>25.27 26.00 26.11 25.27 26.00 26.18 25.27 26.07 26.01</td><td>25.11 26.18 26.08</td><td>23.09 26.22 26.10</td><td>21.38 26.29 26.10</td></tr><tr><td>En-Fr (BLEU-4)</td><td colspan="2">Baseline Constr. Gap Constr. Rank N = 3 M = 2.0</td><td>40.15 40.77 40.83 40.15 40.78 40.86 40.15 40.77 40.81</td><td>40.52 40.98 40.99</td><td>38.64 41.05 41.05</td><td>35.03 41.06 41.02</td></tr><tr><td>Gigaword (R-1 F)</td><td colspan="3">Baseline Constr. Gap Constr. Rank N = 2 M = 0.85 33.56 34.27 34.29 33.56 34.22 34.16 33.56 34.48 34.45</td><td>34.01 34.43 34.25</td><td>33.67 34.33 34.23</td><td>33.23 34.32 34.32</td></tr><tr><td>MSCOCO (BLEU-4)</td><td colspan="3">Baseline Constr. Gap Constr. Rank N = 2 M = 0.45 29.66 32.24 32.33 29.66 32.36 31.96 29.66 32.52 31.97</td><td>30.04 32.36 30.88</td><td>29.87 32.35 30.87</td><td>29.79 32.35 30.87</td></tr></table>

Number of predictions that are in the training set for the baseline and the two types of discrepancy-constrained beam search for different beam widths.

Table content: <table><tr><td colspan="3">Dataset</td><td/><td>Method</td><td/><td colspan="11">Parameter B=1 B=3 B=5 B=25 B=100 B=250</td></tr><tr><td colspan="5">Gigaword Baseline</td><td/><td/><td/><td/><td>81</td><td>86</td><td/><td>86</td><td/><td colspan="2">115</td><td>163</td><td>224</td></tr><tr><td colspan="5">Gigaword Constr. Gap</td><td/><td colspan="3">M = 0.85</td><td>81</td><td>81</td><td/><td>77</td><td/><td colspan="2">79</td><td>78</td><td>78</td></tr><tr><td colspan="7">Gigaword Constr. Rank N = 2</td><td/><td/><td>81</td><td>81</td><td/><td>79</td><td/><td colspan="2">79</td><td>79</td><td>79</td></tr><tr><td colspan="5">MSCOCO Baseline</td><td/><td/><td/><td/><td>163</td><td>260</td><td/><td>371</td><td/><td colspan="2">588</td><td>582</td><td>576</td></tr><tr><td colspan="5">MSCOCO Constr. Gap</td><td/><td colspan="3">M = 0.45</td><td>163</td><td>265</td><td/><td>271</td><td/><td colspan="2">271</td><td>271</td><td>271</td></tr><tr><td colspan="7">MSCOCO Constr. Rank N = 2</td><td/><td/><td>163</td><td>242</td><td/><td>262</td><td/><td colspan="2">231</td><td>231</td><td>231</td></tr><tr><td colspan="17">C RESULTS FOR CONSTRAINED BEAM SEARCH ON WMT'14 EN-DE</td></tr><tr><td colspan="17">C.1 RESULTS FOR DISCREPANCY GAP CONSTRAINED BEAM SEARCH (M = 1.5)</td></tr><tr><td/><td>400</td><td/><td/><td>beamWidth = 5</td><td/><td/><td/><td/><td colspan="2">beamWidth = 100</td><td/><td/><td/><td/><td/><td>beamWidth = 250</td></tr><tr><td/><td>300</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>Count</td><td>200</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>100</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>0</td><td>1</td><td>2</td><td>3 Discrepancy Position 4 5 6 7 8</td><td>9</td><td>10</td><td>1</td><td>2</td><td colspan="2">3 Discrepancy Position 4 5 6 7 8</td><td>9</td><td>10</td><td>1</td><td>2</td><td colspan="2">3 Discrepancy Position 4 5 6 7 8</td><td>9</td><td>10</td></tr></table>

Peer review (iclr2019):
 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. Strengths: - The reduction in performance from using larger beam widths has been often reported and needs more investigation. - The paper views beam search decoding through the lens of heuristic and combinatorial search, and suggests an interesting connection with methods such as limited discrepancy search (Harvey and Ginsberg 1995) that seek to eliminate early ‘wrong turns’. - In most areas the paper is clear and well-written, although it may help to be more careful about explaining and / or defining terms such as ‘highly non-greedy’, ‘search discrepancies’ in the introduction. Weaknesses and suggestions for improvement: - Understanding: The paper does not offer much in the way of a deeper understanding of search discrepancies. For example, are search discrepancies caused by exposure bias or label bias, i.e. an artifact of local normalization at each time step during training, as suggested in the conclusion? Or are they actually a linguistic phenomenon (noting that English, French and German have common roots)? As there are neural network methods that attempt to do approximate global normalization (e.g. https://www.aclweb.org/anthology/P16-1231), there may be ways to investigate this question by looking at whether search discrepancies are reduced in these models (although I haven’t looked deeply into this). - Evaluation: In the empirical evaluation, the results seem quite marginal. Taking the best performing beam size for the proposed method, and comparing the score to the best performing beam size for the baseline, the scores appear to be within around 1% for each task. Although the proposed method allows larger beam widths to be used without degradation during decoding, of course this is not actually beneficial unless the larger beam can improve the score. In the end, the evidence that search discrepancies are the cause of the problems with large beam widths, and therefore the best way to mitigate these problems, is not that strong. - Evaluation metrics and need for human evals: The limitations of automatic linguistic evaluations such as BLEU are well known. For image captioning, the SPICE (ECCV 2016 https://arxiv.org/abs/1607.08822) and CIDEr (CVPR 2015 https://arxiv.org/abs/1411.5726) metrics show much greater correlation with human judgements of caption quality, and should be reported in preference (or in addition) to BLEU. More generally, it is quite possible that the proposed fix based on constraining discrepancies could improve the generated output in the eyes of humans, even if this is not strongly reflected in automatic evaluation metrics. Therefore, it would be interesting to see human evaluations for the generated outputs in each task. - Rare words: The authors reference Koehn and Knowles’ (2017) six challenges for NMT, which includes beam search decoding. One of the other six challenges is low-frequency words. However, the impact of the proposed constrained decoding approach on the generation of rare words is not explored. It seems reasonable that limiting search discrepancies might also further limit the generation of rare words. Therefore, I would like to suggest that an analysis of the diversity of the generated outputs for each approach be included in the evaluation. - Constrained beam search: There is a bunch of prior work on constrained beam search. For example, an algorithm called constrained beam search was introduced at EMNLP 2017 (http://aclweb.org/anthology/D17-1098). This is a general algorithm for decoding RNNs with constraints defined by a finite state acceptor. Other works have also been proposed that are variations on this idea, e.g. http://aclweb.org/anthology/P17-1141, http://aclweb.org/anthology/N18-1119). It might be helpful to identify these in the related work section to help limit confusion when talking about this ‘constrained beam search’ algorithm. Minor issues: - Section 3. The image captioning splits used by Xu et al. 2015 were actually first proposed by Karpathy & Li, ‘Deep visual-semantic alignments for generating image descriptions’, CVPR 2015, and should be cited as such. (Some papers actually refer to them as the ‘Karpathy splits’.) - In Table 4 it is somewhat difficult to interpret the comparison between the baseline results and the constrained beam search methods, because the best results appear in different columns. Bolding the highest score in every row would be helpful. Summary: In summary, improving beam search is an important direction, and to the best of my knowledge the idea of looking at beam search through the lens of search discrepancies is novel. Having said, I don*t feel that this paper in it*s current form contributes very much to our understanding of RNN decoding, since it is not clear if search discrepancies are actually a problem. Limiting search discrepancies during decoding has minimal impact on BLEU scores, and it seems possible that search discrepancies could just be an aspect of linguistic structure. I rate this paper marginally below acceptance, although I would encourage the authors to keep working in this direction and have tried to provide some suggestions for improvement.