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

• URL: http://arxiv.org/abs/2506.16055v1
• Date: Thu, 19 Jun 2025 06:27:54 GMT
• Title: Knee-Deep in C-RASP: A Transformer Depth Hierarchy
• Authors: Andy Yang, Michaël Cadilhac, David Chiang,
• Abstract summary: We consider transformers that round to fixed precision except inside attention.<n>We show that this subclass of transformers is expressively equivalent to the programming language C-RASP.<n>Second, we prove that deeper C-RASP programs are more expressive than shallower C-RASP programs.
• Score: 7.9266383017424795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 with greater depth? 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). These results are established by studying a form of temporal logic with counting operators, which was shown equivalent to C-RASP in previous work. 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.

Related papers

• Transformers for Learning on Noisy and Task-Level Manifolds: Approximation and Generalization Insights [47.62295798627317]
  This work establishes a theoretical foundation by analyzing the performance of transformers for regression tasks involving noisy input data on a manifold.<n>We prove approximation and generalization errors which crucially depend on the intrinsic dimension of the manifold.<n>Our results demonstrate that transformers can leverage low-complexity structures in learning task even when the input data are perturbed by high-dimensional noise.
  arXiv  Detail & Related papers  (2025-05-06T05:41:46Z)
• A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers [29.839710738657203]
  Recent theoretical results show transformers cannot express sequential reasoning problems over long inputs, intuitively because their computational depth is bounded.<n>We show even highly uniform transformers with depth $Theta(log n)$ can express two important problems.<n>We quantitatively predict how depth must grow with input length to express these problems.
  arXiv  Detail & Related papers  (2025-03-05T23:26:25Z)
• On the Robustness of Transformers against Context Hijacking for Linear Classification [26.1838836907147]
  Transformer-based Large Language Models (LLMs) have demonstrated powerful in-context learning capabilities.<n>They can be disrupted by factually correct context, a phenomenon known as context hijacking.<n>We show that a well-trained deeper transformer can achieve higher robustness, which aligns with empirical observations.
  arXiv  Detail & Related papers  (2025-02-21T17:31:00Z)
• On the Role of Depth and Looping for In-Context Learning with Task Diversity [69.4145579827826]
  We study in-context learning for linear regression with diverse tasks. We show that multilayer Transformers are not robust to even distributional shifts as small as $O(e-L)$ in Wasserstein distance.
  arXiv  Detail & Related papers  (2024-10-29T03:27:56Z)
• Interpreting Affine Recurrence Learning in GPT-style Transformers [54.01174470722201]
  In-context learning allows GPT-style transformers to generalize during inference without modifying their weights. This paper focuses specifically on their ability to learn and predict affine recurrences as an ICL task. We analyze the model's internal operations using both empirical and theoretical approaches.
  arXiv  Detail & Related papers  (2024-10-22T21:30:01Z)
• Transformers are Efficient Compilers, Provably [11.459397066286822]
  Transformer-based large language models (LLMs) have demonstrated surprisingly robust performance across a wide range of language-related tasks.<n>In this paper, we take the first steps towards a formal investigation of using transformers as compilers from an expressive power perspective.<n>We introduce a representative programming language, Mini-Husky, which encapsulates key features of modern C-like languages.
  arXiv  Detail & Related papers  (2024-10-07T20:31:13Z)
• Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers [8.908747084128397]
  We introduce the temporal counting logic $textsfK_textt$[#] alongside the RASP variant $textsfC-RASP$.<n>We show they are equivalent to each other, and that together they are the best-known lower bound on the formal expressivity of future-masked soft attention transformers with unbounded input size.
  arXiv  Detail & Related papers  (2024-04-05T20:36:30Z)
• How Transformers Learn Causal Structure with Gradient Descent [44.31729147722701]
  Self-attention allows transformers to encode causal structure. We introduce an in-context learning task that requires learning latent causal structure. We show that transformers trained on our in-context learning task are able to recover a wide variety of causal structures.
  arXiv  Detail & Related papers  (2024-02-22T17:47:03Z)
• AlgoFormer: An Efficient Transformer Framework with Algorithmic Structures [80.28359222380733]
  We design a novel transformer framework, dubbed AlgoFormer, to empower transformers with algorithmic capabilities.<n>In particular, inspired by the structure of human-designed learning algorithms, our transformer framework consists of a pre-transformer that is responsible for task preprocessing.<n>Some theoretical and empirical results are presented to show that the designed transformer has the potential to perform algorithm representation and learning.
  arXiv  Detail & Related papers  (2024-02-21T07:07:54Z)
• Why "classic" Transformers are shallow and how to make them go deep [4.520356456308492]
  Key innovation in Transformer is a Self-Attention mechanism designed to capture contextual information. extending the original Transformer design to models of greater depth has proven exceedingly challenging. We propose a new strategy of surgically removing excessive similarity in contrast to the existing approach of diminishing the SA mechanism explicitly or implicitly.
  arXiv  Detail & Related papers  (2023-12-11T07:49:16Z)
• On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
  We show that saturated transformers transcend the limitations of hard-attention transformers. The jump from hard to saturated attention can be understood as increasing the transformer's effective circuit depth by a factor of $O(log n)$.
  arXiv  Detail & Related papers  (2021-06-30T17:09:47Z)
• Thinking Like Transformers [64.96770952820691]
  We propose a computational model for the transformer-encoder in the form of a programming language. We show how RASP can be used to program solutions to tasks that could conceivably be learned by a Transformer. We provide RASP programs for histograms, sorting, and Dyck-languages.
  arXiv  Detail & Related papers  (2021-06-13T13:04:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.