Many thanks for your nice comments about the paper!

Regarding your question: You are right, there is a small problem with the way in which j_i is defined. The proof, however, works verbatim after a slight modification of the definition of j_i. Please see the modified pdf. Thanks for noticing this!

Many thanks for your comments! We provide answers to your questions below.

Q: In my understanding, in section 2.2 paragraph 2, it is unclear to me why you set T(w) to T(w,v0).

A: We define the acceptance of a language using the content of the first position of the last layer, more specifically, we take a linear function (with values in R) of the value in this position, and we require that this function is positive for words in the language, and negative for words not in the language.

Q: Page 6, "reverses the third coordinate" is not a very precise statement.

A: We meant ``multiplies the third coordinate by (-1)’’. We have restated this (see new version of the pdf).

Q: When is the notion of T(w) >0 (as introduced in section 2.2), used as the criterion in proof on page 6 and page 7. From this proof, I just see that you can perform LTL operations on input strings, but I am not sure how this shows that a string in the language will never be mapped to a string outside the language?

A: We show that for any LTL language, there is a transformer encoder that maps strings from the language to 1 and strings not from the language to 0 (when we look at the first position at the last layer). To satisfy our acceptance criterion, it is enough to make an additional affine position-wise transformation x \mapsto x - ½, which maps 1 to ½ and 0 to -½. We should have added this remark and we, of course, will do that.

Q: Does Kamp's theorem give any bounds on the length of equivalent FO(Mon) equivalent formula in LTL(Mon)?

A: Translations from FO to LTL are non-elementary (which is unavoidable given known results on the satisfiability problem for such logics over finite words). In general, if the quantifier depth of the FO formula A is k, then an equivalent LTL formula is of size k-th exponential on the size of A.

I have read the rebuttal from the authors and comments from other reviewers. I am inclined to keep my score, as I believe the investigated problem is interesting and authors have clarified all the concerns raised by other reviewers. However, through the discussions, clarity of the paper has emerged to be a major concern. I hope that authors will rectify all these concerns for the camera-ready version.

Thanks for your questions. We provide responses below.

Q: In Section 1 Introduction, the paper claims that "the expressive power of transformer encoders has not been fully elucidated to date.". I am curious about that. What do you mean they are not fully elucidated?

A: We mean there is currently no precise characterization of which languages are accepted by different kinds of transformer encoders with infinite precision. We have rephrased this in the pdf to make it more understandable.

Q: I am very confused about the challenges of studying the circuit language. I could not find any information to discuss the existing challenges and related works, which makes it hard to understand the motivation for this work.

A: The question of what can and cannot be expressed by various classes of transformers lies at the heart of the foundation of the area. The works in the past five years (e.g. Hahn (2020) and Hao et al. (2022)) have underlined such an intimate connection between circuit complexity classes and transformer encoders, that results on circuit complexity (e.g. the inability of AC0 circuits to "count", i.e., solve PARITY) have been used to show an inherent limitation of various classes of transformer encoders, prominently Unique Hard Attention Transformers (UHAT) and Average Hard Attention Transformers (AHAT). Despite these, the precise expressivity of transformer encoders belongs to some of the most important open problems in the field, e.g., see Hao et al. (2022), as well as the following new excellent survey that has appeared on arXiv after the submission of our paper:

https://arxiv.org/abs/2311.00208

More precisely, any UHAT (resp. AHAT) transformer was known to be able to be simulated by AC0 (resp. TC0) circuits. Note that AC0 and TC0 are major complexity classes, and after decades of research the expressive power of these circuit classes is understood fairly well. This leads to the open problem of whether any AC0 (resp. TC0) language can also be recognized by UHAT (resp. AHAT). If not, point out which ones, as well as a natural subclasses of AC0 and TC0 languages that can be captured by UHAT and AHAT, respectively.

Q: What are your contributions to this work? I could not find any conclusions about contributions after reading this section, or even the whole manuscript.

