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

Tian Qin; Yuhan Chen; Zhiwei Wang; Zhi-Qin John Xu

cs.AISep 27, 2025

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

Authors: Tian Qin, Yuhan Chen, Zhiwei Wang, Zhi-Qin John Xu

Organizations: School of Mathematical Sciences, Shanghai Jiao Tong University · School of Mathematics and Statistics, Wuhan University · Institute of Natural Sciences, MOE-LSC, Shanghai Jiao Tong University

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 $2^{L-1}-1$ and $\frac{3^{L-1}-1}{2}$ for a model with $L$ attention layers in a single-pass. In addition, we find that, for problems with a fixed number of reasoning steps, Transformers exhibit a preference for generating sequences that satisfy certain ordering relations. Ultimately, we construct a Transformer and prove that the limiting reasoning depth is achievable.

Figures & tables

Figure 1: Illustration of linear reasoning and parallel reasoning.

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

Panel of Figure 3 — Figure 3: Relationship between reasoning chain and reasoning sequence.

Figure 4: A two-step reasoning example.

Figure 5: Test accuracy of sentences with different sequence relationships

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Lower bound example

the number of reasoning steps	3	4	5
the size of datasets	1200000	6000000	30000000

Appendix

Table 1:

Panel of Figure 7 — Figure 7: Training curves of the 3-layer Transformer on 3-step reasoning under different hidden dimensions.

$d_{m}$	64	128	256	512	1024
Test accuracy (%)	9.6	11.9	72.2	99.6	99.6

Appendix

Table 2: Relationship between

d_{m}

and test accuracy

Figure 8: Training curves of the 3-layer Transformer on 4-step reasoning

Figure 9: Test accuracy of sentences with different sequence relationships

Figure 10: (a) Attention propagation under the valid ordering predicted by our theory. When (67, 74) appears after both (74, 42) and (59, 67), the model is able to consolidate information and the critical attention route follows exactly the theoretically derived path.(b) Attention breakdown under an invalid ordering. If the relative order of the three arrays is altered such that (67, 74) is no longer placed after the other two, the model fails to aggregate sufficient information, resulting in fragmented and chaotic attention patterns

the number of reasoning steps	1	2
test accuracy(%)	100	8.4

Appendix

Table 3:

Panel of Figure 12 — Figure 12: Reasoning task represents by $(x_{i})$ in example F.3 .

Transformer

Transformers are neural architectures that use attention to model relationships among sequence elements in language, vision, and scientific data.

See all 558 papers

Ceiling of a Task: When Can a Transformer Succeed Without Its Chain of Thought?
Sep 27, 2026Jiashu He, Jinxuan Fan, Xiao Xiao +2LLM Reasoning
University of Pennsylvania · University of Texas at Austin · Yale University
Turbo Connection: Reasoning as Information Flow from Higher to Lower Layers
Feb 20, 2026Mohan Tang, Sidi LuTransformer Large Reasoning Models
UCLA.
Do Transformers Use their Depth Adaptively? Evidence from a Relational Reasoning Task
Apr 14, 2026Alicia Curth, Rachel Lawrence, Sushrut Karmalkar +1Adaptive Computation Transformer Interpretability
Microsoft Research Cambridge

Sep 27, 2026J/K move · Enter open · S save

Ceiling of a Task: When Can a Transformer Succeed Without Its Chain of Thought?

Jiashu He, Jinxuan Fan, Xiao Xiao, Radu Marculescu+1

University of Pennsylvania · University of Texas at Austin · Yale University

LLM Reasoning

Open paper AskPDF arXiv

Reasoning models generate long chains of thought before they answer, yet it is debated whether the content of these chains does real computational work or is largely decorative. We study this question by viewing a transformer as a shallow circuit. One forward pass through a fixed number of layers has constant depth, so any procedure that runs the model a constant number of times is a shallow circuit. We call the best accuracy that a shallow circuit can reach on a task the ceiling of the task, and a task is serial if its ceiling lies below one. We prove three results on serial tasks that hold for every transformer, no matter how it was trained. Necessity: replacing the chain by anything that does not depend on its content, such as filler tokens or a restatement of the question, drives the accuracy down to the ceiling, and on a maximally serial task down to chance. Depth: no shallow computation can write the chain of a model whose accuracy exceeds the ceiling, not even approximately. Locality: the answer is one shallow pass away from the finished chain, so all of the serial reasoning happens in the chain. On word problems of finite groups, whose ceilings are known, small transformers trained from scratch, with or without reinforcement learning, attain the predicted numbers: chain-trained models solve every input length and fall to chance when the chain is erased, chainless models collapse to the ceiling as the input length grows, and open-weight reasoning models given the same problem in words return to the baseline without their chain. On MATH-500 and AIME, erasing the chain costs open reasoning models 0.52 to 0.82 accuracy, a sentence shuffle is harmless, and a token shuffle is as harmful as erasing; the same holds for checkpoints trained by GRPO with a correct or a random reward. The ceiling of a task therefore answers when a transformer can succeed without its chain of thought.

Abstract

Transformer

Explore similar work

Ceiling of a Task: When Can a Transformer Succeed Without Its Chain of Thought?

Turbo Connection: Reasoning as Information Flow from Higher to Lower Layers

Do Transformers Use their Depth Adaptively? Evidence from a Relational Reasoning Task