Limit Analysis for Symbolic Multi-step Reasoning Tasks with Information Propagation Rules Based on Transformers
This work addresses the theoretical limits of reasoning in Transformers, which is an incremental contribution to understanding AI model capabilities.
The paper tackles the problem of understanding the intrinsic reasoning mechanism of Transformers by proposing information propagation rules and analyzing the limit of reasoning steps, showing that the limit number of steps is between O(3^{L-1}) and O(2^{L-1}) for a model with L attention layers in a single pass.
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})$ and $O(2^{L-1})$ for a model with $L$ attention layers in a single-pass.