Teaching Algorithmic Reasoning via In-context Learning
Authors: Hattie Zhou
Azade Nova
Aaron Courville
Hugo Larochelle
Behnam Neyshabur
Hanie Sedghi
Venue: Submitted to ICLR 2023 (2023)
Keywords: in-context learning
algorithmic reasoning
LLMs
prompting

Abstract: Large language models (LLMs) have shown increasing in-context learning capabilities through scaling up model and data size. Despite this progress, LLMs are still unable to solve algorithmic reasoning problems. While providing a rationale with the final answer has led to further improvements in multi-step reasoning problems, Anil et al. 2022 showed that even simple algorithmic reasoning tasks such as parity are far from solved. In this work, we identify and study four key stages for successfully teaching algorithmic reasoning to LLMs: (1) formulating algorithms as skills, (2) teaching multiple skills simultaneously (skill accumulation), (3) teaching how to combine skills (skill composition) and (4) teaching how to use skills as tools. We show that it is possible to teach algorithmic reasoning to LLMs via in-context learning, which we refer to as Algorithmic Prompting. We evaluate our approach on a variety of arithmetic and quantitative reasoning tasks, and demonstrate significant boosts in performance over existing prompting techniques. In particular, for long parity, addition, multiplication and subtraction and parity tasks, we achieve an error reduction of approximately 10x, 9x, 5x and 2x respectively compared to the best available baselines. 

