The Head Complexity of Boolean Functions in Single-Layer Attention

• URL: http://arxiv.org/abs/2609.04046v1
• Date: Thu, 03 Sep 2026 16:22:02 GMT
• Title: The Head Complexity of Boolean Functions in Single-Layer Attention
• Abstract summary: We study the minimum number of attention heads required to compute a function in a one-layer attention-only model.<n>We establish an exact hierarchy under this measure: $k$ heads compute $k$-bit parity but cannot compute $(k+1)$-bit parity.<n>We also establish compactness bounds for embedding dimension and numerical precision.
• Score: 2.2727733134290813
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $Ω(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.

Related papers

• Attention-based representations for multi-task computation [8.34204538904959]
  We establish bounds on the number of heads required in two simple and concrete multi-task scenarios.<n>In the first scenario, a vector representation is sought so that linear predictors can compute both the smallest and largest numbers in a given list.<n>In the second scenario, a vector representation is sought so that a threshold function can compute the XOR of a given string of $n$ bits.
  arXiv  Detail & Related papers  (2026-08-04T21:52:04Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP)<n>For every fixed $in(0,1)$, there are constants $A_,c_>0$.<n>Unit-sphere MAX-IP matrix is an exact two-valued affine image of the DNF pattern matrix with gap of at least $8$.
  arXiv  Detail & Related papers  (2026-07-22T17:27:20Z)
• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
  We prove two lower bounds for the first order complexity of minimizing a $d$-dimensional $1$-Lipschitz convex function over the unit ball with $m$ bits of memory.<n>We first show that any such (possibly randomized) algorithm must make $tilde(fracd2sqrtm)$ oracle queries.<n>For deterministic optimization algorithms, we show that $tilde(mind1.6,fracd8/3m2/3)$ queries are required.
  arXiv  Detail & Related papers  (2026-07-21T00:40:59Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• On the Computational Hardness of Transformers [14.73362105392153]
  We show that transformers can be computed more efficiently than $LH$ independent evaluations of attention.<n>In the small embedding regime, computing $LH$ attention heads separately takes $LHN2 + o(1)$ time.<n>In the large embedding regime, one can compute $LH$ attention heads separately using $LHN+ o(1)$ arithmetic operations.
  arXiv  Detail & Related papers  (2026-03-11T21:48:43Z)
• An Efficient Computational Framework for Discrete Fuzzy Numbers Based on Total Orders [41.99844472131922]
  We introduce algorithms that exploit the structure of total (admissible) orders to compute the $textitpos$ function.<n>The proposed approach achieves a complexity of $mathcalO(n2 m log n)$, which is quadratic in the size of the underlying chain.<n>The results demonstrate that this formulation substantially reduces computational cost.
  arXiv  Detail & Related papers  (2025-11-21T09:35:07Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We present a novel characterization of rank, grounded in the well-known Transformer architecture.<n>We show that the rank of a function $f$ corresponds to the minimum number of emphChain of Thought steps required by a single-layer Transformer.<n>We also introduce the notion of the multi-head rank that captures multi-head single-layer transformers, and perform the analysis of PAC-learnability of the classes of functions with bounded multi-head rank.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Localization in 1D non-parametric latent space models from pairwise affinities [6.982738885923206]
  We consider the problem of estimating latent positions in a one-dimensional torus from pairwise affinities. We introduce an estimation procedure that provably localizes all the latent positions with a maximum error of the order of $sqrtlog(n)/n$, with high-probability.
  arXiv  Detail & Related papers  (2021-08-06T13:05:30Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
  We consider a standard distributed optimisation setting where $N$ machines aim to jointly minimise the sum of the functions $sum_i = 1N f_i (x)$. Our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the $N$ machines. We show that $Omega( Nd log d / Nvarepsilon)$ total bits need to be communicated between the machines to find an additive $epsilon$-approximation to the minimum of $sum_i = 1N
  arXiv  Detail & Related papers  (2020-10-16T08:10:02Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
  arXiv  Detail & Related papers  (2020-02-23T22:51:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.