acceptodds
Under review as a conference paper at ICLR 2027

Softmax Transformers Are Doubly Exponentially Succinct

Abstract

We prove that fixed-precision softmax transformers can be doubly exponentially more succinct than finite automata, resolving an open question. Over a fixed alphabet, we construct constant-depth transformers with causal masking, one head per layer, no positional encodings, width and precision , and description length . The smallest equivalent NFAs and DFAs each have states, although every accepted word has length . The state lower bound comes from the Boolean tables encoded by prefixes. The separation also holds for fixed-precision average-hard attention. The same language requires description size in C-RASP+, a counting-based formalism expressively equivalent to -precision transformers. This resolves a second open question by ruling out a polynomial-size translation into C-RASP+. A direct finite-state simulation yields a doubly exponential DFA upper bound and singly exponential bounds on shortest accepted and distinguishing words. Finally, we show that nonemptiness is NEXP-complete under the same architectural restrictions.

Primary area:
learning theory
Keywords:
transformer theory, softmax attention, fixed-precision transformers, succinctness, finite automata, formal languages, computational complexity

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_ErJxOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2(+1)
Soundness
3
Read review
Paper summary

This paper considers the succinctness of softmax transformers compared to other representation classes and solves two open problems. First, finite precision softmax transformers can be doubly exponentially more succinct than DFAs. Second, that such transformers can also be singly exponentially more succinct than C-RASP+. Finally, non-emptiness for these transformers is shown to be NEXP-complete. The main proofs are via a language that requires that checking in a sequence of (key, value) pairs, that all instances with the same key have the same value.

Critical strengths

Strong results

The results themselves are quite interesting and nontrivial. A trivial separation would show transformers are singly exponentially more succinct than DFAs, so the double exponential separation is an achievement. I believe the single exponential separation was suggested by Yang et al. 2026 and Bhattamishra et al. 2024. The consistency task defined in the paper is also interesting in its own right.

Resolving the open question about C-RASP+ is also an achievement of the paper. Thus overall the paper has strong results, and has engaged closely with the previous literature by identifying and resolving two open problems in one fell swoop.

Critical weaknesses

Unclear writing

The presentation of the proofs is unfortunately quite unclear and difficult to read. Since the primary contribution of the paper is theoretical, it is quite important for the ideas to be readable. The proofs contain a lot of extra language and abstractions, and not very many hints/signposts. Thus, while I could eventually ascertain the high-level idea of the main construction, the details are opaque to me and were thus hard to verify.

Clarity of writing is weighted quite high. My score would increase if some of the extraneous language and asides were removed, the proofs made less dense, and some additional intuition (in plain language) were given.

Unclear of relevance to practice

While the results are quite interesting, it is nevertheless unclear to what extent a double exponential separation is needed above a single exponential one, and what this might imply for machine learning practitioners. Bergsträßer et al.

Questions for authors

General questions

  • Could you clarify how to interpret figure 1? The green dot is unique-hard attention transformers? The blue star is finite-precision transformers?
  • Can you comment why the fixed-precision softmax case differs from the unique hard attention case?
  • In line 422 there is an aside about streaming, but this was not prefaced at all earlier. How is it connected to the rest of the paper?
  • Is it correct that Yang et al 2026 show that (1,1)-transformers are (singly) exponentially more succcinct than DFAs via the language #a\geq 2^k? So the results here are a significant improvement.

Theorem 4

  • Why are both @ and # used?
  • Why is it relevant that the weights are constructible in polynomial time
  • "Delimiter counts assign record addresses", delimiters were not defined
  • "be the context from m selected hashes of value 1", hashes were not defined
  • " The red cross marks failure." this seems unnecessary in the diagram
3 comments
AuthorsOpenReview ↗

Response to Reviewer ErJx (1/2)

We thank Reviewer ErJx for the close reading and the comments on readability.

Q1. The proofs contain a lot of extra language and abstractions, and not very many hints/signposts.

My score would increase if some of the extraneous language and asides were removed, the proofs made less dense, and some additional intuition (in plain language) were given.

A1.

