acceptodds
Under review as a conference paper at ICLR 2027

What the Exponential Adds: Softmax, Hard Attention, and Exact Counting

Abstract

Hard-attention models simplify the study of transformer expressivity, but their conclusions need not transfer directly to softmax. Averaging hard attention (AHAT) averages values at the highest-scoring positions. Without positional encodings or masking, its rational-parameter version recognizes exactly the counting properties defined by Boolean combinations of polynomial inequalities with rational coefficients. Softmax recognizes strictly more. Two layers decide whether , where excludes one appended end marker: the first averages the indicator, and the second uses this average as the score for . No semialgebraic description captures this property. The same network works when each position attends to itself and earlier positions, answering an open question. More generally, replace by a continuous positive function on a fixed closed interval containing all scores, keeping the remaining operations semialgebraic. Unmasked networks can recognize a nonsemialgebraic counting property exactly when this function is nonsemialgebraic on that interval; polynomial replacements therefore cannot recognize our example. Masking provides another route: three layers attending equally to earlier positions compare a count with , a property no unmasked softmax network built from affine maps and ReLUs recognizes. Finally, replacing by one polynomial keeps outputs of a fixed network with bounded inputs, affine/ReLU updates and an affine readout within any prescribed tolerance at every length. Preserving every decision of even our two-layer network at length requires degree at least . Among positive count triples of length , the degree-ten Taylor replacement's disagreement fraction tends to about , yet it flips a length- decision.

Primary area:
learning theory
Keywords:
transformer expressivity, softmax attention, approximation theory, computational complexity, depth separation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_xEtCOpenReview ↗
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
  1. 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.

  2. 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
AuthorsOpenReview ↗

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.

  • Without masking, hard attention underestimates softmax (Theorem 1). Two softmax layers with parameters in −1,0,1\\{-1, 0, 1\\} recognize the weighted vote x>zey/(n+1)x > z e^{y/(n+1)}, where bb's frequency sets how much each cc counts against the aa's (worked example in W4). No fixed averaging hard attention network with affine/ReLU layers recognizes it, even with arbitrary real parameters (Appendices A.2 to A.4).
  • Under causal masking, hard attention can overestimate softmax (Theorem 4, added in the revision; Q1). Without positional encodings, three averaging hard attention layers decide parity, while no fixed causal softmax network does.

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 bb'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)r \in (0, 1) and t∈Rt \in \mathbb{R}. In Layer 2, the end marker assigns score tt and value −(1−r)-(1-r) to one role, score 00 and value rr to another, and score 00 and value 00 to the remaining two positions. The output is r−(1−r)et3+et,\frac{r - (1-r)e^t}{3 + e^t}, whose denominator is positive, so the decision boundary is r=et/(1+et)r = e^t/(1+e^t). This logistic boundary is not semialgebraic on (0,1)×R(0, 1) \times \mathbb{R}, or even on any bounded open region that meets it.

AuthorsOpenReview ↗

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 γ>0\gamma > 0, one polynomial preserves every decision won by at least γ\gamma, across all lengths. Decisions with shrinking margins arise naturally: in a plain normalized majority vote, a one-vote lead already has margin 1/(n+1)1/(n+1).

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 2.98×10−42.98\times10^{-4} of softmax (added in the revision). With second-layer scores scaled to [0,8][0, 8], the factor exceeds 870 (Appendix E.4, added in the revision).
  • Any length (added in the revision): O(log⁡2N/log⁡log⁡N)O(\log^2 N/\log\log N) significand bits suffice for the softmax network to decide every positive-count input up to length NN.

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 R=19R = 19, 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 [0,19][0, 19], on 16,384 held-out WikiText-103 and FineWeb-Edu positions per model (Section 5.3, Appendix F). On [0,19][0, 19], degree 32 is the smallest even degree at which our bound keeps every row of attention weights within total variation distance 10−310^{-3} 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.

