Transformers Can Represent n -gram Language Models (2024)

Abstract: Plenty of existing work has analyzed the abilities of the transformer architecture by describing its representational capacity with formal models of computation. However, the focus so far has been on analyzing the architecture in terms of language acceptance . We contend that this is an ill-suited problem in the study of language models (LMs), which are definitionally probability distributions over strings. In this paper, we focus on the relationship between transformer LMs and n -gram LMs, a simple and historically relevant class of language models. We show that transformer LMs using the hard or sparse attention mechanisms can exactly represent any n -gram LM, giving us a concrete lower bound on their probabilistic representational capacity. This provides a first step towards understanding the mechanisms that transformer LMs can use to represent probability distributions over strings.

## introduction neural language models (lms) have become the backbone of many nlp systems. their widespread adoption has prompted a plethora of theoretical work investigating what they can and cannot do by studying their representational capacity. most state-of-the-art lms are based on the transformer architecture @xcite , whose theoretical abilities and limitations have been studied extensively; see, e.g., the survey by @xcite . but, many questions remain unanswered. most existing work studies the architecture in terms of binary language recognition. this introduces a category error between the object of study-an lm, which is definitionally a distribution over strings-and the theoretical abstraction-a set of strings. to amend this discrepancy, we ask: what classes of probability distributions over strings can transformer lms represent? formal models of probabilistic computation provide a natural, well-understood, and precise framework for studying the classes of probability distributions language models can represent. traditionally, the representational capacity of neural networks, both in terms of lower bounds (what they can provably do) as well as upper bounds (what they can provably not do), has been studied in terms of boolean sequential models of computation, such as finite-state automata and turing machines (e.g., @xcite @xcite @xcite @xcite . recent work has extended this paradigm to work with probabilistic models of computation @xcite , but so far only for lms based on recurrent neural networks. however, the sequential nature of classical models makes the connection to the inherently parallelizable transformer architecture less straightforward and has resulted in a number of results upper-bounding their representational capacity @xcite @xcite @xcite . we connect transformer lms to a classical class of lms that lend themselves particularly well to parallelized computations: n-gram lms. we show that both hard as well as sparse attention transformer lms can represent any n-gram lm (theorems 3.1 and 4.1). 1 this gives us a concrete lower bound on their probabilistic representational capacity. we also study the role of the number of heads (theorem 3.1) and the number of layers (theorem 3.2), illustrating a trade-off between the number of heads, layers, and the complexity of the non-linear transformations required for the simulation of n-gram lms. altogether, these results offer a step towards understanding the probabilistic representational capacity of transformer lms and the mechanisms they might employ to implement formal models of computation. ## preliminaries let σ be an alphabet, i.e., a finite, non-empty set of symbols, and σ ˚the (infinite) set of all strings formed from symbols of σ. most modern lms define p pyq for y p σ ˚autoregressively-as a product of conditional probability distributions: here, eos r σ is a distinguished end-of-string symbol. the eos symbol enables us to define the probability of a string purely based on the conditional distributions. such a factorization can be done without loss of generality @xcite . we define σ def " σ y teosu. further, the conditional probability distributions p py t | y ăt q are usually defined based on vectorial representations of y ăt computed by some function enc : σ ˚ñ r d . this leads us to the definition of representationbased lms below. definition 2.1. let σ be an alphabet and enc : σ ˚ñ r d a representation function encoding strings as d-dimensional representations. let e p r |σ|ˆd be an output matrix. a representation-based lm p defines the conditional probability distributions p py t | y ăt q as 2 at a high level, we are interested in encoding an arbitrary n-gram lm using a transformer lm. to do so, we need a notion of equivalence between language models. in this paper, we will work with the following simple definition. definition 2.2. two lms p and q over σ ˚are weakly equivalent if p pyq " q pyq for all y p σ ˚. this paper precisely explains and proves the following theorem, stated informally below. theorem 2.1 (informal). for every n-gram lm, there exists a weakly equivalent ({hard, sparse} attention) transformer lm. ## sparse attention transformer lms while the results in §3 concretely characterize the abilities of hard attention transformer lms, the assumption of hard attention is somewhat removed from practical implementations of the model. those most often rely on differentiable normalization functions, such as the softmax. 3 however, the full support of the softmax function makes the connection to formal models of computation difficult @xcite . to bring the theoretical models closer to practical implementations yet still be able to make clear analogies to formal models of computation, we now consider sparse attention transformers, which use the sparsemax normalization function. the sparsity allows sparse attention transformers to simulate n-gram lms just like hard attention transformers while relying on differentiable operations. theorem 4.1. for any n-gram lm, there exists a weakly equivalent single-layer sparse attention transformer lm with n ´1 heads. proof intuition. the intuition behind the simulation with sparse attention is similar to the hard attention one; each head attends to a single position, as illustrated in fig. 1 . effectively, the construction results in a sparse attention transformer that simulates hard attention. in contrast to theorems 3.1 and 3.2, we here require a model with unbounded positional encodings and a non-linearly transformed dot-product scoring function. intuitively, the unbounded positional encodings are required to scale the unnormalized attention scores to differ enough for the sparsemax to focus on a single position. the rest of the proof follows that of theorem 3.1; see appendix c for the details. ■ theorem 4.1 (representing an n-gram lm with n ´1 heads) could naturally be extended to analogs of theorem 3.2 (representing an n-gram lm with n ´1 layers) and theorem 3.3 (representing an n-gram lm with a single head and a single layer) using a similar adaptation of the construction from the hard attention case to the sparse attention one as in theorem 4.1. ## space complexity in §3 and §4, we describe lower bounds that tell us what types of probability distributions transformer lms can represent, but do not say how efficiently they can do so. the space complexity of simulating n-gram lms is discussed in this section. we focus on hard-attention transformer lms with multiple heads or multiple layers (theorems 3.1 and 3.2) since their modeling assumptions (bar hard attention) are closest to practical implementations. the constructive proofs of theorems 3.1 and 3.2 allow us to directly analyze the space requirements for the simulation of n-gram lms, both in terms of (1) the size of the contextual representations x h ℓ as well as (2) the number of bits required to represent the individual entries of the vectors x h ℓ,t . ## discussion and related work to the best of our knowledge, §3 and §4 provide the first results on the probabilistic representational capacity of transformer lms. the relevance of n-gram lms to modern lms. one might rightfully question the utility of connecting the state-of-the-art language modeling architecture to n-gram lms. lms based on the n-gram assumption indeed constitute some of the simplest and least expressive classes of probability distributions. nevertheless, n-gram lms provide a useful playground and theoretical foundation for contextualizing and interpreting the inner workings of modern lms. for example, n-gram lms have been found to comprise a crucial component of in-context learning, where attention heads in different layers of the model together identify individual n-grams and base their predictions on the presence of such n-grams @xcite . the presence of specific n-grams might therefore present the foundations of in-context-based knowledge of transformer lms. as such, understanding the requirements for correct simulation of n-gram lms is important for a thorough grasp of the abilities of lms to learn in context. encouraging n-gram-lm-based learning has also been observed to aid in-context learning abilities @xcite . existing work has also linked n-gram lms to other neural network architectures such as one-dimensional convolutional neural networks @xcite . moreover, the theoretical grounding in classical formal language theory makes precise statements about n-gram lms possible while their simplicity makes them inherently interpretable and easy to analyze. n-gram lms also have a cognitive interpretation @xcite . most importantly, however, ngram lms lend themselves to paralellized processing, which affords a succinct and natural connection to transformer lms and has been suggested to be a crucial part of any theoretical treatment of transformer lms @xcite . understanding the limitations and abilities of hard attention transformer lms. our results are the strongest in the hard attention setting, which follows the trend of using hard attention in theoretical treatments. hard attention makes singling out the important aspects of the string (in our case, the history) possible. concretely, we showcase three different mechanisms that make it possible for transformer lms to implement n-gram lms with hard attention and investigate the role of the number of heads and layers. particularly, our constructions suggest a possible mechanism in which the different transformer heads or layers can specialize in focusing on different positions in the string, a feature that has previously been suggested as an explanation of how transformer lms process strings (elhage et al., 2021) and has been observed in trained transformer lms @xcite ). 6 our presentation of multiple orthogonal mechanisms that can simulate n-gram lms equivalently well is another confirmation of the observation that algorithmic principles learned or implemented by neural lms do not always correspond to a single intuitive implementation of a formal model of computation, which has concrete implications on interpretability methods for the architecture. this has been observed in practical scenarios and warns us that focusing on individual components of the model (that is, using myopic interpretability methods) might result in misleading interpretability results @xcite . ## conclusion we study the representational capacity of transformer lms with n-gram lms. we show how the parallelizable nature of n-gram lms is easy to capture with the transformer architecture and provide multiple lower bounds on the probabilistic representational capacity of transformer lms. concretely, we show that transformer lms can represent ngram lms both with hard and sparse attention, exhibiting multiple mechanisms transformer lms can employ to simulate n-gram lms. altogether, our results reinforce the utility of non-sequential models of computation for the study of transformers, particularly in the language modeling setting.