We removed unnecessary stage numbers, grouped the recognizer into four operations, and added concrete examples and intermediate steps to the proofs. Section 4 (p. 4), Figure 2 (p. 5), and Appendix A.3 (p. 17) now use the same operation names. Appendix A.3 gives each operation's input registers, attention selections, and outputs, and accounts for the ten attention operations used to implement them.

Proposition 3 shows the two accepting runs and how joining them would accept an inconsistent input. Before Lemma 6, an example tests whether a count is at least 3; its proof treats counts below the threshold and counts at or above it separately. Lemma 7 starts with the record 101. After Proposition 9, we explain why the number of counter configurations bounds states and the number of counter increments bounds witness length. Appendix A.6 introduces INDEX before using it in the streaming proof.

An input record is v x1...xn @ #: a value bit, an nn-bit key, then @ and #. BOS is the marker before the input. The four operations are:

  • Group and rank. Count preceding # symbols to give each segment an address, freezing it once the count reaches RR. Counts within a segment assign bit ranks starting at zero and identify boundaries with the required numbers of bits and @ symbols.

  • Recover record. Each bit puts DD times its value in the coordinate for its rank. One head combines these vectors with zero at BOS. At a valid @, each coordinate is positive exactly when its bit is 1; clipping recovers the bits, and validity gating sets invalid positions to zero (Lemma 7).

  • Detect conflict. Select BOS and earlier valid records with the same key and opposite value. A threshold test flags whether any such record exists, including when normalized coefficients round to zero.

  • Global checks. Require exactly RR occurrences of each delimiter, the required bit count, no invalid boundaries, and no flagged conflicts. Appendix A.3 specifies the five predicates, threshold pairs, and final conjunction.

Selected positions have score 0; all others have score at most −H-H, so their unnormalized weights round to 0. The paragraph before Lemma 5 explains the choices of H,Λ,DH,\Lambda,D.

Q2. While the results are quite interesting, it is nevertheless unclear to what extent a double exponential separation is needed above a single exponential one, and what this might imply for machine learning practitioners.

A2.

The doubly exponential lower bound matches the number of nested exponentials in the general DFA upper bound and quantifies the cost of an equivalent automaton; it does not establish runtime or learning gains. Proposition 9 (p. 8) gives at most 22poly(S)2^{2^{\mathrm{poly}(S)}} states. A singly exponential example would leave open whether a second exponential is necessary. The polynomial dependence inside the exponent remains unresolved.

It also rules out small C-RASP+ programs for this task. C-RASP+ is a programming language based on counting operations, and a program of size kk has a DFA with 2O(k)2^{O(k)} states (Lemma 11). Every C-RASP+ program for our language therefore has size 2Ω(n)2^{\Omega(n)}, compared with O(n3)O(n^3) for our transformer (Theorem 12, p. 9). The task is to check records by key in a table with 2n2^n entries.

For practitioners, the result concerns representation size and verification. An equivalent automaton can be doubly exponentially larger than the transformer, and an equivalent C-RASP+ program exponentially larger. For the model class in Theorem 13 (p. 9), deciding whether a transformer accepts any word is NEXP-complete. This is a statement about the whole class, and for our own family the answer is always yes because every LnL_n is nonempty. Section 7 (p. 10) states this scope; inference cost and learning are separate questions.

AuthorsOpenReview ↗

Response to Reviewer ErJx (2/2)

Q3. Could you clarify how to interpret figure 1? The green dot is unique-hard attention transformers? The blue star is finite-precision transformers?

A3.

In Figure 1 (p. 2), the green point denotes Bergsträßer et al.'s unique-hard family, and the blue star denotes our fixed-precision softmax family, also realizable with rounded average-hard attention. The pale green upper-right quadrant shows the unique-hard family's coordinatewise lower bounds. The blue region records universal upper-bound constraints from Proposition 9 and Corollary 10; realizability of every point is not asserted. The axes compare growth rates up to polynomial rescaling of description size.

Q4. Can you comment why the fixed-precision softmax case differs from the unique hard attention case?

A4.