Under review as a conference paper at ICLR 2023
TEACHING ALGORITHMIC REASONING VIA IN-CONTEXT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Large language models (LLMs) have shown increasing in-context learning capa- bilities through scaling up model and data size. Despite this progress, LLMs are still unable to solve algorithmic reasoning problems. While providing a ratio- nale with the final answer has led to further improvements in multi-step reasoning problems, Anil al. (2022) showed that even simple algorithmic reasoning tasks such as parity are far from solved. In this work, we identify and study four key stages for successfully teaching algorithmic reasoning to L.LMs: (1) formulating algorithms as skills, (2) teaching multiple skills simultaneously (skill accumula- tion), (3) teaching how to combine skills (skill composition) and (4) teaching how to use skills tools. We show that it is possible to teach algorithmic reason- ing to LLMS via in-context learning, which we refer to as algorithmic prompting. We evaluate
approach on variety of arithmetic and quantitative reasoning tasks, and demonstrate significant boosts in performance over existing prompting techniques. In particular, for long parity, addition, multiplication and subtraction, we achieve an error reduction of approximately 10x, 9x, 5x and 2x respectively compared to the best available baselines.
INTRODUCTION
Large language models (LLMs) have shown impressive progress in recent years, driven by the scal- ing up of models and training data sizes (Kaplan et al., 2020 Wei et al. [002a Hoffmann et al., that has led to improved performance and sample efficiency (Brown et al. 2020 Chen et al.
2022
2021
Chowdhery et al. 2022). One area with significant room for improvement is the ability of to perform complex reasoning tasks. In this realm, mathematical reasoning (Saxton et al. provides a unique challenge as domain. It requires the ability to parse, to logically decon- struct problem into sub-problems and recombine them, and to apply knowledge of rules, transfor- mations, processes, and axioms.
LLMs
2019)
The idea of providing rationale with the final answer first proposed by Ling al. (2017) and
recently revived for LLMs in the form of scratchpad (Nye et al. (022)) and cfain-of-thought (Wei
et al. 2022b). It has led to improvements in performance on multi-step reasoning problems (Wang
et al. 2019) such as arithmetic, commonsense, and symbolic reasoning tasks (Nye et al. [021] | Wei
al. 2022b; Lewkowycz et al. 2022a Wang et al. 2022a b. Anil et al. 2022 Zhou et al. 2022).
However, despite significant progress, these models still struggle with out-ol -il-oo--disttbttion (OOD)
generalization on reasoning tasks (Nogueira et al. 2021 Kim et al. 2021 Anil et 2022).
To successfully generalize out-of-distribution learn the underlying algorithm for solving a task. We refer this behavior as algorithmic rea- soning (Kaiser and Sutskever, 2015) Veličković and Blundell 2021). While following algorithm can be seen as a form of instruction following, algorithms are generally more complex with larger number of steps, though each step of the algorithm may be simpler and more concise than typical instructions. The benefit of being able to learn algorithms is that since they are input independent by nature, they are immune OOD performance degradation when executed properly. Moreover, algorithms can be specified without ambiguity and hence provide a good test bed to probe model capabilities.
many of these reasoning tasks, the model needs
One surprising capability of LLMs is in-context learning (Brown et al. 2020). which refers to the ability to learn task from few examples being presented within a prompt. In-context learning does

---

Under review as a conference paper at ICLR 2023
Teaching an Algorithm as a Skill
Skill Accumulation
Skill Composition
Using Skills as Tools
128 367 =
Q: 120 367 [AP]
128 367 A: [AP]
Q:
[AP]
[AP]
A:
Q: 205 2.2 A: [AP]
Q: 673 453
Q: 128 267 6000
Q: Jack has 5 applcs and ozangess Hov many cruita do have?
[AP]
A: The sulproblens are
--8-367-ANS1
ANB11 6000-AN02. [AP]
A: Apple and urange are both feal ca so 4=
Q: 305520 79202
Q: 8530939
238692
Q: 3 11
5 4 - A: [AB]>9.
The queotion
conversed into 11=1lel1.
[AP]
Q: TTomyy has 5 coy cere. lix neightber, Jescin, Jessie's older brocher has more caew Chan Tonmy and Jessie How neny do three
[AP]: A detailed non-ambiguous description of the algorithm exccution based on our proposed Algorithmic Prompt (AP) approuch
3
a: 453 9754 -
altogethex?
Figure 1: The four learning stages investigated this work (from left to right): (i) Teaching an algorithm as a skill (Section B (ii) Skill Accumulation, i.e., teaching multiple skills simultancously (Section 4 (iii) Skill Composition, iee the ability to learn a complex skill through building upon simpler ones (Section (iv)
Using Skills Tools to solve problems (Section (6). We teach these algorithms in-context using our proposed algorithmic prompting approach, which does not involve any further training of the underlying model.
not require any weight updates, and provides powerful platform for specialized skill acquisition without losing the generality of the underlying model. Moreover, various prompting strategies have shown significant potential in solving certain types of reasoning problems (Jung al. 2022 Zhou
eet al., 2022] Wei et al. 2022b Kojima et al. (022). Nonetheless, Anil et al. (2022) considered
two algorithmic reasoning tasks and showed that while ationale-based prompting allow LLMs to
generalize to longer problem instances, they are still far from solving simple algorithmic tasks such
as parity.
In this work, we investigate how to teach algorithms and compositions of algorithms to LLMs via in- context learning. This setup is reminiscent of how similar skills are taught to children in school. We identify and explore four key stages for teaching algorithms as skills to LLMs (Figure DT. We begin by studying the shortcomings of existing approaches and proposing ways to alleviate them. We focus on arithmetic algorithms such as addition, subtraction and multiplication as they have been widely benchmarked (Saxton et al.] 2019: Hendryeks et al. (02T] and famously fail at outttr-disttibuutin generalization even for the best performing models on the MATH benchmark (Lewkowycz et al.) 20226). While one can avoid learning these algorithms by using external tools such as calcula- tor (Cobbe et al., 2021), this approach cannot scale to higher levels of abstraction where model needs to use "soft algorithms" and certain steps must be flexibly applied in different situations.
Contributions: Our main contributions are as follows:
We introduce Algorithmic Prompting, which involves providing a detailed description of the algorithm execution running examples, and using explicit explanation and natural language instruction to remove ambiguity. For comparison of algorithmic prompting to existing prompting techniques, see Section and Table
We demonstrate that algorithmic prompting significantly outperforms existing prompting techniques on several algorithmic tasks. In particular, for long parity, addition, multiplica- tion and subtraction, we achieve an error reduction of approximately 10x, 9x, 5x and 2x respectively compared to the best available baselines (Section 3 and Table
Our ablation studies reveal the impact of non amn-guuuu explanations, and show that un- like other prompting approaches, errors in the algorithmic examples affect performance significantly (Section 3.1)
We study the model's ability to simultancously learn multiple algorithms via single prompt, as well as its ability to compose the learned algorithms in order to solve more complex tasks (Sections{ 3).
We explore various approaches to leverage a learned algorithm as a tool to solve math word problems. We show that while is possible to improve the performance in settings that require complex calculations, the model's 's general reasoning capability reduces due to the phenomenon of interference (Section 6).
2

---

Under review as a conference paper at ICLR 2023
2 ALGORIHTMIC PROMPTING
Nye et al. 2021 proposed the idea of getting the model to show its work, i.e, breaking the prob- lem down and asking the model to output the intermediate steps used in solving the task. The authors show that by finetuning LLMs on such data which they refer to as scratchpad - they can greatly improve performance on multi-step computation problems. This was taken further by Wei er al. (202bb) to the in-context learning setting, where they showed that providing rationales in the prompts significantly increases the model's ability to solve multi-step reasoning problems. They refer to this approach as
The main intuition behind the scratchpad approach is that by having intermediate computations in the output, the model can refer to them directly instead of relying on its internal representation space for those calculations. For chain-of-thought, one hypoth- esis is that the rationales loosely provide the model with a "thinking pattern" that it can reference when tackling problem. By encouraging the model to output an explanation along with the an- swer, we steer it towards solving problems by breaking them into steps that logically follow from each other. Inspired by these perspectives, we hypothesize that if we increase the specificity and applicability of these thinking patterns, we can also increase the amount by which the model ad- heres to these patterns in its problem solving. As we will illustrate, this approach leverages both the scratchpad ideas of showing intermediate computations and the chain-of-thouge ideas of providing an explanation for each step.
As motivating example, consider the standard addition algorithm. This method right-aligns the two numbers being added and calculates the sum of pairs of single digits from each number, going from right to left. For every pair of digits, there is possible carry that needs to be added to the next digit sum. If we use a scratchpad-style illustration, then for a question like 182 + 376, the model would see that the digit-sum 2+6 generates carry of O, while 8+77 generates carry of 1. However, the rule for how carry should be computed is highly ambiguous from just this example. Ideally, we expect the model to conclude that for x + y 2, the carry should be computed mod 10)) 100. But from only this example, the model could conclude that the carry is 1 whenever add two even digits together and 0 otherwise, or that the first digit-pair generates a carry of the second digit-pair generates a carry of O, and so on. In order for the model to extrapolate the correct pattern, it must be biased in such a way that the general and correct rule is the default interpretation. Such alignment, however, can not be reliably expected from current models.
(= (=
We hypothesize that existing prompting methods fail to sufficiently constrain the model's interpre- tation of the prompting information, and result in unexpected and undesirable model behaviors on tasks that require precise algorithmic reasoning. We push the limits of rationale-basee prompting by drastically increasing the amount of detail included in the rationales, while specifying the steps of an algorithm within this information. We refer to this strategy as Algorithmic Prompting, and contrast this approach with other types in Table [ We show that it can achieve significant systematic gener- alization on several algorithmic reasoning tasks, and ground our exploration in the four capabilities identified in Figure T
Comparison of different prompting strategies studied in this work. The number of * indicates the level to which each strategy exhibits the given characteristic. In this work, we refer to the basic approach of presenting only input-target pairs with no additional explanation as few-shor, and we refer to prompts that provide explicit instructions but no running examples of a task as insiruction-only. We see that algorithmic prompt includes both qualities of natural language explanation and explicit intermediate computations.
Table 1:
Prompt strategy
Input-target pairs
Natural language
Intermediate com- putations
Rationale diversity
rationale
Few-shot
Chain-of-thougle
Scratchpad Instruction-only
Algorithmic
2.1 EXPERIMENTAL SETUP
Baselines: We compare the proposed algorithmic prompt few-shot and baselines in our experiments. The few-shot baseline refers to the simple approach of presenting examples of question and answer pairs with additional explanation. The chain-of-though baseline provides
3

---

Under review as a conference paper at ICLR 2023
Algorithmic
Screttchpad
0.8
0.8
Detalled Scratchpad
Detailed Scratchpad Comma-delim
0.6
Algorithmic Few-shot thought
accuracy
0.4
Instruction-aniy only
0.2
0.2
8 10
12
14
16
18
2
10
12
14
16
16
Number Digits Answer
Number Digits
(a) Various prompting strategics addition
(b) Variants of scratchpad prompting addition
Figure 2: Accuracy on addition questions of increasing length for different prompting methods. Addition questions are of the form + b = c, where a, b, and are positive integers. The number of digits in answer plotted in the x-axis refers the length of c. Accuracy measured over 2000 total examples sampled uni- formly over the length of c. The max length for examples in the prompt prompting shows near perfect length generalization even on extremely long addition questions, and signifi- cantly outperforms its simple few-shot and chain-of-the mhain-of-thhouhh counterpart. Right: using ccratchpad-style output prompt leads to abysmal performance, but adding a few extra details to the scratchpad format leads to non-trivial generalization.
Left: see that algorithmic
rationale along with the final answer in the few-shot examples. In order to generate the rationale for various tasks, we follow the method introduced in Kojima et al. (2022) and use the phrase "let's think step by step" get a model-generater rationale for the few-shot examples.
We measure both in m--istribution and OOD performance in all experiments. For the in-context learning setting considered in this work, the data distribution is determined by the answer lengths of the prompting examples. Thus, questions with answer lengths that fall within those seen in the prompt considered in-distribution, and those with longer lengths considered -ut-of-disttibution. The choice of length is natural given that it is a measure of complexity in the tasks consider, and length generalization has a rich history as measure of systematic generaliza- tion (Csordás et al. 1 Anil et al., 2022). Thus, length generalization provides a good indication for whether the model has learned the underlying algorithm.
Evaluation metric:
Experimental setting: We use the Codex model code - wwwiiiiii-iiiii-eee-ee -002 from OpenAl (Chen et al., 202T] for all experiments. This model has a maximum context length of 8000 tokens. Task examples are sampled uniformly at each length. All results are sampled once using a temperature of 0 and default settings for other hyperparameters. See Section A.2 for task details.
TEACHING ALGORITHMS AS SKILLS
3.1 TWO-NUMBER ADDITION
We begin our analysis by studying the two-number addition task and explore the effectiveness of various prompting strategies with differing levels of ambiguity. We present an algorithmic prompt for addition and compare its performance against the few-shot, chain-of-thought, instruction-only, and scratchpad methods. An illustration of these prompting strategies is shown in Figure 8, and the prompts can be found in Section B.I For all addition experiments, we use 3 prompt examples and restrict these examples to having answers of up to 5 digits in length. We then evaluate on questions up to 19 digits in length. The length of 19 is chosen because this is the level after which the model begins to run out of context. A similar choice is used for all algorithms considered in Section B
Figure 2(a) shows the performance of algorithmic prompting against existing methods on addition problems. These results demonstrate that algorithmic prompt achieves near perfect performance and OOD generalization on addition, while few-shot, chain-of-thought, and instruction-only have decreasing performance as the length of the answer increases. These results illustrate the bene- fit of incorporating algorithmic steps, unambiguous explanations, and demonstrations on running examples in our prompt.
Impact of unambiguous explanations: Figure 2()) compares the performance of using scratchpad and detailed scratchpad as prompts. With detailed scratchpad. to illustrate how the values the answer (A) and the carry (C) is derived (see Figure g We further include additional version that converts the numbers from space-delimited comma-
add more intermediate steps
4

---

Under review as a conference paper at ICLR 2023
delimited, we observed that comma is more effective deliminator for Codex. We find that the scratchpad template performs extremely poorly as a prompt" but including additional details leads to significant boost in performance. We conjecture that the abysmal performance of scratchpad as a few-shot prompt is due to the structure of the solution format being sufficiently regimented to move the model away from its memorized solutions, but not clear enough for the model to extract the true underlying rules and adapt them to new examples.
We also compare the algorithmic prompt to two less-detailed variants. One version (nonexplicit calculation) omits the explicit equation showing how the carry value is derived. This shares the same intuition as the original motivating example. The second version (uncommon operation) requires the model to index the correct digit for a given step. The indexing of a digit at a variable position is a more uncommon operation than the indexing of the digit at the same position each time. our final addition prompt, we introduce mechanism that allows the model to avoid the indexing operation by copying the unprocessed digits over to each step and always taking the last digit. Figure (3(a) illustrates the relative gains that come from the disambiguation of these two aspects of the algorithm. Prompts used for the ambiguity ablation studies can be found in Section B.2
Is the model actually learning the algorithm through in-context learning? Min et al. (2022) have shown that it is not necessary to provide the correct question question-answer answer pairings in the few-shot prompt, suggesting that the model does not rely on the demonstrations themselves to figure out the right way to solve the given task. However, in order to claim that we are teaching algorithms in- context, would like to understand whether the model is actually following the algorithm it is prescribed in the prompt. To do so, we validate that I) mistakes in the intermediate output steps lead mistakes in the final answer, and 2) errors in the prompt significantly impact performance.
We first look at the errors that the model makes. We find that for every question where the final answer was correct, all intermediate steps were also correct. Next, we analyze the performance of the model when we introduce errors into the algorithmic steps in the prompt. We introduce errors into the second digit of the calculation step (digit, + digit, + carry = answer), and keep everything else the same. We consider two types of errors: irregular errors where only subset of the steps contain an error, and systematic errors where all of the steps presented in the prompt contain an error. With irregular errors (prompt shown in Section B.2.3). the model still has chance of ex- trapolating the correct rule based on the unchanged steps. With systematic errors (prompt shown in Section B.2.4), the model should not derive the correct rule if it was truly learning from context, rather than simply mapping to the output format and overriding the in-context steps with what knows from pretraining. Figure (3b) shows that there is a small degradation in performance with irregular errors, while the accuracy drops to near 0% with systematic errors, thus confirming the expected hehavior of model that is actually learning in-context. This is in contrast to the find- ings in which providing shuffled targets (Min et al.) (022) or wrong patterns in chain-of-thought (Madaan and Yazdanbakhsh| (022) do not materially impact model's 'ss performance. Thus, algorith- mic prompting differs from other approaches and constrains the model's behavior towards what is actually being taught in-context.
3.2 TEACHING OTHER ALGORITHMS USING ALGORITHMIC PROMPTING
To validate that the performance of algorithmic prompting is not specific two-number addition, we evaluate model performance on subtraction, multiplication, and parity tasks. Similar to addition, the maximum length evaluated is based on the length that can fit into context for algorithmic prompts.
Subtraction: We follow a similar strategy as addition. We discuss the peculiarities of the subtraction algorithm in more detail in Section f where we combine both addition and subtraction problems. The performance at length 14 is summarized in Table 2 cantly outperforms the few-shot baseline.
We see that algorithmic prompting signifi-
Multiplication:
The multiplication algorithm requires O(n²) steps if we use a strategy similar to the addition algorithm which takes (n)) steps. Inspired by this complication, we explore whether the model's 'ss existing zero-shot or few-shot capabilities can be leveraged in conjunction with algo- rithmic prompting to reduce the complexity of the required instructions. Therefore, instead of using
'The original paper by Nye et al. 2021 performs finetuning using the scratchpad format, whereas we
directly use as a prompt.
5

---

Under review as a conference paper at ICLR 2023
0.8
0.8
Accuaacy
0.6
Accuracy
Algorithmic
Algerithmic Irregular Errors
0.4
Algerithmic w/ Systematic Errors
Algoritmmic
0.2
Algefitmic wi Nonexplicit Calculation Algerithiic wi Uncommon Operation
02
8
10
12
14
16
18
2
10
12
14
16
Number Digits Answer
Number Digits
(a) Algorithmic prompts with varying ambiguity
(h) Algorithmic prompts with errors
Figure 3: Accuracy on addition questions of increasing length for variants on the algorithmic prompt. Left: Two examples of rule ambiguity that address in the final addition prompt non-explicit carry calculation (Nonexplicit Calculation) and digit indexing (Unconmmn Operation). We observe significant difference in performance before and after reducing the ambiguity these operations. Right: Errors are introduced to algorithmic prompt in the digit value of the second number in the equation. Irregular errors are introduced to minority subset of steps in the algorithmic examples, while systematic errors are introduced to all steps of the examples. We see that irregular errors have a minor impact the performance, and systematic errors completely destroy the model's ability to solve this task. This suggests that the model following the algorithm as is specified in-context, rather than loosely mimicking the format of the algorithm.
single-digit multiplication in each step, we perform direct calculations for 1-digit x n-digit numbers. Instead of doing n²² single-digit calculations for two n-digit numbers, we now only need to perform steps of n-digit multiplication. More details can be found in Section A.4 Performance at length 7 is shown in Table 2 and performance across different lengths is shown in Figure 4 We see that the multiplication algorithmic prompt performs well compared to its few-shot and chain- of-thought counterparts, thus illustrating the potential of utilizing model's inherent abilities within the scaffolding of more structured algorithmic instructions.
Parity: We consider the problem of calculating parity of a given binary list. This task has been studied extensively in Anil et al. (2022), and despite the intrinsic simplicity of the algorithm, is far from being solved. Performance at length 20 is shown in Table 2 We see that algorithmic prompt significantly outperforms random chance on this task, which even greater than the few-shot performance reported in Anil et al. (2022). More details can be found in Figure 12 and Section A.4
Table 2: Performance on addition, subtraction. multiplication, and parity tasks. For addition use the few- shot baseline and evaluate length 19. For subtraction
the few-shot baseline and evaluate at length 14. For multiplication we use the chain-of-though baseline and evaluate length 7. These lengths are chosen based on the maximum task length that could into context for the algorithmic prompt. For parity we evaluate at length 20 which is the longest instance reported in Anil et al. 20222.
Method
Addition
Subtraction
Multiplication
Parity
Algorithmic prompt
90.5%
65.6% 16.7%
79.7%
95.0%
Best available baseline
9.5%
5.5%
50.0%
SKILL ACCUMULATION
So far we have demonstrated the ability teach single-algorithms through in-context learning. In this section, we study the model's ability to simultancously learn multiple algorithms and choose the applicable one when solving problems, which we refer as skill accumulation. To do so, we use the cediition-subbracttin negative numbers. Thus, the problems now have four possibilities: a + b, We refer to questions of the form a + b as addition-only questions, and the rest as subtraction-only questions. For subtraction questions, the ordering of the two numbers matter. To see this, consider the examples 43 250 -207 and 543 250 293. When process the digits from right to left, the answer depends on whether the first number is greater than or less than the second number in absolute value, not just the values of the two digits. Thus, subtraction requires different albeit similar- algorithm to addition. For a sense of the relative complexity of the two settings, note that the subtraction algorithm
task. We expand on the addition problem to allow for both positive and
b, -a b, a b.
runs in 2n steps, while the addition algorithm runs in n steps.
To succeed at this task, the model needs to demonstrate the ability to follow different processing paths when the question is addition subtraction. Figure 5 the performance of the combined

---

Under review as a conference paper at ICLR 2023
Siik day Adtery Can Age A30o6
Cort Jeders
Oreb OT Acdedy Gore Stlar
Accursc
Accuracy
0.4
0.4
Algorithmic
0.2
0.2
Chain- thalugh
0.0
20
Number of Digits Answer
Number of Digis Answer
Figure 4: Performance of algorithmic prompt on multiplication questions, where at least one of the two numbers in the question is less than 1000, We use 2 shots of up to 6-digits in answer length in all the prompts. Algorithmic prompt shows superior length generalization compared the baselines.
Figure 5: Accuracy on addition and subtraction ques- tions using combined prompt. We use 6 shots of up to 5-digits in length in the prompt (2 shots of addition and shots of subtraction). "Comb Algo" refers to the combined algorithmic prompt with both addition and subtraction examples, while "single algo" refers to the algorithmic prompt for addition Section 3.1
addition-subbraatioo prompt, with the accuracy broken down by question type. We see that the model able to effectively execute the correct algorithm based on the individual questions. The model exhibits lower accuracy subtraction questions compared to addition-only questions, reflecting the increased complexity of the subtraction algorithm. Comparing the performance on addition- only questions to the addition prompt from Section 3.1 we that there is minimal change in performance despite having an extra other algorithm present in the prompt. More analysis regarding the effects of combining these two algorithms can be found in Section A.5
SKILL COMPOSITION
In this section, we explore the model's ability to learn multiple algorithms that build top of each other. This is a desirable property because it enables the model to learn a more complex algorithm without having to relearn simpler sub-components of that algorithm and enables modularization of complex algorithms. To establish a framework for skill composition, we explore two extensions the addition algorithm: 1) adding multiple numbers together, and 2) solving multiplication by turning it into an addition problem (e.g. by converting 3 * 7 into 7 + 7 + 7). The ability to add multiple numbers builds on top of the ability to add two numbers together. Solving multiplication as addition further builds on the addition of multiple numbers. An illustration can be found in Figure [5| The evaluation dataset contains 1000 examples sampled uniformly by length of answer.
The performance on composite tasks are shown in Figure We teach these algorithms in in-context by creating composite prompt that includes 2 examples from the 2-number addition prompt, exam- ple of addition of 3 numbers, and example of converting multiplication into addition. This forms simple composition strategy (Algo- - (Simple Comp)). This prompt can be found in Section B.7 We also consider two ablations of the composite algorithmic prompt. The algorithm for n-number ad- dition involves wrapping 2-number additions within a larger loop of n - addition problems. Thus, could provide even more information by converting the 2-number addition prompt examples into the same loop format as the 3-number addition example. This version (Algo (Augmented Comp)) provides an upper estimate on multi-number addition and iitippiiaatio-a--addiiit ablation (Algo (No Comp)) only presents the example that illustrates the extended skill. This has no composition and provides a lower estimate on the performance of the two extended skills, and illustrates the improvement that comes from having first learned the component algorithms. See Figure T for an illustration of the different composition strategies.
The second
In-context skill composition is limited by the context length of current models. Unlike the previous experimental results, these composition tasks include a number of questions that were incomplete for the algorithmic prompt. To separate out the issue of context length from the ability of the model to follow an algorithm, in Figure 6 we report performance on only the questions for which the algo- rithmic prompt could fit into context. This subset is also used for all baselines. Figure 6 shows that the algorithmic prompt significantly outperforms few-shot and over, observe that there is minimal difference between the simple composition and augmented composition strategies, and that the "no composition" approach performs much worse than its com- posed counterparts. We also explore two approaches to move beyond context length limitation: 1)
baselines. More-
7

---

Under review as a conference paper at ICLR 2023
0.8
0.8
Acorracy
0.6
0.6
0.4
Algo ISimple Camp)
0.4
Algn (Simple Compl
Algo (Augmented Comp)
Algo (Augmientd Comp)
Fow shot
0.2
Chain of thought
0.2
Chain-dt of thought
Algo INo Comp)
Algo (No Comp!
10
3
6 Number Digits in Answer
10
Number Digits Answer
(a) Multi-number addition
(b) Multiplication-as- aisiiiattioo----aditionnnn
Figure 6: Performance on compositions of skills. "Algo" indicates algorithmic prompting. "Simple Comp" refers to a simple composition strategy where previously taught algorithms are transferred as is. "Augmented Comp" adjusts the previously taught algorithm to match the format of the new task. This simulates version where the full prompt specializes to the new task. "No Comp" uses only the part of the "Simple Comp" prompt that descrihes the new task. This simulates the comparison to learning a skill from scratch without first learning its stepping stones. generalization than the baseline methods. Note that for multiplication, we evaluate the algorithmic methods on a harder task than the few-shot baselines, since force the model to convert the question into the addition of number n times, while for other baselines simply perform 1 n-digit multiplication directly.
observe that the composed algorithmic templates demonstrate hetter
second- -osond-passaaa approach where only the last completed step instead of the full output is used during second inference pass, and 2) a dialogue-like strategy where separate contexts are used for individual subroutines of the algorithm. We describe these approaches and their results in detail in Section A.6 Overall, we find that we can achieve performance comparable to Figure 6 on the full dataset.
USING SKILLS AS TOOLS
In this section, study the behavior of the model when using given algorithm step in solving a larger mathematical reasoning problem. Such problems (e.g GSM8k benchmark (Cobbe et al, 202Th) usually consist of two components: 1) the informal mathematical reasoning component which requires the model to come up with the correct solution steps to arrive at the answer based on the information provided in the question and 2) the calculation of arithmetic operations used in the solution steps. In this paper, we study how the model can leverage a learned algorithm to improve the quality of the second component, i.e., arithmetic operations inside broader reasoning process. Although an external calculator can be used in this case, this will not be possible in general for more abstract skills such as simplifying mathematical equations.
Dataset: We consider the following two math word problem datasets: GSM8k and GSM8k-Hard. GSM8k (Cobbe et al. (02T) consists of high-quality mathematical reasoning problems presented as natural language questions. In order to study the ability to use the addition algorithm while solving GSMSk questions, we simplify the task by filtering for a subset of GSM8K whose solutions consist of only addition steps. The filtering procedure results in 108 pure-addition GSM8K questions. To further illustrate the potential of leveraging skills as a form tool use, we create a hard dataset called GSM8k- -ardd which consists of 50 examples from the pure-addition subset of the GSM8k with larger numerical values. For more detail on the datasets, see Section A.7
We first evaluate whether the chain-of-thought prompt prompt for the addition operation. To do so, we use a single prompt to illustrate both the informal mathematical reasoning skill and the addition skill. Specifically, we embed the addition algorithm within the chain-of-thought solutions whenever the solution calls for the summing of numbers. We use an <ALGO> flag within the prompt to indicate that algorithmic reasoning should be used, and the <NONALGO> flag to indicate direct, non-algorithmic calculations. Results are shown in Fig- ure (a) A detailed description of this prompting strategy and the corresponding results can be found in Section A.7.I We find that including algorithmic output in the examples significantly dis- rupts the model's s informal mathematical reasoning abilities in the <ALGO> experiment, but leaves the <NONALGO>> performance relatively unchanged. This demonstrates the existence of interference between the two skills. This is in contrast to the results from skill accumulation Section 4 We conjecture that this occurs when mix highly different skills within the same context.
be augmented with the algorithmic
Next, motivated by context length limitations and the interference issue that we have identified, propose way alleviate these problems through dialogue-like interaction between models loaded with different prompts. We do so by teaching the model to output specific tokens for when the addition algorithm should be called. See Figure 7 for an example. See Section A.7.2 for de-
8

---

Under review as a conference paper at ICLR 2023
0.90
Q: June liked to cellect cat stickers. ahe total 768835
<ALGO> <NONALGO>
collection. Ber tuir stater Bonnte also antted eat stickers and had 63212920 in her collestion, For their birthday, their grandperents gave then 250148 eat stickers each. Now nany compined stickers did they have?
Add only GSMBK Accuracy
0.75
0.70
0.65
had
<ACDO_STARRD> (TA. ADD ALC0>101
0.60
8982 stickers. Bornie had
0.55
<A'00 START96321 21179822112202255188--a Ann A16006
3462068 a;ickers. Togethar, thay had <alG0_ STARI=1018993 (112999-5111166--226 ADD ALGO> 64462051 stickers, The snswer is 61462051.
0.50
No plan No algo
No plan W/ algo
W/ plan alge
plan algo
Performance on GSM8k addition-only subset
(h) Example of tool use for GSM8k-Hard.
Figure 7: Addition algorithm tool use in solving GSM8K questions. Left: Ablation study with or with- algorithmic ouiput the prompt output. "W/ algo" indicates that algorithmic ouiput is embedded within prompt examples, and "no algo" indicates that only of-nn-of-thought rationale is included the prompt. <ALGO> flag indicates that algorithmic reasoning is encouraged in the output, while <NONALGO> flag indicates that calculations are done directly by the model. "Plan" indicates a chain-or thain-of-thee thought strategy that summarizes the solution plan before executing individual reasoning steps. We see that having algorithmic output within context leads significant interference with the model's informal mathematical reasoning abilitics. This al- leviated by using a summary before the algorithmic output, but not fully. Right: An example question-answer pair from the GSM8k-Hard addition dataset, which includes GSM8k-like questions with large numerical values.
tailed description of this approach. The performance on GSM8K Hard is shown in Table 3 Logical accuracy refers to the correctness of the solution setup, while addition accuracy refers to the correct- ness of the calculations steps within the solution. We see that despite removing the algorithm output from the context of the first model, we still observe interference coming from the use of specific tokens in the informal natural language solution steps. Nonetheless, the method that leverages algo- rithmic tool use still achieves double the accuracy as the baseline chain- -fann-ff-hooooo of-thought method without algorithmic prompting. Lastly, this result illustrates the ability of dialogue- context length limitations, as single model would not have fit all the output within its context.
tool use to bypass
Table 3: Performance on GSM8K- Hard addition dataset with or without algorithmic tool use. We see that the overall performance is doubled when we call on second model loaded with the algorithmic addition prompt to perform addition calculations, demonstrating the potential of leveraging in-context algorithmic skills as a form of tool-use. Moreover, we observe that this performance gain comes directly from more accurate addition accuracy. and the model that performs informal mathematical reasoning still suffers from interference due to the of specific tokens in the logical reasoning output, as shown in the decreased logical accuracy.
Method
Overall Accuracy
Logical Accuracy
Addition Accuracy
Chain-of-thougee w/ Algo call
55.8%
57.7%
98.4%
Chain-of-thought wo/ Algo call
27.4%
70.6%
61.9%
7 CONCLUSION AND FUTURE WORK
Motivated by the potential of in-context learning as a general mechanism for compositional skill acquisition in LLMs, we studied teaching algorithmic reasoning via in context learning. We iden- tified and studied the fundamental building blocks towards this goal and investigated four settings: teaching an algorithm as a skill, skill accumulation, skill composition and using skills as tools. We investigated the shortcomings of existing approaches and proposed algorithmic prompt to alleviate them, showing that it leads to significant performance boost in various algorithmic reasoning tasks. Our work suggests that it may be possible to convert longer context length to better reasoning per- formance by providing more thorough explanations. This highlights the ability to leverage long contexts (either through increasing context length or other means such as implementing recurrence or an external memory) and generate more informative rationales as promising research directions.
We identified the interference phenomenon for tool use application and investigated different ways to reduce its effect. Our observations about interference suggest that teaching the model the ability to retrieve or selectively attend to specific instructions when solving the particular problem is an important future direction. Moreover, given that there are ongoing efforts in the community to increase the context length of LLMs, it is of interest to design more challenging tasks for each of the four introduced settings and investigate what capabilities can be taught to LLMs when having access to extremely large context length.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Akyurek, E. and Akyurek, A. F. (2022). Notes on teaching gpt-3 adding numbers.
Anil, C., Wu, Y., Andreassen, A., Lewkowycz, A., Misra, V., Ramasesh, V., Slone, A., Gur-Ari, G., Dyer, E., and Neyshabur, B. (2022). Exploring length generalization in large language models. arXiv preprint arXiv:2207.0490)
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P. Sastry, G., Askell, A., al. (2020). Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901.
Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. d. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al. (2021). Evaluating large language models trained on code. arXiv preprint arXiv:2107.0337
Chen, X. (2022).
Chen, X., Liang, C., Yu, A. W., Song, D., and Zhou, D. (2020). Compositional generalization via neural-symbolic stack machines. Advances Neural Information Processing Systems, 33: 1690- 1701.
Chiang, T.-R. and Chen, Y.N. (2018). Semantically-aligned equation generation for solving and reasoning math word problems. arXiv preprint arXiv: 1118710.072.
Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. (2022). Palm: Scaling language modeling with pathways. arXiv preprint arXivv2204.02311
Cobbe, K., Kosaraju, V., Bavarian, M., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. (2021). Training verifiers to solve math word problems. arXiv preprint arXiv:2 10. 14168.
Creswell, and Shanahan, M. (2022). Faithful reasoning using large language models.
https://arzivorr/ab//22000 14271.
Csordás, R., Irie, K., and Schmidhuber, J. (2021). The devil is in the detail: Simple tricks improve systematic generalization transformers. In ACL.
Faldu, K., Sheth, A., Kikani, P., Gaur, M., and Avasthi, A. (2021). Towards tractable mathemati- cal reasoning: Challenges, strategies, and opportunities for solving math word problems. arXiv preprint arXiv:2111.05364
Gordon, J., Lopez-Paz, D., Baroni, M., and Bouchacourt, D. (2019). Permutation equivariant models for compositional generalization in language. In International Conference Learning Represen- tations.
Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Stein- hardt, J. (2021). Mcasuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03874
Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E.. Cai, T., Rutherford, E., Casas, D. d. L., Hendricks, L.. A., Welbl, J., Clark, A., al. (2022). Training compute-optimal large language models. arXiv preprint arXiv:2203.
Jiang, A. Q., Li, W. Tworkowski, S., Czechowski, K., Odrzygó2dž, T., Miloš, P., Wu, Y., and Jam- nik, M. (2022). Thor: Wielding hammers to integrate language models and automated theorem provers. arXiv preprint arXiv:2055.18893
Jones, E. and Steinhardt, J. (2022). Capturing failures of large language models via human cognitive biases. arXiv preprint arXiv:2202.12220
Jung, J., Qin, L., Welleck, S., Brahman, F., Bhagavatula, C., Bras, R. L., and Choi, Y. (2022). Maieutic prompting: Logically consistent reasoning with recursive explanations.
Kaiser, f., and Sutskever, I. (2015). Neural gpus learn algorithms. arXiv preprint 15 1.8228..
10

---

Under review as a conference paper at ICLR 2023
Kaplan, J.. McCandlish, S., Henighan, T., Brown, T. B.. Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. (2020). Scaling laws for neural language models. arXiv preprint arXiv:2001.08361
Kim, J., Hong, G., Kim, K.-m., Kang, J., and Myaeng, S.-H. (2021). Have you that number? investigating extrapolation in question answering models. In Proceedings of the 2021 Conference on Empirical Methods Natural Language Processing, pages 7031-7037.
Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, (2022). Large language models are zero-shot reasoners.
Lewkowycz, A., Andreassen, A., Dohan, D., Dyer, E., Michalewski, H., Ramasesh, V., Slone, A., Anil, C., Schlag, I., Gutman-Solo T., et al. (2022a). Solving quantitative reasoning problems with language models. arXiv preprint arXiv:2206./445
Lewkowycz, A., Andreassen, A.. Dohan, D. M., Dyer, E. S., Michalewski, H., Ramasesh, V., Slone, A., Anil, C., Schlag, I,, Gutman-Solo, T., Wu, Y., Neyshabur, B., Gur-Ari, G., and Misra, V. (2022b). Solving quantitative reasoning problems with language models.
Li, W., Yu, L., Wu, Y., and Paulson, L. C. (2020). Isarstep: benchmark for high-level mathematical reasoning. arXiv preprint urXiv:2006.0922 09265.....
Ling, W., Yogatama, D., Dyer, C., and Blunsom, P. (2017). Program induction by rationale genera- tion: Learning to solve and explain algebraic word problems. In ACL.
Madaan, A. and Yazdanbakhsh, A. (2022). Text and patterns: For effective chain of thought, it takes two to tango. arXiv preprint arXiv:2209.07686
Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L. (2022). Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXiv:2202.1288. 12837.
Nogueira, R., Jiang, Z., and Lin, J. (2021). Investigating the limitations of transformers with simple arithmetic tasks. arXiv preprinl
Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H., Austin, J., Bieber, D., Dohan, D., Lewkowyez, A., Bosma, M., Luan, D., et al. (2021). Show your work: Scratchpads for inter- mediate computation with language models. arXiv preprint arX0v:2112.00114.
Parisi, A., Zhao, Y. and Fiedel, N. (2022). Talm: Tool augmented language models. arXiv preprint arXiv:2205. 12255.
Polu, S. and Sutskever, I. (2020). Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.0339)
Rabe, M. N., Lee, D., Bansal, K., and Szegedy, C. (2020). Mathematical reasoning via self-
supervised skip-tree training. arXiv preprini arXiv:2006.04757.
Razeghi, Y., Logan IV, R. L.., Gardner, M., and Singh, S. (2022). Impact of pretraining term fre-
quencies on few-shot reasoning. arXiv preprint a2Xiv:2202.07206.
Saxton, D., Grefenstette, E., Hill, F., and Kohli, (2019). Analysing mathematical reasoning abili- ties of neural models. arXiv preprint arXiv:1904.01557
Thawani, A., Pujara, J., Szekely, P. A., and Ilievski, F. (2021). Representing numbers in nlp: survey and a vision. arXiv preprint arXiv:2103.13132
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polo- sukhin, I. (2017). Attention is all you need. Advances in neural information processing systems, 30.
Veličković, P. and Blundell, C. (2021). Neural algorithmic reasoning. Patterns, 200733.
Wang, H., Yu, M., Guo, X., Das, R., Xiong, W., and Gao, T. (2019). Do multi-hop readers dream of reasoning chains? arXiv preprint arXiv: 1910. 14520.

---

Under review as a conference paper at ICLR 2023
Wang, X., Wei, J., Schuurmans, D., Le, Q. Chi, E., and Zhou, D. (2022a). Rationale-augmente ensembles in language models. arXiv preprint arXiv:2207.00777.
Wang, X., Wei, J., Schuurmans, D., Le, Q. Chi, E., and Zhou, D. (2022b), Self-consistency im- proves chain of thought reasoning language models. arXiv preprint arXiv:2203.11171.
Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., et (2022a). Emergent abilities of large language models. arXiv preprint mrXiv:2206.07642
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Chi, E., Le, Q., and Zhou, D. (2022b). Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903
Welleck, S., Liu, J., Bras, R. L., Hajishirzi, H., Choi, Y., and Cho, K. (2021). Naturalproofs: Mathematical theorem proving in natural language. arXiv preprint arXi:22104.01112
Wu, Y., Jiang, A. Q., Li, W., Rabe, M. N., Staats, C., Jamnik, M., and Szegedy, C. (2022). Autofor- malization with large language models. arXiv preprint arXiv:2205. 12615.
Xhonneux, L.-P., Deac, A.-I., Veličković, P., and Tang, J. (2021). How to transfer algorithmic rea- soning knowledge to learn new algorithms? Advances in Neural Information Processing Systems, 34:19500-19512.
Xu, K., Li, Zhang, M., Du, S. S., Kawarabayashi, K.-i., and Jegelka, (2019). What can neural networks reason about? arXiv preprint arXiv: /32/1.
Yan, Y., Swersky, K., Koutra, D., Ranganathan, P., and Hashemi, M. (2020). Neural execution
engines: Learning to execute subroutines. Advances in Neural Information Processing Systems, 33:17298-17308.
Zhou, D. (2022).
Zhou, D., Schärli, N., Hou, I.., Wei, J., Scales, N., Wang, X., Schuurmans, D., Bousquet, O., Le, Q. and Chi, E. (2022). Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2005.10625.
A APPENDIX
A.1 ADDITIONAL RELATED WORK
Mathematical reasoning CChang and Chen 2018 Saxton et al. 2019) has been subject of interest for long time. Faldu et al. (2021) summarizes the mathematical reasoning benchmarks that are in the form of math-word problems. In addition to this class of benchmarks, formal mathematics in the form of theorem-proofs (Rabe al. 2020 Li et al. 2020 Polu and Sutskever, 2020 Welleck al.) 2021 Jiang et al. 2022 Wu et al. 2022) has been considered extensively. In this work we focus on algorithmic reasoning for arithmetic tasks and solving GSM8K (Cobbe al. 2021) problems.
Algorithmic reasoning is typically approached via using structured architectures such as graph neural networks(GNNs) and modifying the architecture align to the algorithms under considera- tion (Kiser and Sutskever
2015] Chiang and Chen 2018 Xu et al., 2019 Gordon et al., 2019 Yan al. 2020gJCher et al. 2020; Xhonneux et al.]]2221 Veličković and Blundell (021)) or to the input format (Thawani et al. 2021). However, in this work we focus on teaching algorithmic reasoning to
general purpose transformer-based (Vaswani et al. 2017) models.
There has been some recent works investigating in-context learning phenomena. Razeghi et al. (2022) showed that the performance of LLMs on mathematical calculations correlates with term frequency in the training data. Min et al. (2022) investigate which parts of the (input, output) pairs in the prompt play a role in model's 's performance on 12 NLP tasks. Madaan and Yazdanbakhsh (022) investigate this for sfain-of-though prompts and conclude that the combination of text and patterns together play a role. JJnnss and Steinhardi (0022) compares failure modes of LLMs to human biases in the context of few-shot prompts.
12

