Parity, Sensitivity, and Transformers
Kozachinskiy, Steifer, Wałȩga · cs.LG,cs.AI · 2026-09-05 · 原文 · 证据态 未学
Understanding what neural architectures can and cannot compute is a central challenge in the theory of AI. One of the fundamental problems in this context is the PARITY task, which asks whether the number of 1s in a binary input sequence is even or odd. PARITY is one of the central tasks studied in the theory of computation, yet it remains surprisingly unclear under which conditions transformers can or cannot solve it. In this paper, we show that the minimal number of layers a transformer needs to compute PARITY is two. In particular, we solve the open problem asking whether a one-layer transformer can compute PARITY. We answer it negatively by showing that average sensitivity of a one-layer transformer grows slower than that of PARITY. Furthermore, we show a new construction for transformer that computes PARITY, which improves on the existing constructions by removing a number of impractical assumptions. In particular, the existing transformers for PARITY rely on such impractical assumptions as length-dependent positional encoding, hardmax, layernorm without a regularisation parameter, or incompatibility with causal masking. We show that these assumptions can be removed, at the co
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
Understanding what neural architectures can and cannot compute is a central challenge in the theory of AI.
One of the fundamental problems in this context is the PARITY task, which asks whether the number of 1s in a binary input sequence is even or odd.
2. 领域脉络
本文类目：cs.LG、cs.AI，属于其所在研究脉络的最新进展。
3. 机制拆解
PARITY is one of the central tasks studied in the theory of computation, yet it remains surprisingly unclear under which conditions transformers can or cannot solve it.
In this paper, we show that the minimal number of layers a transformer needs to compute PARITY is two.
In particular, we solve the open problem asking whether a one-layer transformer can compute PARITY.
4. 证据与数字
摘要未给出量化结果——留意原文的实验与数据。
5. 反例与边界
摘要未声明局限与反例——这是需要警惕的信号，精读时先问边界。
6. 跨领域连接与意外收获
横跨 2 个类目（cs.LG、cs.AI），关注其在你兴趣板块间的迁移面。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。
主动回忆
先合上内容自己复述，再点「显示」核对，然后如实自评。评分即时进 FSRS 排程。
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
Understanding what neural architectures can and cannot compute is a central challenge in the theory of AI.
One of the fundamental problems in this context is the PARITY task, which asks whether the number of 1s in a binary input sequence is even or odd.
2. 领域脉络
本文类目：cs.LG、cs.AI，属于其所在研究脉络的最新进展。
3. 机制拆解
PARITY is one of the central tasks studied in the theory of computation, yet it remains surprisingly unclear under which conditions transformers can or cannot solve it.
In this paper, we show that the minimal number of layers a transformer needs to compute PARITY is two.
In particular, we solve the open problem asking whether a one-layer transformer can compute PARITY.
4. 证据与数字
摘要未给出量化结果——留意原文的实验与数据。
5. 反例与边界
摘要未声明局限与反例——这是需要警惕的信号，精读时先问边界。
6. 跨领域连接与意外收获
横跨 2 个类目（cs.LG、cs.AI），关注其在你兴趣板块间的迁移面。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。