- 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
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 targets and BOS sharing the highest score, the selected coefficient is . 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 , and the explicit construction computes the weights from .
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).
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.
Response to Reviewer ErJx (1/2)
We thank Reviewer ErJx for the close reading and the comments on readability.
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 n-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 R. 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 D 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 R 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, so their unnormalized weights round to 0. The paragraph before Lemma 5 explains the choices of H,Λ,D.
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) 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 k has a DFA with 2O(k) states (Lemma 11). Every C-RASP+ program for our language therefore has size 2Ω(n), compared with O(n3) for our transformer (Theorem 12, p. 9). The task is to check records by key in a table with 2n 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 Ln is nonempty. Section 7 (p. 10) states this scope; inference cost and learning are separate questions.