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

CREATORAlexander Kozachinskiy, Tomasz Steifer, Przemysław Wałȩga
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-05896

Browse the full library · About the Tower of Babel