# Lower bounds for one-layer transformers that compute parity

arXiv: https://arxiv.org/abs/2605.12171 · HTML: https://mlsanity.com/paper/2605.12171/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 6 references that are in the map.
- First posted on arXiv 12 May 2026.

## Builds on (most cited first, 2 of 2)

- [Neural networks and rational functions](https://mlsanity.com/paper/1706.03301/) (2017)
- [Parity, Sensitivity, and Transformers](https://mlsanity.com/paper/2602.05896/) (2026)

## Abstract (arXiv)

This note shows that no self-attention layer post-processed by a rational function can sign-represent the parity function unless the product of the number of heads and the degree of the post-processing function grows linearly with the input length. Combining this lower bound with rational approximation of ReLU networks yields a margin-dependent extension for self-attention layers post-processed by ReLU networks.