ModelTop-1 changes, deg. 16Top-1 changes, deg. 36Positions with g>2ηg > 2\eta (0 changed; new in this response)
Pythia-70M-deduped3,239 (19.8%)1015,546 / 16,384
SmolLM2-135M2,496 (15.2%)116,340 / 16,384

Here gg is the baseline's top-two logit gap, and η\eta is the largest change in any logit across the vocabulary observed at degree 36 within the same article. Every position with g>2ηg > 2\eta keeps its top-1 token, since no logit there moves by more than η\eta. 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 [0,19][0, 19] 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.

AuthorsOpenReview ↗

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 x>Hn+2x > H_{n+2}; 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 a,aa,…a, aa, \dots, 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 ii sees exactly one BOS among its ii positions, so uniform averaging in Layer 1 outputs 1/i1/i. 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 aa minus 1/i1/i over all n+2n + 2 positions, giving (x−Hn+2)/(n+2)(x - H_{n+2})/(n+2). Reordering the word leaves xx and Hn+2H_{n+2} 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 aa. For any fixed causal softmax network, adding more aa'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 aa's beat two cc's when one bb is present, yet the same three aa's lose once six more bb's are added (the two cc's weigh 2e1/7≈2.312e^{1/7} \approx 2.31, then 2e7/13≈3.432e^{7/13} \approx 3.43, against 3 votes for aa).
  • 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.
AuthorsOpenReview ↗

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.

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

The paper shows that softmax attention represents a significantly more expanded class of functions that averaged-hard-attention. While the latter can recognize only semi-algebraic functions (defined by sets of polynomial inequalities), the former can recognize even non-polynomial expressions. This is shown directly via construction. Further, it is also shown that strict causal masking is, in certain ways, even more expressive than non-masked attention due to its symmetry-breaking properties. Finally, the authors study the effect of replacing the exponential function eue^u with its taylor approximation. They find that in the limit of the degree going to infinity such a replacement eventually fails at the considered counting tasks when the decision boundary is smaller than the approximation error of the taylor series.

Critical strengths
  1. The results proven give important insights on the expressive power of transformers. Being able to show a dichotomy between semi-algebraic and non-semialgebraic properties for softmax vs average-hard-attention and generating a precise construction for doing so is an interesting and novel direction. The constructions is novel, though a bit arbitrarily constructed. Would have appreciated some intuition behind that.
  2. The paper pursues multiple angles of the questions being asked and proves interesting results throughout.
  3. I find it particularly interesting how there is a difference in expressive power between masked and unmasked transformers. I like the idea that causal masking increases expressivity and I think studying this more would be interesting.
  4. The technique of using taylor expansions both for impossibility and construction seems interesting and new.
Critical weaknesses
  1. Abstract is very dense and difficult to understand. The reader doesn't know the symbols a,b,ca,b,c in the beginning. What is the "open question" being answered? What is semi-algebraic networks? The abstract should try to make the content accessible and give a summary, not simply a condensation of the results.
  2. Define semi-algebraic somewhere before line 144.
  3. Introduce the work of Sälzer et al and their techniques in more detail. Clarify the relationship of that work to this one.
  4. I think it would be valuable to provide further intuition on the constructions considered. Also, can we characterize the families of non-semialgebraic tasks that the masked/softmax attention operators are able to express? The expression $x > z\exp(y/(n+1)) in equation (1) is reversed-engineered and appears arbitrary. What can we say about the general space of tasks that can be expressed? I think understanding the limits of the computation would also be a valuable perspective to have.

Overall, the presentation and clarity of the overall paper can be improved significantly to make the results, mathematical definitions and significance better communicated to the reader. More intuition and clarity is needed to make this work publishable. I am also not in a position to say I can evaluate the mathematical claims to a desired degree due to my lack of understanding of the technical details. If These are interesting results and techniques and I believe that communicating them better can lead to an impactful paper for the community.

Questions for authors

N/A

3 comments
AuthorsOpenReview ↗

