Knee-Deep in C-RASP: A Transformer Depth Hierarchy

Thank you very much for your review.

The results apply specifically to fixed-precision transformers without positional encodings. While this is reasonable in a theoretical sense, it limits immediate applicability to real-world transformer architectures....The no-position-encoding assumption diverges from most practical models, which might limit the audience’s perception of the impact.

We acknowledge that this is a limitation of the paper in its present form. Although transformers with no position encodings (NoPE) have been considered in practice (Kazemnejad et al., 2023), we do have something to say about position encodings and would be happy to add it to the paper. It would be easy to extend Theorem 3.1 (fixed-precision transformers are equivalent to \\mathsf{TL}[\\overset{\\leftharpoonup}{\\#}]) to include periodic position encodings on the transformer side and modular predicates on the logic side. Then, by adding a neutral letter to $L_{k}$ (that is, by allowing some letter, say, $e$, to be inserted anywhere in a string without changing membership), we can show a strict depth hierarchy even in the presence of modular predicates, and therefore for transformers with periodic position encodings.

The empirical validation is limited to formal language tasks. It remains unclear how these results translate to real-world NLP tasks.

It is true that our results are limited to formal language tasks, but the family of formal languages we use, $L_k$, may well be related to real-world tasks. Since it requires searching left to find an $a$, then searching left to find a $b$, and so on up to $k$ times, it can be seen as a prerequisite to any task that involves a chain of $k$ long-distance dependencies.

For example, the $k$-hop induction heads task involves iterating the following procedure $k$ times: at position $i$, find a previous position $i'<i$ with the same symbol as $i$, then find a previous position $i''<i'$ with the same symbol as $i'+1$, and so on, which is essentially the same procedure needed to solve $L_k$. Although more work would be needed to make this more precise, we predict on the basis of our theory that $k$ hops require $k$ layers. (Sanford et al (2024) predict $\log k$ layers; the difference is that they assume a fixed string length, whereas we assume unbounded length.)

Another basic application to NLP would be recognizing "stretched" $k$-grams. Our results imply that for any sequence of symbols $a_1, a_2, \ldots, a_k$, the language $\Sigma^* a_1^+ a_2^+ \cdots a_k^+ \Sigma^*$ requires depth $k$. This is immediately applicable to a modality where each symbol is "stretched" out, like recognizing words in speech. It would be an interesting question for future research to investigate the case without "stretching".

Are there insights into whether width can compensate for depth (especially on these synthetic tasks), even if not in a fully expressive way?

Our results show that width cannot compensate for depth if we would like the transformer to operate uniformly over every input length. However, if we are satisfied with a fixed context window then it is possible. In fact, every finite language can be defined by a depth-2 \\mathsf{TL}[\\overset{\\leftharpoonup}{\\#}] formula, which will imply the same for transformers. However, this requires a width exponential in the context window size. It would be an interesting question to study depth-width tradeoffs for \\mathsf{TL}[\\overset{\\leftharpoonup}{\\#}] formulas in the fixed length regime.

The authors note performance degradation at higher k values (e.g., $k\ge10$). Is this due to optimization difficulties, data sparsity, or theoretical limitations?

One possible cause is insufficient diversity in the training data. Because we restricted the training data to strings of length [101,150], languages $L_k$ for large $k$ tend to have very short contiguous blocks of $a$'s and $b$'s, in order to fit $k$ alternations within the string. Thus, the particular distribution of blocks may become an extraneous signal for $L_k$ that hampers learning as $k$ gets larger.

Other possible causes could be: insufficient training time, insufficient width ($d$), or the so-called "curse of depth" (Sun et al., 2025).

While the authors prove depth separation for expressivity, they do not provide results regarding learnability or training stability at increasing depths.

Our results sharply mark the boundary between expressible and inexpressible functions at varying depths, allowing future investigation to isolate issues of learnability and training stability. Two questions in this vein arise due to our results. First, why is there degradation in learnability past $k=10$, despite the languages being expressible? Second, why is there non-zero performance for $k$ which are inexpressible?

Kazemnejad et al., 2023. The Impact of Positional Encoding on Length Generalization in Transformers. NeurIPS. arXiv:2305.19466.

Sanford et al., 2024. Transformers, parallel computation, and logarithmic depth. ICML. arXiv:2402.09268.

Sun et al., 2025. The Curse of Depth in Large Language Models. arXiv:2502.05795.

Thank you very much for your review.

The paper accumulates a large number of definitions and also heavily relies on objects defined in a few previous background papers (e.g. Chiang et al 2024) which are necessary for readers to follow the paper's arguments.

We agree that the paper is heavy on formalism, and think that Reviewer CRAK's suggestion to add examples of C-RASP and/or \\mathsf{TL}[\\overset{\\leftharpoonup}{\\#}] would be helpful. We will do so in the final version, either in the extra page or in the appendix.

We also agree that there are quite a few definitions used in the proof of Section 4 (accommodating, Parikh numerical predicates, etc.). These definitions represent our effort to clarify ideas developed in previous papers (esp. Behle et al., 2009). We will put some further effort into making the argument clearer, especially the sketch in Section 4.1.

1. In empirical results, authors claim that the drop after 10 layers does not contradict their findings. I thought their findings were tight so I am surprised why this happens. Can you elaborate?

One possible cause is insufficient diversity in the training data. Because we restricted the training data to strings of length [101,150], languages $L_k$ for large $k$ tend to have very short contiguous blocks of $a$'s and $b$'s, in order to fit $k$ alternations within the string. Thus, the particular distribution of blocks may become an extraneous signal for $L_k$ that hampers learning as $k$ gets larger.

Other possible causes could be: insufficient training time, insufficient width ($d$), or the so-called "curse of depth" (Sun et al., 2025).

2. Can you elaborate on how findings on TL generalize to other classes of logic?

In Appendix E we derive a depth hierarchy for $\\widehat{\\mathsf{MAJ}}_2[<]$, a logic studied by Behle et al. (2009). Our results can also be extended straightforwardly to show a depth hierarchy for the extension of \\mathsf{TL}[\\overset{\\leftharpoonup}{\\#}] with successor and modular predicates. An interesting future question is whether this can be shown for the logic with arbitrary numerical predicates, which would correspond to $\\mathsf{TC}^0$ circuits with linear gates.

Behle et al., 2009. Regular Languages Definable by Majority Quantifiers with Two Variables. International Conference on Developments in Language Theory.

Sun et al., 2025. The Curse of Depth in Large Language Models. arXiv:2502.05795.

Thank you very much for your review.

[I]ncluding more intuitive or illustrative examples of [temporal logic and C-RASP] would be very helpful. Adding a brief introductory section on these topics in an appendix could significantly improve the paper's clarity and open it up to a larger audience.

We agree that examples would be helpful, and will add examples in the final version, either in the extra page or in the appendix.

1. The work of Yang and Chiang (2024) seems to present similar results regarding the equivalence of C-RASP, TL[#]-left, and certain transformers. Could you elaborate on how your work differs from theirs? In particular, their work was not included in the comparison table in Section 1, and the equivalence of transformers and TL[#]-left, which appears to be their contribution, is presented as a contribution of the current work on line 29. Clarifying the distinction would be very helpful.

Yang and Chiang (2024) did not prove an exact equivalence; they proved that \\mathsf{TL}[\\overset{\\leftharpoonup}{\\#}] can be converted to an arbitrary-precision transformer, and a transformer with $O(1)$ precision (even inside attention) can be converted to \\mathsf{TL}[\\overset{\\leftharpoonup}{\\#}]. Here, we have tightened these bounds by proving that transformers with $O(1)$ precision (except inside attention) are exactly equivalent to \\mathsf{TL}[\\overset{\\leftharpoonup}{\\#}]. We will clarify these differences in the final version.

(The comparison table at the end of Section 1 is for depth separation results, and Yang and Chiang (2024) did not prove any depth separations, so their paper is not included in the table.)

2. Based on the equivalence results you provide, could you elaborate on the depth required to learn tasks like parity and modular addition?

Our equivalence between transformers and C-RASP proves that tasks like parity and modular addition cannot be expressed by transformers of any depth (without positional encodings). Huang et al. (2025) show that C-RASP programs cannot perform modular counting, which is a prerequisite for both parity and modular addition.

3. Regarding the experiments, accuracy is shown to sharply decline for, even for models with sufficient depth. You attribute this to challenges with learnability, not expressibility. Could you provide more insight into the specific learning challenges for these more difficult cases and speculate on what might be required to solve them?

One possible cause is insufficient diversity in the training data. Because we restricted the training data to strings of length [101,150], languages $L_k$ for large $k$ tend to have very short contiguous blocks of $a$'s and $b$'s, in order to fit $k$ alternations within the string. Thus, the particular distribution of blocks may become an extraneous signal for $L_k$ that hampers learning as $k$ gets larger.

Other possible causes could be: insufficient training time, insufficient width ($d$), or the so-called "curse of depth" (Sun et al., 2025).

Huang et al., 2025. A Formal Framework for Understanding Length Generalization in Transformers. ICLR. arXiv:2410.02140.

Sun et al., 2025. The Curse of Depth in Large Language Models. arXiv:2502.05795.

Yang and Chiang, 2024. Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers. CoLM. arXiv:2404.04393.

Thank you for your response.

Tasks like parity and modular addition cannot be expressed by transformers of any depth.

Could you please clarify whether "expressed" in this context refers to the ability to recognize the language (or solve the task) for any inputs length, or successful length generalization? Many of these tasks can be learned in-distribution, meaning for the input lengths seen during training. Does the framework offer any insights into in-distribution learning, even if it does not address generalization to longer sequences?

languages $L_k$ for large $k$ tend to have very short contiguous blocks of $a$'s and $b$'s, in order to fit $k$ alternations within the string

There appears to be a sudden performance drop from $L_8$ to $L_9$, despite the fact that the lengths of contiguous blocks are very close in these cases. This is a notable artifact in the figure, and the experimental results could be further strengthened if the authors investigate it more closely, potentially by increasing training time or model width, as suggested by the authors.

Thank you very much for your review.

The analysis appears to overlook an important aspect of practical transformers: the residual connections between layers.

Sorry for the mistake. We did assume residual connections, and our translation from \\mathsf{TL}[\\overset{\\leftharpoonup}{\\#}] to transformers depends on them.

Definition A.8 does not specify that $f$ has to be a FFNN, so $f$ could include a residual connection.

However, equation 8 indeed omitted residual connections for self-attention layers. In the final version, we will correct the equation to \\mathbf{h}^{(\\ell)}\_{i}(w) = f^{(\\ell)}\left(\\mathbf{c}^{(\\ell)}\_{i}(w) + \\mathbf{h}^{(\\ell-1)}_i(w)\\right).

Additionally, since positional encoding is not considered in this work, it may be challenging for the model to distinguish tokens at different positions, potentially limiting its expressive power.

We acknowledge that this is a limitation of the paper in its present form. Although transformers with no position encodings (NoPE) have been considered in practice (Kazemnejad et al., 2023), we do have something to say about position encodings and would be happy to add it to the paper. It would be easy to extend Theorem 3.1 (fixed-precision transformers are equivalent to \\mathsf{TL}[\\overset{\\leftharpoonup}{\\#}]) to include periodic position encodings on the transformer side and modular predicates on the logic side. Then, by adding a neutral letter to $L\_{k}$ (that is, by allowing some letter, say, $e$, to be inserted anywhere in a string without changing membership), we can show a strict depth hierarchy even in the presence of modular predicates, and therefore for transformers with periodic position encodings.

In some cases, the accuracy for the depth-(k-1) model remains quite high, while for depth-(k-2) and lower, the accuracy drops significantly. For example, in Figure 5, the "Accuracy on [201,250]" shows this. Why does the depth-(k-1) model perform so differently compared to models with lower depth? Could you provide some explanation or intuition for this observation?

If we understand correctly, you are asking why the numbers in the diagonal just below the the black line are considerably higher than the next diagonal below. In general, the presence of non-zero numbers below the line can be explained by the fact that the training and test data consist of strings of bounded length, whereas the theory only makes guarantees about strings of unbounded length. It stands to reason that these non-zero numbers would fade the further one goes below the line, and fade more sharply as the test length increases. But whether there is something special about the diagonal immediately below the line is not so clear to us, and we don't have any guesses about what would cause that if true.

Kazemnejad et al., 2023. The Impact of Positional Encoding on Length Generalization in Transformers. NeurIPS. arXiv:2305.19466.