Truncation Sampling as Language Model Desmoothing (2022)

Abstract: Long samples of text from neural language models can be of poor quality. Truncation sampling algorithms–like top-p or top-k—address this by setting some words’ probabilities to zero at each step. This work investigates why these methods are important, and how to improve them. We propose thinking of a neural language model as a mixture of a true distribution and a smoothing distribution that avoids infinite perplexity. In this light, truncation algorithms aim to perform desmoothing, estimating a subset of the support of the true distribution. Finding a good subset is crucial: we show that top-p unnecessarily truncates high-probability words, for example causing it to truncate all words but Trump for a document that starts with Donald. We introduce eta-sampling, which truncates words below an entropy-dependent probability threshold. Compared to previous algorithms, our eta-sampling generates more plausible long documents according to humans, is better at breaking out of repetition, and behaves more reasonably on a battery of test distributions.

## introduction the complex, long-range dependencies of natural language make its generation an outstanding challenge. while there has been enormous progress on language modeling that has increased the coherence and length of generation @xcite , sampling directly from a language model can still result in nonsensical output @xcite . the most effective heuristics for generating high quality, diverse samples fall under a category we term truncation sampling. these algorithms set some words' probabilities to zero when generating each word @xcite @xcite . methods differ by their truncation criteria, ranging from simple (keep the k most likely) to complex, and all improve sample quality compared to direct sampling (holtzman et al., 2020). we ask (1) what is the aim of truncation and (2) how can we improve it? our key insight is to write a neural language model's distribution as a mixture of the true distribution and a uniform-like smoothing distribution. this idealized assumption is motivated by kl-divergence: models incur large kl at test time when they place near zero probability on an observed word @xcite . through this lens, the goal of truncation is to desmooth: to approximately recover the words on which the true distribution places some probability. as a stark example of smoothing degenerating sample quality, we show that a 5-gram language model smoothed with the uniform distribution generates nonsense as soon as a word is sampled from outside the support of the 5-gram model (figure 2 ). intuitively, sampling outside the 5-gram support causes future probabilities to be poorly estimated. we derive principles of truncation from an explicit smoothing model that formalizes the intuition that (1) words with high probability should not be truncated, and (2) when all words in the distribution have low probability, only words with low probability relative to the rest should be truncated. we find that state-of-the-art truncation sampling algorithms like top-p break these principles. for example, in top-p truncation (e.g., @xmath0.95), the most likely few words can take up p% of the distribution, causing the next-most likely word to be truncated even if it has high probability (e.g., 4%). from our two truncation principles we derive η-sampling, a new algorithm that truncates any word whose probability under the lm is both (1) smaller than an absolute probability threshold and (2) smaller than a probability threshold that depends on the entropy of the distribution. as we'll show, this ensures that, e.g., though gpt-2 large assigns probability 0.96 to the word trump for a document starting with donald, η-sampling allows multiple possible continuations, unlike top-@xmath1.95. we extensively study the behavior of η-sampling in comparison to top-p sampling and typical decoding @xcite . since each method allows for a range of quality-diversity tradeoffs, we set each method's hyperparameter by maximizing mauve score @xcite . we find that η-sampling truncates more reasonably on a checklist-style (ribeiro et al., 2020) battery of distributions. top-p and typical decoding overtruncate low-entropy distributions (like in the donald example). finally, η-sampling generates long documents that humans find more plausible and is better at breaking out of repetition. foot_0 2 background ## methods we now describe in detail two popular truncation sampling algorithms, discuss how they break our desmoothing principles, and then present two new truncation sampling algorithms including our proposed η-sampling. ## experiments & results our experiments characterize η-sampling relative to the state-of-the-art top-p and typical decoding. we use mauve, an automatic metric for openended generation, to find hyperparameters giving comparable diversity-accuracy tradeoffs. ηsampling behaves better in a range of settings, from long-document generation to more defensibly truncating low-entropy distributions. ## conclusion we've framed the class of truncation sampling algorithms as performing desmoothing, an insight that led to principles for how truncation should be done to recover the training distribution, a new truncation sampling algorithm, and evaluations that show the deficiencies of existing algorithms. we find the tendency of top-p decoding to over-truncate lowentropy distributions to be particularly surprising. we aim for these insights, and the evaluations we use, to drive further research in understanding and improving how we generate from neural language models. tional distributions of languages with rich morphology likely have different properties (especially with subword models).