Generalizing Reasoning Problems to Longer Lengths
Authors: Changnan Xiao
Bing Liu
Venue: ICLR 2025 Poster (2025)
Keywords: length generalization
learning to reason
length extrapolation
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: This paper first introduces a theorem to show the length generalization (LG) problem’s root cause, highlighting what is necessary to resolve it. It then proposes and proves a sufficient condition to solve LG

Abstract: Length generalization (LG) is a challenging problem in learning to reason. It refers to the phenomenon that when trained on reasoning problems of smaller lengths/sizes, the model struggles with problems of larger sizes or lengths. Although it has been proven that reasoning can be learned if the intermediate reasoning steps (also known as chain-of-thought (CoT)) are given in the training data, existing studies only apply to within a given length (interpolation), while LG is about extrapolation beyond the given length. This paper begins by presenting a theorem that identifies the root cause of the LG problem. It then defines a class of reasoning problems for which achieving LG with Transformers can be theoretically guaranteed, provided the CoT schemes are constructed to meet a proposed condition called $(n,r)$-consistency.

Published as a conference paper at ICLR 2025
GENERALIZING REASONING PROBLEMS TO LONGER LENGTHS
Changnan Xiao ObangnXXXgittuub... changnanxi a gma 1. com
Bing Liu
Department of Computer Science University of Illinois Chicago 1 liubluic.edu
ABSTRACT
Length generalization (LG) is a challenging problem in learning to reason. It refers to the phenomenon that when trained on reasoning problems of smaller lengths/sizes, the model struggles with problems of larger sizes or lengths. Al- though it has been proven that reasoning can be learned if the intermediate reasoning steps (also known studies only apply to within a given length (interpolation), while LG is about ex- trapolation beyond the given length. This paper begins by presenting theorem that identifies the root cause of the LG problem, which shows why existing approaches are insufficient for LG. It then defines class of reasoning problems for which achieving LG with Transformers can be theoretically guaranteed, provided the CoT schemes are constructed to meet a proposed condition called (n. -oonsiscnist To our knowledge, limited theoretical work has been done about LGG in the existing literature. In the empirical study, we introduce the CoT schemes for reasoning problems like arithmetic, parity, addition, multiplication, and division to train a Transformer to achieve LG for these problems.
thain-of-though (CoT") are given in the training data, existing
INTRODUCTION
Large language models (LLMs) have been shown to perform reasoming tasks remarkably well (Brown) itt al., 2020) Liu et al., 2023 Xu et al.] 2023b). However, evaluations also revealed some limita- tions. For example, LLMs often have diffiuulties in simple addition and multiplication of large numbers (Nogueira et 2021 Qian et al.] 2022 He et al., (2024). A popular solution to improve reasoning is use Scratchpad (Nye et al. 2021 or Chain of Thought (CoT) (Wei al. (0022) Their idea is to add intermediate sleps for each reasoning problem in the training data. For example,
the training sample for calculating + x 1 may be presented as + 2 x 3 + 2 = 5 rather than 3 + 2 x 1 = 5. CoT has been used to improve reasoning (Anil et al. 2022 Liu & Low 2023).
However, Dziri et al. (003) and others reported that even with detailed CoT steps, the learned models still fail generalize. For example, they showed that when trained with smaller problem instances, e.g., multiplication of two smaller numbers like 1234 x 135 based on the CoT training data, the model cannot generalize solve larger problem instances (c.g., 235469 44562). This problem is called length generalization (LG) (Anil et al. 2022 Kazemnejad et al. 2023). Note that we distinguish a problem, e.g., multiplication of two numbers) and an instance of the problem, e.g., 1234 x 135.
This paper proposes a theoretical study of LG in learning to reason given a step-by-step CoT process for each training problem instance. We will not study the case where the CoT steps are not given but only the direct input and output (c.g.. 3 + 2 x 1 = 5) are provided as it has been proven that this case isn't 't learnable in general (Wies et al. 2023 Feng al., 2023 Malach 2023). Although the learnability based on CoT has been proven for neural networks in (iies et al. [023] Heng et al. 2023] Malach, 2023), these studies are all under i.i.d and given problem length/size N. They do not cover LG. Their statements are like "for given dataset with training instances of problem with length no longer than N, a suitable neural network can learn to solve any instances of the problem with length N' < N under PAC upper bound." The key limitation of their studies is that the training problem instance length and testing problem instance length are in the same range. We will see in Sec. thhat if the test instance length longer than the training instance length range, the model fails badly.

---

Published as a conference paper at ICLR 2025
This paper aims to overcome this limitation to achieve LG. Our statement is: "for given dataset with training instances of a problem with lengths no longer than N. learning can solve problem instances of any length N' if the CoI scheme of the problem can be constructed sattisfy proposed condition." " This condition is called (n, r) consissetnc.. Note that for the same problem, there can be many ways to provide the intermediate steps, which we call different CoTl' schemes. Some CoT schemes may fail to meet the (n, ccoosssstyy condition and struggle to achieve LG, while others may satisfy the condition and can achieve LG.
This paper makes the following contributions:
1. It first presents a theorem to identify the root cause of the LG problem, which explains why existing approaches based various position embedding methods (Duan & Shi 2023
Zhou et al. 2024| He et al. 2024) are insufficient for solving the LG problem.
2. It then proposes the condition (n, r)-cossistency, which formally defines a problem class whose problems can have CoT schemes that satisfy the (n, r)-oossittey condition. We prove that LG can be achieved with a Transformer for this class of problems. To our knowledge, limited theoretical analysis has been done about LG or existing approaches in the literature. In essence, the proposed method only requires the learner to see all n r-llngth intervals to guarantee LG, regardless of the length of the training or testing sequences.
3. We validate the theory by using Transformer learn complex tasks like arithmetic, parity, addition, multiplication, and division, achieving LG for the tested lengths. To our knowledge, no current method attains perfect I.G for multiplication for those lengths, and no reported results exist for division, which presents an even greater challenge.
RELATED WORK
Our related work includes outrof-distribution (OOD) generalization, theories about using CoT for reasoning, and empirical work on I.G. We review the evaluation of reasoning of L.LMs in Appendix A
OOD generalization of reasoning was studied in (Abbe et al., 2023) It assumes that some value combinations are missing during training and that can result in wrong predictions on OOD data. Our work is different as we identify a condition for achieving LG. LG is type of OOD generaliza- tion. However, there is a key difference. Since the maximal length of the training problems is always finite, a larger size/length problem can always appear testing. which can be seen as OOD, But such an OOD is unavoidable regardless of how much data is used in training as long as it is finite. OOD generation in (Abbe et al. 2023) is solvable with more diverse training data.
Wies et al. (2023) proved that when sufficient intermediate steps (or CoT) are available, neural network can learn any function in the P time complexity class. In addition, there exist functions in the P time complexity class that cannot be learned by any polynomial time learning algorithm without COT. Feng et al. (2023) showed why CoT works on problems that can be decomposed into sub bobb-prollms... They also proved that it is not learnable directly without CoT. Li et al. (2023b) showed that CoT can enable the model to identify each step and then work on the step before moving to the next step in the CoT chain. Prystawski & Goodman (023) studied why and how CoT works in L.Mss. |Maachh (2023) proved that with some assumptions, even simple models like linear next-token predictors trained on CoT data are universal learners. However, as discussed in Sec. [ the theorems in these papers are based on the given length/size N. They do not cover LG. An analysis was also done about mathematical reasoning in (Hu al. 2024) and shows that reasoning done more like case-based reasoning rather than based on learned rules.
Many empirical attempts tried to modify the Transformer and learning biases to solve the LG problem better. Duan & Shij (2023), Zhou et al. (022). Pelassi et al. (202)) and He et al. (2024) proposed different position embedding or bias calibration methods to enable the model to learn better. However, their methods are unable to solve addition perfectly or multiplication at all. Manipulating positional embeddings cannot guarantee LG because it still falls within the scope of the proposed Theorem where the learner does not encounter positional embeddings of longer sequences in training and, therefore, cannot ensure LG in testing. Jelassi et al. (2023) further proposed to add a small number of long sequences in the training to help solve long sequences, but still could not solve mulriplication. Chi et al. (2023) proposed a Transformer variant with weight- -hariin, a working memory, etc, to improve 1.G for regular languages, but it still cannot solve multiplication addition. Different
2

---

