The Power of Hard Attention Transformers on Data Sequences: A formal language theoretic perspective
Authors: Pascal Bergsträßer
Chris Köcher
Anthony Widjaja Lin
Georg Zetzsche
Venue: NeurIPS 2024 poster (2024)
Keywords: Theory
Attention
Circuit complexity
Formal languages
Data Sequences
Expressiveness
Primary area: other
TL;DR: We prove results about the expressiveness of Unique Hard Attention Transformers (UHAT) on sequences of data (i.e. tuples of numbers)

Abstract: Formal language theory has recently been successfully employed to unravel 
    the power of transformer encoders. This setting is primarily applicable in
    Natural Language Processing (NLP), as a token embedding function (where
    a bounded number of tokens is admitted) is first applied before feeding 
    the input to the transformer. 
    On certain kinds of data (e.g. time 
    series), we want our transformers to be able to handle arbitrary
    input sequences of numbers (or tuples thereof) without a priori
    limiting the values of these numbers. In this
    paper, we initiate the study of the expressive power of transformer encoders
    on sequences of data (i.e. tuples of numbers).
    Our results indicate an increase in expressive power of 
    hard attention transformers over data sequences, in stark contrast to the 
    case of strings.
    In particular, we prove that Unique Hard Attention Transformers (UHAT) over 
    inputs as data sequences no longer lie within the circuit complexity 
    class AC0 (even without positional encodings), unlike the case of string
    inputs, 
    but are still within the complexity class TC0 (even with positional
    encodings). Over strings, UHAT without positional encodings capture only
    regular languages. In contrast, we show that over data sequences
    UHAT can capture non-regular properties.
    Finally, we show that UHAT capture languages 
    definable in an extension of linear temporal logic with unary numeric
    predicates and arithmetics.

The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
Pascal Bergsträßer RPTU Kaiserslautem-Landaa 67663 Kaiserslautem, Germany bergstraesserrcc.uui uni-kl.d
Chris Köcher MPI-SWS 67663 Kaiserslauter, Germany ckoecher&mpiissss.ooo
Anthony Widjaja Lin MPI-SWS and RPTU Kaiserslautem-Landaa 67663 Kaiserslautemn, Germany aw sxlin@mpi-sws.oom
Georg Zetzsche MPI-SWS 67663 Kaiserslautem, Germany georgompi-svs.co org
Abstract
Formal language theory has recently been successfully employed to unravel the power of transformer encoders. This setting is primarily applicable in Natural Language Processing (NLP), as a token embedding function (where a bounded number of tokens is admitted) is first applied before feeding the input to the transformer. On certain kinds of data (e.g. time series), we want our transformers to be able to handle arbitrary input sequences of numbers (or tuples thereof) without a priori limiting the values of these numbers. this paper, we initiate the study of the expressive power of transformer encoders sequences of data (i.e. tuples of numbers). Our results indicate an increase in expressive power of hard attention transformers over data sequences, in stark contrast to the case of strings. particular, we prove that Unique Hard Attention Transformers (UHAT) over inputs data sequences no longer lie within the circuit complexity class ACO (even without positional encodings), unlike the case of string inputs, but are still within the complexity class TCO (even with positional encodings). Over strings, UHAT without positional encodings capture only regular languages. In contrast, we show that over data sequences UHAT can capture non-regular properties. Finally, we show that UHAT capture languages definable in an extension of linear temporal logic with unary numeric predicates and arithmetics.
Introduction
Recent years have witnessed the success of transformers [42] in different applications, including natural language processing [12], computer vision [14], speech recognition [13], and time series analysis [45, 46]. In the quest to better understand the ability and limitation of transformers, theoretical investigations have actively been undertaken in the last few years. Among others, formal language theory has been successfully applied reveal deep insights into the expressive power of transformers, e.g., see the recent survey [40] and [2, 3, 8, 15, 20, 21, 30, 32, 38, 39]. In particular, relevant questions pertain the power of various attention mechanisms, boundec/unbounded precision, positional encoding functions, and interplay between encoders and decoders, among many others.
One common assumption in the formal language theoretic approach transformers is that the input sequence ranges over a finite set E (called alphabet), which then to fed into a transformer after applying token embedding function of the form f Σ Rdd. As by-product, the number of tokens is finite. In certain applications (e.g. time series forecasting [28]), we want our transformers to
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

be able to handle arbitrary imput sequences of numbers (or tuples thereof) without a priori limiting the values of these numbers. Moreover, numbers could be compared using arithmetic and (in)equality, which is not the case for elements of alphabets considered in formal language theory. For this reason, we propose to investigate the expressive power of transformers over data sequences, which takes us to the setting of formal language theory over the alphabet Σ = Q for some d E Z,30. e.g., see [4, 11]. That is, what properties of a sequence of (tuples of) numbers can be recognized by transformers?
Connections to circuit complexity. Existing work has revealed intimate connections between transformers and circuit complexity. In particular, let us consider the following class of transformer encoders that has been the main focus of many recent papers: Unique Hard Attention Transformers (UHAT). Among others, UHAT allows arbitrary positional encoding and an attention mechanism that picks a vector at unique minimum position in the sequence that maximizes the attention score. is known that the class of formal languages recognized by UHAT is strict subset of the circuit complexity class AC (cf. [3, 20, 21D, i.e., each UHAT can be simulated by a family of boolean circuits of constant depth. More concretely, this entails among others that UHAT cannot compute the parity (even/oddness) of the number of occurrences of any given letter a in the input string (for strings over an alphabet containing at least two letters).
Our first contribution is that UHAT over data sequences (even without positional encodings) is no longer contained in AC unlike the case of finite number of tokens. Instead, we show that UHAT can be captured by the circuit complexity class TC which extends AC circuits with majority gates.
Theorem 1. UHAT with positional encoding over data sequences is TC but not in AC
This complexity upper bound allows us to deduce the expressive power of UHAT over data sequences by using complexity theory. For example, since UHAT accepts only TC languages, successfully constructing a UHAT (e.g. through learning) for
SQRTSUM: := { (a1 b1), (ans bn))
Σ Va. I
bi, and each (a;, E E x Zoor
would constitute a major breakthrough in complexity theory (ef. [I. 18), i.e., showing that SQRTSUM is in the complexity class TC" S P/poly. A byproduct of our proof is that for each length, the set of accepted sequences is a semialgebraic set. This implies, e.g., that the graph ((x,e") E R) C R.2 of o - et (viewed as set of length-1 sequences) is not accepted by UHAT.
Connection to regular languages over data sequences. Recent results have revealed surprising connections between regular languages and formal languages recognizable by transformer encoders. In particular, it was proven (cf. [2]) that languages recognizable by UHAT (even with no positional encodings) form a strict subset of regular languages, namely those that are "star-free" or, equivalently, definable in First-Order Logic (FO), or Linear Temporal Logic (LTL). With positional encodings. similar connections hold, by extending the logics with unary numerical predicates (cf. [2, 31).
To investigate whether such connections extend to data sequences, bring forth formal languages theory over infinite alphabets (cf., [4, 11]), which has been an active research field in the last decade or so with applications to programming languages and databases (to name few), e.g., see 26, 43). Our second contribution is a language over data sequences recognizable by UHAT without positional encodings that lies beyond existing formal models over infinite alphabets (in particular, "regular" ones). This shows the strength of UHAT over data sequences even without positional encodings, in stark contrast to the case of finite alphabets.
Theorem 2. There is non-regular language over Σ Qd that is accepted by masked UHAT with no positional encoding.
Finally, to better understand languages over data sequences recognizable by UHAT, our third contribution is show how UHAT can recognize languages definable by the so-called Locally Testable LTL LL), which extends LTL with unary numerical predicates and local arithmetic tests for fixed-size windows over the input sequence. Using (LT)²L, we can see at a glance what can be expressed by UHAT over data sequences. For one, this includes the well-known Simple Moving Averages. As another example, using (LT)²L can be easily shown that UHAT can capture linear recurrence sequences considered in the famous Skolem problem and discrete linear dynamical systems [25, 27, 29], i.e., sequences of the form æ. Ax, A such that n 2 0 is minimal with y = 0 where y E Qixd and A E Qdxd are fixed and Qd.

---

Theorem 3. Every L-efnnabe language is accepted by UHAT with positional encoding.
Technical challenges. Obtaining our results poses several challenges. First, for the TC upper bound, we need to use Boolean (constant depth) circuits to simulate UHATs, in which real constants can occur (in affine transformations or positional encodings). While in TC it is known that majority gates can be used perform multiplication of rationals [7], arithmetic with reals requires infinite precision and cannot be done with Boolean circuits. To this end, we compute rational approximations of reals accurate enough to preserve the acceptance condition for inputs up to a particular length n.
Here, a naive attempt would be to replace each real occurring in the UHAT in affine transformations and the positional encoding by some rational approximation. However, this is not possible, meaning any rational approximation would change the behavior on input sequences of length n = 3, even for low-dimensional vectors with entries in {0, 1}. Indeed, there is a UHAT involving real numbers a, that accepts a simple sequence of (0, ( --vectoos if and only if aB3 and a = B, i.e. a 3 22. Thus, a and B cannot be replaced by rationals, even for very short inputs (see Appendix A for details).
Instead, show that UHAT can be translated into small Boolcan combination of polynomial inequalities. This format has the advantage that-as we show using convex geometry- the real coefficients of those polynomials can be replaced by suitably chosen rational numbers. In turn, the layer-by-layer construction of these polynomial inequalities requires a carefully chosen data structure to encode the function computed by a sequence of transformer layers. For example, show that the resulting Boolean combinations of polynomial inequalities have a bound on the number of alternations between conjunctions and disjunctions, which is crucial for constructing TC -iircuiss.
Another key challenge occurs in the translation from ( to UHATs: In the inductive construction, we need to represent truth values using reals in [0, 1]. To implement negation, we use UHAT gadget (with positional encodings) that can normalize these truth values to {0, 1}.
Notation. In the sequel, we assume some background from computational complexity, in particular circuit complexity (see the book [44]). In particular, we use the circuit complexity class AC which defines a class of problems that are computable by nonuniform family of constant-depth boolean circuits, where each gate permits an unbounded fan-in (i.c. arbitrary many inputs). Similarly, the complexity class TC is an extension of AC where majority gates are allowed. It is well- weol-known that AC Ç TC Assuming uniformity, both AC and TC" are contained in the class of problems solvable in polynomial-time. For nonuniformity these classes are contained in the complexity class P/ P/poly, which admits (nonuniform) polynomial-size size circuits. It is long-standing open problem whether numerical analysis (e.g. square-root root-smmm is in P/poly, e.g., see [1].
2 Transformer encoders and their languages
In the following, we adapt the setting of formal language theory (see [3. 21,410) 40)) to data sequences. For a vector a (01,...,,0, (d) we write a ali, = (a.......)) (2)) for all 1 Si j S d and if i = j. we simply write ali]. For a set S we denote the set of (potentially empty) sequences of elements from S by St. We write S+ for the restriction to non-empty sequences. We consider languages L over the infinite alphabet 2 = Q",, for some integer d' > 0. That is, is a set of sequences of d-tuples over rational numbers. We will define UHAT (similarly as in previous papers that study formal language theoretic perspectives) as a length preserving map (Q!")* - (R")".
Standard encoder layer with unique hard attention. A standard encoder layer is defined by three affine transformations A, B: I + Rd and C: 2d - R. For a sequence VI.... Un R with 2 1 we define the atlention vector at position i E [1, as a; := vy with E [1.n] minimal such that the attention score (Av,, Br,) is maximized. The layer outputs the sequence C(e,,a)) ai)..., C(U,,; ).).
ReLU encoder layer. A ReLU layer for some k E [1, d] on input Ui. Un E Rd applies the ReLU function to the ke-th coordinate of each 8ú i.e. it outputs the sequence vy,..., v/, where oa := (v,[1, 1: - 1), max(0, v, [k]) }, Di + n]). [Equivalently, one could instead allow a feed- forward network at the end of an encoder layer (see [3, 21, 40])-]
Transformer encoder. unique hard attention transformer encoder (UHAT) a repeated application of standard encoder layers with unique hard attention and ReLU encoder layers. Clearly, using an
3

