Analyzing the Power of Chain of Thought through Memorization Capabilities

We thank the reviewer for acknowledging our theoretical contribution to the largely overlooked topic of expressive ability of CoT transformer in terms of memorization. We think that we have addressed the concerns raised in the Weakness clearly.

W1. In my understanding, CoT is primarily intended to to improve the capability of LLMs for reasoning tasks whose solving typically involves multiple algorithmic steps. From this perspective, the significance of analyzing CoT's impact on memorization is somewhat unclear.

Answer:

We will explain the why studying Memorization CoT Transformer and, closely related, the relationship with previous Reasoning CoT from 3 aspects.

1, First, it should be noted that previous work on Reasoning CoT Transformer is also based on Memorization/Interpolation, since the accurate results are required for reasoning, so study the memorization/Interpolation is important for reasoning. We give precise description for the memorization ability for a LARGER class of problems than previous work on COT, the difference is: our Memorization CoT-Transformer interpolates data sampled from black-box algorithms (Line 301-302), while previous Reasoning CoT-Transformer can only to interpolate data obtained from KNOWN algorithms such as arithmetic problems. So, we consider a LARGER class of problems, because there is no KNOWN algorithms in most real-world situations like language translation. More precisely, previous CoT methods construct the transformer step by step to interpolate data according to the KNOWN algorithm to generate these data, such as give the results of an arithmetic expression step by step. While CoT memorization can be used to interpolate data obtained by black-box algorithms. The above information was given in Lines 31-36.

2, Whether CoT can enhance the transformer’s ability to solve back-box reasoning problems is apparently an important problem. Our work gives a complete answer to this problem.

3, We give the first result on interpolating infinite reasoning dataset by transformer, as shown in the “Section 5.3 Memorization of infinite language is hard”, while ALL previous work on CoT Reasoning focused on finite datasets as far as we know in.

W2. The paper considers fixed-precision Transformers with flexible width and depth, in contrast to prior works that focus on log-precision, constant-depth Transformers when analyzing CoT’s effect on expressivity. In those earlier studies, constant depth is a critical constraint, where CoT serves to increase the model’s effective depth. While it is reasonable to explore a different setting, additional justification may be necessary to explain its relevance (e.g., better alignment with practical models) and to clarify how the differences in setup affect the interpretation and comparability of results with prior work.

Answer:

We answer this question from 3 aspects:

1. Fixed-precision Transformers are more close to practice, since semi-precision (FP16) is usually use to train models. Our results are more useful, especially when considering very long sectences or infinite dataset. Previous settings such as log-precision will fail in this case.

2. The reasons for using different structures are: Firstly, in the real world, due to the improvement of computing power, the depth of the LLM can be very large, which is more closed with our assumptions. Secondly, different problem is considered. As mentioned in answer to W1, we consider a more general problem than previous CoT works: we consider interpolating data sampled from black-box algorithms and previous work consider interpolating data obtained from KNOWN algorithms and the algorithm is used to construct the transformers. In our case, no algorithm is used for dataset, thus larger depth is needed. If we still consider shallow transformers, it will lead the conclusions that are not in line with reality.

3. The impact of our results on practice. We have studied a wider problem of CoT under a more realistic setting, and thus reached new conclusion: we give necessary and sufficient condition for CoT memorization and tight bound of number parameters of the memorization network. These conditions and bounds can be used to guide practitioners to train real models. For some infinte reasoning problem, we show that CoT is helpless.

We thank the reviewer for acknowledging the study of an interesting problem and give a detailed analysis. We think that we have addressed the concerns raised in the Weakness clearly.

W1. This work studies one particular implementation of CoT Transformer (as defined on L154-158). Is it possible that another implementation of CoT Transformers could potentially lead to different memorization capabilities, especially for different languages?

Answer:

The definition of CoT Transformer (L154-158) is the commonly used one in most papers and practical LLMs, which is also called autoregressive Transformer.