Response to Reviewer igJh (1/3)

Thank you for your review, for finding the dichotomy between softmax and hard attention an interesting and novel direction, and for noting that clearer communication could make this an impactful paper. The revision is built around one worked example, which we preview here because the rest of this response refers to it. Section, theorem, and appendix numbers refer to the revised manuscript, and results marked "new in this response" will be added to it.

In their Future Work section, Sälzer et al. (2026) asked whether causal softmax can recognize a counting rule beyond finite combinations of polynomial inequalities on the counts. Our two-layer construction answers yes, and it is easiest to read as a weighted vote: each aa casts one vote for acceptance, each cc casts one weighted vote against it, and a third symbol bb casts no vote but sets the weight on each cc. Concretely, each cc's vote is worth ere^r, where rr is the fraction of positions holding bb (out of all positions, including one end marker). Keep the voters fixed at three aa's and two cc's. With one bb (r=1/7r = 1/7), the two cc's cast 2e1/7≈2.312e^{1/7} \approx 2.31 votes and lose to the three aa's. With seven bb's (r=7/13r = 7/13), the same two cc's cast 2e7/13≈3.432e^{7/13} \approx 3.43 votes and win. A linear weight such as 1+r1 + r also flips the winner in this example, but it still gives a polynomial test on the counts. With the exponential weight, no finite set of polynomial tests reproduces the vote's decisions across all lengths (Q1), and this is what the exponential adds.

W1: An accessible abstract, an early definition of "semialgebraic", and the open question.

Following your suggestions, the motivation, the known baseline, and the open question now appear in plain language before the formal definitions in Section 2.

  • Abstract and introduction. The abstract now opens with the two replacements that motivate the paper, hard attention for softmax in theoretical analyses and a polynomial for the exponential in efficient and encrypted inference, explains why we study counting, and states the main results in words. In the introduction, we explain why counting properties let us isolate the attention rule, and then present "semialgebraic" through what is already known about unmasked hard attention.
  • Semialgebraic, in plain language. A rule is semialgebraic if it can be described by finitely many polynomial inequalities combined with and, or, and not. For example, x2>yzx^2 > yz is a semialgebraic counting rule, and ReLU is a semialgebraic network update because two linear pieces describe its graph. This class is the natural yardstick because Sälzer et al. characterize unmasked averaging hard attention in terms of such polynomial tests on the counts. Section 2 then spells out what we keep fixed across lengths.
  • The open question. Section 1 now connects Sälzer et al.'s question more directly to their known result for hard attention, and answers it with this vote.
  • Reading aids. Figure 1 compares what the two attention rules can count with and without a mask, Figure 2 shows the computations layer by layer, with Figure 2(b) now depicting the two-layer construction with BOS, proof sketches appear under headings such as "Why rule (1) is not semialgebraic", and Table 1 in Section 5 shows which approximation target requires the degree to grow with length.
AuthorsOpenReview ↗

Response to Reviewer igJh (2/3)

W2: Motivation behind the counting rule in Eq. (1).

Eq. (1) is the compact form of the vote above, and each of its parts comes from asking what a constant vote weight cannot do.

From a constant weight to an input-dependent weight. Let xx copies of aa cast one vote each and zz copies of cc cast KK votes each. For any constant KK, even K=eK = e, the test x>Kzx > Kz is linear in the counts and stays semialgebraic. To go beyond polynomial tests, each cc's weight must depend on the input. We let the frequency r=y/(n+1)r = y/(n+1) of a non-voting symbol bb set this weight to ere^r (word length n=x+y+zn = x + y + z, plus one end marker for readout). This gives Eq. (1), x>zey/(n+1)x > z e^{y/(n+1)}, which Figure 2(a) illustrates step by step. The linear weight 1+r1 + r from the opening also flips this vote, yet its test remains polynomial after clearing denominators; the introduction places the two weights side by side for this reason.