Unique-hard attention copies one maximizing position, whereas rounded softmax aggregates values and can round every normalized coefficient to zero. With mm targets and BOS sharing the highest score, the selected coefficient is round(1/(m+1))\mathrm{round}(1/(m+1)). Capped addresses, threshold tests, and validity-gated decoding give the required decisions under this rounding rule.

Proposition 9 and Corollary 10 give singly exponential shortest accepted words in our model. The doubly exponentially long shortest witnesses used by Bergsträßer et al. therefore cannot establish our state lower bound. We use doubly exponentially many distinguishable prefix tables instead.

Table 1 (Appendix A.1, p. 13) compares the two models.

Q5. In line 422 there is an aside about streaming, but this was not prefaced at all earlier. How is it connected to the rest of the paper?

A5.

The streaming bound applies to the same consistency language and shows how much memory a one-pass algorithm must retain from its prefix table. Theorem 22 reduces one-way INDEX: one player holds a bit string, the other an index, and a single message must let the second recover the indexed bit. This bounds memory retained while reading the input. Section 5.2 (p. 8) links the result to the table prefixes, and Appendix A.6 (p. 22) explains INDEX before the proof.

Q6. Is it correct that Yang et al 2026 show that (1,1)-transformers are (singly) exponentially more succcinct than DFAs via the language #a\geq 2^k? So the results here are a significant improvement.

A6.

Yes: our family strengthens Yang et al.'s singly exponential automata lower bound to doubly exponential while keeping accepted-word length singly exponential. Proposition 9 gives a doubly exponential upper bound for our model class. Section 7 (p. 10) credits their threshold-language example (2026, Section 5).

Q7. Why are both @ and # used?

A7.

The symbol @ marks where a record is decoded and compared; the following # advances the address for the next segment. In 101@#010@#, the first three bits and first @ have count 0, and the first # raises it to 1 for the next record. Section 3 defines both roles after Eq. 4 (p. 4).

Q8. Why is it relevant that the weights are constructible in polynomial time

A8.

Polynomial-time constructibility ensures that the hardness reduction can output the transformer's weights within its polynomial time bound. The paragraph after Lemma 5 (p. 5) specifies that Theorem 4 measures constructibility in nn, and the explicit construction computes the weights from nn.

Q9. "Delimiter counts assign record addresses", delimiters were not defined

A9.

The delimiters are the symbols @ and #, now defined immediately after the record format (Eq. 4, p. 4). Counting # gives a record's bits and its @ the same address. The address paragraph (Eq. 8, p. 6) explains the count, rounded average, stored address, and cap flag.

Q10. "be the context from m selected hashes of value 1", hashes were not defined

A10.

Here "hash" means the literal input symbol #. The paragraph after Lemma 5 (p. 5) identifies selected hashes as positions carrying #, each with attention value 1. Section 5.2 also defines the counting operator.

Q11. " The red cross marks failure." this seems unnecessary in the diagram

A11.

We replaced "The red cross marks failure" with the reason for rejection: two records have the same key and opposite values (Figure 2, p. 5).

Reviewer_ErJxOpenReview ↗

Response to Author

Thank you for the thorough response.

The additions to the proof have added clarity. There still remain global problems about clarity of introducing terms. For instance now “the counting tests” are mentioned in the third paragraph of the introductions with no preface. Also, you could consider using $$$ instead of #\# to avoid conflict with the counting operator.

I remain unconvinced about the importance of the theoretical results. Previous works have already known that a description size separation exists between transformers and automata, and that verification is infeasible. Where these new results on a double exponential separation add onto the story for ML practitioners is unclear.

I will increase the presentation score but maintain the overall score.

I thank the authors again for the careful response which has clarified much for me.

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

This paper studies the description complexity of regular languages represented by softmax transformers with fixed precision. It constructs a family of key-value consistency languages. A causal transformer recognizes each language with constant depth, one head per layer, and no positional encodings. Its width and precision are , and its description length is . The smallest equivalent NFAs and DFAs require states. Accepted words have length only . The minimum size of an equivalent C-RASP+ program is , which rules out a polynomial-size translation. Further results include a general finite-state simulation, singly exponential witness bounds, and NEXP-completeness of nonemptiness under strong architectural restrictions. The appendix reports exact arithmetic checks of the explicit constructions and their implementations.

Critical strengths
  1. The paper resolves two concrete open questions with explicit size separations. Bergsträßer et al. (2026) leave open whether fixed-precision softmax and average-hard attention can be doubly exponentially more succinct than finite automata. Theorems 4 and 8 answer yes. They construct transformers with descriptions of size . Every equivalent NFA or DFA requires states. Corollary 20 extends the construction to fixed-precision average-hard attention. Yang et al. (2026) ask whether fixed-precision transformers admit a polynomial-size translation to equivalent C-RASP+ programs. Theorem 12 answers no. For the same language family, the minimum size of an equivalent C-RASP+ program is . The transformer descriptions remain polynomial in n, so such a translation cannot have polynomial output size. Accepted words have length only . The automaton lower bound comes from distinguishing prefix tables, rather than a doubly exponential shortest accepted word.

  2. The main construction involves substantial technical work. The recognizer combines bit-level parsing, address and rank recovery, conflict detection, and format checks. Lemma 6 preserves threshold decisions even when normalized attention coefficients round to zero. Capped addresses and validity gates also handle overly long and malformed inputs. These operations fit within a model with constant depth, one head per layer, and no positional encodings. This is a complete construction rather than an idealized retrieval example.

  3. The results form a coherent theoretical picture. The paper separates state complexity from witness length. Proposition 9 and Corollary 10 use capped histograms to explain this distinction. A model can require a large equivalent automaton while still admitting short accepted and distinguishing words. The C-RASP+ result shows that equal expressive power need not permit efficient translations. The nonemptiness result connects succinct representations to the complexity of formal verification.

  4. The technical details and verification effort are valuable. Precision is included in the description length. The paper also distinguishes the family parameter from input length. Appendix A.10 gives bounded accumulators whose size does not depend on input length. Appendix A.11 proves robustness of the main recognizer under two rules that round after each operation. Appendix A.9 compares register evaluation, compiled matrices, and an independent semantic recognizer. These checks fit the theoretical claims. I did not find a concrete counterexample to the main construction or the finite-state simulation in the arguments I examined.

Critical weaknesses
  1. The new techniques should be distinguished more clearly from standard arguments. The accepting-run argument in Proposition 3, the capped counters in Lemma 11, and the INDEX reduction use established methods. Several later results also share the same recognizer. The main technical novelty lies in the explicit softmax construction and how its components work together. The introduction could identify these new components more precisely. This would help readers assess the contribution without treating every corollary as a separate technical advance.

  2. The quantitative resource bounds leave room for refinement. In terms of description length S, the construction gives a lower bound of the form . The general upper bound is . This establishes a doubly exponential separation but leaves the precise dependence on description length unresolved. The optimal tradeoffs among width, precision, and depth are also unclear. These limits reduce the quantitative detail of the result. They do not undermine the main separation.

  3. The applications concern representation and verification rather than demonstrated runtime gains. Precision is fixed with respect to input length, but it grows across the model family. The paper does not establish which problem sizes can be supported at a standard fixed bit width. The transformer also retains earlier token representations. A smaller parameter description therefore does not imply lower total inference memory. The paper acknowledges this distinction. A more focused discussion could explain the implications for model compression and formal verification. The worst-case complexity results do not predict the performance of a practical verifier.

  4. The presentation of assumptions and implementation checks could be clearer. Checking the arithmetic conditions requires moving between Appendices A.1, A.2, A.10, and A.11. Robustness to rounding after each operation is proved for the main consistency recognizer. It does not automatically extend to every general upper bound. A table linking each theorem to its arithmetic conventions would help. Appendix A.9 checks the compiled matrices of the main recognizer. Its tiling checks cover the register circuits. The verification summary should make these levels easy to distinguish. Finite checks support the construction but do not replace its proof.

