acceptodds
Under review as a conference paper at ICLR 2027

Threshold Degree and the Head Complexity of Single-Layer Attention

Abstract

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 . For a symmetric Boolean function of threshold degree , we prove that heads and a degree- readout compute if and only if . 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 . The characterization is therefore insensitive to the embedding class. We then extend it beyond symmetric functions. If for a designated subset , the same characterization holds, with an upper bound that uses an additive embedding of symbol and position; such is asymmetric whenever is a proper subset of , and no symbol-only embedding computes it at any or . Taking to be parity gives a strict hierarchy in the head count at every fixed readout degree and input length: parity on coordinates requires exactly heads. Finally, we show that threshold degree does not govern the general case: at most functions are realizable with heads and a linear readout, and we exhibit a family of threshold degree in which almost every member requires heads. Experiments on symmetric Boolean targets study the roles of , , and value-dimension in trained attention layers.

Primary area:
learning theory
Keywords:
lower bounds, multi-head attention, transformer expressivity, head complexity, threshold degree, symmetric Boolean functions, parity

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_X1dHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors study the expressiveness of a single-layer transformer as it depends on the number of heads. Since a single-head transformer (with appropriately strong post-processing) can approximate arbitrary functions well, the authors must restrict the post processing or output-layer of the transformer. With this constraint in mind, the authors propose restricting the output layer by modeling it as a polynomial, with degree parameterizing expressivity. The question is then: what functions can a single-layer transformer with HH heads and degree DD output layers compute? The authors prove several results in this direction, and in particular study functions characterized by their threshold degree: the degree of a polynomial that (when rounded) agrees with the function.

  1. A HH head transformer with degree DD output layer can be expressed by a DHDH-degree polynomial. Consequently, any function ff with (threshold) degree TT must be computed by a transformer where DH≥TDH \geq T.

  2. For symmetric functions ff, the above bound is tight. Any symmetric function with (threshold) degree DHDH can be computed a HH head transformer with degree DD output layer. The authors obtain a similar construction for symmetric juntas (that is symmetric functions depending on a subset of the coordinates), with a slightly stronger embedding scheme.

  3. However, threshold degree does not exactly characterize what is expressible. There are many functions with degree DHDH that cannot be expressed by HH heads and degree DD output layer.

  4. The authors establish a hierarchy theorem: more heads is strictly more expressive that fewer heads (assuming DD is constant). The authors also provide some experiments that seem consistent with their theoretical results.

Critical strengths

The paper is a nice theoretical contribution: they analyze natural parameters (heads and output layer complexity) of the transformer, and show that the expressiveness of the transformer w.r.t. these parameters can reasonably be captured by a natural notion of function complexity (threshold degree).

The paper is well written and easy to follow. The proofs are simple and well presented.

Critical weaknesses

While threshold degree TT provides a lower bound on the product of DHDH (eg Result 1), it does not seem to capture really what a HH-head DD-degree single-layer transformer can do. In some sense the characterization is not particularly strong.

I understand the motivation of wanting to understand the trade-off of width (number of heads) and expressiveness. But I'm not convinced that restricting the output layer to be a DD-degree polynomial is the right way to do it.

Questions for authors

Do you have other candidate parameters for function complexity other than threshold degree that might better capture what is computable by a HH-head DD-degree transformer?

Other than the fact that single-head transformer can approximate arbitrary functions, is there another reason to restrict output layer post processing to be a bounded degree polynomial? If the motivation is to understand why transformers with more heads perform better, this does not seem to be the right restriction to make on the model: there should be some other measure that more accurately captures the desired phenomenon.

7 comments
AuthorsOpenReview ↗

Response to reviewer (X1dH)

We would like to thank the reviewer for their detailed review and for recognizing the theoretical contribution and clarity of the proofs. We try our best to address your questions below.

3.1. Re: strength of the characterization and whether threshold degree captures what HH-head degree-DD models can do

  • Besides our universal lower bound and tight characterization for symmetric functions and juntas, our result differs from prior expressivity results in its resource assumptions. Many prior results restrict not only the readout (e.g., linear or Lipschitz) but also the embedding dimension or precision. Our lower bound is a geometric obstruction that holds even with arbitrary embeddings and unbounded precision: neither can compensate for an insufficient head–degree product, because the information is lost in the attention representation itself.

  • Beyond symmetric functions, threshold degree fully characterizes the H=1H=1 regime for all Boolean functions: one head with a degree-DD readout computes ff iff D≥thrdeg⁡(f)D\ge\operatorname{thrdeg}(f) (added Remark 6.1; see also point 1.3 to Reviewer x5ph). How additional heads reduce the required degree for general Boolean functions remains open.

