mlsanityData to 14 Oct 2026

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

arXiv 2506.16055 ↗First posted 19 Jun 2025cs.CL cs.FLcited by 12

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 18 of its 37 references that are in the map. First posted on arXiv 19 Jun 2025.

Builds on

18 of 37 references.

References · 18

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  4. 2020Language Models are Few-Shot Learnerscited by 32,419
  5. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,703
  6. 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,103
  7. 2019BERT Rediscovers the Classical NLP Pipelinecited by 1,059
  8. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 1,003
  9. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  10. 2021Thinking Like Transformerscited by 184
  11. 2024Transformers, parallel computation, and logarithmic depthcited by 79
  12. 2023Exposing Attention Glitches with Flip-Flop Language Modelingcited by 75
6 more
  1. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  2. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 49
  3. 2024A Formal Framework for Understanding Length Generalization in Transformerscited by 45
  4. 2024Theoretical limitations of multi-layer Transformercited by 45
  5. 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
  6. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 10.

12 papers.

  1. 2025Quantitative Bounds for Length Generalization in Transformerscited by 8
  2. 2026Length Generalization Bounds for Transformerscited by 4
  3. 2026Characterizing the Expressivity of Local Attention in Transformerscited by 3
  4. 2025Probability Distributions Computed by Autoregressive Transformerscited by 2
  5. 2026On the Ability of Transformers to Verify Planscited by 2
  6. 2026Rational Transductorscited by 1
  7. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)cited by 1
  8. 2026Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don'tcited by 1
  9. 2026Disentangling the Expressivity of RoPEcited by 1
  10. 2026Synthesis and Verification of Transformer Programs (Technical Report)cited by 0
  11. 2026Encoder-Decoder Transformers: Logical Characterizations and Periodicitycited by 0
  12. 2026Length Generalization for Transformers via Compressioncited by 0