When is a Language Process a Language Model? (2024)

Abstract: A language model may be viewed as a \Sigma -valued stochastic process for some alphabet \Sigma .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).

## introduction mathematically, there are two views of language models. from a formal language perspective, a language model is viewed as a distribution over σ * , the set of (finite-length) strings over a finite alphabet σ @xcite . from a probabilistic perspective, a language model is viewed as a discrete stochastic process {x @xmath0: @xmath1. under the latter view, to signal the end of the string, it is common to augment the alphabet with a special end-of-string symbol, eos, and define the x t to be σ-valued random variables where σ = σ ∪ {eos}. although x t is defined for all @xmath2, the random string consists only of the symbols x t preceding the first eos. we call such a stochastic process a language process, following @xcite . while the literature rarely distinguishes between the two views, there is an important difference: the probability mass of a language process can "leak" onto the set of infinite strings, meaning @xmath3. 1 when such leakage happens, the language process is said to be non-tight @xcite 1 a string has finite length by definition @xcite , so an "infinite string" is really a sequence, not a string. @xcite and cannot be regarded as a language model (i.e., a distribution over σ * ). non-tightness may cause language processes to generate infinite sequences @xcite and bias monte carlo samplers over strings @xcite . this phenomenon raises a natural question: how can we mathematically determine whether a language process is a language model? as demonstrated by several examples in @xcite , a precise answer to this question requires some probability theory @xcite . to this end, @xcite formalize language processes (which they call "sequence models") as extensions of pre-measures, and then obtain characterizations of tightness using the borel-cantelli lemmas. in this work, we revisit the problem of characterizing tightness through the lens of stochastic processes, an intuitive, high-level construct in measure-theoretic probability. we begin by presenting language processes using the kolmogorov extension theorem ( §2), which establishes their existence more simply and directly than the construction of @xcite . we then formulate eos as a stopping time, yielding a natural understanding of eos that connects the tightness property to martingales ( §3.1). 2 applying results from martingale theory, we are able to characterize tightness more generally than in previous work ( §3.2). ## language models as stochastic processes in probability theory, a stochastic process is a collection of random variables {x t : @xmath4, f , p ) over some index set t . 3 language models are often framed in terms of stochastic processes, usually implicitly through the notation x t to refer to the t th word. we first make this intuitive notation rigorous by formulating x t as a random variable over a certain probability space, which we must construct. previous papers simply assume the existence of such a probability space, occasionally explicitly @xcite . it is popular to specify a language model in terms of a parametric family of autoregressive conditional probabilities {p(x t | @xmath5: x @xmath6, @xmath7. however, we need to show that the stochastic process {x t : @xmath8, there is a distribution over infinite sequences in σ ∞ that has the given conditional probabilities. we will use the canonical tool for this, the kolmogorov extension theorem. the theorem states that a collection of distributions over finite subsets of the variables x t can be extended to a joint distribution over all of the infinitely many variables x t , provided that the distributions in the collection agree on the variables where they overlap (a consistency condition). as is the case for many fundamental theorems, the kolmogorov extension theorem has many variants. most probability texts @xcite @xcite only state and prove the theorem for r-valued stochastic processes, whereas we are interested in constructing a σvalued stochastic process. for completeness and rigor, we state a discrete version of the theorem below and provide a proof. ## characterizing tightness having established the existence of a language process with given autoregressive conditional probabilities, we can readily apply tools from the theory of stochastic processes. we will see that two key subjects of our investigation, eos termination and tightness, are naturally characterized by stopping times. stopping times are central to the study of stochastic processes @xcite . 6 this connection will allow us to derive tightness conditions that generalize @xcite . ## conclusions this paper presents a formal treatment of language model and its tightness using the theory of stochastic processes. we discuss the formalization of language model as a stochastic process by applying a discrete version of the kolmogorov extension theorem. we then give a more intuitive formal understanding of eos by characterizing it as a stopping time, a key construct in stochastic processes. finally, the stopping formulation allows us to connect tightness to martingale theory and obtain more general conditions on tightness.