The Transformer Cookbook
Authors: Andy Yang
Christopher Watson
Anton Xue
Satwik Bhattamishra
Jose Llarena
William Merrill
Emile Dos Santos Ferreira
Anej Svete
David Chiang
Venue: Accepted by TMLR ()

Abstract: We present the transformer cookbook: a collection of techniques for directly encoding algorithms into a transformer's parameters. This work addresses the steep learning curve of such endeavors, a problem exacerbated by a fragmented literature where key results are scattered across numerous papers. In particular, we synthesize this disparate body of findings into a curated set of recipes that demonstrate how to implement everything from basic arithmetic in feed-forward layers to complex data routing via self-attention. Our mise en place of formulations is for both newcomers seeking an accessible entry point and experts in need of a systematic reference. This unified presentation of transformer constructions provides a foundation for future work spanning theoretical research in computational complexity to empirical investigations in architecture design and interpretability. We provide code implementations of each construction in numpy alongside a suite of generative unit tests.

Published in Transactions on Machine Learning Research (01/2026)
The Transformer Cookbook
Andy Yang"
ayang4 Ond. edu
University of Notre Dame
Christopher Watson
ccuetson upenn edu
University of Pernsyloania
Anton Xue University of Texos Austin
anlon.nue@uuusinn.uuk eduu
Satwik Bhattamishra University of Ouford
nutuik.bmikkuusss.o...
Jose Llarena Independent Reseorcher
jose.llavena@@mmail.cm
William Merrill Allen Institute for Artificial Intelligence
willm@allenii.org
Emile Dos Santos Ferrcira Stellenbosch University
emsilfferveira awteriirrruuuaa....
Anej Svete ETTH Zürich
asveteBethe.ck ch
David Chiang
dchiang Ond edu
Universily of Notre Dame
Reviewed on OpenReview: https: // openreview. net/ forum? id= sPahCSuDrX
Abstract
We present the transformer cookbook: collcction of techniques for directly encoding al- gorithmss into transformer's parameters. This work addresses the steep learning curve of such endeavors, problem exacerbated by fragmented literature where key results scattered across numerous papers. In particular, we synthesize this disparate body of find- ings into a curated set of recipes that demonstrate how to implement everything from basic arithmetic feed-forward layers to complex data routing via self-attention. Our mise en place of formulations for both newcomers seeking an accessible entry point and experts in need of a systematic reference. This unified presentation of transformer constructions provides foundation for future work spanning theoretical research in computational com- plexity to empirical investigations in architecture design and interpretability. We provide code implementations of each construction in numpy alongside a suite of generative unit tests.
"Corresponding author.
Formal Languages and Neural Networks Seminars: httpe://tlannseennn github. (odde maintainer. Code http://htt....eeeeeeeeeeeeeeears

---

