Analyzing the Power of Chain of Thought through Memorization Capabilities
Authors: Lijia Yu
Xiao-Shan Gao
Lijun Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Theory
Chain of Thought
Transformer
Memorization
Primary area: theory
TL;DR: Use the memorization theorem to analyze the power of chain of thought.

Abstract: It has been shown that the chain of thought (CoT) can enhance the power of LLMs to simulate a Turing machine or an algorithm, and in particular its mathematical reasoning ability. The memorization capability of LLMs is an important aspect of their expressive ability, which offers valuable insight into designing models with enhanced generalization potential. Currently, the optimal memorization capacities of transformers have been established for both the general dataset and the dataset that satisfies a specific separability condition. However, the question of whether the CoT can improve the memorization capability of LLMs remains unexamined. To fill this gap, we establish the memorization capability for fixed-precision autoregressive transformers with or without CoT. Precisely, we first give the necessary and sufficient conditions for transformers to memorize a finite language and then provide the upper and lower bounds for the number of parameters of the memorization transformers. Our result indicates that the classes of languages that can be memorized by transformers with or without CoT do not contain each other, and the same number of parameters is needed for transformers with or without CoT to memorize, implying that CoT does not enhance a transformer’s memorization power significantly. We further show that CoT can not help transformers to memory certain infinite languages.