A: In relation to our answer to the previous question, our results have significantly improved our understanding of what UHAT and AHAT transformer classes are (in)capable of. We have provided a concrete "counting language" in AC0 and showed that it cannot be recognized by UHAT, consequently UHAT is a strict subclass of AC0. We have also provided a natural subclass of AC0 that can be captured by UHAT, namely, a logical counterpart L of AC0 but restricted to monadic numerical predicates. We have shown similar results as well for AHAT by providing a natural subclass of TC0 (in terms of an extension of L that naturally incorporates counting capabilities of TC0, in particular the majority function) that can be captured by AHAT. As a corollary of these results, we showed that AHAT has an extremely powerful counting capability (e.g. the language of strings of a's, b's, and c's with the same number of occurrences of these letters).

Q: The paper has a very weak introduction to related works, making this work hard to understand and compare.

A: We feel that we have mentioned most of the papers that provide the relevant background for understanding our results, but of course we may have missed some (the area is, in fact, very dynamic). We will revise this for the final version of the paper. The fact that there is now a survey on the topic will definitely be useful for doing this.

Q: I would suggest that an illustration figure be provided to clearly show the main idea of this work.

A: Thanks. We will think about how to implement this idea in the final version of the paper.

Q: Many related works are missing. The paper states that “there has been very little research on identifying logical languages that can be accepted by transformers”. However, with a quick google scholar search, I found the following highly-related papers not cited in the paper. It would be nice to discuss the relation of this paper’s results with these prior works. [1] Merrill, William, Ashish Sabharwal, and Noah A. Smith. "Saturated transformers are constant-depth threshold circuits." Transactions of the Association for Computational Linguistics 10 (2022): 843-856. [2] Merrill, William, and Ashish Sabharwal. "The parallelism tradeoff: Limitations of log-precision transformers." Transactions of the Association for Computational Linguistics 11 (2023): 531-545. [3] Strobl, Lena. "Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits." arXiv preprint arXiv:2308.03212 (2023).

A: Here we were referring to "logical languages", i.e., languages that are defined by means of logical formulas (which do not always have natural circuit complexity classes counterparts, e.g., our FO(Mon) and LTL(+,C)). At the time of writing, the paper by Chiang et al. (2023) was the only example we were aware of, which we mentioned in Related Work. A new article on logical languages accepted by transformers appeared on arXiv last month (after our submission):

Dana Angluin, David Chiang, Andy Yang. Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages. (https://arxiv.org/abs/2310.13897)

An excellent survey also recently appeared on arXiv after the submission of our paper that discusses logical languages accepted by transformers:

https://arxiv.org/abs/2311.00208

We will discuss these in detail in the final version of our paper.

None of [1]-[3] deal with logical languages, but rather connections of different classes of transformers to circuit complexity, like the earlier papers by Hahn (2020) and Hao et al. (2022), which we already discussed in detail in the introduction. [Note also that [3] appears after the submission of our paper, so we could not possibly cite it.] We have added [1]-[3] in the introduction.

Thanks for your comments and questions. We provide responses to them below.

Q: Precision of the number processed by the transformer. The paper does not include any restriction on the precision of the numbers processed by the transformer ...

A: Firstly, we would like to point out that even infinite precision cannot take UHAT outside AC^0, as shown by Hao et al. (2022).

Our current positional encoding needs polynomially many bits of precision. In fact, we have an alternative construction where instead of cosines in the positional encoding we simply use 2^{-i} and 2^{-2i} in the ith position. For our construction we need an attention that, at position i, is strictly smaller for any j < i than for any j >= i, and moreover, which strictly decrease for j = i, i+1, … An example of such attention is -(2^{-i} - 2^{j})^2 which is a bilinear of form in the positional encoding mentioned above. It seems open how to achieve the same result with logarithmically many bits of precision.

Q: No assumptions have been made about the number of transformer layers. Prior work usually assume constant depth or logarithm depth (w.r.t. sequence length). Related to this assumption, it seems that the proof of Proposition 2 constructs a Transformer whose number of layers depends on the form of input LTL. This makes it particularly important to make the correct assumption.

A: Our Transformers are of constant depth wrt the sequence length. You are right that the depth of the transformer that represents a given LTL formula phi depends on the structure of phi. We will make this more explicit in the final version of the paper.

Q: Structure of the model. The model does not include residual connections and only uses single-head attention. Also the ReLU layer only applies ReLU to a single element of the input vector ...

A: We could include these features into the model, but note that this would have made our main result – that transformers accept every language in FO(Mon) – only weaker. This is because we are showing that even without these features transformers can still do that. As for the lower bound (that transformer encoders cannot accept every language in AC^0), it relies on the sensitivity technique of Hahn, which is valid in the case with constant number of attention heads and arbitrary activation and attention functions. In other words, the lower bound is quite robust and does not depend on the technical details of the model.

As for the ReLU – it is true that in practice as activation one uses feed-forward networks, not just application of ReLU to a single element. Still, one might note that in the context of acceptance of formal language it does not matter – both variants just mean that position-wise, we can use arbitrary compositions of affine transformations and max-function.

We agree, however, that it is better to elaborate more on how these assumptions actually look at practice, and we will definitely do that.

Q: The last sentence of the second paragraph of section 2.2 makes no sense. f is a function from Sig -> R^d, T: Sig^+ -> R et the last sentence says that T get an input sequence that type as a sequence of vectors of R"e ...

A: In our view, the main point of confusion arises from the fact that we are abusing notation and using T to denote both the transformer, which transforms sequences of vectors in R^d to sequences of vectors in R^e, and the function that given a word \bar w outputs a real number based on T. We have modified this and updated the pdf accordingly. Regarding your comment that the value of T(w) only depends on t and v0: please notice that v0 is not f(a_0) + p(0, n), but the first vector in the output of T when presented with the input f(a_0) + p(0, n), …, f(a_n) + p(n,n). We believe there is no mistake in this case.

Q: About your open question: Additionally, does there exist a language in the circuit complexity class TC0, the extension of AC0 with majority gates, that cannot be recognized by AHATs: I would go for Dyck language. Sounds hard for a AHATs.

A: Thanks for the suggestion! In fact, [Yao et al. 2021] show that Dyck languages (even with more than one type of brackets) can be accepted by a transformer with soft attention. But they are actually using only uniform weights, which can also be done in AHAT. That being said, they are also using layer normalization. It seems unknown whether Dyck with more than one type of brackets can be done by AHATs without layer normalization.

Many thanks for your valuable comments. They will definitely help in improving the paper. We respond to your questions next.

Q: While it is rather clear that computation performed by UHAT can be computed in AC0 when restricted to rational numbers, it is much less clear when going within rational numbers ...

A: Thank you for noticing, we should have made it more explicit. Actually, the paper by Hao et al. (2022) shows that even a more general model they call GUHAT, where arbitrary attention and activation functions over an arbitrary set of values are allowed, can be simulated efficiently in AC^0. This model subsumes UHAT with real numbers.

Q: About Proposition 1. I believe a much simpler argument can be used using a simple padding argument: AC^0 recognized all languages up to exponential padding ...

A: We actually considered this idea, but we do not see how to finish this argument. The problem is that actually information propagates substantially between vectors through the maximization of attention score. Another informal argument, why the situation is not that simple with this approach is that such an information-based argument should also apply to a more general model GUHAT considered in Hao et al. (2022). However, it is not hard to see that if the input contains only log n substantial variables, then we can compute the standard DNF within GUHAT: just compute all possible ANDs of literals on the first layer (one entry in the layer can compute one AND) and compute OR of them on the second layer. Of course, this does not work if we have a function with 2 log n substantial variables, since there are too many ANDs now. But it seems that a simple information theoretic argument should not be affected by the constant in front of the logarithm.

Q: Logic with counting operators has been introduced in the past (Majority logic) and a study of its expressivity with respect to circuit classes. See for instance (https://link.springer.com/chapter/10.1007/978-3-642-02737-6_7) Is there a connection?

A: It is difficult to try to establish a precise connection between our counting LTL and the numerous extensions of FO with counting that have been proposed in the literature. This is because very few extensions of Kamp’s theorem have been obtained for counting logics (the only one we are aware is given in the following paper: https://www.sciencedirect.com/science/article/pii/S1571066111001447?ref=pdf_download&fr=RR-2&rr=8268825c5e7f3687). In turn, our logic LTL + counting is subsumed by the infinitary counting logic presented in Chapter 8 of Libkin’s book “Elements of Finite Model Theory”. We do not know whether sensible connections can be established with less powerful logics, such as extensions of FO with majority.

Q: Some of the contribution sounds really artificial to me. In particular, why should we study the commutative closure of language defined by transformers?

A: Two themes have played an important role in understanding the expressive power of transformer encoders: (1) counting, and (2) regular languages. The result by Hao et al. (2022) shows that AHAT cannot recognize some regular language (under a reasonable complexity theoretic assumption). Likewise, Hahn's well-known result that the regular language PARITY is not in UHAT implies the inability of UHAT to "count" the number of 1s in the input string (i.e. eveness or oddness thereof).

Results in our paper on Parikh images (Proposition 5) and permutation-closed languages (Corollary 2) provide a characterization of the expressive power of UHAT and AHAT in expressing counting properties, especially in relation to regular languages.

Parikh-equivalence (i.e. equivalence up to letter permutation) is an established notion in automata theory, whereby a computing device (in our case, transformers) is allowed to try all letter permutations of the input string, and accepts iff some such letter-permutation is accepted. In other words, the "correct" reordering of the letters in the input word will have to be first nondeterministically guessed. Proposition 5 shows the ability of UHAT to capture regular languages (up to Parikh-equivalence), and particularly "counting regular languages" like PARITY can in this technical sense be expressed in UHAT.

The ability to recognize permutation-closed languages is more powerful than Parikh-equivalence, in that the computing device is required to be able to perform the required counting task, regardless of the reordering of the letters in the input string. Corollary 2 shows that AHAT can capture permutation closures of regular languages, and in this way capture languages of strings with the same number of a's, b's, and c's (which is by the way not even regular).