Recursion of Thought: Divide and Conquer Reasoning with Language Models
Authors: Soochan Lee
Gunhee Kim
Venue: Submitted to ICLR 2023 (2023)
Keywords: reasoning
language models
chain of thought

Abstract: With the recent advances in language models, attempts are being made to apply them to solving multi-step reasoning problems. A major breakthrough in this line of research is to let language models generate intermediate steps, often called Chain of Thought (CoT), before producing a final answer. However, language models have an upper bound on the context size, i.e., the number of input tokens, such as 2048 for the recent GPT-3 and PaLM. Although several thousand tokens are enough to handle various tasks, solving more complex reasoning tasks can require orders of magnitude more tokens. Therefore, the context limit imposes a fundamental limit on the model's reasoning capability. Inspired by human's incredible reasoning ability based on abstraction and recursion, we propose Recursion of Thought (RoT) as a model-agnostic framework with the novel paradigm of teaching a language model to divide and conquer complex problems by recursively creating multiple contexts. Since RoT casts the context-related operations as tokens, a language model can trigger the recursion operations by simply producing the corresponding tokens. On multiple arithmetic and algorithmic reasoning tasks, we demonstrate that RoT dramatically improves the recent large-scale language model GPT-3 to solve extremely complex problems. Moreover, RoT can make tiny, randomly initialized Transformers or LSTMs to solve problems that even humans find daunting.

Under review as a conference paper at ICLR 2023
RECURSION OF THOUGHT: DIVIDE AND CONQUER REASONING WITH LANGUAGE MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
With the recent advances in language models, attempts are being made to apply them to solving multi-step reasoning problems. A major breakthrough this line of research is to let language models generate intermediate steps, often called Chain of Thought (CoT), before producing a final answer. However, language models have upper bound the context size, i.e., the number of input tokens, such as 2048 for the recent GPT-3 and Pa Although several thousand tokens are enough to handle various tasks, solving more complex reasoning tasks require orders of magnitude more tokens. Therefore, the context limit imposes a fundamental limit on the model's reasoning capability. Inspired by human's in- credible reasoning ability based on abstraction and recursion, we propose Recur- sion of Thought (RoT) as a -odel--ggostic framework with the novel paradigm of teaching a language model to divide and conquer complex problems by recur- sively creating multiple contexts. Since RoT casts the context-related operations as tokens, a language model can trigger the recursion operations by simply produc- ing the corresponding tokens. On multiple arithmetic and algorithmic reasoning tasks, we demonstrate that RoT dramatically improves the recent large-scale lan- guage model GPT-3 to solve extremely complex problems. Moreover, RoT can make tiny, randomly initialized Transformers or LSTMs to solve problems that even humans find daunting.
INTRODUCTION
Recently, language models (LMs) have become a prominant direction to solve reasoning. Given question sequence, the models are tasked to predict the following answer sequence. One recent line of research for reasoning with LMs is chain of thought (CoT) generation (Nye et al. 2021 Wei et al.) 2022 Kojima et al. 2022] Lewkowyez et al.) 2022). In CoT generation, complex reasoning problems solved by generating intermediate reasoning steps, chain of thought, before producing the final answer. Directly answering a question would require a model to fully solve the problem in single forward pass, meaning the range of solvable problems is severely limited by the model's capacity. On the other hand, generating CoT before the answer allows the problem's 's complexity to be spread across the CoT, making each token generation more straightforward given the previous tokens. This is closer to how humans solve complex problems, as we think step by step, instead of producing an answer reflexively.
Although CoT seems promising, there is a critical issue that significantly limits its utility: the ef- fective context size of sequence models cannot grow unbounded. In this work, context refers the set of input tokens that model is conditioned on when generating output. Practically, all sequence models have limit on the maximum context length due to various reasons. For instance, Trans- formers (Vaswani et al., (017) suffer from a quadratic computational cost on the context length, and RNNs (Hochreiter & Schmidhuber) 1997) struggle with long-term dependency modeling. Therefore, even the ofate-of-the-art language models, such as GPT-3 (rrwnn et al. 2020) and PaLM (Chowd-) hery et al. 2022). limit the maximum context length by up to 2048 tokens. However, the length of intermediate steps can grow rapidly with the problem's complexity and exceeds the context limit. Since CoT can handle a problem only if the process of solving fits into single context, the range of problems that CoT can handle is severely constrained by the context limit. This issue must be

---

