Consistent Bidirectional Language Modelling: Expressive Power and Representational Conciseness (2024)

Abstract: The inability to utilise future contexts and the pre-determined left-to-right generation order are major limitations of unidirectional language models. Bidirectionality has been introduced to address those deficiencies. However, a crucial shortcoming of bidirectional language models is the potential inconsistency of their conditional distributions. This fundamental flaw greatly diminishes their applicability and hinders their capability of tractable sampling and likelihood computation. In this work, we introduce a class of bidirectional language models, called latent language models, that are consistent by definition and can be efficiently used both for generation and scoring of sequences. We define latent language models based on the well-understood formalism of bisequential decompositions from automata theory. This formal correspondence allows us to precisely charaterise the abilities and limitations of a subclass of latent language models, called rational language models. As a result, we obtain that latent language models are exponentially more concise and significantly more expressive than unidirectional language models.

## introduction recently, language models @xcite @xcite have established themselves as the primary approach for solving natural language processing tasks @xcite @xcite . they have also exhibited noteworthy capabilities in computer programming @xcite and commonsense and mathematical reasoning @xcite . language models are traditionally differentiated based on the contextual conditioning that they use for token prediction. unidirectional (or autoregressive) language models, such as those based on recurrent neural networks (rnns) @xcite as well as the transformer-based gpt models @xcite , condition the prediction of a given token only on its left context. on the other hand, bidirectional (or masked) language models, such as those based on bidirectional rnns @xcite as well as the transformer-based bert @xcite and t5 @xcite , predict tokens based on both their left and right contexts. naturally, because of the access to richer contextual information, bidirectional language models have proven to produce stronger learned representations @xcite . in this regard, @xcite speculate that the inability of gpt-3 to benefit from future contexts could explain its inferior performance on certain tasks where bidirectionality is important. additionally, several studies have brought attention to the importance of the order in which sequences are processed @xcite . to this end, both empirical @xcite and theoretical @xcite results have implied that, as opposed to bidirectional language models, the pre-determined left-to-right order used by unidirectional language models is often suboptimal for tasks that require exploration, planning or strategic lookahead @xcite . despite of the aforementioned advantages of bidirectional language models, it is currently unclear how to tractably ensure the consistency of their conditional distributions. 1 in other words, it is non-trivial to guarantee the existence of a joint distribution whose conditionals coincide with those of a given bidirectional language model @xcite @xcite . furthermore, even if such a joint distribution exists, it is often computationally ex-pensive to access it explicitly. those fundamental flaws of bidirectional language models greatly hinder their applicability for sampling @xcite and likelihood computation @xcite , and often lead to self-contradictory behavior during inference @xcite . in this work, we introduce a class of bidirectional language models that are consistent by definition and can be efficiently used both for generation and scoring of sequences. to achieve this, we consider language modelling from the point of view of automata theory @xcite @xcite . @xcite have already explored the relations between unidirectional language models and sequential transducers. we extend their work by considering the bidirectional formalism of bisequential decompositions @xcite . by examining how bisequential decompositions represent probability distributions, we derive a class of bidirectional language models that we call latent language models. this formal correspondence allows us to precisely charaterise the abilities and limitations of a subclass of latent language models, called rational language models. as a result, we obtain that latent language models are exponentially more concise and significantly more expressive than unidirectional language models. we argue that such knowledge about the abilities and limitations of language models is essential whenever we require formal guarantees of the correctness and consistency of their outputs. ## factorisations of language models given a finite set σ, we shall use σ * to denote the set of finite sequences of elements of σ and ϵ to denote the empty sequence. in this case, σ is called an alphabet, the elements of σ are called letters and the elements of σ * are called words. additionally, given a word α, we shall write |α| for the length of α, α i for the i-th letter of α, α ≤i (or α <i+1 ) for the prefix α 1 α 2 • • • α i and α ≥i (or α >i-1 ) for the suffix α i α i+1 • • • α |α| . lastly, we shall naturally extend concatenation of words to sets of words. definition 2.1. let σ be an alphabet. a language model over σ is a discrete probability distribution over σ * ; i.e., a function p : σ * → [0, 1] such that foot_1 α∈σ * p(α) = 1. the support of a real-valued function f is the set supp(f ) := α ∈ dom(f ) | f (α) ̸ = 0 . we call a probability distribution p over x positive if supp(p) = x. naturally, a family of positive probability distributions is also called positive. in practice, it is not difficult to model a function from σ * to [0, 1] (e.g., with a logistic curve). however, satisfying the normalisation constraint (1) is non-trivial due to the infinitarity of σ * . consequently, in this section, we consider how language models can be factorised into families of finite conditional probability distributions that can then be modelled efficiently (e.g., with a softmax-based linear prediction head @xcite ). ## sequential language models in this section, we consider language modelling with sequential transducers. we argue that they provide a meaningful abstraction of unidirectional language models. thus, attaining deeper knowledge of the properties of sequential transducers could lead to better understanding of the abilities and limitations of unidirectional language models. ## rational language models in this section, we consider bidirectional language modelling with a pair of right-to-left and left-toright sequential transducers. we show that, compared to single independent sequential transducers, such bidirectional representations are exponentially more concise and significantly more expressive because they can realise any rational language model. ## latent language models the study of bisequential decompositions in section 4 suggests that for language modelling it might be beneficial to map (via an encoding function η) the input probability space σ * onto a latent probability space γ * where the corresponding probability measure p could be easier to represent. to make sure that the composition η • p is a probability measure on σ * , we have to ensure that no probability mass in the latent space 'leaks' onto inaccessible elements (that is, supp(p) ⊆ im(η)) and that the encoding function η does not map different elements of σ * onto a single latent element with non-zero probability (that is, η should be injective on η -1 supp(p) ). indeed, those properties are sufficient for η • p to be a language model over σ. in this case, we also have that η is a bijection from η -1 supp(p) to supp(p); thus, sampling from η • p is equivalent to sampling γ ∈ supp(p) from p and then computing η -1 (γ). ## conclusion we introduced a class of consistent bidirectional language models, called latent language models, that allow for efficient sampling and scoring of sequences. we defined latent language models based on the well-understood formalism of bisequential decompositions. this formal correspondence allowed us to precisely charaterise the abilities and limitations of a subclass of latent language models, called rational language models. as a result, we showed that latent language models are exponentially more concise and significantly more expressive than unidirectional language models.