PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.16041v1cs.LGcs.AI

TL;DR

The stochastic prediction errors of autoregressive language generation remain insufficiently understood from a rigorous probabilistic perspective. The paper characterizes cumulative token-prediction errors as a martingale and derives its moment properties; white-box experiments show empirical trajectories closely follow the predicted first- and second-order behaviors.

  • Problem

    How stochastic prediction errors evolve during autoregressive generation remains an open question requiring a principled stochastic-process characterization.

    Source: Introduction · p. 1

  • Method

    The paper defines token-level prediction errors, proves their cumulative process is a martingale, and derives first- and second-order moment characterizations, including an analytical quadratic-variation expression.

    Source: Introduction · pp. 1–2

  • Results

    Empirical decoding trajectories closely follow the theoretically predicted first- and second-order behaviors in white-box experiments across multiple LLM families.

    Source: Introduction · p. 2

  • Takeaways & Limitations

    The non-normalized cumulative martingale measure captures trajectory-level global drift and stochastic dynamics that conventional step-averaged uncertainty measures smooth out.

    Source: Relationship with Existing Uncertainty… · p. 7

    The stopping-time result assumes τ is bounded by the maximum generation length lmax, as required for the martingale stopping theorem.

    Source: Notations · p. 4

Abstract

from arXiv · show

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.

Introduction

The introduction frames autoregressive generation as a stochastic process whose sequence-level prediction errors remain undercharacterized by local token analyses. It presents a martingale framework for characterizing first- and second-order behavior and reports white-box empirical validation across multiple LLM families.

  • Prior analyses emphasize local predictive behaviors, including likelihood, uncertainty, entropy, and calibration, rather than stochastic deviations across complete decoding sequences (Holtzman et al. 2020; Meister, Cotterell, and Vieira 2020; Guo et al. 2017; Desai and Durrett 2020; Gal and Ghahramani 2016).The introduction identifies sequence-level evolution of prediction errors as an open question because each predictive distribution depends on previously generated tokens.Source: Introduction · p. 1
  • The cumulative token prediction-error vector is a martingale with respect to the decoding filtration, establishing a zero-drift first-order property.Although individual token realizations are stochastic, cumulative deviation remains zero in expectation.Source: Introduction · pp. 1–2
  • The second-order analysis gives an analytical expression for martingale fluctuations from realized token probabilities, without constructing high-dimensional error vectors.This connects sequence-level stochastic fluctuations to predictive distributions in autoregressive decoding.Source: Introduction · p. 2
  • White-box Monte Carlo experiments across multiple LLM families show empirical decoding trajectories closely follow the predicted first- and second-order behaviors.The introduction describes the validation as covering multiple families and scales.Source: Introduction · p. 2

Related Work

Prior work examines generation quality, uncertainty, decoding strategies, model internals, and other stochastic processes, but leaves the sequential stochastic evolution of autoregressive token generation underexplored. This work characterizes that evolution as a discrete martingale and analyzes its first- and second-order moments.

Analysis of Large Language Model Generation Dynamics

  • Research on autoregressive generation has studied quality, uncertainty, degeneration, and decoding strategies, including how decoding choices control model behavior.This passage situates the paper among work on generation behavior and decoding algorithms.Source: Related Work · p. 2
  • Existing uncertainty methods quantify predictions at isolated decoding steps, whereas this work models how prediction errors accumulate across generation as a martingale.Prior approaches use token likelihood, entropy, calibration metrics, and semantic-level uncertainty estimation; the proposed formulation enables first- and second-order moment analysis of the sequence.Source: Related Work · pp. 2–3

Theoretical Understanding of Neural Language Models

  • Prior theoretical studies address scaling, optimization, and internal mechanisms, while this work characterizes inference-time probabilistic dynamics independently of architecture.The passage distinguishes insights into model parameters and activations from the underexplored stochastic evolution of generated sequences.Source: Related Work · p. 2

