Local Normalization Distortion and the Thermodynamic Formalism of Decoding Strategies for Large Language Models (2025)

Abstract: Advances in hardware and language model architecture have spurred a revolution in natural language generation. However, autoregressive models compute probability distributions over next-token choices, and sampling from these distributions, known as decoding, has received significantly less attention than other design choices. Existing decoding strategies are largely based on heuristics, resulting in methods that are difficult to apply or improve in a principled manner. We develop the theory of decoding strategies for language models by expressing popular decoding algorithms as equilibrium states in the language of ergodic theory and stating the objective functions they optimize. Using this, we analyze the effect of the local normalization step required to make probabilities sum to one in top-k, nucleus, and temperature sampling. We argue that local normalization distortion is a fundamental defect of decoding strategies and quantify the size of this distortion and its effect on mathematical proxies for the quality and diversity of generated text. This yields conclusions for the design of decoding algorithms and the detection of machine-generated text.

## introduction autoregressive large-language models are poised to transform industries such as healthcare, finance and education @xcite . rapid advancements in this field have been fueled by scaling @xcite , transformer network architectures @xcite , and alignment processes @xcite . however, autoregressive language models produce conditional distributions over predicted next tokens, and these must be iteratively sampled during inference. a suite of decoding methods exist * equal contribution. for this sampling, such as top-k, nucleus, or temperature sampling, but these are based on heuristics and our understanding of these methods is in its infancy, with most being developed through trial and error @xcite . this is surprising, since the choice of decoding strategy has a profound impact on the quality of the generated text and, in some cases, may be more important than the model architecture @xcite . for example, greedy sampling, or the related concept of beam search, tends to produce accurate but repetitive or dull text @xcite . in contrast, pure sampling produces much more varied and interesting text but can produce text which is 'incoherent and almost unrelated to the context' @xcite . our primary goal is to fill this gap and initiate the theoretical study of decoding strategies. as an application of this theory, we investigate a wellknown defect of popular decoding strategies, which results from truncating the distribution of possible next tokens at each step during inference. truncation necessitates repeated renormalization to obtain valid probability distributions, and results in a phenomenon we term local normalization distortion. the fact that local normalization distorts the resulting probability distribution is well-known, but not well-understood. our contributions are as follows. ## a motivating example many autoregressive models for natural language generation work broadly as follows. given a vocabulary v, one builds a large neural network to estimate the likelihood p(y t |@xmath0, given the previous tokens @xmath1. then, one decides on a decoding strategy (sampling algorithm), which is a way of using the collection of likelihoods {p(y t |@xmath2: y @xmath3. for example, one could always choose the token y t which has highest likelihood p(y t |@xmath4, or one could allow each token y t to be chosen with probability equal to the likelihood p(y t |@xmath5. let q(•|@xmath6. having chosen the token y t , one repeats the process to choose y t+1 given the new context in many settings, rather than conditioning on the whole history @xmath7, making the process of generating texts an l-step markov process. a simple example shows how the decoding strategy can dramatically influence q. suppose we have a language model that produces model likelihoods p. we feed in the context 'the cat sat on' and obtain the likelihoods of the various choices of the next two tokens. let these likelihoods be as described in figure 1 . assume further that we decide that various choices of tokens are unreliable and so we wish to restrict our choices to the two most likely tokens depicted in blue boxes. we now have probabilities which do not sum to one, and so have to decide how to normalize them. option 1: global normalization. compute the probabilities of complete strings and divide by the sum of the probabilities of complete strings. in our example, the sum of the probabilities of complete strings is 0.26 = 0.01 + 0.01 + 0.18 + 0.06. we end up with 'the cat sat on a fence' being selected with probability 0.01/0.26 ≈ 0.038. option 2: local normalization. renormalize conditional probabilities locally so that the probabilities of outward edges from each node sum to one. for example, we choose the first word 'a' with probability 0.1/0.4 and 'the' with probability 0.3/0.4. with local normalization, we end up with 'the cat sat on a fence' being selected with probability 0.25×0.5 = 0.125. observe that these two different methods of normalizing probabilities yield very different probability distributions. ## decoding strategies the decoding strategies we study in this article fall into two classes, truncation sampling algorithms (such as nucleus sampling and top-k) and temperature sampling. truncation sampling algorithms work by defining an allowed set a @xmath8, restricting the model conditional probability distribution p(•|@xmath9. ## decoding strategies as equilibrium states in the last section we reviewed the literature on what a decoding strategy ought to maximize. in this section we prove results about what popular decoding strategies actually optimize. in particular, we state results of the form 'given some context @xmath10, the probability distribution q on the set a * @xmath11,k obtained by sampling according to a certain decoding strategy is the unique probability distribution on a * @xmath12,k that maximizes the following objective function...'. in the language of ergodic theory, what we are doing is describing the outcome of a decoding strategy as an equilibrium state associated to a certain potential. while the mathematics of this section is not hard, it is useful as it allows us to ask whether the function that our decoding strategy maximizes is well aligned with the theoretical goals of a decoding strategy. in a follow-up paper @xcite we apply the ideas of this section to build a novel algorithm for detecting text generated by a language model. we use the following standard result. as usual, let 0 log 0 := 0. lemma 5.1 @xcite , lemma 1.1). let @xmath13, • • • , k} be a finite set and let @xmath14, • • • , r k ) be a probability measure on x assigning mass r i to symbol i. then r is the unique probability measure maximizing the quantity the results of this section follow as direct corollaries to lemma 5.1 by analyzing the measures (r 1 , ..., r k ) given by various decoding strategies. details are given in the appendix d. our first result concerns top-k decoding. corollary 5.1. given some context @xmath15, the distribution q k on a * @xmath16,k produced by top-k sampling is the unique distribution maximizing the quantity h(µ) proxy for diversity if our equation above had only the first two terms, it would show that q k maximizes the sum of mathematical proxies for diversity and quality among distributions supported on a * @xmath17,k . the third term however, which is an artifact of local normalization, distorts this goal. if the third term was constant across sequences y then it would have no effect, but issues arise when it has a large variance; see section 6.1. next, we consider nucleus sampling. corollary 5.2. given some context @xmath18, the distribution q π on a * @xmath19,π generated by nucleus sampling is the unique distribution maximizing the quantity thus nucleus sampling produces a distribution q π maximizing a goal related to quality, diversity and an error term related to both by the length of the sequence y and the extent to which the mass of the tokens selected by nucleus sampling overshoots the target π. finally, we consider temperature sampling. corollary 5.3. given some choice of temperature τ and context @xmath20, the distribution q τ is the distribution maximizing the quantity when nucleus or top-k sampling set π < 1 or @xmath21, they produce distributions with lower entropy than p, since token choice has been reduced. this process also redistributes mass from low probability tokens to higher probability tokens, reducing the average log-likelihood. thus the parameters associated with nucleus or top-k sampling allow one to prioritize quality or diversity. this is somewhat hidden in the statements of corollaries 5.1 and 5.2, it appears only in that it is the space of distributions on a * upon which the proxy for diversity, proxy for quality, and distortion term are maximized. temperature sampling is not a truncation algorithm, and the way it modulates between prioritizing quality and prioritizing diversity is in the factor 1/τ preceding the mathematical proxy for quality in the main equation of corollary 5.3. as before, the third term here is not related to the goal of maximizing quality or diversity. it is broadly similar to the distortion introduced by top-k, except rather than dividing by the product along a sequence of the mass contained in the top-k tokens, it divides by the product along a sequence y m • • • y t of the l 1/τ norm of the distribution p(•|@xmath22. finally, we see that global normalization removes the problematic third term in each of the quantities maximized by our decoding strategies. corollary 5.4. in each of corollaries 5.1-5.3, if the locally normalized probability distribution (q k , q π , or q τ ) is replaced by its globally normalized equivalent, the statement of the theorem remains the same except without the third term (i.e. the distortion term) in the expression for the maximized quantity. this is important because it shows that, in terms of the quality-diversity trade off goals of the previous section, locally normalized decoding strategies perform strictly worse than their globally normalized counterparts. in section 6.2 we quantify this effect. ## experiments in this section we quantify the size of effects predicted in our theoretical sections. in particular, we measure the size of local normalization distortion and its effect on the quality-diversity trade off, measured through log-likelihood and entropy. while one may, in some circumstances, care more about semantic diversity than lexical diversity, or about human judgements of quality than language model log-likelihood, effects on these metrics would be downstream of the true mathematical effect of local normalization distortion, and likely highly dependent on both the language model and the task being performed. thus, for reasons both of stability and of quantifying our theoretical results directly, we run our experiments on metrics present in the objective functions maximized by decoding strategies. the experiments of this section are run using llama 2-7b @xcite ) on a single a100 gpu. detailed setup for each experiment is contained in the corresponding sections and appendices. in appendix e, we repeat our experiments using pythia 1b and 2.8b @xcite , and llama 3.2 1b and 3.2 3b @xcite . as predicted above, our experimental results remain qualitatively unchanged. the primary challenge to running these experiments is the computational cost of global normalization. to do this efficiently, we introduce a process based on rejection sampling in appendix b. ## conclusions our primary contribution is to express popular decoding strategies as equilibrium states. in doing so, one can see that the quantity which they maximize contains a term relating to local normalization of probability mass which seems unrelated to any reasonable goal of a decoding strategy. in particular, this term pulls the resulting probability distribution away from the quality-diversity maximizing curve. we have shown experimentally that the effect of local normalization distortion on the probability of selecting a string is typically very large (section 6.1), and that it has a strongly negative effect on the quality-diversity tradeoff (section 6.2) when these quantities are measured through entropy and loglikelihood. in a follow-up work @xcite we build a detector of machine generated text based on local normalization distortion which outperforms state of the art alternatives. these factors lead us to the conclusion that local normalization distortion may have a negative effect on machine-generated text and that it should be carefully considered both when practitioners choose a decoding strategy and in the design of future methods for detecting machine-generated text.