Introduction
In the era of Large Language Models (LLMs), we often treat the sequence of tokens generated by a GPT-style model as a valid probability distribution over text. However, from a formal language theory perspective, a true "language model" must define a distribution over the set of all finite strings, $\Sigma^*$. Modern autoregressive models are technically "language processes"—stochastic processes that generate tokens one by one. This paper addresses a critical theoretical gap: under what conditions does a language process actually define a valid, "tight" language model?
The Problem of Non-Tightness
A language model is considered "tight" if the sum of probabilities for all possible finite strings equals exactly 1. If a model is non-tight, it "leaks" probability mass into infinite sequences. This is not merely a theoretical nuisance; non-tightness has practical consequences:
- Decoding Failures: It can lead to "infinite loops" during greedy or beam search decoding.
- Biased Evaluation: It can bias evaluation metrics that assume a proper distribution.
- Sampling Issues: It can break Monte Carlo samplers that rely on the process eventually terminating.
The authors seek a precise mathematical characterization of when a process is guaranteed to stop with probability 1.
A Measure-Theoretic Approach
To solve this, the paper shifts the perspective from simple string distributions to measure-theoretic probability. The framework relies on three pillars:
- Kolmogorov Extension Theorem: The authors use this classic theorem to prove that a language process (defined by conditional probabilities $p(x_t | x_{<t})$) exists as a unique probability measure over infinite sequences.
- Stopping Times: They define the appearance of the end-of-string (EOS) symbol as a "stopping time" ($\tau_{EOS}$). This allows them to use the machinery of stochastic processes to analyze the behavior of the model at the exact moment it decides to finish a string.
- Filtrations: They introduce filtrations—a sequence of $\sigma$-algebras representing the information revealed as a string is generated. This connects the "local" probability of an EOS token at step $t$ to the "global" property of tightness.
The Core Theorem: Tightness via Martingales
The central contribution of the paper is the application of the Lévy–Borel–Cantelli Theorem, a generalization of the Borel-Cantelli lemmas. This leads to Theorem 3.4, which states that for any filtration, a language process is tight if and only if:
$$\sum_{t=1}^{\infty} P(A_t | \mathcal{G}_{t-1}) = \infty \text{ (almost surely)}$$
where $A_t$ is the event that the process has stopped by time $t$. In plain language, a language process is tight if and only if the sum of the conditional probabilities of generating an EOS token (given the history) diverges to infinity. If the model "tries hard enough" to stop over time, it eventually will.
Practical Implications and Examples
The authors provide concrete examples to illustrate how this condition manifests in model design:
- Guaranteed Tightness: If the probability of an EOS token is always bounded below by some function $f(t)$ such that $\sum f(t) = \infty$, the model is guaranteed to be tight.
- Non-Tightness Example: If the probability of EOS at step $t$ decays too quickly—for example, $p(EOS|x) \le 2^{-(t+1)}$—the sum converges. This means there is a positive probability that the string never ends, making the process non-tight.
By framing tightness as a martingale property, the authors are able to re-derive and simplify several existing tightness conditions from previous literature, showing that their theorem serves as a general case for earlier, more restrictive results.
Limitations and Future Work
While the framework provides a rigorous foundation for autoregressive models, it has limitations:
- Model Scope: The current construction focuses on autoregressive models. While Probabilistic Context-Free Grammars (PCFGs) also face tightness issues, the Kolmogorov Extension Theorem as applied here does not directly account for the branching structures of PCFGs.
- Computational Complexity: Some derived conditions involve partition functions that are often intractable to compute for complex modern architectures like large Transformers.
Future work may extend these martingale-based proofs to other generative processes, potentially providing a unified theory of tightness for all structured prediction models.
Summary updated