mlsanityData to 14 Oct 2026

Theoretical limitations of multi-layer Transformer

arXiv 2412.02975 ↗First posted 4 Dec 2024cs.LG cs.AI cs.CCcited by 45

Not on the map. Why?

Abstract (arXiv)

Transformers, especially the decoder-only variants, are the backbone of most modern large language models; yet we do not have much understanding of their expressive power except for the simple 1-layer case. Due to the difficulty of analyzing multi-layer models, all previous work relies on unproven complexity conjectures to show limitations for multi-layer Transformers. In this work, we prove the first textitunconditional lower bound against multi-layer decoder-only transformers. For any constant L, we prove that any L-layer decoder-only transformer needs a polynomial model dimension (nOmega(1)) to perform sequential composition of L functions over an input of n tokens. As a consequence, our results give: (1) the first depth-width trade-off for multi-layer transformers, exhibiting that the L-step composition task is exponentially harder for L-layer models compared to (L+1)-layer ones; (2) an unconditional separation between encoder and decoder, exhibiting a hard task for decoders that can be solved by an exponentially shallower and smaller encoder; (3) a provable advantage of chain-of-thought, exhibiting a task that becomes exponentially easier with chain-of-thought. On the technical side, we propose the multi-party textitautoregressive textitcommunication textitmodel that captures the computation of a decoder-only Transformer. We also introduce a new proof technique that finds a certain textitindistinguishable textitdecomposition of all possible inputs iteratively for proving lower bounds in this model. We believe our new communication model and proof technique will be helpful to further understand the computational power of transformers.

Key facts. Cited by 45 papers in the map (data through 14 Oct 2026). Builds on 50 of its 80 references that are in the map. First posted on arXiv 4 Dec 2024.

Builds on

50 of 80 references.

References · 50

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2023GPT-4 Technical Reportcited by 18,396
  5. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  6. 2024Gemini 1.5: Unlocking multimodal understanding across millions of tokens of contextcited by 3,224
  7. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
  8. 2022Emergent Abilities of Large Language Modelscited by 2,512
  9. 2022Measuring and Narrowing the Compositionality Gap in Language Modelscited by 1,075
  10. 2016Error bounds for approximations with deep ReLU networkscited by 574
  11. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 503
  12. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 320
38 more
  1. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  2. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  3. 2023Physics of Language Models: Part 3.1, Knowledge Storage and Extractioncited by 270
  4. 2022Transformers Learn Shortcuts to Automatacited by 268
  5. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  6. 2016Benefits of depth in neural networkscited by 250
  7. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 216
  8. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  9. 2015The Power of Depth for Feedforward Neural Networkscited by 183
  10. 2024Do Large Language Models Latently Perform Multi-Hop Reasoning?cited by 169
  11. 2023Representational Strengths and Limitations of Transformerscited by 133
  12. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
  13. 2023A Theory for Emergence of Complex Skills in Language Modelscited by 113
  14. 2024Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Processcited by 108
  15. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  16. 2023Physics of Language Models: Part 1, Learning Hierarchical Language Structurescited by 83
  17. 2016Why Deep Neural Networks for Function Approximation?cited by 82
  18. 2024Transformers, parallel computation, and logarithmic depthcited by 79
  19. 2024RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrievalcited by 64
  20. 2024On Limitations of the Transformer Architecturecited by 63
  21. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 59
  22. 2020RNNs can generate bounded hierarchical languages with optimal memorycited by 59
  23. 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
  24. 2017Depth Separation for Neural Networkscited by 46
  25. 2023Decoder-Only or Encoder-Decoder? Interpreting Language Model as a Regularized Encoder-Decodercited by 44
  26. 2020The Depth-to-Width Interplay in Self-Attentioncited by 42
  27. 2023The Impact of Depth on Compositional Generalization in Transformer Language Modelscited by 38
  28. 2024Encoder vs Decoder: Comparative Analysis of Encoder and Decoder Language Models on Multilingual NLU Taskscited by 34
  29. 2024One-layer transformers fail to solve the induction heads taskcited by 32
  30. 2023Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammarscited by 30
  31. 2019Depth Separations in Neural Networks: What is Actually Being Separated?cited by 27
  32. 2024Mixture of Parrots: Experts improve memorization more than reasoningcited by 21
  33. 2024ALPINE: Unveiling the Planning Capability of Autoregressive Learning in Language Modelscited by 18
  34. 2020Neural Networks with Small Weights and Depth-Separation Barrierscited by 17
  35. 2020Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depthcited by 13
  36. 2024ENTP: Encoder-only Next Token Predictioncited by 5
  37. 2016Polynomial Representations of Threshold Functions and Algorithmic Applicationscited by 3
  38. 2021Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemmacited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 21; 2026: 23.

