When is a Language Process a Language Model?

Li Du, Holden Lee, Jason Eisner, Ryan CotterellACL 2024 · OpenReview

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:

  1. 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.
  2. 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.
  3. 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

Abstract

A language model may be viewed as a 𝛴-valued stochastic process for some alphabet 𝛴.However, in some pathological situations, such a stochastic process may “leak” probability mass onto the set of infinite strings and hence is not equivalent to the conventional view of a language model as a distribution over ordinary (finite) strings.Such ill-behaved language processes are referred to as *non-tight* in the literature.In this work, we study conditions of tightness through the lens of stochastic processes.In particular, by regarding the symbol as marking a stopping time and using results from martingale theory, we give characterizations of tightness that generalize our previous work [(Du et al. 2023)](https://arxiv.org/abs/2212.10502).
BibTeX
@inproceedings{du2024when,
  author = {Li Du and Holden Lee and Jason Eisner and Ryan Cotterell},
  title = {{When is a Language Process a Language Model?}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2024},
  url = {https://openreview.net/forum?id=rmyvCKodNN},
}
Figure