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