Local Normalization Distortion and the Thermodynamic Formalism of Decoding Strategies for Large Language Models
This work addresses the fundamental issue of decoding strategies for researchers and practitioners in natural language generation, offering a theoretical foundation to guide algorithm design and machine-generated text detection.
The paper tackles the problem of decoding strategies in large language models, which are often heuristic-based and lack principled improvement, by developing a theory that frames popular decoding algorithms as equilibrium states and quantifying the distortion caused by local normalization on text quality and diversity.
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.