Why each part is there.

  • Two layers: Layer 1 averages the indicator of bb to compute rr; Layer 2 gives cc the score rr and aa the score 00, so each cc's vote gets weight ere^r. A single unmasked layer with fixed embeddings gives each symbol a constant score, so one layer must measure bb's frequency before the next can use it.
  • The symbol bb: with only aa and cc, the voters' own counts would fix every frequency; bb changes the vote weight while the voters stay fixed.
  • Under a causal mask: the same two layers work. At the end marker, Layer 1 sees the whole word and computes the global frequency rr. This value enters the end marker's Layer-2 query, and each cc only supplies its own key and value, so no cc needs to see the bb's that come after it.

Q1 shows that this vote is one instance of a general mechanism.

Q1: How we build on Sälzer et al. (2026), and the general space of expressible tasks.

We reuse their reduction from networks to computations on counts. What we add is a proof that no finite set of polynomial tests can follow the exponential's tie curve, and three results then map the wider space of tasks.

What we reuse. Without masking or positional encodings, all copies of a symbol share one hidden state at every layer. Sälzer et al. use this to rewrite each layer as a function of the counts, and characterize unmasked averaging hard attention with rational parameters in terms of polynomial inequalities on the counts. We reuse this rewriting step (Section 3.2).

What our proof adds. After the rewriting, a fixed unmasked network with hard attention or positive polynomial weights and semialgebraic updates decides by finitely many polynomial inequalities in the counts. We prove that no such finite set can follow the limiting tie curve (4) in letter proportions: the letter proportions of integer inputs approach this curve from both sides, and no nonzero polynomial vanishes along it (Appendices A.2 to A.4). The impossibility holds even when hard attention is allowed arbitrary real parameters, while our softmax network uses only parameters in −1,0,1\\{-1, 0, 1\\}.

What we know about the general space.

  • A family of votes, added in the revision (Section 3.1, Appendix A.6): Layer 1 can measure the frequencies of several symbols, and Layer 2 can use linear combinations of them to weight every symbol's votes.
  • Which weight functions add power (Theorem 2): replace exp⁡\exp with any continuous positive weight function ww on a fixed score interval, keeping the network unmasked and the rest semialgebraic. Such networks recognize at least one non-semialgebraic counting rule exactly when ww itself is not semialgebraic. This line is sharper than "non-polynomial": v=1/(1+s2)v = 1/(1+s^2) is not a polynomial, yet (1+s2)v=1(1+s^2)v = 1 describes it, so it adds no power, whereas exp⁡\exp and the sigmoid do. Our vote shows why ww itself is what matters: on the score interval [0,1][0, 1], at a tie with limiting bb-frequency tt, the voter ratio x/zx/z equals w(t)/w(0)w(t)/w(0), so the tie curve traces w(t)/w(0)w(t)/w(0) directly.
  • Causal masking (Theorem 4, Q2): under a shared causal mask, we characterize exactly which regular counting rules each attention rule recognizes.

A complete characterization of all counting rules that softmax recognizes is the natural next step.

AuthorsOpenReview ↗

Response to Reviewer igJh (3/3)

Q2: Studying masking further, and computational limits (Theorem 4, added in the revision).

Neither constructions nor impossibility results for hard attention transfer automatically to softmax. Without a mask, softmax goes beyond semialgebraic counting through the exponential (Eq. (1)). With a shared causal mask and BOS token, three layers of averaging hard attention decide parity, which no fixed causal softmax network can. In response to your suggestion to study masking further, the revision adds Theorem 4 to make this second result precise. This also gives an exact limit within regular counting rules.

Result. Theorem 3 compares causal with unmasked attention, which changes what each position sees. In Theorem 4, we instead give both rules the same non-strict causal mask, BOS token, and affine/ReLU layers, with no positional encodings, so only the attention rule differs. Regular counting rules combine thresholds on each count ("at least three aa's") with modular tests ("an even number of aa's"). Three layers of averaging hard attention recognize all of them, while fixed causal softmax recognizes exactly the Boolean combinations of thresholds, so it misses parity (Appendices B.6 to B.8).

