acceptodds
Under review as a conference paper at ICLR 2027

Mind the Mask: A Succinctness Hierarchy for Attention and Recurrence

Abstract

How large must a recurrent model become to reproduce an attention model's decisions? We study exact replacement on every finite nonempty sequence for unique hard-attention transformers without positional encodings and with exact rational evaluation. The recurrent target has fixed finite state and explicitly represented Boolean update and readout circuits. We show that the replacement cost depends sharply on the attention masks. For fully unmasked attention, we prove an exact characterization by the first- and last-occurrence orders of input symbols, with polynomial conversions to profile predicate circuits and polynomial-size recurrent replacement. For mixed masks, we construct dictionary recognizers over a four-symbol alphabet, of description size polynomial in , for which every exact recurrent replacement requires at least persistent bits. One unmasked retrieval between causal stages makes dictionary representations depend on the later query; causal operations then compare complete blocks. Together with inherited bounds, these results give polynomial, single-exponential, and double-exponential replacement regimes for unmasked, causal, and mixed attention. A direct causal compiler further quantifies the role of retrieval depth, and classical information bounds show that, under a specified dense dictionary distribution, any fixed average error below one half still requires a constant fraction of these bits.

Primary area:
learning theory
Keywords:
Transformers, recurrent neural networks, attention masks, memory complexity, formal languages, succinctness, sequence modeling

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_J8DFOpenReview ↗
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
  1. Could you expand on why these results are interesting?
  2. Would these results be possible, if you remove the exact arithmetic assumption? In general, how strongly are the assumptions connected to the separations?
  3. Minor: Appendix link is broken on line 473.
