Research map / Architectures and efficiency / Attention and transformers
Knee-Deep in C-RASP: A Transformer Depth Hierarchy
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that fixed-precision transformers (rounding except inside attention) are expressively equivalent to C-RASP / TL_C with depth preserved, proves a strict depth hierarchy for these models, and validates it empirically on the a+b+ alternating-block languages.
Problem
Which formal capabilities do transformers gain with additional depth, and can the depth needed for sequential dependencies be characterized formally for parameter-uniform transformers?
Approach
Establishes an exact equivalence between depth-preserving fixed-precision transformers (rounding except inside attention) and past temporal logic with counting / C-RASP, then uses affix restrictions, cropping and reduction lemmas on piecewise testable languages to prove a strict depth hierarchy that transfers to transformers, including with sinusoidal, RoPE, and ALiBi positional encodings.
Key results
- Fixed-precision transformers of depth k+1 recognize the (k+1)-block language but depth k cannot, proved via reduction to depth-1 formulas.
- Experiments show a depth-k transformer without positional encodings reaches 100% accuracy on alpha_{k+2} as predicted, often generalizing to double the training length.
- Depth hierarchy also holds for transformers with sinusoidal, RoPE, or ALiBi positional encodings with a different separating language.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase transformer depth to the theoretically predicted requirement | Future-masked transformers without positional encodings · altplus{k} next-token prediction and length generalization | accuracy | Helped |
Limitations
- Theoretical results use a fixed-precision transformer definition that differs from standard softmax transformers.
- Experiments do not use positional encodings and only cover formal languages.
- Other factors like width, data diversity, and training dynamics may affect practical depth requirements.
Experimental setup
Datasets: synthetic alternating-block strings from a+b+ languages
Benchmarks: synthetic alpha_k next-token prediction (length bins up to 400)
Metrics: exact-match accuracy over whole sequence
Builds on: C-RASP Yang et al. 2024 counting logic Krebs et al. 2008 typed morphisms Hahn-style depth hierarchy for MAJ2[<]
Closest papers by meaning
- What Algorithms can Transformers Learn? A Study in Length Generalization (ICLR 2024 · similarity 0.88)
- A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers (NeurIPS 2025 · similarity 0.88)
- Length Generalization for Transformers via Compression (NeurIPS 2026 · similarity 0.86)
- Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages (NeurIPS 2024 · similarity 0.86)
- Characterizing the Expressivity of Fixed-Precision Transformer Language Models (NeurIPS 2025 · similarity 0.86)
- Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.