On the Representational Capacity of Recurrent Neural Language Models (2023)

Abstract: This work investigates the computational expressivity of language models (LMs) based on recurrent neural networks (RNNs). Siegelmann and Sontag (1992) famously showed that RNNs with rational weights and hidden states and unbounded computation time are Turing complete. However, LMs define weightings over strings in addition to just (unweighted) language membership and the analysis of the computational power of RNN LMs (RLMs) should reflect this. We extend the Turing completeness result to the probabilistic case, showing how a rationally weighted RLM with unbounded computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. Since, in practice, RLMs work in real-time, processing a symbol at every time step, we treat the above result as an upper bound on the expressivity of RLMs. We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.

## introduction a language model (lm) is definitionally a semimeasure foot_0 over strings (icard, 2020). recent advances in their capabilities, leading to the widespread adoption of lms, have sparked interest in their theoretical properties and guarantees. previous work has characterized modern architectures such as recurrent neural networks (rnns; elman, 1990; hochreiter and schmidhuber, 1997) in terms of the formal languages they can and cannot recognize (kleene, 1956; minsky, 1967; siegelmann and sontag, 1992; merrill et al., 2020, inter alia). however, characterizing lms as formal languages is, in some sense, a category error because lms encode semimeasures over strings instead of deciding language membership (chen et al., 2018) between different models of computation. a ptm is a reformulation of the classic probabilistic turing machine. a qptm is a ptm with multiple rationally weighted transition functions. a 2pda is a probabilistic two-tape pushdown automaton. a σ-2pda is a 2pda that is deterministic in its output alphabet. an rlm is a simple rnn lm. an εrlm is an rlm augmented with an empty output symbol (ε). the prefix "rd-" denotes deterministic real-time machines. the empirical capabilities of trained language models have spurred a large field of work testing their reasoning and linguistic abilities. however, our theoretical understanding of what these models are inherently capable of is still lacking (deletang et al., 2023). connecting an lm architecture to well-understood models of computation can help us determine whether the architecture is able to perform the sequences of computations required to carry out an algorithmic task (pérez et al., 2019). furthermore, connecting it to linguistic models can tell us whether the architecture is capable of correctly modeling the linguistic structure of a sentence symbolically (linzen et al., 2016). finally, characterizing the types of semimeasures the architecture can represent allows us to make more concrete claims about the abilities and limitations of the architecture itself. rlms have set many important milestones in language modeling and still hold the state of the art in some important settings of natural language processing (qiu et al., 2020; orvieto et al., 2023). moreover, despite the recent trend towards the recurrence-free and, thus, parallelizable, transformer-based lms (vaswani et al., 2017), elements of recurrence have found their way into recent language models and rnns themselves have recently even been proposed as alternatives or extensions to some high-performing models (peng et al., 2023; orvieto et al., 2023; zhou et al., 2023). at a high level, rnns work by maintaining a hidden state encoding the processed string, much like how formal models of computation such as turing machines process and store information. this sequential nature has motivated the comparison of the computational power of rnns to that of various formal models of computation, from simple models such as finite-state automata (kleene, 1956; merrill et al., 2020) and counter machines, all the way up to turing machines and related models (minsky, 1967; siegelmann and sontag, 1992; weiss et al., 2018). precisely where rnns end up on the hierarchy of formal models of computation depends on the specific formalization. in this work, we characterize the computational power of rnns in their most permissive formalization, i.e., one that allows rnns to process and produce rational-valued vectors and perform an unbounded number of computational steps per input symbol by allowing them to emit empty tokens, ε, in between words. siegelmann and sontag (1992) show that such rnns can simulate any deterministic turing machine and are, hence, turing complete. @xcite while this sheds light on the processing power of rnns, their result is not directly applicable to language modeling, as it does not take into account the probability assigned to the strings. by extending siegelmann and sontag's (1992) construction to the probabilistic case, we provide first steps towards understanding the expressive power of rlms with rational arithmetic. we show that rlms with rational weights and unbounded computation time can compute exactly the same semimeasures over strings as probabilistic turing machines. on one hand, rational arithmetic offers a reasonably faithful formalization of real-world models in that computer scientists often analyze numerical algorithms using such an idealization. @xcite however, on the other hand, the assumption of unbounded computation time does represent a large departure from realistic models. in practice, rlms perform a constant number of computational steps per symbol, operating in a real-time setting (weiss et al., 2018). therefore, we treat the above result as an upper bound on the computational power of recurrent rlms. as a lower bound, we study a second type of rlms, restricting the models to operate in real-time, which results in a more fine-grained hierarchy of specific turing machine-like models equivalent to an rlm. we hence characterize the expressivity of rlms in terms of classical computational models. our work offers a first step towards a comprehensive characterization of the expressivity of rlms in terms of the classes of probability measures they can represent. in addition to providing insights into the computational capacity of rlms, the work also follows the recent exploration of the measure-theoretic foundations of lms (welleck et al., 2020; meister et al., 2023; du et al., 2023), while focusing on a particular architecture. we conclude the paper by posing several open questions on the exact position of rlms in the hierarchy of relevant computational models. fig. 1 shows a roadmap of the paper, with the two types of rlms of interest and their relation to different formal computational models. ## preliminiaries in this section, we build up the necessary definitions and vocabulary for the rest of the paper. ## a lower bound while thm. 3.2 establishes a concrete result on the expressive power of εrlms, the result follows from somewhat unrealistic assumptions, namely rationally weighted networks and unbounded computation time. we contend the first assumption is a reasonable approximation, since even for small neural networks the number of expressible states can be large; assuming double precision floating point numbers, an rnn can yield as many as 2 64•d different states, where d is the number of neurons. @xcite however, rlms used in practice operate in real-time, outputting a symbol at every computation step. to make our analysis closer to this use case, in this section, we develop a lower bound on the expressivity of an rlm under the real-time restriction while still allowing rational arithmetic operations. ## open questions this work establishes upper and lower bounds on the expressive power of rlms. while this shows how powerful rlms can be, the bounds do not completely and precisely characterize the models of interest. a natural question for follow-up work is, therefore, the following. ## discussion and conclusion the widespread deployment of lms in more and more far-reaching applications motivates a precise theoretical understanding of their abilities and shortcomings. in this paper, we show that tools from formal language theory, namely, probabilistic turing machines and their extensions, offer a fruitful means of investigating those abilities by allowing us to directly characterize the classes of (probabilistic) languages lms can represent. concretely, we place two different formalizations of rlms into the framework of probabilistic turing machines, thus characterizing their computational power. to connect our results with the bigger picture of understanding rlms, consider again fig. 1 . the upper part of fig. 1 (left to right) expresses the equivalence of ptms, their rationally valued equivalent and probabilistic two-stack pdas. these provide an upper bound for σ-deterministic 2pda, which are 2pda that are deterministic in their output alphabet. these in turn can be simulated by rlms that can output ε, allowing the model to perform an unbounded number of computations in between outputting output tokens. in appendix g, we show that any εrlm is weakly equivalent to some 2pda, meaning the expressivity of εrlm is upper-bounded by that of 2pda. the lower half of the fig. 1 shows the results on the more realistic real-time rlms with rational weight. we show that such models match the expressive power of real-time probabilistic turing machines with rational weights (lower left) through their correspondence to real-time deterministic probabilistic 2-stack pdas (lower right). these results provide a set of first insights into the modeling power of modern language models and hopefully provide a starting point for the investigation of other modern architectures, such as transformers (vaswani et al., 2017).