The Underlying Logic of Language Models: The Underlying Logic of Language Models: Transformers and Automata

The Underlying Logic of Language Models: Transformers and Automata

Speakers: Jiaoda Li, Ryan Cotterell, Franz Nowak, Anej Svete

Conference: ICML 2025

YouTube: https://slideslive.com/39043868

Overview

This talk delves into the fascinating intersection of modern deep learning architectures, specifically Transformers, and classical automata theory and algebraic automata theory. Presented by Jiaoda Li, Ryan Cotterell, Franz Nowak, and Anej Svete at ICML 2025, the session explores how Transformers, despite their parallel processing nature, can effectively approximate and even implement formalisms traditionally associated with recurrent processes. The central theme revolves around structural decomposition, a powerful analytical technique where complex mathematical objects are broken down into simpler, understandable components. This approach is applied to Transformers to uncover their underlying computational logic, drawing parallels to how integers are decomposed into prime numbers.

The core motivation behind this research is to gain a deeper theoretical understanding of the computational capabilities of Transformers, particularly their ability to recognize different classes of formal languages. By mapping Transformer mechanisms—such as attention, feed-forward networks, and residual connections—to the components of automata and their algebraic equivalents, the speakers provide a rigorous framework for analyzing what these powerful models can and cannot learn. This work bridges the gap between empirical success in natural language processing and the foundational theories of computation, offering insights into architectural design and the inherent limitations of Transformers under varying constraints.

Ultimately, the talk aims to answer fundamental questions about the expressive power of Transformers: which semi-groups and semi-automata can they model, and under what conditions? This has significant implications for how we design, train, and deploy large language models, providing a theoretical lens through which to interpret their remarkable performance and guide future innovation in the field.

Background

▶ Watch: Introduction: Structural decomposition for analyzing transformers (0:00)

The problem of understanding the computational capabilities of neural networks, particularly their ability to process sequential data, has long been a central question in ML and systems research. While recurrent neural networks (RNNs) were explicitly designed with recurrence in mind, mimicking the step-by-step processing of traditional finite state automata (FSA) or Turing machines, Transformers operate fundamentally differently. Transformers process sequences in parallel, relying on self-attention mechanisms to weigh the importance of different tokens across the entire input sequence simultaneously, rather than processing them one at a time. This parallel nature initially seemed at odds with recurrent formalisms. However, Transformers have demonstrated exceptional performance on tasks that involve sequences, often outperforming RNNs, raising questions about how they achieve this and what classes of languages they are capable of recognizing.

Classical automata theory provides a rich framework for defining and classifying languages based on the computational machines required to recognize them. A semi-automaton consists of a finite set of states (Q), a finite alphabet of symbols (Σ), and a transition function (δ) that maps a state and a symbol to a new state. When augmented with an initial state and a set of final states, it becomes an automaton, capable of accepting or rejecting strings to define a formal language. The set of all languages accepted by finite automata are known as regular languages, which can also be expressed by regular expressions (Kleene's theorem). These concepts can be elegantly represented using linear algebra, where states are one-hot encoded vectors and transition functions are matrices that are right-multiplied in sequence.

To further analyze the structure of automata and the languages they recognize, algebraic automata theory introduces concepts like semigroups, monoids, and groups. A semigroup is a set with an associative binary operation; a monoid adds an identity element; and a group further adds inverses for all elements. A homomorphism is a structure-preserving map between these algebraic structures. Crucially, the set of all finite-length strings over an alphabet (Σ*) forms a free monoid under concatenation. Regular languages can then be defined algebraically as the preimage of a finite subset of a finite monoid under a monoid homomorphism from Σ*.

Within algebraic automata theory, transformation semigroups are particularly relevant, representing the collection of state transformations an automaton can perform. These can be decomposed into fundamental types: permutation semigroups (which act like groups, being invertible) and aperiodic semigroups (where repeated application of a transformation eventually leads to an idempotent state, effectively "resetting" or stabilizing). The seminal Krohn-Rhodes theorem, developed 60 years ago, provides a powerful decomposition principle: any finite transformation semigroup (or semi-automaton) can be expressed as a cascade product of simpler components, specifically aperiodic semigroups and finite simple groups (which correspond to permutation groups). A cascade product involves stacking automata where the input to a higher automaton includes the state of the one below it, creating a hierarchy of information flow. While this decomposition represents a "division" rather than strict equality at the semigroup level (meaning a surjective homomorphism exists from the cascade to the original), it can achieve full language equivalence by carefully mapping the initial and final states of the resulting cascade automaton.

This theoretical framework has a rich history of applications, including Schützenberger's work in 1964, which linked star-freeness of regular languages to aperiodic transition monoids, and Straubing's work in 1994, connecting finite monoids to circuit complexity classes like ACC0 (which includes constant-depth circuits with modular gates). These connections reveal a sub-Chomsky hierarchy within regular languages: star-free languages (recognized by cascades of only aperiodic semigroups), solvable languages (recognized by cascades of aperiodic semigroups and cyclic groups, corresponding to modular addition), and finally, all regular languages (which may include more complex groups). The talk builds on this foundation, asking how Transformers fit into this established hierarchy.

Key Findings

▶ Watch: Automaton string acceptance with initial and final states (2:30)

The central findings of this talk establish a theoretical equivalence between the computational capabilities of Transformers and specific classes of regular languages, leveraging the Krohn-Rhodes decomposition to understand the underlying mechanisms.

Firstly, the talk demonstrates that Transformers can, in principle, recognize any regular language if allowed a logarithmic number of layers relative to the input sequence length. This is achieved by composing transition functions, effectively building a binary tree of operations that reduces the required depth from linear (one layer per symbol) to logarithmic. This represents a "shortcut" compared to the symbol-by-symbol processing of traditional recurrent models.

Secondly, for constant-depth Transformers (a more realistic architectural constraint), the ability to recognize regular languages is tied to the solvable languages subset of the regular language hierarchy. This is possible if Transformers can implement two fundamental components from the Krohn-Rhodes decomposition: resets (aperiodic semigroups) and modular counting (cyclic groups). The talk shows that:

• Resets/Memory can be implemented using attention mechanisms. Specifically, approximating hard attention with soft attention allows the model to "remember" the last relevant input symbol, akin to a flip-flop or reset automaton.
• Modular Counting can be implemented using a combination of soft attention (for summing values) and MLP feed-forward layers (for computing the modulo operation). This requires specific conditions on the MLP's width or activation functions.

The capability to perform these elemental operations in constant depth, combined with the ability to transmit information between layers via residual connections (enabling the cascade product), allows constant-depth Transformers to recognize all solvable languages. This implies that Transformers can inherently handle tasks like parity checks or modular arithmetic.

A crucial distinction is made regarding the MLP width required for modular counting: standard MLPs would need a linear width in the sequence length, which is impractical. However, if rotational activation functions (like sine or cosine) are employed, the MLP width can be reduced to constant, making the constant-depth recognition of solvable languages more feasible.

Finally, the talk clarifies that these theoretical constructions typically yield a family of models, where parameters might adapt to the maximum sequence length, rather than a single universal model capable of handling arbitrary input lengths without modification. This is analogous to how circuit complexity classes are defined. These findings provide a robust theoretical foundation for understanding the expressive power of Transformers and their relationship to classical computation.

Technical Deep Dive

▶ Watch: Kleene's Theorem: Automata define regular languages (3:15)

The technical core of the talk meticulously links the components of Transformers to the formalisms of automata theory and algebraic automata theory, primarily through the lens of the Krohn-Rhodes theorem.

Automata and Algebraic Foundations

The journey begins with the definition of a semi-automaton, characterized by a finite set of states $Q$, a finite alphabet $\Sigma$, and a transition function $\delta: Q \times \Sigma \to Q$. This can be visualized and computed using linear algebra: states are represented as one-hot encoded vectors (e.g., state 1 as [1, 0], state 2 as [0, 1]), and transitions for each symbol are represented by transition matrices. Applying a symbol corresponds to right-multiplying the current state vector by the symbol's transition matrix. An automaton extends this by adding an initial state and a set of final states; a string is accepted if, starting from the initial state, the sequence of transitions leads to a final state. The set of languages accepted by finite automata are precisely the regular languages.

Algebraic structures provide a more abstract view. A semigroup is a set with an associative binary operation. A monoid is a semigroup with an identity element. A group is a monoid where every element has an inverse. The set of all finite strings over an alphabet, $\Sigma^$, forms a free monoid under concatenation, with the empty string $\epsilon$ as the identity. A regular language $L$ is then defined as the preimage of a finite subset of a finite monoid $M$ under a monoid homomorphism $\phi: \Sigma^ \to M$.

Transformation semigroups are collections of functions from a set to itself, closed under composition. These are fundamentally equivalent to semi-automata. Two key types are distinguished:

• Permutation semigroups: These transformations are invertible, acting like a group.
• Aperiodic semigroups: These are non-invertible; repeated application of a transformation eventually leads to an idempotent state (e.g., $f(f(x)) = f(x)$ for some $x$ after a certain number of applications). This property is characteristic of "reset" behaviors.

The cascade product is a method of composing semi-automata in a hierarchical fashion. If we have two semi-automata, $A_1$ and $A_2$, the cascade product creates a new semi-automaton where $A_2$ takes inputs from both the original alphabet and the states of $A_1$. This allows for a layered information flow.

Krohn-Rhodes Decomposition Theorem

The Krohn-Rhodes theorem states that any finite transformation semigroup (or semi-automaton) can be decomposed into a cascade product of two fundamental types of "atoms": aperiodic semigroups (corresponding to resets) and finite simple groups (corresponding to permutations or cyclic counting). This decomposition is a "division" rather than an exact equality at the semigroup level, meaning there's a surjective homomorphism from a subset of the cascade's states to the original semi-automaton's states. However, for automata (which include initial and final states), this decomposition can achieve language equivalence, meaning the cascade automaton accepts precisely the same language as the original. This is crucial as it means we can understand complex language recognition by decomposing it into simpler, well-understood operations.

This theorem provides the theoretical underpinning for the sub-Chomsky hierarchy of regular languages:

• Star-free languages: Recognized by automata whose transition monoids are entirely aperiodic (cascades of only resets). These correspond to first-order logic.
• Solvable languages: Recognized by cascades of aperiodic semigroups and cyclic groups (corresponding to modular addition). These are equivalent to ACC0 circuits (constant-depth circuits with modular gates).
• Arbitrary regular languages: May include more complex non-solvable groups in their decomposition.

Two concrete examples of simple automata that form the basis of solvable languages are the reset automaton (always moving to state 0 upon seeing a '0' and state 1 upon seeing a '1', regardless of the current state, hence aperiodic) and the modular counting automaton (performing addition modulo $N$, which corresponds to cyclic groups and rotation matrices).

Transformer Mechanisms for Automata Simulation

The talk then directly maps these theoretical constructs to Transformer components:

1. Recognizing All Regular Languages with Logarithmic Depth:

• A Transformer can simulate an automaton's transition function for each input symbol. A naive approach would require $N$ layers for an $N$-symbol string.
• However, by leveraging the compositionality of transitions (e.g., multiplying transition matrices for $\sigma_1$ and $\sigma_2$ to get a combined transition), Transformers can compute transitions over increasingly larger segments of the input in parallel.
• This forms a binary tree of computations, reducing the required Transformer depth to $\mathcal{O}(\log N)$ layers for a sequence of length $N$, while maintaining finite MLP width. This is the first "shortcut" described.

1. Recognizing Solvable Languages with Constant Depth:

• This more challenging scenario requires implementing resets and modular counting within a constant number of layers.
• Resets/Memory: Implemented using attention. The key insight is that attention can be used to locate and "remember" the last occurrence of a specific input symbol. The authors refer to a prior work that uses a special fractional relative position encoding and approximates hard attention with soft attention. The closest two symbols (e.g., the current position and the last '0' or '1') will yield the highest attention score, effectively recalling the desired symbol. This mimics the behavior of a reset automaton.
• Modular Counting: Achieved by combining soft attention and MLP feed-forward layers. Soft attention, especially with causal masking, naturally computes sums over values up to the current position. An MLP can then be configured to compute a modulo operation on this sum (e.g., modulo 2).
• A critical constraint here is the MLP width. For standard activation functions, computing modulo operations across varying input ranges would typically require an MLP whose width is linear in the sequence length. This is not practical for large sequences.
• However, the talk highlights that if rotational activation functions (like sine or cosine) are permitted, the MLP width can be reduced to constant, making constant-depth modular counting feasible.
• Cascade Product: The hierarchical information flow required by the cascade product is naturally enabled by residual connections (skip connections) in Transformers. The "state" of a lower layer can be directly forwarded to higher layers via the residual stream, allowing subsequent layers to condition their computations on previous layer outputs.

In summary, the talk meticulously demonstrates how the fundamental building blocks of Transformers—attention, MLPs, and residual connections—can be precisely mapped to the "atoms" and composition methods prescribed by algebraic automata theory, thereby explaining their capacity to recognize various classes of formal languages under specific architectural and computational constraints.

Experimental Setup & Results

▶ Watch: Example: Reset automaton (flip-flop) and singular matrices (4:00)

This talk primarily presents a theoretical framework for understanding the computational power of Transformers rather than detailing a specific experimental setup or new empirical results. The focus is on establishing equivalences between Transformer architectures and classes of formal languages, building upon existing theoretical work in algebraic automata theory and recent influential papers like "Transformers Learn Shortcuts to Automata."

Therefore, there is no "experimental setup" in the traditional sense of training a new model on a dataset and reporting performance metrics like accuracy or F1 scores. Instead, the "results" are in the form of theoretical proofs and constructions that demonstrate what Transformers can represent under certain assumptions.

Key "results" from this theoretical perspective include:

• Logarithmic Depth for All Regular Languages: The construction shows that a Transformer with $\mathcal{O}(\log N)$ layers (where $N$ is the sequence length) and finite-width MLPs can recognize any regular language. This is achieved by composing transition functions in a binary tree structure.
• Constant Depth for Solvable Languages: Under the condition of finite layers:
• Transformers with finite-width MLPs can recognize star-free languages. These rely on attention for "reset" mechanisms.
• Transformers with linear-width MLPs or special rotational activation functions (e.g., sine/cosine) in their MLPs can recognize solvable languages. This capability hinges on attention for resets and soft attention combined with MLPs for modular counting.

The "hardware" and "datasets" are abstract in this context; the discussion assumes ideal computational primitives and sufficient precision for the theoretical operations. The "baselines" are the definitions of language classes themselves (star-free, solvable, regular) and the classical automata (reset, modular counting) that recognize them.

It's important to note that these are computational complexity results and not empirical benchmarks. The paper "Transformers Learn Shortcuts to Automata" is referenced as a foundational work that first connected Krohn-Rhodes to modern NLP research, and its assumptions (e.g., logarithmically bounded numerical precision, approximation of hard attention by soft attention) are implicitly carried over.

The talk acknowledges a crucial caveat: these constructions typically yield a family of models, not a single, universal Transformer. The parameters of the model (e.g., fractional position embeddings) may depend on the maximum sequence length, meaning a model trained for sequences up to length $L$ might not generalize to arbitrary longer sequences without re-parameterization or retraining. This is a common characteristic when drawing parallels to circuit complexity theory, where a "circuit" for a given problem is defined for inputs of a fixed size.

In essence, this section details the theoretical capabilities of Transformers as computational devices, rather than reporting on their performance in a practical, empirical setting.

Practical Implications

▶ Watch: Algebraic definition of regular languages using monoids (4:30)

The theoretical insights presented in this talk have profound practical implications for practitioners, infrastructure teams, model builders, and deployers working with Transformers and large language models.

1. Deeper Understanding of Transformer Capabilities: This work provides a rigorous, theoretical explanation for why Transformers are so effective at sequence processing, even without explicit recurrence. It clarifies that their power stems from their ability to mimic fundamental automata operations like memory (resets) and counting (modular arithmetic) through attention and MLPs, respectively. This moves beyond empirical observation to foundational understanding.

1. Architectural Guidance and Design Principles:

• Attention is Key for Memory: The demonstration that attention can implement "resets" or "memory" (recalling the last relevant input) underscores the critical role of attention in encoding sequential dependencies and state-like information. This reinforces the importance of designing effective attention mechanisms.
• MLPs for Computation: The finding that MLPs can perform modular arithmetic highlights their role beyond simple non-linearity. This suggests that the internal structure and activation functions of MLPs could be further optimized for specific computational tasks.
• Residual Connections Enable Composition: The use of residual connections to facilitate the "cascade product" explains how Transformers can build complex computational hierarchies by passing "state" information between layers. This validates the ubiquitous use of residual connections in modern deep learning architectures.

1. Limitations and Tradeoffs for Model Builders:

• Precision Requirements: The theoretical results often rely on assumptions about logarithmically bounded numerical precision. In practice, floating-point precision can introduce errors, potentially limiting the exact realization of these theoretical capabilities, especially for long sequences or complex counting tasks.
• MLP Width vs. Activation Functions: The tradeoff between linear-width MLPs (for solvable languages with standard activations) and constant-width MLPs (requiring special rotational activations like sine/cosine) is significant. Linear-width MLPs are computationally expensive and impractical for long sequences. Exploring and adopting novel activation functions might be a pathway to more efficient and powerful constant-depth Transformers.
• "Family of Models" vs. Universal Generalization: The finding that these constructions yield a "family of models" (where parameters might depend on the maximum sequence length) implies that a single Transformer might not flawlessly generalize to arbitrary input lengths without adjustments. This has implications for training strategies and the robustness of models deployed in dynamic environments. Model builders might need to consider strategies for length generalization or dynamic model adaptation.
• Trainability vs. Representational Power: While Transformers are theoretically capable of representing these languages, the question of trainability remains. Can optimization algorithms effectively learn these specific automata-like functions, especially with current training paradigms and finite data? This gap between theoretical representational power and practical learnability is an ongoing area of research.

1. Implications for Infra Teams and Deployers:

• Understanding the computational complexity (e.g., logarithmic depth vs. constant depth, MLP width) provides insights into the resource requirements for different types of language recognition tasks.
• The choice of activation functions or the need for specific precision levels could influence hardware selection and optimization strategies (e.g., specialized hardware for trigonometric functions or higher precision arithmetic).

In essence, this work provides a blueprint for understanding the computational "grammar" of Transformers. It empowers practitioners to make more informed decisions about architecture, hyperparameter tuning, and the potential pitfalls associated with pushing the boundaries of what these models can achieve, especially when aiming for rigorous, formal language recognition.

Key Takeaways

• Krohn-Rhodes Theorem as a Lens: The Krohn-Rhodes decomposition theorem provides a powerful theoretical framework for understanding how complex automata (and by extension, Transformers) can be broken down into simpler, fundamental components: aperiodic semigroups (resets) and finite simple groups (cyclic counting).
• Logarithmic Depth for All Regular Languages: Transformers can theoretically recognize any regular language by employing a logarithmic number of layers relative to the sequence length, leveraging the compositionality of transition functions.
• Constant Depth for Solvable Languages: With a constant number of layers, Transformers can recognize solvable languages (a subset of regular languages including star-free languages and those involving modular arithmetic). This requires specific conditions on MLP width (linear, or constant with rotational activations).
• Attention for Memory and Counting: Attention mechanisms are crucial for implementing "resets" (memory or recalling the last relevant input) and contribute to modular counting (by summing values), demonstrating their fundamental role in sequential processing.
• MLPs and Residuals Enable Computation and Composition: MLP feed-forward layers perform the actual modulo computations, while residual connections facilitate the "cascade product" by transmitting state information between layers, allowing for hierarchical composition of automata.
• Theoretical Capabilities vs. Practical Constraints: While Transformers possess significant theoretical power, practical limitations include assumptions about numerical precision, the need for potentially linear-width MLPs (or specialized activations), and the construction often yielding a "family of models" rather than a single universal model for arbitrary input lengths.

About the Speaker(s)

The talk "The Underlying Logic of Language Models: Transformers and Automata" was presented by Jiaoda Li, Ryan Cotterell, Franz Nowak, and Anej Svete at ICML 2025. This collaborative work represents a significant contribution to the theoretical understanding of modern AI/ML architectures.