What Formal Languages Can Transformers Express? A Survey (2024)

Abstract: As transformers have gained prominence in natural language processing, some researchers have investigated theoretically what problems they can and cannot solve, by treating problems as formal languages. Exploring such questions can help clarify the power of transformers relative to other models of computation, their fundamental capabilities and limits, and the impact of architectural choices. Work in this subarea has made considerable progress in recent years. Here, we undertake a comprehensive survey of this work, documenting the diverse assumptions that underlie different results and providing a unified framework for harmonizing seemingly contradictory findings.

## introduction transformers @xcite have gained prominence in natural language processing (nlp), both in direct applications like machine translation and in pretrained models like bert @xcite and gpt @xcite @xcite . consequently, some researchers have sought to investigate their theoretical properties. such studies can broadly be divided into studies of expressivity and trainability. while trainability is very important and the focus of much study (e.g., @xcite , here we focus on expressivity, which is a prerequisite for trainability. studies of expressivity could be further divided into those from the perspectives of approximation theory and of formal language theory. the former (e.g., @xcite , investigates transformers as approximators of various classes of functions, along the lines of the universal approximation theorem for feedforward neural networks @xcite . the latter, which is the subject of this survey, investigates transformers as recognizers or generators of formal languages-that is, the inputs or outputs are treated as sequences of discrete symbols from a finite alphabet, and crucially as sequences of unbounded length. the core research question in this subarea is: how can we characterize the expressivity of transformers in relation to various formal models, such as automata, boolean circuits, or formal logic? applications of this subarea, which are not addressed by the papers surveyed here but could be by future work, would hopefully answer questions like: this paper provides a comprehensive survey of research in this subarea. compared to the surveys of @xcite and @xcite , which cover convolutional neural networks (cnns), rnns, and transformers, this is a narrower, but deeper, survey on transformers only. interpreting theoretical transformer results is complex due to diverse assumptions. many variants of transformers exist in practice, and even more have been proposed in theory. this diversity leads to varied, even seemingly contradictory, results. we set up a unified framework for talking about transformer variants ( §4), and discuss how some of these variants compare to one another in expressivity. we then provide background on various formal models that transformers have been compared with ( §5). then, in §6, we systematically survey current results in this literature, documenting their assumptions and claims in terms of the definitions of sections 4 and 5. much work on lower bounds has looked at automata like finite automata, counter machines, and turing machines, all of which had been successfully related to rnns before @xcite . this wide diversity of machines is due to different variants of transformers, especially whether a transformer decoder is allowed to take a number of interme-diate steps before outputting a decision ( §4.3.4), which dramatically increases its power ( §6.1). by contrast, investigation of upper bounds has mainly focused on circuit complexity ( §5.2), which had been successfully related to feedforward networks before @xcite @xcite . this line of research began with restricted models of transformer encoders and progressed to increasingly realistic variants and tighter bounds. one way to restrict transformers is by discretizing the attention mechanism ( §4.2.1); another is to limit the precision of number representations ( §4.4). more recent work has turned to formal logic ( §5.3) as a way of characterizing the expressive power of transformers. the finer control afforded by logics opens the possibility for them to be used as upper bounds, lower bounds, or both. vectors we use d, d , etc., for dimensionalities of vector spaces, lowercase bold letters (x, y, . . . ) for vectors, and uppercase bold letters (x, y, . . . ) for matrices. for any vector @xmath0, we number its elements starting from 0. for @xmath1, we write x i or [x] i (not x i ) for the i-th component of x. sequences for any set a, we write a * for the set of all finite sequences over a. we write the length of a sequence @xmath2; thus, s we use the variable w for a string in σ * and n for the length of w. for sequences in r * , we use lowercase bold letters (x, y, . . .), and for sequences in (r d ) * , we use the variable x. the activation functions we use are the rectified linear unit (relu) r (x) = max(x, 0) and the logistic sigmoid function σ(x) = 1/(1 + e -x ). the softmax function s : r * → r * converts any sequence of reals into a probability distribution: ## transformers in this section, we define transformers and relevant variants, and how transformers are used to describe formal languages. for additional background on transformers (not in relation to formal languages), @xcite give a lucid commentary on the original paper, @xcite give formal definitions and pseudocode, and @xcite survey many variants of transformers. transformers are composed of an input layer ( §4.1), one or more hidden layers ( §4.2), and an output layer ( §4.3). the inputs and outputs of the layers are sequences of vectors, which we treat as members of (r d ) * . foot_0 ## current results while this area of research still has many unresolved questions, the emerging picture has three levels of expressivity. at the upper end are decoders or encoder-decoders with intermediate steps; these are equivalent to turing machines ( §6.1). at the lower end are encoders with leftmost-hard or rightmost-hard attention; these can recognize only languages in ac 0 ( §6.2). in the middle are encoders with average-hard or softmax attention, which are the least well-understood but appear to lie between ac 0 and tc 0 ( §6.3). in this section, ''transformer'' refers to a transformer encoder unless otherwise indicated.