Autoregressive Decoding as a Martingale: Characterizing the Stochastic Dynamics of LLM Generation

Xiahui Zhu; Zhenyi Qi; Wanwei Liu; Haoang Chi; Yang Tan; Xinyu Sun; Ji Wang

cs.LGOct 12, 2026

Autoregressive Decoding as a Martingale: Characterizing the Stochastic Dynamics of LLM Generation

Authors: Xiahui Zhu, Zhenyi Qi, Wanwei Liu, Haoang Chi, Yang Tan, Xinyu Sun, Ji Wang

Organizations: College of Computer, National University of Defense Technology, Changsha, Hunan, China

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.

Figures & tables

Figure 1: A stochastic process perspective of autoregressive generation. Existing analyses focus on local token-level uncertainty, while the evolution of prediction errors across the entire generation sequence remains unclear. Our perspective models autoregressive decoding as a stochastic process, where cumulative prediction errors form a martingale and exhibit predictable second-order dynamics without requiring full prediction distributions.

Panel of Figure 2 — Figure 2: The case where $\mathbb{E}_{y_{\leq t}}[\|\bm{M}_{t}\|_{2}^{2}]$ isn’t maximized when $\sum_{i=1}^{t}\mathrm{Var}(\bm{w}_{i})$ is maximized.

Figure 3: Empirical verification of the first-order martingale property on Llama-3.2-3B-Instruct. The sampled vocabulary dimensions exhibit random fluctuations, while their averaged cumulative error remains around the theoretical expectation $\mathbb{E}[\mathbf{M}_{t}]=0$ .

Figure 4: Verification of the second-order martingale identity on Llama-3.2-3B-Instruct. The empirical second-order moment closely matches the theoretical prediction throughout the generation sequence.

Model	Empirical	Theoretical	Error
Llama-1B	861.60	865.23	3.63
Llama-3B	796.40	781.61	14.79
Llama-8B	708.74	698.66	10.09
Llama-70B	475.45	462.09	13.36
Qwen-1.5B	609.81	622.64	12.84
Qwen-3B	434.98	436.80	1.83

Table 1: Cross-model verification of the second-order martingale identity. The empirical second-order moment consistently agrees with the theoretical quadratic variation across different model scales.

Panel of Figure 5 — Figure 5: Generality analysis of the second-order martingale behavior. The empirical second-order moments consistently agree with the theoretical quadratic variation across different model scales, sampling temperatures, and prompt categories.

	Entropy	PPL	MaxProb
SM	0.7203	0.7057	0.7018
NSM	0.9889	0.9482	0.9950

Table 2: Pearson correlation between the martingale second-order moment (SM), its normalized form (NSM), and existing uncertainty measures.

Autoregressive Decoding

Autoregressive decoding generates outputs step by step, conditioning each token on earlier ones while balancing quality, control, and inference cost.

See all 56 papers

Aug 7, 2026

Stochastic Autoregressive Learning

Motivated by LLMs, which generate outputs by iteratively sampling from next-token distributions, we introduce a PAC-learning model for binary stochastic autoregressive learning. This generalizes the deterministic autoregressive learning framework of Joshi et al., COLT 2025. In our model, one fixed generator assigns a Bernoulli next-token distribution to every prompt string. Starting from an input prompt, a token is sampled and appended to the prompt; the same generator is then applied again to this expanded prompt; this procedure is repeated for

M

steps. Three forms of supervision are considered: base one-step samples, chain-of-thought (CoT) samples that reveal full random trajectories of length

M

, and end-to-end (e2e) samples that reveal only the final token of length

M

trajectories. For a generator class, we study the minimum number of samples

m_{base}(\varepsilon),m_{CoT}(\varepsilon), m_{e2e}(\varepsilon)

, resp., required to learn the one-step probabilities in the base model, and the final-token probability in the CoT and e2e models, under squared loss error~

\varepsilon

. We show that stochastic autoregressive learning fundamentally differs from the deterministic theory. At scale

\varepsilon

, there is no universal comparison between the three learning tasks: both

m_{CoT}/m_{base}

and

m_{e2e}/m_{CoT}

can be made simultaneously arbitrarily larger than

M/\varepsilon

, the natural analogue for the existing deterministic results. Nevertheless, after altering scales, for every class, CoT learning at scale

\varepsilon

is upper-bounded by base learning at scale

\varepsilon/M^2

, whereas e2e learning at scale

\varepsilon

is upper-bounded, up to logarithmic factors, by

(M/\varepsilon) m_{CoT}(Θ(\varepsilon))

. These dependencies and scales are essentially tight. We complement these bounds by studying dimension

d

logistic functions in our model.

Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel

1MIT · 2The Hebrew University

Autoregressive Generation PAC Learning Autoregressive Modeling

Ask PDF

Oct 20, 2026

Predictive Latents for Autoregressive Language Models: Possibility, Gauge, and Obstruction

Autoregressive language models are trained by next-token cross-entropy, yet several recent systems also iterate a hidden state without emitting a token: continuous thoughts, pause steps, and recurrent depth. This note separates three risks on one latent process. The token risk

R_{\mathrm{tok}}

scores a readout. The teacher-forced latent risk

R_1

scores a one-step map that sees the true hidden state. The open-loop risk

R_H

scores the same map after it has been iterated on its own outputs. If the Bayes next-token posterior is a function of a

k

-dimensional statistic with full-rank covariance, a width-

k

latent, a linear least-squares transition, and a refit unembedding match the Bayes token predictor. The statistic is identified only up to an invertible gauge: whitening the residual stream does not change the token law once the unembedding is refit. The matching obstructions are sharp. A constant latent drives

R_1

to zero while token cross-entropy falls back to the marginal entropy. A perfect token predictor can still hide a null-space walk whose open-loop error grows linearly in the horizon. A small next-latent loss does not certificate next-token prediction, and a small next-token loss does not certificate free latent rollout, unless a rank or injectivity condition is stated with the number.

Yuzhou Hong

Zhejiang Sci-Tech University

Autoregressive Language Modeling Latent Dynamics Modeling Next-Token Prediction Recurrent Language Models

Ask PDF

Sep 20, 2026

The Probabilistic Structure of Large Language Models

This paper presents a probabilistic perspective on large language models (LLMs), developed with the aim of bringing together, in a single self-contained account, tools that are usually treated separately across the literature. LLMs are described through probability measures on the set of sequences of tokens, specified via their autoregressive conditional distributions. Training is formulated as a maximum-likelihood estimation problem, addressed by stochastic gradient methods, while text generation is viewed as the sequential simulation of the resulting stochastic process. The role of the asymmetry of the Kullback--Leibler divergence in text generation is examined in relation with characteristic phenomena such as hallucination and the distinction between statistical plausibility and truth. As a complementary illustration of the same viewpoint, we also discuss diffusion models, built around the score function, which cast generation not as sequential token prediction but as the simulation of a reverse-time stochastic process transforming noise into data both in discrete and continuous time.

Adnan Aboulalaâ

Language Modeling Autoregressive Language Modeling LLM Training

Ask PDF

Abstract

Autoregressive Decoding

Explore similar work

Stochastic Autoregressive Learning

Predictive Latents for Autoregressive Language Models: Possibility, Gauge, and Obstruction

The Probabilistic Structure of Large Language Models