3.2. Re: your concern of restricting to the DD-degree PTF post-processing

  • To specifically address this concern we can break it down to three related questions: (i) why restrict the readout function at all, (ii) why choose bounded degree PTF as the right restriction, and (iii) how do bounded-degree PTF readouts compare to standard MLPs.
    • For (i), as your summary notes, unrestricted readouts make the problem trivial (e.g., unbounded-degree polynomials, by Stone–Weierstrass). A bottleneck can instead come from finite precision, where rounding makes nearby representations indistinguishable, or from a restricted readout. We study the latter and allow infinite precision.

    • For (ii), polynomial degree gives a controlled hierarchy extending the linear readout (D=1D=1), letting us quantify how extra heads reduce the degree needed to decode a target. For symmetric targets of threshold degree TT, we characterize this tradeoff exactly.

    • For (iii), previous empirical studies have compared polynomial predictors with MLPs in function approximation [OLT08] and classification [AMC+26]. We extend this comparison to decoding the MHA output for symmetric targets of varying threshold degree (Appendix A). For H>1H>1, homogeneous polynomial readouts achieve higher zero-error success than parameter-matched GELU MLPs, are comparable to MLPs with twice as many readout parameters, and are generally outperformed by those with four times as many. Thus, polynomial readouts are competitive with standard MLPs on our tasks while admitting the exact head–readout tradeoff in (ii).

      [OLT08]: A Functional Approximation Comparison between Neural Networks and Polynomial Regression.

      [AMC+26]: Polynomial Perceptrons for Compact, Robust, and Interpretable Machine Learning Models.

3.3. Re Question: other candidate measures for function complexity

  • The notion of split-VC dimension introduced by [KUO+26] might be relevant. Another candidate is the average sensitivity discussed in [KSW26] and [Hsu26]. As mentioned in the Remark 1 of [Hsu26], it is possible to lower bound the resources even for approximately computing the parity (on average with respect to uniform distribution over the boolean cube), conditioned on that the (asymptotic) Gotsman-Linial conjecture [GL94] holds. Indeed, we can now obtain such a lower bound for parity and extend it to general boolean functions since the Gotsman-Linial conjecture has recently been proved correct [OpenAI26]. Specifically, for any nn-variate boolean function ff, the total influence I(f)I(f) is bounded by 8⋅thr-deg(f)n8\cdot\text{thr-deg}(f)\sqrt{n}, and is further bounded by 8DHn8DH\sqrt{n}. Computing ff with error at most ϵ∈[0,1/2)\epsilon\in[0,1/2) under the uniform distribution then requires DH≥(I(f)−2nϵ)/(8n)DH\geq(I(f)-2n\epsilon)/(8\sqrt{n}); for parity, DH≥(1−2ϵ)n/8DH\geq(1-2\epsilon)\sqrt{n}/8. (For exact parity, ϵ=0\epsilon=0, our result gives the tight DH≥nDH\ge n.). We've added a paragraph noting this connection in the related section (marked in green in the updated manuscript) for future readers, as well as a formal proof at the end of the appendix.

    [KUO+25]: Strassen attention, split VC dimension and compositionality in transformers. NeurIPS 2025

    [GL94]: Spectral properties of threshold functions. 1994

    [OpenAI26]: Average sensitivity of polynomial threshold functions. 2026

    [KSW26]: Parity, sensitivity, and transformers. 2026

    [Hsu26]: Lower bounds for one-layer transformers that compute parity. 2026

We hope these explanations and results, including the extension to approximate computation, address your concerns. We are happy to elaborate further, and if your concerns are resolved, we would appreciate your re-evaluation. Thanks!

