Analyzing the Power of Chain of Thought through Memorization Capabilities

It has been shown that the chain of thought (CoT) can enhance the power of large language models (LLMs) to solve certain mathematical reasoning problems. However, the capacity of CoT is still not fully explored. As an important instance, the following basic question has not yet been answered: Does CoT expand the capability of transformers across all reasoning tasks? We demonstrate that reasoning with transformers is essentially a memorization problem for reasoning datasets. Thus, examining the power of CoT across all reasoning tasks amounts to analyzing the memorization capabilities of CoT transformers. In this paper, we provide a complete description of the memorization capabilities of fixed-precision transformers, with or without CoT, and give a negative answer to the aforementioned question. Precisely, we first provide necessary and sufficient conditions for fixed-precision transformers with and without CoT to memorize a finite reasoning dataset and show that these two conditions do not imply each other. Then, we provide lower and upper bounds for the number of parameters needed for transformers, with or without CoT, to memorize a finite reasoning dataset with N elements, which are Θ(N ) in all cases. This implies that there exist reasoning tasks for which CoT does not enhance the reasoning power of transformers, leading to a negative answer to the aforementioned question. Finally, we present the first results on memorizing infinite reasoning datasets by CoT transformers and demonstrate that some simple infinite datasets cannot be memorized by transformers, with or without CoT.