---

Under review as a conference paper at ICLR 2023
There have been attempts of improving chain-of-thoughh scratchpad- prompts for two-number addition. Akyurek and Akyurek (2022) provides an analysis of the scratchpad approach to prompt- ing. They studied various style choices and natural language descriptions and evaluated their impact on performance. Their focus is on what type of formatting works best with scratchpad, and show that having certain natural language descriptions within the prompt benefits performance. In trast to their approach, we focus much less on the formatting and style of the provided explanations. Instead, our key insight is in elucidating certain operations in an unambiguous manner. Moreover, Zhou (2022) and Chen (2022) proposed other variants of the chain-of -ft--fgh-thhgtt approach to addition. We compare the performance of these three methods in Figure [23] and we find that all of them sig- nificantly underperforms the algorithmic and few-shot baselines. We provide a detailed comparison of these prior works in Section A.8
A.2 ADDITIONAL INFORMATION ON EXPERIMENTAL SETUP
In T we provide a summary of experimental settings for all arithmetic and parity experiments in this paper.
Table 4: Evaluation setting for arithmetic and parity tasks. Questions are sampled uniformly based on an- swer lengths, with an average of 100 samples per length. *For composition tasks of multi-number addition and pultiplicationaa-aadiiiie
the number of shots indicate the number of prompt examples that illustrate the particular composition skill, but more examples of other skills may be included in the prompt. See the corresponding sections for more details.
Task
Length range in eval
No. of shots in prompt
Max length in prompt
Two-number addition
19
Subtraction (combined)
2- 14
6 (2 add, 4 sub)
5
Multiplication
7
6
Parity
2 30
8
Multi-number addition
2 10
1
4
Multiplication as addition
2 10
1"
2
A.3
ADDITIONAL RESULTS TWO-NUMBER ADDITION
This section includes additional details and results for Section 3
In Figure 8 we provide an illustra- tion of different prompting strategies for two-number addition with differing levels of detail in the explanation.
The role of natural language within algorithmic prompt: Since the algorithmic prompt lever- ages both natural language descriptions and intermediate computations, we disentangle the two components and study the role that natural language plays in the algorithmic prompt. To do so, we consider the following ablations: 1) symbols-only version of the original algorithmic prompt for addition, where we strip away most of the natural language descriptions, but still retain the use of certain keywords such as Len and Max (Section B.2.5) 2) symbols-only version where keywords Len and Max are replaced with random words VBZ and UXC version where keywords are replaced with adversarial words Str and Min, which are associated with known other operations in the pretraining distribution. The results of the ablations are shown in Figure? [ We see that there is a small but clear drop in performance when we move from the original prompt to the symbols-only prompt. We observe a further drop when certain keywords are replaced by uninformative symbols. These results point to the usefulness of leveraging the natural language understanding of L.MS in specifying aspects of the algorithm. Moreover, we see that using misleading symbols leads to significant drop in performance, which further illustrates the model's 's reliance on its pretraining when interpreting the algorithmic instructions.
and 3) symbols-only
Error analysis: We perform an error analysis for the results using algorithmic prompting for Table We that the model
two-number addition. Details of various error categories are found in can reliably perform single-step operations, such as identifying the max number of digits, calculating two-digit sums (with carry), and copying the previous carry value the next step. However, the
13

---