I thank the authors for their careful response. However, I will keep my score as I am still not particularly convinced by the motivation (for example, restricting the model to finite precision seems much more natural to me than restricting the MLP function). More generally, it seems to me that the advantage of having many heads is that any token (e.g. the query token) can attend to different other tokens in different heads, and this should somehow be useful (otherwise, if you attend to the same token, the number of heads should not matter too much, instead probably the sum of all value dimensions is most important). Thus, it seems to me that it should be the case that a separation on the number of heads should take advantage of the fact that the same token can attend to different tokens in different heads, and it is not clear to me how the current results support this. It is also still not clear why restricting the MLP helps us say something about why it is useful to have more heads.

AuthorsOpenReview ↗

Reply to X1dH's comment

We thank the reviewer for your quick reply! Regarding "restricting the model to finite precision seems much more natural...", we agree that it is also interesting to study the transformer model of putting finite-precision rounding to the attention layer but no restriction to the MLP, which is what most of the existing works focus on. Instead, we study the model with restricted readout but allowing infinite precision because (i) the former setting has been studied for different tasks and the analysis technique is shared and standard; (ii) With no rounding applied to the attention layer, we are able to isolate the computational bottleneck purely from the self-attention mechanism, as we refer to the geometric bottleneck. Note that there hasn't been identified any such type of bottleneck in the literature. Moreover, this requires new technique for the analysis, which also leads to the functional understanding of what a multi-head attention layer can represent as what we discussed in our rebuttal.

Regarding "it should be the case that a separation on the number of heads should take advantage of the fact that the same token can attend to different tokens in different heads", even in our setting different heads can have different weights for the same tokens and thus different attention scores. Also notice that our lower bound allows for joint token–position embeddings -- meaning the model is allowed to encode each (token, position) pair as a completely unique token. Therefore, every (xi,i)(x_i, i) pair can be mapped to a completely distinct vectors (e.g., for 44-bit parity, 88 arbitrary vectors {a0,b0,c0,d0,a1,b1,c1,d1}\{a_0, b_0, c_0, d_0, a_1, b_1, c_1, d_1\} are allowed corresponding to bit values at positions 11 through 44). Consequently, in our model, different heads are definetly allowed to "attend to different tokens in different heads". The geometric obstruction in our lower bound holds despite this.

We recognize the time constraints, but would appreciate it if you could clarify what you mean by “the same token can attend to different tokens in different heads.”

Reviewer_KwqxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the question of how many softmax attention heads are needed, given a degree-DD polynomial threshold decoder, to approximate a given Boolean function ff. In the case where ff is a symmetric Boolean function, the paper shows that if ff has threshold degree TT, then T/DT / D heads are necessary and sufficient. The paper also extends this result to the case where ff is a symmetric function of a subset of the variables. For general non-symmetric ff, the paper gives a family of functions of threshold degree TT in which almost every member requires nT−2n^{T - 2} heads, and shows that the number of functions that an HH-head attention layer can compute is much smaller than the number of functions of a given threshold degree. The paper also corroborates these theoretical findings with synthetic experiments.

Critical strengths
  • The paper gives a tight characterization on head complexity for symmetric Boolean functions
Critical weaknesses
  • The problem setting is somewhat artificial and the authors do not properly motivate why it is interesting from an ML perspective to study symmetric Boolean functions, or why threshold degree is the right measure of complexity to consider. The paper feels more in scope for a venue like COLT or ALT
Questions for authors

The first paragraph of the introduction briefly mentions that the restricted setting considered in this paper can provide insights broadly for mechanistic interpretability. What are plausible settings for the latter where the authors envision bounds like the ones in this paper can provide insight?

1 comment
AuthorsOpenReview ↗

Response to reviewer (Kwqx)

Thank you for your detailed review and for recognizing the theoretical contribution and clarity of the proofs! To address your concerns:-

2.1. Re: why study symmetric functions and ML relevance

  • Regarding the weaknesses you pointed out, first, note that our lower bound holds for non-symmetric functions as well (we give a universal lowerbound). Symmetric functions are fundamental because, without positional information, transformers only compute symmetric functions. Moreover, symmetric functions lend themselves well to theoretical analysis and provide a natural starting point for studying the computational power of transformer models but also do have practical relevance (see point below).

  • Regarding broader ML relevance, symmetric functions are also directly related to problems that arise in natural language tasks for LLMs. For instance, there is a direct connection between parity and tasks that require serial computation, such as function composition. [Han20] makes this connection explicit through iterated negation (for example, something like evaluating “It’s not true that the claim ‘the door isn’t locked’ is false”), since composing the maps gi(b)=b⊕xig_i(b)=b\oplus x_i gives gk∘⋯∘g1(0)=x1⊕⋯⊕xkg_k\circ\cdots\circ g_1(0)=x_1\oplus\cdots\oplus x_k. We plan on making these connections explicit in our final version of our manuscript. Thanks for pointing this out!

    [Han20]: Theoretical Limitations of Self-Attention in Neural Sequence Models. TACL 2020.