Stochastic Process Perspectives in Machine Learning

  • Prior stochastic-process analyses mainly address training dynamics or continuous generative processes, whereas this work models discrete inference-time token generation as a martingale.The proposed perspective directly models the autoregressive decoding sequence.Source: Related Work · p. 2

Martingale Theory in Machine Learning

  • Although martingale methods are established in probability, online learning, and sequential decision-making, their application to autoregressive generation has not been systematically explored.This work formulates cumulative prediction error as a martingale and provides a probabilistic characterization through first- and second-order moment analysis.Source: Related Work · pp. 2–3

Preliminaries

The preliminaries formalize token history as a filtration and introduce martingales and stopping times to describe prediction-error evolution under variable-length decoding.

  • The token-history filtration F_t = σ(y_1, …, y_t) represents observed text, while a martingale is an integrable process adapted to that filtration with the martingale conditional-expectation property.The sequence of historical-token σ-algebras is monotone.Source: Preliminaries · p. 3
  • For text generation, the martingale property means the expected increment in cumulative prediction error, conditional on historical information, is zero when predictions are accurate and unbiased.Source: Preliminaries · p. 3
  • A stopping time models variable sequence termination when whether τ = t is determined by token history through time t.Source: Preliminaries · p. 3
  • For a bounded stopping time, the Martingale Stopping Theorem gives E[M_τ] = E[M_1]; a maximum generation length ensures bounded stopping and statistically conserves expected cumulative prediction error despite stochastic termination.Source: Preliminaries · p. 3

Theoretical Analysis

The analysis models autoregressive generation as a stochastic process, proves that cumulative prediction error is a martingale with zero first-order moment, and derives second-order measures linked to output stability.

Notations

  • The setup defines the filtration from generated-token histories, the predictive and one-hot token vectors, their prediction error, cumulative error M_t, and output length as an EOS-or-limit stopping time.The stopping time is bounded by the maximum generation length, satisfying the boundedness condition for the martingale stopping theorem.Source: Notations · pp. 3–4

Martingale and its Property of First-Order Moment

  • The cumulative prediction-error vector M_t is a martingale, and its first-order moment is zero at fixed times and stopping times.The stopping-time result is presented as a stronger formulation of the fixed-time result; the generation length is bounded by l_max.Source: Martingale and its Property of… · p. 4, Notations · p. 4

Calculation of the Second-Order Moment of the Martingale

  • The second-order moment can be computed from realized token probabilities as sum_t(1-p(y_t | y_<t)), including for stopping times, without summing over the full vocabulary.The fixed-length formula is expressed through the predictive probability vector; the realized-token formula uses scalar sums and probabilities commonly accessible from inference APIs.Source: Calculation of the Second-Order Moment… · p. 4

Second-Order Moment and Stability of Model Outputs

  • The second-order moment quantifies expected stepwise squared error and output uncertainty: larger values indicate less reproducible generations, while zero means generation is fully determined.The second-order moment decomposes the sum of token-indicator variances into within-sequence randomness and predictive-vector variance across sequences, and is a lower bound on that sum.Source: Second-Order Moment and Stability of… · p. 5
  • The second-order moment can distinguish output-stability differences that the sum of token-indicator variances does not, making it a more effective stability measure.The analysis also states that minimizing the second-order moment is equivalent to minimizing the sum of token-indicator variances; maximizing the former is not generally equivalent to maximizing the latter.Source: Second-Order Moment and Stability of… · pp. 5–6

Experiments

Experiments verify the martingale’s first- and second-order predictions across sampled generations and model families, then compare the second-order quantity with conventional uncertainty measures. The normalized quantity is highly correlated with token-level metrics, while the cumulative form retains additional sequence-level information.