Intuition. Hard attention uses prefix averages to locate the middle aa and checks whether it lies exactly halfway: among five aa's it picks the 3rd (2×3≠52 \times 3 \neq 5), and among six it also picks the 3rd (2×3=62 \times 3 = 6). For fixed causal softmax, suppose we keep inserting aa's between a fixed prefix and suffix. As their number kk grows, each layer's attention averages eventually follow a single dominant term in kk, so every ReLU settles on one branch and the accept/reject label stops changing while parity keeps alternating.

W3 (on the Taylor result in your summary): When polynomial replacement preserves decisions, and when the degree must grow (Theorem 6, formerly Theorem 5).

Table 1 in the revision lists the degree each target requires. In short, on inputs of bounded length, a sufficiently high Taylor degree preserves every decision of the vote, while any fixed degree eventually changes some decision as the input length grows.

This result connects the two halves of the paper. For each fixed degree dd, the Taylor vote x>z,Td(y/(n+1))x > z\\,T_d(y/(n+1)) becomes a polynomial inequality in the counts after clearing the positive denominator, so it belongs to the semialgebraic class that unmasked averaging hard attention recognizes. Section 5 asks how closely such a rule tracks the exact vote, and the answer depends on what is held fixed:

  • Fixed length bound: For any length bound, a sufficiently high degree preserves every decision. Through length 1,080 with all three symbols present, degree 10 changes one decision and degree 12 preserves all of them (Appendix E.3).
  • Fixed margin: For any fixed positive margin, one polynomial preserves every decision won by at least that margin, across all lengths (Proposition 5, formerly Proposition 4).
  • Growing length: As length grows, some inputs come ever closer to a tie, and exact agreement forces the exponential and polynomial cutoffs to differ by less than one count, so the degree must grow at least as fast as (1−o(1))log⁡n/log⁡log⁡n(1-o(1))\log n / \log\log n (Theorem 6).

So polynomial replacements of softmax, used for efficient or encrypted inference, preserve every decision of this vote on bounded lengths with a finite degree. For scale, in an additional exact-arithmetic check through length 64,000 (new in this response), degree 16 preserves every decision whenever all three symbols occur.

Summary. Each of your points now has a place in the paper: the introduction explains Eq. (1) through the vote before any proof and introduces "semialgebraic" in plain language, the paper marks which steps come from Sälzer et al. and which are new, Theorems 2 and 4 chart what each attention rule can express, and Table 1 organizes the Taylor result. A short reading path: the introduction, where the linear and exponential weights appear side by side; Figure 2(a) for the two layers; and Table 1 in Section 5 for when the degree must grow. We hope these changes make the paper as accessible as you suggested it could be, and we would welcome your reassessment of the presentation and overall scores.

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

This paper studies the exact counting power of attention networks without positional encodings, with a fixed architecture and parameters across input lengths. It constructs a two-layer softmax network that recognizes a nonsemialgebraic counting property, establishing a strict separation from rational-parameter unmasked averaging hard attention. It then characterizes when a continuous positive attention weight function permits nonsemialgebraic counting, assuming the remaining operations are semialgebraic. A separate construction shows that strict causal masking enables uniform attention to recognize a harmonic-sum threshold that unmasked affine/ReLU softmax networks cannot recognize. Finally, the paper distinguishes uniform output approximation from exact decision preservation under polynomial substitution, providing approximation guarantees, degree lower bounds, and a certified finite disagreement example.

