- 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 heads and degree 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.
-
A head transformer with degree output layer can be expressed by a -degree polynomial. Consequently, any function with (threshold) degree must be computed by a transformer where .
-
For symmetric functions , the above bound is tight. Any symmetric function with (threshold) degree can be computed a head transformer with degree 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.
-
However, threshold degree does not exactly characterize what is expressible. There are many functions with degree that cannot be expressed by heads and degree output layer.
-
The authors establish a hierarchy theorem: more heads is strictly more expressive that fewer heads (assuming 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 provides a lower bound on the product of (eg Result 1), it does not seem to capture really what a -head -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 -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 -head -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
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.
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 pair can be mapped to a completely distinct vectors (e.g., for -bit parity, arbitrary vectors are allowed corresponding to bit values at positions through ). 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.”
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 H-head degree-D 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=1 regime for all Boolean functions: one head with a degree-D readout computes f iff D≥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 D-degree PTF post-processing
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=1), letting us quantify how extra heads reduce the degree needed to decode a target. For symmetric targets of threshold degree T, 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>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 n-variate boolean function f, the total influence I(f) is bounded by 8⋅thr-deg(f)n, and is further bounded by 8DHn. Computing f with error at most ϵ∈[0,1/2) under the uniform distribution then requires DH≥(I(f)−2nϵ)/(8n); for parity, DH≥(1−2ϵ)n/8. (For exact parity, ϵ=0, our result gives the tight DH≥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!