A Measure-Theoretic Characterization of Tight Language Models

Li Du, Lucas Torroba Hennigen, Tiago Pimentel, Clara Meister, Jason Eisner, Ryan Cotterell

TL;DR

This paper provides a rigorous measure-theoretic framework to define "tightness" in language models—the property that a model assigns a total probability of 1 to finite strings rather than "leaking" mass to infinite sequences. The authors prove that modern Transformer architectures are inherently tight, while Recurrent Neural Networks (RNNs) are tight as long as their hidden state growth is sufficiently constrained.

What Problem Does This Paper Address?

In natural language processing, we typically define a language model as a probability distribution over a set of finite strings. However, autoregressive models generate text one token at a time. If a model’s probability of producing the end-of-sequence (EOS) token decays too quickly as the sequence grows, the generative process might never terminate.

When this happens, the model is said to be non-tight (or inconsistent). Probability mass "leaks" onto the set of infinite sequences. This isn't just a theoretical nuisance; non-tight models can break MCMC sampling algorithms and fail to represent valid probability distributions over the languages we actually use. While previous work noted this issue in specific models, this paper seeks a universal, mathematically rigorous way to characterize and prove tightness across different neural architectures.

Methods

The authors turn to measure theory to handle the fact that the set of all infinite sequences is uncountably infinite.

  1. Formal Space: They define a probability space over the union of finite strings ($\Sigma^*$) and infinite sequences ($\Sigma^\infty$).
  2. Carathéodory’s Extension Theorem: They use this classic mathematical tool to construct a unique probability measure for sequence models based on their conditional prefix probabilities.
  3. Tightness Criteria: They link tightness to the Borel–Cantelli lemmata. Specifically, they show that a model is tight if and only if the sum of the conditional probabilities of generating an EOS token (given that it hasn't been generated yet) diverges to infinity.
  4. Architectural Analysis: They apply these tools to analyze Stochastic Finite-State Sequence Models (SFSSMs), Transformers, and RNNs, using topological properties (like compactness and continuity) to prove tightness.

Datasets

As a theoretical paper, it does not use standard NLP training datasets like WikiText or Common Crawl. Instead, it uses synthetic motivating examples to demonstrate edge cases:

  • Non-tight bigram models: Simple finite-state machines where certain states can never reach the EOS token.
  • RNNs with ReLU activations: Specifically constructed to show how unbounded activations can lead to non-tightness if the hidden state grows too fast.

Key Insights and Ideas

  • EOS Probability Decay: Simply having a non-zero probability of EOS at every step isn't enough to guarantee tightness. If the probability of EOS decays too rapidly (e.g., like $1/e^t$), the model can still be non-tight. Conversely, a slower decay (like $1/t$) can still result in a tight model.
  • Transformers are Inherently Safe: The authors prove that any fixed-depth Transformer using softmax is tight. Because the Transformer operates on a finite vocabulary and uses continuous functions over compact sets, the EOS probability is always bounded below by some $\epsilon > 0$, ensuring the model eventually terminates.
  • The RNN Growth Limit: Unlike Transformers, RNNs have a depth that grows with the sequence length. The authors find a "speed limit" for RNNs: if the hidden state norm grows sub-logarithmically relative to the sequence length, the model remains tight.
  • Visualizing Leakage: Figure 1 illustrates how a simple change in transition probabilities can turn a valid language model into one that "leaks" mass.
Comparison of tight and non-tight bigram models. In (a), the model can enter a loop in state 'b' where it never sees an EOS, leading to non-tightness. In (b), every state has a path to EOS.

Key Results

  • SFSSMs (n-grams): An SFSSM is tight if and only if every state reachable from the start can also reach the EOS state. The authors provide a linear algebra formula using matrix inversion to calculate the exact termination probability.
  • Transformers: Proved to be tight regardless of parameter settings, provided they use standard softmax and continuous activations.
  • RNNs: Proved that RNNs with bounded activations (like tanh or sigmoid) are always tight. For unbounded activations like ReLU, they provided a sufficient condition for tightness: $k\|h_t\|_2 \le \log t$ for large $t$.

Limitations and Future Work

  • Computability: The paper does not address whether these measures are "computable" in the sense of theoretical computer science, leaving this for future work.
  • Sparse Distributions: The proofs for Transformers and RNNs rely on the strictly positive nature of the softmax function. The results do not necessarily apply to models using sparse alternatives like sparsemax, where the probability of EOS could be exactly zero for long sequences.
  • Non-Autoregressive Models: The formalism is strictly focused on autoregressive production and might not easily translate to other frameworks like Probabilistic Context-Free Grammars (PCFGs) without further modification.

Summary updated

Abstract

Language modeling, a central task in natural language processing, involves estimating a probability distribution over strings. In most cases, the estimated distribution sums to 1 over all finite strings. However, in some pathological cases, probability mass can ``leak'' onto the set of infinite sequences. In order to characterize the notion of leakage more precisely, this paper offers a measure-theoretic treatment of language modeling. We prove that many popular language model families are in fact tight, meaning that they will not leak in this sense. We also generalize characterizations of tightness proposed in previous works.
BibTeX
@inproceedings{du2023measure,
  author = {Li Du and Lucas Torroba Hennigen and Tiago Pimentel and Clara Meister and Jason Eisner and Ryan Cotterell},
  title = {{A Measure-Theoretic Characterization of Tight Language Models}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2023},
  doi = {10.18653/v1/2023.acl-long.543},
}
Figure