- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the cost of exactly replacing a UHAT by a finite-state RNN on every input. The worst case replacement costs for fully unmasked, causal and mixed mask UHATs are polynomial, single-exponential and double-exponential respectively (assuming no positional encodings and assuming exact arithmetic).
Note that [1] had already established exponential replacement bounds for causal UHATs and doubly exponential upper bound for mixed-mask UHATS. There are two main new results here. First, fully unmasked UHATS have poly sized separation, the second the mixed mask UHATS that require doubly exponential recurrent memory (the upper bound that was expected) is actually constructed.
The authors also provide a general construction that can convert a causal UHAT to an equivalent RNN. Finally, they also show that the doubly exponential case holds even if some errors are allowed, as long as the average error stays below 1/2.
[1] Bergsträßer et al ICLR 2026: Transformers are Inherently Succinct
Critical strengths
The technical contributions made by the paper are clear, and complement the existing results from [1] and the proofs look correct to me.
[1] Bergsträßer et al ICLR 2026: Transformers are Inherently Succinct
Critical weaknesses
While technically, everything is correct, I was just not excited about the paper when I read it. I personally do not see any practical relevance of the results here. This is not a reason to reject, but I am just sharing my opinion. The hierarchy that is being completed - I am not sure, whether this was in any way a critical open problem or whether it truly increases our understanding.
What I mean is that, the notion of succinctness by [1] was important and gave a new and fresh perspective about Transformers, and was one of the rare frameworks which explained why Transformers are so successful in real life. Given the results of the Bergsträßer paper, I personally think that these new set of results do not improve intuitions about how powerful Transformers are compared to recurrent models. I hope I have not missed something, if I have, I would request the authors to point that out.
And of course, every theory paper has assumptions, and theoretical abstractions like UHAT, and no positional encodings etc are all necessary to get started, and to establish the first set of results on them. But to me, follow up papers that try to add to the results, should try to close the gap between existing assumptions and practice. The current paper seems to go in the opposite way, it doubles down in some sense -- the combinations of causal and unmasked attentions that are being studied, they help theoretically, I do not see how going the "other way" and establishing stronger separations in that setting is a substantial contribution.
Even though, it feels like this paper belongs more in TMLR, rather than here. I will keep my score as weak reject for now to denote the fact that I am not particularly excited about the results of the paper, and do not immediately see how it could be impactful or whether there are any practical takeaways. I would love to engage with the authors if they disagree and feel that my points are not valid. In fact, if the discussion turns out to be fruitful, I would be happy to increase my score, and as a side note would also then suggest that the authors put points from the discussion in the next draft. Understanding those implications, and understanding why I as a general ML audience member should be excited about the results here, can only add to the paper.
[1] Bergsträßer et al ICLR 2026: Transformers are Inherently Succinct
Questions for authors
- Could you expand on why these results are interesting?
- Would these results be possible, if you remove the exact arithmetic assumption? In general, how strongly are the assumptions connected to the separations?
- Minor: Appendix link is broken on line 473.
3 comments
Thank you for your response and your clarification.
Re: your response to Weaknesses, Q1.
The authors agreed that, this was not some open problem and that completing the hierarchy is not a significant contribution. Finding what kinds of information flow makes attention compact is as I suspected studying attention models that are not used in practice with assumptions that also make it far removed from practice.
I think I am more convinced now that this is just a misfit for the venue imo: the paper is technically correct, and at the same time authors seem to agree that a large part of their paper (completing the tower) is not as significant as it was made out to be in their submitted version. It also seems that the other reviewers share my viewpoint at least to some extent.
Owing to the last minute response from the authors, it's a pity that we can't have more back and forth. However, I would want to share a small suggestion that may help the authors in a future version of the paper. The fact that context representations that depend on the query are exponentially cheaper than the ones fixed before the query arrives is something that the authors could expand upon. Perhaps some discussion (even better if some experiments can be designed as well) around when this takes place in some actual queries/ benchmarks would really help ground the contribution.
Thank you for taking the time to consider our response despite the very short time available, and for offering a constructive direction for future work. We particularly appreciate your suggestion to connect query-dependent context representations to concrete tasks and benchmarks. This suggestion may guide and expand our paper. We plan to develop this aspect more clearly in a future version and explore experiments that could help establish when this distinction matters in practice. Your feedback has been helpful in identifying how we can strengthen and better motivate the paper. We again thank you for your thoughtful suggestions.
Thank you for the careful reading and for the offer to discuss.
Why the results are interesting (weaknesses, Q1). We agree that the hierarchy was not a designated open problem, and that a taller tower alone would add little to Bergsträßer et al. What we think it adds is an answer to which information flow makes attention compact. Seeing the whole input is not enough (Thm 4.1). Searching the past from the last token is not enough either: every causal UHAT for Dn has size 2Ω(n) (Cor 4.5). The small recognizer exists because one unmasked retrieval lets each dictionary cell read the later query, after which causal retrievals check whole records. In short, context representations that may depend on the query are exponentially cheaper here than ones fixed before the query arrives.
Q2 (exact arithmetic). The recurrent lower bound involves no arithmetic; it counts distinguishable prefixes of Dn. Exact rationals are needed for the general upper bounds, not for the separating family: Tn uses Boolean fields and integer scores in [−1,n] with a gap of at least 1 between matching and non-matching keys, so signed integers of O(logn) bits suffice at every input length. We also implemented Tn and compared it with an independent parser for Dn on 149,216 words (n≤6) without a disagreement. Arbitrary rounding is a different matter, since it can change ties, and we make no claim there. We will add this remark.
Q3. The reference pointed to a section we had removed. We will fix it.