The Head Complexity of Boolean Functions in Single-Layer Attention

Summary

This theory paper introduces head complexity: the minimum number of attention heads a single-layer, attention-only transformer needs to compute a Boolean function exactly. The central result is an exact hierarchy: k heads compute k-bit parity — via a partial-fraction construction whose per-head denominators equal the Hamming weight plus the head index — while k heads provably cannot compute (k+1)-bit parity (Theorem 1). The lower bound is an alternating-sum argument: after clearing softmax denominators, every monomial of the decision polynomial depends on at most k of the k+1 input bits, so its signed sum vanishes. Since the argument never touches the embedding or arithmetic precision, compactness theorems (Theorems 3-4) show any computable function has a realization with dimension at most min{kL, qN}+1 and rational parameters of bit-length 2^{O(n_var log(k+1))}; neither resource can substitute for heads. The same obstruction yields a (k+1)-head lower bound for k-ESP, with a matching Cauchy-interpolation construction, and for the (k+1)-hop induction-head task. Universally, 2^n heads compute every n-bit function (one head per multilinear monomial), while Warren's sign-pattern bound shows almost all functions need Omega(2^n/n^2) heads. Limitations: the obstruction essentially repackages the classical degree-k polynomial-threshold-function containment (Lemma 8) plus parity's classical degree bound; coefficient precision of the parity and ESP constructions is unanalyzed; the model excludes MLPs and causal masking; and no explicit hard function is identified.