Under review as a conference paper at ICLR 2023
overcome to solve more challenging and useful reasoning problems, whose solutions may require millions of tokens.
Humans can handle this issue by using abstraction and recursion. We divide large problem into smaller subproblems and focus on each subproblem while solving it, instead of considering the entire problem at every step. We can further subdivide subproblem into even smaller subproblems. With this intuition, we propose Recursion of Thought (Ro'T) as a model-agnostic framework for recursively solving multi-step reasoning problems. The key feature of RoT is grant the model the ability to recursively create and utilize multiple contexts for subproblems. We achieve this feat by introducing several special tokens that a model can output to control its context. During inference, the model recursively solves the problems by producing appropriate tokens at the right time. Moreover, RoT' supports tail recursion, which enables general computation with an indefinitely long chain of recursion.
We demonstrate RoT on four basic arithmetic operations (addition, subtraction, multiplication, and division) and four algorithmic tasks (longest common subsequence, longest palindromic subse- quence, 0-1 knapsack, and matrix chain multiplication) to show its generality. Without any task- specific component, such as calculator, all tasks are formulated autoregressive sequence model- ing problems. These tasks require a model to generalize by just seeing a tiny fraction of the problem space since the space is combinatorially large. For example, even in simple arithmetic operations, two 6-digit operands result in one trillion possible combinations. Hence, we evaluate whether a model understands the underlying rules, instead of brute force memorization. In our experiments, the range of problems that CoT can handle is seriously constrained by the context limit. On the other hand, RoT leads language models achieve near perfect accuracy, even if the problem size increases to the extreme, where solving one problem requires producing hundreds of thousands of tokens. Moreover, the dramatic improvement not limited to large pre-trained language models like GPT-3. RoT can make tiny, randomly initialized Transformers or LSTMs perform extremely complex reasoning.
The key messages of this work are summarized as follows:
The reasoning capability of current language models is seriously constrained by the maxi- mum length of single context.
Our Recursion of Thought (RoT) unleashes the reasoning capability of language models by letting them recursively create and utilize multiple contexts of subproblems, following the principle of divide and conquer.
In the supplementary file, we provide the source code to fully reproduce our experiments.
2 RELATED WORK
Chain of Thought. Among several prior works on applying language models to reasoning. Scratch- pad (Nye et al. 2021) may be the most closely related to work. It is the first approach to fine-tune language models to produce CoT before generating an answer. It demonstrates its effectiveness on 8- 8-digit addition, polynomial evaluation, and Python program execution. It also mentions the con- fined context size as a major limitation to be overcome. In order to unlock the full potential of Scratchpad, the authors argue that Transformers should be improved to allow greater context sizes. We solve this exact problem from a completely different perspective, i.e., using multiple contexts to divide-and-conuuee context limit. More recently, it has been found that sufficiently large pre-trained language models can be induced produce CoT, by simply tuning the prompt. For instance, CoT prompting (Wei et al. 2022) adds several QA exemplars with CoT before the main question, encouraging the model to generate final answers in the similar manner. Kojima et al. (2022)'s ' prompting is even simpler; after a question, they start the answer with "Let's think step by step." and then let the model finish the rest. Even without fine-tuning, these methods significantly improve the reasoning accuracy of language models. Minerva (Lewkowycz et al. (022) utilizes these prompting techniques with specially curated scientific pre-training dataset to achieve remarkable results on various reasoning benchmarks. However, all of these works are still limited by the maximum context size.
Our approach is more practical and scalable, compared increasing the
2

---

Under review as a conference paper at ICLR 2023
Neural Programmerr-nterpped (NPI. Unlike language models, NPI (Reed & de Freitas 2016) interacts with its environment through a series of program execution. It consists of an LSTM core, an encoder for each domain, and memory of program embeddings. At every time step, the LSTM core takes a program embedding, arguments, and an observation of its environment to produce the next program embedding and corresponding arguments. Cai al. (2017) combine NPI with recursion and show that recursion plays a critical role in generalization. Since NPI requires full execution traces for training, there are multiple works relax this requirement using reinforcement learning Li et al. 2017 Fox et al. 2018 Pierrot et al. 2019).
System 1 Approaches for Reasoning, Kahneman (2013) classifies cognitive tasks into two cate- gories: System I and System 2. System refers to fast and reflexive thinking. while System 2 refers to sequential reasoning. is hard to define strict criteria to distinguish between System and Sys- tem 2 approaches. We classify a model as System if it directly outputs an answer, while System generates its process, as well. In that sense, RoT, CoT and NPI are System 2 approaches, while there have been various System approaches to solve symbolic reasoning. Zaremba & Sutskever (2014) train LSTMs with curriculum learning to solve integer addition up to nine digits. Kaiser & Sutskever (016)) propose convolutional architecture called Neural GPU that performs binary addition and multiplication. Trained on 20-bit problems, this model operates like a digital circuit for the arithmetic operations, which can generalize up to 2,000 bits. Similarly, Yan al. (2020) solve 8-bit binary addition and 12-bit binary multiplication with Transformers. If Neural GPUs are like digital circuits, Neural Arithmetic Logic Units (Trask et al., 2018) are like analog circuits for arithmetic. They represent numerical quantities with the activation values of neural networks and design clever architecture for arithmetic operations. Although these System I approaches fall be- hind System 2 methods in terms of generality, they can be highly efficient in specific domains. We believe future systems will often be a hybrid of System and System 2, harnessing the advantages of both types.
3 RECURSION OF THOUGHT
The main idea of Recursion Thoughi (RoT) is to let the model recursively solve small subproblems in separate contexts, keeping each reasoning step simple and learnable. Our RoT model-agnostic and general enough to be combined with any kind of sequence model that supports autoregressive generation. The only requirement is that the model should be able to infer p(x;+1 the proba- bility of the next token 21+1 given sequence X1:: [21] ...; r.,; Therefore, sequence models such as Transformers, RNNs, or more advanced ones can all be used in the RoT framework. RoT teaches sequence model to solve problem using the divide and conquer paradigm in supervised man- ner. That is, we assume that ground truths for the intermediate steps of how to recurse are readily available, as in Scratchpad (Nye et al. 202T) or NPI (Reed & de Freitas 2016).
For better understanding, we discuss RoT in the reverse order of the pipeline. In $3.1 we first describe how to perform RoT inference with fully trained model. In $3.2 we introduce the training process. Finally, in |3.3] we discuss how to recursively divide the problems and build the training data for intermediate steps automatically.
3.1 INFERENCE
Recursion of Thought (RoT) grants language model the ability to control the recursion process. For basic recursion control, we first introduce the following special tokens: GO, STOP, and THINK. GO and STOP respectively mark the start and end of a problem sequence. They can be nested inside another STOP pair to indicate a subproblem. THINK initiates a recursion procedure. RoT teaches model how to use these tokens so that it can perform fivide-anddconquer problem solving. We formulate each inference context of a QA problem, denoted X, as the following concatenation:
X = [Q: sub,1
aub.1
Sub..N sub..N AA]
where Q and A are the main question and answer sequence, and quib; and sub are the ques- tions and answers of the lop-level subproblems. During inference, a model is given Q and tasked to generate the rest. Questions (both Q and Q start with GO token, and answers (both A and A Asub,*) end with STOP token. For trivial cases, i.e., the base cases of recursion, the context
3

---

Under review as a conference paper at ICLR 2023
Q
Q
Auub1
Q g
A
x
GO
GO
THINK
GO
THINK
STOP
9
STOP
STOP
Q
4 PUNN
Q
A 5uib
x GO
STOP
x
GO
B
GO
THINK
GO
THINK
7
5
STOP
STOP
STOP
Q
A
@
STOP
GO
STOP
Figure I: An example of the Recursion of Thought inference in Algorithm
Each table represents
an inference context X in order of creation, which has the structure of Eq For each context, the model is given Q and tasked to generate the rest, one token at time. The model outputs the THINK token when it needs to generate A sub,* the answer of subproblem. The THINK token triggers recursive process that solves the subproblem in a new context and returns the answer.
1ubb1
Aubb11
Qouh,
A
x
G0
4
8
8
GO
8
STOP
G0
5
STOP
5 9
STOP
yt
PAD
PAD
GO
B
THINK
PAD
GO
3
5
THINK
PAD
PAD
9 STOP
Figure 2: The target sequence y is produced from x' in Figure by Algorithm 2
Given X the
model trained to output Y; except for PADs that are ignored. Note PAD is dummy token to make sure || = ||
contains no (Qrub;, A pair. A subproblem can have smaller, lower-level subproblems recur- sively, but only the top-level subproblems remain context. As a result, we can abstract away the details for solving the subproblems and keep only the high-level results in the current context.
For tail recursion, where the last subquestion's 's answer becomes the final answer, we additionally introduce the TAIL token. If TAIL used in the place of a GO token in the last subquestion Quub.N its answer A sub,N treated the final answer A, and the context X does not have duplicate A.
Algorithm summarizes the inference process. Figure presents a example of solving 408 351 for better understanding. More detailed illustrations of inference can be found in Appendix A The RoT function (L[ takes a fully trained model with a question Q as input and returns the answer A as output. The procedure starts by initializing the context X with the original question Q (c.g., GO 4 8 + 3 5 1 = in Figure []. ians is the starting index of the answer, which initialized to | where generates a next token from X, which is appended to the end of X. After the initialization, the model expected
F
is the length of sequence. Then, in the main loop, the model iteratively
generate answer directly or (ii) output GO. If the model immediately generates A and finishes it with a STOP, the answer is returned (L9),, which is the base case of the recursion. Up to this point, the algorithm is identical to common language models.
On the other hand, if the model decides to output GO, which signals the start of subproblem, its index stored in 'go (LIT). Since a subproblem has started, the next several tokens from the model should constitute the question of the subproblem. In Figure [ the first subproblem of the main context x is adding the last digits, i.e., 8 + 1. Once the subquestion is generated, the next step is to find an answer to This is the pivotal moment: instead of producing the answer, the model outputs context (L16 23). First, separate the
the THINK token, which initiates the recursion with subquestion Qeub, starting from dzo (L(16). Second, using it as an input, we trigger the recursive call (1 to obtain the answer A dua As shown as red arrows in Figure | this call creates another context x² and initializes its question part with the subquestion. Then, the same inference process executed inside the new context, sometimes rumning more recursions. In the case of 8 + 1, the answer STOP is immediately returned since is base case. Finally, the THINK token is replaced
4

---

Under review as a conference paper at ICLR 2023
with A (121) and the starting position of the answer is updated (1 Hence, when predicting the next token, the model sees the returned answer as input, instead of the THINK token.
Once subproblem is finished, the model can solve another subproblem in the same way, or output the final answer. In Figure [] the second subproblem is to add all the remaining digits, i.e., 40 35. To solve it, the model recursively solves two other subproblems, i.e., adding each digit, be- fore generating the answer. If the model outputs the final answer followed by a STOP token, the answer returned (19).. the model starts a sub- problem with TAIL instead of GO, it becomes a tail recursion (L and its answer is returned di-
Algorithm 1 Recursion of Thought Inference
Require: A sequence model M trained for Re-
cursion of Thought, question sequence
1:
function ROT(M, Q)
2:
X Q
Initialize context with Q
3:
Pans + |X] +
D Start of answer Tail recursion
t false
5:
while True do
x. MMX) > Generate next token
7:
X [X;a]
if œ STOP then
rectly as the final answer (L (119).
9:
return -|
10:
else if GO then
3.2 TRAINING
11:
igo - |X] D Mark last GO
12:
else if x TAIL then
We teach RoT in supervised manner; the model trained with the ground truth (GT) intermediate
13:
igo < |X|
14:
+ true D Mark tail recursion
steps, which also include when to output the spe- cial tokens. Each training example is constructed as a pair of a ground truth context sequence X and the corresponding target sequence Y. The GT context X is structured as Equation D au- tomatically built by the algorithms that will be in- troduced in $3.3 and Appendix [ In this section, we discuss how to construct the target sequence Y for X, and define the training objective.
15:
else if THINK then
16:
Qaub. X ioo
17:
A sub ROT(M, QT1h)
18:
if then
return auub end if
19:
20:
21:
X [X1x A A
Replace THINK with A sub
22:
23:
aans |X| +
Algorithm| summarizes the process of convert- ing X to Y. where Y has the same length with X. Refer to Figure an example. Overall, y copy of X except for the parts corresponding to Q and A Since the question Q is always given in context, Q is replaced by special PAD tokens (L which mean "nothing to predict for this part." Each subproblem's answer A sub. is replaced by THINK token followed by several PADs that fill in the rest to make sure |X] = |Y| 4.. This way, the model is trained to output THINK instead of the first token of subb,, Since the whole A sub,n will be returned from the recur- sive process and replace the THINK during infer- ence 17 of Algorithm []. we do not need a training signal for the rest of A Asub,
24:
end if
25:
end while
26: end function
Algorithm 2 Creating the target sequence
Require: Context X
[Q: " q.hh
; Auu.,
S suu,,,, :A]
Y PAD PAD
IQ1 2: for n in L...N do
3:
Y - [Y; Q mu...ng
4:
Y + [Y; THINK PAD ... PAD
5: end for
Given a pair (X,Y). the training objective is de- fined as follows:
Y [Y; A]
7: return Y
L= L= Σ [uai PAD]logp(vwnlIigg (2)
where I is the indicator function that excludes PADs from training. Simply, it means that the se- quence model is trained to output 1/+1 the next token for given X1st- Its form is almost identical to the standard language modeling objective: LIM = - Σ, log pog;(<;;1 [xxx), which is to predict the next token given previous tokens. With this objective, any sequence model is trained in the standard way, i.c., end-to-end via stochastic gradient descent. For decoder-only transformers with causal masks, the training can be efficiently done in parallel for all tokens.
5

---

Under review as a conference paper at ICLR 2023
3.3 THE RECURSIVE REASONING PROCEDURES
As explained in $3.2 we teach the recursive reasoning procedure for a problem type by providing ground truth contexts. To produce these contexts, we design an exemplary reasoning procedure for each problem type and implement it as a teacher program that automatically generates the contexts given problem. The major desiderata for the exemplary reasoning procedures are two fold: (i) each context should be short, and (ii) the next tokens to generate should be obvious from the pre- vious sequence. Although the definition of "being obvious" may vary depending the model's architecture (e.g.. Transformers vs. LSTMs), the reasoning procedures developed for human gener- ally meet these desiderata. Therefore, our procedures for the arithmetic problems borrowed from the elementary school math. For example, the addition procedure shown in Figure D is a recursive version of adding digits one by one starting from the last digit. In another example of multiplica- tion, an N-digit x M-digit multiplication is divided into an N N-digit x 1-digit multiplication and an N N-digit x (M -iigiit multiplication. The -idigi 1-digit multiplication is further divided into a I-digit x 1-digit multiplication and an (NV - 1)-dig x I-digit multiplication. For the algorithmic problems, we also borrow standard, well-known algorithms. In Appendix [D] we provide the full details of the procedures for each problem type, with Python code snippets of the key parts. Note that our proposals for the reasoning procedures in Appendix D are one of many possible solutions, which are not necessarily optimal.
Training Data Distribution. We use the same problem distribution for both training and evalu- ation, since out-of-distribution generalization is not within the scope of this paper. That is, when teaching 6-digit multiplication to the model, both training and test sets are all examples of 6-digit multiplication. The problem distributions are elaborated in Appendix C Another important detail regarding the training of RoT is that each training example in batch is a context, not a whole prob- lem. Since RoT generates multiple contexts per problem, often a large portion of contexts can be duplicate (mostly the base cases). Therefore, to build a training batch for RoT, we first sample a top level problem and find the set of unique RoT contexts from the problem. Out of the unique contexts, we randomly sample one context as training example. We find this simple technique works well, and we do not need more sophisticated method, such as the adaptive curriculum learning in Reed & de Freitas (2016).
4
EXPERIMENTS
Since Recursion of Thought is the first approach of this kind, we mainly compare with two baselines. The first one is to output an answer directly from a question, which we call Without Thought (WT). The other one is to generate all the intermediate steps before the answer without recursion (Nye et al.) 2021), which we refer to as Chain of Thought (Co';; not to be confused with the CoT prompting Wei al. 2022 for consistency. We construct the ground truths for CoT's by unraveling the same recursive process which we design for RoT, into a single context sequence (see Appendix B for examples). Therefore, the number of tokens to generate while solving a problem is the same for both CoT and RoT (if we do not count the THINK tokens). However, the sizes of the individual contexts of CoT are far longer than those of RoT due to the recursively nested subproblems. Refer to Appendix for more detailed analysis of the context sizes. Note that we train these baselines and do not use any prompting technique. When evaluating, we consider a problem to be correctly solved only if all the intermediate steps and the answer are correct. In other words, we impose stricter rules on both RoT and CoT by not counting "lucky guesses" as correct.
4.1 THE REASONING PROBLEMS
To evaluate the reasoning capabilities, we test various reasoning tasks that are grouped into two categories: arithmetic reasoning and algorithmic reasoning. We below provide a rough description of the tasks, whose details can be found in Appendix C All the reasoning tasks share one characteristic we can easily adjust the problem's 's difficulty. Therefore, we can gradually increase the degree of difficulty and which method fails first. Since the goal of our experiments is to test the reasoning capability of language models, all problems are formulated in pure sequence modeling, with external program (e.g., calculator) called by the models.
in common:

---

Under review as a conference paper at ICLR 2023
Arithmetic Reasoning, We test four basic arithmetic operations, i.e., addition, subtraction, mul- tiplication, and division, with two non non-negate negative integers. The difficulty of arithmetic problems is represented by the maximum number of digits in an operand. For instance, in 6-digit multiplication, each operand can range from 0 to 999,999. When we sample a problem, we sample each operand from the log-uniform distribution. Compared the uniform distribution where the samples highly biased towards extremely large numbers, we get roughly the same ratio of samples for each number of digits. The sampling schemes for each operation are elaborated in Appendix C.T
Algorithmic Reasoning, We test four algorithmic tasks with distinct characteristics. These prob- lems are generally solved via dynamic programming (DP), and the length of intermediate steps can increase rapidly since the time complexity of DP algorithms ranges from ((N2) (LCS, LPS, and 0-1 Knapsack) to ONN") (MCM). (1) Longest Common Subsequence (LCS): Given two random sequences of length N. the model finds the longest common subsequence and its length. The se- quences consist of 10 characters from 0 to 9, and the problem difficulty is defined to be the sequence length N. (2) Longest Palindromic Subsequence (LPSS): Similar to I.CS, given random sequence of length N, the model finds the longest palindromic subsequence and its length. (3) 0-1 Knapsack: Given list of N items with specific value and weight, the model finds the best combination of items that maximizes the total value under the weight limit of a knapsack. The problem difficulty is repre- sented by the number of items. (4) Matrix Chain Multiplication (MCM): The computational cost of multiplying N (> 2) matrices varies greatly depending on the order of multiplication. MCM is the task of finding the best multiplication order that yields minimal computation cost. The difficulty is controlled by the number of matrices N.
4.2 UNLEASHING GPT-3's REASONING CAPABILITY THROUGH RECURSION OF THOUGHT
Despite their remarkable language modeling capabilities, the state-of-the-arr large language models, including GPT-3 (Brown et al. 2020), struggle to solve even the basic arithmetic tasks (Nye et al.) 2021]. For instance, it cannot correctly handle multiplication with more than one or two digits. Using the OpenAl API, we fine-tune GPT-3 on the reasoning tasks in I for 10K steps with batch size of 256. Each training batch is randomly sampled from the training data distribution explained in $33 The results are presented in Figure 3a and the technical details are described in
Appendix E Each point in the graphs represents one experiment at a certain problem difficulty. We report the accuracy on test set of IK unique problems randomly sampled as explained in Appendix
C To the best of our knowledge, the problems at this scale (e.g., 48-digit addition/subrractinn and 16-digit multiplication/ddiiiioon have never been solved by any language model without the help of external programs. For reference, Minerva (Lewkowycz et al. 2022) achieves around 80% accuracy on 10-digit addition and 20% on 18-digit addition.
Even WT fine-tuning cannot make GPT-3 deal with such a level of complexity, while CoT is not applicable due to the context limit of 2048. The green dotted lines mark the maximum difficulty that can be handled by CoT under the context limit. On the other hand, RoT finetunes the GPT-3 to achieve near perfect scores in every experiment. As presented in Appendix [ solving each problem requires up to tens of thousands of tokens. Without any architectural change, RoT makes GPT-3 handle these extremely complex problems.
4.3 RECURSION OF THOUGHT WITH TINY LANGUAGE MODELS
Recent research on reasoning has been mostly focused on extremely large pre-trained language mod- els. In this section, we show an interesting result that RoT can make even tiny models, without any pre-training, perform convoluted reasoning procedures. Since RoT is model-agnostic, we test the two basic sequence model architectures: Transformer Vaswani et al. (017) and LoTM[Hocreeiter & Schmidhuber (1997). For Transformer, we use a decoder-only model with 4 layers, 2 attention heads, 128 embedding dimensions, and 256 feed-forward dimensions, a total of only 536K parameters. is million times smaller than the largest PaLM (Chowdhery et al., 2022) with 540B parameters. The context limit is set to 2048 following GPT-3 and PaLM. For LSTM, we use layers, 64 input dimensions, and 256 hidden dimensions, which result in 272K parameters. We set the context limit of the LSTM to 512 since (i) it takes a lot of time for LSTMs to process the tokens sequentially, and (ii) they not good at handling long-term dependency.
7

---

Under review as a conference paper at ICLR 2023
Without Thought
Chain of TThought
Recursion of Thought
Addition
Subtraction
Multiplication
Division
Accurncy
1.00
Accuracy
1.00
Accumecy
Accuracy
0.75
0.75
0.5
0.5
0.50
0.50
0.0
0.0
24
32
32
16
16
Max Digits
Max
Digits
Max Digits
Max Digits
LCS
LPS
Knapsack
MCM
Accuracy
Accuracy
1.00
Accuracy
1.00
Accuracy
1.0
0.75
0.75
0.75
0.5
0.50
0.50
0.50
0.0
Sequence Length
Sequence Length
of Items
Matrices
(a) GPT-3
Addition
Subtraction
Multiplication
Division
Accurncy
1.0
Accuracy
Accuracy
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
64
28
Max Digits
Max
Digits
Max
Digits
Max Digits
LCS
LPS
0-1 Knapsack
MCM
Accumcy
1.0
Accumeyy
1.0
Accurucy
1.0
Accuncy
1.0
0.5
0.5
0.5
12
16
24 28 32
16
32
40
48
4
6
12
2
10
12
Sequence Length
Sequence Length
# of Ttems
#ff Matrices
(b) Tiny Transformer
Addition
Subtraction
Multiplication
Division
Accuncy
1.0
Accunicy
1.0
Accuncy
1.0
Accurcy
1.0
0.5
0.5
0.5
0.5
2
4
8
10
12
14
16
10
12
14
16
2
3
4
5
7 Max Digits
6
2
3
4
5
6
7
8
Max Digits
Max Digits
Max Digits
(c) Tiny LSTM
Figure 3:
Comparison of the thought processes. In each graph, the x-axis is the problem difficulty, while the y-axis is the reasoning accuracy. Each point represents an independent experiment. The green vertical lines indicate the maximum problem difficulty that CoT can handle without exceeding the maximum context size.
By virtue of their small sizes, we conduct far more extensive experiments than GPT-3, which are presented in Figure 3b and Figure 3dl We test both arithmetic and algorithmic reasoning problems with Transformer, and the arithmetic problems with LSTM. For each experiment, we train ran- domly initialized model and evaluate it a test set of 30K unique problems. With batch size of 256, Transformers and LSTMs are trained for 500K steps and 800K steps, respectively. We repeat each experiment eight times and report the average and standard deviation of the accuracies. Ap- pendix K enummeraees the exact values of Figure 3 With the tiny Transformer, we experiment to the extent where even humans would find daunting. For example, we test addition/subrraction up to 64 digits and mulipplication/diiiss up to 32 digits. Note that 32- 32-digit number cannot even fit into the 64-bit integer datatype.
Throughout the experiments, we observe consistent patterns:
WT's accuracy drops most quickly as the problem difficulty increases.
8

---

Under review as a conference paper at ICLR 2023
CoT achieves near perfect accuracy, but it can only be applied simple problems due to the context limit.
RoT achieves near perfect accuracy and can be scaled up to extremely complex problems.
Despite the small sizes, RoT makes the Transformers master all types of extremely complex prob- lems. We do not test more difficult problems mainly because the evaluation becomes too costly, not because RoT is incapable learning them.
5 DISCUSSION
The results of the tiny Transformer suggest that we might have to rethink the capability of large language models. If RoT enables the tiny Transformer to easily master 32-digit multiplication or division, what would million times bigger model, like PaLM, be capable of? In contrast to the currently ongoing arms race language models, the number of parameters might not the main bottleneck anymore to increase models' reasoning capability. We believe that our new paradigm of utilizing multiple contexts has the potential to make a huge leap in this line of research.
The current limitation of RoT is the need for supervision to learn divide and conquer for each task. In order to apply RoT to a wider range of tasks, may be crucial to reduce the expensive supervi- sion. As possible approach, we may borrow the RL-based methodologies that are developed for reducing supervision NPI (Li et al.) 2017 Fox et al. 2018 Pierrot et al. (019)).
Interestingly, RoT cannot facilitate length generalization, c.g., training 8-digit multiplication with RoT cannot make a model generalize to 16-digit multiplication. We believe this problem is rooted in more fundamental limitation of the Transformer architecture (Hahn) 2020), orthogonal to RoT. Fortunately, since RoT is model-agnostic framework, we would be able to apply RoT to more advanced architectures come in the future, which might be capable of length generalization.
CONCLUSION
Despite the remarkable advances in language models, their reasoning capability has always been constrained by the maximum size of single context. In this work, we introduce Recursion of Thought to solve this problem by utilizing multiple contexts. We prove its potential through exten- sive experiments, showing that it is possible to make language models solve problems that require hundreds of thousands of tokens. We believe the core idea of utilizing multiple contexts will play an essential role in future language models.
REFERENCES
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse. Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Ties Tauan-Tien Lin (eds.), Advances Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https: http:///poooeeee..eeeee URL/ttps:://pooccdinnnn neurips httpp.cc//aaae wwtpccpppppppeeeee (paper/2020/hasse (tw.cco6bbcbb996711bbfffboo Abbaaaac144eaaa-aatraaaaaaaaaaaa
Jonathon Cai, Richard Shin, and Dawn Song. Making neural programming architectures generalize via recursion. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net,, 2017. https: //openreview. nett:forumm.dd-kbbboooe...
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh,

---

Under review as a conference paper at ICLR 2023
Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek B Rao, Parker Barnes, Yi Tay, Noam M. Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Benton C. Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev. Henryk Michalewski, Xavier García, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omer- nick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Oliveira Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathleen S. Meier- Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. PaLM: Scaling language mod- eling with pathways. ArXiv, abs/2204.02311. 2022.
Roy Fox, Richard Shin, Sanjay Krishnan, Ken Goldberg, Dawn Song, and Ion Stoica. Parametrized hierarchical procedures for neural programming. In 6th International Conference on Learn- ing Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. httphhtps://ppeeeeeeeee r363fZZR
www. net/forum?id=
Michael Hahn. Theoretical limitations of self attentttentoon in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-1711 2020. doi: 10.1162/tacl a_00306. URL httLsttps:/ // ac Lantho logy. org/ 2020. tacl-1.11
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9:1735-
1780, 1997.
Daniel Kahneman. Thinking, fast and slow. Farrar, Straus and Giroux, 2013. ISBN 9780374533557.
Lukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL
1511 08228
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), ), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. htLht //arxiv. org. / abs 14112. 6980
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. ArXiv, abs/2205. 11966, 2022.
Aitor Lewkowyez, Anders Johan Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Venkatesh Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative reasoning problems with language models. ArXiv, abs/2206. 148888880..1888,,.. 2022.
Chengtao Li, Daniel Tarlow, Alexander L. Gaunt, Mare Brockschmidt, and Nate Kushman. Neu- ral program lattices. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL hittp:://operret ew. net/ forum? id=Hjj 1d=
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowyez, Maarten Bosma, David Luan, Charles Sutton, and Au- gustus Odena. Show your work: Scratchpads for intermediate computation with language models. ArXiv, abs/2112.0001144... 2021.
Thomas Pierrot, Guillaume Ligner, Scott E. Reed, Olivier Sigaud, Nicolas Perrin, Alexandre Laterre, David Kas, Karim Beguir, and Nando de Freitas. Learning compositional neural programs with recursive tree search and planning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Ach-eBus Buc, Emily B. Fox, and Roman Garnett (eds.), Ad- vances in Neural Information Processing Systems 32: Annual Conference on Neural Informa- tion Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, wttppipppsccpppp/////111 http://.e.eurriis....//////////
pp. 14666-14656, 2019. URL http/tttpp///prrceecnggg..o haaa3399444.att133221aaaa661646.
10

---

Under review as a conference paper at ICLR 2023
Scott E. Reed and Nando de Freitas. Neural programmer interpreters. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http:// org/ hrg//bs/// 10111111111111
programmer-mieeppeeters.
Andrew Trask, Felix Hill, Scott E. Reed, Jack W. Rae, Chris Dyer, and Phil Blun- som. Neural arithmetic logic units. In Samy Bengio, Hanna M. Wallach, Hugo and Roman Garnett (eds.), Advances
Larochelle, Kristen Grauman. Nicolò in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp- 8046-8055, 2018. URL httpp:::/ppocceeennngeee//////ee neurips wwtpcccppppppp/////eeee 2ater//018///hhhhh (666:770083222266531777500---060
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998 6008, 2017. URL
neurips hccc/ppper/2211///ee 3 Abstrcct
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoe Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. ArXiv, abs/2201. 11903, 2022.
Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad Hashemi. Neural execution engines: Learning execute subroutines. ArXiv, fbs/2200.080844 2020.
Wojeiech Zaremba and Ilya Sutskever. Learning to execute. ArXiv, 2b0. 2014.
11

---

Under review as a conference paper at ICLR 2023
A A STEP BY STEP ILLUSTRATION OF RoT INFERENCE
In this section, we provide a step by step illustration of the example in Figure ideal model fully trained for RoT.
|
Here we assume an
Step
The context is initialized with the question Q.
x
GO
4
8
3 5
Step 2
The model generates the first subquestion + 1.
sub,
GO
4
8
5
GO
Step 3
Instead of immediately producing the answer, the model outputs the THINK token.
Quub,1
A sub,1
x
GO
4
GO
THINK
Step 4
The THINK token triggers the creation new context. The new context is initialized with the subproblem starting from the last GO of x i.c.,
Sub,1
sub,1
x
GO 4
GO
THINK
GO
8
12

---

Under review as a conference paper at ICLR 2023
Step 5
Since the subproblem is a base case, the model outputs the answer immediately.
Q
x
GO
THINK
A
X²
GO
8
STOP
Step 6
The answer is returned and replaces the THINK token.
Q
A suu,1
x
GO
4
8
5
GO
STOP
Step 7
The model generates the next subproblem, which to add the remaining digits. Then, produces THINK find its answer.
sub,1
A
sub,1
X
GO
STOP
sub.2
A sub,2
GO
0
5
THINK
Step 8
The THINK token creates a new context X for solving 40 + 35.
Sub,1
sub,1
GO
4
8
5
GO
STOP
sub
aub
GO
0
3
THINK
GO
4
5
13

---

Under review as a conference paper at ICLR 2023
Step
Since 40 35 a base case, the model recursively produces more subproblems. this case, the first subproblem is to add the last digits, i.e., 0 and 5. Then it outputs the THINK token to solve the subproblem.
sub,1
X
GO
4
8
5
GO
STOP
gub,2
auub
GO
0
3
5
THINK
qub,1
sub,1
x
GO
4
THINK
Step 10
The new context X
is created to solve 5.
Sub,1
A sub,1
x
GO
4
8
5
GO
STOP
sub.2
suh
GO
0
THINK
sub,1
sub,1
x
GO
4
5
GO
THINK
A
GO
5
STOP
14

---

Under review as a conference paper at ICLR 2023
Step
The answer is returned to X and replaces the THINK token.
Q
A
x
GO
STOP
gubb22
suu
GO
0
THINK
sub,1
sub,1
X 3
STOP
Step 12
The model generates the subproblem.
Quub,
A sub,1
X
GO
GO
STOP
sub,2
suh,2
GO
THINK
Sub,1
sub,1
sub,2
sub.2
3
STOP
THINK
15

---

Under review as a conference paper at ICLR 2023
Step 13
X created to solve the subproblem 3. Since this base case, the model produces the answer directly.
Q
A sub,1
x
GO
4
8
3
5
GO
STOP
sub
A sub
THINK
sub,1
sub,1
Q qub,2
A 2uu,,
x 3
GO
4
5
GO
STOP
GO
THINK
A
X 5
GO
4
STOP
Step 14
The answer from X replaces the THINK token in X
Sub,1
A sub,1
x
GO
4
8
3
5
GO
STOP
Sub
sub,2
THINK
Lub,1
A sub,1
qub,2
A aub,2
GO
4
5
GO
STOP
GO
STOP
16

---

Under review as a conference paper at ICLR 2023
Step 15
Since all subproblems are solved in x the answer 75 generated and returned to X
Q
4ub,1
x
GO
4
STOP
gub,2
Auub,2
GO
THINK
sub,1
sub,1
qub,,2
subb22
X
STOP
STOP
A
7 STOP
Step 16
The answer of x replaces the THINK token in X
Q
Sub,1
A sub,1
x
GO
4
8
3 5
GO
STOP
Q sub,2
A sub,2
STOP
Step 17
Since the subproblems in X
all solved, the model produces the final answer.
sub,1
sub,1
x
GO
4
STOP
Qubb2
A sub,2
GO
3
5
7
STOP
5 STOP
B EXAMPLES OF COT TRAINING DATA
If we solve the example of 408+351
1 in figure I with RoT, the following five contexts produced.
- GO
4 0
5
GO
8
STOP
GO
4
0
3
7
5
STOP 7 5
STOP
x²
STOP
3 GO
3
G0
STOP
GO
STOP
7
STOP
2 GO
STOP
17

---

Under review as a conference paper at ICLR 2023
Xx
G0 4
STOP
The CoT context of the same problem is:
60
STOP
STOP
GO
4
STOP
5 STOP 7
STOP
In a slightly more complicated example of 34 x 5, the RoT contexts are as follows:
X GO
3
4
5
GO
STOP
G0
3
5
1
STOP
TAIL
1 5
2
0
THINK
X² GO
4
5
= 2
0
STOP
X² GO
3
* 5
=
5 STOP
X
1 0
2
STOP GO
STOP 1 0
STOP
X
STOP
x 5 2 60 5 STOP
7 STOP
x²: GO 5 + 2 = 7 STOP
The corresponding CoT context is:
*X CoT G0
3
5
G0
4
5
STOP
GO
1
STOP TAIL 5
2 GO
0
STOP
GO
1
5
GO
5
2 7 STOP 1 STOP
7 0
STOP
Notice that the CoT context consists of all the corresponding RoT contexts as its subsequences. The number tokens to generate identical that RoT, if we do not count the THINK tokens. Even in these simple examples, however, the context size of CoT is far longer than that of RoT. For much more complex problems, such as 8-digit multiplication or 0-1 Knapsack, the CoT context size can be orders of magnitude larger than RoT. See Appendix for more details the distribution of context sizes.
C PROBLEM SPECIFICATIONS
C.I THE ARITIMETIC PROBLEMS
For arithmetic tasks, we test addition, subtraction, multiplication, and division on non-negative in- tegers. For subtraction, we add a constraint that the first operand is not less than the second one, in order enforce non-negative answers. For division, let the output include both quotient and remainder, separated by special token R, c.g., GO 7
2 R 1 STOP.
As briefly mentioned in naively sampling the operands from uniform distribution makes the operands extremely biased towards large numbers. For example, the probability of sampling 2-digit number from the 6-digit space is less than 0.01%. Thus, we define variation of the log- uniform distribution (often called the reciprocal distribution) to sample the operands. As result, we obtain roughly the same proportion of operands for each number digits.
The probability density of a log-uniform distribution is proportional to the reciprocal of the value. By definition, zero not the support a log-uniform distribution, and samples are overly concen- trated to the first few values in the sampling range. Therefore, slightly extend the log-uniform distribution by introducing an offset parameter 8. To sample an integer in range [a, 3) with offset ö, first uniformly sample real number in range [log(a 8), ( 8)]. Then, is transformed to (xx(() - jJ. We denote the extended uniformm distribution Ulo (a, 3, 8). As gets larger, the samples
dispersed to larger numbers. In the experiments, set 8 = 3.
Additionally, we introduce several other sampling details for division problems. Assume that we independently sample numbers and b for the dividend and the divisor. In about half of the
18

---

Under review as a conference paper at ICLR 2023
Addition
Subtraction
Multiplication
Division
1330 121163
376776 35241
9466 176175
620261 155034
114780 4356
10638 100
179 516
111730 1176
638 +
109033 52649
5509 x 133
28268 +
35 + 77
85137 3098
6783 X 2
588137 + 25571
114261 354
22355 2821
6 x 80285
180330 739
13792
7-1
37275 19258
879975 97772
10151 +7
652781 78853
168484 151
111461 905026
22 1399
64911 3114
3331 X 40
42338 + 14003
363356 450475
13041 1422
349 X 158
108 + 384103
73 + 11
28293 4540
17988 262130
60002 7479
179895 4128
11553 3576
8140 1670
131467 131290
+ 10
656291 2795
51 X
890679
+ 141972
93 - 42
16497 X 158
228 + 131108
57612 + 18403
55972 1782
74 X 10
892 + 124
9 1621
84587 51
216 13414
15 964156
3370
273269 5867
621 x
369044 28364
678 + 8854
274405 14
x 5951
457 + 46
422 + 10348
51926 9
189486 x 13080
14687 + 730
118 + 582
4272 229
552792 X 763
200361 1049
1343 408534
223267
x
19715 965179
9251
14857 1994
179090 469029
98
315 + 652424
914771 836
1037 X 258
406
355 + 4434
3035 2963
8 X 769974
47345 + 122
22 834928
30 12
47765 7254
391613 1631
3028 357
560S 18164
892642 3898
777 + 1355
89057 -
21437 x 12
241554 + 1901
154874 81059
296410 -
15007 X 15
116475 + 12908
64936 + 216852
-
539860 X 427
488317 197443
3 340939
78906
3583 9754
7519 325
+ 984775
56560 29960
3560 847611
50581 + 1183
98 -
266394 X 185
9711 + 1385
115 + 943
16551 920
3988 X 12
44510 + 103
110 + 49
25606 194
5514 X 57
19721 # 58
17058
-5-37 37
1712
59544 + 24
36278 + 100
129443 70196
17 X 430178
333057 + 333057
6 + 23516
221 - 54
227 x 127
25719 + 5142
1462 848
11010 818
20888 x 54
7544 46
1002 2773 135 + 178346
47759 67
96 232801
45 410
-
175 1050
195659 2047 412572 + 16
22672 + 162038
1439 153
146 X 166
Table 1: 40 randomly selected samples of each type of 6-digit arithmetic problems.
cases, the dividend would be less than the divisor b, the quotients will be zero for those
To ensure a diverse range of quotients, we sample the divisor b from (i 10 .3, the quotient from Ulog (0, 10 /6, 3), and the remainder from Uno 60, The dividend is calculated from these values: a x e + This way, we can sample division problems with diverse range of quotients and remainders.
Table presents 40 problem samples for each 6-digit problem type. Several properties of our sam- pling scheme can be observed from the table. First, each number ranges over diverse numbers of digits. Second, the division problems are mostly non-trivial, i.c., the quotients are not concentrated zero.
19

---

Under review as a conference paper at ICLR 2023
C.2
THE ALGORITHMIC PROBLEMS
C.2.1 LONGEST COMMON SUBSEQUENCE (LCS)
The question of an LCS problem is two number sequences joined by the LCS token, and the answer the corresponding LCS and its length separated by ; Here is an example of length-4 LCS problem:
Q:
60
1
LCS 4 8
A: 4 2 STOP
For a length-N LCS problem, we sample two sequences of length N. Each character of the se- quences are randomly sampled from 0-9 with equal probability.
C.2.2 LONGEST PALINDROMIC SUBSEQUENCE (LPS)
The question of a length-N LPS problem starts with the LPS, followed by sequence of length N. Similar to LCS, the answer contains the corresponding LPS and its length separated by ;. The following is an example of length-8 LPS problem:
Q: GO LPS 4
5
2
A: 2
2
STOP
The sequence of an LPS problem is sampled in the same way as done for the LCS problem.
C.2.3
0-1 KNAPSACK
Each item 0-1 Knapsack problem represented by its value and weight. For instance, 1 & 3 4 represents item with value of 12 and weight of 34. The question part of a 0-1 Knapsack problem is a sequence consisting of the KNAPSACK token, a list of items separated by the token @, and the capacity of the knapsack. The answer part starts with a list of items to include, then $, and finally the total value. The following is example of 3-item knapsack problem.
Q: GO KNAPSACK & 1
2
2
1
1 1999
&
e
e
A:: 2 5 & 15 . 9 &
8
STOP
In this example, given knapsack of capacity 40, the last are selected with the total value of 44. For fixed number of items, we uniformly sample each item's value and weight from the integers of range [1, 99].
C.2.4 MATRIX CHAIN MULTIPLICATION (MCM)
The cost of multiplying many matrices is very sensitive to the order of multiplication. Matrix chain multiplication is the task of finding the best order with the minimum cost. Here, the cost is defined to be the total number of element multiplications. In the example of three matrices A, B, and C, whose shapes are 4 2, 2x8, and 8 8x3 respectively, the cost of computing ( (AB)C 4x2x x x 160, while another order A(BC) costs only x x 3 + x x 72. In the question of an MCM problem, the sizes of the matrices are enumerated, and the answer contains the order and the total cost separated by 3. The example above is represented the following sequences.
Q: GO MCM 2
3
A:
STOP
Given fixed number of matrices, we sample the sizes of matrices from the range [1, 99].
C.2.5 SORTING
Although not included in the main text, we test the problem sorting multi dilit numbers. The results are presented in Appendix | The problem difficulty is defined by the maximum number of
20

---

Under review as a conference paper at ICLR 2023
terms. For sorting problem of most N terms, first uniformly sample the number of terms from [2.N]. N.. Then we sample each term from Ulog 1000, 5). The following an example of the sorting problem.
*
Q: GO SORT
3
1
8
4
3
4
9
4
A:
1
4
STOP
D DETAILS OF THE RECURSIVE REASONING PROCEDURES
In this section, we elaborate the procedures to recursively solve the arithmetic problems. Specifi- cally, we present the algorithms to produce the subproblems of problem. Therefore, for set of randomly sampled questions, we can generate ground truth contexts using these algorithms. For better understanding, problem, we create a child class the Problem class and implement thought static method. The method takes of arguments for problem and returns the list of direct subproblems, Each sub- problem is represented by a problem class, problem arguments, and recursion type (whether it is tail recursion not). We use named tuple to group these information:
present the key parts of our Python code, the thought methods. For each
1 from collections import namedtuple
2 namedtuple( ('Thughht' l'prob_cls', targs', "tyee'1, defaults=["
For instance, T [Mull (3, 4)) represents a regular subproblem of 3 x 4, and T T(Add, (12, 340), , 'tail') represents subproblem of 12 + 340 which should be performed tail cursion. Once the thought method returns list of Ts, we can recursively find more subproblems for each subproblem.
D.1 ADDITION
The core idea of our recursive procedure for addition is first add the last digits, and then add the rest. If the sum the last digits is greater than or equal to 10, we insert another subproblem for adding the carry right after adding the last digits.
1 class Addoboo
2
@staticmethod def thought -> list[T]: left, right args
3
4
5
6
Base cases
7
if left and right 10:
return []
Llaas, r_last left % 10, right % thoughts (T(Add, (l_last, r_last)]]
12
13
L_rest, r_rest left // 10, right // 10 if Last r_last >= 10:
14
15
appughts.apeend(((Aar (l_rest, 1))) Lrest +=
if Lrest r_rest thoughts append (Add,, (l_rest, r_rest)))
21
return thoughts
Figure D in the main draft is an example with no carry, and the following is another example of 27+65 with carry.
GO
3
117
5
GO
1
STOP
G0
3
3
STOP
GO
3
STOP
8
STOP
21

---

Under review as a conference paper at ICLR 2023
X²
GO
STOP
X
GO
STOP
2 STOP
X
GO
1
STOP
6
STOP
8 STOP
GO
6
STOP
D.2 SUBTRACTION
Similar to addition, we first subtract the last digits and solve the rest recursively. When subtracting the last digits and y, we always borrow 10 for prevent negative result. The borrowing of 10 is easy for a sequence model: just put 1 before z. Therefore, the base cases of subtraction are when 19 and actually needed, we subtract from the rest of the first operand m.
If the subtraction result of the last digits is smaller than 10, i.e., the borrow is
class Sub(Problem) @staticmethod
2
3
def (args) -> List[T]:
4
Left, right args
5
6
Base cases
7
if left <= 19 and right <= 9:
8
return []
9
Laaat left
r_last right
thoughts (T(Sub, (1_ last, r_last))]
L_rest, r_rest left // 10, right // 10
if L_last r_last 10:
thoughts.appeen(((Suu (l_rest, 1)))
16
1_rest -= if r_rest 8:
17
18
thoughts.appeen(T(Sub, (l_rest, r_rest)))
return thoughts
Here is an example of 432-216:
GO
4
3
2
2
1
6
GO
1
2
6
STOP
GO
3
1
4
2
STOP
GO
1
STOP
STOP
2
GO
1
2
6
6
STOP
x
GO
GO
1
STOP
2
STOP
x
GO
1
3
1
1
2
STOP
x
GO
4
2
2
GO
2
STOP
GO
4
2
STOP
2
1
STOP
x
2
1
STOP
x²
GO
4
2
STOP
Notice that the final answer and the questions of each subproblem be easily constructed from previous sequence.
D.3 MULTIPLICATION
The base cases of multiplication are (i) when either operands are or 1, or (ii) when both operands less than 10. If one of the operands is 0, then the answer is zero; when of them is 1, then the answer just a copy of the other operand. For the cases where both operands are less than 10, we just let the model memorize them, which is similar to elementary school math curriculum.
22

---

Under review as a conference paper at ICLR 2023
There two types of non-base cases. For the simpler case, where the second operand is less than 10, we first split the first operand into the last digit and the rest. We then multiply each of them with the second operand and combine the results. Otherwise, split the second operand into the last digit and the rest. The first operand is multiplied to each of them, and the results are summed.
1 class (ur(bboblem):
2
@staticmethod
3 def (args) -> ListfT1:
4
left, right args
if Left
right
8
return []
9
if Left <= 9 and right <= 9: return []
11
12
thoughts []
if right 19:
thoughts.append
(left & 10, right)))
thoughts. append (T (left 10, right)))
(left
right
(left // 10) right
thoughts. append (Add, (a2 10, al), 'tail))
else:
21
a1 left (right 16) Bhoughts.appende (Mul, (left, right & 18)))
22
23
24
a2 left (right // 19)
25
thoughts appughts.append(Ti (T (left, right // 10)))
26
thoughts.c append (T (Add, (a2 10, al), 'tail"))
thoughts
Here are some example contexts of multiplication:
STOP
STOP
TAIL
6
0
4
3
THINK
X
GO
4
3
1
STOP
X
GO
4
2
GO
STOP
GO
STOP
TAIL
8
THINK
x
GO
3 *
STOP
5
GO
2
8
STOP
6
GO
8
0
6
GO
6
STOP
8 6
STOP
GO
STOP
X
G0
8
0
4
GO
3
3
STOP
GO
9
STOP
9
3
STOP
x
GO
STOP
x 1
GO
8
G0
4
1
STOP
GO
+
9
STOP
9
STOP
x=1,
G0
6
4
0
STOP
x
GO
8
STOP
Notice that tail recursion in x and x
23

---

Under review as a conference paper at ICLR 2023
D.4 COMPARISON
Comparison is used as a subroutine during division. The procedure for comparison consists of three steps:
1. Compare the numbers of digits.
2. If the numbers of digits are the same, compare the most significant digits.
3. If the most significant digits are identical, compare the remaining digits recursively.
We find that the sequence models can perform the first step without an explicit subproblem. There- fore, we only add intermediate steps for the second and the third steps.
1 class Compare(Problens
2 @staticmethod
3
def (argg) -> List[T]:
4
left, right args
5
6
Base if left and right return []
8
9
thoughts
digit_l, digit_r = (en(str(left)), ten(str(right)) if digit_l == digit_r:
12
13
Compare first digit
14
1_first, r_first int(str(left) int(str(rightt [0])
thoughtssappenn((((Cmrrr (l_first, r_first))) if 1_first == r_first:
Compare the rest
Lrest int(str(left)
r_rest int [i:gh)
(p (l_rest, r_rest)))
21
22
return thoughts
The following an example of comparing 153 and 159.
X
GO
VS
GO
VS
EQ
STOP
GO
5
VS
9
LT
STOP
STOP
X
GO
1
VS
EQ
STOP
x
GO
5
3
VS
9
G0
5
VS
EQ
STOP
GO
VS
9
LT
STOP
LT
STOP
x
VS
EQ
STOP
X
GO
VS
LT
STOP
D.5 DIVISION
Solving division is the most challenging among the four basic arithmetic operations since the pro- cedure basically trial and error, searching for the correct quotient. Nonetheless, the following process is recursive version of the elementary school division.
The base case is when the dividend less than or equal to the divisor. the dividend is smaller than the divisor, the quotient O, and the remainder is the dividend. If the dividend is equal to the divisor, than the quotient is and the remainder is Both cases can be handled relatively easily by neural sequence models. To determine whether it is of these cases, always perform the comparison as the first subproblem.
If is not base case, check whether the dividend is smaller than 10 times the divisor. If the dividend smaller, we subtract the divisor from the dividend and recursively divide the result with the divisor. The final answer is attained by simply adding to the quotient of the smaller division.
24

---

Under review as a conference paper at ICLR 2023
To explain the other case, where the dividend is greater than 10 times the divisor, let call the dividend and the divisor b. First, we split the a into the last digit x and the remaining digits m. Then, divide with the divisor b, i..., we define the division operation to return both a quotient and a remainder, the quotient / m and mod from the subproblem is added to the context. Next, concatenate the remainder and z, which is numerically computing x 10 + 2, and divide it again with b. Let the quotient and the remainder of this operation 92 and T2. Then, the quotient of the final answer is Q1 x 10 + 92, while the remainder is simply
solving one-digit-smallee subproblem first. Since
the remainder r1
1 class (Pr(Problem)
2
@staticmethod
def (args) List[T]:
left, right args
5
thoughts [T(Compare, (left, right))
7
Base cases if left <= right: return thoughts
8
9
10
11
apoughts (T (left, right 16)))
if left <= right 10:
diff left right
append
(left, right)))
apoedd (T (diff, right)))
else:
thoughts. apppttst (left // 18, right)))
remaindee (left // 10) % right left % thoughts. apppghtt..pppddgggg (T [left_remaindee right)))
20
return thoughts
The following an example of 76
29.
X
GO
6
2
GO
VS
2
GT
STOP
GO
VS
2
0
LT
STOP
GO
6
2
9
4
7
STOP
GO
4
7
2
9
1
1
STOP
R
1
STOP
x²
GO
7
6
VS
2
9
GO
7
VS
GT
STOP
GT
STOP
X
GO
7
VS
2
GT
STOP
X
GO
7
6
VS
2
9
LT
STOP
X
GO
7
2
9
G0
1
9
7
STOP
GO
STOP
GO
6
STOP
7
STOP
X-9
GO
4
7
2
9
60
7
V5
2
GT
STOP
GO
4
7
VS
2
0
LT
STOP
STOP
8
STOP
R
STOP
X=10
GO
VS
2
GO
VS
2
STOP
STOP
111
GO
4
VS
GT
STOP
X
GO
4
VS
2
0
LT
STOP
GO
4
2
9
G0
STOP
GO
4
STOP
GO
2
STOP
STOP
17,
GO
1
G0
8
VS
9
STOP
8
STOP
GO
1
VS
2
GO
VS
2
LT
STOP
STOP
25

---

Under review as a conference paper at ICLR 2023
D.6 LONGEST COMMON SUBSEQUENCE (LCS)
Given sequences A and B. the algorithm starts by comparing the last characters of the two se- quences. If the last characters are the same, find LCS of the subsequences without the last characters, i.e., LCS of A and B.-1- Otherwise, we compute the LCSs of the cases where the last character either side is removed, and return the better one. In the following code, LCS. answer _cswernswer is the subroutine that finds the LCS of two sequences. Equal returns TRUE if the two arguments are the same, or FALSE otherwise.
class (Crobbe))))
2
@staticmethod
3 def thought -> List[T]:
4
L, = args
5
if (l) 0 or ten(r)
6
return []
thoughts [T(Equal, (U-11, r[-11))1
9
[[-1] r[-1]:
thoughts. thoughts.append(T(Gr (U[=11), r(:-1))))
return thoughts
12
13
lcsi_args = (L[:-11, r)
14
lcs2_args (1, r[:-1])
15
lcs1 = LCS._answer (1css_arrc
les2 LCS._answer (1s__,ars (lcs2_args)
thoughts.
T(LCS, lcsl_args),
T(LCS, lcs2_args),
T(Compare, (len(les1), len(lcs2)))
21
1)
22
return thoughts
The following an example of finding the LCS of 123 and 234.
X
GO
1
2
3
LCS
2
4
GO
EQUAL
FALSE
STOP GO
1 2
LCS
3 2
2
STOP
GO
1
2
LCS
2
3
2
2
STOP
G0 1 VS
=
LT
STOP
2
STOP
x
EQUAL
4
FALSE
STOP
x
GO
1
LCS
2
3
GO
EQUAL
2
4
FALSE
STOP
GO
LCS
2 3
STOP
GO
1
LCS
3
2
STOP
GO
0
VS
= LT
STOP
2
1
STOP
21
GO
2
3
LCS
2
3
GO
EQUAL
TRUE
STOP
GO
1 2
LCS
2
=
STOP
2
3
2
STOP
x
1
STOP
D.7 LONGEST PALINDROMIC SUBSEQUENCE (LPS)
The overall algorithm for LPS is similar to LCS. The base cases are when the sequence length is less then 3. it is not a base case, we first check if the characters at both ends of the sequence are the same. If they are the same, find the LPS of the subsequence excluding them. Otherwise, compare the cases where one of the end characters are excluded.
class LPS(orotlem) 2
@staticmethod
3
def thought >> List(T]:
Base
if (args)))) return []
26

---

Under review as a conference paper at ICLR 2023
elif Len(args) 2: return (T(Equal, args)]
9
thoughts [T(Equal, (args[0), args[1]))]
if args [0] args[-1]:
sub_lps LPS._anse (1s____swwr(args(1-111)
13
thoughts.extend()
T(LPS, args[1:-1]),
15
T(Add, (subbb_pp))) 2))
})
else:
lpsl_args args[:-1]
1ps2_args args[1:]
lps1 LPSw_annwer (lpssaarss))))
21
1ps2 LPS._answer (1ps2_args)
choughts.extend([
23
T(LPS, (psl_args),
24
T(LPS, (ps2_args),
25
T(Compare, (len(Ips1), len(1p))))
26
1) return thoughts
The following is an example of LPS.
X
LPS
GO
EQUAL
FALSE
STOP
STOP
STOP
GO
3
LT
STOP
2
2
3
STOP
X²
EQUAL
1
2
FALSE
STOP
X
LPS
2
EQUAL
FALSE
STOP
1
STOP
GO
LPS
2
1
STOP
GO
VS
EQ
STOP
STOP
x10
X 10
GO
LPS
2
3
2
G0
EQUAL
2
2
TRUE
STOP
G0
LPS
3
3
STOP
GO
+
2
3
STOP
2
3
2
3 STOP
x
STOP
D.8 0-1 KNAPSACK
The base cases when there is only item. In this case, simply compare the item's weight and the knapsack's 's capacity, to determine whether the item should be included. is a non-base case, compare two possibilities: (i) include the first item, or (ii) exclude the first item. We recursively compute the subproblems and find the case with the best value.
class LPS(Problem)
2
@staticmethod
3
def (args)) List[T]:
items, capacity args value, weight itmss
7
Base case if Len(itens) == 1:
8
9
return (T(Compare, (weight, capacity))]
10
11
# When excluding the current iten itens_max, value_max Batrsscck__aswerr((ie capacity)) thoughts
12
T(Knapsack, (i:) capacity)), T(Compare, (weight, capacity)),
27

---

Under review as a conference paper at ICLR 2023
When including the itea if weight capacity:
items_sub, value_sub Knapsack._answerr
21
(1:tms(1:], capacity weight))
value_ value_sub value
23
nhouhhss.extend(.
24
T(Sub, (capacity, weight)), T(Knapsack, (items[l:], capacity weight)),
25
26
T(Add, (value_sub, value)),
27
T(Compare, nncue_iicl, value_max)),
28
1)
thoughts
The following is an example of 0-1 knapsack problem with three items and knapsack capacity of
10.
KNAPSACK
&
&
1
KNAPSACK
9
2
9
$
STOP
GO
VS
LT
STOP
GO
STOP
GO
KNAPSACK
4
2
9
5
1
5
STOP
STOP
GO
LT
STOP
1
STOP
x
GO
KNAPSACK
&
&
5
@
1
6
GO
KNAPSACK
&
&
$
STOP
G0
2
VS
0
LT
STOP
GO
0
2
8
STOP
G0
KNAPSACK 9
5
8
=
9
5
STOP
G0
9
+
STOP
GO
3
VS
GT STOP 4
&
2
&
$
1
STOP
I
GO
VS
STOP
1-
GO
1
1
STOP
X
GO
KNAPSACK
2
&
1
KNAPSACK
$ STOP
GT
STOP
STOP
x
STOP
X
3
1
STOP
D.9 TERNARY ADDITION AND MULTIPLICATION
Ternry addition and multiplication arises as a subproblem while solving MCM, which will be ex- plained the next section. They are simple extensions of addition and multiplication three integers.
class TernaryAdd(Problen) @staticmethod
2
3
def (hrught((rgs)) -> list[T]:
4
a2, a3 args return [
5
6
T(Add, (al, a2)), T(Add, a2, a3), 'tail')
]
9
class (ernarylul(Problee)
12
astaticnethen
13
def thought (args) -> List(T]:
a2, a3 = return [
T(Nul, (a1, a2)),
T(Mul, a2, a3), 'tail')
28

---

Under review as a conference paper at ICLR 2023
D.10 MATRIX CHAIN MULTIPLICATION (MCM)
Given N matrices, the N 1 subproblems are defined for each possible binary split. For the mul- tiplication of four matrices ABCD, there are three possible binary splits: A(BCD), (AB)(CD), and (ABC) D. For each binary split, the total cost is the sum of (i) the minimum cost of computing the first group, (ii) the minimum cost computing the second group, and (iii) the cost of multiply- ing the two matrices resulting from each group. Once get the total costs of cach binary split, return choose the best split with the minimum cost. The following code implements this procedure.
class MCM(Problem): @staticmethod
3
def (args) ListfT1: mats, min_order, min_cost args
4
5
6
Base cases
7
if Len (mats) == 1:
8
return []
if min order None: 9
Top-level problem 1_mats, r_mats mats[:1], mats[1:]
else:
Middle recursion
1_mats, r_mats mats
17
L_args (l_mats, None, None) r_args (r_mats, None, None)
18
Lorder, Loost = NCH. acs___nswer(L_argg
20
r_order, r_cost NCH. http__asserrr_aag_e__
21
agg_ [_mats[0][o] [o] [_mats[0][0] * [_mats[-1]
thoughts
T(NCH, l_args),
T(NCH, r_args),
T(TernaryMul, (L_mat[[e[00,, r_mats[0][0], (_a))s(-1](1)),,
T(TernaryAdd, (l_cost, r_cost, agg_cost)), ]
27
28
29
cost = __cost + r_cost agg_cost
30
if min_cost is not None:
31
thoughts. (Compare, (Cmmpr, (cost, min_cost)))
1f min_cost is None cost min_cost:
min_cost
min_order L_order, r_order
if Len(r_mats) new_l_mats L_mats (r_mats(01,) new_r_mate r_mats[1:] append) T(MCM, ((ne__1_mats, new new_r_mats), min_order, min_cost), (tail!))
37
39
40
41
42
return thoughts
The following an example of three-matrix MCM.
GO
MCM
3
9
x
x
GO
MCM
X
x
9
0
STOP
GO
MCM
9
4
4
5
9
x
1
8
0
STOP
GO
1
5
STOP
G0
0
1
0
1
5
3
1
STOP
TAIL
MCM
3
9
9
4
x
ACC
3
X
9
X
5
1
5
THINK
X
32
GO
MCM
3
9
9
4
4
ACC
)
3
GO
MCM
9
9
STOP
GO
MCM
5
STOP
GO
STOP
GO
8
6
1
8
29

---

Under review as a conference paper at ICLR 2023
STOP
G0
6
VS
3
5
LT
STOP
4
1
STOP
D.11 SORTING
Among several sorting algorithms, we choose merge sort for our experiments with CoT and RoT. Note that WT is not relevant to the sorting algorithm since it produces the answer directly. The merge sort algorithm is simple: (i) split the given sequence to two equally sized subsequences, (ii) sort each subsequence, and (iii) merge the two sorted sequences. Since the final merge operation quite complicated, we define the merge as a problem type.
Merge(Prablem):
@staticmethod
3
def (args) -> List/T1:
4
L, args
5
if (e) == 8 or len(r) == 0:
6
return []
7
8
thoughts [T(Compare, (L[e), r(o]))]
9
if tíol rrol and (e) (1) 1:
thoughts. (ooughts.apendd((Werggg
(t[1:], r)))
elif [[o] r[e] and len(r)
thoughts.append(T(Me)) (1, r(1:])))
thoughts
class PergeSort(Problenn
17
che
18
def thought -> List(T]:
if (args) < 2:
20
return []
21
1_ Len (args))))) 1) args[:l_]en]
args[1_[en:]
return [
26
T(MergeSort, L)
27
T(MergeSort, r), T (Nerge, (tuple(sorted(U)) tuple(sortedrr)),, 'tail!)
28
29
1
E FINE-TUNING GPT-3 FOR RECURSION OF THOUGHT
Using the OpenAI API, we fine-tune GPT-3 for Recursion of Thought. The goal is to learn 16-digit addition, 16-digit subtraction, 8-digit multiplication, and 8-digit division simultaneously. GPT-3's fine-tuning API takes dataset where each example is a prompt-completion pair in plain text. is converted to tokens by special tokenizer for GPT, which we cannot control. This API is not directly compatible with RoT due to several reasons.
There no special tokens such as GO, THINK, and STOP.
The input and target sequences have to be the same. However, they different in RoT due to the THINK token. Once THINK is produced, the RoT framework triggers the recursion process find the subproblem's 's answer and replace the THINK token with it. Therefore, the THINK token appears in the target sequences, but never in the input sequences.
Moreover, the way that GPT-3 tokenizes numbers hinders the learning of arithmetic reasoning rules. GPT-3 tokenizes multi-digit number into set of two-digit three-digit numbers. For example, the text 1234567 7 is converted to the sequence of tokens 123 45 67. Under this tokenization scheme, the relationship between the numbers become obscured. As example, the tokens 7, 17,
30

---

Under review as a conference paper at ICLR 2023
27, ... 997 all have their last digit. Since there is direct way for model to know that they share the same digit, it is crucial to use each digit as a token. We believe that OpenAl needs to conrect this tokenization of GPT-3 for numbers.
Luckily, we can mimic the RoT procedures with the API by using several tricks. First, we replace the special tokens with plain lower-case words, e.g., GO go and STOP stop, which included in the vocabulary of GPT-3. Second, we add a space before each token to make sure that the GPT tokenizer separates each token. We also add space before each digit prevent the tokenizer grouping a number into 2-to-3-digit tokens. Finally, to simulate the behavior of the THINK and STOP tokens, we derive multiple examples from each context, one for each THINK or STOP output.
As an example, context X in Figure is converted the following JSON lines for GPT-3 as follows:
GO
5
GO
0
5
STOP
GO
4
3
7
STOP
7 5 STOP
y
PAD
x7
GO
0
THINK PAD GO
4
3
THINK PAD 7 STOP
1 ("prompt": __ "completion": "_
2. ("prompt": "_89_A_A_ 1_____________0 L0 "completion": "_
3. ("prompt"; "LEO_A_B 0 3 s "completion": "_ s_t_tt
In the of Without Thought (WT), each problem simply converted into single example:
X GO
0
STOP
Y
PAD x7
7 STOP
["prompt":: "L 33="" "completion"; "_7_5_stop")
In both cases of RoT and WT, fine-tune GPT-3 for 10K steps with batch size of 256. Among the several variants of GPT-3, we use Ada which offered at the lowest cost. Note that RoT produces multiple contexts for each problem, and each RoT context is converted to multiple training examples. For this reason, the GPT-3 fine-tuned for RoT encounters much fewer problems during training, although the number of training steps are the same.
F TRAINING DETAILS OF THE TINY MODELS
In all experiments, we use a batch size 256 and Adam optimizer Kingma Ba (0155) with learning rate of 0.001, i.c., the default learning rate in PyTorch. We train the Transtormers for 500K steps and and decay the learning rate by half every 50K steps. Since the LSTMs converge slower than the Transformers, we train them for 800K steps and decay the learning rate by half every 100K steps. At every 20K steps, we evaluate the model on test set of 30K problems, and if model reaches perfect accuracy of 1.0, we do not train the model further. The models can be trained single GPU with 12GB memory.
G EFFICIENT EVALUATION OF RoT
At the problem scales that RoT is tested, solving single problem can require hundreds thousands of tokens. Therefore, have develop efficient evaluation algorithm. Since the models
31

---

Under review as a conference paper at ICLR 2023
deterministie, we do not need evaluate the context multiple times. Therefore, given test set, we first find all unique contexts that should appear while solving the test set. Note that there would be lot of duplicate contexts, especially for the base cases. These unique contexts can be evaluated parallel. We evaluate each context a similar manner to the training. For each context, described in $3.2 and check if the model outputs the target
construct the target sequence, sequence correctly, given the GT context. In case of GPT-3, we convert the contexts and target sequences as described evaluated, the next step is to aggregate the results. In this aggregation stage, (sub) is marked correct only if its subproblems all marked correct. This way, we efficiently evaluate RoT with minimal cost.
Appendix D feed into the API. Once every context individually
H FAILURE CASE ANALYSIS OF GPT-3 WITH ROT
In this section provide some failure cases of RoT in the GPT-3 experiments for further insights. Although the model achieves an accuracy of over 99% in almost every case, there are several prob- lems where it makes mistakes. Nonetheless, only few characters are wrong in each context.
The most common type of стrоr is repeating the same character for a wrong number of times. The following is the examples of this error type.
Prompt
go 1 4 4
0 1
go
eq stop
Completion
go
1
think
Model Output
go
6
3
vs
think
Prompt
go
4
0
9
4
0
5
6
7
go
8
0
9
4
5
8
5
5
9
*
7
=
3
3
6
6
6
4
6
7
stop
go
9
4
8
4
0
2
5
3
6
0
1
2
1
3
0
7
0
8
1
4
7
0
0
6
0
5
1
7
stop
Completion
tail
2
1
3
0
7
0
8
0
4
7
8
9 0
1
0
1
9
1
0
3
6
1
6
9
3
= think
Model Output
tail
9
0
0
1
3
3
6
6
6
4
6
6
2
7
1
3
7 think
Prompt
go 1
5
6
5
go
0
0
5
1
0
stop
go
0
5
4
6
0
1
1
5
6
0
stop
Completion
tail
0
think
Model Output
tail
5
7 1
6
think
Another common case is incorrectly counting the number of digits while comparing two numbers. When comparing numbers following our recursive procedure, the model has immediately return the answer if the number of digits are different. In the following example, the first number has seven digits, and the second one has six digits.
Prompt
go 1
6
0
4
vs
5
6
Completion
gt
stop
Model Output
go 1 vs
Although the model should directly output the answer, i.e., gt stop, it decides that the number of digits are the same and moves on to the next step, which to compare the most significant digits. This enror is caused by the specific recursive procedure of choice. Since model would easily figure out the difference in the numbers of digits, we did not add explicit steps count the digits. Although the model detects the difference in most cases, turns out be
assume that the
32

---

Under review as a conference paper at ICLR 2023
relatively challenging operation. possible solution is to teach the model to explicitly count the number digits and compare them.
I CONTEXT LENGTH DISTRIBUTION
In Figure we present the distributions context lengths for each problem type. We compare the context lengths of RoT and CoT. For each configuration, randomly sample 10K contexts from the training distribution and plot the histogram of their lengths. The graphs show that the context sizes of CoT many orders of magnitude larger than RoT. In theory, the total number of tokens to generate for each problem is identical in both RoT and CoT (if we do not count the THINK tokens). However, RoT's context sizes much smaller since it utilizes multiple contexts.
Another advantage of RoT is the utilization of dynamic programming. Since we can easily cache the duplicate computations of RoT as explained Appendix we can drastically reduce the amount of token generation if there is redundant structure in the problem. The amount of tokens to generate for each problem plotted in Figure 5 The benefit especially prominent in the algorithmic problems, For example, finding the LCS two 32-digit sequences results more than 10 tokens if we naively CoT RoT. If use dynamic programming with RoT, efficiently solve the same problem with much less cost.
J TRANSFORMERS ARE POWERFUL SORTING MACHINES
In fact, the first algorithmic task that we tested is sorting since it has been widely used as a benchmark for algorithmic reasoning (Reed & de Freitas 2016 Cai al. 2017 Pierrot et 2019). However, we find that Transformers are incredibly good at sorting, even in the WT setting. Figure 6 shows the sorting experiment. For CoT and RoT, we train the merge sort algorithm. Interestingly, WT easily achieves a perfect score in sorting 64 three-digit numbers. Also the training converges much faster than RoT, The Transformer architecture, more specifically the attention mechanism, seems be perfectly suited for the sorting operation.
K THE EXACT VALUES OF FIGURE 3
show the exact values of the graphs in Figure 3 Except for the GPT-3 experiments in we report the average and the standard deviation of eight runs. Each GPT-3 experiment done only once.
Table Table
5
33

---

Under review as a conference paper at ICLR 2023
/dd 32-digit/ RoT
Add / 32-digit CoT
Add / 64-digit/ RoT
Add 64-digit CoT
200
2000
2500
3000
400
8000
10000
Sub / 32-digit RoT
Sub / 32-digit / CoT
Sub 64-digit/ RoT
Sub 64-digit CoT
0
100
200
2500
3000
200
400
9000
10000
Mul/ 16-digit/ RoT
Mul/ / 16-digit/ CoT
Mul 32-digit / RoT
Mul / 32-digtt CoT
100
200
0
20000
40000
200
100000
200000
Div/ 16-digit/ / RoT
Div 16-digit/ CoT
Div / 32-digitt RoT
Div 32-digit/ CoT
100
200
10000
20000
200
400
50000
100000
LCS length 16 RoT
LCS length 16 CoT
LCS/ length 32 RoT
LCS /lngthh 32/ CoT
100
0
100
200
0
1c10
le18
LPS length 16 RoT
LPS/ length 16 CoT
LPS / length 32 / RoT
LPS / length 32/ CoT
500000
100
1e10
Knapsack/ items RoT
Knapsack items
Knapsack/ items RoT
Knapsack 12 items CoT
100
200
2500
5000
200
400
0
200000
400000
MCM/ 6 matrices/ RoT
MCM 6 matrices/ / CoT
MCM 12 matrices / RoT
MCM/ 12 matrices / CoT
1
200
50000
100000
250
2.5
7.5
1c7
Figure 4: The distributions of context lengths.
34

---

Under review as a conference paper at ICLR 2023
Add /32-digit/ Ro'I'
Add / 32-digit CoT
Add / 64-digit/ RoT
Add / 64- CoT
2000
2500
3000
2000
2500
3000
8000
9000
10000
8000
10000
Sub / 32-digit/ RoT
Sub / 32-dittt / CoT
Sub 64 144diiit// RoT
Sub /4-digitt CoT
2500
3000
2000
2500
3000
8000
10000
8000
10000
Mul/ /6-//it RoT
Mul / 16-digit/ CoT
Mul / 32-digit/ RoT
Mul 32-digit// CoT
20000
20000
0
100000
0
100000
200000
Div / 16-digit/ RoT
Div/ / 16-digit/ CoT
Div 32-digit RoT
Div / 32-digit CoT
10000
20000
20000
50000
100000
50000
100000
LCS length 16 RoT
LCS longth 16 CoT
LCS length RoT
LCS / length 32/ CoT
10000
15000
0
60000
80000
0
5
1e10
1e18
LPS length 16/ RoT
LPS length 16 CoT
LPS / length 32 / RoT
LPS / length 32/ CoT
2000
500000
10000
20000
le10
Knapsack items RoT
Knapsack items// / Coll
Knapsack 12 items RoT
Knapsack 12 items CoTT
2000
4000
2500
5000
0
100000
200000
400000
MCM 6 matrices / RoT
MCM 6 matrices/ / CoT
MCM/ 12 matrices / RoT
MCM 12 matrices / CoT
10000
20000
50000
100000
100000
200000
2.5
5.0
7.5
Figure 5: The distribution of the total number of tokens to produce in order to solve each problem. RoT can utilize dynamic programming reduce redundant computations.
35

---

Under review as a conference paper at ICLR 2023
Sorting
1.0
Accuracy
Without Thought
0.5
Chain of Though
Recursion of Thought
0.0
16
24
32
40
48
56
64
of Items
Figure 6: Sorting experiment with the tiny Transformer.
Problem
Difficulty
WT
CoT
RoT
32 digit 48-digit
0.991
0.998
Addition
0.853
0.995
32 22-digit
0.991
0,998
Subtraction
48-digit
0.886
0.998
8-digit
0.337
0.999
Multiplication
16-digit
0.098
0.994
8-digit
0.363
1.000
Division
16-digit
0.123
0.989
length 16
0.980
0.995
LCS
length 24
0.832
0.998
length 24
0.995
1.000
LPS
length 40
0.800
0.974
4 items
0.945
0.999
0-1 Knapsack
6 items
0.634
1.000
3 matrices
0.481
0.997
MCM
4 matrices
0.110
0.992
Table The exact values the GPT-3 experiments in Figure 3a
36

---

Under review as a conference paper at ICLR 2023
Problem
Difficulty
WT
CoT
RoT
8-digit
0.863 + 0.265
1,000 + 0.000
1.000 + 0.000
16-digit
0.370 0.475
1.000
0.000
1,000 + 0.000
24-digit
0.336 0.430
1.000 + 0.000
1.000 + 0.000
32-digit
0.455 0.458
1.000 0.000
Addition
40-digit
0.119 + 0.316
1.000 + 0.000
48-digit
0.082 = 0.216
1,000 = 0.000
56-digit
0.105 0.277
1,000 + 0.000
64-digit
0.000 0.000
1.000 + 0.001
8-digit
0.982 0.006
1.000 0.000
1,000 + 0.000
16-digit
0.705 0.411
1.000 + 0.000
1.000 - 0.000
24-digit
0.238 + 0.412
1.000 + 0.000
1.000 = 0.000
32-digit
0.221 + 0.385
1.000 I 0.000
Subtraction
40-digit
0.426 0.433
1,000 + 0.000
48-digit
0.114 0.303
1,000 + 0.000
56-digit
0.116 t 0.307
1,000 + 0.000
64-digit
0.161 + 0.282
1.000 = 0.000
2-digit
1.000 + 0.000
1.000 + 0.000
1.000 + 0.000
4-digit
0.817 + 0.023
1.000 + 0.000
1.000 = 0.000
8-digit
0.340 0.032
1.000 = 0.000
12-digit
0.169 0.015
1,000 = 0.000
Multiplication
16-digit
0.104 0.016
1.000 + 0.000
20-digit
0.048 + 0.020
1.000 + 0.000
24-digit
0.033 + 0.017
0.999 + 0.001
28 digit
0.014 0.006
0,999 + 0.001
32-digit
0.012 0.001
0,999 t 0.000
2-digit
1.000 0.000
1.000 0.000
1.000 + 0.000
4-digit
0.978 0.008
1,000 + 0.000
1.000 + 0.000
8-digit
0.354 t 0.029
1.000 + 0.000
12-digit
0.186 + 0.009
1,000 + 0.000
Division
16-digit
0.128 0.011
1.000 = 0.000
20-digit
0.087 0.012
1.000 + 0.000
24-digit
0.075 0.005
1.000 + 0.000
28-digit
0.059 + 0.007
0.999 + 0.000
32-digit
0.048 0.008
0.999 + 0.000
Table 3: The exact values of the Transformer experiments in Figure 3b (arithmetic problems).
37

---

Under review as a conference paper at ICLR 2023
Problem
Difficulty
CoT
RoT
length 3
1.000 + 0.000
1.000 + 0.000
length 4
0.997 + 0.008
1.000 = 0.000
longth 8
0.999 + 0.002
1.000 = 0.000
length 12
0.965 + 0.025
1.000 = 0.000
LCS
length 16
0.880 0.035
1.000 0.000
length 20
0.759 + 0.043
1.000 + 0.000
length 24
0.622 + 0.038
1.000 + 0.000
length 28
0,484 t 0.043
0.999 # 0.000
length 32
0.375 t 0.030
0.999 0.000
length 4
1,000 + 0.000
1.000 + 0.000
length 7
1.000 t 0.000
1.000 + 0.000
length 8
1.000 + 0.000
1.000 + 0.000
length 16
0.999 + 0.001
1.000 + 0.000
LPS
length 24
0.950 + 0.019
1.000 = 0.000
length 32
0.788 + 0.019
1.000 = 0.000
length 40
0.608 0.023
1.000 0.000
length 48
0.477 t 0.030
0.999 + 0.001
length 56
0.365 + 0.029
0.998 + 0.000
items
1.000 t 0.000
1.000 + 0.000
1.000 + 0.000
4 items
0.966 + 0.006
1.000 = 0.000
1.000 + 0.000
6 items
0.849 + 0.007
1.000 + 0.000
0-1 Knapsack
8 items
0.640 0.242
1.000 0.000
10 items
0.481 t 0.279
1.000 + 0.000
12 items
0.435 t 0.252
0.988 + 0.029
matrices
0.973 t 0.009
1.000 + 0.000
1.000 + 0.000
4 matrices
0.177 t 0.069
1.000 + 0.000
6 matrices
0,088 t 0.029
1.000 + 0.000
MCM
8 matrices
0.033 + 0.025
1.000 # 0.000
10 matrices
0.051 + 0.032
0.998 # 0.001
12 matrices
0.026 + 0.011
0.996 + 0.002
Table 4: The exact values of the Transformer experiments in Figure 3b (algorithmic problems).
38

---

Under review as a conference paper at ICLR 2023
Problem
Difficulty
WT
CoT
RoT
2-digit
1.000 + 0.000
1.000 + 0.000
1.000 + 0.000
4-digit
0.642 + 0.305
1.000 + 0.001
1.000 + 0.000
6-digit
0.005 0.008
0.997 0.005
0.999 + 0.000
8-digit
0.000 0.000
0.905
0.999 + 0.001
Addition
10-digit
0.000 0.000
0.795 + 0.341
0.986 + 0.024
12-digit
0.000 + 0.000
0.871 + 0.275
14-digit
0.000 0.000
0.358 + 0.430
16-digit
0.000 0.000
0.120 + 0.202
2-digit
1.000 0.000
1.000 + 0.000
1,000 + 0.000
4-digit
0.776 0.179
1.000 0.000
1.000 + 0.000
6-digit
0.006 0.001
1.000 + 0.000
1.000 + 0.000
8-digit
0.000 + 0.000
0.896 + 0.252
0.994 + 0.016
Subtraction
10-digit
0.000 + 0.000
0.443 + 0.377
0.908 + 0.236
12-digit
0.000 0.000
0.507 + 0.398
14-digit
0.000 0.000
0,295 + 0.406
16-digit
0.000 + 0.000
0.101 + 0.137
2-digit
1.000 0.000
1,000 + 0.000
1.000 + 0.000
3-digit
0.855 + 0.044
1.000 + 0.000
4-digit
0.636 + 0.061
1,000 + 0.000
Multiplication
5-digit
0.338 0.063
1,000 I 0.000
6-digit
0.270 0.030
0,987 + 0.008
7-digit
0.162 t 0.025
0,896 t O. 105
8-digit
0.138 + 0.025
0.670 = 0.208
1-digit
1.000 t 0.000
1.000 + 0.000
1.000 t 0.000
2-digit
1.000 + 0.000
1,000 + 0.000
3-digit
1.000 - 0.001
1.000 = 0.000
4-digit
0.891 0.072
1.000 = 0.000
Division
5-digit
0.516 0.077
0.998 + 0.004
6-digit
0.308 t 0.069
0.996 + 0.007
7-digit
0.192 + 0.028
0.958 + 0.036
8-digit
0.115 0.015
0.914 + 0.090
Table The exact values the LSTM experiments Figure 3c
39


Reviews:
[{"review_id": "lh5UBvG9rUM", "reviewer": "Reviewer_k2RA", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper demonstrates that for simple algorithmic problems (arithmetic), language models can be taught to split problems into multiple subproblems, which can then be fed back to the LM to be solved independently. With very small models this can achieve great performance on these tasks, and it circumvents the limit in context-length of existing transformer models.", "summary_of_the_review": "This paper demonstrates that decomposing simple algorithmic problems can circumvent the limit in context length language models.\n\nHowever, the technique only seems to work for problems for which we already have algorithms, and it is unclear to me if this could be extended to more general problems. The writing style should be improved.", "strength_and_weaknesses": "My main concern with this approach is that the paper does not discuss how to apply this approach to more general problems. The problems considered here are very simple, and an algorithm to solve them needs to be known in order to generate the training data. So, in its current form this does not enable any new abilities as we could use the base algorithm instead of using expensive LMs.\n\nIn terms of the insight from a learning point-of-view, I also do not see anything surprising in this work. After decomposing the problem manually (i.e. by writing an algorithm to generate training data), the learning task is pretty simple (for addition, for example, all the model has to do is to extract the last digit from two numbers). So the high accuracy of the resulting method is not that surprising.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "aWhsAMl3aDq", "reviewer": "Reviewer_U3UZ", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper experiments with fully supervised training of a LM to produce subsequences needed for solving simple reasoning tasks, motivated by limited context size of LMs.", "summary_of_the_review": "Unfortunately, I don't see much impact from this work in practical terms. The formulation doesn't scale to general reasoning problems, the tasks considered aren't tasks that you would train a specific LM to solve, and the algorithmic solution is very simple/trivial extension. Hence, I'm not able to recommend this paper for publication.", "strength_and_weaknesses": "On the positive side, the paper is well written and easy to read.\n\nOn the negative side, the solution proposed is formulated as a fully supervised problem, meaning for each task the exact steps needed to solve the problem needs to be annotated. This is not a scalable approach as for realistic real-world applications obtaining detailed annotations for reasoning problems is an expert task which is expensive to scale to large datasets. As a result, outside of tasks such as arithmetic operations where the dataset can be created automatically (and one could argue that you wouldn't use a task specific LM as the paper doesn't deal with multiple tasks or out-of-distribution problems), the applicability of this approach is minimal.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "KhQeTvSVFsh", "reviewer": "Reviewer_kKKS", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work proposed a model-agnostic framework, Recursion of Thought (RoT), to release the capacity constraint by the maximum size of a single context in language models. RoT teaches a language model to divide and conquer complex problems by recursively creating multiple contexts; therefore, a complex problem could be solved by utilizing multiple contexts. This work also conducts extensive experiments on arithmetic and algorithmic reasoning tasks to show the power of RoT in helping language models solve problems that require hundreds of thousands of tokens. \n\nOverall, the proposed framework (RoT) is novel and well-motivated, and the authors have conducted multiple experiments which demonstrate the great power of RoT on much more complex arithmetic and algorithmic reasoning problems. One important point missing from this work is how to systematically construct subproblems given any problem in order to teach the model learn the recursion of thoughts. Still, I think this work has great potential to allow language models to achieve better reasoning abilities.", "summary_of_the_review": "This work proposed a novel model-agnostic framework, Recursion of Thought (RoT), to release the capacity constraint by the maximum size of a single context in language models. RoT teaches a language model to divide and conquer complex problems by recursively creating multiple contexts; therefore, a complex problem could be solved by utilizing multiple contexts. It then conducts extensive experiments on arithmetic and algorithmic reasoning tasks to show the power of RoT in helping language models solve problems that require hundreds of thousands of tokens. \n\nThe proposed framework (RoT) is novel and well-motivated, and this work has a good and clear presentation of its idea, its specific methodology, and its experiment settings. The quality and originality of the work should meet or exceed the conference standard. My main concern is on how to properly train the RoT framework as the training of RoT requires (non-trivial) human inputs to design proper subproblems. Still, I think this work has great potential to allow language models to achieve better reasoning abilities.", "strength_and_weaknesses": "Strength:\n-\n\n[+] The proposed framework (RoT) is novel and well-motivated.\n\n[+] The work has conducted multiple experiments which demonstrate the great power of RoT on much more complex arithmetic and algorithmic reasoning problems. \n\nWeakness:\n-\n\n[-] The training of RoT requires (non-trivial) human inputs to design proper subproblems.\n\nMore specifically, I wonder \n\n1) what is the limitation of the problems that RoT could solve: for example,\n\n- Does RoT have the ability to learn backtrack? Some problems may require people to modify the earlier part of the answer based on the new observed information.\n\n- Does RoT have the ability to learn a problem where its subproblems have different structures (as recursion usually requires the same structure in the subproblems)?\n\n- What is the performance of RoT on (maybe small-scale) NP-hard algorithmic problems that may not have the divide-and-conquer structure such as TSP？\n\n2) how to design proper subproblems in order to use RoT to train the models?\n\n- What are the criteria of the subproblems for RoT? What kinds of structures do they need to have？ \n\n- Are there systematic approaches to design subproblems for reasoning tasks in general?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject