acceptodds
Under review as a conference paper at ICLR 2027

h+1 heads express more than h heads

Abstract

We prove the existence of the following hierarchy: for each there exists a decision problem which can be solved by a one layer transformer with heads but not with only heads. The result holds for a standard transformer architecture, which includes both attention and feed-forward blocks.

Primary area:
learning theory
Keywords:
transformers, expressivity, heads, polynomial thresholds

Reviews

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

The paper is a very TCS paper. It proves a strict head hierarchy for one-layer softmax transformers with a fixed finite ReLU readout. For each k, its count-threshold language PowGraph_k is computable with k heads but not with fewer heads, uniformly over all input lengths. The lower bound combines a polynomial-sign representation with Ramsey restriction and symmetrization. The upper bound uses an explicit joint token-position encoding and an affine readout. The proofs appear correct within the stated model. My main concern is whether this specialized hierarchy provides sufficient additional significance beyond the existing head-count literature.

Critical strengths
  • The hierarchy survives an arbitrarily large, but fixed, finite ReLU readout. This is a genuine advance over attention-only separations.
  • Lemma 2.4 addresses a real technical obstacle: it homogenizes individual predicate signs before symmetrization. Merely averaging the original predicates would not justify the argument.
  • The bounds match exactly. The upper construction is explicit, and the mathematical exposition is generally clear.
Critical weaknesses
  • The main result is mathematically clean, but its broader significance is limited.

    The separation is proved for one constructed language, PowGraph_k, in the uniform setting where a single fixed network must work for every input length. This quantifier is essential: at any fixed length, a sufficiently large MLP can represent arbitrary Boolean functions, so the result does not establish a finite-context head requirement or a practically meaningful head-count tradeoff. As a result, I view the contribution primarily as a specialized formal-language separation rather than a broader characterization of what additional attention heads enable.

  • The positive result also depends on a fairly specialized positional-encoding assumption.

    The upper bound uses a joint token-position encoding that is explicitly non-additive, while the corresponding result for standard additive positional embeddings is left open. The discussion of RoPE only establishes that non-additive mechanisms exist. It does not show that the construction can be realized with RoPE or another commonly used positional mechanism. This substantially narrows the scope of the headline claim that the hierarchy holds for a "standard transformer architecture."

Questions for authors
  1. What can be established for additive positional encoding or a specified standard non-additive mechanism? Please distinguish proved results from conjectured extensions.
  2. What is the precise novelty relative to Yu et al.'s approximation results and Hsu's ReLU-readout bounds, including the differing assumptions and quantifiers?
  3. Does the Ramsey/sign-homogenization argument imply another meaningful expressivity consequence, or a finite-resource statement, that would clarify its broader significance?
1 comment

thanks for the clarifications. the new results seems nice and might address my concerned weaknesses. unfortunately, i do not have time to examine new results. so prefer to keep my score. thank you!

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

The paper establishes a strict hierarchy in the number of attention heads for one-layer softmax transformers with a fixed finite ReLU feed-forward readout. For every fixed integer k >= 2, it considers PowGraph_k: on interleaved binary strings x and y, decide whether |y| ≥ |x|^k, where the bars denote Hamming weights. The authors prove that a single k-head transformer recognizes this language at every input length, whereas no transformer with fewer than k heads can do so, regardless of its fixed embedding dimension or fixed ReLU readout size. The lower bound reduces the model to a finite combination of signs of degree-at-most-H polynomials, then uses Product Ramsey theory, sign-preserving symmetrization, and a two-variable polynomial obstruction. The matching upper bound uses a fixed joint token-position encoding and a partial-fraction identity. The contribution is theoretical, with proofs rather than empirical evaluation as its principal validation. The corresponding head-count hierarchy question for transformers with L ≥ 2 layers is not resolved in this paper.

Critical strengths
  1. A tight head-count hierarchy that survives an arbitrary fixed finite ReLU readout. The consequential contribution is not merely another attention-only separation: for every k, the same language is realizable with k heads and impossible with fewer, even if the competing model is allowed a larger fixed embedding dimension and a larger fixed feed-forward network. Using a language defined over unbounded input lengths avoids the fixed-length memorization issue that limits the earlier parity-based separations discussed in the introduction. This directly advances the central expressivity question posed by the paper.

  2. A well-chosen separating task with complementary lower- and upper-bound arguments. PowGraph_k connects the target head threshold to the degree of a polynomial counting boundary. The lower bound handles arbitrary positional dependence by extracting a restriction on which the complete sign vector depends only on the two counts, making symmetrization valid. The upper bound then matches the threshold through a partial-fraction construction, using only an affine final readout. This combination provides a concrete explanation of how parallel heads supply expressive power that additional fixed feed-forward computation cannot replace. The novelty should be attributed to the tight head-count characterization, rather than to polynomial counting predicates in isolation.

Critical weaknesses

The introduction mentions sensitivity bounds, split-VC, and circuit classes without introducing these notions. Brief explanations would make the background more self-contained.

Questions for authors

The upper bound uses a non-additive joint token–position encoding, with position-dependent query, key, and value coordinates (Eqs. 27–28). Does this choice affect your main result?

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

The paper proves a strict hierarchy in the number of attention heads for one-layer transformers that include a feed-forward network. It defines PowGraph_k, which accepts a pair of binary words (x, y) when the number of ones in y is at least the k-th power of the number of ones in x. The lower bound says no one-layer transformer with fewer than k heads computes it. The proof turns the transformer into sign patterns of degree-H polynomials (Proposition 2.1), shows by a growth-rate argument that degree below k cannot realize the threshold (Proposition 2.2), and reduces to two counts using Product Ramsey and symmetrization (Lemmas 2.3 and 2.4). The upper bound builds a k-head transformer with a non-additive joint token-position encoding (Theorem 1.2). A Lean formalization is provided as a supplement.

Critical strengths
  • The lower bound is very general: embeddings may depend arbitrarily on position, bit and the input length N, any fixed embedding dimension is allowed, and no precision limit is imposed.
  • The bound is tight: Theorem 1.1 says fewer than k heads fail and Theorem 1.2 gives a construction with exactly k heads, which yields the full h versus h+1 hierarchy for every h ≥ 1.
  • The proof plan is clearly laid out before the details.
Critical weaknesses
  1. The scope is narrower than the framing. The motivating question asks for a task for every h and every number of layers l, and the title is general, but only one layer is treated (Theorems 1.1 and 1.2). Whether l layers with h+1 heads beat l layers with h heads is left unstated as open in the text. The title and abstract should say one layer.

  2. The upper bound does not hold for the standard transformer that the abstract names. The abstract says the result holds for "a standard transformer architecture", but the construction needs a non-additive encoding: at odd positions the key depends on the bit, at even positions it ignores the bit (equations (27)-(28)), and the query contains log N and log(c_j − N^{-(k-1)}). The claim that RoPE makes such encodings "common" is not argued, since RoPE rotates queries and keys and does not give this joint token-position embedding. The decision margin in (26) is of order N^{-k}, so the construction needs precision growing with N, whereas the lower bound is precision-free.

Questions for authors

N/A

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.