2.2. Re: why is "threshold degree the right measure of complexity"

  • We didn’t "settle" on this complexity measure. It just turns out to be the right answer for characterizing symmetric boolean functions under the attention's computation (threshold degree emerges naturally from our analysis). Indeed, considering the sign pattern of a function is inspired by the fact that agggregation of attention heads has a positive denominator and thus the sign of the attention's output equals to the sign of its numerator, which simplifies the analysis. (we also addressed this in point 3.1 for reviewer X1dH)

2.3. Re: relevance to ICLR’s scope

  • We thank you for suggesting COLT and ALT as more appropriate venues for submitting our paper. In fact, in addition to practical works, the interdisciplinary ICLR conference also includes learning theory as relevant topics and has accepted many theoretical works studying similar topics [e.g., KS24, AYB25, TKRS26, YJBYL26]. Hence, we strongly believe the theoretical nature of the submission should not be the ground for rejection.

    [KS24]: Are transformers with one layer self-attention using low-rank weight matrices universal approximators? ICLR 2024

    [AYB25]: Quality over quantity in attention layers: when adding more heads hurts. ICLR 2025

    [TKRS26]: Two (narrow) heads are better than (an arbitrarily wide) one. ICLR 2026

    [YJBYL26]: The effect of attention head count on transformer approximation. ICLR 2026

  1. Re Question: Mechanistic Interpretability
  • We belive our results could serve as a theoretical benchmark for testing the sufficiency and minimality of proposed attention circuits. Extending these insights to larger models requires further work. We will clarify this in the final version.

We hope our response clarifies your concerns. We welcome further questions or discussion. If these clarifications address your concerns, we would appreciate your re-evaluation of our work. Thanks!

Reviewer_x5phOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors study the expressivity of a single attention layer with multiple heads. They consider the class of networks with HH attention heads and a polynomial readout of degree DD, and examine the number of heads required to compute a Boolean function f:0,1n→0,1f:\\{0,1\\}^{n}\to\\{0,1\\}. Their findings are as follows:

  • For a symmetric function f=F(∣x∣)f=F(|x|), a network with degree-DD readout computes ff if and only if DH≥TDH\ge T, where TT is the threshold degree of ff.
  • The same characterization holds for symmetric juntas, i.e. the functions of the form f(x)=F(∣xS∣)f(x)=F(|x_{S}|), where xSx_{S} denotes the restriction of xx to the coordinates S⊆[n]S\subseteq[n]. The distinction from the case of symmetric functions is that, for symmetric juntas, the network embedding must contain positional information.
  • For a general Boolean function ff, the condition DH≥TDH\ge T is not sufficient.
Critical strengths

I find it interesting that, for symmetric functions and symmetric juntas, the number of heads and the degree DD of the readout are interchangeable in their representational power.

Critical weaknesses

While the obtained results offer certain advantages, their scope is limited. In particular, results of the “only if” direction are restricted to symmetric functions and symmetric juntas. In these cases, the attention heads only need to compute one statistic, which is ∣x∣|x| for symmetric functions and ∣xS∣|x_{S}| for symmetric juntas, so there is no need for each head to compute distinct information. Consequently, I think these functions do not fully exploit the advantages of a multi-head architecture. Furthermore, for general Boolean functions, the authors show that the lower bound DH≥TDH\ge T is not sufficient. Specifically, they provide an example of ff for which, given a network with$D=1$, computing the function requires H=Ω(nT−2)H=\Omega(n^{T-2}) attention heads.

Questions for authors

Are there any significant insights regarding the ability of Transformers to represent general functions?

3 comments
AuthorsOpenReview ↗

Response to reviewer (x5ph)

Thank you for your thoughtful review! We try our best to address your points below:-