Critical strengths
  1. The paper identifies two distinct sources of exact counting power through explicit constructions and impossibility results. The two-layer exponential construction is simple enough to inspect directly, while the weight-function criterion explains the broader mechanism behind the separation. The harmonic-threshold result further shows that causal masking can provide counting power even with uniform attention. Together, these results give a useful account of how the weight function and attention mask affect expressivity.

  2. The distinction between output approximation and exact decisions is developed carefully. The output guarantee applies uniformly across input lengths and accounts for changes in intermediate states after substitution. The finite-length decision lower bound addresses a different requirement and allows the replacement polynomial to depend on the target length. The certified disagreement example makes this distinction concrete. These results strengthen the paper beyond the qualitative expressivity separation.

Critical weaknesses

The main limitation is the uncertain relevance of the exact separations to finite-precision computation. The results assume exact real arithmetic, and the decision differences can occur at very small output margins. For example, evaluating Equation (3) and its degree-ten replacement at the reported length-1080 input gives outputs of approximately −2.33×10−10-2.33\times10^{-10} and 2.03×10−122.03\times10^{-12}, respectively. This supports the exact disagreement claim, but its interpretation under floating-point execution remains unclear. The paper acknowledges this limitation, and I do not view it as a correctness issue. It does, however, limit how strongly the results support conclusions about practical attention replacements.

Questions for authors

Could you clarify what the current results imply about numerical robustness? In particular, can you provide a precision requirement or a bounded-length margin analysis for the exponential counting construction, including the length-1080 example? I am asking for a clearer interpretation of the existing results rather than a complete finite-precision expressivity theory. Evidence that the distinction remains meaningful at a specified precision would strengthen my assessment of its broader significance.

2 comments
AuthorsOpenReview ↗

Response to Reviewer af6k (1/2)

Thank you for your constructive review, and for noting that our constructions are simple enough to inspect directly and that we carefully separate output approximation from exact decisions. Below we give the precision requirement and the bounded-length margin analysis you asked for, and then explain what they mean for polynomial replacements in trained models. Section, theorem, and appendix numbers refer to the revised manuscript, and results marked "new in this response" will be added to it.

W1: What precision does our construction need, and does the length-1080 disagreement persist in floating-point arithmetic?

Yes, it persists. In floating point, a computed sign is reliable whenever the output magnitude exceeds its rounding error, however small the output itself is. By this criterion, the length-1080 disagreement holds by a wide margin, and 45 significand bits suffice for each network to reproduce its own exact decisions through length 1,080.

Precision requirement. In Appendix E.3, added in the revision, we bound the rounding error of a specified evaluation with balanced pairwise summation.

  • The length-1080 input you raised (74,976,30)(74, 976, 30): Even the smaller output magnitude exceeds the binary64 rounding bound by more than 460×460\times, and the bound accounts for cancellation in the final signed sum of votes (first row of the table below).
  • Bits needed through length 1,080: 45 of binary64's 53 significand bits suffice, on every positive-count input.
  • Any length NN: O(log⁡2N/log⁡log⁡N)O(\log^2 N/\log\log N) significand bits suffice for the softmax network to decide every positive-count input up to length NN (added in the revision), so the required precision grows only polylogarithmically.

Bounded-length margin analysis. We check all 209,369,160 positive-count triples through length 1,080 exactly (see the details below), so the analysis covers the whole range. In exact arithmetic, degree 10 changes the decision only at that input, and degree 12 preserves every decision. Binary64 reproduces both results: the smallest softmax output magnitude in the range is 2.33×10−102.33\times10^{-10}, while the combined approximation and rounding error at degree 12 stays below 8.03×10−118.03\times10^{-11}. This range thus shows both where a replacement fails and at which degree full agreement returns. This agreement extends far beyond 1,080: through length 63,993 (the range covered by our binary64 rounding bound), binary64 evaluation of both softmax and its degree-16 replacement reproduces every exact softmax decision on positive-count inputs (new in this response).

Single precision. On a different input, binary32 also preserves opposite signs for the original, unscaled network, as the second row shows:

