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

## Abstract

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^11One-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](https://arxiv.org/html/2509.23178v1#S2.F1)(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](https://arxiv.org/html/2509.23178v1#S2.F1)(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] to the final node in the next layer. In this way, a single-step reasoning is achieved. Multi-step reasoning follows the same principle.

Figure: Figure 1: Illustration of linear reasoning and parallel reasoning.
Refer to caption: linear_and_parallel_reasoning.png

### 2.3 Parallel Reasoning

However, we note that the above-described mode, where each layer performs only one step of reasoning, is far from the upper limit of the Transformer model. As shown in Figure [1](https://arxiv.org/html/2509.23178v1#S2.F1)(b), adjacent position matching and same token matching can occur multiple times within a single layer, thereby enabling even shallow Transformer models to perform multi-step reasoning. We refer to this phenomenon as parallel reasoning. The central question considered in this paper is: given only adjacent position matching and same token matching, what are the upper and lower bounds of the parallel reasoning step that a transformer with $L$ layers attention blocks can perform?

## 3 Informal Theorems

To investigate the above question, we first consider the simplest case in which all reasoning relations are arranged sequentially. As shown in Figure [2](https://arxiv.org/html/2509.23178v1#S3.F2)(a), the information flow of reasoning in this setting exhibits a clear “binary tree” structure. It then follows directly that the reasoning steps scale as $O(2^{L-1})$. In what follows, we will provide a rigorous proof of this result by mathematical induction. We note that permuting the order of reasoning pairs within the sequential arrangement does not disrupt the flow of sequential reasoning. Hence, when logical relations are arranged in sequence, the reasoning steps of a Transformer constitute the lower bound among all possible cases.

On the other hand, we observe that for a 3-layer model, when the data are arranged as illustrated in Figure [2](https://arxiv.org/html/2509.23178v1#S3.F2)(b), the final layer carries the maximum amount of information. The data in this case exhibit an evident fractal structure. The advantage of such a configuration is that each local terminal node can simultaneously match two preceding nodes by leveraging both the maximum and minimum information it carries, thereby expanding its information content. Consequently, the reasoning steps scale as $O(3^{L-1})$. Therefore, we arrive at the following informal conclusion:

Figure: Figure 2: Example of lower bound and upper bound of parallel reasoning.
Refer to caption: example_lower_and_upper_bound.png

###### Theorem 3.1 (Informal Corollary 6.4 ) .

The maximal number of reasoning steps a transformer with $L$ layers attention blocks can perform has a lower bound $O(2^{L-1})$ and an upper bound $O(3^{L-1})$.

Next, we will provide a formal statement of the problem and a rigorous proof of the conclusion.

###### Theorem 3.1 (Informal Corollary 6.4 ) .

## 4 Symbolic Reasoning Task

In this section, we give a brief introduction to the reasoning task and some related definitions. Moreover, we shall introduce the rules of information propagation.

A reasoning task typically involves a question and an answer to that question, along with the rule and process to get the answer. For example, given $A_{1}\subseteq A_{2}$ and $A_{2}\subseteq A_{3}$, the question is the relation of $A_{1}$ and $A_{3}$, and the answer is $A_{1}\subseteq A_{3}$. We shall use a more symbolic way to express reasoning tasks as in the following example in figure [3](https://arxiv.org/html/2509.23178v1#S4.F3).

Figure: Figure 3: Three steps reasoning task. One step reasoning leads to $2$, two steps reasoning leads to $3$.

We use a sequence $(1,2,2,3,3,4)$ to denote this reasoning task. Indeed, this sequence is composed of three bigrams $(1,2)$, $(2,3)$, $(3,4)$, and each bigram represents one step of reasoning. We call these bigrams reasoning pairs, which we will define below.

###### Definition 4.1 .

A reasoning pair is an element in $\mathbb{Z}^{2}$ of the form $\bm{a}_{i}=(\bm{a}^{1}_{i},\bm{a}^{2}_{i})$ where $i\in\mathbb{Z}$, $\bm{a}^{1}_{i},\ \bm{a}^{2}_{i}\in\mathbb{Z}$ and $\bm{a}^{1}_{i}\neq\bm{a}^{2}_{i}$.

The set of all reasoning pairs is denoted as $\mathcal{A}$. $a^{1}_{i}\rightarrow a^{2}_{I}$ represents one step of reasoning.

It is natural that we shall define the $s$ step reasoning chain as follows.

###### Definition 4.2 .

An $s$ step reasoning chain is a finite sequence $(\bm{a}_{i})_{1\leqslant i\leqslant s}$ with $\bm{a}_{i}\in\mathcal{A}$, and it shall satisfy the following conditions:

- •
$\bm{a}^{2}_{i}=\bm{a}^{1}_{i+1}$ for $1\leqslant i\leqslant s-1$;
- •
For any subsequence $(\bm{a}_{i_{m}})_{i_{m}\in\mathcal{I}}$ of $(\bm{a}_{i})_{1\leqslant i\leqslant s}$,
we have $\bm{a}^{1}_{\min\{\mathcal{I}\}}\neq\bm{a}^{2}_{\max\{\mathcal{I}\}}$ (no loop), where $\mathcal{I}$ is a subset of $\{1,2,\cdots,s\}$ containing at least two elements.

The first condition ensures that the reasoning chain does not break before the final step, and the second condition ensures that there is no loop of arbitrary size in the reasoning task.
For example, the sequence $((1,2),(2,3),(3,1))$ and $((1,2),(3,4),(4,5))$ are
not reasoning chains.

###### Remark 4.3 .

For notational simplicity, here and in the sequel, we shall write $(\bm{a}_{i})$ for $(\bm{a}_{i})_{i\in I}$ when the index set $I$ is clear from the context.

We shall also consider the case when the reasoning chain is of infinite length.

###### Definition 4.4 .

A sequence $(\bm{a}_{i})_{i\in\mathbb{Z}}$ is called a reasoning chain if it satisfies the following conditions:

- •
$\bm{a}_{i}\in\mathcal{A}$;
- •
$\bm{a}^{2}_{i}=\bm{a}^{1}_{i+1}$ for $i\in\mathbb{Z}$;
- •
For any subsequence $(\bm{a}_{i_{m}})_{i_{m}\in\mathcal{I}}$ of $(\bm{a}_{n})$, we have $\bm{a}^{1}_{\min\{\mathcal{I}\}}\neq\bm{a}^{2}_{\max\{\mathcal{I}\}}$, where $\mathcal{I}\subseteq\mathbb{Z}$ containing at least two elements.

Note that for any $i_{0},s\in\mathbb{Z}$, we can truncate the reasoning chain $(\bm{a}_{n})$ as follows

$$ $\bm{\tilde{a}}_{k}=\bm{a}_{i_{0}+k-1},\ 1\leqslant k\leqslant s$ (4) $$

to get an $s$ step reasoning chain $(\bm{\tilde{a}}_{k})$.

In practice, a sentence may consist of reasoning pairs which are not in order. Due to the mask condition which is common in the LLM, the order of reasoning pairs may influence the information propagation. To describe the order of these reasoning pairs and their relation to the reasoning chain, we need to introduce the concept of permutation.

###### Definition 4.5 .

A symmetric group $\operatorname{Sym}(S)$ on a countable set $S$ is a group whose elements are all bijective maps from $S$ to $S$ and whose group operation is that of function composition.

The elements of a symmetric group are called permutations. And we shall focus on $\operatorname{Sym}(\mathbb{Z})$.

###### Definition 4.6 .

Given a reasoning chain $(\bm{a}_{m})_{m\in\mathbb{Z}}$ and a permutation $\sigma\in\operatorname{Sym}(\mathbb{Z})$,
a sequence $(x_{i})_{i\in\mathbb{Z}}$ is called a reasoning sequence constructed from $(\bm{a}_{m})_{m\in\mathbb{Z}}$ and $\sigma$ if it satisfies:

$$ $x_{i}=\bm{a}_{\sigma(\lfloor\frac{i+1}{2}\rfloor)}^{2-(i\bmod 2)}.$ (5) $$

Also, $(\bm{a}_{m})_{m\in\mathbb{Z}}$ and $\sigma$ are called the constructing reasoning sequence and constructing permutation of $(x_{i})$, respectively.

When referring to a reasoning sequence $(x_{i})$, we are actually denoting the tuple $((x_{i}),(\bm{a}_{m}),\sigma)$.
Moreover, if $\sigma=\text{Id}$, then the reasoning sequence is called a sorted reasoning sequence.
Note that from the relation ([5](https://arxiv.org/html/2509.23178v1#S4.E5)) we also have

$$ $\bm{a}_{i}=\bm{a}_{\sigma(\sigma^{-1}(i))}=(x_{2\sigma^{-1}(i)-1},x_{2\sigma^{-1}(i)}),$ (6) $$

where $\sigma^{-1}$ is the inverse of $\sigma$ satisfying $\sigma\circ\sigma^{-1}=\sigma^{-1}\circ\sigma=\text{Id}\in\text{Sym}(\mathbb{Z})$.

###### Remark 4.7 .

In the definition of reasoning sequence we use the permutation to change the order of reasoning pairs which does not break the relation inside each reasoning pair. Moreover, no permutation should be applied to the original sequence $(x_{i})$. For example, the sequence $(1,2,2,3,3,4)$ can be $(2,3,3,4,1,2)$ or $(3,4,2,3,1,2)$ under some certain permutations. Both of these sequences are related to the reasoning chain $((1,2),(2,3),(3,4))$. However, it cannot be transformed into $(1,3,3,4,2,3)$ through any permutation that acts on reasoning pairs.

Figure: Figure 4: Relationship between reasoning chain and reasoning sequence.

Similarly, we shall also use a reasoning sequence of finite length.

###### Definition 4.8 .

An $s$ step reasoning sequence $(x_{i})_{1\leqslant i\leqslant 2s}$ with constructing reasoning chain $(\bm{a}_{m})_{1\leqslant m\leqslant s}$ and constructing permutation $\sigma$ is defined as:

$$ $x_{i}=\bm{a}_{\sigma(\lfloor\frac{i+1}{2}\rfloor)}^{2-(i\bmod 2)},\ \text{for }1\leqslant i\leqslant 2s.$ (7) $$

###### Example 4.9 .

The sequence $(x_{i})_{i\geqslant 1}=(\lfloor\frac{i}{2}\rfloor)_{i\geqslant 1}$ can be seen as a sorted reasoning sequence with constructing permutation $\sigma=\operatorname{Id}$ and constructing reasoning chain $((0,1),(1,2),(2,3),(3,4),\cdots)$.

###### Example 4.10 .

The sequence $(x_{i})=(1,2,6,3,2,4,3,5,4,6)$ with constructing reasoning chain $({\bm{a}}_{m})=((1,2),(2,4),(4,6),(6,3),(3,5))$ and constructing permutation $\sigma$ satisfying
$\sigma(1)=1,\ \sigma(2)=4,\ \sigma(3)=2,\ \sigma(4)=5,\ \sigma(5)=3$.
In this example,

$$ $\displaystyle{\bm{a}}_{1}=(1,2)=(x_{1},x_{2}),\ \ {\bm{a}}_{2}=(2,4)=(x_{5},x_{6}),\ \ {\bm{a}}_{3}=(4,6)=(x_{9},x_{10}).$ $$

Figure: Figure 5: Reasoning task represents by $(x_{i})$ in example [4.10](https://arxiv.org/html/2509.23178v1#S4.Thmtheorem10).

When considering a finite step reasoning sequence, the concept of reasoning start, which indicates where the reasoning task should begin, is also needed.
More specifically, we consider an $s$ step reasoning sequence $(x_{i})_{1\leqslant i\leqslant 2s}$ with constructing reasoning chain $({\bm{a}}{a}_{m})_{1\leqslant m\leqslant s}$ and constructing permutation $\sigma$. Then one more element $x_{2s+1}$ is added to the end of the reasoning sequence $(x_{i})$, and $x_{2s+1}={\bm{a}}^{1}_{m_{0}}$ for some ${\bm{a}}_{m_{0}}\in({\bm{a}}_{m})$.

###### Example 4.11 .

We set the sequence $(x_{i})=(1,2,6,3,2,4,3,5,4,6,4)$ with constructing reasoning chain $({\bm{a}}_{m})$ and constructing permutation $\sigma$ as in example [4.10](https://arxiv.org/html/2509.23178v1#S4.Thmtheorem10). In addition, the reasoning start is set to be $4$. Then one step reasoning result is $6$ and two steps reasoning result is $3$.

Next we define nodes which serves as containers of information.

###### Definition 4.12 .

A node corresponding to a reasoning sequence $(x_{i})$ is a set of two sets.
More specifically, for $i\in\mathbb{N}$,
an $l$th layer node is defined as $N^{l}_{i}=\{V^{l}_{i},I^{l}_{i}\}$
where $V^{l}_{i}$ is called a value set whose elements are integers, and $I^{l}_{i}\subseteq\mathbb{Z}$ is an index set. Also, we require that $V^{l}_{i}=\bigcup\limits_{i_{\alpha}\in I^{l}_{i}}\{x_{i_{\alpha}}\}$.

We define the information quantity of a node $N^{l}_{i}=\{V^{l}_{i},I^{l}_{i}\}$ as $C^{l}_{i}=|V^{l}_{i}|$.
Moreover, we denote $\mathcal{N}^{l}$ as the set of all $l$th layer nodes.

We denote the information propagation between two nodes as $N^{l+1}_{i}=N^{l}_{m}\star N^{l}_{i}$ where $N^{l}_{m}\star N^{l}_{i}:=\{V^{l}_{m}\cup V^{l+1}_{i},I^{l}_{m}\cup I^{l+1}_{i}\}$. The case $i\neq m$ represents the attention mechanism, more specifically, the node $N^{l}_{m}$ attends to the node $N^{l}_{i}$ and the result is stored in the node $N^{l+1}_{i}$. The case $i=m$ represents the residual connection, in which case $N^{l+1}_{i}=N^{l}_{i}$.
Moreover, there may be more than one node transmitting information to a node $N^{l}_{i}$. In this case, we denote the set of all such nodes as $N^{l}_{\mathcal{I}}\subseteq\mathcal{N}^{l}$ where $\mathcal{I}$ is some index set. The information propagation process in this case is then defined by $N^{l+1}_{i}=N^{l}_{\mathcal{I}}\star N^{l}_{i}:=\{\bigcup_{{i_{\alpha}\in\mathcal{I}}}V^{l}_{i_{\alpha}}\cup V^{l+1}_{i},\bigcup_{{i_{\alpha}\in\mathcal{I}}}I^{l}_{i_{\alpha}}\cup I^{l+1}_{i}\}$.

###### Definition 4.1 .

###### Definition 4.2 .

###### Remark 4.3 .

###### Definition 4.4 .

###### Definition 4.5 .

###### Definition 4.6 .

###### Remark 4.7 .

###### Definition 4.8 .

###### Example 4.9 .

###### Example 4.10 .

###### Example 4.11 .

###### Definition 4.12 .

## 5 Rules of information propagation

We can extract the following rules of information propagation from the behavior of transformer as follows.

- •
Rule 0 (Initial setup): The nodes in 0th layer are constructed as $N^{0}_{i}=\{\{x_{i}\},\{i\}\}$. For $l\geqslant 1$, the $l$th layer of nodes are initially constructed as $N^{l}_{i}=\{\emptyset,\emptyset\}$.
- •
Rule 1 (Mask Condition): Attention happens only from former nodes to later nodes.
That is, the attention mechanism $N^{l+1}_{i}=N^{l}_{m}\star N^{l}_{i}$ is performed only when $m<i$. For the multiple nodes information transmission case, the operation $N^{l+1}_{i}=N^{l}_{\mathcal{I}}\star N^{l}_{i}$ is performed only when $i_{\alpha}<i$ for all $i_{\alpha}\in\mathcal{I}$.
- •
Rule 2 (Adjacent position matching): For $l=1$, the information in an odd position node can be transmitted to the subsequent even position node. In this case, the mask condition is satisfied automatically.
More specifically, the nodes in $1$st layer are of the form $N^{1}_{2i}=N^{0}_{2i-1}\star N^{0}_{2i}$ after position matching.
- •
Rule 3 (Same token matching): For $l\geqslant 2$, a node $N^{l}_{i}$ is updated as $N^{l}_{i}=N^{l-1}_{\mathcal{I}}\star N^{l-1}_{i}$
provided there exists a set $N^{l-1}_{\mathcal{I}}\subseteq\mathcal{N}^{l-1}$ satisfying the mask condition $i_{\alpha}<i$ and $V^{l-1}_{i_{\alpha}}\cap V^{l-1}_{i}\neq\emptyset$ for all $i_{\alpha}\in\mathcal{I}$.
- •
Rule 4 (Residual Connection): For $l\geqslant 1$, $\forall N^{l}_{i}\in\mathcal{N}^{l}$, $N^{l}_{i}=\{V^{l-1}_{i}\cup V^{l}_{i},I^{l-1}_{i}\cup I^{l}_{i}\}$.

###### Remark 5.1 .

With a slight abuse of notation, we still denote the value set and index set of a node $N^{l}_{i}$ as $V^{l}_{i}$ and $I^{l}_{i}$ after the information propagation process.
For example, through residual connection $N^{l}_{i}$ is updated as $N^{l}_{i}=\{V^{l-1}_{i}\cup V^{l}_{i},I^{l-1}_{i}\cup I^{l}_{i}\}$,
and we still denote the sets $V^{l-1}_{i}\cup V^{l}_{i}$ and $I^{l-1}_{i}\cup I^{l}_{i}$ as $V^{l}_{i}$ and $I^{l}_{i}$, since we only care about the result after each layer’s information propagation.

###### Remark 5.2 .

It makes no difference whether the residual connection happens before or after same token matching or position match. The result stored in the next layer remains unchanged.

###### Remark 5.3 .

In the above information propagation rules we require that the adjacent position matching only happens when $l=1$ and the same token matching only happens when $l\geqslant 2$.
We can also set the same token matching to happen when $l=1$ and adjacent position matching to happen when $l\geqslant 2$, since the index set $I^{l}_{i}$ in fact encodes the position information. The necessary condition for adjacent position matching to happen is $\exists I^{l}_{k}$ and $I^{l}_{j}$ s.t. there exist $i_{j}\in I^{l}_{j}$ and $i_{k}\in I^{l}_{k}$ satisfying $\min{i_{k},i_{j}}\bmod 2=1$ and $|i_{j}-i_{k}|=1$.
It is easy to see that the index set $I^{l}_{i}$ in this same token matching first rules plays the same role as $V^{l}_{i}$ in above adjacent position matching first rules, and there will be no essential difference for the result in our main theorems under these two different rules.
For simplicity, we only consider the above adjacent position matching first rules.

Two concepts of layer arise in this framework: the layer of attention blocks and the layer of nodes.
The $l$th layer attention block takes $(l-1)$th layer of nodes as input and produces the $l$th layer of nodes as output. Due to this relation, we use “layer $l$” referring to the $l$th layer of attention blocks and $l$th layer of nodes interchangeably.

###### Remark 5.1 .

###### Remark 5.2 .

###### Remark 5.3 .

## 6 Main Theorems

In this section we analyze the information quantity in the process of information propagation according to the above information propagation rules, and our main theorem follows.

###### Theorem 6.1 .

Under the rules of information propagation, given any reasoning sequence $((x_{i})_{i\in\mathbb{Z}},(\bm{a}_{m})_{m\in\mathbb{Z}},\sigma)$,
for any given $x\in\{x_{i}\}_{i\in\mathbb{Z}}$,
and for any $l\in\mathbb{Z}^{+}$ there exists $i\in\mathbb{Z}^{+}$ such that $x\in V^{l}_{i}$, and we have the following bound for $T^{l}(x)=\max\limits_{i\in\mathbb{Z}}\{C^{l}_{i}\mid x\in V^{l}_{i}\}$:

$$ $\displaystyle 2^{l-1}+1\leqslant T^{l}(x)\leqslant 3^{l-1}+1.$ (8) $$

The whole proof is based on mathematical induction. Here we only give a sketch of the proof. The complete proof can be found in the appendix [A](https://arxiv.org/html/2509.23178v1#A1).

Given a reasoning sequence $((x_{i}),(a_{m}),\sigma)$, when considering the lower bound,
by Rule 2 the value sets of nodes in layer $1$ contain only one reasoning pair except the case where only residual connection happens.
Suppose that $j<i$ and the node $N^{1}_{i}$ contains ${{\bm{a}}^{1}_{m_{i}},{\bm{a}}^{2}_{m_{i}}}$ as value set, or simply we say $N^{1}_{i}$ contains ${\bm{a}}_{m_{i}}$, and $N^{1}_{j}$ contains ${\bm{a}}_{m_{j}}$.
Two cases may happen, $n_{i}+1=n_{j}$ and ${\bm{a}}^{2}_{m_{i}}={\bm{a}}^{1}_{m_{j}}$ or $n_{j}+1=n_{i}$ and ${\bm{a}}^{2}_{m_{j}}={\bm{a}}^{1}_{m_{i}}$.
Both cases will lead to $N^{2}_{i}$ containing ${\bm{a}}_{m_{i}}$ and ${\bm{a}}_{m_{j}}$ by Rule 3. This process is the same for any other two nodes containing two adjacent reasoning pairs respectively. The process for layer $3$ is analogous to that for layer $2$: information contained in two nodes in layer $2$ is propagated to one node in layer $3$.
The whole structure is in fact a binary tree and hence the bound is powers of 2.

Regarding the upper bound, due to the mask condition (Rule 1), the permutation $\sigma$ may affect the information propagation. However, the upper bound is always bounded by the case when the mask condition is lifted. Therefore, we ignore the mask condition to find the upper bound.
Just like the proof of the lower bound which use two adjacent reasoning pairs, now we use three adjacent reasoning pairs. Suppose the nodes $N^{1}_{i}$, $N^{1}_{j}$ and $N^{1}_{k}$ contain the reasoning pairs ${\bm{a}}_{m_{i}}$, ${\bm{a}}_{m_{j}}$ and ${\bm{a}}_{m_{k}}$ respectively and $m_{i}+1=m_{j}=m_{k}-1$.
Then by Rule 3, at least one of the node $N^{2}_{j}$ contains ${\bm{a}}_{m_{i}}$, ${\bm{a}}_{m_{j}}$ and ${\bm{a}}_{m_{k}}$. As for layer $3$, there are nodes that contain information propagated from three nodes like $N^{3}_{j}$. The whole structure is a ternary tree and hence the bound is powers of 3.

###### Theorem 6.2 .

Under the rules of information propagation ([5](https://arxiv.org/html/2509.23178v1#S5)), for any $s$ step reasoning sequence $((x_{i})_{1\leqslant i\leqslant 2s},(\bm{a}_{m})_{1\leqslant m\leqslant s},\sigma)$ with reasoning start $x_{2s+1}$, for any $l$ satisfying that $1\leqslant l\leqslant 1+\log_{2}s$, we have the following estimate for $C^{l}_{2s+1}$.

$$ $2^{l-1}\leqslant C^{l}_{2s+1}\leqslant 3^{l-1}.$ (9) $$

The proof of this theorem is similar to the proof of Theorem [6.1](https://arxiv.org/html/2509.23178v1#S6.Thmtheorem1) with two main differences.
First, we need to take into account the reasoning start which requires using mathematical induction twice: once on the node of reasoning start and once on the nodes in the sequence. Second, the reasoning sequence is now finite, and we require it to be long enough to support the structure of the binary tree and the ternary tree. The complete proof is included in the Appendix [B](https://arxiv.org/html/2509.23178v1#A2).

###### Remark 6.3 .

In the proof of this theorem, the mask condition was relaxed to obtain the upper bound. However, we showed in Appendix [C](https://arxiv.org/html/2509.23178v1#A3) that there is a way to construct a large class of reasoning sequences such that the upper bound is attained
under mask condition. This proves that the upper bound is indeed tight.

###### Corollary 6.4 .

For a given transformer with $L$ layers of attention blocks and an input sequence of length $n=2s+1$, where $s\in\mathbb{Z}^{+}$ and $1\leqslant L\leqslant 1+\log_{2}s$, the maximal number of reasoning steps $S_{p}$ it can perform satisfies the following bounds:

$$ $2^{L-1}-1\leqslant S_{p}\leqslant\frac{3^{L-1}-1}{2}.$ (10) $$

###### Remark 6.5 .

Although the upper bound on information quantity as we show in Theorem [6.2](https://arxiv.org/html/2509.23178v1#S6.Thmtheorem2) is $3^{L-1}$, this only implies that up to $3^{L-1}-1$ reasoning steps are involved. However, since the process does not track information back through the reasoning chain, only $\frac{3^{L-1}-1}{2}$ reasoning steps are effective in the reasoning tasks. A quick example is the sequence $(0,1,1,2,1)$ with reasoning start $1$. For $l=2$ there are two reasoning steps in total but only one effective reasoning step $1\rightarrow 2$.

###### Theorem 6.1 .

###### Theorem 6.2 .

###### Remark 6.3 .

###### Corollary 6.4 .

###### Remark 6.5 .

## 7 Experiments and Discussions

### 7.1 Training task

Our task aligns with the reasoning sequence described earlier. Specifically, we begin with a reasoning sequence denoted as $(x_{i})_{1\leq i\leq 2s}$. Subsequently, we introduce $x_{2s+1}$ as the starting point. The complete sequence $(x_{i})_{1\leq i\leq 2s+1}$ serves as the input to the transformer. The output corresponds to the reasoning result from the starting point with a fixed reasoning step (an example in Fig. [6](https://arxiv.org/html/2509.23178v1#S7.F6)).

Figure: Figure 6: A two-step reasoning example.
Refer to caption: x1.png

### 7.2 Experimental results

The detailed hyperparameter settings are provided in the appendix [E](https://arxiv.org/html/2509.23178v1#A5). Reasoning pairs in the test set are totally different from the training set in order to prove transformer can learn reasoning instead of remembering these sequences. In this section, we present key experimental results. We begin by examining a 3-layer transformer architecture. As predicted by our theoretical analysis, this model is capable of solving 3-step reasoning problems with perfect accuracy. Furthermore, we observe that the model dimension $d_{m}$ in our construction is notably large and a higher hidden dimension aids in storing more intermediate information. To validate these findings, we investigate whether a transformer can be trained to achieve exact accuracy on 3-step reasoning tasks and whether a large $d_{m}$ is indeed necessary. Our experiments confirm that such a model can be successfully trained, and that a sufficiently large $d_{m}$ is critical for achieving optimal performance. The relationship between the model dimension $d_{m}$ and test accuracy is summarized in the table below.

**Table 1: Relationship between $d_{m}$ and test accuracy**
| $d_{m}$ | 64 | 128 | 256 | 512 | 1024 |
| --- | --- | --- | --- | --- | --- |
| Test accuracy (%) | 9.6 | 11.9 | 72.2 | 99.6 | 99.6 |

As shown in Table [1](https://arxiv.org/html/2509.23178v1#S7.T1), test accuracy increases monotonically with dimension $d_{m}$, eventually approaching $100\%$, which confirms that a 3-layer transformer can solve 3-step reasoning tasks.

We further investigate scenarios where the model exhibits partial or complete failure. According to the theoretical analysis presented earlier Corollary [6.4](https://arxiv.org/html/2509.23178v1#S6.Thmtheorem4), for reasoning step lengths in the interval [$2^{L-1}$, $\frac{3^{L-1}-1}{2}$], the model can produce correct answers under certain sequence ordering conditions. However, when the number of steps exceeds $\frac{3^{L-1}-1}{2}$, information propagation to the final token becomes insufficient, resulting in incorrect answers. Since this implies that high accuracy is unattainable in such regimes, experimental validation remains partial.

We consider a 3-layer Transformer. Given that $2^{3-1}=4$ and $\frac{3^{3-1}-1}{2}=4$, the model can solve 4-step reasoning tasks when sequence order conditions are satisfied, but fails for 5-step reasoning.
Experimental results under these settings are as follows:

- •
For 4-step reasoning, the model achieves a test accuracy of 46.1%.
- •
For 5-step reasoning, the test accuracy drops to 25.1%.

The decrease in accuracy for the 5-step case provides empirical support for theoretical results. We also find that if the reasoning pairs satisfy a proper order, the network can obtain accurate results for 4-step cases [11](https://arxiv.org/html/2509.23178v1#A5.F11) but not for 5-step cases [13](https://arxiv.org/html/2509.23178v1#A5.F13).
Complete training curves and additional experiments are provided in the Appendix [E](https://arxiv.org/html/2509.23178v1#A5).

## 8 Related Work

In-context learning (ICL) was first introduced by Brown et al. (2020).
This was subsequently followed by numerous studies (Olsson et al., 2022; Garg et al., 2022; Wang et al., 2022; Müller et al., 2021; Goldowsky-Dill et al., 2023; Bietti et al., 2024; Nichani et al., 2024; Edelman et al., 2024; Chen et al., 2024; Todd et al., 2023; Chen and Zou, 2024) to investigate the ICL using induction heads,
which can be seen as a special case of one-step reasoning.

Various reasoning tasks were proposed to study the multi-step reasoning such as recognizing context-free grammars (Zhao et al., 2023), learning sparse functions (Edelman et al., 2022), learning compositionality (Hupkes et al., 2020), generalizing out of distribution when learning Boolean functions (Abbe et al., 2024), matrix digits task (Webb et al., 2023), SET game tasks (Altabaa et al., 2023), reasoning tasks designed by anchor function (Zhang et al., 2024c).
Kil et al. (2024); Li et al. (2024a) use Chain-of-Thought (CoT) reasoning (Wei et al., 2022) to achieve multi-step reasoning via prompt engineering.
Zhang et al. (2023) introduced the
beam retrieval framework for multi-hop QA improving the few-shot QA performance of LLMs.
Li et al. (2024b); Yang et al. (2024); Shalev et al. (2024) locate the potential intermediate answers within middle layers which play a causative role in shaping the final explicit reasoning results.
Zhang et al. (2024b); Yao et al. (2025); Wang et al. (2025a) show that with small initialization, Transformers in condense regime (Luo et al., 2021; Xu et al., 2025) can learn reasoning better.
Wang et al. (2025b) investigated the $k$-fold task which is similar to the k-hop induction head task in Sanford et al. (2024).
Our paper’s difference from Sanford et al. (2024)
is that we consider the transformer with mask and FNN whereas they ignore mask and FNN, which indicates that our framework operates under assumptions that align more directly with practical Transformers.

LLM / AI Tool Disclosure.
During the preparation of this manuscript, we used DeepSeek-V3 (July 2024) to assist with language polishing (grammar, wording).
All substantive content, ideas, and core writing remain the authors’ own, and the authors are fully responsible for any error including those introduced during polishing.

## References

- Abbe et al. [2024]
Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk.
Generalization on the unseen, logic reasoning and degree curriculum.
*Journal of Machine Learning Research*, 25(331):1–58, 2024.
- Altabaa et al. [2023]
Awni Altabaa, Taylor Webb, Jonathan Cohen, and John Lafferty.
Abstractors: Transformer modules for symbolic message passing and
relational reasoning.
*arXiv preprint arXiv*, 2304, 2023.
- Barbero et al. [2024]
Federico Barbero, Alex Vitvitskyi, Christos Perivolaropoulos, Razvan Pascanu,
and Petar Veličković.
Round and round we go! what makes rotary positional encodings useful?
*arXiv preprint arXiv:2410.06205*, 2024.
- Bietti et al. [2024]
Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon
Bottou.
Birth of a transformer: A memory viewpoint.
*Advances in Neural Information Processing Systems*, 36, 2024.
- Brown et al. [2020]
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla
Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell,
et al.
Language models are few-shot learners.
*Advances in neural information processing systems*,
33:1877–1901, 2020.
- Chen et al. [2024]
Siyu Chen, Heejune Sheen, Tianhao Wang, and Zhuoran Yang.
Training dynamics of multi-head softmax attention for in-context
learning: Emergence, convergence, and optimality.
*arXiv preprint arXiv:2402.19442*, 2024.
- Chen and Zou [2024]
Xingwu Chen and Difan Zou.
What can transformer learn with varying depth? case studies on
sequence learning tasks.
*arXiv preprint arXiv:2404.01601*, 2024.
- Cybenko [1989]
George Cybenko.
Approximation by superpositions of a sigmoidal function.
*Mathematics of control, signals and systems*, 2(4):303–314, 1989.
- Davies et al. [2021]
Alex Davies, Petar Veličković, Lars Buesing, Sam Blackwell, Daniel
Zheng, Nenad Tomašev, Richard Tanburn, Peter Battaglia, Charles
Blundell, András Juhász, et al.
Advancing mathematics by guiding human intuition with ai.
*Nature*, 600(7887):70–74, 2021.
- Devlin et al. [2019]
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.
Bert: Pre-training of deep bidirectional transformers for language
understanding.
In *Proceedings of the 2019 conference of the North American
chapter of the association for computational linguistics: human language
technologies, volume 1 (long and short papers)*, pages 4171–4186, 2019.
- Edelman et al. [2022]
Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang.
Inductive biases and variable creation in self-attention mechanisms.
In *International Conference on Machine Learning*, pages
5793–5831. PMLR, 2022.
- Edelman et al. [2024]
Benjamin L Edelman, Ezra Edelman, Surbhi Goel, Eran Malach, and Nikolaos
Tsilivis.
The evolution of statistical induction heads: In-context learning
markov chains.
*arXiv preprint arXiv:2402.11004*, 2024.
- Garg et al. [2022]
Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant.
What can transformers learn in-context? a case study of simple
function classes.
*Advances in neural information processing systems*,
35:30583–30598, 2022.
- Goldowsky-Dill et al. [2023]
Nicholas Goldowsky-Dill, Chris MacLeod, Lucas Sato, and Aryaman Arora.
Localizing model behavior with path patching.
*arXiv preprint arXiv:2304.05969*, 2023.
- Hupkes et al. [2020]
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni.
Compositionality decomposed: How do neural networks generalise?
*Journal of Artificial Intelligence Research*, 67:757–795, 2020.
- Kil et al. [2024]
Jihyung Kil, Farideh Tavazoee, Dongyeop Kang, and Joo-Kyung Kim.
Ii-mmr: Identifying and improving multi-modal multi-hop reasoning in
visual question answering.
*arXiv preprint arXiv:2402.11058*, 2024.
- Li et al. [2024a]
Yanyang Li, Shuo Liang, Michael R Lyu, and Liwei Wang.
Making long-context language models better multi-hop reasoners.
*arXiv preprint arXiv:2408.03246*, 2024a.
- Li et al. [2024b]
Zhaoyi Li, Gangwei Jiang, Hong Xie, Linqi Song, Defu Lian, and Ying Wei.
Understanding and patching compositional reasoning in llms.
*arXiv preprint arXiv:2402.14328*, 2024b.
- Liu et al. [2018]
Peter J Liu, Mohammad Saleh, Etienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz
Kaiser, and Noam Shazeer.
Generating wikipedia by summarizing long sequences.
*arXiv preprint arXiv:1801.10198*, 2018.
- Luo et al. [2021]
Tao Luo, Zhi-Qin John Xu, Zheng Ma, and Yaoyu Zhang.
Phase diagram for two-layer relu neural networks at infinite-width
limit.
*Journal of Machine Learning Research*, 22(71):1–47, 2021.
- Müller et al. [2021]
Samuel Müller, Noah Hollmann, Sebastian Pineda Arango, Josif Grabocka, and
Frank Hutter.
Transformers can do bayesian inference.
*arXiv preprint arXiv:2112.10510*, 2021.
- Nichani et al. [2024]
Eshaan Nichani, Alex Damian, and Jason D Lee.
How transformers learn causal structure with gradient descent.
*arXiv preprint arXiv:2402.14735*, 2024.
- Olsson et al. [2022]
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma,
Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al.
In-context learning and induction heads.
*arXiv preprint arXiv:2209.11895*, 2022.
- OpenAI [2023]
R OpenAI.
Gpt-4 technical report. arxiv 2303.08774.
*View in Article*, 2(5):1, 2023.
- Radford et al. [2019]
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya
Sutskever, et al.
Language models are unsupervised multitask learners.
*OpenAI blog*, 1(8):9, 2019.
- Sanford et al. [2024]
Clayton Sanford, Daniel Hsu, and Matus Telgarsky.
Transformers, parallel computation, and logarithmic depth.
*arXiv preprint arXiv:2402.09268*, 2024.
- Shalev et al. [2024]
Yuval Shalev, Amir Feder, and Ariel Goldstein.
Distributional reasoning in llms: Parallel reasoning processes in
multi-hop reasoning.
*arXiv preprint arXiv:2406.13858*, 2024.
- Todd et al. [2023]
Eric Todd, Millicent L Li, Arnab Sen Sharma, Aaron Mueller, Byron C Wallace,
and David Bau.
Function vectors in large language models.
*arXiv preprint arXiv:2310.15213*, 2023.
- Touvron et al. [2023]
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne
Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric
Hambro, Faisal Azhar, et al.
Llama: Open and efficient foundation language models.
*arXiv preprint arXiv:2302.13971*, 2023.
- Trinh et al. [2024]
Trieu H Trinh, Yuhuai Wu, Quoc V Le, He He, and Thang Luong.
Solving olympiad geometry without human demonstrations.
*Nature*, 625(7995):476–482, 2024.
- Vaswani et al. [2017]
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones,
Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.
Attention is all you need.
In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus,
S. Vishwanathan, and R. Garnett, editors, *Advances in Neural
Information Processing Systems*, volume 30. Curran Associates, Inc., 2017.
- Wang et al. [2022]
Kevin Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob
Steinhardt.
Interpretability in the wild: a circuit for indirect object
identification in gpt-2 small.
*arXiv preprint arXiv:2211.00593*, 2022.
- Wang et al. [2025a]
Zhiwei Wang, Yunji Wang, Zhongwang Zhang, Zhangchen Zhou, Hui Jin, Tianyang Hu,
Jiacheng Sun, Zhenguo Li, Yaoyu Zhang, and Zhi-Qin John Xu.
Understanding the language model to solve the symbolic multi-step
reasoning problem from the perspective of buffer mechanism,
2025a.
URL [https://arxiv.org/abs/2405.15302](https://arxiv.org/abs/2405.15302).
- Wang et al. [2025b]
Zixuan Wang, Eshaan Nichani, Alberto Bietti, Alex Damian, Daniel Hsu, Jason D.
Lee, and Denny Wu.
Learning compositional functions with transformers from easy-to-hard
data, 2025b.
URL [https://arxiv.org/abs/2505.23683](https://arxiv.org/abs/2505.23683).
- Webb et al. [2023]
Taylor Webb, Keith J Holyoak, and Hongjing Lu.
Emergent analogical reasoning in large language models.
*Nature Human Behaviour*, 7(9):1526–1541,
2023.
- Wei et al. [2022]
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V
Le, Denny Zhou, et al.
Chain-of-thought prompting elicits reasoning in large language
models.
*Advances in neural information processing systems*,
35:24824–24837, 2022.
- Xu et al. [2025]
Zhi-Qin John Xu, Yaoyu Zhang, and Zhangchen Zhou.
An overview of condensation phenomenon in deep learning.
*arXiv preprint arXiv:2504.09484*, 2025.
- Yang et al. [2024]
Sohee Yang, Elena Gribovskaya, Nora Kassner, Mor Geva, and Sebastian Riedel.
Do large language models latently perform multi-hop reasoning?
*arXiv preprint arXiv:2402.16837*, 2024.
- Yao et al. [2025]
Junjie Yao, Zhongwang Zhang, and Zhi-Qin John Xu.
An analysis for reasoning bias of language models with small
initialization.
*Forty-second International Conference on Machine Learning*,
2025.
- Yao et al. [2023]
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and
Karthik Narasimhan.
Tree of thoughts: Deliberate problem solving with large language
models.
*Advances in neural information processing systems*,
36:11809–11822, 2023.
- Yu et al. [2025]
Zeping Yu, Yonatan Belinkov, and Sophia Ananiadou.
Back attention: Understanding and enhancing multi-hop reasoning in
large language models.
*arXiv preprint arXiv:2502.10835*, 2025.
- Zhang et al. [2023]
Jiahao Zhang, Haiyang Zhang, Dongmei Zhang, Yong Liu, and Shen Huang.
Beam retrieval: General end-to-end retrieval for multi-hop question
answering.
*arXiv preprint arXiv:2308.08973*, 2023.
- Zhang et al. [2024a]
Yifan Zhang, Yang Yuan, and Andrew Chi-Chih Yao.
On the diagram of thought.
*arXiv preprint arXiv:2409.10038*, 2024a.
- Zhang et al. [2024b]
Zhongwang Zhang, Pengxiao Lin, Zhiwei Wang, Yaoyu Zhang, and Zhi-Qin John Xu.
Initialization is critical to whether transformers fit composite
functions by inference or memorizing.
*arXiv preprint arXiv:2405.05409*, 2024b.
- Zhang et al. [2024c]
Zhongwang Zhang, Zhiwei Wang, Junjie Yao, Zhangchen Zhou, Xiaolong Li,
Zhi-Qin John Xu, et al.
Anchor function: a type of benchmark functions for studying language
models.
*arXiv preprint arXiv:2401.08309*, 2024c.
- Zhao et al. [2023]
Haoyu Zhao, Abhishek Panigrahi, Rong Ge, and Sanjeev Arora.
Do transformers parse while predicting the masked word?, 2023.
URL [https://arxiv.org/abs/2303.08117](https://arxiv.org/abs/2303.08117).

## Appendix A Proof of Theorem 6.1

We first prove the lower bound.

According to Rule 0, the nodes in first layer are constructed as $N^{1}_{i}=\{(x_{i}),\{i\},\{i\}\}$.
According to Rule 2, we have the nodes in second layer are constructed as $N^{1}_{2i}=\{\{x_{2i-1},x_{2i}\},\{2i\},\{2i-1,2i\}\}$ for $i\in\mathbb{Z}$. Clearly, we have $C^{1}_{2i}=2$.

We use mathematical induction to prove that for $k\geqslant 2$, for any $x_{j}\in\{x_{i}\}_{i\in\mathbb{Z}}$, there exists an integer $i\in\mathbb{Z}$ such that

- •
$x_{j}\in V^{k}_{i}$,
- •
We denote $\sigma({I}^{k}_{i})$ to be the set $\{\sigma(\lfloor\frac{i_{m}+1}{2}\rfloor)\}_{i_{m}\in{I}^{k}_{i}}$,
and we have
$\max{\sigma({I}^{k}_{i})}-\sigma(\lfloor\frac{j+1}{2}\rfloor)\geqslant 2^{k-1}-1$ which implies that $C^{k}_{i}\geqslant 2^{k-1}+1$.

For $k=2$, given any $x_{j}\in(x_{i})$, according to Rule 2, we know that $x_{j}$ is contained in the value set $V^{1}_{2\lfloor\frac{j+1}{2}\rfloor}$ of node $N^{1}_{2\lfloor\frac{j+1}{2}\rfloor}$.

For simplicity, we assume that $j$ is an even number, then $V^{1}_{2\lfloor\frac{j+1}{2}\rfloor}=V^{1}_{j}=\{x_{j-1},x_{j}\}$ and $I^{1}_{j}=\{j-1,j\}$.
We now want to find a node $N^{i}_{2}$ such that $V^{1}_{i}\cap V^{1}_{j}=\{x_{j}\}$.
To do so, by definition of reasoning sequence and using the relation ([5](https://arxiv.org/html/2509.23178v1#S4.E5)) we know that $x_{j-1}$ and $x_{j}$ comes from the reasoning pair $\bm{a}_{\sigma(\frac{j}{2})}$.
By definition of reasoning sequence and relation ([6](https://arxiv.org/html/2509.23178v1#S4.E6)) we have

$$ $\displaystyle\bm{a}^{2}_{\sigma(\frac{j}{2})}=\bm{a}^{1}_{\sigma(\frac{j}{2})+1},$ (11) $\displaystyle\bm{a}_{\sigma(\frac{j}{2})+1}=\left(x_{2\sigma^{-1}\left(\sigma(\frac{j}{2})+1\right)-1},x_{2\sigma^{-1}\left(\sigma(\frac{j}{2})+1\right)}\right).$ $$

Set $i={2\sigma^{-1}\left(\sigma(\frac{j}{2})+1\right)}$.
It is now clear that the node $N^{1}_{i}$ have value set $V^{1}_{i}$ satisfying $V^{1}_{i}\cap V^{1}_{j}=\{x_{j}\}$ and index set $I^{1}_{i}=\{i-1,i\}$.
By Rule 3, the node $N^{2}_{\max\{i,j\}}$ have value set $V^{2}_{\max\{i,j\}}$ such that $\{x_{j-1},x_{j},x_{i+1}\}\subseteq V^{2}_{\max\{i,j\}}$. Hence, $C^{2}_{\max\{i,j\}}\geqslant 3$ and
$\sigma(\frac{j}{2})+1-\sigma(\frac{j}{2})=1\geqslant 2^{2-1}-1$.

Now we assume the induction hypotheses hold for $3\leqslant k\leqslant k_{0}$ and consider the case $k=k_{0}+1$.
There exists a node $N^{k_{0}}_{m_{0}}$ such that

$$ $\displaystyle x_{j}\in V^{k_{0}}_{m_{0}},$ (12) $\displaystyle\max{\sigma({I}^{k_{0}}_{m_{0}})}-\sigma(\frac{j}{2})\geqslant 2^{k_{0}-1}-1,$ (13) $\displaystyle C^{k_{0}}_{m_{0}}\geqslant 2^{k_{0}-1}+1.$ (14) $$

Set ${\alpha}=\max\sigma(I^{k_{0}}_{m_{0}})$ then using relation ([6](https://arxiv.org/html/2509.23178v1#S4.E6)) we know that $\bm{a}^{2}_{\alpha}=x_{2\sigma^{-1}(\alpha)}\in V^{k_{0}}_{m_{0}}$.
Using definition of reasoning sequence and relation ([5](https://arxiv.org/html/2509.23178v1#S4.E5)) we know that

$$ $x_{2\sigma^{-1}(\alpha+1)-1}=\bm{a}^{1}_{\alpha+1}=\bm{a}^{2}_{\alpha}=x_{2\sigma^{-1}(\alpha)}.$ (15) $$

Note that $\sigma(\lfloor\frac{2\sigma^{-1}(\alpha+1)-1+1}{2}\rfloor)=\alpha+1$. And then the induction hypotheses implies that there is a node $N^{k_{0}}_{m_{1}}$ such that

$$ $\displaystyle x_{2\sigma^{-1}(\alpha+1)-1}\in V^{k_{0}}_{m_{1}},$ (16) $\displaystyle\max{\sigma({I}^{k_{0}}_{m_{1}})}-(\alpha+1)\geqslant 2^{k_{0}-1}-1,$ (17) $\displaystyle C^{k_{0}}_{m_{1}}\geqslant 2^{k_{0}-1}+1.$ (18) $$

This construction ensures that $x_{2\sigma^{-1}(\alpha+1)-1}=x_{2\sigma^{-1}(\alpha)}\in V^{k_{0}}_{m_{1}}\cap V^{k_{0}}_{m_{0}}$,
then by Rule 3, we know that the node $N^{k_{0}+1}_{\max\{m_{0},m_{1}\}}$ have value set $V^{k_{0}+1}_{\max\{m_{0},m_{1}\}}$ and index set $I^{k_{0}+1}_{\max\{m_{0},m_{1}\}}$ satisfying that

$$ $\displaystyle x_{j}\in V^{k_{0}+1}_{\max\{m_{0},m_{1}\}},$ (19) $\displaystyle I^{k_{0}}_{m_{0}}\cup I^{k_{0}}_{m_{1}}\subseteq I^{k_{0}+1}_{\max\{m_{0},m_{1}\}}.$ (20) $$

Combining ([13](https://arxiv.org/html/2509.23178v1#A1.E13)), ([17](https://arxiv.org/html/2509.23178v1#A1.E17)) and ([20](https://arxiv.org/html/2509.23178v1#A1.E20)) leads to

$$ $\max{\sigma(I^{k_{0}+1}_{\max\{m_{0},m_{1}\}})}-\sigma({\frac{j}{2}})\geqslant 2^{k_{0}}-1,$ $$

which implies that $C^{k_{0}+1}_{\max\{m_{0},m_{1}\}}\geqslant 2^{k_{0}+1-1}+1$.
This completes the proof for lower bound.

Next we prove the upper bound.

It is clear that if Rule 1 is removed, the information quantity in each node can only maintain unchanged or increase. Therefore, we consider the no-mask condition, without loss of generality, we consider the reasoning sequence to be $\{x_{i}=\lfloor\frac{i}{2}\rfloor\}_{i\in\mathbb{N}}$ with constructing permutation $\sigma=\text{Id}$ and constructing reasoning chain $(\bm{a}_{m})=((m-1,m))$.

We will use mathematical induction to prove that
for $k\geqslant 2$ and $m\in\mathbb{Z}$, the value set of node $N^{k}_{2m}$ satisfies $V^{k}_{2m}\subseteq\{m-\frac{3^{k-1}+1}{2},m-\frac{3^{k-1}+1}{2}+1,\cdots,m+\frac{3^{k-1}-1}{2}\}$ and $C^{k}_{2m}\leqslant 3^{k-1}+1$.

Since the index set of a node will play no rule in this proof, we will just ignore them in the expression of a node.

When $k=2$, By Rule 2 the nodes $N^{1}_{i}$ are of the form $N^{1}_{2i}=\{\{x_{2i-1},x_{2i}\},\{2i\}\}$.
Then by Rule 3 the nodes in layer $3$ are of the form $N^{2}_{2i}=\{\{i-2,i-1,i,i+1\}\{2i\}\}$. Therefore, the conclusion holds for $k=2$.

Assuming the conclusion holds for $k\leqslant k_{0}$.
When $k=k_{0}+1$, by inductive hypotheses, there are three nodes $N^{k_{0}}_{2m}$, $N^{k_{0}}_{2m_{1}}$, $N^{k_{0}}_{2m_{2}}$ with value sets $V^{k_{0}}_{2m}$, $V^{k_{0}}_{2m_{1}}$, $V^{k_{0}}_{2m_{2}}$.
We require that

$$ $\displaystyle m+\frac{3^{{k_{0}}-1}-1}{2}=m_{1}-\frac{3^{{k_{0}}-1}+1}{2},$ (21) $\displaystyle m_{2}+\frac{3^{{k_{0}}-1}-1}{2}=m-\frac{3^{{k_{0}}-1}+1}{2}.$ $$

Simple calculation shows that

$$ $m_{1}=m+3^{{k_{0}}-1},\ m_{2}=m-3^{{k_{0}}-1}.$ (22) $$

And the three nodes
$N^{k_{0}}_{2m}$, $N^{k_{0}}_{2(m+3^{{k_{0}}-1})}$, $N^{k_{0}}_{2(m-3^{{k_{0}}-1})}$ have value sets

$$ $\displaystyle V^{k_{0}}_{2m}\subseteq\{m-\frac{3^{{k_{0}}-1}+1}{2},m-\frac{3^{{k_{0}}-1}+1}{2}+1,\cdots,m+\frac{3^{{k_{0}}-1}-1}{2}\},$ (23) $\displaystyle V^{k_{0}}_{2(m+3^{{k_{0}}-1})}\subseteq\{m+\frac{3^{{k_{0}}-1}-1}{2},m+\frac{3^{{k_{0}}-1}-1}{2}+1,\cdots,m+\frac{3^{{k_{0}}-1}-1}{2}\},$ (24) $\displaystyle V^{k_{0}}_{2(m-3^{{k_{0}}-1})}\subseteq\{m-\frac{3^{{k_{0}}-1}+1}{2},m-\frac{3^{{k_{0}}-1}+1}{2}+1,\cdots,m-\frac{3^{{k_{0}}-1}+1}{2}\}.$ (25) $$

Again by Rule 3, we know that the node $N^{k_{0}+1}_{2m}=N^{k_{0}}_{2(m+3^{k-2})}\star N^{k_{0}}_{2(m-3^{k-2})}\star N^{k_{0}}_{2m}$ have value set $V^{k_{0}+1}_{2m}\subseteq\{m-\frac{3^{{k_{0}}}+1}{2},m-\frac{3^{{k_{0}}}+1}{2}+1,\cdots,m+\frac{3^{{k_{0}}}-1}{2}\}$, and therefore, $C^{k_{0}+1}_{2m}\leqslant 3^{k_{0}}+1$. This completes the proof.

## Appendix B Proof of Theorem 6.2

We shall also use the mathematical induction to prove this theorem.

We first assert that
for $1\leqslant l\leqslant 1+\log_{2}s$ and for $j$ satisfying $1\leqslant\sigma(\lfloor\frac{j+1}{2}\rfloor)\leqslant s-2^{l-1}+1$ there exists a node $N^{l}_{k}$ such that

$$ $\bigcup\limits_{0\leqslant\alpha\leqslant 2^{l-1}-1}\{x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+\alpha\right)-1},x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+\alpha\right)}\}\subseteq V^{l}_{k}.$ (26) $$

For $l=1$, the relation ([26](https://arxiv.org/html/2509.23178v1#A2.E26)) can be verified easily since after position matching the nodes in $\mathcal{N}^{1}$ are of the form $N^{1}_{2m}=\{\{x_{2m-1},x_{2m}\},\{2m\},\{2m-1,2m\}\}$.
And note that $x_{j}\in\{x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)\right)-1},x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)\right)}\}\subseteq V^{1}_{2\lfloor\frac{j+1}{2}\rfloor}$.

Now we assume that ([26](https://arxiv.org/html/2509.23178v1#A2.E26)) holds for $l=l_{0}$, then we prove it still holds for $l=l_{0}+1$.
Given $x_{j}\in(x_{i})$ with $1\leqslant\sigma(\lfloor\frac{j+1}{2}\rfloor)\leqslant s-2^{l_{0}}+1$, it is clear that $1\leqslant\sigma(\lfloor\frac{j+1}{2}\rfloor)\leqslant s-2^{l_{0}-1}+1$. Then by inductive hypotheses we know that there exists a node $N^{l_{0}}_{k_{1}}$ such that

$$ $\bigcup\limits_{0\leqslant\alpha\leqslant 2^{l_{0}-1}-1}\{x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+\alpha\right)-1},x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+\alpha\right)}\}\subseteq V^{l_{0}}_{k_{1}}.$ (27) $$

On the other hand, since $1\leqslant\sigma(\lfloor\frac{j+1}{2}\rfloor)\leqslant s-2^{l_{0}}+1$ we have $1\leqslant\sigma(\lfloor\frac{j+1}{2}\rfloor)+2^{l_{0}-1}\leqslant s-2^{l_{0}-1}+1$, and again by inductive hypotheses there exists a node $N^{l_{0}}_{k_{2}}$ such that

$$ $\bigcup\limits_{0\leqslant\alpha\leqslant 2^{l_{0}-1}-1}\{x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+2^{l_{0}-1}+\alpha\right)-1},x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+2^{l_{0}-1}+\alpha\right)}\}\subseteq V^{l_{0}}_{k_{2}}.$ (28) $$

Note that by the definition of reasoning sequence we have

$$ $x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+2^{l_{0}-1}\right)-1}=x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}+\rfloor)+2^{l_{0}-1}-1\right)}.$ $$

By Rule 3, there exists a node $N^{l_{0}+1}_{\max\{k_{1},k_{2}\}}$ such that

$$ $\bigcup\limits_{0\leqslant\alpha\leqslant 2^{l_{0}}-1}\{x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+\alpha\right)-1},x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+\alpha\right)}\}\subseteq V^{l_{0}}_{k_{1}}\cup V^{l_{0}}_{k_{2}}\subseteq V^{l_{0}+1}_{\max\{k_{1},k_{2}\}}.$ $$

This completes the proof of our assertion.

Set the reasoning start as $x_{2s+1}=x_{j}$,
we then assert that

$$ $\bigcup\limits_{0\leqslant\alpha\leqslant 2^{l-1}-2}\{x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+\alpha\right)-1},x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+\alpha\right)}\}\subseteq V^{l}_{2s+1}.$ (29) $$

When $l=2$ the assertion ([29](https://arxiv.org/html/2509.23178v1#A2.E29)) can be easily verified. We assume ([29](https://arxiv.org/html/2509.23178v1#A2.E29)) holds for $l=l_{0}$ and consider the case $l=l_{0}+1$.
By assertion ([26](https://arxiv.org/html/2509.23178v1#A2.E26)), we know there exists $N^{l_{0}}_{k}$ such that

$$ $\bigcup\limits_{0\leqslant\alpha\leqslant 2^{l_{0}-1}-1}\{x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+2^{l_{0}-1}-1+\alpha\right)-1},x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+2^{l_{0}-1}-1+\alpha\right)}\}\subseteq V^{l_{0}}_{k}.$ (30) $$

Again, by definition of reasoning sequence we have

$$ $x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+2^{l_{0}-1}-1\right)-1}=x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}+\rfloor)+2^{l_{0}-1}-2\right)}.$ $$

And by Rule 3 we know that

$$ $\bigcup\limits_{0\leqslant\alpha\leqslant 2^{l_{0}}-2}\{x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+\alpha\right)-1},x_{2\sigma^{-1}\left(\sigma(\lfloor\frac{j+1}{2}\rfloor)+\alpha\right)}\}\subseteq V^{l_{0}}_{k}\cup V^{l_{0}}_{2s+1}\subseteq V^{l_{0}+1}_{2s+1}.$ $$

