- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the expressiveness of fixed-size Transformers with softmax attention, infinite precision, a ReLU-based output MLP, and no CoT. Its main result establishes that a one-layer Transformer in this setting cannot compute PARITY.
The main proof idea is that these Transformers can compute only functions with average sensitivity bounded by , whereas PARITY has average sensitivity .
Critical strengths
The paper makes a clear theoretical contribution and develops a new lower-bound technique. Moreover, the one-layer lower bound yields two important comparisons with previous work:
- Two-layer Transformers are known to compute PARITY, establishing a sharp depth separation within the stated model.
- Several previous communication-complexity lower bounds require precision to be restricted to bits. This paper establishes a lower bound without such a restriction, and resolves the one-layer PARITY problem. Though existing Split-VC methods could do not require bounded-precision, it could not address the PARITY problem.
Critical weaknesses
About the one-layer vs. two-layer contrast: the known two-layer construction uses a non-standard positional encoding. This assumption should be explicitly stated in the paper.
Minor: The citation commands \citep and \cites are used incorrectly in some places.
Questions for authors
None.
Thank you for the positive review! We will clearly state that we are using i↦(i,i2) PE in the introduction, and will fix the \citep, \cites issue in the revised version.