PrecisionNetwork, degreeInput (x,y,z)(x, y, z)SoftmaxReplacementRounding boundRatio to bound
binary64original, deg. 10 (App. E.3)(74,976,30)(74, 976, 30)−2.33×10−10-2.33\times10^{-10}+2.03×10−12+2.03\times10^{-12}4.39×10−154.39\times10^{-15}>460×>460\times
binary32original, deg. 5 (added in the revision)(319,2639,136)(319, 2639, 136)−1.259×10−5-1.259\times10^{-5}+1.257×10−5+1.257\times10^{-5}2.21×10−62.21\times10^{-6}5.7×5.7\times
binary32scores scaled to [0,8][0, 8], deg. 10 (App. E.4)(395,1191,1)(395, 1191, 1)−4.23×10−3-4.23\times10^{-3}+4.44×10−3+4.44\times10^{-3}4.86×10−64.86\times10^{-6}>870×>870\times

In the second example, every attention row of the degree-5 replacement stays within total variation distance 2.98×10−42.98\times10^{-4} of softmax, yet the decision still flips: the two outputs have opposite signs, and both magnitudes stay above the binary32 rounding bound. This is the distinction you highlighted, now under a specified single-precision evaluation. Scaling the second-layer scores to [0,8][0, 8] (third row) raises this ratio beyond 870×870\times.

These results rest on three checks:

  • Exhaustive coverage: for fixed nn and yy, the output is monotone in zz, so we only need to check the integers on either side of each sign change (or the endpoints); 581,581 such slices cover all 209,369,160 triples. The rounding bound holds for every token order.
  • Evaluation model: Balanced pairwise summation and an exponential routine whose relative error is at most 2−522^{-52} in binary64.
  • 45 bits: substituting u=2−45u = 2^{-45} into the bound of Appendix E.3 gives an error below 1.13×10−121.13\times10^{-12}, below the smallest degree-10 output magnitude through length 1,080 (2.03×10−122.03\times10^{-12}).
AuthorsOpenReview ↗

Response to Reviewer af6k (2/2)

W2: What do these results imply for replacing the exponential in practical models?

For practical replacements, the distinction you highlighted reappears in trained models. Our bound gives a sufficient degree for the row-error target; at degree 36, only a few predictions change in two language models, and all of them occur at near-ties, the regime of the length-1080 disagreement.

In experiments added to the revision, we replaced the exponential with its Taylor polynomial in every attention layer of frozen Pythia-70M-deduped and SmolLM2-135M (FP32), on held-out WikiText-103 and FineWeb-Edu text. The Taylor model and the exponential baseline shift and clip attention scores to the same range [0,R][0, R], so the comparison isolates the polynomial.

  • Our bound closely tracks what attention rows need. As RR grows from 8 to 32, our theoretical degree for 10−310^{-3} row total variation distance rises from 16 to 48, matching the smallest tested degree reaching 10−310^{-3} on sampled attention rows of both models; at R=19R = 19, the bound gives degree 32 (Figure 3).
  • At degree 36, the remaining changes occur at near-ties. At R=19R = 19, we compared degree 16 (below 32) and degree 36 (just above 32) on 16,384 held-out positions per model. Degree 16 changes the top-1 token at 3,239 positions (19.8%) in Pythia and 2,496 (15.2%) in SmolLM2; degree 36 changes only 10 and 1 (Section 5.3, Appendix F). All 10 Pythia changes lie among the 42 positions (0.26%) with the smallest gap between the baseline's top two logits, and SmolLM2's single change is at the smallest gap. This concentration is consistent with Proposition 5 (formerly Prop. 4): a prediction can change only when the logit perturbation reaches half of that gap.

Choice of range: We chose R=19R = 19 because a narrower range lowers the degree but also changes the model being approximated. On 2,048 positions per model, clipping at R=8R = 8 already changes 315 (Pythia) and 273 (SmolLM2) native top-1 predictions, compared with 2 and 0 at R=19R = 19.

