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
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 2L−1−1 and 23L−1−1 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.
Figure 2: Three steps reasoning task. One step reasoning leads to 2 , two steps reasoning leads to 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:
Figure 7: Training curves of the 3-layer Transformer on 3-step reasoning under different hidden dimensions.
dm
64
128
256
512
1024
Test accuracy (%)
9.6
11.9
72.2
99.6
99.6
Appendix
Table 2: Relationship between dm 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:
Figure 11: L=4 dm=128
Figure 12: Reasoning task represents by (xi) in example F.3 .
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.
Jiashu He, Jinxuan Fan, Xiao Xiao +2
University of Pennsylvania · University of Texas at Austin · Yale University
Complex problems, whether in math, logic, or planning, are solved by humans through a sequence of steps where the result of one step informs the next. In this work, we adopt the perspective that the reasoning power of Transformers is fundamentally limited by a fixed maximum number of steps along any latent path of computation. To address this, we introduce Turbo Connection (TurboConn), a novel architecture that overcomes the fixed-depth constraint by routing multiple residual connections from the higher-layer hidden states of each token t to the lower layers of token t+1. Fine-tuning pre-trained LLMs with our method not only yields accuracy gains of 0.9% to over 10% on benchmarks like GSM8K, Parity, and multi-step arithmetic, but also demonstrates that the density of these backward connections is critical; our dense interaction significantly outperforms "sparse" alternatives that only pass a single hidden state or vector. Notably, TurboConn can be integrated into pre-trained LLMs to overcome task-specific plateaus: while a fine-tuned Qwen-3-1.7B achieves only 53.78% on Parity, adding our architectural modification enables the model to reach 100% accuracy, all without the necessity to retrain the full model from scratch or sophisticated curriculum learning. Our results provide strong empirical evidence that the depth of the computational path is a key factor in reasoning ability, also offering a new mechanism to enhance LLMs without significantly affecting generation latency.
We investigate whether transformers use their depth adaptively across tasks of increasing difficulty. Using a controlled multi-hop relational reasoning task based on family stories, where difficulty is determined by the number of relationship hops that must be composed, we monitor (i) how predictions evolve across layers via early readouts (the logit lens) and (ii) how task-relevant information is integrated across tokens via causal patching. For pretrained models, we find some limited evidence for adaptive depth use: some larger models need fewer layers to arrive at plausible answers for easier tasks, and models generally use more layers to integrate information across tokens as chain length increases. For models finetuned on the task, we find clearer and more consistent evidence of adaptive depth use, with the effect being stronger for less constrained finetuning regimes that do not preserve general language modeling abilities.