🤖 machine learning

Parity, Sensitivity, and Transformers

This paper resolves the open question of whether one-layer transformers can compute the PARITY task by proving they cannot due to sensitivity constraints, while simultaneously presenting a practical four-layer transformer construction that solves PARITY without relying on previously necessary impractical assumptions like length-dependent positional encoding or hardmax.

Original authors: Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wał\cega

Published 2026-05-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wał\cega

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very smart, but slightly rigid, robot how to play a simple game called "The Parity Game."

In this game, the robot is shown a long string of lights, some red (0) and some blue (1). The robot's only job is to answer one question: "Is the total number of blue lights even or odd?"

If there are 3 blue lights, the answer is "Odd." If there are 4, the answer is "Even."

This sounds easy to us, but for a specific type of AI architecture called a Transformer (the kind that powers many modern chatbots and translators), this game has been a mystery. Scientists have been arguing: How many "thinking layers" does this robot need to solve the game?

Here is what this paper discovered, explained simply:

1. The "One-Layer" Robot is Too Dumb

The authors first asked: Can a Transformer with just one layer of thinking solve this?

They proved the answer is no.

The Analogy: Imagine the robot is a person standing in a room full of people holding up red or blue cards. The person can only look at everyone at once and take a quick "average" glance.

The "Parity" game is incredibly sensitive. If you change just one person's card from red to blue, the answer flips completely (from Even to Odd).
The authors showed that a one-layer robot is too "smooth" and "lazy." It can't react sharply enough to a single change. It's like trying to detect a single pin drop in a hurricane by only listening to the average wind speed. The robot's "sensitivity" grows too slowly to catch the tiny, crucial changes needed to solve the game.

The Verdict: You need at least two layers of thinking to solve this.

2. The "Old Solutions" Had Too Many Hacks

Before this paper, other scientists had figured out how to build a Transformer that could solve the game, but they had to use some "cheats" or unrealistic settings:

The "Magic Ruler": They gave the robot a ruler that knew the exact length of the string before it started reading (e.g., "This string is exactly 1,000 characters long"). Real robots usually don't know the length of the sentence they are reading until they finish.
The "Perfect Switch": They used a "hard switch" that makes binary decisions instantly, rather than the "soft, fuzzy" probability switches real robots use.
The "Zero-Error" Filter: They removed a safety filter (called LayerNorm) that usually prevents the robot's numbers from exploding into infinity.

These solutions worked on paper but wouldn't work in the real world because they relied on assumptions that don't exist in actual AI training.

3. The New, Real-World Solution

The authors of this paper built a new robot that solves the Parity game without using any of those cheats.

No Magic Ruler: It uses a "length-independent" positional encoding. It doesn't need to know the total length of the string in advance; it just looks at where things are relative to each other.
Soft Switches: It uses standard "soft" attention (the kind used in real chatbots).
Safety Filters: It works without needing to remove safety filters.
The Catch: To do this without cheats, the robot needs four layers of thinking instead of two.

The Analogy:
Think of the old "cheat" solutions as a magician who solves a puzzle by peeking at the answer key hidden under the table.
The new solution is like a master detective who solves the same puzzle by carefully examining every clue, cross-referencing them, and doing a bit more work (four layers instead of two). It's a bit slower and requires more "brain power" (depth), but it works in a real courtroom, not just on a magic stage.

Summary of the Breakthrough

Lower Bound: A Transformer with only one layer is mathematically incapable of solving the Parity game. It's not a training problem; the robot literally doesn't have the architecture to do it.
Upper Bound: You can solve the game with a Transformer, but to do it in a realistic way (without cheating with length-dependent tricks or removing safety filters), you need four layers.

The paper essentially draws a clear line in the sand: "If you want a realistic AI to count odd and even numbers, give it at least four layers of depth. Anything less, and it's mathematically impossible."

Based on the provided text, here is a detailed technical summary of the paper "Parity, Sensitivity, and Transformers."

Problem Statement

The paper addresses the fundamental question of the expressivity of Transformer architectures, specifically regarding the PARITY task. PARITY is a Boolean function that outputs 1 if the number of 1s in a binary input sequence is odd, and 0 otherwise. It is a canonical problem in theoretical computer science known for its high sensitivity (flipping any single bit changes the output).

While previous research has established that Transformers with hard attention mechanisms (specifically Unique Hard Attention or UHAT) cannot compute PARITY in constant depth, the capabilities of Transformers with soft (softmax) attention remain less clear. Existing constructions for soft-attention Transformers capable of computing PARITY rely on "impractical" assumptions, such as:

Positional encodings that depend on the total input length ( $n$ ).
Hard attention mechanisms.
Layer normalization with a regularization parameter $\epsilon = 0$ .
Incompatibility with causal masking.

