Limit Analysis for Symbolic Multi-step Reasoning Tasks with Information Propagation Rules Based on Transformers
Qin Tian 2, † \dagger , Yuhan Chen 3, † \dagger , Zhiwei Wang 1,2, † \dagger , Zhi-Qin John Xu 1,2, ∗ \ast 1 Institute of Natural Sciences, MOE-LSC, Shanghai Jiao Tong University 2 School of Mathematical Sciences, Shanghai Jiao Tong University 3 School of Mathematics and Statistics, Wuhan University · 2025
Read Limit Analysis for Symbolic Multi-step Reasoning Tasks with Information Propagation Rules Based on Transformers by Qin Tian 2, † \dagger , Yuhan Chen 3, † \dagger , Zhiwei Wang 1,2, † \dagger , Zhi-Qin John Xu 1,2, ∗ \ast 1 Institute of Natural Sciences, MOE-LSC, Shanghai Jiao Tong University 2 School of Mathematical Sciences, Shanghai Jiao Tong University 3 School of Mathematics and Statistics, Wuhan University (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-23178.txt.
Introduction
How many reasoning steps can a transformer take in one pass? Tian Qin and 3 co-authors bound that limit with information propagation rules. Their rules describe how data moves through attention layers. Symbolic multi-step tasks serve as the test bed for the theory. For a model with a set number of attention layers, the step limit sits in a stated range.
The range runs between two exponential bounds in the layer count. The result gives a clean yardstick for single-pass reasoning depth. It speaks to why deeper stacks unlock longer chains of thought. The mechanism behind transformer reasoning stays open, and this narrows it.
Catalog record
| CREATOR | Qin Tian 2, † \dagger , Yuhan Chen 3, † \dagger , Zhiwei Wang 1,2, † \dagger , Zhi-Qin John Xu 1,2, ∗ \ast 1 Institute of Natural Sciences, MOE-LSC, Shanghai Jiao Tong University 2 School of Mathematical Sciences, Shanghai Jiao Tong University 3 School of Mathematics and Statistics, Wuhan University |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-23178
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Limit Analysis for Symbolic Multi-step Reasoning Tasks with Information Propagation Rules Based on Transformers Qin Tian 2, † \dagger , Yuhan Chen 3, † \dagger , Zhiwei Wang 1,2, † \dagger , Zhi-Qin John Xu 1,2, ∗ \ast 1 Institute of Natural Sciences, MOE-LSC, Shanghai Jiao Tong University 2 School of Mathematical Sciences, Shanghai Jiao Tong University 3 School of Mathematics and Statistics, Wuhan University † \dagger These authors contributed equally as co-first authors. ∗ \ast Corresponding author: [email protected] Abstract 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 ( 3 L − 1 ) O(3^{L-1}) and O ( 2 L − 1 ) O(2^{L-1}) for a model with L L attention layers in a single-pass. 1 Introduction The transformer architecture introduced by ( Vaswani et al. 2017 ) has demonstrated capabilities across a wide range of tasks ( Liu et al. 2018 ; Devlin et al. 2019 ; Radford et al. 2019 ; Touvron et al. 2023 ; OpenAI 2023 ) , showing particularly significant progress in logical reasoning. These models can not only solve complex mathematical problems Davies et al. 2021 but have also reached performance levels comparable to top human contestants in the International Mathematical Olympiad (IMO) ( Trinh et al. 2024 ) . The reasoning capabilities of large language models are fundamentally shaped by the thinking strategies they employ. Widely adopted approaches include Chain-of-Thought (CoT) ( Wei et al. 2022 ) , Tree-of-Thought (ToT) ( Yao et al. 2023 ) , and Diagram-of-Thought (DoT) ( Zhang et al. 2024a ) . While these strategies substantially improve multi-step logical reasoning accuracy by prompting models to generate explicit intermediate reasoning steps, they often exhibit an over-thinking phenomenon that consumes excessive computational resources and increases response time. This inefficiency highlights a critical question: what is the intrinsic single-pass reasoning capacity of these models? Specifically, how many reasoning steps can a model effectively execute without requiring iterative prompting or external scaffolding? Based on the Transformer and the information propagation rules, we utilize a common symbolic multi-steps reasoning task to show that the limit of reasoning steps in single-pass of an L-layer Transformer is between O(3^{L-1}) and O(2^{L-1}) . The key ingredient is that, i) in one layer, tokens parallelly perform reasoning; ii) each position can store information of multiple tokens in different sub-linear space. Building on established Transformer architectures and information propagation mechanisms from prior research, we employ symbolic multi-step reasoning tasks to investigate the theoretical limits of reasoning depth achievable in a single forward pass through an L-layer Transformer. Our analysis demonstrates that the maximum number of reasoning steps is between O(3^{L-1}) and O(2^{L-1}) . This result stems from two key architectural properties: (i) tokens execute reasoning operations in parallel within each layer, and (ii) each embedding in a hidden layer can encode information from multiple tokens across distinct sublinear spaces. We also perform experiments to support our analysis. For 3 -layer Transformers, we find that it requires large hidden dimensions to execute parallel reasoning. The maximum reasoning steps have lower and upper bounds. 2 Transformer and Reasoning Mechanism 2.1 Transformer Architecture We investigate a decoder-only Transformer with L -layer attention blocks. For integer n , given any sequence (x_{i})_{1\leqslant i\leqslant n} , we denote its one-hot encoding 1 1 1 One-hot encoding is a technique that represents categorical data as binary vectors, where only one bit is set to 1 others are set to 0. as {\bm{X}}^{\mathrm{in}}\in\mathbb{R}^{n\times d} with d as the dictionary size. The model first applies an embedding layer including both token embedding and positional encoding to obtain the input representation as {\bm{X}}^{(0)}={{\bm{X}}^{\mathrm{emb}}}+{\bm{X}}^{\mathrm{pos}}\in\mathbb{R}^{n\times d_{m}} . Moreover, we denote the set of word embeddings of each word in the dictionary as W^{E} . We shall use the single-head attention in each layer which is computed as follows: \displaystyle\mathcal{A}^{(l)}({\bm{X}}^{(l)}) \displaystyle=\operatorname{SoftMax}\left(\frac{\mathrm{mask}({\bm{X}}^{(l)}{\bm{W}}^{q(l)}{\bm{W}}^{k(l),\mathsf{T}}{\bm{X}}^{(l),\mathsf{T}})}{\sqrt{d_{k}}}\right), \displaystyle\quad{\bm{X}}^{\mathrm{qkv}(l)} \displaystyle=\mathcal{A}^{(l)}({{\bm{X}}}^{(l)}){{\bm{X}}}^{(l)}{\bm{W}}^{v(l)}{\bm{W}}^{o(l)}, where 0\leqslant l\leqslant L and \tilde{\sigma} is the softmax operator. For simplicity of expression, we will abbreviate {\bm{W}}^{q(l)}{\bm{W}}^{k(l),\mathsf{T}} as {\bm{W}}^{qk(l)} and {\bm{W}}^{v(l)}{\bm{W}}^{o(l),\mathsf{T}} as {\bm{W}}^{vo(l)} in the following text. Also, we ignore the normalization coefficient \sqrt{d_{k}} in later sections for notational simplicity. The output of the (l+1) -th layer is obtained as: {\bm{X}}^{\mathrm{ao}(l)}={\bm{X}}^{(l)}+{\bm{X}}^{\mathrm{qkv}(l)},\ \ {\bm{X}}^{(l+1)}=\operatorname{LayerNorm}(f^{(l)}({{\bm{X}}}^{\mathrm{ao}(l)})+{\bm{X}}^{\mathrm{ao}(l)}), where f^{(l)}(\cdot) represents the feedforward neural network of the (l+1) -th layer. The final output (in the form of token indices within the vocabulary) is obtained as: {\bm{Y}}=\operatorname{SoftMax}({{\bm{X}}}^{(L)}_{n}{\bm{W}}^{p})\in\mathbb{R}^{d}. 2.2 Induction Reasoning Mechanism Based on numerous works on In-Context Learning, Induction Heads ( Brown et al. 2020 ; Garg et al. 2022 ; Bietti et al. 2024 ; Nichani et al. 2024 ) , and recent studies on multi-step reasoning ( Wang et al. 2025a ; Yu et al. 2025 ) , the reasoning capability of Transformers can be largely attributed to a mechanism called the Buffer Mechanism for storing diverse information, together with adjacent position matching and same token matching for achieving information matching and transmission. Buffer Mechanism The Buffer Mechanism is a crucial way for Transformers to store multiple pieces of information ( Wang et al. 2025a ) . Specifically, the interaction of information among tokens in a Transformer occurs in the attention module. Figure 1 (a) illustrates the information flow of a 3-layer model performing 2-step reasoning, i.e., given a sentence of the form “… [a][b] … [b][c] … [a] ”, the model is required to output [c] . The dashed lines denote residual connections, while the solid lines denote information propagation induced by the attention mechanism. When a token (e.g., [b] ) attends to a previous token (e.g., [a] ), its next-layer state is not simply [a]+[b] , but rather \texttt{[a]}{\bm{W}}^{vo}+\texttt{[b]} . In other words, the Transformer stores the two pieces of information into subspaces spanned by different matrices through a linear transformation. Adjacent Position Matching Similar to humans, language models rely heavily on the immediately preceding word when predicting the next word ( Barbero et al. 2024 ) . That is, the model can leverage positional encodings to establish connections between adjacent tokens. In fact, constructing such an attention weight matrix is not difficult. Assuming the positional encodings approximately satisfy {\bm{p}}_{i}^{\mathsf{T}}{\bm{p}}_{i}=1,{\bm{p}}_{i}^{\mathsf{T}}{\bm{p}}_{j}=0,i\neq j , it suffices to construct: {\bm{W}}^{qk}=\sum_{i=1}^{[l_{\text{seq}}/2]}{\bm{p}}_{2i}{\bm{p}}_{2i-1}^{\mathsf{T}}, (1) (x_{2i}+{\bm{p}}_{2i}){\bm{W}}^{qk}(x_{2i-1}+{\bm{p}}_{2i-1})^{\mathsf{T}}\approx 1, (2) Clearly, by this method, we can construct attention between any adjacent tokens of fixed length. However, due to the inherent diversity of language tasks, only the attention between the most adjacent pair is the most salient. We refer to this mechanism as adjacent position matching. Same Token Matching Same token matching is the most essential mechanism within induction heads. Its existence grants Transformers strong out-of-distribution generalization ability. As shown in the Figure 1 (a), because both nodes in the first layer contain the same information [a] , they can attend to each other via the same token matching mechanism. Specifically, it suffices that the weight matrices satisfy {\bm{W}}^{qk(1)}{\bm{W}}^{vo(0),\mathsf{T}}=I , in which case q(\texttt{[a]})k(\texttt{[a]}{\bm{W}}^{vo(0)}+\texttt{[b]})^{\mathsf{T}}\approx\texttt{[a]}{\bm{W}}^{qk(1)}{\bm{W}}^{vo(0),\mathsf{T}}\texttt{[a]}^{\mathsf{T}}=\texttt{[a][a]}^{\mathsf{T}}\approx 1, (3) That is, the final token node will allocate nearly all of its attention to the previous node containing the same information [a] , thereby transmitting [b]