---

alternation of standard layers and ReLU layers, we can assume that the output of UHAT layer is an arbitrary composition of affine transformations and component ReLU application. In particular, these compositions may use the functions max and min.
Languages accepted by UHAT'. The notion of "languages" accepted by UHAT (i.e. set of accepted sequences) can be defined, depending on whether positional encoding is permitted. If it is
permitted, language L - (Q++)+ is accepted by UHAT T if and only if there exists a positional encoding function p: N X N + -s and an acceptance vector E Rº such that on every sequence
(p(1, n + 1), v.)........ (p(n, n + 1), vn), (p(n + +1, 1 1),00
(I)
T outputs a sequence 2/ v/.-... 2/+1 E R with vf) 0 if and only if (01....., v..) L. Note that if Ti and T3 are UHATs with positional encoding that realize functions fi: (Q*)* - (Q*)* and f2: (Q*) + (Q")", then there is a UHAT T2 Ti with positional encoding that realizes the composition f2 fi by using a positional encoding that combines the positional encodings of Ti, T2.
In the above definition we appended an additional zero vector to the end of the input. Over finite alphabets it is often assumed that the input sequence is extended with special unique end-of-inpun marker (e.g. see 121, 40)). When the input is a sequence of (tuples of) numbers, if we allow positional encoding, then the zero vector the end of the input can be turned into a unique vector marking the end of the input (see Section 5). Without positional encoding, however, we have to explicitly make the zero vector at the end of the input unique. That is, UHAT without positional encoding is
initialized with the sequence (1, 0i ....... (1, v,), 0 E Qd+11 instead; this ensures, among others, that the end-of-input marker does not appear in the actual input.
In the definition of a standard encoder layer the attention vector at position e [I, can be any vector in the sequence UI...., Vn. Using masking, one can restrict the attention vector to vectors of certain positions. A UHAT with past masking restricts the attention vector a; at position 1 I < n to be contained in the subsequence U,+1;-.., Un and at position a, == Un-
3 UHAT and TC
In this section, we prove Theorem 1, First, we show that all languages of UHAT (even with positional encoding) belong to the class TC Then, we show that there is a UHAT (even without positional encoding) whose language is TC under -edurcccn.. We begin with the proof that all UHAT languages belong to TC
Input encoding A language L C Σ" over finite alphabet E belongs to TC if for every input length n, there is a circuit of size polynomial n. such that the circuit consists of input gates (for each input position i, and each letter Σ, there is a gate that evaluates to "true" if and only if position of the input words carries an a). Boolean gates (computing the AND, OR, or NOT function) and majority gates (evaluating to true if more than half of their input wires carry true). Here, AND, OR, and majority gates can have arbitrary fan-in. In order to define what it means that a language L C (Q4)+ belongs to TC", we need to specify an encoding as finite-alphabet words. To this end, we encode a sequence u1,..-, Un with u, E Qd
string u1 ... Hun. where e; p1 p1/q1 Dpa/pppa/pp qa with Pj. 9j E {-,0, 13". Here, 2/ E / D, 0, 13 represents the vector u, E Qd such that u, b5 by E Z. and Pj. 9 E 0, are the binary expansions of aj and by.
Remark 4. The main challenge in proving Theorem I is that the constants appearing in a UHAT can be real numbers. These can in general not be avoided: There are UHAT languages over Σ = Q (even without positional encoding) that cannot be accepted by UHAT with rational constants (even with positional encoding). For example, for every real numberr r >> O, one can' construct a UHAT for the language I., of all sequences over = Q where the first letter is >> r. Note that L,, * I., for any 8 >> 0, r + s. However, there are clearly only countably many languages over Σ = Q accepted by UHAT with rational constants where membership only depends on the first letter". Thus, there are uncountably many real 0 such that L, is not accepted by UHAT with rational constants.
FFirst, use standard encoding layer transform the sequence (æ1 T..) _ into (r-
1, J...,," - 1) " Then, accept if and only the left-most vector is > 0. "This is because all employed affine transformations (which are rational matrices), but also the values 2) E Q of the positional encoding can be described using finitely many bits.

---

The construction of TC circuits comprises three steps. In Step I, we show that the set of accepted length-n sequences can be represented by a Boolean combination of polynomial inequalities. Impor- tantly, (i) this representation, called "polynomial constraints" is polynomial-sized in n, and (ii) the number of alternations between conjunction and disjunction is bounded (i.e. independent of n). The polynomials in this representations can still contain real coefficients. In Step II, we show that if we restrict the input not only to length-n sequences, but to rational numbers of size S m, then we can replace all real coefficients of our polynomials by rationals of size polynomial in m and n, without changing the language (among vectors of size I m). In Step III, we implement TC circuit. Here, it important that the number of alternations between conjunctions and disjunctions in our polynomial constraints is bounded, because the depth of the circuit is proportional to this number of alternations.
Step I: UHAT as polynomials We first consider formalism describe set of sequences over Q We consider such sequences (211..... Fn,) of length n, where 2; E Q for each i. In this case, we also abbreviate
(......,, Fn.. A polynomial constraint (PC) is positive Boolean combination (i.e., without negation) of constraints of the form p(æ) > 0 or p(z) 2 0, where p E R[ Xaml is a polynomial with real coefficients. Here, plugging æ E (Q")) n into p is defined by assigning the d rational numbers in ē to the d n variables X1..... $1..... Xd-n- The PC accepts sequence of vectors & E (Q")), if the Boolean formula evaluates to true when plugging T into the polynomials p in a. The set of accepted sequences is denoted by [o.] Now let a E N. A PC has a alternations if the positive Boolean combination has a alternations between disjunctions and conjunctions.
In the following, constrained polynomial representation (CPR) can be used to compute from se- quence of inputs (æI,.... Fnn with .1,..., Fn Rdd a new sequence of outputs (y1..... vn.) with y/, y1...... Yn E Idd Formally, a CPR comprises for each E {l...., n2 a sequence (f91 D1)..... (Ps,, Dx.)) of pairs (ej, Dý), where each pair (4y,, D2) is a "conditional assignment": each (f), Dj) tells us that if the condition Sjj is satisfied, then we return Dz More precisely: (i) each ,9 a polynomial constraint where all polynomials have degree S 2, (ii) for any j + m, the constraints yo and pm are mutually exclusive, and (iii) each Dy: IR-'-2 - Rd is an affine transformation. Because of their role as conditional assignments, we also write 42 + + D, for such pairs. For a E N, we say that the CPR is innterraationbbbunde if each of the formulas (2 has at most alternations. A CPR as above computes function Rd''- - Rdd, Given ē (#1,.... ..,) with æ1;-.. Tn Rdd, it computes the sequence (y1,..., yn if for every i [1,...,m], y: = Dā))), provided that j is the (in case of existence uniquely determined) index for which 4 (Φ) satisfied. The size of PCs and CPRs are their bit lengths (see Appendix for details).
n), we have
Proposition 5. Fix UHAT with positional encoding and & layers. For any given sequence length n. there exists a polynomial-sized PC with (()) alternations such that [o]] equals the set of accepted sequences length n.
Note that Proposition implies that the set of sequences of each length n is semialgebraic set [31]. The proof is by induction on the number of layers, which requires slight strengthening:
Lemma 6. Fix UHAT with positional encoding and E layers. For any given sequence length one can construct in polynomial time an O ((l))aaltenatton-bbuuu [dd-(++1) + Re-(n+1) computed by the UHAT.
CPR computing the function
Proof. We prove the statement by induction on the number of layers. First, we consider the positional encoding p: N x N + Rd as some affine transformations P.: (d((1))) - Rd mapping the input sequence & to az; + p(i, n + 1). Then we obtain a CPR with - P. for each 1 S < n + 1. Now, suppose the statement is shown for E layers and consider a UHAT with f+ layers. Suppose that the first é layers of our UHAT compute function (n+1)) computes a function Rd (x++1) + (=+(++)), By induction, we have polynomial size CPR consisting of conditional assignments spi, > Dr,e for every i E (I,..., + 1} and S S 8,. Here, each Da, is an affine transformation IR' (n+11 + Rd.
[dd(++1), and the last layer
Let us first consider the case that the last layer of our UHAT is a standard encoder layer. For each (i, (,I,J,J) E (l,..., n + 134, we build the conditional assignment using the formula $s.r.j.7 j-1
V M=1
5m
Pm, A J.m. (0) >0) A
(1)
n+1
A
V
8m
Pm. A (z) 2
m=1
m=j+1
M=1
5

---

where J.m.J.J.m..M ( is the polynomial (A,,, BD - BDm..rr Then, the conditional assignment is Pi.r A Pp.J A VL..j.JJ - r ) Here. the idea is that (i) Pi, expresses that the I-th conditional assignment was used to produce the i-th cell in the previous layer, (ii) Pj.J says the J-th conditional assignment was used to produce the j-th vector in the previous layer, and (iii) P.J.. says the vector æ; yields the maximal attention score for the input a;, meaning (iii-a) for all positions m < j. 3m has a lower score than 3j (left parenthesis), and (iii-b) for all positions m > J. 2m has at most the score of T (right parenthesis), In (iii-) and (iiib), we first find the index M of the conditional assignment used to produce the mnth cell in the previous layer. Note that then indeed, all the PCs tr.,,j.1 1 are mutually exclusive. Moreover, the polynomials a BD i=- - BDm 2) have indeed degree 2 and are of size polynomial in n. Furthermore, if the assignments A + Da,: had at most a alternations, then the new assignments have at most a + 3 alternations. Finally, the case of ReI.U layers is straightforward (see Appendix B).
Finally, the proof of Proposition 5 is straightforward: from the constructed CPR in Lemma 6 we obtain the polynomial constraint V PP,, (t, Di, > 0 with bounded number of alternations.
Step II: Replace real coefficients by rationals In our proof, the key step is to replace the real coefficients in the PC by rational coefficients so that the rational PC will define the same set of rational sequences, up to some given size. Let us make this precise. We denote by Qçm = {a E Q ||a||2 S m] ) the set of all rational numbers of size at most m. A polynomial constraint is rational all the polynomials occurring in it have rational coefficients.
Proposition 7. For every m E N and every PC a with polynomials having n variables, there exists a rational PC a' of polynomial size such that [o]] 2 [[a'] [
Proving Proposition 7 requires the following technical lemma, for which we introduce some notation. For two vectors u, v E RC and m E N, we write u ~'m v for every w E Q' and every 2 E Q with || I1, ||=I|2 S m, we have (i) (wn, u) 2 z if and only if (w, v) 2 and (ii) (w, u) > z if and only if (w, v) > z. In other words, we have u mm v if and only if u and w satisfy exactly the same inequalities with rational coefficients of size at most m.
Lemma 8. For every e RC and m E N. there a c' E Q' with ||c'll2 S (mt))(11) and C mm C' Remark 9. For proving Lemma 8, it is not sufficient to pick rational c with ||c' cll < e for some small enough e. For example, note that if in some coordinate, e contains a rational number of size I m, then in this coordinate, c' and must agree exactly for ~m c' to hold.
Before we prove Lemma 8, let us see how to deduce Proposition 7: in PC a we understand each polynomial p(X)...., xx,) as a scalar product (w, u) where w constains only variables and u consists of all coefficients. Then Lemma 8 yields a vector ~2mm u containing only rationals with the same behavior as u. From this we finally obtain polynomials having only rational coefficients, which also proves Proposition 7. A detailed proof of Proposition 7 can be found in Appendix B.
In the proof of Lemma 8, we the following fact about solution sizes systems of inequalities. Lemma 10. Let A E Q A' @fx", Q2 x' E Qf with ||A]22 ||A' || || m. If the inequalities Ax >0 z and A'x: 2 z' have a solution in RD, then they have a solution r E Q" with |r||a (m1))01))
We prove Lemma 10 in the appendix. The proof idea is the following. By standard results about polyhedra, the set of vectors æ satisfying Ax 2 z and A'x 2 z' can be written as the convex hull of some finite set X fø1...... I. plus the cone generated by some finite set f. yt.. Here, the vectors in X YUY Y are all rational and of polynomial size. By the Carathéodory Theorem, the real solution& $ E I=" to As > 2 and A's s 2 z' belongs to the convex hull of n elements of X, plus a conic combination of n elements of Y. We then argue that by taking the barycenter of those n elements of X, plus the sum of the n elements of Y gives rational vector E Q" with Ar >> z and A'r 2 z'. The full proof of Lemma 10 in Appendix B.4. To prove Lemma 8, given e E TR. we set up system of (exponentially many) inequalities of polynomial size so that the solutions the vectors d with d ~m c. The solution provided by Lemma 10 is the desired (see Appendix B.5).
exactly
Step III: Constructing TC circuits is now straightforward to translate polynomial-sized CPR with rational coefficients and bounded alternations into TC" circuit:

---

Proposition 11. Every language accepted by a UHAT with positional encoding is recognized by family of circuits in TC
We now show that the TC" upper bound is tight: There is a UHAT whose language is TC -hard under AC reductions. In particular, this language is not in AC since AC is strictly included in TC".
Proposition 12. There is a TC -complete language that is accepted by a UHAT, even without positional encoding and masking, but is not recognized by any family of circuits in AC
Proof. As shown by Buss [6, Corollary 3], the problem of deciding whether ab = for given binary encoded integers a, b, c E E is TC -complee under AC -reductions. Since ab = if and only if ab > c 1 and -a > - (c + 1). the problem of deciding ab > c is also TC -complete.. We exibit a UHAT such that the problem of deciding ab > c can be AC -reduced to membership in the language.
It suffices to define UHAT T that accepts language L S (Q²)+ such that for all r, E Q we have that (r,s) 8) E I. if and only if > s. Then we can reduce the test ab > e to checking whether (a, }) E L. Note that formally, 5 is represented as string containing the binary encodings of c and b separated by a special symbol. The UHAT
by definition initialized with the sequence (I, s)), (0, 0,0) Q2 since only have to consider the accepted language restricted to sequences of length 1. It can directly check that r 8 > 0 using the acceptance vector := (0,1,-1)
UHAT and regular languages over infinite alphabets
It was shown by Angluin et al. [2] that UHATs with no positional encoding on binary input strings accept only regular languages, even if masking is allowed. We show that UHATs with masking over data sequences
recognize "non-regular" languages over infinite alphabet (Theorem 2). More precisely, a standard notion of regularity over the alphabet Σ = Q is that of symbolic automata (see the CACM article [1]]), since extends and shares all nice closure and algorithmic properties of finite automata over finite alphabets, while at the same time permitting arithmetics. Intuitively, a transition rule in symbolic automaton is of the form p + 4- where yp represents the (potentially infinite) set S C Qdd of solutions to arithmetic constraint yp (e.g. 2x = y represents {(n, 2n) meaning of such a transition rule is: move from state p to state by reading any a E S.
Q}). The
To prove Theorem 2, we define the language
Double == ((ri...., rw.) E Q" 2 and 2r, < ri+1 for all 1 S < n}
of sequences of rational numbers where each number is more than double the preceding number. Lemma 13. UHAT with past masking and without positional encoding can recognize Double.
Proof. Given an input sequence U1,.... Un+1 = (1, rn), (0, 0) E Q2, we need to check that for all pairs 1 < i < j < n + 1, we have 2 r. < T3. To this end, first standard encoder layer uses the differences 2r; - Ty as attention scores except for = n + 1, where the attention score will scores-cceepl
be O. This is achieved by setting the attention score for positions i,j to 2u, u, [1] -u, 12] Indeed, this evaluates to 2r; - ry for j < n + 1, and to 0 for < j = n + 1. In particular, for a position i (1, n). the attention score is maximized at
1 if and only if 2r; < ry for all
ii + 1, n).
The output vector v; at position is then set to a, [1]. where a; is the attention vector at position i. Thus, the output vector has dimension 1, and for each i E [1, n + 1]. we have v, 0 if and only if 2 rv- <r holds for all j E [,,].
In second standard encoder layer we now check whether all v; have value 0. To this end, we choose for i <j j S n + 1 the attention score Uj. Let b, denote the attention vector at position i. Then b. = 0 iff U.+1...., u, are all 0. We then output wi = 1 (v; + b.), which is positive if and only if 0; = =.. Un+1 0. Finally, with the acceptance vector t we accept if and only Unt1 0. As we saw above, the latter holds if and only 2r; < ry for all i.j with 1 < <i<j <
> 0, which is equivalent to
The proof of regulagyy of Double is easy (see Appendix C). One could also easily show that Double cannot be recognized by other existing models in the literature of formal language theory over infinite alphabets, c.g., register automata [4, 9, 24, 36, 41], variable/parametricc automata [16, 19, 23],
7