This completes the proof of assertion ([29](https://arxiv.org/html/2509.23178v1#A2.E29)), which implies that for $l\geqslant 2$, $C^{l}_{2s+1}\geqslant 2^{l-1}$.

For $l=1$, it is clear that $C^{2}_{2s+1}=1$ since only residual connection happens. And we complete the proof for the lower bound.

The upper bound is proved similarly as in the proof of Theorem [6.1](https://arxiv.org/html/2509.23178v1#S6.Thmtheorem1), except we consider mainly the reasoning start position, which results in one fewer element.

## Appendix C Examples where the theoretical bounds are achieved

In this section we give some examples related to Theorem [6.2](https://arxiv.org/html/2509.23178v1#S6.Thmtheorem2). In fact, both the lower bound and upper bound can be attained.

#### Lower bound

We construct a reasoning sequence $(1,2,2,3,3,4,4,5\cdots,2s-1,2s,1)$. Assume that $1\leqslant l\leqslant 1+\log_{2}s$, it is clear that $C^{l}_{2s+1}\geqslant 2^{l-1}$

Figure: Figure 7: Lower bound example
Refer to caption: x2.png

#### Upper bound

In this section, we shall use the concept of truncation of a reasoning sequence. This truncated reasoning sequence contains a finite step reasoning chain and some irrelevant reasoning pairs which serves as some redundant information as in practice. In fact, we truncate a reasoning sequence $(x_{i})$ as follows:

- 1.
Firstly, we truncate the constructing reasoning sequence $(\bm{a}_{m})$ to be an $s$ step reasoning chain $(\bm{\tilde{a}}_{k})=(\bm{a}_{i},\bm{a}_{i+1},\cdots,\bm{a}_{i+s-1})$.
- 2.
Secondly, we use the relation ([6](https://arxiv.org/html/2509.23178v1#S4.E6)) to find those elements constructed from this $s$ step reasoning chain. That is
$E=\{x_{2(\sigma^{-1}(i)-1)},x_{2(\sigma^{-1}(i)-1)+1},\cdots,x_{2(\sigma^{-1}(i+s-1)-1)},x_{2(\sigma^{-1}(i+s-1)-1)+1}\}.$
(31)
- 3.
Thirdly, we set
$\displaystyle\mathcal{I}_{E}=\{$
$\displaystyle{2(\sigma^{-1}(i)-1)},{2(\sigma^{-1}(i)-1)+1},\cdots,$
(32)
$\displaystyle{2(\sigma^{-1}(i+s-1)-1)},{2(\sigma^{-1}(i+s-1)-1)+1}\},$
which is the set of all subscripts of elements in $E$. Moreover, we take the subsequence $(\tilde{x}_{i})=(x_{\min\{\mathcal{I}_{E}\}+i-1})$ as the truncated reasoning sequence,
where ${1\leqslant i\leqslant\max\{\mathcal{I}_{E}\}-\min\{\mathcal{I}_{E}\}+1}$.

We call this sequence $(\tilde{x}_{i})$ the truncated reasoning sequence containing $(\bm{\tilde{a}}_{k})$.

With this definition of truncation, we provide a method to construct finite step reasoning sequences which allows the upper bound in Theorem [6.2](https://arxiv.org/html/2509.23178v1#S6.Thmtheorem2) to be attained.
This is achieved in a recursive way.

Consider a reasoning sequence $(\bm{a}_{i})_{i\in\mathbb{Z}}$. For a given integer $i$
we define

$$ ${\bm{s}}_{1}(i)=(\bm{a}_{i}),\ \ {\bm{s}}_{2}(i)=(\bm{a}_{i},\bm{a}_{i+2},\bm{a}_{i+1}),$ $$

and

$$ ${\bm{s}}_{3}(i)=(\bm{a}_{i},\bm{a}_{i+2},\bm{a}_{i+1},\bm{a}_{i+6},\bm{a}_{i+8},\bm{a}_{i+7},\bm{a}_{i+3},\bm{a}_{i+5},\bm{a}_{i+4}).$ $$

For simplicity, we use the notation

$$ $\displaystyle{\bm{s}}_{3}(i)$ $\displaystyle=({\bm{s}}_{2}(i),{\bm{s}}_{2}(i+6),{\bm{s}}_{2}(i+3))$ $\displaystyle:=(\bm{a}_{i},\bm{a}_{i+2},\bm{a}_{i+1},\bm{a}_{i+6},\bm{a}_{i+8},\bm{a}_{i+7},\bm{a}_{i+3},\bm{a}_{i+5},\bm{a}_{i+4}),$ $$

and with this notation ${\bm{s}}_{3}(i)$ is still a sequence of reasoning pairs.

For $k\geqslant 3$ we define

$$ ${\bm{s}}_{k}(i)=({\bm{s}}_{k-1}(i),{\bm{s}}_{k-1}(i+2\times 3^{k-2}),{\bm{s}}_{k-1}(i+3^{k-2})).$ $$

Same notation as in ${\bm{s}}_{3}(i)$ and all ${\bm{s}}_{k}(i)$ are sequences of reasoning pairs.

We now construct our reasoning sequence.

Set $r_{1}=({\bm{s}}_{l-1}(i-\frac{3^{l-1}-1}{2}),\cdots,{\bm{s}}_{3}(i-13),{\bm{s}}_{2}(i-4),{\bm{s}}_{1}(i-1),{\bm{s}}_{1}(i),{\bm{s}}_{2}(i+1),{\bm{s}}_{3}(i+4),\cdots,{\bm{s}}_{l-1}(i+\frac{3^{l-2}-1}{2}))$,
it is clear that there exist $\sigma\in\text{Sym}(\mathbb{Z})$ such that $(\bm{a}_{\sigma(1-\frac{3^{l-1}}{2})},\cdots,\bm{a}_{\sigma(1)},\bm{a}_{\sigma(2)},\cdots,\bm{a}_{\sigma(\frac{3^{l-1}-1}{2})})=r_{1}$.
By the construction of $r_{1}$ we know all the reasoning pairs in $r_{1}$ forms a finite step reasoning chain
$(\bm{a}_{i-\frac{3^{l-1}-1}{2}},\cdots\bm{a}_{i},\bm{a}_{i+1},\cdots,\bm{a}_{i+\frac{3^{l-1}-3}{2}})$, we extend this finite step reasoning chain to an infinite reasoning chain $\tilde{a}$ by adding reasoning pairs to both sides.
And we take a permutation $\tau\in\text{Sym}(\mathbb{Z})$ satisfying $\bm{a}_{\tau(i_{m})}=\bm{a}_{\sigma(m)}$ where $i_{m}\in I$ with $I=\{i_{1-\frac{3^{l-1}}{2}},\cdots,i_{1},i_{2},\cdots,i_{\frac{3^{l-1}-3}{2}}\}$ and $i_{1-\frac{3^{l-1}}{2}}<\cdots<i_{1}<i_{2}<\cdots<i_{\frac{3^{l-1}-3}{2}}$.

We truncate the reasoning sequence $((x_{j}),\tilde{{\bm{a}}},\tau)$ to contain the finite reasoning chain
$(\bm{a}_{i-\frac{3^{l-1}-1}{2}},\cdots,\bm{a}_{i+\frac{3^{l-1}-3}{2}})$
to get a sequence $(\tilde{x}_{j})=(x_{\min\{\mathcal{I}_{E}\}+j-1})_{1\leqslant j\leqslant\max\{\mathcal{I}_{E}\}-\min\{\mathcal{I}_{E}\}+1}$. Here $E$ and $\mathcal{I}_{E}$ are defined as in ([31](https://arxiv.org/html/2509.23178v1#A3.E31)) and ([32](https://arxiv.org/html/2509.23178v1#A3.E32)).
This $(\tilde{x}_{j})$ with reasoning start $x_{\max{\mathcal{I}_{E}}+1}=\bm{a}^{1}_{i}$ is the sequence we want.

###### Remark C.1 .

Under the rules of information propagation, the elements in $(\tilde{x}_{j})$ contributing to the node $N^{l}_{\max{\mathcal{I}_{E}}+1}$ are those come from the reasoning chain
$(\bm{a}_{i-\frac{3^{l-1}-1}{2}},\cdots,\bm{a}_{i+\frac{3^{l-1}-3}{2}})$.
Hence, the information in $N^{l}_{\max{\mathcal{I}_{E}}+1}$ will be the same if we consider the reasoning sequence constructed from
$(\bm{a}_{i-\frac{3^{l-1}-1}{2}},\cdots,\bm{a}_{i+\frac{3^{l-1}-3}{2}})$
and $\sigma$.
However, the above complicated way we construct truncated sequence is still necessary which shows that there is a large class of reasoning sequence allows the upper bound to be attained.

###### Proposition C.2 .

We consider the reasoning sequence $(x_{i})$ with constructing reasoning chain $(\bm{a}_{m})=((m,m+1))_{1-\frac{3^{\tilde{l}-1}-1}{2}\leqslant m\leqslant\frac{3^{\tilde{l}-1}-1}{2}}$ and constructing permutation $\sigma$ satisfying that

$$ $\displaystyle(\bm{a}_{\sigma(1)},\bm{a}_{\sigma(2)},\cdots,\bm{a}_{\sigma(\frac{3^{\tilde{l}-1}-1}{2})})=({\bm{s}}_{1}(1),{\bm{s}}_{2}(2),{\bm{s}}_{3}(5),\cdots,{\bm{s}}_{l}(\frac{3^{l-1}+1}{2}),\cdots{\bm{s}}_{\tilde{l}-1}(\frac{3^{\tilde{l}-2}+1}{2})),$ (33) $\displaystyle\begin{aligned} (\bm{a}_{\sigma(1-\frac{3^{\tilde{l}-1}}{2})},\bm{a}_{\sigma(2-\frac{3^{\tilde{l}-1}}{2})},\cdots,&\bm{a}_{\sigma(0)})=\\ &({\bm{s}}_{\tilde{l}-1}(\frac{3-3^{\tilde{l}-1}}{2}),\cdots,{\bm{s}}_{l}(\frac{3-3^{l}}{2}),\cdots{\bm{s}}_{3}(-12),{\bm{s}}_{2}(-3),{\bm{s}}_{1}(0),).\end{aligned}$ (34) $$

If the reasoning start is set be to $x_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}=\bm{a}^{1}_{1}$, then for $1\leqslant l\leqslant\tilde{l}$, we have $C^{l}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}=3^{l-1}$.

To prove this proposition we need the following two lemmas.

###### Lemma C.3 .

For $m\geqslant 1$, $\forall k\in\{\frac{3^{j-2}+1}{2}\}_{2\leqslant j\leqslant\tilde{l}}$, there exists $i_{(m,k)}\in[1,{3^{\tilde{l}-1}-1}]\cap\mathbb{Z}$ depending on $m$ and $k$ such that the node $N^{m}_{i_{(m,k)}}$ have value set $V^{m}_{i_{(m,k)}}$ satisfying the following property.

$$ $\{k,k+1,\cdots,k+3^{m-1}\}\subseteq V^{m}_{i_{(m,k)}}.$ (35) $$

###### Lemma C.4 .

For $m\geqslant 1$, $\forall k\in\{\frac{3-3^{j-1}}{2}\}_{2\leqslant j\leqslant\tilde{l}}$, there exist $i_{(m,k)}\in[1-{3^{\tilde{l}-1}},0]\cap\mathbb{Z}$ such that the node $N^{m}_{i_{(m,k)}}$ have value set $V^{m}_{i_{(m,k)}}$ satisfying the following property.

$$ $\{k,k+1,\cdots,k+3^{m-1}\}\subseteq V^{m}_{i_{(m,k)}}.$ (36) $$

###### Proof of Proposition C.2 .

The case $l=1$ is trivial and omitted. We use mathematical induction to prove this proposition.
We assert that for $l\geqslant 2$ the reasoning start node $N^{l}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}$ have value set $V^{l}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}$ satisfying

$$ $\{\frac{3-3^{l-1}}{2},\frac{3-3^{l-1}}{2}+1,\cdots,0,1,2,\cdots,\frac{3^{l-1}+1}{2}\}\subseteq V^{l}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}.$ (37) $$

The case $l=2$ can be verified easily.
We assume that for $l=l_{0}\in[2,\tilde{l}-1]\cap\mathbb{Z}$ the node $N^{l_{0}}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}$ have value set $V^{l_{0}}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}$ satisfying

$$ $\{\frac{3-3^{l_{0}-1}}{2},\frac{3-3^{l_{0}-1}}{2}+1,\cdots,0,1,2,\cdots,\frac{3^{l_{0}-1}+1}{2}\}\subseteq V^{l}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}.$ (38) $$

Now for $l=l_{0}+1$, by Lemma [C.3](https://arxiv.org/html/2509.23178v1#A3.Thmtheorem3), we know there exists a node $N^{l_{0}}_{i(l_{0},\frac{3^{l_{0}-1}+1}{2})}$ such that

$$ $\{\frac{3^{l_{0}-1}+1}{2},\cdots,\frac{3^{l_{0}-1}+1}{2}+3^{l_{0}-1}\}\subseteq V^{l_{0}}_{i(l_{0},\frac{3^{l_{0}-1}+1}{2})}.$ $$

And by Lemma [C.4](https://arxiv.org/html/2509.23178v1#A3.Thmtheorem4) there exist a node $N^{l_{0}}_{i(l_{0},\frac{3-3^{l_{0}}}{2})}$ such that

$$ $\{\frac{3-3^{l_{0}}}{2},\cdots,\frac{3-3^{l_{0}}}{2}+3^{l_{0}-1}\}\subseteq V^{l_{0}}_{i(l_{0},\frac{3-3^{l_{0}}}{2})}.$ $$

We then have

$$ $\displaystyle V^{l_{0}}_{i(l_{0},\frac{3^{l_{0}-1}+1}{2})}\cap V^{l_{0}}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}=\{\frac{3^{l_{0}-1}+1}{2}\},$ (39) $\displaystyle V^{l_{0}}_{i(l_{0},\frac{3-3^{l_{0}}}{2})}\cap V^{l_{0}}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}=\{\frac{3-3^{l_{0}-1}}{2}\},$ $$

and by Rule 3, we know that the node $N^{l_{0}+1}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}$ have value set $V^{l_{0}+1}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}$ satisfying