Furthermore, it remained an open problem whether a single-layer Transformer could compute PARITY.

Methodology

The authors employ two distinct methodological approaches to address the lower bound and the upper bound (construction) of Transformer expressivity for PARITY.

1. Lower Bound via Average Sensitivity
To prove that a one-layer Transformer cannot compute PARITY, the authors utilize the concept of average sensitivity.

Definition: The average sensitivity of a function $f$ is the expected number of input bit positions such that flipping the bit changes the function's output. For PARITY, this value is exactly $n$ (linear growth).
Logic: The authors model the computation of a one-layer Transformer as a function expressible in the first-order logic of real numbers $(\mathbb{R}, <, +, \cdot)$ . By applying the Tarski-Seidenberg theorem (quantifier elimination), they demonstrate that any function computed by a one-layer Transformer can be represented as a Boolean combination of a fixed number of low-degree polynomial threshold functions (PTFs).
Bounding: Citing a result by Kane, they establish that the average sensitivity of low-degree PTFs grows at a rate of $O(\sqrt{n} \cdot (\log n)^{O(1)})$ . Since the average sensitivity of PARITY grows linearly ( $n$ ), a one-layer Transformer cannot compute it.

2. Upper Bound via New Construction
To demonstrate that PARITY is computable by a Transformer without impractical assumptions, the authors propose a new four-layer construction.

Mechanism: The construction uses softmax attention and length-independent, polynomially bounded positional encodings. It avoids layer normalization and works under both full-attention and causal masking.
Algorithmic Strategy:
1. Layer 1: Computes a weighted sum of input bits to derive a value $\gamma$ related to the count of 1s ( $\Sigma$ ).
2. Layer 2: Uses positional encodings ( $i \mapsto (\ln i, i^{10})$ ) and the value $\gamma$ to compute a weighted average $\Gamma$ . This value approximates a function $f(\rho)$ that encodes information about $\Sigma$ .
3. Layer 3: Constructs attention weights $L_{i,n}$ that are highly concentrated on the position $i = \Sigma$ . This is achieved by using the value $\Gamma$ (computed in Layer 2) to approximate a specific quadratic form that peaks at $i = \Sigma$ . The authors prove that for the correct position, the attention weight is significantly larger (by a margin of $\Omega(n^6)$ ) than for any other position.
4. Layer 4: Computes a weighted sum of $(-1)^i$ using the concentrated attention weights. The result is a value $z$ close to $(-1)^\Sigma$ , allowing the final layer to distinguish between even and odd parity.
Handling Large Inputs: To handle cases where the number of 1s ( $\Sigma$ ) is large, the construction splits the input into $M$ subsequences (where $M$ is an even constant), computes the parity of each in parallel, and aggregates the results.

Key Contributions and Results

Resolution of the One-Layer Open Problem: The paper definitively answers the open question of whether a one-layer Transformer can compute PARITY. The result is negative. The authors prove that the average sensitivity of any function computable by a one-layer Transformer is bounded by $O(\sqrt{n} \cdot (\log n)^{O(1)})$ , which is insufficient for the linear sensitivity of PARITY.
Improved Construction for PARITY: The authors present a new four-layer Transformer construction that computes PARITY. This construction improves upon prior work (e.g., Chiang and Cholak, 2022; Yang et al., 2025) by removing several restrictive assumptions:
- It uses soft attention (softmax) rather than hard attention.
- It employs length-independent positional encodings.
- It requires no layer normalization (or specifically, does not rely on $\epsilon=0$ ).
- It is compatible with causal masking.
- The positional encodings are polynomially bounded, making them feasible for practical input lengths.
Depth Requirements: The paper establishes that while one layer is insufficient, four layers are sufficient under realistic design constraints. This refines the understanding of the depth requirements for computing highly sensitive functions.

Significance

The paper advances the theoretical understanding of Transformer architectures by precisely characterizing their depth requirements for the PARITY task. By linking Transformer expressivity to the average sensitivity of Boolean functions, the authors provide a rigorous lower bound that rules out one-layer models. Simultaneously, by providing a four-layer construction that adheres to standard architectural practices (soft attention, causal masking, bounded encodings), the paper demonstrates that PARITY is computable by Transformers without resorting to theoretical artifacts.

The authors note that these results help explain why Transformers might struggle to generalize on tasks like PARITY during training: the function requires a specific depth and architectural configuration that may not be easily learned via standard gradient descent methods if the model is too shallow or constrained. The work complements existing literature on the expressivity of hard-attention models and provides a more realistic baseline for the capabilities of soft-attention Transformers.