Under review as a conference paper at ICLR 2023
Ieput:
Input:
128+367
128+367
Tazget:
Target:
<scratch>
<soratch>
[1,2,8]
digits.
2 8
7
c:
[3,6.7] has digits.
[1,2,8] + [3,6,7] C-D 8+740=15 A-25 C->1
+
9
C:
[1,2] [3,6] A=[5] C=1 2+6+1=9
A->9 C->0
[1] + [3] A=[9,5]] C=0 1+340=1 4-24 C-50
9
[1 A=[4,,95] c=0
</scratch>4
</scrateh>
Scrutchpad
Detailed seratchpad
comma-delim
Problem: 1284367
Problem: 128+367=? Explanation:
Length of NN is 3. 18=(1,2,8]. Length of SN is 3. 6N=[3,6,7]. FN[3]=8. [M[3]=7. c[3]=0. Since 8+7+0=15, 15810=5. Length of is 1. Thus R=[5] Since (10=5) c(2]=1.
Lat's think step by step.
2. FN-[1,2] Length of is 2. SN- PN[2]=2. SN[2]=6. c[2]=1. Since 2+6+1=9, 9t10=9. Length is 2. Thus [= Since (9-9)/10=0, c[1]=0.
Length
128-3377-1224334-6444444
7=495.
The final Answer is 495.
There
digits c[0]=D. Thus the process complete. The final Answer is [4, 9,51
Chaon-of-thought
Algorithmic prompt
Figure 8: Examples of the two-number addition prompt using different techniques.
1.0
Accuracy
0.6
0.4
Algo Original
Algo Symbols Only
0.2
Algo w/ Uninformative Symbols
Algo Misleading Symbols
0.0
10
12
14
16
18
Number of Digits in Answer
Figure Performance of various symbols-only algorithmic prompts on the two-number addition task. Symbols-only prompt strips natural language from the original prompt. but keeps the use of keywords such Len and Max. Uninformative symbols replaces Len and Max with random words VBZ and UXO. Mislcad- ing symbols replaces Len Max other known words prompt performs worse than the original algorithmic prompt, and that removing the use known kcywords and replacing them with uninformative symbols results in a further drop in performance. This illustrates the usefulness of natural language descriptions in the prompt. Using misleading symbols leads to significant drop performance, further demonstrating the model's reliance its pretraining when interpreting the algorithmic instructions.
and Min. We see that the symbols-only
model struggles with multi-step operations such as separating digits by comma and copying all digits within a list from the previous step.
We also see that most of the errors happen in the earlier steps of solving the problem. This is illustrated in Figure I0 The first steps have the most number of unprocessed digits, which may explain why they are the most error prone as the model struggles to copy the lists of digits from step to step.
14

---

Under review as a conference paper at ICLR 2023
Table 5: Error analysis of two-number addition algorithmic prompt results. We that the most error-prone steps are faithfully copying list from previous step, followed by counting and separating digits into list format.
Error Category
Overall Accuracy
Wrong Questions Only
Count first number digits
99.55%
88.46%
Count of second number digits
99.04%
75.64%
Identify max number of digits between first and second number
100.0%
100.0%
Convert first number list format
99.6%
89.74%
Convert second number to format
99.19%
79.49%
Copy unprocessed digits from first number Copy unprocessed digits from second number
99.55%
88.46%
97.88%
16.15%
Extract digit from unprocessed first number digits Extract last digit from unprocessed second number digits
99.9%
97.44%
99.85%
96.15%
Copy previous carry value in two-digit calculation step Sum two digits calculation
100.0%
100.0%
100.0%
100.0%
Calculate carry value from two-digit calculation step
99.8%
94.87%
Copy previously accumulated answer digits
99.14%
78.21%
Insert new value from two-digit calculation result into answer
99 99.65%
91.03%
30
Number of Examples
25
20
10
0.2
0.4
0.6
0.8
Progress Ratio to Completion
Distribution of where first occur in two-number addition questions using algorithmic prompt. Progress ratio calculated (first_error _errrrrttrpp// total_steps). We see that errors oceur earlier steps, where model has more remaining digits to process.
Figure 10:
A.4 ADDITIONAL RESULTS TEACHING OTHER ALGORITHMS
This section includes additional details and figures for Section 3.2
To choose reasonable value of for this experiment, we evaluate the model's zero-shot accuracy in n-digit multiplication (shown Figure [T]. We see that after 3, the zero-shot performance deteriorates drastically. Thus, we restrict to < 3. If number has more than 3 digits, we break down into groups of 3 digits and add the resulting sub-components appropriately. For simplicity, 1000, so that we only need to perform the group splitting on one the two numbers.
Multiplication:
consider the problems where least one of a and b is less than
The prompt used for this experiment is displayed in Section B.4.2 in answer length in the prompt. As seen in the prompt, we explain how to break large numbers into groups of 3 or fewer digits in natural language. This natural language description is detailed enough such that the model can correctly extrapolate to creating multiple splits for long numbers, though it has only examples of single splits in the prompt. This illustrates the benefit
We use shots of up 6-digits
15

---

Under review as a conference paper at ICLR 2023
of using natural language instructions along with showing the intermediate calculation steps, and showcases the model's ' ability to extrapolate beyond just length generalization.
1.0
Zero-shot
0.8
Accuracy
0.6
0.4
0.2
0.0
2
10
Number of Digits in Answer
Figure 11:
Zero-shot accuracy of one-digit multiplication, where the other number can have up to 11 digits. We see that the accuracy starts to drop after 3 digits in the answer.
Parity: Similar to (Anil al. 2022 we investigate the parity problem as an example of length generalization. We use algorithmic prompting for parity and compare its performance to few-shot baseline, as well as to scratchpad-style prompt as discussed Anil al. (2022). Figure 12 cap- tures the performance of these three approaches 8-digits in answer length in the prompt. Each point in Figure [eguuee[2rppreeentt average over 100 random samples and nificantly outperforms both baselines and while the baselines' performance reaches random chance (50%) around length 5, algorithmic prompt keeps accuracy of around 80% to lists of up 30 digits. Section B.5 and B.6 depict the prompts used in this experiment.
lists of varying sizes. We use 2 shots of up to
the same examples for all methods. We observe that algorithmic prompt sig-
1.0
0.8
Accuracy
0.4
Algorithmic
Scratchpad (Anil et al 2022)
Chain-of-thought (Anil 2022)
0.2
Few-shot (Codex)
50% (Random chance)
0.0
5
10
15
20
25
30
Number of Elements in the List (List length)
Figure 12: Investigating the performance of algorithmic prompt on parity problem and comparing it to scratch- pad few-shot prompt of Anil et al. (2022) well as few-shot prompting OpenAl's Codex. Fach point the Algorithmic plot correspouds to 100 random samples of binary list of the same length. Sections [B.5] B.6 depict the prompts used algorithmic
scratchpad methods. The number of examples used in prompt two. The scratchpad method uses the prompt from Figure in (Anil et al. 2002).. Chain-of-thouse values are directly copied from Figure in Anil et al. (2022) (few shot finetuning few shot eval), and correspond to prompt from Figure 10 in Anil al. 2002)
A.5 ADDITIONAL RESULTS FOR SKILL ACCUMULATION
This section includes additional details and figures on skill accumulation from Section
We study whether the superior performance of the algorithmic prompt can be attributed the fact that it much longer than the few-shot prompt. To control for this variation, we perform an ablation the addition-subraaction of the few-shot baseline. We generate examples of addition and sub-
16

---

Under review as a conference paper at ICLR 2023
traction, such that the total number of tokens is equal to the number of tokens used in the algorithmic prompt. Figure 13 shows that having more few-shot examples does not improve performance.
1.0
Few-shot 6-shot
Few-shot N-shot
0.8
Accuracy
0.6
0.4
0.2
2
4
6
8
10
12
14
Number of Digits in Answer
Figure 13: Accuracy on combined addition- subtrictionttattionn questions using a few-shot prompt. Since the algorith- mic prompt uses more tokens in the prompt, we perform an ablation for the few-shot baseline and use n number of examples in the prompt, where chosen such that the prompt length matches the algorithmic prompt. We see that there no improvements in performance beyond the examples used in the baseline.
To further study the effects of teaching addition alongside subtraction, we evaluate two subtraction- only prompts. The first removes the addition-only prompt examples from the combined addiition-subtractiin prompt. In the combined prompt, 6 examples are provided, with of them being addition-only examples. After removing the addition-only examples, only examples in the prompt. The second subtraction-onl prompt matches the number of shots as the original combined prompt. but includes only subtraction-only examples for all 6 shots. The results are shown in Figure [1(a) We see that using only the 4 subtraction-only prompt exam- ples (Combined Algo, Sub examples-only) results in a significant decrease performance compared to the combined algorithmic prompt. However, when we are able to match the same number of shots (6) as the combined prompt (Sub-only Algo), we can recover the original performance. This demonstrates the synergy and positive transfer when simultaneously learning algorithms that share similarities. As a control experiment, we also observe in Figure 14(b) that adding more shots to an addition-only prompt does not improve performance beyond the original prompt, which supports the conclusion that addition-only performance using the combined prompt is not harmed by having other algorithms in the same prompt.
left with subtraction-
Finally, we note that the prompt development for this task was non-trivial, and the best performance required adding all combinations of positive and negative numbers in the prompt. Thus, scaling to larger number of algorithms may call for more efficient strategies.
A.6 ADDITIONAL RESULTS FOR SKILL COMPOSITION
This section includes additional details and figures on skill composition from Section In Fig- ure [3] we provide an illustrative demonstration of the change in the prompt when going from two- number addition to multi-number addition to aatpliicaaioo-aaaddiitite showing the progression in complexity.
In Figure 17, we include the results for the entire evaluation dataset, including examples that ran out of context in the first pass through the model. In Figure [8] we show the same results but using the count of numbers being added as the x-axis. We employ second-pass strategy, where we append the last completed step from the first-pass output to the original test question, and perform another inference pass using the new prompt. We observe that this simple second-pass strategy allows to correctly solve a portion of the questions that were previously incomplete. However, the performance is still significantly below the hypothetical upper estimate performance achieved by first-pass completed questions.
In Figure 19, we use a dialogue-like like approach where we employ two models loaded with specialized prompts. For multi-number addition, prompt one model with example that explains how to
17

---

Under review as a conference paper at ICLR 2023
1.0
0.8
Accuracy
0.6
Accuracy
0.6
0.4
0.4
Combined Algo Sub anly
0.2
sub-only Alge Sub-only
Addition Algo 3-shot
Combined Algo, Sub examples-only Sub-only
Addition 6-shot
0.0
10
12
10
12
16
18
Number Digits in Answer
Number Digits in Answer
(a) Subtraction-only prompts on subtraction
(b) Addition-only prompt on addition
Figure 14: Left: Performance subtraction-only questions. "Combined Algo" refers using 4 examples of subtraction questions and examples addition questions within the prompt. "Sub-only Algo" refers using 6 examples of subtraction questions within the prompt. "Combined Algo, Sub examples-only" refers to using 4 examples of subtraction questions within the prompt. We see that removing addition-only examples from the prompt significantly harms performance subtraction-only questions, thus showing the positive transfer that comes from having addition examples. Right: Performance addition-only questions using addition- only prompts with different number shots. We see that performance the original addition prompt on the addition task is already saturated on the number of shots.
Q: 3*11
Q: A: The subproblema aze 128+367=AN81,
question converted into 11+11+11.
9:
ANS1+6000=AMS2.
Q: 128+367=?
A: The subproblems are 11+11=AN81, AN81411=AN52,
0: 128+367-7
128
128
367
2: 11+11-?
367
11
95
11
495
C: 40506000=?
22
495
60000
3: 22+11=2
22
6495
33
Figure 15: Illustration of the tasks and algorithmic prompting strategies considered for skill composition in Section The actual prompts use algorithmic prompting for each addition question. Starting from simple two- number addition, we explore nuult--umberr addition which decomposes the problem into set of two-number addition questions, then extend it further to multiplication-al as--a---aaa as-addiion which converts multiplication question into equivalent multi-number addition question.
solve multi-number addition problems as a sequence of two-number addition problems, and prompt second model with the algorithmic prompt for two-number addition. Within the prompt for multi- number addition, we employed specialized tokens to indicate the start and end of a two-number addition problem that the model needs query the cadition-promptter model for. We extract the two-number addition question and send it to the second model, then retrieve the answer and allow the The
first model to continue with its output. We use the same strategy for aattiillicatio-aa--ddiiite prompt of this first model can be found in Section f0 multi-number addition, and Section B. for multiplication-as casoon-----dee addition. antiiiitiinnaiiiion..... We find in Figure 19]that we are able to generalize out-of--istriilee distribution from single prompt example, and avoid context length limitations when evaluated on the longest problems in the evaluation data. This approach allows us to achieve performance comparable to those in Figure 6 on the full dataset.
18

---

Under review as a conference paper at ICLR 2023
128+367=?
Q: 902+7145+6=?
129+367-?
Q: 802-7145++67
002-714546m?
subproblens
subpreblens
At The sutproblees are 602 31145-A51, ANG1 6wAND2.
128
are A3- ANG1-6-AR52.
subprobiens are
aze 302+1145-A891,
267
128-367-2888..
AM51-6-A852.
80247145-7
802-7145-7
Q: B02-7145-2
B02
802
B02
7145
367
7145
7145
7947
7847
7947
Q: 7947+6-2
Q: 7947+6-2
G: 7945+667
1947
7947
7947
1953
7953
7953
Simple Composition
Augmented Composition
No Composition
Figure 16: Illustration various composition strategies. The actual prompts use algorithmic prompting for each addition question. Simple composition combines the prompt from previously taught skill to new examples illustrating the composed skill. Augmented composition changes the previous prompt examples so that they treated special cases of the new composed skill. No composition includes only examples illustrating the new composed skill.
1.0
1.0
Accuracy
Accuracy
0.6
0.4
Algo (Simple Camp)
0.4
Algo (Simple Comp)
Ao (Augmented Comp)
Algo (Augmented Comp)
Few-shot
Few-she Few-shot
0.2
Chain-of-thought
0.2
Chain-of-thougee
go (No Comp)
Algo (No Comp)
0.0
0.0
2
10
10
Number Digits in Answer
Number of Digits Answer
(a) Multi-number addition
(b) Mullipiiaation-as-atttiio
Figure 17: Performance on compositions of skills. Due to length of the algorithmic output for this task, a number of the longest examples exceed the context length limit for Codex. We employ a second pass strategy to get a final answer for the incomplete questions, where keep in-context only the last completed state from the first pass. The dotted lines consider only questions for which the model completes the output within one pass, and provide an upper estimate on performance. The dashed lines consider all incomplete questions as false, and provide an lower estimate on performance. We observe that although the algorithmic prompting methods are suffering from having to do second pass for the longer samples in this task, they still demonstrate better generalization than the baseline methods. Note that for multiplication, we evaluate the algorithmic methods on a harder task than few-shot baselines, since force model to convert the question into the addition of a number n times, while for other baselines we simply perform 1 x n-digit multiplication directly.
Can the model extrapolate to novel compositions? We explore whether the model can general- ize to new setting than what is demonstrated in the composition skills. In Figure [9 we explored learning multi-number addition by calling the addition algorithmic prompt for each two-number addition subroutine. Now, we evaluate the same multi-number addition prompt to see if it is able to solve multi-number addition- subtraction questions (an extension to the setting in Section 4 We test the model's generalization ability for composition since the model does not see any example of multi-number subtraction. Here, the only change is that we call on the addition cutttiinn-ubttattion com- bined prompt each time the specialized tokens outputted. The results are shown in Figure 20 We see that the model is able to perform multi-number addition addition-subtraation despite never seeing a demonstration of this skill. The algorithmic prompt outperforms the few-shot and chain-of-thought baselines while demonstrating good length generalization.
A.7 ADDITIONAL RESULTS FOR TOOL USE
This section includes additional details and figures for tool use in Section
19

---

Under review as a conference paper at ICLR 2023
1.0
0.8
Accuracy
Accuracy
0.6
Algo (Simple Comp)
0.4
Algo (Simple Comp)
go (Augmented Comp)
Algo (Augmented Comp)
Few-shot
Few-shot
0.2
Chain-of-thought
0.2
Chain of thought
go (No Comp)
Algo (No Comp)
0.0
0.0
2
10
Count Numbers Added
Single-digi. Multiplier
(a) Multi-number addition
(b) Multiplication-al as-addition
Performance on compositions of skills with the x-axis heing the count of numbers being added instead of the number of digits in answer used in Figure [77] Due length of the algorithmic output for this task, number of the longest examples exceed the context length limit for Codex. We employ second pass strategy get final answer for the incomplete questions, where we keep in-context only the completed state from the first pass. The dotted lines consider only questions for which the model completes the output within one pass, and provide an upper estimate on performance. The dashed lines consider all incomplete questions false, and provide lower estimate performance. We observe that although the algorithmic prompting methods are suffering from having to second pass the longer samples this task, they still demonstrate better generalization
Figure 18:
the baseline methods. Note that multiplication, we evaluate the algorithmic methods on a harder task than the few-shot baselines, since we force the model to convert the question into the addition of number n times, while for other baselines simply perform n-digit multiplication directly.
1.0
1.0
Accuracy
0.6
Accuracy
0.6
0.4
0.4
A/go (Simple Comp)
Algo (Simple Comp)
Algo (Simple Comp) Incompletes
Algo (Simple Comp) w/ Incompletes
0.2
Algo Call Comp)
0.2
Call (No Comp)
go Call (No Comp) w/ Incompletes
Ao Call (No Comp) w/ Incompletes
0.0
0.0
Number of Digits in Answer
Number of Digits Answer
(a) Mllli--uubbr addition
(b) Multiplication as ss-adiition
Figure 19: Porformance on compositions of skills with algorithmic calls. Due to length the algorithmic output for this task, number of the longest examples exceed the context length limit for Codex. We employ dialogue-like like strategy to get final answer for the incomplete questions, where allow models loaded with different prompts to interact with each other through the of specialized tokens learned in-context. The dashed lines consider incomplete questions as false, Call" refers to this dialogue-lik like method, which is akin to the "No Composition" setup since we do not include the two-number addition examples in the prompt. We find that we are able to generalize out out-of-die of-distribution from single prompt example of digits length 2, and avoid context length limitations when evaluated the longest problems in the evaluation data.
provide an lower estimate on performance. "Algo
Dataset:
shows an example question and answer pair from GSM8K with chain-of-thought Figure 21
rationale, For the GSM8k-Har dataset, we increase the numerical values used in the questions, thus making the task more difficult for the model. The number of digits in the answer range from 3 to 12, with an average length 7.2. In the original GSM8k addition-only subset, the number of digits range from to 5 with average length of 2.4. An example is presented in Figure 7(b)
20

---

Under review as a conference paper at ICLR 2023
0.8
0.8
Accuracy
0.6
Algo Comp)
Accuracy
0.6
Algo Call (No Comp)
Few shot
Few shot atthougt
0.4
Chain of thought
0.4
0.2
0.2
0.0
Number of Digits in Answer
Count of Numbers Added
Figure 20: Performance on multi-number addition-subbraction questions with algorithmic calls. This dataset consists of 1000 questions of multi-number addition where each number could be positive or negative. We treat all incomplete questions as wrong. We use the same composition prompt as Figure [9(a] which only demonstrates an example of multi-number addition. In this case, we call on the addition- -ubtrrccttttttnnnnnn algorithm each time the specialized tokens called. We see that the algorithmic call method outperforms the chain-of- thought and few-shot baselines and demonstrates length generalization. Left: Accuracy with number of digits the final answer on the x-axis. Right: Accuracy with count of numbers the equation on the x-axis.
Q: Tommy has toy cars. His neighbor, Jessie, has cars too. Jessic's ' older brother has more cars than Tommy and Jessie. How many cars do the three of them have altogether? A: Tommy and Jessie have 3+3=6 cars. Jessie's 's brother has 5+6=11 cars. Altogether, they have 6+11=17 cars. The answer is 17.
Figure 21: An example question and answer pair from GSM8k with chain-of-thougle rationale.
A.7.1 ADDITIONAL DETAILS ON AUGMENTING INFORMAL MATHEMATICAL REASONING
There are two challenges in augmenting algorithmic prompt to the chain-of-thougle prompt: 1) since there are many instances of addition in the chain-of-thoughh examples, this prompt would take up a large number of tokens, and 2) we have seen previously that combining similar skills like addition and subtraction within the same prompt did not result in any interference (with evidence of positive transfer), but since informal mathematical reasoning and arithmetic operations are very different skills, this may no longer be the case.
To address the first challenge (lengthy prompt), we only embed the addition algorithm in 2 of the prompt examples, and we indicate these augmented examples through the <ALGO> flag while the remaining 6 examples use the <NONALGO> flag. These flags allow us to control whether the model should perform addition using the algorithm or by direct calculation. Thus, for each setting, we two experiments by appending the <ALGO> flag-based strategy is simple yet effective, with 86% of <ALGO> examples and 0% of <NONALGO> examples exhibiting algorithmic output. See Section B.13 for the actual prompt.
<NONALGO> flag the test question. This
For the second challenge (interference), we hypothesize that explicitly presenting the summary of the solution may help disentangle the two skills (i.e. informal mathematical reasoning and arithmetic operation). Thus we explore a version of chain-of-thouge where the answer begins with an overall plan/summary of the solution steps, before the individual steps are explained. We refer to this version as "with plan". and refer to the baseline version without a summary as "no plan". The actual prompt shown in Section
Figure (a) shows the results using this approach. First. we evaluate the impact of including algo- rithmic output in the prompt by comparing the chain-of-thought baseline with ("no plan no algo"") and without ("no plan w/ algo")) algorithmic output for addition questions. We find that includ- ing algorithmic output the examples significantly disrupts the model's informal mathematical reasoning abilities in the <ALGO> experiment, but leaves the <NONALGO> performance relatively unchanged. This demonstrates the existence of interference between the two skills. We conjecture that this occurs when mix highly different skills within the same context. The informal math- ematical reasoning component relies on the model's pretraining knowledge, while the algorithmic component is regimented and requires the model to follow specific instructions, and the different
21

---

Under review as a conference paper at ICLR 2023
nature and format of these two skills appears to interfere with their performance. Next, evaluate the impact of having a solution plan at the beginning of the output. Comparing the performance of "w/ plan w/ algo" and "no plan w/ algo", interference seen in the <ALGO> experiment. Nonetheless, the performance is still much worse than the same version without algorithmic output ("w/ plan no algo"). In summary, identify interference phenomenon which may occur when combining skills of different kind within the same context, and find that using flags in the prompt can be a simple way of directing model's attention as <NONALGO> experiments do not suffer from interference the way that <ALGO> experiments do.
that the solution plan alleviates some of the
A.7.2 ADDITIONAL DETAILS ON ALGORITHIMIC PROMPT AS TOOL USE
In this approach, we utilize one model for performing the informal mathematical reasoning steps and separate model for doing algorithmic addition calculations. To enable dialogue-like interaction, we teach the first model to output specific tokens to indicate when a separate model should be consulted. See Figure for an example of how these tokens used. We then extract the addition question using these tokens and send it to the second model loaded with the addition algorithmic prompt, which executes the addition algorithm and returns the answer back the first model. The first model would then continue with the rest of the answer without needing to keep the algorithmic output in its context. Creswell and Shanahan (2022) uses similar multi-model and multi prompp strategy in order to separate out selection from inference in reasoning problems. This approach can be considered a form of tool use (Parisi et al. 2022), where a model queries another source for particular type of information.
A.8 OTHER RESULTS ON TWO-NUMBER ADDITION
Chain-of-thougie prompt comparison: In order to generate chain-of touhh-of-t prompt templates using the "let's think step-by-step" approach, we first set the temperature to 0.3 and generate number of samples. We find that the output of the model centers around two formats, shown in Sec- tion B.1.3 We convert both formats into chain-of-thon of-touht prompt and evaluate their performance. We choose the better performing version as the baseline in the main results.
1.0
Chain-af-thought Chain-of-thought V2
0.8
Accuracy
0.6
0.4
0.2
0.0
14
16
Number of Digits in Answer
Figure 22: Performance of two-number addition with two versions of chain-of-thought prompt. Due to the stochasticity of the "let's think step-by-step" approach, there can be multiple strategies being generated by the model. "Chain-off of of-thought" is the one that in the main results. "Chain-o of tf-tthought V2" is alternative version shown Section B.1 We choose the better performing version the main chain-of of-thuught method.
Other baselines: There have been other attempts of understanding and developing improved ver- sions of scratchpad and chain-of-thought prompts for addition. For (aample,Akyyrrkk and Akyurek (002)) provides an analysis of the scratchpad approach to prompting. They studied various style choices and natural language descriptions and evaluated their impact performance. Moreover, approaches to addition that different
Zhou (022) and Chen (022) showed new thain-of-thougee find from using "let's think step by step." We study these approaches under evaluation setting, and the results are shown in Figure 23 We find that the performance these methods are lower than existing baselines. For these methods, adopt the same prompt exam-
than the
22

---

Under review as a conference paper at ICLR 2023
ples that use for all methods. We note that evaluation dataset allows for the possibility that the two number have different lengths, which different from the results shown these works that use the same length for both numbers. Moreover, for these methods, the questions represented in delimited format (e.g. 1,2,8), while all the other methods use standard number representations (e.g. 128). We have observed from seratchpad experiments that having delimiters tend to help scratchpad-like prompts and hurt few-shot methods.
Algorithmic
Few-shot
Chain-of-thought
Accuracy
0.6
Instruction-only
CoT (sug. by Denny Zhou)
CoT (sug. by Xinyun Chen)
0.4
Scratchpad (sug. by Ekin Akyürek)
0.2
Number of Digits Answer
Performance of two-number addition with additional chain-of-thought ("CoT"") and scratchpad baselines. We find that these methods perform worse than existing baselines and do not demonstrate significant length generalization. Crucially, although these prompts are augmented with more natural language deserip- tions, they do not use unambiguous rules like algorithmic prompt does, which explains the performance gap.
Figure 23:
Moreover, although Akyurek and Akyurek (2022) also cite the importance of natural language de- scriptions in the prompt and not leaving things up interpretation, their conclusion based on having markers for different values and standard formats for the carry component. Although our prompts also use natural language descriptions, we do so mainly to explain more abstract concepts that are harder to illustrate, such the grouping operation in memorized multiplication (see Sec- tion 3.2). We have shown in Figure g that symbols-only addition prompt with minimal natural language still performs significantly better than all baselines and achieves length generalization. In addition, we provide explicit explanation in the sense of giving the actual equations for deriving certain values and replacing uncommon operations with more common ones, which the key con- tributor to the high performance of algorithmic prompts. In fact, we find that having inconsistent markers for carry can still significantly outperform consistent template when more explicit rules are provided, contrary to the claims in (Akyurek and Akyurek (2022). In Figure 24 we show that using prompt with inconsistent carry formats (i.e. carry only included in the equation 1, and omitted when it is 0) but with the inclusion of the modulo operator to extract the answer digits significantly outperforms the version with consistent carry formats. Here, we compare to the algorithmic prompting with nonexplicit calculation ablation from Figure 3(a] and both prompts do not include the effect of explicit carry equations. We also use an inconsistent format for the modulo operator, only displaying this step when the digit sum is greater than 9. This shows that having more explicit rules is much more crucial than having standardized formats in the prompt. The prompts can be found in Section B.2.2 Overall, these results differentiate the insights in this work with those in Akyurek and Akyurek (2022).
is
B PROMPT EXAMPLES
B. ADDITION PROMPT STRATEGIES
For addition prompts, we use 3-shot with the examples 128 +28+336, 9980+29, and 802+7145 in order. For conciseness, may include only subsets of the prompt questions in the prompt examples.
23

---

Under review as a conference paper at ICLR 2023
1.0
0.8
Accuracy
0.6
0.4
Algorithmic
Algorithmic w/ Nonexplicit Calculation
Algorithmic w/ Nonstandard Format
0.0
10 12
14 16
18
Number of Digits in Answer
Figure 24: Performance of two-number addition with variants of algorithmic prompt. Both "algorithmic w/ nonexplicit calculation" "algorithmic w/ nonstandard format" do not contain equation for carry value derivations. However, "algorithmic w/ nonstandard format" further do not use standard format for the carry values, omitting it completely when the value is 0. "Algorithmic w/ nonstandard format" further includes the modulo operation for deriving the found in Section B.2.2] We find that "algorithmic w/ nonstandard format" significantly outperforms the with standard format, illustrating that having more explicit rules is much more crucial than having standardized formats in the prompt.
digit, again in nonstandard format. Prompts be
24

---

FN-[8,0]. length of SN is 3. SN-[7,1, EN [N Thus Under review as a conference paper at ICLR 2023
B.1.1
ALGORITHMIC PROMPT FOR ADDITION
Problem: 128+367=
Explanation:
The first number is 128, FN= [1, 2, The second number is 367, SN= (N, 6, Since FN [1,2,8] has digits, SN [3, 6, 7] has 3 digits, thus the maximum number of digits is 3. In each subsequent step, we remove number from the end of FN and one from the end of SN. Length FN is 3. 2N- Length of SN is 3. 6, FN13/=8. SN[3]=7. C131=0, Since 8+7+0=15, 15>10, 15810=5. Length of A is 1. Thus A=[5]. Since (15-5)/10=1, c12]=1.
Length FN is 2. EN=11,2]. Length of SN is 2. SN=13, =21 SN[2]-6. C[2]-1. Since 2+6+1-9, 9<10, 9810-9. length of A is 2. Thus A-[9,5]. Since (9-9)/10-0, c[1]-0.
Length of PN is 1. FN-[I]. Length of sN is 1. SN[1]=3. C[1]=0. Since 1+3+0=4, 4<10, 4810=4. A=14,9,5]. Since (4-4)/10=0, C10]=0.
SN-[3] FN[1]=1.
Length of A is 3. Thus
There are no more digits and c10]=0. Thus the process is complete. Since there are no more operators, the problem is complete. The final Answer is 9,5.
Problem: 9980+29=
Explanation:
The first number is 9980, 1,, 0] The second number is 29, SN- [2, Since FN 1,,9,8,0) has digits, sN [2, 9] has 2 digits, thus remove
the maximum number of digits is 4. In each subsequent step, from the end of SN.
number from the end of FN and Length of Length of FN is 4. EN=19,9,8,01. [N[4]-0. SN[4]-S. C[4]-0. Since 0+940-9, 9<10, 9$10-9. Length of A Since (9-9)/10-0, C[3]-0.
2. SN=12,
is 1. Thus A-[9]. Length of PN is 3. EN-(9,9,8]. Length of SN is 1. SN-121. FN[3]-8. SN13]=2. C[3]=0. Since 8+2+0=10, 10=10, 10810=0. Length of A is Thus A=10, Since (10-0)/10-1, Length of FN is 2. is empty. C[2)=1. Since 940+1=10, 10-10, 10$10-0. Length of A is 3. Thus 3=9], Since (10-0)/10=1, c[1]=1.
EN=[9,9]. Length of aN is 0. SN=[]. =N[2]=9. SN
Length of FM is 1. EN=19]. Length of SN 0. SN= [N[1]=9, SN is empty. C[1]-1. since 940+1-10, 10-10, 10810-0. length of is 4. Thus 0, 9]. Since (10-0)/10-1) c[0]-1. There are more digits, but c[0]-1. length of is 5. Thus 0=11,0,0,0,91.
There are no more digits and the process complete. Since there are no more operators, the problem is complete. The final Answer is 01,0, 0,
Problem: 802+7145=
Explanation:
The first number is 802, FN- 0,2). The second number 7145, ON,17,1,,,5), Since FN-18, 2] has 3 digits, 1, has 4 digits, thus the maximum number of digits is 4. In each subsequent step, we remove number from the end of EN and Length of FN is 3. FN=18,0,2). Length of SN 4. SN= EN14]=2. 5N14]=5. C14]=0, Since 2+5+0=7, 7<10, 7810=7. Length of A is 1. Thus A-[7]. Since (7-7)/10=0, C[3]-0. Length of PN is 2. SN[3]-4. c[3]=0. Since 0+440-4, 4<10, 4810-4. Length of A A-[4,7]. Since (4-4)/10-0, C[2]-0.
from the end of SN.
Length of FN is 1. EN=181. Length of eN is 2. SN[2]=1. C[2]=0. Since 8+1+0=9, 9<10, 9810=9. A=19,4,7] Since (9-9)/10=0, c[1]=0.
SN=17,1]. ]N[2]=8.
Length of A is 3. Thus
is 0. FN=[]. Longth of su SN(1]=7, c[1]=0. Since 0+740=7, 7<10, 7810=7. Length of A is 4. Thus 4, Since (7-7)/10=0, c10]=0.
Length
SN=
FN expty.
There are no more digits and c[0]-0. Thus the process is complete. Since there are no more operators, the problem is complete. The final Answer [7,9,47]].
25

