Umeå University's logo

This thesis studies the computational expressivity of transformers from the perspective of formal language theory, circuit complexity, and transductions. It develops a unified framework that locates finite-precision transformer architectures within established constant-depth circuit classes and descriptive logics, and links their recognition power to well-known hierarchies of string-to-string functions.

The analysis focuses on architectures under explicit and realistic constraints: constant depth, O(log n) precision, and simple positional features. Under these assumptions, encoder-only transformers with average-hard attention lie within DLOGTIME-uniform TC0. With a small set of positional encodings, masked average-hard encoders can simulate a calculus that contains the aperiodic polyregular transductions. Together, these results point to constant-depth counting (e.g., prefix sums and majority) as a shared mechanism behind both recognition and transduction.

The thesis further shows that temperature-scaled softmax attention can match the selection behavior of unique-hard attention, and that for average-hard heads with a unique maximizer per query (uniform-tieless), the same outputs can be obtained without changing the learned weights by choosing a length-dependent temperature. It also characterizes trade-offs in succinct models: some table-lookup layouts can be solved by a single concise layer under structure-aware encodings, whereas structure-oblivious layouts require either additional depth or super-polylogarithmic communication size.

Throughout, constructive proofs are paired with reference implementations and learning experiments on synthetic tasks. This combination clarifies which theoretically possible behaviors emerge in practice and where learnability lags expressivity, especially for length extrapolation. The thesis concludes with open directions toward adaptive masking, resource-aware analyses, and conditions under which standard training enables the models to reach their theoretical potential, strengthening the bridge between formal methods and neural language modeling.

We study the sequence-to-sequence mapping capacity of transformers by relating them to finite transducers, and find that they can express surprisingly large classes of (total functional) transductions. We do so using variants of RASP, a programming language designed to help people “think like transformers,” as an intermediate representation. We extend the existing Boolean variant B-RASP to sequence-to-sequence transductions and show that it computes exactly the first-order rational transductions (such as string rotation). Then, we introduce two new extensions. B-RASP[pos] enables calculations on positions (such as copying the first half of a string) and contains all first-order regular transductions. S-RASP adds prefix sum, which enables additional arithmetic operations (such as squaring a string) and contains all first-order polyregular transductions. Finally, we show that masked average-hard attention transformers can simulate S-RASP.

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.