Parity, Sensitivity, and Transformers
Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wałȩga · 2026
Read Parity, Sensitivity, and Transformers by Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wałȩga (2026) 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-2602-05896.txt.
Description
Parity, deciding whether a binary string has an even or odd number of ones, is a litmus test for what a neural architecture can compute. Alexander Kozachinskiy, Tomasz Steifer, and Przemysław Wałęga settle an open problem about transformers and parity. They show the minimum number of layers a transformer needs for parity is two, and that one layer cannot do it.
The proof compares growth rates: the average sensitivity of a one layer transformer grows slower than that of parity itself. The authors also give a new construction that computes parity while dropping several impractical assumptions of earlier ones, such as length dependent position codes and hard attention. Their practical version uses four layers with ordinary softmax attention and length independent, polynomially bounded encodings. It maps the boundary between what attention can and cannot compute.
Catalog record
| CREATOR | Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wałȩga |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-05896