Different types of CoT transformer require different theoretical support, and we believe that there are some other types of CoT transformer that can help improve the memorizaiton and reasoning capabilities of transformers.

To study the memorization capability of other CoT Transformers will be listed as a future work in the paper.

We thank the reviewer for acknowledge that our paper provides theoretical insights into the memorization expressiveness of transformers. The main concerns of the reviewer on our paper is about clarity. After carefully check the questions, we believe that the paper has formally and clearly defined these notions as to be explained below.

Questions: Major Problems: P1. What is the meaning of {K_k} in Theorem 4.1 and κ_j in Theorem 4.4? Is it a one-element set of κ_k or a k-element subset of κ?

Answer: In Th4.1: '$typ (x1)=typ (x2)=\\{\kappa_k\\}$ for some $k \in [T]$' means that typ (x1)=typ (x2) and they all contain only one basic element. Here, {$\kappa_k$} is the set with a single element $\kappa_k$ but not a k-element subset of $\kappa$. Hence, $\kappa_k$ does not specifically refer to a certain basic element, but only refers to the basic element contained in typ (x1) and typ (x2). Please note that we mentioned 'for some $k \in[T]$' in Line 180, according the definition of $\kappa$ and typ(x) in the Line 95-97, the meaning of $\\{\kappa_k\\}$ is clear.

In Th4.4：‘for any j ∈ [T] satisfying $\\{(x,y) \in S :typ(x) = \kappa_j\\}$ ≠ ∅‘ should be ‘for any j ∈ [T] satisfying $\\{(x,y) \in S :typ(x) = \\{\kappa_j\\}\\}$ ≠ ∅‘, we lose a '{}' here, but it does not affect the correct of theorem.

Similarly, $\kappa_j$ is not a specific basic symbol but used to refer to any $j\in[T]$ that satisfies $\\{(x, y) ∈ S: typ (x)=\\{κ_j\\}\\}$ $\ne$∅. $\\{\kappa_j\\}$ is the set with a single element $\kappa_j$ but not a j-element subset of $\kappa$. Please note that we said 'for any j ∈ [T]' in Line 208. According the definition of $\kappa$ and typ(x) in the Line 95-97, the meaning of $\\{\kappa_j\\}$ is clear.

P2. How does a COT transformer memorize LCP^{=1}_{n}? By Theorem 4.1, a non-COT transformer only considers the set of distinct input symbols, not their positions or counts. For inputs x = A and x = A ···A, the COT process should be identical since they share the same typ() at each step, leading to the same output. How does the COT transformer produce different outputs based on input length?

Answer:

1. This result comes from Theorem 4.4 by verifying its hypothesis, as we did in the Proof of Proposition 4.7 in Lines 1057-1060.

2. We explain why a CoT transformer F can produce different results for x1=A and x2=AAAAAA.

First by the definition of CoT transformer(line 154-157), we note that since each step of a CoT can be saw as once calculation process of no-CoT, we can use Prop 4.3 and Theorem 4.1 to each step of CoT.

F(x1) and F(x2) are indeed the same in the first step of the CoT according to Prop 4.3, and let \widehat{F}(x1)=\widehat{F}(X2)=B.

But, in the second step of the CoT, B will be attached to the ends of x1 and x2, which are the new inputs to F, that is, we will compute F(AB) and F(AAAAAAB). Now, |typ(AB)|=|type(AAAAAAB)|=2. Since AB and AAAAAAB contain more than one element in $\kappa$, F can give different results for them according to Theorem 4.1.

The same applies to every subsequent step, so CoT can solve the dataset with typ=1.

P3. Does Theorem 4.1 simply state that a non-COT transformer is a universal approximator for functions dependent only on typ(x), i.e., it can express all functions in UAT(typ(x))?

Answer:

1. Memorization means exactly equal to the value of the function. Then Theorem 4.1 is about exact interpolation of finite data sampled from black-box functions, NOT approximate the functions with a high accuracy. More precisely, Theorem 4.1 gives the necessary and sufficient conditions for using no-CoT transformers to exactly interpolate values of a black-box function on finite elements from $2^\kappa$.
2. So Theorem 4.1 is not about express functions over typ(x), but is about functions over $2^\kappa$. More precisely, about exact interpolation of finite data sampled from black-box functions over $2^\kappa$.

P4. What mechanism allows a COT transformer to leverage input information beyond typ(x)?

Answer: Beyond typ(x), a COT transformer can also use the autoregressive nature of CoT-Transformers to produce intermediate steps, which may result in different results than no CoT case. See our answer to P2.

P5. The notation 2^κ, where κ is a set, is confusing. A more conventional notation would be κ^k, representing a length-k array with elements from κ.

Answer: $2^\kappa$ is clearly defined in Line 96: $2^\kappa$ is use to denote the set of all sequences with elements in kappa. What we want to clarify is that we did not impose any limit on the length of sentences throughout the paper, so we wanted to use a symbol to represent all sentences (regardless of length), which is why we chose an expression that is independent of length.

P6. What is the relationship between embedding dimension d and width W in Section 3?

Answer: In standard Transformers, d and W are the same. In some papers, W is less than d in order to use less parameters. In our paper, we relaxed this restriction so that they can be different. This more general assumption will not affect the rationality of the structure, as we introduced the situation where d and W are different in Line 130.

We appreciate the reviewer's comments. We think that we have addressed the questions and concerns clearly.

W1. Limits analysis to single-token labels, leaving sequence outputs unaddressed.

Answer: You are correct on this which was also mentioned in lines 416-418. However, please note the following aspects: The single-token label case can also include many meaningful tasks, such as language recognition, topic classification and other single-token classification tasks; multiple choice questions such as mathematical multiple-choice questions, disease diagnosis choices, and color or place name recognition; single token code completion, single token mathematical computation, and other single token generation problems. We will add the above content in the revised paper. So, studying single-token memorization also has certain theoretical significance. Considering that our paper already has 41 pages, we list sequence memorization as a future research topic in line 417.

W2. Omits positional encodings and LayerNorm, diverging from real-world Transformers.

Answer: You are correct on this. However, please note the following aspects:

1. The effect of positional encodings on memorization was given. Lines 251-269 prove that “Position embedding is important for no-CoT transformer, but not for CoT-transformer”, which increases our understanding of positional encodings.
2. We include the main construction blocks of the Transformer. We acknowledge that analyzing the whole transformer is more important and difficult. Considering that this is the first paper on fixed precision CoT-Transformer memorization capability, we would like to thank the reviewer for understanding of this simplification.
3. Partial reasons why we do not consider positional encodings were given Remark3.3（Line 117）.

W3. Provides no empirical experiments, so theoretical claims are not validated in practice. and Q1. Could you report empirical results on real LLMs to confirm the theoretical predictions?

Answer:

1. We note that “learning theory” is a topic in the CFP and this paper belongs to this topic.

2. We think our main contribution is theoretical under practical background. We give necessary and sufficient condition for memorization with or no CoT, and tight bound of number parameters of the memorization network; further the more realistic fixed parameter precision model is considered for the first time. These conditions and bounds can be used to guide practitioners to train real models. Even the negative result that “CoT does not help memorization” is useful in practice: when solve problems obviously have no KNOWN algorithms, CoT will have no effect with high probability.

3. Due to time constraints, we cannot report experiment results.

Q2. Section 4 shows CoT and no-CoT memorize disjoint finite-language classes. Can you further characterize which natural NLP tasks map onto each class, or give examples where this distinction has concrete practical consequences?

Answer:

1. Firstly, We must clarify that we never say that CoT and no-CoT memorize disjoint finite-language classes. Proposition 4.7 shows that their scopes do not include each other (Line 232). We further said they are “both strong enough to memorize most languages” (Line 231).
2. Proposition 4.7 gives such examples: (2) of Prop 4.7 gives examples in the scope of Cot-Trans but not in that of no-CoT-Trans; (3) of Prop 4.7 gives examples in the scope of no-Cot-Trans but not in that of CoT-Trans;