3 comments

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 DnD_n has size 2Ω(n)2^{\Omega(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 DnD_n. Exact rationals are needed for the general upper bounds, not for the separating family: TnT_n uses Boolean fields and integer scores in [−1,n][-1,n] with a gap of at least 1 between matching and non-matching keys, so signed integers of O(log⁡n)O(\log n) bits suffice at every input length. We also implemented TnT_n and compared it with an independent parser for DnD_n on 149,216 words (n≤6n \le 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.

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.

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

Previous work [1] exhibit languages on which transformers are more succinct than recurrent architectures. That is the smallest transformer to accept the language is smaller than the smallest recurrent architecture to accept it. Let us write GG the gap in sizes. [1] also provide an upper bound on GG by constructing (bigger) recurrent architectures that can simulate arbitrary transformers (that is they accept the same language). They do this on several masking strategies.

This paper builds on [1] by showing that their upper bound on GG is tight. This closes a gap, as the lower bound offered in [1] is not tight.

[1] Transformers are inherently succinct, Bergsträßer et al, ICLR 2026

Critical strengths

This paper, while incremental, closes a gap in the literature.

Critical weaknesses

The main weakness of this paper is that it is poorly written. I think it requires major rewriting before it can be valuable to the community.

  • The main are of this paper is expressivity/the study of formal languages. It is surprising that this is not mentioned neither in the title or abstract.
  • The paper never motivates its result.
  • Many terms are undefined, including some that are core to the main theorems: exact replacement (line 12), ss (Table 1), persistent bits (lines 20, 56, 64, 92, 101, 102, 110, ...), source (line 136), vv (line 155, eligible positions (line 154) only to cite a few.
  • Many claims are unjustified (you can cite [1] when you mention the limits of RNNs on information retrieval for instance).
  • The introduction makes no distinction between what is proven by previous work and what is proven by the paper.
  • I don't understand the relevance of the dictionary lookup task in the context of expressivity studies.
  • There are typos ("earlier" and "later" inverted line 33, "the set of" missing line 137, "??" line 474).

These are just a few things. I encourage the authors to spend time polishing the writing as it is really hard to read as is.

[1] RNNs are not Transformers (Yet): The Key Bottleneck on In-Context Retrieval, Wen et al, ICLR 2025

Questions for authors

What are your motivations for this work?

How is Theorem 4.3 different from point 3 of Proposition 4.2?

1 comment

Thank you for the concrete list; we agree with most of it.

W1. The abstract will state in its first sentence that the paper is about formal-language recognition.

W2, Q1 (motivation). Recurrent and state-space models are proposed as cheaper replacements for attention. We ask the formal version: when a UHAT recognizes a language, how large must an RNN recognizing the same language be, and how does the answer depend on the attention mask? The general response summarizes the answer.

W3, W4. These notions are defined in Section 2 but used earlier. We will define them at first use. We will cite Wen et al. (2025) where we mention the retrieval limits of recurrent models.

W5. See "New and inherited" in the general response. The introduction and Table 1 will carry this marking.

W6. The dictionary language is the witness for the lower bound. Before the query arrives, an RNN must distinguish arbitrary sets of records, which gives 222n2^{2^{2^n}} distinguishable prefixes, while a UHAT of size poly(n)\mathrm{poly}(n) recognizes the language. The language is regular, so this is a statement about size, in the sense of the succinctness results of Bergsträßer et al.

W7. We will fix the typos.

Q2. Both give the same worst-case bound 2poly(s)2^{\mathrm{poly}(s)}. Prop 4.2(3) obtains it through the LTL translation. Thm 4.3 is a direct construction whose cost is polynomial in the number of distinct activation vectors, and Thm 4.4 needs this parameter: it gives polynomial replacement when 2klog⁡(m+1)=O(log⁡s)2^k \log(m+1) = O(\log s). Cor 4.5 can use either. We will present Thm 4.3 as a refinement.

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

The paper studies how much recurrent memory is needed to exactly reproduce hard-attention models without positional encodings. It shows that fully unmasked models admit polynomial-size recurrent replacements, while certain models mixing causal and bidirectional attention require doubly exponentially many recurrent state bits. These results clarify how attention masks affect the cost of recurrent replacement, and hence the title of the paper.

Critical strengths

The paper proves a new lower bound on recurrent memory required to exactly reproduce attention models’ outputs. It constructs small hard-attention models with causal and bidirectional masks whose equivalent finite-state recurrent models require doubly exponentially many state bits. This strengthens the previous single-exponential lower bound.

The paper also shows when only a polynomial-size recurrent replacement is needed. Fully unmasked hard attention without positional encodings depends only on the first- and last-occurrence orders of symbols to determine its answer. A recurrent model can store these two lists and reproduce the answer, giving a polynomial-size replacement.

Critical weaknesses

The theoretical results assume hard attention without positional encodings, and the strongest result requires bidirectional masking. It is unclear which conclusions extend to practical causal transformers.

Questions for authors

Could the authors clarify the main takeaways for practitioners? Specifically, what do these results imply about the recurrent state needed to match attention on practical tasks such as in-context recall? Which conclusions, if any, extend to causal softmax transformers with positional encodings?

It may be useful to test whether a mixed-mask model, with width and depth in similar ranges to the theoretical construction, can learn the dictionary task through training or not. This can help assess whether the compact solutions established by the theory can be learned in practice, clarifying the practical relevance of the lower bound on memory.

1 comment

Thank you for the positive assessment and the questions.

W1, Q1 (practice). The hierarchy is proved for hard attention without positional encodings; we do not claim it for causal softmax transformers. Two things carry over. (i) The memory bound depends only on the task. Any one-pass model with finite state, including state-space models, that must decide after the context whether a queried record occurred needs 22n2^{2^n} bits for DnD_n, and with a dense random dictionary any constant error below 1/2 still needs a constant fraction of them (Thm 3.3). This gives no numerical requirement for natural-language recall without a reduction from that task. (ii) The mechanism. The compact solution does not search the past from the last token; it re-encodes each context position using the later query. Whether a size gap of this kind holds for softmax attention with positional encodings is open, and it is what we plan to work on next.

Q2 (training). We will run a simulation with hard-attention transformers with various mask structures.

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

The paper asks how large a recurrent recognizer RR must be to reproduce an attention recognizer TT: for every finite nonempty input ww, require R(w)=T(w)∈0,1R(w)=T(w)\in\\{0,1\\}. It studies exact rational hard attention without positional encodings. For fully unmasked attention, every model of size ss has an equivalent recurrent recognizer of size poly⁡(s)\operatorname{poly}(s). By combining causal and unmasked attention, however, the paper constructs models of size poly⁡(n)\operatorname{poly}(n) that solve a dictionary-membership task, while any recurrent recognizer solving the same task exactly needs at least 22n2^{2^n} bits of memory. Thus, a small attention model can require an enormously larger recurrent replacement. Further results address retrieval depth and approximate recognition.

Critical strengths

(1) The mixed-mask construction establishes a new separation: a small attention model solves a dictionary-membership task that requires doubly exponentially many bits of recurrent memory. The construction handles malformed inputs and checks that the query matches a single complete record. It also yields a comparison between causal and mixed attention on the same task.

Critical weaknesses

(1) The significance of the stronger separation is insufficiently established. Prior work already demonstrates retrieval-memory separations between small Transformers and recurrent models (Bhattamishra et al., 2024, Theorems 3 and 7–8). Although those results do not subsume this construction, the paper does not convincingly explain what conceptual understanding its sharper bound adds.

(2) The technical advance is modest. The dictionary construction adapts addressed-cell encodings, counters, equality-based retrieval, and verification gadgets from Bergsträßer et al. (2026, Appendix A.2–A.3). Its query-dependent block aggregation is new, but the remaining results largely combine inherited bounds, a short profile argument, the known activation-count recurrence (Yang et al., 2024, Lemma 22), and standard random-access information arguments (cf. Nayak, 1999, Theorem 2.3, for the related quantum bound).

(3) The exposition also leaves the conceptual contribution unclear. Repeated resource qualifications and subsidiary results obscure the main obstacle and why overcoming it matters. An earlier explanation of why unmasked attention is restricted and mask interleaving changes the picture would help.

Questions for authors

(1) What is the main technical obstacle overcome by the dictionary construction beyond adapting the predecessor’s gadgets?

(2) Why is the resulting mask-ordering separation consequential beyond completing the succinctness classification?

1 comment

Thank you for the precise questions.

W1 (significance, relation to Bhattamishra et al.). We agree that retrieval-memory separations were known and that those results are closer to practice. They concern inputs of length up to NN, with width and precision growing like log⁡N\log N. In our setting one fixed recognizer works at every length and the comparison is in description size, where the gap is doubly exponential and meets the known upper bound. The part without a counterpart there is the role of the mask (Thm 4.1, Cor 4.5), which compares transformers with transformers.

W2 (technical advance). We agree with your attribution. Cell encodings, counters and restricted selections come from Bergsträßer et al. (Lemma 9, App. A.2–A.3), the value recursion from Yang et al., and the counting and information arguments are classical. New are the whole-record aggregation, the unmasked characterization with polynomial conversions, and the causal bound on the same language. We will say this in the text.

Q1 (the obstacle). There are two. First, the earlier lower-bound method cannot give a second exponential. It relies on a long shortest accepted word. A recognizer with bb state bits accepts some word of length at most 2b2^b, and every UHAT of size ss has an NFA with 22poly(s)2^{2^{\mathrm{poly}(s)}} states (App. C.1), so this method forces at most 2poly(s)2^{\mathrm{poly}(s)} bits. One needs instead a language with 222n2^{2^{2^n}} distinguishable prefixes that still has a recognizer of size poly(n)\mathrm{poly}(n). Second, the recognizer must check "some record agrees at all addresses" in this order. Address-wise lookup gives the reverse order and accepts B1000B0010B1010B_{1000}B_{0010}B_{1010}. (For that weaker condition about 2n+12^{n+1} recurrent bits would suffice, so the quantifier order is also what the lower bound needs.) The new step is that, once every dictionary cell has fetched the query bit at its address, one causal rightmost selection of "latest mismatch or block start" certifies agreement over a whole record, for any number of records and with malformed inputs rejected.

Q2 (why mask order matters). It locates the source of the compactness. DnD_n has no unmasked recognizer (Sec. 4.1), needs size 2Ω(n)2^{\Omega(n)} with causal masks (Cor 4.5), and has size poly(n)\mathrm{poly}(n) with mixed masks. The order matters too: causal retrievals followed by unmasked ones never cost more than one exponential (Thm 4.4), so the second exponential requires causal retrievals after the unmasked one.

W3 (exposition). Agreed. We will open with the equal-symbol invariant and the scattered-match example, and move the resource accounting and supporting results after the main argument.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank all four reviewers. A few points recur, so we answer them once here.

What the paper claims. Bergsträßer et al. (2026) showed that causal UHATs can be exponentially more succinct than RNNs. Their LTL translation also implies that replacing a UHAT by an RNN costs at most one exponential for causal masks and at most two for arbitrary masks. We ask whether the mask decides this cost. The answer has three parts.

  1. Without masks the cost is polynomial. An unmasked UHAT sees the whole input, but equal symbols keep equal vectors, so only the first- and last-occurrence orders matter (Thm 4.1).
  2. Mixing masks forces the second exponential. A UHAT of size poly(n)\mathrm{poly}(n) with one unmasked retrieval between causal ones recognizes DnD_n, and every equivalent RNN needs 22n2^{2^n} state bits (Thm 3.2).
  3. On the same language, every causal UHAT has size 2Ω(n)2^{\Omega(n)} (Cor 4.5). So the mask changes the size of the transformer itself, and not only that of its recurrent replacement.

We agree the submission buried the third point under "completing a table".

New and inherited. New: Thm 3.2 (with Prop F.2), Thm 4.1, Cor 4.5. Inherited from Bergsträßer et al.: everything in Prop 4.2. Supporting: Thms 4.3–4.4, which use the value recursion of Yang et al. (2024), and Thm 3.3, which applies a classical information bound. The counting argument behind the lower bound and the two-order word equivalence are classical, and we do not claim them.

Assumptions. The hierarchy is proved for unique hard attention without positional encodings and with exact arithmetic. Two parts do not depend on this. The recurrent lower bound uses only the language DnD_n, so it applies to any one-pass model with finite state. And TnT_n stays correct if positional coordinates are appended to the embeddings, because it can ignore them, so the gap between poly(n)\mathrm{poly}(n) and 22n2^{2^n} on DnD_n is not an artifact of removing positional encodings. The upper bounds (Thm 4.1, Prop 4.2) and the causal lower bound (Cor 4.5) do depend on the model. We have not proved them with positional encodings or softmax attention. We expect a suitable version to hold, but we cannot do this properly within the rebuttal period and prefer not to claim it. We will state it as a limitation.

Presentation. We agree the paper is hard to read. We will define every resource before its first use, mark each result as new or inherited in the introduction and Table 1, move the supporting results out of the main line, and fix the broken reference.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.