Questions for authors
  1. What does Lemma 6 add to the counting construction of Yang et al.? Please separate the new rounding analysis, handling of arbitrary input lengths, and record recovery.

  2. How much of the gap between the bounds expressed in S is due to dense encoding? Please discuss possible tradeoffs between width and precision, and which bounds may be improved.

  3. Could a single table identify which theorems support downward rounding, nearest rounding, bounded accumulators, and rounding after each operation?

  4. Could the verification summary list parameter ranges, implementation levels, and boundary cases? Is there also a check of the full compiled matrices for the tiling construction?

3 comments
AuthorsOpenReview ↗

Response to Reviewer aywd (1/3)

We thank Reviewer aywd for the detailed technical questions, which led to Table 2, a new discussion of description size in Appendix A.4, and the revised verification summary in Appendix A.9.

Q1. The new techniques should be distinguished more clearly from standard arguments.

The main technical novelty lies in the explicit softmax construction and how its components work together.

A1.

The main new construction is the explicit softmax recognizer and its correctness on every input; accepting-run splicing, capped-counter simulation, and the INDEX reduction use standard methods. The recognizer combines capped record addresses, bit ranks, one-head record recovery, validity checks, and conflict detection, including on arbitrarily long malformed words. Section 1 (p. 1) now states these contributions and credits the earlier methods.

We credit Yang et al. (2026, App. B.4) for the counting idea that assigns the start marker BOS an offset value. Three arguments are standard, namely joining parts of accepting runs in Proposition 3 (the fooling-set method), capped counters in Lemma 11, and the one-way INDEX reduction in Appendix A.6. The witness bound uses counts of hidden vectors, the C-RASP+ result uses the automata lower bound, and NEXP-completeness also needs the tiling reduction.

Q2. What does Lemma 6 add to the counting construction of Yang et al.? Please separate the new rounding analysis, handling of arbitrary input lengths, and record recovery.

A2.

Lemma 6 (p. 6) extends BOS-offset counting to round-to-nearest with any fixed tie rule and proves correctness for arbitrarily many targets; record recovery is established separately in Lemma 7 (p. 7). Yang et al. (2026, App. B.4) introduced the offset method under downward rounding. Our lemma covers thresholds 1≤t≤1/(4δ)1\le t\le1/(4\delta), where δ\delta is the grid spacing. If the count mm is below tt, the offset −(t−12)-(t-\tfrac12) puts the unrounded context at most −3δ/2-3\delta/2. After rounding it is at most −δ-\delta, so its sign stays negative.

A malformed input can have arbitrarily many targets, so its coefficient α=round(1/(m+1))\alpha=\mathrm{round}(1/(m+1)) may become zero. This requires m≥tm\ge t, since Lemma 6 gives α≥3δ\alpha\ge3\delta when m<tm<t. Zero context is therefore possible only where the test should answer "yes", and the test works for every m≥0m\ge0.

Lemma 6 only tests counts, so record recovery also needs addresses that freeze after RR occurrences of # (Eq. 8), bit ranks (Eq. 10), and checks for valid records. Without the cap, the rounded address average eventually drops to 0. Lemma 7 combines these parts to read a whole record with one head, and its proof starts with the example 101.

AuthorsOpenReview ↗

Response to Reviewer aywd (2/3)

Q3. How much of the gap between the bounds expressed in S is due to dense encoding? Please discuss possible tradeoffs between width and precision, and which bounds may be improved.

A3.

For this construction, sparse encoding reduces description size from O(n3)O(n^3) to O(n2)O(n^2), while bounded depth requires pd=Ω(n)pd=\Omega(n) and rules out constant precision even with unrestricted width. Its matrices have O(n2)O(n^2) entries but only O(n)O(n) nonzero coefficients: the compiler has a fixed number of blocks, O(n)O(n) rows per block, and a constant number of nonzero coefficients per row, including signed-value relays. Listing coefficients and indices costs Ssp,n=O(n(p+log⁡(n+1)))=O(n2)S_{\mathrm{sp},n}=O(n(p+\log(n+1)))=O(n^2) bits. Thus the state lower bound is 22Ω(Ssp,n1/2)2^{2^{\Omega(S_{\mathrm{sp},n}^{1/2})}} under sparse size, compared with 22Ω(Sn1/3)2^{2^{\Omega(S_n^{1/3})}} under dense size Sn=∣Tn∣S_n=|T_n|. A universal sparse-size form of Proposition 9 requires separate analysis.

