- 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
- What can be established for additive positional encoding or a specified standard non-additive mechanism? Please distinguish proved results from conjectured extensions.
- 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?
- Does the Ramsey/sign-homogenization argument imply another meaningful expressivity consequence, or a finite-resource statement, that would clarify its broader significance?
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!