---

Under review as a conference paper at ICLR 2023
B.1.2
FEW-SHOT PROMPT FOR ADDITION
Q: 128+367=
A: 495.
Q: 9980+29=
10009.
Q: 802+7145=
A: 7947.
B.1.3
CHAIN-OI-THOUGHT PROMPT FOR ADDITION
Problem: 128+367=?
explanation: let's think step by step.
The final Answer 495.
Problem: 9980+29=?
Explanation: Let's think step by step. -300-39-990-20555100000000000000 The final Answer is 10009.
Problem: 802+7145=?
The final Answer is Explanation: Let's think step by step. 600-1008800000000444440000144440 7947.
The following is another version of chain-of-thought prompt that we tried, but the performance was worse than the previous prompt.
Problem: 128+367=?
Explanation: Let's think step by step.
1. 128+367=?
2. 128+300=428
3. 428+60-488
4. 488+7-495
5. 495-495
So, 128+367=495.
The final Answer is 495.
B.1.4 INSTRUCTION ADDITION PROMPT FOR ADDITION
The following are instructions for solving addition problems the form of x + y 7, where x, y, and are positive integers.
we will use the standard al algorithm for addition. we align the nurbers x and the least significant digit, which is the ones digit. Starting from right
left, we go from the least significant digit to the most the corresponding digits from each number.
significant digit and when the sum of the two digits is greater than 9, a carry of is included in the sum of the next digits. when there is only one digit available from the two numbers, only that digit along with any carry is included in the sum. When all the digits remaining carry if any shall be included the sum.
processed, only the
For x + = where x = int (str (abc)), y = (str (defg) , we can solve with the following steps:
1) otg=w', #10
2) (=E+((W'=)//1)=v/ u=u1$10
v=ve$10
3) (11
4) de ((p/-o)//10)=t/ t=t/s10
5) s=(t
Thus, int (str(stvv))
The answer should be in the form below:
Q: What is abc+defg=?
A: abc
+defg
stuvw
The answer is stuvw.
26

---

Under review as a conference paper at ICLR 2023
B.1.5
SCRATCHPAD PROMPT FOR ADDITION
Input:
128+367
Target:
<scratch>
C:
2
3
5
C: 1
+
5
C:
4
5
C:
9
</scratch>4
5.
Input: 9980+29
Target:
<acratch>
9
8
0
2
9
C:
9
+
C:
0
9 0
1
C:
1
0
0
9
C:
1
0
0
9
</scratch>1
9.
B.1.6 DETAILED SCRATCHPAD PROMPT FOR ADDITION
Input:
128+367
Target:
<scratch> has digits.
6 has digits.
2 8
+ 3
6 C=0
8 +
7 +
=
1
A->5
C->1
1 2
6 A=5 C=1
2
6
1 A->9 C->0
+ 3 A=9 5 C=0
+
A-24
C->0
A=4
C=0 END
</scratch> 9 5
Input:
9980+29
Target:
<scratch> 9 8 0 has digits.
9 has digits.
9 0 2 C-0
+
+
9
A->9 C->0
9 8 + 2 A=9 C=0
8
2
0
1
A->0 C->1
9 A=0
9 C=1
+
0
+
0
A->0 C->1
+ 2=0
C=1
A-20 C->1
A=0
C=1
A->1 C-x0
A=1
0 0
C=0
END
</scratch>
0
0
B.2
ALGORITHMIC PROMPT ABLATIONS FOR ADDITION
B.2.1
ALGORITHMIC PROMPT WITH UNCOMMON OPERATIONS FOR ADDITION
The uncommon indexing operation is highlighted in red.
27

---

Under review as a conference paper at ICLR 2023
Problem: 128+367=
Explanation:
The first number is 128, FN- FN=[1, 2,, The second number 367, 1N,13,6, 7] Since EN 11,2, 8] has digits, sN [3, 6, has 3 digits, thus the maximum number of digits is 3. In each subsequent step, we remove number from the end of FN and FN13|=8. SN[3]=7. C131=0, Since 8+7+0=15, 15>10, 15810=5. Length of is 1. Thus A=[5]. since (15-5)/10-1, C[2]=1.
from the end of SN.
FN[2]=2. SN[2]-6. c[2]-1. Since 2+6+1-9, 9<10, 9810-9. length of A is
2. Thus A-19,5]. Since (9-9)/10-0, C[100-0 C[1]-0.
ENI1]=1. SN|1]=3. C11]=0. Since 1+3+0=4, 4<10, 4810=4. Length of is
3. Thus 6=14,9,51, Since (4-4)/10=0, c101=0.
There are no more digits and C10]=0. Thus the process is complete.
Since there are no more operators, the problem is complete. The final
Answer is [4,9,5].
B.2.2 ALGORITHMIC PROMPT WITH NON-EXPLICIT CARRY FOR ADDITION
In this prompt, the explicit carry calculations in the prompt in Section B.I. is omitted.
Problem: 128+367=
Explanation:
The first number is 128, FN- (,, 22 The second number 367, 1, Since EN 11,2,8] has digits, SN 13, 6, has 3 digits, thus the maximum number of digits is 3. In each subsequent step, we remove number from the end of FN and Length of FN is 3. EN=11,2,81. Length of SN [N[3]-8. SN[3]-7. C(3]-0, Since 8+740=15. Length of A is 1. Thus
from the end of SN.
A-[5]. C[2]=1.
Length of FN is 2. FN-[1,2], Length of SN is 2. SN-13, 61 [N[2]=2.
SN12]=6. C[2]=1. Since 2+6+1=9. Length of is 2. Thus []
c[1]=0.
Length of FN is 1. SN(1]=3. c[1]=0. Since 1+340=4. Length of A is 3. Thus A= 9,5). c[0]=0.
EN=[1]. Length of aN is 1. SN=[3]. FN[1] =1.
There are no more digits and c10]=0. Thus the process is complete. Since there are no more operators, the problem is complete. The final
Answer is [4,9, 9]
In this prompt, the explicit carry calculations prompt Section B.I.I is omitted. In addition, the carry format inconsistent, omitting the carry completely when the value is 0. This prompt is used for the ablation in Figure 24
Problem: 128+367=
Explanation:
The first number is 128, FN= [N, The second number is 367, SN=13,6,
Since EN 11,2, 81 has digits, SN 6, has 3 digits, thus the maximum number of digits is 3, In each subsequent. step, we remove one number from the end of PN and one from the end of SN. Length of PN is 3. FN-(1,2,8]. length of SN is 3. SN-[3,6,7]]
FN[3]-8. SN[3]=7. c[3]=0. Since 8+7-15, 15>10, 15810-5. Length of is 1. Thus A=[5]. c[2]-1. Length of EN is 2. FN=[1,2]. Length of SN is 2.
SN=13,6]. FN[2]=2. SN[2]=6. c[2]=1. Since 2+6+1=9, 9<10. Length of is 2. Thus A=[9,5] CI1]=0. Length
FN=[1]. Length of SN 1. SN=[3]. FN[1]=1. SN[1]=3. c[1]=0. since 1+3-4, 4<10. Length of A is 3. Thus A= (4, 9, 5]. c[0]=0.
is 1.
There more digits and C[0]=0. Thus the process is complete. Since there are no more operators, the problem is complete. The final Answer [4,9,5]
28