There is also a gap in the generic simulation: for this family's d,p=O(n)d,p=O(n) and constant LL, it gives 22O(n2)2^{2^{O(n^2)}} states, whereas Proposition 3 gives the minimum 2Θ(2n)2^{\Theta(2^n)}.

For every recognizer of LnL_n under Proposition 9, 2n≤1+L(p+s+1)2pd2^n\le1+L(p+s+1)2^{pd} and hence pd≥n−log⁡2(4Lp)pd\ge n-\log_2(4Lp). Thus bounded depth forces pd=Ω(n)pd=\Omega(n).

The precision claim follows by counting reachable vectors over the fixed alphabet. Put K=2p+sK=2^{p+s} and let mℓm_\ell count reachable layer-ℓ\ell vectors on all inputs. There are no positional encodings, so m0≤∣Σ∣+1m_0\le|\Sigma|+1. The preceding vector and capped histogram determine the next vector, giving

\operatorname{dfa}(L(T))\le2\prod_{\ell=1}^{L}(K+1)^{m_{\ell-1}}.$$ At bounded precision and depth this is a uniform constant independent of width, contradicting $\operatorname{dfa}(L_n)\ge2^{2^n}$ for unbounded $n$. Thus width alone cannot keep precision bounded for the whole family. This does not prove a linear precision lower bound. Our construction uses $pd=\Theta(n^2)$ and $p=\Theta(n)$; optimal precision growth remains open. These analyses are included in Appendix A.4 (pp. 19–20). > **Q4.** The applications concern representation and verification rather than demonstrated runtime gains. > The paper does not establish which problem sizes can be supported at a standard fixed bit width. > A smaller parameter description therefore does not imply lower total inference memory. **A4.** The results establish description-size and verification bounds; runtime gains, lower total inference memory, and implementations at standard bit widths remain unproved. Section 7 (p. 10) states this scope. Inference memory includes the earlier token representations retained by attention, and we make no claim about learnability. The explicit sufficient choice $p=12n+78$ (Appendix A.1, p. 13) uses 90 bits at $n=1$, above 16-, 32-, and 64-bit formats. For a specified finite $n$, whether a different construction works at these bit widths remains open. This finite-instance question differs from using one bounded precision across the entire family as $n$ grows: at fixed alphabet and bounded depth, Appendix A.4 (pp. 19–20) now rules out the latter even with unrestricted width. The optimal asymptotic precision growth remains open.
AuthorsOpenReview ↗

Response to Reviewer aywd (3/3)

Q5. Could a single table identify which theorems support downward rounding, nearest rounding, bounded accumulators, and rounding after each operation?

A5.

Table 2 (Appendix A.1, p. 14) now lists the results supported by each arithmetic rule, including both rules that round after each operation. Section 2.2 points to the table.

  • Recognition and the automata separation (Theorems 4 and 8) hold with downward rounding, round-to-nearest, bounded accumulators, and both rules that round after each operation in Proposition 26.

  • The correspondence with Yang et al.'s (1,1)(1,1) model (Lemma 21) uses downward rounding. The C-RASP+ lower bound itself is a property of the language LnL_n, independent of any rounding rule.

  • The general DFA and short-witness bounds (Proposition 9, Corollary 10) and decision results (Theorem 13, Corollary 24) hold with downward rounding, round-to-nearest, and bounded accumulators. The decision results also require a tie rule computable in polynomial time. For rounding after each operation, the paper states recognition and the automata separation only.

With bounded accumulators, sums use storage bounded independently of input length, and this storage may be wider than the original pp-bit grid.

Q6. Could the verification summary list parameter ranges, implementation levels, and boundary cases? Is there also a check of the full compiled matrices for the tiling construction?

A6.