Analyzing the Power of Chain of Thought through Memorization Capabilities
Lijia Yu', Xiao-Shan Gao Lijun Zhang!.3,
Institute of Al for Industries, Chinese Academy of Sciences
SKLMS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences
Universitty of Chinese Academy of Sciences Key Laboratory of System Software of Chinese Academy of Sciences
Abstract
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. How- ever, the capacity of CoTT is still not fully explored. As an important instance, the following basic question has not yet been answered: Does CoT expand the capabil- ity of transformers across all reasoning tasks? We demonstrate that reasoning with transformers is essentially memorization problem for reasoning datasets. Thus, examining the power of CoT across all reasoning tasks amounts analyzing the memorization capabilities of CoT transformers. In this paper, we provide a com- plete description of the memorization capabilities of fixed- seed-precision transformers, with or without CoT, and give negative answer to the aforementioned question. Precisely, we first provide necessary and sufficient conditions for ixed-precision transformers with and without CoT to memorize 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 without CoT, to memorize a finite reasoning dataset with 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 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.
1 Introduction
Transformer-basee LLMS 33 are most powerful models in natural language processing, and autoregressive transformer-based models 27 4 28
42 are the predominantly used forms, which can solve a huge number of tasks by turning them into a sequence generation problem.
It has been shown that CoT 36 allows LLMs to generate a step-by-step "thinking" process, thus improving the mathematical reasoning power of LLMs. Theoretical studies reached the same conclusion. Log-precision transformers without CoT can only solve problem class TC [22). but log-precision transformers with CoT can solve any P problem [2I] Transformers with CoT can solve arithmetic problems and dynamic programming problems that cannot be solved by transformers without CoT [8]. It was further shown that CoT also enhances the reasoning power of constant precision transformers [1
These findings clearly illustrate the advantages of CoT in boosting the capability of transformers simulate certain algorithms by constructing transformers step by step according to the algorithm.
"Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

However, the capability of CoT is still not fully explored. First, many problems may not have an explicit algorithm, such as the decision of whether an algebraic differential equation has a rational solution 37. Even if algorithms exist, they may be too complicated for constructing simulating transformer, such as symbolic integration ( For these types of problems, the earlier method of incrementally building transformers following the algorithm appears to be ineffective. Whether CoT enhances the capability of transformers to solve such problems is not known. Second, experimental studies indicate that CoT has limited scalability, even worse performance compared to direct prompting in planning problems [il and pattern-based in-context learning problems 43 So raise the following natural and basic question:
Question 1. Does CoT expand the capabilities of transformers across all reasoning tasks?
Since mathematical reasoning demands exact results, a key observation of this paper is that reasoning
with L.LMs is essentially memorization problem. Following previous work, formulate reasoning
R(x)) For a sample set S = {(T, y) over given imput domain D, the memorization problem asks whether there exists transformer F such that y = F(x) for every (I, y) E S. In the previous work on LLMs reasoning, memorizing reasoning datasets permits the use of information from the algorithm R. For example, the arithmetic problems considered in [8] can be viewed as the memorization of the reasoning dataset
task as a function or an algorithm:
((x))xx of R
2p...
As capacity measure of neural networks, memorization has been widely studied [10 9 23 41 32) Recently, optimal memorization capacities of transformers have been established for both the general dataset [9]] and the dataset that satisfies a separability condition [12. . However, in these works, the autoregressive transformers that can generate intermediate steps or CoT were not considered. Furthermore, the precision of their model parameters depends on the input and/or model parameters, and the more realistic case of fixed-precision parameters was not considered.
In light of the above observations on the interplay between reasoning and memorization, alongside the limitations of existing research on memorization, we can rephrase Question I as follows:
Question 2. Does CoT expand the memorization capability of transformers for all reasoning datasets?
In this paper, we give complete description of the memorization capabilities of fixed-precision transformers with or without CoT for general datasets and give a negative answer to Questions 1 and 2. Our main conclusions and contributions are as follows:
Necessary and sufficient conditions for fixed -red-iprcision transformers with and without CoT to memorize a finite reasoning dataset are given. It is shown that these two conditions do not imply each other. We further show that by using position embedding (adding more basic symbols), transformers without CoT (with CoT) can memorize all finite datasets.
2. Lower and upper bounds for the number of parameters needed for fixed-precision transform- ers with or without CoT to memorize a finite reasoning dataset S are given. For a dataset S with N elements, all these bounds are ((N), when omitting some smaller quantities. This implies that both CoT transformer and no-CoT transformer need exactly (NN) parameters to memorize certain reasoning datasets.
As consequence of the above results, know that although CoT can enhance performance on some tasks, there exist reasoning tasks for which CoT does not enhance the reasoning power of transformers, leading to negative answer to Questions and 2.
3. We give the first results on memorizing infinite datasets by CoT-transformers. We show that both transformers with without CoT cannot memorize some simple infinite datasets and arithmetic tasks in Zp cannot be memorized by any CoT-transformer with positive confidence (refer to Proposition 5.7 for precise meaning).
In conclusion, our results provide not only new theoretical insights into the capabilities of CoT but also practical guidance. The tight bound for the number of parameters of memorization transformers and the effects of the position encoding and more symbols (Section (.33 may serve as useful guidance for practitioners. Even the negative results, such as "CoT does not help general memorization" are useful in practice: when solving difficult problems or problems with no explicit algorithms, CoT probably has no effect, which is aligned with the experimental results in [3 43)
2

---

2
However, some works Related work
Memorization. As a capacity measure of neural networks, memorization has been widely studied. It was shown that feedforward neural networks (FNNs) with O(N) parameters and various activation functions can memorize any dataset with N elements [TO
29
9 23 41). and O(N) parameters are
also necessary for memorization (3]. A neural network with ((N2/5) parameters can memorize [25] Furthermore, O(vN) parameters are enough for memorization [32]. Since the VC dimension of FNNs with N parameters and ReLU activation function is at most ((N)) M. the result of (32) is optimal. Robust memorization networks were constructed in [I3 39I. which require essentially more parameters than memorization. Sample complexities for memorization FNNs were established [40] and it was shown that memorization FNNs are not generalizable for certain data distributions [15] 40]. It has been shown that memorization enhance the generalization ability of large models by memorizing diversified features of the data 40
dataset satisfying certain separation conditions
For memorization of the general dataset using transformers, O(N) parameters are also sufficient and optimal [19 20 III. OVVN) parameters are also optimal for memorization with transformers for datasets satisfying certain separation conditions [12 [3).
Our results are new in that autoregressive transformers are used and the parameters have fixed precision. For instance, in order to achieve O(VN) parameters 12 it inevitably leads to an unbounded parameter precision.
Reasoning with COT. CoT is a key method to enhance the reasoning capabilities of LLMs [36]. Recent studies have explored various aspects of CoT, including its theoretical foundation and practical applications. For the theoretical foundation, transformers were shown to be Turing complete when infinite precision parameters are allowed [26). The log-precision transformer without CoT can only solve problems within the complexity class TC (22). With CoT, the log-precision transformers can solve any P problem 21] CoT also enhances the reasoning power of constant precision transformers [66 77. The mutual expression relationship between Turing machines and LLMs was further studied in [24 3. CoT has proven to be highly effective in solving traditional mathematical problems such as arithmetic and dynamic programming [8]. For practical applications, a series of works have further improved the inference accuracy of transformers using CoTs [4
showed that CoT also has certain limitations 35 38
It is important note that these theoretical findings, such 8 21), neither conflict with nor imply our results. They showed that CoT can enhance the ability of transformers to solve polynomial-tine problems, by simulating a known algorithm. We show that there exist reasoning problems for which CoT does not increase the power of transformers, by establishing memorization capabilities.
Prerequisite
In this paper, we ((4) to mean value not greater than cAA for some constant and O mean that small quantities, such as logarithms, are omitted. We use 2(4) to mean a value not less than cA for some constant c, and Q2 or to mean that small quantities are omitted.
Data. Let r = (TTTT be set of basic symbols or tokens. We call the sequence (ry ) length-k sentence and use I't to denote the set of all sentences with positive lengths. For sentence x, let len(x:) be its length and typ(#) C I' be the set all the distinct symbols in z. Moreover, let no be the stop symbol that does not appear in the sentence or label, which is only used to stop the transformer. In this paper, we consider the following kind of data.
Definition 3.1. A subset = {x1, yi) HEA r x I is called a language based on symbols r, W: # yj implies 24 Jij-
Here is language used throughout the paper.
Example 3.2. Let Arith, be the arithmetic Zp., where p is a given prime number. We have = (7x ( where T =p- + 7, and 7 = i for [p]. 7p+1 to 7p47 are =, +, x, / (,), respectively. (z, y) is in Arith, if and only if x is arithmetic expression in E, and y is the result
3

---

of r. Further, let grith.. = ((,,) y) E A len(x) I n be the set of arithmetic expressions with length not greater than n. Clearly, Arith, an infinite set and p a finite set. Remark 3.3. In Sections Hand [ only finite languages are considered, which can clearly be described by a Turing machine. The infinite languages considered in Section a also computable by Turing machine. Thus, all languages considered in this paper can be computed by a Turing machine and, therefore, are reasoning datasets.
Remark 3.4. As a first step our study, only single-token labels are considered in this paper. Note that the majority of theoretical work on transformer reasoning has focused on the setting with a single- token label [26] g 22 21. Also note that even the single-token label case includes many meaningful tasks, such as language recognition and other single-token classification tasks, mathematical multiple- choice questions and other multiple-choice questions, single-token mathematical computation and other single-token generation problems.
Autoregressive Transformer. An autoregressive transformer F has three parts:
Part One: Embedding. The transformer first embeds each basic symbol %/2 into a vector v; E Rd where U, serves as an adjustable parameter in the transformer based on different tasks, and is called the embedding dimension. Then the input sentence x (hk, ) E I+ is embedded into matrix with r-rows and d-columns. See appendix for details. We will use x and its matrix representation interchangeably whenever this does not lead to confusion.
Remark 3.5. We do not use position encoding in the embedding layer in most of our results. See Appendix A for details on the embedding layer.
Part Two: Hidden layer. Firstly, we define the feedforward layer and the attention layer. For an input x E Baxd the feedforward layer with width W is FNN(x)) Relu(xFF @ b) E2, where E1 RdxW b R RIxW Eg R wxxd are the parameters, and æE @ means adding the vector b to each row of EE For an input x E R=*d the attention-layer with width W and head H is ATT(=)= = Σ Sottma((rQ.K.))
+ M) ))V, where Q, E RdxW K, E RWxd V, E Rddd are the parameters. M E (-oc, 0} is a causal mask defined as M. = -oo if and only if > i. M ensure that the i-th row only attend to the j-th row where autoregressive generation.
which is commonly used in
Let the transformer have D hidden layers or have depth D, ( be the output of the i-th layer, and (0) x E R the input. Then the i-th hidden layer of the transformer is
(1) (1- W + ((-)(= + (x
+ ATT, (x i,,,), D
where ATT, and FNN; are the i-th feedforward and attention layers defined above, and W; E Rdxd is a residual matrix. It is easy to see that (+)) E Rnnd for all i. W and L are called the width and depth of the transformer, respectively.
Remark 3.6. The residual matrix W; cannot improve the power of the transformer, which allows the transformer to use fewer parameters to express the target. Details can be found in Appendix A.2
Part three: Output layer. The output layer performs a linear transformation for the last row of the last hidden layer, that is, F(x) =oo(()) W. + bo II+(1++)) where =fon(a) is the last row of x (D))
W. E Rdx()+1), and h, E RIx(++1).
Let j = arg max (F(x)): Then, the output of F(r), which is written as F(z), is 7 when j < T; and the output of F(z) is To when j = T + 1.
Transformers with or without COT. For any sentence x, its label can be predicted using a transformer F by employing two methods:
1. No CoT Transformer. Just like FNN, use y = F(x) as the prediction label of x. For conve- we refer to this type of transformers as no- Con-srroffommrrs
2. CoT Transformer. The result is obtained as follows: Let cot = ()
(1) Let s be the concatenation of x and cot, and let = ==(x');
(2) If y * Yoo insert y the last element of cot, and return to (1):

---

(3) y Yo, let the last element of cot be the prediction label of z and be denoted as Feor (x) which said be obtained with CoT-transformers.
Remark 3.7. For the CoT-transformer, we require that the transformer terminates in finite number of steps, and at termination, CoT is not empty.
Here is an illustrative example. If we input 3 + (2 12-1] 1) x 5 into a -rr-noo-rrnn,,rrmrrr it directly 1) into CoT-transformer, by step, such as = 3 + x 5 = 3 + = 87yo. where "Yo is the stop symbol.
gives the answer If we input 3 +
can obtain the answer step
Definition 3.8. Let W.D.H D.H (WW.D. with width W. depth D, head H, and parameter precision q.
H,ott) the hypothesis space of no-CoT (CoT) transformers
Parameter precision and the number of parameters. The transformer is said to have precision q E 24 if every parameter of the transformer is a q-digit decimal real number whose absolute value is not more than 10". A transformer FF in H W.D.H (HW W.D.H.col and based on the basic symbol set contains para(W W, D, H, OldT + DH(Wd + dR)) parameters.
4 Memorization expressive ability of transformers
In this section, we give necessary and sufficient conditions for CoT- and memorize finite language and give upper bounds for the number of parameters of the memorization transformer. We further compare the expressive powers of CoT- and no-Coo--ransformeers. Proofs are given in the Appendix.
to
4.1 Memorization using no-Coo-trrassormer
A no- Coa-transformer (CoT-transformer) FF is said to be memorization of a language S if F(x) (For (x) 3) for any (z, S. We have the following general memorization theorem for no-CoT-transformers.
Theorem 4.1. Let S be a finite language of basic symbols r (x) N = (S], L (a (Ien())), (len)))) and E Z4. Then S can be memorized by a no- -o-Coo--ransformer if and only if (21, M1), (I2, 122 E and typ(s1) = typ(x2) = {"n for some E [T] imply y1 = y/-
Furthermore, if above condition is satisfied, then there exists a no-CoT memorization transformer F for S in H9 O(T),O(NLI) (NL(NTT)4)))o and can be computed in polynomial time about N,T, L.g. This gives an upper bound para(F) O In (N for the number of parameters needed to memorize S.
Theorem 4.1 gives necessary and sufficient condition for a language be memorized by no- CoT-transformer and the required transformer size. It is clear that most commonly used languages satisfy the condition in Theorem 4.1 For example, the language Arith, satisfies this condition and thus can be memorized by Cor-CoT-transformmer This theorem indicates that even without CoT and position embedding. transformers have the power to memorize most languages, the sentence lengths are uniform in the language, then the condition in Theorem 4.1 is inherently met. Thus, we obtain:
Corollary 4.2. If a finite language S satisfies len(z) = foror all (x,v) E S, then there exists no- noT memorization transformer F for S in H OO (1
The following result gives the reason behind the condition in Theorem 4.1
Proposition 4.3. Given æ1, 22 E I+ such that typ(æ1) = typ(z2) {rk) for certain k E [T]. follows that F(xz) = F(xz)) for any no- no-CoT Sa--CoT-traasnn CoT-transformer F.
4.2 Memorization using CoT-transformer
In this section, the memorization capacity of CoT-tranfformers will be discussed. We first introduce several notations. For a sentence let æ be the i-th symbol of x and Zjn] be the sentence composed of the first symbols of v. For example, if (M1,22 72: 73). then xx[2] 7/2 and x12) = (71, 72). For any language S and (z, y) e S, we define set Sp 1 as follows: E S2 if and only if
5

---

(1) [(nn(()) = 2 and 2 Ien 2)] =
(2) (tp())en(())+)) > and
(3) for any (21, y1) E 5, if len(x1) len(z) and [[on(=1)) 21, then y1
Furthermore, let S {z(len(x) 1]:2 2 S.}. We have the following result.
Theorem 4.4. Let S be finite language of symbols. N = [S], I. = max (ax (len(z)) and Et. Then S can be memorized by CoT transformer if and only if (2): [Sa] > for any (z, y) E S and (2): ((xaa)eSttv(a)==()))
+ 0 for any j E [T] satisfying {(x,)) y) E ::typ(())
(n))) + V.
Furthermore, if the above condition is satisfied, then there exists a Col memorization transformer F which can be computed in polynomial time about N, L. This gives upper bound para(F) = O In (NLT) /4l) for the number of parameters needed to memorize S.
for S in H HO(T), (N tn²
Theorem 4.4 gives necessary and sufficient condition for a language be memorized by a CoT transformer and estimates the required transformer size. But the necessary and sufficient condition in Theorem 4.4 not intuitive, and we give several easy-to-check sufficient conditions below.
Proposition 4.5. Let S be a finite language of symbol I. Then each of the following conditions sufficient for S to be memorized by a CoI-transformer.
1. The set of the last elements of all sentences in S is a proper subset of r, that is, {x [[le(())] (z, v) E S} I.
2. All sentences in S have the same length, that is, len(x) for all (x, y) S.
By Proposition 4.5 most commonly used languages representing algorithms satisfy this condition. For example, by Condition of Proposition 4.5 the language Arith,, defined in Example 3.2 satisfies this condition because the four arithmetic operators 't', '-,, "x', 1 cannot be the last symbol of arithmetic expression.
4.3 CoT and no- CoT-rrassformers:: comparison and more results
This section will address the distinctions between the two types of transformers. In particular, will show that their memorization powers are different.
The memorization powers for no-CoT-trannformer and CoT-transformer are different. From Theorems 4. and 4.4 the conditions for languages that can be memorized by no-CoT or CoT- transformers are rather stringent. While the memorization powers of CoT- and -r-Coo--rrassormmess are both strong enough to memorize most languages, the languages that can be memorized by CoT- and no-CoT-transformers are different, as shown by Proposition 4.7 We first define language.
{T>)T we define the language of length calculation problem LCP: (x, 3) LCP if and only if a is sentence and the label of x is y = M(()), where (xx) = len (x) mod T and mod is defined as (i + kT) mod = i for 0 < < T and k E Z In addition, let LCP, {xx y) E LCP: læn I n), LCP=1 {(x,)) LCP,, [typ(x) 1}. and LCP>1 ((x, v) E LCP,, |(yp(x)) 1}.
Example 4.6. For any basic symbol set
This is simple language that counts the length of sentences. We have the following result.
Proposition 4.7. For any symbol set I such that [T] 2 2 and n 2 2, and precision E Z4, we have LC), cannot be memorized by any no-CoT CoT-transformer.
(2) LCP=1 can be memorized by a CoT-transformer, but cannot be memorized by any no-CoT- transformer.
(3) LCP>1 can be memorized by a no-CooT-transformmr, but cannot be memorized by any CoT- transformer.
From Proposition 4.7 CoT- and no- Cor-trrsfforrmsrss can solve different parts of T.C. ... which
confirms their different expressive abilities and demonstrates that using CoT can change the range

---

of languages that transformers can memorize, but it is not strictly superior to those without CoT. But transformers with CoT or without CoT cannot memorize LCP,.. n. In fact, it is hard for transformers to memorize LCP n. From Corollaries 4.9 and 4.12 given below, (CoT) no-CoT- transformers can memorize I,PP, n by (adding new symbols) using position embedding.
Position embedding is important for mo-Coo--rranffrrmer, but not for Cos-transformer. Theo- rem [.1 shows that no-CoT-transee -ronssaasformrrs without position embedding memorize almost every language but cannot memorize certain special languages. This limitation arises because the no- T- transformer cannot completely leverage the length information, which leads to Proposition 4.3) If position encoding is added, then there will be no such limitation, as shown below.
Proposition 4.8. Let S be a finite language with N elements and T basic symbols, (ee))s)) and E E_. Then S can be memorized by a ro-Coo-transformer F in H "Frr--MNChhOOOWETTTTTNNNW
which uses position encoding for the first L positions.
As consequence, we have
Corollary 4.9. For any given q Z.., every finite language can be memorized by a no-CoT- transformer with precision and position encoding.
On the other hand, position encoding is not as useful for CoT-transformers, as shown below.
Proposition 4.10. Let S be a finte language and [ty((z) > for any (z, y) E S. S cannot be memorized by CoI-transformerr then it also cannot be memorized by a CoT-transfrrmer with position encoding.
Position embedding can help memorize sentences satisfying [typ(z) = which is weakness for the No-CoT-transformee But based on the conditions in Theorem 4.4 and Proposition 4.5) the CoT-transformer capable of managing these types of sentences in the majority of cases; thus, position embedding holds limited significance for CoT-transformers.
Remark 4.11. In most results in this paper, we do use position encoding. Results just proved show that position encoding is important for transformers without CoT,, but has no effect for transformers with CoT, which increases our understanding of positional encoding. See Appendix A for more details.
More basic symbols important for CoT-transformer, but not for co-Coo-transtormer. By condition I of Proposition 4.5 adding few new symbols to enables CoT-transformers to memorize all finite languages, as illustrated below.
Corollary 4.12. A finite language S can be memorized by a CoT-transformer if ((a=)ssttp(() is proper subset T.
Corollary 4.12 is not applicable to con-Coo-rransffrmmeess highlighting the benefit of CoT's ability to
exploit the basic symbols entirely. We will give additional clarification this phenomenon. Let S be a language based on r [ and lyp(x) C (w)N for any (x, v) E S. Then when we +M+N
uscless; but when classify S by a CoT-transformer, {nx M N- are useful because they can appear in the COT. For example, in mathematical proofs. logical symbols like ".." "." " commonly used in the problem description. So, if we do not use CoTs, such logical symbols are useless for generating proofss; but if use the CoTs, these symbols are useful in generating the proofs, so adding more symbols to the basic symbols can better help the transformer generate a CoT.
classify S by o--CoT-tranformmet the symbols {m) (
often used in the proof, but not
5 Necessary conditions for memorization with transformers
In this section, we give some necessary conditions for memorization with CoT- and no-CoT- transformers, and show that, from the perspective of necessary conditions, CoT may not provide particularly significant assistance in some situations.

---

5.1 ((N) parameters are necessary and sufficient for memorization
In Section we show that O(N) parameters are sufficient for both no-CoT-transformer and CoT- transformer to memorize any language with N elements. In this section, we will show that O(N) parameters are also necessary for both kinds of transformers to memorize some languages.
Theorem 5.1. For any N, 2 3 and basic symbols {-)]= there exists finite language S that satisfies the condition in Theorem 4.1 (Theorem 4.4) and max len(x) S (In(NN), such that for any given W, D, H, if para(W, D, H) < 0 2 I),, then cannot memorized by any transformer F W.D.H (F E H.D.H.
This theorem establishes a lower bound for the number parameters of a transformer to memorize finite languages, even T, L < N, (INN) parameters are required for some languages, and the lower bounds for two kinds of transformers are essentially the same, which implies CoT cannot effectively reduce the number of parameters required for memorization for some languages.
Remark 5.2. From Theorems 4.1 and 5.1 we see that there exists a gap between the lower bound and the upper bound for the number of parameters for memorization transformers. But when q, I' are constants and >> L, as shown in the Theorems [.1] we can only consider N as in most existing works. Then (2NN) parameters are necessary and sufficient for both CoT- and no-CoT- transformers to memorize a language of size N, giving the optimal memorization capacity for both CoT- and Cor--rrassformrrrs Note that most cases, we have N > L. and in the actual situation, q and T are al always constants, so the above discussion is meaningful.
5.2 The length of sentences affects memorization
In this section, will show how the length of sentences affects memorization. Firstly, in Theorems 4.1 andddd4. (4.4, the memorization transformer depends on the sentence length L, which is due to the limitation on the parameter precision (i.e. q Z4). Without limitation (i.e. 9 = oo) on the parameter precision, the structure of the transformer does not need to depend on L, as shown below; the proofs given in the Appendix F.2.1 for no-Soo-:rr and Appendix F2.2 for CoT-transformer.
Proposition 5.3. Let S be a finite language with N elements and for T basic symbols, which satisfies the condition in Theorem 4.1 (Theorem 4.4). Then there exists no- no-CoT- Con-rranforrmmr (CoT-trunsformer) F & H8TT),(N)) (I E H O(N)))))) which can memorize S.
But when the precision is limited, the increase length will bring more difficulties to memorization for transformers, and CoT cannot help to eliminate this difficulty. We can show that if the precision of transformers is limited, the number of parameters of the memorization transformer must depend on the length for some language, as shown below.
Theorem 5.4. For any E 2 and precision q E 244, there exists a n E Z44, a basic symbol set T such that [['l < 5 and a sub- languaeg S C LCP,, n with [S] < 10, such that S satisfies the condition in Theorem 4.1 (Thorrem 4.4), but cannot be memorized by any F E H&Pp, (F E H,
The above theorem shows that as the length increases, any fixed structure transformer is not sufficient to memorize certain languages which just contain O(1) sentences and O(1) basic symbols. Although do not know how accurately calculate the dependence of parameters sentence length, the above theorem actually implies that both types of transformers will face difficulties with languages with unbounded sentence lengths.
6 Memorization of infinite language is hard
In the preceding sections, we only considered finite languages. This section will explore the challenges transformers face in memorizing infinite languages, illustrated through two specific languages. If transformer can memorize an infinite language like Arith,, then we can say that transformers truly have the ability simulate algorithm. For the expressive power of tranffosfsss,rrs, all results are for finite languages. For instance, Arith,,.. is considered in [ and input with finite length is considered in 26 21].
In this section, we discuss whether transformer can memorize infinite languages which is an important open problem, and we provide some negative results related to this problem. We
8

---

demonstrate that neither the no-Col CoT-transformmrr nor the CoT-tranfformer is able to memorize certain basic infinite languages, suggesting that CoT might not genuinely aid transformers in resolving these issues.
Memorizing TCP with transformer. By Theorem 4.1 Theorem 4.4). for any S C I.P,, that satisfies the condition in Theorem [4.] (Theorem (.4). there exists no-Coo--rranformer (CoT- transformer) that memorizes S. But for the infinite language I.CP, this is not true, as shown below, which is a corollary of Theorem 5.4
Proposition 6.1. There exists a basic symbol set T and an infinite sub-language L.PP bused on r, such that S satisfies the condition in (.7 4.4, but S cannot be memorized by any no-CoT-transformer (CoT-transformer with any precision 2 co.
This proposition shows that both types of transformers, even without precision limitations, cannot memorize certain simple infinite languages, such as length counting.
Memorizing Arith, with transformer. Since Arith, is a very basic computation problem or algorithm, it is interesting open problem to show whether there exists CoT-transformer that can memorize Arithp. We will prove a negative answer to this problem under certain conditions.
We first define how to transformers to solve problems in Arithp,, and Arithp. We say that no- CoT-transformer F can solve Arith (Arith,) if J can memorize Arith p. (Arith,). We say that CoT-transformer FF can solve Arithp.. (Arith,) F can memorize Arith,, (Arithp), and for any (z, y) E prith (Arithp), F(x) outputs CoT as follows: I = 21 where I; is sentence in Arith p.r. (Arith,) obtained from T;-1 (z zσ) by performing several accurate arithmetic computations. We introduce a notion below.
ZM = y'o.
Definition 6.2. For a transformer F and a sentence x, define the confidence of F(x) to be Fi(x) maxjşt (x) where i arg maxy (z:). We say that Co.--rrannsformrrr.... F solve Arith p. (Arith,) with confidence c E R2,, if the confidence F(x) is not smaller than c for all (I. y) E Arith Arith (Arithp). We say that CoT-transformer F can solve Arithp..(Aritt)
with confidence
if the confidence of each step in CoT is not smaller than e for all (I, y) E Arith,. (Arith,).
We explain the motivation behind the notion. In real computation on a computer, is impossible to achieve arbitrary precision. Therefore, to ensure that F produces an accurate output for the input with positive certainty (the confidence level of the correct label should exceed the confidence level of the incorrect labels), the confidence of F(x) must exceed a specific constant c. We will show that, under such a confidence assumption, the transformer cannot solve Arithp-
Proposition 6.3. For any c > and precision q E Z, J
(1) there exists no- Cor--rrssffnfrrerr or CoT-transformer with precision q that can solve Arith with confidence e. ffror any fixed L..;
(2) there does not exist a no--so--tr or a CoT-transformer with precision q that can solve Arith, with confidence
This theorem reveals that, despite the absence of precision constraints for transformer parameters, under the realistic assumption of positive confidence, is not feasible to tackle infinitely long arithmetic problems. However, finite-length arithmetic problems can be addressed effectively. This conclusion highlights the challenges that transformers face when tackling entire arithmetic problems. In fact, we propose the following conjecture.
Conjecture 6.4. Arith, cannot be memorized by any exed-precision CoT- or no-CoT-trees CoT--transformers.
Remark 6.5. In [26] 211, transformers have been shown to be Turing complete in the sense that transformer can simulate a Turing machine with finite inputs, and a set of transformers can simulate an entire Turing machine. The main technical difficulty in limiting finite inputs that the input length is used to construct the position encoding of the transformer. Conjecture 6.40 i.44iplies single transformer cannot simulate Turing machine with an infinite number of inputs and thus not Turing complete in the rigorous sense.
implies that

---

7 Conclusion
In this work, from memorization-capacii perspective, theoretically analyze the impact of CoT on autoregressive transformers. We have found and proven the necessary and sufficient conditions for finite language be memorized by the CoT-transformer or no-Coo-tranfformer, and estimated the number of parameters required for memorization from the perspective of upper and lower bounds. Thus, the relationship between the CoT-transformer and the no-CoT-transformer was thoroughly studied. Specifically, the languages that can be memorized by the no- no-Col Cor--ransformmrr and CoT- transformer are different, and the mo-Coo-rransfommee requires position embedding to enhance its expressive power, while the CoT-transformer needs only more basic symbols to enhance its expressive power. Finally, we proved that CoT' cannot help the transformer solve some problems from the perspective of necessity, such memorizing infinite languages. Although no experiments are provided, our results have some practical implications that are explained in the last paragraph of Section 1.
Limitation and Future Work. This paper only analyzes the power of CoT in memorization for data with one token as the label and ignores LayerNorm to simplify the model for analysis. Positional encoding not considered in most results. Refer Remark 4.11 for detailed explanation of this issue. Finally, several key aspects of the power of CoT are still not well understood, including those connected Conjecture 6.4
Acknowledgments
This paper is supported by the Strategic Priority Research Program of CAS Grant XDA0480502, a Huawei Grant TC20251015013 NSFC Grants 12288201 and 92270001, and the Robotic Al-Scientist Platform Chinese Academy of Sciences, CAS Project for Young Scientists in Basic Research Grant YSBR-040, ISCAS New Cultivation Project ISCAS-PYFX-20220 DCCSS-CZD-202202. The authors thank anonymous referees for their valuable comments.
and ISCAS Basic Research
References
[1] Peter Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve- dimension and pseudodimension bounds for piecewise linear neural networks. Journal of 2019.
Machine Learning Research,
[2] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32)15849--5588 2019.
[3] Manuel Bronstein. Symbolic Integration, Transcendental Functions. Springer, 2005.
[4] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 13:1877-1901, 2020.
[5] David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. In International Conference Machine Learning, pages 5544 5562.. PMLR, 2023.
[6] Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. In Advances in Neural Information Processing Systems, pages 2881-2891, 2020.
[7] Guhao Feng, Kai Yang. Yuntian Gu, Xinyue Ai, Shengjie Luo, Jiacheng Sun, Di He, Zhenguo Li, and Liwei Wang. How numerical precision affects mathematical reasoning capabilities of llms. arXiv preprint arXiv:2410.1385; 2024.
[8] Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective. In Advances in Neural Information Processing Systems (NeurIPS 2023), 2023.
[9] Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint 1rXiv3161,.04231, 2016.
10

---

[10] Shih-Chi Huang and Yin-Fang Huang. Bounds on number of hidden neurons of multilayer perceptrons in classification and recognition. In Proceedings of 1990 IEEE International Symposium Circuity and Systems (ISCAS), pages 2500-2503, 1990.
[11] Tokio Kajitsuka and Issei Sato. Are transformers with one layer self-attention using low-rank weight matrices universal approximators? arXiv preprint arXi:: 14023, 2023.
[12] Tokio Kajitsuka and Issei Sato. On the optimal memorization capacity of transformers. In The Thirteenth International Conference on Learning Representations, 2025.
[13] Junghwan Kim, Michelle Kim, and Barzan Mozafari. Provable memorization capacity of transformers, In The Eleventh International Conference on Learning Representations, 2022.
[14] Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilić, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al. Bloom: 176b-parameter open-access multilingual language model. arXiv preprint arXiv:221 2023.
[15] Binghui Li, Jikai Jin, Han Zhong, John E Hoperoft, and Liwei Wang. Why robust generalization in deep learning is difficult: Perspective of expressive power. In Advances in Neural Information Processing Systems, 2022.
[16] Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. In ICLR2024, 2023.
[17] Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern perepparamttrized learning. In Proceedings of the 35th International Conference on Machine Learning, pages 3325-3334, 2018
[18] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhssh, and Peter Clark. Self- refine: Iterative refinement with self-feedback. In Advances in Neural Information Processing Systems, volume 36, pages 46534-46594, 2023.
[19] Liam Madden, Curtis Fox, and Christos Thrampoulidis. Next-token prediction capacity: general upper bounds and a lower bound for transformers. arXiv preprint arXiv:2405.13718, 2024.
[20] Sadegh Mahdavi, Renjie Liao, and Christos Thrampoulidis. Memorization capacity of multi- head attention in transformers. arXiv preprint arXiv:2306.0200 2023.
[21] William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. arXiv preprint arXiv:2310.00923, 2023.
[22] William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions the Association for Computational Linguistics, 11:531-545, 2023.
[23] Quynh Nguyen and Matthias Hein. Optimization landscape and expressivity of deep enns. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 3730-3739, 3739,, 2018
[24] Franz Nowak, Anej Svete, Alexandra Butoi, and Ryan Cotterell. On the representational capacity of neural language models with chain-of-thought reasoning. arXiv preprint arXiv:2406.1417 14197, 2024.
[25] Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks using sub-linear parameters. In Proceedings of Thirty Fourth Conference Learning Theory, pages 3627-3661, 2021.
[26] Jorge Pérez, Pablo Barceló, and Javier Marinkovic, Attention is turing-complete. Journal of Machine Learning Research, 22(75):1 2021.
[27] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 188)99 2019.
11

---

[28] Jack W Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican. Jordan Hoffmann, Francis Song. John Aslanides, Sarah Henderson. Roman Ring, Susannah Young, et al. Scaling language models: Methods, analysis & insights from training gopher. arXiv preprint arXiv:21 22:::21/2.11 1446, 2021.
[29] Michael A. Sartori and Panos J. Antsaklis. A simple method to derive bounds on the size and to train multilayer neural networks. IEEE Transactions on Neural Networks, 2(4):467-471, 1991.
[30] Eduardo D. Sontag. Shattering All Sets of 'k' Points in "General Position" Requires (k: 1)/2 Parameters. Neural Computation, 9(2):337-348, 1997.
[31] Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati, Chain of thoughtlessness? an analysis of cot in planning. arXiv preprint 2XXi:22405.04776:2 2024.
[32] Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of relu neural networks. arXiv preprint arXiv:2 10.03/17, 2021.
[33] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[34] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint ar arXiv:2203. 2022.
[35] Zezhong Wang. Xingshan Zeng. Weiwen Liu, Yufei Wang, Liangyou Li, Yasheng Wang, Lifeng Shang, Xin Jiang, Qun Liu, and Kam-Fai Wong. Chain-of-proon Examing the necessity and accuracy of cot step-by-step arXiv preprint vrXiv:2406.16444 2024.
[36] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837 2022.
[37] Franz Winkler. The algebro-geomeen method for solving algebraic differential equations a survey. Syst Sci Complex, 32:256-270 2019.
[38] Nan Xu and Xuezhe Ma. Ilmm the genius paradox: A linguistic and math expert's struggle with simple word-based counting problems. arXiv preprint 11Xiv:2410014166, 2024.
[39] Lijia Yu, Siao-Shan Gao, and Lijun Zhang. Optimal robust memorization with relu neural networks. International Conference on Learning Representations (ICLR 2024), 2024.
[40] Lijia Yu, Xiao-Shan Gao, Lijun Zhang, and Yibo Miao. Generalizablity of memorization neural network. In Advances in Neural Information Processing Systems (NeurIPS 2024), 2024.
[41] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commuications of the ACM, 64(3):007 115, 2021.
[42] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.0100 01006, 2022.
[43] Tianshi Zheng, Yixiang Chen, Chengxi Li, Chunyang Li, Qing Zong, Haochen Shi, Baixuan Xu, Yangqiu Song, Ginny Y. Wong, and Simon See. The curse of cot: On the limitations of chain-of-thought in in-context learning. arXiv preprint AXiv:25044000081, 2025.
[44] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205. 2022.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, we have done.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
Justification: In the Section 7
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:[Yes)
13

---

Justification:
In this Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our contributions are theoretical research.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA]
Justification:
Our contributions are theoretical research.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.ce
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /mips.cccppblic/guici. httpp///iiiiciiiccoo/oooeeaaaaaa CoodeSubeeiieeeeeeeeee ssi asiinnolle onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Our contributions are theoretical research.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
Our contributions are theoretical research.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Jus contributions are theoretical research.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:///eeips..eeeee httpp//p.....ppp....///ccccccaas
Answer: [NA]
Justification:
Our contributions are theoretical research.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there exists special consideration due laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: None of these.
Guidelines:
The answer NA means that there exists no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there exists a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
16

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there cxist negative socictal impacts, the authors could also discuss possible mitiga- tion strategies (e-g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our contributions are theoretical research.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our contributions are theoretical research.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppawpptseeee throdee.etecce...... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
17

---

Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Our contributions are theoretical research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our contributions are theoretical research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [No]
18

---

Justification:
The large model only helps polish the language.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to LLM policy http:ear//eerriioocccc/oooeereee for what should or should not be described.
19

---

A Details about the structure of the transformer
A.1 Position Encoding
Embedding matrix. For sentence æ, the embedding matrix of x: is Ie (Dly Ub....., U., ) which will be the input to the first hidden layer in the transformer. We call n the input length. Unlike feedforward neural networks, the input length of the transformer does not need to be fixed, and transformer can handle input sentences with any length.
About Position Encoding, With position encoding, the embedding of is (U), + Ej, 2/ E vi,, + En)", where E, is the position encoding for the i-th position. The position en- coding provides location information. However, the use of position encoding may limit the length of the language that the transformer can process. In this paper, we aim for the transformer handle languages of arbitrary length and do not limit the length of CoT, so do not employ position encoding. For example, we see position encoding as adjustable parameters, then encoding the first N positions only will make the transformer able to process input with length of no more than N. If we take position encoding as n for the n-th position, then, at the later positions, the position encoding may exceed the precision limitation.
A.2 The residual layer
In the definition of transformers, we use a transition matrix W in the residual layer. In some other works such as W / is the identity matrix.
In fact, the functions that the transformer can express under these two definitions are the same, as shown below. Firstly, name the transformer defined by W,-1 I in each residual layer as F1. Then we have the following result.
Proposition A.1. For any given basic symbol set I, we have
(1) For any transformer F1, there exists a transformer F with transition matrices such that F(z) = Fi(x) for any x r+
(2) For any transformer F with transition matrices, there exists a transformer F, such that Fi(x) F(x) for any T+, and width(F,) I 2w)dth(F), depth(Fr) S 4depth(FF) and head(Fi) S
(F..
Proof. (1) in the proposition is apparent: we just need to take the whole transition matrix in the residual layer of as I, and other parameters are the same as F7.
We now prove (2). We will show the following at first: for any hidden layer in F, it can be expressed by a combination of four hidden layers whose transition matrices in the residual layer are I.
Let a hidden layer L J with width m and head be written as L(x) = -W +ATT())>)) + (*W ATT(z)), where ATT(x)= Σm (aammaxxxxQ,KKK + M)zV, and FNN (z) = Relu(zw1 + b)w2.
Then we define four layers with width not more than 2m and head H whose transition matrix in the residual layer is as follows:
The first layer To also uses x E R2xm to obtain (z, 0) E R2222m which is similar to that in the proof in Lemma B.2
The second layer is (t) = t + Relu(t(WT), yTV where Vy.m+s 1, V Vn+im+s = -1 for all j E [m] and the other weights are
The third layer is L2(t) = t (t) + FNN + (t))
The attention layer is calculated as AT)2(() = ΣH, SO + M)LV', where Q2 E R2mx2m is defined as: the (j. k) weight is the same as the (j, k)-th weight of Qi, where j, k E [m]. and other weights are O. K¹ IR. 2m2mx2n x2m is defined as: the (j. k)th weight is the same as the (j.k) k)
weight of K, where j. l E [m]. and other weights are O. V E 2m2m x x2m is defined as: the (j. k k-
weight is the same the (j. k)-th weight of V,, where j, d [m.) and other weights are O.
The FNN layer is calculated as FNN2(1) = Relu(tuf @ b') 8')uk. w/, w/ are defined as: the (i+ m, m)-th weight is the same as the (i.j)-th weight of wk. where i,j E [m]] and other weights are 0. b'
20

