Transformers in Uniform TC$^0$
Authors: David Chiang
Venue: Accepted by TMLR ()

Abstract: Previous work has shown that the languages recognized by average-hard attention transformers (AHATs) and softmax-attention transformers (SMATs) are within the circuit complexity class TC$^0$. However, these results assume limited-precision arithmetic: using floating-point numbers with O(log n) bits (where n is the length of the input string), Strobl showed that AHATs can be approximated in L-uniform TC$^0$, and Merrill and Sabharwal showed that SMATs can be approximated in DLOGTIME-uniform TC$^0$. Here, we improve these results, showing that AHATs with no approximation, SMATs with O(poly(n)) bits of floating-point precision, and SMATs with at most $2^{−O(poly(n))}$ absolute error are all in DLOGTIME-uniform TC$^0$.

Published in Transactions on Machine Learning Research (01/2025)
Transformers in DLOGTIME-Uniform TC
David Chiang University of Notre Dame
dehiang amnd edu
Reviewed on OpenReview: https: // openreview. net/ porm? id- ZA7D4nQuQF
Abstract
Previous work has shown that the languages recognized by average- hare attention transform- ers (AHATs) and softmax-altention transformers (SMATs) are within the eircuít complexity class TC However, these results assume limited- preccssin arithmetic: using peaating-ponte mumbers with Ollogn) bits (where the length of the input string), Strobl showed that AHATs can be approximated in L-uniform TC and Merrill & Sabharwal showed that SMATs be approximated in PLOGTIME-unifore TC". Here, we improve these results, showing that AHATs with approximation, SMATs with (poly(nn) bits of seating-point precision, and SMATs with at most 2 O(poly(n)) absolute error are all in
TC².
1 Introduction
Previous work (summarized in Table 1) has shown that the languages recognized by average-hard attention transformers (AHATs) and softmax-attention transformers (SMATs) are within the circuit complexity class TC This places some interesting computational problems beyond the power of these transformers. In particular, if TC * NC² (as often assumed, Williams 2022), then these transformers cannot solve any NC' problems. For example, consider Boolean formulas with constants 0 and 1 and no variables, like 1 A 1). Checking the syntaz of such formulas equivalent is recognizable by both AHATs (Yao et al., 2021) and SMATs (Yang & Chiang, 2024). But computing the semantics of such formulas, that is, deciding whether formula is true, is NC -compeee (Buss, 1987) and therefore not solvable by these transformers (unless TC = NC
the Dyck language, which
However, these non-solvability results assume limited -peciioo arithmetic. The best results that we are aware use floating- point numbers with (llog n) bits (where n is the longth the input string): Strobl (2023) showed that AHATs can be approximated L-uniform TC", and Merrill Sabharwal (2023b) showed that SMATs can be approximated DLOGTIME- TCº. These results leave open the possibility that AHATs and SMATs, defined on paper using real numbers, might not be subject to the same limitations. Here, we improve these results, showing that:
AHATs (without any approximation) are in DLOGTIME-unifrnn TC
SMATs with O(poly(n)) bits of floating-point precision in DLOGTIMEEuniform TC
Furthermore, because there are many different ways to approximate transformer using limited precision, and different ways appear to lead to different results, we propose an alternative assumption, which is that the final output is approximated up to a certain (absolute) error. Thus, we show:
SMATs with at most (0((poy(nx) absolute error are DLOGTIME-umifomm TCº.
This can also be rephrased as a statement, not about the expressivity of approximations of SMATs, but about the expressivity of exact SMATs themselves:
Any language that recognized by SMAT with margin 2 (-p(po((nn) is in DLOGTIME-uniform TC

---

Published in Transactions on Machine Learning Research (01/2025)
Summary of results on transformer encoders in previous work and in this paper. Our results show that even when (average-hard attention softmax-attention) transformers computed to very high precision, they remain limited to DLOGTIME-unilorn TC
Table 1:
attention
approximation
class
Merrill et al. (2022)
average
(loggn) precision
non-uniform TC
Liu et al. (2023)
softmax
(log precision
non-uniform TC
Strobl (2023)
average
(log precision
L-uniform TC
Merrill & Sabharwal (2023a)
softmax
Ollogn) precision
L-uniform TC
Merrill & Sabharwal (2023b)
softmax
(logn) precision
DLOGTIME-umfforn TC
This paper, Theorem 7
average
none
DLOGTIME-umifrm TC
This paper, Theorem 13
softmax
(poly(n)) precision
DLOGTIME-umfom TC
This paper, Theorem 14
softmax
2 ((polyy(m)) error
DLOGTIME-unifrm TC
2
Background
We write [n] for the set (1,2...., We write [æ] for the floor of x (greatest integer less than equal to 2). and [x] for the ceiling of æ (least integer greater than or equal to z). We write O(poly(n)) for the family of functions Un2o )nn²).
2.1 Transformers
We assume familiarity with transformers (Vaswani et al., 2017) and describe few concepts briefly. For more detailed definitions, please see the survey by Strobl et al. (2024), whose notation and terminology we follow.
In standard attention, attention weights are computed from attention scores using a softmax:
oij = [softmax st,. exp si
Σ3 s.y'
We call transformer with standard attention softmar- attertion transformer (SMAT). An average-hard allention transformer (AHAT, Pérez et al. 2019; Merrill et al. 2022) is one where the softmax is replaced by:
ahardmax si,- = lim softmax ST, 7-0
In other words, each position attends to those positions j that maximize the score 8tj- If there is more than one such position, attention divided equally among them.
Layer normalization (Ba et al., 2016) scales and shifts the components of a vector to have mean and standard deviation equal to parameters y and B:
F(x]
LayerNorm(x) Var +c
07+B
(1)
where is componentwise multiplication and is a constant. require that 0 (as is standard in practice).
When layer normalization used, we
We assume that transformer has single scalar output, computed from the last position. For simplicity, we assume that the output is used for binary classification, follows:
Definition A transformer T: E. R recognizes language L if, for every string w Σ" if then T(w) > and if L. then T(w) 0.
2

---

Published in Transactions on Machine Learning Research (01/2025)
2.2 Complexity classes
A TC circuit is one with made from the usual AND, OR, NOT gales, as well as MAJORITY gates, which are true if strict majority of their inputs are true. A TC circuit family is set of circuits indexed by lengths n. > O, such that the circuit for length n has polynomial size, bounded depth, and unbounded fan-in. DLOGTIME-unifrm TC is the set of TC circuit families for which queries about the circuit for length n can be decided in deterministic O(logn) time. Throughout this paper, whenever we say TC we mean DLOGTIME-unione TC
The class TC is also the class of languages definable in first-order logic with majority quantifiers (Mr.0(z) iff Φ(z) is true for a majority of positions x) and the BIT predicate (BIT v) iff the y-th bit of is 1) (Barrington et al., 1990). Depending on the context, it may be casier to think about TC in terms of circuits or in terms of logical formulas. Our descriptions of functions in TC abstract away from details of either circuits or formulas, making use of functions already known to be in TC together with the fact that functions in TC are closed under scrial and parallel composition (Jeřábek, 2012).
Theorem 2. The following operations on O(poly(n)) bit integers are in TCO:
(a) Addition of two numbers
(b) Comparison of two numbers
(c) Marimum of n namberrs
(d) Truncated base-2 logarithm llog2 x]
(e) Iterated addition of n numbers
(f) Multiplication of two numbers
(9) Iterated multiplication of numbers
(h) Truncated division of lwo numbers.
Proof. Addition (a) shown by Immerman (1999, Prop. 1.9) for n bits and casy to extend O(poly(n))
bits. Comparison (b), maximum (c), and truncated base-2 logarithm (d) are also easy. These cases do not roquire majority gates.
Iterated addition (e) is shown, for example, by Barrington & Maciel (2000, Lecture 7, Section 2), and multiplication (f) is closely related.
Iterated multiplication (g) was proven to be in TC by Hesse et al. (2002, Theorem 5.1) and can be used for truncated division (h).
2.3 Approximation error
We will define various numeric representations and associated concepts as they are needed, but will make use of the following definitions throughout.
Definition 3. For functions f: X R and f: X + R, we say that f approximates f with absolute error at most if for all æ E X, we have 1f(x) - f(x) < and f approximates / with relative error at most. if for all x E X, we have f(z)-f(z)
<e. e.
f(x)
3 Arbitrary-precisoon AHATs
In this section, we prove that AHATs without layer normalization, even with arbitrary precision, are in TC We do this by representing rational numbers as pairs of integers. This turns out only need polynomial number of bits, so it can be computed in TC
3

---

Published in Transactions on Machine Learning Research (01/2025)
Definition 4. A p-bit rational number is pair (a, b), where is integer in 1-2",27) and b is integer in [1,2)) The value of (a, b) is a/b.
(According to this definition, p-bit rational number actually requires (2p+ 1) bits: for the sign, p for the numerator, and for the denominator.)
Lemma 5. The following operations on O(poly(n))-bit rational numbers are in TC
(a) Addition, multiplication, division, and comparison of two numbers
(b) Iterated multippicationn of n numbers
(c) Iterated addition and mazimum of numbers.
Proof. The operations (a,b) can be expressed in terms of operations on O(poly(n))-bit integers, which are in TC (Theorem 2):
(a1, b1) + (az, b2) (a1bz + bia2, b162)
(2)
(a1, b1) (az, b2) (a102, b1b2)
(3)
(a1, b1) (az, b2) (a1b2, b122)
(a1, b1) (a2,b2) + a1b² b102
II
(a., b,)
II ae b, VEEm
(6)
iE
iE(m]
To find the sum or maximum of n rational numbers (c), we precompute the product of the denominators:
B II bj
jE[n]
Σ (at bb)
o,B/b,, B
(7)
EE|n]
max (a;, bi) iE(n]
max B/b, B (iE/n]
(8)
Lemma 6. Let T be an AHAT with rational weights, p-bit position embeddings, and no layer normalization. Let be the depth Tf T. Then the computation of needs O(m=²) bits for each intermediate and final value.
Proof. First, note that if (a1, bi) uses O(n²) bits and (az, b2) uses (nn²) bits, then their sum, product, and quotient (Eqs. (2) (4)) also use Onn)) bits. But (a,, b1) for i [n]] use O(n)) bits each, then their sum (Eq. (7)) uses O(1++)) bits.
We prove the lemma by induction L. If L O, we just look up the embeddings, which need O(p) bits per value. If L > O, assume that layer (L 1--11 11 required Oppn-11 bits per value. In the self-attention, the queries, keys, values, and scores need Opm--1i bits. The sum of the maximum-scoring values, which there could be up to n of, needs (pm²² bits, as does the average. Finally, the activations of the FFNN also need Oppn*) bits.
Theorem 7. Let T be an AHAT with rational weights, O(poly(n))-biz position embeddings, and no layer normalization. Then the language recognized by T in TC
Proof. AHATs use only the operations in Lemma 5 on rational numbers with (ppoly(n)) bits (Lemma 6). Since these operations are all computable in TC and can be composed in TC the language recognized by T is in TC
4

---

Published in Transactions on Machine Learning Research (01/2025)
Remark 8. We now have more less complete characterization of which regular languages can be recognized by AHATs. Barrington et al. (1992) showed that every regular language I is either in ACC or NC¹ -comleee
If L in ACC", then it can be defined in linear temporal logic with modular counting (Baziramwabo et al., 1999), and therefore can be recognized by an AHAT with suitable position encodings (Barceló ct al., 2024).
If L is -Cmccomp, then by Theorem 7 it cannot be recognized by an AHAT unless TC NC
4 Dolynomial-precisionn SMATs
Next, we turn to SMATs, extending Merrill & Sabharwal's proof from O(logn) bits to O(poly(ni) bits.
Definition A p-bit floating-por point number is a pair {m, e) where m (called the significand) and e (called the exponent) are integers, |m|] E {0} U [2"_1,,00 ,2),, and E [-2", ,2)). The value of (m, e) is m 29. We write rr)) where is either a real number a floating-point number, for the p-bit floating- point number nearest to œ. If there are two such numbers, we call r a breakpoint and define round,(z) to be the one with an even significand.
(According to this definition, a p-bit floating-point number actually requires (2p + 2) bits: (p + 1) for the significand and its sign, and (p + 1) for the exponent and its sign.)
To compute SMAT with p-bit foating-poiit numbers mcans to approximate the operations in the SMAT with operations floating-pol point numbers. In typical floating-point implementations, addition, multiplica- tion, division, and square root are rounded to the nearest foating-poin number, but exp is only approximated with a relative error of about PPP We also assumee that summation of n numbers is performed exactly and then rounded (following Liu et al. 2023; Chiang et al. 2023; Merrill & Sabharwal 2023a; but pace Li et al. (2024), who argue that rounding should be performed after each addition).
Lemma 10. The following operations on floating-posts point numbers with p e O(poly(n)) bits are computable in TC", with ezact rounding to the nearest p-bit floating- point remberr:
(a) Addition, multiplication, division, and comparison of two numbers
(b) Iterated mulliplicationn of numbers.
Proof. These operations on O(poly(n))-bit integers are in TC (Theorem 2). We just have to show that they are also definable on floating- -oont numbers. This is not new result, but try to fill in some details here that are missing elsewhere.
First, roundy e)) can be computed in TC as follows: Count the number of significand bits = llog [m]] + 1 (Theorem 2d), shift m right by (q p)) bits, and increment e by (g - p). Round m to the nearest integer, and if mm| = 2", shift m and increment e once more. For the operations (a), we have
(1) + (2) = roundp((m; + m2 // 201- aa))
if 2 e2
round,((m) // 2-2-01 + m2,
if S e2
(m) x (m2, E2) = round,(mm)yy,, E1 + +22)
(1), + (m2, e2) round,((1), 2 m22 El 62 p 1))
mi Sm // 2 if e 2 P2
(m1, 01) (22,62) $
m1 // 2 < m2 if e 5 62.
The operation // is defined as
a/b
if a/b a multiple of 1/4 otherwise.
a a//b b
118
5

---

Published in Transactions on Machine Learning Research (01/2025)
O(poly(n))
2 p
[log2 n
O(poly(ni)
summands
block-sums
*
*
(poly(nn)
2 p
(ppoly(n))
Overview of algorithm for iterated addition of p-bit floating-pont point numbers. The summands are grouped into blocks that each span ((poly(n)) bits. They are separated by at least + flogz n bits, so that the block-sums are separated by at least bits.
Figure 1:
The result has three fractional bits (called the guard, round and sticky bits), which ensure that the result is correctly rounded to the nearest floating point number (Goldberg, 2017). Note that this can be computed efficiently even if b is a large power of 2.
For iterated multiplication (b), we have
mi Σ e 1 IE(n]
(m,, e.) = round, II kEIn
II
iE(n)
Lemma 11. Iterated addition of floating- numbers, each with p E O(poly(n)) bits, is in TC
Proof. We are given p-bit floating toiting--ointt... numbers (m1, ,..,,... (mas Gn). Without loss of generality, assume m, f O. We need to compute the sum
round,
Σ (mps es) iE(nl
Step Define the relation i~ just in case le; eyl 2p [log2 n]. The transitive closure of partitions the (indices of the) summands into blocks B1,..., B& S [m] (that is, if j, then and j in the block). The intuition (Fig. 1) is that, in the binary representation, the numbers within each block are close enough together that we can sum them by brute force, while numbers in different blocks are far enough apart that we can ignore all but the two leftmost blocks.
The partitioning into blocks can be computed in TC" as follows. Call i E [n] block-ménimal there is no E [m] such that (my,es eg) < (m,,es) e.) and j. Then and j belong to the same block if and only if there is block-minimal & E [n] such that e; ex S Ej or ej < Ek S ex.
Step 2. For each block B, compute the sum of all the numbers in B. Let be the minimal exponent in B (that is, = min 1 B}). Since all the exponents in B are bigger than e by at most n(2p + flog, n²) E Oppoly(n)), we can perform this sum exactly (Merrill & Sabharwal, 2023a):
Σ (m, es) = iEB
Σ BEB
mi 26

---

Published in Transactions on Machine Learning Research (01/2025)
P
2
2 1
2
*
*
())
10...0
s(1)
(22)
+1
11
Case 2
Case 3
Figure In Case ( is a breakpoint, so the sum s depends on the sign (and only the sign) of s(2), Case 3, even (1) has only single bit, the remaining block-sums do not affect the whole sum.
We've left the block-sums unnormalized; that is, their significands could have more or less than p bits. Slep Let 8(0) (mll)) be the sum of the block with the i-th largest absolute sum. Then the first block-sum g(1) dominates the whole sum; any number not the first block has absolute value less than (29, e(0) 2p [logz nl). So we can bound the rest of the sum as:
(0) < n 2p 20
2210-ppp- 2p
Mlog m < 20(
(9)
1=2
In other words, in the binary representation, there is a gap of at least p zero bits between the first block-sum and the remaining block-sums.
It's not necessary to sort the block-sums; it's enough to find the maximal block-sum ( and the second block-sum s()) Then we consider three cases (see Fig. 2).
Case 1: If (1)
then the whole is zero, and are done.
Case 2: If (1) is breakpoint, then we need to look at the remainder to see which way to round. Since
2c (1) (Eq. (9)), it's enough to look at the sign of r, which is the sign of m2)).
Case 3: Otherwise, (1) is sufficiently far (on the number line) from breakpoint that the addition of r cannot change the result. Due to cancellation, m!)) could have fewer than p bits, down to just one bit. So the distance to the nearest breakpoint could be as small (0 But < (0(1) by Eq. (9).
Lemma 12. Given a floating-pon point number a with O(poly(n)) bits, the following functions can be computed TC
(a) Vz, rounded to the nearest floating- number
(b) expx, with relative ervor of at most 2-P
Proof. The basic idea is to truncated Taylor series (Merrill, p.c.; Hesse al., 2002, Cor. 6.5). This is not new result, but try to fill in some details here that missing elsewhere. Let p E Oppol((n)).
For vz: Find E [2, and an even integer k such that r = r 2 as follows. If (m, e) and e + p is even,
let r = m P E (.11 1) and & = e + p; if e + is odd, let r m 2- E [1 1) and A = e + + 1. Then
compute VT using the Taylor series about
N -F=
Σ i=0
?
(r 1)a + -0

---

Published in Transactions on Machine Learning Research (01/2025)
Since the error term is in - 1) and 2, there is some such that the error is at most a/r 1 & ( To make this less than 2-P-1, set N log 2+go E Opp). Then we decide which way to log 7 round by squaring the breakpoint ncarest to the approximation of vr and comparing it with r. Finally, v vr. 2k/2.
For expx: z: Let k = |z/ 2og2] and r = a -- kog 2, where log computed using the series:
N-1
log 2
Σ
1 +0
2.
im1
Compute expr using the Taylor series about 0:
N-1 0(
ps
expr
Σ =
+
Since the error term is in O(r*)) and r E [0, log 2), there is some a such that the relative error is at most ar" expr I (llog2) So get relative error of p- set N plog 2+1og log log
O(p). Finally, exp
(expr)-27
Theorem 13. Any language that is recognizable by O(poly(n))-bit precision SMAT is in TC
Proof. SMATs use only the operations in Lemmas 10 to 12. Since these operations are all computable in TC and can be composod TC the language recognized by an ((poly(n))-bit precision SMAT in TC J
5 Approximating SMATs with 2-O(poly(n)) error
Defining "transformers with p-bit precision" and characterizing the class of languages they recognize is complicated, because there many different ways to perform rounding, which can lead to differences in expressive power (Li et al., 2024). In this section, we propose an alternative approach, which is to limit the error of the final result of a transformer approximation and abstract away from details (like precision and rounding) of how that level of error achieved. We show that approximating a SMAT with absolute error at most 2 -(pool)(()) can be done TC
This has two advantages. First, it has simple and unambiguous definition. Second, it will allow us to say something about the expressivity of large subclass of exact SMATs, namely, those that accept reject strings with margin 2 ((poo))(n))
Theorem 14. For any SMAT T: Σ- R and for any e(n) 2 g-O(pol((n)), there is a function î: E + in TC such that for all Σ* with jwl, (Tw)) T(w)l <(n).
Proof. We construct î out of the following operations, where > 0 and c > do not depend on n:
(a) Addition of two numbers
(b) Multiplication zy where (r), lyl S
(c) Comparison of two numbers
(d) Inverse square root where |x| 2
v
(e) Iterated addition of n numbers
()) Softmax of numbers.
8

---

Published in Transactions on Machine Learning Research (01/2025)
The upper bound C on all activations was shown by Hahn (2020), and in operation (d), the lower bound exists because we defined layer normalization to add constant to the variance (Eq. (1))-
To simplify the error analysis, all of the above operations are performed on O(poly(n))-bit rational numbers. In TC all of these operations can be computed exactly (Lemma 5), except v and exp2, which can be approximated with relative error e for any 6 E 2-0(poy(xx), by Lemma 12. In that Lemma, the case for square root asks for r E [t 1] and an even integer k such that = r 2t, We do this as follows. If a b, compute [ using truncated division (Theorem 2h), then count the number of bits (Theorem 2d) to get odd, increment by
:: [log2] [JJ] + Similarly,
b, compute h = - |loge| 1 + 1. Finally,
Fix éfinal > 0. We show by induction that, for each operation i in the computation of T, there is a 6 E ((c/poly(n) such that we compute operation i with error 6;, then the final answer has error Gimal- In particular, is possible to compute f using O(poly(n))-bit rationals and achieve a final error of at most 2 2-0(poly(m)).
For each operation, will show that for any O, there is 5 (((//)) such that if the inputs to the operation approximated with error 6, then the output is approximated with error e.
If a function f: I + R is p-Lipschitz continuous, then for any > O, if ||b|| S c/p, then +) f(x) s p ||b]] e. Operations (a d) are p-Lipschitz continuous with not depending on n, while iterated addition of n numbers (e) is n--iissciizz continuous, and softmax of n numbers (f) is p-Lipschitz continuous with p not depending on n.
We show the cases of inverse square root and softmax, as these also have error due to the Taylor approxi- mations.
For inverse square root = for x 2 For any <> O, let ó = min (5. eve (2et)) Suppose that x has Va
been approximated as å = r + h where |h| S 8. Because V for 2 c- h / is Ve Lipsschitz continuous, approximate v with relative error n where |n/ 6. So we
have I/2- Vzl s 6 approximate y as i = vi(++)) and the error is
Ve Furthermore,
10 - vl =
VI(1+ + 1)
VI
1
+
triangle inequality
Vi(1+ + m)
Vi
V
/
Vx
"
V
Vi
+
V5(1 + 1))
5
8
Vc
S. 5, f.
G.P. N
VE 2
1
V2
(2c + 1)v2
8
cve
SE
Suppose that for all i E [m], xy has been approximated as x; + h2 where [hg] / 6, and let 17 where |n < be the relative error of approximating exp(x; + ht). Then the softmax and its approximation are
For softmax of n numbers: For any e > 0, let 8 = min (5. (
expXt
V1 Σ, expx; 2j
(exp(2; + h:)) + 17))
01 E, (exp(zz + h2 )1 +2))
9

---

Published in Transactions on Machine Learning Research (01/2025)
and i overestimates y by at most
(exp(a; + 61)(1 + +)
0. y (expx(( 6))(1 6)
(exp 20) + +6) - yi
1
(exp (1 + 6)
y1 S
1-8 8
(1 + 41) + 8)
25 E [0, = exp 25 - 1 1 4.48
8
88
8 85 2
1-6 8
K 168
8 1
2
5 16
Similarly, we can show that 9 underestimates y by most
Vi
0 88 S
The above is a statement about the expressivity SMAT approxinations, but as mentioned at the beginning of this section, also makes it possible say something about the expressivity of large subclass of exact SMATs.
Definition 15. A transformer T: E- + R recognizes a language with margin c(n) if, for every string w E' with w/, if w E L then T(w) > e(n), and if then T(w) -e(n). Corollary 16. Any language that recognizable by a SMAT with maryin 2 ((pol((n))) is TC
Proof. Let L be a language recognized by SMAT with margin e E 2- (m)))) By Theorem 14, there is a function T in uniform TC such that for all w, we have 6 S ((w) T(w) Se. w E L,, then T(w) > 6, f'w)== 2 T(w) - 0. Similarly, if L, then T(w) -e, so (w) S T(w) +e O. Therefore, T also recognizes L.
6 Limitations and Conclusions
The levels of precision considered here go far beyond what is practical compute with. Nevertheless, these results are valuable because they further strengthen the case that transformers cannot compute any function outside of TC
Moreover, Section 5 offers an alternative approach to Limited-precision transformers that may be useful in more realistic settings. In particular, an analogous argument shows that it takes (logn)) bits of precision to achiove an error of 1/O(poly(n)), which may make SMATs with margin 1/O(poly(n)) an interesting target for future research.
References
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey F. Hinton. Layer normalization. In NIPS 2016 Deep Learning Symposium, 2016. URL
06450.
Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir Podolskii. Logical languages accepted by transformer encoders with hard attention. In Proceedings of the Twelfth International Confer- ence on Learning Representations (ICLR), 2024. URL https: //pp//veeereeeeeee/ /ttp://ppoooooooooooooo/oaaaaaaa
David A. Barrington, Kevin Compton, Howard Straubing, and Denis Thérien. Regular languages in NC
Journal of Computer and System Sciences, 44(3):478-45) 499, 1992. 1oi:10.1016/ 00000///0222000000990004444
10

---

Published in Transactions on Machine Learning Research (01/2025)
David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC'. Journal of Computer and System Sciences, 41 (3):2744-300 1990.
David Mix Barrington and Alexis Maciel. Advanced course on computational complexity, 2000. URL https: wwwrkala..edeeeeeeooo.o.oo.eaaae htt.a//...etuaalleesss////////// CMI-PCMI Undergraduate Program.
Augustin Baziramwabo, Picrre McKenzie, and Denis Thérien. Modular temporal logic. In Proceedings of the 14th Symposium on Logic in Computer Science (LICS), pp. 344 351, 1999. 100:10.119//IIS.19900
Samuel R. Buss. The Boolean formula value problem is in ALOGTIME. In Proceedings of the Nineleenth Anaual ACM Symposium on Theory of Computing (STOC), pp. 123-131, 1987. Noi:10.1145/28335.0 28405
David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity transformer encoders. Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202 of Proceed- ings of Machine Learning Research, pp. 5544,5562, 2023. URL https://proceeddngss mlr hatpp//gg...rr..rss///22222 press/v202/ chiang23a. html.
David Goldberg, Computer arithmetic, 2017.
URL book-compant on/ /000///80011195.1. Appendix J of John L. Hennessy and David A. Patterson, Computer Archileclure: A Quantilative Approach, 6th ed.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020. doi:10.1162/tadd 00306.
William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences, 65(4):695-716, 2002. 1oo:1001116; 200.100.110//0022-00000000 (0022-0000012))00025-5
Neil Immerman. Descriplive Complexily. Springer, 1999. 400:1000077998:1-411200553
Emil Jerábek. Root finding with threshold circuits. Theorelionl Computer Science, 462:59 69,
2012. (es:10..16/))...s22222.. 50304397512008006.
URL https://www.. www.sseeeeneerrrtt... https://ww.sceeeeddeettt htt.://teett..coeeeeee///e/rr//e
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve in- herently serial problems. In Proceedings of the 12th International Conference on Learning Representations (ICLR), 2024. URL https:/ / httpr/rreetttooommmdaaa//EEE///
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shorteuts automata. In Proceedings of the Eleventh International Conference on Learning Representa- lions (ICLR), 2023. URL http::////oaaaereeeeeeeee///eeee
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log- bog-precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023a. doi:10.1162/vaad a 00562.
William Merrill and Ashish Sabharwal. A logic for expressing log-precision transform- ers.
In Advances Neural Information Processing Systems 36 (NeurPPS), pp. 52453- 2023b.
52463,
URL https://paperr neurips.. wwtrriss.cc/aapepe cc/ppaprrfilleeppeeeeeeeeeeeeeee wtt.ffe//lppp///22///. hashh/ @B665577CT18881111550020228888 www.eeetttttttttaaaaaeaaoeee
html.
William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, doi:10.1162/taar 00493.
2022.
Jorge Pérez, Javier Marinković, and Pablo Barceló. On the Turing completeness of modern neural network architectures. In Proceedings of the Seventh International Conference on Learning Representations (ICLR), 2019. URL https://openrevver. wtt.rriee..netttooeeeeee httpa//wwwwee..eeeeeoom/o/ataaaa
11

---

Published in Transactions on Machine Learning Research (01/2025)
Lena Strobl. harr attention transformers constant-depth uniform threshold circuits, 2023. URL https://arxiv. wrg/ 032112. arXiv:2308.0321.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? A survey. Transactions of the Association for Computational Linguisties, 12:543-
561, 2024. doi:10.1162/tade 00663.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Pro- cessing Systems 30 (NeurIPS), 2017. URL httpa://procedings. nngrrcccddings..uuiip....... httpa///ss...iissss//////////111 cc/papper/201//hahhl ( Abstract..tt............aaaae..t html.
R. Ryan Williams. Some estimated likelihoods for computational complexity. In Bernhard Steffen and Gerhard Woeginger (eds.). Computing and Software Science: State of the Art and Perspectives, pp. 9-26. 2.
Springer-Verlay, 2022. 001:10.0007/978--3311--33
Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. Proceedings of the First Conference on Language Modeling (CoLM), 2024. URL https: //openreview.o peee/forumiidFPaaPgUUll
Shunyu Yao, Binghui Peng, Christos Papadimitrion, and Karthik Narasimhan. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (ACI-IJCNIP), pp. 3770 3770-3785, 2021. doi:10.1 (ai:10.1163). 18653/v1 1222221 acl-long..92.
12


Reviews:
[{"review_id": "Sp7PWmTsJG", "reviewer": "Reviewer_dNpr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe strength of this work lies in the clear presentation of the results, especially through the use of a table (Table 1). Most of the statements are well-articulated and easy to understand.\n\nWeaknesses: \n1. It is hard to identify the studying scenario of approximation of different precision such as $O(\\log n)$ and $O(\\textrm{poly}(n))$. Usually, when a model is trained, it is unlikely people will change the precision of weight or computation based on the input sequence length. It is necessary that the author give interpretation of this modification in the paper. (As can be seen, all other paper are discussing $O(\\log n)$ scenario)\n2. There is no discussion on the challenges of extending the results to multi-layer cases. It is common for results in multi-layer settings to differ from those in single-layer scenarios. Including a brief discussion or sketch of a potential approach to study the multi-layer case would be beneficial for readers and could guide future research.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This is a theoretical paper studying the transformer and the relationship with $TC^0$. It is shown that with suitable approximation and approximation structure, a DLOGTIME-uniform approximation can be achieved. However, the significance of DLOGTIME-uniform $TC^0$ in this context remains unclear. Nevertheless, the paper is well-written and easy to follow.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Provide the argument that meaning of different approximation approaches. (O(log n) and O(poly(n)) )\n2. It is essential to examine whether the theorems presented in Table 1 can be extended to multi-layer architectures. This extension would require careful consideration of the interactions and dependencies across layers, as well as potential changes in the underlying assumptions or structures. If such a generalization is feasible, it would significantly enhance the scope and applicability of the results. However, the current formulation may not provide sufficient details or tools to directly support this extension, leaving room for further exploration in future work.", "broader_impact_concerns": "The results are primarily theoretical, and their broader impact remains unclear. It is also uncertain whether these theorems represent their optimal form or if there is potential for future refinement and improvement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JAXZXKx3nB", "reviewer": "Reviewer_g37N", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- For the most part, it is a piece of art\n- The paper no doubt is full of profound advances in pushing the limits of what was previously known about the expressiveness of hard and soft attention transformers and attempts to break new ground by using approximation error as opposed to internal details of computation \n\n### Weaknesses \n- Proofs end a little too abruptly. There is not enough background knowledge given to connect the dots. Better final statements is very much needed\n- It is very easy to lose track of how the technical arguments end up contributing to the lemma/theorem. Cases in point: **Lemma 11** and **Lemma 12** , for all the technical sophistication it seems to **implicitly** boil down to whatever circuit you're looking for as long as the algorithm can be boiled down to these already defined as $TC^0$ circuits and put them together it should be a $TC^0$ circuit\n- The implicit reigning concept that **DLOGTIME uniform $TC^0$** circuits are closed under an input-to-output class size preserving, circuit size maintaining composition _is understated_\n\n### Concerns\n1. In **Lemma 12**\n\n   > there is an N $ \\in O(p)$ that makes the relative error at most $2^{−p−1}$\n\n   I would reason that there needs to be a mention of how the maximum relative error w.r.t precision to give the reader as to how the number was arrived at\n\n 2. **Corollary 16** definitely needs more development.  Maybe it's because of space constraints or something else but atleast to me there's no doubting that Section 5 ends rather abruptly without connecting the dots properly. The claimed easy proof for __Corollary 16__ according to me is very much needed to establish how  $\\tilde{T}$ is in $TC_0$ \n\n3. Under **Lemma 1** Before _Step 1_ shouldn't the numbers' significands be normalized given the relation $| e_i - e_j| \\lt 2p + \\lceil \\log_2 n \\rceil $ excludes the  significands and order of magnitudes can be misinterpreted as we're only looking at the exponents?\n\n4. Under **Definition 9** the definition of a p-bit number perhaps needs a bit of explanation of how the p bits are distributed between the significand and exponent. The lack of this makes **lemma 11** hard to follow\n\n 5. Under **Theorem 14** \n\n    > To simplify the error analysis, all of the above operations are performed on O(poly(n))-bit rational numbers. All operations are exact except √x and exp x (inside softmax), which, by Lemma 12, can be approximated with relative error $\\eta$ for any $\\eta \\in 2^{-\\textrm{O\\(poly\\(n)\\)}}$.\n\n    Specifically for $\\sqrt{x}$, lemma 12 seems to pertain to floating point numbers which I'm aware is a superset of rational numbers. But are we able to use the same argument here ?\n\n6. Under **Section 5**  how much of the following goal:\n  \n    > In this section, we propose an alternative approach, which is to limit the error of the final result of a transformer approximation and abstract away from details (like precision and rounding) of how that level of error is achieved\n\n   is being achieved if in the process of simplifying the error analysis an assumption is being made about the precision?\n\n\n### Nitpicks and Questions\n1. Under **Background** given how important the concept of _uniformity_ is, it is not defined which is rather odd given every other concept like _DLOGTIME_, _transformers_ are defined\n2. Under **Section 2.2 Complexity classes**\n \n   > The class $TC_0$ is also the class of  ... (bit about FOL)\n\n   is  perhaps best kept as Remark as it does (please correct me if I'm wrong) nothing for the development of the ideas in this paper (as far as I can tell)\n3. Under **Lemma 11**\n\n   > We compute the partitioning into blocks as follows ....\n \n   I would reason that the relation and it's associated transitive closure is already mentioned, this block is perhaps redundant. Perhaps I am missing something?\n 4. The complexity class of rounding isn't mentioned anywhere (perhaps I missed this)\n 5.  Under **Section 5** in this particular part\n   \n      >  and abstract away from details (like precision and rounding) of how that level of error is achieved\n\n      other than *precision* and *rounding*, is there anything else that is being abstracted away?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper is another addition to establishing the computational complexity and as a consequence the decision problems solved by transformers both of the hard attention (AHAT) and soft attention variety (SMAT)\n\n- The authors aims to improve on previous results i.e AHAT (with limited precision) can be approximated in L-Uniform $TC^0$. The improvement being it is now in DLOGTIME Uniform $TC^0$ with arbitrary precision \n- The authors aim to push the previously established complexity class for for SMATS from input floats of **log size** bits  to input floats of **poly size** bits    \n- The authors are attempting to break ground with expressing the expressiveness of SMAT by abstracting away precision and rounding details and soley focusing on SMAT output approximation error (establishing the absolute error to  be at most $2^{-\\textrm{O\\(poly\\(n)\\)}}$", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Section 5's ending i.e **Corollary 16** definitely needs an expansion\n- Under **Definition 9** the definition of a p-bit number perhaps needs more explanation of how the p bits are distributed between the significand and exponent", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OK4WCVxPp7", "reviewer": "Reviewer_gNug", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n- The paper is generally well-written, and clearly structured.\n- The main theorems are well-motivated and intuitive, focusing on the new high-precision scenario and improving previous results.\n- Introducing absolute error as a new approximate method adds a fresh perspective to transformer complexity analysis.\n\n**Weakness**\n- As acknowledged by the authors, the assumptions of $O(\\text{poly}(n))$-bit precision and $2^{-O(\\text{poly}(n))}$ absolute error are highly unrealistic in practical settings. This limits the applicability of the theoretical results to provide meaningful insights for real-world transformer implementations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper explores the circuit complexity of Average-Hard Attention Transformers (AHATs) and Softmax-Attention Transformers (SMATs), demonstrating that both architectures belong to the complexity class $TC^0$ under the assumption of high-precision arithmetic. The authors first prove that AHATs, when equipped with position embeddings of $O(\\text{poly}(n))$-bit precision and without layer normalization, can be computed within DLOGTIME-uniform $TC^0$. This result is derived through a detailed analysis of the operations involved in AHATs, leveraging existing results on the circuit complexity of these operators. Similarly, the paper shows that all operations in SMATs, using $O(\\text{poly}(n))$-bit precision, also fall within DLOGTIME-uniform $TC^0$. Finally, the authors introduce a new approximation technique based on the absolute error, proving that SMATs with an error bound of at most $2^{-O(\\text{poly}(n))}$ are computable within DLOGTIME-uniform $TC^0$.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I am not very familiar with the complexity circuits of transformers. However, I have noticed that some prior works also omit layer normalization for simplicity in their proofs. Could the authors clarify whether your results still hold when layer normalization is included?\n\n- I am also unsure whether the absolute error bound of $2^{-O(\\text{poly}(n))}$ is too loose in relation to the existing theorems. Could the authors provide additional insights or potential strategies to further tighten this bound?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper builds on previous results that aim to characterize Transformers in terms of their membership in complexity classes when taking into consideration the model's precision. The paper unifies these past findings and extends them a bit, in particular showing DLOGTIME-uniform TC0 complexity for a few different Transformer variaitons (including different versions of attentions and precision). All reviewers felt the results were sound and possibly of interest and therefore recommended acceptance.
Decision: Accept (poster)