Head complexity of one-layer attention for Boolean functions

How many attention heads are required to compute a Boolean function in a one-layer attention-only transformer with a dedicated query token and linear threshold readout? The model uses the paper’s additive token/position convention, so bounds are architecture-specific.

Why it matters and what counts as progress

Why it matters: Exact head counts connect Boolean complexity to a specific attention architecture and separate expressivity from training performance.

What counts as progress: Determine exact head counts or matching lower and upper bounds, such as the proposed n-head requirement for n-bit parity.

How the problem developed

3 Sept 2026 · Parity hierarchy [1]
Rajmohan Rajaraman, Ravi Sundaram and Amanuel Tesfaye In a one-layer attention-only model, proved that k heads compute k-bit parity but cannot compute (k+1)-bit parity, even with unbounded embedding dimension and numerical precision.
18 Oct 2026 · Formal characterization [2]
Karthik Viswanathan, Plamen Dimitrov, Stefano Rocca and Sarayu Sirikonda Reported a Lean-formalized characterization: in their fixed-query model with additive positional embeddings, a symmetric Boolean function needs one head per change across consecutive Hamming-weight levels.

AI contribution

Formally Verified Autoresearch for Analyzing the Expressivity of Multi-Head Attention

Karthik Viswanathan, Plamen Dimitrov, Stefano Rocca, Sarayu Sirikonda

For the paper’s one-layer, attention-only transformer on Boolean inputs with a dedicated query token and linear threshold readout, the autonomous core results characterize head complexity by sums of admissible linear-fractional functions, bound it below by threshold degree, and determine it exactly for symmetric Boolean functions by the number of sign changes. In particular, n-bit parity requires exactly n heads.

AI involvementAI-autonomous

ImportanceNotable

Technical verificationFormal (Lean)

Human understandingFew