Large language model token prediction follows a predictable error pattern
Autoregressive Decoding as a Martingale: Characterizing the Stochastic Dynamics of LLM Generation
Machine LearningArtificial Intelligence
Summary
Predicting the next word in a sentence with large language models (LLMs) involves some randomness, but this paper shows that the errors over time follow a special balanced pattern called a martingale. The authors provide a way to measure how much the sequence of predicted tokens fluctuates based on the model's own uncertainty. They tested their math on several popular LLMs and found the predictions matched real data closely. This helps us understand the “randomness” in text generation and could improve detecting AI-generated text or estimating uncertainty.
What this means in practice
- •For llm system developers: Analyze the uncertainty and error dynamics during token generation to improve model debugging and calibration.
- •For ai content moderators: Apply the predictable error patterns to more reliably detect AI-generated text by identifying statistical fingerprints distinctive to LLM outputs.$Commercial implications: Enables AI-generated text detection tools for platforms requiring content authenticity verification.
Tested on one dataset.
Authors
Xiahui Zhu, Zhenyi Qi, Wanwei Liu, Haoang Chi, Yang Tan, Xinyu Sun, Ji Wang
Abstract
Large language models (LLMs) have achieved remarkable success across a wide range of language tasks. At their core, autoregressive LLMs are conditional probability models that learn to approximate the next-token distribution given the preceding context. Despite this probabilistic nature, the stochastic dynamics of autoregressive decoding have rarely been investigated from a rigorous probabilistic perspective. In this work, we define the per-step prediction error as the difference between the sampled token indicator and the model's conditional predictive distribution, and prove that the cumulative error process is a martingale with respect to the decoding filtration, implying that its conditional first-order moment is identically zero. Beyond this first-order property, we derive a closed-form expression for the second-order behavior of the martingale sequence: its predictable quadratic variation reduces to $\sum_t\left(1-p(y_t\mid y_{<t})\right)$, computable from realized token probabilities alone. This identity establishes a direct theoretical connection between sequence fluctuations and predictive uncertainty during autoregressive decoding. White-box experiments on Llama-3.x and Qwen2.5 families (1B to 72B parameters) verify that the empirically measured second-order moments closely match the theoretical predictions derived from our martingale analysis. These results provide a probabilistic framework for analyzing autoregressive LLM decoding, reveal intrinsic probabilistic fingerprints of different language models, and establish a rigorous mathematical foundation for LLM-generated text detection and uncertainty quantification.