45 papers.

Sort:

By area:

  1. 2025When More is Less: Understanding Chain-of-Thought Length in LLMscited by 183
  2. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
  3. 2025(Im)possibility of Automated Hallucination Detection in Large Language Modelscited by 15
  4. 2025Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalizationcited by 14
  5. 2025The Serial Scaling Hypothesiscited by 13
  6. 2025Knee-Deep in C-RASP: A Transformer Depth Hierarchycited by 12
  7. 2025Language models can learn implicit multi-hop reasoning, but only if they have lots of training datacited by 11
  8. 2025Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descentcited by 8
  9. 2025Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformerscited by 8
  10. 2025Understanding Input Selectivity in Mamba: Impact on Approximation Power, Memorization, and Associative Recall Capacitycited by 7
  11. 2025Ehrenfeucht-Haussler Rank and Chain of Thoughtcited by 6
  12. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thoughtcited by 6
33 more
  1. 2025Chain-of-Thought Tokens are Computer Program Variablescited by 6
  2. 2025Transformers Meet In-Context Learning: A Universal Approximation Theorycited by 6
  3. 2026Parity, Sensitivity, and Transformerscited by 5
  4. 2025Efficient Turing Machine Simulation with Transformerscited by 4
  5. 2026Expressivity-Efficiency Tradeoffs for Hybrid Sequence Modelscited by 4
  6. 2024Lower bounds on transformers with infinite precisioncited by 3
  7. 2025Concise One-Layer Transformers Can Do Function Evaluation (Sometimes)cited by 3
  8. 2025From Sequence to Structure: Uncovering Substructure Reasoning in Transformerscited by 3
  9. 2025Fast attention mechanisms: a tale of parallelismcited by 3
  10. 2026Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidthcited by 3
  11. 2026Continuous Latent Contexts Enable Efficient Online Learning in Transformerscited by 3
  12. 2025Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scalingcited by 2
  13. 2025Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differentlycited by 2
  14. 2026The Seriality Gap in Video Diffusion Modelscited by 2
  15. 2026Indexing: the Beginning and the Endcited by 2
  16. 2025CompoST: A Benchmark for Analyzing the Ability of LLMs To Compositionally Interpret Questions in a QALD Settingcited by 1
  17. 2026A model of errors in transformerscited by 1
  18. 2026A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attentioncited by 1
  19. 2026Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformerscited by 1
  20. 2026Algorithmic Task Capture, Computational Complexity, and Inductive Bias of Infinite Transformerscited by 1
  21. 2026On the Expressive Power and Limitations of Multi-Layer SSMscited by 1
  22. 2026The two clocks and the innovation window: When and how generative models learn rulescited by 1
  23. 2026Attention-based representations for multi-task computationcited by 1
  24. 2026On the Computational Hardness of Transformerscited by 0
  25. 2026When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compressioncited by 0
  26. 2026The Power of Power Law: Asymmetry Enables Compositional Reasoningcited by 0
  27. 2026A Hierarchical Language Model with Predictable Scaling Laws and Provable Benefits of Reasoningcited by 0
  28. 2026Frontier Language Models Struggle to Copy: Text Can Be Better Viewed in 2Dcited by 0
  29. 2026When Chain-of-Thought Helps and When It Hurts: An Empirical Investigation of the Serial-Depth Bottleneck in LLM Reasoningcited by 0
  30. 2026On the Expressive Power of Transformerscited by 0
  31. 2026Resilient Concurrent Causal Discovery for Topological Event Sequencescited by 0
  32. 2026VC Dimension and Expressivity of Real-Valued Transformerscited by 0
  33. 2026On the Trade-off Between Information Loss and Generalization in Sparse Attentioncited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Exact Expressive Power of Transformers with Padding
  2. 2023The Expressive Power of Transformers with Chain of Thought
  3. 2025Equivalence of Context and Parameter Updates in Modern Transformer Blocks
  4. 2024Transformers are Multi-State RNNs
  5. 2025The Impossibility of Inverse Permutation Learning in Transformer Models
  6. 2025BitSkip: An Empirical Analysis of Quantization and Early Exit Composition in Transformers
  7. 2024MLKV: Multi-Layer Key-Value Heads for Memory Efficient Transformer Decoding
  8. 2024Relaxed Recursive Transformers: Effective Parameter Sharing with Layer-wise LoRA