Experimental Setup

  • Experiments use Llama-3.2-3B-Instruct by default with pure stochastic sampling at temperature 1.0, top-p 1.0, and top-k 0, without repetition penalties or external constraints.The paper reports white-box experiments with full logit access.Source: Experimental Setup · p. 6

First-Order Martingale Verification

  • On Llama-3.2-3B-Instruct, the averaged empirical first-order moment remains close to zero throughout generation despite fluctuations in individual vocabulary dimensions.The experiment estimates the mean from 300 randomly sampled vocabulary dimensions in one stochastic generation sequence.Source: First-Order Martingale Verification · p. 6, Figure 3 · p. 6

Second-Order Moment Identity Verification

  • With Llama-3.2-3B-Instruct, the empirical quadratic variation closely follows the theoretical curve across 30 independent sampled generation sequences.The comparison uses Monte Carlo estimates of the empirical quadratic variation against the theoretical expectation.Source: Second-Order Moment Identity… · p. 6, Figure 4 · p. 7

Scaling and Generality Analysis

  • Across Llama-3.x and Qwen2.5 models from 1B to 72B parameters, empirical second-order moments match theoretical predictions across scales, temperatures, and prompt categories.The authors also observe consistent differences in averaged quadratic variation across models under identical prompts, suggesting a potential model-specific probabilistic fingerprint.Source: Scaling and Generality Analysis · p. 6, Table 1 · p. 7, Figure 5 · p. 7

Relationship with Existing Uncertainty Measures

  • NSM is highly correlated with conventional token-level uncertainty metrics, whereas SM has only moderate correlation and preserves additional sequence-level information.The comparison uses predictive entropy, maximum probability, and perplexity over 300 unconstrained RAID benchmark trajectories.Source: Relationship with Existing Uncertainty… · p. 7, Table 2 · p. 7

Conclusion and Discussion

The paper characterizes autoregressive LLM decoding as a martingale process, deriving a closed-form predictable quadratic variation and finding that empirical trajectories track theoretical predictions. It presents the framework as a foundation for future work on uncertainty quantification, model identification, and adaptive decoding.

Conclusion and Discussion

  • The authors define per-step prediction errors from sampled indicators and conditional distributions, prove their cumulative sum is a zero-mean martingale, and derive a closed-form predictable quadratic variation.The conclusion frames these results as a rigorous characterization of autoregressive decoding.Source: Conclusion and Discussion · p. 7
  • White-box experiments show empirical trajectories precisely track theoretical predictions, supporting the claim that these stochastic dynamics are intrinsic to autoregressive generation.The conclusion describes the experiments as extensive.Source: Conclusion and Discussion · p. 7
  • Future work will explore using the martingale properties for trajectory-level uncertainty quantification, model identification, and adaptive decoding strategies.The paper presents these directions as extensions of its mathematical framework for interpreting model decoding dynamics.Source: Conclusion and Discussion · p. 7

A Proof

The proof establishes that the cumulative prediction-error process is a martingale and develops second-order moment results for ordinary and stopped versions of the process. It also examines conditions associated with zero predictive variation and equality in stated bounds.

A Proof

  • The process M_t is a martingale because it is adapted to the decoding filtration and its prediction-error increment has conditional expectation zero.The proof computes E[M_t | y_<t] = M_{t−1}.Source: A Proof · p. 9
  • The proof derives second-order moment expressions for the martingale, including versions with a stopping time.The passages state results for both ordinary and stopped processes but do not include the expressions themselves.Source: A Proof · pp. 9–11
  • One-hot conditional predictive vectors correspond to fixed token outputs and zero summed predictive variance.The passage also considers stopping times with positive probability, noting that the remaining proof is similar.Source: A Proof · p. 12
  • For the stated bounds, equality requires conditional mean predictive vectors to be uniform; equality in the second bound requires the vectors themselves to be uniform almost surely.The passage states that the latter condition implies the former and hence gives equality in equation (60).Source: A Proof · p. 12

Related papers

Loading 2610.16041v1…