---

Under review as a conference paper at ICLR 2023
B.2.3 ALGORITHMIC PROMPT FOR ADDITION WITH IRREGULAR ERRORS
The enrors are highlighted in red.
Problem: 128+367=
Explanation:
The first number is 128, FN= 1,, The second number is 367, SN=13, since FN 11,2, 8 has digits, SN 13, 6, has 3 digits, thus the maximum number of digits is 3. in each subsequent step, we remove one number from the end of EN and one from the end of SN. Length of PN is 3. (N-(1,2,8]. Length of SN is 3. [8-[1,6,7], EN13]=8. SN[3]=7. C13]=0. Since B+6+0=15, 15>10, 15810=5. Length of Since (15-5)/10-1 c[2]=1.
is 1. Thus A=[5].
Length of FN is 2. EN=[1,2]. Length of SN is 2. [3, FN[2]=2. SN[2]=6. c[2]=1. Since 2+6+1-9, 9<10, 9810-9. A=19,5], Since (9-9)/10=0, c[1]=0.
Length of A is 2. Thus
is 1. [N=[L]. Length of SN 1. SN(1]-3. c[1]-0. Since 1+2+0-4, 4<10, 4810-4. Length A is 3. Thus A-[4,9,5) Since (4-4)/10-0, C[0]-0.
Length
SN= FN[1]=1.
There are more digits and C[0]-0. Thus the process is complete. Since there no operators, the problem. is complete. The final Answer 14,9,51.
B.2.4 ALGORITHMIC PROMPT FOR ADDITION WITH SYSTEMATIC ERRORS
The errors are highlighted in red.
Problem: 128+367=
Explanation:
The second number is 367, SN-13,6, Since EN [1,2, 8] has digits, SN [3, 6, 7] has 3 digits, thus the maximum number of digits is 3. In each subsequent step, we remove one number from the end of EN and one from the end of SN. Length of FN is 3. EN=11,2,8). Length of SN is 3. 6N=(3,6,7). FN[3]=8. SN[3]=7. C[3]=0. Since 8+6+0-15, 15>10, 15a10-5. Length of is 1. Thus A-[5]. Since (15-5)/10-1, C[2]-1. length of PN is 2. FN-[1,2]. length of SN is 2. SN-[3,6] FN[2]-2. SN121=6. C121=1. Since 2+5+1=9, 9<10, 9810=9. Length of A is 2. Thus A=19,51. Since (9-9)/10=0, CI1]=0.
The first number is 128, FN= [N,[11, 8]. 8].
Length of is 1. FN=[lI. Length of sN is 1. SN(1]-3. c[1]-0. Since 1+240-4, 4<10, 4810-4. Length of A is 3. Thus A-[4,9,5], Since (4-4)/10-0) c[0]-0.
SN= #N[1]=1.
There are more digits and c[0]=0. Thus the process is complete. Since there are no operators, the problem is complete. The final Answer 5].
B.2.5 SYMBOLS-ONLY ALGORITHMIC PROMPT FOR ADDITION
Problem: 128+367=
Explanation:
FN=128, FN=[1,2,8). SN=367, SN- 6, Len (FN)) Len (SN) =3, MaxLen=3.
(FN) (N,
(SN)
(N 71. FN[3]=8. SN[3]=7. (A) A=[5]. (15-5)/10=)
C[3]=0. 8+7+0=15, 15>10, 15810=5. c[2]=1.
(FN) FN-(1, 21 (SN) -2. SN-[3,6] FN[2]-2. SN[2]-6. C[2]=1.
2+6+1=9, 9<10, 9810-9. (A) A- (9-9)/10-4 c[
(FN) PN-[1]. Len (SN) SV-[3] #N[1]=1. SN[1]=3. c[1]-0.
Since 1+3+0=4, 4<10, 4810=4. Ien (A) A-14,9,51. (4=4)/10=0, 010]=0.
(FN) and (SN) and C10]=0. Done. The final Answer is [,,
B.2.6 SYMBOLS-ONIY ALGORIITMIIC PROMPT FOR ADDITION WITHOUT KEYWORDS
In this prompt, do not the keywords Len and Max.
29

---

Under review as a conference paper at ICLR 2023
Problem: 128+367=
Explanation: FN-128, (1,,,1, SN-367, SN- [3, 6, 71. (B2) =3, (BN) =3, UXCVEZ-3.
VB2 =3.) FN=[1,2,8] 81. (SN) SN= [N=[3, 71 71. FN[3]=8. SN[3]=7.
C[3]=0.
8+7+0=15, 15>10, 15$10=5,
VBZ (A) =1. A=15]. (15-5)/10=1, =12]=1.
(F2) FN=[1,21. =SN)
SN=[3,6] FN[2]=2.
= C12)=1.
2+6+1-9, 9<10, 9810-9. VB% (A) A-[9,5] (9-9)/10-0, c[1]-0.
(RV) [N-[1]
(SN)=1. SV-[3]. [N[1]=1. SN[1]-3. c[1]-0.
Since 1+3+0-4, 4<10, 4$10-4. (A)-33 A-[4,9,5]. (4-4)/10-0, C[0]=0.
(EN) and VBZ (9N) =0 and C10]=0. Done. The final Answer is 9,
B.2.7 SYMBOLS-ONLY ALGORITHMIC PROMPT FOR ADDITION WITH MISLEADING KEYWORDS
In this prompt, we replace the keywords Len and Max with Str and Min.
Problem: 128+367=
Explanation:
FN-128, FN- (,, SN-367, SN-13, 6, 71 (tr -3, Str (SN) -3, MinStr-3.
(FN) FN= 2, Str (SN)=3.. 6, 71. FN[3]=8. BN[3]=7.
C[3]=0. 8+7+0=15, 15>10, 15$10=5. Str(A)=1. A=[5]. (15-5)/10=1)
C[2]=1.
(FN) FN=[1,21. (SN) 6N-[3,6] FN[2]=2. SN[2]=6. C[2]=1.
2+6+1-9, 9<10, 9$10-9, (A)=2. A=[9,5].
c[1]=0.
(FN) FN=[1]. Str (SN) SN=(3]. EN[1]=1. SN[1]=3. C[1]=0,
Since 1+3+0-4, 4<10, 4810-4. (A) A-[4,9,5]. (4-4)/10-0, C[0]=0.
Str (FN) and Str (SN)=0 and C[0]=0. Done. The final Answer is [4,9,5].
B.3 ADDITIN--UBTTRACTION PROMPT STRATEGIES
B.3.1 ALGORITHMIC PROMPT FOR ADDITION- SUBBRCCTTONT
For the addition-subtractio prompt, we use prompt examples 128 + 367, 9980 + 29, 29 5700 99 21, 483 389, and -30 + 8002 in order.
Problem: 483-389=
Explanation:
The first number is 483, adding commas between each number, FN- 3].
The second number is -389, adding commas between each number, 13,- EN [4, 8, has 3 digits, SN - 8,, 9] has 3 digits, rax is
3.
(EN) FN=[4,8,3], FN[3]=3. Len (3N)=3.
SN= 13,-19,, SN[3]=-9.
c13]=0. Since 3-9+0=-6, -6<-10, -68-10=-6. Len (A) A=[-6] Since (-6--6)/10=0, c[2]=0.
SN=- [3, 8). SN SN =-8 =FN) 28-14,81, EN[2]=8. Len =2)==22
c[2]=0. Since 8-8+0-0, 0<10, 0810-0. Len -2) -2 A- Since
(0-0)/10-0, c[1]=0.
(FN) PN-[4]. EN[1]-4. len (1 SN- [N--13]. SN[1]--3. c(1]-0.
Since 4-3+0=1, 1<10, 1810=1. (A)=33. A=11, -61 Since (1-1)/10=0, C10]=0.
=EN) FN=[]. ENI0]=empty: Len (SN) SN=-1]. SN
since both and are empty, next. Since c[0]=0, the steps are done. Since there are in A, we check the sign of the last step A[1]=1. Since
1 is non-neg, we process A from right to left. x=11,0,-6]-(t1,40, c[3]=0.
A[3]=-6. Since -640, B=10, c[2]=-1. Since c[3]=0, thus -6+10+0=4. Len (1. ANEW-[4]. c[2]=-1. (A)=22 A=[+1,+0), =12]=+0. Since +0 is 0, B-0, c[1]=0. Since c12]=-1, thus 0+0-1=-1, which is neg, thus repeat with B=10, c[1]=-1. -1+10+0=9. Len =2NEW)=2. ANEW=19, 41. c[1]=-1.
(A)=33 +=[+1,+0,-66
###continued on page
30

---

Under review as a conference paper at ICLR 2023
A[1]=+1. Since +1>0, B=0, c[0]=0. Since c[1]=-1, Len (A)=1. A=[+
thus 1+0-1=0. Len (ANER) =3. AN, 9, C[0]=0.
=A)=0. A= since A empty, the problem is complete. The final
Answer is 9,4,
Problem: 29-570=
Explanation:
The first number is 29, adding commas between each number, FN [2, 9] The second number -570, adding commas between each number, SN-- [5, 7, EN 12,9] has 2 aigits, SN -,,,7, 01 has 3 digits, max is 3.
=2 FN=12,91. EN12|=9. Len Len =3. 15,
SN[3]=-0.
C13]=0. Since 9-0+0=9, 9<10, 9810=9. (en A= Since (9-9)/10=0, C[2]=0.
(FN) FN-[2]. EN[1]-2. Len (SN) SN- [5, 7]
SN[2] --7
c[2]=0. Since 2-7+0=-5, -5<-10, -58-10--5.
Len (A) -2.
3-[-5, 9]
Since
(-3--5)/10=0, C[1]=0.
(EN) FN=[]. EN[0]=
(eN)
SN=-
SN[1]=-5.
c[1]-0. Since 0-5+0=-5, 10, 58-10--5.
(A)=3)
A= -5,
Since (-5--5)/10=0, C10]=0.
(FN) FN=[]. EN10]==mpt:) Since both FN and SN empty, next. Since C10]=0, the steps done. Since there are Since -5 is neg, we change the sign and process A from right to left. A-[-5,-5,9]- (5, (A)=33 -=- A13]=-9. Since -9<0, B=10, c[2)=-1.
Len (SN) SN=- =e(o]
A, we check the sign of the 1ast step A[1]=-5.
C[3]-0.
Since
C13]=0, thus -9+10+0=1, Len (ANEW) ANEW=-11).
=12]=-1.
(A)=2) A=-[+5,+5]. =12]=+5.
Since +5>0, B=0, C11]=0. Since
c[2]=-1, thus 5+0-1-4. Len (ANEW)
[N, cI1]-0.
(A)-1. A=-[+5]. A[1]=t5. Since +5>0, B-0, c[0]-0. Since c[1]=0,
thus 5+0+0=5. Len (ANEW)= =3. A5,
4, 1, C[0]=0.
Len =A) A=-(]- []. Since A is empty, the problem is complete. The final
Answer - 15, 1]
B.3.2 CHAIN-OF-THOCGHT PROMPT FOR ADDITION-STRTRACTIIO
Problem: 128+367=?
Explanation: Let's think step by step.
122438/122240001774448871399 The final Answer 495.
Problem: 9980+29=?
Explanation: Let's think step by step.
The final Answer is 10009.
Problem: 29-570=?
Explanation: Let's think step by step.
33--770----000-7--44-----------1
The final Answer is -541.
Problem:-99-21-11
Explanation: Let's think step by step.
99-21--9--011111111--10 The final Answer is -120.
Problem: 483-389=?
Explanatioo: let's think step by step.
The final Answer is 94.
Problem: 3048802-?
Explanation: Let's think step by step.
-308002--00000022---000011111 The final Answer is 7972.
B.4 MEMORIZED MULTIPLICATION PROMPT STRATEGIES
B.4.1 CHAIN-OF-THOUGHT PROMPT FOR MEMORIZED MULTIPLICATION
For multiplication, prompt examples 128 367 and 2035 87 in order.
31

---

