A completely uniform transformer for parity
Alexander Kozachinskiy, Tomasz Steifer · 2025
Read A completely uniform transformer for parity by Alexander Kozachinskiy, Tomasz Steifer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-02535.txt.
Introduction
Alexander Kozachinskiy and Tomasz Steifer solve a neat problem about transformer models, in a 2025 paper. Parity asks whether a string of bits holds an even or odd count of ones. It is a classic hard test for simple networks. The authors build a transformer that can judge parity for strings of any length.
Their design has three layers and a fixed size. Neither the weights nor the code for position in the string depends on string length. An earlier design needed only two layers, but its position code grew with the input. The new result trades one extra layer for full sameness across lengths. Results of this kind map the true limits of the transformer design. They show which tasks the design can handle in a strict, uniform way.
Catalog record
| CREATOR | Alexander Kozachinskiy, Tomasz Steifer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 10 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-02535
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A completely uniform transformer for parity Alexander Kozachinskiy, Tomasz Steifer Abstract We construct a 3-layer constant-dimension transformer, recognizing the parity language, where neither parameter matrices nor the positional encoding depend on the input length. This improves upon a construction of Chiang and Cholak who use a positional encoding, depending on the input length (but their construction has 2 layers). 1 Introduction One of the ways to do mathematical analysis of the capabilities and limitations of the transformer architecture [ 8 ] is to study formal languages, recognizable by them. Namely, for a given formal language L , we study, if there exists a choice of parameters in the transformer architecture, for which words from L are accepted and words not from L are rejected by the resulting transformer. A seminal work of Hahn [ 5 ] performed such analysis for a number of formal languages, including the parity language , consisting of binary words with even number of 1s. Hahn have shown that transformers, recognizing this language, must have low confidence, partially explaining an empirically observed struggle of transformers in learning this language [ 1 , 4 ] . However, this does not exclude the possibility of existence of a theoretical solution for this language. And indeed, as was shown by Chiang and Cholak [ 3 ] , there exists a 2-layer transformer with constant embedding dimension, recognizing the parity language. Their construction is uniform in a sense that parameter matrices in it do no depend on the input length. However, there is one aspect of their construction which is not completely uniform – the positional encoding . At position i , they use i/n , where n is the input length. This means that their positional encoding has to be reset each time we want to use their transformer for a larger input length. In this paper, we get rid of this disadvantage of their construction by giving a completely uniform 3-layer transformer, recognizing parity. That is, in our construction, neither parameter matrices nor positional encoding depend on n . We do not use neither positional masks nor layer norm. It remains open if the parity language can be recognized by a 1-layer transformer with constant embedding dimension, even non-uniformly. Current lower bound methods against 1-layer transformers [ 2 , 6 , 7 ] do not seem to work against parity. 2 Preliminaries An attention layer of dimension d is a length-preserving function A\colon(\mathbb{R}^{d})^{*}\to(\mathbb{R}^{d})^{*} , given by three matrices K,Q,O\in\mathbb{R}^{d\times d} and a neural network \mathcal{N}\colon\mathbb{R}^{d}\to\mathbb{R}^{d} with ReLU activation. On input (f_{1},\ldots,f_{n})\in(\mathbb{R}^{d})^{n} , the output A(f_{1},\ldots,f_{n}) is computed as follows. First, we define: a_{i}=\frac{\sum\limits_{j=1}^{n}e^{\langle Kf_{j},Qf_{i}\rangle}f_{j}}{\sum\limits_{j=1}^{n}e^{\langle Kf_{j},Qf_{i}\rangle}},\qquad i=1,\ldots,n, and set: A(x_{1}\ldots x_{n})_{i}=\mathcal{N}(f_{i}+Oa_{i}),\qquad i=1,\ldots,n. Applying \mathcal{N} allows us to do arbitrary piece-wise linear transformation of \mathbb{R}^{d} . Definition 1 . We say that a language L\subseteq\{0,1\}^{*} is recognizable by a completely uniform transformer with C layers if there exists d\in\mathbb{N} , C attention layers A_{1},\ldots,A_{C} of dimension d , and a letter embedding \ell\colon\{0,1\}\to\mathbb{R}^{d} , and a position encoding p\colon\mathbb{N}\to\mathbb{R}^{d} such that for any n\in\mathbb{N} , and for any x=x_{1}x_{2}\ldots x_{n}\in\{0,1\}^{n} , the following holds. Define: f_{1}=\ell(x_{1})+p(1),\ldots,f_{n}=\ell(x_{n})+p(n), and set (g_{1},\ldots,g_{n})=A_{C}\circ\ldots\circ A_{1}(f_{1}\ldots f_{n}). Then the following must hold. If x\in L , we have g_{1}^{1}>0 , and if x\notin L , we have g_{1}^{1}<0 . Note that in our definition, the positional encoding p does not take n , the input length, as an input. 3 Construction Lemma 1 . For any function f\colon\mathbb{N}\to\mathbb{R} , there exists a completely uniform transformer that, for any input length n , computes f(n) in every position in one layer. Proof. We need a positional encoding p\colon\mathbb{N}\to\mathbb{R} such that: \frac{p(1)+\ldots+p(n)}{n}=f(n), for every n (this average is computable via softmax with uniform weights), which is achievable by setting p(1)=f(1) and p(i)=if(i)-(i-1)f(i-1) for i\geq 2 , ∎ Theorem 1 . There exists a 3-layer completely uniform transformer, recognizing the parity language. Proof. Assume that on input we get x=x_{1}\ldots x_{n}\in\{0,1\}^{n} . Denote \Sigma=x_{1}+\ldots+x_{n} . Let us first give a construction, assuming that \Sigma\geq 1 , that is, that not all input bits are 0. We explain how to get rid of this assumption in the end of the proof. The plan of the proof is as follows. At the first two layers, we need to compute a sequence of numbers a_{1},\,\,a_{2},\ldots,\,\,a_{n}, with the property that a_{\Sigma} is strictly larger than any other number in the sequence. Assuming we have done this, at the last layer we can compute the following: \frac{\sum\limits_{i=1}^{n}\exp\{a_{i}f(n)\}\cdot(-1)^{i}}{\sum\limits_{i=1}^{n}\exp\{a_{i}f(n)\}}. (1) using a positional encoding i\mapsto(-1)^{i} and Lemma 1 for a function f\colon\mathbb{N}\to\{0,1\} of our choice. Our goal for ( 1 ) is to encode parity, i.e., ( 1 ) must be positive if \Sigma is even and negative otherwise. Indeed, the limit of ( 1 ) as f(n)\to+\infty is (-1)^{\Sigma} , because a_{\Sigma}>a_{i} for i\neq\Sigma . For any fixed n , there are finitely many inputs of length n . Hence, we can take f(n) large enough so that, for any input x of length n , the difference between ( 1 ) for this x and (-1)^{\Sigma} is at most 1/3 . It remains to calculate a sequence a_{1},\ldots,a_{n} with this property at the first two layers. By Lemma 1 , we compute \ln n at every position in the first layer. Then, for an absolute constant \delta\in\mathbb{R} , to be specified later, we set \alpha=e^{\delta} and use the second layer to compute the following expression at every position: \gamma=\frac{\sum\limits_{i=1}^{n}e^{(-\ln(n)+\delta)\cdot(1-x_{i})}\cdot x_{i}}{\sum\limits_{i=1}^{n}e^{(-\ln(n)+\delta)\cdot(1-x_{i})}}=\frac{\Sigma}{\Sigma+(n-\Sigma)\cdot\frac{\alpha}{n}}=\frac{1}{1+\frac{\alpha}{\Sigma}-\frac{\alpha}{n}}. (2) It now suffices to prove the following lemma. Lemma 2 . There exists \alpha\in(0,1) such that for all n and \Sigma\in\{1,\ldots,n\} , the maximum of the expression: a_{i}=-\left|\gamma-1+\left(\frac{\alpha}{i}-\frac{\alpha}{n}\right)-\left(\frac{\alpha^{2}}{i^{2}}+\frac{\alpha^{2}}{n^{2}}\right)\right| over i\in\{1,\ldots,n\} is attained uniquely at i=\Sigma , where \gamma is defined by ( 2 ). Indeed, once we have computed \gamma , we can express a_{i} by computing \frac{\alpha}{n}-\frac{\alpha^{2}}{n^{2}} in every position by Lemma 1 , and using a positional encoding i\mapsto\frac{\alpha}{i}-\frac{\alpha^{2}}{i^{2}} . We can then calculate the absolute value using a constant-size ReLU network. Proof of Lemma 2 . Observe that: \left|\frac{1}{1+z}-(1-z+z^{2})\right|=\frac{z^{3}}{1+z}\leq z^{3} for z\geq 0 . Applying this to z=\frac{\alpha}{\Sigma}-\frac{\alpha}{n} , we get: \gamma=1-\left(\frac{\alpha}{\Sigma}-\frac{\alpha}{n}\right)+\left(\frac{\alpha}{\Sigma}-\frac{\alpha}{n}\right)^{2}+\rho, for some \rho with |\rho|\leq\frac{\alpha^{3}}{\Sigma^{3}} . We now can write: a_{i}=-\left|\left(\frac{\alpha}{i}-\frac{\alpha}{\Sigma}\right)+\left(\frac{\alpha^{2}}{\Sigma^{2}}-\frac{\alpha^{2}}{i^{2}}\right)-\frac{2\alpha^{2}}{\Sigma n}+\rho\right| Denoting b_{i}=\left(\frac{\alpha}{i}-\frac{\alpha}{\Sigma}\right) , c_{i}=\left(\frac{\alpha^{2}}{\Sigma^{2}}-\frac{\alpha^{2}}{i^{2}}\right) and \lambda=-\frac{2\alpha^{2}}{\Sigma n} , we get: a_{i}=-|b_{i}+c_{i}+\lambda+\rho| For i=\Sigma , we get a_{\Sigma}=-|\lambda+\rho| . To prove that the maximum of a_{i} is attained at i=\Sigma , we show that: (1/10)\cdot|b_{i}|>|c_{i}|,\qquad(1/10)\cdot|b_{i}|>|\lambda|,\qquad(1/10)\cdot|b_{i}|>|\rho|,\qquad\text{ for }i\neq\Sigma, which implies that: \displaystyle-a_{i}=|b_{i}+c_{i}+\lambda+\rho|\geq|b_{i}|-|c_{i}|-|\lambda|-|\rho|\geq(7/10)|b_{i}|>|\lambda|+|\rho|\geq-a_{\Sigma}. Firstly, for i\neq\Sigma , observe: \frac{|b_{i}|}{|c_{i}|}=\frac{i\Sigma}{\alpha(\Sigma+i)}\geq\frac{1}{2\alpha}, (3) where the last inequality is due to the fact that i,\Sigma\geq 1 . Next, for i\neq\Sigma , observe: \frac{|b_{i}|}{|\lambda|}=\frac{\frac{\alpha|i-\Sigma|}{i\cdot\Sigma}}{\frac{2\alpha^{2}}{\Sigma n}}\geq\frac{1}{2\alpha}. (4) Finally, for i\neq\Sigma , write: \frac{|b_{i}|}{\rho}\geq\frac{\frac{\alpha|i-\Sigma|}{i\cdot\Sigma}}{\frac{\alpha^{3}}{\Sigma^{3}}}\geq\frac{1}{\alpha^{2}}\cdot\frac{|i-\Sigma|\cdot\Sigma}{i} If \Sigma\geq i/2 , since |i-\Sigma|\geq 1 , we obtain \frac{|b_{i}|}{\rho}\geq\frac{1}{2\alpha^{2}} . If \Sigma\leq i/2 , we obtain |i-\Sigma|\geq i/2 , implying the same bound \frac{|b_{i}|}{\rho}\geq\frac{1}{2\alpha^{2}}, (5) since \Sigma\geq 1 . Taking \alpha=1/100 , we obtain that the right-hand sides of the inequalities in ( 3 ), ( 4 ), ( 5 ) are all larger than 10, as required. ∎ Finally, we explain how to get rid of the assumption \Sigma\geq 1 . Let us denote the value of the expression ( 1 ) by \theta . We have that \theta is positive for even \Sigma\geq 1 , and \theta is