The Power of Hard Attention Transformers on Data Sequences: A formal language theoretic perspective

Q: How much of $TC^0$ is covered?

A: Firstly, Barcelo et al. [3] showed that there is an $AC^0$ language over the alphabet {0,1} that is not in UHAT. The same language is also a witness that UHAT over sequences of numbers (i.e. our setting) cannot even recognize some $AC^0$ language.

While it is true that likely not every $TC^0$ language is recognized by a UHAT, we do show in the proof of Prop. 10 that UHAT recognize a $TC^0$-complete language. Thus, the $TC^0$ upper bound is best-possible in terms of complexity classes.

We will clarify this in the paper.

Q: Would the paper also fit at a computer science theory conference?

A: We agree that the paper contains many theoretical results and thus would also be a candidate for a general theory venue. However, virtually all prior work on Formal Languages and Neural Networks (FLaNN) has appeared in ML and NLP venues (ICML, ICLR, ACL, EMNLP, TMLR). In addition, we believe that our results specifically clarify aspects of transformers that are of significant practical interests (see our comments on practical implications in the global rebuttal).

Q: Which logic precisely captures UHAT?

A: This is actually still an open question even for the case of finite alphabets. Barcelo et al. [3] showed that first-order logic (equivalently LTL) with monadic numerical predicates (called LTL(Mon)) is subsumed in UHAT with arbitrary position encodings, i.e., the transformer model that we are generalizing in this paper to sequences of numbers. This does not capture the full UHAT, e.g., palindrome. As remarked in [3], the logic can be extended with arbitrary linear orders on the positions (parameterized by lengths), which can capture palindrome. The same can be done for $(LT)^2L$. However, it is possible to show that the resulting logic is still not general enough to capture the full generality of UHAT.

That said, although our logic does not capture the full UHAT, it can still be used to see at a glance what languages can be recognized by UHAT (see an example in response in global rebuttal).

There could perhaps be a hope of obtaining a precise logical characterization if we restrict the model of UHAT. The recent paper [2] showed that LTL(Mon) captures precisely the languages of masked UHAT with position encodings with finite image. It is interesting to study similar restrictions for UHAT in the case of sequences of numbers.

We will add the above remarks in the paper.

Q: What are the practical implications?

A: See answer in global rebuttal.

Q: Is there a restriction to input lengths up to $n$?

A: We do not restrict the language to sequences of length up to $n$. Instead, the definition of the circuit complexity class $TC^0$ is that there is a family of circuits: namely one circuit for each input length $n$ (with Boolean and majority gates, arbitrary fan-in, bounded depth, and size polynomial in $n$) that recognizes exactly the input strings of that length $n$.

Thus, providing a construction for each input length $n$ is exactly what is required to prove that the entire UHAT language belongs to the class $TC^0$. In particular, the results are shown exactly as stated.

Q: Which results continue to hold in the setting with rational parameters in the UHAT?

A: What we mention in the conclusion is that many of our results not only clarify the setting of real precision in the transformer parameters, but also the case of rational-precision parameters: The $TC^0$ upper bound continues to hold (because rational precision is a restriction). Moreover the $TC^0$ lower bound also still holds, because our lower bound proof (Proposition 10) yields a UHAT with rational parameters. Likewise, the example of non-regularity is already available for rational precision.

Q: Do the same results hold for formal languages over the alphabet $\mathbb{Q}$? If yes, why are the results derived in terms of tuples?

A: Yes, all our main results (Theorems 1,2,3) also hold for languages over the alphabet $\mathbb{Q}$ (in other words, when $d=1$). Let us elaborate on this. This is trivial for the $TC^0$ upper bound in Theorem 1 and for Theorem 3. Moreover, our lower bound results (the non-regular example in Theorem 2, and the non-containment in $AC^0$ in Theorem 1) hold in the case of $d=1$: For the $TC^0$ lower bound (and non-containment in $AC^0$) for UHAT with positional encoding, one can use our result in Section 5 to see that the language of all length-2 sequences $(r,s)$ over $\mathbb{Q}$ with $r>s$ is accepted by a UHAT with positional encoding. The reason we consider the more general case of tuples is two-fold: (1) this is standard in the literature on formal languages expressiveness of UHAT: Each token is encoded by a vector of real numbers, (2) time series in general is a sequence of tuples of numbers (e.g. for stock application, a position in the sequence could be associated with max/min and entry/closing prices for the day, as well as other information like trading volume on that day).

Q: What are the practical implications?

A: See answer in global rebuttal.

Q: The infinite precision of rational numbers can not be represented in real-world systems. Instead, they would be approximated by floating point numbers such that the result of previous work applies.

