Abstract
This paper establishes a rigorous theoretical foundation for Large Language Model (LLM) decoding strategies by framing them through the lens of thermodynamic formalism. We identify a fundamental mathematical defect termed local normalization distortion, which arises from the step-by-step probability renormalization used in common heuristic strategies like top-k and nucleus sampling. By decomposing the objective functions of these strategies, we demonstrate that local normalization introduces a "distortion term" that unnecessarily sacrifices text quality for diversity. Our empirical results across Llama and Pythia model families quantify this distortion, showing it can alter relative string probabilities by factors exceeding 300x, and provide a theoretical explanation for the empirical success of nucleus sampling.
Introduction
In autoregressive text generation, LLMs predict a probability distribution for the next token. To avoid the repetitive and deterministic nature of greedy search, practitioners employ decoding strategies such as top-k, nucleus (top-p), or temperature sampling. These methods introduce stochasticity, but they are largely heuristic, developed through empirical trial and error rather than first principles.
A critical commonality among these strategies is that they truncate the token distribution and "locally" renormalize the remaining probabilities at every step so they sum to one. This paper investigates the mathematical consequences of this local renormalization, arguing that it distorts the final probability of the entire sequence in a way that harms the balance between text quality and diversity.
Theoretical Framework: Decoding as Physics
The researchers bridge the gap between natural language processing and statistical mechanics using ergodic theory and thermodynamic formalism. Under this framework, popular decoding algorithms are viewed as "equilibrium states" that maximize a specific objective function.
The authors prove that the objective function optimized by these strategies can be decomposed into three distinct components:
- Diversity: Measured as the entropy of the distribution.
- Quality: Measured as the average log-likelihood of the sequence.
- Distortion Term: A mathematical "tax" paid for the convenience of local normalization.
To isolate the impact of this distortion, the study compares standard "local" decoding against a theoretical "global" version, which normalizes the probability of the entire sequence at once. While global normalization is computationally infeasible for standard inference, the authors utilize rejection sampling to simulate it for research purposes.
Experimental Methodology
The theory was evaluated using several open-source model families, including Llama 2 (7B), Llama 3.2 (1B and 3B), and Pythia (1B and 2.8B). The researchers generated completions from simple prompts (e.g., "The ") to measure how significantly local normalization boosts or suppresses specific strings compared to the mathematically ideal global baseline.
Key Insights
The Scale of Distortion
The distortion is not merely a theoretical nuance; it is a substantial error. The math reveals that local normalization adds significant noise to the objective function, pulling the model away from the ideal quality-diversity frontier. For temperature sampling at $\tau = 0.86$, the researchers found that in 50% of cases, local normalization distorted the relative probabilities of two different string completions by a factor of at least 392.
Nucleus Sampling as the "Least Broken" Strategy
One of the most significant practical findings is that nucleus sampling (top-p) suffers from considerably less distortion than top-k or standard temperature sampling. This provides a theoretical justification for why nucleus sampling has emerged as the industry standard for high-quality text generation.
The Quality-Diversity Trade-off
Experiments consistently showed that "Global" decoding—the version stripped of the distortion term—outperforms "Local" decoding. At any fixed level of diversity (entropy), the globally normalized version produces text with higher model-rated quality (log-likelihood). This suggests that current models are capable of producing better text than our current decoding strategies allow.
Conclusion and Future Directions
This research highlights that local normalization distortion is a universal property of current autoregressive generation, holding true across different model architectures and sizes. While globally normalized decoding is currently too computationally expensive for real-time applications, this theoretical framework opens the door for "distortion-aware" decoding algorithms. Such algorithms could potentially offer the benefits of global normalization without the associated compute costs. Additionally, the authors suggest that the specific signature of this distortion could be used as a signal to improve the detection of machine-generated text.
Summary updated