SOURCE-LINKED INTELLIGENCE

The Head Complexity of Boolean Functions in Single-Layer Attention

arXiv · AI, language, vision and robotics · article · Sep 3, 2026 · UTC

What can a single layer of self-attention compute? We study head complexity: the minimum number of attention heads required to compute a function in a one-layer attention-only model. We establish an exact hierarchy under this measure: $k$ heads compute $k$-bit parity but cannot compute $(k+1)$-bit parity. The lower bound is unconditional in the two resources a transformer might otherwise exploit; it holds at unbounded embedding dimension and unbounded numerical precision. The proof rests on an alternating-sum obstruction: after clearing the softmax denominators, every monomial in the resulting

Read original source ↗ Open in workspace

recordType

paper

region

Global