If beam search is the answer, what was the question? (2020)

Abstract: Quite surprisingly, exact maximum a posteriori (MAP) decoding of neural language generators frequently leads to low-quality results. Rather, most state-of-the-art results on language generation tasks are attained using beam search despite its overwhelmingly high search error rate. This implies that the MAP objective alone does not express the properties we desire in text, which merits the question: if beam search is the answer, what was the question? We frame beam search as the exact solution to a different decoding objective in order to gain insights into why high probability under a model alone may not indicate adequacy. We find that beam search enforces uniform information density in text, a property motivated by cognitive science. We suggest a set of decoding objectives that explicitly enforce this property and find that exact decoding with these objectives alleviates the problems encountered when decoding poorly calibrated language generation models. Additionally, we analyze the text produced using various decoding strategies and see that, in our neural machine translation experiments, the extent to which this property is adhered to strongly correlates with BLEU.

## introduction as a simple search heuristic, beam search has been used to decode models developed by the nlp community for decades. indeed, it is noteworthy that beam search is one of the few nlp algorithms that has stood the test of time: it has remained a cornerstone of nlp systems since the 1970s @xcite . as such, it became the natural choice for decoding neural probabilistic text generators-whose design makes evaluating the full search space impossible @xcite @xcite . while there is no formal guarantee that beam search will returnor even approximate-the highest-scoring candidate under a model, it has repeatedly proven its merit in practice @xcite @xcite and, thus, has largely been tolerated-even embraced-as nlp's go-to search heuristic. however, in the context of neural machine translation (nmt), a shocking empirical finding has emerged: using beam search to decode sentences from neural text generators almost invariably leads to better text than using exact search (or beam search with a very large beam size). in fact, @xcite report that exact search returns the empty string @xmath0, 1 showing that the success of beam search does not stem from its ability to approximate exact decoding in practice, but rather due to a hidden inductive bias embedded in the algorithm. this inductive bias appears to be paramount for generating desirable text from neural probabilistic text generators. while several works explore this phenomenon @xcite @xcite , no one has yet hypothesized what beam search's hidden inductive bias may be. our work fills this gap. we analyze the beam search blessing by reverse engineering an objective that beam search returns the exact solution for. specifically, we introduce a regularizer for the the standard (map) decoding objective for text generation models such that the exact solution to this regularized objective is equivalent to the solution found by beam search under the unmodified objective. qualitative inspection reveals that our "beam search regularizer" has a clear connection to a theory in cognitive science-the uniform information density hypothesis (uid; @xcite . the uid hypothesis states that-subject to the constraints of the grammar-humans prefer sentences that distribute information (in the sense of information theory) equally across the linguistic signal, e.g., a sentence. in other words, human-produced text, regardless of language, tends to have evenly distributed surprisal, formally defined in information theory as negative log-probability. this connection suggests beam search has an interpretation as exact decoding, but with a uid-promoting regularizer that encourages evenly distributed surprisal in generated text. this insight naturally leads to the development of several new regularizers that likewise enforce the uid property. empirically, we experiment with our novel regularizers in the decoding of nmt models. we first observe a close relationship between the standard deviation of surprisals-an operationalization of uid-and bleu, which suggests that high-quality text does indeed exhibit the uid property. additionally, we find that even with exact search, our regularized objective leads to performance similar to beam search on standard nmt benchmarks. both of these observations are reflected in fig. 1 . lastly, we see that our regularizers alleviate the text-quality degradation typically seen when decoding with larger beam sizes. we take all the above as evidence that our proposed explanation of beam search's inductive bias indeed elucidates why the algorithm performs so well as a search heuristic for language generation tasks. ## neural probabilistic text generation probabilistic text generators define a probability distribution p θ (y | x) over an output space of hypotheses y (to be defined in eq. ( 1 )) conditioned on an input x. foot_1 modern generators are typically parameterized by a deep neural network-possibly recurrent-with a set of learned weights θ. in the case of text generation, the full set of possible hypotheses grows exponentially with the vocabulary size |v|. we consider the set of complete hypotheses, i.e., valid outputs, as the decoding objective for text generation aims to find the most-probable hypothesis among all candidate hypotheses, i.e. we aim to solve the following optimization problem: this is commonly known as maximum a posteriori (map) decoding since p θ is a probability model. while there exists a wealth of literature on decoding algorithms for statistical text generation models, e.g., phrase-based machine translation models, many of these methods cannot reasonably be used with neural models. specifically, due to the non-markovian structure of most neural text generators, dynamic-programming algorithms for searching over the exponentially large space are not efficient in this setting. indeed, there are formal results that solving eq. ( 3 ) with a recurrent neural network is np-hard @xcite . therefore decoding is performed almost exclusively with heuristic methods, such as beam search. ## deriving beam search we introduce a regularized decoding framework. the idea is simple; we seek to solve the regularized optimization problem to decode for a strategically chosen r(•). clearly, for certain r(•), we recover the decoding objectives discussed in §2.2. the question we ask in this work is the following: if we want to view beam search as an exact-decoding algorithm, which r(•) should we choose to recover beam search? we discovered an elegant answer rooted in information theory and cognitive science (the connections are discussed in-depth in §4). we first define the model's time-dependent surprisals, which are an information-theoretic concept that characterizes the amount of new information expressed at time t: note that minimally surprising means maximally probable. for the special case of greedy decoding, where @xmath1, the following choice of regularizer recovers beam search for sufficiently large λ: the intuition behind eq. ( 11 ) is to encourage locally optimal decisions: every local surprise u t should be close to the minimally surprising choice. in the limiting case where locally optimal decisions are not just encouraged, but rather enforced, we recover greedy search. formally, we have the following theorem: proof. by induction. in app. a. theorem 3.1 establishes that greedy search is the limiting case of a regularizer that seeks to encourage decisions to have high-probability locally. in contrast, the optimal map solution will generally not have this property. this is because a globally optimal map decoder may require a locally suboptimal decision for the sake of being able to make a compensatory decision later that leads to global optimality. 6 we now consider the generalization of greedy search (@xmath2. recall that beam search returns not just a single output, but rather a set of outputs. thus, we must consider the set-decoding objective proof. the proof follows from the same argument as theorem 3.1, albeit with sets instead of an individual hypothesis. note that in the (predominant) case where we want to return a single candidate sentence as the output rather than an entire set-as would be generated by eq. ( 12 )-we can take the highest-probability sequence in the chosen set y as our decoded output. the objective in eq. ( 12 ) boils down to a subset selection problem which, given the size of y, is a computationally prohibitive optimization problem. nonetheless, we can use it to analyze the properties enforced on generated text by beam search. ## from beam search to uid the theoretical crux of this paper hinges on a proposed relationship between beam search and the uniform information density hypothesis @xcite , a concept from cognitive science: hypothesis 4.1. "within the bounds defined by grammar, speakers prefer utterances that distribute information uniformly across the signal (information density). where speakers have a choice between several variants to encode their message, they prefer the variant with more uniform information density (ceteris paribus)" @xcite . at its core, the theory seeks to explain various aspects of human language processing in terms of information theory; it is often applied to an area of psycholinguistics known as sentence processing where the uid hypothesis is used to explain experimental data @xcite . as the uid hypothesis concerns a cognitive process (virtually) independent of the language in use, the theory should hold across languages @xcite . to see the hypothesis in action, consider the classic case of syntactic reduction from @xcite : in the above example, the sentence does not require the relativizer that at the start of the relative clause (denoted by rc); it would also be syntactically correct without it. however, many would agree that the relativizer makes the text qualitatively better. the information-theoretic explanation of this perception is that without the relativizer, the first word of a relative clause conveys two pieces of information simultaneously: the onset of a relative clause and part of its internal contents. including the relativizer spreads this information across two words, thereby distributing information across the sentence more uniformly and avoiding instances of high surprisal-which, from a psycholinguistic perspective, are displeasing. in short, the relativizer helps to ensure the uid property of the sentence. importantly, the preference suggested by the uid hypothesis is between possible utterances (i.e., outputs) where grammaticality and information content are held constant. any violation of these assumptions presents confounding factors when measuring, or optimizing, the information density of the generated text. in our setting, there is reason to believe that grammaticallity and information content are approximately held constant while selecting between hypothesis. first, the high-probability outputs of neural generation models tend to be grammatical @xcite . second, because decoding is conditioned on a specific input x, the conditional probability model p θ (y | x) is able to assign high-probability to outputs y that are plausible outputs (e.g., translations) of the given x. thus, even though the various y are not constrained to be sematically equivalent to one another, they tend to express similar information because they are at least relevant to the same x. this is why our regularized optimization problem eq. ( 9 ) combines an information-density regularizer with log p θ (y | x): the term log p θ (y | x) rewards grammaticallity and content relevance, whereas the information-density regularizer encourages the human preferences posited by the uid hypothesis. the parameter λ allows the preferences to be calibrated to perform well on downstream evaluation metrics, such as bleu and rouge. ## generalized uid decoding if beam search is trying to optimize for uid, can we beat it at its own game? this section develops a battery of possible sentence-level uid measures, which can be used as regularizers in our regularized decoding framework and compared experimentally on downstream evaluation metrics. variance regularizer. we first consider the variance regularizer from @xcite . in essence, uid concerns the distribution of information over the course (i.e., time steps) of a sentence. a natural measure for this is variance of the surprisals. ## experiments we explore how encouraging uniform information density in text generated by neural probabalistic text generators affects its downstream quality. to this end, we decode nmt models using the regularized objective (eq. ( 9 )) with our uid regularizers. we perform exact decoding for a range of λ and observe how text quality (quantified by bleu @xcite using the sacrebleu (post, 2018) system) and the distribution of surprisal changes. we additionally evaluate our regularizers under the beam search decoding strategy to see if penalizing violations of uid alleviates the text-quality degradation typically seen with increased beam widths. experiments are performed using models trained on the iwslt'14 de-en @xcite and wmt'14 en-fr @xcite datasets. for reproducibility, we use the model provided by fairseq @xcite for the wmt'14 task; foot_8 we use the data pre-processing scripts and recommended hyperparameter settings provided by fairseq for training a model on the iwslt'14 de-en dataset. we use the newstest'14 dataset as the test set for the wmt'14 model. all model and data information can be found on the fairseq nmt repository. foot_9 ## related work neural probabilistic text generators are far from perfect; prior work has shown that they often generate text that is generic @xcite , unnatural @xcite , and sometimes even non-existent @xcite . in the context of the degenerate behavior of these models, the beam search curse-a specific phenomenon where using a larger beam size leads to worse performance-has been analyzed by a number of authors @xcite @xcite @xcite @xcite . many of these authors attribute the performance drop (as search becomes better) to an inherent bias in neural sequence models to pefer shorter sentences. other authors have ascribed fault to the model architectures, or how they are trained @xcite @xcite @xcite . to remedy the problem, a large number of regularized decoding objectives and modified training techniques have been proposed. in contrast, this work analyzes the behavior of neural text generators from a different angle: we provide a plausible answer-inspired by psycholinguistic theory-as to why beam search (with small beams) leads to high-quality text, rather than another explanation of why exact search performs so badly. ## conclusion we analyze beam search as a decoding strategy for text generation models by framing it as the solution to an exact decoding problem. we hypothesize that beam search has an inductive bias which can be linked to the promotion of uniform information density (uid), a theory from cognitive science regarding even distribution of information in linguistic signals. we observe a strong relationship between variance of surprisals (an operationalization of uid) and bleu in our experiments with nmt models. with the aim of further exploring decoding strategies for neural text generators in the context of uid, we design a set of objectives to explicitly encourage uniform information density in text generated from neural probabalistic models and find that they alleviate the quality degradation typically seen with increased beam widths.