---

and data automata variants [5, 17]. For example, for register automata over (Q: <) (see the book [4]), one could use the result therein that data sequences accepted by such an automaton are closed under any order-preserving map of the elements in the sequence (e.g., if 1, 2, 3 is accepted, then so is 10, 20), which is not satisfied by Double.
Logical languages accepted by UHAT
In this section we show that an extension of linear temporal logic (LTT.) with linear rational arithmetic (LRA) and unary numerical predicates is expressible in UHAT over data sequences (Theorem 3). A formula of dimension d > 0 in locally testable LTL (LLT)L) has the following syntax:
:== (.i............................. xb+1) | up V
Xyp ppUpp
Here, the for k 2 0 is an atom in LRA over the d-dimensional vectors of variables æ; of the form where a E Q(((++1) and b E Q. Intuitively, 4h allows one to check the values in the sequence with & "lookaheads". Furthermore, Q is unary numerical predicate, ie. a family of functions 0, [l.....n] + {0,1} } for all n 2 We define the satisfaction of an LLT)?L formula y over a sequence ö = (#1.... 2, of vectors in Q position E [1, n], written (ū, i) | sp inductively as follows (omitting negation and disjunction):
(a, (#1..... xk+1)) +
(0,t) F (x Tb+1) iff S and th (U...... mitk)
(6, F θ iff (1) =1
. (0,1) F X iff i < and (Ø, 1) +
(6,1) F u iff there j E [2, n] with (ū, } to and (Ø, k) F so for all le E [ 1]
We write T(p):= = (w (Q4)+ (6, for the language of sp.
Example 14. Consider sequences of the form x, Ax, A²xr,..., A" such that A and
n 2 O is minimal with this property where y E Qiiid and A E Tyxx are fixed and a E Qá. Theorem 3 implies that this language is accepted by a UHAT since it is defined by the L.
G[(- + (yæ1 # 0 A Ax = x2)) A (Last + yo = 0)]. where Last := -XT.
Example 15. Take the standard notion of 7-day Simple Moving Average (7-SMA); this can be generalized to larger sliding windows of 50-days, or 100 days, which are often used in finance. Using (LT L, is easy to show that the following notion of "uptrend" can be captured using UHAT: sequences of numbers such that the value at each time t is greater than the 7-SMA value time t. The formula for this is:
G(X"T + >(((1....,,
where ((() is the formula 7x, > Ei= Z4. Note here that G1 means (as usual for LTL) "globally" db. which can be written as -TU--L). Similarly, X3 means that X is repeated times.
We assume UHATs with positional encoding and a zero vector at the end of the input sequence (see Section 2). In the following we always assume that the components from the positional encoding are implicitly given and are not changed by any UHAT. So we write the sequence in Eq. (1) as 01...., Un, O. We use the following results from [3] that also hold for UHAT's over data sequences. Lemma 16. Let d > 0 and e [1.d]
1) For every E 10 there is a UHAT with positional encoding that on every se- quence 01 o1...., Un Qd with c.[d] E (0,1) for all [1,n] outputs the sequence U,...., Dn.,, (1, - 11,b, v. 1,
2) There UHAT layer with positional encoding that every sequence v1,..., Un Q and for every E [1,n n 1) picks attention vector a, = 0/+1-
3) There is a UHAT layer with positional encoding that on every sequence ...... E Qd.. for every & [1, d) with v [0]..... [[).....;,-11. {0, 1) and v,[ 0, and for every E [1,m] picks attention vector a; Uj with minimal j E [ē, n) such that v, = =0.
Here, 2) and 3) directly follow from [3]. For 1) we remark that in [3] only the case b is shown. On input U....., Un as in 1), the UHAT uses positional encoding function p(i,n) n) = (i,

---

and a composition of affine transformations and ReLU to output at position E [1. [1.n] the vector [v, f b,, u, 1.)) where b, := min(v,[4], n i} if 6 and b, := max v [e] - n n+11
b ===1 1.
Using Lemma 16, we show that UHAT can transform rational values > 0 and values S 0 0. This will be used to evaluate incqualities by outputting for true and 0 for false.
Lemma 17. Let d 0 and E E [L. [L. There is a UHAT with positional encoding that on every sequence U1..... Un+1 E Qd outputs v' .i...... V2+1 E Q with ot := (v:[1, - 11, bis vile + 1, d.) for all i E [1, n + 1] where b; :- 1 v; > 0 and b; == 0 otherwise.
Proof. On input vi,.... 1n E Q² the first layer outputs at position i E [I. + 1] the vector w, == (e, L 1), ri, 0z(e + 1, d)) where r; == max [,(0),0 0}. Thus, r; 0 if 0, and r; > 0 otherwise. The second layer turns the sequence W1, ...... Wx+1 into (0, w)),
(0, 1,+1).
We then apply 1) of Lemma 16 to obtain the sequence (0, wy),.... ..... (0, w,), (1, w,,1), i.e. the last
vector has first component 1, and all other vectors have first component O. Let u uI...., Un+1 E
Qa+1 be the resulting sequence. The final layer uses attention score (Aui, Buy) for all S i,j S n +1 1 where the affine transformations A, B: Qu+1 + Q+++1 yield Au; = (u, 0,..., 0) and Buj= = [1,[1],0 0,...,0) 0). Let a; be the attention vector of position E [1, + 1]. Since
u. 2 0, we have a [1]
if u. [c] = 0 and a.[I] 1 if u.((] > 0. The layer outputs
v. = (u [.]., u, l + 2, d + 1J) at position i E [1, + 1].
We now prove Theorem 3. We claim that for every (L formula yp of dimension d and every m 2 d there exists a UHAT T Tp.m with positional encoding that on every sequence Wi...., wn, 0 E Q outputs a sequence w/...... w', 0 E @=++1 such that for all i E [1, n) we have w m] = w; and wi(m + 1] = 1 if (6, i) F O and w|[m 1] 0 otherwise, where == (w) [1, dl] ..... w,, [1, d)-
Then the theorem follows since for every (L formula yo of dimension d the UHAT p.a outputs on every sequence 5 = (o),.... : Un) of vectors in Q" extended with the vector 0 E Q a sequence
vy...., 2/, 0 E Qd+1 such that v [d + 1] > 0 if and only if (ő, 1) += c. Thus, Tepdd accepts L(p)) by taking the acceptance vector& = (O,.... 0, 1) E Qd+1.
We prove the claim by induction on the structure of L formulas. If the formula is a unary numerical predicate θ, then we can use the positional encoding p(i n + 1) == Oz((1) for all e [1.n] and p(n + 1, n + 1) == 0 to output on every sequence wi....; Wn, 0 E Q the sequence (w),p(L, 1))..... ..... (w,, p(n, n + 1)), (0. + 1, + 1)) E Q
If the formula is an atom (x 1x+1) of the form (a, (I1,.... xk+1)) + b > 0, the UHAT Te.. adds in its first layer component that is set every sequence wi...., Wn, 0 E Q"H the sequence (1, w))...... (1, wn.,, (1, 0). Then we apply 1) of Lemma 16 to turn this sequence into (1, wi),..,, (1, w.) 0. Next, Te uses k layers allow each position to gather the first d + 1 components of its k right neighbors. More precisely, the f-th layer, for é [1, k). on sequence u1,...; Un+1 uses 2) of Lemma 16 to get for every position i E [I.n] the attention vector a; = us+1 and the attention vector an+1 is arbitrary. Note that if é == 1, then a, = O. Then it applies an affine transformation output at position E [I. the vector (a, d + 1], u.) and using 1) at position n + 1 the vector (0, an+1 (2, d + 1], 11) Let ......, un+1 E (d++++)++ 1)+m+1 be the output of the k-th of those layers. We add another layer that using a composition of ReLU and affine functions outputs at every position E [1. + 1] the vector ui : (u, + 1) + 2, k(d d + 1) + m + 11, E Q where r; == min u. [1]. (a. az) + b} and ú; [u, d 1). u. (d + 3, 2(d 1)), u. u: + k + 2, (k- 1)(d+ 1)]),
to the top of every vector, outputting on
which contains the first d components of the initial input vector and its k right neighbors. That is, for all i [L, n| we have that r, = 0 (a, ú.) + 6 < Or + k > n since u, [1] can only be 0 if was gathered from the vector at position n + 1 using attention. Furthermore, r; > 0 if (a, ú.) + 6 > 0 and i k < n. Note that [1, m)] is equal to the input vector w; from the beginning if i E [1, n] and if = n + 1. Finally, we apply Lemma 17 followed by 1) to output at position i E [1, n]] the vector where r 1 if > 0 and r/ := otherwise and at position + 1 the vector wh := (u', (4/_1 11, [1. 0) = O. Thus, for all i E [1. n)] we have that w([m + 1] = 1 if (ö. i) } t/x and w/[m + 1] = 0 otherwise, where = (w) [1, d), .., w. [1, d)).
w : (u/ [m]
Let us now continue with the inductive step where we assume that yp and sb are (LT))1. formulas of dimension d such that for all m 2 d we already showed existence of the UHATs T Tp.m and T Tm.++1

---

For the cases -i VV and X we refer to Appendix D. For ş define the UHAT T p. that first applies T Ty.m+1 o T p.m outputring a sequence ......., U,,, O E Qu++2 Observe that (Ø, i) }= pUrb for i [I,n] and v := [u, .J.... un|l, d)) if and only if for the minimal j [ n] with
(b, -= - V we have (ū.j) F v and such a j exists. Equivalently, for the minimal j E [ n 1]
with min(u, uy [m++11, 1- [m]
Oit holds that uj [ = 1. To check this, we first add a layer
that outputs at position E [1,=+1] 1] the vector ui == ( eu: [m++mm+ 1], -u,(m+ ( 2 E Qm+.
Finally, we add a layer that uses 3) of Lemma 16 to get attention vector a; = un with j E [ n +
minimal such that u/ fm + 3] = 0. The layer then outputs at position i E [1, n + 1] the vector
w/ :- (u/[1, ml] amIm + 2)) Q=+t1.
6 Concluding remarks
We initiated the study of the expressive power of transformers, when the input is a sequence of (tuples of) numbers, which is the setting for applications like time series analysis/forecasting Our results indicate an increased expressiveness of transformers on such input data, in comparison to the previous formal language theoretic setting (see survey [40]), i.e., when token embedding function (with a bounded number of tokens) first applied before feeding the input to a transformer. More precisely, this represents for Unique Hard Attention Transformers (UHAT) a jump from the complexity class AC to TC (since AC C ) and the jump from regular to non-regular languages (when position encoding not allowed). On the positive side, we successfully developed an expressive class of logical languages recognized by UHAT in terms of a logic called locally testable LTL, which extends previously identified logic for UHAT for strings over finite alphabets [2. 3].
Limitations. While we follow the standard formalization of transformer encoders in Formal Lan- guages and Neural Networks (e.g. [3, 20, 21, 40]), limitations of the models are known (see [40] for thorough discussion). For example, used real numbers could be of unbounded precision, which allow one precisely represent values of sin and cos functions (actually used in practice for positional encoding). In addition, the positional encoding used by the model could be uncomputable. Three answers can be given. First, an upper bound complexity on the model with unbounded precision and arbitrary positional encodings (e.g. in TC²) still applies in the case of bounded precision. Second, limiting the power of UHAT (e.g. allow only rational numbers, and assuming efficient (i.e. uniform TC") computability of the positional encoding p : N x N + Q(),, our proof in fact yields uniformity of our TC" upper bound. Third, our lower bound for non-regularity of UHAT (cf. Theorem 2) holds even with only rational numbers and no positional encodings. Finally, to alleviate these issues, we have always made an explicit distinction between UHAT with and without positional encodings.
Future directions. Our paper opens up a plethora of research avenues on the expressive power of transformers on data sequences. In particular, one could consider other transformer encoder models that have been considered in the formal language theoretic setting to transformers (see the survey [40]. For example, instead of unique hard attention mechanism, we could consider the expressive power of transformers on data sequences using average hard attention mechanism. Similar question could be asked if we use a softmax function instead of a hard attention, which begs the question of which numerical functions could be computed in different circuit complexity classes like TC" Another important question concerns a logical characterization for UHAT over sequences of numbers. 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 (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. There are UHAT languages (e.g. the set of palindromes) that are not captured by this. As remarked in [3]. LTL(Mon) can be extended with arbitrary linear orders on the positions (parameterized by lengths), which then can define the palindromes. [An analogous extension for (LT)²L can detine palindromes over an infinite alphabet.] However, it is possible to show that the resulting logic is still not expressive 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 (e.g. Simple Moving Averages). There could perhaps be hope of obtaining a precise logical characterization if we restrict the model of UHAT. The recent paper [2] showed that LTL((Mo)) 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.
10

---

Funded by the European Union (ERC, LASD, 101089343 and FIN- ABIS, 101077902). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency, Neither the European Union nor the granting authority can be held responsible for them.
Acknowledgments
References
[1] Allender, E., Bürgisser, P., Kjeldgaard-Peddersen, J., and Miltersen, B. (2006). On the complex- ity of numerical analysis. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 331-339, IEEE Computer Society.
[2] Angluin, D., Chiang. D., and Yang, A. (2023). Masked hard-attention transformers and boolean RASP recognize exactly the star-free languages. CoRR, abs/2310.13897,
[3] Barcelo, P., Kozachinskiy. A., Lin, A. W., and Podolskii, V. (2024). Logical languages accepted by transformer encoders with hard attention. In ICLR.
[4] Bojarizzy., M. (2019). Slightly Infinite Sets. See https: https://www.mimux www.w.immw.......mmmm edu.pl/ pl/"bojan up upload/main-10 pdf.
[5] Bojańezyk, M., David, C., Muscholl, A., Schwentick, T., and Segoufin, L. (2011). Two-variable logic on data words. ACM Trans. Comput. Log., 12(4):27:1-27:26.
[6] Buss, S. R. (1992). The graph of multiplication is equivalent to counting. Inf. Process. Lett., 41(4):199-20
[7] Chandra, A. K., Stockmeyer, L., and Vishkin, U. (1984). Constant depth reducibility. SIAM Journal on Computing, 13(2)4233-33.
[8] Chiang, D., Cholak, P., and Pillay, A. (2023). Tighter bounds on the expressivity of transformer encoders. In ICML, volume 202, pages 5544-5562. PMLR.
[9] D' Antoni, L.., Ferreira, T., Sammartino, M., and Silva, A. (2019). Symbolic register automata. In Dillig, and Tasiran, S., editors, Computer Aided Verification 31st International Conference, CAV 2019, New York City, NY, USA, July 15-18, 2019, Proceedings, Part I, volume 11561 of Lecture Notes in Computer Science, pages 3-21. Springer.
[10] D' Antoni, L. and Veanes, M. (2017). The power of symbolic automata and transducers. In Majumdar, R. and Kuncak, V., editors, Computer Aided Verification 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part 1, volume 10426 of Lecture Notes in Computer Science, pages 47-67. Springer.
[11] D'Antoni, L. and Veanes, M. (2021). Automata modulo theories. Commun. ACM, 64(5):86-95.
[12] Devlin, J., Chang. M.. Lee, K., and Toutanova, K. (2019). BERT: pre-training of deep bidi- rectional transformers for language understanding. In Burstein, J., Doran, C., and Solorio, T., editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume (Long and Short Papers), pages 4171-4186. Association for Computational Linguisties.
[13] Dong, L., Xu, S.. and Xu, B. (2018). Speech- traeef-rransformrr A no-recurrence sequence-to- sequence model for speech recognition. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2018, Calgary, AB, Canada, April 15-20, 2018, pages 5884-5888. IEEE.
[14] Dosovitskiy, A.. Beyer, L.. Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, and Houlsby, N. (2021). An image is worth 16x16 words: Transformers for image recognition at scale. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net.
[15] DuSell, B. and Chiang, D. (2024). Stack attention: Improving the ability of transformers to model hierarchical patterns. In Proc. ICLR, Vienna, Austria.

---

[16] Faran, R. and Kupferman, O. (2018), LTL with arithmetic and its applications in reasoning about hierarchical systems. In Barthe, G., Sutcliffe, G., and Veanes, M., editors, LPAR-22. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Awassa, Ethiopia, 16-2/ November 2018, volume 57 of EPiC Series Computing, pages 343-362. EasyChair.
[17] Figueira, D. and Lin, A. W. (2022). Reasoning on data words over numeric domains. In LJCS, pages 37:1-37:13, ACM.
[18] Garey, M. R., Graham, L.,, and Johnson, S. (1976). Some NP-complete geometric problems. In Chandra, A. K., Wotschke, D., Friedman, E. P., and Harrison, M. A., editors, Proceedings of the 8th Annual ACM Symposium on Theory of Computing, May 3-5, 1976, Hershey, Pennsylvania, USA, pages 10-22. ACM.
[19] Grumberg, O., Kupferman, O., and Sheinvald, S. (2010). Variable automata over infinite alphabets. In Dediu, A., Fernau, H., and Martín-Vide C., editors, Language and Automata Theory and Applications, 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings, volume 6031 of Lecture Notes in Computer Science, pages 561-572. Springer.
[20] Hahn, M. (2020). Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput. Linguistics, 8:156-171.
[21] Hao, Y., Angluin, D., and Frank, R. (2022). Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Trans. Assoc. Comput. Linguistics, 10:800- 810.
[22] Hesse, W., Allender, E., and Barrington, D. A. M. (2002). Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci., 65(4))695-776.
[23] Jez, A., Lin, A. W., Markgraf, O., and Rümmer, (2023). Decision procedures for sequence theories. In CAV (2), volume 13965 of Lecture Notes in Computer Science, pages 18-40. Springer.
[24] Kaminski, M. and Francez, N. (1994). minite-memory automata. Theor. Comput. Sci., 134(2):329-363.
[25] Karimov, T., Kelmendi, E., Ouaknine, J., and Worrell, (2022). What's decidable about discrete linear dynamical systems? In Raskin, J., Chatterjee, K., Doyen, L., and Majumdar, R., editors, Principles of Systems Design- Essays Dedicated Thomas A. Henzinger on the Occasion of His 60th Birthday. volume 13660 of Lecture Notes in Computer Science, pages 21-38. Springer.
[26] Libkin, L., Martens, W., and Vrgoc, D. (2016). Querying graphs with data. J. ACM, 63(2):14:1- 14:53.
[27] Lipton, R., Luca, F., Nieuwveld, J., Ouaknine, J., Purser, D., and Worrell, (2022), On the Skolem problem and the Skolem conjecture. In Baier, C. and Fisman, D., editors, LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 5, 2022, pages 5:1-5:9 ACM.
[28] Liu, Y., Hu, T., Zhang, H., Wu, H., Wang, S., Ma, L.,, and Long, M. (2023). itransformer: Inverted transformers are effective for time series forecasting. CoRR, ICLR'24.
To appear
[29] Luca, F., Maynard, J., Noubissie, A., Ouaknine, J., and Worrell, J. (2023). Skolem meets Bateman- Horn. CORR, abs/2308.01
[30] Merrill, W., Sabharwal, A., and Smith, N. A. (2022). Saturated transformers are constant-depth threshold circuits. Trans. Assoc. Comput. Linguistics, 10:843-856.
[31] Mishra, B. (1993). Algorithmic Algebra. Texts and Monographs in Computer Science. Springer.
[32] Pérez, J., Barceló, P., and Marinkovic, J. (2021). Attention turing-complete. Mach. Learn. Res., 12::5..
12

---

[33] Reif, J. H. (1987). On threshold circuits and polynomial computation. In Proceedings of the Second Annual Conference on Structure Complexity Theory, Cornell University, Ithaca, New York, USA, June 16- 19, 1987, pages 118-123. IEEE Computer Society.
[34] Reif, J. H. and Tate, S. R. (1992). On threshold circuits and polynomial computation. SIAM J. Comput., 21(5):896-99)) -088.
[35] Schrijver, A. (1986). Theory of linear and integer programming. John Wiley & Sons.
[36] Segoufin, I.. and Toruńczyk, S. (2011). Automata based verification over linearly ordered data domains. Schwentick. T. and Dür, C., editors, 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12. 2011, Dortmund, Germany, volume 9 of LIPIcs, pages 81-92. Schloss Dagstuhl Leibniz-Zentruu für Informatik.
[37] Sipser, M. (1997). Introduction to the Theory of Computation. PWS Publishing Company.
[38] Strobl, L. (2023). Average-hard attention transformers are constant-depth uniform threshold circuits. CoRR, abs/2308.03212.
[39] Strobl, L., Angluin, D., Chiang, D., Rawski, J., and Sabharwal, A. (2024). Transformers as transducers. CoRR, abs/2404.020400.
[40] Strobl, L., Merrill, W. Weiss, G., Chiang, D., and Angluin, D. (2023). Transformers as recognizers of formal languages: survey on expressivity.
[41] Toruńczyk, S. and Zeume, T. (2022). Register automata with extrema constraints, and an application to two-variable logic. Log. Methods Comput. Sci., 18(1).
[42] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017). Attention all you need. NeuriPS, pages 5998-6008.
[43] Veanes, M., Hooimeijer, P., Livshits, B., Molnar, D., and Björner, N. S. (2012). Symbolic finite state transducers: algorithmss and applications. In Field, J. and Hicks, M., editors, Proceedings of the 39th ACM SIGPLAN-SIGAGE Symposium on Principles of Programming Languages, POPL 2012, Philadelphia, Pennsylvania, USA, January 22-28, 2012, pages 137-150. ACM.
[44] Vollmer, H. (1999). Introduction Circuit Complexity. Springer.
[45] Wen, Q., Zhou, T., Zhang, C., Chen, W., Ma, Z., Yan, J., and Sun, I.. (2023). Transformers in time series: A survey. In IJCAI, pages 6778-67 77776676.. ijeai.org.
[46] Zhou, H., Zhang, S., Peng, J., Zhang, S., Li, Xiong, H., and Zhang, W. (2021). Informer: Beyond efficient transformer for long sequence time-series forecasting. Thirty- AAAI Conference on Artificial Intelligence, AAAI 2021. Thirty-Third Conference Innovative Applica- tions of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 11106-111111 AAAI Press.
13

---

A Example UHAT with real parameters
We present here an example UHAT in which two real numbers a and occur (each occurs once in a matrix associated to a particular layer) such that the simple sequence
(1, O, e1) e2) 0, ez).
(2)
where E R$ is the i-th unit vector, is accepted if and only if og33 = 2 and = 3. This shows that even if we restrict the input sequence to particular number B of bits (e.g. the number of bits to represent the imput sequence Eq. (2)), it is not possible to replace the real constants and & by rational numbers without changing the accepted sequences up to bits: The sequence Eq. (2) is only accepted if a = 3 = v2. And we change a or | in any way, the sequence Eq. (2) will not be accepted anymore.
1. Input layer:
(1. (1),
2. Using a standard encoding layer, we multiply the first component in each position by a. Result:
(a, 0, ea) O, (2, 0,
3. Using attention, we can apply distinct affine transformations to the first three positions. We choose the following affine transformations. The first position unchanged. The second position is mapped to (1, 0, e2), and the third position is mapped to (0, a, ex), using matrix that flips the first and second component. Result:
(a, (1, O, (0,
4. Using standard encoding layer. we multiply the first component in each position with Result:
(a.3, 0, e, (8, O, (2,
5. Finally, by using our result on LL we can build further layers so that we accept if and only if (i) the first component of the first position equals and (ii) the first component of the second position equals the second component of the third position. Thus, we accept our original input if and only if a.3 = 2 and a
B Omitted definitions and proofs in Section 3
B.1 Descriptional size
Let IR be some real number. The (descriptional) size of x is size(x) + [logz(1p] 1)] [log + 1)1 if x = P is a rational number (where and are relatively prime integers) and size(x) = 1 if is an irrational number. Note that in the latter case placeholder, since we do not have to represent irrational numbers in any algorithm. However, for analysis of the sizes in constructions still need some value.
7
the number 1 as some
ua)". Let M E Ruxn be a matrix. The size of M is size(M) mn + Eisism,isiso size(a:)) where
Let Rd be vector. The size of is size(v) + Σi= size(u;) where
M = (an)ssism1//5m
Let A: Rd -, Re be an affine transformation, i.e., we have A(x) Be + e with B E Rdxe and E R Then the size of A is size(A) = size(B) (B) + size(c) + 1.
Now, let P E R[ X,) be polynomial. Then we have p(XI,..., (i,...,,,))
E Cos Sk Grmmna X ... X for some numbers A E N and Gran..r E R. The size of
is
size(p)=
Σ
sine( + size(ri) +... size(ra) + n.
Let a be a polynomial constraint. We define the size a inductively on the structure of the formula as follows:
14

---

if a = (p(X) ~ 0) with ~ E is an atom. Then size(a) = size(p) + 1.
if Aisisk
Visish 8 is formula with PCs 81, ...... BK. then size(a)
k Eisish (i,,)())B.).
Let R = Di)........ (ØR, D2) be a CPR. Then the size of this CPR is Rize(R) = k +
Σx size(d:) + size (iz)
B.2 ReLU case in Lemma
Let consider ReLU layer. Assume that compute the ReLU-value for the j-th component, i.e. we compute max Fiij for each E {l...., + } where æij is the j-th component of
a; From each conditional assignment &i,, - Di,e with E fI,..., l] and 1 I < 8; construct two new conditional assignments:
(e -,, 2 0 + Di, where en is the h-th unit vector.
2. ( (-E(i-1) Dz >
MM Di. where M (mgh ) (gg is the matrix with j and migh 0 otherwise (i.e., M is the unit matrix
myhh if g h + (i - 1)
except for the (i - 1) j-th entry).
Now, if the j-th component æ; non-negative, only the first conditional assignment satisfied and the value of this component is left untouched. Otherwise, the j-th component is negative. But then the second conditional assignment satisfied and the value of this component is set to (while the others stay unchanged). So, obtain again some polynomial sized CPR with the same number of alternations as before.
B.3 Omitted proof's
Proof of Proposition 5. Let t E Re be the acceptance criterion of the UHAT and f: [Rd+(++1)) + (e((+))) be the computed function for inputs of length n. By Lemma 6, we can construct in polynomial time ((t)-alternation-- bounded CPR computing f. So, let Pi, Di, be the conditional assignments in this CPR (for S < n and S S sz). Then we obtain a PC from
this CPR as follows:
P1.J A (1, > 0. J=1
V
Note that this PC has still polynomial size, accepts an input sequence (æ1,..., In, 0) if, and only if, the UHAT accepts (....... ), and - if the CPR is callernation-bouunde then it has at most a + 2 alternations of disjunctions and conjunctions.
Proof of Proposition 7. Consider constraint p(X1.... Xn,) 0 (or 2 0 resp.) in a. Then p E [8[ X,.] polynomial of degree at most i.c., there are real numbers C.j.n, such that
p(X X.n)
Σ
Σ
055+$52 ISiSisn
Now, construct two vectors u and w with a component for each tuple (i, j, r. 8): Ui.j.. = Gijins and w r,j, XTX Then is clear that p(XI,..., X,) (u, w (XI...... Xn)) holds.
Application of Lemma 8 yields vector Q' with ||o|| S (2ml))(1) and ~mm Note that we need to consider rational numbers up to size 2m due to the fact that substitution of the variables w by rational numbers the polynomial obtained from p be replacing the coefficients Ca.j.r,s E R by Vt.j.r Q. Then for each æ E Q we have p(x) = (u, w(x)) > (resp. 2 0) if, and only if, pf (x) = (v. (x)) > (resp. > 0).
Q" yields rational vector w(x) E Q2 Let p'X (Xi,..... Xn) be
Replacing each real polynomial p a by the constructed rational polynomial p/ results in a rational PC a' with [a] n n [a]] Q
D
15

---

B.4 Proof of Lemma 10
The rest of this subsection devoted to proving Lemma 8, for which we rely on results from convex geometry, which requires some terminology. For set S C IR, we define the convex hull of S as
conv.hull S (A181 +
8m m 0, 81, ................................ 8m E S, A A Am E [0,1], A1 + + Am = 1}
and the cone generated by S as
cone S = {1181 + ... + Am
m O, 81
E S, ,
Am 2 0}.
We will also rely Carathéodory's 's theorem, which says that points in cones and convex sets can be obtained from at most n points. See, for example, [35, Theorems 7.1i and 7.1j].
Theorem 18 (Carathéodory's Theorem). Let S C R". For every a E conv.hull there are 21. En S with æ conv.hull (#1...., Ln Moreover, for every y cone S, there are 91 Un E with y E cone (yI....,nnh
potyhedron set of the form {I E R" Ax 2 b), where A E Rm and b E R for some m E N. If the matrix A and the vector b are rational, then the polyhedron is called a rational polyhedron. a standard result about polyhedra that and are rational of size most m, then the polyhedron P = {ær E R Aæ b) can be written as
P kull {x
v.} cone {y1,.... yc),
with rational vectors 21 ...... .. Vn . Vr. where each vector has size polynomial in mn. See, for example, [35, Theorem 10.2].
Proof. We define the matrix B E Q(k+())* and the vector b E QA++ as
A
B
b
A'
and consider the polyhedron P (a: E TR. Ba 2 b). As mentioned above, we can write
P conv.hull {æ1,..... z.} cone fy1.....,y.. 3ee,
where $1...... T. ....... y, are rational vectors of size polynomial in mn. By our assumption, there exists an E R" with As and A's z'. By Carathéodory's Theorem, wlog, belongs to the smaller polyhedron
cone (VI..... -nn) Q conv.hull { ..)
Now note that have Au 2 and A'u z' for every u E U = {I ........ En. 31 ....... Vn We claim that the vector
r [x) + ... x..) + + ... ... yn
satisfies Ar z and A'r 2 z'. Indeed, it clearly belongs Q S P and thus satisfies A'r 2 z'. Moreover, for every row we would would have a Ar > z. Finally, the vector has size at most || 12 +.. ||=.,|12 + |/ +... || which polynomial in mn, since each æ; and each y; has size polynomial in mn.
of Ax > there must be a E U with a 2 zttherwise, z for every E U and thus a T
z. In particular, we have
B.5 Proof of Lemma 8
Proof of Lemma 8. Collect the set of all inequalities (ur, u) > 2 or (w, u.) 2 2 with w E Q and E Q5m that are satisfied for u. This results in two large matrices A E Q kxt mm and A' E Q and vectors Q& and z' Q such that we have ~m if and only if Av > and A'o 2 z Thus, we can construct el using Lemma 10. Observe that the bound from Lemma 10 does not depend on the (exponentially large) k and L.
16

---

Proof of Proposition 11. Let T'' be some UHAT with positional encoding and n. m E N be two natural numbers. In the following, we consider input sequences of ' having the length n and size m. By Propositions 5 and 7 there is polynomial sized, O ((())aateraation-oonl bounded,, and rational PC ar (where& l is the number of layers in 7) such that the set of sequences of size m accepted by the UHAT' T equals [a] n Q
We finally show that the PC a can be realized as a circuit of constant depth and polynomial size. So, consider a constraint of the form p( ~ 0 where ~ E {2,>}, is a polynomial of degree at most 2 and represents the input sequence. Since addition and multiplication of rational numbers are realizable in TC [7], it is clear that the computation of the value p(æ)) is also realizable. Additionally, checking whether this value is 2 0 (or >> 0, resp.) is simple check of the bit representing the signum (and checking that the numerator has at least one non-zero bit).
Finally, we have to connect all the atoms of the form p(z) ~ to the Boolean formula a. Since a alternates only bounded number of times between disjunctions and conjunctions,
can realize the complete formula a in a circuit of constant depth and with polynomial size. Since a is equivalent (up to the input size m), the UHAT 7 is realizable in TC Note that here, we need to perform iterated addition of rational numbers, which requires iterated multiplication of integers represented in binary. The latter is well-known to be possible in TC" [33, 34] (even uniformly [22], but this is not needed in our setting).
C
Proof of non-regularity in Section 4
Recall that
Double == ((r)....,,.)) E Q" In |n 1 and 2r, < ri41 for all iiiii <i<nn n).
We next define the notion of symbolic automata [10, 11, 43]. A symbolic automaton is tuple (Q, ô, go, F',, where Q is finite set of states, Qo E Q is an initial state, F C Q is a set of final states, and 8 is set of transition rules of the form (p, S, q). where S C Q. For a E Q, we write p + q (read "there is a transition from p to reading a) if there is a transition rule (p, S, such that a E S. Slightly abusing notation, for a set S C Q. we also write p - g to mean that (p, S, q) a transition rule in 8. The notion of run, and an accepting run can then be defined in exactly the same way as for finite automata (e.g. see [37]); namely, it is sequence of transitions qu 7a Jan Zn- where 4.. E F, reading the sequence w =
On over Q.
To prove that there is no symbolic automaton recognizing Double, let assume the contrary that such an automaton A exists, say, with n states. Consider a sufficiently long w = a1 ... am E Double (i.e. of length at least ni), and an accepting run of A:
40 S
S. 4m
where each a; E S and Im E F. Since m + 1 > n, by pigeonhole principle, it must be the case that g. 9s for some r < s. Thus, also the sequence
Cr (ar+1 ........... ...)))))) aa,)aaaa..0 2 0mm
is accepted by A and therefore contained in Double. This is a contradiction since Double imposes a. Og.
D Omitted cases in proof of Theorem 3
For mp the UHAT T s.m first applies Tp.m and on the obtained sequence u1.... Un, 0 E @m++ uses further layer followed by 1) to output wt := (u,[1, m), u4 + 1]) at position E [1,m] and 0 E @ at position n 11
For yp we define the UHAT To that first applies TV m T Topm followed by a layer that on sequence u1 u....., Un+1 E Qin-2 outputs w'...., wh++1 E @ with
w = (ui[1, m), (u. + 1], um(m (m + 2]3)
for all i E [1, + 1]. Note that if un+1 = O. then also w/+1 0.
17

---

For Xp the UHAT T. first applies Tp.m to output sequence ui...., un+1 E Q with Un+1 O. With an additional layer that uses 2) get attention vector a; = u for all E [1, n]
then outputs at position E [1, ni the vector w/ == (u; [1, m], a; (m + 1J) and at position n + the
vector w+ = (um+1(1, [1, m), 0) after applying 1).
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
This paper contains theoretical results on the expressive power of transformers data sequences. As standard in theoretical results, we try mathematically formulate the results as as precisely as they can be.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have discussed assumptions made in this paper (e.g., regarding the for- mal model of transformers) and what consequences they have (see Limitations in Concluding Remarks).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "LLiitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
19

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Since this a theory paper, we try to be explicit in all the assumptions that we made for our results. We have also included all the proofs for the claims we made in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper contains experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
20

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper contains no experiments and no code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.c
public/gu des/ Codee//ooduubbiic as
wwtpiimsssssoooooooooooooooooo aasiooooiccy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //niss. cctppcccccc//cccccccccccccccccct guides/
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper contains no experiments.
Guidelines:
The answer means that the paper does not include experiments.
The experimental setting should be presented the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
The paper contains no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
21

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper contains no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:
Appulic/Ethiiie htte:/Ethhiiiiiiie ce@uidelness?
Answer: [Yes]
Justification: This is a theory paper with no reference to human subjects and datasets. Our paper does not have neither direct societal impact nor potential harmful consequences. We have also carefully checked the impact mitigation measures, which do not directly apply to our paper, which involves neither experiments nor code.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: This is theory paper with no direct societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
22

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is theory paper with neither experiments, codes, nor the use of datasets.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This is theory paper that code, data, and models. We do not assets of others in any form.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
23

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi th code. . wwo.coo//aaa/// cattett has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This is theory paper with no crowdsourcing and no human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This is theory paper with no crowdsourcing and no human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "f90sJwJtVp", "reviewer": "Reviewer_iac6", "summary": "This paper studies the expressive power of transformer encoders with leftmost-hard attention and strict past-masking, where the input is not a sequence of symbols from a finite alphabet, but a sequence of rational vectors. The three main results are:\n\n1. Transformers (under the assumptions above, with or without position encodings) are in TC0 but not in AC0.\n2. There is a UHAT that recognizes a non-regular language (that is, cannot be accepted by a finite automaton whose transitions are labeled with arithmetic constraints instead of symbols).\n3. Every language definable in locally testable linear temporal logic (that is, linear temporal logic where an atomic formula can check a linear constraint on the current “symbol” and k lookahead “symbols”) is recognizable by a UHAT with position encoding.", "questions": "Could you explain why it's important for the parameters to be real, not just rational?\n\nHow do you define Boolean circuits that take sequences of rational vectors as input?\n\nCould you expand on the significance, in this setting, of the classes AC0, regular, and TC0? Perhaps it would be helpful to give some examples of languages that do/don’t belong to these classes and expand on the practical implications. You allude to the language at lines 321-324 being important, but don’t explain why.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Theorem 1: This proof (because the transformer weights are real) looks ambitious and interesting, although I was not able to check the details.\n\nTheorem 2: This proof looks correct.\n\nTheorem 3: Although I didn’t check every line of this proof, I definitely agree that the result is correct.", "weaknesses": "Theorem 1: I didn’t exactly understand why the inputs are rational vectors but the parameters are allowed to be real. Appendix A shows why allowing reals makes a difference, but:\n(a) It doesn’t explain why the difference is important.\n(b) It doesn’t show that language (2) requires real parameters, only that a particular UHAT requires real parameters to recognize language (2).\n(c) One could make exactly the same argument about UHATs for strings over a finite alphabet.\n\nWith rational weights, I take it Proposition 9 would be fairly easy.\n\nHow do you define Boolean circuits that take sequences of rational vectors as input? This is hinted at in line 273 but should be spelled out more explicitly for Proposition 10 and its proof to be clear.\n\nTheorem 2: I think it would be helpful not to reuse variable names.\n\nTheorem 3: Just a minor comment on the phrase “logical language” in the title of Section 5. I understand a “logical language” to be the syntax of a logic, not the set of strings models of a logical sentence, so I find this phrase confusing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q: What is the role of past masking in the paper?**\n\nA: 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).\n\nMore 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]. \n\nWe 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.\n\n**Q: Why is it important to have rational inputs, but real parameters?**\n\nA: 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. \n\nWe 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. \n\nSecondly, 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.\n\n**Q: Why does Appendix A not show that any UHAT for language (2) requires real parameters?**\n\nA: 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).\n\nThe 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).\n\nWe 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.\n\n**Q: Why are UHAT with real parameters more expressive than UHAT with rational parameters?**\n\nA: 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.\n\nWe are happy to add this to the paper.\n\n**Q: One could make exactly the same argument of Appendix A for strings over a finite alphabet.**\n\nA: 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.\n\nHowever, 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.\n\nIn 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).\n\n\n**Q: How do you define Boolean circuits with rational vectors as input?**\n\nA: The rational vector is encoded as a string, where each rational number is\nencoded as a pair of binary-encoded integers. We will make this more explicit.\n\n **Q: Significance of $AC^0$, regular and $TC^0$ in the context of UHAT over sequences. Practical implications?**\n\nA: See answer in global rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y3ImwPes8a", "reviewer": "Reviewer_exed", "summary": "The paper studies the computational expressiveness of unique hard attention transformers (UHAT) on formal languages formed over an infinite alphabet. The work is motivated by the application of transformers to time series forecasting where input values can be unbounded. Specifically, the authors assume the language to be formed over tuples of rational numbers. To this end, the paper contributes three novel results: (1) The languages recognized by UHAT belong to the circuit complexity class $\\mathsf{TC}^0$ and there exists a language recognized by UHAT which is $\\mathsf{TC}^0$-hard. (2) There exists a non-regular language over the alphabet $\\mathbb{Q}^d$ that is recognized by a UHAT with past masking and no positional encoding. (3) UHAT with positional encoding recognize all languages expressible in an extension linear-time temporal logic with unary numerical predicates and linear rational arithmetic.", "questions": "Do the same results hold for formal languages over the alphabet $\\mathbb{Q}$? If yes, why are the results derived in terms of tuples?", "limitations": "The authors have addressed limitations adequately, except for the real precision of UHAT. As detailed in the review it seems that some results only hold for inputs up to a particular length n. The theorems themselves do not state this.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- To the best of my knowledge, the paper is the first to connect the formal language theory over infinite alphabets with the computation expressiveness of transformers. For unique hard attention transformers, a comprehensive set of results is established.\n- The paper's results are particularly interesting in the light of existing results for finite alphabets. For finite alphabets, the languages accepted by UHAT are contained in $\\mathsf{AC}^0$ and are exactly the star-free regular languages when masking is applied. Therefore the results provide insights into the increase in computational expressiveness due to an infinite alphabet.\n- The paper’s technical claims are well presented. For each claim, either a full proof or a proof sketch with references to a full proof in the appendix is provided.\n- Although the paper is densely written the contributions are clear and the paper is easy to navigate.", "weaknesses": "- There seems to be an important restriction to the first result: because real precision is assumed for UHAT, language inclusion can only be shown for words up to a particular length n. I assume that without this restriction the two classes are actually incomparable. At the same time, the authors seem to suggest in the concluding remarks that some results still hold when assuming rational precision for UHAT. The importance and implications of this choice should be discussed more clearly in the paper.\n- The paper does not clearly convey the practical implications of the results. 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.\n- Minor: It would be helpful if the abstract already states that arbitrary input refers to the rational numbers, to avoid confusion with a real-valued input.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q: Is there a restriction to input lengths up to $n$?**\n\nA: 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$.\n\nThus, 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. \n\n**Q: Which results continue to hold in the setting with rational parameters in the UHAT?**\n\nA: What we mention in the conclusion is that many of our results not only clarify the\nsetting 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\nis a restriction). Moreover the $TC^0$ lower bound also still holds, because our\nlower bound proof (Proposition 10) yields a UHAT with rational parameters.\nLikewise, the example of non-regularity is already available for rational\nprecision.\n\n**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?**\n\nA: 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.\nThe 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).\n\n**Q: What are the practical implications?**\n\nA: See answer in global rebuttal.\n\n**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.**\n\nA: 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "khfWWfkbjE", "reviewer": "Reviewer_TvTa", "summary": "This paper focuses on analyzing the expressive power of transformers through the lens of formal languages, inspired by Angluin's approach. Specifically, while traditional unique hard attention transformers (UHAT) on strings are associated with $AC^0$ and regular languages definable in first-order logic, the authors here explore the implications of using data sequences instead of words as input. The main findings are:\n- UHATs over data sequences with positional encodings fall within $TC^0$, not $AC^0$.\n- Non-regular languages can be recognized even by masked UHATs without positional encodings.\n- UHATs can recognize all languages definable in $(LT^2)L$, an extension of LTL with unary predicates and local arithmetic tests over finite windows over the data.", "questions": "Please comment on **W1** and **W3**.", "limitations": "This has been addressed in a satisfactory way by the authors.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**S1: Important Contribution**\nUnderstanding the expressive power of significant classes of transformers is crucial, given their widespread popularity. Moreover, considering data sequences is a natural and worthwhile extension. The results obtained are both elegant and insightful.\n\n**S2: Clarity**\nFor readers familiar with the topic, this is a well-written paper. The authors effectively set the stage and explain most concepts and proof ideas in sufficient detail within the main text.\n\n**S3: Elegant Proofs**\nThe results linking UHAT with $TC^0$ involve a well-crafted stepwise reduction using polynomial equations and polyhedral analysis.", "weaknesses": "**W1: Coverage of $TC^0$**\nWhile the characterization of UHAT on data sequences in $TC^0$ is commendable, it does not fully encompass $TC^0$. A precise characterization of the power of UHATs would strengthen the paper. This observation also applies to the other main results: Which logic precisely captures UHAT?\n\n**W2: Accessibility**\nThe authors make little effort to make the paper accessible to the broader ML community. As it stands, the paper could have been submitted to any computer science theory conference. Consequently, the results may not be surprising to those communities.\n\n**W3: Practical Implications**\nThe paper lacks discussion on the practical implications of the theoretical analysis for transformer design. Coupling the theory with practical insights would enhance the paper's value.\n\nIn summary, the paper provides significant insights into the expressive power of transformers over data sequences, presenting elegant and theoretically sound results. However, a broader characterization of UHATs' power, increased accessibility for a wider audience, and practical implications would strengthen the paper further.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q: How much of $TC^0$ is covered?**\n\nA: 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. \n\nWhile 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.\n\nWe will clarify this in the paper.\n\n**Q: Would the paper also fit at a computer science theory conference?**\n\nA: 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).\n\n**Q: Which logic precisely captures UHAT?**\n\nA: 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. \n\nThat 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).\n\nThere 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.\n\nWe will add the above remarks in the paper.\n\n**Q: What are the practical implications?**\n\nA: See answer in global rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their in-depth reviews and useful feedback. There are some common questions with regards to practical implications of the results, which we will address here. Other questions are addressed directly to the reviewers.

**Q: What are the practical implications?**

A: We believe that the results in the paper have several interesting practical implications and applications. We mention them below, and will add them in the paper.

Firstly, that UHAT over sequences of numbers are still contained in $TC^0$ provides a justification that over sequences of numbers (be they represented as rationals or floats) are still efficiently parallelizable (more precisely, constant-time parallel complexity). This is in stark contrast to Recurrent Neural Networks, which are in the class $NC^1$ and so have logarithmic parallel complexity, and so are not as efficiently parallelizable. Note that $TC^0$ is contained in $NC^1$ (containment is not known to be strict) and that RNN can recognize $NC^1$-complete languages.

Secondly, our $TC^0$ bound can be used to understand possible limitations of UHAT in expressing various concepts over sequences of numbers. In particular, some numerical analysis concepts (e.g. SQRTSUM – which we mentioned in the paper on line 54 – determinants, and permanents) might be difficult to capture.

Thirdly, our logic $(LT)^2L$ provides a declarative language for a sufficiently large subset of UHAT. It can be used to show that some important concepts in time series can precisely be captured using UHAT. For example, take the concept of 7-day Simple Moving Average (7-SMA); this can be generalized to larger sliding windows of 50-days, or 100 days, which are often used in finance. Using $(LT)^2L$, it is easy to show that the following notion of "uptrend" can be captured using UHAT: sequences of numbers such that the value at each time t is greater than the 7-SMA value at time t. The $(LT)^2L$ formula for this is

$G( X^7\top \to \varphi(x_1,\ldots,x_7))$

where $\varphi(\bar x)$ is the formula $7x_7 > \sum_{i=1}^7 x_i$.

**Q: Significance of AC0, regular and TC0 in the context of UHAT over sequences.**

A:  That UHAT over sequences of numbers can recognize non-$AC^0$ and non-regular languages, and that UHAT are in $TC^0$ entail that the model is sufficiently powerful in performing arithmetics over supplied numbers in the input sequence, which is crucial for many applications involving sequences of numbers (e.g. time series). The latter also entails efficient parallelizability. In particular, $AC^0$ is known to have limited counting and arithmetic ability, e.g., multiplications and PARITY (the number of occurrences of a certain element in the sequence is even). *Regular languages* over sequences of numbers (i.e. well-known notion captured by symbolic automata discussed in the CACM paper [10]) have limited abilities in comparing numbers at *different positions* in the input sequence. That UHAT contains non-regular languages entails that UHAT can compare numbers at different positions in the input sequence. Finally, the circuit complexity class $TC^0$ equips $AC^0$ with the power of performing arithmetics. That UHAT over sequences of numbers capture $TC^0$-hard problems like multiplications shows the expressive power of UHAT in performing arithmetics over the numbers in the input sequence. In addition, $TC^0$ is associated with the class of languages that are efficiently parallelizable (i.e. constant time parallel complexity), as we already remarked above.

Meta-review: All reviewers agree that the submission makes a significant contribution on revealing the expressive power of transformers through the lens of formal languages, and that several important findings are drawn. Although all reviewers pointed out some potential weaknesses, all of them are addressed by the authors in rebuttal. All reviewers seem satisfactory on the responses and give positive confirmations, leaving only some comments on improving the presentation which are easy to handle. Considering the significant theoretical contributions of the submission, a spotlight acceptance is recommended.
Decision: Accept (poster)