1.1. Re: your concern of the scope

  • The "only if" direction holds for non-symmetric functions as well (we give a universal lowerbound). For the "if" direction, we show representations for symmetric functions using content-only embeddings. This is very reasonable because, without positional encoding, transformers only compute symmetric functions. For general boolean functions, see our discussion in the bullet 1.3 below.

1.2. Re: one statistic

  • We agree that for symmetric functions and symmetric juntas, computing the aggregatic statistic of the inputs helps but it is generally insufficicnt to decode the correct final output (e.g consider the linear readout case, D=1D=1). Additionally, the existence of a sufficient statistic does not mean that having multiple heads provides no computational advantage. Indeed, a single uniform attention head can already encode the statistic ∣x∣|x|, yet requires a high-degree post-processing function to compute the target F(∣x∣)F(|x|) from that statistic. In contrast, our upper bound shows that different heads can implement different functions of the same statistic, making a low-degree readout possible.

  • However, you are correct in pointing out that these functions do not fully exploit the advantages of multi-head computation. That said, we believe our results estabilish an important baseline for understanding its expressive power. In particular, our lower bound is clean and strong in a sense that it witnesses a geometric obstruction of multi-head representation, allowing arbitrary embedding and level of precision (also in point 3.1 in our response to the reviewer X1dH). Thus, the limitation arises from the attention mechanism itself, rather than from restrictions on encoding capacity or precision. More general lower bounds of multi-head attention might depend on further resources and might be of different types of bottleneck.

1.3. Re: the insufficiency with regard to general Boolean functions

  • The polynomial head lower bound you highlighted concerns linear readouts, as you correctly pointed out! However, at the other extreme, even a single-head model equipped with a D=TD=T readout is sufficient to solve all Boolean functions of threshold degree up to TT (where T≤nT\le n even in the general case, with parity attaining the maximum threshold degree nn).

  • Therefore, for the same family in Theorem 4, one head with a degree-TT readout suffices for every member, whereas almost every member requires Ω(nT−2)\Omega(n^{T-2}) heads with a linear readout. This makes the asymmetry between the two resources explicit! Allowing for unbounded head dimension and precision level still won't help move this lower bound. Therefore, it matters how you allocate these two resources if you want to solve general Boolean functions. We have added Remark 6.1 (marked in green) to make this distinction clear-er -- hopefully this helps future readers. We leave open the exact characterization of this tradeoff for general boolean functions.

1.4. Re Question: insights for representing general functions

  • Our lower bounds also extend to non-boolean functions simply by restricting the inputs to the Boolean hypercube. On the restricted domain, if the function's outputs can be separated by a single threshold into a boolean function of threshold degree TT then DH≥TDH\ge T remains necessary!

We hope these clarifications address your concerns about the scope of our results and the benefits of multiple heads. We would be happy to discuss any remaining questions. If your concerns have been addressed, we would appreciate your re-evaluation of our work. Thanks!

Thank you for your detailed response and for updating the manuscript.

First, I apologize for mistakenly writing "only if" in my original review. I intended to refer to the "if" direction (sufficiency). I now understand that multiple heads can provide a computational advantage even when only a single aggregate statistic is needed. However, I still believe that such settings do not fully capture the advantages of multi-head attention, particularly its ability to process and combine different information across heads. I also find the newly added Remark 6.1 interesting, as it highlights the asymmetry between head count and readout degree for general Boolean functions. Nevertheless, my concern about the limited theoretical characterization of general functions remains.

Overall, I acknowledge the contributions of this work and appreciate the clarifications. While I will maintain my current rating, my assessment has become more positive and is now closer to a score of 3 than it was when I submitted my original review. Thank you again for your response.

AuthorsOpenReview ↗

Replay to x5ph

Thank you for the follow-up and for kindly letting us know your assessment is now closer to a 3. We would like to respond to the remaining concern.

If by "fully capture" you are asking for a full characterization for general boolean functions, we have pointed out the asymmetry in the representation power of (1, H) and (1, D) models. We note this asymmetry to show that a characterization for general functions cannot be stated in terms of threshold degree alone and remains outside of the scope of this paper. We believe our techniques and results can help inform extension of our work for general functions.

Since your remaining concern is about questions beyond the paper’s scope rather than about the results themselves, and since you now describe your assessment as closer to a 3, we would be grateful if you would consider updating your score. Thanks!!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.