Published as a conference paper at ICLR 2025
attention mechanisms and new architectures are also proposed in Nangia & Bowman 2018 Bowman al., 2015; Tay et al., [022]] Choowhhury & Caragea b). However, they don't 't use CoT but only the direct imput and output in training. Their methods work various text copying and list operations but don't solve these problems and do not work on more complex large-number addition and multiplication. Theoretically, learning to reason without intermediate steps (or CoT) has been shown not learnable (Wies et al. 2023 Feng et al. (2023).
LG is also studied for text generation, which has the problem when training on short text while evaluating on longer text (Sun et al., [023] Press et al. 2022 Ruoss et al. 2023 Han et al. 2023 He
al. 2024). However, this body of work different than the LG problem in reasoning.
3 PROPOSED THEORETICAL STUDY OF LG
Let y be a reasoning problem and the sequence (or string) S = 81 81..-1151 be an instance of the problem, i.e., L. We use [S] to denote the length of and ST]] = s; to denote the i'th element of S, where 8; E V and V is finite vocabulary space.
CoT scheme for a reasoning problem is a sequence of intermediate steps for solving the problem T We use St to denote the input of the ''th CoT step of S and S as the output of the step, which
also the input of the (t + 1)'th CoT step. For simplicity, we use (S", .S1 5T)., ) to denote the CoT process of S (5 is the same as S here), where S represents the end. Note that T is function of S", i.e. T = T(S)). ). but again for simplicity, we simply write T. For instance, given S as 3 + 2 x 1 (an instance of the arithmetic problem), 5 also 3 + x 1, St is 3 and S is 5, which form the CoT process of S. We use S₁. to represent the k' instance of the problem I, and S the input of the t'th CoT step of Sk. Similarly, we use [ to denote the i' i'th element of St. An element S can also have multiple dimensions. Below, we will also use Sg to represent the kth problem instance Sk-
Problem Statement of Length Generation (LG):: For a problem I, A N > O, when we learn a func- tion f that performs perfectly on the problem instances of length S. N, i.e., f(St) + St+1, VSS| S N, YO S 1 < T we want the learned function f to also perform perfectly on problem instances of arbitrary length N' (i.e., f(S*) + St+1, Y > or N' I N, V = N', VO S t < T). Note that N' is of arbitrary size, and T is also of arbitrary size as it is function of So.
We propose a condition called (n, r)-cossistency that is sufficient for achieving LG. This defines class of problems whose CoT schemes can be designed to satisfy the condition existence of parameterized Transformer with a mask following the condition to achieve LG.
3 We prove the
3.1 ROOT CAUSE OF THE LG PROBLEM
Before introducing the proposed condition, we present the following theorem to give the root cause of the LG problem, which also highlights what is necessary resolve the problem. Without loss of generality, we represent a CoT step as multivariate function that maps tokens to tokens. For simplicity in analysis, we assume it to be a single-valued function, mapping a set of tokens single token. The LG problem involves observing the function's 's behavior with up to N tokens and predicting how behaves with more than N tokens.
Theorem 3.1 Define V as a metric space. Denote E V to be the empty token. For gN VN + 11,,1] A N' > N, there exists infinitely many continuations fN VN + 1-1,1] s.s. fN -1, UN, O, 0) gN(UU,...,
See the proof Appendix [. Here V represents the vocabulary. The number of the input tokens (the length) is represented by N. Let the ground truth function reasoning arbitrarily many tokens be goo : I1 V + [-1, 1]. The ground truth function reasoning on up to N tokens represented by ON. which restricts g onto the first N tokens, i.c. gN (v1. ...., UN) 9oe (v1, ........ .. UN. O, 0, O,
'There can be many CoT schemes for the same problem as we discussed carlier and will see shortly.
2 Notice the slight difference from the existing CoT modeling, which is f(S)) = 5*1 S², .s.......''" ST.
3 This does not claim that (n, r) coonsssstyy is necessary for achieving I.G or that it is possible to design
CoT schemes for all reasoning problems satisfy (n, c--cossiste
3

---

Published as a conference paper at ICLR 2025
Theorem 3.1
states that there exists infinite number of continuation fNr of a higher dimension N that can achieve the effect of the function INv of a lower dimension N.
The LG problem is to attain ON (N' N) when observing gN. which is the constraint that 9x restricted on N dimensions is gN- However, Theorem [3 shows that there exist infinitely many functions f. that can produce the effect of 9Nv when restricted on N dimensions. This means that, with only the continuity bias and the input and output data of gN. it is almost impossible to predict the correct gN as there exist infinitely many fN (which are not gN.) that satisfy the same constraint.
This analysis shows that with only the input and output data of gN. it is insufficient to achieve LG, i.e. predicting 9N. We have the following necessary condition for achieving IGG for problem:
* Sufficient bias needs to be introduced to the problem s.t. with the bias, fN in Theorem 3.1 is made equal to gN uniquely (or with high concentration
In what follows, we propose a specific bias, namely the (n, r) connistteny which is sufficient to achieve LG. This bias is pattern based and requires the consistency condition to ensure that gNv is uniquely determined when its pattern matches the corresponding pattern in 9N.
3.2 (n,, CONNSISNSSTN THE INTUITIVE IDEA
We now intuitively discuss the proposed (n, connsistteny Denote y as a problem and 5 E 5 as an instance of the problem. In CoT step t, we have the input St and output St+1 Our goal is to find a solver (or learn a function) ff that predicts 5t+1 given St, i.c. st+1 = f(S*) [$] The problem of predicting 5t+1 can be decomposed into sub-problems of predicting each element of S*+1 i.e., ( for each position index i. To do so, we further ensure that the lengths St and 5t+1 are the same by adding blank space elements in suitable positions. (n,r) basically means a context with
r-length intervals (or subsequences) in St can predict 5(+1
For example, let consider one instance, 1 123+567, of the problem, addition. We consider the CoT step with the input S = *123+567- $0' and output S = '123+567- 790', where ? indicates that 0 carried and indicates that is carried. To ensure that the input and the output are of the same length, a blank space (or empty) element is added after '-' in S in the CoT scheme. We call this CoT scheme of addition as addition-[1].
Let us consider the prediction of the 10's element 9 in the output S i.e., [' 9. The 10's position of 5 is $. Let us say that we use the three elements interval or subsequence S" (i.e., = 3 and $ is the central element of the interval) as the context to predict 9 in the 10's position of 5t, which clearly insufficient as 9 can only be calculated by using 2, 6, and in S This means that we need at least three intervals in 5 as context to predict 9 in S1, i.e., '123', '56'', and $0', where 2, 6, and $ are central elements in the intervals respectively, and then 3. We call $0' the anchor interval the position (10) of its central element $ is the one that we want to predict in 5 with this set of intervals, which we call (3, 3) -ontext for predicting the value (i.e., 9) in the 10's position of S (3. -conteex represents three 3-Iength intervals.
$0 in
We now introduce the concept of (n, r)-oosiistency with regard to a problem, (3, 33)-consistency with regard to addition in our case above. Consistency here means that 9 should be predicted for the position of the central element of the anchor interval (the position of in $0' in 5 whenever the three intervals (* $ '123', *567') appear in an instance of the addition problem. Note that we put the anchor interval first and separate it from the other intervals using ':' to indicate what we want to predict. This (3, 3)-cottext is not consistent for the addition problem. This is because we can easily find another problem instance that contains the (3, 3) cconteett but does not predict *9' for the position of the central element of the anchor interval. For example, the input S" = *12342+ 4562244577- $0' and output S $12342 2 + 4544457777 45445568$222 $20' Obviously, 5 here contains the above (3, -oonttex,, but the prediction for the position of the central element of the anchor interval (the position of '$') in the input Sa should be 2 in the output S'1 not 9. These two scenarios result in a conflict in learning. Thus, addition-[I [imoon[[liin [ine]] is not (3, 3) -ccoossstt for n = 3 and 3. The intuition of (n, cooosissteyy is that we want to learn and predict the same element value with the same context with no conflict or uncertainty.
'We still don't 't have a complete set of biases contributing to the necessary condition. This paper provides one such bias, i.c., (n, connsssttn,,, that is sufficient for achieving L.G. For simplicity, we omit. N in fx, where N represents the length of the problem instance.
4

---

Published as a conference paper at ICLR 2025
We can design different CoT scheme for addition using two lines achieve (3, -consisnnttt We call this scheme addition-[2]. which uses tags to indicate the digits to be calculated next (see the CoT process in Fig 3 of Appendix F. The two CoT examples above become,
[22 567 SO
123 567
$0 =
and
12342 + 45678
$0)
12342 + 45678 = $0 7
K
where I and J indicate the digits to be added next and K indicates the position of the output. In this case, each element has 2 dimensions and when the second dimension is not L, J, or K, it is an empty token, which is also significant. In this 2-dimensional case, the corresponding (3, -onttetx of 5 1123+567= $0' becomes (notice the anchor interval in the first position),
(x 90' '123', ' '567'
K I
In this case, the (3, 3)-ontetxtt is not contained in the above CoT step of 12342 + 45678. In fact, no other possible problem instance can have the same three 2-dimensional intervals whose central elements are not the elements to be calculated next because L, J, and K indicate the elements to be calculated next. Thus, addition-(2) [2] is (3, 3) -consisstn,,, meaning that for any instance of the addition problem if it contains the above (3, 3) conttex,, the output element at position K will always be 9.
To summarize, the (3, 3) -onttext example implics that (1) a context is independent of the positional distances between any pair of intervals in it and (2) the same or consistent output is obtained if any CoT step input of a problem instance contains the same context. Thus, this example introduces a bias that if local context in the input always implies the same output without requiring any dynamic information depending on the length or position (c.g., position encoding in the Transformer), it's possible to achieve LG. Based on this idea, we propose (n, r) consistency and show is one special bias that is sufficient to achieve LG by a parameterized Transformer.
3.3 (n, CONNSSSSNSTYN DEFINITION AND PROPERTIES
We now formally define (n, coonsiisten. For simplicity of notations, we will use 5 to represent S and S to represent gt++1 Similarly, we can also call any St problem instance. We now introduce the concept of consistent context.
Definition 3.2 (Consistent Context) Denote a context h = (a) .0,..., mpa) a sequence of [h| intervals, where is called the anchor interval and each interval consists of a sequence of elements, Le. a3 88,1 Pj.1...8pp .j.rr 8j,1 E V, 1 S S [hl, 1 1 S r, where V a finite vocabulary
(i) For a problem instance S 81 ... 8150, we say h S (contained in) if there exists S mi, m|a1 S | s.t. Sm, Sm, +r-1 = aj, j S [/..
(ii) We say a context of a problem yf there exists a problem instance S E E s.t. h h
(iii) We define c(h, 59) m2 + [ as the position index of the central element of the anchor interval a1 = Smy Sm, +r-1 in 50 (due to the flooring, r does not have to be odd). For example, given c(h, SO) = 4, and S (ch
r S 1 22 and a₁
1, then m. 3, 1,11
x.
(iv) We say a consistent context if for any S9. E I and their respective CoT step outputs St,Sh, when h C 50 S9 they always have the same element at the central element position of a of h ie., S (((chh,s))] Sc(chh S1) To ensure the equal length of Sh and St. blank space elements are inserted in suitable positions (see below).
(v) For a consistent context h, define (hh) = 5- S9), V E
J S.L. So
When h = (01 : ........ ) h'' = (a) .e.. (), |7/| > |/| and a, a/. 1 Sis [h], we say h is the prefix of I and write h x h'. We write h 3 W. when h h or h M'
It is not important where the intervals other than the anchor interval are located.
7 is not required that mi < m2 < ... < mpj and every a, (a, ..,..., qai) docsn't contain
any positional information in 5
5

---

Published as a conference paper at ICLR 2025
constrains only the anchor interval d1 of h and it seems to leave the other intervals unconstrained except h is contained in 5 As indicated in Sec. 3.2 the other intervals usually contain the other elements involved in reasoning step. This leads to our (n, -consisttey definition.
Definition 3.2
Definition 3.3 (n. r CoConsiitt Problem) We say a problem y is (n, ro..siccnsstten, for every problem instance 8 in I, i.e. A E E. denote S as the CoT step output of 5 for every index or position i of 5 (i.e. V1 S sis [S')), there exists consistent context bgg s.I. (i) c(h(a), 80) i, (ii) Megal S n, (iii) all intervals in hig is r-length.
For simplicity, we omit (ii) and (iii) of Def. 3.3 in the following discussions unless necessary. When I is (n,, -cooniitett, for S E E, determining the output S of the CoT step can be decomposed into determining every element [ for every index i. Given a particular index i, if we can find some consistent context hig s.t. c(Ira) ) i, where the existence of lug is guaranteed by Def. 3.3
then we have [ (b()) by Def. 3.2 By concatenating S' [d]'s, ss we achieve the objective of determining St. Intuitively, discussed in Sec. 3.2, want the CoT scheme to have a consistent context hm to predict the element [1] in each output position i with no uncertainty.
Both the consistency property of h and the (n, -ooosssttny property of I are monotonic.
Property 3.4 If is consistent context and h 3 hi, then h' is also consistent context.
Property 3.5 If : is (n,, -coosistttttt then for Vn' 2 n, Vr 2 r, y is (n',,"")-cossiittet -cosssitstt
The proofs are given in Appendix B It is easy to see that different intervals the same context may have different lengths (number of tokens). We use the same size r in our theory for simplicity. It also important to note that in practice, when we design a CoT scheme, we don't need design minimal consistent context. It's enough as long as the context is consistent.
3.4 (n, r) CONSSISESYY IMPLIES LENGTH GENERALIZATION (LG)
We now show that when a problem is (n, connsisttnn LG can be achieved (see the problem statement at the beginning of Sec. B) That is, there always exists solver (e.g.. model algorithm) that can learn to predict the CoT step output for an arbitrary problem instance of any length.
Here propose one solver that can achieve LG. It is Transformer- based model. The model takes problem instance as the input and output of the CoT step of the problem instance. We show that there exists a proper parameterization of the model, s.t. the CoT step output prediction is correct for input problem instances of arbitrary length.
Theorem 3.6 Ifa problem I is (n, coonsisttnt then there exists an n-layer Transformer model f. for V 5 E f with CoT process (SO, .TT, we always have 5t+1 f(55), <
[Proof Sketch.] For 5 E 5 with (S".....,S") ST), for V < T. we construct a n-layer Transformer model f s.t. gt+1 f(S). For simplicity, denote St as S and St+1 S Since I is (n, consssttt,, for each 1 5 i S | there exists a consistent context hij s.t. c(hig S*) i. The key idea to construct f is to extract hig for each i, so that [*] = (hbgg is determined. The 1st layer applies local padding mask with relative position encoding, where the local mask guarantees that the token at index can only observe the interval that centers at i. The 1st attention layer aggregates a1 for each h(j 's. The 1st fordard layer lists the contexts that are potentially consistent when concatenating 01 to the end. The 2nd attention layer has no mask, which seeks for potential 02" that (a,,a)) is the prefix of some consistent context h. The 2nd feed rerdffrrward layer produces an indicator if (m1, a2) is already a consistent context. The process continues. Since P is (n, consissttn, there must exists a consistent hig for each i after n layers. The last layer maps h[]] to (hag) for each i.
The full proof is given in Appendix B This theorem shows (n, consisteenc implies the existence of a Transformer model that can achieve LG The interplay of the problem complexity and the network capacity (e.g., the number of parameters and layers) is discussed as part of the proof.
*This does not imply that (n, r) connisttnyy guarantees the IG learnailiiyy of the Transformer. However, while theory only establishes that (n, (c.nssccosis implies the existence of Transformer model capable

---

Published as a conference paper at ICLR 2025
3.5 How TO DESIGN CoT SCHEMES TO ACHIEVE ( -CONSISTEECCY
It's challenging to create a universal procedure that can generate CoT schemes across reasoning problems to satisfy (ni, --oossitttnn Each problem is likely to require tailored method different problems have entirely different computation steps. However, as demonstrated by the examples in Sec. 3.2 and those in the experiment section (Sec. 4. the general approach quite clear. We use tags to infom the learner what positions or elements are involved in calculating each CoT step, which naturally creates consistent local contexts to ensure that each output element a reasoning step can be learned and predicted without conflicts across all possible instances of the problem. For example, the tags I, J, and K in the addition problem Sec. 3.2 tell the learner about which digit (!) from one number should be added to which digit (J) from the second number, and what the result should be in the output position (K) in each reasoning step. In a nutshell, the tags implicitly inform the learner how the calculations are done in solving the problem. With such tags, the learner learn the underlying reasoning rules without ambiguity or conflict. The (n, --oossssttyyy condition checks whether the provided tag information is sufficient for learning to achieve LG. The key weakness of existing approaches is that they learn short-cut patterns or regularities, rather than reasoning rules. That why they cannot extrapolate to longer lengths. To achieve LG, the learner must learn second-order patterns (reasoning or calculation rules for each problem) similar to how we teach children to do addition or multiplication by making them learn the rules of calculation rather than guess based on example inputs and outputs alone.
However, defining tags manually and then checking (n, -oonsssssss for each possible problem is not scalable. There exists an automatic method that can transform problem into r.-onssstttt, which is induced by Def. 333 and outlined Appendix(C) However, its high computational complexity makes it impractical. Improving this automated CoT design method is an interesting future work 0
4 EXPERIMENTS
Our experiments verify (1) for a CoT scheme of a problem, if it is (n, (n,rr)-com conssistttn,,, it is solvable for LG, and (2) for the same problem, one CoT scheme may not be solvable for LG, but another may. The code of our system can be downloaded at https://ogooeevvewwweee//o/iiiie
4.1 EXPERIMENTAL PROBLEMS, COT SCHEMES, AND (n, r-r-C)OSSSTNNNEE
Experimental Problems. We use reasoning problems in our experiment. (1) arithmetic in Fr (the finite prime field with seven elements, i.e., F7 {0. 1, 2, 3, 4, 5, 6)), where the calculations are under the sense of 'mod 7', (2) parity, which is the problem of deciding whether there are an even or odd number of I's in sequence of 0's and 1's, (3) addition of two integer numbers, and (4) multiplication of two integer numbers. (5) division of two integer numbers.
CoT Schemes for the Problems. As mentioned earlier, each CoT step is pair (Input(i), Output(i)). Fig. 3 in Appendix gives an example for each CoT scheme. Below, we detail the CoT' schemes.
(1) arithmetic in Fy. It is formulated in the usual way and represented as input and output pairs. A detailed training example is given in Fig. Bin Appendix F This CoT scheme achieves LG, as is (1, -onssisnstt Each element belongs to at most one calculation step, and the distance between the elements that are calculated together is at most 4, e.g., between '(" and ')' in (3 13+27 2). Therefore, to determine whether the i' 'tth element might be calculated next, we consider i ''th neighbors of radius 4, i.e. 8;-4... 81+4- 4- To check whether 8j-4....; 8i+4 are in other higher priority calculations, we further consider each neighbor of radius 4, i.e. 8i-8... 81+8. Therefore, every 17-length interval determines the next central element, regardless of problem instance and position index. Note that we
of achieving LG, experiments show that Transformer-based models can leam achieve LG for challenging mathematical reasoning tasks. This suggests that (n, --ccosiisyy may lead to stronger conclusion, such as the learnability of a Transformer- based model capable of achieving LG or extrapolation, beyond the traditional i..dd assumption. We leave this for future investigation.
"That being said, we envision an approach in which we only need design CoT schemes for a finite set of basic reasoning functions. More complex reasoning tasks are compositions of these basic functions. When addressing a complex problem, the system call upon the relevant basic functions as needed. This approach may reflect how humans learn and reason. Relying on ever-increasing amounts of sequential data to learn short-cut patterns a brute-force manner may not he the most effective efficient solution.
7

---

Published as a conference paper at ICLR 2025
Table I: Experimental settings, Train Length: Training length. LG Test i: Length generalization test with longer lengths. We have one training set and 6 test sets for each problem. Test set 0 has the same length setting as the Training Length setting and is thus omitted from this table. L stands for (c [12]
length. For addition-[172 (a b), multiplication- [1/1 1] (a x b) and division-
b), L is
the number of digits in a or b.
Train Length
LG Test
LG Test 2
LG Test
Test 4
Test
arithmetic in Fr
L E [3,20]
Le (3,30)
L 3,
L (3,50)
Le [3,60]
L 100)
parity-[22 [2]
LE (.8)
Le [1,30)
Le 1,40)
Le [1,50)
Le (1,60)
Le [. 100)
addition-[122 [1/2]
L. (188)
1. 1,10)
L (1,11
Le 16)
L [1.21)
multiplication- [1]1]]
Le [1.6
Le [1.7)
[1.8)
1.99
Le (1)10)
LE [1,11)
division-[15 [12]
L. [1,6)
L (1,7)
L. (1.8)
L. 1.9)
L. (0)
1. (1.11)
pad blank or empty elements in the training data to ensure that every element in any problem instance 8 can be center element in a context of length 17.
(2) parity. It is formulated in 2 lines, i.e., parity-[2]. On the 2nd line, ? indicates the current position of the CoT process, represents odd and 0 represents even. See Fig. 3 in Appendix for an example. This CoT scheme can achieve LG as it is i co-osssstt For any problem instance 8 any position/index i, if c(h, S*) i, where = (a1) and ai = $182, then (1) when ? is not in 01. [ $2, (2) when ? is in 81 $2, it's not difficult to check that S [t] is determined by ai without ambiguity. Therefore, every 2-1ength interval context determines an output central element, regardless of the problem instance and position index.
(3) addition. is formulated in CoT in two ways: additioon[[1 and additiio-12]. As discussed in Sec. 3.2 addition-[1] [1] is not (n, -coossittet, and addition- is (3. 3)-consistent. See Fig. 3 in Appendix F for a full training example for each formulation in the CoT input and output format.
(4) multiplication. It is formulated in two ways: multiplication-(1] (one line) and multiplication-([]]] (11 lines). multiplication-LI is not coonsssttt,, but multiplication-111 [1]] is (12, 3))ccssssttett
For multiplicaatin-(1] we decompose the problem into two stages. In the 1t stage, we transform multiplication into a summation of multiple integers. In the 2nd stage, we solve the summation recursively. An example is shown in Fig. 3 in Appendix [ The 2nd stage is not (n, -coossisttn as addition-[1] not. The 1st stage is also not (n, --ooosisstentt. For instance, let input[k] ?" When & < b output(k] = 'a b a a+ +?" when k = b 1,
'a x b = +
k+1
output[k]= = 'a x b = a at..tg" a². In this example, whether to add '+?' or to go to the second stage
k+1
depends on b and the number of existing a's. For V (n,r) there always exists a large enough a and b s.t. n r-length intervals cannot cover all a's as well as distinguishing all a's. It's not difficult to exploit this fact to construct inconsistent instances for arbitrary context h.
For multiplication-[11 I] (each element has I I-ddmmnnsions), an example is given in Fig. ilnn in Appendix When calculating b, since addition-[2] solves LG, we only need to multiply each digit of a and each digit of b and add the product to the result by merging addition- [2] into the CoT process.
Multiplication- [11] is (12, 3) 3))ccnsisteent For any h (a1 .g.............................. 412). (1) when 01 doesn't 't contain any indicator, the output of the central element of aj is simply identical to the input, (2) when a1 contains least one of the indicators, by letting d2,--., 012 containing other 11 indicators the center, it's not difficult to find that the output of the central element of aj is determined by context h.
(5) division. It is formulated in 12 lines, i.e. division- [1). It's almost the same multiplication-111 except that multiplication does addition but division does subtraction. The numerator may fail to subtract the denominator (numerator is smaller than the denominator) and the numerator has to be restored before the subtraction. An example is given Fig. 3 in Appendix multiplication-11] division- [12] is (10,3) connsisttt
F For the same reason as
4.2 DATA GENERATION
Training Set. The model for each problem is trained with training set of 50k batches. Each batch contains 256 CoT steps. For each problem, we first randomly generate an instance of the problem and then its detailed CoT steps. Each CoT step is a pair (Input(i], Output(i]), shown in Fig. 3 in
8

---

Published as a conference paper at ICLR 2025
[ppendix We put the CoT steps of each generated problem instance into batch until it reaches 256. The steps of the last problem instance that overflow the 256 batch go to the next batch.
Test Sets. We use 6 test sets evaluate the model learned for each problem. The 5 columns marked 'LG Test 1" in fable[]give the length ranges of the 5 test sets for each problem, where the maximum lengths of the test sets increase gradually. The first test set has the same length range as that of the training set and thus shares the 'Train Length' column. Every test set consists of 1 questions (test problem instances), which are in sequence format with no CoT steps, e.g., 3 3 2.
Training and Test Data Generation. Every training or test set is generated independently. The training set and each test set are generated in the same way for each problem except that for the training set, we also need to generate its CoT steps for each problem instance based on individual CoT schemes, but for each test set, we do not. For each training instance, the CoT steps end with an "EOS" token. The additional data generation details are as follows:
(1) arithmetic in F7. The length (number of elements L) of a problem instance in the dataset is generated to be as close to the maximum length as possible (see Table I.
(2) parity. The length (number of elements) of a problem instance is uniformly sampled from to the maximum length (see Table Tb. Each element in the sequence is sampled randomly from {0, 1}.
(3) addition. The number of digits (or length L) a or in a + b of each problem instance is uniformly sampled from 1 to the maximum length (see Table I Each digit in or b is sampled from {0, 1,3,, 4, 5, 6, 7, 8, 9}, while the left-most digit is removed when it's O.
(4) multiplication. The number of digits (or length L) in or b as in a x b of each problem instance is uniformly sampled from to the maximum length (see Table J. Each digit in from {0, 1,,3,, 4, 5, 6, 7, 8, 9}, while the left-most digit is removed if it is O.
is also sampled
(5) division. The number of digits (or length L) in a or b as in C + a = 6 of each problem instance is uniformly sampled from 1 to the maximum length (see Table D. Each digit in or b is also sampled from {0, 1, 2,3, 4, 5, 6, 7, 8, 9), while the left-most digit is removed when is O. Then e = a x and are given as numerator and denominator, and is the correct answer. This setup ensures that the answer b is an integer. But our formulation can be easily extended to allow decimal answers.
4.3 IMPLEMENTATION DETAILS
The models for arithmetic, parity, addition-[1], and multiplication--[] have Trannfoormrr encoders with relative position encoding. The models for addition- multiplicationn-II and division- [12] have 6 Transformer encoders, as they are (n, r) cooossisttt and n > 1. By the proof of Thm. 3.6 both the attention layer with relative position encoding and the attention layer without position encoding are needed. The 1st, 3rd, and 5th encoders use relative position encoding with padding masks, which for the i'th token is {il S j -- 5), i.e. the r-length interval. The 2nd, 4th, and 6th encoders don't use position encoding, which exchanges information of the intervals. The optimizer is Adam and the learning rate is 0.0001. The training data for each task contains 12.8M CoT steps. Due the complexity of multiplication and division. they are additionally trained on 25.6M CoT steps with learning rate 0.000005.
When CoT scheme has multiple lines, e.g., multiplication- each element has multiple dimen- sions and each dimension has a token, including the blank/empty token. The model first maps each token into an embedding vector and then concatenates the vectors at the same position index. Then a fully connected layer maps the concatenated vector into a vector via a linear transformation. The remaining model is a standard Transformer with masks and position encoding described above.
We pad empty tokens at the beginning and/or at the end to guarantee that each position (or element) can be the central element of a sequence interval of length if the problem formulation is (n, r-coossistnnt Specifically, we pad [ empty tokens at the beginning and [اكا]] tokens at the end. For addition-[2], we further pad an empty token the right of = align input and output (see Sec. 3.2 and Fig. 3in in Appendix F) For CoT schemes that are not (n, r) conssssenn,, we don't 't pad as is unclear where and how many empty tokens to pad.
Training: As mentioned above, the model for each problem is trained with 50k batches and each batch contains 256 CoT steps. The training is done only in one epoch.
9

---

Published as a conference paper at ICLR 2025
Figure
Test results in accuracy.
0.8
0.8
04
0.
arthmmbic
addition(3]
additinPii
muhipkcetlo-(1)
multipiiation((11
dianion-(122
Train length
#IGTest
#G Test
Tests
Testing: We solve each test question using the trained model. The output generation stops when the termination token "EOS" is predicted.
For all problems, the final output is considered correct only when it is identical to the ground truth The accuracy is the number of correctly answered instances divided by the total number instances.
4.4 EXPERIMENTAL RESULTS
arithmetic in F7. Fig. shows the problem achieves 100% accuracy for all test sets as the problem (1, conssssett.
parity. It is formulated in 2 lines (parity-[2]), and achieves 100% accuracy in LG for all test sets (see Fig. as the problem (1. 2) conosiistt
addition. It is formulated in two ways: addition-[1] and addition- Fig. shows that addition- [1] fails to achieve LG as not (n, coonssistttt.. But addition-[2) achieves 100% accuracy for all test sets (Fig. 1 as it's (3, (),3))com connsisttt (Sec. 3.2
multiplication. It is formulated in two ways: multiplication-(1] and multiplication-1111] Since multiplication-111 is not (nt ---ossiistttn,, Fig. (12, consistetn
[ shows poor LG accuracy. Since mulippicatton-(11] solvable for 1.G with 100% accuracy for test sets (Fig. D
division. It is formulated as division-[12], Since it's (10, 3) c)-cossitt, it achieves LG, but there are three cases where we do not achieve 100% accuracy (Fig. D. See the details Appendix
Appendix repoort additional experimental results for these problems with even longer lengths to stress test the system, where we will see imperfections. We will also explain why they happen even when the (n, r) -consistenyyy condition is satisfied for these problems.
Note that we don't compare with existing systems because, as we discussed in Sec. 2 no existing reported system can solve multiplication and reported system has even attempted division.
5 CONCLUSION
Length generalization (LG) is a challenging problem in learning reasoning skills. There is little theoretical understanding so far. This paper introduces a theoretical framework for understanding reasoning that extends beyond specific problems or architectures. It first introduced theorem to show the root cause of the LG problem, which explains why existing approaches are insufficient for solving the LG problem. It then formally defines class of problems for which achieving LG with Transformers can be theoretically proven. Specifically, the problem class's CoT schemes can be designed to satisfy condition called (n, cocosissten Empirical results align well with the theory, showing perfect LG for large tested lengths several challenging reasoning problems.
Limitations and future work: The proposed (n, c-coosssstnncyy can seen as a sufficient condition for achieving LG. However, regarding necessary conditions, we only know that sufficient learning biases are needed, but not the complete set of biases contributing to the necessary condition. Further research is needed. In the current approach, need to manually design CoT scheme satisfy the (n,, r) conssisenncy for a reasoning problem. A future research direction is to automate the design of CoT schemes and realize the approach outlined in footnote 9.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Bing Liu's work was supported in part by three NSF grants (IIS-2229876, IIS-1838770, and CNS- 2225427).
REFERENCES
Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk. Generalization on the unseen, logic reasoning and degree curriculum. arXiv preprint arXiv:2301.13105, 2023.
Risako Ando, Takanobu Morishita, Hirohiko Abe, Koji Mineshima, and Mitsuhiro Okada. Evaluating large language models with neubaroco: Syllogistic reasoning ability and human-like biases. arXiv preprint arXiv:2230..22500 125677 2023.
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. Advances in Neural Information Processing Systems, 35:38546-38556, 2022.
Zhen Bi, Ningyu Zhang, Yinuo Jiang, Shumin Deng, Guozhou Zheng, and Huajun Chen, When do program-of-thoughe work for reasoning? arXiv preprint X.Xx::2308.155522 2023.
Samuel R Bowman, Christopher D Mamning, and Christopher Potts. Tree-structured composition in 2015,
neural networks without tree-structured architectures. arXiv preprint
Tom Brown, Benjamin Mann, Nick Ryder, Mclanie 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: 33:1877-1901, 2020.
2020.
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. Program of thoughts prompt- ing: Disentangling computation from reasoning for numerical reasoning tasks. arXiv preprint frXiv:2211.12588, 2022.
Yangyi Chen, Karan Sikka, Michael Cogswell, Heng Ji, and Ajay Divakaran. Measuring and im- proving chain-of-thought reasoning in vision-language models. arXiv preprint 41X1v.2309.04411, 2023.
Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, Rahul Nadkarni, Yushi Hu, Caiming Xiong, Dragomir Radev, Mari Ostendorf, Luke Zettlemoyer, et al. Binding language models in symbolic languages. ICLR-2023, 2023.
Ta-Chung Chi, Ting-Hap Han Fan, Alexander Rudnicky, and Peter Ramadge. Transformer working memory enables regular language reasoning and natural language length extrapolation. arXiv preprint arXiv:2305.0377 2023.
Jishnu Ray Chowdhury and Comelia Caragea. Monotonic location attention for length generalization. Proceedings of the 40th International Conference on Machine Learning (ICML-2023), 2023a.
Jishnu Ray Chowdhury and Cornelia Caragea. Recursion in recursion: Two-level nested recursion for length generalization with scalability. Proceedings of 37th Conference on Neural Information Processing Systems (NeurIPS 2023), 2023b.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. Scaling instruction iestruction-fintuueed language models. arXiv preprint arXhv:2210.11411 2022.
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:/8/00 110.00400, 2018.
Shaoxiong Duan and Yining Shi. From interpolation to extrapolation: Complete length generalization for arithmetic transformers. arXiv preprint arXiv:2310. /9884, 2023.
11

---

Published as a conference paper at ICLR 2025
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jian, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D Hwang, et al. Faith and fate: Limits of transformers compositionality. arXiv preprint arXiv:2305.
2023.
Guhao Feng, Yuntian Gu, Bohang Zhang, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. arXiv preprint 2305522305..4088. 2023.
Yao Fu, Litu Ou, Mingyu Chen, Yuhao Wan, Hao Peng, and Tushar Khot. Chain-of-thought hub: A continuous effort to measure large language models' reasoning performance. arXiv preprint 1xXiv:3305.17300 2023.
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. Pal: Program-aide aided language models. In International Conference Machine Learning, pp. 10764-10799. PMLR, 2023.
Gaël Gendron, Qiming Bao, Michael Witbrock, and Gillian Dobbie. Large language models not abstract reasoners. arXiv preprint arXiv:2305. 19555, 2023.
Chi Han, Qifan Wang, Wenhan Xiong, Yu Chen, Heng Ji, and Sinong Wang. Lm-infinite: Simple on-the-fly length generalization for large language models. arXiv preprint arX1v:2308.16137, 2023.
Zhenyu Hc, Guhao Feng, Shengjie Luo, Kai Yang, Di He, Jingjing Xu, Zhi Zhang, Hongxia Yang, and Liwei Wang. Two stones hit one bird: Bilevel positional encoding for better length extrapolation. Proceedings of the 41st International Conference on Machine Learning. 2024.
Cheng- Yu Hsich, Chun-Liang Li, Kuan Ych, Hootan Nakhost, Yasuhisa Fujüi, Alexander Ratner, Ranjay Krishna, Chen- Yu Lee, and Tomas Pfister. Distilling step-by-step! outperforming larger language models with less training data and smaller model sizes. Findings of the Association for Computational Linguistics (ACL2023), 2023.
Pengbo Hu, Ji Qi, Xingyu Li, Hong Li, Xinqi Wang, Bing Quan, Ruiyu Wang, and Yi Zhou. Tree-of- mixed-thought: Combining fast and slow thinking for multi-hop visual reasoning. arXiv preprint arXiv:2308. 006588 2023a.
Yi Hu, Haotong Yang, Zhouchen Lin, and Muhan Zhang. Code prompting: a neural symbolic method for complex reasoning in large language models. arXiv preprint 2...v:2305./8507. 2023b.
Yi Hu, Xiaojuan Tang, Haotong Yang, and Muhan Zhang. Case-based or rule-based: How do transformers do the math? Proceedings of the 41st International Conference Machine Learning, 2024.
Samy Jelassi, Stéphane d' A'scolli, Carles Domingo-Enrich Yuhuai Wu, Yuanzhi Li, and François Charton. Length generalization in arithmetic transformers. arXiv preprint arXiv:2306. /50000000.5440, 2023.
15400,
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding length generalization in transformers. 37th Conference Neural Information Processing Systems (NeurIPS 2023), 2023.
Jb. Kim, Hazel Kim, Joonghyuk Hahn, and Yo-Sub Han. ATHENA: Mathematical reasoning with thought expansion. In Houda Bouamor, Juan Pino, and Kalika Bali (,ds.), Proceedings of the 2023 Conference Empirical Methods in Natural Language Processing, pp. 16315- Singapore, December 2023. Association for Computational Linguistics. doi: 10. 1014. UtL/pttps///acaatttoooogg.
2023 www.eeeenmmm..... 1014
Soochan Lee and Gunhee Kim. Recursion of thought: divide-and-conquer approach to multi- context reasoning with language models. arXiv preprint 20X.822330000688),, 2023.
Jiaxuan Li, Lang Yu, and Allyson Ettinger. Counterfactual reasoning: Testing language models' understanding of hypothetical scenarios. arXiv preprint arXiv:2305.16572 2023a.
12

---

Published as a conference paper at ICLR 2025
Yingeong Li, Kartik Sreenivasan, Angeliki Giannou, Dimitris Papailiopoulos, and Samet Oymak. Dissecting chain-of- -f--uughhtth A study on compositional in-context learning of mlps. arXiv preprint 188.,,,305..886, 2023b.
Zhan Ling, Yunhao Fang, Xuanlin Li, Zhiao Huang, Mingu Lee, Roland Memisevic, and Hao Su. Deductive verification of chain-of-thought reasoning. arXiv preprini arXiv:2306.03877 2023.
Hanmeng Liu, Ruoxi Ning, Zhiyang Teng, Jian Liu, Qiji Zhou, and Yue Zhang. Evaluating the logical reasoning ability of chatgpt and gpt-4. arXiv preprint 2Xiv:2304.03439, 2023.
Tiedong Liu and Bryan Kian Hsiang Low. Goat: Fine-tuned Ilama outperforms gpt-4 arithmetic tasks. arXiv preprint vrXiv:2305.14201 2023.
Jieyi Long. Large language model guided tree-of-thought. arXiv preprini arXiv:2305.0829)) 2023.
Qing Lyu, Shreya Havaldar, Adam Stein, Li Zhang, Delip Rao, Eric Wong, Marianna Apidianaki, and Chris Callison-Burde Faithful Chain-of-thoughh reasoning, arXiv preprint a:X1v:2301.13379
2023.
Eran Malach. Auto-regressive next-token predictors are universal learners. arXiv preprint arXiv:2309.06997 06979, 2023.
Jordan Meadows, Marco Valentino, Damien Teney, and Andre Freitas. A symbolic framework for sys- tematic evaluation of mathematical reasoning with transformers. arXiv preprint arXiv:2305. 125663 2023.
Shentong Mo and Miao Xin. Tree uncertain thoughts reasoning for large language models, 2023.
Subhabrata Mukherjee, Arindam Mitra, Ganesh Jawahar, Sahaj Agarwal, Hamid Palangi, and Ahmed Awadallah. Orca: Progressive learning from complex explanation traces of gpt-4. arXiv preprint arXiv:2306.02707, 2023.
Nikita Nangia and Samuel R Bowman. Listops: diagnostic dataset for latent tree learning, arXiv preprint arXiv: 06028, 2018.
Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. Investigating the limitations of transformers with simple arithmetic tasks. arXiv preprint arXiv:2102. 13019, 2021.
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz. Maarten Bosma, David Luan, al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint 1rXiv:2112.00111 2021.
Gabriel Poesia, Kanishk Gandhi, Eric Zelikman, and Noah D Goodman. Certified reasoning with language models. arXiv preprint arXiv:2306.0403// 2023.
Ofir Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. ICLR 2012-2002,200 2022.
Ben Prystawski and Noah D Goodman. Why think step-by- bt-step? reasoning emerges from the locality of experience. 37th Conference on Neural Information Processing Systems (NeurIPS 2023), 2023.
Jingyuan Qi, Zhiyang Xu, Ying Shen, Minqian Liu, Di Jin, Qifan Wang, and Lifu Huang. The art of socratic questioning: Zero-shot multimodal reasoning with recursive thinking and self-questioning. arXiv preprint 2305 2tt::2335.449999 14999, 2023.
Jing Qian, Hong Wang, Zekun Li, Shiyang Li, and Xifeng Yan. Limitations of language models in arithmetic and symbolic induction. arXiv preprint arXiv:2208. 05051, 2022.
Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Bennani, Shane Legg, and Joel Veness. Randomized positional encodings boost length generalization of transformers. arXiv preprint arXiv:2305. /6843, 2023.
Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal analysis of chain-of- thothutght arXiv preprint arXiv:2210.0/244 2022.
13

---

Published as a conference paper at ICLR 2025
Rylan Schaeffer, Kateryna Pistunova, Samar Khanna, Sarthak Consul, and Sanmi Koyejo. Invalid logic, equivalent gains: The bizarreness of reasoning in language model prompting. arXiv preprint arXiv:2307.10573. 2023.
Zhihong Shao, Fei Huang, and Minlie Huang. Chaining simultaneous thoughts for numerical reasoning. arXiv preprint 2. 2022.
Jingyuan Selena She, Christopher Potts, Samuel R Bowman, and Atticus Geiger. Scone: Benchmark- ing negation reasoning in language models with fine-tuning and in-context learning. arXiv preprint arXiv:2305. 19426. 2023.
Alessandro Stolfo, Yonatan Belinkov, and Mrinmaya Sachan. Understanding arithmetic reasoning in language models using causal mediation analysis. arXiv preprint arXiv:2305. 2023.
Yutao Sun, Li Dong, Barun Patra, Shuming Ma, Shaohan Huang, Alon Benhaim, Vishrav Chaudhary, Xia Song, and Furu Wei. A length-extrapolatable transformer. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics, 2023.
Qingyu Tan, Hwee Tou Ng, and Lidong Bing. Towards benchmarking and improving the temporal reasoning capability of large language models. arXiv preprint arXiv:2306.0899 2023.
Xiaojuan Tang, Zilong Zheng, Jiaqi Li, Fanxu Meng, Song-Chul Zhu, Yitao Liang, and Muhan Zhang. Large language models are in-context semantic reasoners rather than symbolic reasoners. arXiv preprint arXiv:2305. 12.3305..48255 14825, 2023.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: benchmark for efficient transformers. Proceedings of ICLR2021, 2021.
Boshi Wang. Sewon Min, Xiang Deng, Jiaming Shen, You Wu, Luke Zettlemoyer, and Huan Sun. Towards understanding thain-of-thouglle afouhhught prompting: An empirical study of what matters. arXiv preprint arXi::22/2. 2022a.
Dingzirui Wang. Longxu Dou, Wenbin Zhang, Junyu Zeng, and Wanxiang Che. Exploring equa- tion as better intermediate meaning representation for numerical reasoning. arXiv preprint arXiv:2308. 10585, 2023a.
Jianing Wang, Qiushi Sun, Nuo Chen, Xiang Li, and Ming Gao. Boosting language models reasoning with Mhain-of-knowledee prompting. arXiv preprint arXiv:2306.06427, 2023b.
Peiyi Wang, Lei Li, Liang Chen, Feifan Song, Binghuai Lin, Yunbo Cao, Tianyu Liu, and Zhifang Sui. Making large language models better reasoners with alignment. arXiv preprint 4444442309.02144 2023c.
Tianduo Wang and Wei Lu. Learning multi-step reasoning by solving arithmetic tasks. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 1229-1233, 2023.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang. Aakanksha Chowdh- ery. and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint 2rXiv:2203./117/ 2022b.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V 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.
Noam Wies, Yoav Levine, and Amnon Shashua. Sub-task decomposition enables learning in sequence to sequence tasks. Proceddings of International Conference on Learning Representations (ICLR- 2023), 2023.
Zhaofeng Wu. Linlu Qiu, Alexis Ross, Ekin Akyürek, Boyuan Chen, Bailin Wang, Najoung Kim, Jacob Andreas, and Yoon Kim. Reasoning or reciting? exploring the capabilities and limitations of language models through counterfactual tasks. arXiv preprint arXiv:2307.02477 2023.
14

---

Published as a conference paper at ICLR 2025
Binfeng Xu, Zhiyuan Peng, Bowen Lei, Subhabrata Mukherjee, Yuchen Liu, and Dongkuan Xu. Rewoo: Decoupling reasoning from observations for efficient augmented language models. arXiv preprint arXiv:2305.18323, 2023a.
Fangzhi Xu, Qika Lin, Jiawei Han, Tianzhe Zhao, Jun Liu, and Erik Cambria. Are large language models really good logical reasoners? a comprehensive evaluation from deductive, inductive and abductive views. arXiv preprint arXiv:2.306.000 099441 2023b.
Mengjiao Sherry Yang, Dale Schuurmans, Pieter Abbeel, and Ofrr Nachum. Chain of thought imitation with procedure cloning. Advances in Neural Information Processing Systems, 35:36366- 36381, 2022.
Fanglong Yao, Changyuan Tian, Jintao Liu, Zequn Zhang, Qing Liu, Li Jin, Shuchao Li, Xiaoyu Li, and Xian Sun. Thinking like expert: Multimodal sypergraph-of-thoughle (hot) reasoning to boost foundation modals. arXiv preprint arXiv:2308.066 062007, 2023a.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305. 10601, 2023b.
Yao Yao, Zuchao Li, and Hai Zhao. Beyond chain-of-thought, effective graph-of-though reasoning in large language models. arXiv preprint arXiv:2305. 2023c.
Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling transformers with lego: synthetic reasoning task. arXiv preprint arXiv:2206.04301, 2022.
Yifan Zhang, Jingqin Yang, Yang Yuan, and Andrew Chi-Chih Yao. Cumulative reasoning with large language models. arXiv preprint arXiv:2308. 04377, 2023.
Hattie Zhou, Arwen Bradley, Etai Littwin Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms can transformers learn? study in length generalization. Proceedings of International Conference on Learning Representations (ICLR-202) R-2244,, 2024.
15

---

Published as a conference paper at ICLR 2025
Appendix
A RELATED EMPIRICAL WORK
Here we review the related empirical work, which includes the evaluation of LLMs in reasoning, chain-of-thoughts for reasoning, dealing with length generalization (LG) in learning reason, and dealing with LG in text generation.
Evaluations and limitations of LLMs in reasoning. Continuing with the discussion about evalua- tions of the reasoning capabilities of LLMs in Sec. we present a more extensive literature survey here. In general, evaluations conducted several latest LLMSs showed that they struggled with many reasoning tasks Gendron et al. ) Tang et al. (2023).
In Sec. 1 we discussed empirical works about LG Anil al. (2022) Dziri et al. (2023); ) Zhang et al. (202)). In these papers, the authors also tried to mitigate the problem through improved training and CoT Anil et al. (2022), improved prompting and fine-tuning of LLMs Zhang al. (2022). and
curriculum learning Abbe et al. (2023). An evaluation of the deductive reasoning capability of LLMs was also conducted in Prysstaskii & Goodman (2023), which shows that CoT helps improve the results, but does not achieve perfect accuracy. None of them studied the LG problem theoretically as we do. Below, we focus on surveying other empirical works. Many of them identified limitations of LLMs in solving different reasoning problems, but few have characterized the limitations in formal manner to facilitate theoretical investigation.
Meadows et al. (2023) created a dataset specifically for mathematical reasoning that can be perturbed.
They showed that perturbations of the tasks heavily affect the results, reducing F1 score from 97% to 17%, which suggests that inference is likely to be dominated by surface-level patterns unrelated to the deeper understanding of the mathematical operators. However, this evaluation was done using only DERTDevlin al.] (2018) based models, but not more recent I.LMs like ChatGPT and GPT4, Wu et al. (202)) used "counterfactual" tasks that deviate from the standard reasoning tasks to evaluate LLMs. It was found that the performance degrades substantially compared to the default conditions, which again suggests that while LLMs can perform reasoning to some extent, they often rely on narrow, transsreeeeeaeee procedures or surface patterns for solviso. A counterfactual- evaluation was also done in (Li et al. 2023a), which reached the same conclusion.
Liu et al. (2023) evaluated ChatGPT and GPT-4 on logical reasoning. The results showed that they do relatively well on well-known public domain datasets, but their performances drop substantially when newly released and outoo-ddistribution datasets are used. Xu et al. (2023b) also evaluated
LLMS using logical reasoning (deductive, inductive, abductive, and mixed-form reasoning) and gave pros and cons of LLMs. She et al. (003)) created a dataset for reasoning involving negations and evaluated LLMs and showed poor results. Ando et al. (2023) created dataset, originally designed for psychological experiments to assess human logical abilities in syllogistic reasoning. The authors examined three types of biases observed in human syllogistic reasoning: belief biases, conversion errors, and atmosphere effects. The evaluation on LLMs showed that they struggle with problems involving these biases too. Tan et al. (2023) created dataset evaluate L.MSs on temporal reasoning and showed some weaknesses of LLMs. They then proposed an approach to improve the results.
Chain of thoughts (CoT) and variants. Earlier prompting for solving reasoning problems using LLMs only states the question and the answer. They found that these two pieces of information are insufficient for LLMs to learn to perform effective reasoning. Then chain of thought (CoT) prompting (Wei et al., 2022) was proposed to improve the situation. CoT basically contains the detailed intermediate reasoning steps between the question and the answer for fine-tuning the LLMs. which significantly enhance I.MMs' reasoning capabilities Chung et al. (2022); Hsieh et al. (2023); Mukherjee et al. (2023); Fu al. (2023). Saparov & He (2022) created synthetic dataset generated based on first-order logic. They then parsed the generated CoT into symbolic proofs for formal analysis. It was shown that LLMS are capable of reasoning. The success of CoT has encouraged researchers to refine the technique and also propose variations of the technique.
For example, Chen et al. (023) proposed a metric to measure the effectiveness of CoT and a technique to improve CoT for vision- languae models. Wang et al. (2023c) studied using multiple reasoning paths and positive and negative answers to improve CoT reasoning. Zhang et al. (2023) proposed cumulative reasoning, which employs L.LMs in cumulative and iterative manner to emulate the
16

---

Published as a conference paper at ICLR 2025
human thought process. Qi et al. (023) proposed divide-and ann-con algorithm that simulates
the questionni and recursive thinking process of humans to improve COT. Wang & Lu (2023)
investigated how to incorporate into relatively small LMs the capabilities of multi-step reasoning
and CoT. |Wang et al. (202aa) found that even logically invalid CoT also helps to reason. This was Pirrennces,oesiiaa confirmed in (Schaeffer et al. 2023). To deal with unsound inferences. Poesia et al.] (2023) introduced a class of external tools for LLMs called guides that use states and incremental constraints to guide the
generation in reasoning. A related work on using external tools was done in Xu al. (2023a). Wang
et al. (2022b) improved CoT using multiple paths and consistency checks. Ling et al. (2023) studied
the verification of CoT. SSooffo et al. (2023) identified part of an LLM responsible for reasoning. In
different direction, Yang et al. (2022) argued that the prevailing approach to CoT prompt selection through trial and error is unsatisfactory. They then proposed a principled approach for multi-domain LLM CoT prompt selection.
Several researchers also broadened the CoT method and proposed the neural symbolic code prompt-
ing (Hu et al.] 2023b), program of thoughts (Chen et al. 2022] Cheng et al. 2023), tree-of-
thoughts Yao et al. 2023b Long 2023), rree-of-miee-tthugghe (Hu et al. 2023a), tree of uncertain
(Yao et al., 2023a), recursion of thoughts (eee & Kim 2023), chain of knowledge ( (Wang et al., (023b), chain of simultaneous thoughts (Shao
thoughts (Mo & Xin (023), hypergraph-of-thouee
let al. 2022), graph-of-thuuhht. (Yao et al. (203cc), faithful chain of thoughts (Lyu et al. (023).
and thought expansion Kim et al. (2023). Further, [Bi et al. (2023) proposed a complexity measure
and chose the optimal complexity to improve the program of thoughts (Chen et al., 2022). Wang
iet al. (2023a) proposed a method to improve the generation of equations from natural language questions as the intermediate step to answer the original question. [ao et al. (2023) combined CoT and Program-Aided Language Models (PAL) for improved reasoning.
Empirical work on LG in reasoning. Many empirical attempts have been made to modify the Transformer and/or learning biases to better solve the LG problem. Duan & Shi (2023) and Zhou et al. (2024) proposed some bias calibration methods to enable the model to learn suitable attention biases. However, their methods are still unable to solve addition perfectly or multiplication at all. [Jelassi et al.) (2023) proposed to add a small number of long sequences in the training to help solve long sequences, but still could not solve the multiplication problem. Chi et al. (2023) proposed Transformer variant with weight-sharing, a working memory, etc, to improve LG for regular languages. It can solve some problems but is still unable to deal with multiplication or addition. Different attention and new architectures are also proposed in Nangia & Bowman (2018); [Bowman et al. (2015);; (Tay et al. (202T); [Bowaa
Chowdhury & Caragea (2023a b). However, they don't 't use CoT but only the direct input and output in training. Their methods work on various text copying and list operations but don't solve these problems and do not work on more complex large-number addition and multiplication. Theoretically, learning to reason without intermediate steps (or CoT) in training is not learnable (Wies et al.) 2023 Feng et al. 2023). Our work needs no specialized architectures for different problems, but just a vanilla Transformer with relative position encoding.
B PROOFS
In the section, we provide proofs. For case of reading, we state the same property/theorem again. For simplicity, denote (r) as the set of all consistent contexts composed of r-length intervals. For simplicity, denote H,)(r) = [h|lhl S n, E Hr))).
Theorem B.1 (Thm. 3.1 a detailed description) Define V to be a metric space. Denote 0 E V to
be the empty token. Denote (w) - v2) to be the metric on V. 01, U2 E VV. For gN : V - [-1,1] 1). A N' > N, there exists infinitely many fx. : V + [-1.1] s.f. (i) (V1, UN O......) 9N (VI...., Un), (ii) fw is tipchitz-continune is Lipehitz-comtimuuus in the neighborhood of (vi,..., ).)
in the neighborhood of (Ui...., UN ... 0) if gN
[Proof.] Denote Vp:.]= (01..... UN). V let V + 1-1,1], 0 to be an e-Lipschitz continuous function i.e.
(u(v) - u(v')l < <cju -' 1'l.
There exists infinitely many u's, e.g. u(v) sign(/v - 01) c/v 0/0 a 1.
17

---

Published as a conference paper at ICLR 2025
Let
1,
u(UN+1) > 1- IN (V(VUNN))
[N+1(V
1,
u(UN+1) < <-1 -11-9N(Vp.N) (V(:N)))))
IN (V + u(UN+1),
else.
Since u(0)= 0, we have [X = IN (X(1.N))
Note that
((N+I(v(UN+1) fN- 1 (VIIN+
+ u((N+1)) (V)NN)
(9N (Vi1N)] + u(2/x+1))l
<19N(V -NN(V[LNN) |u(uN+)) - x((x41)
<VoN(V gN (V c/UN+1 - r/v+1l-
When yN is Lipschitz continuous in the neighborhood of VI:.N. we have
1gN (V(u.N)) AN (VLNN)) < <SN |M - Vianll
Therefore, (V JN+1 (V S (egN + +c)lVu-N++1 Misw+nl Thus, JN+1 is Lipschitz continuous in the neighborhood of (V[L:N),
By induction, A N' > N. there exist infinitely many fxr satisfying the condition (i) and (i).
Property B.2 (Prop.
3.4) h is a consistent context and h 3 h', then h' is also a consistent context.
[Proof.] Denote V = h c S} and Av (S) E S}. Let S E Fv., and the CoT step output S², Since h < h/ N' S implies h S which means S Fr. Since h is consistent, we have 5 [c(h, 89) = (h)) Since h < h' again, we have c(h, 50) = c(h'. 50), which implies S' ('[chh, (s)))) = S¹ ((h,,5)) (h). Therefore, for any 5 LN., ('(c(h', 55 always (h)) which means that h is also consistent.
Property B.3 (Prop. 3.5 If y is (n,r) then for Vn 2 n, Vr 2 r. y is (nl, consistent.
[Proof.) Since S (n, coonnsssttt, by definition, for 5 E S and S to be the CoT step output,
A1 < < |. there exists h4g E (r) s.t. c(hi), 50) = i. Denote hμj = (01 02 Alaaa since hig S there exists 1 S mı...., Mppll $ |S s.t. Smy Smy +r-1 1 aj. S j s [h
(i) For Vn' 2 n, since Ihaa S S n', which means hi E H.. (r), 9 is (n', -onsssssttnt..
(ii) For Vr 2 we construct hig E (r').. Let left = | [ and right = -
Let a' Smm- ....lefff................. Sm, ... Sm. +r-1+--1--0 --itihh 1 S j S |/qlle then it's not difficult to verify that the central element of a' is the central element of a,- Let h/4 (a1 al. .., m/ma)))
If Mig is inconsistent, the inconsistent instances containing h/g must also contain hn-- However, all central elements of hig and hig are the same, which contradicts the fact that hig is consistent. Therefore, Mi] is consistent, i.e. M/) (r")") is (n, -'consisttt
Combining (i) and (ii), y is (nn,,r")ccossitte
Theorem B.4 (Thm. 3.6 If a problem I is (n, consiissen, then there exists an n-layer Trans- former model for V S I with CoT process (59 (SD....,,') ST),, always have St+1 f(S)). t t< T.
[Proof.] Our key idea is to construct a Transformer model that the predicted CoT step output free from the length of the input problem instance, which thus achieves LG.
To finish our proof, we borrow lemmas from (Feng et al. 2023). We briefly state them below.
Lemma B.5 (LOOKUP, Lemma C.5 in (Feng et al., 2023) For any lookup table g [l....;
di + [1..., d. for Ve > there exists a lwoer MLP with GeLU activation f: d [1..... d s.I. (f()) g(x) < <e,x E ......d..
18

---

Published as a conference paper at ICLR 2025
Lemma B.6 (COPY. Lemma C.7 in (Feng et al., 2023)) For sequence I1, .1...., In with scores
Ti,..... Tn- denote 9, = Wi i kę = W V; W for V > 0. 4A > 0, the outpu of single head attention layer 01 ................................ On satisfies (o, Varg max, (r3 la: Ky <d)
< E, sis n.
Let's first formulate the structure H,, (r), which helps apply Lemma B.5 and Lemma B.6 in constructing the Transformer model. Given h (aq :2...... anj) and interval/sequeene denote the operation that concatenates a to the end of h as
(a1 02 .......... a)),a).
Let be arbitrary r-length interval. Denote
X(a) = (M) E (r),), M.
Note that the context in X(a) needn't be consistent. If (r) only contains contexts that have at most r-length intervals, which is finite set, then X(a) is also finite. For an arbitrary a, we could order h's in X(a) and denote
(a) (h1, h2...... ................................ (xoo)) {hl {o(a)) X(a).
where (a) represents the ordered Ma). Denote
NA = max (a)a)).
Let be an arbitrary context. Denote
B(h) = {al E3 E Hg 313.
Similarly, (hh could be ordered for each h, which is
(h) = (a1, 02, ()(1)) {al a E Bo(h)) = B(h).
Denote
No max [B(())).
Transformer Construction
Now we construct a Transformer model. Denote the input problem instance as 5 = 81 ... $|59| and
the CoT step output as S1 Since y is (n, r)-cossistent, for 1 s i S | there exists hpy E (r) s.t. c(hig, SD) and [ [1] = (haa))
For simplicity, denote the r-length interval that centers i
8
$+11"11-
Layer The 1st attention layer applies a padding mask with relative position encoding. For each i, the padding mask only exposes the r-length interval [[s]. Denote
hi = (ap)).
Then, after the 1st attention layer, each vector at position index contains
e; (a hgg)
We further make Ng copies of hig and write
P = (h.).....AA) hig), |pb) = Ng.
Then, each vector at position index contains
(ap) P(a);
where P(j contains N3 potential contexts, and we use P(J,. to represent the j-th context of P())-
The 1st feed-forward (FFD) layer maps dpg to )o(a))) Since {o(arg) = (fi,..., ......,,/xGon h) it
induces a lookup table
(a),,) + hj, 1 S [A(ag)] N₂.
19

---

Published as a conference paper at ICLR 2025
where h is represented by any form that could be distinguished from other h's (e.g. one-hot for [h| I n)). Therefore, by Lemma B.5 we could construct at most NA lookup tables that maps Alj) to Ao(a))) Then after the 1tt FFD layer, each vector at position index contains
6 = (a Ao(a)g))P())
Note that (ara)) contains N2 contexts, and we use {o(a))) to represent the j-th context of (a(aa))
Layer 2 to Layer n. The following layers share the same procedure. We describe the construction of the 2nd layer in detail, and the remaining layers are the same.
The 2nd attention layer has Ng Nx attention heads. For the 12)th head, let Wg. Wk, We be
q
W&& Pilli K Wge: )o(a))))2 Us = Wee; a(j]
Then it's not difficult to find that Lemma B.6 the matching set {4s, Kig < 6} has at most 1 element only when P(i]j (()) )12- By Lemma B.6 the (J1,12)-th head's output for position index
Pl],i atp Ph = Xo(aw)) (pp,5i
otherwise.
Among these N3 x N, heads, by definition of Ns, there exist at most N3 heads that concatenate a new interval. Denote the output of these heads as Pij again. Then, after the 2nd attention layer, P[{ is updated, and each vector of position index is
C2 = (a do >o(a:)))P())
The 2nd FFD layer verifies whether one of Pic] has already been a consistent context. For any |4] < is either in H (r) or not, which induces a lookup table -> {0, 1]. Therefore, by Lemma B.5 there exists Ng FFD layers verify whether each context of Pta has already been consistent. Then, after the 2nd FFD layer, each vector of position index i is
e = (a()) A (at)), P(j)- (4),
where [a]] has Ng boolean, and the j-th boolean indicates whether PØJ consistent. For the remaining Transformer layers, the attention layer updates P[ and the FFD layer updates [
Output After Transformer layers, since / is (n, rr.ccsssssstttt,, for each position index i, there must exist at least one consistent context h in pis]. i.e. at least one positive boolean in 1 Since (b)h) induces lookup table, by Lemma B.5
simply map the consistent context h into (hh)
by FFD layer. When f is consistent and c(h, S = i, by definition, (h)) is exactly [i]..
C A METHOD TO ACHIEVE (n, r) -CONSISTTENCY
We first introduce measure induced by Def. 3.3 that describes how far problem is from (n, r--
consistency. Let (a a2...., (qa) be a context. For problem instances < N, let Ja be measure of ht' 10 Let (()(h)(( be the probability density (h) conditioned on h, where (h)) is
the central element of the next CoTT step of the anchor interval of h (Def. 3.3 (v)). Denote & as the entropy function and E Epp(vi (h)()) the entropy (())h)))). Define
Q(N:n,r) = f (armmr))=((((((()))p)))) ((p(((h)l)))
Note that when problem is (),rr)-consiiei conssssten by definition, h, (()(())))) is Dirac delta function. Therefore, E(p(v(h))k) 0 and ((N:n.r) = O. It's not difficult to see that a problem is (n,r)- consistent if and only if lim limssup O(N;; N/N; = 0.
Therefore, when problem is not (n, conssistttt i.e.. 2(N;n,r) > 0. there exists method to transform into (n, rcconsistnttt When Q(N;n, r) > there exists h s.t. (pp(((h)))) 0. For
1F..g let to be uniform measure over all problem instances < N and let to he uniform measure of all context given problem instance S. Then (h) (()))))(SS)d defines measure of h's.
20

---

Published as a conference paper at ICLR 2025
this h, let B) be separation of the vocabulary, i.. AUB = V and An B = 0. It's obvious that
(h)(,, (h) e A)) + ((p(((h))) (()) e B)) (p(())))))
(2)
where holds iff [b(b)]b} n A 0 or (w(h)))] nB D. Therefore, whenever [(v( > there always exists separation s.t. ()) decreases strictly. Therefore, we could add
tag (A, h) for (h) E and a tag (B, h) for (h) E B. Repeating adding tags for h will finally decrease E(p(v(())))) (1)) to O. Repeating dealing with all possible h with ((p((()))))) > 0 will finally decrease (N; n, to O.
This method adds different tags for different hss. This is inefficient for most problems, as many tags could have been shared among f's. Listing all tags for all hts without reduction makes this method computationally intractable. It's unknown whether there exists more computationally efficient method to transform a problem into (n, conssstttn
D SUPPLEMENTARY EXPERIMENTS
In addition the main results reported in Fig. 1 add more tests with longer lengths to stress test the system. Three more test settings are added, i.e. LG Test 6, 7, and 8. The full set of test settings and their corresponding results are given in Table and Table 3 respectively.
Table 2: Experimental settings. The settings from Train Length LG Test 5 have already been given in Table I
LG Test 6, 7, and 8 are additional settings with longer lengths.
Train Length
LG
T
LG Test
LG Test
LG Test
LG Test
LG Test
LG Test 8
anthmetic F.
[3,
20)
L [3,
3.400
L 3. 50)
I 3 80)
L 100;
L p.. 200)
C (3.500)
[3. 1000)
parity-[2] [2)
L e
Le (1,30)
Le 1.40)
Le 1.50)
Le [..00
Le (1,00
Le [1. 200)
Le [1,500)
L [L. 10000)
addision- (2)
L e
(1.9)
Le 1,10
Le 1.11)
[1.00
LE 1.211
Le (1.31)
L L (1,4))
L 51)
muhiplication-11
I. (1
Lg 1.8)
1.99
[1.10)
LC 1.11)
L (1,21)
L 11,
division: [12]
Le (L.6)
(L.))
Le 1.8)
LE Le(.))
(.11)
[L.66)
(1,21)
(1,26)
! Notice that LG Test 5 is 100%, but LG Test 2, 3, and 4 are not. This is possible because each experiment randomly generates its training and test data.
Table 3: Experimental results. The results up to LG Test 5 have been shown in Fig.
Accuracy (9)
Train Length
LG Test
LG Test
LG Test
LG Test 4
LG Test
LG Test
LG Test 7
LG Test
artthmetic F;
parity-[2] [2]
10000
100.0
100.0
100.0
100..)
100.0
100.0
100.0
100.0
addition-[2] [2]
10000
100.0
100.0
100.0
100.0
100.0
100.0
90.0
77.5
mulippicatiioo(111
100.0
100.0
100.0
100.0
100.0
100.0
98.9
70.0
61.4
division- [12]
100.0
99.8
100.0
81.4
We can observe that although these problems are (n, conssiseent they still struggle to achieve perfect LG for extremely long lengths. The key reason is due to the "dense" property of the attention layer, which involves noise beyond the desired n intervals as the length increases. Fig, gives an example show the dilution of the probability distribution.
E COMPUTING RESOURCES
Each experiment is running on a machine with 8 CPU cores. Each experiment takes less than 24 hours.
F COT EXAMPLES
Fig. ssowws some examples of CoT schemes of the experimental reasoning problems. Note that the parity problem uses '?' in the second line of the input and output to represent the position to be calculated next, 1 to represent odd, and 0 to represent even. The first line in the input is the input bit sequence. The addition problems use "?' to represent being carried from the right and 's" to
represent 1 being carried from the right. In all problems, # is equivalent x. We use # instead of x for ease of aligning chars. The orange lines the output, which are for easy reading, are not predicted in practice, they are identical to lines in the input.
Table lists all the indicator tokens used in multiplication-LLL [11]. Table 5 all the indicator tokens used division-[12].
21

---

Published as a conference paper at ICLR 2025
Figure 2: An example of diluted probability distribution. We present the attention probability where the query 13456678,, respectively. The increased number
distribution on the first CoT step of 123 x 789/123456789/ 12410/2225526615556665220 is 3 and the key/value is of tokens takes attention away from the desired tokens, which degrades the performance.
Table 4: Descriptions of indicator tokens for multiplication-(11]
Indicator
Dynamic
Description
do move do not move
start and of
start and end of b
moves back move left; when reaches J moves back to move
digit multiply
J
digit of 5 to multiply
aligned
distance between F and the same as distance between and
K
left; when reaches F, moves back T
indicator of output position index
c
move left: ? appears after multiplication appear when addition is done
carries D and carries addition
# indicates CoT step be multiplication
Table Descriptions of indicator tokens for division-[12].
Indicator
Dynamic
Description
E.S
and of
not move
start and end
move right when J moves back to left; when reaches subtmationn fails, back move right when moves back to
digit of a to subtract
he subtract
T.T
start and K; T is alignod with
distance between and the same distance between and
K
left: when K reaches subtraction fuils, moves back T
indicator of outpoi position index
appear when subtraction
22

---

Published as a conference paper at ICLR 2025
Figure 3: Examples of the CoT schemes in Sec. 4 Note that the figure covers multiple pages. multiplication-(11 and division-[12] appear in the next three pages.
(a) arithmetic in prime field F: (nots, this is normal arithmetic)
parity-121
addition-[1]
Taput(O]:
1011
Teput[0]: 285-9805-
Input(0): +0+44 -(2-3*)) (4+
Ourpur[0]: 285-9805-90 50
Outpun(Oj: -(2- 4
Outpen(O]:
Ingot[1]: 285-9805-
Input(1]: (4-(2-4))*
12
Ourput(1]: 285-9805--00 190
Outpur[1]: (4. 5 +
Iopui(1]:
1011
Inpu[2]] 285-1805= (X0
Inpul(2]: (4-5)*
17
Ouiput[2]: 285-9805-9090
Outpur[]]: 6 +4
Outpui[1]:
117
Ingut[3]: 285-9805- c090
Ingun[3]: 6
Ourput(3]:
285-9805-10000
Ourpur[3]: [3]:
Input[2]]
112
Outpui[2]:
(d) addition-|2]
110?
Ingut(0]:
285 + 9805
Input(0]: 1+3-7
Input[3]:
Output[O]:
1+3=1+?
1107
Outpu:[O]:
285 9805
Outpui(3):
1013
J K
Inpu([1]: 1*3-1+?
Output[1]:
1+3-1+1+?
1011
Inpun[1]:
Input(2]:
1+3-1+147
Outpu[[]]:
285 9805
790
Output(2]: 1+3=1+14+
Input[3]: 1+3-1+1+1
Ingut[2]:
285 9805 290
Output[3]:
1*3-2+1
Input[4]: 1*3-2+1
Output[3]:
9805
$090
Ourpon[4]: 1+3=3
Input(3]:
Ouspu:(3]:
285 9805 10090
23

---

Published as a conference paper at ICLR 2025
(9) muttiplication(111
bpett:
Depat0)
Oxpatt]
K
1:00
Oxys(7)
24

---

Published as a conference paper at ICLR 2025
(g) division-[12] ()
Iqet2
Oxpaf3]
kpdff)
25

---

Published as a conference paper at ICLR 2025
division- [12] (i)
IOKERS
Oxpating
Oxpe((]]]
(xpx(11)
lqe(113
Ocpett)
Oxpall11
26


Reviews:
[{"review_id": "TxexX0bIb6", "reviewer": "Reviewer_F4Li", "summary": "This paper proposes a framework for studying the length generalization ability of scratchpad/chain-of-though (CoT) methods for reasoning problems such as arithmetic. More precisely, a condition, $(n, r)-consistency$, has been proposed such that if CoT satisfies this property, one can design a model capable of length generalization (an approximation/expressivity result). The paper further provides experimental evidence showing that the proposed CoTs are indeed learnable.", "questions": "- From what I understand from Appendix D, we see that output[k] is not always exactly equal to input[k+1] (e.g., in the addition examples). I think this is some sort of processing that is not necessarily generalizable to other tasks because it uses the knowledge of the task too much (I personally see it an engineering hack). Is there a way to avoid that and be more agnostic towards the task?\n- Similar to the concern above, In Appendix D, we see some orange lines that are not predicted by the model and are manually inserted. I think this again reduces the learning part of the paper and is an engineering trick. Can it be avoided?\n- I'm not sure if I completely understand how the padding works. When you pad, you still have blank tokens at the start and end of the sequence. However, they are not the middle of any interval. So how are they predicted? Also are the padding tokens provided for all the examples in Appendix D?\n- In experiments, the length generalization ability is tried on different lengths and for all of them we see 100% performance. So I wonder what's the point that we see some reduction in the performance? Why haven't you tested the length generalization ability on longer sequences?\n- The experiments are done with specialized Transformers. I wonder what would be the length generalization performance if CoT steps were learned by a typical model, e.g., GPT2 or llama?\n\nMinor feedbacks: \n- From what I understand, it's not important where the intervals other than the anchor interval are located, is that right? I think it would be  nice if this is further clarified in the paper. \n- I think Theorem 3.1 is doing more harm than good. I think the statement that is saying \"we have infinite continuations\" is more or less intuitive. Further, I think modeling discrete token space with continuous intervals is not justified. Also, why is Lipschitz assumption on these intervals a reasonable property? (and in that case what are the Lipschitz constants?) By default, we expect the distance of the tokens to be more or less the same, however, the Lipschitz assumption goes hand in hand with the Euclidean distance on the intervals which is problematic. For example, if tokens A, B, C correspond to points -1, 0, 1 on the interval. The Lipschitz assumption implies that the semantic distance between (A, B), (B, C) is smaller than (A,C). So I think the Lipschitz property and the use of continuous intervals in this Theorem is unjustified. I would really suggest to use a simpler theorem on discrete token space.\n- The abstract and intro imply that authors have found a necessity condition for length generalization and thus I think they should be revised. \n- I find the proof sketch part very interesting, and I'd suggest authors to further elaborate on it. (In that case, you may want to move some of the experiment details to the appendix).", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper tackles the important problem of length generalization on reasoning tasks. It provides a condition for CoTs such that if that condition is satisfied length generalization becomes potentially possible. Theoretical results on the expressively and empirical results on learning are provided in the support of that condition. \n- The experimental results seem very interesting and strong (e.g., division is a newly considered task) although there are concerns (see below). \n- The multi-line scratchpad/CoT and its implementation are interesting.", "weaknesses": "- One of the main weaknesses is the modeling assumption. Generally, the CoT setting works as follows that when we have given $S_0$ as input to the language model (LM), the LM would generate a sequence of thoughts, $S_1, S_2, \\ldots, S_T$ that would solve the task (answer is often in $S_T$). However, the modeling in this paper is that we give $S_0$ to the model and get $S_1$ then we give $S_1$ as input to the model to get $S_2$ and so on. So instead of $model(S_0)=S_1, S_2, \\ldots, S_T$ we have $model(S_i)=S_{i+1}$. I think this modeling is not a significant issue, it is just an unconventional way (which may work better that the the conventional way) that should be properly acknowledged, explained, and clarified throughout the paper. Currently the paper doesn't acknowledge this difference with normal CoT methods. Further, this problem becomes more significant in two ways:\n     - The model doesn't learn the termination condition. In other words, it's not the model that understands $model(S_{T-1})=S_{T}$ is the final step and it shouldn't compute $model(S_T)$, but this is manually controlled by the user. \n     - It seems some further processing are done on the inputs and outputs. In particular, it seems input[k+1] is not exactly output[k]. \n\nAll of these processings and manual handlings seem like engineering hacks which would not generalize to other problems. (Although length generalization on tasks such as addition are important as evaluation metrics, however, we are more generally looking for approaches that would generalize to other problems as well -- in particular to problems that we have less control over the data.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rfYwxjcZkD", "reviewer": "Reviewer_sCy1", "summary": "**Update after rebuttal:** While some of my criticism remains, the authors have clarified some misunderstandings and questions I have had, and have significantly sharpened the focus of the paper (defining a problem class for which LG can be theoretically guaranteed; as well as putting the emphasis on the empirical side). Accordingly, I have raised my score from a 5 to a 6.\n\n---\n\nThis paper investigates the challenge of length generalization with transformers. The paper first points out the well-known fact that the induction problem has no correct solution. For length generalization, additional assumptions are thus necessary. The paper proposes to restrict length generalization to a class of problems that can be decomposed into a set of (n) repeated subproblems that only require local context (of length r) around a set of anchor positions: (n,r) consistency. This “necessary” condition (which is a bit of a tautology because the problem class was defined according to the necessary condition) is then shown to be sufficient for the problem to be solved with transformers in theory (ignoring questions around learnability and model capacity, etc.). As the paper notes in 3.5, there is no general method to implement the process that decomposes an original length generalization problem into a “Chain-of-Thought” (CoT) formulation that can be solved by sequential execution of a number of local subproblems. But the paper correctly argues that if solving this problem reformulation such that (n,r) consistency can be ensured, transformers should suffice in principle to solve the modified problem. (n,r) consistency can thus be seen as a guiding target for CoT formulations. A small set of empirical results confirms the relevance of the theoretical result in practice. For training the CoT decomposition of the original problem is done by manually designed, problem specific algorithms, and transformers are trained to execute these algorithms of stepwise rewriting of the problem and simultaneously solving suitable subproblems during rewriting.", "questions": "**Improvements** (that would make me raise my score, but may not be possible within the short rebuttal time)\n\n1. A significant overhaul / rewrite to emphasize that the main contribution is not a theory of length generalization and identification of a novel root cause (the root cause is well known in machine learning, mathematics and philosophy), but a definition of a problem class that has favorable properties w.r.t. length generalization built in, and these properties can be exploited by transformers.\n2. If the focus of a major revision lies on the theory (though I personally would recommend leaning more towards the empirical side), then the problem class of (n,r) consistent problems needs to be better understood theoretically. E.g., how does it relate to commonly known complexity classes such as regular languages or $TC^0$? Is this class likely to be complete, i.e., all problems where transformers can length generalize must be (n,r) consistent (which I personally doubt), and if not, what are counterexamples?\n3. Strengthen the point of how the current theoretical understanding can help design learnable CoT schemes that generalize. The empirical examples in the paper are good, but how much did the theoretical understanding contribute? Could it help to come up with a less manual process or procedure to design CoT schemes? How? Currently, the manual decomposition / rewriting of the original problem does all the heavy lifting.\n4. The notation in Sec. 3.3 is quite tedious to parse - a figure would really help (probably all of Def. 3.2 could easily be shown graphically).\n5. Theorem 3.6 is fine (there always exists a transformer that can solve the CoT problem), but what about learnability (via SGD)? How do we find that transformer in practice? Is that always easy or only sometimes, and if so, when?\n\n\n**Questions:**\n\n1. What can be said theoretically about the complexity of (n,r) consistent CoT schemes? How does the number of CoT steps scale with problem complexity and problem length (e.g. the CoT scheme for multiplication seems to not scale very well).\n2. How would one use the insights from the paper to design reasoning systems that can reason in many settings, or even at LLM / Frontier model scale? Currently the CoT format for each task is very different, and it is unclear that there is any synergy between learning different tasks simultaneously with a single model. The very different CoT schemes may even hurt performance when learning many tasks simultaneously.\n3. L 186: Why is it theoretically important that the lengths are the same?\n4. How can one in general determine if a problem is (n,r) consistent? Only by finding a valid decomposition (CoT scheme)? How does one find n and r in practice?\n\n\n**Minor comments:**\n1. L 133: “Note that we do not define CoT formally” - this is a weakness for a theory paper and should ideally be fixed.\n2. L 136 (Problem statement): The text says “performs well“ which is very informal, whereas the mathematical statement seems to say “performs perfectly in all steps (for any deterministic reasoning problem)”. This discrepancy needs to be fixed - either performing well means always the correct $S^{T+1}$, or there is some other error function that measures how well the model performs. Since this is a theory paper, being precise is important.\n3. L 170 says that “with only the continuity bias […] it is almost impossible to predict”. The continuity has never been formulated. I would rather rephrase this to: “without any complexity penalty (such as forms of continuity bias, (n,r) consistency, or forms of Occam’s razor) it is impossible to prefer one continuation over any other, and thus generalizing correctly would rely entirely on chance (with vanishingly small probability as the gap between $N$ and $N’$ grows”.\n4. L536-539: I would have liked to see that much earlier in the paper (e.g., around L176).\n5. L 251: $s_{j,l}$ and $s_{j,r}$ swapped.\n6. L 347: “We use 4 classes” - should be 5.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Timely and important problem: length generalization even on simple tasks is a regime where transformers struggle.\n* Definition of an interesting class of length generalization problems: the class of problems where a decomposition with (n,r) consistency is possible. These problems match well onto, and are probably solvable (in theory) by, transformers.\n* Good empirical results on historically challenging problems like parity, addition, multiplication and division.", "weaknesses": "* The CoT decomposition does most of the heavy lifting - but it is done manually. The paper makes very little progress here, except defining (n,r) consistency as a guiding principle to aim for (but with no systematic process to get there, and no theoretical understanding of how the class of (n,r) consistent decomposable problems relates to general function and complexity classes (e.g., regular languages).\n* Writing throughout most of the manuscript makes claims that are either too grand or not sharp enough, which makes the first part of the paper a bit misleading. For example, (n,r) consistency is not *necessary* to solve length generalization in general. There are loads of other approaches that have been proposed before and that are theoretically very well understood - they typically use different biases, most commonly low-complexity biases, to answer the induction problem (such as Solomonoff Induction or Bayesian inference for example). What is correct is that when restricting to problems that allow for a (n,r) consistent decomposition, length generalization can be solved uniquely without requiring additional biases. I will be more specific in the Questions section. \n* Learnability and generalization with transformers in practice remain unclear (bounded capacity, finite data, SGD). The CoT decomposition works on the simple examples shown, but it is not clear whether this would hold at scale (the number of (n,r) consistent CoT steps may scale very badly for some problems); or even how to do this - e.g., how would one train a transformer that can solve all tasks in the paper simultaneously. How would one go about eventually reaching the scale of modern frontier models?\n\n**Verdict**\nOverall I think the research in the paper is on a good track, but the current theoretical understanding and presentation is lacking a bit. Large parts of the paper sound like the paper makes a fundamental theoretical contribution that solves length generalization once and for all (such as “a theorem to show the LG problem’s root cause”, or a ”necessary [theoretical condition] to resolve it.” ). Actually the “root cause” (theorem (3.1)) simply points out the very well known and much discussed fact that the induction problem (of which length generalization is one instance) has no correct solution (unlike logical deduction) only plausible or highly likely continuations, and that additional inductive biases are needed (commonly used are low-complexity biases such as Occam’s razor, formalised in many different ways). The “necessary” condition introduced in Sec. 3 is nothing but a restriction to a subset of length generalization problems (the condition is not necessary in general, it simply defines a problem class for which a solution strategy and uniqueness of the solution can be proven). I would strongly prefer if the paper were rewritten to acknowledge this (from the very beginning and throughout), by saying: here is a formal definition of a problem class for which length generalization with transformers can be proved theoretically, and empirical results align well with the theory. For a theory paper I would then like to see more theoretical understanding of this problem class; which length generalization problems can be massaged to fall into this class, and what can be said about the process to do this (can we bound the number of CoT steps in a meaningful way, how does the problem class relate to other well known complexity classes, etc). Alternatively the theory can be left lightweight as is, and the empirical part could be strengthened - but since the CoT decompositions must be manually designed, this is quite tedious. Overall I think the work is ready for presentation and discussion (and notions similar to (n,r) consistency have popped up recently in other works regarding length generalization), but the best format currently, I think, is a workshop. This is not meant to discourage the authors (after all the empirical results on addition, parity, and multiplication are nice - but they are mainly due to handcrafting), but I think a much stronger version of the manuscript is possible with a bit more time and a major revision.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kHNaeot8LY", "reviewer": "Reviewer_AyZa", "summary": "This paper addresses the problem of generalizing chain-of-thought (CoT) reasoning to arbitrary lengths, which is called Length Generalization (LG). The previous work has only shown the effective generalization of CoT over inputs of the same length. \nThe paper first gives a theorem characterizing the root cause of the LG problem - namely there exist infinitely many Lipschitz-continuous extensions of a Lipschitz-continuous function g over N inputs. This implies that LG cannot be achieved in general without some restrictions. It then proves a condition called (n-r) consistency under which LG can be achieved. The paper gives experimental results that show that algorithms for parity, addition, multiplication, and division are learned by transformers with CoT representations that satisfy (n-r)-consistency.", "questions": "How robust is the approach to errors in the steps of the CoT? Can you conduct some experiments to study this and report in the final paper?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "LG is an important problem that demonstrates the power of transformers to learn procedures over inputs of arbitrary size. \n\nThe paper presents a sound theory that characterizes the root cause of the problem and gives a sufficient condition for its solution. \n\nThe experimental results are compelling and illustrate the successes and failures of generalization that depend on the (n,r)-consistency.", "weaknesses": "The CoT training seems to be quite tedious for complex procedures such as multiplication. \n\nTypo:Def 3. ... are r-length.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)