Q3. Could you clarify what concrete practical or scientific insights are gained by measuring CoT’s memorization limits, and why those insights cannot be obtained more directly by studying CoT’s reasoning performance instead? Given that Chain-of-Thought is primarily a reasoning aid, not a storage mechanism, the motivation for analysing its memorisation capacity feels under-justified.

Answer: We thank the reviewer for raising this important topic about scientific insights and relation between previous works on reasoning CoT. Answers 1-3 below mainly address the scientific insights. Practical insights are addressed in Answer 4-6 for Q4.

1. First, it should be noted that previous work on Reasoning CoT Transformer is also based on Memorization/Interpolation, since the accurate results are required for reasoning, so study the memorization/Interpolation is important for reasoning. We give precise description for the memorization ability for a LARGER class of problems than previous work on COT, the difference is: our Memorization CoT-Transformer interpolates data sampled from black-box algorithms (Line 301-302), while previous Reasoning CoT-Transformer can only to interpolate data obtained from KNOWN algorithms such as arithmetic problems. So, we consider a LARGER class of problems, because there is no KNOWN algorithms in most real-world situations like language translation. More precisely, previous CoT methods construct the transformer step by step to interpolate data according to the KNOWN algorithm to generate these data, such as give the results of an arithmetic expression step by step. While CoT memorization can be used to interpolate data obtained by black-box algorithms. The above information was given in Lines 31-36.
2. Whether CoT can enhance the transformer’s ability to solve back-box reasoning problems is apparently an important problem. Our work gives a complete answer to this problem.
3. We give the first result on interpolating infinite reasoning dataset by transformer, as shown in the “Section 5.3 Memorization of infinite language is hard”, while ALL previous work on CoT Reasoning focused on finite datasets as far as we know in.

Q4. As in Q3, your study focuses solely on whether finite datasets can be memorized, leaving untouched the core advantages of Chain-of-Thought—namely algorithmic reasoning difficulty and accuracy. Could you justify why these reasoning metrics were excluded and provide evidence (theoretical or empirical) that the reported memorization bounds translate into meaningful gains—or at least no regressions—in actual CoT reasoning performance? Same concerns were raised in Limitions by the reviewer: Since no empirical experiments validate the theoretical results on real LLMs, their practical reliability remains untested. The work considers only whether data can be memorized, ignoring CoT’s core strengths—algorithmic reasoning difficulty and accuracy.

Answer: We continue our answers from Q3.

4. “your study focuses solely on whether finite datasets”.

Actually, our paper seems to be first one on treating infinite dataset by transformer as far as we know. Section 5.3 of our paper “Memorization of infinite language is hard” considers infinite dataset, while ALL previous work on CoT Reasoning focused on finite datasets. See Lines 360-262.

5. “core advantages of CoT: algorithmic reasoning difficulty and accuracy”.

First, accuracy seems not a problem, because both our work and previous work which based on Memorization/Interpolation are accurately solved the problem. See Line 175-177 for definition. Our results are more useful in the sense, we consider fixed-precision parameters for the first time (Line 43-44). For algorithmic reasoning difficulty, our CoT Memorization measures the capability of CoT-Transformer to solve any language problem, while previous CoT applies to reasoning problems which are solved by KNOWN algorithms, as we know that there is no KNOWN algorithm “in most real-world situations like language processing”. For more, please refer to answer 1 for Q3.

6. “translate into meaningful gains” and practical implications.

We give necessary and sufficient condition for memorization with or no CoT, and tight bound of number parameters of the memorization network; further the fixed parameter precision model is considered for the first time. These conditions and bounds can be used to guide practitioners to train real models. Even the negative result that “CoT does not help memorization” is useful in practice: when solve problems obviously have no KNOWN algorithms, CoT will have no effect with high probability.