Summary of revisions. In short, under the specified evaluation, 45 significand bits suffice for each network to reproduce its own exact decisions through length 1,080, and in binary64, degree 12 preserves every original decision. In two trained language models, the few predictions that change at degree 36 all occur at positions with the smallest top-two gaps. The revised paper adds the double-precision rounding bound with the 45-bit bound (Appendix E.3), the single-precision examples (Appendix E.4), the O(log⁡2N/log⁡log⁡N)O(\log^2 N/\log\log N) general-length precision bound, the score-range sweep (Figure 3), and the 16,384-position results (Section 5.3, Appendix F). We will also add the binary64 check through length 63,993. If these bounds and tests address your questions about specified precision and broader significance, we would welcome your reconsideration of the score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to All Reviewers

We thank the Area Chair and all reviewers for their constructive feedback, and for recognizing the rigor of our proofs, the simplicity of our constructions, and the value of disentangling expressivity and approximation gaps in softmax attention.

Core Contributions. This paper examines two standard replacements for softmax attention: averaging hard attention in theoretical expressivity analyses, and polynomial approximations of the exponential in efficient and encrypted inference. We use counting rules as a controlled setting that isolates the attention mechanism itself, and establish three main conclusions:

  1. No automatic transfer between hard attention and softmax: Neither constructions nor impossibility results transfer automatically between the two models. Without masking or positional encodings, softmax recognizes counting rules beyond the semialgebraic power of hard attention (and we characterize precisely which attention weight functions yield non-semialgebraic counting power); under a shared causal mask with a BOS token, hard attention conversely recognizes counting rules (such as parity) that fixed causal softmax cannot.
  2. The role of causal masking: Causal masking enables softmax to recognize counting rules beyond unmasked softmax networks with affine/ReLU layers, including under standard non-strict masking with a BOS marker.
  3. Output approximation versus exact decisions: For polynomial replacements of the exponential, preserving decisions separated by any fixed positive margin requires only a single fixed-degree polynomial across all lengths, whereas preserving all exact decisions as length grows forces the polynomial degree to grow.

How Our Revision and Rebuttal Address Reviewer Concerns. Across the revision and our individual responses, we strengthened both the technical scope and the accessibility of the paper along the four main themes raised by the reviewers:

  • Finite-precision robustness and margin behavior (af6k, xEtC): To address whether small-margin separations survive realistic arithmetic, we added provable rounding-error bounds in both double and single precision, exhaustive bounded-length margin checks, and a general-length precision bound. Together, these show that the distinction between close output approximation and exact decision preservation persists under a specified floating-point evaluation.
  • Implications for practical pretrained language models (af6k, xEtC): To clarify what our theory implies beyond synthetic constructions, we added experiments replacing the exponential with polynomials across all attention layers of frozen pretrained causal language models. Our row-error bound closely tracks the degree that sampled attention rows need, and at degree 36 the few remaining prediction changes all occur at positions with the smallest top-two logit gaps, consistent with our margin analysis.
  • Broader scope: masking, positional encodings, and continuous inputs (igJh, xEtC): To address questions on model assumptions and masking, we (i) proved a new converse separation under a shared non-strict causal mask with BOS, characterizing the exact regular counting rules recognized by each attention mechanism; (ii) elevated the non-strict causal construction with BOS to the main text and clarified that BOS merely marks the start while the mask supplies the counting power; and (iii) extended our constructions and analysis to rotary positional encodings, a wider family of counting rules, and continuous-input Set Transformers.
  • Clarity, motivation, and positioning (igJh, xEtC): To make the paper substantially more accessible, we rewrote the abstract and introduction in plain language around the two motivating replacements, introduced semialgebraic rules and our core counting rule intuitively before formal definitions, clearly delineated prior machinery (Sälzer et al.) from our new contributions, and turned main-text proof sketches into concise explanations supported by updated overview figures and tables.

All of these additions are already incorporated into the revised manuscript. We appreciate the reviewers' thoughtful engagement and believe these revisions substantially strengthen the paper's clarity, rigor, and practical relevance.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.