Published in Transactions on Machine Learning Research (01/2026)
1 Introduction
Transformers are the key ingredient of large language models (Vaswani et al., 2017). While they are typ- ically trained through data, there is also much interest explicitly "programming" algorithms into their parameters. By linking algorithmic procedures to model constructions, we obtain a more transparent view of transformers: the problems they can solve, the mechanisms they might implement, and their fundamental limitations. In practice, theorctical results proven through transformer constructions are commonly used molivation for lasks ranging from model training to mechanistic interpretability.
However, transformer constructions are difficult to study and apply. The literature is highly fragmented, with key results scattered across numcrous publications, each with its own unique notation and architectural assumptions. For instance, a major step was made by Weiss el al. (2021) who created the RASP programming language, followed up by Lindner et al. (2023) who created a compiler that compiled a subset of RASP programs into transformer weights. However, RASP as full language was somewhat more powerful than transformers, and compilation using Tracr required restrictions on the input length. While notable surveys, such as that of Strobl et al. (2024), chart and map out key results built from these constructions, they rarely dive deep into the specific technical details. In fact, there has been no unified presentation of the techniques used in these constructions, which forces newcomers to piece together the requisite knowledge from disparate sources.
To address this gap; we curate and systematize the common constructions of transformee--nnooded algorithms, creating a unified reference for both aspiring and seasoned (ransformisss that makes these methods explicit, precise, and accessible. While each construction comes with its set of assumptions and preconditions, our unified presentation enables the reader to compare the detailed implications of cach onc. This synthesis establishes a common ground for both theory and practice: theoretically, it abstracts a set of core compu- tational principles from the literature; empirically, it offers a library of idealized circuits to guide the design of new architectures and the analysis of existing ones. More broadly, we believe this unified perspective is essential for building safe and reliable AI systems.
To achieve these goals, this cookbook is structured as follows:
Preliminarics (Section 2). This section gives an overview of the mathematical background and the key components of transformer. Even if the reader is already familiar with this topic, we nevertheless encourage giving this section read, since nearly all constructions in the book will follow the notational conventions introduced here.
Basic Ingredients (Section 3). Before diving into constructions, we next present some lemmas that will be of use. Additionally, we discuss some key concepts that must be considered in any rigorous construction, such as the issue of uniformity and representing common data types.
Feedforward Layers (Section 4). The feedforward layers of transformer offer opportunities for rich computation. Here, discuss how to construct arithmetic computations, logic circuits, and other tricks. A summary of the key constructions is shown in Table 1.
Self- Attention Layers (Section 5). Innovations in the self-attention layer are what set the trans- former apart from the architectures that came before it. We show how to construct useful aggregation and selection operations here. A summary of the constructions is provided in Table 2.
Layer Normalization (Section 6). This an important architectural component that enabled early practitioners to train large-scale transformers with numerical stability. We show how to leverage this component to perform operations, such the amplification of signals.
Rounding (Section 7). Whereas it is often convenient for humans to reason in discrete values (e.g., tokens), transformers fundamentally operate on continuous-valued inputs. We discuss various rounding tricks here that allow for easy conversion from the continuous to the discrete.
Assembly (Section 8). Having introduced many constructions, we now give useful lemmas on how to connect them. The primary operations involve putting constructions in sequence ("serial composition") and in parallel ("parallel composition").
2

---

Published in Transactions on Machine Learning Research (01/2026)
Examples (Section 9). To round out our cookbook, we provide instructive examples on how classical constructions from the literature may be achieved with our recipes. In particular, we give examples with induction heads and the Dyek languages. A summary of these constructions is given in Table 3.
2 Preliminaries
2.1 Notation
We write [n] for the set {I....,ny nj.. For any true/false statement b, we let [b] = b is true and b is false. If X set, we write X for the of sequences over X, and X+ for the set of non-empty sequences over X. Let D be a finite alphabet. We write strings in E as wi ..- wn. We write for the zero vector matrix, I for the identity matrix, and 1 for vector matrix whose entries all 1. For any function I: IR + R and any veclor x = [m:]/=1 E IRd, exlend f to x coordinate-wise:
x1
(ax )
x2
f(z2)
f(x) =
((raa)
We write f: X+ 1 + to state that f is a function from X to Yt, and it is length-preserving, that is, it maps every sequence to sequence of the same length. Slightly unusually (following Strobl et al. (2024)), we will often work with sequences vectors in (Rd)+, which we write as (x1...., x,). Two sequences of the same length be added position-wise: (X1,..., x..) (y1...., (x1 + , X, yn).
To avoid excessive subscripting and superscripting in complex networks, adopt "dot notation" which is nonstandard in mathematics but hopefully familiar from many programming languages. If f is function that depends on some parameters, we give the parameters names like f.a and f.b. If is another function with parameters g.a and g.b, there is no implied relationship between f.a and g.a.
2.2 Transformers
A transformer is a neural network that, in this paper, defines a longth-preserving mapping from strings to strings. An input layer maps a string to a sequence of vectors. Then the network processes sequences of vectors through multiple layers, each consisting of a self-attention sublayer followed by feed-forward sublayer. Finally, an output layer maps the sequence of vectors string.
Here, we define the overall structure of the transformer function, before defining the individual compo- nents in subsequent sections.
Definition 2.1. A transformer is a function
tf: Σ 1 y+
tf(x
Fn) = 811 .. y/ where
(1)
z; (0) tf.we(x;) + tf.pe,, (i)
i [n]
(2)
(z) (1)
(1) (1) (z) (0)
(0)
(3)
(2)
(1) (()
tf.tt( (1 (b-1) (1-11)
..... z (1-11)
(4)
y: tf.ouu(z!! (L)
E [n]
(5)
where tf.we and te, are embedding functions, defined below (Section 2.2.1), the tf () are transformer layers, defined below (Section 2.2.2), and tf.out is an unembedding function with some output space ) discussed below (Section 2.2.3).
3

---

Published in Transactions on Machine Learning Research (01/2026)
Function
Type
Definition
Behavior
Exact?
Reference
Identity
_ gd
returns the input unchanged
Yes
Section 4.3
Min / Max
I + R
min(2, y) or max(a.
Yes
Section 4.4
Add Subtract
R22 R
a y (or 2- v)
Yes
Section 4.5
Multiply by
R R
scales imput:
Yes
Section 8.2
Multiply (zy)
R²2 + R
product zy via 2nd-order Taylor expansion of GELU (re-
No
Section 4.6
quires GELU activations)
Comparators
(0, 1}
1x > 0]. Ma 2 0J, 1 0] any Boolean function of bits
No
Section
Boolean functions
{o. 1m {0. 1}
Yes
Section 4.8
Conditional (if)
10,1} x R +R R
if #p= = then æ else
Yes
Section 4.9
CPWL
R R
any continuous piccewiso- linear function with finitely many
Yes
Section 4.1
pieces
Cancel Residual
Rd
R
builds so that (x) f(x)
Yes
Section 4.2
Table 1: Feed-forwarddlayer constructions. "Exact?" states whether the net work realises the target function
exactly or only approximately.
Function
Definition / Behavior
Weighting
PR
Reference
Identity
passes each token through unchanged
SMAT, AHAT, UHAT SMAT, AHAT
AHAT,UHAT
Section 5.1.1
Uniform Avg.
each token outputs the of unmasked tokens (prefix-mean causal mask) retrieves the value at position each token retrieves the content position i-1
Section 5.1.2
First
SMAT, AHAT, UHAT AHAT, UHAT
D)
Section 5.2
Predecessor
(-1)
Section 5.4
(or i/n with
strict mask)
Index Lookup Multi-head Tie-break
lookup fixed index in the sequence simulate multi-headed attention with one head add tiny bias +1/(j 1) avg-hard emulates unique- hard
SMAT, AHAT, UHAT SMAT, AHAT, UHAT AHAT
Table
Section 5.3
Section 5.5
Section 5.6
Hard Attm.
simulate hard attention using soft attention and round- ing/precision limits
SMAT
Section 5.7
Table 2: Self-attention layer constructions. "Weighting" lists which attention weighting function cach con- struction works with: softmax (SMAT), average-hard (AHAT), and unique-hard (UHAT). "PE" describes the assumed positional encoding. All constructions map from (IR)) + (I2))+
Construction
Mapping
Definition / Behavior
Relevant Citations
Reference
Serial Composition
Rd + gd
f(x) = g(h(z))
Section 8.3
Parallel Composition
Rd + Rd
Apply two transformers in parallel (stack the resulting output embed- dings)
Section 8.3
Routing lemma
(Rdy+ + (R
Reorder, duplicate, or sero out en- tries in hidden representations.
Section 8.2
Induction Head
+ +
current symbol and last ae- curence was followed by B, then predict B
Elhage et al. (2021)
Section 9.1
Dyck-1
{())+ +
Recognize well-nested parentheses
Rhattamishra et (2020)
Section 9.2.1
Dyck-1-2
{{))+ +
Recognize well-nested hesent
Yao et al. (2021). Yang al. (2024)
Section 9.2.2
with maximum nesting depth of
Table 3: Assembly and example constructions. Parallel composition requires no layornorm, architectural assumptions for Induction Head and Dyck language construcctios are described text.

---

Published in Transactions on Machine Learning Research (01/2026)
Note that the above is generalized template of the transformer architecture. Specific implementation details often differ, such as the choice of positional encoding even activation functions. This architectural flexibility is key strength, as it enables extensive customization while retaining key advantages, such as support for mature training and inference pipelines. We give an overview the key components below.
2.2.1 Embedding
In order to process strings, the transformer needs to map them from sequences of discrete symbols to sequences of real-valued vectors. Let I = 2122 In E E+ be an input sequence length n. In Eq. (2), each token F2 mapped to a vector tf..e( + tf. (t,,, where tf.we: Σ + R is a word embedding and pe, + Rd a position embedding. For more on word embeddings, see Section 3.2; for more on position embeddings, see Sections 3.3 and 3.5.
2.2.2 Transformer Layers
Here, we will define the transformer layers and sublayers. For now, we have omitted layer uormalization; it will be discussed in Section
Definition 2.2. A transformer layer is function
tl: (IR4)+ 1g (R2))
tl( Zn) = (zi...., znn) where
(oI,..., Cn) = al.sa(z)...... 2n) + (Zi,..., 2n)
z, = =l.ff(c.)) + c2
i E [n]]
where tl.sa is a self-attention layer (scc below, Definition 2.3) and tl.ff is a FFN (see below, Definition 2.5).
Self-attention A self-attention layer computes weighted sums of value vectors at all positions, where the weights determined by query and key vectors.
Definition 2.3 (Self-Attention). A (scaled dot-product) self-attention layer with d input//otput dimensions and dkey key/ /value dimensions is a length-preserving function
sa: (R2 In (R*)+
with linear transformations
sa. (Q))
sa. W Rd dlay
sa. w(V; Rd + Rdd
and a weighting function
sa.S: R 1 E
is a function where, for positions and sa
2n) = (c1, ..... cn,)
where
(6)
q = sa. w(Q) 2,
(7)
k, sa. (K)) Zj
(8)
V, = sa. W(V) 23
(9)
SL = q kj
(10)
/ dhey
0g,+ Sa.S S(i,e)
(11)
C,
Vi
(12)
5

---

Published in Transactions on Machine Learning Research (01/2026)
We call the $. the attention scores, and we call the onj the attention weights. Other variations attention are used very often in theoretical papers; these are discussed below in Section 5.
Real transformers apply a linear transformation sa. ( to Ci, but this does not add any expressivity, so we omit it. Real transformers also use multi-head self-attention, but we don't use it because it can be emulated using single-head self-attention, described in Section 5.5.
In fulkre-masked (also known as causally-masked) self attention, every position is forced to attend only to preceding positions, by redefining the attention scores in Eq. (10) to the following, letting exp(-oc) 0:
9. Kj dwey
jsi
$1.j
otherwise.
Tt sometimes convenient consider strietly future-masked attention, in which case we have:
q k
j
<i
$1.j
dley
otherwise.
where it sometimes convenient to let the first position's attention weight 01,1 = 0 as a special case.
Position-wise feed-forward networks feed-forward layer computes two position-wise affine transfor- mations, with an activation function in between. Here is defined with ReLU, but other choices can be found in Section 4.
Definition 2.4 (ReLU). A rectified linear wnit or ReLU (Fukushima, 1975) is non-linear activation function
ReLU: R - Rd ReLU(x)= = max
(13)
Definition 2.5 (Feed-Forward Network). two-layer forward network or FEN or FFNN is a function
ff: _d + Rdd ff ff(x) y where h ReLU(W, + b1)
(14)
(15)
y W2(h) b
(16)
with parameters
ff. W, E Bddaa xd
ff.b, E Rddia
ff. W2 2 E ddxdua
ff. ff.bg E Rd.
This completes the definition of transformer layer. In Eqs. (3) and (4), transformer has transformer layers, each with its own parameters. After the last layer, the transformer produces output sequence (z)²). (1)) e (Rd)+. There is considerable variation in what happens next.
2.2.3 Unembedding
After the last layer outputs a sequence of vectors z (L) converts these vectors into some useful output. The most common setups are classification and language modeling.
(L) Rd. the unembedding function tf.out

---

Published in Transactions on Machine Learning Research (01/2026)
Classification In theoretical papers, it's very common to treat transformer as binary classifier, in order to line them up with computational complexity classes. To do this, we look only at the last output vector, un (Some papers, following typical usage of BERT (Devlin al., 2019) a classifier, add a CLS symbol to the beginning end of the string, and use the output that position the classification.) This vector can be interpreted using any of the Boolean representation schemes described in Section 3.1. An extremely common choice is for tf.out to linearly project the output vector down to & scalar, and to interpret positive values as acceptance and of her values as rejection:
tf. W out E Rixd
Yi = I tf. W out (2,4)) 200) 0
(17)
For multi-class classification, interpret z; (L) using any categorical representation (Section 3.2). Most commonly,
tf. W out E RR x//d
Y: argmax (t.. out (z. (2)
(18)
In language models, tfu maps each 2, (1)
Language modeling
to probability distribution over Σ:
tf. W E E Elxd
y; = softmax (ff.Wout out (2.
(19)
This induces a probability distribution over strings
y1 ... Bay given input strings x:
n
Ply x) II d
(20)
But most modern LMs autoregressive, which means that æл BOS, x; = 9:-1 for i ,,...,7, and Vn EOS. That is, the transformer takes as imput prefix of string, and outputs distribution over the next symbol in the string. Then Eq. (20) defines an unconditional probability distribution over strings.
2.3 Uniformity
In theoretical constructions of transformers, an important question is how much the construction can depend the length of the imput sequence (n), concept known uniformity. This question has practical relevance, since sequence lengths currently stretch into the millions. In this cookbook, we will observe three principles.
First, properties of a transformer not involving the parameters may depend on n. This includes:
Position embeddings can be function of n.
Numerical precision of computed values can depend on n.
Second, the number value of the parameters may depend on maximum length N. That is, for any N, there exists transformer that works all sequences of length n < N. In these cases, will state how the number of parameters scales as function of N (e.g., O(N) or O(log N)).
Third, if there is any dependence on n or N, its computational complexity should be noted (if not obvious). If unconstrained, these dependencies could allow constructions to decide undecidable languages. While such constructions can be mathematically interesting, care should be taken when drawing implications from them. Instead, it preferable to have some constraints, such as: for each N, the parameter values and positional encodings for sequences of length up to N can be computed in poly(log N) time.

---

Published in Transactions on Machine Learning Research (01/2026)
false
true
Continuous Ops.
Min. Gap
Fixed Mean
Fixed Variance
0o, 0]
00)
yes
yes
no
11
+1
yes
yes
n10
110
(-o0, 0)
(0, 00)
yes
no
no
110
0
[1, 0c)
yes
yes
110
+1
yes
yes yes
yes
+1
-8
+
yes
yes
+6
Table 4: Different Boolean representations and their properties.
3
Basic Ingredients
While transformers are length-preserving functions that operate sequences of real-valued vectors, they are often used to operate on discrete data, with much freedom how to represent these discrete values during computation. For instance, the ability to represent Boolean values integers is often crucial for tasks like formal language recognition, string transduction, and other algorithmic constructions. Here, we discuss how to represent these discrete values in a way that is compatible with the architectural specifics of the transformer. The particular methods of representation often shed light on the expressive capacity of transformers.
3.1 Boolean Representations
Boolean values are very useful and commonly used ingredient, and there are many ways represent them (Table 4). To choose representation, must consider how different parts of the transformer operate them.
Position-wise FFNs can be used to compute position-wise Boolean operations, covered in detail in Sec- tion 4.8, and also to convert between different representations. Since the FFNs compute continuous piecewise lincar functions, this rules out reprosentations like false (-o0, 0], true (0, +oo), as negation would not be continuous function. The representations false 0, true or false 1,, true +1 work fine.
Layer normalization is covered in detail Section As discussed there (Section 6.3), we usually just want layer normalization preserve truth values (false stays false, true stays true), so we can use a representation like
+1
false
true
+1
Unfortunately, there doesn't t seem to be any one representation that has all the properties we want. It may be necessary to switch between representations as needed.
3.2 Categorical Representations
More generally, we may want. to represent elements of a finite set. For example, word embeddings are repre- sentations of words drawn from a finite vocabulary, and position embeddings are sometimes representations of positions up to some finite maximum length. We refer to any such representation as a categorical represen- tation. In theoretical constructions, categorical representations should idcally be separated by minimum distance, for the same reasons noted above for Booleans.
8

---

Published in Transactions on Machine Learning Research (01/2026)
Additionally, since it's common to attend only to particular category, the categorical representations are often orthogonal. That is, they are simply one-hot vectors. To accommodate set of k categories, a width of d 2 k is required. If we are concerned about how large d is, we may be able to use almost orthogonal vectors (Section 5.3.2).
3.3 Integer Representations
Integer values are another common construction, frequently used to represent counts, indices, or other discrete quantities. These representations share the same concerns as Boolean values in transformers, but furthermore the sign and magnitude of the integers can be important, as we may need to add and compare them.
Representing integers requires greater numerical precision to represent larger integers. This means that the numerical precision of the transformer plays role in the maximum size of integers that can be represented. For more on precision, see Section 7. Since positions are integers, see also Section 3.5.
The simplest representation an integer C' is just C itself. But this representation is unbounded, and there a theorem that a transformer with bounded position embeddings and Lipschitz position-wise functions (Hahn, 2020) even non-Lipschitz layer normalization (Chiang et al., 2023), all computed values are bounded. So it may be difficult to compute values in this representation.
Instead, it's very common to see count C' stored as C/n where is the length of the input (Chiang et al., 2023) or C/i where i is the position where this integer is stored. We often end up with the former when using unmasked uniform attention to compute integer values, and the latter when using nuture-masker uniform attention. A invariant representation of integers is via the layer norm (Section 5.3.3).
Since each position has the same denominator, position-wise operations are straightforward implement using this representation. Position-wise addition and subtraction is described in Section 4.5. Position-wise comparison of integers is described-wiin some important caveats- in Section 4.7.
3.4 Special Symbols
In Scction 2.2.3, mentioned the special symbols BOS (beginning of sequence), EOS (end of sequence), and CLS (classification). Having one of these tokens in the sequence also allows transformer to compute the value I+I (or FI if future-masked by using uniform attention (Section 5.1.2).
3.5 Positional Encodings
Transformers use positional encodings as a method for incorporating information about token positions, since neither self-attention nor position-wise FFNs have an inherent representation of token ordering. The original transformer model (Vaswani et al., 2017) used sinusoidal positional encodings, but since then, many encodings have been proposed, addressing length generalization (Kazemnejad et al., 2023), relative distances between tokens (Shaw et al., 2018), well as representing tree structure in sequences (Shiv & Quirk, 2019). In this section, we focus different kinds of positional encodings and how they may affect the exprossiveness of the model. Here present scalar positional encodings, according to the definition of the token embeddingg function Section 2.2.1, positional encoding is vector in Rd. It is common to choose a single positional encoding (i.e. a vector in !R however some constructions make use multiple positional encodings in different dimensions of the emebdding.
3.5.1 Simple Positional Encodings
The value 1 Obtaining the value 1 al position can be introduced via a positional encoding, or it can be computed using a future-masked uniform attention layer (Section 5.1.2) and the presence of a BOS token. This positional encoding plays a role in the constructions of Bareclo al. (2024), Merrill & Sabharwal (2024a), and others. Additionally, as described in Section 5.6, this value may be used to simulate UHAT using AHAT.
9

---

Published in Transactions on Machine Learning Research (01/2026)
Length-averaged f Similar to above, the value 1 may also be obtained at position i using unmasked uniform attention layer Section 5.1.2 and the presence of beginning-of-seqqeee encoding can be found in the constructions of Merrill & Sabharwal (2023); Chiang & Cholak (2022); Strobl et al. (2025). One reason for using i place is that sometimes it's desirable for the position encoding to be bounded.
token. This positional
Powers of Powers of other than i-1 can also be used as positional encodings. In partieular, and j are crucial to perform certain index lookups in Section 5.3. Higher powers like 1 are used by Yang et al. (2026) in order to simulate table-lookup exactly using soft-attention. Generally, these large powers of i are used to create attention scores that scale rapidly with the sequence length, to ensure that attention can be locused on single position.
3.5.2 Sinusoidal Positional Encoding
The original paper on transformers (Vaswani et al., 2017) used sinusoidal position encodings. Suppose that the embedding dimension d is even, then for 0 S c S d
2 1, let:
pe(i, 20 + 1) = sin
M2cea
pe(i, cos
M2e/d
where M is large number, such as M = 10000 (Vaswani et al., 2017). Sinusoidal positional encodings. Using the table-lookup operation described in Scction 5.3, these positional encodings can also be used to do modulo counting to recognize PARITY, for instance.
4 Feed-Forward Layers
Feed-forward layers are a fundamental building block of transformers. Empirically, they have been observed to contribute to the expressive power of transformers (Geva et al., 2021). Here, we show how feed-forward layers compute varicty of important functions. Given enough parameters and large enough imput and hidden dimension, feed-forward layer can approxinate very large class of functions (Cybenko, 1989; Hornik et al., 1989), but here we focus on those that can be expressed exactly, with a fixed number of parameters.
Much of the expressive power of leed-forward layers comes from their non-linear activalion functions. The concept was originally inspired by the threshold- based firing of biological neurons (McCulloch & Pitts, 1943), and they were later shown be essential for allowing neural networks to learn non-linear functions, critical property for modeling complex data (Hornik et al., 1989). We focus here two popular activation functions, the rectified linear unit (ReI.U) and Gaussian error linear unit (GELU). Other notable activation functions include sigmoid, softmax, hyperbolic tangent, exponential linear unit (ELU), and gated linear unit (GLU).
Recall (Definition 2.5) that a FFN has the form
FFN(x) = WaReLU(W xx + bi) + ba
In the following constructions, we will specify for cach FFN the parameters WT, W2, bı, and by, which can be plugged into Definition 2.5.
4.1 Continuous Piecewise Linear Functions
ReLU FNNs may be used represent any continuous piecewise linear function made up of finite number of linear segments (pieces). We first define such functions follows.
Definition 4.1 (Continuous Piecewise Linear Function). Let X C Rd. A function f: X + R is continuous
piecewise linear (CPWL) if there are closed polyhedral subsets X1...., X, S X such that Usejo X, = X. and for all i [m), fl flx, is affine.
10

---

Published in Transactions on Machine Learning Research (01/2026)
For the univariate case (d = 1). let f: Y:R- R be CPWL. Assume that f has 2 2 pieces (of which the first and last extend to infinityy and is represented by < < In++1 and y1...., U0+1 such that f(zx) = yk for k = L,.., n + 1. Points (22: 12) to (Inz Mv) are the "knots" of f. while points (f1,91) and (Ix+1 Mx+1) lie in the first and last piece.
The main idea to concatenate a sequence of ReLU components at these knots, such that each component approximates one linear piece of while "undoing" the effect of its immediate predecessor. Specifically, we first rewrite as:
f(x) y1 mi (x x1)
mg m& ReLU x.))
11 mi (x 21),
x S 22
Us m& (z kk),
2b S S Ik+1
V/ mn(a In),
I 2
where mi...., are the slopes defined as:
my yk++ Uk
for k 1,
3k+1 Tk
This is achievable with the following FFN of hidden dimension n
0
-22
f.W1
f.b
n copics
-33
Tn
f.W2 = [-m] M (m2 mm1)
(m, mn-1))
f.b2
[V1 m1
For the multivariate case (f: Rd IR), any CPWL. function with k pieces be computed exactly by FEN with (log k) layers (Arora et al., 2018); we don't reproduce this construction here, but below, show some cases that can be computed in two layers.
4.2 Canceling Residual Connections
As noted above, an FFN f: Rd + d is normally used with residual connection, y f(x)+ +x. Sometimes, we don't want the residual connection, and fortunately, it's always possible to cancel it out (Chiang et al., 2023). That is, there is an FFN f' with parameters
fW 1 I
f.bi 0
F.W,
f.b,
-I
0
W. [/.W2 -I 1
f. f.b2
so that = fxx + f(x); that is, f' with residual connection behaves like f without a residual connection. From now on, we assume without loss of generality that residual connections are optional.
4.3 Identity Function
We very often need an FFN that does nothing, either because we need two self-attentions in a row or as a building block for the other constructions below.
id: Rd - T
id(x)
11

---

Published in Transactions on Machine Learning Research (01/2026)
If residual connection is present, then this is straightforward: zero out the FFN and retain only the residual connection. In particular, the zero FNN is defined as follows:
zero. Wi zero. W2 Oaxd
zero.b, zero. b2 Od:
Then, when combined with a residual connection, the zero FNN satisfies the identity + zero(z) r.
If a residual connection is not present, however, then some encoding is necessary. We first consider the simplified case embedding dimension 1, in which case we set:
[-]]
id. W.W
id.b;
(21)
id. W2 This constructs the identity FFN, as would expand as:
[1 -1] id.b O.
id(x) ReLU(()) + ReLU(-zz)
To generalize this vectors in Ra 2 1), we may use parallel composition (Lemma. 8.3) and routing (Lemma 8.1) to stack d copies of this construction into single FFN:
I -I"d
id. W
id.b,
02d
(22)
id. W2
[
I
id.b3 0₂
In general, we will state constructions using scalars when vectors are not necessary, but they be gener- alized to vectors have done here.
4.4 Min and Max
It is often desirable to compute the minimum maximum of two numbers:
min, max: R x IR - IR
min
min(x, y)
y
[
max
max(x; v)-
y
These functions are CPWL, there exist FFNs to compute them:
0
min. W, =
-1
0
min.b; 0
-1
min. W [1
-1
min.by b2 0
0
max. W = -1 0
max. bj 0
-1 1
max. W = -1 1]
max.by b2 0
Then
min
ReLU(xx) ReLU(-x) ReLU(x y) = ReLU y) min(x. y)
y
max
ReLUUx)) ReLU(-x)) ReLU(y x) = ReLU(y x) max v)-
y
12

