Thank you very much for your positive review! We will try to make the final version of the paper more accessible to a broader CoLM audience.

Responses to questions:

Yes, our results imply that any fixed-precision transformer can be converted to a uniform-attention transformer (albeit a very big one); in fact, this was already shown by Chiang et al., 2023.

To answer your interesting question, we can specify exactly where the parameters are distributed. The base GPT-2 model has 12 attention layers, 12 heads, and an embedding dimension size of 768, so we can give an idea on how many parameters a uniform-attention transformer needs to be to simulate 4-bit GPT-2 by estimating the number of layers, heads, and embedding dimensions it requires.

Nearly all of the overhead comes from needing to preprocess the attention scores so they can be simulated with uniform attention. Essentially, we have to enumerate all $(2^4)^{768}$ possible query vectors, and write predicates to access each bit of each dimension of each vector. Therefore, as a ballpark estimate, $16^{768}\cdot4\cdot768$ embedding dimensions get added (this enumeration allows us to simulate all heads with one).

Then, following Theorem 5.7, an upper bound of $4$ blocks are needed to simulate each fixed-precision attention layer. Altogether, we roughly estimate that it would take a transformer with embedding dimension of $16^{768}\cdot3072$, $48$ single-head attention layers (with query and key weights all zero), and $48$ FFN's with hidden dimension $16^{768}\cdot3072$ in order to simulate 4-bit GPT-2.

Thank you for your review!

You observed that our translation from Kₜ[#] to transformers uses uniform attention, so Kₜ[#] is also a lower bound on AHATs; we'll add this result to the final version! Then, you ask what our results say about softmax-attention transformers (SMATs) as opposed to AHATs. Barcelo et al 2024 prove LTL(C,+) is a lower bound on AHATs, but their construction relies on the "winner-take-all" behavior of AHATs, and it's unclear how to adapt it to SMATs. By contrast, Kₜ[#] restricts LTL(C,+) just enough so that it can be simulated by SMATs, while remaining above the previous lower bound of FOC[+;MOD].

Comparisons with other bounds:

• FOC[+;MOD] is "underpowered" and Kₜ[#] is a "much better" lower bound because of the example of Dyck-1, which is relevant for practical applications, and because FOC[+;MOD] translates to 2-layer transformers whereas Kₜ[#] translates to deeper transformers.

• FOM[BIT] (Merrill and Sabharwal 2023) is likely a much looser upper bound than Kₜ[#]. For instance, integer multiplication is in FOM[BIT], but transformers are observed to struggle with it (Dziri et al 2023), and it does not seem definable in Kₜ[#].

• B-RASP (Angluin et al 2023) cannot express Dyck-1, but Kₜ[#] can. On the other hand, FO[<] can express Σ*aaΣ*, which we suspect Kₜ[#] and SMATs can't without positional encodings.

Answers to questions:

1. We agree UHAT languages are likely a subset of AHAT and SMAT languages. To our knowledge, this has not been shown (we hope to in future work). However, the relationship between AHAT and SMAT is not clear: SMATs have nonuniform attention, but AHATs have "winner-take-all" behavior, suggesting AHATs may recognize a language SMATs can't, or vice versa. We know of no examples, but note that all published proofs that transformers with chain-of-thought are Turing-complete (https://arxiv.org/abs/1901.03429, https://arxiv.org/abs/2006.09286, https://arxiv.org/abs/2310.07923) use average-hard attention.

2. On FOC[+;MOD], please see above.

3. Regarding size, we'll note in the final version the formula will have depth O(L) for L attention layers (even with multiple heads), and width $O((2^F)^d)$ in the precision F and width d of the transformer.

Thank you for your insightful review. Regarding the lack of position embeddings, we've considered modular predicates, but it is possible, as Angluin et al., 2023 do for LTL, to consider any finite-image position embedding in Theorem 7.1.

Regarding LTL(C,+), the short answer is that LTL(C,+) is not known to be simulatable by SMATs, but Kₜ[#] restricts LTL(C,+) just enough so that it can be simulated by SMATs, while remaining above the previous bound of FOC[+;MOD]. For the longer answer, please see below.

Responses to questions

1. Indeed, the fact that our results apply to the softmax-attention transformers (SMATs) used in practice rather than AHATs is the main distinction from [Barcelo et al 2024]. Their construction uses a table-lookup operation that relies crucially on the "winner-takes-all" behavior of hard attention, so it cannot directly be applied to SMATs. Further differences include:

• They use nonstandard positional encodings to implement the table-lookup operation. In contrast, ours does not require positional encodings.
• They interleave unmasked self-attention layers to "broadcast" a final value to every other position. Our construction uses only future-masked attention, like in practice.
• They do not consider layernorm, so any construction that relies on maximizing an attention score at a particular position, like their Lemma 1 or simulation of X ("next" operator), may break when the position-dependent scaling factor of layernorm is added. In contrast, our construction works with (and indeed requires) layer normalization.

2. Indeed, attention weights may become zero on large enough inputs if we round to the nearest number, but we don't think this is a fatal objection. Another reasonable policy, like rounding up, would avoid this. It's also true that changing the order of operations might affect the final output; for example, Li et al., 2024 argue that rounding should take place after every term of the summation. Our final version will make explicit where and how rounding should take place.
3. Regarding the comment on "overwritten" values, further explanation is on page 20. Our construction appends computed values to the "residual stream", where they are left untouched. However, integers eventually get clipped to ±1 due to technicalities of the comparison operation. The correctness of the construction is unaffected.

Thank you very much for your review.

You wrote that our results are an improvement over previous results, but the improvement is not so clear. As a lower bound, Kₜ[#] is better than FOC[+;MOD] in the sense of defining a strict superset of languages, but we think you're asking for some intuition of how much better it is. In short, Kₜ[#] is able to account for the expressive power gained by using causal masking and by increasing depth, which the previous result FOC[+;MOD] cannot.

First, the paper gives the particular example of Dyck-1, which is definable in Kₜ[#] but not FOC[+;MOD]. Many other separating languages exist, due to the inability of FOC[+;MOD] to model ordering, but this is an especially important one. It has clear practical relevance to modeling natural languages and programming languages, and we also know empirically (Ebrahimi, 2020) that transformers can learn Dyck-1.

Second, whereas the translation from FOC[+;MOD] outputs a transformer of bounded depth, our translation from Kₜ[#] outputs deeper transformers for deeper formulas. While we don't know whether deeper transformers are in fact more expressive, we suspect that they are, and practical applications certainly suggest that they are. So the fact that Kₜ[#] translates to deeper transformers suggests Kₜ[#] is much stronger and closer to actual transformers than FOC[+;MOD].

You also wrote that our results do not take into account decoding steps, e.g., chain-of-thought. The expressive power of transformer decoders that are allowed to take intermediate steps (chain-of-thought) is by now fairly well understood (Merrill and Sabharwal, 2024), and you're right that intermediate steps make the model much more expressive. But there are many situations when it's not desirable to allow intermediate steps; in particular, training data for intermediate steps is not always available. So understanding what transformers are capable of in a single step remains an important question.