CLeAR: Continual Learning on Algorithmic Reasoning for Human-like Intelligence
Authors: Bong Gyun Kang
HyunGi Kim
Dahuin Jung
Sungroh Yoon
Venue: NeurIPS 2023 poster (2023)
Keywords: Continual learning
Knowledge transfer
Algorithmic reasoning
TL;DR: Propose novel human-like continual learning scenario "Continual learning on algorithmic reasoning" and ways to solve it.

Abstract: Continual learning (CL) aims to incrementally learn multiple tasks that are presented sequentially. The significance of CL lies not only in the practical importance but also in studying the learning mechanisms of humans who are excellent continual learners. While most research on CL has been done on structured data such as images, there is a lack of research on CL for abstract logical concepts such as counting, sorting, and arithmetic, which humans learn gradually over time in the real world. In this work, for the first time, we introduce novel algorithmic reasoning (AR) methodology for continual tasks of abstract concepts: CLeAR. Our methodology proposes a one-to-many mapping of input distribution to a shared mapping space, which allows the alignment of various tasks of different dimensions and shared semantics. Our tasks of abstract logical concepts, in the form of formal language, can be classified into Chomsky hierarchies based on their difficulty. In this study, we conducted extensive experiments consisting of 15 tasks with various levels of Chomsky hierarchy, ranging from in-hierarchy to inter-hierarchy scenarios. CLeAR not only achieved near zero forgetting but also improved accuracy during following tasks, a phenomenon known as backward transfer, while previous CL methods designed for image classification drastically failed.