Appendix A.9 (p. 26) now lists the parameter ranges, implementation levels, and boundary cases; the tiling construction is checked at the register level, with no full compiled-matrix check. The submitted case counts are retained, and commands and further results remain in the supplementary code.

  • The consistency tests run the compiled matrices on all formatted words for n=1n=1, all words of length at most three, edited inputs, and selected cases for n=2n=2. They compare acceptance with the register program and a separate checker of the language definition.

  • The tiling tests use the register representation, which describes operations on named values before compilation into matrices. They include all 2×22\times2 assignments for tile sets of sizes three and four, every record ordering of one valid grid, selected 4×44\times4 cases, malformed records, duplicate coordinates, and illegal labels. Local-circuit tests include counts near reciprocal underflow.

Lemma 16 proves how to compile the register representation into matrices. An input-to-output run of the compiled tiling matrices, like the one in the consistency tests, would require extending our compiler.

The code implements downward rounding and nearest-even rounding, which resolves ties by choosing an even grid index. For other fixed nearest tie rules and the two operation-by-operation rules, the stated results rest on the proofs alone.

Q7. Finite checks support the construction but do not replace its proof.

A7.

Correctness for all input lengths and the stated rounding rules rests on the proofs; the tests check only the listed finite cases. Appendix A.9 (p. 26) states this scope, distinguishes full-matrix tests from register-circuit tests, and gives the parameter ranges of the main suites.

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

This paper extends existing work examining succinctness of transformer architectures showing that a softmax transformer architecture can be applied to accept languages that may only be recognized by nondeterministic finite automata at least 2 exponential in the size of the transformer. This extends existing result for hard attention transformers which are known to be doubly exponential over NFAs. These results improve existing results from 2EXP to EXP in the shortest accepted word length.

While these results have some theoretical interest, they are not especially surprising as the context window of a transformer must be encoded in states for any equivalent NFA, making some degree of succinctness expected. The result is extended to C-RASP.

The paper is clear, well organised and appears correct. There is an opportunity to improve the paper by highlighting the novelty of the result as compared to Bergstrasser et al.

Critical strengths

Theoretically rigorous results. Improved bounds and generalisations of existing state of the art. Links theoretical foundations of computer science with contemporary AI tools.

Critical weaknesses

It is not clear how the methodology extends the work of Bergstrasser et al.

Questions for authors

What is the novel insight in work that goes beyond the work of Bergstrasser et al?

2 comments
AuthorsOpenReview ↗

Response to Reviewer uNqK

We thank Reviewer uNqK for asking how our work goes beyond Bergsträßer et al., which led us to add Table 1 comparing the two models.

Q1. While these results have some theoretical interest, they are not especially surprising as the context window of a transformer must be encoded in states for any equivalent NFA, making some degree of succinctness expected.

A1.

Our result establishes a doubly exponential automata gap for fixed-precision softmax transformers, resolving the open question left by Bergsträßer et al. (2026). Encoding a context in automaton states suggests succinctness, but does not show that a polynomial-size transformer can enforce the required distinctions after rounding. Yang et al.'s (2026) threshold language gives a singly exponential gap. Our automata lower bound uses a standard accepting-run argument; the explicit softmax recognizer supplies the compact representation.

Rounding can erase attention weights even when every earlier position is visible. Suppose m+1m+1 positions share the highest score and their rounded weights before normalization are nonzero. The denominator sums at least these m+1m+1 equal weights, so each coefficient is at most round(1/(m+1))\mathrm{round}(1/(m+1)). This is zero for large enough mm under either rounding rule. In our construction these positions are mm targets and BOS, the marker before the input. The recognizer must remain correct when these coefficients are zero and reject malformed inputs of any length.

The lower and upper bounds have the same number of nested exponentials: Proposition 9 (p. 8) gives every transformer in our model an equivalent DFA with at most 22poly(S)2^{2^{\mathrm{poly}(S)}} states, where SS is the dense description length in bits. Our lower bound is doubly exponential. We do not claim tight polynomial dependence inside the exponent.

Q2. It is not clear how the methodology extends the work of Bergstrasser et al.

What is the novel insight in work that goes beyond the work of Bergstrasser et al?