A: Firstly, our result implies also that UHAT with only floating point numbers in the input is also contained in $TC^0$ and therefore is efficiently parallelizable. Secondly, although we end up with a finite alphabet if we assume a finite set of floating point numbers, this finite alphabet is extremely large ($2^{64}$ or sometimes $2^{128}$ or more in modern computers). Treating them as finite alphabets and using constructions for UHAT over finite alphabets yield extremely large $TC^0$ (in fact $AC^0$) circuits, i.e., of size at least $2^{64}$ or $2^{128}$. This is because the finite-alphabet constructions assume the alphabet size to be constant, meaning the actual size does not impact that complexity analysis. This is analogous to representing boolean circuits/formulas by their lookup tables, or solving games like chess/go by precomputing lookup tables (because there are finitely many configurations), none of which are realistic settings.

Q: What is the role of past masking in the paper?

A: Our paper mostly does not use masking, but instead permits arbitrary position encodings. This follows the classic model of UHAT formalized by Hao et al. [18], and has been used in various papers (e.g. see [3]). We used masking to obtain a stronger bound in the paper (e.g. Theorem 2).

More precisely, masking has been used in several papers because it is a very mild version of position encodings (e.g. in the recent paper [2]). In particular, masking (future/past) can be easily simulated by using arbitrary position encodings. Without masking and position encodings, transformers cannot tell the ordering of the elements in the input sequence [27].

We show in Theorem 2 that UHAT with "very mild position encodings" (namely, past masking) can already recognize non-regular languages. This is in stark contrast to the results over finite alphabets, where UHAT with masking recognize only regular languages.

Q: Why is it important to have rational inputs, but real parameters?

A: The use of rational numbers in the input sequence is standard when studying symbolic computation involving reals because (1) they can represent, among others, real numbers with finite precision, and (2) we cannot represent all real numbers by finite means.

We use real parameters in the specification of transformers (e.g. in the position encodings, in the specification of affine transformations, etc.) for two reasons. Firstly, the purpose of this paper is not to create a new theory from scratch, but rather to extend existing works. In particular, the classic model of UHAT over finite alphabets [18] permits arbitrary real-valued parameters for affine transformations, position encodings, etc. See also the recent survey by Strobl et al. [33]. Such usage of real numbers in the formal model of transformers has been argued by the need of practical applications of transformers that also employ real-valued functions in position encodings like sin/cosine.

Secondly, many of our results (e.g. that UHAT is in $TC^0$ and there is a UHAT for a $TC^0$-hard language) apply also to the more limited setting with only rational parameters.

Q: Why does Appendix A not show that any UHAT for language (2) requires real parameters?

A: The point of Appendix A is not to show that real parameters yield more expressiveness than rational parameters (for this one can argue in a different way, see the next question).

The point of Appendix A is to illustrate the difficulty of obtaining Theorem 1: It demonstrates that proving a $TC^0$ upper bound cannot be done by showing that each real parameter in a UHAT can be replaced by a rational one while preserving recognized input sequences (even those of length 3).

We overcome this difficulty by showing that one can translate the UHAT into a carefully chosen data structure (polynomial constraints with alternation bounds). Here, the key observation is that in polynomial constraints, one can sufficiently approximate all real parameters by rational numbers.

Q: Why are UHAT with real parameters more expressive than UHAT with rational parameters?

A: Here is a simple example: For every real number r, one can easily build a UHAT that recognizes all sequences of length 1 and with d=1 (i.e. every accepted sequence consists of a single rational number) such that a number x is accepted if and only if x>r. This yields a different language for each of the uncountably many choices of r. However, there are only countably many languages with sequence length 1 and d=1 recognized by rational-parameter UHAT (since the set of rational numbers is countable). Thus, there must be a number r for which our real-parameter UHAT has no rational-parameter equivalent.

We are happy to add this to the paper.

Q: One could make exactly the same argument of Appendix A for strings over a finite alphabet.

A: Yes, exactly: The example in Appendix A shows that also for finite alphabets, one cannot sufficiently approximate the real parameters in the UHAT by rational ones.

However, in the finite-alphabet case, this does not add to the difficulty, because there is no need to replace real numbers by rationals at all: Since the alphabet is finite, there is only a finite set of intermediate values. This means, all computations can be made symbolically using a fixed table, because one only needs to distinguish the finitely many possible values.

In other words, yes, Appendix A shows in particular that a naive approach to achieving sufficient precision (which is needed in the infinite-alphabet case) would already fail in the finite-alphabet case (but it is not needed there).

Q: How do you define Boolean circuits with rational vectors as input?

A: The rational vector is encoded as a string, where each rational number is encoded as a pair of binary-encoded integers. We will make this more explicit.

Q: Significance of $AC^0$, regular and $TC^0$ in the context of UHAT over sequences. Practical implications?

A: See answer in global rebuttal.