CLeAR: Continual Learning on Algorithmic Reasoning for Human-like Intelligence
Bong Gyun Kang!*
HyunGi Kim?
Dahuin Jung?
Sungroh Yoon 1.2
1 Interdisciplinary Program in Artificial Intelligence, Seoul National University Department of Electrical and Computer Engineering, Scoul National University
Abstract
Continual learning (CL) aims to incrementally learn multiple tasks that are pre- sented sequentially. The significance CL lies not only the practical importance but also in studying the learning mechanisms of humans who are excellent contin- ual learners. While most research on CL has been done on structured data such images, there is lack of research CL for abstract logical concepts such as counting, sorting, and arithmetic, which humans learn gradually over time the real world. In this work, for the first time, we introduce novel algorithmic reasoning (AR) methodology for continual tasks of abstract concepts: CLeAR. Our methodology proposes one-to-many mapping of input distribution to shared mapping space, which allows the alignment of various tasks of different dimensions and shared semantics. Our tasks of abstract logical concepts, in the form of formal language, can be classified into Chomsky hierarchies based on their difficulty. In this study, conducted extensive experiments consisting of 15 tasks with various levels of Chomsky hierarchy, ranging from in-hierarchy to inter-hierarchy scenarios. CLeAR not only achieved near zero forgetting but also improved accuracy during following tasks, phenomenon known as backward transfer, while previous CL methods designed for image classification drastically failed.
Introduction
From an early age, humans develop their ability to solve complex logical reasoning problems through lifelong learning. They gradually learn sequential cognitive skills, from basic counting methods to more advanced concepts such as addition, subtraction, and logical operations (2] Although this sequential learning ability is inherent in humans, deep learning models experience catastrophic forgetting (30), where their performance on previous tasks rapidly declines, after learning a new task. Continual learning (CL) 19 is essential not only for practical purposes but also for developing human-like artificial intelligence that can maintain its performance on previous tasks after lcarning new tasks. However, existing CL. research has been limited learning streams of structured data with fixed input formats, such as images, where each task involves the same classification task only with different image classes [4 [ 48 Current approaches fail to reflect the learning of abstract logical concepts that humans continuously acquire in the real world.
There are three major challenges in naively leveraging existing CL methodologies to continual algorithmic reasoning (AR) tasks. Firstly, in AR tasks, input data contain little information, and the input data and task are decorrelated (Fig. [ip). In traditional image CL, the inherent information in the image itself enables the model to estimate which task the image belongs to [18]. However, in CL for abstract concepts, the input data may be completely decorrelated from the task that the model needs
" Juckypanda @ snu.ac.kr * The code is available at http://gittaacommPsscooacaCCCCCe t Corresponding author (sryoon @snu.ac.kr)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Parity Check
Modular Arithmetic
SUM of sequeeee
0101: Even
3+1 (Mod5)
1001010:
1x2-4 -4 [Mod5]
00101011:
3x3-1-2 = (Mod5)
110:0100:
2x4x2 (Mad5)
T1. SUM even(odd)
0010: Odd
2x113x4+1 (Mod5)
11010 0110101...
T2. First & Last digit same(different)
Identical input distribution
Variant tasks
(a) Sequential Tasks of Learning Logics
(b) Input-Tase Task Decorrelation
Figure 1: Introduction of continual learning on algorithmic reasoning (a) showing two representative
continuous AR tasks and (b) showing an example of two tasks sharing identical input distribution.
to learn. For example, consider binary input sequence consisting of O's and I's. In the first task, the model needs to determine whether the sum of the sequence is odd or even, while in the second task, needs to determine the square root of the sequence when treated as a binary number. In this case, the input data distribution is identical for both tasks, thus is impossible to correctly predict the task based on the input data. Therefore, CL for AR of abstract concepts is better suited to task incremental learning. Moreover, since the input data contains little information, learning data distribution (e.g. contrastive learning based CL) is inapplicable.
Secondly, the dimensions of the datasets of each task can be dynamic in the AR of abstract concepts. In current CL, data has mostly fixed shape and dimension (ex. height, weight, and channel H x W x C) throughout the tasks [47] 1 48). However, ways of representing each "abstract logical concept" as the sequential input-output format are various [1] [26]. For example, when trying to train the model for modular arithmetic, there are various ways to introduce the concepts of numbers and operators to the model. Specifically, all used numbers and operators can be one-hot encoded numbers, and operators can be represented in different dimensions, or numbers can be represented in binary format. Furthermore, input sequences of different tasks result in different dimensions and lengths. Therefore, it is impossible to apply the same model directly to each task's 's data like the traditional image CL methodology, and additional operations adjusting the data shape are necessary.
Thirdly, the goal of generalization that the AR task aims to achieve different. In traditional CL, the model learns the input data distribution itself, assuming that the train dataset and test dataset are identical and independently distributed (IID) 45) However, in AR tasks, the model learns the general rule that generates labels from input distribution. To identify whether the model has appropriately learned to generate the correct answers rather than simply memorizing them, the test set is composed of
(OOD) data [33] that was never seen during training. Therefore, the goal of AR is not generalization performance for IID as in traditional CL, but generalization for OOD [4. Due to these characteristics. the performance of replay- based CL methods that replay buffer to represent the input data distribution decreases. The core of the replay buffer is to extract representative samples prototypes that represent the input data distribution [5]. However, unlike sharp-eared and long-tailed image that represents a cat class, "5+8=13" cannot be considered as representative of the concept of arithmetic.
This work. We have developed CL. methodology that can be applied the aforementioned scenario. We have applied novel one-to-many mapping strategy to handle input data of different formats, and through this mapping, we have proposed ways to prevent forgetting previous tasks when learning new tasks, and even increased performance on previous tasks during the process of learning new tasks. We conducted extensive experiments on sequential models such as RNN, LSTM, and Tape RNN [12 [5] 17] 43 which have memory, and used AR tasks with various levels of Chomsky hierarchy to conduct extensive experiments on sequential tasks of the same level and different levels.
We introduce the scenario of CL on AR for the first time. This scenario is of great importance it is similar to how humans learn logical reasoning abilities incrementally in the real world and has very different characteristics from conventional CL. scenarios as described above.
We introduce new data mapping methods and CL algorithms that are applicable to the aforementioned scenario and have demonstrated high performance not only in catastrophic forgetting but also in knowledge transfer, which is one of the ultimate goals of CL.

---

We demonstrated the superiority of our method over the existing CL methods in our proposed CL scenario for AR through extensive experiments on various combinations of AR tasks. We also showed that existing CL. methods perform poorly due to the reasons described above.
2 Preliminary
Continual learning. CL is one of the long-standing challenges in deep learning [35], aiming to preserve the performance of previous tasks while effectively learning new tasks (without access to data from previous tasks) in situations where multiple tasks are learned sequentially. The existing CL methodologies can be broadly classified into three categories based on the methods used to prevent catastrophic forgetting [24]. First, regularization based methods [19 22 21] constrain the model's s important parameters for the previous task from changing when learning new task. Elastic Weight Consolidation (EWC) 19 approximates the Fisher information matrix to learn loss-minimizing weight space and regularizes the gradient direction maintain the low loss for previous tasks. Learning without forgetting (LwF) [22] regularizes the loss through knowledge distillation by using the output of previous tasks as pseudo-labes
during the learning of new tasks. Second, memory- based methods [5] 22 4 37 are further divided into experiment-replay and orthogonal projection methods. Experiment replay (ER) 5 stores small amounts of data from previous tasks in memory use their information when learning new tasks. The performance of this method depends on the representative sample selected capture the entire distribution of data. Orthogonal projection methods ( stores gradient and update weight in a direction orthogonal to the gradient from the previous task. Third, parameter isolation-based methods [39 28 40) use different parts of the model's parameters for each task. The parameters used in previous task learning are masked during the learning of the next task, and the model can also be extended as new tasks are introduced.
Recent CL models aim not only to prevent catastrophic forgetting of previous tasks but also to enhance the overall performance of the entire task by transferring common knowledge between tasks (24). This is a property that humans, as excellent continual learners, naturally possess, allowing them learn new tasks more easily from previous experiences and gain deeper understanding of previously acquired knowledge as they learn new tasks. However, such knowledge transfer is not easy for deep learning models to obtain. Backward transfer refers to improving the performance of previously learned tasks by learning the current task, while forward transfer refers to previously learned tasks helping to learn new task. Although there have been studies in this knowledge backward transfer is still hard to achieve [46).
Knowledge Transfer:
area
39 25
Algorithmic Reasoning. The core of human logical reasoning ability lies in inductive inference 20 36). This is the ability to derive general rules from finite examples and use them to infer the correct answers from unseen data. From the perspective of deep learning. this is AR 11 23 where the model receives a finite number of input-output data and infers the underlying general rule to generate output for input seguences that have not been seen before. There has been much research on program induction [34] [2 32 [I), however, conventional approaches for serial AR have a critical limitation in that they require prior human knowledge about the task pre-configure the model (29 44 [3] In general deep learning, the model learns through empirical risk minimization of statistical learning theory to achieve the theoretical bound of its performance and estimates the generalization error using test data 45 An important assumption here is that the train and test data are independent and identically distributed (IID). However, in AR, where the model needs to learn general rules, this assumption is violated [II. Therefore, in AR tasks, we have to measure the model's performance not only on the train data distribution but also on -ut-of-distribution (OOD) distribution [
Formal Language and Chomsky Hierarchy. Computational problems that generate output through learnable rules can be represented in formal language [41] [ 33). Formal language can be classified into hierarchies based on their complexity, which is known as the Chomsky hicrarchy 3 D. The hierarchy ranges from regular language, which requires the lowest complexity of memory, context- free language, which requires stack-type memory, sensitivv language, which requires linear tape memory, and recursively enumerable language, which requires infinite tape memory. Research has been conducted on whether various deep learning models can learn each level of formal language in this hierarchy [1] 12 7. Results have shown that there is a Chomsky hierarchy bound on the formal language that each deep learning model can learn, whereas models with external memory can leam languages of high Chomsky hicrarchy.
3

---

3 Method
Problem Statement. Our goal is to train fixed-size model that sequentially learns various abstract logical tasks, following a standard CL scenario. We assumed that predicting the output sequence corresponding to the imput sequence, as in [II] is closer to real-world scenarios which are learned through inductive inference than inferring the internal state of automata, as (26). There are various methods of representing the same abstract logical concept into an input sequence that model can understand. However, different forms of input can affect the performance of the model. Therefore, for fairness, used the data format proposed in the previous paper
In a CL scenario. sequence of tasks t is given as dataset D; ((x,,) 1e with S. sample pairs. Each pair of Ye, comes from { OOn-hoot( Lin) E -0, 10, ( One-hot(LLow)) E {0, 13((E four) }. where
{task f] is given one after another. Each task
In E {{Ein)
hin SN and T.out E E{Eouut } loue is input and output language pair from task t. N is
given the input sequence length limit. Σ and Eout are corresponding alphabets.
model fo(-) parameterized by fixed-sized To match different sized input Xt,; of each task to model input, we require a task-wise mapping function (-). Also, to project the model output vector to match different sized output Yr,i, we applied task-wise linear projection head (.) which consists of a single layer perceptron. After learning a k-th task, the model is parameterized by (kk), and the projection head becomes h.,)
Consider a sequence-to-sequee
During training, the model can only access data from the current task. And after training, to evaluate whether the model actually learned the general output sequence generation rule, the model is tested
on OOD dataset (Dfestt = [(xffort vlest) g which are created in the same method as train dataset N-llisM
)
and its corresponding output sequence L'uut E { [ loue learning a k-th task, model performance on task / is measured using an average of per-sequence accuracy of test data, i.e., ACC
from L E {Ein)
After
k.t
ACC k.t
1
Σ
(2,, y)
Stestt
1 Σn [argmax, yji) = (argmax, (m, y
(r, (z. y) =
Following we set the maximum training input sequence length to 40 (N = 40) and sampled input sequence length from the uniform distribution 2(11, N). OOD test set input sequence length was sampled from the uniform distribution U(N + 1, M) where N 40 and M = 100.
Tasks. We conducted a comprehensive evaluation of CL on AR (CL-AR), involving 15 diverse logical reasoning tasks. These tasks exhibit various levels of complexity, resulting in different our AR tasks and the corresponding Chomsky hierarchy. The
Chomsky hierarchies. Table detailed information for each task is in Appendix A. We conducted three major CL scenarios. (a) nigh-correlation CL-AR scenario continually learns the same kind of task with varying difficulty. One example the Modular Arithmetic task with increasing modular value enabling the model to access larger numbers. Another example is the Cycle Navigation task with increasing cycle length. This scenario allows us to interpret the model's behavior upon learning highly correlated reasoning tasks. (b) In-hierarchy CL-ARR scenario continually learns various tasks of the same level of Chomsky hierarchy. This scenario allows us to analyze the interaction among tasks different natures but with similar complexity. (c) hiter-hieraryhy CL-AR scenario consists of tasks of different Chomsky hicrarchies. This is by far the most challenging scenario for neural network that has to manipulate its memory structure.
Models. Recently, there have been numerous quantitative studies on whether various architectures of neural networks can learn formal languages. In recent research, it has been shown that regardless of the increase the number of training data, models have "hard limitations for scaling laws" " and cannot lear generalization rules based on the complexity of the task and the inductive bias of the model. Furthermore, to learn high-level tasks, models with external memory are necessary, and the commonly used transformer model has demonstrated very limited AR performance. Therefore, in

---

{0,13 Dimm 1, 1,
(0,1)Dimm
Mapping space
One to-ttoymmyy
Task 1
Domain valid input
Valid input for both tasks
One to-one
Model
[0,1) Dim
One-to-one
Task 2
One-to-many
Domain of valid input
Range Codomain
Figure 2: my maps this input space to the entire mapping space, which shared across all tasks. In order to map the entire space, mapping from the input space to the mapping space become one-to- many, making an arbitrary point in mapping space to be mapped from a valid input sequence for every task. Also, this mapping function ensures that the distribution of inputs from the input space becomes a uniform distribution the mapping space.
this paper, we used RNN [2] and LSTM [1]. as well as stack RNN [17 and tape RNN 43 which have additional differentiable memory structures added the standard RNN. The length of the external memory stack and tape stack RNN and tape RNN was set to 40, and each element had dimensions 11 and dimensions were doubled with CL of more than 5 tasks.
Evaluation Metries. We adopt generalization accuracy as the basic evaluation metric. Final model accuracy (ACC) is the average accuracy of all tasks after learning all tasks as follows:
T
ACC = Σ ACC
(1)
In order to evaluate not only the catastrophic forgetting but also the model's knowledge transfer capability, we introduced a metric that measures backward/forward knowledge transfer [2 Backward knowledge transfer (BWT) (27) indicates how much learning the next tasks has influenced the performance of the previous task. BWT > 0 indicates that there has been a transfer of beneficial knowledge the previous task during the CL process. Forward knowledge transfer (FWT)) measures how helpful previously learned knowledge is when learning a new task. FWT is obtained by calculating the difference between the accuracy achieved in the CL scenario and the accuracy achieved by training an independent model (as Table
[6].
D. BWT and FWT are expressed as follows:
BWT T
Σ
ACC - ACC
FWT T
Σ
ACC
ACC
CLeAR. We propose novel CL algorithm for the CL-AR scenario: CLeAR. The CLeAR model is divided into two main parts. The first part is mapping function m, that maps se- quences sampled from the input data distribution to shared mapping space. The second part consists of the main model fo(-), which learns labels from the features in the feature space, and the fask-wise angle-layer projection head h,
Algorithm CLeAR-training procedure for given task
Input:
Trained up task t-1: my, fa(1-1) and ha.e-1 --1 (1 S <)
Dataset task D.
Train:
Train me with Dr
fa = so(t-1 and h4 1u,1- (1 Freeze fole-1). ha.e-1 (1 <t) Random initialize hts for Z2.4s Vt. ~ De do (Pre-tuning with small samples)
Ot,i h4 fe((-1) (Xe.).))
L Lnew (o Vt.s)
Compute VL and update ht
maps the input sequence sampled from the input space of task feature space (mapping space), pre- serving length but changing dimen- sion to fixed size D Dmap- The input sequence consists of binary values, de- noted as (0, 1) (D.... and the range of the mapping space is expressed as {0, 1) ( (Dman.!) As described in Fig.
end for
for Vl, ~ D. do (Main training) Du.s argmax h So(e-1) (X..)) for 1...t-1
Ou.i f- hy fo (x....)) for 1..
L= X. ):1 Laul(R,s Dv.e) Lnew (or,s, Vk..)
Compute L and update fo. by for k 1...
end for Output:
Trained up to task ma. fo and by (1 S l: S t)

---

Input Sequence
0 0 0 1
1 0 0 0
0
Perfect Reconstruction
Mapped Sequence
Input Sequence
1 0 0 0
0/1
Encoder
1
0
1
Decoder
Mapped Sequence
0/2
1
0
1
0/1
Random Noise
0/1
0
0
1
Decorrelation
1 0
1 0
0
0
0
0/1
3. Mean 0.5
Figure 3: Mapping function is trained using encoder-decoder architecture and under three constraints. First, input sequence is perfectly reconstructed. Second, each column of mapped sequence is decorrelated. Third, each column of mapped sequence has mean of 0.5.
our mapping finctiinn my has the following characteristics. First, an arbitrary sample from the input distribution is mapped to one or more points in the mapping space (one-to-many). Sec- ond, for any point in the mapping space, a corresponding sample exists in the input space. Third, the mapping of input distribution resembles uniform sampling in the mapping space: me (wiiinttdistrrruutte distribution) Re (({0, 1) (Dmaa))) Therefore, the mapping function of each task expands the input distribution to fill the mapping space fully. Thus, an arbitrary sample drawn from the map- ping space can correspond
valid input sample for any task. This allows the model to consider single sequence in the mapping space as valid input for each previous task. is similar to how we can perceive the number 395 in various ways, such as being odd, multiple of or having sum of digits equal to 17. These mapping functions can be expressed very simply, requiring minimal computational resources in the overall model. Additional details about the mapping function, positional mapping. and specific mapping for each task are explained in Appendix C.
To create such mapping functions, an encoder-decoder structure is considered for tasks where the distribution of alphabets is preserved across all positions of the input language. As shown in Fig. 3 the encoder takes the input sequence sampled from the input space and additional random noise to generate a mapped sequence. Then, the decoder reconstructs the input sequence from the mapped sequence. In this process, each column of the mapped sequence should have mean of 0.5 and should be decorrelated from each other. The encoder serves as the mapping function, and the decoder is discarded.
The functions fo()) and (+) are trained using a similar approach to LwF [22]. After completing the training for the t-1 th task, the training proceeds for the th task, temporarily saving fo(t-1) 1) and h for this task. First, my is trained. Then, the randomly initialized h2 is pre-tuned while the rest of the model is frozen using small portion of the dataset. For each sample xt,i, N,,,, the pseudo-label for the k-th (1 S l t) task Dk. is obtained by argmax- h fo(t-1) (x,,)... The loss is calculated for all heads. For the outputs of the k-th task heads: hg fo (x,.)) (1 < k < t), the loss is computed with the pscudo-labels Ok.s for S k < t, and for the t-th task head, the loss is computed with y,,-- The final loss is the sum of the losses for each head up t-th. The overall learning process is shown in Algorithm
Experiments
In this section, we first confirmed that applying our mapping function and tuning structure did not alter the learning ability of each model tasks from various Chomsky hierarchies, compared to the previous study [1]. Next, we demonstrate CLeAR's 's superior performance on high-correlation, in-hierarchy, and inter-hierarchy CL-AR tasks through extensive ablations. Furthermore, we analyze the model's robustness terms of noise within the mapping space. A detailed explanation of the experiment setting and comparison with existing CL algorithms [19 22 and their failure is shown in Appendix D.
4.1 Baseline Generalization Accuracy
In T. we presented the generalization accuracy of each model for all tasks in our paper. Corre- sponding in-distribution accuracy and reported generalization accuracy in the previous paper [II] paper shown in Appendix B. was shown that applying mapping and head did not greatly affect the model's performance and did not alter the limits of the Chomsky hierarchy that each model can learn. The reported performance here was used as a benchmark for calculating Single-task accuracy and FWT.

---

Table 1: Baseline generalization accuracy (%) of overall tasks. Each task was averaged on three repeats, trained for 50,000 epochs each. The accuracy value was reported with positional mapping (aceuracy without positional mapping parentheses). For accuracy over 90%, we considered that the model successfully learned AR suggested in [Α The random accuracy is 50% except for Modular Arithmetics (R), Cyclic Navigation (R), and Bucket Sort (CS). Tasks that require additional
positional mapping are tagged with
Level
Task
RNN
Stack-RNN
Tape-RNN
LSTM
Even Pairs
100.0(100.0)
100.0(100.0)
51.4(53.1)
100.0<100.0)
Modular Arithmetic
99.7(98.8)
99.1(99.2)
63.1(82.4)
100.0(100.0)
Regular
Parity Check
100.0(100.0)
100.0(100.00
99.6(99.3)
100.0(100.0)
Cycle Navigation
100.0(98.1)
99.7(100.0)
80.0(97.3)
92.1(87.9)
Compare Occurrence Stack Manipulation Reverse String Divide by 2
96.6(97.9)
99.5(98.5)
97.7(97.9)
99.6(99.5)
Context Free
57.0
83,9
75.6
82.4
77.7(79.9)
80. (80.0)))0)
51.3(56.2)
79.3(79.8)
71.4
92.0
59.8
Duplicate String Interlocked Pairing! Odds First
54.3(53.2
58.0(60.1)
51.3(51.6)
74.2(76.9)
60.6
96.7
53.8
99.7
56.5(56.5)
60.8(61.3)
61.4(61.4)
73.2(72.3)
Context Sensitive
Binary Addition!
48.6
55.4
51.9
71.3
Binary Multiplication'
50.1
52.3
48.9
60.9
Compute Sqrt
57.9(57.4)
64.4(64.1)
56.3(60.3)
66.3(66.7)
Bucket Sort
59.3(55.9)
96.7(97.5)
71.4(78.7)
97.2(98.7)
Table 2: Generalization accuracy (%) on high-correlation CL-AR scenario, averaged on three repeats. Joint refers to simultaneously training all tasks, with tasks alternating at each step and ultimately being learned uniformly. Single refers to averaging the accuracy of each individual task. CL. Initial averages the accuracy immediately after learning each task, while CL. Final is the final average accuracy. CL Final values that are greater than 90% the Joint accuracy were marked in bold, as well as the positive BWT values.
Average Accuracy (%)
Task
Model
Joint
Single
CL Initial
CL Final
BWT
RNN
40.32
99.70
61.08
59.68
-1.64
Stack-RNN
54.24
97.98
63.27
62.66
-0.72
Modular Ari thmetic
Tape-RNN
43.68
84.72
30.84
24.58
-7.31
LSTM
93.07
99.96
96.38
96.25
-0.15
RNN
96.33
99.36
98.57
98.09
-0.56
Stack-RNN
96.97
99.83
98.52
97.88
-0.75
Cycle Navigation
Tape-RNN
56.93
88.65
65,46
67.76
2.67
LSTM
98.72
96.18
99.54
99.37
-0.20
RNN
46.46
64.11
42.64
40.42
-2.60
Stack-RNN
60.00
67.84
68.39
67.69
-0.81
Reverse String
Tape-RNN
24.77
40.53
42.93
39.48
-4.02
LSTM
46.35
65.98
50.73
48.91
-2.12
RNN
51.43
56.06
54,25
51.36
-3.36
Stack-RNN
93.49
94.19
95.16
92.44
-3.18
Bucket Sort
Tape-RNN RNN
73.28
74.54
79.22
77.54
-1.96
LSTM
99.92
98.40
99.55
99.97
0.48
4.2 CLeAR on CL-AR
In this section, we demonstrate that the CLeAR can be applied to various abstract logical tasks, regardless of the model type and difficulty level. Firstly, we conducted experiments on a scenario where a single task becomes progressively more challenging (high-correlation scenario). Since the sequentially presented tasks require similar logical reasoning, there is significant level of correlation between these tasks. For example, the same Cycle Navigation task, the difficulty increases the cycle size expands, while in Modular Arithmetic, the difficulty increases the modular
7

---

Table Generalization accuracy (%) on in-hierarchy CL-AR scenario, averaged on three repeats. Each task is abbreviated to: Cycle Navigation(CN), Modular Arithmetic(MA) Parity CP)) Even Pairs(EP), Divide by 2(DT), Reverse String(RS), Stack Manipulation(SM), Compare Occurrence(COO, Maltippication(BMM) Bucket Sort(BS), Compute Sqrt(CS), Duplicate String(DS), Interlocked Pairing(IP), Odds First(OF).
Binary Addition(BA), Binary
Average Accuracy CL Initial
Task
Model
Joint
Single
CL Final
BWT
FWT
RNN
97.61
99.22
99.85
47.50
-69.80
Regular
Stack-RNN
96.50
99.79
99.42
47.64
-69.04
CN-MA-PC-EP
Tape-RNN
71.05
83.01
98.24
47.44
-67.73
w/o CLeAR
LSTM
98.73
96.96
98.02
50.65
-63.15
RNN
97.79
99.22
98.72
53.80
-5.900
Regular
Stack-RNN
96.50
99.79
99.97
55.11
-59.82
EP-PC-MA-CN
Tape-RNN
71.05
83.01
68.24
47.56
-27.58
w/o CLeAR
L.TM
98.73
96.96
97.48
53.61
-58.48
RNN
97.61
99.22
96.45
96.17
-0.37
-4.39
Regular
Stack-RNN
96.50
99.79
94.89
87.09
-10.40
-10.47
CN-MA-PC-EP
Tape-RNN
71.05
83.01
76.31
76.70
0.53
-8.43
LSTM
98.73
96.96
98.21
96.49
-2.29
0.97
RNN
97.79
99.22
99.68
99.80
0.16
0.72
Regular EP-PC-MA-CN
Stack-RNN
95.22
99.79
98.19
99.28
1.45
-0.50
Tape-RNN
59.61
83.01
58.16
74.45
21.72
-27.17
LSTM
98.72
96.96
99.99
99.96
-0.05
RNN
65.95
75.66
64.13
61.67
-3.27
-14.33
Context Free DT-RS-SM-CO
Stack-RNN
69.64
88.88
79.14
69.95
-12.26
-17.63
Tape-RNN
54.06
71.09
62.26
62.07
-0.25
-9.77
LSTM
82.72
82.86
76.93
79.36
3.24
4.57
RNN
65.95
75.66
64.87
63.89
-1.30
-1.96
Context Free CO-SM-RS-DT
Stack-RNN
69.64
88,88
69.74
67.59
-2866
26.85
Tape-RNN
54.06
71.09
74.42
67.67
-9.01
0.63
LSTM
82.72
82.86
75.69
74.78
-1.21
-9.14
RNN
55.33
55.33
50.77
50.51
-0.34
-5.28
Context Sensitive BA-BM-BS-CS-DS-IPOF
Stack-RNN
52.70
69.19
61.06
60.52
-0.72
-9.53
Tape-RNN
45.97
56.43
46.77
45.97
-1.07
-12.60
LSTM
76.73
77.54
73.48
74.11
0.84
-3.38
value grows. Table shows that CLcAR demonstrated very low forgetting for the most tasks, and in some cases, backward knowledge transfer occurred. In general CL. Joint considered a soft upper bound [10]. We have highlighted CL Final when it exceeds that of Joint, well when surpasses 90%, indicating successful learning of all tasks. Notably. CLeAR effectively preserve the best information they have learned
in cases where task is not fully learned (low CL Initial) when learning a specific task deemed impossible for such a model 11 Secondly, we conducted experiments distinct tasks that belong the same level of the Chomsky hierarchy (in-hierarchy scenario). This represents scenarios where the tasks are of different types but have similar difficulty levels. As evident from the first two rows of Table simple sequential learning without using CLeAR completely forgets the previous task while learning the next task. In contrast, CLeAR exhibits low levels of forgetting for tasks across all Chomsky hierarchies and demonstrates multiple instances of Backward/forward knowledge transfer (Table 33. Note that even in cases not highlighted in bold, CLeAR exhibited very little forgetting or near Joint performance. Lastly, we explored CL for tasks belonging to different levels of the Chomsky hierarchy hiiterr-ierrrhhy scenario). This entails tasks that differ both in type difficulty level. Thole both RNN and LSTM are capable of storing information on tasks of different levels. During the learning process, which includes relatively long and completely unrelated tasks, both models successfully remember all the tasks learned from the very beginning.

---

Table For inter-hierarchy CL-AR scenario, average generalization accuracy (%) obtained for each group of tasks, averaged on three repeated experiments. The scenario consisted of ten AR tasks that followed an ascending order the Chomsky hierarchy: 1PP-NN-C..COOR3--MIPPP------ (abbreviations same with Table 3)
Average
Accuracy (%)
Model
Chomsky hierarchy
Joint
Single
CL Initial
Final
BWT
Regular
60.50
100.0
93.31
75.04
-27.40
RNN
Context Free
59.94
77.10
61.59
60.78
-0.81
Context Sensitive
49.48
57.68
47.13
46.99
-0.19
Regular
96.76
97.37
100.0
93.46
-9.06
LSTM
Context Free
79.70
87.10
80.94
79.11
-1.83
Context Sensitive
83.38
86.08
79.60
77.67
-2.57
Accuracy of first task
0.03
0.9
Noise level (std)
0.8
0.02
0.7
0.01
0.6
t=1
t=2
t=3
=
t=
EP MA PC CN SM DS OF CS
noise std 0.00
stá 0.04
noise std 0.06
noise std 0.08
noise std 0.10
Tasks
(a) Robustness against Different Noise Level
(b) Visualization of Noise Value of Each Task
Figure 4: An analysis of the impact of noise in the mapping space on CLeAR and an assessment of the amount of noise present in each task. In (a), we show that the proposed framework is robust enough till the noise level of std 0.06 for five continual tasks. In (b), we provide the noise level of the task's mapping space distribution for all 15 tasks and show they are all smaller than the notable noise level.
4.3 Robustness to Distribution Shift
Although we aim to map the input distribution become uniformly distributed, this not always possible. We provide quantitative analysis of whether the model can maintain high CL performance without catastrophic forgetting, even in situations where the mapping distribution not uniform. We conducted experiments by adding Gaussian noise with specific standard deviation (std) to the uniform probability distribution on the model's mapping space. As shown in Fig. 4 [), the model exhibited robustness even in the presence of significant noise (std up to 0.06 induces forgetting of 5% or less for the five continual tasks). For our mapping strategy, the std of mapping space distribution is much smaller than the notable noise level for all 15 tasks shown in Fig, 4b).. This indicates that CLeAR performs well for task mappings with distributions that deviate to some extent from a uniform distribution, demonstrating high robustness.
4.4 Joint training of AR tasks
We discovered from the experimental results in Tables 2 and that continual learning of tasks for CL-AR often showed higher performance compared when all tasks were learned simul- taneously (Joint). This contrasts with the conventional view of continual learning that regards soft upper bound [IO]. Therefore, we analyzed the characteristics of the model in continual learning and simultaneous learning. First, we visualized the model's ''s in- ternal feature space for the simplest two tasks, Parity Check (PC) and Even Pairs (EP), as described in this paper [11, to illustrate how the model's learning occurs in each scenario in Fig. 55] From all the plots, we can observe that after the model learns PC or EP, it internally learns the corresponding automata for each task. Furthermore, after CL joint training, it's ev- ident that the hidden feature is clustered to solve both tasks simultaneously (Fig. C, D). When learning EP following PC, the distribution of the hidden features remains similar. and it exhibits a pattern where each cluster further splits. However, in the case of joint training, the hidden features occupy a broader space, and unlike CL, the states for PC clustered into eight pieces.
joint training accuracy

---

0
O
10
S3
54
0
51
S3
1
S2
A
Figure 5: The A represents the automata for Parity Check (PC, up) and Even Pairs (EP, down). Each state (S1-S4) is color-coded to match the features of B. C. and D, with the final states for positive labels highlighted in yellow. Plots show the distribution of the model's 's hidden features using PCA visualization: after PC training (B), after PC-EP CL (C), and after PC-EP joint training (D). The upper row corresponds to PC automata states, and the lower corresponds to EP automata states.
The difference between the two learning meth- ods can be even more clearly observed in the following experiment. We separated the features of each model, trained with CL and joint train- ing, based on the two consecutive digits in Fig. 6 These consecutive two digits are not necessary for learning PC or EP but represent easy-to-learn patterns that the model can easily grasp. In the
(a) CL
(b) Joint training
case of joint training, this pattern is learned, and the feature is well separated, while in the case of
Figure 6: Clustering on two consecutive digits
CL, this information not Iearned. These observations suggest that when learning tasks sequen- tially through CLeAR, previously learned tasks can act as regularizer, reducing the acquisition of unnecessary information for the task.
Conclusion
Our study elucidates the distinct features of CL-AR as compared to conventional image- CL and highlights the limitations of traditional CL approaches. Additionally, introduce CLeAR. novel methodology for the continual learning of abstract logical concepts. Experiments on 15 tasks with varying difficulty validate the efficacy of CLeAR. It achieves near-zero forgetting and often improves accuracy on previous tasks during subsequent training. There are major challenges specific to CL-AR tasks: the decorrelation between input data and tasks, dynamic dimensions of datasets, and the goal of generalization for OOD data. CLeAR tackles these challenges by employing a ame-to-many mapping strategy that aligns tasks of different dimensions and shares mapping space. This prevents forgetting previous tasks and enhances overall performance. Our research contributes to the development of lifelong learning abilities, resembling human cognitive processes. By overcoming the limitations of existing CL approaches and focusing on abstract concepts. CLeAR opens new possibilities for continual learning. The limitation of our approach is that the mapping strategy used in our method involves discretized mapping, making it challenging to train the accompanying model end-to-end.
Acknowledgement
This work was supported by Electronics and Telecommunications Research Institute (ETRI) grant funded by the Korean government. [23ZSI 100. Core Technology Research for Self-Improving Integrated Artificial Intelligence System], Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) [2021-0-01 343: Arti- ficial Intelligence Graduate School Program (Seoul National Univ.) and 2021-0-020 -021-000206:: Artificial Intelligence Innovation Hub]. National Research Foundation of Korea (NRF) grant funded by MSIT (2022R1 A3B 1077720 and 2022R AARRRIAAA700 A5A7088908 1) and the BK21 FOUR program of the Education and Research Program for Future ICT Pioneers, Seoul National Univ. in 2023.
10

---

References
[1] Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Marcus Rohrbach, and Tinne Tuyte- laars. Memory aware synapses: Learning what (not) to forget. In ECCV, pages 139-154, 2018.
[2] Michael A Arbib. Brains, machines, and mathematics. Springer Science & Business Media, 2012.
[3] Mikael Bodén and Janet Wiles. On learning context-free and context-sensitive languages. IEEE Trans. Neural Networks, 2002.
[4] Arslan Chaudhry, Marc' Aurelio Ranzato, Marcus Rohrbach, and Mohamed Elhoseiny, Efficient lifelong learning with a-gem. In International Conference on Learning Representations, 2018.
[5] Arslan Chaudhry, Marcus Rohrbach, Mohamed Elhoseiny, Thalaiyasingam Ajanthan, Puneet Dokania, Philip HS Torr, and Marc' Aurelio Ranzato. On tiny episodic memories in continual learning. arXiv preprint arXiv: / 091...92...88. 2019.
[6] Zhiyuan Chen and Bing Liu. Lifelong machine learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 12(3):1-207, 2018.
[7] Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder- decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing. 2014.
[8] Noam Chomsky. Three models for the description of language. IRE Trans. Inf. Theory, 1956.
[9] Noam Chomsky, Syntactic structures. Mouton de Gruyter, 2002.
[10] Matthias De Lange, Rahaf Aljundi, Mare Masana, Sarah Parisot, Xu Jia, Aleš Leonardis, Gregory Slabaugh, and Tinne Tuytelaars. continual learning survey: Defying forgetting in classification tasks. IEEE transactions pattern analysis and machine intelligence, 44(7):3366 3385, 2021.
[11] Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A Ortega. Neural networks and the chomsky hierarchy. The Eleventh International Conference on Learning Representations, 2023.
[12] Jeffrey L. Elman. Finding structure in time. Cogn. Sci., 1990.
[13] Alexander L Gaunt, Mare Brockschmidt, Nate Kushman, and Daniel Tarlow. Differentiable programs with neural libraries. In International Conference on Machine Learning, pages
1213 2212-122.. PMLR, 2017.
[14] Faustino J. Gomez, Jürgen Schmidhuber, and Risto Miikkulainen. Accelerated neural evolution through cooperatively coevolved synapses, J. Mach. Learn. Res., 2008.
[15] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 1997.
[16] Mingcheng Hou and Issei Sato. A closer look at prototype classifier for few-shot image classification. arXiv preprint arXiv:2110.05076, 2021.
[17] Armand Joulin and Tomás Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. In Advances in Neural Information Processing Systems 28, 2015.
[18] Gyuhak Kim, Changnan Xiao, Tatsuya Konishi, Zixuan Ke, and Bing Liu. A theoretical study on solving continual learning. arXiv preprint arXiv:2211.02633 2022.
[19] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Bariikka,, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 1 114(13):3511-3222 2017.
11

---

[20] Karl Josef Klauer and Gary D Phye. Inductive reasoning: A training approach. Review of educational research, 78(1):85-122 123, 2008.
[21] Sang-Woo Lee, Jwa Kim, Jaehyun Jun, Jung-Woo Ha, and Byoung-Taa Tak Zhang. Overcoming catastrophic forgetting by incremental moment matching. Advances in neural information processing systems, 30, 2017.
[22] Zhizhong Li and Derek Hoiem. Learning without forgetting. JEEE transactions on pattern analysis and machine intelligence, 40(12):2935-2947, 2017.
[23] Perey Liang, Michael I. Jordan, and Dan Klein. Learning dependency- compositional semantics. Comput. Linguistics, 2013.
[24] Sen Lin, Li Yang, Deliang Fan, and Junshan Zhang. Beyond not-forgetting: Continual learning with backward knowledge transfer. arXiv preprint arXiv:22/1.0000 1,00899, 2022.
[25] Sen Lin, Li Yang, Deliang Fan, and Jumshan Zhang. Trgp: Trust region gradient projection for continual learning. arXiv preprint htt::2202.0293111 2022.
[26] Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shorteuts to automata. arXiv preprint urXiv:2210.107499 2022.
[27] David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in neural information processing systems, 30, 2017.
[28] Arun Mallya and Svetlana Lazebnik. Packnet: Adding multiple tasks to single network by iterative pruning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 7765-7773, 2018.
(29] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. Advances in neural informa- fion processing systems, 31, 2018
[30] Michael McCloskey and Neal J Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pages 109-165. Elsevier, 1989.
[31] William Merrill, Ashish Sabharwal, and Noah A Smith. Saturated transformers are constant- depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843- 856, 2022.
[32] William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. formal hierarchy of RNN architectures. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020.
[33] John P Miller, Rohan Taori, Aditi Raghunathan, Shiori Sagawa, Pang Wei Koh, Vaishaal Shankar, Percy Liang, Yair Carmon, and Ludwig Schmidt. Accuracy on the line: on the strong correlation between out-of-distribution and in-distribution generalization. In International Conference on Machine Learning, pages 7721-7735. PMLR, 2021.
[34] Peter Nordin. Evolutionary program induction of binary machine code and its applications. PhD thesis, Dortmund University of Technology, 1997.
[35] German I Parisi, Ronald Kemker, Jose L Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: A review. Neural networks, 113:54-71, 2019.
[36] Michael Pazzani and Dennis Kibler. The utility of knowledge in inductive learning. Machine learning, 9:57-94, 1992.
[37] Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 2001-2010, 2017.
[38] Elaine Rich. Automata, Computability and Complexity. Prentice-Han Hall, 2007.
12

---

[39] Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins. Hubert Soyer. James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks, arXiv preprini arXiv: 04660660447,, 2016.
[40] Joan Serra, Didac Suris, Marius Miron, and Alexandros Karatzoglou. Overcoming catastrophic forgetting with hard attention to the task. International Conference on Machine Learning, pages 4548 4555. PMLR, 2018.
[41] Michael Sipser. Introduction the theory of computation. PWS Publishing Company, 1997.
[42] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Advances in neural information processing systems, 30, 2017.
[43] Mirac Suzgun, Sebastian Gehrmann, Yonatan Belinkov, and Stuart M. Shieber. Memory- augmented recurrent neural networks can learn generalized dyck languages. CoRR, 2019.
[44] Lazar Valkov, Dipak Chaudhari, Akash Srivastava, Charles Sutton, and Swarat Chaudhuri. Houdini: Lifelong learning program synthesis. Advances in neural information processing systems, 31, 2018.
[45] Vladimir Vapnik. Statistical learning theory. Wiley, 1998.
[46] Liyuan Wang, Mingtian Zhang, Zhongfan Jia, Qian Li, Chenglong Bao, Kaisheng Ma, Jun Zhu, and Yi Zhong, Afec: Active forgetting of negative transfer in continual learning, Advances in Neural Information Processing Systems, 34:22379-2239) 2021.
[47] Zhen Wang, Liu Liu, Yiqun Duan, Yajing Kong, and Dacheng Tao. Continual learning with lifelong vision transformer. In CVPR, pages 171-181, 2022.
[48] Junting Zhang, Jie Zhang, Shalini Ghosh, Dawei Li, Serafettin Tasci, Larry Heck, Heming Zhang, and C-C Jay Kuo. Class caasemineremnntal learning via deep model consolidation. In WACV, pages 1131-1140, 2020.
13


Reviews:
[{"review_id": "LkjEC5HcIu", "reviewer": "Reviewer_FdFh", "summary": "The paper looks at the continual learning (CL) setting involving tasks which require more abstract reasoning (reusable across input domains), s.a. addition and multiplication. The authors imagine that the inputs of all encountered tasks can be mapped into a common space, which, in turn, can be similarly transformed across tasks, in order to achieve transfer on a higher level. To take advantage of this fact, the inputs are processed by three NNs: 1) task-specific m_t which maps the inputs to a common space; 2) f which processes the resulting latent embeddings; 3) h_t which is a task-specific single-layer projection head. m_t is trained using an additional decoder. f and h_t are trained using a similar approach to Learning without Forgetting (LwF). The paper introduces a new set of tasks for evaluating abstract reasoning in a CL setting. The results demonstrate that this approach is capable of backward transfer on the created tasks.", "questions": "What do you think would happen if two tasks have partially overlapping input alphabets, e.g. (task1: 1 2 3 4 , task2:  3 4 5)? Would this idea of mapping both input distributions to the same space be problematic?\n\nWhat would you say is learned in f_theta across disparate tasks, which allows for transfer between them?\n", "limitations": "The fixed-size model limits the effective number of tasks which can be solved.\n\nIt appears that the approach relies on some level of similarity between tasks, as it uses the new inputs to create pseudo-labels.\n", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper looks towards an interesting direction in CL. I found the discussion on the challenges around using most CL methods for abstract reasoning (AR) to be interesting.\n\nThe paper introduces a novel set of logical reasoning tasks which are categorised according to a class in the Chomsky hierarchy.\n\nThe experiments demonstrate the method’s capability of achieving backward transfer.\n\nThe use of the auto-encoder objective to learn a common mapping between tasks appears novel.\n", "weaknesses": "The method claims to introduce the first CL scenario for abstract reasoning, but simpler AR tasks have been explored in NeuralTerpret, HOUDINI, DeepProbLog.\n\nThe description of the algorithm seems rushed. The approach is presented but not well motivated, e.g. the properties of the mapping m_t on lines 218-222. The continual learning approach’s novelty seems limited, being mainly modelled after LwF.\n\nMy impression is that the method is not evaluated on a difficult enough setting in order to determine whether it is promising. Each input consists of one-hot encodings (as opposed to images) which I imagine are easier to learn how to map to a common space.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*We thank you for the insightful comments and suggestions. We have addressed each of your questions below.*\n## Weaknesses\n**W1**\nThank you for introducing us to these inspiring works. We will add this research to the related work section (we reported a summary in global comment). While all of these studies are remarkable, we think there are significant differences between their works and our work in terms of scenarios and methods.\n\nFirst, our work does not rely on any human (prior) knowledge about the tasks in its model construction. The model purely performs \"Learning from data\" without knowing incoming logical tasks. In contrast, their works require pre-configured programs that handle logic with human knowledge of future tasks. This contradicts the assumption of CL, as it is impossible to anticipate and program for all potential problems that may arise.\n\nSecond, our paper performs logical operations using a pure neural network. While their works do utilize neural network structures internally, they mainly use them as feature extractors, such as extracting features from MNIST digits. Also for the lifelong learning scenarios they presented (e.g., Summing two images to perform arithmetic operations on multiple images), the neural network acts as a feature extractor, while pre-defined programs perform the actual logicals.\n\nThird, while our methodology allows CL, their works lack scalability to multiple tasks. They either modularize programs for each task or create parameterized programs from the beginning to accommodate multiple tasks.\n* * *\n**W2**\nWe apologize for the unclear explanation of algorithm. In the final version, we will revise the description of our CLeAR methodology, motivated by the unique characteristics of AR tasks.\n\nCLeAR is a specialized model for AR tasks, serving a distinct purpose from LwF. Unlike images, where input distributions share common attributes like color, texture, and patterns, AR tasks present highly distinct input distributions unique to each task. Given the considerable dissimilarity between tasks and their varying dimensions, we introduce a novel approach CLeAR to effectively adapt to these environments.\n\nThe mapping function, first part of CLeAR, is designed to explicitly align different task inputs. We propose a novel approach that can align distributions without prior knowledge of each task adopting Auto-Encoder architecture.\nOtherwise, LwF assumes image distributions are similar across tasks. While this imperfect assumption leads to outdated performance in the image domain, it fortunately benefited by our mapping function. However, due to the regularization term in LwF that accounts for image distribution shift, LwF does not fully utilize the aligned mapping, resulting in lower performance for ten complex tasks (W3). On the other hand, our CLeAR consistently exhibits high performance for AR tasks, thanks to its AR specialized label sharpening term.\n* * *\n**W3** We conducted additional experiments on more complex sequential tasks involving 10 different AR tasks (EP-CN-PC-CO-RS-SM-IP-OF-BS-DS: reported average).\n1. Increasing hierarchy\n> CLeAR final 60.22%, BWT -7.55%  \nLwF (our mapping) final 59.42%, BWT -12.07%  \n2. Decreasing hierarchy\n> CLeAR final 63.32%, BWT -2.90%  \nLwF (our mapping) final 63.05%, BWT -8.49% \n \nOur model demonstrated favorable performance and less forgetting in these difficult scenarios.  \nAccording to recent research (main[11]), even for tasks that may seem very simple to humans, like the parity-check task (whether the sum of binary is even or odd), transformer models completely fail to learn the algorithm. Therefore, We find it difficult to consider our task as a very easy task from the model's perspective.\n## Questions \n**Q1** Thank you for suggesting good experiments. We conducted experiments on tasks that have semantically identical partially overlapping input alphabets.\n\nMA (modular arithmetic) task with fixed modulus 8, and for each task, input digit is (0,1,2,3), (2,3,4), (3,4,5), (4,5,6,7), (1,3,5,7), and (2,4,6,8) sequentially (reported average).\n> CLeAR final 66.17%, BWT 0.62%  \nLwF (our mapping) final 60.98%, BWT -3.68%\n\nBS (bucket sort) task, same set of numbers sequentially included in the input.\n> CLeAR final 45.03%, BWT -1.85%  \nLwF (our mapping) final 45.95%, BWT -0.55%\n\nCLeAR demonstrates favorable performance on MA-partial overlap achieving best Acc 99.81% with LSTM; however for BS-partial overlap, there are plenty of rooms to be improved.\n***\n**Q2** To address your comment, we performed additional experiments. We observed and analyzed, for the first time, how a model learns certain AR tasks internally during a CL process and coordinates knowledge. Additionally, through this rebuttal, we made a notable observation that CL on AR can often outperform joint training. Based on these, we proposed hypotheses to explain this phenomenon. Please refer to Fig.R1 and R2 in the attached PDF file and iPYe Q1 for details.\n## Limitations\n**L1** Your observation is valid, and indeed, increasing the model's capacity is a viable approach in the field of CL. There are foundational models like Progressive Neural Networks (2016) and Dynamically Expandable Networks (ICLR 2018). However, recent CL research has primarily been oriented toward using a fixed-sized neural network that is more challenging and resembles human learning processes.\n***\n**L2** We agree with your insight. In fact, methodologies in CL aim to identify similarities between tasks and leverage them to facilitate the learning of subsequent tasks. Traditional CL on images has shown high similarity because all tasks involved recognizing general features like colors or stripes, which require similar kernels.\nHowever, in CL-AR, the distributions between such tasks vary significantly, making it challenging for the model to capture similarity as mentioned in W2.\n\n*Due to text limit, we'll promptly provide the full table in W3, Q1 during the interactive review on request.*"}, {"review_id": "NkTRJPUe2T", "reviewer": "Reviewer_iTug", "summary": "In this paper, the authors introduce CLeAR, a new method of Continual Learning (CL) for Algorithmic Reasoning (AR). In doing so, several relaxations to standard CL are discussed: (1) scenarios where the same data are used for different tasks, (2) the variation of the input, being not of fixed size, and (3) analysis of performances on OOD data. The main algorithm proposed, namely CLeAR, combines a map to a shared feature space with a RCNN or a LSTM where learning happens, and uses an additional MLP to project in the output space. The CL strategy for catastrophic forgetting builds on LwF. \n\nTo evaluate the proposed model, the authors propose 15 benchmarks of increasing difficulty, based on the use of different Chomsky hierarchies. The experiments are conducted for the method and several baselines, some of which include known CL strategies. Overall the results show that CLeAR addresses the CL in AR, providing also positive Backward transfer.", "questions": "Can you provide more details about why LwF is performing very well in CL-AR? Is it because of the pseudo-labels in the initial training phase?", "limitations": "**Major** The related work connected to AR is poorly discussed and only one recent work is mentioned in the related work. This gives somehow the feeling that research in AR is niche. To this end, more works should be cited or, otherwise, the motivation for CL in AR should be strengthened. \n\n**Minor** Details on the benchmarks are not entirely clear, making a bit fuzzy the decision behind their design. Such explanation can be improved even in the Supplementary to make understand how different tasks combine in increasing level of difficulty", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors address for the first time the CL adaptation of AR. The setup proposed differentiates from standard CL, where input data dimensions are fixed, and evaluation is typically done in an IID test-set w.r.t. to the joint task distribution. This leads to a more general setting w.r.t. standard CL which can improve current research and lead to new methodologies. \n\nThe proposed method well adapts to variegated AR tasks, being designed to use a shared feature space where learning takes place. The experiments show that this choice has the desired effects, addressing catastrophic forgetting in several scenarios. In addition, the newly designed benchmarks (to be released on github) offer space for further research in this new field. \n\nThe presentation is overall clear, with much focus on benchmarking the method in several experiments.", "weaknesses": "It seems some information is missing in the current text, and the experimental evaluation can be improved. Referring to Table 3, the discussion in Section 4.2 only mentions the first 4 rows, but nothing is mentioned about the last three. How should those results be interpreted and what do they convey? It seems that the method is not solving the task, accordingly to the authors' claim that the threshold should be above 90% of the task's accuracy.\n\nAs a suggestion, the comparison with existing CL strategies is very important and should appear or at least be discussed in the main text.\n\nAll experiments are conducted in a single run, contrary to common practice, especially in CL. This may lead to a confirmation bias over the proposed method and should be clarified at least here why the choice of single runs does convey all relevant information. Based on the experiments in Appendix D, I'm not entirely sure that LwF combined with the shared feature mapping would drastically differentiate from CLeAR (Tables 4 and 5), since it is showing very similar classification scores. To this end, I sense that adopting LwF is particularly suited for the task the authors are proposing since it is likely adapting previous tasks to new observed sequences.  \n\n**Typo** In the bibliography refs [33] and [34] coincide.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*We thank you for the insightful comments and suggestions. We have addressed each of your questions below.*\n***\n## Weaknesses\n\n**W1** Thank you for your sharp comments. And we apologize for the insufficient explanations in certain parts. As you pointed out, we will make sure to incorporate the mentioned content into the final version of the paper.\n\nThe accuracy exceeding 90% in the single training (Table 1) indicates that the model has learned the algorithm perfectly. In this case, the model possesses accurate information about the algorithm, making it easier to transfer this knowledge to the next task. However, to create an excellent CL methodology, we believe it is important to preserve and transfer even partial information (CL Initial under 90%) about the task, even if it is not complete. Therefore, rows 5, 6, and 7 in Table 3 serve as positive indicators that the model can preserve even incomplete information for challenging tasks with a high Chomsky hierarchy. Firstly, the CL final score for difficult tasks did not significantly decrease compared to the CL Initial score, and we observed numerous cases where performance on past tasks actually increased through BWT. Secondly, our model demonstrated higher performance compared to the baseline of existing CL methodologies.\n\nFrom these points, we can conclude that our model remains valid even for tasks with a high hierarchy where there are limitations in learning just a single task.\n\nFurthermore, to enhance our experimental evaluation, we have paid attention to the phenomenon related to Joint training shown in the results table. These inspection of our result is in **Experiment 2** of the global comment and **Fig.R1** and **R2** of the **PDF**.\n***\n**W2** We agree with the comment. In the final version, we will include the accuracy of conventional CL that was compared in the supplementary section in the main paper.\n***\n**W3** Following your comment, we conducted three repeated experiments for all settings by adding two additional seeds. \n|% std|RNN|Stack-RNN|Tape-RNN|LSTM|\n|---|---|---|---|---|\n|Joint|1.14|5.01|6.77|1.76|\n|Initia|1.55|1.41| 3.91|1.41|\n|Final|1.40|2.25|5.01|2.25|\n* Standard deviation from three separate runs of high-correlation CL-AR scenario (Table 3 main)\n\nWith the exception of Tape-RNN, which is largely contingent on the initialization, minimal variance was observed, confirming the consistency of the content of this paper. In the final version table, we promise to include the results and variances from the repeated experiments. \n***\n## Questions\nQ1. CLeAR is a specialized model for AR tasks, serving a distinct purpose from LwF. Unlike images, where input distributions share common attributes like color, texture, and patterns, AR tasks present highly distinct input distributions unique to each task. Given the considerable dissimilarity between tasks and their varying dimensions, we introduce a novel approach called CLeAR to effectively adapt to these unique scenarios.\n\nThe mapping function, first part of CLeAR, is designed to explicitly align different task inputs. We propose a novel approach to create mapping that can align distributions without prior knowledge of each task adopting Auto-Encoder architecture. This resulted in highly aligned distribution of all tasks (Fig.4-b in main). \n\nOtherwise, LwF assumes image distributions are similar across tasks. While this imperfect assumption leads to outdated performance in the image domain, it fortunately benefited by our mapping function. However, due to the regularization term in LwF that accounts for image distribution shift, LwF does not fully utilize the highly aligned mapping space, resulting in notably lower performance for ten complex tasks (Supp. table 5). On the other hand, our CLeAR consistently exhibits high performance for AR tasks, thanks to its AR specialized label sharpening term.\n\nTable 5 in appendix D shows that CLeAR is more capable of preserving information for long sequential CL. Especially for RNN. Additionally, we demonstrated that our CLeAR methodology surpasses not only LwF but also LwF w/ our mapping. \n\n||CLeAR|||LwF (our mapping)|\n|---|---|---|---|---|\n|High-correlation|final(%)|forgetting(%)|final(%)|forgetting(%)|\n|MA| 60.09% |3.07| 55.37%|43.64%|\n|CN| 87.23% |0.46%| 82.95%|11.20%|\n|RS | 46.29% |1.52%| 50.30% |2.72%|\n|BS| 79.17% |2.73%| 75.31% |4.41%|\n* MA: modulus from 2 to 8\n* CN: cycle length from 2 to 8\n* RS: string alphabet count from 2 to 8\n* BS: string alphabet count from 2 to 8\n\n\n||CLeAR|||LwF(our mapping)|\n|---|---|---|---|---|\n| Inter-hierarchy|final(%)|forgetting(%)|final(%)|forgetting(%)|\n|Ascending|60.22|7.55|59.42|12.07|\n|Descending|63.32|2.90|63.05|8.49|\n\n* 10 tasks of EP-CN-PC-CO-RS-SM-IP-OF-BS-DS. Ascending and descending order of hierarchy\n\nExperiments showed that the CLeAR is capable of long and challenging scenario and outperforms LwF (+our mapping)\n***\n## Limitations\n**L1** Thank you for the valuable feedback. We will cite two categories of AR-related papers and add relevant content to the related work section. We include papers such as DeepProbLog (2018), HOUDINI (2018), NeuralTerpret (2017), which tackle AR tasks using logic solvers, as well as Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With an External Differentiable Stack (2021 PMLR) and Learning Hierarchical Structures with Differentiable Nondeterministic Stacks (2022 ICLR), which attempted AR solutions using neural networks. Additionally, we will add ref [24] of the main paper to the related work section.\n***\n**L2** We apologize for the inadequate explanation of the details of the benchmarks. In the final version, we will strengthen the explanation in the supplementary section and promise to publicly provide a comprehensive disclosure of the complete code we used and the precise experimental setups for each task.\n***\n*p.s. Due to space constraints, we'll promptly provide the full table for W3, Q1 during the interactive review on request*\n"}, {"review_id": "rNJ2EohDro", "reviewer": "Reviewer_iPYe", "summary": "The authors propose a training framework for continual learning in which task inputs are mapped to regions of or distributions over an embedding space, before the resulting embedding is passed to a single model that learns continually to solve the tasks.  They apply this continual learning framework to tasks based on learning algorithms, testing against input-output pairs from outside the training distribution. The resulting training and task framework can solve a number of algorithmic reasoning tasks, up to the limitations imposed by model architectures.", "questions": "Where do the authors think some form of hierarchical representation or compression of previous \"knowledge\" is happening to enable continual learning?\n\nThe authors have submitted supplementary material on exactly this question.", "limitations": "The authors duly discuss the chief limitation of their approach being a discretization in the embedding space.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is one of the first I've seen to tackle algorithmic reasoning/algorithm induction tasks along with continual learning. The core idea of mapping tasks and inputs to an embedding space from which a unified model learns continually to solve tasks (via a task-specific output head) is, to my knowledge, highly novel. The paper is duly careful about which levels of the Chomsky hierarchy it considers as algorithms for purposes of defining the algorithmic reasoning task.", "weaknesses": "The paper needs to more clearly present its comparisons between a baseline and a contribution.  I understand that the authors do not claim every task on which they evaluated to be \"solved\", especially since many of them require positional encodings and a context-free or context-sensitive memory.  However, since the message is more complicated, the authors could do a better job presenting exactly where their training framework and meta-model architecture makes a difference against, for instance, just training the baseline neural network architectures with no continual learning, or training them and then retraining with a baseline level of catastrophic forgetting.\n\nThe authors have since conducted a number of additional experiments to address this weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*We thank you for the positive comments and suggestions. We have addressed each of your questions below.*\n***\n## Weakness\n**W1** Thank you for the insightful comments. We apologize for the insufficient explanation of the experimental results. As you suggested, we will address these points in the final version of the paper.\n\n**Explanation**  \nIn single task training (Table 1 main), an accuracy exceeding 90% was considered that the model learned the AR. In such cases, the model possesses accurate algorithmic information, making it easier to transfer this knowledge to subsequent tasks. However, many models and tasks exhibit low accuracy in single task training. To make CLeAR an effective CL methodology, we believe it is crucial to preserve even partial information (ACC < 90%) when the model is not able to learn the algorithm perfectly and transfer it successfully. Therefore, we conducted experiments even for challenging tasks with low single-training performance. Performance of CLeAR is evaluated through CL Initial, CL Final, and BWT values. The average of single task training results for each task and the joint training performance, which is generally considered an upper bound in typical CL scenarios, provide insights into the difficulty of tasks, rather than just CLeAR's performance.\n\nAcross our experiments, CLeAR demonstrated the ability to preserve even incomplete information (CL Initial < 90%) for challenging tasks with a high Chomsky hierarchy. First, for difficult tasks, the CL Final score did not significantly decrease compared to the initial CL Initial score, and in many cases, performance even increased through BWT. Second, CLeAR outperformed the baseline of existing CL methodologies (supple. D).\n\nFrom these observations, we can conclude that our CLeAR methodology is valid not only for learning individual tasks but also for difficult tasks with a high Chomsky hierarchy.\n***\n## Questions:\n**Q1** We sincerely appreciate your crucial question. Thanks to your comment, we devise new analytical methods to address a crucial yet challenging aspect of CL: how the model preserves and integrates information from previous tasks while incorporating new knowledge. \nIn addition, we found interesting results with your comment (W1). Unlike typical CL scenarios where joint training is an upper bound, our experiments often showed lower results compared to CL. Analyzing the model's internal learning process in joint training, we found that while CLeAR acts as a regularizer, integrating information between tasks, joint training in CL-AR fails to find common information. \nThese new analyses advance the paper a step further and highlight the significance of CL in AR tasks, similar to human learning logic in real-world situations.\n\n**Experiments (Fig.R1 and Fig.R2 in PDF)**  \nWe conducted experiments with two simple regular tasks, Parity-check (PC: whether the sum of input is even or odd) and Even-pairs (EP: whether the count of two consecutive digit pairs, 01 and 10, is the same), both with binary inputs, using a fixed seed and an RNN model. In both CL and joint training, 100% IID and OOD accuracy was achieved.\n\nFrom the perspective of formal language theory, learning each task requires acquiring the automata structure (Fig.R1 D) internally. Fig.R1 A, B, C, E represent the model's hidden feature space colored corresponding to PC (up) and EP (down) automata states for the input sequence. Fig.R1 A shows that after learning PC, the model has fully acquired the corresponding automata (up), while for the unlearned EP, the points remain undivided (down). Fig.R1 B demonstrates that after learning EP via CLeAR, the model maintains information from PC (upper) while learning EP (lower), with minimal change in feature space. The first task acts as a regularizer, preventing inefficiency and maintaining a minimal joint automata state for both tasks.\n\nFig.R1 C illustrates joint training, where the feature space of the model is separated for the corresponding automata state (up), leading to the use of less effective feature space. Opposed to CL, it failed to learn commonality. This characteristic is more distinct in Fig.R1 E. This is an easy-to-learn feature for the model but doesn't contribute to problem-solving, making it unnecessary to learn. Fig.R1 E shows that while joint training leads to unnecessary clusters, CL avoids learning redundant features. These observations suggest that CLeAR acts as a regularizer in CL-AR, reducing the ineffective use of feature space and integrating information between tasks by combining corresponding automata states.\n\nFor more complex context-free (Stack manipulation: SM) and context-sensitive (Bucket sort: BS) tasks, Stack-RNN was used (Fig.R2). In the case of SM, for learning to occur, the model must necessarily internalize the usage of a memory stack. CL exhibited superior results compared to joint training for both SM and BS in IID and OOD test sets. To verify whether the model has indeed learned true algorithms in each case, Fig.R2 B shows the memory stack actions based on the input alphabet. In CL (left), it is evident that the model has accurately learned the stack usage. Furthermore, during the learning process of BS, it retains this knowledge and even gets closer to appropriate actions, resulting in backward transfer. Fig.R2 C displays stack changes based on the sequence in both CL and joint training, revealing more appropriate learning in CL, while what joint training learned is a shortcut for IID, not the actual algorithm.\n\nThrough these experiments, CL-AR was shown to integrate task-related information by learning automata internally and positioning similar-role states closely in the feature space. Additionally, CL could be more preserving and robust against shortcut learning compared to joint training. This work showcased the strength of CL methodology in learning logics  and proposed a novel approach for analyzing internal learning processes from a CL perspective."}, {"review_id": "a0VhDdfwER", "reviewer": "Reviewer_GYfA", "summary": "This paper introduces CLeAR, a novel algorithmic reasoning (AR) methodology for continual learning (CL) of abstract logical concepts. The main component of CLeAR is a one-to-many mapping strategy that aligns various tasks of different dimensions in a shared mapping space, allowing for the gradual learning of abstract concepts. The paper addresses the challenges specific to CL for AR tasks, such as decorrelated input data, dynamic dimensions of datasets, and the goal of generalization for out-of-distribution data. Extensive experiments are conducted, demonstrating that CLeAR achieves near-zero forgetting and improved accuracy during subsequent training, outperforming existing CL methods designed for image classification. The paper highlights the importance of studying CL in the context of abstract logical concepts and offers valuable insights into human learning mechanisms.", "questions": "- Could the authors provide further insights on why end-to-end approaches are necessary or beneficial in comparison to symbolic reasoning with pre-defined rules and structures? \n- Have the authors considered including other CL methods or foundation models in the evaluation? I guess most of the tasks listed in the paper can be solved by models like gpt4. So why learning Algorithmic Reasoning important?", "limitations": "See weaknesses and questions.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a novel methodology, CLeAR, for continual learning of abstract logical concepts. It addresses the lack of research in this area and presents a unique approach to aligning tasks of different dimensions and sharing semantics. By focusing on abstract algorithmic reasoning tasks, the paper bridges the gap between CL and real-world cognitive skills development. The proposed one-to-many mapping strategy addresses the challenges unique to abstract concept learning and offers a solution for preventing forgetting and improving accuracy during subsequent training.", "weaknesses": "From my point of view, I'm not sure why end-to-end algorithmic reasoning is important when this problem can easily be solved via symbolic reasoning with pre-defined rules and structures. Also, I think the paper should include some other baseline experiments, like standard CL methods, for comparison. Foundation models can also be considered if possible. This would provide a better understanding of the performance improvement achieved by CLeAR and allow for a more comprehensive assessment of its effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*We thank you for the positive comments and suggestions. We have addressed each of your questions below.*\n***\n## Weaknesses\n**W1** (Aligned with Question 1)  We appreciate your insightful comment. Frameworks such as **DeepProbLog (2018), HOUDINI (2018), NeuralTerpret (2017)**, and others have been developed using symbolic reasoning with predefined rules and structures to solve AR. We intend to explain the significance of our end-to-end algorithmic reasoning by focusing on the differences between our work and these frameworks.\n\nFirstly, our model does not rely on any human (prior) knowledge about the tasks that the model will learn. The model purely performs \"Learning from data\" without knowing what logical tasks it is dealing with. In contrast, the aforementioned frameworks require pre-configured programs that handle logic using human knowledge of each task. This contradicts the assumption of continual learning, as it is impossible to anticipate and program for all potential problems that may arise in the real world.\n\nSecondly, our paper performs logical operations using a pure neural network. While the aforementioned frameworks do utilize neural network structures internally, they mainly use them as feature extractors, such as extracting features from MNIST digits or recognizing arrow directions. Even in lifelong learning scenarios presented in those frameworks (e.g., tasks like summing two images to performing arithmetic operations on multiple images), the neural network acts as a feature extractor, while pre-defined programs perform the actual logical operations.\n\nLastly, the mapping methodology proposed in our paper allows for continual learning of multiple tasks with different dimensions, relying solely on data without any prior knowledge about the tasks. While the aforementioned papers also introduce sequential learning scenarios, they lack scalability as they either rearrange modularized programs for each task or create predefined parameterized programs using knowledge of all the future tasks from the beginning.\n\nOur research proposes a method where the model can learn any task without the need for human intervention to change the model's structure for each task. This is similar to how a person who has learned arithmetic can smoothly integrate previous knowledge when learning linear algebra without rewiring the brain, approaching the key goal of CL, which is to learn consecutive tasks like a human.\n***\n**W2** We completely agree with what you said. The comparison results with the three baseline methods are currently only presented in the supplementary section D. As a result, we observed that CLeAR outperforms all other CL methods in terms of final CL accuracy and knowledge backward transfer. In the final version of the paper, we will mention the comparison results of the three baseline CL methodologies, **EWC (Table 3 supple.), LwF (Table 4,5 supple.), and ER (Table 6 supple.)**, in the main paper.\n***\n**W3** We appreciate your inspiring comment. Recently in the field of CL, there is a growing trend of using foundation models like LLM (large language model). Based on your comment, first of all, to obtain a deeper understanding of our model's functioning, we conducted a more comprehensive assessment using the new analytical methods that we propose. Through this, we have discovered that our CLeAR learns reasoning by internally simulating automata and is capable of integrating automata states for new tasks. Additionally, we have analyzed that it can exhibit higher learning capability than what is typically considered an upper bound in joint training in the context of Continual Learning (Global Comment Experiments 2). In future work, as LLM has demonstrated high performance across various domains, applying a foundation model to CL-AR tasks would be a novel research direction. In future work, we will attempt CL-AR task learning and evaluation using the LLM approach, utilizing resources like the gpt4 API or Alpaca (2023).\n***\n## Questions\n**Q1** Explained in W1\n***\n**Q2-1** As mentioned in W2, we compared the performance of three baseline CL methods using three different mapping methods and provided the results in the Supplementary Material.\n***\n**Q2-2**  In addition to its pure academic value in studying the process of logic learning in models, AR also holds significance in relation to LLM for the following reasons.\n\nAccording to recent research on Transformer architecture and algorithmic reasoning (ref[11,24] in main and \"Simplicity Bias in Transformers and Their Ability to Learn Sparse Boolean Functions\" (2022)), Transformers often struggle with generalization to out-of-distribution (OOD) data of varying lengths due to their tendency to learn shortcuts in AR tasks.\n\nFor instance, regardless of the number of model heads, hidden dimensions, or training epochs, and the type of positional embedding, transformers fail to learn algorithms of very simple (for human) tasks like Parity check (PC: whether the sum of a binary sequence is even or odd). Despite showing 100% accuracy on test sets of the same length as the training data, the model's accuracy drops to a random chance of 50% for longer OOD sequences. This is attributed to the Transformer architecture's focus on memorizing input data distribution rather than learning rules, leading to shortcut learning. From this perspective, LLMs with Transformer architecture could also encounter similar challenges. In a broader scope, we think that a methodology of continually training our AR task could potentially offer new insights to enhance the model architecture of LLM like OpenAI's recent attempts of step-by-step learning through process supervision.\nUltimately, we expect that through the challenging CL-AR learning scenario that current neural networks struggle with, we may gain insights into how humans learn and integrate knowledge in the brain.\n"}, {"review_id": "eS5kui1KHJ", "reviewer": "Reviewer_aCtv", "summary": "This work tackles the problem of continual learning for rule-based tasks. The method first maps algorithmic inputs to a discrete latent space. This mapping is one-to-many, which allows the method to learn multiple features for the inputs of each task. A model then consumes results from this discrete latent space to perform the task. The authors test and verify the method works on various algorithmic tasks drawn from the Chomsky hierarchy.", "questions": "Major questions:\n- Line 229: How do you control the size of the mapping set?\n- How much of the performance is explained by learning regular languages well and nothing else? For example, in the context-free tasks, are the models just solving the subset of examples that can be modeled via a regular language? \n- Is the CL setting better than the pretrain-finetune or meta-learning settings, where we might pretrain/meta-train over multiple tasks and then adapt to one task?\n\nMinor\n- Line 24: The decline is not necessarily rapid. See [this](https://arxiv.org/abs/1910.08475) [this](https://arxiv.org/abs/2102.07686) for more recent citations to catastrophic forgetting.\n- Line 113: “the model performing backward transfer is still limited.” What does this mean?\n- Line 126: Missing citations to [this](https://arxiv.org/abs/2106.16213) [this](https://aclanthology.org/2020.acl-main.43/) and related works on the languages that can be recognized by transformers and RNNs. These works essentially define the upper bounds to your empirical work.\n- Table 3: What is the logic behind the bold numbers here?\n\nNits:\n- Line 16: typo “during following”\n- Line 83: could you spell out LwF?\n- Line 365: duplicated references", "limitations": "I would argue that an additional limitation is the latent space design itself. More accurately, the discrete latent space comes with tradeoffs. Because the method does not define a distance metric over the discrete latent space, there is no notion of exemplars or typicality in the mapped sequences. By design, all the sequences represent features of equal importance. However, one might presume that for some tasks, certain features of task deserve a higher weighting than others. This seems easier to solve in a continuous latent space, where you can map the importance of a feature onto distance.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The authors define a new set of problems for continual learning\n- The approach for mapping inputs to learned features makes sense\n- Continual learning is becoming more prevalent as models become more expensive to train from scratch, so the work is timely", "weaknesses": "- The framing uses catastrophic forgetting, but whether catastrophic forgetting is a pressing issue in today’s deep models is an open question. We do not know how increasing model scale impacts catastrophic forgetting, and deep networks like GPT-3 are fine-tuned often in production. Recent empirical results on catastrophic forgetting in neural networks are not as dramatic as the authors imply, and these works should be cited. See my comments in the questions section for references.\n- It’s unclear how the experiments in the paper map onto real world problems. Can the authors say more about this? When would we want to train a model sequentially over algorithmic tasks?\n- It seems CLeAR gets outperformed by multitask and single task training. Is there a baseline that would demonstrate the lift of this approach?\n\nSee questions for other concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*We thank you for the positive comments and suggestions. We have addressed each of your questions below.*\n***\n## Weaknesses\n**W1** We appreciate your insightful analysis on catastrophic forgetting, especially on recent LLMs. Following your suggestion, we have incorporated the references you mentioned into our work (Global Comment Literature Reviews 2).\n***\n**W2** So far, CL-AR has been a challenging field where deep learning models have not yet demonstrated practical real-world performance, making it difficult to apply in everyday life.\n\nIn the most ideal scenario, a robot, like a human, continuously acquires logical knowledge while integrating previous knowledge without losing it. In more practical fields, medical/industry datasets containing information that requires logical reasoning may be benefitted from CL-AR. Especially when it's not possible to define the task all at once from the beginning or access to previous data is prohibited due to privacy issues.\n\nIn a broader scope, we believe that our method of continually training logics could contribute to future LLM training like Open AI is now trying to enhance its performance on reasoning tasks through process supervision.\n\nUltimately, we expect that through the challenging CL-AR learning scenario that current neural networks struggle with, we may gain insights into how humans learn and integrate knowledge in the brain.\n***\n**W3** To establish a baseline for assessing the performance of our model, we attempted the following three approaches.\nFirst, we compared the performance of our CLeAR method with the Conventional CL algorithm as a baseline. The performance of the EWC, LwF, and ER methods is indicated in Supplementary D, demonstrating that our CLeAR significantly outperforms these methods.\n\nSecond, to further demonstrate the lift of our approach, we calculated the accuracy difference after the initial training of each task and after all tasks, which indicates how much information the model lost by CL. CLeAR not only retained nearly all information but also frequently exhibited backward transfer of information to previous tasks.\n\nThird, according to the paper “A continual learning survey:Defying forgetting in classification tasks(2021)” multitask training (joint training) is considered as a soft upper bound in CL scenario. And for most of the conventional cl methods, there is a considerable performance gap between multitasking training. Although our work is the first paper on CL scenarios in a completely new field, approaching joint training performance still indicates excellent continual learning is taking place. In fact, our model exhibited very high performance close to joint training and even demonstrated impressive results surpassing joint training performance on multiple tasks.\n***\n## Questions\n**Q1** We apologize for the insufficient information transfer to the model. We understood the “mapping set” you mentioned as the dimension of mapping space. The dimension of the mapping space is a hyperparameter determined by us, similar to the model's hidden dimension. It is advisable to set a larger value for the dimension when the number of alphabets in the input data is high. Our mapping function aligns the raw input sequence to the defined mapping space dimension. Furthermore, it is possible to increase the dimension of the mapping space during CL to readjust its size.\n***\n**Q2** According to formal language theory, tasks from the upper Chomsky hierarchy (context-free tasks) can not be represented by grammar on the lower Chomsky hierarchy  (regular grammar) or solved by corresponding automata (Finite-state automata). \nTherefore, even if finite state automata produced correct answers in some samples, It is appropriate to attribute this to random chance. However, theoretically, a neural network is a universal approximator capable of solving all problems, akin to a Turing machine. Consequently, if a neural network generates correct answers for certain samples, further analysis is necessary to determine whether it is due to random chance or if the network has indeed learned certain aspects of the task.\n***\n**Q3** CL, pretrain-finetune (P-F), and meta-learning (M-L) address different learning scenarios. It seems difficult to say which setting is better. In the context of AR, the goal is to excel at individual tasks rather than creating a generally superior model, which is why we found M-L incompatible. Additionally, due to the shifting data distributions for each task and the need to adapt well to previously learned tasks, we considered CL more suitable than P-F. During this rebuttal, we conducted additional experiments and discovered possibilities that pretraining on multiple tasks might not be advantageous in learning multiple AR tasks, making our CL-AR setup worthwhile. (Please refer to **General Response Experiment 2 and iPYe Q1** for detail).\n***\n**Q4** Apologies for the insufficient description. This statement implies that even recent CL methodologies find achieving positive backward transfer quite challenging. Recent methods such as AFEC (NeurIPS 2021) achieve only slight positive backward transfer on simple image datasets.\n***\n**Q5** Thank you for introducing important papers related to this study. As per your comment, we will make sure to cite the two mentioned papers in the related work section of the final version (**Global Comment Literature Reviews 3**).\n***\n**Q6** For the CL Finals column, the emphasis is on results above 90%, and for BWT and FWT columns, on positive values. However, the non-bold case does not imply low CL performance. Due to the text limit, please refer to **iPYe W1** for a detailed explanation. \n***\n## Limitations\n**L1** We agree with your statement. Expanding this work into distance-preserving mapping in a continuous feature space would be meaningful. As part of future work, we intend to explore our continuous feature space mapping using models such as diffusion models."}]

Author rebuttal:
We thank all the reviewers very much for their valuable comments and constructive suggestions to strengthen our work. Also for the positive comments and encouraging remarks: The paper addresses for the first time the continual learning (CL) adaptation of algorithmic reasoning(AR) tasks (iTug, iPYe). It also introduces a novel set of logical reasoning tasks for CL which are categorized according to the Chomsky hierarchy (FdFh, aCtv). These are disparate from the standard CL scenario (iTug) and research has not yet been conducted (GYfA). Also, it is challenging to use most previous CL methodologies on this new task (FdFh). The paper introduces a novel methodology, CLeAR (GYfA), and the core idea of mapping tasks and inputs to an embedding space from which a unified model learns continually to solve tasks is, to my knowledge, highly novel (iPYe), novel (FdFh), makes sense (aCtv). With several experiments, the proposed method showed desired effects, preventing catastrophic forgetting in several scenarios (iTug) and showing the capability of achieving backward transfer (FdFh). The paper bridges the gap between CL and real-world cognitive skills development (GyfA) and leads to a more general setting w.r.t. standard CL which can improve current research and lead to new methodologies (iTug).

Following reviewers’ suggestions, we have added literature reviews and performed more supporting experiments. Here, we would like to highlight the **main revisions**:

# Literature reviews  
We cited and discussed the following papers  
> **DeepProbLog(2018)[1], HOUDINI(2018)[2], NeuralTerpret(2017)[3]**: These papers propose a neuro-symbolic or probabilistic framework for solving logical problems. These frameworks are divided into two main parts. The first part consists of task-specific pre-defined parameterized functions capable of handling logic (e.g., ProbLog for DeepProbLog, symbolic program synthesizer for HOUNDINI, and program interpreter for NeuralTerpret). The second part involves Neural networks (NN). These frameworks support end-to-end gradient-based updates for the combination of the parameterized functions and the NN. The program part acts as a logic solver while NN acts as a feature extractor from the image. We included this paper In the "related work" section and described their relevance and differences compared to our research (by FdFh, GYfA).

> **On warm-starting neural network training[4], Does the Adam Optimizer Exacerbate Catastrophic Forgetting?[5]**: This paper discusses catastrophic forgetting, one of the core challenges in CL. It addresses the issue of rapid forgetting by preventing abrupt changes in model parameters. We have added this paper to the "introduction" and revised its relevant content (by aCtv).

> **A formal hierarchy of RNN architectures[6], Saturated transformers are constant-depth threshold circuits[7]**: These papers discuss the feasibility of initial AutoRegressive (AR) tasks on RNN and Transformer model architectures. We have added citations to these papers in the “related work” section (by aCtv).

# Experiments
> **Repeated experiments**: We updated single-run experiments to three repeated experiments by adding two more seeds. We confirmed that there were only minor variations in the values of the experimental results. In the final version, we will conduct many more repeated experiments, and this measure will further reduce confirmation bias (by iTug. refer **iTug W3** for more detail).

> **In-depth inspection of the model learning reasoning**: “What is learned in the model across disparate tasks, allowing knowledge transfer.”(FdFh), “How does the model coordinate incoming tasks?”(iPYe), “Is it really good to learn AR sequentially instead of learning all at once?”(aCtv) These are very important questions in CL, but it has been a challenging problem due to the black-box nature of the NN. However, we have taken a step forward in solving these problems with the help of the high interpretability of the AR task and automata theory. We conducted an analysis of **A. what the model actually learns from data and how they coordinate it with the new task** by analyzing the model’s hidden feature with the corresponding automata. And **B. what differences are achieved between CL and joint training.** In typical CL scenarios, joint training (all tasks learned together), is often considered an upper bound in terms of performance. However, contrary to the conventional belief, joint training often showed lower performance in the conducted AR tasks, which emphasizes the importance of continually learning AR tasks just like humans improve their logical abilities through step-by-step learning in the real world. We quantitatively compared the performance of joint training and CL and proposed a convincing hypothesis for why CL outperforms joint training in certain cases (by FdFh, iPYe. For the result of this experiment, refer **Fig R1,R2 of attached PDF** and **iPYe Q1** for more detail).

> **Experiments on more difficult tasks**: We extended our experiments to more model structures on the challenging ten sequential AR task scenarios from our paper, along with reversed order of the Chomsky hierarchy. Furthermore, we conducted additional experiments to investigate cases of tasks with partially overlapping columns (by FdFh. refer **FdFh W3,Q1** for more detail).

* The code for additional experiments will also be publicly released in the final version.

# References  
[1] Manhaeve, et al. "Deepproblog: Neural probabilistic logic programming."  
[2] Valkov, et al. "Houdini: Lifelong learning as program synthesis."  
[3] Gaunt, et al. "Differentiable programs with neural libraries."  
[4] Asht, et al. "On warm-starting neural network training."  
[5] Ashley, et al. "Does the Adam Optimizer Exacerbate Catastrophic Forgetting?."  
[6] Merrill, et al. "A formal hierarchy of RNN architectures."  
[7] Merrill, et al. "Saturated transformers are constant-depth threshold circuits."

Meta-review: This paper studies continual learning of algorithms for the first time. Authors introduce a novel set of logical reasoning tasks classified into Chomsky hierarchies. Then they propose a methodology that involves one-to-many mapping of input to a shared representation space. The experimental results demonstrate that their methodology (CLeAR) achieves zero forgetting and backward transfer. All reviewers except one voted for acceptance. After reading the reviews and authors detailed response, I am recommending  acceptance. Please take reviewers suggestions into account for the camera-ready version. In particular, I think it is important to discuss the motivation for this line of work in light of foundation models and how they relate.
Decision: Accept (poster)