A2.

We construct a fixed-precision softmax recognizer and obtain the automata lower bound from distinguishable prefix tables, whereas Bergsträßer et al. use doubly exponentially long shortest words. Each of our tables has 2n2^n Boolean entries, so there are 22n2^{2^n} tables encoded by prefixes of singly exponential length.

Our simulation tracks the current vector and counts of past vectors, stopping each count at a fixed cap, and these counts never decrease. Proposition 9 and Corollary 10 use this to show that every nonempty recognized language has a singly exponential-length witness, meaning an accepted word. Their long-witness argument therefore cannot establish the state lower bound in our model; we instead use one prefix per Boolean table, and accepting-run splicing shows that these prefixes require different automaton states (Proposition 3).

The recognizer is new as well, because rounded softmax returns a weighted sum whose coefficients can round to zero, and the recognizer must remain correct when they do. Our constant-depth recognizer has one head per layer and no positional encodings. It assigns record addresses by counting #, places each bit in its own coordinate, and reads a whole record with one head. A head in a later layer finds records with the same key and opposite values (Section 4, Figure 2). The construction works on every input. We credit Yang et al. (2026) for the BOS-offset counting idea.

The same language rules out a polynomial-size translation into C-RASP+, a programming language based on counting operations (Theorem 12), a question that Yang et al. (2026) left open. A tiling reduction built on the record parser gives NEXP-hardness of nonemptiness, the question of whether a given transformer accepts any word, and Corollary 10 gives membership in NEXP (Theorem 13). Sälzer et al. (2025) left softmax hardness open. These two results reuse the language and the parser of the main construction.

Table 1 in Appendix A.1 (p. 13) compares the models.

Q3. These results improve existing results from 2EXP to EXP in the shortest accepted word length.

A3.

The singly exponential witness bound applies to our fixed-precision softmax model; Bergsträßer et al.'s doubly exponential witnesses use unique-hard attention. Corollary 10 shows that a transformer in our model accepting any word accepts one of length at most 2poly(S)2^{\mathrm{poly}(S)}. Our family still requires doubly exponentially many automaton states. Figure 1(b) (p. 2) shades the region allowed by Proposition 9 and Corollary 10.

Thank you for your clear and thoughtful responses. I agree with the result, and to some degree it's significance, but a clear summary of the enabling insight would be interesting as well. I will maintain my rating.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the reviewers for their careful reading and constructive feedback. We summarize the main revisions below and address each reviewer's questions separately. Added or revised text is highlighted in red.

1. Readability (aywd, ErJx). We removed unnecessary stage numbers and organized Section 4 and Figure 2 around four operations: group and rank, recover record, detect conflict, and global checks. Proposition 3 displays the accepting runs; concrete examples explain threshold tests and record recovery. The parameters are explained before Lemma 5, and Appendix A.3 gives the implementation details.

2. Contribution relative to prior work (uNqK, ErJx). Table 1 (Appendix A.1, p. 13) compares the models and results. We distinguish the new explicit softmax recognizer from standard automata, capped-counter, and INDEX arguments, and credit Yang et al. for BOS-offset counting. We explain why our construction needs a different argument from unique-hard attention: rounded coefficients can become zero, and shortest accepted words are only singly exponential despite the doubly exponential state lower bound.

3. Description size and precision (aywd Q3–Q4). Appendix A.4 (pp. 19–20) adds the sparse description estimate O(n2)O(n^2) and analyzes width–precision tradeoffs. At fixed alphabet and bounded depth, bounded precision cannot recognize the whole family LnL_n, regardless of width. This does not establish a linear precision lower bound; optimal precision growth and implementations at standard bit widths for specified finite nn remain open.

4. Arithmetic, verification, and scope. Table 2 (Appendix A.1, p. 14) identifies the arithmetic assumptions for each result. Appendix A.9 (p. 26) separates compiled-matrix tests of the consistency construction from register-level tests of the tiling construction and states their finite coverage. Section 7 (p. 10) clarifies that the results concern description size and worst-case decision complexity; runtime and learnability gains are not established.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.