Under review as a conference paper at ICLR 2023
Q: 1289367=?
A: Let's think step by step.
1284377-18
128-3601122-30042224441111- 128-3877:8800+7804888
128+367=46976
So, 128+367=46976.
The answer is 46976.
2035:87==
A: Let's think step by step.
2055567-2200--8133--777777 2035x8/:114400+2204453 2035+81=177045 So, 2035+87=177045.
The answer is 177045.
B.4.2 ALGORITHMIC PROMPT FOR MEMORIZED MULTIPLICATION
Q: 128*367=
ixplanation: FN-128, 1N-[1, 2, SN-367, SN-[3, 6, 7] (FN) -3, Len -3N)-3. is 3. Since 3-3, the lengths of two numbers are equal, pick EN and break 11,2,81 into 3//3=1 group of three and group of 383=0 leftover digits. Since there are 0 leftover digits, from 11,2, we break the sirst 0 digits as (1,,,2,8), thus the leftover group is []=empty and the main group is [1,2,8] Since there is 3//3-1 group of three, we break the main group into 1 group of each: [1,2,8) 8]. Reformatting for each main group, we have 128. Thus, ignoring the empty group, the groups are 128. The other number is the MULVAL, thus MULVAL-367.
-3. Max len
The submulproblems are 128+367-MOL1. There is 1 mul operator. **START**
Submulproblem: 128+367-MU11
FN=128, FN=11,2, 81. Muival=367. (FN) PO=0. 8+367=2936. PO=0, append zero II to
(FN)
1,, 81. F-13]=8.
12,9,3,6111: 1,,9,3,61=ADV,
(FN)
EN[2]-2. [7,3,410]: [7,3,4,0]-ADV,
FN-[1,21.
2+367-734. P0-1, append 1 zero [0] to
Len FN-[1]. EN[1]-1, [3,6,710,0]: 3,6,,,,000=2D00
14367-367. P0-2, append 2 zero [0, 0] to
(FN)
Done.
++START++
Addition Problem: ADV1+ADV2+ADV3-
Explanation:
The subproblems are ADV1+ADV2-AN91, ANS1+ADV3-ANG2, There are 2 add operators.
Subproblem: ADV1+ADV2-ANS1
FN-ADV1, FN=[2, 3, 61 SN-ADV2, (7- 3, 0] len (FN) -4, Leen (SN) -4, max len is 4.
(FN)) 9,3,,, 61. Len (SN)= 3, 01. FN]4]=6. SN|4]=0.
C14]=0. 6+0+0=E, 6<10, 6810=6. Ien (A) A= (6-6)/10=0, C13]=0.
(PN) [N-[2,9,3],
(SN)
FN[3]=3. (7,
SN[3]=4.
c[3]-0. 3+4+0=7, 7<10,
7810-7.
(A) A-
/1-0), C[2]=0.
(FN) FN-[2,9]. Len (SN)
SN- [7,3], FN[2]-9. SN[2]=3. c[2]=0.
9+3+0=12, 12>10, 12810=2.
Len (A)=3.
c[1]=1. A= (12-2)/10=1, C[1]
(en) FN=[2] (SN) SN= EN[1]=2. SN[1]=7. c[1]=1.
2+7+1=10, 10-10, 10%10=0. (A)= A=
(10-0)/10-1, C[0]=1. (PN) FN=[]. (SN) SN=(] Both are empty. c[0]=1. Not
done. Len (A) 2N81=(1,0,2,7,,11 Since there are add operators and processed up to ANSI, continue. The EN is 2,,0,,,7,6). ###continued
page
32

---

Under review as a conference paper at ICLR 2023
Subproblem: ANS1+ADV3-ANS2
IN=ANS1, FN=[1,0,2,7]
SN=ADV3, SN=(3, 0], Len (FN) =5, Len (SN) =5,
max len is 5. Len (EN)= PN[5]=6. SN[5]=0. c[5]=0. 6+0+0-6, 6<10, 6810-6. Len (A) A-[6]
FN-[1,0,2,7,6]
Len (9N) SN-
0] 0]
(6-6)/10-0, C[4]-0.
(FN)) E8=[1,0,2,7|, Len (SN)=44 1N=13,6,7,01, FN[4]= SN|4]=0)
C14]=0. 7+0+0=7, 7<10,
7510=1. Len (A)=2. 6]. (1-7)/10=0, C13]=0. (SN) 9N=13, 71 3 9810-9. lin (A)-3. A-19,7,6] (9-9)/10-0,
(EN) FN=11,0,21.
SN13]=7.
C[3]-0. 24740-9, 9<10,
c[2]=0.
(FN) FN-[1,0], (SN)
SN-[3,6], FN[2]-0. SN[2]-6. C[2]=0.
0+6+0=6, 6<10, 6810=6.
(A)
2=[6,9,7,6]- (6-6)/10=0, c[1]=0.
(EN) FN=[1]. (SN) SN=(3]. FN[1]=1. SN[1]=3. c[1]=0.
1+3+0=4, 4<10, 4810=4. (A) 6,,7,6 (4-4)/10=0, C[0]=0.
0. FN=[]. (SN) SN=[]. Beth are empty. c[0]=0. Done.
6,, Since there are add 2 operators and processed up to ANS2, complete. The final ADDAnSwer 14,6,9,7,6). ++END++
**
6, 9] Since there is mul operator and processed up to now combine the results. Since mul operator, we append 3+ (1-1)=3+0== zeros to MULI, MUL1=14,
MUI.1, complete.
Addition Mul Problem: MUL1+EMPTY= Explanation: The subproblens are MULL-EMPTY-ANSL There is 1 MA operator. Since EMPTY is in the equation, ANS1-MULI-[4,6. 9, 6] Since there is MA operator and processed up to ANSI, complete.
END Answer [4, 6, 9,7,6 61.
B.5 ALGORITHMIC PROMPT FOR PARITY
For parity, prompt examples [1, 1, 1, and [0, 1, 1, 0, 0, 0, 0] in order.
Q: What is the parity the 1ist a=
1, 01?
A: We initialize s=
a=(1, 1, D, 1, 0]. The first element of a is so b-1. = + b
= ==1, 1. s=1.
a=[1, 0, 1, 0). The first element of is 1 b=1.
b
0. s=0.
a- 1, 0]. The first element of a 0 sc b-0. s
0.
3-0.
a=11, 01. The first element of a is so b=1. s = s
1. 1. s=1.
s=1.
a= a=101. The first element a is so b=0. s
a= is empty. Since the list a is empty and we have s=1, the parity is 1.
B.6 SCRATCHPAD PARITY FOR PARITY (ANIL ET AL. 2022
Q: What is the parity on the list a=(1, 1, 0, 1, 0]?
A: [1, 0, 0, 1, 11, the parity is 1.
Q: What is the parity the 1ist a=[0, 0, 0, 013
A: [0, 1,
0, 0, 0, the parity
33

---

Under review as a conference paper at ICLR 2023
B.7
ALGORITHMIC PROMPT FOR MULTI-ADD AND MULTIPLY-AS-ADD
Problem: 128+367=
Explanation:
The first number is 128, FN 1N, 8,8 The second number 367, 13, 7]. Since EN [1,2, 8] has digits, SN [3, 6, has 3 digits, thus the maximum number of digits is 3. In each subsequent step, we remove number from the end of EN and length
from the end of SN. is 3. (N- length of SN is PN[3]-8. SN[3]=7. c[3]-0. Since 8+7+0-15, 15>10, 15810-5. Length of is 1. Thus A=[5]. since (15-5)/10-1, C[2]-1.
6N-(3,
Length of FN is 2. EN=11,21. Length of SN is 2. 3N=13,6] 61. EN[2]=2. SN12|=6. C12]=1. Since 2+6+1=9, 9<10, 9810=9. Length of A is 2. Thus A=19,51. Since (9-9)/10=0, C11]=0.
Length of FN is 1. FN-[1]. Length of SN is 1. SN[1]-3. c[1]=0. Since 1+340-4, 4<10, 4810-4. A-(4,9,5), Since (4-4)/10=0, C10]=0.
SN-13] FN[1]-1.
Length of A is 3. Thus
digits and C[0]=0. Sinal Answer is [,)
There
Thus the process is complete. The
Problem: Problem: 9980429=
Explanation:
The second number is 29, SN=12,91- Since EN 1,,9,8,0 0] has digits, SN 12, has digits, thus the maximum number of digits is 4. in each subsequent step, we remove one number from the end of PN and one from the end of SN. Length of PN is 4. FN-[9,9,8,0]. EN14]=0. SN]4]=9. C141=0. Since 0+9+0=9, 9<10, 9810=9. Length of 1. Thus A=[9]. Since /900) C[3]=0.
The first number is 9980, 9,,,
Length of SN is 2. SN-[2,
Length of FN is 3. EN=19,9,8]. Zengh of sN is 1. SN= FN[3]=8. SN[3]-2. c[3]=0. Since 8+240-10, 10-10, 10$10=0. Length of A is 2. Thus A= [], Since (10-0)/10=1, c[2]-1. c(2)-11 Length is empty. C[2]=1. Since 940+1-10, 10=10, 10s10-0. Length of A is 3. Thus 0,99.. Since (10-0)/10-1, c[1]=1.
is 2. EN=[9,9]. Length
is 0. SN=[]. 7N[2]=9,
Length of FN is 1. FN-(9). Length of SN is o. SN-I]. FN[1]-9. SN is empty. C[1]=1. Since 940+1-10, 10-10, 10810-0. Length of is 4. Thus 0,99, Since (10-0)/10=1, C101=1.
There are no more digits, but C10]=1. Length of A is 5. Thus A,
The final Answer is 11,0,0,0,91. Problem: 802+7145+6=
Explanation:
The subproblems are 80247145-ANS1 and 6-AN22. There are 2 operators.
Subproblem: 802+7145-ANS1 The first number is 802, FN- EN, 0,2) The second number is 7145, SN=[7,1,4,5). Since FN=18, 0, has 3 digits, SN=17,1, thus the maximum number of digits is 4. In each subsequent step, we remove one number from the end of FN and one from the end of SN. Length of FN is 3. (N,(), Length of SN is 4. 1,,,7,,,,,55 FN[4]=2. SN[4]=5. c[4]=0. Since 2+5+0-7, 7<10, 7810-7. Length of is 1. Thus A-[7]. Since (107)/10-0, C[3]-0. Length of FN is 2. EN=18,01. Length of SN is 3. SN=17,1,41, 41. EN|3]=0
has 4 digits,
SN|3]=4. C13]=0. Since 0+4+0=4, 4<10, 4810=4. Length of A is 2. Thus A114,71. Since (4-4)/10=0, c12]=0.
is 1. FN=(8). Length of sN SN[2]-1. c12]=0. Since 8+140-9, 9<10, 9810-9. A-(9,4,7], Since (9-9)/10-0, c[1]=0.
Length
SN-[7,1] FN[2]-8.
length of A is 3. Thus
Length of FN is 0. EN=I]. Length of sN is 1. SN[1]=7. C[1]=0. Since 0+7+0=7, 7<10, 7810=7. Length of A is Thus
SN=[7]. EN is empty.
A- Since (7-7)/10-0, C[0]=0.
There are no more digits and c10]=0. Thus the process is complete. Since there are 2 operators and we processed to ANS1, there are more operators to process. Thus, ANSI is 17,9,4771. page
###continued
34

---

Under review as a conference paper at ICLR 2023
Subproblem: ANS1+6-ANS2
The first number is ANSI, 1,,17,9,4, 41, The second number is 6, SN= [6]. Since FN-(7,9,4,7] has digits, SN-[6] has 1 digit, thus the maximum number digits is 4. In each subsequent step, we remove one number from the end of FN and one from the end of SN. Length of FN is 4. EN=-1,,,,,7],, SN14]=6. C14]=0. Since 7+6+0=13, 13>10, 13%10=3. Lengta of A is 1. Thus A=13]. Since (13-31/10=1, C131=1.
Length of SN is 1. SN=[6], EN14]=7.
Length of PN is 3. FN-(7,9,4]. length of SN is 0. SN- [N[3]=M [33]=4 SN is empty. C[3]=1. Since 440+1-5, 5<10, 5810-5. Length of A is 2. Thus A-[5,3]. Since (5-5)/10-0, c[2]-0.
Length FN is 2. EN=[7,9]. Length of SN is 0. SN=(]. =9[ SN is empty. C[2]=0. Since 9+0+0=9, 9<10, 9810=9, Length of is 3. Thus 3-19,5,3]. Since (8-9)/10-0, c[1]=0.
Length of FN is 1. EN=[7]. Length of sN is 0. SN=[]. FN[1]=7. SN is empty. C[1]=0. Since 74040=7, 7<10, 7$10=7. Length of is 4. Thus 1- since (7-7)/10=0, c10]=0.
There are no more digits and c[0]=0. Thus the process is complete.
Since there are 2 operators and we processed to ANS2, the probl em is complete. The final Answer is 17,9,5,31.
Problem: 3*7=
Explanation:
The subproblems are 3+7=MS1. There is 1 operator. Subproblem: 3+7=MS1
Since the problem is multiplication, numbers and add the larger number as many times as the smaller number. The first number is 3, FN-[3]-3. The secend number is 7, SN-(7]-7. Since 3 is smaller than 7, we rewrite the problem as summed together times: 7+7+7. We end at ANS (3-1)=2-ANN9,.
find the smaller of the
The subproblems are 747=ANS1 and ANS1+7-ANS2. There subproblem: 7+7=ANS1
operators.
The first number is 7, FN=17]. The second number is 7, SN=(7). Since FN=17] has digit, SN=17] has 1 digit, thus the maximum number of digits is 1. In each subsequent step, we remove one number from the end of PN and one from the end of SN.
length of PN is 1. FN-(7]. length of SN is 1. SN-[7]. #N[1]-7. SN[1]=7. CI1]=0. Since 7+740=14, 14>10, 14810=4. Length of A is 1. Thus A=14]. Since (14-4)/10=1, C10]=1. There There are no more digits
digits and C[0]=1. Length the process complete. Since there are operators and we precessed up to ANS1, there are more operators to process. Thus, ANS1 is [1,4]. Subproblem: ANS1+7-ANS2
is 2. Thus A=11,
The first number is ANSI, [N- The second number is 7, SN=[7) Since [N-[1,4] has digits, SN-[7] has 1 digit, thus the maximum number of digits is 2. In each subsequent step, we remove one namber from the end of FN and one from the end of SN.
Length FN is 2. FN=11,4]. Length of SN is SN=[7]. 7N[2|=4. SN[2]-7. C[2]-0. Since 44740=11, 11>10, 11810-1. Length of Thus A-[1]. Since (11-1)/10-1, c(1]-1. Length of FN is 1. EN-(I]. Length of sN is 0. SN- FN[1]=1. SN is empty. c[1]=1. Since 1+0+1=2, 2<10, 2810=2. Length of A is 2. Thus A=12,1]. Since (2-2)/10=0, C10]=0.
There are no more digits and c10]=0. Thus the process is complete. Since there are 2 operators and we processed up to ANS2, the problem is completo. Since there is 1 operator and we processed to MS1, the overall problem is complete. The final Answer is 12,
B.8 CHAIN-OF-THOUGHT PROMPT FOR MULTI-ADD
We use the same prompt examples as the algorithmic prompt, which are 128 + 367, 9980 + 29, 802 7145 6, 7 in order.
35

---

Under review as a conference paper at ICLR 2023
Q: 802+7145+6z
A: Let's think step by step. 802+7145-7947
794746-7953
So, 802+7145+6=7953.
The answer is 7953.
Q:7+777
A: Let's think step by step.
747-14
1447-21
So, 74747-21.
The answer is 21.
B.9 CHAIN-OF-THOOUGIT PROMPT FOR MULTIPLY-AS-ADD
We use prompt examples 107, x x 9, x order.
Q: 3*07=
A: Let's think step by step.
3+100=300
3+7=21
300+21=321
So, 3+107=321.
The answer is 321.
5:6*
A: lett' think step by step.
5+6-30
So, 5x6-30.
The answer is 30.
B.10 ALGORITHMIC PROMPT FOR MULTI-ADD WITH ALGO CALLS
This prompt uses single example to illustrate multi-number addition. The special tokens that correspond to the start and end of the question extraction are Subprobles em: and <GET>.
Problem: 802+7145+6=
Explanation:
The subproblems are 802+7145-ANS1 and ANS1+6-ANS2. Since ended ANS.2, there are operaters.
Since there are 2 operators and we processed up to ANS1, there are more operators to process.
Subproblem: 802+7145(6E77=77977
Subproblem: 7947+6(<ET)=7953. Since there are 2 operators and we processed up to ANS2, the problem is complete. The final Answer is 7953.
B.11 ALGORITHMIC PROMPT FOR MULTIPLICATIION ADDIITION WITH ALGO CALLS
This prompt uses a single example to illustrate wawpiiiattiona--adtiiiiti and combines it with the multi-number addition example from Section B.10 The special tokens that correspond to the start and end of the question extraction are Subproblem: and <GET>.
Problem: 3+7=
Explanation:
find the smaller the numbers and add the larger number as many times as the smaller number. The first number is 3, FN-[3]-3. The second number is 7, SN=(7]=7. Since 3 is smaller than 7, we rewrite the problem as summed together times: 7+7+7. We end at -NN(3-1)---AN92,
Since the problem is miltiplication,
Since ended ANS_2, 7+7=ANS1 and AN81+7-ANS2. there are 2 operators.
The subproblems
Subproblem; (GET))))1 Since there are 2 operators and we processed up to ANS1, there are more operators to precess.
Subproblem: 14+7(2ET)=21. Since there up ANS2, the problem is complete. The final Answer is 21.
operators and processed
36

---

Under review as a conference paper at ICLR 2023
B.12 CHAIN-OF-THOUGHT PROMPT FOR MULTI-ADD
Q: 9980+29= A: Let's think step by step. So, 9980+29-10009. Q: 802+714546
9980+29-10009
The answer is 10009.
A: Let's think step by step.
80247145-7947 794746-7953
B.13 ALGORITIMMIC PROMPT FOR GSMSK
The following is the full prompt corresponding to the "W/ plan W/ algo" experiment in Figure 7(a)
37

---