---

Published in Transactions on Machine Learning Research (01/2026)
Note that this construction maps from IR to R'. If one wishes to make the input-output dimensionalities the same, then we may pad the output weights with zero-valued rows. For example, to make the out of max component in IR²,, we may zero-pad the output weights to shape max. W2 E I22x3 and max. E RR Similar padding ideas can be applied to other constructions to enforce desired dimensionalitics.
4.5 Addition and Subtraction
Addition (or subtraction, or any linear function) is an easy extension of the identity (Eq. (21)).
add: R x R + R
add( y) = x + y
-1
0
add. W
add.bb 0
0
0
-1
add. W2
[1 -1
-1]
add.b2 0
Then
[z] y
add
ReLU(x) - ReLU(-x) + ReLU(w) - ReLU(-u) = x +
4.6 Multiplication
Multiplication by constant is easy (use the identity recipe (Section 4.3) with the routing lemma (Lemmaa 8.1) to premultiply postmultiply by c), but multiplication of two activations only be approx- imated, and requires an activation function with nonzero second derivative (Akyürek et al., 2023, Lemma 4). Feng et al. (2023, Lemma C.1) give a similar approximation.
mul: R x
R
R
mul
gr Rs Ty-
y
What we ideally want is quadratic activation function. Here, we the Gaussian Error Linear Unit (GELU), which is used in modern transformer architectures like BERT (Devlin et al., 2019) and GPT (Rad- ford et al., 2018). It is not exactly quadratic, but we can think of it as an approximation of its second-order Taylor approximation, which is.
Definition 4.2 (GELU). A Gaussian error linear unit or GELU (Hendrycks & Gimpel, 2016) is a non-lincar activation function
GELU: Rd + Rd
GELU(x) = x (z)
(23)
+ erl
(24)
2
-2
VV (ar 0.01471677)
1 lauh
(25)
2 x siggmoidd
(26)
where is the cumulative distribution function of the standard normal distribution, erf is the Gauss error function, and sig 1/(1 + =-*).
13

---

Published in Transactions on Machine Learning Research (01/2026)
c= 0.5
1.0
C 2.0
c= 10.0
ReLU GELU
ReLU GELU
ReL.U GELU
ReLU GELU
Activatton
2
Activation
Activation
2
Activatiion
2
-2
-2
2
-2
-2
X
Figure 1: e GELU(CE) (e) for sulficiently large c <>> 0. Many of our ReI.U-based constructions can thus be implemented with GELUs given appropriate scaling and error analysis near the origin.
The approximations (25) and (26) are from Hendrycks & Gimpel (2016). PyTorch implements a choice between (24) or (25).'. While GELU a popular activation in real-world transformer implementations, ReLU remains popular for theoretical analysis as it is a simpler function. In particular, it is possible to use GELU to approximate ReLU by noting that (FLLU(())) = ReLU(x) for sufficiently large e O, see Fig. 1, which occurs because:
GELU(Ct) c cz x(cc))
(27)
where note that the scaled Gaussian CDF + ((cr) approaches a discrete step function in the limit:
1, 2 0, lim ((cx) c-+00
(28)
0, < 0.
Regardless of whether GELU is defined as Eq. (24) or Eq. (25), we have
2
GELU(:) = V2x
+ R(z)
where the Lagrange remainder term is, for some E [0, 2/1
R(2) = GELU" (5) 6
R[2)] < 1213
From this, we can derive
GELU(>+ +)) GELU(>) GELU(s)) xy + +
where the error is
1 le(x, v)1 $ 7 (|x) + 1
Thus we can construct an FFN with GELU activations (implemented using the first terms fo the Taylor expansion) and the following parameters:
1
mul. W, =
1 0
mul.b; 0
0
1
mul. W₂ =
mul. by = 0.
httee////.psthaaer////////ssasss ......nnn............. GELU.html
14

---

Published in Transactions on Machine Learning Research (01/2026)
4.7 Comparisons
Binary-valued comparisons (=, <, S, etc.) are not CPWL because there is a jump from 0 to 1. However, we may approximate them using FFNs. If some position-independeen and Length-independent tolerance is known apriori, we may construct these FFNs as follows, where below we specify the intended behavior, show its implementation FFN weights, and give a visualization plot.
0
x h 0
GTZero.(x)
x/e
0 < x <
1
(29)
[
0
GTZero,. W
GTZero,.
1
-c
GTZero,. W2
[1/e -1/e]
GTZero..bz
-5-6
GEZ
1+ (x/e)
<<<I<0
1
5
(30)
GEZero,. W
GEZero,. 0
GEZero.. W2
[1/e
-1/e]
GEZero..bz
| 2
EqZero,(z)
1
lx/d
0
1
== 0
1
(31)
EqZero. W1
EqZero,.bb
0
-c
0 6
EqZero W2
[1/e
-2/E
1/e]
EqZero,.bz
We emphasize that. the above constructions compute exact comparisons only for some inputs. Inputs where the construction does not work as intended are shown in gray and are to be avoided.
Alternatively, if the desired threshold e input-dependent, and we are also willing to accept values as small 2 "true", then may the following e-parameterized constructions:
15

---

Published in Transactions on Machine Learning Research (01/2026)
0 zΣ0
GTZero(z,e)
< x <e
E5T
(32)
1 0
GTZero. W =
GTZero,.br =
1 -1
GTZero,. 2
-1]
GTZero,.bz = 0
x S -
GEZero(z, e)
I+C - << x <
0 S x
(33)
1 17
GEZero. W1
GEZero.b; bj
GEZero. 2 =
-1]
GEZero.bz b2 =
0
a 2
EqZero c)
E - |a|
< xx| <
(34)
EqZero. W
EqZero.b,
-1
EqZero. W₂
[1
2
EqZero.b
Similar to the input-independent constructions, input values where the computation not exact are shown in gray and are be avoided.
4.8 Boolean Functions
In this section, we show how to compute arbitrary Boolean functions using single feed-forward network. We show the construction for true = 1, false = (see Section 3.1). This is probably the easiest case, but the others are not much more difficult.
If we are not concerned about depth, the connectives A, V, can be computed by FFNs with ReLU activations. Conjunction (A) is equivalent to min, disjunction (V) is equivalent to max, and logical negation
(-) is just z1
But we can also pack an arbitrary Boolean function Φ: (0, 1)m + {0.1) into single two-layer FFN. The easiest (not necessarily the most efficient) way to do this is to list out all the possible inputs and outputs of f. There are 2d possible truth assignments to the variables 21..... Zmi number them Eo. : E {0, 1)m. That is, [Ex] is the i-th bit k; and Ex is the number of variables that & makes true.
(2E0- - 1)T
- +1
(261- 1)
1 11 G +1
ff.. W,
(262- 1)
E +1
(35)
(262m-1 T)T
1 +1
m
ff.. W2 [ó(En) ... 6(f2m_1)
ff bb = 0.
16

---

Published in Transactions on Machine Learning Research (01/2026)
We want hg to test, for each truth assignment Êk, where &x- Consider the vectors (2Ex - 1) and (2x 1).
whose entries are all +1: they are equal if and only iff their dot-product is m. So we want
(250 - 1) (2x 1) (
h4 ReLU
(252m-1 - 1) (2x - 1) - m2 1)
26n x - x 1 - 50 1 ++1
= ReLU
252m -1 X x 1 m
+ 1
(2 - 1) x - 1 60 +
ReLU
(25mm-1 1) -x 1 62m -1 ff. + f1g.b)).
Then the second layer tests any truth assignment & makes ø true:
y Σ o(Ex) he
Σ ((Ex) x]
(xx).
4.9 Conditionals
Suppose we want to compute the conditional expression
if if p 0.
if v. v)
We assume that x, [0, 1], but the construction is easily generalized for any bounded interval. We adapt construction used by Pérez et al. (2021, Lemma 11) and Merrill & Sabharwal (2024a, Theorem 1).
1 07
if.b 1
if.WW
-1 0
0
if. W₂
1
1]
if if.b 0.
Then
if
ReLU(z) + ReLU(y 1)
0
if
ReLU(x - 1) + ReLU(y)
5 Self-Attention Layers
Attention layers are the fundamental ingredient of transformers, allowing computations across positions the sequence a parallelizable manner (Vaswani al., 2017). The original motivation for self-attention was compute the relationships between source and target words in machine translation (Bahdanau al., 2015), but since then the mechanism has been trained to perform huge variety of different tasks. In this
17

---

