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

arXiv: https://arxiv.org/abs/2509.23178 · HTML: https://mlsanity.com/paper/2509.23178/

## 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 (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [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)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 small](https://mlsanity.com/paper/2211.00593/) (2022)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [Transformers Can Do Bayesian Inference](https://mlsanity.com/paper/2112.10510/) (2021)
- [Generating Wikipedia by Summarizing Long Sequences](https://mlsanity.com/paper/1801.10198/) (2018)
- [Function Vectors in Large Language Models](https://mlsanity.com/paper/2310.15213/) (2023)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [Emergent Analogical Reasoning in Large Language Models](https://mlsanity.com/paper/2212.09196/) (2022)
- [Localizing Model Behavior with Path Patching](https://mlsanity.com/paper/2304.05969/) (2023)
- [Do Large Language Models Latently Perform Multi-Hop Reasoning?](https://mlsanity.com/paper/2402.16837/) (2024)
- [Birth of a Transformer: A Memory Viewpoint](https://mlsanity.com/paper/2306.00802/) (2023)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains](https://mlsanity.com/paper/2402.11004/) (2024)
- [How Transformers Learn Causal Structure with Gradient Descent](https://mlsanity.com/paper/2402.14735/) (2024)
- [Round and Round We Go! What makes Rotary Positional Encodings useful?](https://mlsanity.com/paper/2410.06205/) (2024)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimality](https://mlsanity.com/paper/2402.19442/) (2024)
- [Generalization on the Unseen, Logic Reasoning and Degree Curriculum](https://mlsanity.com/paper/2301.13105/) (2023)
- [Phase diagram for two-layer ReLU neural networks at infinite-width limit](https://mlsanity.com/paper/2007.07497/) (2020)
- [Do Transformers Parse while Predicting the Masked Word?](https://mlsanity.com/paper/2303.08117/) (2023)
- [Understanding and Patching Compositional Reasoning in LLMs](https://mlsanity.com/paper/2402.14328/) (2024)
- [Learning Compositional Functions with Transformers from Easy-to-Hard Data](https://mlsanity.com/paper/2505.23683/) (2025)
- [Making Long-Context Language Models Better Multi-Hop Reasoners](https://mlsanity.com/paper/2408.03246/) (2024)
- [Back Attention: Understanding and Enhancing Multi-Hop Reasoning in Large Language Models](https://mlsanity.com/paper/2502.10835/) (2025)
- [Distributional reasoning in LLMs: Parallel reasoning processes in multi-hop reasoning](https://mlsanity.com/paper/2406.13858/) (2024)

## 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.