$$ $\displaystyle\{\frac{3-3^{l_{0}}}{2}\cdots,0,1,2,\cdots,\frac{3^{l_{0}}+1}{2}\}$ $\displaystyle=V^{l_{0}}_{i(l_{0},\frac{3^{l_{0}-2}+1}{2})}\cup V^{l_{0}}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}\cup V^{l_{0}}_{i(l_{0},\frac{3-3^{l_{0}-1}}{2})}$ (40) $\displaystyle\subseteq V^{l_{0}+1}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}.$ $$

This completes the proof of our assertion. From above assertion we know that $C^{l}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}\geqslant 3^{l-1}$. Combining the proof of Theorem [6.2](https://arxiv.org/html/2509.23178v1#S6.Thmtheorem2), we know that $C^{l}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}\leqslant 3^{l-1}$. And therefore
$C^{l}_{2\sigma(\frac{3^{\tilde{l}-1}-1}{2})+1}=3^{l-1}$.
∎

###### Proof of Lemma C.3 .

We use mathematical induction to prove this lemma. The case $m=2$ can be verified easily through Rule 2. We assume that for $m=m_{0}$, $\forall k\in\{\frac{3^{l-2}+1}{2}\}_{2\leqslant l\leqslant\tilde{l}}$,

$$ $\{k,k+1,\cdots,k+3^{m_{0}-1}\}\subseteq V^{m_{0}}_{i_{({m_{0}},k)}}.$ (41) $$

For $m=m_{0}+1$, by assumption, there exists $i(m_{0},k)$, $i(m_{0},k+3^{m_{0}-1})$, $i(m_{0},k+2\times 3^{m_{0}-1})$ such that

$$ $\displaystyle\{k,\cdots,k+3^{m_{0}-1}\}\subseteq V^{m_{0}}_{i(m_{0},k)},$ (42) $\displaystyle\{k+3^{m_{0}-1},\cdots,k+2\times 3^{m_{0}-1}\}\subseteq V^{m_{0}}_{i(m_{0},k+3^{m_{0}-1})},$ $\displaystyle\{k+2\times 3^{m_{0}-1},\cdots,k+3^{m_{0}}\}\subseteq V^{m_{0}}_{i(m_{0},k+2\times 3^{m_{0}-1})}.$ $$

Set $i{(m_{0}+1,k)}=\max\{{i(m_{0},k)},i(m_{0},k+3^{m_{0}-1}),i(m_{0},k+2\times 3^{m_{0}-1})\}$, by Rule 3 and ([42](https://arxiv.org/html/2509.23178v1#A3.E42)) we know that

$$ $\{k,\cdots,k+3^{m_{0}}\}\subseteq V^{m_{0}}_{i(m_{0},k)}\cup V^{m_{0}}_{i(m_{0},k+3^{m_{0}-1})}\cup V^{m_{0}}_{i(m_{0},k+2\times 3^{m_{0}-1})}\subseteq V^{m_{0}+1}_{i(m_{0}+1,k)},$ (43) $$

which completes the proof.
∎

The proof of Lemma [C.4](https://arxiv.org/html/2509.23178v1#A3.Thmtheorem4) is analogous to that of Lemma [C.3](https://arxiv.org/html/2509.23178v1#A3.Thmtheorem3) and is omitted.

###### Remark C.1 .

###### Proposition C.2 .

###### Lemma C.3 .

###### Lemma C.4 .

###### Proof of Proposition C.2 .

###### Proof of Lemma C.3 .

## Appendix D Construction of transformer

### D.1 Embedding

We assume that $d_{m}$ is large enough.
We choose a suitable embedding
(which can be done by choosing a suitable basis of $\mathbb{R}^{d_{m}}$)
such that the non-zero elements of all value vector ${\bm{X}}^{pos}$ are located in the first $n$ coordinates and all the elements in ${\bm{X}}^{tgt}$ located at the first $n$ coordinates are zero.

We denote ${\bm{X}}^{tgt}=({\bm{X}}^{tgt,\mathsf{T}}_{1},{\bm{X}}^{tgt,\mathsf{T}}_{2},\cdots,{\bm{X}}^{tgt,\mathsf{T}}_{n})^{\mathsf{T}}$ with each ${\bm{X}}^{tgt}_{i}=({\bm{X}}^{tgt}_{i,1},{\bm{X}}^{tgt}_{i,2},\cdots,{\bm{X}}^{tgt}_{i,d_{m}})\in\mathbb{R}^{d_{m}}$. Similarly, we denote ${\bm{X}}^{pos}=({\bm{X}}^{pos,\mathsf{T}}_{1},{\bm{X}}^{pos,\mathsf{T}}_{2},\cdots,{\bm{X}}^{pos,\mathsf{T}}_{n})^{\mathsf{T}}$ and ${\bm{X}}^{(l)}=({\bm{X}}^{(l),\mathsf{T}}_{1},{\bm{X}}^{(l),\mathsf{T}}_{2},\cdots,{\bm{X}}^{(l),\mathsf{T}}_{n})^{\mathsf{T}}$.

We correspond each element in the set $\tilde{E}$ to an index i.e., the set $\tilde{E}$ is of the form $\tilde{E}=\{{\bm{v}}_{1},{\bm{v}}_{2},\cdots,{\bm{v}}_{d}\}$. Moreover, each ${\bm{v}}_{i}$ is of the form $(\underbrace{0,0,\cdots,0}_{n\ \text{zeros}},0,\cdots,1,\cdots,0)$, and we denote $k_{i}$ the position of $1$.
Let $n\leqslant k_{1}<k_{2}<\cdots<k_{d}$, we require the embedding is chosen such that ${k_{i}}$ satisfies that

$$ $\left\{\begin{aligned} &k_{1}-n\geqslant 2(n+1)(3^{L}+1),\\ &k_{i}-k_{i-1}\geqslant 2(n+1)(3^{L}+1),\ \ \text{ for }2\leqslant i\leqslant\frac{n-1}{2},\\ &d_{m}-k_{\frac{n-1}{2}}\geqslant 2(n+1)(3^{L}+1).\end{aligned}\right.$ (44) $$

### D.2 Construction of parameters

We set the weight matrices as follows:

$$ $\displaystyle{\bm{W}}^{q(l)}={\bm{I}}(0\leqslant l\leqslant L),$ (45) $\displaystyle{\bm{W}}^{vo(l)}={\bm{I}}(1\leqslant l\leqslant L),\ {\bm{W}}^{vo(0)}={\bm{R}},$ (46) $\displaystyle{\bm{W}}^{k(l),\mathsf{T}}=\sum_{i=-(n+1)3^{L}}^{-1}{\bm{R}}^{i}(l\geqslant 1),\ \ {\bm{W}}^{k(0)}=\sum_{i=1}^{\frac{n-1}{2}}{\bm{p}}_{2i-1}{\bm{p}}_{2i}^{T}.$ (47) $$

Here ${\bm{p}}_{j}$ is the positional encoding and arbitrary two positional encodings are orthogonal to each other. Moreover, ${\bm{R}}\in\mathbb{R}^{d_{m}\times d_{m}}$ is defined as
${\bm{R}}=[\bm{R}_{ij}]$, with $\bm{R}_{i+1,i}=1=\bm{R}_{1d_{m}}\text{ for }1\leqslant i\leqslant d_{m}-1$, and all the other elements of ${\bm{R}}$ are set to be 0. In fact,

$$ ${\bm{R}}=\begin{bmatrix}0&0&0&\cdots&1\\ 1&0&0&\cdots&0\\ 0&1&0&\cdots&0\\ \vdots&\vdots&\ddots&\ddots&\vdots\\ 0&0&\cdots&1&0\end{bmatrix}.$ $$

This matrix ${\bm{R}}$ is called the left shift matrix. When we apply ${\bm{R}}$ to a vector ${\bm{v}}=({\bm{v}}_{1},{\bm{v}}_{2},\cdots,{\bm{v}}_{d_{m}})$ then result is ${\bm{v}}{\bm{R}}=({\bm{v}}_{2},\cdots,{\bm{v}}_{d_{m}-1},{\bm{v}}_{d_{m}},{\bm{v}}_{1})$.
The notation ${\bm{R}}^{i}$ means that the matrix ${\bm{R}}$ act $i$ times, i.e., ${\bm{v}}{\bm{R}}^{i}={\bm{v}}{\bm{R}}{\bm{R}}\cdots{\bm{R}}$. Also, the inverse of $mR$ is called the right shift matrix, and ${\bm{R}}^{-1}={\bm{R}}^{\mathsf{T}}$.

For any given matrix ${\bm{M}}=[m_{ij}]$, we define the mask operation as

$$ $\text{mask}({\bm{M}})=\begin{bmatrix}m^{(l)}_{1,1}&-\infty&-\infty&\cdots&-\infty\\ m^{(l)}_{2,1}&m^{(l)}_{2,2}&-\infty&\cdots&-\infty\\ m^{(l)}_{3,1}&m^{(l)}_{3,2}&m^{(l)}_{3,3}&\cdots&-\infty\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ m^{(l)}_{n,1}&m^{(l)}_{n,2}&\cdots&m^{(l)}_{n,n-1}&m^{(l)}_{n,n}\end{bmatrix}.$ (48) $$

Furthermore, we denote

$$ ${\bm{A}}^{(l)}=\mathrm{mask}({\bm{X}}^{(l)}{\bm{W}}^{q(l)}{\bm{W}}^{k(l),\mathsf{T}}{\bm{X}}^{(l),\mathsf{T}})=\begin{bmatrix}{\bm{A}}^{(l)}_{1,1}&-\infty&-\infty&\cdots&-\infty\\ {\bm{A}}^{(l)}_{2,1}&{\bm{A}}^{(l)}_{2,2}&-\infty&\cdots&-\infty\\ {\bm{A}}^{(l)}_{3,1}&{\bm{A}}^{(l)}_{3,2}&{\bm{A}}^{(l)}_{3,3}&\cdots&-\infty\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ {\bm{A}}^{(l)}_{n,1}&{\bm{A}}^{(l)}_{n,2}&\cdots&{\bm{A}}^{(l)}_{n,n-1}&{\bm{A}}^{(l)}_{n,n}\end{bmatrix}.$ (49) $$

We shall still use the notation $N^{l}_{i}$ to denote the $i$th node in $l$th layer with slightly modification: the value set ${\bm{V}}^{l}_{i}$ is now a set ${\bm{V}}^{l}_{i}$ which contains the embedded value as element.

Given any reasoning chain $({\bm{a}}_{u})_{1\leqslant i\leqslant n}$, after embedding it is of the form

$$ $(\tilde{{\bm{a}}}_{u})=((\tilde{{\bm{a}}}^{1}_{u},\tilde{{\bm{a}}}^{2}_{u}))_{1\leqslant i\leqslant n}=(({{\bm{a}}}^{1}_{u}{\bm{W}}^{\operatorname{emb}},{{\bm{a}}}^{2}_{u}{\bm{W}}^{\operatorname{emb}}))_{1\leqslant i\leqslant n}.$ $$

We define a sequence $(\tilde{{\bm{b}}}_{v})_{1\leqslant v\leqslant n+1}$ as follows:

$$ $\displaystyle\tilde{{\bm{b}}}_{v}=\tilde{{\bm{a}}}^{1}_{v},\ \ \text{for }1\leqslant v\leqslant n,$ (50) $\displaystyle\tilde{{\bm{b}}}_{v}=\tilde{{\bm{a}}}^{2}_{n}\ \ \text{for }v=n+1.$ $$

Assume the node $N^{l}_{i}$ contains the information from $(\tilde{a}_{i})$, then its value set ${\bm{V}}^{l}_{i}$ must contain the elements from a subsequence of $\tilde{{\bm{b}}}_{v\in{[v_{1},v_{2}]\cap\mathbb{Z}}}$ where $v_{1},v_{2}$ depends on $i$ and $l$.
For simplicity, we set ${\bm{b}}^{l}_{i,v}=\tilde{{\bm{b}}}_{v_{1}+v-1}$ for $v\in[1,v_{2}-v_{1}+1]\cap\mathbb{Z}$. In fact, $v_{2}-v_{1}+1=C^{l}_{i}$.

With these notations, we define the FNN as follows

$$ $\left\{\begin{aligned} L^{l}_{N}(f^{l}_{i}({\bm{X}}^{ao(l)}_{i})+({\bm{X}}^{ao(l)}_{i}))&=\sum_{1\leqslant k\leqslant C^{l}_{i}}{\bm{b}}_{i;k}{\bm{R}}^{i3^{L}-j+k}\text{ for }i\geqslant 2,\\ L^{l}_{N}(f^{l}_{i}({\bm{X}}^{ao(l)}_{i})+({\bm{X}}^{ao(l)}_{i}))&={\bm{X}}^{tgt}_{1}{\bm{R}}^{(n+1)3^{L}}\ \text{for }\ i=1.\end{aligned}\right.$ (51) $$

Here $L_{N}$ stands for LayerNorm and $j\in[1,n]\cap\mathbb{Z}$ satisfies ${\bm{b}}^{l}_{i,j}=X^{tgt}_{i}$.

###### Remark D.1 .

Note that this is not an accurate expression, since we can not simply define the output of a FNN. However, we can show that there exist $f^{(l)}_{i}$ for each layer such that the output of $L_{N}(f^{l}_{i}({\bm{X}}^{ao(l)}_{i})+({\bm{X}}^{ao(l)}_{i}))$ differs very little from the right-hand side of ([51](https://arxiv.org/html/2509.23178v1#A4.E51)).
And also the information propagation won’t be affected by this error. This will be explained in detail in later sections.

By this construction the reasoning information contained in the node $N^{l}_{i}$ is encoded by $L_{N}(f^{l}_{i}(\cdot)+(\cdot))$.

In order to extract the result after m-step reasoning, we set

$$ ${\bm{W}}^{p}={\bm{R}}^{-n3^{L}-m+1}{\bm{Q}}{\bm{W}}^{emb,\mathsf{T}},$ (52) $$

where ${\bm{Q}}$ satisfies ${\bm{Q}}{\bm{v}}_{1}={\bm{v}}_{1}$, …, ${\bm{Q}}{\bm{v}}_{d}={\bm{v}}_{d}$ and maps other basis to 0.
Note that last token on the $s$-th layer is ${\bm{X}}_{n}^{(L)}={\bm{b}}_{n;1}{\bm{R}}^{n3^{s}-j+1}+......+{\bm{b}}_{n;t}{\bm{R}}^{n3^{s}+t-j}$, and we have

$$ ${\bm{X}}_{n}^{(L)}{\bm{W}}^{p}={\bm{b}}_{n;1}{\bm{R}}^{-j-m+2}{\bm{Q}}{\bm{W}}^{emb,\mathsf{T}}+......+{\bm{b}}_{n;t}{\bm{R}}^{t-j-m+1}{\bm{Q}}{\bm{W}}^{emb,\mathsf{T}},$ (53) $$

and the output

$$ ${\bm{Y}}=argmax(\tilde{\sigma}({\bm{X}}_{n}^{(L)}{\bm{W}}^{p})).$ (54) $$

When $m+j-1\leqslant t$, ${\bm{X}}_{n}^{(L)}{\bm{W}}^{p}={\bm{b}}_{n;m+j-1}{\bm{W}}^{emb,\mathsf{T}}$ and the above setting yields the desired reasoning result.
However, when $m+j-1>t$, ${\bm{X}}_{n}^{(L)}{\bm{W}}^{p}=0$ and therefore we can not get a right reasoning result.

In fact, the sufficiency of transformer depth $s$ relative to the required reasoning steps $m$ is a key factor in ensuring accurate reasoning result.

We can roughly categorize this relationship into three cases

- •
Case 1 $m\leqslant 2^{L-1}-1$;
- •
Case 2 $2^{s-1}\leqslant m\leqslant\frac{3^{L-1}+1}{2}$;
- •
Case 3 $m>\frac{3^{L-1}-1}{2}$.

For the first case, note that $t-j+1\geq 2^{L-1}-1$ and therefore $m+j-1\leq t$ which means we can get the result.
For the third case, since $t-j+1\leq\frac{3^{L-1}+1}{2}$ and consequently $m+j-1>t$, the model can not derive the result.
The second case is more complicated, since we can not derive the relationship of $t-j+1$ and $t$ from the relationship of $m$ and $s$. Whether the model can derive the reasoning result now depends on $t-j+1$ and $t$.

###### Remark D.1 .

### D.3 Explanation

First, we explain how the same token matching rule works in this construction. More specifically, the attention matrices defined above satisfy the following property.

###### Lemma D.2 .

For $l\geqslant 1$, we have

$$ $\displaystyle{\bm{A}}^{(l)}_{i,j}=0,\text{ if }\ \ j=1,$ (55) $\displaystyle{\bm{A}}^{(l)}_{i,j}=0,\text{ if }\ \ i\geqslant j\geqslant 2,\ {\bm{V}}^{l}_{i}\cap{\bm{V}}^{l}_{j}=\emptyset,$ $\displaystyle{\bm{A}}^{(l)}_{i,j}\geqslant 1,\text{ if }\ \ i\geqslant j\geqslant 2,\ {\bm{V}}^{l}_{i}\cap{\bm{V}}^{l}_{j}\neq\emptyset.$ $$

###### Proof.

Start with given any ${\bm{X}}^{(0)}=({\bm{X}}^{(0)}_{1},{\bm{X}}^{(0)}_{2},\cdots,{\bm{X}}^{(0)}_{n})^{\mathsf{T}}$, we denote ${\bm{X}}^{(l)}=({\bm{X}}^{(l)}_{1},{\bm{X}}^{(l)}_{2},\cdots,{\bm{X}}^{(l)}_{n})$ with ${\bm{X}}^{(l)}_{i}=\sum_{u=1}^{C^{l}_{i}}{\bm{b}}^{l}_{i;u}{\bm{R}}^{i3^{L}+u-d^{(l)}_{i}}$,
where $C^{l}_{i}=|{\bm{V}}^{l}_{i}|$ and ${\bm{b}}^{l}_{i;u}\in\tilde{E}$.

$$ $\displaystyle{\bm{A}}^{(l-1)}_{i,j}$ $\displaystyle={\bm{X}}^{(l-1)}_{i}{\bm{R}}^{q(l-1)}{\bm{R}}^{k(l-1),\mathsf{T}}{\bm{X}}_{j}^{(l-1),\mathsf{T}}$ (56) $\displaystyle=(\sum_{u=1}^{C^{l-1}_{i}}{\bm{b}}_{i;u}^{l-1}{\bm{R}}^{i3^{L}+u-d^{(l-1)}_{i}})(\sum_{m=-(n+1)3^{L}}^{-1}{\bm{R}}^{m})(\sum_{v=1}^{C^{l-1}_{j}}{\bm{b}}_{j;v}^{l-1}{\bm{R}}^{j3^{L}+v-d^{(l-1)}_{j}})^{\mathsf{T}}$ (57) $\displaystyle=\sum_{u=1}^{C^{l-1}_{i}}\sum_{m=-(n+1)3^{L}}^{-1}\sum_{v=1}^{C^{l-1}_{j}}{\bm{b}}_{i;u}^{l-1}{\bm{R}}^{i3^{L}+u-d^{(l-1)}_{i}-j3^{L}-v+d^{(l-1)}_{j}+m}{\bm{b}}^{l-1,\mathsf{T}}_{j;v}$ (58) $$

For any $i\geqslant j\geqslant 2$ and ${\bm{V}}^{l-1}_{i}\cap{\bm{V}}^{l-1}_{j}=\emptyset$.

Since $-(n+1)3^{L}\leqslant i3^{L}+u-d^{(l-1)}_{i}-j3^{L}-v+d^{(l-1)}_{j}+m\leqslant(n+1)3^{L}$ and ${\bm{b}}_{i;u}^{l}\neq{\bm{b}}^{l}_{j;v}$, we have ${\bm{b}}_{i;u}^{l-1}{\bm{R}}^{i3^{L}+u-d^{(l-1)}_{i}-j3^{L}-v+d^{(l-1)}_{j}+m}{\bm{b}}^{l-1,\mathsf{T}}_{j;v}=0$.
Therefore, ${\bm{A}}^{(l-1)}_{i,j}=0$.

When $i\geqslant j\geqslant 2$ and ${\bm{V}}^{l-1}_{i}\cap{\bm{V}}^{l-1}_{j}\neq\emptyset$,

$$ $\displaystyle{\bm{A}}^{(l-1)}_{i,j}$ $\displaystyle=\sum_{u=1}^{C^{l-1}_{i}}\sum_{m=-(n+1)3^{L}}^{-1}\sum_{v=1}^{C^{l-1}_{j}}{\bm{b}}_{i;u}^{l-1}{\bm{R}}^{i3^{L}+u-d^{(l-1)}_{i}-j3^{L}-v+d^{(l-1)}_{j}+m}{\bm{b}}^{l-1,\mathsf{T}}_{j;v}$ (59) $$

Since ${\bm{V}}^{l-1}_{i}\cap{\bm{V}}^{l-1}_{j}\neq\emptyset$, there exists $j,v,i,v_{0}$ such that ${\bm{b}}^{l-1}_{j;v}={\bm{b}}^{l-1}_{i;v_{0}}$. Moreover, since
$1\leqslant i3^{L}+u-d^{(l-1)}_{i}-j3^{L}-v+d^{(l-1)}_{j}+m\leqslant(n+1)3^{L}$ and there exists $j,v,i,v_{0}$ such that ${\bm{b}}^{l-1}_{j;v}={\bm{b}}^{l-1}_{i;v_{0}}$,
there exists $m_{0}$ s.t. ${\bm{b}}^{l-1}_{j;v}{\bm{R}}^{i3^{L}+u_{0}-d^{(l-1)}_{i}-j3^{L}-v_{0}+d^{(l-1)}_{j}+m_{0}}{\bm{b}}^{(l-1),\mathsf{T}}_{j;v_{0}}=1$.
This indicates that ${\bm{A}}^{(l-1)}_{i,j}\geq 1$

When $j=1$,

$$ $\displaystyle{\bm{A}}^{(l-1)}_{i,1}=\sum_{u=1}^{C^{l-1}_{i}}\sum_{m=-(n+1)3^{L}}^{-1}{\bm{b}}^{l-1}_{i;u}{\bm{R}}^{i3^{L}+u-d^{(l-1)}_{i}-(n+1)3^{L}-1+m}{\bm{X}}^{tgt,\mathsf{T}}_{1}$ (60) $$

Since $-2(n+1)3^{L}-1\leqslant i3^{L}+u-d^{(l-1)}_{i}-(n+1)3^{L}-1+m\leqslant-1$, we know that ${\bm{A}}^{(l-1)}_{i,1}=0$.
∎

###### Lemma D.2 .

###### Proof.

### D.4 Information propagation

Next, we explain how the above defined transformer extract reasoning result.

${\bm{X}}^{ao(0)}={\bm{X}}^{(0)}+{\bm{X}}^{qkv(0)}$

When $l=0$, for $i\geqslant j$, using ([45](https://arxiv.org/html/2509.23178v1#A4.E45)), ([46](https://arxiv.org/html/2509.23178v1#A4.E46)), ([47](https://arxiv.org/html/2509.23178v1#A4.E47)) and ([49](https://arxiv.org/html/2509.23178v1#A4.E49)) we have

$$ $\displaystyle{\bm{A}}_{i,j}^{(0)}$ $\displaystyle={\bm{X}}_{i}^{(0)}(\sum_{t=1}^{\frac{n-1}{2}}{\bm{p}}_{2t}{\bm{p}}_{2t-1}^{\mathsf{T}}){\bm{X}}_{j}^{(0),\mathsf{T}}$ (61) $\displaystyle=\sum^{\frac{n-1}{2}}_{t=1}{\bm{X}}_{i}^{tgt}{\bm{p}}_{2t}{\bm{p}}_{2t-1}^{\mathsf{T}}{\bm{X}}_{j}^{tgt,\mathsf{T}}+\sum^{\frac{n-1}{2}}_{t=1}{\bm{X}}_{i}^{pos}{\bm{p}}_{2t}{\bm{p}}_{2t-1}^{\mathsf{T}}{\bm{X}}_{j}^{tgt,\mathsf{T}}+\sum^{\frac{n-1}{2}}_{t=1}{\bm{X}}_{i}^{pos}{\bm{p}}_{2t}{\bm{p}}_{2t-1}^{\mathsf{T}}{\bm{X}}_{j}^{pos,\mathsf{T}}$ $\displaystyle+\sum^{\frac{n-1}{2}}_{t=1}{\bm{X}}_{i}^{tgt}{\bm{p}}_{2t}{\bm{p}}_{2t-1}^{\mathsf{T}}{\bm{X}}_{j}^{pos,\mathsf{T}}$ $$

It is clear that

$$ $\displaystyle{\bm{A}}_{i,j}^{(0)}=1,\ \text{when $i=j+1$ and $i\bmod 2=0$, }$ (62) $\displaystyle{\bm{A}}_{i,j}^{(0)}=0,\ \text{when $i\neq j+1$ or $i\bmod 2\neq 0$. }$ $$

Then for $m\in[1,n]\cap\mathbb{Z}$, we get ${\bm{X}}_{m}^{ao(0)}=\sum_{i=1}^{m}\frac{\exp({\bm{A}}^{(0)}_{m,i})}{\sum_{j=1}^{m}\exp({\bm{A}}^{(0)}_{m,j})}{\bm{X}}_{i}^{(0)}{\bm{R}}+{\bm{X}}_{m}^{(0)}$, when $m\bmod 2=0$, we can get reasoning chain $({\bm{b}}_{m;1}^{(1)},{\bm{b}}_{m;2}^{(1)})$.

In fact, we set all the coefficient $\frac{\exp(0)}{{\sum_{j=1}^{m}\exp({\bm{A}}^{(0)}_{m,j})}}$ to be 0, then ${\bm{X}}_{m}^{ao(1)}$ is of the form $\frac{\exp(1)}{\sum_{t=1}^{m}\exp({\bm{A}}^{(0)}_{m,t})}{\bm{b}}_{m;1}^{(1)}{\bm{R}}+{\bm{b}}_{m;2}^{(1)}$.

By ([51](https://arxiv.org/html/2509.23178v1#A4.E51)) we have $L^{0}_{N}(f_{m}^{(0)}({\bm{X}}_{m}^{ao(0)})+{\bm{X}}_{m}^{ao(0)})=b^{(1)}_{m;1}{\bm{R}}^{m3^{L}-1}+b_{m;2}^{(1)}{\bm{R}}^{m3^{L}}$

When $m\bmod 2\neq 0$ and $m>1$, we can recognize $b_{m;1}^{(0)}={\bm{X}}_{m}^{tgt}$, and $L^{0}_{N}(f_{m}^{(0)}({\bm{X}}_{m}^{ao(0)})+{\bm{X}}_{m}^{ao(0)})=b_{m;1}^{(1)}{\bm{R}}^{m3^{s}}$

When $m=1$, we can recognize ${\bm{b}}_{1;1}^{(1)}={\bm{X}}_{1}^{tgt}$, and
$L^{0}_{N}(f_{1}^{(0)}({\bm{X}}_{1}^{ao(0)}+{\bm{X}}_{1}^{ao(0)}))={\bm{b}}_{1;1}^{(1)}{\bm{R}}^{(n+1)3^{L}}$.

After the first layer decoder, the even positions pass information to subsequent odd positions. And we can eliminate the position vectors on the second floor.

In fact, by our construction we have

$$ $\displaystyle{\bm{X}}^{ao(l-1)}_{i}$ $\displaystyle=\sum_{j=1}^{i}\frac{\exp({\bm{A}}^{(l-1)}_{i,j})}{\sum_{t=1}^{i}\exp({\bm{A}}^{(l-1)}_{i,t})}{\bm{X}}_{j}^{(l-1)}+{\bm{X}}^{(l-1)}_{i}$ (63) $\displaystyle=\sum_{j=1}^{i}\frac{\exp({\bm{A}}^{(l-1)}_{i,j})}{\sum_{t=1}^{i}\exp({\bm{A}}^{(l-1)}_{i,t})}\sum_{u=1}^{C^{l-1}_{j}}{\bm{b}}^{l-1}_{j;u}{\bm{R}}^{j3^{L}+u-d^{(l-1)}_{j}}+\sum_{u=1}^{C^{l-1}_{i}}{\bm{b}}^{l-1}_{i;u}{\bm{R}}^{i3^{L}+u-d^{(l-1)}_{i}}.$ (64) $$

For any $i,\ j$ such that $i\neq j$, note that $|u-d^{(l-1)}_{j}|\leqslant\frac{3^{L}-1}{2}$ and $|v-d^{(l-1)}_{i}|\leqslant\frac{3^{L}-1}{2}$, by theorem [6.2](https://arxiv.org/html/2509.23178v1#S6.Thmtheorem2), we have

$$ $\displaystyle|j3^{L}+u-d^{(l-1)}_{j}-i3^{L}-v+d^{(l-1)}_{i}|$ $\displaystyle=|(j-i)3^{L}+u-v-d^{(l-1)}_{j}+d^{(l-1)}_{i}|$ (65) $\displaystyle\geqslant 3^{L}-|u-v-d^{(l-1)}_{j}+d^{(l-1)}_{i}|\geqslant 1,$ (66) $\displaystyle|i3^{L}+u-d^{(l-1)}_{i}|\leqslant(n+1)3^{L}.$ (67) $$

And therefore, the nonzero element of ${\bm{b}}^{l-1}_{j;u}{\bm{R}}^{j3^{L}+u-d^{(l-1)}_{j}}$ and ${\bm{b}}^{l-1}_{i;u}{\bm{R}}^{i3^{L}+u-d^{(l-1)}_{i}}$ ($i\neq j$) won’t locate at the same coordinate.

Denote ${\bm{X}}^{ao(l-1)}_{i}=({\bm{X}}^{ao(l-1)}_{i,1},\cdots,{\bm{X}}^{ao(l-1)}_{i,d_{m}})$.
Firstly, set the number on the axis which equals to $min_{1\leqslant j\leqslant i}\{{\bm{X}}^{ao(l-1)}_{i,j}>0\}$ to be 0.

Suppose the nonzero component of $X_{1}^{tgt}$ located at the $k_{p}$-th axis.
Then, $X_{i,k_{p}-(n+1)3^{L}}^{ao(l-1)}=\frac{exp(0)}{\sum_{1\leqslant j\leqslant i}exp(A_{i,j}^{(l-1)})}$.
Since $\min\limits_{1\leqslant j\leqslant i}\{{\bm{X}}^{ao(l-1)}_{i,j}>0\}=\frac{1}{\sum_{t=1}^{i}\exp({\bm{A}}^{(l-1)}_{i,t})}$, there remains the information propagated from ${\bm{X}}^{(l-1)}_{j}$ s.t. ${\bm{A}}^{(l-1)}_{i,j}\geqslant 1$ which indicates that ${\bm{V}}^{l-1}_{i}\cap{\bm{V}}^{l-1}_{j}\neq\emptyset$.
We use the sequence $({\bm{b}}^{l-1}_{i;1},\cdots,{\bm{b}}^{l-1}_{i;C^{l-1}_{i}})$ associated to $N^{l}_{i}$ and the sequence $({\bm{b}}^{l-1}_{j;1},\cdots,{\bm{b}}^{l-1}_{j;C^{l-1}_{j}})$ associated to $N^{l-1}_{j}$ to construct a new sequence $({\bm{b}}^{l}_{i})$
associated to $N^{l}_{i}$ in the following two rules.

- •
If ${\bm{V}}_{i}\subseteq{\bm{V}}_{j}$(resp. ${\bm{V}}_{j}\subseteq{\bm{V}}_{i}$), then we set $({\bm{b}}^{l}_{i})=({\bm{b}}^{l-1}_{i})$(resp. $({\bm{b}}^{l}_{i})=({\bm{b}}^{l-1}_{j})$).
- •
If ${\bm{V}}_{i}\not\subseteq{\bm{V}}_{j}$ and ${\bm{V}}_{j}\not\subseteq{\bm{V}}_{i}$. Since ${\bm{V}}_{i}\cap{\bm{V}}_{j}\neq\emptyset$ without loss of generality we assume the set ${\bm{V}}_{i}\cap{\bm{V}}_{j}$ is of the form $\{{\bm{b}}^{l-1}_{i;1},{\bm{b}}^{l-1}_{i;2},\cdots,{\bm{b}}^{l-1}_{i;k_{i}}\}$ for some $k_{i}\leqslant C^{l-1}_{i}$. Also, there exist $k_{j}\leqslant C^{l}_{j}$ such that
${\bm{b}}^{l-1}_{j;k_{j}}={\bm{b}}^{l-1}_{i;1}$. And therefore the sequence ${\bm{b}}^{l}_{i}$ is set to be $({\bm{b}}^{l-1}_{j;1},{\bm{b}}^{l-1}_{j;2},\cdots{\bm{b}}^{l-1}_{j;k_{j}},{\bm{b}}^{l-1}_{i;2},{\bm{b}}^{l-1}_{i;3}\cdots{\bm{b}}^{l-1}_{i;C^{l-1}_{i}})$.

Moreover, for a given node $N^{l-1}_{i}$ there might exist more than one node $N^{l-1}_{j}$ satisfying ${\bm{A}}^{(l-1)}_{i,j}\geqslant 1$.
Denote $\Lambda^{l}_{i}=\{j|{\bm{A}}^{(l)}_{i,j}\geqslant 1\}$,
then the information in each node $N^{l-1}_{k}$ with $k\in\Lambda^{l}_{i}$ is transmitted to $N^{l-1}_{i}$ as the above way by treating ${\bm{b}}^{l}_{i}$ as ${\bm{b}}^{l-1}_{i}$ each time.
More specifically, we set initially $N^{l}_{i}=N^{l-1}_{i}$ and correspondingly ${\bm{b}}^{l}_{i}={\bm{b}}^{l-1}_{i}$. Then for each $k\in\Lambda^{l}_{i}$ and for ${\bm{b}}^{l-1}_{k}$ associated to $N^{l-1}_{k}$, we update ${\bm{b}}^{(l)}_{i}$ as in the above two rules by setting ${\bm{b}}^{l-1}_{i}={\bm{b}}^{l}_{i}$ and ${\bm{b}}^{l-1}_{j}={\bm{b}}^{l-1}_{k}$.

###### Remark D.3 .

The information propagation in this transformer satisfies the rules as we defined in section [5](https://arxiv.org/html/2509.23178v1#S5).
Although we ignore the information propagated from the node $N^{l-1}_{1}$ by setting ${\bm{A}}^{(l-1)}_{i,1}=0$ for $l\geqslant 1$,
there won’t be any information loss. Since the first node in each layer will only contain one value which is also contained in $N^{1}_{2}$ by Rule 2.

###### Remark D.3 .

### D.5 Existence of approximating FNN and error analysis

We find the FNN we required in three steps.

- •
Step 1 Find continuous functions that decode the information;
- •
Step 2 Extend the continous function to allow small error;
- •
Step 3 Use universal approximation theorem to find a FNN to approximate the extended continuous functions.

### Step 1 , Continuous funtions

Since $\{({\bm{z}}_{1},\cdots,{\bm{z}}_{d_{m}})|{\bm{z}}_{i}\in\{0,1\}\}\subseteq\operatorname{Range}(L_{N})$, there exists continuous functions $f^{l-1}_{i}$ s.t.

$$ $L^{l-1}_{N}(f^{l-1}_{i}({\bm{X}}^{ao(l-1)}_{i}))=\sum_{u=1}^{C^{(l)}_{i}}{\bm{b}}^{l}_{i;u}{\bm{R}}^{i3^{s-1}+u-d^{(l)}_{i}}.$ (68) $$

By the universal approximation theorem (Theorem [D.9](https://arxiv.org/html/2509.23178v1#A4.Thmtheorem9)), we know that
a neural network can approximate any continuous function with arbitrarily small error.
In fact, we can prove the following theorem.

###### Lemma D.4 .

If $L_{N}(f)$ is a simple function, there exists a single-hidden-layer neural network $f^{\prime}$ for any $\epsilon^{\prime}$, such that:

$$ $\sup\limits_{x\in K}||L_{N}(f(x))-L_{N}(f^{\prime}(x))||<\epsilon^{\prime}$ $$

where $K\subseteq\mathbb{R}^{d}$ is an arbitrary compact set.

Here and in the sequel, we use the notation $\|\cdot\|$ to denote the $\infty$ norm of vectors, i.e. for $v=(v_{1},v_{2},\cdots,v_{d_{m}})\in\mathbb{R}^{d_{m}}$, $\|v\|=\max\limits_{1\leqslant i\leqslant{d_{m}}}|v_{i}|$.

As we have discussed earlier in remark [D.1](https://arxiv.org/html/2509.23178v1#A4.Thmtheorem1), we can not define a FNN such that it satisfies ([51](https://arxiv.org/html/2509.23178v1#A4.E51)). However, as we have shown in Lemma [D.4](https://arxiv.org/html/2509.23178v1#A4.Thmtheorem4), we can find a FNN such that it differs from ([51](https://arxiv.org/html/2509.23178v1#A4.E51)) by a small error $\varepsilon^{\prime}$.
And we now analyze the effect caused by this small error during the information propagation.

###### Lemma D.4 .

### Step 2: Expansion of f i f_{i}

To proceed, we shall use the following notations.
Note that for a given node $N^{l}_{i}$ the reasoning sequence contained in this node can be transmitted from an input matrix
$({\bm{X}}^{tgt}_{i})$ or a permutation of $({\bm{X}}^{tgt}_{i})$ say $({\bm{X}}^{tgt}_{\sigma(i)})$ where $\sigma\in\mathbb{Z}\cap[1,n]$.
In this case we denote correspondingly the output of $l$th layer in transformer as ${\bm{X}}^{(l)}_{\sigma,i}$ or simply ${\bm{X}}^{(l)}_{\sigma}$.
Also, when the input matrix is set to be ${\bm{X}}^{tgt}_{\sigma(i)}$, we denote correspondingly the sequence associated to each node $N^{l}_{i}$ as ${\bm{b}}^{l}_{\sigma,i;u}$, the attention matrices ${\bm{A}}$ as ${\bm{A}}_{\sigma,i,j}$ and $({\bm{X}}^{ao(l)}_{i})$ as $({\bm{X}}^{ao(l)}_{\sigma,i})$.

Moreover, for a given input matrix $({\bm{X}}^{tgt}_{i})$ and for fixed $i$, $l$ and $\sigma$ we denote the set

$$ $\displaystyle D^{l}_{\sigma,i}$ $\displaystyle=\{{\bm{Y}}\in\mathbb{R}^{d_{m}}:\ L^{l}_{N}\circ f^{l}_{i}({\bm{Y}})={\bm{X}}^{(l)}_{\sigma,i}\}$ (69) $\displaystyle\cap\{{\bm{Y}}\in\mathbb{R}^{d_{m}}:{\bm{Y}}={\bm{X}}^{ao(l-1)}_{\sigma,i}\}$ $$

And for a given input matrix $({\bm{X}}^{tgt}_{i})$ we define the equivalence class of permutations as follows

###### Definition D.5 .

For fixed $i\in[1,n]\cap\mathbb{Z}$ and fixed $l\in[1,L]\cap\mathbb{Z}$, two permutations $\sigma\in\operatorname{Sym}(\mathbb{Z}\cap[1,n])$ and $\tau\in\operatorname{Sym}(\mathbb{Z}\cap[1,n])$ are said to be $N^{l}_{i}$ level equivalent if and only if they satisfy

$$ ${\bm{X}}^{(l)}_{\sigma,i}={\bm{X}}^{(l)}_{\tau,i}.$ (70) $$

And the equivalence class of $\sigma$ is denoted as

$$ $[\sigma]^{l}_{i}=\{\tau\in\operatorname{Sym}(\mathbb{Z}\cap[1,n]):{\bm{X}}^{(l)}_{\sigma,i}={\bm{X}}^{(l)}_{\tau,i}\}.$ (71) $$

Moreover, we denote $E^{l}_{i}$ the set of all the $N^{l}_{i}$ level equivalent classes.

It is clear that $D^{l}_{\sigma,i}$ are all finite sets since $\operatorname{Sym}(\mathbb{Z}\cap[1,n])$ is a finite set.
We shall also use the notation $d(x,y)=\|x-y\|$.

To expand the $f^{l}_{i}$ defined in ([68](https://arxiv.org/html/2509.23178v1#A4.E68)), we need the following lemma.

###### Lemma D.6 .

For $\sigma_{1},\sigma_{2}\in\operatorname{Sym}(\mathbb{Z}\cap[1,n])$, and for $i\in\mathbb{Z}\cap[1,n]$, if $({\bm{b}}^{l+1}_{\sigma_{1},i})\neq({\bm{b}}^{l+1}_{\sigma_{2},i})$, then for ${\bm{X}}\in D^{l+1}_{\sigma_{1},i}$ and ${\bm{Y}}\in D^{l+1}_{\sigma_{2},i}$ we have
$d({\bm{X}},{\bm{Y}})>0$.

Since the sets $D^{l}_{\sigma,i}$ are all finite, then by Lemma [D.6](https://arxiv.org/html/2509.23178v1#A4.Thmtheorem6) for $\sigma_{1}$ and $\sigma_{2}$ satisfying ${\bm{V}}^{l}_{\sigma_{1}}\neq{\bm{V}}^{l}_{\sigma_{2}}$ we have

$$ $d^{l+1}_{i}=\min\limits_{{\bm{X}}\in D^{l}_{\sigma_{1},i},{\bm{Y}}\in D^{l}_{\sigma_{2},i}}d({\bm{X}},{\bm{Y}})>0.$ (72) $$

We now define the expansion of $f^{l}_{i}$ as follows

$$ $\tilde{f}_{i}^{l}=(L^{l}_{N})^{-1}\left(\sum_{[\sigma]^{l}_{i}\in E^{l}_{i}}\mathbf{1}_{D^{l+1}_{\sigma,i}+[-\delta_{i}^{l+1},\delta_{i}^{l+1}]^{n}}\right),$ (73) $$

for some $\delta^{l+1}_{i}\in(0,d^{l+1}_{i})$. Here the symbol $+$ in $D^{l+1}_{\sigma,i}+[-\delta_{i}^{l+1},\delta_{i}^{l+1}]^{n}$ denotes the addition of sets in $\mathbb{R}^{n}$,
and the condition $\delta_{i}^{l+1}<d_{i}^{(l+1)}$ ensures that ([73](https://arxiv.org/html/2509.23178v1#A4.E73)) are well-defined

###### Definition D.5 .

###### Lemma D.6 .

### Step 3 , approximating FNN

Note that for given $i$, $l$ and $\sigma$ the set $D^{l+1}_{\sigma,i}+[-\delta_{i}^{l+1},\delta_{i}^{l+1}]^{n}$ is a compact set,
according to Lemma [D.4](https://arxiv.org/html/2509.23178v1#A4.Thmtheorem4), $\forall\eta^{l+1}_{i}>0$,
there exist a single-hidden-layer neural network $\hat{f}^{l}_{i}$ such that

$$ $\sup\limits_{{\bm{X}}\in D^{l+1}_{\sigma,i}+[-\delta_{i}^{l+1},\delta_{i}^{l+1}]^{n}}||L^{l}_{N}(\hat{f}_{i}^{l})({\bm{X}})-L^{l}_{N}(\tilde{f}_{i}^{l})({\bm{X}})||<\eta_{i}^{(l+1)}.$ (74) $$

This $\hat{f}$ is the FNN we are looking for which can tranmit information as $f$. In fact we have following proposition.

###### Proposition D.7 .

For given ${\bm{X}}_{\sigma,i}^{ao(l)}$, we have

$$ $\displaystyle L^{l}_{N}(f_{i}^{(l)}({\bm{X}}_{\sigma,i}^{ao(l)}))={\bm{X}}^{(l+1)}_{\sigma,i};$ (75) $\displaystyle L^{l}_{N}(\hat{f}_{i}^{(l)}({\bm{X}}_{\sigma,i}^{ao(l)}))\in\{{\bm{X}}^{(l+1)}_{\sigma,i}\}+[-\epsilon,\epsilon]^{n}.$ $$

###### Proof.

Without loss of generality we set $L^{l}_{N}(\hat{f}_{i}^{(l)}({\bm{X}}^{ao(l)}_{\sigma,i}))=\sum_{u=1}^{C^{(l+1)}_{i}}{\bm{b}}^{l+1}_{iu}R^{i3^{s-1}+u-d^{(l+1)}_{i}}+\epsilon^{(l+1)}_{i}{\bm{r}}^{(l+1)}_{i}={\bm{X}}^{(l+1)}_{\sigma,i},\text{ where }|{\bm{r}}_{i}|=1,{\bm{r}}_{i}\in\mathbb{R}^{d_{m}}$.
Take $\epsilon^{(l)}_{i}<\epsilon$ and set

$$ $\bar{\bm{A}}^{(l)}_{i,j}=(\sum_{u=1}^{C^{l}_{i}}{\bm{b}}_{i;u}^{l}{\bm{W}}^{i3^{L}+u-d^{(l)}_{i}}+\epsilon^{(l)}_{i}{\bm{r}}^{(l)}_{i})(\sum_{m=-(n+1)3^{L}}^{-1}{\bm{W}}^{m})(\sum_{v=1}^{C^{l}_{j}}{\bm{b}}_{j;v}^{l}W^{j3^{L}+v-d^{(l)}_{j}}+\epsilon^{(l)}_{j}{\bm{r}}^{(l)}_{j})^{\mathsf{T}}$ $$

Since $\bar{\bm{A}}^{(l)}_{i,j}=\bm{A}^{(l)}_{i,j}+\epsilon^{(l)}_{i}{\bm{r}}^{(l)}_{i}(\sum_{m=-(n+1)3^{L}}^{-1}{\bm{W}}^{m})\epsilon^{(l)}_{j}{\bm{r}}^{(l)}_{j}$, we have
$\forall i,j,l$, $|\bar{\bm{A}}^{(l)}_{i,j}-\bm{A}^{(l)}_{i,j}|\leqslant 3^{L}(n+1)\epsilon^{(l)}_{i}\epsilon^{(l)}_{j}\leqslant\eta_{0}$.

And therefore,

$$ $\displaystyle\bar{\bm{X}}^{ao(l)}_{\sigma,i}$ $\displaystyle=\sum_{j=1}^{i}\frac{\exp(\bar{\bm{A}}^{(l)}_{i,j})}{\sum_{t=1}^{i}\exp(\bar{\bm{A}}^{(l)}_{i,t})}\bar{\bm{X}}_{\sigma,j}^{(l)}+\bar{\bm{X}}^{(l)}_{\sigma,i}$ (76) $\displaystyle=\sum_{j=1}^{i}\frac{\exp(\bar{\bm{A}}^{(l)}_{i,j})}{\sum_{t=1}^{i}\exp(\bar{\bm{A}}^{(l)}_{i,t})}(\sum_{u=1}^{C^{l}_{j}}{\bm{b}}^{l}_{j;u}{\bm{W}}^{j3^{L}+u-d^{(l)}_{j}}+\epsilon^{(l)}_{j}{\bm{r}}^{(l)}_{j})+\sum_{u=1}^{C^{l}_{i}}{\bm{b}}^{l}_{i;u}{\bm{W}}^{i3^{L}+u-d^{(l)}_{i}}+\epsilon^{(l)}_{i}{\bm{r}}^{(l)}_{i}$ $\displaystyle=\sum_{j=1}^{i}\frac{\exp(\bar{\bm{A}}^{(l)}_{i,j})}{\sum_{t=1}^{i}\exp(\bar{\bm{A}}^{(l)}_{i,t})}(\sum_{u=1}^{C^{l}_{j}}{\bm{b}}^{l}_{j;u}{\bm{W}}^{j3^{L}+u-d^{(l)}_{j}})+\sum_{u=1}^{C^{l}_{i}}{\bm{b}}^{l}_{i;u}{\bm{W}}^{i3^{L}+u-d^{(l)}_{i}}$ $\displaystyle+\sum_{j=1}^{i}\frac{\exp(\bar{\bm{A}}^{(l)}_{i,j})}{\sum_{t=1}^{i}\exp(\bar{\bm{A}}^{(l)}_{i,t})}\epsilon^{(l)}_{j}{\bm{r}}^{(l)}_{j}+\epsilon^{(l)}_{i}{\bm{r}}^{(l)}_{i},$ $$

along with

$$ $\displaystyle\bar{\bm{X}}^{ao(l)}_{\sigma,i}-{\bm{X}}_{\sigma,i}^{ao(l)}$ $\displaystyle=\sum_{j=1}^{i}\left[\frac{\exp(\bar{\bm{A}}^{(l)}_{i,j})}{\sum_{t=1}^{i}\exp(\bar{\bm{A}}^{(l)}_{i,t})}-\frac{\exp(\bm{A}^{(l)}_{i,j})}{\sum_{t=1}^{i}\exp(\bm{A}^{(l)}_{i,t})}\right](\sum_{u=1}^{C^{l}_{j}}{\bm{b}}^{l}_{ju}{\bm{W}}^{j3^{s-1}+u-d^{(l)}_{j}})$ (77) $\displaystyle+\sum_{j=1}^{i}\frac{\exp(\bar{\bm{A}}^{(l)}_{i,j})}{\sum_{t=1}^{i}\exp(\bar{\bm{A}}^{(l)}_{i,t})}\epsilon^{(l)}_{j}{\bm{r}}^{(l)}_{j}+\epsilon^{(l)}_{i}{\bm{r}}^{(l)}_{i}$ $$

Direct calculation and ([77](https://arxiv.org/html/2509.23178v1#A4.E77)) leads to

$$ $\|\bar{\bm{X}}_{\sigma,i}^{ao(l)}-{\bm{X}}_{\sigma,i}^{ao(l)}\|\leqslant\text{I}+\text{II},$ (78) $$

where

$$ I $\displaystyle=\max_{i,j,l}|\frac{\exp(\bar{\bm{A}}^{(l)}_{i,j})}{\sum_{t=1}^{i}\exp(\bar{\bm{A}}^{(l)}_{i,t})}-\frac{\exp({\bm{A}}^{(l)}_{i,j})}{\sum_{t=1}^{i}\exp({\bm{A}}^{(l)}_{i,t})}|,$ (79) II $\displaystyle=|\sum_{j=1}^{i}\frac{\exp(\bar{\bm{A}}^{(l)}_{i,j})}{\sum_{t=1}^{i}\exp(\bar{\bm{A}}^{(l)}_{i,t})}\epsilon^{(l)}_{j}{\bm{r}}^{(l)}_{j}+\epsilon^{(l)}_{i}{\bm{r}}^{(l)}_{i}|.$ (80) $$

Take $\eta_{0}$ small enough such that $\forall|x|<\eta_{0}$, $|\exp(x)-1|<2x$. We then have

$$ $\displaystyle\begin{aligned} \text{I}&\leqslant\max\bigg\{\frac{|\exp(\bar{\bm{A}}_{i,j}^{(l)})-\exp({\bm{A}}_{i,j}^{(l)})|\ |\sum_{t=1}^{i}\exp({\bm{A}}_{i,j}^{(l)})|}{(\sum_{t=1}^{i}\exp({\bm{A}}_{i,j}^{(l)}))(\sum_{t=1}^{i}\exp(\bar{\bm{A}}_{i,j}^{(l+1)}))}\\ &+\frac{|\sum_{t=1}^{i}(\exp({\bm{A}}_{i,j}^{(l)})-\exp(\bar{\bm{A}}_{i,j}^{(l)}))|\ |\exp({\bm{A}}_{i,j}^{(l)})|}{(\sum_{t=1}^{i}\exp({\bm{A}}_{i,j}^{(l)}))(\sum_{t=1}^{i}\exp(\bar{\bm{A}}_{i,j}^{(l)}))}\bigg\}\\ &\leqslant\max\bigg\{n\times\big|\exp(\bar{\bm{A}}_{i,j}^{(l)}-{\bm{A}}_{i,j}^{(l)})-1\ \big|\exp({\bm{A}}_{i,j}^{(l)})\exp(M)\\ &+(\sum_{t=1}^{i}|\exp(\bar{\bm{A}}_{i,t}^{(l)}-{\bm{A}}_{i,t}^{(l)})-1|)\exp({\bm{A}}_{i,j}^{(l)})\exp(M))\bigg\}\\ &\leqslant 2n\eta_{0}\exp(2M)+2n\eta_{0}\exp(2M)\\ &\leqslant 4n\eta_{0}\exp(2M)\end{aligned}$ (81) $\displaystyle\text{II}\leqslant(n+1)\epsilon.$ (82) $$

Combining ([77](https://arxiv.org/html/2509.23178v1#A4.E77)), ([81](https://arxiv.org/html/2509.23178v1#A4.E81)) and ([82](https://arxiv.org/html/2509.23178v1#A4.E82)) leads to

$$ $\|\bar{\bm{X}}_{\sigma,i}^{ao(l)}-{\bm{X}}_{\sigma,i}^{ao(l)}\|\leqslant\text{I}+\text{II}\leqslant 4n\eta_{0}\exp(2M)+(n+1)\epsilon.$ (83) $$

We then choose $\eta_{0}$ and $\epsilon$ small such that $4n\eta_{0}\exp(2M)+(n+1)\epsilon<\delta_{i}^{(l)}$, and thus
$\bar{\bm{X}}_{\sigma,i}^{ao(l)}\in D^{l+1}_{\sigma,i}+(-\delta_{i}^{l+1},\delta_{i}^{l+1})^{n}$.
Moreover, we have

$$ $L^{l}_{N}(\hat{f}_{i}^{(l)}({\bm{X}}_{\sigma,i}^{ao(l)}))=\sum_{u=1}^{C^{(l+1)}_{i}}{\bm{b}}^{l+1}_{i;u}{\bm{R}}^{i3^{s-1}+u-d^{(l+1)}_{i}}+\epsilon^{(l+1)}_{i}{\bm{r}}^{(l+1)}_{i}\in{\bm{X}}^{(l+1)}_{\sigma,i}+[-\epsilon,\epsilon]^{n},$ (84) $$

where $|{\bm{r}}_{i}|=1,{\bm{r}}_{i}\in\mathbb{R}^{d_{m}}$.
This completes the proof of our proposition.
∎

###### Lemma D.8 .

LayerNorm of the form $L_{N}(x)=\alpha\frac{x-\operatorname{E}(x)}{\sqrt{{\operatorname{Var}}(x)+\epsilon}}+\beta$,
where $\alpha,\beta$ and $\epsilon$ are constants and the function $\operatorname{E}(\cdot),\ \operatorname{\operatorname{Var}}(\cdot)$ stands for the expectation and variance respectively, is injective (i.e., For any $x_{1}\neq x_{2}$, we have $L_{N}(x_{1})\neq L_{N}(x_{2})$).

###### Proof of Lemma D.8 .

Note that
$L_{N}(x)=\alpha\frac{x-\operatorname{E}(x)}{\sqrt{\operatorname{\operatorname{Var}}(x)+\epsilon}}+\beta$,

For any $x_{1}\neq x_{2}$, if $L_{N}(x_{1})=L_{N}(x_{2})$, then we have

$$ $(\alpha\frac{x^{1}_{1}-\operatorname{E}(x_{1})}{\sqrt{\operatorname{\operatorname{Var}}(x_{1})+\epsilon}}+\beta,\cdots,\alpha\frac{x^{n}_{1}-\operatorname{E}(x_{1})}{\sqrt{\operatorname{\operatorname{Var}}(x_{1})+\epsilon}}+\beta)=(\alpha\frac{x^{1}_{2}-\operatorname{E}(x_{2})}{\sqrt{\operatorname{\operatorname{Var}}(x_{2})+\epsilon}}+\beta,\cdots,\alpha\frac{x^{n}_{2}-\operatorname{E}(x_{2})}{\sqrt{\operatorname{\operatorname{Var}}(x_{2})+\epsilon}}+\beta),$ $$

which leads to

$$ $\alpha\frac{x^{i}_{1}-\operatorname{E}(x_{1})}{\sqrt{\operatorname{\operatorname{Var}}(x_{1})+\epsilon}}+\beta=\alpha\frac{x^{i}_{2}-\operatorname{E}(x_{2})}{\sqrt{\operatorname{\operatorname{Var}}(x_{2})+\epsilon}}+\beta,\text{ for }1\leqslant i\leqslant n.$ (85) $$

Therefore, summation from $1$ to $n$ in both sides of ([85](https://arxiv.org/html/2509.23178v1#A4.E85)) leads to

$$ $\alpha\frac{n\operatorname{E}(x_{1})-\operatorname{E}(x_{1})}{\sqrt{\operatorname{\operatorname{Var}}(x_{1})+\epsilon}}+n\beta=\alpha\frac{n\operatorname{E}(x_{2})-\operatorname{E}(x_{2})}{\sqrt{\operatorname{\operatorname{Var}}(x_{2})+\epsilon}}+n\beta,$ $$

which indicates that

$$ $\frac{\operatorname{E}(x_{1})}{\sqrt{\operatorname{\operatorname{Var}}(x_{1})+\epsilon}}=\frac{\operatorname{E}(x_{2})}{\sqrt{\operatorname{\operatorname{Var}}(x_{2})+\epsilon}}.$ (86) $$

By ([85](https://arxiv.org/html/2509.23178v1#A4.E85)), we also have

$$ $\frac{x^{i}_{1}}{\sqrt{\operatorname{\operatorname{Var}}(x_{1})+\epsilon}}=\frac{x^{i}_{2}}{\sqrt{\operatorname{\operatorname{Var}}(x_{2})+\epsilon}},\text{ for }1\leqslant i\leqslant n.$ (87) $$

Combining ([86](https://arxiv.org/html/2509.23178v1#A4.E86)) and ([87](https://arxiv.org/html/2509.23178v1#A4.E87)) yields that

$$ $\frac{x_{1}}{x_{2}}=\frac{\operatorname{E}(x_{1})}{\operatorname{E}(x_{2})}=\frac{\sqrt{\operatorname{\operatorname{Var}}(x_{1})+\epsilon}}{\sqrt{\operatorname{\operatorname{Var}}(x_{2})+\epsilon}}.$ (88) $$

Set $k=\frac{\operatorname{E}(x_{1})}{\operatorname{E}(x_{2})}$, then $x^{i}_{1}=kx^{i}_{2}$, $\operatorname{E}(x_{1})=k\operatorname{E}(x_{2})$, and therefore $\operatorname{\operatorname{Var}}(x_{1})=k^{2}\operatorname{\operatorname{Var}}(x_{2})$. These relations together with ([87](https://arxiv.org/html/2509.23178v1#A4.E87)) lead to

$$ $\frac{x^{i}_{1}}{\sqrt{\operatorname{\operatorname{Var}}(x_{1})+\epsilon}}=\frac{kx^{i}_{1}}{\sqrt{k^{2}\operatorname{Var(x_{1})}+\epsilon}},\text{ for }1\leqslant i\leqslant n.$ (89) $$

Since $\epsilon>0$ and $\alpha\neq 0$, it is cleat that $k$ must be 1, which contradicts with $x_{1}\neq x_{2}$.
∎

###### Proof of Lemma D.6 .

We prove this lemma by contradiction.

Suppose that there exist ${\bm{X}}\in D^{l+1}_{\sigma_{1},i}$ and ${\bm{Y}}\in D^{l+1}_{\sigma_{2},i}$ such that $d({\bm{X}},{\bm{Y}})=0$.

Since $({\bm{b}}^{l+1}_{\sigma_{1},i})\neq({\bm{b}}^{l+1}_{\sigma_{2},i})$,
there exists $i_{0}$ and $j_{0}$ such that ${\bm{b}}_{\sigma_{1},i_{0},j_{0}}^{l}\in\{{\bm{b}}^{l+1}_{\sigma_{1},i,1},...,{\bm{b}}^{l+1}_{\sigma_{1},i,c_{\sigma_{1},i}^{(l+1)}}\}$ and ${\bm{b}}_{\sigma_{1},i_{0},j_{0}}^{l}\notin\{{\bm{b}}^{l+1}_{i,\sigma_{2},1},...,{\bm{b}}^{l+1}_{i,\sigma_{2},c_{i,\sigma_{2}}^{(l+1)}}\}$. For simplicity, we denote $h={\bm{b}}_{\sigma_{1},i_{0},j_{0}}^{l}$.

By ([69](https://arxiv.org/html/2509.23178v1#A4.E69)), we know that

$$ $\displaystyle{\bm{X}}={\bm{X}}_{\sigma_{1},i}^{ao(l)}$ $\displaystyle=\sum^{i}_{j=1}\frac{\exp(A_{\sigma_{1},i,j}^{(l)})}{\sum^{i}_{t=1}\exp(A_{\sigma_{1},i,t}^{(l)})}{\bm{X}}_{\sigma_{1},j}^{(l)}+{\bm{X}}_{\sigma_{1},i}^{(l)}$ (90) $\displaystyle=\sum^{i}_{j=1}\frac{\exp(A_{\sigma_{1},i,j}^{(l)})}{\sum^{i}_{t=1}\exp(A_{\sigma_{1},i,t}^{(l)})}\sum^{C_{\sigma_{1},j}^{l}}_{u=1}{\bm{b}}_{\sigma_{1},j;u}{\bm{R}}^{j\times 3^{L}+u-d_{\sigma_{1},j}^{(l)}}+\sum_{u=1}^{C_{\sigma_{1},j}^{l}}{\bm{b}}_{\sigma_{1},i;u}^{l}{\bm{R}}^{i\times 3^{L}+u-d_{\sigma_{1},i}^{(l)}}$ (91) $$

$$ $\displaystyle{\bm{Y}}={\bm{X}}_{\sigma_{2},i}^{ao(l)}$ $\displaystyle=\sum^{i}_{j=1}\frac{\exp(A_{\sigma_{2},i,j}^{(l)})}{\sum^{i}_{t=1}\exp(A_{\sigma_{2},i,t}^{(l)})}{\bm{X}}_{\sigma_{2},j}^{(l)}+{\bm{X}}_{\sigma_{2},i}^{(l)}$ (92) $\displaystyle=\sum^{i}_{j=1}\frac{\exp(A_{\sigma_{2},i,j}^{(l)})}{\sum^{i}_{t=1}\exp(A_{\sigma_{2},i,t}^{(l)})}\sum^{C_{\sigma_{2},j}^{l}}_{u=1}{\bm{b}}_{\sigma_{2},j;u}{\bm{R}}^{j\times 3^{L}+u-d_{\sigma_{2},j}^{(l)}}+\sum_{u=1}^{C_{\sigma_{2},j}^{l}}{\bm{b}}_{\sigma_{2},i;u}^{l}{\bm{R}}^{i\times 3^{L}+u-d_{\sigma_{2},i}^{(l)}}$ (93) $$

If $h\notin\cup_{t=1}^{i}V_{t}^{l}$, then we know that $X^{ao(l)}_{\sigma_{1},i,u}\geqslant\frac{\exp(1)}{\sum_{t=1}^{i}\exp({\bm{A}}^{(l)}_{\sigma_{1},t})}$ and $X^{ao(l)}_{\sigma_{2},i,u}=0$ which contradicts with our assumption.

If $h\in\cup_{t=1}^{i}V_{t}^{l}$ then $X^{ao(l)}_{\sigma_{2},i,u}$ can either be $\frac{\exp(0)}{\sum_{t=1}^{i}\exp({\bm{A}}^{(l)}_{\sigma_{2},t})}$ or 0. The case $X^{ao(l)}_{\sigma_{2},i,u}=0$ clearly contradicts with our assumption. Hence, we consider only the case
$X^{ao(l)}_{\sigma_{2},i,u}=\frac{\exp(0)}{\sum_{t=1}^{i}\exp({\bm{A}}^{(l)}_{\sigma_{2},t})}$.
And we then know that

$$ $X^{ao(l)}_{\sigma_{1},i,u}\geqslant\frac{\exp(1)}{\sum_{t=1}^{i}\exp({\bm{A}}^{(l)}_{\sigma_{1},t})},\ \ X^{ao(l)}_{\sigma_{2},i,u}=\frac{\exp(0)}{\sum_{t=1}^{i}\exp({\bm{A}}^{(l)}_{\sigma_{2},t})}.$ (94) $$

Suppose the nonzero components of ${\bm{X}}_{\sigma_{1},1}^{(tgt)}$ and ${\bm{X}}_{\sigma_{2},1}^{(tgt)}$ located at as the $k_{\sigma_{1},1}$-th axis and the $k_{\sigma_{2},1}$-th axis respectively. Note that

$$ $\displaystyle{\bm{X}}_{\sigma_{1},1}^{(l)}$ $\displaystyle={\bm{X}}_{\sigma_{1},1}^{tgt}R^{(n+1)3^{L}},$ (95) $\displaystyle{\bm{X}}_{\sigma_{2},1}^{(l)}$ $\displaystyle={\bm{X}}_{\sigma_{2},1}^{tgt}R^{(n+1)3^{L}},$ (96) $$

and that by ([44](https://arxiv.org/html/2509.23178v1#A4.E44)) the distance between any two embedding axis $\geqslant 2(n+1)(3^{L}+1)$, we have

$$ $\displaystyle{\bm{X}}_{\sigma_{1},i,k_{\sigma_{1},1}-3^{s-1}n}^{ao(l)}$ $\displaystyle=\frac{\exp(0)}{\sum^{i}_{t=1}\exp({\bm{A}}_{\sigma_{1},i,t}^{(l)})},$ (97) $\displaystyle{\bm{X}}_{\sigma_{2},i,k_{\sigma_{2},1}-3^{s-1}n}^{ao(l)}$ $\displaystyle=\frac{\exp(0)}{\sum^{i}_{t=1}\exp({\bm{A}}_{\sigma_{2},i,t}^{(l)})}.$ (98) $$

If $k_{\sigma_{1},1}\neq k_{\sigma_{2},1}$,

$$ $\frac{\exp(0)}{\sum^{i}_{t=1}\exp({\bm{A}}_{\sigma_{2},i,t}^{(l)})}={\bm{X}}_{\sigma_{1},i,k_{\sigma_{1},1}-3^{L}n}^{ao(l)}={\bm{X}}_{\sigma_{2},i,k_{\sigma_{1},1}-3^{L}n}^{ao(l)}=0$ $$

,

which is impossible. Therefore, we have $k_{\sigma_{1},1}=k_{\sigma_{2},1}$.

In addition, there exist ${\bm{v}}_{q}\in\tilde{E}$ and the corresponding $k_{q}$ such that $k_{q}=k_{\sigma_{1},1}=k_{\sigma_{2},1}$, the components of ${\bm{X}}^{ao(l)}_{\sigma_{1},i}$ and ${\bm{X}}^{ao(l)}_{\sigma_{2},i}$ on the $(k_{q}-(n+1)3^{L})$-th axis are equal, which leads to

$$ $\frac{1}{\sum^{i}_{t=1}\exp(A_{\sigma_{1},i},t)}=\frac{1}{\sum^{i}_{t=1}\exp(A_{i,\sigma_{2}},t)}.$ (99) $$

Combining ([94](https://arxiv.org/html/2509.23178v1#A4.E94)) and ([99](https://arxiv.org/html/2509.23178v1#A4.E99)) leads to contradiction with $d({\bm{X}},{\bm{Y}})=0$. And we complete the proof of Lemma [D.6](https://arxiv.org/html/2509.23178v1#A4.Thmtheorem6).
∎

###### Proof of Lemma D.4 .

By Lemma [D.8](https://arxiv.org/html/2509.23178v1#A4.Thmtheorem8), we can easily know that $(L^{l}_{N})^{-1}(L^{l}_{N}(f))=f$ is also a simple function.

According to the lemma above,

there exists a single-hidden-layer neural network $f^{\prime}$ for any $\epsilon_{0}$ s.t

$$ $\sup\limits_{x\in K}||f(x)-f^{\prime}(x)||<\epsilon_{0}$ $$

Set $M=\max\limits_{x\in K}||f^{\prime}(x)||$, for any $||x-y||<\epsilon_{0}$,

$$ $\displaystyle|L_{N}(x)-L_{N}(y)|$ $\displaystyle=|\alpha\frac{x-\operatorname{E}(x)}{\sqrt{\operatorname{Var}(x)+\epsilon}}-\alpha\frac{y-\operatorname{E}(y)}{\sqrt{\operatorname{Var}(y)+\epsilon}}|$ (100) $\displaystyle=|\alpha|\times|\frac{(x-\operatorname{E}(x))\sqrt{\operatorname{Var}(y)+\epsilon}-(y-\operatorname{E}(y))\sqrt{\operatorname{Var}(x)+\epsilon}}{\sqrt{\operatorname{Var}(y)+\epsilon}\sqrt{\operatorname{Var}(x)+\epsilon}}|$ $\displaystyle\leqslant|\alpha|\times\frac{||(x-y-(\operatorname{E}(x)-\operatorname{E}(y))||\sqrt{\operatorname{Var}(y)+\epsilon}}{\epsilon}$ $\displaystyle+|\alpha|\times\frac{||y-\operatorname{E}(y)||\ |\sqrt{\operatorname{Var}(x)+\epsilon}-\sqrt{\operatorname{Var}(y)+\epsilon}|}{\varepsilon}.$ $$

Since $||\operatorname{E}(x)-\operatorname{E}(y)||\leqslant||x-y||\leqslant\epsilon_{0}$ and $\operatorname{Var}(y)=\operatorname{E}(y)^{2}-(\operatorname{E}(y))^{2}\leqslant\operatorname{E}(y)^{2}\leqslant(M+\epsilon_{0})^{2}$ we have

$$ $\displaystyle|\operatorname{E}(x)^{2}-\operatorname{E}(y)^{2}|$ $\displaystyle=|\operatorname{E}(x-y)(x+y)|$ (101) $\displaystyle\leqslant\sqrt{\operatorname{E}(x-y)^{2}\ \operatorname{E}(x+y)^{2}}$ $\displaystyle\leqslant\sqrt{\epsilon_{0}^{2}\ (2M+\epsilon_{0})^{2}},$ $$

and

$$ $\displaystyle|\sqrt{\operatorname{Var}(x)+\epsilon}-\sqrt{\operatorname{Var}(y)+\epsilon}|$ $\displaystyle=\frac{|\operatorname{Var}(x)-\operatorname{Var}(y)|}{\sqrt{\operatorname{Var}(x)+\epsilon}\sqrt{\operatorname{Var}(y)+\epsilon}}$ (102) $\displaystyle\leqslant\frac{|\operatorname{E}(x)^{2}-\operatorname{E}(y)^{2}|+|(\operatorname{E}(x))^{2}-(\operatorname{E}(y))^{2}|}{\epsilon}$ $\displaystyle\leqslant\frac{\epsilon_{0}(2M+\epsilon_{0})+\epsilon_{0}(2M+\epsilon_{0})}{\epsilon},$ $$

$$ $\displaystyle|L_{N}(x)-L_{N}(y)|$ $\displaystyle\leqslant|\alpha|\ \frac{2\epsilon_{0}\sqrt{(M+\epsilon_{0})^{2}+\epsilon}+(M+\epsilon_{0})(\frac{\epsilon_{0}(2M+\epsilon_{0})+\epsilon_{0}(2M+\epsilon_{0})}{\epsilon})}{\epsilon}.$ (103) $$

We can set $\epsilon_{0}$ small enough such that

$$ $\sup\limits_{x\in K}||L_{N}(f(x))-L_{N}(f^{\prime}(x))||\leqslant\sup\limits_{\forall|x-y|<\epsilon_{0}}|L_{N}(x)-L_{N}(y)|<\epsilon^{\prime}.$ $$

∎

###### Theorem D.9 (Universal Approximation Theorem [Cybenko, 1989 ] ) .

For any given continuous function $f:\mathbb{R}^{d}\to\mathbb{R}^{n}$ and an allowable error $\epsilon>0$, there exists a single-hidden-layer neural network $f_{\theta}$ with appropriate parameters $\theta$, such that:

$$ $\sup\limits_{x\in K}||f(x)-f_{\theta}(x)||_{\infty}<\epsilon,$ $$

where $K\subseteq\mathbb{R}^{d}$ is an arbitrary compact set.

###### Proposition D.7 .

###### Proof.

###### Lemma D.8 .

###### Proof of Lemma D.8 .

###### Proof of Lemma D.6 .

###### Proof of Lemma D.4 .

###### Theorem D.9 (Universal Approximation Theorem [Cybenko, 1989 ] ) .

## Appendix E Details of the experiment

### E.1 Dataset

We require reasoning sequence $(x_{i})_{1\leq i\leq 2s}$ of the training set satisfy the following condition.

$$ $\displaystyle x_{2i}-x_{2i-1}\bmod 5\in\{0,1,4\}$ (104) $$

The sequence of the test set satisfy:

$$ $\displaystyle x_{2i}-x_{2i-1}\bmod 5\in\{2,3\}$ (105) $$

The values of each token range from 20 to 100,i.e.,$x_{i}\in[20,100]$.

### E.2 Hyperparameters

In this section, the fixed and tunable hyperparameters employed in the model are outlined.

The fixed hyperparameters are as follows. Transformer architecture uses one attention head per layer. The dataset is partitioned into a training set comprising 90% of the data and a test set comprising the remaining 10%. Training is conducted over 2000 epochs. A weight decay of 0.1 is applied. The dimension of the model $d_{m}$ is set equal to the key dimension $d_{k}$. The feed-forward network dimension $d_{feedforward}$ is set to 1200.

**Table 2:**
| the number of reasoning steps | 3 | 4 | 5 |
| --- | --- | --- | --- |
| the size of datasets | 1200000 | 6000000 | 30000000 |

The following hyperparameters are varied across experiments.
We compare models using both pre-layer normalization and post-layer normalization configurations.
The number of layers, the number of reasoning steps, the model dimension $d_{m}$, the learning rate, the size of datasets (table [2](https://arxiv.org/html/2509.23178v1#A5.T2)) and the batch size are also systematically varied.

### E.3 About the prelayernorm and postlayernorm

We train a transformer which has 3 layers and 21 token length with batch size equal to 1000 and learning rate equal to $5\times 10^{-5}$ to do 3-step reasoning. Initially, the model is configured with post-layer normalization. However, this result in suboptimal performance. There is figure [8](https://arxiv.org/html/2509.23178v1#A5.F8) we train .

Figure: Figure 8: postlayernorm
Refer to caption: post_dm=256_o=3_L=3.png

We therefore employ pre-layer normalization in our architecture. Empirical results indicate that this configuration yields significantly improved performance. The corresponding training curves and outcomes are presented in the figure [9](https://arxiv.org/html/2509.23178v1#A5.F9).

Figure: Figure 9: prelayernorm
Refer to caption: pre_dm=256_o=3_L=3.png

### E.4 Causal intervention experiment

In this section, we investigate whether transformer is capable of genuine reasoning or merely memorizes the answers, under the settings of 4-step and 5-step reasoning. We then describe the experimental methodology employed to obtain the results.

First, a sequence that can be answered correctly will be selected. Subsequently, a specific attention line or residual connection is masked. If transformer produces an incorrect output after the masking of a particular attention line or residual connection, that line will be marked in grey. If the model’s output remains correct, the line will left unchanged. The resulting attention graph retains only those connections that critically influence the outcome. This approach allows for conclusions to be drawn regarding whether the model has learned to perform reasoning.

#### E.4.1 L=3 step-order=4 d m = 1024 d_{m}=1024

Figure: Figure 10: accuracy of 4-step reasoning
Refer to caption: L=3_4-step_reasoning.png

Figure: Figure 11: L=3, 4-step reason
Refer to caption: 4-step_correct.png

Figure [11](https://arxiv.org/html/2509.23178v1#A5.F11) shows that when the input reasoning pairs satisfy some sequence relationship ((79, 52) occurs after both (67, 79) and (52, 24). ), the model produces the correct output, and the information flow aligns with the prescribed reasoning rules.

#### E.4.2 L=3 step-order=5 d m = 1024 d_{m}=1024

Figure: Figure 12: accuracy of 5-step reasoning
Refer to caption: L=3_o=5_dm=1024.png

Figure: Figure 13: L=3, 5-step reasoning
Refer to caption: 5-step_correct.png

As shown in Figure [13](https://arxiv.org/html/2509.23178v1#A5.F13), when transformer produces a correct answer in the 5-step reasoning task, the attention and residual connections do not conform to the expected reasoning patterns. This may suggest that the 3-layer transformer fails to adequately learn genuine 5-step reasoning. Instead, the model might rely on memorization to arrive at the correct response.

### E.5 Guess about d m d_{m}

Based on the aforementioned experiments, it can be observed that training a model capable of parallel reasoning—where the number of reasoning steps exceeds the depth of the transformer (i.e., number of layers minus one)—requires a substantially large model dimension $d_{m}$. It is therefore hypothesized that for string reasoning, wherein the number of reasoning steps equals the depth of the transformer (layers minus one), a significantly smaller $d_{m}$ may suffice.

We train a 4-layer Transformer model to perform 3-step reasoning. In this experiment, the sequence length is set to 21, the batch size is 1000, and the learning rate is $5\times 10^{-5}$. The model is trained for 500 epochs with a hidden dimension of $d_{m}=128$.

Figure: Figure 14: L=4 $d_{m}=128$
Refer to caption: L=3_o=3_dm=128.png

The experimental results indicate that the blue and red strings both rapidly approach 100% success rates. Under the string reasoning condition, a transformer model with 128 hidden dimensions demonstrates the capability to effectively perform 3-step reasoning tasks (figure [14](https://arxiv.org/html/2509.23178v1#A5.F14)). In contrast, under the parallel reasoning condition, an architecturally equivalent model with the same number of hidden dimensions achieves only an 11.9% success rate.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 2
presentation: 2
questions: - Can you add experiments for L=2,4,5 on the same symbolic task, with width sweeps, to show whether the “steps vs. depth” curve is actually exponential in practice?
- Your own results show strong dependence on hidden size. Can you give a dimensionality or capacity argument along the lines of “to realise N parallel reasoning items at layer L, you need at least O(N) (or similar) width”?
soundness: 2
strengths: - The authors provide both a constructive lower bound and a constructive upper bound.
- Appendix D gives an explicit way to choose Q/K/V and use residuals/FFNs so that a single-head, causal Transformer can behave like the rule system.
summary: The paper studies the intrinsic, single-pass reasoning capacity of decoder-only transformers by introducing an idealized information-propagation model that abstracts attention and residual connections into set-based rules over “reasoning pairs.” The core task is symbolic: inputs are made of shuffled pairs (a_i^1, a_i^2) that form a reasoning chain, and the model must recover the target reached after multiple reasoning steps. Within this abstract model, the authors prove that for an L-layer system following their rules, the number of reasoning steps whose information can reach the final position is between a lower bound of 2^{L-1}-1 and an upper bound of \frac{3^{L-1}-1}{2}, i.e. exponential in depth with bases 2 and 3 respectively. These bounds are made concrete by constructing special input permutations that attain the two extremes. They further provide a constructive mapping from the abstract rules to a hand-designed single-head masked transformer that realizes adjacent-position matching and same-token matching with specific Q/K/V choices, arguing this shows the rules are implementable in principle. Experiments on synthetic data with a 3-layer transformer show: (i) near-perfect 3-step reasoning when width is large, (ii) partial success on 4-step when the ordering is favorable, and (iii) clear degradation on 5-step, which the authors present as consistent with their theoretical limit. However, the experiments do not test the theory’s central scaling claim in L, and the symbolic abstraction is stronger than what real, trained models are guaranteed to implement.
weaknesses: - The theorems (Sec. 6) are proven for a set-union model of information, not for the actual vector-space, soft-attention transformer. It does not show that trained transformers implement those rules. The proofs are also dimensionality-agnostic, implicitly assuming each node can store arbitrarily many distinct reasoning items regardless of hidden size. However, the authors’ own experiments (Table 1) show that performance depends strongly on hidden size (larger widths are required for multi-step reasoning) indicating that representational capacity is a limiting factor.
- The empirical results insufficiently probe the core scaling law: the theory predicts reasoning capacity should grow exponentially with depth, yet all reported experiments evaluate only one depth (L=3).
- The assumption that adjacent position matching occurs only in layer 1 and same-token matching only in layers L >= 2 (Rule 2 & 3) is entirely artificial. There is no architectural or theoretical reason for this strict layering of function.

---

confidence: 2
contribution: 4
initial_rating: 8
presentation: 3
questions: How do you expect the theoretical bounds derived under idealized symbolic settings to translate to more realistic scenarios, where the reasoning process involves natural language, semantic ambiguity, and potentially noisy or unstructured inputs?
soundness: 4
strengths: This paper makes a strong contribution by providing a clear and rigorous theoretical understanding of the intrinsic reasoning capacity of Transformer models.

More specifically, it establishes formal upper and lower bounds on the number of reasoning steps a Transformer can perform in a single forward pass, moving beyond purely empirical observations. The information propagation framework is well structured, connecting low-level attention mechanisms to high-level symbolic reasoning, which enhances interpretability. The proof techniques are clean and logically sound, offering precise insights into how reasoning depth scales with model depth. The experimental results closely match the theoretical analysis, validating the tightness of the proposed bounds. Overall, the work addresses a fundamental and timely problem, making it both theoretically significant and practically relevant.
summary: This paper provides a theoretical analysis of the symbolic multi-step reasoning limits of a Transformer in a single forward pass. By modeling information propagation through adjacent position and same-token matching, the authors show that an $L$-layer Transformer can support between $O(2^{L-1})$ and $O(3^{L-1})$ reasoning steps. Experiments on symbolic reasoning tasks confirm these bounds, showing that a 3-layer model succeeds on up to 4-step reasoning but fails beyond that. The work offers a formal and tight characterization of single-pass reasoning capacity, extending beyond prior empirical analyses.
weaknesses: While the paper makes a solid theoretical contribution, it also has some limitations. The analysis is based on highly idealized symbolic reasoning tasks, which may not fully capture the complexity of real-world natural language reasoning scenarios. However, this might be understandable given the difficulty of rigorous theoretical analysis. 

In addition, although the theoretical bounds are tight, the paper offers limited discussion of how these limits might interact with optimization dynamics, initialization, and data distribution, and a deeper treatment of these aspects would make the results more practically relevant.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 3
questions: Do your bounds predict the specific deficits seen in compositional and recursive reasoning in transformers? 

How would the bounds change without the single pass assumption?
soundness: 3
strengths: A clear, formal definition of “reasoning step” tied to concrete token-level propagation primitives (adjacent and same-token matching). Theorems bound capacity as a function of depth.

The bounds are constructive and interpretable.

Empirical checks (3-layer transformer; accuracy vs. hidden size) align with the theoretical picture that wider representations help store intermediate facts but do not break the depth-dependent step limit.
summary: This paper studies the intrinsic single-pass reasoning depth of transformer decoders with L attention layers. Within a symbolic multi-step reasoning setup, the authors formalize “information propagation rules” (adjacent-position matching, same-token matching, residuals) and prove bounds on the maximum number of effective reasoning steps in one forward pass lies between. They give matching constructions showing a binary-tree lower bound and a ternary-tree upper bound, and provide experiments (e.g., a 3-layer model achieving perfect 3-step reasoning with sufficiently large hidden dimension) consistent with the theory.
weaknesses: It’s not yet clear (at least to me) how to map the notion of the reasoning step from the paper to what counts as a step in naturalistic prompting in reasoning experiments with LMs. For instance, Guzmán et al. (NAACL Findings 2024) document persistent failures of the transformer's logical generalization (recursivity and compositionality). Could such phenomena be explained through the main result of the paper?

---

confidence: 4
contribution: 1
initial_rating: 2
presentation: 1
questions: - Does this theory make any predictions about how the number of “reasoning steps” computable by a Transformer scales with the number of heads, in addition to the number of layers?
- How does the proposed model of “information propagation” relate to existing formal models of Transformer computation, such as those in RASP?
- In Rule 2 of the information propagation rules, why is it stipulated that “adjacent position matching” information must flow from odd-position nodes to subsequent even-position nodes? This appears to be an artificial constraint intended to align the model with the pair structure of the “reasoning chains.” How would such a rule correspond to realistic models of position-based attention?

Typos?
- line 200: $a_i^1 \to a_I^2$
- Line 285: $(\mathbf{a} a_m)_{1 \leq m \leq s}$
soundness: 2
strengths: This work tackles an important problem that is of great interest to the machine learning community, namely, characterizing the theoretical capabilities of Transformers to perform "reasoning". A key aspect that is highlighted is the potential to perform parallel computation across all tokens at each layer.
summary: This work studies the question: "how many 'reasoning steps' can an $L$-layer Transformer carry out in a single forward pass?". To answer this question, the paper posits a formulation of "reasoning chains" as sequences of pairs of integers $a_i^1 \to a_i^2$, which can be permuted. It then formalizes an abstract model intended to represent multi-layer Transformers by defining rules of "information propagation", where the information at each token in the transformer is a set $V_i^l$ that expands at each layer (i.e., $V_i^{l+1} = V_{\mathcal{I}}^{l} \cup V_i^{l}$). The question of how many reasoning steps a transformer can carry out is mapped to the question of how big $C_i^l = | V_i^l|$ can be. The main result of the paper is to show that this is between $2^{l-1}$ and $3^{l-1}$.
weaknesses: - The main weakness of this work lies in the modeling of its notions of "reasoning" and "Transformers", which underpins the main theoretical result. The framework is presented in a highly abstract (and arguably unnecessarily so) manner, lacking clear motivation or grounding in real tasks or implementations of Transformers. Formalizing vague concepts like “reasoning” is inherently difficult, but the formulation proposed here is neither clearly useful nor evidently interesting. It is unclear what class of problems this artificial setup captures.
- Moreover, the formulation of Transformer computation is also limited and artificial. On the one hand, it considers only a very limited subset of the types of computations Transformers can do (namely, "same token matching" and "adjacent position matching"). On the other hand, even those limited computations are modeled in an overly simplistic manner, which is disconnected from the parameterization of Transformers and the distributed vector representations at each layer.
- The central result is unsurprising given the artificial nature of the model. In particular, the toy model of Transformer computation crucially does not consider the capacity of finite-precision vector embeddings, which has been shown to be critical in determining the function class of neural networks, including Transformers, in prior work.
- The experimental section is limited and does not substantively test the theoretical results. While the experiments are designed around the paper’s own notion of “reasoning,” they only consider $L=3$ and yet claim empirical support for the theory. To meaningfully support the theoretical result, the authors would need to vary $L$ and demonstrate that the conclusions hold more generally. Since the theory concerns scaling with depth, fixing the depth in experiments fails to test the key claim.
- The Related Work section lacks substantive discussion. It merely lists a large number of papers with minimal analysis. In particular, relevant work on the approximation / representation capacity of Transformers is missing (e.g., Perez et al. 2019; Yun et al. 2020; Wei et al. 2022; Sanford et al. 2023; etc.). 
- Communication and structure are also weak points. The logical flow of the paper is difficult to follow. For instance, Section 3 presents an informal preview of the theoretical result before introducing the necessary definitions of “reasoning” or “information propagation”. The mathematical formalism is often redundant or unnecessarily complicated. For example, Definitions 4.2 and 4.4 are redundant, Definitions 4.6 and 4.8 are redundant, and Definition 4.5 appears unnecessary. Overall, much of the abstraction overcomplicates otherwise simple concepts.