cs.FLJul 29, 2026

A Compositional Theory of Causally Masked Transformers

Authors: Franz Nowak, Ryan Cotterell, Reda Boumasmoud

Organizations: 1ETH Zürich

Abstract

What types of decision problems can a causally masked, finite-precision transformer solve for inputs of arbitrary length? Existing answers often rely on idealized arithmetic, but under finite precision, rounding and evaluation order can change what information attention retains and therefore what the model can compute. We develop an algebraic formalization that derives expressivity directly from the model's implemented dynamics. Its central object is its memory; the finite internal state computed by attention that summarizes the information from the prefix available to all future queries. Each attention head updates its own state independently within a layer, while layers compose hierarchically, providing a uniform route from model assumptions to expressivity bounds. Applying this method to transformers without positional embeddings, we obtain an expressivity hierarchy governed by the attention type under specific numerical semantics. Width-one sliding-window attention supports bounded-suffix memory, while a modified form of soft attention supports irreversible, checklist-like state, and combining the two mechanisms provides an interplay of both. Ordinary left-to-right floating-point soft attention can realize more expressive memory operations than any of the above. Algebraically, the four cases correspond to definite, R-trivial, locally R-trivial, and aperiodic semigroups. Under an explicit free-wiring assumption, all four bounds are tight.

Explore similar work

CardsList
May 28, 2026cs.LG

Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't

Recent work describes what transformers can and cannot compute through connections to boolean circuits, but existing results lack exact characterizations and are sensitive to modeling choices. Padded transformers -- to whose input filler symbols such as ``...'' are appended -- emerge as a useful gadget for establishing equivalences to circuit classes by providing polynomial space for adaptive parallel computation. However, only a limited set of padded transformer idealizations has been studied, leaving open how robustly these equivalences hold under changes to attention type, model width, and uniformity. We find that, under practical assumptions, padded transformers are surprisingly robust to all of these, and identify numeric precision and model depth as the main factors affecting expressivity. Concretely, we prove that polynomially padded L-uniform\text{L-uniform} constant-precision transformers are equivalent to L-uniform AC0\text{L-uniform AC}^0, while growing-precision ones achieve L-uniform TC0\text{L-uniform TC}^0 regardless of width. Furthermore, looping enables sequential processing analogous to circuits: log⁡dN\log^d N-looped constant-precision transformers reach FO-uniform ACd\text{FO-uniform AC}^d, and growing-precision ones reach FO-uniform TCd\text{FO-uniform TC}^d. Interestingly, growing width or precision beyond logarithmic does not increase expressivity, and all our results hold for both softmax and average hard attention transformers.
Anej Svete, William Merrill, Ryan Cotterell +1
Transformer VariantTransformer AttentionExpressivityTensor ProgramsCircuits
AskPDF
May 1, 2026cs.CL

Characterizing the Expressivity of Local Attention in Transformers

The transformer is the most popular neural architecture for language modeling. The cornerstone of the transformer is its global attention mechanism, which lets the model aggregate information from all preceding tokens before generating the next token. One common variant of attention is called local attention, which restricts each token to aggregating information from a bounded window of predecessors, reducing the quadratic cost of global attention to linear. Although this restriction is usually motivated by efficiency, it has also been found to improve model quality, a phenomenon that has so far lacked a satisfactory explanation. We provide a formal account of this phenomenon in terms of recognizer expressivity. It has been shown that fixed-precision transformers with global attention correspond to a fragment of linear temporal logic containing a single past operator. We additionally prove that adding local attention introduces a second temporal operator, strictly enlarging the class of recognizable regular languages. Moreover, global and local attention are expressively complementary: neither subsumes the other, and combining them yields the richest fragment. Experiments on formal language recognition and natural language modeling corroborate the theory, showing that hybrid global--local transformers outperform their global-only counterparts.
Jiaoda Li, Ryan Cotterell
Transformer AttentionModel AttentionHybrid TransformerExpressivity
AskPDF
Apr 16, 2026cs.LG

Expressivity of Transformers: A Tropical Geometry Perspective

To quantify the geometric expressivity of transformers, we introduce a tropical geometry framework to characterize their exact spatial partitioning capabilities. By modeling self-attention as a vector-valued tropical rational map, we prove it evaluates exactly to a Power Voronoi Diagram in the zero-temperature limit. Building on this equivalence, we establish a combinatorial rationale for Multi-Head Self-Attention (MHSA): via the Minkowski sum of Newton polytopes, multi-head aggregation expands the polyhedral complexity to O(NH)\mathcal{O}(N^H), overcoming the O(N)\mathcal{O}(N) bottleneck of single heads. Extending this to deep architectures, we derive the first tight asymptotic bounds on the number of linear regions in transformers (Θ(NdmodelL)Θ(N^{d_{\text{model}}L})), demonstrating a combinatorial explosion driven intrinsically by sequence length NN, ambient embedding dimension dmodeld_{\text{model}}, and network depth LL. Importantly, we guarantee that this idealized polyhedral skeleton is geometrically stable: finite-temperature soft attention preserves these topological partitions via exponentially tight differential approximation bounds.
Ye Su, Yong Liu
Multi-Head AttentionExpressivityOptimal Sample ComplexityPerspective
AskPDF