Published in Transactions on Machine Learning Research (01/2026)
section primarily explain how attention can be used to retrieve information from different positions in specific ways.
While attention layers were defined in Definition 2.3, there are additional design choices that can be made for the ease implementing particular constructions, which we detail below.
Attention Masking While transformers are typically implemented using future- future-masked masked attention with masking, in past-masked attention, we have
q kj v dkey
j 220
8ij
otherwise.
Weighting Function The weighting function S: R+ 1 R+ computes the attention weights oi, based
the attention scores Si, A common choice is the softmax function:
[softmax(s)....... -k=1 e
But we consider several alternatives below.
Hard Attention In hard attention, the attention weights are assigned to focus all attention on the maximum-scoring position or positions.
Definition 5.1 (Hardmax). The leftmost, rightmost, and average- hardmax functions are defined as follows. For any sequence of scores (Si,..., s,); let
(ss) eie [s|]] s; maxs]
be the of indices of maximal scores. The lhardmax and rhardmax functions return a one-hot vector with the position of the leftmost or rightmost maximal element, respectively:
[lhardmax(s)]:
T(i = min [s))
(rhardmax(s)]: Ili max ((s)).
The ahardmax function pays equal attention all the maximal elements:
lahardmax(s));
[[(s) [[i e [(s)].
most-hst- attetion was previously called hard atlention by Hahn (2020) and unique-hard atlention by Hao et al. (2022). One may also consider rightmost-hait attention, in which the rightmost maximal element is used. Average-hard attention was also called hard attention by Pérez et al. (2021) and saturated attention by Merrill al. (2022), and has been argued to be a realistic approximation how trained transformers behave in practice (Merrill et al., 2021). Neither type of hard attention should be confused with the concept of hard attention used in computer vision (e.g., Xu et al., 2015).
5.1 Trivial Cases
These trivial cases are the most basic ways attention layer process sequence information: leave it unchanged, aggregale them uniformly.
5.1.1 Identity
We start with the identity function,
I 1n IR+
id:
id(x) x.
18

---

Published in Transactions on Machine Learning Research (01/2026)
As with FFNNs (Section 4.3), the easiest way to compute the identity function is to use the residual con- nection, by setting the value vectors to zero:
att zero Ze..ze.W (
att zero W(K
att zero zer.zerr... W(V)
Then, the residual connection will pass the input through unchangod.
id(x) = att _xroeero((x)))))) +x.
5.1.2 Average
We can atlention to implement averaging of vectors or scalars, as follows:
Avg, Avg.: (R.*) In (R-2)+
Avg(xI, X2, Xxai
Xk for i [N]
k=1
(x), Xn)i
Xx for b [
We can make each position attend uniformly to all (unmasked) positions by setting the query and key matrices to zcro.
Avg. ( = 0
Avg. (K)) = 0
Avg. ((V) =I
And Avg. is defined the same way, but uses future masking. For Avg, all positions receive the same value irrespective of For Avg,, we output the average over all previous positions.
5.2 First
We can construct an attention layer using positional encoding (-1)' and an FFN layer to implement a first predicate, which I at the first position and 0 everywhere else. This allows us to distinguish the first position and compute the value 1/i in every position while only using the positional encoding (-1)², which are useful for technical constructions Yang et al. (2026).
first: IR 1g RR (-1)")
= (-1))),).....))))
01,),
To mark the first position, we just need to use uniform future-maskod attention.
first. (Q) 0
first. (K() = 0
first. ((V) = -1
If = 1, then only the first position receives attention, and then the output value e, is 1. If > 1, then the attention output is the average of -1's and I's, and so will always be at most 1/3. Finally, we can map values in [o, 1/3] to 0 via a comparison operation GTZero - 1/3), slightly modifying the construction for GTZero by modifying the bias term and output sign (Section 4.7).
5.3 Index Lookup
Theoretical constructions of transformers often require a query to focus on a single position in order to retrieve data from that position. In this section, we will discuss how one can perform this retrieval from specific positions via the attention mechanism.
Assume that at each position [n), we have:
19

---

Published in Transactions on Machine Learning Research (01/2026)
Approach
Map
Width
Requirements
One-hot
(R4N+1)+ 1 R
(NN)
one-hot positional encodings
Almost-orthogonal
(R2m+ly+ 1 R
(log N)
near-orthogonal positional vectors
Layernorm-hash
(R²)+ + L RR
(())
Selective layernorm
Quadratic maximization
(R²y+ R+
((1)
positional features j and je where E N
Table 5: Summary of attention-base based index-lookup implementations.
a query which is (an encoding of) a position, that is, E [n],
(an encoding of) i itself, and
value et.
An inder lookup is a self-attention layer in which each position i attends to position gi, making it possible to retrieve Ey at each position i.
The following implementations of table lookup have form similar to:
lookup:
(R2)+
1 R
lookup
(Ugr..... Dg..)
U1
Un
These implementations use average-hard attention; however, in Section 5.7 we will discuss ways to make these implementations work with soft attention as well.
5.3.1 One-Hot Encodings
A naïve approach to maximize attention weights at desired position is to encode positions one-hot vectors CI...., eN E R.,, up to maximum length N.
ohLookup:
2R2 13 R
eq:
eyn
ohLookup
Ci
Cn
(U
Vga)
U1
Un
The query, key, and value projections are set to
W INN
N
Nx
W
OONNN
NNN
Nx
WIV) OOXXN
O 1]
so that, at any position i,
Eqi e;
Ogg ej
q. (QQ)
ey.
k, (K)
=
V, vy= = (VV)
e,
Uj.
(36)
1/
1/
1/
Then the dot products satisfy q: - k, eyg e, Lpi = 4)- With hard attention, this suffices to concentrate all attention on j = 4:- This realizes the lookup task with width 2(N).
With soft attention, the lookup will be only approximate, but note that there a minimum gap between the highest attention score and the highhs attention score of y = In Section 5.7, we will discuss how to magnify this gap enough to correct the approximation error.
20

---

Published in Transactions on Machine Learning Research (01/2026)
5.3.2 Almost Orthogonal Embeddings
The one-hot approach forces the embedding width to be at least ((N). To mitigate this, we can use almost orthoyonal vectors (Bhaltamishra al., 2024; Sanford et al., 2023; 2024a) to obtain width Ollo N). family of vectors ; R" is almost orthogonal if, for some small > 0,
X x S (1
X; x; 2 1
(37)
One can pack exponentially many, exp()((m)) such vectors (Vershynin, 2018, Chap. 3) into m dimensions. A straightforward way to construct such vectors is: Given
maximum error >> 0,
a maximum length N, and
maximum probability of failure 8 > 0,
set constant k such that the probability of failure No S 8 and, take positive integer mn as,
12k log(2N) 2
O N).
(38)
Then, if samples XI. E (+1//m}m uniformly and independently, then with probability
most - 6, these vectors will satisfy Eq. (37).
The construction of these almost orthogonal vectors is also equivalent to taking the MaansoonLindenstraane (JL) transformations (Johnson et al., 1984) of the N ono-hot vectors. To avoid storing ((N) vectors explicitly, one can use a derandomization of the JL lemma (Sivakumar, 2002) to generate them in log-space. Such near- orghoglnal families have been used in constructions for sparse averaging (Sanford et al., 2023), string equality and nearest-neighbour algorithms (Bhattamishra al., 2024), and graph algorithms (Sanford et al., 2024a).
Then we define
(R 2m++ 1g R
aoLookup:
Xyy
Xgn
aoLookup
X1
Xn
(U ( Uga):
U1
Un
where the family {xi,..., xN) satisfies (37) with m Olog N).
The query, key, and value projections are in Eq. (36), that for any position i, by (37), the attention dot products satisfy
2 - if gi:
q k, = Xg:
SE
if + qi.
Taking = 1/4 for simplicity, we have qi kj 2 3/4 for j = qi and qa k, S 1/4 for j + 4: Under hard attention, the output at position is then exactly Vg..
With soft attention, the attention weights are nonzero at all positions, so the retrieved value will only be approximate. The minimum gap between the attention scores q, kg. and qi ky for qi is 7 = - 2c. In Section 5.7, we will discuss how to magnily this gap enough to correct the approximation error.
5.3.3 Layernorm hash
Another way to implement table lookup to encode positions by their layer-norm hash (Merrill Sabharwal, 2024a; Yao al., 2021). Merrill & Sabharwal (2024a) use table lookup simulate a Turing machine tape with chain-of-thoughtt transformers: specifically, to retrieve the last value written to previous index
21

---

Published in Transactions on Machine Learning Research (01/2026)
the tape. Merrill & Sabharwal (2024b) use it to implement a binary tree construction with log-depth transformers.
IhLookup: (R²)+
1 R
[ Ih(11 U1
Th (n))
1hLookup
[h(n)
(w
Ugn) )-
Up
IhLookup. ((Q)
[
04x4
0
LoLook W(K)
[04x4
I4x4
04x1]
IhLookup. W(V) [O1X4
0
1]
Let LN be a layer normalization with LN.e= 0, LN. = 0, LN. = 1. Merrill & Sabharwal (2024a)² store an integer x as
2
1
Ih(x:) LN
x
+
-1
The layernorm hash is scale-invariant in the sense that 1h(kxr) = [l(()). So even if we're only able to compute z/i and 1/4 (as is common when counting positions using uniform attention), we can still compute 1h(x)) as
2
1/6
1h(x)= LN
22/ i
1/2
If, for all >>>000000 O, we can compute queries and keys
q 1h(())) LN (1
1 - 1/i
9/í -////
1
1/j
k, = 1l(()) = LN
-1
1/j
then the dot product 8i. q: k, Ih((;)) Ih(5) is uniquely maximized when attention, this allows us to attend only to position = %. after which the the value of uy can be retrieved by appropriately setting W(V). But because the minimum gap between the score at the desired position Si., and the score at other positions decreases with n, a considerable amount of error accunulates when approximating ths construction using soft attention Section 5.7.
j. Under hard
One problem is that the residual stream may store other values besides the ones shown above, but standard pre-norm is applied to all values in the residual stream. Then Ih will incorrectly be scaled by some factor that may be different at each position. So we need the ability to selectively apply LN to just four components of vector. We can do this if we use pre-norm and modify the architecture by inserting linear transformation W(N) before the layer normalization:
y = saNNNL + x.
The linear transformation (N), which can be restricted to diagonal matrix if desired, can mask out information encoded in the residual stream that is not relevant at this layer, allowing the network to compute the layer-norm hash a specific value.
Merrill & Sabharwal (2024a) slightly different formula LN, but this only changes the construction by factor of 2.
22

---

Published in Transactions on Machine Learning Research (01/2026)
5.3.4 Quadratic Maximization
Barcelo et al. (2024) include j and j² in the position embodding, allowing table lookup as follows:
qmLookup:
(R²)+ + 1
R
q1
Q2
On
1
1
qmLookup
2
(Ugy+ Ugas-... Ugg
1
2
n²
U/2
Un
qmLookup. ((Q) (
1
0
0
0
0 0
0
0
0
qmLookup. W
0
0
2
0
0
0
-1
qmLookup. w
[O1x4
Then the queries and keys are
[g
2j [-j
ky
Their dot product St, 2q--- which is uniquely maximized when j = q:- This is true even if either q or kj is scaled by some factor (for example, 1/i or 1/n). Under hard attention, this solves the lookup problem exactly.
Under soft attention, the lookup is only approximate. But the minimum gap between the score at the desired position 8i.g and the score at any other position 8i, (j * q:) is ? = 1, and we will discuss in Section 5.7 how to magnify this gap enough to correct the approximation error.
5.4 Predecessor
The predecessor function is the special case of index lookup where each position attends to position i- 1, and the first position always outputs 0. The construction could be generalized to output default value other than 0, even output the original value in the first position. The index lookup methods of Section 5.3 can be used to do this; in particular, using quadratic maximization (Section 5.3.4), W and W(Q) can be set so that 8ij is 2(i - 1)j - ja. Then, the first position can be set to O using the construction from Section 5.2 the positional encoding includes (-1)
In this section, we present two alternative constructions. First, we present one that uses a simpler position encoding but potentially requiring more layers. Here, Then, we present simpler construction which takes advantage of strict future-masking and does not require values to be in [0, 1].
that the values vi bounded to [0, 1].
pred: (R² x [0, 1)) 1|+
pred (-1)² V1
(-1 1
(-1)" (0, en Un-1). 1)-
Un
This can be achieved by rightmost UHAT with positional encoding (-1)². We compute the predecessor at positions i >> by making cach position i attend only position (i (i- If 1, we output Ó. If odd (and greater than 1), we make the attention scores greater even positions, so that rightmost tic-breaking selects position 1). If is even, make the attention scores greater at odd positions.
23

---

Published in Transactions on Machine Learning Research (01/2026)
To do this, we two future-masker attention layers (or one layer with two heads). The first is:
pred.odd. W
pred.odd. (red.odd.Wr(k) 0 1 0] pred.odd. w(V) [o
If is odd, the result of pred.odd is 0--1- The second attention head is defined similarly:
pred.even. ( 0 o] pred.even. W -1 0] pred.even. W(V) [0 0
Now i is even, the result of eved.even is 0--1-
At each position i, check if i using the construction in Section 5.2, and we check if i is even using GTZero, ((-1)²) After that, because the v/ are bounded, we can use a conditional (Section 4.9) in order to select the correct result either from pred.even or pred.odd:
pred kn)) = if((TZero)((11)), pred.even(Z). ..neen) pred..d((...... zn)))
This construction is similar to the one in Barcelo et al. (2024) using AHAT, and we note that Yang et al. (2026) demonstrate how this can be simulated using SMAT, if the values are bounded.
If we choose to use strict future-masking, then predecessor look-up becomes considerably easier. This is because for any position i, the attention weight will only be non-negative positions j In particular, it suffices use positional encoding of i/n along with AHAT. Then, letting the attention matrices act the i/n positional encoding, the i position will automatically be selected by AHAT as it will be the largest among the sequence AHAT(I/n,.... (i 1)/n, O,....0) 0), where note that the value i/n is not present because the attention is strictly anture-masking If we use rightmost tie-breaking and UHAT, the construction is even simpler; set the attention matrices to O, and since the attention weights will all be equal, rightmost tie-breaking (with strict future-masking) will directly select the predecessor position.
linear projections
5.5 Simulating Multi-Head Attention with Single-Head Attention
The result of a multi-headed attention layer with H heads with daia key/value dimensions per head is the concatenation of resulting vectors from separate attention heads. this way, an attention layer with heads can be simulated by single-headed attention layers, and the results summed together at the end using Scction 4.5.
5.6 Simulating Unique- Hard Attention with Average-Hand Hard Attention
When using average-hard attention, sometimes we want to be able to simulate leftmost unique-hard or rightmost unique-hard attention. To do this, we have add tie-breaking term to the attention scores that decreases or increases (respectively) with the position. However, care must be taken make the tie-breaking term big that non-maximal attention score becomes the maximal attention score.
Suppose that we have atlention scores computed from queries and keys as follows:
qi k,
81j
V /deey
and we know that there exists 7 > 0 such that for all i,j, either
8 = max 8ig or 8ij max 8:g' 7-
(39)
24

---

Published in Transactions on Machine Learning Research (01/2026)
First, depending on the desired form of unique-hard attention, the appropriate tie-breaking term t can be chosem:
rightmost
leftmost
t() =
j
rightmost
leftmost
Second, the appropriate y must be chosen to satisly Eq. (39). Then, we add additional dimensions to the input embedding so that y and t(i) can be stored in each position. Thus, an input of [x] at position
x
becomes
?
Then, the tie breaking term is added in to the scores sig = ssg + yt(i) by setting the key,
((1)
query, and value matrices as follows:
WiQ
QQQ) 0
0 1 0
W(K)
()Q) 0
0
wiv [w(V) 0 o].
5.7 Simulating Tieless Average-Hard Attention with Soft Attention
Many of the above constructions are exact under average-hard attention but only approximate under soft attention. In particular, to perform index-lookup operations, attention has to be concentrated on the single query position. With hard attention, 100% of the score can be concentrated on the query position, with soft attention this is not possible, because every position receives positive attention. This causes error when approximating hard attention using soft attention.
The amount of error is based the gap y between the highest attention score and all other attention scores. We have noted, when appropriate, what the minimum gap y will be in many constructions. In this section, we discuss how to correct this error if y is known.
One way to correct the approximation error is using limitedpprecision arithmetic. we multiply the query vectors by a factor 1/r large enough that exp exp-7/t -7/r rounds to zero, then softmax becomes exactly equal ahardmax and soft attention becomes equivalent to average-hard allention.
When want to unbounded precision, will also need the factor 1/r to depend the sequence length. This results in non-uniform construction (sec Section 2.3). In index-lookup operations the score is always highest on single position, condition which we give a special name to.
Definition 5.2. For any vector IR+,, let M max; 8,. We say that tieless if Hi s; = M) = 1, and has gap y if for all i such that 8; M, we have s; < M 7.
I is tieless, then Ihardmax(s)) = rhardmax(s) = ahardmax(s), and we write hardmax(s) for all three. In the rest of this section, we assume s will be tieless, as it would be for the typical index-lookup setup Section 5.3.
Lemma 5.3 (Edelman et al. 2022, Lemma B.7). Let Ss) be attention scores and let j E [n] and 7 > 0 be such that for all # j we have 83 < 85- 7- Then
|| hhadmma(s)) softmax(s)]l < 2ne
When we do not want dependence on the sequence length, we can assume that v (0, 1} for all E [n]. and that there maximum length N. The idea to keep the error small enough that we can round the retrieved valued correctly to either or
25

---

Published in Transactions on Machine Learning Research (01/2026)
Let W(o) (())) where 1/olgg If we compute attention scores using W(Q) instead of W get - (1/T)q kj, and the minimum gap is now 8og&N instead of y. Let a aN [0, 1] be the resulting attention weights at position i. The output of attention at position is
N
C, Σ
0vV3 = Va: +
Σ aj%j
==1
j7g
c Ug: (1 Ogge) + Σ O3j
579.
2Ne
(by Lemma 5.3)
1
4
So c; S. 1/4 if Vo. and c; 2 3/4 if Vq. =1 (Bhattamishra al., 2024, Thm. 1). Thus, the value can be rounded to 0 or 1 using 2-layer ReLU FFN, namely, /TZero1/2(C; - 1/4).
Sometimes we can do better; in particular, Yang et al. (2026) show how this can be done with quadratic maximization without assuming a maximum length N.
6 Layer Normalization
Layer normalization (Ba et al., 2016), or layernorm for short, is normalization technique originally proposed for the purpose of reducing training time.
Definition 6.1 (layer normalization, Ba et al., 2016). A layer normalization is a function
LN: Rd + Rd
I3 P
LN(z)
LN. LN.3
Va2 + LN.s
/ Σ 34
d
0²
= Σ
(xt 11)
[=1
where L. LN.B E Rd and LN.s > 0 is small constant for numerical stability.
The original transformer model (Vaswani al., 2017) used layer normalization (or layernorm for short) after each sublayer and residual connection. It has since been shown have an impact on the expressiveness of the model, for example, by affecting the Lipschitz continuity of the model (Hahn, 2020) and the ability to express certain attention patterns (Brody et al., 2023). In theoretical work, layernorm in some cases may complicate the proof, and in other cases may be an essential component of the proof. In this section, we discuss the theoretical aspects of layer normalization and how the literature on expressivity proofs has treated it.
6.1 Relevant Properties
The use of layer normalization can affect the sensitivity of a network with respect to its inputs. Understanding how sensitive a network to small perturbations in its input is crucial for analyzing its stability and generalization. The property of Lipschitz continuity provides a formal way to bound this sensitivity, and is useful in analysis in adversarial robustness (Zühlke & Kudenko, 2025), generalization (Bartlett et al., 2017), and expressivity (Chiang et al., 2023).
Definition 6.2 (k-Lipschitz Continuity). A function f is k-piscchitz continuous if for all X1, X2, (x [xx)]] k||x; Xa|l-
26

---

Published in Transactions on Machine Learning Research (01/2026)
In simple terms, k-Lipschitz continuous function cannot change arbitrarily fast. Since every operation in FFN (matrix multiplication, addition, and the ReLU activation function) is itself Lipschitz continuous, their composition is as well. We discuss below how layernorm may break the Lipschitz contimuity of a network.
Another important property, particularly for FFNs without bias terms, is how the function's output scales with the magnitude of its input. This scaling behavior is captured by the concept positive homogeneity. Definition 6.3 (Positive 6-homogeneity). A function is positively k-hoomggeeous for all x and 2 0, f(ex)= fxx).
This definition states that scaling the input vector by non-negative constant results in the output being scaled by ct. For standard FFN with ReLU activations and no bias terms (i.e., ff.b, ff.b 0), the function is positively I-homogeneous (or "linear" in its scaling behavior). This is because ReLU((c)) c. RcLU(z) for all c 0, and this property is preserved through the linear transformations of the network. If every layer of network is 1-homogeneous and the output scale-invariant, then layernorm will not affect the network.
6.2 Post-Norm vs. Pre-Norm
The original definition of the transformer used what is now known as "post-norm" architecture, where layer normalization is applied after each residual connection:
y = (x(
where f either a self-attention or FFN.
This is in contrast to the "pre-norm" architecture, where layer normalization is applied before each residual connection:
y= f(N(xx))) +x.
Additionally, the final layer followed by one more layer normalization.
The pre-norm architecture is currently the standard. This is because the post-norm architecture has problems with exploding gradients, making training unstable, which the pre-norm architecture does not (Xiong et al., 2020). Some constructions, however, still use post-norm (Chiang & Cholak, 2022; Chiang et al., 2023; Hahn & Rofin, 2024; Yang & Chiang, 2024).
6.3 Circumventing Layer Normalization
Some theoretical constructions simply omit layernorm, and some constructions don't do anything useful with it, but simply try to circumvent it. We can't circumvent it completely; the best we can do is the following.
For any layernorm LN with LN.3 = 0, for all x,
(
x
cx
LN
for some That is, if the components of vector come in pairs that additive inverses of each other, then it has zero mean, so the layernorm LN can only scale the vector.
6.4 Sign Function
Hahn (2020) showed that if transformer's position-wisd operations all Lipschitz-continnn and its position embeddings are bounded, then it also has the Lipschitz-like property that change in a single imput symbol can only produce a change of O(1n)) in any output activation.
But layer normalization LN is Lipschitz-continunt only LN.e 0; (as originally defined) LN.e = 0, then LN not Lipschitz-continmuus,, possibly allowing the model express more complex functions. For example, Yang Chiang (2024) use layernorm with LN.c order to compare numbers (like in Section 4.7) via computation of sign function.
27

---

Published in Transactions on Machine Learning Research (01/2026)
Here, explain how layernrom can be used to compute the sign function (here, the computation outputs 0 on inputs of 0). The primary challenge is that layernorm cannot be used only on selected components. In order to use layernorm to compute the sign function, we have to clip all components to be in {-8,ó} and ensure the entire vector has mean O. Let x E Rd be a vector with | 2 å for all E [d]. First, we ensure the vector has mean by doubling up the dimensions and negaling every other one. A vector X1, x2.... Xn
thus becomes -X1, X1, -X2 X2..... -n, Xx. We can construct a FFN that clips all activations to +ō using the following weights and biases:
clip3: IR + IR
[
clip, W
clip,.b, bi
[
-
clip3. W2
-1]
clipg.b;
-68
Applying layernorm after this FFN will normalize all activations to +1.
LN: R R
LN.E 0
L = 0
LN.y =
7 Rounding and Approximation
7.1 Rounding
Transformers as defined Sention 2 operate over real-valued activations, which sometimes comes tension with the discrete tasks we expect them to do, such as simulating finite automata or logical reasoning. One way to address this is to enforce rounding to fixed-precision. This may not be cause for objection due to the fact that transformers are implemented using fixed- precision in practice (say 32-bit floating point for example). In this section, we describe how rounding can be used as mechanism, and how it may be handled via approximation.
7.1.1 Comparisons
In Section 4.7 we saw that a FFN can simulate a step function up to fixed tolerance
If values smaller than were rounded down to 0, this would permit exact simulation of step function.
This could be scaled up to perform comparisons exactly.
7.2 Error Analysis
While transformer may sometimes be unable exactly implement a discrete operation, it can often approximate the operation very closely. When transformer construction makes such approximation,
28

---

Published in Transactions on Machine Learning Research (01/2026)
can bound the error using the following results. Below, ||-|| around matrices is the operator norm. For simplicity, one can use the Too,1 norm instead,
,l Σ max |Aul
Proposition 7.1 (Bounded activations, Hahn 2020, Chiang et 2023). Let tf be a transformer with (t) for all and E [n]. Even tf contains layer normalization LN with LN.e 0, there an X such that for all and i, we have ||z S X. Proposition 7.2 (Error analysis of FFNs). If || x1| S 6 and ff a ReLU FFN, then there constant K such that
[|f(()) - ff(x))l S K6.
Proposition 7.3 (Error analysis of attention, Yang et al. 2026). If ||*| S | x < and sa is self- lefffattention layer, then there is a constant K such that for all i,
[[[sa()]]: [sa(x)]<ll S K8.
Proposition 7.4 (Error analysis of residual connections). If | x|| S 6, f: RR + Rd, and fl f(x)l s
e, (hen
f + & (f(x) + x) S 6.
Proposition 7.5 (Error analysis of layer normalization). If ||[|| S X, || - x|| 105505 and LN is a layer
normalization with LN.c 0, then there is constant such that
[|LN(x) - LN(x)] - K6.
8 Assembly
8.1 Residual stream
The layers of a transformer compute a sequence of sequences of vectors,
(c
tf.t(() sa(z) (0)
(0)
+
(z
2
(z)
(1)
() .f(e) (1)
c
+ (c
11
(c
= (f sa(z) (1-11)
(1-11)
+ (z) (1-1)
Zn (1-11)
Zn
(f ff(cc (1)
(cl
Because each layer doesn't 't replace its input but adds to it, this sequence of sequences of vectors sometimes referred to as the "residual stream" (Elhage et al., 2021).
In thcoretical constructions of transformers, if there is no nced minimize the dimension d, it's typical for each layer only to add lo components that have zero value. Then transformer resembles a straight-line program, where each layer sets one more components, each component is set exactly once, and each layer see the components set by all previous layers.
8.2 Routing Lemma
The following lemma is extremely useful for passing information through transformer, and constructions very frequently make use of it without mentioning it explicitly.
Lemma 8.1 (Routing Lemma). If ff: Rdd + Rd is FFN, and L, R. Rd + Rd are linear transformations, then L and ff R are also FFNs.
Similarly, let sa: (Rd)- > (R&)+ be self-attention layer, and L, R: Rd Rd be linear transformations. Then L and R induce positionwise mappings (IRd)+ (Rd)+, and L sa and sa R. are also self-attention layers.
29

---

Published in Transactions on Machine Learning Research (01/2026)
This means in particular that can reorder, duplicate, zero out the components of the hidden vectors of transformer at will. We will leave these transformations implicit. (In particular, our definition of FFN and self-attention requires that the imput and output dimension (d) be equal, but we will often give definitions of FFNs and self-attentions where this is not the case, bocause the routing lemma can be used to make them equal.)
Proof. Given ff and matrices L and R, can construct FFN ff' of R:
ff'. W (ff.W.)R
ff'b; ff.b,
ff' W = 2)f.
bb = L(ff.ba).
Given sa and matrices L and R, we can construct a self-attention layer sa' = sa R:
sa'. (V())Q (sa. W R
sa'. W(K) = (sa. ((K) R
sa'. W(V) L(sa. W()) R.
8.3 Composition operations
Lemma 8.2 (Serial Composition). Given two layers th tl2: RRd Rdd, there is a layer tly ott that compules (w)).
Proof. Simply stack tly on top of the layers of th This can then be extended to sequences of multiple layers.
Lemma 8.3 (Parallel Composition). Given transformers without layer normalization
tf E' lg (Rd1)**
tfa: x 1 (z)
there is a transformer
tf tf2: Ex 13 tRa)+
such that for all strings wi.... W, E",
[w) (tf, @ (w) = (fz(w)) tf2(w))
(w))
(40)
Proof. This is special case of Lemma 8.1. Let di and d2 be the width of tf, and tf2, respectively, and let d d= di + d2. If one of tf, and tf, has fewer layers than the other, add trivial layers (layers that compute the identity function) until they have the same number of layers L.
The new transformer has embedding layer
[tf [tf).e((o) tfg.we(())
(tf @ we(o)
[ti, (2)
(tf tfz)) (i)
tf2. (i)
30

---

Published in Transactions on Machine Learning Research (01/2026)
For each layer & E [L], let fi ttl and f2 tfg.tle. Widen fi into layer fi with width d as follows.
f.sa. W(Q) = sa. W
fl.sa. ((K) sa.. W(K
0
S.sa. W(V) fi.sa. W(V)
fr. W
0
f..
f. =
ff.ff.b
0
f. 0
ff.
f.f.WW2== =
f.
0
Similarly, widen fe into a layer 8/ with width d, but using the bottom half of the activation vectors:
S/.a..Wr ((Q) = [0 Sa. f2.a..W(Q)]
f2, ((K) [o
sa. W(K)
sa. W(V) =
f2. W(V)
0
O
0
W. =
f2.
f2.ff. W
f2.
0 f2.f..W.
0
f. f. W =
f2.ff.b =
f2.ff.b2
Then, by Lemma 8.2, stack Jí on top of lzz or the other way around. (II we had multi-head attention, we could have combined and f2 into a single layer.)
9 Putting It All Together: Example Constructions
In this section, we demonstrate how our tools can be applied to construct a transformer for certain tasks. In particular, present the construction of induction heads, well construction to recognize the Dyck language adapted from Bhattamishra et al. (2020); Yao et al. (2021); Yang et al. (2024). We note that the constructions presented here require multi-layer Transformers. Communication complexity-based arguments show that, for sequences of length N, any single-layer Transformer whose size is o(N) or independent of N cannot compute induction heads (Sanford et al., 2024b) or recognize Dyck languages (Bhattamishra et al., 2024).
9.1 Induction Heads
The term induction head was coined by Elhage et al. (2021) in order to describe a transformer which performs basic pattern-rocognition task: If the current symbol A and the previous occurrence A was followed by B, then predict the next symbol B. In other words, the induction head is formally specified as a function with the following type:
Induct: E + +
There are few variants of the induction head, each of which can be solved in a slightly different way.
9.1.1 Most- Induction
In this case, the given sequence may contain multiple previous instances of the symbol to perform induction with. Here, we take the right-most instance for the induction. If none exists, we predict the current symbol. For example in the sequence, at the last position we will predict C, because the last symbol is A and the symbol following the second-to last A is C. The same applies at other positions.
31

---

Published in Transactions on Machine Learning Research (01/2026)
(ACABAACCAAAA ACCRDBBADD
Then, the predicted symbol is C. This mechanism can be achieved using the following construction, using the imput above running example. We will represent each symbol with its one-hot encoding e, for E.
First, we use a one-hot embedding in order encode the sequence
WE(ACABDACDDCA) = Ca, cc, CA, Cg, CA, CC, CD, CD,CC.Co
For every symbol, use the routing construction from Lemma 8.1 and the pred construction from Section 5.4 retrieve the embodding of the predecessor symbol (returning when none cxists).
Pre((ACADDADDC) 0, e ec: eA; en, en, e ec; en, ec
If the current symbol is A, we can perform a similar construction as the one-hot encoding lookup from Section 5.3.1 in order to retrieve the right-most position whose predecessor is A. this case, we use q; = (, k, = (r)) and V, WE(x;). Attention will be maximizod at all positions with the same symbol as æ;. Then, right-most unique hard attention (say, using Section 5.6) can be used to maximize attention on the rightmost of these positions, and W(V) retrieves the symbol that position.
Retieve(ACCADDACDCAA CA. cc, ec,ep. CD Cg. CAi CA. CD,
This construction also could have been achieved using soft-attention. Because the dot product of one-hot encoding vectors always results in 0 or 1, we have a gap of y = between the largest and second-largest. attention scores. Thus, one could use a temperature scaling factor of r log&N as described in Section 5.7 to simulate average-hard attention using softmax attention, and then a positional encoding including the term 7 to simulate right-most hard attention using average-hare attention described in Section 5.6.
9.1.2 Most-Frequent Induction
In this case, the given sequence may contain multiple previous instances of the symbol to perform induction with. Here, we take the most frequently occurring induction as the ultimate induction. For example in the soquence, we perform induction the last position with the symbol A, which occurs thrce times previously. Here, the predicted symbol is C, because AC occurs twice while AB only occurs once. When two symbols have the same probability, can break ties arbitrarily since there are finitely many symbols (here, use the alphabetic ordering to break ties).
Inductrrequent (ACABDACDCA InduCCrruemmAAABAAAACA = ACCBDBAAAC
This mechanism can be achieved using the following construction
First, onc-hot embedding in order to encode the sequence
WE(ACABDACDDCA) = C,,, ec, CA, CD, ec, CD, CA
For every symbol, use the routing construction from Lemma 8.1 and the pred construction from Section 5.4 to retrieve the embedding of the predecessor symbol (returning 0 when none exists). This allows us to encode the bigram T;-10; at each position.
Bigra((ACARDACDCA)
e
ecc
eA
eg
ep
e
ecc
ep
Tec
ex
0
CA
C,4
eB
ep
C
cc
Cp
cc
32

---

Published in Transactions on Machine Learning Research (01/2026)
Using the uniform attention construction from Section 5.1.2 and appropriately define value matrix to select the desired bigram embedding, we can count the occurrences of each bigram 0102 up to each position.
Using a comparison as described in Section 4.7, the symbol that most Irequently follows an A can be detected, and used as the prediction. At position i, we enter a case for the symbol w; =a. In this case, we look at every count BigramCount and check for each a' if Aa"ga' BigramCount,or (w); Z BigramCount (w)). We return the alphabetically first o' for which this is true.
Retieve(ACAADDACDCCAC e,, ec, ec, eB, eD. eB, CA eA. ec
9.2 The Dyck Languages
The Dyck languages are important because they exemplify hierorchical structure, key feature of both natural and formal languages. Recognizing them requires tracking long-distance dependencies and nested relationships, making them excellent case study for a model's capacity for fundamental computational primitives. In Section 9.2.1 we present construction to recognize DYCK-1, the prototypical Dyek language. DYCK-l consists of well-nested strings from the alphabet Σ = {{)} and is defined by two conditions:
PROPERTY 1 (Prefix Condition): In every prefix of the string, the count of open brackets must be greater than or equal to the count of close brackets.
PROPERTY 2 (Balance Condition): The total count of open and close brackets in the entire string must be equal.
For example, the string (()) is in DYCK-1, while O) is not. Formally, DYCK-1 is the language generated by the grammar:
S e (S)S
The decision problem is determine if an input string E {{))}* is member of DYCK-1. We present transformer construction to recognize DYck-1 in Section 9.2.1. In sections Sections 9.2.2 and 9.2.3 we introduce depth- bounded variants of the Dyck language and present two additional transformer constructions.
9.2.1 A Transformer Construction for Dyck-1
We now present recipe to construct a transformer that recognizes DYCK-1, based on work by Bhattamishra al. (2020). This construction requires the following ingredients: average-hard atlention, layer normal- ization, and (non-strict) future masking. The construction presented requires two layers, where we assume the use of residual connections for both the self-attention and feodforward components. We note that in practice, transformers learn to simulate this algorithm when trained from data (Bhattamishra et al., 2020).
Intuition A simple algorithm for recognizing DYCK-1 provides intuition for the transformer construction: we make a single left-to-right pass and maintain running count of the number of open minus closed parentheses. As illustrated in Fig. 2, this count must be non-negative each position, and be exactly at the final position of the string. The main idea is to futurc-masked uniform attention (i.c., future-masked average hard attention) to compute this value at each position.
Overview For an input string w of length and a position 0 i < n, let O denote the number of open parentheses ('C) appearing in the prefix w.. Similarly, let C, denole the number of close parentheses (t)) appearing in Wy. We use a two-layer transformer to implement recognition attention head computes the running balance B, O, - C, and its feod-forward network calculates a prefix error signal E; then, the second layer's attention head aggregates the E, to compute the total error t. Finally, inspect the output the last position (index n) to check whether the string belongs in DyCk-1.
DYCK-1: The first layer's
33

---

Published in Transactions on Machine Learning Research (01/2026)
0= = -,30011000220
O₂ -3=1,C==2,0 = <s
x
0,=20,-1,,006
())0
()(O)
0, = C. =, 3,,0=3
3; C. = 3, 0,
Os = 4, 2, # Co x
Figure 2: Prefix-sum checks for membership in the Dyck language. Each subpanel plots the running counts OR (opens) and C₁ (closes) at each position & of candidate string of length N 6. (Left) Valid Dyck-1 string: O2 2 C for all < N and ON = CN: satisfying non-ncgativity and balanced counts, respectively. (Center) Prefix violation: Although ON CN, at position = 3, we have O3 < C3, violating non-negativity. (Right) Here O& 2 Cg for all k, but ON # Cv, so the total counts are unbalanced.
Step 1: Rumning balance computation We first convert the symbolic inputs into a numerical format by embedding the '(' and ')* as follows:
0i
+1 if position is C 2; 0,
0 0
(41)
if position is )
yielding sequence of embedding vectors (.1,..., Zn). The core of the algorithm is to compute the running balance of parentheses at every position, which we do with future-masked uniform attention. In particular, we use the (Avg.) construction from Section 5.1.2 with first-coordinate projection on x to compute the cumulative average:
(Ngg((0))
Σ j=1
0j
O
C.
B: where (01, 02,...,,n)) On)-
(42)
The running balance B,/i is then written into workspace dimension (see Eq. (44)). Note that scaling the balance B; by positive scalar 1/i does not change the sign of the running balance, so the necessary information to check the Dyck propertics is preserved.
Step 2: Computing balance violations Having used the first self-attention layer to compute running balance at each position, we next aggregate an error signal into the final position, such that the final DycK-l- acceptance check needs to only inspect the n-th position output. To do this, we use an FFN with weights set so as to compute Fg = ReI.U(-B./i) noting that E, > iff the non-negativity condition of the running balance (PROPERTY 1) is violated. This can be achieved using an FFN with W, W₂ and left and right matrices in Section 8.2 used to negate the input and zero-out all output dimensions besides the third
Step 3: Aggregating to the last position Finally, we use the second layer's self-attention to aggregate the error signal as follows:
4; = (Avg. [E)) = Σ F5 where E (Fa, Fz,.... E,),
(43)
1=1
where note that at the final position, tu > iff the running balance (PROPERTY 1) has boen violated at any position, and that tn = 0 otherwise. Altogether, this construction performs the following operations at each position
0,
0,
0
Compute Balance
Bi/i 0
Negative B, Error?
B E
Sum Errors,
Bi/i
(44)
0
E;
0
0
0
t;
34

---

Published in Transactions on Machine Learning Research (01/2026)
The second layer's accumulation reduces work to checking the output vector at the final position n. In particular, to check PROPERTY 1, it suffices to check that in = 0, since in aggregates the prefix violations for all prefixes of the string. To check PROPERTY 2, it suffices to check that B,/n = 0 (i.e., the final balance is zero). To implement these checks, however, we must first decide whether our construction's paramoters should depend on the input length n (see the discussion of wniformily, Section 2.3). In our selting, a nonumiform construction can output 0/1 binary value to indicate acceptance, while a uniform construction requires the final acceptance check to be performed externally.
Uniform implementation In a uniform implementation, the transformer's parameters are fixed and do not depend on the input length n. This approach is often preferred in theoretical analyses as it reflects a single model that can handle inputs of any length. Since a uniform model cannot use length-dependent comparison functions from Section 4.7, it cannot produce a single 0/1 output. Instead, the acceptance condition is defined by an external check on the final output vector, in the manner described above.
Nonuniform implementation However, if one wishes to cocrce the acceptance decision into single 0/1 value (at a particular position in the transformer's putput) one must perform a nonuniform construction. To see this, consider the family of FFNs EqZero, (which checks equality with zero) described in Section 4.7. A EqZero, FFN is parameterized by the magnitude needed for a value to be considered different from zero. In our setting, using Eq where n is the length of the input sequence would suffice. This is because the smallest nonzero magnitude of the (scaled) running balance B, is 1/1, and i is upper-bounded by the input sequence length n. Since in is computed by using Avg. to average the values of B,, the smallest nonzero magnitude of ln is 1/n². Similar reasoning shows that the smallest nonzero magnitude of B./n is 1/n.
One could add an additional transformer layer that uses an FFN (built from the components EqZero, and logical AND from Sontion 4.8) to render a 0/1 decision, however this would require fixing an upper bound on the maximum length of the input sequence that the transformer can process.
9.2.2 A Transformer Construction for Dyck-1-2
We will now present construction that recognizes depth-bounded Dyck language. In particular, we will focus on DYCK-1-2, which is the Dyck language formed with one kind of bracket in which the maximum nesting depth is 2. The maximum nesting depth of a string being D means that the total number of unclosed brackets in any prefix is at most D. This construction for DYCK-1-2 appears in Yang et al. (2024) and is basod on Yao et al. (2021). This construction requires the following ingrodients: (unique or averaging) hard allention, no layer normalization, striet future masking, strict past masking, and i/n positional encodings.
Intuition Consider the input string (O), which is a member of DYCK-1-2 (and thus should be accepted). We will check membership in two steps. First, we will look at pairs of adjacent brackets and mark all the matching pairs. In our example string, we would mark "(O) ())) This suffices to check for depth-one matches.
In the second step, we filter out all the brackets we marked in the first stop and then mark all the matching adjacent pairs in this filtered string. This checks for depth-two matches. To continue our example, filtering out all the brackets marked in step 1 leaves with the string ()" In this case, each bracket matches an adjacent bracket in the filtered string, so we would mark all the remaining brackets.
In the final step, we accept the string iff all brackets have been marked as matched after the second step.
Overview Our deseription of this construction will pull together many ingredients from carlier soctions of the cookbook. The main idea of this construction is to use multiple transformer layers to perform steps 1 and 2 in sequence. Importantly, we need to keep track of which brackets have been marked "matched"
35

---

Published in Transactions on Machine Learning Research (01/2026)
during steps 1 and 2. We do this by maintaining "active bit" within the intermediate representation each position. Concretely, we initialize our embedding vector at each position i as follows:
1
+1 if position is C
C2
O
Oi
=
(45)
-1 if position is )
0 i/m
As before, let o, denote whether position i is open (+1) or closed (-1). The second entry is the "active bit", where denotes that the current position not yet matched, and which we later set denote a successful match. The third and fourth entries are initialized zero and serve scratch space on which to store intermediale computations. Finally, we positional encoding containing i/n.
Step 1: Identifying depth-1 matches We first use the predecessor construction in Section 5.4 that uses strict future masking, well as the successor construction (a slight modification of predecessor), to fetch the bracket types immediately to the left and right of the current position. Based on this, we then use an FFN to check for depth-1 matches and update the "active-bit" as follows:
02 1
Aright
FFN Mark Matched
0j-1
(46)
0,+1
i/n
i/n
i/m
A value of = 1 indicates that no depth-1 match has occurred, such as when 01-10:0141 corresponds to the bracket sequence ) C. In particular, let:
0 if = +1 and o++1 11
04
0 if = -1 and 0 = +1,
(47)
otherwise,
which may be implemented using techniques from Section 4. As a corner case, let 0-1 = On+1 = 0, or some other distinguished value, which the FFN's conditional implementation can handle.
Step 2: identifying depth-2 matches The depth-2 match similar above, except at each position we search for the nearest left and right components that are not yet matched (i.e., whose active bit is still 1). Finding the nearest not-yel-matched position to the left can be done similarly to the predecessor construction employed above, and may be done by by running strict future-masked UHAT on the following scores:
UHAT
| [- n1
a1;
2 + 02 .... + On
n
for i 1, I,...,n,
(48)
We add the active bit aj to the positional encoding 1 at position j to ensure that the maximal attention corresponds to an unmatched position. These scored may be achieved by applying a linear transform to the embedding state of Eq. (46), such as via the self-attention's ((Q) and WKK) matrices. A similar approach (using strict past masking) allows us concentrate attention on the nearest unmatched position to the right. We then proceed analogously step 1, where let:
0
02
0j
d
0
Select. Nearest Active
1;
Check Match
0
(49)
0
Ti
i/n.
i/n
36

---

Published in Transactions on Machine Learning Research (01/2026)
where ra ra E {+1} correspond to the left and right tokens not yet matched. Likewise, let df = 1 if position is not part of any depth-1 depth-2 matches, and let af 0 otherwise if it is matched. As above, these conditional checks and updates can be implemented via an FNN.
Step 3: Check for unmatched brackets Finally, it remains to check that no positions remain un- matched: accept the string iff at all positions have a a' O. This is similar to the zero-check in our earlier DYCK-1 construction, and similar discussions uniformity vs. non-uniformity apply.
9.2.3 Generalization to Dyck-k-D
The DyCK-k language consists of well-balanced strings over an alphabet of l parenthesis pairs Go )i for E [k], generated by the context-free grammar:
S = el (:5)s, for i i [k]]
The DYCK-k-D language is the subset of DYCK-K where the maximum nesting depth (the number of unclosod open parentheses any point in the string) does not exceed D.
We now generalize the construction of Section 9.2.2 to DYCK-K-D, where the algorithmic idea is to find and cancel matching parentheses iteratively for depths 1....,.. D. To do this, we first expand the parentheses encoding from Eq. (45) as:
0 E E -1, +1, ..... +k},
allowing us to encode both the openness (+) and type (I....,k) k) of the parenthesis position i. Then, we repeat the select-nearess-active and check-match of Eq. (49) D times, where augment the feedforward component of Eq. (46) to handle matching for & different perentheses pairs. Finally, the acceptance criterion is the same as Step 3 above, which involves checking whether any positions remain active (unmatched). As a final remark, we note that generalizations to DYCK-k of unbounded depth were discussed by Yao et al. (2021, See B.4) and Yang et al. (2026, See D).
10 Discussion
This cookbook presents an overview of what transformers can compute and how they may compute. The recipes presented herein give a mise en place of ingredients sampled from the literature. Theoretically, they are a useful reference for investigations in transformer expressivity and learnability. Practically, they are starting point for experiment design in areas such as mechanistic interpretability and architecture design. We have provided a code repository containing implementations of cach construction to support future work. However, our curation is by no means exhaustive: new ideas and techniques are under active development. Indeed, we eagerly await what new flavors the reader will discover!
11 Acknowledgments
We would like to thank the anonymous reviewers for their helpful comments. We would like to thank the following chefs for bringing new flavors to our kitchen: Lena Strobl, Yuval Pinter, Dana Angluin, Jonathan Rawski, Gail Weiss, Brian DuSell, Marco Cognetta, Gabriel Faria, Travis Bartley, Nithila Sivapunniyam, Yingshan Chang, Akos Kadar, Shahaf Bassan, Yash Sarrof, Frederick Morlock, and other members of the FLaNN Discord Server.
This material is based upon work supported by the National Science Foundation under Grant Nos. DMS- 2502292, CCF-2505865, CCF-2313010 and IIS-2331783, 783, the ARPA-H program on Safe and Explainable AI under the grant D24AC00253-00, and a gift from AWS Al to the ASSET Center at Penn. Merrill is supported Two Sigma PhD fellowship, an NSF Graduate Rescarch Fellowship, and the Allen Institute for Artifical Intelligence, Svete is supported by the ETH Zürich AI Center doctoral fellowship, and Yang supported by NSF Graduate Research Fellowship under Grant No. 2236418.
37

---

Published in Transactions on Machine Learning Research (01/2026)
References
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algo- rithm is in-context lcarning? Investigations with linear models. In Proceedings of the Eleventh Interna- lional Conference on Learning Represenlations (ICLR), 2023. URL https:/ bttps:://ppeneviee..o nww..ewrnet/frmm id=0gOX4HByN44.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In Proceedings of the Sirth International Conference on Learning Representa- tions (ICLR), 2018. URL attps://opee /ttpse//oponrevvee net/forum?dd B11__mm/BddBBB_
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. In NIPS 2016 Deep Learning Symposium, 2016. URL https://arxiv http://raaii..ooaa/b///aoa wwwg///s///0..../////// .64550.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In Proceedings of the Third International Conference on Learning Representations (ICLR), 2015. URL https://arxiv/ wrtpeii...rr//ooee org/abs///../.oo /ttb//////../.. 0473.
Pablo Barcelo, Alexander Kozachinskiy, Anthony W. Lin, and Vladimir Podolskii. Logical languages accepted by transformer encoders with hard attention. In International Conference on Representation Learning, pp. 22077-22087 2024. URL httpss//openreviee
Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. bounds for neural networks. In Advances in Newral Information Processing Systems 30 (NeurlPS), pp. 6241 6250, 2017. URL nttps://papers nips b220577ab619450030333cBe
ppectrally-normalle margin
happs.cc/paet cc/paper feaperffllss//eee cc/papprr_ilees/pppeeeeeeeeeeeee
Abstract.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of Transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7096-7 7116, 2020. Not:10.18653/112000 2e22000emmlpmmminn... 576.
Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the representational capabilitics of Transformers and recurrent architectures. In Advances in Neural Information Processing Systems 37 (NewrIPS), pp. 36002-36045 2024. URL https: https://prooeeddings www.eeeeeddiinnnnnn.e.ee.e.eee.. neurips ww/ppccc_ppppeeeeeeeeeeeeeee oc/paper_files/ files/ html.
Shaked Brody, Uri Alon, and Eran Yahav. On the expressivity role of LayerNorm Transformers' atten- tion. In Findings of the Association for Computational Linguistics: ACL 2023, pp. 14211 14221, 2023. doi:10.18653/ v11 htt///22...nnnnnes...
David Chiang and Peter Cholak. Overcoming a thcoretical limitation of self-attention. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguislics (ACL), pp. 7654 7664, 2022. doi:10018653/ w1/202222a222aa acl.2.2cl-ooon.52..
David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. Proceedings of the 40th International Conference on Machine Learning (ICML), pp. 5544 15642, 2023. URL httpe://procceedins. mlr ggress/v202/chiang22 html.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control Signal Systems, 2: 303-314, 1989. Not:1011007/BF0255177
Jacob Devlin, Ming- Wei Chang. Kenton Loc, and Kristina Toutanova. BERT: Pro-training of deep bidi- rectional Transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Longuage Technologies, pp. 4171 4186, 2019. 4b1:10.18533/11/N191122
Benjamin L. Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In Proceedings of the 39th International Conference on Machine Learning, pp. 5793 5831,, 2022. URL http::///poooeeeggg.....eee///ee
mlr. wtt../eeess/v112eeeelleeee html.
38

---

Published in Transactions on Machine Learning Research (01/2026)
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuniao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds. Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. A mathematical framework for transformer circuits. Transformer Circuils Thread, 2021. URL http::/trransfoorer-rrraatt pub/ 2021/framework/ wetpi//iindxx.hahe
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: thcoretical perspective. In Advances in Neural Information Processing Systems 36 (NeurIPS), pp. 70757 70798, 2023. CRL https://proceedingg. neurips.... wtt.ipp.....pppppeeeeeeeeeeeeepe wctpappp_eaaieeeeeeeeeeeeeeeeeee fil.e/lllppppe files/paper/ .ttll.
Kunihiko Fukushima. Cognitron: A self-organizing multilayered neural network. Biological Cybernetics, 20 (3):121-136, Sep 1975. dot:10.1007/BF00332222
Mor Geva, Roei Schuster, Jonathan Berant, and Omer Levy. Transformer feed-forward layers are key-value memories. In Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, pp. 5484-5495, 2021. doi:10.18653//1/220 http:///////...mmmmmmmmm.////// emnlp-main.446
Michacl Hahn. Thcoretical limitations of self-attention in neural sequence models. Transactions of the Association for Compulational Linguislics, 8:156 171, 2020. doi:10.1162/uaad 00306.
Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? In Proceedings of the 62nd Annual Meeting of the Associalion for Computational Linguistics, pp. 19973-15088, 2024. doi:10.11663/v1122222 /2024..cl-ooog.800
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10: 800-810, 2022. doi:10.1162/tadd t 00490.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (GELUs), 2016. URL https://arxiv.org abs/1606. 08415. arXiv:1606.08415,
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Newral Networks, 2(5):359-33) 366, 1989.
William B Johnson, Joram Lindenstrauss, et al. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984. fol:10.1090/com//000 0026/7/77//7700
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in Transformers. In Advances in Neural Information
Processing Systems 36 (NewrIPS), pp. 24892 24928, 2023. URL sttpse//prooeeeding heurips.. cc/ html.
paper http:////pppppee/s//a////a//aaaa hatp:e/aeee--tttttat--ooooeeeeee
David Lindner, János Kramár, Matthew Rahtz, Thomas McGrath, and Vladimir Mikulik. Tracr: Compiled transformers as a laboratory for interpretability. In Advances in Neural Information Processing Systems 36 (NewrIPS), pp. 37876-37899, 2023. URL attps://papezz: caipsccc/paprr fnceerfflllsse files/ /alles/paperr2223/mmaa h20s/ 77115bbae74400556111444b44 Abstractt-oofeeeeeeeeeee html.
Warren S. McCulloch and Walter Pitts. A logical calculus of the ideas immanent in nervous activity. The Bulletin of Mathematical Biophysics, 5:115-133 133, 1943. 100110.1007/BF02472200
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023.
doi:10.1162/taar 00562.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In Proceedings of the Twelfth International Conference on Learning Representations (ICLR), 2024a. URL http://ewww....eeeeommmmaaaaaaad
39

---

Published in Transactions on Machine Learning Research (01/2026)
William Merrill and Ashish Sabharwal. A little depth goes long way: The expressive power of log-depth transformers. In NeurIPS 2024 Workshop on Mathemalics of Modern Machine Learning, 2024b. URL https://openreriew.nr http://w.eettooommmmddnnnnoooooo
William Merrill, Vivek Ramanujan, Yoav Goldberg, Roy Schwartz, and Noah A. Smith. Effects of pa- rameter norm growth during transformer training: Inductive bias from gradient descent. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 1766-1781, 2021. 111111.1865//11120000 http://111121..elmmmmmaaee amnlp-mmin..33.
William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843-800 856, 2022. doi:10.1162/tanl a 00493.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention corine-complete. Journal of Machine Learning Research, 22:75:1-75:35, 2021. URL http://jmlr wrtppppprss/v22/20000000- html.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training, 2018. URL / wwtp:///eweee////ggguuuuuuuuupaa
Clayton Sanford, Daniel J. Hsu, and Matus Telgarsky. Representational strengths and limita- tions of transformers. In Advances in Newral Information Processing Systems 36 (NeurIPS), pp. 36677-36707, 2023.
URL https://papers. mips. https/ccppppppaaaaeeeee wttps//eeeeeeeeee/e/e/// /hash/ html.
Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mchran Kazemi, Jonathan Hal- crow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabil- ities via graph algorithms. In Aduances in Newral Information Processing Systems 37 (NewrIPS), pp. 78320 78370, 2024a. URL attps://papees: 8F994400044666f122222236333
httc//pper_fillsppppeee////////p Abstract-Conferenn html.
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. One-layer transformers fail to solve the induction heads lask, 2024b. URL https://arxiv org/ httpss//arrri..rr//aa///00. 14332. arXiv:2408.1433 14332..
Peter Shaw, Jakob Uszkorcit, and Ashish Vaswani. Self-attention with relative position reprosentations. In Proceedings of the 2018 Conference of the North American Chapler of the Associalion for Compulational Linguistics: Human Language Technologies, pp. 464-468, 2018. doi:10.18653/v1// 111186653/11N18-120 21144207.
Vighnesh Shiv and Chris Quirk. Novel positional encodings to enable tree-based transformers. In Advances in Neural Information Processing Systems 32 (NewrIPS), 2019. URL attps://papers: nips wwwpiccppp.p.eeeeeeeeeee cc/paper. Abstract. html.
D. Sivakumar. Algorithmic derandomization via complexity theory. In Proceedings of the Thiry-Fowrth An- nual ACM Symposium on Theory of Computing (STOC), pp. 619 626, 2002.
5509996....
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? A survey. Transactions of the Association for Computational Linguistics, 12:543 561, 05 2024. doi:10.1162/taan a 00663.
Lena Strobl, Dana Angluin, David Chiang, Jonathan Rawski, and Ashish Sabharwal. Transformers as transducers. Transactions of the Association for Computational Linguistics, 13:200 219, 2025. doi:10.1162/tarr /tacll 00736.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, L ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Pro- cessing Systems 30 (NIPS), 2017. URL https://papers. wwwp.cc/ppp..eeeeeeee 3tte2246 Abstraattbbttttttt.ammmmma html.
Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
0oi:10.0017/97111 1077331996
40

---

Published in Transactions on Machine Learning Research (01/2026)
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In Marina Mcila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11080 110900.110.... PMLR, 18 24 Jul 2021. URL attps://proceedinn mlr. www.press/vveee satass/vv3///eiss/// html.
Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization in the Transformer archilecture. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning mlr pttps///119/xooog20/000 html.
Research, pp. 10524-10533, 2020. URL
Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In Proceedings of the 32nd International Conference on Machine Leorning, pp. 2048-2057, 2015. URL https:
/ h/proceedings.co wawpeeddiiimmmm......mmm..am.e.e www.mlr.ppp..... ptwss/v37/ss//// prress/33/xucc5.. /xcc1xcc11.. html.
Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. In First Conference Language Modeling, 2024. URL https: attps://opente http://pppeeeee.eeneeeee
id=FnhPgUUJ9K.
Andy Yang, David Chiang, and Dana Angluin. Masked hard-attention transformers recognize ex- actly the star-free languages. In Advances in Neural Information Processing Systems, volume 37, pp. 10202 10235, 2024. URL https: https://prooceedings..nt ctpppeeeeeee.pp...ppppppeeee 1aar1122590-1230555a7aaaaaa attpr/ccccccaaaacccaaaaatttt-toe AbstracttCooffereeeeee
wwtpppperfilleeeeeeeeeeeeeeeeeee fww.s/ /i1le//paperr222//mnss hhmml.
Andy Yang, Lena Strobl, David Chiang, and Dana Angluin. Simulating hard attention using soft attention. Transactions of the Association for Computational Lènguistics, 2026. URL attps://arae org/ abs/ 2412. 09925. To appear.
Shunyu Yao, Binghui Peng, Christos Papadimilriou, and Karthik Narasimhan. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natural Language Processing, pp. 3770-3785, 2021. doi:10.18633/v1200D0 22112220c2ccllo
Monty-Maximilian Zühlke and Daniel Kudenko. Adversarial robustness of neural networks from the per- spective of Lipschitz calculus: A survey. ACM Computing Surveys, 57(6), 2025. Nof:10.1145/364835.
41


Reviews:
[{"review_id": "wrvQrKYcvd", "reviewer": "Reviewer_rSer", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper's primary contribution is to serve as a unified cookbook that synthesizes the fragmented literature on programming transformers. It collects and systematizes techniques for building specific, pre-defined algorithms directly into a transformer's parameters. It provides a library of concrete recipes including explicit weight matrices and bias vectors for implementing components like arithmetic, conditional logic, and various forms of attention-based table lookup. The paper concludes by showing how to assemble these components to solve more complex tasks, using induction heads and Dyck-language recognition as examples.\n\n**Key Strengths**:\n\n- Synthesis and Clarity: The paper's main strength is its value as a single, comprehensive reference. It pulls together dozens of techniques from disparate papers into one consistent notational framework, which is a significant service to the community.\n\n- Concrete and Actionable: The \"recipe\" format is excellent for teaching and reproducibility. Providing explicit parameter matrices makes the constructions tangible and removes ambiguity.\n\n- Breadth: The cookbook is thorough, covering a wide range of useful primitives from FFN-based computation and techniques using Layer Normalization that are useful for practitioners and researchers.\n\n**Key Weaknesses**:\n\n- Idealized Assumptions: Many core recipes rely on non-standard or impractical assumptions, such as \"average-hard attention\" (e.g., the Dyck-1 construction in the Examples section), setting LayerNorm epsilon to zero (LN.ϵ=0) (see the Layer Normalization section), or requiring architectural changes like \"selective\" LayerNorm. These assumptions are interesting but depart from standard transformer architectures and deserve clearer discussion of practicality.\n\n- Missing Practical Validation: The paper claims to be a practical cookbook but provides no empirical validation or code. It's unclear if these recipes, particularly their soft-attention approximations, work as described under real-world constraints. The paper is a collection of blueprints that often point to prior work for details, but the authors do not provide implementations or experiments that demonstrate the constructions are stable in practice, which one would expect from a cookbook.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper's theoretical claims (i.e., \"if you had an idealized machine with hard attention, these weights would produce this result\") are well-supported by the mathematical constructions. However, the paper's implicit practical claim that this is a useful \"cookbook\" for understanding and building algorithms in real transformers is not supported throughly by convincing evidence. The evidence is missing in three key areas:\n\n- Reliance on Impractical Primitives: Many constructions rely on components not present in standard transformers. For example, the Dyck-1 recipe explicitly requires average-hard attention. The layernorm-hash construction relies on LN.ϵ=0 and the ability to selectively apply LN, which the paper acknowledges would require architectural modifications. The amplification trick similarly assumes LN.ϵ=0. These constructions are theoretically interesting but do not, by themselves, establish practicality for standard models.\n\n- Unquantified Approximations: The paper's primary method for bridging hard attention to soft attention is to scale queries (see the attention approximation discussion). It proposes a scaling factor τ = γ / ln(8N) and claims this can make approximation error small enough to round. This argument is presented qualitatively but lacks a worked numerical example or practical analysis of typical parameter regimes; the authors should spell out the numeric implications and provide explicit error bounds for representative N and γ values.\n\n- The paper positions itself as a \"cookbook,\" which implies practical applicability. However, as presented it is largely theoretical and lacks empirical validation, such as anonymized code artifacts or experiments, to demonstrate how these constructions perform in practice. It is unclear whether the recipes, particularly soft-attention approximations or those relying on idealized components, function as intended when implemented in common deep-learning libraries.\n\nWhile the paper provides an excellent theoretical synthesis, the absence of basic implementations or verification makes it difficult to assess practical robustness. This gap between theory and practice undermines the paper's stated goal of providing a \"foundation for... empirical investigations\", since the first empirical verification step is missing.", "audience_yn": "Yes", "audience_explanation": "Yes, the TMLR audience, which sits at the intersection of theory and practice, would be extremely interested in this work.\n\n- Interpretability Researchers: This community will find this paper invaluable. It provides a \"library of idealized circuits\" that can be used as formal hypotheses when trying to understand the mechanisms learned by real models (e.g., \"Is this model performing table lookup using a mechanism similar to the 'almost-orthogonal' recipe?\").\n\n- Theorists: Researchers working on the formal expressive power of transformers will appreciate this paper as a clean, unified, and well-organized synthesis of dozens of scattered results. The consistent notation (Section 2) alone is a valuable contribution.\n\n- Architecture Designers: The paper provides a clear functional analysis of how components like LayerNorm and positional encodings contribute to or limit a transformer's algorithmic capabilities, which could inform future architecture design.\n\nThe central problem of \"what can transformers compute and how\" is one of the most important in the field, and this paper provides a uniquely accessible and comprehensive entry point.", "requested_changes": "- Add a Summary Table of Assumptions. This is the most critical change for clarity. The authors must add a table that lists every major recipe (e.g., \"Index-Lookup: One-Hot,\" \"Index-Lookup: LN-Hash,\" \"Dyck-1\") and, for each, lists its key properties:\n\n        (i) Width / Param cost (e.g., O(N), O(logN), O(1))\n\n        (ii) Dependence on N (uniform/non-uniform)\n\n        (iii) Required Primitives (e.g., \"Softmax,\" \"Hard Attention,\" \"Selective LN,\" \"LN.ϵ=0\")\n\n        (iv) Error bound or \"Practicality\" (e.g., \"Exact,\" \"Approx. (see Sec 5.7),\" \"Theoretical-only\")\n\n- Provide a Reproducibility Artifact (Code). The authors should provide a small, runnable code release (e.g., a Python script with numpy/PyTorch) that implements a subset of the most important recipes. This will serve as the \"convincing evidence\" that is currently missing. A good test suite would be:\n    (i) The \"almost-orthogonal\" index lookup\n    (ii) The \"quadratic maximization\" index lookup\n    (iii) The soft-attention approximation demonstration, showing empirical error after applying the proposed τ scaling\n    (iv) The Dyck-1 construction using the soft-attention approximation, to measure accuracy on strings of increasing length\n\n- Add Practical Numerical Analysis. For the soft-attention approximation, the authors should add a paragraph or appendix analyzing its practicality. Using their formula τ = γ / ln(8N), they should present worked numeric examples for representative N and γ values and discuss the resulting logits and whether the approximation gives sufficiently small error for rounding in those regimes.\n\n- Formalize Key Claims: For the most important constructions (like the index-lookup methods and the soft-attention approximation), the claims should be stated as formal Propositions or Lemmas with all preconditions, assumptions, and error bounds made explicit. This is more rigorous than the current \"recipe\" text.\n\n- Clarify Architectural Assumptions: The paper must be more explicit in the main text when a \"recipe\" departs from a standard, off-the-shelf transformer. The suggestion of adding a linear projection before LayerNorm is an architectural modification and must be clearly marked as such.", "broader_impact_concerns": "No. This is a foundational, theoretical, and mechanistic paper. It does not introduce a new model, dataset, or application with direct, foreseeable societal impacts.", "additional_comments": "I want to reiterate that this is a highly useful and valuable piece of work. The \"cookbook\" metaphor is apt, and the authors have done a great service by synthesizing scattered results. The paper is well-organized and the concrete recipes are a strong contribution.\n\nMy request for some revisions is not intended to diminish the work. Rather, it is intended to push the paper to fulfill its ambitious goal of being a practical cookbook. As presented, it is closer to an idealized theoretical cookbook. By providing code, a table of assumptions, and a practical analysis of its soft-attention approximations, the paper can be elevated to a very strong submission. I look forward to the revised version. The paper is very long and I have tried my best to follow it with my understanding; I hope these comments help the authors improve clarity, reproducibility, and practical applicability.", "extra_scores": {}, "extra_text": {}}, {"review_id": "LBy4baFuEo", "reviewer": "Reviewer_ybd8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The content of the paper is exactly what the abstract promises. \nAn overview of functions which can be either exactly implemented or very well approximated (square function) by a transformer.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper is mostly about synthesis of the literature and as such, the claims are convincing. I admit that I have not checked the references, but I was looking at the arguments of how functions are implemented and they seems to be fine.", "audience_yn": "Yes", "audience_explanation": "The intention of the paper is to ease an entry for people interested in which function transformers can implemented exactly. For those people, this is very good. I also believe this to be quite good for researchers interested in extracting functions (computational graphs) from transformers. The last type of audience I can imagine are those, who are interested in learning algorithms and functions. The paper can tell them if the algorithm / function to be learned can be represented by transformer exactly. Personally, I have found this type of thinking frequently important for choosing the right architecture for my problem.", "requested_changes": "I am not an expert on this topic, but I have found weird that RASP language [1] is not mentioned. For me, this was one of the first papers trying to formalize, which operations transformers can do. There is a companion paper TRACR [2], which might be useful as well.\n\nAlthough the paper is very long, I would like to also see examples of use. Why knowing which types of function transformers implements is important and what can I do with it? I have hinted something above, but I would expect to learn, where and how this is used. Does it have any practical impact, or it is mostly just a theoretical work.\n\n\n[1] Weiss, G., Goldberg, Y., & Yahav, E. (2021, July). Thinking like transformers. In International Conference on Machine Learning (pp. 11080-11090). PMLR.\n\n[2] Friedman, Dan, Alexander Wettig, and Danqi Chen. \"Learning transformer programs.\" Advances in Neural Information Processing Systems 36 (2023): 49044-49067.\n\n[3]  Lindner, D., Kramár, J., Farquhar, S., Rahtz, M., McGrath, T., & Mikulik, V. (2023). Tracr: Compiled transformers as a laboratory for interpretability. Advances in Neural Information Processing Systems, 36, 37876-37899.", "broader_impact_concerns": "I do not see any ethical concern. I think that broader impact would be limited, mainly because the paper summarizes one aspect of understanding transformers, which few people are interested (this is not a criticism, this is statement of the fact that most people are interested in great applications).", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hNHJV6kwl2", "reviewer": "Reviewer_QZtd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, authors Unifies scattered “hand-crafted transformer” results into a single, accessible cookbook that directly encodes algorithms in transformer parameters.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Although no new theory or results are presented, the paper’s well-organized consolidation of existing methods serves as a useful reference for researchers.", "audience_yn": "Yes", "audience_explanation": "Given TMLR’s audience of transformer researchers, this submission would be a valuable reference for the community.", "requested_changes": "Overall, I have no major concerns about the submission. In my view, it is acceptable as is and would serve as a useful reference for researchers in the transformer community.\n\nThat said, the paper would benefit from an explicit, self-contained summary of the model architecture: ideally a short “Model at a Glance” subsection placed before each technical section. For example, you model piecewise-linear behavior via ReLU, while multiplicative interactions are approximated using a Taylor expansion of the GELU activation. Please clarify whether these two mechanisms are intended to be complementary or if they introduce overlapping, or potentially conflicting effects.\n\nFinally, there are a few typos. Please proofread the submission carefully and revise. For instance, on page 31, “Thr prototypical Dyck language” should read “The prototypical Dyck language.”", "broader_impact_concerns": "Na.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)