---

is defined as: the (j + m)-th weight is the same as the j-th weight of b but other weights are O, where j E [m].
Then we have that, for any x E R we can obtain x' = (x. 0) E R2x22 by the first layer To- Then by the definition of L1, we can calculate: I, (x²) (x, (.). Hence in the T2z, it holds
ATTa ((a,, wW)) = > soft K2 + +M) (0, zV.)) = (0, ATT(2)). In the FNN, we have FNN2 (12, x: W) ATT ((2, (1,, ))) FNN ((x,, (TT()))) = (N (T)()))). So
we get Lg(x') = (z, ww + (TT(z) + FNN aw + AT))
Let the last layer Li use (z, xw ATT +NN(( (z)) to obtain aw (TT(2) +FN ATT(
So L(x) = xW + ATT()) + FNN + ATT(2)) is equal to L1(I2((1 (Lo())))) = ((( 0)))
((L = xW + ATT(2) FNN(=W + ATT(2)). And it is easy to see that the width, heads of Lo, L1, La and L1 are not more than 2m and H, respectively.
So by the above result, for an F with width Wi, depth D and head H, for each hidden layer in the transformer, we can construct four hidden layers as above. Then use such layers and the output layer which is the same that in F to form transformer Fj, which has width 2W1, depth 4D, head H. and Fz) = F(z) for any x E r So we prove the result.
B Preliminary results
We give two lemmas that will be used in the subsequent proofs.
Lemma B.1. For any sentences and z, if the first n symbols in x and are the same, then for any transformer F and j E Z4,, the first n rows in the outputs of the j-th hidden layers of F(z) and F(z) are the same.
Proof. Firstly, we prove that for the j-th hidden layers Fi Ff if 1 and 2 satisfy that the first n rows in Iı and 2 are the same, then the first rows of F (11) and F are the same.
Assume that FC can be written as: (i) xw+ - softmax(#Qu V.=" V +M) FNN (xw E softmax(#Q& VVxT + M))
In the residual layer, the calculations in this layer do not include the interactions between different rows.juss do the same transformation to each row. So when F and ž satisfy that the first n rows in I and are the same, I w and w also satisfy that the first n symbols are the same.
In the attention layer, from the definition of M, for any i Z4. the i-th row of softmax(#2 Vg M) can be written as (z, Qx Va,zT' 2x Va x; Que V4 ................................ xz Qu Va22 0, O,... 0), where æ, is the i-th row of z. So it is easy to see that, when 21 and 21 satisfy that the first n rows in 21 and 21 are the same, the first rows of sax Q2 Va + M)zz and softmax Qu V + M)2; are the same. Hence, because the other parts in the attention layer do not include the interactions between different rows, we have that the whole output of the attention also satisfies that the first symbols are the same when input 1 and ø1.
By the above result, we find that the first n rows of 2 w + Et softmax (2) ( Veaf + M)x K and 21 w + E softmax Qu 2 + M) K& are the same. Similarly to the residual layer, we know that the first n rows of FNN(21 w + Σé softmax(2; Vi.a" MM + M) K2) are the same. Adding them, we can obtain the result.
and FNN
Ex= softmmmxax(x
Now, can prove the lemma. We prove the result for the first layer. If the first symbols in and are the same, then the first n rows of their embedding matrix are also the same. According to the above result, we see that the first n rows in the output of the first hidden layer are the same for input x and 2.
If the first n rows in the output of the i-th hidden layer are the same, according to the above result and the fact that the output of the i-th hidden layer is the input of the (i + 1) hidden layer, then the first n rows in the output of the (i + 1)-th hidden layer are also the same. When input and to the transformer, we have proved that the result is valid for i 1, so the result is valid for any We prove the lemma.
D
21

---

Lemma B.2. Let F: : - R 1xm be an FNN network with depth D and width W. Then we have
(I)IF F has oulput layer, then we can find transformer F1 without output layer such that for any k E Z4 and x E Rkxn, it holds Fi(x) = (F2 2 (x1). ).F (zz)....., ......TT (xxx) ")²))"" where Ij is the i-th row of x. Hence, Fi has width O()) and depth (D), and has the same precision F.
(2) We can find a transformer F1 such that for any l E Z+ and x E B it holds Fi F(( F(xx), where z& is the last row of z. Hence, Fi has width O(W) and depth O(D), and has the same precision as F.
Proof. It is easy to that (2) can be obtained by (I), so we just need to prove (1). To prove (I), we just need to show how to simulate an FNN layer by the transformer layer.
Let an FNN layer be written Relu(=W+B) R Ixn + R xm where W E R=x and B E R 1xmm Then we can use three transformer layers with width m + n to simulate it, which directly proves the lemma.
The first layer Fl. Use R to calculate the (ar, 0) R*x(n+m), Just need to take the residual layer in the transformer layer as rw, where (1, 0) (=x((+m), and / is the identity matrix. Other parameters in the attention layer and the FNN layer are all zero.
The second layer F Let the residual layer be and the parameters in the attention layer be all O. Then the second layer can be written as: x + FNN( = x - Relu @ b)w2.
Then, we define Wi [((*t))((+*m) as: the last m columns are w/ (WT 0)" and the first columns are O. We define b b x (n + m) as: the last m columns equal to B and the first n columns are O. Then W2 E (enett))(m+) is an identity matrix.
It is easy to check that the k-th row of Relu(F (F' (z)w) + b)wg is (0, Relu(x W + B)), where Iy is the k-th row of x and l E [n]. So the k-th row of FFF (x)) ) is (IA, 0) + (0. F(xx)) = (æx, F(xx)). The third layer F3. This layer satisfies F F(xx))) = F(xx) for each l E [n]] We just need to take the residual layer as zw where w (0, 1)a E [(n+m)xm and other parameters are 0.
We prove the lemma.
C Proofs of results in Section 4.1
In this section, we will give proofs for Theorem 4.1 and Proposition 4.3
C.1 Position value
For given sequence consisting of and b, such as = (a, a, b, a, b). let |s| be the length of s. We define the position-a value as (a k) where a E 24, and S [s], which calculated as (similar for the position-b value of 8 as (s k)):
(1) Let ne (s k) Σt l(s: = a) be the number of in the first k elements of s. Similarly, let mo(s, k) = Ek=1 ((8: = b), where s; is the i-th element of s.
(2) Let (8, (s, (2mo(s.k)tnnao.
(s.A)
(3) Let Vo (8,
(8,
We call Va the position value. is easy see that if [s|] = |s2| n. then Vi k)) Va (s2, k) for any k E [n] if and only if s = 52. So the position value can be used to distinguish the sequences with the same length.
(s2,
For the 81 and $2 with the different lengths, the position value can be used to distinguish them. We have the following lemma.
Lemma C.I. Let a E 24 and 81, 82 be sequences satisfying |rs| * |82). VfVo (81, (s1)), Va (82, (s2))
not 0 and 1, then V (s1, (sil) * V ( s22)).
22

---

Proof. Without loss of generality, we assume that |s1 < Va ($2, s2l) are not and 1, and (s) (si]) Va S2., 82 lemma in three steps.
|s2]- Assume that (s1 (s1l) and We derive contradictions prove the
Step one: We define two rational polynomials Fa,es (z)
[s Ek=1 tn.(s).)) and
Jel
(a
Fa,0z (x) = 1
Eial
s2l
(a( ans +na then we have the following result:
p22
Fa,s, (x)
= (2) Fa,os for any x E E.R.
This is because Fa,si (e") V (s2 = Fa (e"), and considering that e" is not an algebraic number and Fa,s, is rational polynomial whose coefficients are rational numbers. We thus have Fa,sy (I) = Pa,sz (I) for all E IR.
Step two: Assume that P < [s2] is the maximum prime number not more than |s2]. Then we have the following result: The first P elements of are the same.
If not, we have ($2, P) + 0 and ms(52, P) o O, we consider the value of Fa,ey (x) and Fo (2))
(=2.P) for x = Rs
c).
Because P is the maximum prime smaller than [82). so P |s2|/2. So, there exist no Q E [|>2] and Q + P such that
n, (=(=2
(*2.P)) P) If not, there must be Plna(s2 Q) + (s Q), which P)-
my ())
implies Q 2 2P > [22). a contradiction with Q [[>|]]-
So, when I = na (N0.
PT (1 +) and + O, at most one sub-rational formula in Fa and Fa,s2 te (e
tends to co (i.e. the P)o(s..P)tn.(e...
So if (81, , P) na (82, P). then Fa (3)/ amols, P)nn,,, tends to 1 when -> 0 for i == 2. Since |1|| < |sı| - 0.5 < [32|. we have Fa,s (x) < (len( ++0.3j Fa,s. when e + 0, which is contradiction to step one.
ne (M..
If (s1, P) # (a P), then Fa,s, (z) will not tend co when 0, which is also contradiction to step one. So we proved step two.
Step three: We now prove the lemma.
Because Vo (81,/1110 |11l) and V (s2)) are not and 1, there exists at least one and at least one b in the $1 and $2. By step two, without loss of generality, we assume that the first P elements in 82 all a, and the position of the first in 82 is at mg It is easy see that mo 2 P.
Then, consider the values of Fa,ss (x) and Fa (x) for (=. (1+ c). mo(
Firstly, we show that no other Q * mo and Q [s2] satisfy (e2 p. Ps..mmo mo+1)
ms(a2. mll)
Because mo 2 P > / 2 and ny (52, mo + 1) = 1, so if (=2.2
there must be
no (=2
mo
(32, Q) 2 2n, ( (82, mo 1) 2mg 2 2P > |22]. which is a contradiction.
Then, similar before, Fa.e.()) which is contradiction to step one, so we prove the lemma.
prove that if
na m= (1 + <) and c - 0, then Fa (z) + mo(ez.mo+1)
have the following result for sequences of the same length.
Lemma C.2. Let E Z.. For any such sequences $1 and s2 where len(s1) ) = -ee((22) = and
va (s1, Va (s2, n²) We have
(I) The number of E [n) such that (s1 k)) = is equal to the number of k E [n] such that Va (82, (2,k)=11 1.
(2) The number of E [n] such that (s1, is equal to the number of k E [m] such that
Va (82, k) 33=00
Proof. We prove (1) first.
23

---

If V. (s1. n) = Vi (s2. n2) = 1, then we know that all elements in are all 1; if V (s1, n)
=
Va ($2, n) = 0, then we know that all elements in s; are all
Assume ( n) = ( (82, n) o O and V n) = Vo (82, n) + We define two rational poly-
nomials Fa,s (ar |i
analé kea and Fa.s, (x)
Eiel
Re (89.
82
Then, similar to the proof of Lemma C.1 R.
we have the following result: Fa,st (x) = Fa.. (2) for any
is easy to see that when x >> 00, (2) (x1.k)
0 when no(s1, k) # O, and (s1,
(a(a)k) = 1. So consider the Fa,si (x) = Fa,2((2 (x) when x + oo, we know there must be #h
na (=2.f) that there must be the same number of 1 in (nn( JEE(m] and (ma()
(a(e1)))
]E(n] +nn(ss))) = for any S J. similar for $2- So the same number of 1 in (na bE(N)) and { ne na(3):)
It is easy to see that (me(el 1 equals na
na(#1.f)
na(s).)
(no Je(n) implies there
exist the same number of ls E [[s1]] such that Va (s1, k) = ($2, = 1. Hence, we directly get
(I) in the lemma.
For (2) in the lemma, just need to consider that 2h (sk. j) + o (sk. 1 and Va V (sk, Vg (sk, = for any & E {0,1} and j S n. Similar to the proof of (1), we get the result.
L
Then, we calculate the following value:
($1, (21)) m Jeu(( )s L,Le((e))) L. (enl (V
Va (#2, (82, (s2))]
Firstly, we have the following lemma.
Lemma C.3. If f is a nonzero integral coefficient polynomial whose coefficients have absolute values not more than A, then for any E Z satisfying e² > A 1, we have (f(c)) 1.
Proof. Because ex A+ 1, so E Ae = A -
n-' S usts
So, letting L dfg(f), we have lf(e") eth e -t-11 Ac ca A A= ct-1 this is what we want.
> e -1)
Lemma C.4. e 2 1,2L+2 + 1, then
min (aal
(81, -
Proof. Firstly, without loss of generality, let (()(s)) > (*2), we have that:
va (s1: (21) Vo (52, (82))
1 E
111 == Le (81, k:)
k= Lh (82, k:)
|22
|azl
(e Ab) 51 Ekel es no (osssskk) +n
Isal
(e2
180
= 1 Fr (e")
1 F., (e
(ea)
leal He
22 F., (c)) (e") Fr,
(e))
81 12 Ho, (e" H. (e))
Here Hg, (x)
n (mo(s), k) (s k)) is an integral coefficient polynomial, whose coefficients
are not more than | (ms (si, k) + nu (ss, k)) < Lt; Fx, = E/ n. m..sk.)H... (x)
is an inte-
gral coefficient polynomial, whose coefficients are not more than F. (z) S Σ (s, < 1++
So. we have that |sz| (x) and |s Fe, (x) H H,, (x) are two positive integral coefficient polynomials, so |s2 F., (z) (x) is $1lFe, (x) , (x) is integral coefficient polynomial, where the absolute values of coefficients are not more than L x L 1++1 x 1'. = 21,42 Considering Lemma
C.3 and e > 1 1, can prove that |82 Fs, (e H., (ca) |81 / (e (e,) (ea) > 1.
Hence, we have that |s ||>2 H., (6)) (c S (T ca = 1,2L+122al, We prove the result.
D
24

---

C.2 A lemma for FNN classification
For FNN, we have the following result.
Lemma C.5. Let (xx
Relu((Az + B)/109) where A, B, C are integers. Then f(x) can be expressed as a network with width 6 and depth ([In(max /B1)) + [C/q]) and precision
Proof. Firstly, we define a function (m)m) for any integer m: when m 2 O, h,(m) (m/10% 1004 10 10 when m < O, h;(m) = -h; --,(-m). Then we have that: m = Inggo m//g.
(m)). Hence, let Hy(m) Σ j < [oog1 m/g]- It is easy to see that Hnogio mm/ = m. When j > [log10 m/g]. let (m(m)= m.
Σ Elloroo m/vl m//
ii m/al-j 10(- --08000 m/al)an, when
Then, calculate Relu Az + B) as follows:
The first layer has width 6:
Use x to calculate Relu(z), Relu(-2), Relu (A)a), Relu(-Ho(A)r)) Relu and Relu(-Ho(B)) Because HA(A) and HB(B) are q-precision, such layer just needs q- o-precision.
The n-th layer has width 6:
Assume n - 2 < [logoo A/gl- Since Hn (A)z = -- + hog m/v -x+1 (A)z and 2 = Relu(H,-2(A4))
Belu(-H,-2(A)p)) x = Relu(x) Relu(- x)) use layer with g-precision calculate (H,-1(A)a) Relu( (A)xr by Relu(H (AA))), just need to keep Hn- (A) 2 (B)) can be caleulated similarly.
(A)x) and Relu(z), (elu(-=)), If n 2 2 [log A/gl. then we
So we can use
Relu(x:), Relu(-x), Relu(HHn-2(A)e)
Ret----((A))))))t(((---22)))),) Rel(-
to calculate the following values in the q precision:
(zlu(z), Relu( ()), Relu H (A)x))))ar) Relu(- -H Hn-1(A)xx), (ela)))),,el((H--a.e.,. (B)) Relu( (Hn--
At the = [log10 max ( (A, B3/g] + layer, calculate Relu(Az (Ax + B).
Because T - 2 2 [log10 A/g] and T 2 2 [log10 B/g), so (A( = A and Hr = B.
In this layer, use Relu(x), Relu(- x), Relu (A)x)))) Relu( - Hr(()x)) (B)u) ReluReelluuaaaeeee -Hr
to calculate Relu(Aa Ax + B), just use (A) = A, Hr(B) = B and Relu( Ax + B) =
Relu(Relu(Az)) Relu(- + Relu B) (eel(--))-- We can obtain the result.
Finally, in the next [C'/q] layers, we just need to divide Relu(Aæ + B) by 10s in each layer, and the last layer, divide it by (00-9 Then we obtain Relu((Az + B)/10C) and prove the lemma. O
Lemma C.6. For any given 2 < x2 <... EN where x, C and bz, IzI > G. any given
E [m], there exists a network f with precision q. width O()), and depth O(N lnmC// that satisfies (f;) vil 0.2.
Proof. To begin with, we demonstrate the case for the scenario without precision limitations. In this scenario, achieving these tasks requires depth O(N) and width O(1), as described below:
The first part: In this part, f is used to calculate the label of æ1 and has three layers.
The first layer f fl:) (z) has width 2, with fi (x) Relu (10 æn] 10axr) and fl (x) Relu(z).
where is the minimum integer such that 10 2 10th z1 + 2. Since x2 2 Φ1 + c, we have 10th < (1/cc.
The second layer (x) has width 3: f fl. (x) Relu(1 . f (=)/100) (2) Relu(10 x
(0.5 - fl. (x))) and f f1.2 Relu( (1. (æ)), where d is the minimum integer such that 1092-2 2 >
m. It is easy that q2 S m).
25

---

The third layer (x) ( is the output of the first part, which has width 2: f1()) f11 =
Relu(y1 (x) 21.2 (x))) and fg (z) = f2- = Relu(fs (z)).
So when i + 1, we have n (a:)) 0, so f = and / 2 5. Hence ʃ (x) [z)
Relu(y) (1 - 5))
0. When 1 = 1, using the definition of q1. we have 20 > 10 x2
10 x1 2 Relu (10%) x22
10 = fl. (m1) 2 Relu(109) 22 - 1 21) 2 1, so - f1.2(a) (x) = 1+ fl (z) 10 <
1+0.2/m (use the value of (2) and f2 (x1) = Relu 10x (0.5 (f)((())) I Relu(10-(005--0)
0.
Hence, we have fi (x))
Relu(y) 22) [vi, / + 0.2]. using the lvi S m. Finally, we have
(xx))
E [V1.21 21 + 0.2] if and only i = 1 and (xx) = 24 for any E [N] which is apparent.
The i-th part, where i - N: This part is used to calculate the label of 2, and has five layers.
The input i-th part is the output of (i - 1) part. If the (i - 1) part fr satisfies: the output of f== has width 2, | (xz) yز 0.2 when j S i- 1, f (zy)
when j i 1, and f2 (x,) = 2. for any E [ then we can make the output of the i-th part (*) to satisfy: (*) has width 2. lf((z,) Myl s 0.2 when j S fi(z,) 0 when j > i, and f2(z,) 2j for any j E [N].
To do this, the i-th part needs six layers: The first layer and the second layer output (x) satisfying:
(x) = ( 2 (w) 2ee 1/100 (x)) f2- (x) and f3²(() 1 (z).
where d1 the minimum integer that satisfies [10"*x;]/100 1/100 < sq + c/3. easy to see that 10nh - O1/cc. Now we show that f2 (x,p)
f > c/3 for any p + i.
We know that fi.2 (x;) 2j when j j> i, and // (xxx) = 2; 1/100 - 3%k when h: S i, so there must be 53² (xpp) f (x;) 2 ming-ci,
Jo. ;2 10 v; /100- - -,, (2 /10 - x:) for all p * Based on the definition of q1, we know that Vy - (2 /10 - 5.) > c/3 for any 2.) > c for any k < i, so get the result.
j > i and 20[10%,,1/00f
Ix) (2 x0
Then let the next three layers follow the first part, and use fa,) to obtain (x) that satisfies:
ph = - (z): (xx) - wl & 0.2, f f (xz) = 0 when + i; and fx²(() (z) = f1
f2 (z).
And the last layer is the output of the i-th part, where: fi(x) = Relu R (1))x())))))))))))(()) + ... (x)( and fi(x) = f (xx), which is what we want.
The output part: Just output (x)), and this is what we want.
is easy to check that such a network has O(N) nodes and has width O(1), where each parameter is not greater than OmmC//c) Now we just need to turn the parameters of the above network to be of g-precision. By Lemma C.5 and each layer defined before, if a node has parameters beyond precision, we can use network with ((1) width and (0(lmC//p depth instead of it. So we obtain the result.
We have the following lemma which is used in the paper 225
Lemma C.7. For any u E IR" and T 2 1, let u E R" be uniformly randomly sampled from the hypersphere 5m-1, Then we have P(((u, |lolla
7.
So we can prove the following lemma. Lemma C.8. For any given {x,) C R where ||:: $ 1 and 10; 2y1100 c, any given y: E [m). there exists a network f with width ((1) and depth O(N In that can satisfy [f(;)) vil < 0.2.
Proof. Firstly, we can find a vector u E Re that satisfies ||w||2 = and |uer uayl > O N just using Lemma
Then, we can find Up R such that: [|u, a//oo S ( xZ and each weight of u, is a finite decimal with precision OIn( N2n") )/9), so have |,,,24 Uy > 2 (x)))) and |u, 2n.
26

---

Then, we can use a layer to map 2; to U,-3; + 2n, and then use Lemma C.6 to find an FNN to memorize {(u,I, + 2n, y4)) and obtain the result.
C.3
Proof of Theorem
Now we prove Theorem
Proof. The proof has five parts.
For any given (z. y) E S, we define a sequence $x,5 E 2(a.b) as follows: Sn,i has the same length as I, and the j-th element of Sæ, is if and only if a: ys.
Part One: The Embedding.
We will embed in the following way: The basic symbols will embed in (vi, "ig......ff 10,1)47 where of = (0, 1, when j i,
vf 0,,1,,
Hence, the input sentence æ whose len(x) = will be embedded in a vector V E {0, 13
Part Two: Use the ([InnLIn L)/4]) layers to calculate the position value.
Let a be the minimum positive integer such that e 10" 2 L It is easy to see that < (n L)).
Step one: Firstly, for any input whose embedding matrix is Vz, use all the (4i 1) columns V expand 10a times, where E [T].
[ hidden layer make
To do this, in the first [ar/q] layers, we make the parameters in the FNN layer and attention layer but the transition matrix the residual layer is defined as: the (j,j)-th weight of the transition matrix is if # 4i for any i E [T]: the (4i 1, 4i 1)-th weight is 10"; other weights are O. Of course, make the (4i 1)-th columns expand 10th times, in the |a/gl 1-th layer, the transition matrix in the residual layer is -0a-af of
at (4i 1, 48 1)-th weights.
Step two: We use hidden layer to calculate 220 (sz,6, k).
Firstly, let the attention layer in this hidden layer have heads and let the i-th head in this attention layer be written as (attmmaxxx,KK,aa
+ M).V, where Qi 10,1) 1447x47 the (4i, 4i 1 1)-th
weight of Q; is 1, others are O; K2 E f0. 1]47444 and K; is the identity matrix; V, E {0, 10,1)47x4 1447x4T. where the (4i 2, 4i 2) weights of Vi are and others are 0.
Now, we consider the output of the i-th head when input x into the transformer, assuming that the output of the previous step is x'. Firstly, by part one and the definition of Qi, Kü, we know that the k-th row of x' Q2 K
Q'a'
((=))ai(1))<<<) (u))))) ( ( (x))aarz ((x))u-11 (xb) a............. ..... (z/)4-1)
(0=([(x[1] # n)) I (x:12] #
I [x[[n] 47))
Hence, considering the definition of M, the weight in k-th row and 4i 2-th column of Σ [<))))))))
"oftmax(='Q,KK,'") +M)x' is 0000 Σ
((1l)=nn) which is equal to !00 (su, k).
Then, is easy to check that (4i 2)-th column of softmax " Ve'V
(g 10"
(Sa,i, 1), 10" (s 2), 10" (sz, .)......................... d (s len(x)))
", ('' )o'V, are O. Hence, let the residual layer use matrix W E {0, 1) 1T4T, which defined as: for the i E [T]. (Ai - 1, 4i 1) and (4i, 42) 4i)-th weights of W are and the other weights are 0. The FNN layer is
By the definition of V.. it easy know that other columns of softmax
27

---

all O. Then, assume that the whole layer will calculate matrix (x E RRlo(2))477 by inputting the transformer. It is easy check that the (4i 2)-th [T) column of M1 (x) is
(ga 10 (Sm,, 1), da 10"h (N 2), to
10" 3)..,, ................................ _0t (Sx, (en(x)))
Other columns are the same V.
Step three: Next, use hidden layer to calculate V,100 ($2,ú, k).
In this layer, the input the Mi (ar) gotten by the above layer, so we can calculate the position value
by Mi (x).
Let the attention layer in this layer have T heads, and the i-th head (i E [T]. we have Qi K;
V, E {0, 1] 1 x4T" and the (4i 2, 4i - 2)-th weights of V, are 1, while others are 0.
Because Qi K; 0, it is easy check that in the i-th head, it holds
softmax softmax(M (z) (x) ()) = softmax (0 + (x) I (x),
where 1 is an inder-triangle aami-matrix, and the i-th row is ( ...... ......,,,000 0,000.... ...0....)) 0) (the first i weights are 1/1, while others are O). Considering that V220 (s. k) Σi Un (s, based on the definition of Mi (z), we know that the 4i 2 columns of i-th head are
((MM (x) 2
Va 1000 (sn,ú, 2)T = (V210' (82,5 1), 10 (82,6, 2), V00" (),,;,))....
By the definition of V,, it easy to know that other columns are 0.
Let the residual layer and the FNN layer in this layer be the same as in the layer in step two. So we can easily check that when we input the the transformer, we can obtain the matrix M2(2) in this layer, whose (4i 2)-th column (i E [TT) is
(V.10* (Sm,3, 1), V-10" (S2,5; 2), V-10" (s,,..),.... V.10" (s2,,, len())))²
Other columns are the same MI()), which implies other columns are the same as Us-
Part Three: Use FNNs.
Define the set V =(V:10 (s2. where j E [L] and V = U)e[1
We try to find an FNN f1 such that:
(1) (1) < 0.2 and (0)] < 0.2:
(2) If 2 E Vg/(0, 1}, then there exists a 2q E [NT] such that [fi(z) Zzg (NTL) < 0.2; morcover, when 21, 22 E uy. there exists (21) + (22)q-
Since there exist at most NT' samples in Vj and Vg n.v C [0 when i + by Lemma C.I such a network fi must exist. Hence, considering Lemma C.4 and Lemma C.6) know that such FNN fi just needs precision and O(NLT[LIO In LNT/41) layers and ((1) width.
Based on the (2) and the above fi, when input to the transformer, we define the matrix Ma()) which has the same size as M2(xr) as: the (4i 1)-th columns of Ma are ({M2(2z))4s-2)) 2), where (M2(x))4:-2 is the (4i 2)- column of M2(x); other columns are the same as those of M2(2).
Then by Lemma B.2 we can use transformer with width O(1) and depth
L L to obtain Mz(x) by M2(x).
Part Four. In this part, we use several hidden layers to obtain vector that is different from by Mz(x).
In the first layer, this attention layer has T heads, in the i-th head, Q: 0, K; 0 and Vi (0, 11 such that the (4i - 1, 1i - 1)-th weight of V, is I; others are 0.
The residual layer uses W E {0, 1] 1 xT' which is defined as: for the E [T]. (4i - 2, 4i - 2) weights of W are 1, others are The FNN layer is all 0.
Finally, we use 2L NTL layers to reduce the (4i 1) -tth columns (i E [T) of the output of the first layer by (NTT) times, in order to reduce the norm of the output for the above layer to no more than 1.
28

---

Let the last row for the output of the above layers be M() when input with length to the transformer. Then based on the definition of Mz(x), have that:
(1) The (4i 2)-th weight of M((x) is V110" (sz,i: n) for any i [n].
(2) The (4i 1) weight Ejs f1 (aa.id)) for any i E [n]. a(NTL)a)
Firstly, by the definition of position value and f1, it is easy to see that [2 I 1. Then we will prove that: for all (x, y), (z, S that do not satisfy, typ(x) - typ(=) = 72 for some E [T], we
have [[M{(>)) Mz(z)] 0c 2 min (2x10 L(NTL)
When typ(2) typ(2) = 1, let % typ(z). Then it is easy to see that % & typ(2). Now we consider the (4i 2)-th weights of Mc(x) and Mz).). is easy to see that the (4i - 2)-th weight of Mi(z) is but the (4i 2)-th weight of MI) is O. Which is what we want.
When (yp(a)) > 1, we consider two situations.
If len(x) o len(2). ). by typ(x) > 1, there must be an such that % E typ(z) and (2p * {rc). so we consider the (4i 2)-th weights of Mx) and Mi(z). By Lemmas C.I and C.4 for such an i E [21. there must be |V_10" len()) 101 (52,i,en((2) > LLa
If len(x) = len(=), let i E [T] satisfy 8,,1 * 82,1. Such must exist, because 8 = 82,4 implies that Y has the same position x and 2. Since it stands for any [T], there must be z 2. If va0* (s len(x)) * 1110% ($a,i, len()), then we have similar results before. If not, then we consider the (4i 1)-th weights of M((x) and Mi(2), which are Σi= (iv"""""e". (e....))) and (NTT)))
E;= f1 (s,,5))
Assume & is the maximum one in [n] satisfying V (8 k)) # V200 ()),ak).. Based on the definition of fi and Lemma C.2 we know that
Σラ= fi (s,,), Σラ= fi(V. ($2,11
(NTL)22-2 0.2 - (E k- (T 0.2)
j=u
= (NTL)28-2 28 (NTL) 2_1 -022 > 1.
NT12-1/
So we have
DE fr (V (82.1,5) len len(z)(NTL)2L
Σ fi (V210 (s2...))
len (NTL))))
L(NTL)2L*
The case of typ(2)= > 1 similar, so we obtain the result.
Part Five.
If typ(x)) typ(=) %. Proposition 4.3 shows that there must be F(x) F(z). Considering the conditions of the theorem, x and = have the same label, so let S = {(x, v) E S [typ(=) = =1] and S2 ((7, w:) 3(x m/) E S, typ(x) = 7:.. We just need transformer
memorize S2US/SI.
In this part, we use an FNN to obtain the result. By Lemma C.8 and Part Four, since 10T = O(L In L). there exists an FNN with depth ONN In? NTLL4]) and width (1)) which can classify M M((x) to y for all V)) S2 U S/S1. Hence, by Lemma B.2, we can use transformer with depth (O(NTL? In NTL/9]) and width (1) to simulate that FNN network. Adding all the above four parts, we can directly get the theorem.
C.4 Proof of Proposition 4.3
Proof. Assume that satisfies typ(x) = {re. To prove the proposition, we need only to show F(x) F(r) for any given transformer F.
Firstly, we will show that, in each hidden layer Fi of F, if the input of Fi ensures that each row is the same, then the output of J ensures that each row is the same.
We just need to prove for j 1; other layers are similar. Let V, be the embedding matrix of x and casily see that the input of the first hidden layer is V, whose rows the same.
29

---

Let the first layer be written as
=V.)) VV + E softmax(V,,, M)VK FNN(V,W, + -i softmax((V.Q M)V.V)).
In the attention layer, because each row of Vg is the same, we have softmax V2Q.KVN MVV, I Va where 1 is semimatrix under, and the i-th row is (1 J...... 7. 0,0,0 ..., 0) (the first weights of are i/1, others are 0). Then the first hidden layer is
-V -
Σ 4 Σ 4V.V).
By the definition of 4T, we have that LV22 = V. and by the definition of transformer, it is easy to that all other parameter matrices in the attention layer and FNN layer all right multiplied for Vz, which does the same transformation between all rows the Vg. Thus all rows of F (V+) are the same. Similar for the other layers.
To be convenient, let have hidden layers and F F(x) be the output the last hidden layer of F(x). By the above result, we know that the rows in the output of the first hidden layer are all the same; hence we can obtain the output of the second hidden layer all the same, and so forth. Finally, we have that the rows of F F()) are all the same. Hence, by Lemma B. the first row of F' F(x) is equal to the first row, which is also the only row, of F (74). So all the rows in the F (x) are equal to Fl (7:).
Now, we can prove the proposition. By the structure of the transformer, the output of the F(x) is linear transformation the same as Fl (ni), so (x) is also equal to the linear transformation on the F (7:), which is equal to F(7)). So we get the result.
the last row of Fxr). Because we have shown that each row of the F (xx is
D Proofs of results in Section 4.2
D.1 Proof of Theorem
First, we prove the sufficient condition.
Proof. The proof of the sufficient condition for Theorem 5.1 needs three parts.
Part One: In this part, we construct new set Sg as follows.
For each (x, y) S, we select an 2s E S. satisfying the following conditions to form set S.. = {x2 (x, y) E S}.
(c1) for any k, the z [len(x) + 1] are the same for all (x, y) S satisfying typ(z) {ry }. and
(c2) len(2) S 2.
By the conditions given in the theorem, (cl) must be satisfied. Based on the definition of Sz, = E Sz only affects the first T. symbols and the last symbol in z, and the subsequent symbols will not affect the overall satisfaction of the conditions the definition of Sy. So, 2 is longer than + 2, we just need remove the L + 2 to the penultimate symbols in z, and it is still in the S.. So, (c2) can be satisfied.
Part Two: Define new language.
First, we will use S., to define a new language Sn.
For any given (x. E and xz E Sr, we define 75- = xz [i] if and only if j S <len(zz) and
Then(a, To. Based on that, we define the sentence x² (x, tha 1en(z 7 and let it have the label vfr = T where & E (l)) len(x:))
Now we construct set Sn:
S. (1 )12 Seer k (len(z), len(z) + +,..... len(xz)]].
30

---

We make the following operation on Sn until it stops: If there exists ((xa)) 4/ (da)s), ((ra) Vi (())=) S, such that (xa) (rx) but yloaho + y ((s))a for some k and len(ra) < len(ss), then remove ((xa)² Uk ) from Sn.
Second, show that S, will be language. It suffices show that after doing such operation, we can ensure that for any (II, 31), (22, 32) E Sn. # y22 implies #1 + 22.
1,2 satisfy y1 K y/2 but = 22. the operation will not stop. To show that, we just need to prove that if (Ia)² = (xx) is valid but yk (aaa) * y/ (#s)s for some Ia + 24 and k, then there must be len(xa) * len()s). If not, we have Ja = ((n)pen(a..)) = (en)s))()))) = 2h where x1 = (z.) which contradiction with za + Tb.
We just need to show that, if (Ii, 3/5 E S,, where
Finally, we show S, a language that can be memorized by a tr-Coo--rrnssfommer.
To prove this, we need only to show that Sn satisfies the condition in Theorem 4.1 For any given i, if there exists a (ar uk ) E S,, such that typ(=5) = {7kh. by the definition of S., there must be
= -en(x). Hence, we have = = x. Then considering (c1) of the definition See, we have that these ufc are the same for any a satisfied typ(a*) = 7/- This result implies that S, satisfies the condition in Theorem 4.1
Moreover, since Sn contains most O(L[S)) samples and each sentence in it has length L such transformer has width OTT), depth O(NI,2 (NTLL)) /ql), and heads O(T).
Part Three: Prove the result.
Assume that F is a -rr-no--rrnn that can memorize S,,. We will show that F can memorize S as CoT-transformer, which can directly prove Theorem 4.4
Step One:
For any (x, E S satisfying the fact that any (4 vx: does not removed from Sn, where ks E we show that (x))(x)=
Because we do not remove any (x vl² from Sn (k E (len(x). ...., ())( from S,, there must be F(a+) yi and consider that sentence (a yk x= x+1 and Vieu(z)) = To. so the CoT of F when input x is (755*) (17 ==len(=)++1 and r = [ز] if and only if < len(z), and 2e 1en(x.)+1 = 70
[en[2=)+1
meaning stop. Then by the definition of 7 we know that the symbol before %o is y. so Feoe (x)(z) y. We get the result.
Step Two:
For any (1, S satisfying the fact that some (o vi) is removed from Sn, we show that Foot (a)xx)=) = y.
not, let (z., y) E S be the sentence of maximum length such that Foot(x) # y.
Let km be the minimum value such that (ar"" vee. has been removed from Sn. Then let (x1, v1) E S be the maximum length sentence such that (x1 km == Because (n vbn) has been removed from S,, so there exists at least one (No, vo) E S such that 2:-m = (fo) and len(2o) > len(x), so we have x1 * x and len(æ1) len(z). Now we will show that Foot (x1) Foor (x) and y Vı. so have Foor (x1) A V1, which is contradiction to the maximum of len(.:)
Firstly, we show that there must be y = y/. Considering that (I=)[en(zz)) = I1 and len(x1) > len(x). by the definition of Sz, we know that y = V1-
Secondly, by the minimum of kin similar to step one, we know that the first km lon lxn(x) step CoT of F when input is (Weem(a)> Vien 1en(z))1:....- Vk
(Nen(a))4>> Tee Nen(x)) k Con-
sidering that hm 2 len(x1) and (x1)² = a for any lo < km. so by the minimum of kin we know (21)
that the first km 1en(x1) step CoT of F when input æ1 is (M Men(z1)+1 V Fe n= (eem(e)))1 + Men((r))2
(m1)
31

---

It is easy to see that
(I, +en +en(a)+ Ni... = (01, - (en(=1)+2 T..)) which implies that a adding the first km - len(z) steps of CoT is equal to I1 adding the first km (Z1 steps CoT, according to the definition of Too-transformer, there must be (x1) = Foot(z).
Second, we prove the necessity of the condition.
Proof. We will show that if the conditions are not satisfied, then such a language cannot be memorized by any CoT-transformer.
Part One.
Firstly, show that when S for some (z, v) S, S cannot be memorized by any CoT- transformer.
If not, let S be memorized by a CoT-transformer F. Then we can obtain CoT for such and write the CoT as (I, Nh : V/ 70)-
Then we prove that (z, Taa Pa.....9.. ,,,, 3) E Sz, which is in contradiction to S = á and thus prove the result.
We just need to verify that (1), (2), (3) the definition of S, are correct.
First, it easy to see that (1) in the definition of Sg is correct.
For (2), if (2) is not correct, then [Lyp(ær 71
By Proposition 4.3 we know that
The so Vio Thp y 74 F((z, Mii ......., Ti.))
Similar any The where h [n]. So we have F((x, Ni M...... ., :h, To. but based on the defi- nition of 7o. there must be 70 + y, which contradictory.
F((x,, Yv,
F(x)
For (3), if for some (1) S such that x1 = (x. Ve. Y2...... Ti..) for some m 2 1, then by the definition of CoT-transformer, we have F(x1) = F(z), so there must be yı y. So prove the result.
Part two.
We show that if (f (x.g))Sttyp()==
Φ for some 7 I which satisfies ((r,y) E S typ(x) {txF} * o, Then S cannot be memorized by CoT-transformer.
By Proposition 4.3 know that for any sentences (I1, 91), (I2, V22 S such that typ(x1) typ(#2) {Tr the output of F(x)) ) and F(x2) are the same, which implies that if S can be memorized by a Coo-transformerr the first symbol in CoT is the same for F when input 21 or 22- Considering the arbitrariness of and Ø2, the above result implies that (tn))))Sttpaa)=((aa)) so we can obtain the result.
0.
D.2 Proof of Proposition 4.5
Proof. We first prove (1) in the proposition. We show that if the set of the last elements of all sentences in S is proper subset of r, that is, {=<[en(<x)] (x,w) E 8) S Г, then S satisfies the conditions in Theorem
Part 1.1. We need simple result: Let 7 S/(x[ee((z]] (z, y) E S). and x(L) (7t, 7hs 7s) be a sentence with length and all symbols in it are %.- Then for any (x, v) and I+ there must be x2 = (z, (LL) 2, 3) Sz-
To prove the above result, we just need verify the three conditions in the definition of S..
Condition (1) in the definition of Sy is clearly valid.
For condition (2) in the definition of Sr. because & [x]]en(x)] : (x. v) E S). so (xz (x=)(ee(()++1) > 1.
For condition (3) in the definition of Sg. If (en( > len(x), considering that len( $ L, the last symbol in (xx) (en(r)) is 24 which must not be the last symbol in æ1. So (x=) # for any len(z;) len(x), implying condition (3).
32

---

Part 1.2. Now we can prove (1) in the proposition. We just need to verify the conditions in Theorem
Firstly, by the result in Part 1.1, we know that Sx * Φ for any (r,y) y) E S.
Secondly, for any yy such that {(x, y) E 8 typ((z) = mr * 0, we have 7/ E {=|len(z)] (2, v) 8), so j # where i is defined in Part 1.1. Then we know that E (a S by Part 1.1. This proves (1).
We now prove (2) in the proposition. We show that if len(x) = for all (r, y) E S, then S satisfies the conditions in Theorem 4.4
Part 2.1. We need a simple result: for any ().y) E S, if 74 + =[len(x)), then for any E r+ there must be 2 (I, Yss 2, 3) Sz. In fact, by definition of Sz, this is obvious.
Part 2.2. Now we can prove (2) in the proposition. We just need verify the conditions in Theorem 4.4
Firstly, by the result in Part 2.1, we know that S₂ + ø for any (a, v) S.
Secondly, for any " such that ((x, typ((()) = }5} + 0, we just need take * j. then we know that 7/ (1.:))e S2 by Part 2.1. This proves (2).
E Proofs of results in Section 4.3
E.1 Proof for Proposition 4.7
We just need to verify the conditions Theorems 4.1 and 4.4 for language T.CP.
Proof. It is easy to see that (2) and (3) in Proposition 4.7 can directly lead to (1), so we just need to prove (2) and (3) Proposition 4.7
For no- Cor-aaassssorr
For LCP=1 we consider the sentence .;, n..... ?1) where len(x;) = i. It is easy to see that F; and 2++1 have different labels by the definition of LCP, but typ(æ;) typ(#++1) fn}
ns
So LCP does not satisfy the conditions in Theorem 4. and cannot be memorized by no-CoT- transformers.
For ICPP?1 It is easy that (x,y) v) LCP>1 implies [typ(=) > 2, LCP>1 satisfies the conditions in Theorem 4.1 and can be memorized by ro-CoT-transtormers.
For CoT-trasfformer
For LCP and (x.y) LCP= let typ(x) = 7/- for any 7/ # Yz and Foot r+t So LCP satisfies the conditions in Theorem 4.4 and can be memorized by CoT-transformers.
easy to check that (z, Yss Teots 8) Sz
n For LCP>1 and (x, y) E LCP>1 n such that len(x) < n. If x, = (a, Yi Teots 8) Sp for some
7i E I' and Toot E e+, then by the fact ((x, w1), LCP,. we have (I=) [en[)]]+1 = (zz, 75) but
y1 # y, which is contradictory with the definition of Sz. So LCP?1 does not satisfy the conditions in Theorem 4.4 and cannot be memorized by the Cor-transformmr.
E.2 Proof of Proposition 4.8
This proof also follows the proof of Theorem 4.1
Proof. The proof has five parts. And we still define 8,, as that the proof Theorem 4.1
Part One: The Embedding.
We will embed in the following way:
The basic symbols 7, will embed in ...,, 14,00 0) E {0, 1 Hlog 47 where of = (0,0,1,1)
when j * i, and of (0, 0,
33

---

The position embedding for n-th position is (O.0......0 n2)) E {0, 10.1]-7-: - Togg 1., where n2 E {0, 13 [og, 4] is the binary representation of n, such as when n = 11, the n2 = O..0..... 0, 0, 1). Hence, the input sentence satisfying len(x) will be embedded in vector Va {0, 1)mx(47+ [log, I.)).
Parts Two, Three, Four.
In these three parts, we perform the operation on the first 47 columns V. the same way as that in the proof of Theorem 4.1 keeping the value of the last [log2 L] columns unchanged throughout these parts.
Similar to that in Part Four of the proof of Theorem 4.1 we show that for any (zz, M2), , (z, U2), can
obtain a different vector for a and 2.
If x and do not satisfy typ(x) typ(2) = {rr } for some I columns and follow the proof part four in the proof of Theorem
[T] then we consider the first 47'
æ and z satisfy typ(x) = typ(=) { for some E [T), then there must be len(x) o len( so consider the last [log2 I. -t columns. Based on the definition of the position embedding, know that the [log2 L| columns in the last row of the embedding matrix of x and are different, and the Loe norm of the difference between them is at least Since the last [log, L7-th columns unchanged throughout these parts, we obtain the result.
Part Five.
Quite similar Part Five in the proof of Theorem 4.1
E.3
Proof for Proposition 4.10
Proof. We will show that, if [typ(z)) > for any (x.y) S and the conditions in Theorem 4.4 are not satisfied, then such language cannot be memorized by any CoT-transformer with position encoding.
Because [typ(z) > for any (a, y) E S, we need only to show that if S, = Φ for some (x, v) E S, then S cannot be memorized by any CoT-transformer with position encoding.
not, assume that can be memorized by a CoT-transformer with position encoding. Then we can obtain CoT for such x, written as (I, Thi Thg. Yo, M/ 70).
Then we prove that (x, N , v) E Sg, which contradiction to Sg o, and establish the result.
We just need to verify (1), (2), (3) in the definition of Sz are true.
First, it easy to see that (1) the definition of S. true.
For (2), because [typ(=)) > 1, it obviously stands.
For (3), for some (x1,21) E S such that = (xt, Tha Ma..... Timn for some 2 > 1, even with position encoding, we have F(z1) F((x, Yhp Par... Y... Therefore, by the definition of
trr-fraasformer we have F(x1) F(x). Thus, there must be So we prove the result. O
Proofs of results in Section
F.1 Proof for Theorem 5.1
Proof. Let L, [logr- +1 Then T 2 N, since N,T 3. Therefore, [log, +1+1+ N. We can arbitrarily select the N sentences with length LN. By Corollary 4.2 and Proposition 4.5 know that the language composed these sentences with arbitrary labels must meet the conditions of Theorem 4.1 and Theorem 4.4. It is easy to that, for these N sentences, there exist N different situations to assign labels to them. Hence, N different languages can be created by these N sentences. We will show that at least of these languages requires no-CoT CoT-transformer (CoT-trane (oT-transformer) with least N In parameters to memorize it, which is what want.
6g
34

---

It is easy to see that for transformer with no more than P parameters, its width, head, and depth are all smaller than P. Therefore, for any T 2 there exist at most p8 pairs of W, D, such that para(W, D, H, ? < P. Hence, for any W, D, H such that para(W, W D, H, T) S P. considering that each parameter has precision q. we have that each parameter has most 1024 different choices. So, there exist at most (1024)P different transformers in H W.D.H H (or H W.D.H. H,oto for CoT transformer). So, there exist most (1022)) P situations for no-CoT transformer (or CoT transformer) with P parameters and precision
So to memorize all these TN languages created by such N sentences, least T. different trans- formers are required. So, if each of these languages can be memorized by no-Coo--ransformme (CoT-transformer) with more than / parameters, there must be T S (1022))) which implies N In < 3ln P + 2q 10 S P (g 2 3 is used here). The theorem is proved.
E.2 Proof of Proposition 5.3
F2211 Proof of Proposition 5.3 for no-CoT transtormers
In this section, we provide the proof of Proposition 5.3 for no-CoT transformers. We present an easy lemma first.
Lemma F.1. If {as] [b: C RR,, satisfy that:
for any + j. we have la; - a5l 2 1, lb; - byl 2 and
for any i, E [n]. we have lb: a,l 2 when a₁ o bj-
Then holds
ET co
2i o
nh eat)
Proof. Just need to prove that D"
e Ei=1 dh 1. Without loss of generality, let a; a;+1
and b; 2 bi+1. Assume & E [m] is the minimum such that ak + bb, and let ag > bg. Then we have
that: Ei=1 Eh E e 2 eav Em= e² 2 eak -o-n+k+1e"= e-1
aa 1/(e 1))
e - e/(e - 1) > 1, which is what we want.
We now prove Proposition 5.3 for no-CoT transformers.
Proof. We follow the proof of Theorem 4.1 And we still define sn,i as that in the proof of Theorem
Part One: Embedding
This is the same as Part One in the proof of Theorem
Part Two: Use the three layers to calculate the position value.
This is the same Part two in the proof of Theorem 4.1 But because there exists no precision limitation for the transformer, we just need three layers.
Part Three
Define the set V, [V.10' (su,s, (s..s:))) where j E [L] and V Uj Let A E R. satisfy |Ar Azl > 1 for any x, V.
In this proof, we define matrix M2(x)) which has the same size M2(x) as: the (4i -4i 3) column of M3 is A(M2 (()))x)) where (M2(z)) is the (4i - 2)-th column of M2 (x); other columns are the same as M2(x). is easy see that a hidden layer with width O(1) is enough calculate Ms(x) by M2)x).
Next,
FNN fi R R to map 0 and 1, but other values in V to 0. It is easy to that such a network fi need only the O(1) layers and O(1) width.
Based on such FNN /1 and Ma(x), we define matrix Ma(x:) which has the same size Ma( as: the (4i 1) column of Ma(a) is fi ((M2)4:-2) where (Mz)4t-2 is the (4i 2)-th column of M3(x);; other columns are the same Mz(z).
35

---

Then by Lemma B.2 we can use transformer with width (11) and depth O(1) to obtain Ma(x) by M3(x).
Part Four.
In this part, we use two hidden layers obtain vector by M4 which is different from
In this layer, this attention layer has T" heads, and the i-th head, Qi g4Tx44" and the (4i, 4i 3)- th weight of Q: is 1, and others are O; K; = I and V2 E {0, 1] 42 x4T and the (4i - 1, 4i - 1) weights of V2 are 1 and others are
The residual layer uses E {0. 1 1347x4T which is defined as: for E [T], (4i - 2, 4i 2)-th weights of W is 1, others are O. The FNN layer is O.
Let the last row for the output of this layer M(x) when input x with length n to the transformer, then based on the definition of Ma(x), we have that:
(I) The (4i 2) weight of M((x) is Va2" (82,2,
(2) The (4i - 1)-th weight of Mi(x) is En evva (00, FV(20 (#za
Ej=n (25,55)
We will prove that for (x. (z, U2) E that do not satisfy typ(x) = typ(z) 71 for some 1 E (7), we have [[M(2) M1 0.
When typ(2) typ(z), the proof is similar to the proof of Theorem 4.1
When (x)(2) L (=) and typ(x) > 2. the proof is similar to the proof of Theorem
When len(x)) (en(2) and typ(z) > 2, let E [T] satisfy Sx,i + Sz,i. V (Sr,s, (s,,,.e((x)) * V-10" (s2.i, len (2)), then we have the same result as before; if not, by Lemma
C.2 we know that
there exist the same number of or O in (V-10' ()) the definition of f1, we know that
len(s) and (V10" (82,5. (aa: len(s)
(e) Based on
n
Σ
ava (#na))) fi (8r,))
AV (#2 fi (Va2"" (82,11)) # 0.
Hence, based on Lemmas F.1 and
C,2 and considering the definition of A, we know that 0, we prove the result.
E A0 (#2,512)
Σ
AV
Part Five. Quite similar to Part Five in the proof of Theorem 4.1 But because there exists no precision limit the transformer, we just need O(N) layers shown in Lemma C.8
F.2.2 Proof of Proposition 5.3 for CoT transformers
In this section, we give the proof of Proposition 5.3 for CoT transformers.
Proof. The proof is based the proof of Theorem 4.4 Part One.
We need only to change the definition of S..-
For each (z, y) S, put an x. Sp satisfying the following conditions into set Sns {x= (x, y) E S}:
(c1) for any k, the symbols æ (len(x) + 1] are the same for all (x, y) E S such that typ(x) = {7k};
(c2) len(x=)) læ)) & N 1
We just need to consider (c2).
For (I, y) E S such that [typ(x)) > 1. Let E Sz and len(x.) be the minimum. If len(xz) len(x) > N, then there exists len(x)) I < len(z) such that there exists no (2,82) S such that ys * and (en(2) =
So consider a sentence x; ((x=)p-1j. 1|. v). It is easy to check that 2, S, and len(x;) < len(x.) which are contradictory to the minimum of (en())). So len(æz) len(x) < N.
36

---

For a (I,z) E S such that typ(z)
{x}.
By the condition of Theorem 4.4 let Y
Then we let 23 E S satisfy that v; Ien (z) + 1| = "3 and len(x=) be the minimum. Similar to the above, we can show that len(x;) (len (z) + +1) - N. So we get the result.
Parts two and three. These two parts similar to the proof of Theorem [4.4 Considering that the S, constructed by S.. defined in Part One has at most ((N2) samples in it, and using the result in we prove the result.
Section R 12.1
E3 Proof of Theorem 5.4
F3.1 Proof of Theorem 5.4 for no-Cor-transformmrs
Firstly, we define the following language.
Let I'= = {u1, 72) and S, be a sub-language of LCP with 2 samples (1). v5) where E {1, in it. We define that æt is a sentence with length i 1, and the i-th element of æf is 72, the other elements are Y/; the zá only contains 1/1 with length i; the labels are decided by LCP.
Now we can prove Theorem 5.4 for CoT--rrassfoomerr we show that for any q and P. there exists an such that S; cannot be memorized by any transformer in H.P...
Proof. Assuming that for a pair of P, q, each i Z,, Sz can be memorized by non-CoT transformer in H'. P.p,p, we can derive contradictions.
First, let F(x); be the i-th weight of F(x), then let mingent,ee. [I(F()) = F(m))))+(((()) F(m)2)l Following the proof of Theorem 5.1 we know that there exist finite varieties of different transformers H P.P.P. so O.
If S, is memorized by F E H.pp. i Z4, so [((b)) F (())22 [F(n) F(1)22 2
P.P.P. then by Proposition 4.3 we have F(xb) = F(m) for any
We will prove that for any given transformer E H.p.p it holds -(z))) when i + DC.
If [[{())) F( - when i - 00 for any given F E Hypp.p- then because there exist finite varieties of different transformers in Hy there exists an satisfying that ( [[((x))
<
e/3 for any F H,p,,, which implies
F(zi)1- F(zi)2 2F(z5)1 -(a)) 2((z)) 2(x6)2-244
F(zi)a))
Since 1 2 any F H.P., will give the same label of 2 and Zzz. Considering that zi and æ have different lengths, by the definition of L.CP language, they have different labels. This is contradictory to the assumption and directly gets the result we want.
Similarly, it holds F(z)) - 2</32
To show that, we need three parts, assume F is transformer in H2, Let 1| be the maximum Ln norm of the row in matrix.
Part One: For any j, the j-th hidden layer F,y J., the first rows of Fy(x1) and (abh) are equal to that j-th hidden layer in F(1)).
This can be proved by using Lemma B. and Proposition
Part Two: For any i.j and x E S,, in the j-th hidden layer F, of F, (FF( S MP...r where Mp.. is value that does not rely on i but only depends P.q.j.
the j-th hidden layer, if the input = of the j-th hidden layer, which is also the output of the (i (i-1) 1) hidden layer, satisfies that each row has the L, norm not more than A, then we can show that the output norm of the j-th hidden layer also depends only on and P, q. To show that, we just need to consider the attention layer, FNN and the residual layer respectively.
37

---

In the attention layer (TT(2) = E softmax(2Q, + M)2K, since the L1 norm of each row + .) is 1, and we limited the precision of the transformer, it holds that each parameter in K; is not more than 10". So we can show that each row of (TT(²) will have a L1 norm no more than P(A x p2 x 109).
of softmax (oftmaxx==Q;V6
Upon the residual layer zue similar to before, each row has a Lı norm of not more than A p x 10", In the FNN layer FNN + Az)( each row of + (=)(=) goes through two transformer matrices, so the L norm of each row has at most 109)) - ATT (T)())) |1-1 means the maximum |||=
L1 norm of the row in a matrix.
Adding them, the L1 norm for each row of the output of the j-th hidden layer is at most P2)3 A).
If we take A = Mr...j11, then we know that Mr.g S O(P M Considering that the input of the first hidden layer is only bound by P and q, we have the result.
Part Three: For any j, in the j-th hidden layer F F, (x))) - F (xb))sll - 0 when i - xc. This directly leads to our result.
To be convenient, we write Fi as f(i and k-row of f(*, *, *). And let
and az as f(j.2, and (*,,,, means the f(- = 1,
For convenience,
define the input of the first hidden layer as the output of the 0-th hidden layer (i.e.. = 0) here. Consider that for any E Zt. the i ++1 row of x and the row of x? are the same, so (7, i) 0 for the first hidden layer. We will prove that, if mn( 1, satisfies nij 1, 0 when i + oo, then n7j, i) also tends to 0 when i + 20.
Note that 1, can be calculated as: f(j 1,,, j-1 + ATT(GG - 1, + FNN(J(i 1, 1,, + ATT(J(i - 1,),
- 109 12 1, 1) 10 n(j 1. 1).. Based on the assumption of n 1,, when oc, it holds [[( [j- - - 1,2, w-1ll - O.
Firstly, for the residual layer, we have (-11
1, 1) (
Secondly, by part one and Proposition 4.3 the first i - 1 rows of f(j 1, i. and all rows
of 8/i - 1, are the same as FJ-1 m voftmax(XQVX]]
So in a head of attention layer in Fj. written as
we have that:
(softmax
+ M)S( 1,0))4
1)- (- ((-1122)) ('G0-111)
4-- te"
4e"
where 8 -
p - 1-, ( 11-1,1,1))
Considering that (softmax L,
1, (22 1,2,), let - -ssotmmax f(j 1, f(j 1,2, }f - 1,2, + (softmaax L1
1,1, 1, 1, 11 = c(i). have that:
c(i)
(1-)) Te- +e"
"f00-11))
te + "e- (ffL-111
(
- f
to + ((-..))))))))
te
Consider that the transformer has precision and part two, so we have ( Gi-lje+te te" 2e M 2 121020
te
2e M4 9 221020 +(1-1)e My M3 P2i02y similar to te and (f- te tex Hence, by p
part two, we have that [|c(1)] S O(Mr.5-1 pi Pan 14-11 Po10 ), which tends
to 0 when i + xc And for the whole attention layer with P heads and matrix K, we have (fTT(f() - 1,1, - (ATT(() - 1,), & 10d () which is a value that tends to when co.
Finally, about the FNN layer, similar to Part two, for any given two vectors oi and 22, we have that FNN(21) FNN(22) < 0((10p?))11 xalli). Consider that we have proved that (
38

---

and
0
when i + so holds
2, --+
(.),) (ATT(( (ATT(F( 0 when 00.
Adding the results of such three parts in the j-th hidden layer, we can obtain the result.
E.3.2 Proof of Theorem 5.4 for CoT-transformerss
For the CoT-transformer, we consider the following example.
Let = (n, f2, Ya. ) and S sub-language of LCP with 10 samples (at, v/) where j E [10] in it. We define that:
(I) zf is sentence with length i and all elements in zf are Y15
(2) m (j = 2,3,44 is sentence of length i + 1 and the first elements of æf are n, the last one is 75-1:
(3) my (j (j= 5, 6, 7) is sentence of length i + 2 and the first i elements of æf are n. the (i + 1) 1 element 7/4. and the last Y--3i
(4) x4) (j 8, 10) is sentence with length i + 3 and the first elements of 2 are ni the (i + 1)-th element 744 the (i + 2)-th element ?/, and the last one is (71, 72, 74), respectively.
Their labels are decided by LCP. Then we can prove Theorem 5.4 for CoT-transformers, We show that for any q and P. there exists an i such that Sy cannot be memorized by any transformer in H H.P.P.
Proof. Assume that for pair of P, such that any i E Z4, Sy can be memorized by F E H7, P.P. P.o. we can derive contradictions.
Firstly, if S can be memorized by an F E H. P.P.P.. we can show that the CoT created by F(xi)
(74, Yi, ...... for any i e E..
Let the first symbol of the CoT created by F(x1) be 7ý. If E [3], then it holds (#1, 7s) ++ which implies F((a), = +1) so that F will give the same label to x and 2)+1 Because of and 1 have different lengths, based on the definition of LCP, they must have different labels. This is contradictory to F memorizes Sy. So. we have proved that the first symbol of CoT created by F(x1) not 71, 72. Ys. Thus, the first symbol of the CoT created by F(x)) т4. For the second and third symbols in CoT, in similar way, we can show that the CoT created by F(x{) is (74,7) 71, .3.
Secondly, by the definition of CoT-transformers and such CoT, we know that F(xt) = 74 and F((a), 74, 11)) 73- Moreover, because æf sentence with length and all elements in of are 71. so by the Proposition 4.3 we have (((1f.7)) f(x+) 74, which implies F can memorize (((a), m)) ((x), 74, 71), r3)} as no-Coo--ransffommer.
Therefore, based on the assumption, we can deduce that for any i, the language [((=), m1), 74), ((=), 74, 71), r3)} can be memorized by a F E H H.po So, similar the proof of no-CooT-ransformers, we prove the result.
F4 Proof of Corollary 6.1
Let S, be defined as in Section F.3. and S. = Ulez, Szi c LCP. Let Sy be defined as in Section R33 and S. = Usez St C LCP. is easy to check that Sa(S)) satisfies the conditions in Theorem
Proof. 1. For Co-Coo-transformer. If a no-Col no-CoT-trann CoT-transformer F can memorize S,, then we can prove that the result within two parts, which is similar to the proof of Theorem 5.4
Part One: For any 23 E Sa, there exists an 0 such that {F(=2)); - F(x )² 2 6 for any
i Z...
39

---

for any E Z+. If F(1)1 F(21)2 then JF cannot memorize 2²2 which is a contradiction with F can memorize S.. So there exists an F(1)2 (F(2)) - = >a for any i E Z_
By Lemma 4.3
F(z2); F(
F(1)2) -
6 E ER_ such that 6 = [F(1))
Part Two:
We have ) =(=2))) - when xc, which leads to result. Consider that the value of parameters in JF has an upper bound and a lower bound, so the proof of this part is similar that in the proof of Theorem 5.44 and we omit
CoT-transformer F can memorize Sy, similar to that in the proof of Theorem 5.44 for any z S%, know that the CoT created by F(xf") is (74, (74.7, (.....) for any d E Z,. which implies that F can memorize {((xf) 12,, Ya),, ((z 7/1 71) 71))88) for any i E 2+ as no no-Cooo CoT-transfommer. So, similar to before, we can obtain the result.
For CoT-transformer.
F,5 Proof of Proposition 6.3
By Theorems 4.1 and (1) in the proposition is apparent. So, we just need find a sentence in Arith, such that no CoT- or CoT-transformers can solve it with confidence c.
Note that for Arith,,. % i when i [p]. 7/+-1 is the symbol
F5.11 Proof of Proposition 6.3 for no-CoT transformers
Proof. Let C₁ be the sentence +++++++.. + I' Arith where there exist i Is it. is easy to see that C, has label i mod p. We will show that, for any no-CoT-transformrr Fcnnoo memorize some of these sentences with confidence c.
cannot
Let F be no-CoT-transforme and F be the (-th hidden layer of F.
Firstly, we show that there exists vector C such that [[F(C;) ClI2 - 0 when cc.
Assume that the output of jk when input C2 to the transformer can be written as (1), and (1)
means the j-th row of ( (i).
Assume that jk can be written as
H
F())) = rw
Σ
Softmax(2Q M)rK
1=1
FNN *
Softmax(xQ MarK))
We first consider Fl. Let be the embedding vector of symbol + and let be the em- bedding vector of symbol 1. We have that: ( = 4 + Σ/ e'Jeyte'sen KJ FNN(U+ + E/= 6014460' K!), where 8, 2 Q.V. VI and = u4 V3V, of. And we have 6'44''
e'
(e +ee Kj), where (1) = wil + Σ/n (1-1)e te K, + FNN( + Ejn (1-1)=
= 8) = V of. and t2 = VIQ.
is easy to see that 21) does not depend on i, and (1) satisfies (1) - Viw-
Σ te etel
K. + FNN( E beete
K!) when + oo.
By the above result, we can see that the last two rows of 7 (t) converge to a vector separately when i + xo. Then we will show that if (x) and ( (i) satisfy that converge to a vector separately when i + co, it also stands for ( and (i).
2 2 200)
For Fk. we have that: (1) k-1 (1) Σ/
KB + FNN(
H Σ 2260 1() K3), where (0))))))))
1==1
ΣdL2 2 .60)
40

---

We will show that (1)) will converge to a vector, similar for ( so we can prove our conclusion.
Firstly, without loss of generality, assume that lim; 1k-1 2 = veo1 and lim; 22 1 (2) = vec2.
Secondly, by Lemma
B.1
we have (1)
(1=2)) when i 2 12221
- (4)
Σ 2p=l - K and s²())
so
20 プE (1)) -
ebt0
KJ
Σp=r (866)
Note that 22p = 12 (0, (1+1))) tends of veri Q2 V (vec))
) when p, and 22 12 (0)), (1 (p + 1))² tends to tl = Q, V (vecy)) when i, + co. Using
12
Lemma F2, we have that lim4-+00 2 bong 1(12)1))
A Avee te'ee So lim 2
oti +o'd
vec1 th
Eド H
veve
K3 + FNN(vcC1 whth + Ej=1 4000
H
ell ellver tevere KG), and get the R.40%
result.
Finally, considering that the output of the transformer is only dependent on the the last row in the last hidden layer (i.e. 1 (i) when input C2 to the transformer), which has limitation when co. So, we know that F(C,) has a limitation when i + co.
Secondly, we prove the result.
Let Cīk] be the k-th weight of C. Then if C(k] > C(j) for some k,j [p], then by the above result F(C;) + C' when + 0o, there exists an in such that for any i> io. it holds (F(C:)) > (F(C:)) io. Then have that F will not give C₁ the
We take i such that å1 mod p j and correct label j. because (F(Ci, )) > (F(Ci, ))j. which implies F cannot memorize the Arith
If Clu C(2] C[3] ... C[P], then there exists ig such that when i 20, have (F(CC)) - C(] < c/2, which implics that (F(())) (F(C)))) < c for any i > ip and # j. so JF cannot memorize Arithp,n with confidence
The above proof needs the following lemma.
Lemma F.2. If sequence of positive real numbers {x;} satisfies that limp-400 22p = a > and
limp-+2 72p-1 b > 0, and sequence of vectors {21} satisfies that limp-roo 22p Ve and
Σ/= zyzt (ave boa)/(a b).
limp-+20 22p+1 va. then lim
E,=1
Proof. Assume that i(e) satisfies that y > i(e). then 12p v2p-al < 122p41-10 -I| < 1192p - volla <e and V2p+1 Valla <
ilte)
Ei 2yy;
Then we have that:
M(c) 1540 _ 2g
Firstly, easy to see that for any given e, when p - co, we have
0, because
b > O, and Ep Bj ET my
I also because the a, b > 0.
Σ Einee 3391
Secondly, we show that can directly prove our result.
- (ave bua)/(a+ b) when c c- and p - i(c) + oo, which
We consider the Σj=ue #5M5 Ej=ne 2,
E 20 Tj
E Eo Ty
at first. We have that:
E)=00) 21
Σ Eymee 2y
41

---

>> (mste) Billi
Th
Nd "=>)=)(()) 2=1 43
112
2n (())( "i
Li 3, (1,
10 my (y m()
E 2i 2,et -11
2z-(()
c.
> 21 8y3; So
Ve E3
#1
ve 25 2i when - 0.
))=(() oi
2)=1()) 3j
E H0-12-00
Hence, we show that we have
when + 0 and p i(c) - oc.
Σz-(() By
Li-ne "j ([(a-c)-(((b-)) where vf is the number even (odd) in [((e).). pl. is easy to see that when e + and i(E) + co, we have (e (f(a))
Because vf(a-)) ((att))t
of(a+))
a/(a + b) and [((0-))t + a/(a + b). By the squeeze theorem, we get the result.
(a+e)
Similarly, Ei "y
when c - and p i(c) - oc.
E) o+b
Combining the above results, have
Σ ) 3335
11m--0,p-if
000
Σ (=)()) 4
Σ 100
lim, (()
Ljm((e) 22
Σj
a+b
So we get the result.
F.5.2 Proof of Proposition 6.3 for CoT-fransformers
j Arith, where there exist i Is in it and j [p]. It is easy to see that, C² has label (i+j) mod p. We will show that, for any Cor-trasforrmer
Proof. Let C/ be the sentence 1 1+t
F.F cannot give some of such sentences correct CoT with confidence
Assume that a CoT-transformer and can solve the Arith, with confidence e.
First, similar to the above subsection, we know that for such transformers F and j, when -> oc, holds F(C)) - C()) for a vector C(j).
So. if F can solve Arith, with confidence c, there must be (C()) + 1] > (C())[ for any t + ++p+1. (CG))l++1
(CG))[ for some + pp+ + 1, then the symbol will not appear at the start of the CoT with confidence e for the F(C)).
Second, consider the CoT of F(Ci), where C is defined in Section F.5.1
From the definition of transformers, we know that if F can solve Arith,. then F(C;) must output at the beginning of COT. Now we consider the output of F((C,, =)) Similarly to the preceding subsection, we know that there exists a vector such that F((C,,=)) + C' when 0o.
Because F can solve Arith, with confidence c, so as to meet the basic expression of the four arithmetic operations, the symbol =' must be followed by number [p]. so know there exists t E (p) such that C(t) > Clj] when j * 1 and j E [p 7]. If not, similar to the above section, we can show that F cannot get the correct CoT for C. with confidence c, which contradicts the assumption.
Then there exists é such that when ė in. F((C,, =)) =
Third, we consider F(C!) and F((C,, :)). These are two sequences whose lengths are the same, which only differ at the penultimate symbols, one being + and the other one being =. Then, because the parameters of F have the upper bound and lower bound, similar to that shown in Section F.3 there must be |[F(() F((C,, t))ll 0 when i + oo. In part one, we showed that when
42

---

- oc, we have (F(C)) > for any j * + 1. So by the above results, there must be (t))
== for any * p + when i oc, which implies that =((C;,,(1) will output the symbol = and create CoT (=,4, for C₁.
Now know that the CoT of C2 must have the form (=,4, --,....... when cc. If satisfies that i mod & t. then it is not a correct CoT to solve C₁ which is a contradiction to the fact that F can solve Arithp. So we prove the result.
G Impact Statement
We have theoretically demonstrated the power of CoT in the memorization capabilities of transformers. Our research does include conclusions that have negative effects on the community.
43


Reviews:
[{"review_id": "a5reVHXHuP", "reviewer": "Reviewer_ueXx", "summary": "CoT-enabled and standard fixed-precision autoregressive Transformers are formally compared, treating CoT as a scratch-pad workspace added at inference time.\nBoth models memorize any finite dataset with N parameters, though each obeys distinct necessary conditions; CoT does not lower the parameter count required for memorization.\nThus CoT alters which languages can be memorized but leaves raw memorization capacity unchanged, implying its gains come from reasoning structure rather than extra memory.", "questions": "Q1. Could you report empirical results on real LLMs to confirm the theoretical predictions?\n\nQ2. 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?\n\nQ3. 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?\nGiven that Chain-of-Thought is primarily a reasoning aid, not a storage mechanism, the motivation for analysing its memorisation capacity feels under-justified.\n\nQ4. 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.\nCould 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?", "limitations": "Since no empirical experiments validate the theoretical results on real LLMs, their practical reliability remains untested.\nThe work considers only whether data can be memorized, ignoring CoT’s core strengths—algorithmic reasoning difficulty and accuracy.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Gives exact necessary and sufficient conditions for memorization with and without CoT.\n2. Proves tight N parameter bounds, showing CoT does not cut model size.\n3. Identifies finite languages each model can memorize exclusively, clarifying expressive differences.\n\nWeaknesses\n1. Limits analysis to single-token labels, leaving sequence outputs unaddressed.\n2. Omits positional encodings and LayerNorm, diverging from real-world Transformers.\n3. Provides no empirical experiments, so theoretical claims are not validated in practice.", "was_revised": true, "final_justification": "Since the authors addresses my concerns, I raise d the score.", "rebuttal": "We appreciate the reviewer's comments. We think that we have addressed the questions and concerns clearly.\n\n**W1. Limits analysis to single-token labels, leaving sequence outputs unaddressed.**\n\n**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.\n\n**W2. Omits positional encodings and LayerNorm, diverging from real-world Transformers.**\n\n**Answer:** You are correct on this. However, please note the following aspects:\n1. 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.\n2. 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.\n3. Partial reasons why we do not consider positional encodings were given Remark3.3（Line 117）.\n\n**W3. Provides no empirical experiments, so theoretical claims are not validated in practice.\nand\nQ1. Could you report empirical results on real LLMs to confirm the theoretical predictions?**\n\n**Answer:**\n\n1. We note that “learning theory” is a topic in the CFP and this paper belongs to this topic.\n\n2. 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.\n\n3. Due to time constraints, we cannot report experiment results.\n\n**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?**\n\n**Answer:**\n\n1. 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).\n2. 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; \n\n\n\n**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.**\n\n**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. \n\n1. 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.\nWe 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.\nMore 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.\n2. 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. \n3. 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.\n \n**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?\nSame 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.**\n\n**Answer:** We continue our answers from Q3. \n\n4. “your study focuses solely on whether finite datasets”. \n\nActually, 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.\n\n5. “core advantages of CoT: algorithmic reasoning difficulty and accuracy”. \n\nFirst, 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).\nFor 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.\n\n6. “translate into meaningful gains” and practical implications.\n\nWe 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."}, {"review_id": "PL2MEHgPjV", "reviewer": "Reviewer_ZKA9", "summary": "This paper investigates the expressiveness of transformers without positional encoding, both with and without chain-of-thought (COT). It establishes a simplified theoretical framework, derives necessary and sufficient conditions for the languages expressible by these models, and compares their expressive power, illustrated through the LCP problem. Additionally, it provides bounds on parameter size estimates for valid languages. While the problem is of significant interest to the community, the paper is difficult to follow due to unclear notations and insufficient intuitive explanations of theorems.", "questions": "Major Problems:\n1. 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 κ?\n2. 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?\n3. 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))?\n4. What mechanism allows a COT transformer to leverage input information beyond typ(x)?\n\nMinor Problems:\n1. The notation 2^κ, where κ is a set, is confusing. A more conventional notation would be κ^k, representing a length-k array with elements from κ.\n2. What is the relationship between embedding dimension d and width W in Section 3?\n\nThese questions are adequately addressed by the authors in the responses.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper addresses a compelling problem and provides theoretical insights into the expressiveness of transformers with and without COT. The analysis of expressive power differences and the application to the LCP problem are notable strengths. However, the paper suffers from insufficient explanations. Theorems lack intuitive interpretations, and key concepts are not adequately clarified, hindering readability.", "was_revised": true, "final_justification": "My technical concerns have been adequately addressed. However, despite the authors' explanations, I still find the presentation overly abstract, lacking intuitive explanations or high-level proof sketches to enhance clarity. While the paper is technically sound, I cannot recommend it for acceptance.", "rebuttal": "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.\n\nQuestions:\nMajor Problems:\n**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 κ?**\n\n**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.\n\nIn 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.\n\nSimilarly, $\\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.\n\n**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?**\n\n**Answer:**\n\n1. 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. \n\n2. We explain why a CoT transformer F can produce different results for x1=A and x2=AAAAAA. \n\nFirst 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.\n\nF(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.\n \nBut, 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. \n\nThe same applies to every subsequent step, so CoT can solve the dataset with typ=1.\n\n**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))?**\n\n**Answer:**\n1. 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$. \n2. 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$.\n\n**P4. What mechanism allows a COT transformer to leverage input information beyond typ(x)?**\n\n**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.\n\n**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 κ.**\n\n**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.\n\n**P6. What is the relationship between embedding dimension d and width W in Section 3?**\n\n**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."}, {"review_id": "Ss5KFnumNq", "reviewer": "Reviewer_VN8V", "summary": "This work studies whether CoT can enhance a model's memorization capability from a theoretical perspective. The authors first identified the necessary and sufficient conditions for Transformers to memorize a language. Then, the authors presented lower and upper bound on the number of model parameters required to memorize a given language with and without CoT. These bounds show that (1) CoT affects the languages that can be memorized by the Transformer (2) CoT does not increase the memorization capability of Transformers significantly.", "questions": "See weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "(Disclaimer: I do not work on formal language or learning theory, hence might not be the right person to judge the significance of this work)\n\n**Strengths**\n* This work studies an interesting problem: whether CoT enhance the memorization capacity of Transformers.\n* This work includes a detailed analysis comparing memorization capacities of CoT and non-CoT Transformers under different language classes, position embeddings setup, etc.\n* The paper is generally well written. The settings and assumptions are clearly stated in the paper.\n\n**Weaknesses**\n* 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?", "was_revised": true, "final_justification": "Given the concerns raised by other reviewers regarding the validity of the problem setup, I have lowered my rating to 4, as the impact of this work on understanding memorization in pre-trained Transformers might be limited. However, as someone who works on the empirical side of memorization, I do value theoretical work that tries to model memorization, even under toy settings.", "rebuttal": "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.\n\n**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?**\n\n**Answer:**\n\nThe definition of CoT Transformer (L154-158) is the commonly used one in most papers and practical LLMs, which is also called autoregressive Transformer. \n\nDifferent 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.\n\nTo study the memorization capability of other CoT Transformers will be listed as a future work in the paper."}, {"review_id": "TkRFc73YA0", "reviewer": "Reviewer_wb9P", "summary": "This work studies whether CoT prompting can enhance the expressive power of Transformers in the context of memorization. Focusing on fixed-precision Transformers and finite datasets, the authors claim that CoT does not significantly improve a transformer's ability to memorize general datasets. They show that Transformers with CoT do not strictly dominate those without CoT in terms of memorization capacity. Additionally, the paper demonstrates that CoT does not enable Transformers to memorize certain infinite languages.", "questions": "See Weaknesses.", "limitations": "N/A", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The paper presents an interesting and somewhat counter-intuitive result that CoT may not enhance the expressive power of Transformers from the perspective of memorization. This aspect seems to be largely overlooked in prior literature.\n2. The theoretical analysis appears solid, covering both necessary and sufficient conditions as well as providing matching upper and lower bounds.\n\nWeaknesses\n1. 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.\n2. 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.", "was_revised": true, "final_justification": "The authors' response partially addresses my concerns, but I still believe algorithmic structures or complexity classes are essential for properly analyzing CoT reasoning, even with the additional clarifications. Memorization, which considers the most general class, does not fully capture the reasoning aspects of CoT. Since this limitation remains unresolved, I maintain my original score.", "rebuttal": "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.\n\n**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.**\n\n**Answer:**\n\nWe will explain the why studying Memorization CoT Transformer and, closely related, the relationship with previous Reasoning CoT from 3 aspects.\n\n1, 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.\n\n2, 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.\n\n3, 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.\n\n**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.**\n\n**Answer:**\n\nWe answer this question from 3 aspects:\n\n1. 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.\n\n2. The reasons for using different structures are:\nFirstly, 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.\nSecondly, 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.\n\n3. 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."}]

Author rebuttal:

Meta-review: **Summary of Claims and Findings**

This paper provides a theoretical analysis of the memorization capabilities of autoregressive transformers with parameters of fixed-precision, both with and without Chain of Thought (CoT). The authors establish necessary and sufficient conditions for these models to memorize a finite language and provide upper and lower bounds on the number of parameters required. Their central finding is that while the classes of languages memorizable by transformers with or without CoT are not subsets of each other, the number of parameters needed is asymptotically the same, specifically $\overline{O}(N)$ for a dataset of size $N$. This implies that CoT does not significantly enhance a transformer's raw memorization power. The paper also extends the analysis to infinite languages, arguing that CoT cannot help transformers memorize certain infinite arithmetic tasks.

**Strengths**

* **Novel Theoretical Contribution:** The paper addresses a novel and interesting theoretical question regarding the power of CoT from the perspective of memorization, an area that has been largely overlooked. The positive memorization results could be even stronger if considering practical usage of transformers, e.g., if a special [BOS] (beginning of sentence) token is added in the beginning, then the Non-CoT construction could memorize any dataset. 

* **Rigorous Analysis:** The authors provide a solid theoretical framework, including necessary and sufficient conditions for memorization and tight bounds on the required number of parameters.

**(c) Weaknesses**

* **Simplifications:** The analysis omits key components of modern transformers like LayerNorm, positional encoding (in most parts of the paper) and focuses on single-token outputs, limiting its direct applicability. In particular, layerNorm could break some results such as Proposition 5.7(2) because Layernorm is non-lipschitz when input is around the zero and the current analysis seems to rely on the lipschitzness of the transformer layers. 

Though this paper focuses on finite precision transformer, in the forward pass the transformer actually have infinite precision. This makes sense as intuitively the description length of transformer (measured by total number of bits used in parameters) upper bounds its memorization capability. However this also leads to questions about the practical relevance of the theoretical results presented in this paper, given the that the transformer forward pass are also done with finite precision and rounding.

* **Lack of Empirical Validation:** The submission is purely theoretical and lacks experiments on real-world models, making it difficult to assess the practical implications of its findings.

**Reasons for Recommendation**

This is a borderline paper, but its strengths ultimately outweigh its weaknesses. The primary reason for acceptance is the novelty and significance of the theoretical question it tackles. By formally analyzing CoT's impact on memorization, the paper provides a new and valuable lens through which to understand the mechanisms of large language models. While the practical implications are not yet clear and the theoretical model is simplified, the core findings that CoT alters *what* can be memorized but not *how much* and the analysis is a solid contribution to the theory of transformers.
Decision: Accept (poster)