Characterizing the Expressivity of Fixed-Precision Transformer Language Models

Jiaoda Li Ryan Cotterell · 2025

Read Characterizing the Expressivity of Fixed-Precision Transformer Language Models by Jiaoda Li Ryan Cotterell (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23623.txt.

Introduction

Jiaoda Li and Ryan Cotterell pin down exactly what a simplified transformer language model can and cannot express. Their idealization uses fixed numerical precision, blocks attention to the future, uses soft attention, and drops position markers. Within those rules, the model's power matches a specific fragment of temporal logic that uses only a single operator, one that talks about the past.

That fragment also lines up with known classes from automata theory and algebra, giving one unified map of this model's reach. Experiments agree with the math. Trained transformers generalize across text lengths on languages inside the boundary and consistently fail on languages outside it.

Catalog record

CREATORJiaoda Li Ryan Cotterell
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-23623

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Characterizing the Expressivity of Fixed-Precision Transformer Language Models Jiaoda Li Ryan Cotterell Abstract Transformer-based language models (LMs) have achieved widespread empirical success, but their theoretical expressive power remains only partially understood. In this work, we analyze a restricted idealization of fixed-precision transformers with strict future masking, soft attention, and no positional encodings. We establish that this class of models is exactly as expressive as a specific fragment of linear temporal logic that contains only a single temporal operator: the past operator. We further connect this fragment to established classes in formal language theory, automata theory, and algebra, yielding a unified framework for understanding transformer expressivity under this idealization. Finally, we present empirical results that align closely with our theory: transformers trained on languages within their characterized expressive capacity generalize reliably across sequence lengths, while they consistently fail to generalize on languages beyond it. 1 1 1 Code available at GitHub repository . 1 Introduction Transformer-based language models (LMs) have demonstrated remarkable empirical success [ 46 , 36 , 12 ] on a wide variety of natural language tasks [ 47 , 19 , 41 , inter alia ] . This success has sparked growing interest in understanding the theoretical expressive power of transformers, i.e., what languages they can and cannot recognize, and, by extension, what tasks they can and cannot perform. A significant body of work approaches this question by relating transformers to well-established frameworks such as formal languages, logic, and circuit complexity [ 18 , 31 , 50 , 42 ] . To facilitate their theoretical analysis, theoreticians often propose idealizations of transformers. For instance, while practical implementations of transformers operate under fixed precision, e.g., single (32-bit) or half (16-bit) precision, many authors assume arbitrary [ 38 , 18 , 34 ] or length-dependent precision [ 32 , 7 ] . Although such idealizations capture key aspects of transformers, they tend to overestimate their expressive power [ 38 ] . A recent step toward a more faithful theoretical understanding of the expressive power of transformers comes from Yang et al. [50] , who show that fixed-precision transformers with strict future masking and unique hard attention (UHA) are exactly as expressive as linear temporal logic {\textup{{LTL}}[{\mathrel{\textup{{P}}}},{\mathrel{\textup{{F}}}},{\mathrel{\textup{{S}}}},{\mathrel{\textup{{U}}}}]} , which includes four temporal operators: {\mathrel{\textup{{P}}}} ( past ), {\mathrel{\textup{{F}}}} ( future ), {\mathrel{\textup{{S}}}} ( since ), and {\mathrel{\textup{{U}}}} ( until ). However, UHA still deviates from the soft attention used in practice. To address this gap, Yang and Chiang [49] analyze fixed-precision transformers with strict future masking and soft attention, an idealization that most closely reflects the models deployed in real-world applications. Yang and Chiang [49] show that such models are upper bounded by C-RASP, a counting-based programming language, though a precise characterization of these models’ expressivity remains open. In this paper, we close this gap by providing an exact characterization of the expressive power of fixed-precision transformers with soft attention, strict masking, and no positional encodings (NoPE). We show they are precisely characterized by {\textup{{LTL}}[{\mathrel{\textup{{P}}}}]} , a restricted fragment of {\textup{{LTL}}[{\mathrel{\textup{{P}}}},{\mathrel{\textup{{F}}}},{\mathrel{\textup{{S}}}},{\mathrel{\textup{{U}}}}]} that uses only the past operator ( {\mathrel{\textup{{P}}}} ). We further demonstrate that {\textup{{LTL}}[{\mathrel{\textup{{P}}}}]} is equivalent in expressivity to partially ordered deterministic finite automata (PODFAs), which are characterized by {{{\mathcal{R}}}} -trivial monoids and recognize left-deterministic polynomials. These results offer a detailed and principled characterization of the expressive power of this idealization, delineating its strengths and limitations. Crucially, our findings imply that many simple languages, e.g., bounded Dyck languages, which have been shown to be recognizable under more permissive idealizations, are beyond the reach of the models we study. We also extend our theoretical results to transformer LMs, showing that their expressivity matches that of transformer recognizers. A visual overview of the theoretical landscape is provided in Fig. 1 . {\textup{{LTL}}[{\mathrel{\textup{{P}}}}]} {\textup{{PFO}}^{2}[\mathord{<}]} PODFA {{{\mathcal{R}}}} -trivial monoid left-deterministic polynomial transformer language model transformer Theorem 2.1 Theorem 5.2 Theorem 5.1 Theorem 3.3 Theorem 3.2 Lemma C.1 Lemma C.4 [ 4 ] Figure 1 : Roadmap of the paper. Red arrows indicate novel results. To arrive at a compelling theory, it is essential to show that it faithfully reflects the behavior of models trained under standard machine learning paradigms. To this end, we provide empirical evidence using the length generalization framework, a widely used method for gauging neural network expressivity [ 10 , 6 , 22 ] . We construct a suite of languages spanning a fine-grained hierarchy of formal language classes. Our results ( Tab. 1 ) exhibit strong alignment between theory and practice: for all languages that transformers are predicted to recognize, the models generalize perfectly over lengths ( 100\% accuracy); for languages beyond their theoretical capacity, they consistently make generalization errors, regardless of learning rates or random seeds. 2 Background In this section, we present the necessary background knowledge that underpins our analysis. 2.1 Strings and Languages An alphabet , denoted as {{\Sigma}} , is a finite, non-empty set of symbols. A string over {{\Sigma}} is a finite sequence of symbols drawn from {{\Sigma}} . The set of all strings over {{\Sigma}} is denoted by its Kleene star {{{{\Sigma}}^{*}}} . A subset of {{{{\Sigma}}^{*}}} is called a language . A regular expression is a declarative way to describe a language, defined recursively as follows: • \emptyset and each {\texttt{a}}\in{{\Sigma}} are regular expressions; • If \alpha and \beta are regular expressions, so are the union \alpha+\beta , concatenation \alpha\beta , the Kleene star \alpha^{*} , and complement {{\alpha^{\textsf{c}}}} . A language is regular if and only if it can be described by a regular expression [ 26 ] . A regular language is said to be star-free if it can be described by a regular expression without the Kleene star [ 28 ] . As an example, {{{{\Sigma}}^{*}}} , the set of all strings over {{\Sigma}} , is star-free, as it can be described by {{\emptyset^{\textsf{c}}}} . 2.2 {\textup{{LTL}}[{\mathrel{\textup{{P}}}}]} Linear temporal logic {\textup{{LTL}}[{\mathrel{\textup{{P}}}},{\mathrel{\textup{{F}}}},{\mathrel{\textup{{S}}}},{\mathrel{\textup{{U}}}}]} [ 25 ] is a modal logic, with modalities referring to time. The full definition is given in § A.1 . In this paper, we define a fragment of {\textup{{LTL}}[{\mathrel{\textup{{P}}}},{\mathrel{\textup{{F}}}},{\mathrel{\textup{{S}}}},{\mathrel{\textup{{U}}}}]} —denoted as {\textup{{LTL}}[{\mathrel{\textup{{P}}}}]} —that includes only one temporal operator {\mathrel{\textup{{P}}}} ( past ). Formulas in {\textup{{LTL}}[{\mathrel{\textup{{P}}}}]} are composed of atomic formulas {\pi}_{\texttt{a}} for every {\texttt{a}}\in{{\Sigma}} , Boolean connectives \land,\lnot , and a temporal operator {\mathrel{\textup{{P}}}} . The disjunction \lor is definable in terms of \land and \lnot as: {\psi}_{1}\lor{\psi}_{2}\mathrel{\stackrel{{\scriptstyle\textnormal{\tiny def}}}{{=}}}\lnot(\lnot{\psi}_{1}\land\lnot{\psi}_{2}). (1) When defined over strings, the formulas are interpreted with respect to a string {{\textbf{{w}}}}={\texttt{w}}_{1}\cdots{\texttt{w}}_{N} at a position n\in\{1,\ldots,{N}\} . The semantics are defined inductively. Given a string w , a position n , and a formula {\psi} , we define {{\textbf{{w}}}},n\models{\psi} ( w satisfies {\psi} at position n ) as follows: {{\textbf{{w}}}},n\models{\pi}_{\texttt{a}} if and only if the n^{\text{th}} symbol of w is an a . {{\textbf{{w}}}},n\models{\psi}_{1}\land{\psi}_{2} if and only if {{\textbf{{w}}}},n\models{\psi}_{1} and {{\textbf{{w}}}},n\models{\psi}_{2} . {{\textbf{{w}}}},n\models\lnot{\psi} if and only if {{\textbf{{w}}}},n\not\models{\psi} . {{\textbf{{w}}}},n\models{\mathrel{\textup{{P}}}}{\psi} if and only if there exists m such that m<n and {{\textbf{{w}}}},m\models{\psi} . Example: • {\texttt{a}}{\texttt{b}}{\texttt{b}},1\models{\pi}_{\texttt{a}} as the first symbol is a . • {\texttt{a}}{\texttt{b}}{\texttt{b}},3\models{\mathrel{\textup{{P}}}}{\pi}_{\texttt{a}} as an a occurs before position 3. To say a string w of length {N} satisfies a formula {\psi} , written as {{\textbf{{w}}}}\models{\psi} , we evaluate from position {N}+1 (the position after the final symbol): {{\textbf{{w}}}}\models{\psi}\quad\text{if and only if}\quad{{\textbf{{w}}}},{N}+1\models{\psi}. (2) The

Read the complete text