Under review as a conference paper at ICLR 2023
Q: Tommy has 3 toy cars. His neighbor, Jessie, has 3 cars too. Jessie's older brother has 5 more than Tommy and Jessic. How many cars do the three of them have altogether?
A: <NONALGO> Tommy and Jessic have 3+3=6 cars. Jessic's brother has 5+6-11 cars. Altogether, they have 6+11=17 cars. The answer is 17. Q: An elestronic shop offers smartphones for $467 each, PCs are $128 more expensive than smartphones, and advanced tablets are the prices of smartphone and PC combined. How much do you have to pay to buy one of each of the three mentioned products?
A: <ALGO> To solve this problem, we need to find the prices of PC and advanced tablet. Then, need to add the price of all three products together.
The price of a PC is $128 more than a smartphone, thus the price of PC is 4674128. We use the addition algorithm:
Problem: 467+128=
Explanation:
The subproblems are 467+128-ANS1. There connecting operator.
Subproblem: 467+128-ANS1
The first number is 467, 1N=14,6,7], 7]. The second number is 128, 8N= Since EN 13,6,71 has digits, SN 11,2,8] has 3 digits, thus the maximum number of digits is 3. In each subsequent step, remove one number from the end of PN and one from the end of SN. length of is 0.
Length of FN is 3. EN=14,6,7). FN13]=7.
Length of SN is SN=11,2,81. SN[3]=8. CI3]=0. Since 7+8+0=15, 15>10, 15810=5. Length of is 1. Thus A=[5]. Since (15-5)/10=1, C12]=1.
Length of FN is 2. EN-[4,6]. FN[2]-6. Length of sN is 2. SN- (1, SN[2]-2. c[2]-1. Since 6+2+1-9, 9<10, 9810-9. Length of A is 2. Thus A-[9,5], Since (9-9)/10-0, c[1]=0.
Length FN is 1. FN=[4]. FN[1]=4. Length of is 1. SN-(1] SN(1]-1. c(1]=0. Since 4+1+0=5, 5<10, 5810-5. Length A is 3. Thus A-(5,9,5]. Since (5-5)/10-0, c[0]=0.
There are no more digits and C10]=0. Thus the process is complete. Since there is operator and processed up to ANSI, the problem. is complete. The final Ansver is 15,9,51. Removing all commas, we have 595.
The addition algorithm tells us that the price of a PC is 595. Since the price of an advanced tablet is the sum of smartphone and PC, its price is 467+595. We the addition algorithm: Problem: 467+595=
Explanation: The subproblems are 4674595-ANS1. There is connecting operator. Subproblem: 467+595-ANS1
The first number is 467, FN=14, 7]. The second number is 595, SN=15, 5]. since EN 64, has digits, SN [5, 9, has 3 digits, thus the maximum number of digits is 3. In each subsequent step, we remove one number from the end of FN and one from the end of sN. Length of A is 0.
Length FN is 3. EN=14,6,7J. FN13]=7. Length of is 3.
9N=15,9,51. 3N13]=5. =13]=0. Since 7+5+0=12, 12>10, 12810=2. Length o A is 1. Thus A=121. Since (12-2)/10=1, c12]=1.
Length of FN is 2. EN=14,61. FN[2]=6. Length of sN is 2. SN=15, 5,, 9). SN[2]-9. c[2]-1. Since 6+9+1-16, 16>10, 16410-6. Length of A is 2. Thus A=16,2]. since (16-6)/10=1, c[1]-I Length of FN is 1. FN-14). FN[1]-4. Length of SN is 1. SN- [5]. SN[1]=5. c[]]=1. Since 4+5+1=10, 10=10, 10810=0. Length of A is 3. Thus 2=[0,6,2]. Since (10-0)/10=1, c[0]=1
digits, but c10]=1. Length of is 4. A= 6, 2] Thus the process is complete. Since there is operator and we processed up to ANS1, the problem is complete. The final Answer is (1,0,6,2). Removing all 3 commas, we have 1062.
There
###cont inudd on next page
38

---

Under review as a conference paper at ICLR 2023
The addition algerithn tells us that the price of an advanced tablet is 1062. To buy of each of these products, you would have to pay
4674595+1062. We use the addition algorithm:
Problem: 467459541062-
Explanation:
The subproblems are 4674595-ANS1, ANS1+1062-ANS2. There are connecting operators.
Subproblem: 467+595-ANSI
The first number is 467, FN=14, 71. The second number is 595, 9N=15,9,51. Since EN 14,6,7 has digits, SN 15,9,5] has 3 digits, thus the maximum number of digits is 3. In each subsequent step, remove one number from the end of and one from the end of SN. Length of is 0.
Length of FN is 3. 6N-[4, FN[3]-7.
Length of SN is 3.
[5,[5,,,5], SN[3]=5. c13]=0. Since 7+5+0=12, 12>10, 12810-2. Length of is 1. Thus A=[2]. Since /10=1, C[2]=1.
Length of is 2. FN-[4,6]. FN[2]=6. Length of SN is 2. (N,
SN[2]=9. c12]=1. Since 6+9+1=16, 16>10, 16t10=6. Length of A is 2. Thus A= Since (16-6)/10=1, c(1)=1.
Length of PN is 1. FN=14]. FM[1]=4. Length of SN is 1. SN=[5]
SN[]]-5. c[1]=1. since 445+1=10, 10-10, 10810-0. liength of Thus 6,2] since (10-0)/10-1, c[o]-1.
There are no more digits, but c[0]-1. length of A is 4. A-[1,0, 6, 2]. Thus the process is complete. Since there are 2 operators and we processed up to ANSI, there 11, 11,0,67 6, subproblem: ANS141062-ANS2
operators to process. The EN
The first number is ANS1, 1N, 2, The second number is 1062, 0,-11,0,6,
since EN 11,0,6,2 6,2] has digits, SN 11,0, 6, has digits, thus the maximum number of digits is 4. each subsequent step, we remove one number from the end of EN and one from the end of SN. Length of A is 0.
Length of FN is 4. EN=11,0,6,2] FN14]=2. Length of SN is 4.
0,221. S814]=2. C14]=0.
Since 2+2+0=4, 4<10, 4810=4. Zength A is 1. Thus A=14). Since (4-4)/10-0, C[3]-0.
Length of PN is 3. FN-[1,0,6]. PN[3]-6. Length of SN is 3.
5N-[1,0,6]. SN[3]-6. C[3]-0. Since 6+6+0=12, 12>10, 12810-2. Length
of A is 2. Thus A=12,4]. Since (12-2)/10=1, c12]=1. Length of is 2. FN=[1,0]. FN12]=0. Length SN is 2. SN=(1,0],
SN12]=0. c[2]=1. Since 0+0+1=1, 1<10, 1810=1. Length of A is 3. Thus 4=(1,2,4], Since (1-1)/10=0, c[1]=0.
Length of PN is 1. FN=[1]. FN[1]=1. Length of SN is 1. SN=(1] SN[1]=1. c[1]=0. Since 1+140=2, 2<10, 2$10=2. Length A 4]. Since (2-2)/10-0, C[0]-0.
Thus
There are no more digits and c[0]-0. Thus the process is complete. Since there are 2 operators and we processed up to ANS2, the problem is complete. The final Answer is 12,1,2,41. Removing all 3 commas, we have 2124.
The addition algorithm tells us that the sum of all the products is 2124. The answer is 2124.
Q: Cally and Danny washed their clothes. Cally has 10 white shirts, 5 colored shirts, pairs of shorts, and pairs of pants, while Danny has white shirts, 8 colored shirts, 10 shorts, and pairs of pants. How many clothes did they wash?
A: <NONALGO> They washed 10+6=16 white shirts. They washed 5+8=13
colored shirts. They washed 7+10=17 sherts. They washed 6+6=12 pants. Therefore, Cally and Danny washed total of 16+13+17+12-58 clothes. The answer is 58.
Q: If there are four times as many red crayens as blue crayons in a box, and there are 3 blue crayons. How many crayens total are in the box? A: <NONALGG0> There are times as many red crayons as blue crayons, which means there are 3+34343-12 red crayons. Since there are blue crayons and 12 red crayons, in total there are 12+3=15 crayons. The answer is 15.
###continued next page
39

---

Under review as a conference paper at ICLR 2023
Q: Larry spent $5 for lunch and gave his brother $12. How much did Larry have at the beginning if he has $3 new?
A: <ALGO> To solve this problem, we need find the total amount that Larry spent and add it to the amount he has left.
Larry spent $5 for lunch and gave his brether $12, which means he spent 5+12. We use the addition algorithm:
Problem: 5+12-
Explanation:
The subproblems are 5+12-ANS1. There is connecting operator.
Subproblem: 5+12=ANS1
The first number is 5, FN=15]. The secend number is 12, SN=[1,2). Since [5] has digit,
[1,2] has digits, thus the maximum number of digits is 2. In each subsequent step, we remove one number from the end of FN and one from the end of SN. Length of A is 0.
Length of FN is 1. EN=[5]. FN[2]=5. Length of SN is 2. [N=[1,2].
SN[2]=2. CI2]=0. Since 5+2+0=7, 7<10, 7810=7. Length of A is 1. Thus A-[7]. Since (7-7)/10=0, c[1]-0.
Length of FN is 0. EN=I]. EN[1]=0. Length of sN is 1. SN= SN[1]=1. cI1]=0. Since 0+140=1, 1<10, 1810=1. Length of A is 2. Thus A=11,7]. Since (1-1)/10=0, C10]=0.
There Since there is operator and we processed up to ANS1, the problem is complete. The final Answer is [1, Remeving all comma, we have 17. The addition algerithm tells that the amount spent is 17. Larry has $3 now, so must have had 1743 the beginning. We the addition algorithm:
more digits and c[0]=0. Thus the process is complete.
Problem: 1743-
Explanation:
The subproblems are 1743-ANS1. There is connecting operator. Subproblem: 17+3-ANS1
The first number is 17, FN. The secend number 3, SN- [3]. Since EN [1,7] has 2 digits, SN [3] has digit, thus the maximum number of digits is 2. In each subsequent step, we remove one number from the end o EN and
from the end of SN. Length A is D.
Length of is 2. FN=11,71. FN12|=/. Length SN is 1. SN=13]. [N[2]-3. c12]-0. Since 74340-10, 10-10, 10810-0. Length of A is Thus A=[0]. Since (10-0)/10-1, c[1]-1.
Length of PN is 1. FN-[I]. FN[1]-1. Length of SN is 0. SN-[]. SNI1]=0. C11]=1. Since 1+0+1=2, 2<10, 2810=2. Length of A is 2. Thus A=12,0]. Since (2-2)/10=0, C10]=0.
There are no more digits and c[0]=0. Thus the process is complete.
Since there is operator and we processed up to ANS1, the problem. is complete. The final Answer is [2, Remeving all comma, have 20. The addition algorithm tells us that the tctal amount is 20. The answer is 20.
Q: Shawn has five teys. For Christmas, he got two toys each from his mom and dad. How many tcys does he have now?
A: <NONALGO> He has toys. He got 2 from mom, after that he has 5+2=7 toys. Then got 2 more from dad, so total he has 7+2=9 toys. The answer is 9.
Q: Karen wanted to go out to get some fast food. She pulls to the drive-through and orders 5-dollar burger. Her then yelled out that he wanted 4-collar sandwich, so was added to the order. Karen then decided to order some drinks and opted for two 4-dollar smoothies. what is the total cost of Karen's s fast-food order?
A: <NONALGO> Karen and her son order 5+4=9 dollars worth of food. Karen decides to buy 4+4=8 dollars worth of smoothies. Thus, the total for this order 9+8=17 dollars, The answer 17.
Q: If there are 100 cars in the parking 1et and 6 more cars arrive, how many cars are in the parking lot?
A: <NONALG0>> There are 100+6-106 cars in the parking lot. The answer is 106.
40


Reviews:
[{"review_id": "u4sD1H1iu0", "reviewer": "Reviewer_UYXX", "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": "The paper introduced a more detailed prompt for LLM math reasoning, and study their impact on task composition and assisting in solving math problems in a recent dataset. The proposed method shows very high accuracy in simple tasks and starts to fall short when the tasks are more complex. One of the challenges is the max number of tokens that the model accepts, so they study multiple alternatives.\nIn summary, the paper shows that precision on the prompt can help to improve LLM reasoning, while the method requires longer prompts so it becomes harder to realize its gains. ", "summary_of_the_review": "The paper proposes a prompting method that focuses on providing a more precise text description of the reasoning. It performs very well in addition, parity and others, but space limitation of the context of LLM precludes performing the real experiments when doing composition and the MATHS problems.\n\nI recommend the acceptance of the paper based on the positive findings, while I recommend interpreting the results without assuming that LLMs would be able to achieve high performance.  \n", "strength_and_weaknesses": "Strengths\n- The systematic study of the structure of the prompt, including influential related work.\n- Focus on the number of digits to study the generalization\n- Study of kind of errors in the proposed prompt strength the proposal\n\nWeaknesses\n- The interference found is a negative result in an area poorly understood. It's entirely possible that a slight variation of the prompt managed to fix the issue. I'm not ready to accept strong interpretations of \"X prompt didn't work\". I suggest lowering the tone of such findings. \n- The jump from addition to combination with subtraction is relatively small at an abstract level: just four combinations. This could become a strength if presented as a simple change that becomes challenging for the LM.\n\nPotential weakness\n- The study of the composition of skills gets confusing around multiplication. The setting of using a shorter explanation becomes out of the general hypothesis. This might become a strength if it were presented as a limitation and not as a solution.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Xi11xX2P-D", "reviewer": "Reviewer_9LM1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The authors study whether degrees of algorithmic reasoning emerge from pre-trained large language models (LLMs) by only intervening on the input prompt. Basically, the authors show that by describing all mathematical passages underlying a certain mathematical operation, e.g. addition, directly in the prompt, LLMs improve at solving these mathematical questions and they exhibit a problem solving process which is akin to an algorithm.", "summary_of_the_review": "While I find the prompting scheme interesting, I don’t find the overall contribution to be relevant for ICLR. The technical contribution is poor, i.e. no learning whatsoever, and the manuscript is not precise and does not present experimental details very clearly. Lastly, a final concern about real-world utility as the prompting does not perform well on harder problems (logical tasks).", "strength_and_weaknesses": "The underlying idea of showing a language model how to break down “complex” data manipulation is quite interesting. From the results, the model seems to benefit from this prompting technique. \n\nI found the paper somewhat hard to follow and the writing style rather confusing. For instance, I did not understand what “defining algorithms as skills” means exactly. This is mentioned several times in the manuscript but it looks to just boil down to using the aforementioned prompting technique. The paper should make a clear statement somewhere that the language model is not re-optimized and no weight updates actually happen, since the name “in-context learning” might be misleading.\n\nThe main drawback of the manuscript is that technical details of the experimentation are largely missing. The authors do not mention explicitly how many examples they provide in the prompt for each task, whether it is only one or multiple. Details of the baseline are not provided either, such as which prompts are used, making the comparison between different ideas harder.\n\nSection 3, evaluation metric paragraph -- “We measure [..] OOD performance [..] where the model sees shorter examples at training time and generalize” -- missing s, typo -- ”to longer problems at test time”. This should be rephrased, there is no training/test time as long as a learning problem is not formulated and executed.\n\nUsage of space is not well-balanced, the authors dedicated a full subsection for explaining “two-number addition” (section 3.1) and only a few paragraphs for all the others. In particular, the algorithm for parity is not even mentioned but its results appear in table 2.\n\nSection 4 shows that we can “teach” multiple problems at a time, such as subtraction and addition. This looks to perform worse than showing each problem separately, therefore I am not exactly sure what conclusions can be drawn from there.\n\nWhile it is undoubtedly interesting that “hard” reasoning capabilities emerge from LLMs with the right prompt, the problems faced in the paper seem only to be “toy problems”. The fact that this prompting fails on logical tasks (section 6) poses serious concerns on its applicability on harder problems other than simple mathematical operations and, therefore, its real-world utility.\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HSv1JJb1UP", "reviewer": "Reviewer_Ke6m", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 proposes a new prompting method called algorithmic prompting that aims to teach algorithms to LLMs via in-context learning. Specifically, the method focuses on using very details execution traces and explanations as part of the in-context demonstration to remove any ambiguity. Using this prompting method, in-context learning performance on simple arithmetic operations is significantly improved, especially under length extrapolation setting. Furthermore, the authors also demonstrate that models can acquire more/composed skills by having algorithmic prompting demonstrations of two different/composed algorithms in the context. The authors also show that it is possible to use the learned algorithm as a tool for solving math word problems.\n", "summary_of_the_review": "Overall, the proposed method demonstrates significant improvement in some simple settings and I think this is an interesting direction. But so far it is unclear whether this technique can be scaled to more complicated problems.", "strength_and_weaknesses": "Strength:\n- The method makes sense conceptually and demonstrates significant performance gain upon standard scratch pad/CoT in multiple aspects.\n- The performance improvement for length extrapolations is especially impressive.\n- The paper is clearly written with concrete examples.\n\nWeaknesses:\n- The demonstrated examples are all for very basic arithmetic operations, and it is unclear whether this technique can scale to more complicated cases.\n- The algorithmic prompting method conceptually requires that we know how to break down the target operation (like parity) into recurrent steps and provide traces. With this level of specificity required, it is no longer necessary to use prompting to solve the tasks (we already solved it with our brain when providing the prompt and can totally write a program for it). Some generalizations (other than length) from the demonstration to the actual task would make the method much more useful. Some examples:\n    - Can algorithmic prompting be extended to operations we only know the structure of? Like solving dynamic programming problems with demonstrations for a DP problem with different state space or update functions? \n    - The skill composition could also be very useful if the demonstration of combining skills A and B can be generalized to combine A and C or even B and C. \n- The length extrapolation intuitively only works because the recurrent step is the same for all lengths, so LM can follow the demonstration in a straightforward and local way. Although this is arguably possible for all operations, it could lead to a very large state to carry over in each recurrent step. In fact, even for just addition, the copying of a large number of digits in context repetitively already seems very expensive given the limited context window. The second-pass strategy seems a promising start to handle this. Maybe the demonstration can just only demonstrate the recurrent step from f(n + 1) to f(n), so that each recurrent step can be generated in a separate context like a recursive call? \n- For the final tool use demonstration, what is the advantage of <call_add_algo> over calling the injected calculator as designed in the original dataset?", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject