To understand how a Transformer "thinks," researchers have begun treating its architecture not as a black-box statistical engine, but as a programmable computer. By mapping the operations of multi-head attention and feed-forward networks to formal logic and programming primitives, we can precisely define the computational limits of these models.
RASP: The Assembly Language of Attention
The bridge between neural weights and symbolic logic was solidified by Gail Weiss, Yoav Goldberg, and Eran Yahav in Thinking Like Transformers. They introduced RASP (Restricted Access Sequence Processing Language), a formal language where "code" maps directly to Transformer components.
In RASP, an attention head is viewed as a "select" operation that creates a boolean matrix (e.g., "does token $i$ match token $j$?"), and the MLP is a "map" operation that transforms values. This abstraction allows researchers to prove that a specific task—like reversing a string or checking for balanced parentheses—requires a minimum number of layers or heads. It transforms the question from "Can a Transformer learn this?" to "Is there a RASP program that can compute this?"
The Hierarchy of Hard Attention
A central challenge in this field is the gap between the "soft" attention used in practice (softmax) and the "hard" attention used in proofs. Theoretical frameworks often simplify attention into two flavors:
- Unique Hard Attention (UHAT): A head can only attend to exactly one position.
- Average Hard Attention (AHAT): A head can attend to a set of positions and average their values.
Pablo Barcelo and colleagues demonstrated in Logical Languages Accepted by Transformer Encoders with Hard Attention that this distinction is fundamental to a model's "intelligence." UHAT models are surprisingly weak; they struggle with simple circuit-level patterns. However, upgrading to AHAT grants the model "counting" powers, enabling it to recognize languages like majority (are there more 1s than 0s?) and parity.
This hierarchy was further refined by Andy Yang, David Chiang, and Dana Angluin, who proved that masked hard-attention Transformers are mathematically equivalent to Linear Temporal Logic (LTL). This means they recognize exactly the "star-free" regular languages, providing a rare exact characterization of what a specific architecture can "understand" Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages.
Succinctness: The Power of Compression
If Transformers and Finite Automata can both recognize certain languages, why prefer the Transformer? The answer lies in succinctness.
Pascal Bergsträßer, Anthony Widjaja Lin, and Ryan Cotterell proved in Transformers are Inherently Succinct that Transformers are exponentially more efficient than RNNs or LTL at representing certain patterns. A tiny Transformer can represent logic that would require a "doubly exponential" number of states in a finite automaton. This suggests that the Transformer's success isn't just about its ability to learn, but its ability to pack complex logical rules into a remarkably small number of parameters.
Bridging the Softmax Gap
While hard-attention models provide clean proofs, real-world Transformers use continuous softmax. This creates a theoretical friction: softmax assigns at least a tiny bit of weight to every token, making it difficult to "isolate" a single historical context perfectly. Anej Svete and Ryan Cotterell noted that this "leakage" makes it mathematically challenging for standard softmax models to represent discrete $n$-gram distributions exactly Transformers Can Represent n-gram Language Models.
However, Andy Yang and Lena Strobl showed that soft attention can simulate hard attention by manipulating temperature scaling or positional embeddings Simulating Hard Attention Using Soft Attention. This suggests that the "crisp" logic found in RASP and LTL is indeed accessible to practical models, provided they learn to sharpen their attention distributions sufficiently.
Transformers as Universal Simulators
The ultimate expression of this formal view is the idea of the Transformer as a "universal simulator." In On the Existence of Universal Simulators of Attention, Debanjan Dutta and colleagues used the RASP framework to prove that a Transformer encoder can be algorithmically constructed to replicate the exact matrix operations of any other attention-based model.
This moves the field toward a unified theory: Transformers are not just sequence processors, but a flexible computational substrate capable of simulating complex transducers and formal hierarchies Transformers as Transducers. By understanding the symbolic logic under the hood, we can begin to verify their properties and predict their behavior with mathematical certainty.