# Compositional Reasoning with Transformers, RNNs, and Chain of Thought arXiv: https://arxiv.org/abs/2503.01544 ยท HTML: https://mlsanity.com/paper/2503.01544/ ## Key facts - Cited by 6 papers in the map (data through 14 Oct 2026). - Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. - Builds on 30 of its 47 references that are in the map. - First posted on arXiv 3 Mar 2025. ## Placed in - LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/) ## Builds on (most cited first, 30 of 30) - [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023) - [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023) - [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022) - [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021) - [Prompt Programming for Large Language Models: Beyond the Few-Shot Paradigm](https://mlsanity.com/paper/2102.07350/) (2021) - [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019) - [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023) - [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019) - [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022) - [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024) - [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023) - [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024) - [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022) - [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024) - [CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text](https://mlsanity.com/paper/1908.06177/) (2019) - [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021) - [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023) - [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023) - [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021) - [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022) - [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022) - [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024) - [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020) - [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019) - [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017) - [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024) - [On the Computational Power of RNNs](https://mlsanity.com/paper/1906.06349/) (2019) - [Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers](https://mlsanity.com/paper/2502.02393/) (2025) - [When Can Transformers Count to n?](https://mlsanity.com/paper/2407.15160/) (2024) - [On the Benefits of Rank in Attention Layers](https://mlsanity.com/paper/2407.16153/) (2024) ## Built on by (most cited first, 6 of 6) - [A Survey of Efficient Reasoning for Large Reasoning Models: Language, Multimodality, and Beyond](https://mlsanity.com/paper/2503.21614/) (2025) - [When Is Compositional Reasoning Learnable from Verifiable Rewards?](https://mlsanity.com/paper/2602.07992/) (2026) - [How does Chain of Thought decompose complex tasks?](https://mlsanity.com/paper/2604.08872/) (2026) - [Compositional Reasoning Depth Predicts Clinical AI Failure: Empirical Evidence Consistent with Transformer Compositionality Limits in Electronic Health Record Question Answering](https://mlsanity.com/paper/2606.16890/) (2026) - [On the Computational Complexity of Structural Generalization](https://mlsanity.com/paper/2607.19573/) (2026) - [AgentVidBench: A Multi-Hop Video Question Answering Benchmark for Evaluating MLLM Agents](https://mlsanity.com/paper/2609.21386/) (2026) ## Abstract (arXiv) It is well understood that different neural network architectures are suited to different tasks, but is there always a single best architecture for a given task? We compare the expressive power of transformers, RNNs, and transformers with chain of thought tokens on a simple and natural class of tasks we term Compositional Reasoning Questions (CRQ). This family captures multi-step problems with tree-like compositional structure, such as evaluating Boolean formulas. We prove that under standard hardness assumptions, none of these three architectures is capable of solving CRQs unless some hyperparameter (depth, embedding dimension, and number of chain of thought tokens, respectively) grows with the size of the input. We then provide constructions for solving CRQs with each architecture. For transformers, our construction uses depth that is logarithmic in the problem size. For RNNs, logarithmic embedding dimension is necessary and sufficient, so long as the inputs are provided in a certain order. For transformers with chain of thought, our construction uses n CoT tokens for input size n. These results show that, while CRQs are inherently hard, there are several different ways for language models to overcome this hardness. Even for a single class of problems, each architecture has strengths and weaknesses, and none is strictly better than the others.