Knee-Deep in C-RASP: A Transformer Depth Hierarchy
Open accessAbstract
It has been observed that transformers with greater depth (that is, more layers) have more capabilities, but can we establish formally which capabilities are gained? We answer this question with a theoretical proof followed by an empirical study. First, we consider transformers that round to fixed precision except inside attention. We show that this subclass of transformers is expressively equivalent to the programming language C-RASP and this equivalence preserves depth. Second, we prove that deeper C-RASP programs are more expressive than shallower C-RASP programs, implying that deeper transformers are more expressive than shallower transformers (within the subclass mentioned above). The same is also proven for transformers with positional encodings (like RoPE and ALiBi). These results are established by studying a temporal logic with counting operators equivalent to C-RASP. Finally, we provide empirical evidence that our theory predicts the depth required for transformers without positional encodings to length-generalize on a family of sequential dependency tasks.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Transformers and C-RASP programs define the exact same class of languages.
“because transformers and C-RASP programs define the exact same class of languages (cf.Yang et al., 2025, Theorem 3.1)”
From Length Generalization Bounds for Transformers (2026) · cites this paper as Yang et al., 2025, Theorem 3.1
Theorem 3.1 (Section 3, p. 5) establishes an exact, depth-preserving correspondence between the languages defined by TL[↼#]—which the introduction (p. 1) identifies as equivalent to C-RASP—and those recognized by a specified fixed-precision transformer. The claim omits that restriction: Section 2.1 (p. 3) specifies rounding except inside attention, future masking, and no positional encodings. The theorem also states the correspondence with a <BOS> prefix. (LLM, conf=0.90)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Still being checked.
Research works printed but not linked: 29
- Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir V. Podolskii. 2024. Logical languages accepted by transformer encoders with hard attention. In Proceedings of the Twelfth International Conference on Learning Representations (ICLR) .
- Christoph Behle, Andreas Krebs, and Stephanie Reifferscheid. 2009. Regular languages definable by majority quantifiers with two variables. In Developments in Language Theory: 13th International Conference, DLT 2009 , pages 91-102.
- Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP) , pages 7096-7116.
- Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D. Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, and 12 others. 2020. Language models are few-shot learners. In Advances in Neural Information Processing Systems 33 (NeurIPS) , pages 1877-1901.
- Lijie Chen, Binghui Peng, and Hongxun Wu. 2025. Theoretical limitations of multi-layer Transformer. In Proceedings of the IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) . To appear.
- David Chiang, Peter Cholak, and Anand Pillay. 2023. Tighter bounds on the expressivity of transformer encoders. In Proceedings of the 40th International Conference on Machine Learning (ICML) , pages 5544-5562.
- Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. 2019. What does BERT look at? An analysis of BERT's attention. In Proceedings of the ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP , pages 276-286.
- Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional Transformers for language understanding. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL HLT) , pages 4171-4186.
- Kousha Etessami and Thomas Wilke. 2000. An until hierarchy and other applications of an Ehrenfeucht-Fraıïssé game for temporal logic. Information and Computation , 160(1):88-108.
- Dov Gabbay, Amir Pnueli, Saharon Shelah, and Jonathan Stavi. 1980. On the temporal analysis of fairness. In Proceedings of the 7th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) , pages 163-173.
- Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. 2019. Conditional hardness results for massively parallel computation from distributed lower bounds. In Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1650-1663.
- Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, and Michael Hahn. 2025. A formal framework for understanding length generalization in transformers. In Proceedings of the Thirteenth International Conference on Learning Representations (ICLR) .
- Diederik P. Kingma and Jimmy Lei Ba. 2015. Adam: A method for stochastic optimization. In Proceedings of the Third International Conference on Learning Representations (ICLR) .
- Andreas Krebs. 2008. Typed semigroups, majority logic, and threshold circuits . Ph.D. thesis, Universität Tübingen.
- Jiaoda Li and Ryan Cotterell. 2025. Characterizing the expressivity of transformer language models. In Advances in Neural Information Processing Systems 38 (NeurIPS) . To appear.
- Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. 2024. Chain of thought empowers transformers to solve inherently serial problems. In Proceedings of the Twelfth International Conference on Learning Representations (ICLR) .
- Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. 2023. Exposing attention glitches with flip-flop language modeling. In Advances in Neural Information Processing Systems 36 (NeurIPS) .
- William Merrill and Ashish Sabharwal. 2023. A logic for expressing log-precision transformers. In Advances in Neural Information Processing Systems 36 (NeurIPS) , pages 52453-52463.
- William Merrill and Ashish Sabharwal. 2024. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations (ICLR) .
- Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, Pouya Tafti, Léonard Hussenot, Aakanksha Chowdhery, Adam Roberts, Aditya Barua, Alex Botev, Alex Castro-Ros, Ambrose Slone, Amélie Héliou, Andrea Tacchetti, and 30 others. 2024. Gemma: Open models based on Gemini research and technology. arXiv:2403.08295. · arXiv
- Rohit J. Parikh. 1966. On context-free languages. Journal of the ACM , 13(4):570-581.
- Ofir Press, Noah Smith, and Mike Lewis. 2022. Train short, test long: Attention with linear biases enables input length extrapolation. In Proceedings of the Tenth International Conference on Learning Representations .
- Clayton Sanford, Daniel Hsu, and Matus Telgarsky. 2024. Transformers, parallel computation, and logarithmic depth. In Proceedings of the 41st International Conference on Machine Learning (ICML) , pages 43276-43327.
- Imre Simon. 1975. Piecewise testable events. In Automata Theory and Formal Languages: 2nd GI Conference , pages 214-222.
- Ian Tenney, Dipanjan Das, and Ellie Pavlick. 2019. BERT rediscovers the classical NLP pipeline. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (ACL) .
- Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems 30 (NIPS) .
- Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021. Thinking like transformers. In Proceedings of the 38th International Conference on Machine Learning , pages 11080-11090.
- Andy Yang and David Chiang. 2024. Counting like transformers: Compiling temporal counting logic into softmax transformers. In Proceedings of the First Conference on Language Modeling (CoLM) .
- Andy Yang, David Chiang, and Dana Angluin. 2024. Masked hard-attention transformers recognize exactly the star-free languages. In Advances in Neural Information Processing Systems 37 (NeurIPS) , pages 10202-10235.
Cited by
Sorted by citations
Length Generalization Bounds for Transformers
Yang, A., Bergsträßer, P., Zetzsche, G., Chiang, D., & Lin, A. W. (2026) · Zenodo · doi:10.5281/zenodo.18800699
Self-citation
- Authors
- Yang, A. J., Cadilhac, M., & Chiang, D.
- Affiliations
- University of Notre Dame (US)
- DePaul University (US)
- ORCID
- Cadilhac, Michaël
- Venue
- Advances in Neural Information Processing Systems 38
- Published
- 2025
- Pages
- 41756-41797
- ISSN
- 1049-5258 (ISSN-L)
- OpenAlex
- W4417537678
- Cited by
- 0
- References
- 0
- FWCI
- 0.00
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- neural information processing systems (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Keywords
- positional encoding, rope, alibi, length generalization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
