What Do You Get When You Cross Beam Search with Nucleus Sampling? (2022)

Abstract: We combine beam search with the probabilistic pruning technique of nucleus sampling to create two deterministic nucleus search algorithms for natural language generation. The first algorithm, p-exact search, locally prunes the next-token distribution and performs an exact search over the remaining space. The second algorithm, dynamic beam search, shrinks and expands the beam size according to the entropy of the candidate’s probability distribution. Despite the probabilistic intuition behind nucleus search, experiments on machine translation and summarization benchmarks show that both algorithms reach the same performance levels as standard beam search.

## introduction the standard approach to natural language generation uses a search algorithm, guided by an autoregressive (conditional) language model, to search through the space of possible strings. since this search space is immense, pruning techniques have been introduced to facilitate tractable text generation. beam search @xcite is a deterministic algorithm that prunes the search space according to the relative rank of each prefix, keeping only the top b prefixes at every step. although rank-based pruning has no probabilistic justification -it is mainly motivated by its ability to limit memory consumption -beam search is an effective approach for generation tasks such as machine translation and summarization. nucleus sampling @xcite , on the other hand, is a stochastic algorithm, which prunes the bottom percentile of the model's next-token distribution, thus eliminating bad candidates while retaining some degree of randomness, which is important for free-form generation. what if we were to replace beam search's rank-based pruning mechanism (top k) with the probabilistic mechanism of nucleus sampling (top p)? we experiment with two variants of this hypothetical nucleus search. the first algorithm, p-exact search, locally prunes the search space by retaining only the top p of every next-token distribution that the underlying language model produces. it then performs an exact search over the remaining space, guaranteeing the most probable sequence under the local pruning assumption. the second algorithm, dynamic beam search, selects the top p beams at each step, according to their normalized probabilities (rather than top k, by rank). this method can shrink or enhance the number of beams to match the current step's low or high entropy, respectively. we evaluate both algorithms on three conditional generation benchmarks: subword-level translation (wmt'14 en-fr), character-level translation (iwslt'14 de-en), and summarization (xsum). while we observe that both nucleus search algorithms produce competitive results with standard beam search, we do not find any empirical advantage to our probabilistically-motivated approach. we further analyze the algorithms by isolating the impact of dynamically expanding or shrinking the number of candidates. experiments show that expanding the beam, even when entropy is high, tends to decrease performance. pruning candidates, on the other hand, appears to have no adverse effects, and may even have a marginal positive effect in certain cases, which possibly cancels out with the negative effects of beam expansion. ## background natural language generation can be defined as a search problem in the space of possible sequences over a token vocabulary v , where the goal is to find an optimal sequence @xmath0, ..., y n ) ∈ v * according to some cost function. typical search algorithms explore this infinite space via sequence prefixes, starting with the empty sequence, and appending one potential token y t at a time. search terminates by returning a sequence (or a sequences set) that ends with a special token that indicates the end of the sequence (eos). the cost function is based on an underlying language model that, given a prefix @xmath1, induces a probability distribution over v , which we denote p (y t |@xmath2. 1 the probability of a sequence (or prefix) y is computed as the product of its tokens probabilities: in practice, it is common to use the negative log probability instead: this defines a monotonic additive cost function, where appending each token y t adds a positive cost log p (y t |@xmath3. ## nucleus search we combine beam search with tail pruning, producing two variants of nucleus search: p-exact search and dynamic beam search. byrne (2019) show that exact search @xcite often produces extremely short and even empty sequences because the underlying model assigns a non-zero probability to the eos token at each step. we use tail pruning (section 2.2) to round all near-zero probabilities (whether belonging to eos or any other token) to zero. we apply exact search over the pruned space, guaranteeing the most probable sequence that contains only top-p tokens at each step. ## experiments we compare our search algorithms to beam search on a variety of tasks, and use the same model across all settings, for each task. ## results main result despite their increased stability, there appears to be no significant advantage to either p-exact search or dynamic beam search over the original beam search. in fact, the performance differences between the best settings of each algorithm are always under 0.2 bleu/rouge, and often zero. we find this trend counter-intuitive, since we originally assumed that expanding and trimming the beam based on entropy would benefit language generation. we further test these assumptions individually. ## related work as a standard decoding strategy, there is a significant body of literature on beam search. recently, there has been more focus on the empty string problem @xcite , and the fact that increasing the beam size beyond a small constant typically hurts performance. @xcite show that beam search optimize for sequences that distribute information uniformly, and therefore, using small beam sizes allows it to overcome the empty string problem. @xcite train models with multiple different eos tokens based on their positions, instead of a single universal eos token. @xcite replace the softmax function with the sparse entmax transformation @xcite that can assign absolute zero probability to tokens. this method has a similar effect to our p-exact search, but requires training the model with entmax, while our contribution only modifies the search algorithm. massarelli et al. (2020) also propose a combination of beam search and sampling methods, but with a different method and a different goal. they focus on free-form text generation, addressing two problems -repetition and halucination -by sampling the first few tokens, and then switching over to beam search. @xcite explore how using a small fixed beam size, pruned further according to the relative or absolute distance from the top scored candidate, can increase decoding speed. in this work, we focus on the quality of the generated text, comparing the use of a fixed beam size to tail pruning, an established method that keeps candidates according to the nucleus of the distribution. ## conclusion language models predict a distribution over their vocabulary, yet beam search only utilizes the rank of different candidates, not their actual probability scores. a natural assumption is that searching the space of prefixes with a constant number of options is not optimal. we hypothesize that using the probability scores to dynamically determine the number of candidates may benefit natural language generation. we test our hypothesis by introducing two nucleus search algorithms, which incorporate probabilistic tail pruning @xcite with beam search, but find that they perform on par with the baseline beam search algorithm when its beam size is restricted to a small constant.