Source-linked AI summary
The Head Complexity of Boolean Functions in Single-Layer Attention
Rajmohan Rajaraman, Ravi Sundaram, Amanuel Tesfaye
TL;DR
The paper asks how many attention heads a one-layer attention-only transformer needs to compute Boolean functions, and whether unbounded dimension or precision can replace heads. It proves an exact parity hierarchy, bounds continuous resources by discrete task data, and obtains nearly matching universal bounds for general binary functions.
Problem
The paper asks for a precise head-complexity measure of one-layer self-attention and whether embedding dimension or numerical precision can substantially increase capability at fixed head count.
Method
The paper combines parity-based lower bounds, a compactness argument for dimension and precision, and monomial-based constructions with counting bounds for general Boolean functions.
Results
Head count forms an exact hierarchy: k heads compute k-bit parity but not (k+1)-bit parity; dimension and precision collapse to discrete task data, while almost all n-bit functions require Ω(2^n/n^2) heads and all are computable with 2^n heads.
Takeaways & Limitations
Head count strictly orders expressivity in the one-layer attention-only model, and unbounded dimension or precision cannot eliminate the need for additional heads.
Takeaways & Limitations
The paper does not identify an explicit natural function with exponential head complexity, and its worst-case bounds remain separated by a poly(n) factor.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper formalizes attention-head count as a complexity measure for one-layer attention and establishes exact and near-tight Boolean-function bounds. Its results use an alternating-sum obstruction, compactness arguments, interpolation, and counting to show that additional heads strictly expand expressivity.
- 1.1 Summary of Results: k heads compute k-bit parity but cannot compute (k+1)-bit parity, yielding a strict per-head hierarchy even with unbounded dimension and precision.The result makes head count an exact complexity measure for one-layer attention.
- 1.1 Summary of Results: The alternating-sum obstruction extends the parity lower bound to k-ESP and the (k+1)-hop induction-head task.After clearing softmax denominators, each polynomial monomial omits an input bit, forcing zero correlation with parity.
- 1.1 Summary of Results: A compactness theorem bounds realizable embedding dimension and numerical precision using discrete task data, so these resources cannot substitute for heads.The argument factors computation through a finite cross-Gram matrix and finitely many strict polynomial inequalities.
- 1.1 Summary of Results: 2^n heads compute every n-bit Boolean function, while counting shows almost all require Ω(2^n/n^2), matching within a poly(n) factor.The upper bound uses one additive head per monomial; the lower bound counts realizable sign patterns.
- 1.1 Summary of Results: The paper’s lower bounds hold for the general joint embedding regime, while its upper bounds use restricted additive embeddings.This pairing gives the strongest comparison between the two regimes described in the paper.
- Overview of Techniques: The matching parity construction uses Hamming-weight interpolation, with rational terms whose signs alternate across the k+1 possible weights.Partial-fraction coefficients make the k-term decision statistic match parity on Hamming levels 0 through k.
2 Preliminaries
The preliminaries define a one-layer, attention-only transformer that maps Boolean sequences to one output bit using softmax attention and arg-max or equivalent affine read-outs. They also distinguish unrestricted joint embeddings from restricted additive embeddings.
- 2 Preliminaries: The model reads x ∈ {0,1}^n as n token positions followed by a fixed query token and predicts one output bit.Token embeddings are written v_b,i = Φ(b,i), with a separate query embedding v_?.
- 2 Preliminaries: In the general joint regime token vectors are unrestricted, whereas the additive regime requires v_b,i = τ_b + π_i.Every additive model is therefore also a joint model.
- 2 Preliminaries: Each of k heads applies an attention matrix and value matrix, and the shared output projections produce two logits at the query position.The model uses softmax(v_? A_j X^⊤) X V_j for each head before read-out.
- 2 Preliminaries: Arg-max read-out predicts 1 exactly when the output-1 logit exceeds the output-0 logit, with ties resolved toward 0.The transformer computes f when this condition agrees with f(x) on every input.
- 2 Preliminaries: Only the difference between the two logits matters, reducing the Boolean decision to a scalar ratio-of-sums condition.The paper also uses an affine scalar read-out, which computes exactly the same Boolean functions at every head count.
3 The Exact Parity Hierarchy
The one-layer attention-only model has an exact head hierarchy: k heads compute k-bit parity but cannot compute (k+1)-bit parity. An alternating-sum obstruction proves the lower bound, while a matching rational-function construction achieves the upper bound and extends the obstruction to related tasks.
- Head-count hierarchy: One more head strictly increases expressivity, with (k+1)-bit parity marking the boundary for k-head models.The hierarchy is defined with all other resources unbounded, and padding with zero-valued heads gives nested head-count classes.
- Lower bound: k heads cannot compute (k+1)-bit parity, even with unbounded embedding dimension and numerical precision.The theorem rules out every parameter choice satisfying the required signed inequalities for all inputs.
- The alternating-sum obstruction: After clearing positive softmax denominators, every decision-polynomial monomial depends on at most k of the k+1 input bits, so its alternating sum vanishes.A free input coordinate cancels each monomial, forcing the full signed sum to be zero and contradicting the strict parity inequalities.
- Beyond parity: The same obstruction yields lower bounds for k-ESP and the (k+1)-hop induction-head task.These tasks satisfy the general condition that more binary coordinates are exposed than there are heads.
- Matching upper bound: k heads suffice for k-bit parity, using an embedding dimension of k+3 and a signed sum of affine-over-linear terms indexed by Hamming weight.The construction chooses denominators c+j and affine numerator gaps so the resulting rational function has sign (−1)^c at every Hamming level.
4 Compactness: Dimension and Precision Are Bounded by the Discrete Data
The compactness results show that continuous resources cannot replace heads: any computable function admits bounded-dimensional, bounded-precision realizations determined by the task’s discrete parameters. The proof factors computation through a finite cross-Gram matrix and then uses polynomial-inequality stability to obtain rational parameters.
- Compactness theorem: Any computable function has a realization whose embedding dimension and numerical precision are bounded by head count, alphabet size, and sequence length.Thus unbounded dimension or precision does not add expressivity beyond what these discrete task parameters permit.
- Precision compactness: Clearing softmax denominators yields finitely many strict polynomial inequalities, enabling rational approximation and bounded-bit parameter realizations.The resulting realization can use embedding dimension at most qN+1.
- Finite representation: The computation depends on parameters only through a finite cross-Gram matrix of inner products between effective head vectors and token embeddings.Token-token products and products within the parameter-vector family never enter the computed function.
- Dimension compactness: Every realization requires dimension at least rank(M), while any prescribed cross-Gram matrix of rank r is realizable in dimension r+1.For binary outputs, the least sufficient dimension is bounded by min(2k, qN)+1.
- Dimension compactness: For the paper’s binary tasks with N=Θ(k), the dimension bound becomes O(k), matching the linear dimension used by its constructions.The sharper additive-embedding bound replaces qN with q+N when additive realizability is preserved.
5 Universal Bounds for General Binary Functions
A single attention layer can compute every n-bit Boolean function with at most 2^n heads, while almost all functions require Ω(2^n/n^2) heads even with unrestricted dimension and precision.
- 5.1 Universal Upper Bound: the Monomial Vote: The upper-bound construction relies on monotone terms as the primitive computation supplied by individual additive heads.Each monotone term detects when every bit in a selected subset is on, and monomial votes combine these terms to realize arbitrary functions.
- 5.1 Universal Upper Bound: the Monomial Vote: 2^n heads suffice for every n-bit Boolean function, using one additive head per monomial in its multilinear expansion.The construction uses embedding dimension O(n) and O(n)-bit parameters.
- 5.2 Counting the realizable functions: Almost all Boolean functions require Ω(2^n/n^2) heads, narrowing the universal upper and lower bounds to a poly(n) factor.The counting argument applies to the general joint embedding, including unbounded dimension and numerical precision.
- 5.2 Counting the realizable functions: After reduction, a k-head transformer depends on at most 4kn + 2k scalar weights and values, independently of embedding dimension and precision.This dimension- and precision-free reduction enables the subsequent polynomial sign-pattern count.
- 5.2 Counting the realizable functions: Warren’s sign-pattern bound limits k-head transformers to 2^O(kn^2) realizable functions, yielding the Ω(2^n/n^2) lower bound.The decision behavior is represented by signs of 2^n low-degree polynomials in O(kn) variables.
6 Conclusion
The paper establishes head count as a precise complexity measure for one-layer attention, with exact parity thresholds, bounded continuous resources, and near-tight generic Boolean bounds. It leaves explicit exponentially hard functions and depth-versus-head separations as open problems.
- 6 Conclusion: Head count forms an exact per-head hierarchy calibrated by parity, while dimension and precision collapse to discrete task data.The generic n-bit head complexity is 2^n/poly(n).
- 6 Conclusion: Almost every Boolean function has head complexity 2^n/poly(n), but the counting argument identifies no explicit natural hard family.Finding such a family would complement the universal counting lower bound with a concrete witness.
- 6 Conclusion: The worst-case upper and lower bounds remain separated by a poly(n) factor: 2^n versus 2^n/n^2.Closing this gap would determine the exact worst-case head complexity of a single layer.
- 6 Conclusion: It remains open whether additional depth can compute an explicit family with polynomial heads per layer that requires exponentially many heads in one layer.Such a separation would clarify when depth reduces head requirements.
- 6 Conclusion: The next target is an explicit function that provably breaks a fixed head budget within one layer or across layers.The paper characterizes the budget but does not yet name the functions that exceed it.
7 Related Work
The paper positions head count as a computational resource distinct from depth, precision, and dimension, extending prior one-layer attention separations to an exact k-versus-(k+1) hierarchy. Its parity result sharpens earlier qualitative and asymptotic lower bounds.
- Attention heads as a resource: Prior work treats attention heads as separate computational units, including mechanistic studies of recognizable head-level subroutines.The paper extends the two-head ESP separation to an exact k-versus-(k+1) hierarchy.
- One-layer lower-bound techniques: Related transformer theory studies limitations arising from depth, feed-forward computation, communication complexity, precision, and dimension-resource tradeoffs.The present setting isolates head count in a one-layer attention-only model.
- Parity and formal-language limitations: Earlier parity results established one-layer hardness or linear head lower bounds, but not an exact head threshold.This paper’s novelty is the unit-tight threshold together with a matching upper bound.
- Universality, positional encodings, and scope: Universality and Turing-completeness results typically use resources outside this exact hierarchy setting, such as extra layers, feed-forward computation, approximation, or unbounded decoding time.The paper instead gives an exact finite-computation construction for arbitrary Boolean functions in its restricted model.
A.1 Equivalence of the two read-outs
The appendix shows that two-logit arg-max and affine scalar read-outs compute the same Boolean functions at every head count, using one added constant coordinate to encode affine thresholds. It then constructs parity through a rational output gap whose sign alternates with Hamming weight.
- A.1 Equivalence of the two read-outs: Two-logit arg-max and affine scalar read-outs are equivalent on Boolean tasks at every head count.The forward direction uses ω = w1 − w0 and zero threshold; the reverse adds one embedding and value coordinate but no head.
- A.1 Equivalence of the two read-outs: The reverse simulation appends a constant-one coordinate so the arg-max read-out can represent a nonzero affine threshold.The attention core and original coordinates remain unchanged.
- Parity construction: For parity, the construction sets embedding dimension to k + 3, encoding token values in two coordinates and positions in the remaining coordinates.Head-specific scores are chosen so the resulting rational output gap depends on Hamming weight.
- Parity construction: The rational gap has sign (−1)^c for every Hamming weight c from 0 through k, matching the parity sign.A sufficiently large finite masking parameter preserves all strict inequalities, so the transformer outputs parity.
A.3 Compactness
The compactness argument replaces arbitrary realizers with equivalent models whose dimension and numerical precision are bounded by the task’s discrete parameters. It uses algebraic-cell stability to preserve decisions while rationalizing scores and model parameters.
- A.3 Compactness: The proof first makes all comparisons strict, yielding a nonempty open semialgebraic realizing cell whose rational points can be bounded using standard point-bit-length estimates.Small label-dependent shifts preserve prior winners while resolving ties, and positivity constraints ensure exponentiated attention weights remain valid.
- A.3 Compactness: A bounded rational point in exponentiated-score coordinates is transferred to rational log-scores through quantitative stability of the decision polynomials.Clearing denominators gives positive integer numerators, while mean-value bounds preserve every signed decision within a sufficiently small neighborhood.
- A.3 Compactness: The resulting parameter bound scales as 2^O(n_var log(k+1)), so precision depends on head count and task size rather than arbitrary real-valued parameters.The bound is stated through the intermediate bit-length estimate β = O(βδn_var + τ + δlog(n_var + δ)).
- A.3 Compactness: Any computable function admits an equivalent rational transformer with embedding dimension at most qN + 1 and parameter bit-length bounded by the compactness estimate.The construction enumerates occurring token types, uses basis embeddings, and realizes rational score and value-projection tables.
- A.3 Compactness: For k-ESP, the task uses a finite endpoint vocabulary and k+3 input tokens, so its compactness bounds depend on k, vocabulary size, and input length.The k-ESP input contains k selector bits, two endpoints, and a query token.
B.2 Lower Bound for 𝑘-ESP
The k-ESP lower bound reduces arbitrary endpoint vocabularies to a two-symbol restriction that exposes k+1 binary coordinates. Clearing softmax denominators produces a decision polynomial whose monomials omit one coordinate, making the required parity signs impossible.
- B.2 Lower Bound for k-ESP: No one-layer k-head transformer solves k-ESP over any finite endpoint vocabulary with at least two symbols.The proof fixes two endpoints, considers both orders, and obtains a stronger infeasibility statement on that restricted family.
- B.2 Lower Bound for k-ESP: After clearing positive denominators, every monomial in the decision polynomial depends on at most k of the k+1 free bits.Each numerator or denominator factor depends on at most one coordinate, so one coordinate is absent from every product term.
- B.2 Lower Bound for k-ESP: The alternating sum over all free-bit assignments annihilates every monomial, but the required parity inequalities make the same sum strictly positive, yielding a contradiction.Odd-weight inputs contribute strict positive terms while all remaining terms are nonnegative.
B.3 Upper Bound for 𝑘-ESP
The k-ESP lower bound is tight: k+1 heads suffice for every finite endpoint vocabulary. The construction separates parity-dependent selector weighting from endpoint identity copying and realizes the required signs by rational interpolation.
- B.3 Upper Bound for k-ESP: The construction matches the lower bound: k heads do not suffice, whereas k+1 heads solve k-ESP exactly.The lower bound comes from the two-symbol restriction; the upper bound works uniformly over all distinct endpoint pairs.
- B.3 Upper Bound for k-ESP: A one-layer additive transformer with k+1 heads solves k-ESP over every finite endpoint vocabulary U, using embedding dimension k + |U| + 5.Vocabulary coordinates copy supplied endpoints into their own output logits, while positional coordinates encode the interpolation mechanism.
- B.3 Upper Bound for k-ESP: Endpoint positions add input-independent denominator mass while their values copy candidate identities, so they do not interfere with interpolation over selector Hamming weight.The same fixed parameters handle arbitrary supplied endpoint symbols through vocabulary-identity coordinates.
- B.3 Upper Bound for k-ESP: Each head contributes a rational term indexed by selector Hamming weight, and Cauchy interpolation chooses coefficients whose combined sign alternates across weights 0 through k.The design sets denominators to c + j and interpolates the desired parity signs at the k+1 Hamming levels.
- B.3 Upper Bound for k-ESP: The construction uses finite parameters: a sufficiently large finite query-mask score preserves all required output signs.The query contribution can be made arbitrarily small without changing the candidate comparison signs.
C 𝑘heads cannot solve (𝑘+ 1)-hop induction heads
The paper reduces (k+1)-hop induction heads to (k+1)-bit parity on an encoded input family. Because k heads cannot compute that parity, no one-layer k-head transformer solves the induction task.
- C k heads cannot solve (k+1)-hop induction heads: The encoding maps each (k+1)-bit parity input to a fixed-query sequence whose (k+1)-hop output is the parity token.The first k hops maintain an XOR accumulator, and the final hop resolves the accumulated state.
- C k heads cannot solve (k+1)-hop induction heads: Every variable position in the encoding depends on at most one parity bit, satisfying the structural hypothesis needed for the alternating-sum obstruction.The query is fixed, and fixed scalar projections of each position depend on at most one of x_0 through x_k.
- C k heads cannot solve (k+1)-hop induction heads: No one-layer k-head attention-only transformer solves the (k+1)-hop induction-head task.The reduction uses only the requirement that the correct binary output outrank the other binary symbol.
- C k heads cannot solve (k+1)-hop induction heads: After clearing denominators, each monomial depends on at most k of the k+1 bits, so its alternating sum vanishes; parity correctness would require a positive sum, producing contradiction.Odd-weight inputs contribute strictly positive terms under the required sign inequalities.
- C k heads cannot solve (k+1)-hop induction heads: The lower bound is one hop short of the known exponential constructive upper bound, leaving the linear-to-exponential gap open.The reduction establishes a lower bound of k+1 heads for (k+1)-hop induction, while the matching upper-bound scale remains unresolved.