mlsanityData to 14 Oct 2026

Limit Analysis for Symbolic Multi-step Reasoning Tasks with Information Propagation Rules Based on Transformers

arXiv 2509.23178 ↗First posted 27 Sep 2025cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

Transformers are able to perform reasoning tasks, however the intrinsic mechanism remains widely open. In this paper we propose a set of information propagation rules based on Transformers and utilize symbolic reasoning tasks to theoretically analyze the limit reasoning steps. We show that the limit number of reasoning steps is between O(3L-1) and O(2L-1) for a model with L attention layers in a single-pass.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 37 of its 46 references that are in the map. First posted on arXiv 27 Sep 2025.

Builds on

37 of 46 references.

References · 37

  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. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  5. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  6. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,211
  7. 2022Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 smallcited by 1,165
  8. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 715
  9. 2021Transformers Can Do Bayesian Inferencecited by 360
  10. 2018Generating Wikipedia by Summarizing Long Sequencescited by 335
  11. 2023Function Vectors in Large Language Modelscited by 308
  12. 2019Compositionality decomposed: how do neural networks generalise?cited by 265
25 more
  1. 2022Emergent Analogical Reasoning in Large Language Modelscited by 240
  2. 2023Localizing Model Behavior with Path Patchingcited by 195
  3. 2024Do Large Language Models Latently Perform Multi-Hop Reasoning?cited by 169
  4. 2023Birth of a Transformer: A Memory Viewpointcited by 161
  5. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  6. 2024The Evolution of Statistical Induction Heads: In-Context Learning Markov Chainscited by 118
  7. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 118
  8. 2024Round and Round We Go! What makes Rotary Positional Encodings useful?cited by 115
  9. 2024Transformers, parallel computation, and logarithmic depthcited by 79
  10. 2024Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimalitycited by 74
  11. 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
  12. 2020Phase diagram for two-layer ReLU neural networks at infinite-width limitcited by 67
  13. 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
  14. 2024Understanding and Patching Compositional Reasoning in LLMscited by 46
  15. 2025Learning Compositional Functions with Transformers from Easy-to-Hard Datacited by 36
  16. 2024Making Long-Context Language Models Better Multi-Hop Reasonerscited by 26
  17. 2025Back Attention: Understanding and Enhancing Multi-Hop Reasoning in Large Language Modelscited by 23
  18. 2024Distributional reasoning in LLMs: Parallel reasoning processes in multi-hop reasoningcited by 21
  19. 2024What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Taskscited by 19
  20. 2025An overview of condensation phenomenon in deep learningcited by 17
  21. 2024On the Diagram of Thoughtcited by 16
  22. 2024Understanding the Language Model to Solve the Symbolic Multi-Step Reasoning Problem from the Perspective of Buffer Mechanismcited by 15
  23. 2025An Analysis for Reasoning Bias of Language Models with Small Initializationcited by 13
  24. 2024Anchor function: a type of benchmark functions for studying language modelscited by 11
  25. 2024II-MMR: Identifying and Improving Multi-modal Multi-hop Reasoning in Visual Question Answeringcited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Multi-head Transformers Provably Learn Symbolic Multi-step Reasoning via Gradient Descent
  2. 2025Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization
  3. 2025Analyzing the Power of Chain of Thought through Memorization Capabilities
  4. 2024Reasoning in Transformers -- Mitigating Spurious Correlations and Reasoning Shortcuts
  5. 2025Mechanistic Unveiling of Transformer Circuits: Self-Influence as a Key to Model Reasoning
  6. 2025Hierarchical Reasoning Models: Perspectives and Misconceptions
  7. 2026Revealing Algorithmic Deductive Circuits for Logical Reasoning
  8. 2026To See the Unseen: on the Generalization Ability of Transformers in Symbolic Reasoning