- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper considers which languages certain transformers can recognize, in the sense of receiving a token sequence and answering whether it's in the language or not with the sign of the single output at some position. They focus on languages that depend only on the counts of each token, not on their order. For encoder-only transformers without positional encodings, which can only recognize such counting languages, they show that softmax attention allows recognizing languages that average hard attention does not, and study how replacing the exponential in the softmax attention with other functions changes this ability. They further study the effect of causal masking, showing that such decoder transformers recognize languages beyond ones recognizable by the studied encoder transformers. Lastly, they study the output deviation when replacing exp with a polynomial and the input length up to which their constructed softmax encoder still recognizes the separating language under this replacement.
Critical strengths
The results are well-stated and unambiguous and the proofs appear to be correct and more rigorous than the ones in many other works.
Critical weaknesses
-
Practical relevance The relevance of the results is barely discussed. For many transformer expressivity works, the general motivation appears to be to improve understanding of the models actually used for natural language processing. Counting languages, however, do not seem to be very relevant or related to natural language in a meaningful way. Moreover, not using positional encodings in transformer encoders eases theoretical analysis, as equal tokens have equal residual stream throughout, but for the same reason does not seem to be used in practice (to the best of my knowledge) as it wastes computation. An exception are e.g. set transformers, but these use continuous inputs rather than discrete tokens. Moreover, recognizing the separating languages depends on tiny margins (as stated by the authors) that don't seem to hold up under realistic finite precision, further restricting the relevance to practice.
-
Presentation The paper is dense and hard to read, with large parts of the main part filled with proof sketches (often needing a closer look to be identifiable as such), and even the abstract includes a proof sketch. I feel like the work would be more accessible if it instead spent more space motivating the general ideas and each result.
Questions for authors
How would theorem 3 hold up under non-strict causal attention (which is arguably more standard than strict causal masking), or would it then need a begin-of-sequence marker? The construction seems to rely on your convention that attention over the empty set yields output 0, which is used to turn the first token into a beginning-of-sequence marker. So is there a way to achieve the same with non-strict causal attention?
4 comments
Response to Reviewer xEtC (2/4)
W2: Tiny margins under realistic finite precision.
By Proposition 5, the exponential's extra power lies in decisions whose margins shrink with length, and our rounding bounds show that such decisions preserve their signs at realistic precision: at the length-1,080 input in float64, and at separate inputs in float32.
Where the margins shrink. Your margin observation matches Proposition 5: for any fixed margin , one polynomial preserves every decision won by at least , across all lengths. Decisions with shrinking margins arise naturally: in a plain normalized majority vote, a one-vote lead already has margin .
Why the signs survive rounding. A computed sign is reliable whenever the output magnitude exceeds its rounding error, however small the output is. We prove rounding bounds for a specified evaluation with balanced pairwise summation:
- float64 (Appendix E.3, added in the revision): at the length-1,080 disagreement, both output magnitudes exceed the rounding bound by a factor of more than 460, and the bound accounts for cancellation in the final sum.
- float32: on the unscaled network of Theorem 1 at another input (length 3,094, degree 5), both output magnitudes exceed the rounding bound by a factor of about 5.7, while every attention row stays within total variation distance of softmax (added in the revision). With second-layer scores scaled to , the factor exceeds 870 (Appendix E.4, added in the revision).
- Any length (added in the revision): significand bits suffice for the softmax network to decide every positive-count input up to length .
In W3, we test full FP32 language models.
W3: What this implies for models actually used in natural language processing.
Our theory yields a consequence that can be checked on such models. Proposition 5 bounds how much a polynomial replacement perturbs the logits, and a prediction can change only where that perturbation reaches half the gap between the top two logits. In two pretrained language models, at degree 36 and , the few predictions that change all occur at positions with the smallest gaps. Such replacements are needed wherever attention must be computed with polynomial operations only, as in encrypted inference (Zimerman et al., 2024; Li et al., 2024).
What we tested. In experiments added to the revision, we ran Pythia-70M-deduped (LayerNorm/GELU) and SmolLM2-135M (RMSNorm/SiLU) in FP32 with all trained weights, causal masks, and positional encodings unchanged, and replaced the exponential with a Taylor polynomial in every attention layer. We then compared top-1 next-token predictions with an exponential baseline that uses the same score clipping to , on 16,384 held-out WikiText-103 and FineWeb-Edu positions per model (Section 5.3, Appendix F). On , degree 32 is the smallest even degree at which our bound keeps every row of attention weights within total variation distance of the exponential weights, so we tested degree 16 (below 32) and degree 36 (just above 32). Because each replaced layer also changes what later layers receive, we measured whole-network predictions directly.
What we found.
| Model | Top-1 changes, deg. 16 | Top-1 changes, deg. 36 | Positions with (0 changed; new in this response) |
|---|---|---|---|
| Pythia-70M-deduped | 3,239 (19.8%) | 10 | 15,546 / 16,384 |
| SmolLM2-135M | 2,496 (15.2%) | 1 | 16,340 / 16,384 |
Here is the baseline's top-two logit gap, and is the largest change in any logit across the vocabulary observed at degree 36 within the same article. Every position with keeps its top-1 token, since no logit there moves by more than . The experimental finding is that the remaining changes concentrate at the smallest gaps: all 10 Pythia changes lie among the 42 positions (0.26%) with the smallest baseline gap, and SmolLM2's single change occurs at the position with the smallest gap.
Choice of range: We clip to so that Taylor weights stay positive, and we choose this range because it leaves the native models essentially intact: on 2,048 positions per model, clipping at 19 changes 2 and 0 native top-1 predictions (Pythia and SmolLM2), whereas clipping at 8 changes 315 and 273. A narrower range would lower the degree but change the model being approximated.
Response to Reviewer xEtC (3/4)
Q1: How does Theorem 3 hold up under non-strict causal attention, and would it need a BOS marker?
It holds with an explicit BOS marker. Under the standard non-strict mask, the same two layers recognize the harmonic threshold ; we moved this BOS construction from the appendix of our submission into Theorem 3 (Section 4.1, Figure 2(b)). The counting power still comes from the causal mask.
What BOS does, and why the mask does the work. Your reading is right: under strict masking, the empty prefix turns position 1 into an implicit start marker, and under the non-strict mask a BOS token plays this role. Without it, a word that begins with a run of identical tokens produces the same average at each prefix , so those positions share one state at every layer and our construction cannot single out position 1. Whether a fixed softmax network under the non-strict mask can recognize the harmonic threshold without BOS remains open (Appendix B.1). An unmasked softmax network given the same BOS and end markers still cannot recognize this language (Appendix B.4), so BOS marks the start and the mask supplies the counting power.
Mechanism: Position sees exactly one BOS among its positions, so uniform averaging in Layer 1 outputs . Kazemnejad et al. (2023) use the same reciprocal signal to show that causal Transformers without positional encodings can recover absolute position. At the end marker, Layer 2 averages the indicator of minus over all positions, giving . Reordering the word leaves and unchanged, so the language remains a counting language.
Related result added in the revision: under the same mask, hard attention can also beat softmax (Theorem 4, Appendices B.6 to B.8). With non-strict masking, BOS, affine/ReLU layers, and no positional encodings, both attention rules see identical prefixes. Three layers of averaging hard attention decide parity by locating the middle . For any fixed causal softmax network, adding more 's in a fixed context eventually leaves the accept/reject label unchanged while parity keeps alternating; a fixed temperature folds into the query and key weights, so the accept/reject label still eventually stops changing.
W4: Presentation of the abstract, motivation, and proof sketches in the main text.
Following your suggestion, the abstract now states the questions and results in words, and the main text motivates each result before a labeled proof sketch.
- Abstract: It opens with the two replacements we study (hard attention for softmax in theoretical analyses, and a polynomial for the exponential in efficient and encrypted inference) and states the results in words; we moved the layer-by-layer calculation out of the abstract.
- Vote before formula: The introduction now explains the vote in words before Eq. (1) and places a linear weight beside the exponential one. In the example right after Eq. (1), three 's beat two 's when one is present, yet the same three 's lose once six more 's are added (the two 's weigh , then , against 3 votes for ).
- Proof sketches as explanations: We limit each main-text sketch to the idea a reader needs and leave full arguments to the appendices. In Section 4.1, for example, we explain why the harmonic rule needs opposite labels on two adjacent counts and why an unmasked network eventually gives them the same label, leaving the sign argument to Appendices B.2 to B.4.
- Figures and headings: Figure 2(b) now shows the two-layer construction with BOS beside the vote in Figure 2(a). Proof sketches appear under headings such as "Why rule (1) is not semialgebraic", so readers can follow the results first and read proof ideas on demand.
Response to Reviewer xEtC (4/4)
Summary.
- W1: Counting languages test whether conclusions drawn from hard attention transfer to softmax; neither its constructions nor its impossibility results transfer automatically (Theorems 1 and 4), and the vote construction carries over to RoPE (added in the revision) and, through a construction added in the revision, to continuous set inputs.
- W2: Shrinking margins are where the exponential's extra power lies (Proposition 5), and proven rounding bounds show that our separating examples preserve their signs in float64 and float32.
- W3: A prediction survives whenever the logit perturbation stays below half the top-two gap; at degree 36, only 10 of 16,384 predictions change in Pythia and only 1 in SmolLM2, all among the smallest gaps.
- Q1: With BOS, Theorem 3 holds under non-strict causal attention; BOS only marks the start, since an unmasked network with the same markers still fails (Appendix B.4).
- W4: The abstract states the questions and results in words; main-text proof sketches give the key idea (e.g., Section 4.1), with full arguments in the appendices.
We hope these results address your concerns about practical relevance and the role of BOS, and we would be grateful if you would reconsider your score.
Response to Reviewer xEtC (1/4)
Thank you for the careful review and for recognizing the rigor of our proofs. Your observations on shared token states and on the empty prefix under strict masking match ours. W1 to W3 address practical relevance (model setting, finite precision, trained language models), Q1 the non-strict mask, and W4 the presentation. Section, theorem, and appendix numbers refer to the revised manuscript (Proposition 4 is now Proposition 5), and results marked "new in this response" will be added to it.
W1: Practical relevance of counting languages, unmasked encoders without positional encodings, and Set Transformers.
In short, expressivity analyses often replace softmax with averaging hard attention to make proofs tractable, and counting languages provide a controlled test of whether their conclusions transfer to the softmax used in practice; the vote construction also carries over to RoPE (added in the revision) and, through a construction added in the revision, to continuous set inputs. As you note, identical tokens share one state in an unmasked encoder without positional encodings, so both attention rules see exactly the same token counts, and any difference in what they recognize comes from the attention rule itself. Sälzer et al. (2026) characterized exactly which counting languages hard attention recognizes in this setting, providing a precise baseline. In the counting model we can also tune how close a decision is to a tie and prove who wins after the weight function changes; in a language model we can measure how far the top token leads and whether it remains on top after the exponential is replaced with a polynomial (W3).
Neither constructions nor impossibility results transfer automatically.
Positional encodings and causal masks. To see whether our vote depends on omitting positional encodings, we added to the revision a new two-layer softmax network that recognizes the same vote under standard RoPE and under fixed-period rotary encodings. For fixed-period rotations, the revision also proves that every fixed unmasked averaging hard attention network errs on arbitrarily long words whose letter proportions stay bounded away from the tie curve (Section 3.1, Appendix A.8). For standard RoPE, the degree lower bound for exact decisions also extends to our construction (Section 5.2, Appendix A.8). Our guarantees for polynomial replacement (Proposition 5; Corollary 24 in Appendix C.8) rest on boundedness and stability assumptions, so they apply to causal Transformers with RoPE and LayerNorm or RMSNorm, including the two models we test in W3. The two-layer network of Theorem 1 also recognizes the same vote under a causal mask, because the end marker sees the whole word in both layers.
Set Transformers with continuous inputs (added in the revision). For the exception you mentioned, Set Transformers (Lee et al., ICML 2019), the separation also holds for continuous set inputs of fixed size four, where a feature mean plays the role of b's frequency. No fixed semialgebraic network, including networks with averaging hard attention or polynomial attention weights, computes the resulting decision, even with fixed positional encodings, since these are constants on four positions. Construction: Take three set elements and one end marker. Each element carries two real features (zero at the marker) and a role indicator that moves with the element, keeping the network permutation invariant. Layer 1 averages the two features into means r∈(0,1) and t∈R. In Layer 2, the end marker assigns score t and value −(1−r) to one role, score 0 and value r to another, and score 0 and value 0 to the remaining two positions. The output is 3+etr−(1−r)et, whose denominator is positive, so the decision boundary is r=et/(1+et). This logistic boundary is not semialgebraic on (0,1)×R, or even on any bounded open region that meets it.