Paper deep dive
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
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.16041v1
- Canonical: https://arxiv.org/abs/2610.16041v1
Trouble viewing inline? Open PDF directly →
Full Text
69,389 characters extracted from source content.
Expand or collapse full text
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 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 ∑t(1−p(yt∣y<t)) _t (1-p(y_t y_<t) ), 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. 1College of Computer, National University of Defense Technology, Changsha, Hunan, China zhuxiahui21@nudt.edu.cn 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. Introduction Large Language Models (LLMs) have achieved remarkable success across a wide range of natural language tasks through autoregressive decoding (Touvron et al. 2023; Achiam et al. 2023), where tokens are sequentially sampled from context-dependent predictive distributions. Despite their probabilistic nature, the stochastic dynamics governing the evolution of LLM generation sequences remain insufficiently understood from a rigorous probabilistic perspective (Welleck et al. 2020). Since autoregressive LLMs are fundamentally conditional probability models, understanding their generation dynamics is a natural yet underexplored direction. Existing analyses mainly focus on local predictive behaviors, including likelihood, uncertainty, entropy, and calibration metrics (Holtzman et al. 2020; Meister et al. 2020; Guo et al. 2017; Desai and Durrett 2020; Gal and Ghahramani 2016). However, these approaches characterize individual prediction distributions rather than the evolution of stochastic deviations over complete decoding sequences. A fundamental question therefore remains open: how do stochastic prediction errors evolve during autoregressive generation? Since the predictive distribution at each step depends on previously generated tokens, a principled stochastic-process characterization is needed to understand the intrinsic randomness of language generation. In this work, we introduce a martingale perspective to analyze autoregressive LLM decoding. We define token-level prediction error as the difference between sampled token indicators and conditional predictive probabilities, and prove that the cumulative error process forms a martingale with respect to the decoding filtration. This establishes a fundamental first-order zero-drift property: although individual token realizations are stochastic, their cumulative deviation remains zero in expectation. Beyond the first-order property, we characterize the fluctuation dynamics through second-order analysis. We derive an analytical identity showing that the martingale second-order moment can be computed directly from realized token probabilities, avoiding explicit construction of high-dimensional error vectors. This establishes a theoretical connection between sequence-level stochastic fluctuations and predictive distributions in autoregressive decoding. To validate the theoretical framework, we conduct white-box experiments on multiple LLM families using Monte Carlo sampling. Results show that empirical decoding trajectories closely follow the theoretically predicted first- and second-order behaviors. The main contributions of this work are summarized as follows: • We formulate autoregressive LLM decoding as a stochastic process and establish that the cumulative prediction error vector forms a martingale with respect to the decoding filtration. • We derive first- and second-order moment characterizations of the decoding martingale, including an analytical quadratic variation expression determined by the model’s predictive probability distribution. • We provide comprehensive white-box empirical verification across multiple modern LLM families and scales, confirming the generality of the derived stochastic properties. Related Work Analysis of Large Language Model Generation Dynamics. Understanding the behavior of autoregressive generation has become an important research direction for large language models. Previous studies have mainly investigated generation quality, uncertainty estimation, degeneration phenomena, and decoding strategies (Fan et al. 2018; Li et al. 2023; Leviathan et al. 2023; Mitchell et al. 2023). Holtzman et al. analyzed neural text degeneration and proposed nucleus sampling to alleviate unreliable low-probability token selection during generation (Holtzman et al. 2020; Meister et al. 2022). Meister et al. studied the relationship between beam search and probabilistic sequence generation, highlighting the importance of decoding strategies in controlling model behavior (Meister et al. 2020). Beyond decoding algorithms, recent studies have explored uncertainty estimation and confidence calibration for neural language models. Token-level likelihood, entropy, calibration metrics, and semantic-level uncertainty estimation approaches have been widely adopted to quantify predictive confidence during generation (Guo et al. 2017; Jiang et al. 2021; Kuhn et al. 2023; Lin et al. 2022; Kadavath and others 2022; Brier 1950). However, these approaches primarily focus on the marginal properties of individual predictions. They characterize uncertainty at isolated decoding steps but do not explicitly model how stochastic deviations accumulate and evolve along the autoregressive generation sequence. In contrast, our work studies the sequential stochastic dynamics of prediction errors and establishes a martingale-based characterization of autoregressive decoding. Theoretical Understanding of Neural Language Models. Recent advances in large language models have motivated increasing efforts toward developing theoretical explanations of their capabilities and behaviors (Wei et al. 2022; Ouyang et al. 2022). Existing theoretical studies have investigated scaling behavior, optimization properties, and internal mechanisms of large neural language models (Garg et al. 2022). Kaplan et al. revealed empirical scaling laws describing the relationship between model size, dataset size, and performance (Kaplan et al. 2020). Hoffmann et al. further refined these observations by studying compute-optimal scaling strategies for large language models (Hoffmann et al. 2022). In the realm of interpretability, current mechanistic approaches have made significant strides in uncovering how transformer architectures internally represent and process information (Meng et al. 2022; Wang et al. 2023; Olsson et al. 2022). While these studies yield profound insights into model parameters and internal activations, the stochastic evolution of the generated sequence over time remains largely underexplored. Our work provides a complementary perspective by characterizing the macroscopic probabilistic dynamics induced during autoregressive inference, entirely independent of specific architectural components. Martingale Theory in Machine Learning. Martingale theory provides a fundamental mathematical framework for analyzing stochastic processes whose future conditional expectation is determined by their current information state. Classical martingale results have played an important role in probability theory, sequential analysis, and stochastic optimization (Doob 1953; Freedman 1975; McDiarmid 1989). In machine learning, martingale techniques have been widely applied to derive concentration bounds, analyze online learning algorithms, and establish theoretical guarantees for sequential decision-making problems. For example, Azuma-Hoeffding inequalities and related martingale concentration tools have been extensively used in reinforcement learning and multi-armed bandit analysis (Azuma 1967; Bubeck and Cesa-Bianchi 2012; Lattimore and Szepesvári 2020). Stochastic Process Perspectives in Machine Learning. Stochastic process theory has provided powerful tools for analyzing sequential behaviors in machine learning systems. Recent studies have employed stochastic differential equations, diffusion processes, and stochastic optimization frameworks to characterize the dynamics of learning algorithms and generative models (Song et al. 2021; Li et al. 2022). However, these analyses mainly focus on training dynamics or continuous generative processes, while the discrete stochastic evolution of autoregressive token generation remains largely unexplored. Our work differs by directly modeling the inference-time decoding sequence of LLMs as a discrete martingale process. Despite its importance in sequential learning theory, martingale analysis has not been systematically explored for autoregressive language generation. In this work, we bridge this gap by introducing a martingale formulation for the cumulative prediction error process of LLM decoding. This perspective enables rigorous first- and second-order moment analysis of the generation sequence and provides a probabilistic characterization of autoregressive decoding dynamics. Preliminaries In this section, we briefly review the central concepts of martingale theory within the context of probability theory and stochastic processes, providing a theoretical underpinning for the modeling of the autoregressive generation process discussed in the subsequent chapter. Consider a complete probability space (Ω,ℱ,P)( ,F,P). In the context of discrete-time autoregressive text generation, the output token sequence ytt≥1\y_t\_t≥ 1 produced by the stochastic process corresponds to the observed sequences in the sample space. Definition 1 (Filtration). A sequence of sub-σ-algebras =ℱtt≥1F=\F_t\_t≥ 1 on the measure space is called a filtration if it satisfies the property of monotonicity, i.e., ℱ1⊆ℱ2⊆⋯⊆ℱn⊆ℱF_1 _2 ·s _n . In this study, we define ℱt=σ(y1,y2,…,yt)F_t=σ(y_1,y_2,…,y_t) as the σ-algebra generated by the historical token sequence up to time t, representing all observed historical text information (Doob 1953). Definition 2 (Martingale). Given a filtration F, a stochastic process M=Mtt≥1M=\M_t\_t≥ 1 adapted to this filtration is called a martingale with respect to F if it satisfies: 1. Integrability: For any t≥1t≥ 1, [|Mt|]<∞E[|M_t|]<∞; 2. Martingale Property: For any t≥1t≥ 1, the conditional expectation equality holds almost surely: [Mt+1∣ℱt]=Mt.E[M_t+1 _t]=M_t. (1) In the context of text generation, this property implies that if the model prediction is accurate and unbiased, then the expected increment of the future evolution of the cumulative prediction error—where observed values deviate from predicted probabilities—given the historical information, should be zero. In actual text generation tasks, the length of a sequence is often not fixed but determined by specific stopping conditions (such as generating an [EOS] token or reaching a maximum length limit). This is mathematically characterized by “stopping time“. Definition 3 (Stopping Time). A random variable τ:Ω→ℕ∪+∞τ: ∪\+∞\ is called a stopping time with respect to filtration F if for any t, the event τ=t\τ=t\ depends only on the historical information up to time t, i.e., τ=t∈ℱt\τ=t\ _t (Doob 1953). With the definition of stopping time, we have the theorem as follows. Theorem 1 (Martingale Stopping Theorem). Let M=Mtt≥1M=\M_t\_t≥ 1 be a martingale with respect to F, and τ be a stopping time. If τ is bounded (i.e., there exists a constant K such that τ≤Kτ≤ K almost surely), then the expected value of the process at the stopping time equals its expected value at the initial time: [Mτ]=[M1]E[M_τ]=E[M_1]. Noticing that for LLMs the maximum generation length ensures a bounded stopping time, MST conditions are always satisfied. This guarantees that the expected cumulative prediction error remains statistically conserved for model-generated sequences, independent of stochastic termination. Theoretical Analysis This section aims to prove and explore martingale properties of LLMs. First, we formalize the generation process of autoregressive language models as a stochastic process, prove that it satisfies the martingale property, and further examine the properties of the first-order moment. Second, based on previous results, we turn our attention to the second-order moment of the martingale, where a series of formulas are given to accommodate the practical operation of LLMs. Finally, we examine the meaning of martingale second-order moments, linking it to the stability of model outputs. Notations Let X and =yt1≤t≤lmax Y=\y_t\_1≤ t≤ l_max be a discrete sequence of input and output text respectively, where yt∈y_t denotes the token at time step t, lmaxl_max denotes the maximum generation length of LLM, and V denotes the complete vocabulary set of the model. We define the filtration =ℱtt≥1F=\F_t\_t≥ 1, where ℱt=σ(y1,y2,…,yt)F_t=σ(y_1,y_2,…,y_t). To be precise, ℱtF_t is the power set of tV^t. The generation process of LLM, an autoregressive model, is essentially a parameterized conditional probability distribution p(yt∣y<t;,)p(y_t y_<t; X, θ), often abbreviated as p(yt∣y<t)p(y_t y_<t) when X and θ remain unchanged and are not the focus of discussion, where y<ty_<t represents the sequence y1y2…yt−1y_1y_2… y_t-1. Similarly, we donte y≤ty_≤ t as the sequence y1y2…yty_1y_2… y_t. In what follows, the notation yt[⋅]E_y_t[·], y<t[⋅]E_y_<t[·] will denote the expectations taken over the random variables yty_t and y1,y1,…,yt−1y_1,y_1,…,y_t-1 respectively. Other cases follow analogously. In practice, large language models output vectors rather than scalars, so we introduce the following vectors in ℝ||R^|V|: Predictive Probability Vector (t g_t): t,y=p(y∣y<t;,). g_t,y=p(y y_<t; X, θ). (2) This vector is just the predictive probability vector given by the model for next token. It depends on input X, parameters θ and the history of output y<ty_<t. Token Indicator Vector (t w_t): t,y=y=yt. w_t,y=I_\y=y_t\. (3) It’s the one-hot vector for the token actually generated by the model at time t. Prediction Error Vector (t e_t): t=t−t. e_t= w_t- g_t. (4) Notice that yt[t∣y<t]=tE_y_t[ w_t y_<t]= g_t, error vector t e_t actually measures the discrepancy between t w_t and its expectation t g_t. Cumulative Prediction Error Vector (t M_t): t=∑i=1ti. M_t= _i=1^t e_i. (5) Just as the name suggests. t M_t is the accumulation of error t e_t, which is the central focus of our paper. We will proof that it is actually a martingale and elaborate on its various properties. To more meticulously model the stochastic process underlying text generation by LLM, it is essential to account for the randomness in the length of the generated text. Hence, we introduce the concept of stopping time: Stopping Time (τ): A random variable τ:Ω→1,2,…,lmaxτ: →\1,2,…,l_max\ which is defined as follows: τ:=inft>0:ytis[EOS]∪lmax.τ:= \ \t>0:y_t\ is\ [EOS]\∪\l_max\. (6) In the context of token tracing, τ is actually the output length. When [EOS] is generated, τ is the first occurrence time of the end-of-sequence token. Otherwise it is the maximum generation length lmaxl_max with length limit reached. It can be easily verified that τ=t∈ℱt\τ=t\ _t and thus τ is a stopping time with respect to F. It should be noted that τ is strictly bounded by the maximum generation length lmaxl_max, which satisfies the boundedness condition required for martingale stopping theorem. Martingale and its Property of First-Order Moment The cornerstone of our entire theoretical analysis rests upon the fact that t M_t is a martingale with respect to the filtration F. Theorem 2. The stochastic process tt≥1\ M_t\_t≥ 1 is a martingale with respect to the filtration F. Furthermore, we define the first-order moment of the martingale as one aspect of the study of its martingale properties. Definition 4 (First-Order Moment of the Martingale). Given a martingale Mtt≥1\M_t\_t≥ 1, the first-order moment of martingale Mtt≥1\M_t\_t≥ 1 at time t (or stopping time τ) is y≤t[t]E_y_≤ t[ M_t] (or y≤lmax[τ]E_y_≤ l_max[ M_τ]). It is not difficult to see that the first-order moment of the martingale t M_t in fact characterizes the expected value of the accumulated prediction error. By the martingale expectation property, it follows that y≤t[t]=y1[1]=y1[1]−1=0.E_y_≤ t[ M_t]=E_y_1[ M_1]=E_y_1[ w_1]- g_1=0. (7) Furthermore, by martingale stopping theorem, we obtain y≤lmax[τ]=y1[1]=0.E_y_≤ l_max[ M_τ]=E_y_1[ M_1]=0. (8) It should be emphasized that equation (8) holds for arbitrary F-stopping times, thereby rendering it a stronger version of equation (7)—indeed, equation (7) is obtained as the special case where τ≡tτ≡ t. In what follows, any theorem or equation stated in terms of stopping times is uniformly understood as a strengthened formulation of the corresponding non-stopping-time version; we shall not repeat this remark subsequently. Equations (7) and (8) show that whether for fixed time t or stopping time τ, the first-order moment of tt≥1\ M_t\_t≥ 1 is always 0, which means accumulated prediction error vanishes to 0 in the long run. This implies that the first-order moment alone cannot furnish sufficient information for analytical and practical purposes, which motivates us to investigate the properties of the second-order moment in the next section. Calculation of the Second-Order Moment of the Martingale To gain a deeper characterization of martingale properties, we now introduce the second-order moment of the martingale. Definition 5 (Second-Order Moment of the Martingale). Given a martingale Mtt≥1\M_t\_t≥ 1, the second-order moment of martingale Mtt≥1\M_t\_t≥ 1 at time t (or stopping time τ) is [‖t‖22]E[\| M_t\|_2^2] (or y≤lmax[‖τ‖22]E_y_≤ l_max[\| M_τ\|_2^2]). Regarding the calculation of the second-order moment, we present the following theorem: Theorem 3. The second-oreder moment of martingale Mtt≥1\M_t\_t≥ 1 can be expressed as follows: y≤t[‖t‖22]=y<t[∑i=1t(1−‖i‖22)].E_y_≤ t[\| M_t\|_2^2]=E_y_<t [ _i=1^t(1-\| g_i\|_2^2) ]. (9) Theorem 3 offers a viable approach for computing the second order moment, which is determined exclusively by the vector t g_t, indicating that it constitutes an inherent characteristic of the LLM. However, it doesn’t consider the random generation text length τ—it can only calculate for fixed length t. Hence, we turn to the formula for the second order moment associated with stopping time. Theorem 4. The second order moment of martingale tt≥1\ M_t\_t≥ 1 with stopping time can be expressed as follows: y≤lmax[‖τ‖22]=y≤lmax[∑t=1τ(1−‖t‖22)].E_y_≤ l_max[\| M_τ\|_2^2]=E_y_≤ l_max [ _t=1^τ(1-\| g_t\|_2^2) ]. (10) In contrast to Theorem 3, Theorem 10 better reflects the practical operation of LLMs. Nevertheless, it presents an application-level concern: the individual components of t g_t are not necessarily all available, depending on the accessibility (open-source vs. closed-source) of the model. In response, we present the following theorem: Theorem 5. The second-oreder moment of martingale Mtt≥1\M_t\_t≥ 1 can be expressed as follows: y≤t[‖t‖22]=y≤t[∑i=1t(1−p(yi∣y<i))].E_y_≤ t[\| M_t\|_2^2]=E_y_≤ t [ _i=1^t(1-p(y_i y_<i)) ]. (11) Theorem 6. The second order moment of martingale tt≥1\ M_t\_t≥ 1 with stopping time can be expressed as follows: y≤lmax[‖τ‖22]=y≤lmax[∑t=1τ(1−p(yt∣y<t))]. gatheredE_y_≤ l_max[\| M_τ\|_2^2]\\ =E_y_≤ l_max [ _t=1^τ(1-p(y_t y_<t)) ]. gathered (12) Compared with equations (9) and (10), equations (11) and (12) do not require knowledge of every component of t g_t. They only need the actually generated tokens y≤ty_≤ t and their associated conditional probabilities p(yt∣y<t)p(y_t y_<t), which are usually accessible from typical LLM inference APIs. In addition, their computation does not require squaring and summing over |||V| components, but only scalar summations. This suggests that equations (11) and (12) are both more computationally efficient and easier to implement in practice. Second-Order Moment and Stability of Model Outputs In fact, the second order moment of martingales is closely tied to the stability of LLM outputs. Here we restrict our attention to syntactic stability, which refers to the similarity of generated texts across repeated generating. Theorem 7. The second-oreder moment of martingale (with stopping time) can be expressed as follows: y≤t[‖t‖22]=y≤t[∑i=1ti2], _y_≤ t[\| M_t\|_2^2]=E_y_≤ t [ _i=1^t e_i^2 ], (13) y≤lmax[‖τ‖22]=y≤lmax[∑t=1τt2]. _y_≤ l_max[\| M_τ\|_2^2]=E_y_≤ l_max [ _t=1^τ e_t^2 ]. (14) Theorem 7 implies that the second order moment of martingales captures the expected sum of squared errors at each step, which essentially quantifies the uncertainty in LLM outputs. The larger this value, the less reproducible the model is, and vice versa. It equals zero if and only if the error at every step is zero—that is, the model’s generation is entirely determined by the given input and parameters. The following theorem further characterizes the relationship between the second order moment of martingales and the output stability of the model. Theorem 8. For the second order moments y≤t[‖t‖22]E_y_≤ t[\| M_t\|_2^2] and y≤lmax[‖T‖22]E_y_≤ l_max[\| M_T\|_2^2], the following relation holds: ∑i=1tVar(i)=y≤t[‖t‖22]+∑i=1tVar(i), _i=1^tVar( w_i)=E_y_≤ t[\| M_t\|_2^2]+ _i=1^tVar( g_i), (15) y≤lmax[∑t=1τVar(t)]=y≤lmax[‖τ‖22]+y≤lmax[∑t=1τVar(t)]. gatheredE_y_≤ l_max [ _t=1^τVar( w_t) ]\\ =E_y_≤ l_max[\| M_τ\|_2^2]+E_y_≤ l_max [ _t=1^τVar( g_t) ]. gathered Then ∑i=1tVar(i)≥y≤t[‖t‖22], _i=1^tVar( w_i) _y_≤ t[\| M_t\|_2^2], (18) y≤lmax[∑t=1τVar(t)]≥y≤lmax[‖τ‖22]. _y_≤ l_max [ _t=1^τVar( w_t) ] _y_≤ l_max[\| M_τ\|_2^2]. (19) Theorem 8 states that the sum of variances of i w_i admits a decomposition into two components: the second order moment of the martingale and the sum of variances of i g_i, and the second order moment serves as its lower bound. Specifically, the second order moment measures the randomness within the same output sequence, while the sum of variances of i g_i measures the randomness across different output sequences. It can be shown that minimizing the second order moment of the martingale is equivalent to minimizing the sum of variances of i w_i. Theorem 9. The following equivalences hold: ∑i=1tVar(i)=0⇔y≤t[‖t‖22]=0, _i=1^tVar( w_i)=0 _y_≤ t[\| M_t\|_2^2]=0, (20) y≤lmax[∑t=1τVar(t)]=0⇔y≤lmax[‖τ‖22]=0. gatheredE_y_≤ l_max [ _t=1^τVar( w_t) ]=0 \\ E_y_≤ l_max[\| M_τ\|_2^2]=0. gathered With Theorem 9, we naturally ask whether the maximization of the second order moment of the martingale is equivalent to the maximization of the sum of variances of i w_i. The answer is negative. We have the following theorem: Theorem 10. The following equivalences hold: ∑i=1tVar(i)=t(1−1||)⇔∀1≤i≤t:y<i[i]=1||, gathered _i=1^tVar( w_i)=t(1- 1|V|) \\ ∀ 1≤ i≤ t:E_y_<i[ g_i]= 1|V|1, gathered y≤t[‖t‖22]=t(1−1||)⇔∀1≤i≤t:(i=1||a.e.), gatheredE_y_≤ t[\| M_t\|_2^2]=t(1- 1|V|) \\ ∀ 1≤ i≤ t:( g_i= 1|V|1\ a.e.), gathered where 1 is the all-one vector. The following implication hold: y≤t[‖t‖22]=t(1−1||)⇒∑i=1tVar(i)=t(1−1||). gatheredE_y_≤ t[\| M_t\|_2^2]=t(1- 1|V|) \\ _i=1^tVar( w_i)=t(1- 1|V|). gathered (27) Counterexample to the converse of equation (27) is provided, as shown in Figure 2. roota(0.5)a(0.7)b(0.3)b(0.5)b(0.7)a(0.3) (a) Maximize ∑i=1tVar(i) _i=1^tVar( w_i). roota(0.5)a(0.5)b(0.5)b(0.5)b(0.5)a(0.5) (b) Maximize y≤t[‖t‖22]E_y_≤ t[\| M_t\|_2^2]. Figure 2: The case where y≤t[‖t‖22]E_y_≤ t[\| M_t\|_2^2] isn’t maximized when ∑i=1tVar(i) _i=1^tVar( w_i) is maximized. In Figures 2(a) and 2(b), each node has |||V| child nodes, representing the tokens that can be generated at the next time step, with each child node associated with a selection probability p(yt∣y<t)p(y_t y_<t). For Figure 2(a), we have y≤2[‖2‖22]=0.92,∑i=12Var(2)=1. gatheredE_y_≤ 2[\| M_2\|_2^2]=0.92,\\ _i=1^2Var( w_2)=1. gathered (28) For Figure 2(b), we have y≤2[‖2‖22]=1,∑i=12Var(2)=1. gatheredE_y_≤ 2[\| M_2\|_2^2]=1,\\ _i=1^2Var( w_2)=1. gathered (29) Comparing equation (28) with equation (29), we can observe that the second order moment of the martingale does not necessarily reach its maximum when the sum of the variances of i w_i is maximized. Furthermore, it is intuitively expected that Figure 2(b) exhibits greater randomness than Figure 2(a). Nevertheless, the above calculation results show that the sum of the variances of i w_i cannot reflect this discrepancy, whereas the second order moment of the martingale can. This suggests that, in contrast to the sum of the variances of i w_i, the second order moment of the martingale serves as a more effective measure of output stability. Experiments Experimental Setup We conduct white-box experiments (with full logit access) to empirically verify the theoretical properties of our martingale formulation. Computations are performed on an Ubuntu 22.04 system equipped with two NVIDIA RTX PRO 6000 GPUs, a 44-core Intel Xeon Platinum 8470Q CPU, 220GB RAM, Python 3.12, PyTorch 2.12.1, and CUDA 13.0. By default, we use Llama-3.2-3B-Instruct. The decoding process uses pure stochastic sampling (T=1.0T=1.0, top-p=1.0p=1.0, top-k=0k=0) with no repetition penalties or external constraints. The experiments are organized into four parts: (1) verification of the first-order martingale property, (2) verification of the derived second-order moment identity, (3) scaling and generality analysis, and (4) comparison with existing uncertainty measures. First-Order Martingale Verification According to Theorem 1 and equation (7), the cumulative prediction error process tM_t forms a martingale with zero first-order moment. Therefore, we empirically examine whether the estimated cumulative prediction error remains centered around zero during autoregressive generation. To empirically verify this property, we perform a single stochastic generation sequence with Llama-3.2-3B-Instruct. At each decoding step, the complete vocabulary-level error vector is computed. Then, K=300K=300 vocabulary dimensions are randomly sampled, and the empirical mean sequence is estimated as μ^t=1K∑j=1KMt,vj μ_t= 1K _j=1^KM_t,v_j. If the martingale property holds, this sequence should remain centered around zero without systematic drift. Figure 3 shows the evolution of the empirical first-order moment. Although individual vocabulary dimensions exhibit random fluctuations, their averaged sequence remains close to zero throughout the generation process, which agrees with the theoretical expectation. 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 [t]=0E[M_t]=0. Second-Order Moment Identity Verification Beyond the first-order property, Theorem 5 and equation (11) provide a tractable estimation of the second-order moment. This result allows us to verify the theoretical quadratic variation using only the probabilities of the actually generated tokens. To verify this relationship, we conduct Monte Carlo sampling with K=30K=30 independent generation sequences using Llama-3.2-3B-Instruct. For each sequence, we compute the empirical quadratic variation ‖t‖22\|M_t\|_2^2 and compare its Monte Carlo estimation with the theoretical expectation given by equation (11). Figure 4 demonstrates that the empirical sequence closely follows the theoretical curve. The consistency between both quantities verifies the derived quadratic variation identity. 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 Qwen-7B 282.13 283.84 1.72 Qwen-72B 210.35 214.05 3.70 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. Scaling and Generality Analysis To ensure these second-order behaviors generalize, we evaluate the Llama-3.x and Qwen2.5 families (1B to 72B parameters). Final-step statistics are summarized in Table 1, while Figure 5 presents complete trajectory comparisons. Across varying model scales, sampling temperatures, and prompt categories, the empirical moments consistently match theoretical predictions. This confirms that our derived identity characterizes an intrinsic property of autoregressive decoding rather than a model-specific artifact. Interestingly, under identical prompts, we observe that the averaged quadratic variation varies consistently across different models, hinting at its potential utility as a model-specific probabilistic fingerprint. (a) Scaling analysis on Llama models. (b) Scaling analysis on Qwen models. (c) Effect of sampling temperature. (d) Effect of prompt variations. 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. Relationship with Existing Uncertainty Measures To interpret our derived second-order quantity, we compute its Pearson correlation against standard uncertainty proxies (predictive entropy, maximum probability, and perplexity) over 300 unconstrained trajectories from the RAID benchmark (Dugan et al. 2024). As Table 2 shows, the length-normalized second-order quantity (NSM) is highly correlated with conventional token-level metrics. Crucially, the non-normalized cumulative form (SM) maintains only a moderate correlation. This demonstrates that our proposed martingale metric captures distinct trajectory-level global drift and cumulative stochastic dynamics that are otherwise smoothed out by conventional step-averaged uncertainty measures. 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. The results show that the martingale second-order moment shares related information with existing uncertainty measures. Interestingly, after normalization by sequence length, the second-order quantity becomes highly correlated with token-level uncertainty metrics. This indicates that the cumulative form preserves additional sequence-level information beyond conventional averaged uncertainty measures. Conclusion and Discussion In this work, we characterize autoregressive LLM decoding as a rigorous martingale process. By defining per-step prediction errors as the difference between sampled indicators and conditional distributions, we prove that the cumulative error forms a zero-mean martingale and derive a tractable, closed-form identity for its predictable quadratic variation. Extensive white-box experiments confirm that empirical trajectories precisely track our theoretical predictions, proving these stochastic dynamics are intrinsic to autoregressive generation. While this paper primarily focuses on theoretical characterizations, our framework offers a robust mathematical foundation for interpreting model decoding dynamics. Future work will explore leveraging these martingale properties for trajectory-level uncertainty quantification, model identification, and adaptive decoding strategies. References Achiam et al. (2023) J. Achiam, S. Adler, S. Agarwal, L. Aflalo, et al. GPT-4 technical report. arXiv preprint arXiv:2303.08774. Cited by: Introduction. Azuma (1967) K. Azuma Weighted sums of certain dependent random variables. Tohoku Mathematical Journal 19 (3), p. 357–367. Cited by: Martingale Theory in Machine Learning.. Brier (1950) G. W. Brier Verification of forecasts expressed in terms of probability. Monthly weather review 78 (1), p. 1–3. Cited by: Analysis of Large Language Model Generation Dynamics.. Bubeck and Cesa-Bianchi (2012) S. Bubeck and N. Cesa-Bianchi Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, p. 1–122. Cited by: Martingale Theory in Machine Learning.. Desai and Durrett (2020) S. Desai and G. Durrett Calibration of pre-trained transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), p. 295–302. Cited by: Introduction. Doob (1953) J. L. Doob Stochastic processes. Wiley. Cited by: Martingale Theory in Machine Learning., Definition 1, Definition 3. Dugan et al. (2024) L. Dugan, A. Hwang, F. Trhlík, A. Zhu, J. M. Ludan, H. Xu, D. Ippolito, and C. Callison-Burch RAID: a shared benchmark for robust evaluation of machine-generated text detectors. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 12463–12492. Cited by: Relationship with Existing Uncertainty Measures. Fan et al. (2018) A. Fan, M. Lewis, and Y. Dauphin Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 889–898. Cited by: Analysis of Large Language Model Generation Dynamics.. Freedman (1975) D. A. Freedman On tail probabilities for martingales. The Annals of Probability, p. 100–118. Cited by: Martingale Theory in Machine Learning.. Gal and Ghahramani (2016) Y. Gal and Z. Ghahramani Dropout as a bayesian approximation: representing model uncertainty in deep learning. In International Conference on Machine Learning, p. 1050–1059. Cited by: Introduction. Garg et al. (2022) S. Garg, D. Tsipras, P. Liang, and G. Valiant What can transformers learn in-context? a case study of linear models. In Advances in Neural Information Processing Systems, Vol. 35, p. 30420–30433. Cited by: Theoretical Understanding of Neural Language Models.. Guo et al. (2017) C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger On calibration of modern neural networks. In International Conference on Machine Learning, p. 1321–1330. Cited by: Introduction, Analysis of Large Language Model Generation Dynamics.. Hoffmann et al. (2022) J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. d. L. Casas, L. A. Hendricks, J. Welbl, et al. Training compute-optimal large language models. In 36th Conference on Neural Information Processing Systems, NeurIPS 2022, Cited by: Theoretical Understanding of Neural Language Models.. Holtzman et al. (2020) A. Holtzman, J. Buys, L. Du, M. Forbes, and L. Zettlemoyer The curious case of neural text degeneration. In International Conference on Learning Representations, Cited by: Introduction, Analysis of Large Language Model Generation Dynamics.. Jiang et al. (2021) Z. Jiang, J. Araki, H. Ding, and G. Neubig How can we know when language models know? on the calibration of language models for question answering. MIT Press - Journals. Cited by: Analysis of Large Language Model Generation Dynamics.. Kadavath et al. (2022) S. Kadavath et al. Language models (mostly) know what they know. arXiv preprint arXiv:2207.05221. Cited by: Analysis of Large Language Model Generation Dynamics.. Kaplan et al. (2020) J. Kaplan, S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Radford, J. Wu, and D. Amodei Scaling laws for neural language models. arXiv preprint arXiv:2001.08361. Cited by: Theoretical Understanding of Neural Language Models.. Kuhn et al. (2023) L. Kuhn, Y. Gal, and S. Farquhar Semantic uncertainty: linguistic invariances for uncertainty estimation in natural language generation. In International Conference on Learning Representations, Cited by: Analysis of Large Language Model Generation Dynamics.. Lattimore and Szepesvári (2020) T. Lattimore and C. Szepesvári Bandit algorithms. Cambridge University Press. Cited by: Martingale Theory in Machine Learning.. Leviathan et al. (2023) Y. Leviathan, M. Kalman, and Y. Matias Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, p. 19274–19286. Cited by: Analysis of Large Language Model Generation Dynamics.. Li et al. (2023) X. L. Li, A. Holtzman, D. Fried, P. Liang, J. Eisner, T. Hashimoto, L. Zettlemoyer, and M. Lewis Contrastive decoding: open-ended text generation as optimization. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 12286–12312. Cited by: Analysis of Large Language Model Generation Dynamics.. Li et al. (2022) X. L. Li, J. Thickstun, I. Gulrajani, P. Liang, and T. Hashimoto Diffusion-lm improves controllable text generation. In Advances in Neural Information Processing Systems, Vol. 35, p. 4328–4343. Cited by: Stochastic Process Perspectives in Machine Learning.. Lin et al. (2022) S. Lin, J. Hilton, and O. Evans Teaching models to express their uncertainty in words. Transactions on Machine Learning Research. Cited by: Analysis of Large Language Model Generation Dynamics.. McDiarmid (1989) C. McDiarmid On the method of bounded differences. In Surveys in combinatorics 1989, p. 148–188. Cited by: Martingale Theory in Machine Learning.. Meister et al. (2020) C. Meister, R. Cotterell, and T. Vieira If beam search is the answer, what is the question?. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, p. 7953–7960. Cited by: Introduction, Analysis of Large Language Model Generation Dynamics.. Meister et al. (2022) C. Meister, T. Pimentel, G. Wiher, and R. Cotterell Typical decoding for natural language generation. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 3184–3203. Cited by: Analysis of Large Language Model Generation Dynamics.. Meng et al. (2022) K. Meng, D. Bau, A. Andonian, and Y. Belinkov Locating and editing factual associations in gpt. In Advances in Neural Information Processing Systems, Vol. 35, p. 17359–17372. Cited by: Theoretical Understanding of Neural Language Models.. Mitchell et al. (2023) E. Mitchell, Y. Lee, A. Khazatsky, C. D. Manning, and C. Finn DetectGPT: zero-shot machine-generated text detection using probability curvature. In International Conference on Machine Learning, p. 24950–24962. Cited by: Analysis of Large Language Model Generation Dynamics.. Olsson et al. (2022) C. Olsson, N. Elhage, N. Nanda, N. Joseph, N. DasSarma, T. Henighan, B. Liao, A. Askell, et al. In-context learning and induction heads. Transformer Circuits Thread. Cited by: Theoretical Understanding of Neural Language Models.. Ouyang et al. (2022) L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, Vol. 35, p. 27730–27744. Cited by: Theoretical Understanding of Neural Language Models.. Song et al. (2021) Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, Cited by: Stochastic Process Perspectives in Machine Learning.. Touvron et al. (2023) H. Touvron, T. Lavril, G. Izacard, X. Martinet, et al. Llama: open and efficient foundation language models. In International Conference on Machine Learning, Cited by: Introduction. Wang et al. (2023) K. Wang, A. Variengien, A. Conmy, B. Shlegeris, and J. Steinhardt Interpretability in the wild: a circuit for indirect object identification in gpt-2 small. In International Conference on Learning Representations, Cited by: Theoretical Understanding of Neural Language Models.. Wei et al. (2022) J. Wei, Y. Tay, R. Bommasani, C. Raffel, B. Zhai, M. Bendersky, S. Bowman, et al. Emergent abilities of large language models. Transactions on Machine Learning Research. Cited by: Theoretical Understanding of Neural Language Models.. Welleck et al. (2020) S. Welleck, I. Kulikov, S. Roller, E. Dinan, K. Cho, and J. Weston Neural text generation with unlikelihood training. In International Conference on Learning Representations, Cited by: Introduction. A Proof Theorem 2. The stochastic process tt≥1\ M_t\_t≥ 1 is a martingale with respect to the filtration F. Proof. We have yt[t∣y<t] _y_t[ M_t y_<t] (30) =yt[t−1∣y<t]+yt[t∣y<t] =E_y_t[ M_t-1 y_<t]+E_y_t[ e_t y_<t] =t−1+yt[t−t∣y<t] = M_t-1+E_y_t[ w_t- g_t y_<t] =t−1+yt[t∣y<t]−t = M_t-1+E_y_t[ w_t y_<t]- g_t =t−1+t−t = M_t-1+ g_t- g_t =t−1 = M_t-1 y≤t[‖t‖2]≤y≤t[∑i=1t‖i‖2]≤y≤t[∑i=1t(‖i‖2+‖i‖2)]≤[∑i=1t2]=2t<∞ gatheredE_y_≤ t[\| M_t\|_2] _y_≤ t [ _i=1^t\| e_i\|_2 ]≤\\ E_y_≤ t [ _i=1^t(\| w_i\|_2+\| g_i\|_2) ]≤ [ _i=1^t2 ]=2t<∞ gathered (31) t g_t and t w_t is decided given y≤ty_≤ t, and so is t e_t. Thus t M_t is adapted to filtration F. According to the definition, t M_t is a martingale. ∎ Theorem 3. The second-oreder moment of martingale Mtt≥1\M_t\_t≥ 1 can be expressed as follows: y≤t[‖t‖22]=y<t[∑i=1t(1−‖i‖22)]E_y_≤ t[\| M_t\|_2^2]=E_y_<t [ _i=1^t(1-\| g_i\|_2^2) ] (32) Proof. y≤t[‖t‖22]=y<t[yt[‖t‖22∣y<t]] \ E_y_≤ t[\| M_t\|_2^2]=E_y_<t[E_y_t[\| M_t\|_2^2 y_<t]] (33) yt[‖t‖22∣y<t]=yt[‖t+t−1‖22∣y<t]=yt[‖t‖22∣y<t]+yt[2t−1⋅t∣y<t]+yt[‖t−1‖22∣y<t]=yt[‖t‖22∣y<t]+2t−1⋅yt[t∣y<t]+‖t−1‖22=yt[‖t‖22∣y<t]+‖t−1‖22 aligned & \ E_y_t[\| M_t\|_2^2 y_<t]=E_y_t[\| e_t+ M_t-1\|_2^2 y_<t]\\ &=E_y_t[\| e_t\|_2^2 y_<t]+E_y_t[2 M_t-1· e_t y_<t]+\\ & \ E_y_t[\| M_t-1\|_2^2 y_<t]\\ &=E_y_t[\| e_t\|_2^2 y_<t]+2 M_t-1·E_y_t[ e_t y_<t]+\\ & \ \| M_t-1\|_2^2\\ &=E_y_t[\| e_t\|_2^2 y_<t]+\| M_t-1\|_2^2 aligned (34) yt[‖t‖22∣y<t]=yt[‖t−t‖22∣y<t]=yt[‖t‖22∣y<t]−yt[2t⋅t∣y<t]+yt[‖t‖22∣y<t]=1−2t⋅yt[t∣y<t]+‖t‖22=1−2t⋅t+‖t‖22=1−‖t‖22 aligned & \ E_y_t[\| e_t\|_2^2 y_<t]=E_y_t[\| w_t- g_t\|_2^2 y_<t]\\ &=E_y_t[\| w_t\|_2^2 y_<t]-E_y_t[2 g_t· w_t y_<t]+\\ & \ E_y_t[\| g_t\|_2^2 y_<t]\\ &=1-2 g_t·E_y_t[ w_t y_<t]+\| g_t\|_2^2\\ &=1-2 g_t· g_t+\| g_t\|_2^2\\ &=1-\| g_t\|_2^2 aligned (35) By combining equations (33), (34) and (35), we can get y≤t[‖t‖22]=y<t[1−‖t‖22+‖t−1‖22]=y<t[1−‖t‖22]+y≤t−1[‖t−1‖22] gatheredE_y_≤ t[\| M_t\|_2^2]=E_y_<t[1-\| g_t\|_2^2+\| M_t-1\|_2^2]=\\ E_y_<t[1-\| g_t\|_2^2]+E_y_≤ t-1[\| M_t-1\|_2^2] gathered (36) Then the following recurrence relation holds: y≤t[‖t‖22]−y≤t−1[‖t−1‖22]=y<t[1−‖t‖22]E_y_≤ t[\| M_t\|_2^2]-E_y_≤ t-1[\| M_t-1\|_2^2]=E_y_<t[1-\| g_t\|_2^2] (37) Thus y≤t[‖t‖22]−y≤1[‖1‖22] _y_≤ t[\| M_t\|_2^2]-E_y_≤ 1[\| M_1\|_2^2] (38) =y≤t[‖t‖22]−y1[‖1‖22∣y<1] =E_y_≤ t[\| M_t\|_2^2]-E_y_1[\| e_1\|_2^2 y_<1] =y≤t[‖t‖22]−(1−‖1‖22) =E_y_≤ t[\| M_t\|_2^2]-(1-\| g_1\|_2^2) =y<t[∑i=2t(1−‖i‖22)] =E_y_<t [ _i=2^t(1-\| g_i\|_2^2) ] So y≤t[‖t‖22]=y<t[∑i=1t(1−‖i‖22)]E_y_≤ t[\| M_t\|_2^2]=E_y_<t [ _i=1^t(1-\| g_i\|_2^2) ] (39) ∎ Theorem 4. The second order moment of martingale tt≥1\ M_t\_t≥ 1 with stopping time can be expressed as follows: y≤lmax[‖τ‖22]=y≤lmax[∑t=1τ(1−‖t‖22)]E_y_≤ l_max[\| M_τ\|_2^2]=E_y_≤ l_max [ _t=1^τ(1-\| g_t\|_2^2) ] (40) Proof. ylmax[‖τ‖22∣y<lmax] _y_l_max[\| M_τ\|_2^2 y_<l_max] =ylmax[∑t=1lmaxτ=t∥t∥22∣y<lmax] =E_y_l_max [ _t=1^l_maxI_\τ=t\\| M_t\|_2^2 y_<l_max ] =ylmax[τ=lmax∥lmax∥22∣y<lmax]+ =E_y_l_max[I_\τ=l_max\\| M_l_max\|_2^2 y_<l_max]+ ∑t=1lmax−1τ=t∥t∥22 _t=1^l_max-1I_\τ=t\\| M_t\|_2^2 =τ=lmaxylmax[∥lmax∥22∣y<lmax]+∑t=1lmax−1τ=t∥t∥22 gathered=I_\τ=l_max\E_y_l_max[\| M_l_max\|_2^2 y_<l_max]+\\ _t=1^l_max-1I_\τ=t\\| M_t\|_2^2 gathered =τ=lmax(1−∥lmax∥22+∥lmax−1∥22)+ =I_\τ=l_max\(1-\| g_l_max\|_2^2+\| M_l_max-1\|_2^2)+ ∑t=1lmax−1τ=t∥t∥22 _t=1^l_max-1I_\τ=t\\| M_t\|_2^2 =τ=lmax(1−∥lmax∥22)+ =I_\τ=l_max\(1-\| g_l_max\|_2^2)+ τ≥lmax−1∥lmax−1∥22+∑t=1lmax−2τ=t∥t∥22 _\τ≥ l_max-1\\| M_l_max-1\|_2^2+ _t=1^l_max-2I_\τ=t\\| M_t\|_2^2 Taking conditional expectation on both sides with respect to y<lmax−1y_<l_max-1: ylmax−1ylmax[‖τ‖22∣y<lmax−1]=ylmax−1[ylmax[‖τ‖22∣y<lmax]∣y<lmax−1]=ylmax−1[τ=lmax(1−∥lmax∥22)∣y<lmax−1]+τ≥lmax−1ylmax−1[∥lmax−1∥22∣y<lmax−1]+∑t=1lmax−2τ=t∥t∥22=ylmax−1[τ=lmax(1−∥lmax∥22)∣y<lmax−1]+τ≥lmax−1(1−∥lmax−1∥22+∥lmax−2∥22)+∑t=1lmax−2τ=t∥t∥22=ylmax−1[τ≥lmax(1−∥lmax∥22)∣y<lmax−1]+τ≥lmax−1(1−∥lmax−1∥22)+τ≥lmax−2∥lmax−2∥22+∑t=1lmax−3τ=t∥t∥22 gatheredE_y_l_max-1y_l_max[\| M_τ\|_2^2 y_<l_max-1]\\ =E_y_l_max-1[E_y_l_max[\| M_τ\|_2^2 y_<l_max] y_<l_max-1]\\ =E_y_l_max-1[I_\τ=l_max\(1-\| g_l_max\|_2^2) y_<l_max-1]+\\ I_\τ≥ l_max-1\E_y_l_max-1[\| M_l_max-1\|_2^2 y_<l_max-1]+\\ _t=1^l_max-2I_\τ=t\\| M_t\|_2^2\\ =E_y_l_max-1[I_\τ=l_max\(1-\| g_l_max\|_2^2) y_<l_max-1]+\\ I_\τ≥ l_max-1\(1-\| g_l_max-1\|_2^2+\| M_l_max-2\|_2^2)+\\ _t=1^l_max-2I_\τ=t\\| M_t\|_2^2\\ =E_y_l_max-1[I_\τ≥ l_max\(1-\| g_l_max\|_2^2) y_<l_max-1]+\\ I_\τ≥ l_max-1\(1-\| g_l_max-1\|_2^2)+\\ I_\τ≥ l_max-2\\| M_l_max-2\|_2^2+ _t=1^l_max-3I_\τ=t\\| M_t\|_2^2 gathered (43) Then, taking conditional expectations successively with respect to y<i(i=lmax−2,⋯,1)y_<i\ (i=l_max-2,·s,1), we have y≤lmax[‖τ‖22] _y_≤ l_max[\| M_τ\|_2^2] (44) =y≤lmax[∑t=1lmaxτ≥t(1−∥t∥22)] =E_y_≤ l_max [ _t=1^l_maxI_\τ≥ t\(1-\| g_t\|_2^2) ] =y≤lmax[∑t=1τ(1−‖t‖22)] =E_y_≤ l_max [ _t=1^τ(1-\| g_t\|_2^2) ] ∎ Theorem 5. The second-oreder moment of martingale Mtt≥1\M_t\_t≥ 1 can be expressed as follows: y≤t[‖t‖22]=y≤t[∑i=1t(1−p(yi∣y<i))]E_y_≤ t[\| M_t\|_2^2]=E_y_≤ t [ _i=1^t(1-p(y_i y_<i)) ] (45) Proof. y≤t[‖t‖22] \ E_y_≤ t[\| M_t\|_2^2] =y<t[∑i=1t(1−‖i‖22)] =E_y_<t [ _i=1^t(1-\| g_i\|_2^2) ] =∑i=1ty<t[1−‖i‖22] = _i=1^tE_y_<t[1-\| g_i\|_2^2] =∑i=1ty<i[1−‖i‖22] = _i=1^tE_y_<i[1-\| g_i\|_2^2] =∑i=1t∑y<i∈i−1p(y<i)(1−‖i‖22) = _i=1^t _y_<i ^i-1p(y_<i)(1-\| g_i\|_2^2) =∑i=1t∑y<i∈i−1p(y<i)(1−∑yi∈p2(yi∣y<i)) = _i=1^t _y_<i ^i-1p(y_<i)(1- _y_i p^2(y_i y_<i)) =∑i=1t∑y<i∈i−1(p(y<i)−∑yi∈p(y<i)p2(yi∣y<i)) = _i=1^t _y_<i ^i-1(p(y_<i)- _y_i p(y_<i)p^2(y_i y_<i)) (46) =∑i=1t∑y<i∈i−1(p(y<i)−∑yi∈p(y≤i)p(yi∣y<i)) = _i=1^t _y_<i ^i-1(p(y_<i)- _y_i p(y_≤ i)p(y_i y_<i)) =∑i=1t∑y≤i∈ip(y≤i)(1−p(yi∣y<i)) = _i=1^t _y_≤ i ^ip(y_≤ i)(1-p(y_i y_<i)) =∑i=1ty≤i[1−p(yi∣y<i)] = _i=1^tE_y_≤ i[1-p(y_i y_<i)] =∑i=1ty≤t[1−p(yi∣y<i)] = _i=1^tE_y_≤ t[1-p(y_i y_<i)] =y≤t[∑i=1t(1−p(yi∣y<i))] =E_y_≤ t [ _i=1^t(1-p(y_i y_<i)) ] ∎ Theorem 6. The second order moment of martingale tt≥1\ M_t\_t≥ 1 with stopping time can be expressed as follows: y≤lmax[‖τ‖22]=y≤lmax[∑t=1τ(1−p(yt∣y<t))]E_y_≤ l_max[\| M_τ\|_2^2]=E_y_≤ l_max [ _t=1^τ(1-p(y_t y_<t)) ] (47) Proof. y≤lmax[∥τ∥22]=y≤lmax[∑t=1lmaxτ≥t(1−∥t∥22)] \ E_y_≤ l_max[\| M_τ\|_2^2]=E_y_≤ l_max [ _t=1^l_maxI_\τ≥ t\(1-\| g_t\|_2^2) ] =∑t=1lmaxy≤lmax[τ≥t(1−∥t∥22)] = _t=1^l_maxE_y_≤ l_max[I_\τ≥ t\(1-\| g_t\|_2^2)] =∑t=1lmaxy<t[τ≥t(1−∥t∥22)] = _t=1^l_maxE_y_<t[I_\τ≥ t\(1-\| g_t\|_2^2)] =∑t=1lmax∑y<t∈t−1p(y<t)τ≥t(1−∑yt∈p2(yt∣y<t)) = _t=1^l_max _y_<t ^t-1p(y_<t)I_\τ≥ t\(1- _y_t p^2(y_t y_<t)) =∑t=1lmax∑y<t∈t−1τ≥t(p(y<t)−∑yt∈p(y<t)p2(yt∣y<t)) = _t=1^l_max _y_<t ^t-1I_\τ≥ t\(p(y_<t)- _y_t p(y_<t)p^2(y_t y_<t)) =∑t=1lmax∑y<t∈t−1τ≥t(p(y<t)−∑yt∈p(y≤t)p(yt∣y<t)) = _t=1^l_max _y_<t ^t-1I_\τ≥ t\(p(y_<t)- _y_t p(y_≤ t)p(y_t y_<t)) =∑t=1lmax∑y≤t∈tp(y≤t)τ≥t(1−p(yt∣y<t)) = _t=1^l_max _y_≤ t ^tp(y_≤ t)I_\τ≥ t\(1-p(y_t y_<t)) (48) =∑t=1lmaxy≤t[τ≥t(1−p(yt∣y<t))] = _t=1^l_maxE_y_≤ t[I_\τ≥ t\(1-p(y_t y_<t))] =∑t=1lmaxy≤lmax[τ≥t(1−p(yt∣y<t))] = _t=1^l_maxE_y_≤ l_max[I_\τ≥ t\(1-p(y_t y_<t))] =y≤lmax[∑t=1lmaxτ≥t(1−p(yt∣y<t))] =E_y_≤ l_max [ _t=1^l_maxI_\τ≥ t\(1-p(y_t y_<t)) ] =y≤lmax[∑t=1τ(1−p(yt∣y<t))] =E_y_≤ l_max [ _t=1^τ(1-p(y_t y_<t)) ] ∎ Theorem 7. The second-oreder moment of martingale (with stopping time) can be expressed as follows: y≤t[‖t‖22]=y≤t[∑i=1ti2] _y_≤ t[\| M_t\|_2^2]=E_y_≤ t [ _i=1^t e_i^2 ] (49) y≤lmax[‖τ‖22]=y≤lmax[∑t=1τt2] _y_≤ l_max[\| M_τ\|_2^2]=E_y_≤ l_max [ _t=1^τ e_t^2 ] (50) Proof. y≤lmax[i2]=y≤i[i2] _y_≤ l_max[ e_i^2]=E_y_≤ i[ e_i^2] (51) =y≤i[(i−i)2] =E_y_≤ i[( w_i- g_i)^2] =y≤i[i2−2i⋅i+i2] =E_y_≤ i[ w_i^2-2 w_i· g_i+ g_i^2] =y≤i[i2]−2y≤i[i⋅i]+y≤i[i2] =E_y_≤ i[ w_i^2]-2E_y_≤ i[ w_i· g_i]+E_y_≤ i[ g_i^2] =1−2y<i[yi[i⋅i∣y<i]]+y<i[i2] =1-2E_y_<i[E_y_i[ w_i· g_i y_<i]]+E_y_<i[ g_i^2] =1−2y<i[i2]+y<i[i2] =1-2E_y_<i[ g_i^2]+E_y_<i[ g_i^2] =y<i[1−i2] =E_y_<i[1- g_i^2] y≤lmax[τ≥tt2]=y≤t[τ≥tt2] _y_≤ l_max[I_\τ≥ t\ e_t^2]=E_y_≤ t[I_\τ≥ t\ e_t^2] (52) =y≤t[τ≥t(t−t)2] =E_y_≤ t[I_\τ≥ t\( w_t- g_t)^2] =y≤t[τ≥t(t2−2t⋅t+t2)] =E_y_≤ t[I_\τ≥ t\( w_t^2-2 w_t· g_t+ g_t^2)] =y<t[yt[τ≥t(1−2t⋅t+t2)∣y<t]] =E_y_<t[E_y_t[I_\τ≥ t\(1-2 w_t· g_t+ g_t^2) y_<t]] =y<t[τ≥tyt[1−2t⋅t+t2∣y<t]] =E_y_<t[I_\τ≥ t\E_y_t[1-2 w_t· g_t+ g_t^2 y_<t]] =y<t[τ≥t(1−t2)] =E_y_<t[I_\τ≥ t\(1- g_t^2)] By combining equations (51) and (52) with equations (32) and (40), respectively, we obtain equations (49) and (50). ∎ Theorem 8. For the second order moments y≤t[‖t‖22]E_y_≤ t[\| M_t\|_2^2] and y≤lmax[‖T‖22]E_y_≤ l_max[\| M_T\|_2^2], the following relation holds: ∑i=1tVar(i)=y≤t[‖t‖22]+∑i=1tVar(i) _i=1^tVar( w_i)=E_y_≤ t[\| M_t\|_2^2]+ _i=1^tVar( g_i) (53) y≤lmax[∑t=1τVar(t)]=y≤lmax[‖τ‖22]+y≤lmax[∑t=1τVar(t)] gatheredE_y_≤ l_max [ _t=1^τVar( w_t) ]\\ =E_y_≤ l_max[\| M_τ\|_2^2]+E_y_≤ l_max [ _t=1^τVar( g_t) ] gathered Then ∑i=1tVar(i)≥y≤t[‖t‖22] _i=1^tVar( w_i) _y_≤ t[\| M_t\|_2^2] (56) y≤lmax[∑t=1τVar(t)]≥y≤lmax[‖τ‖22] _y_≤ l_max [ _t=1^τVar( w_t) ] _y_≤ l_max[\| M_τ\|_2^2] (57) Proof. By the law of total variance, we have Var(i) ( w_i) (58) =y<i[Var(i∣y<i)]+Var(yi[i∣y<i]) =E_y_<i[Var( w_i y_<i)]+Var(E_y_i[ w_i y_<i]) =y<i[yi[(i−yi[i∣y<i])2∣y<i]]+ =E_y_<i[E_y_i[( w_i-E_y_i[ w_i y_<i])^2 y_<i]]+ Var(yi[i∣y<i]) (E_y_i[ w_i y_<i]) =y<i[yi[(i−i)2∣y<i]]+Var(i) =E_y_<i[E_y_i[( w_i- g_i)^2 y_<i]]+Var( g_i) =y≤i[i2]+Var(i) =E_y_≤ i[ e_i^2]+Var( g_i) Var(τ≥tt)=y<t[Var(τ≥tt∣y<t)]+ \ Var(I_\τ≥ t\ w_t)=E_y_<t[Var(I_\τ≥ t\ w_t y_<t)]+ Var(yt[τ≥tt∣y<t]) \ Var(E_y_t[I_\τ≥ t\ w_t y_<t]) =y<t[yt[(τ≥tt−yt[τ≥tt∣y<t])2∣y<t]]+ =E_y_<t[E_y_t[(I_\τ≥ t\ w_t-E_y_t[I_\τ≥ t\ w_t y_<t])^2 y_<t]]+ Var(yt[τ≥tt∣y<t]) \ Var(E_y_t[I_\τ≥ t\ w_t y_<t]) (59) =y<t[yt[(τ≥tt−τ≥tyt[t∣y<t])2∣y<t]]+ =E_y_<t[E_y_t[(I_\τ≥ t\ w_t-I_\τ≥ t\E_y_t[ w_t y_<t])^2 y_<t]]+ Var(τ≥tyt[t∣y<t]) \ Var(I_\τ≥ t\E_y_t[ w_t y_<t]) =y<t[yt[τ≥t(t−t)2∣y<t]]+Var(τ≥tt) =E_y_<t[E_y_t[I_\τ≥ t\( w_t- g_t)^2 y_<t]]+Var(I_\τ≥ t\ g_t) =y≤t[τ≥tt2]+Var(τ≥tt) =E_y_≤ t[I_\τ≥ t\ e_t^2]+Var(I_\τ≥ t\ g_t) Combining equations (58) and (59) with equations (49) and (50), respectively, yields equations (53) and (8). Noting that ∑i=1tVar(i)≥0 _i=1^tVar( g_i)≥ 0 (60) y≤lmax[∑t=1τVar(t)]≥0 _y_≤ l_max [ _t=1^τVar( g_t) ]≥ 0 (61) from equations (53) and (8) we obtain equations (56) and (57). ∎ Theorem 9. The following equivalences hold: ∑i=1tVar(i)=0⇔y≤t[‖t‖22]=0 _i=1^tVar( w_i)=0 _y_≤ t[\| M_t\|_2^2]=0 (62) y≤lmax[∑t=1τVar(t)]=0⇔y≤lmax[‖τ‖22]=0 gatheredE_y_≤ l_max [ _t=1^τVar( w_t) ]=0 \\ E_y_≤ l_max[\| M_τ\|_2^2]=0 gathered Proof. From equations (56) and (57), the left-to-right implications of equations (62) and (9) are obvious. We first consider the right-to-left implication of equation (62). From equation (49), y≤t[‖t‖22]=0E_y_≤ t[\| M_t\|_2^2]=0 is equivalent to ∀1≤i≤t:y≤t[i2]=0∀ 1≤ i≤ t:E_y_≤ t[ e_i^2]=0. This implies that ∀1≤i≤t:(i=ia.e.)∀ 1≤ i≤ t:( w_i= g_i\ a.e.), meaning that for output sequence y1y2…,yty_1y_2…,y_t with nonzero probability, i g_i is a one-hot vector. That is, there is only one output sequence with probability 1, and all other output sequence have probability 0. This means that the output at each token is fixed, and ∑i=1tVar(i)=0 _i=1^tVar( w_i)=0. For equation (9), we consider those t with P(τ=t)>0P(τ=t)>0; the rest of the proof is similar to that of equation (62). ∎ Theorem 10. The following equivalences hold: ∑i=1tVar(i)=t(1−1||)⇔∀1≤i≤t:y<i[i]=1|| gathered _i=1^tVar( w_i)=t(1- 1|V|) \\ ∀ 1≤ i≤ t:E_y_<i[ g_i]= 1|V|1\\ gathered y≤t[‖t‖22]=t(1−1||)⇔∀1≤i≤t:(i=1||a.e.) gatheredE_y_≤ t[\| M_t\|_2^2]=t(1- 1|V|) \\ ∀ 1≤ i≤ t:( g_i= 1|V|1\ a.e.) gathered where 1 is the all-one vector. The following implication hold: y≤t[‖t‖22]=t(1−1||)⇒∑i=1tVar(i)=t(1−1||) gatheredE_y_≤ t[\| M_t\|_2^2]=t(1- 1|V|) \\ _i=1^tVar( w_i)=t(1- 1|V|) gathered (70) Proof. ∑i=1tVar(i) _i=1^tVar( w_i) (71) =∑i=1t(y≤i[i2]−y≤i2[i]) = _i=1^t(E_y_≤ i[ w_i^2]-E_y_≤ i^2[ w_i]) =∑i=1t(1−(y<i[yi[i∣y<i]])2) = _i=1^t(1-(E_y_<i[E_y_i[ w_i y_<i]])^2) =∑i=1t(1−y<i2[i]) = _i=1^t(1-E_y_<i^2[ g_i]) ≤∑i=1t(1−1||)=t(1−1||) ≤ _i=1^t(1- 1|V|)=t(1- 1|V|) Equality holds in equation (71) if and only if ∀1≤i≤t:y<i[i]=1||∀ 1≤ i≤ t:E_y_<i[ g_i]= 1|V|1. Considering equation (32), we have y≤t[‖t‖22] \ E_y_≤ t[\| M_t\|_2^2] =y<t[∑i=1t(1−‖i‖22)] =E_y_<t [ _i=1^t(1-\| g_i\|_2^2) ] =∑i=1t(1−y<t[‖i‖22]) = _i=1^t(1-E_y_<t[\| g_i\|_2^2]) (72) =∑i=1t(1−y<i[‖i‖22]) = _i=1^t(1-E_y_<i[\| g_i\|_2^2]) ≤∑i=1t(1−1||) ≤ _i=1^t(1- 1|V|) =t(1−1||) =t(1- 1|V|) Equality holds in equation (72) if and only if ∀1≤i≤t:y<i[‖i‖22]=1||∀ 1≤ i≤ t:E_y_<i[\| g_i\|_2^2]= 1|V|, i.e., ∀1≤i≤t:(i=1||a.e.)∀ 1≤ i≤ t:( g_i= 1|V|1\ a.e.). Since ∀1≤i≤t:(i=1||a.e.)⇒∀1≤i≤t:y<i[i]=1||∀ 1≤ i≤ t:( g_i= 1|V|1\ a.e.) ∀ 1≤ i≤ t:E_y_<i[ g_i]= 1|V|1, equation (70) holds. ∎