Characterizing the Expressivity of Fixed-Precision Transformer Language Models

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 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 LTL[P, F, S, U], which includes four temporal operators: P (past), F (future), S (since), and 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 LTL[P], a restricted fragment of LTL[P, F, S, U] that 1 Code available at GitHub repository. 39th Conference on Neural Information Processing Systems (NeurIPS 2025).