Threshold Degree and the Head Complexity of Single-Layer Attention

A single layer of multi-head attention produces a vector representation from which a downstream predictor computes an output. We ask how many heads the layer needs when the predictor is a polynomial threshold function of degree $D$. For a symmetric Boolean function $f$ of threshold degree $T$, we prove that $H$ heads and a degree-$D$ readout compute $f$ if and only if $DH\ge T$. The lower bound allows arbitrary joint embeddings of token symbol and position, with unbounded embedding dimension and bit precision; the upper bound uses embeddings that depend on the token symbol alone, with value vectors of dimension at most $\min \{D,O(\log H)\}$. The characterization is therefore insensitive to the embedding class. We then extend it beyond symmetric functions. If $f(x)=F(|x_S|)$ for a designated subset $S\subseteq [n]$, the same characterization holds, with an upper bound that uses an additive embedding of symbol and position; such $f$ is asymmetric whenever $S$ is a proper subset of $[n]$, and no symbol-only embedding computes it at any $H$ or $D$. Taking $F$ to be parity gives a strict hierarchy in the head count at every fixed readout degree and input length: parity on $m$ coordinates requires exactly $\lceil m/D\rceil$ heads. Finally, we show that threshold degree does not govern the general case: at most $2^{O(H{n}^2)}$ functions are realizable with $H$ heads and a linear readout, and we exhibit a family of threshold degree $T$ in which almost every member requires $\Omega (n^{T-2})$ heads. Experiments on symmetric Boolean targets study the roles of $D$, $H$, and value-dimension in trained attention layers.