Locally Typical Sampling (2023)

Abstract: Today’s probabilistic language generators fall short when it comes to producing coherent and fluent text despite the fact that the underlying models perform well under standard metrics (e.g., perplexity). This discrepancy has puzzled the language generation community for the last few years. In this work, we posit that the abstraction of natural language generation as a discrete stochastic process—which allows for an information-theoretic analysis—can provide new insights into the behavior of probabilistic language generators, for example, why high-probability texts can be dull or repetitive. Humans use language as a means of communicating information, aiming to do so in a simultaneously efficient and error-minimizing manner; in fact, psycholinguistics research suggests humans choose each word in a string with this subconscious goal in mind. We formally define the set of strings that meet this criterion: Those for which each word has an information content close to the expected information content, namely, the conditional entropy of our model. We then propose a simple and efficient procedure for enforcing this criterion when generating from probabilistic models, which we call locally typical sampling. Automatic and human evaluations show that, in comparison to nucleus and top-k sampling, locally typical sampling offers competitive performance (in both abstractive summarization and story generation) in terms of quality while consistently reducing degenerate repetitions.

## introduction modern probabilistic models have repeatedly demonstrated their prowess at modeling natural language, placing high probability on held-out corpora from many different domains (brown et al., 2020; hoffmann et al., 2022; chowdhery et al., 2022). yet when used as text generators, their performance is far from perfect. one of the largest determinants of the generated text's qual-ity is the choice of decoding strategy-that is, the decision rule used to extract strings from a model. perhaps surprisingly, for many language generation tasks, decoding strategies that aim to find the highest-probability strings produce text that is undesirable (holtzman et al., 2020; see et al., 2019; eikema and aziz, 2020; zhang et al., 2021; delucia et al., 2021). for instance, stahlberg and byrne (2019) report that in their neural machine translation experiments, the highestprobability string is usually the empty string. on the other hand, stochastic strategies, which take random samples from the model, often lead to text with better qualitative properties (fan et al., 2018; holtzman et al., 2020; basu et al., 2021). however, stochastic strategies still have a host of other problems, while not entirely dispensing with those seen in maximization-based approaches. @xcite at first glance, it is unintuitive that highprobability strings are often neither desirable nor human-like. due to this pathology, a number of studies have concluded that there must be faults in the training objective or architecture of the probabilistic models behind language generators (welleck et al., 2020; guan et al., 2020; li et al., 2020, inter alia). yet, this conclusion is at odds with these models' performance in terms of other metrics. the fact that modern models can place high probability on held-out text suggests that they provide good estimates (in at least some aspects) of the probability distribution underlying human language. we posit that looking at language generation through an information-theoretic lens may shed light on this paradox. communication via natural language can intuitively be cast in information-theoretic terms. indeed, there is a long history of studying language through the lens of information theory (shannon, 1948, 1951; hale, 2001; piantadosi et al., 2011; pimentel et al., 2020, inter alia). in this paradigm, linguistic strings are messages used to convey information, and their information content can be quantified as a function of their probability of being uttered-often driven by context. assuming that humans use language in order to transmit information in an efficient yet robust manner (zaslavsky et al., 2018; gibson et al., 2019), the subset of strings typically used by humans should encode information at some (perhaps near-optimal) rate. @xcite in fact, prior works studying the uniform information density hypothesis (levy and jaeger, 2007; mahowald et al., 2013) empirically observed this property in humans' use of natural language. these insights lead us to re-think what it means to be a probabilistic language generator. first, we contend that language generators, in some cases, can be thought of as discrete stochastic processes. this, in turn, allows us to cleanly define typicality (and the typical set) for these processes. we argue, however, that due to discrepancies between the model behind these generators and the true distribution over natural language strings, directly sampling from the typical set is not a good idea. indeed, for language generators that do not use an end-of-string (eos) state, this is exactly what is done by ancestral sampling-a decoding strategy not known for providing high-quality text. inspired by research on human sentence processing, we then define the more restrictive notion of local typicality, and argue that if we want text generated from a model to be ''human-like,'' we should perhaps enforce this information-theoretic criterion in generations ourselves. to this end, we develop a new algorithm, which we call locally typical sampling. concretely, we hypothesize that for text to be perceived as natural, each word should have an information content close to its expected information content given prior context. when sampling from probabilistic language generators, we should limit our options to strings that adhere to this property. in experiments on abstractive summarization and story generation, we observe that, compared to nucleus and top-k sampling: (i) locally typical sampling reduces the number of degenerate repetitions, giving a rep value (welleck et al., 2020) on par with human text, and (ii) text generated using typical sampling is generally closer in quality to that of human text. 3 ## two views of language modeling in this work, we discuss language models 4 in an information-theoretic light. our first step towards this goal is to re-frame their presentation. concretely, we put forth that there are actually two lenses through which we can view language modeling productively. under the traditional lens, we can think of a language model as a distribution over full strings: a language model constitutes the distribution of a single string-valued random variable. under an alternative lens, we can think of a language model as a discrete stochastic process: a collection of indexed random variables. we compare and contrast these views formally, and then show how to use the language process view to derive a new sampling algorithm in §5. ## information-theoretic properties of language processes the view of language modeling as a discrete stochastic process naturally lends itself to an analysis through the lens of information theory. indeed, much of information theory is concerned with the study of discrete stochastic processes (see, e.g., cover and thomas, 2012, ch. 4). in this section, we review standard information-theoretic definitions in §3.1 and build on these to introduce our own notion of local typicality in §3.2. ## local typicality in natural language to motivate our definition of local typicality in the context of natural language, we must first look at language through an information-theoretic lens. we will consider two distributions in this section: p, the distribution that a speaker of the language is assumed to generate strings from, and p our language process that approximates p-albeit, perhaps not perfectly. in this setting, we view a natural language string y as a means of communicating some information, where each word y t is a symbol via which we construct our message. the information content of y is then defined as its negative log-probability under a specified distribution:log p(y). following the chain rule of probability, this quantity can be decomposed over words, that is, the information content of a word is its negative log-probability given prior context:log p(y t | @xmath0. ## sampling from a language process in this section, we describe how to sample from a language process parameterized by the distribution p, foot_8 or in more commonly used terminology, how to decode from p. there are many different algorithms one could employ to sample from p. the most intuitive strategy is ancestral sampling, foot_9 which works as follows: sample y t ∼ p(• | @xmath1, for example, the eos symbol is sampled or a maximum length is reached. note that in the case of the former criterion, this procedure is equivalent to sampling entire strings according to the distribution p. perhaps the most popular set of techniques for sampling fall under a paradigm we call truncated sampling, where the vocabulary at a time step is truncated to a core subset of words. for instance, fan et al. (2018) propose limiting the sampling space to the top-k most likely words in each decoding step, and holtzman et al. (2020) consider the smallest nucleus (i.e., subset) of words whose cumulative probability mass exceeds a chosen threshold η. in this paper, we give a general treatment of truncated sampling and then discuss our variant. given a context-dependent constraint subset c(@xmath2, we define the truncated distribution as and we call c(@xmath3. now we give two examples of truncated samplers. algorithm 5.1 (top-k sampling). in top-k sampling, the truncation set c(@xmath4, i.e., the solution to the following subset maximization problem maximize algorithm 5.2 (nucleus sampling). in nucleus sampling, we choose a threshold parameter η and define the truncation set c(@xmath5: minimize ## experiments in this section, we explore the efficacy of our decoding strategy on two natural language generation tasks: abstractive summarization and story generation. we assess performance with respect to several other stochastic decoding strategies: nucleus sampling, top-k sampling, temperature sampling, 20 beam search, and mirostat. our evaluation includes both automatic metrics and human ratings. hyperparameters. in a preliminary hyperparameter sweep using mauve @xcite (pillutla et al., 2021), we found @xmath6, 40}, η = {0.9, 0.95} and τ = 3.0 to be the best performing hyperparameters for top-k sampling, nucleus sampling and mirostat, respectively. for locally typical sampling, we found τ = 0.2, τ = 0.95 to provide the best results for story generation and abstractive summarization, respectively. standard values according to the literature for other hyperparameters (i.e., for beam search and temperature sampling) were employed. we use these values in our human evaluations and in computation of automatic metrics. automatic quality metrics. as automatic quality metrics, we evaluate the generated text's perplexity-under both the model used to generate the text (ppl(g)) and an independent, i.e., not finetuned, lm (ppl(i)), namely gpt-2 large (radford et al., 2019). several prior works have shown that neither low nor high perplexity (zhang et al., 2021; nadeem et al., 2020; pillutla et al., 2021) are direct indicators of text quality. rather, human-like text often has perplexity within a certain range. consequently, we report the difference in this metric from the reference text as well. we additionally evaluate using mauve 23 (pillutla et al., 2021) with the reference text. ## conclusion in this work, we analyze decoding from probabilistic language generators in the informationtheoretic framework. we equate a language model to a discrete stochastic process, and use the known properties of such processes to quantitatively describe the samples we should expect. motivated by results in psycholinguistics, we hypothesize that-with the goal of communicating efficiently and robustly-humans produce text whose perword information content is within a close range of the expected information content of a word given prior context. current language models may fall short in capturing this property, which is a possible explanation for why the corresponding language processes often do not lead to humanlike text. yet, this observation provides a simple new criterion for decoding more human-like text from probabilistic language generators: constraining the sampling space to words that meet this criterion. in experiments on two language generation tasks, we find that our strategy-called locally typical sampling-leads to text of comparable or better quality than other stochastic decoding strategies according to human ratings. further, when compared to these other decoding strategies, several quantitative properties of typicallysampled text more closely align with those of human text.