Metraipolis › archive › dc_173a2fcdc29d

The Head Complexity of Boolean Functions in Single-Layer Attention — arXiv:2609.04046

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.04046
License (as archived)
CC0-1.0
Archived
2026-10-17T02:08:45.023Z
SHA-256 of the archived text
af79e2c6c04b648abdd5358ad0610690f2524e69183b940ce6caed2b7dbac6e1
Stable URL of this page
https://metraipolis.com/documento/dc_173a2fcdc29d

How to cite

The Head Complexity of Boolean Functions in Single-Layer Attention — arXiv:2609.04046 — arXiv (en), https://arxiv.org/abs/2609.04046 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_173a2fcdc29d (Metraipolis archive dc_173a2fcdc29d, sha256 af79e2c6c04b648abdd5358ad0610690f2524e69183b940ce6caed2b7dbac6e1)
BibTeX
@misc{dc173a2fcdc29d,
  title = {The Head Complexity of Boolean Functions in Single-Layer Attention — arXiv:2609.04046},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.04046},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_173a2fcdc29d; sha256 af79e2c6c04b648abdd5358ad0610690f2524e69183b940ce6caed2b7dbac6e1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.04046. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 decision polynomial omits at least one of the $k+1$ input bits, forcing its correlation with parity to vanish. The same obstruction yields lower bounds for related tasks, including the well-studied multi-hop induction-head task. We also establish compactness bounds for embedding dimension and numerical precision. Specifically, a compactness theorem shows that any function computable at all can be computed with embedding dimension and precision bounded by the discrete data of the task, namely, head count, alphabet size, and length. Thus, potentially unbounded dimension or precision provably cannot substitute for heads. Finally, we derive nearly matching universal bounds for general binary functions: $2^n$ heads suffice to compute every $n$-bit binary function, with one head per monomial in its multilinear expansion, while a counting argument shows almost all such functions require $\Omega(2^n/n^2)$ heads. This lower bound matches the upper bound to within a $\operatorname{poly}(n)$ factor, even when dimension and precision are unbounded. Together, these results characterize head requirements for Boolean computation in this model.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-04 in cs.LG).
Categorie arXiv: Computational Complexity (cs.CC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.04046 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T01:47:25.641Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).