Can You Learn an Algorithm?  Generalizing from Easy to Hard Problems with Recurrent Networks
Authors: Avi Schwarzschild
Eitan Borgnia
Arjun Gupta
Furong Huang
Uzi Vishkin
Micah Goldblum
Tom Goldstein
Venue: NeurIPS 2021 Poster (2021)
Keywords: Deep learning
algorithms
generalization
recurrent networks
prefix sums
mazes
chess

Abstract: Deep neural networks are powerful machines for visual pattern recognition, but reasoning tasks that are easy for humans may still be difficult for neural models. Humans possess the ability to extrapolate reasoning strategies learned on simple problems to solve harder examples, often by thinking for longer. For example, a person who has learned to solve small mazes can easily extend the very same search techniques to solve much larger mazes by spending more time.  In computers, this behavior is often achieved through the use of algorithms, which scale to arbitrarily hard problem instances at the cost of more computation. In contrast, the sequential computing budget of feed-forward neural networks is limited by their depth, and networks trained on simple problems have no way of extending their reasoning to accommodate harder problems. In this work, we show that recurrent networks trained to solve simple problems with few recurrent steps can indeed solve much more complex problems simply by performing additional recurrences during inference. We demonstrate this algorithmic behavior of recurrent networks on prefix sum computation, mazes, and chess.  In all three domains, networks trained on simple problem instances are able to extend their reasoning abilities at test time simply by "thinking for longer."

Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks
Avi Schwarzschild Department of Mathematics University of Maryland College Park, MD, USA avi 1udi1dumd.ccm edu
Eitan Borgnia
Arjun Gupta Department of Robotics University of Maryland College Park, MD, USA
Department of Computer Science University of Maryland College Park, MD, USA
Furong Huang Department of Computer Science University of Maryland College Park, MD, USA
Uzi Vishkin
Department of Electrical and Computer Engineering University of Maryland College Park, MD, USA
Micah Goldhlum
Tom Goldstein
Department of Computer Science University of Maryland College Park, MD, USA
Department of Computer Science University of Maryland College Park, MD, USA
Abstract
Deep neural networks are powerful machines for visual pattern recognition, but reasoning tasks that are easy for humans may still be difficult for neural models. Humans possess the ability to extrapolate reasoning strategies Icarned on simple problems solve harder examples, often by thinking for longer. For example, a person who has learned to solve small mazes can easily extend the very same search techniques to solve much larger mazes by spending more time. In computers, this behavior is often achieved through the use algorithms, which scale to arbitrarily hard problem instances at the cost of more computation. In contrast, the sequential computing budget of feed-forward neural networks is limited by their depth, and networks trained on simple problems have way of extending their reasoning to accommodate harder problems. In this work, we show that recurrent networks trained solve simple problems with few recurrent steps indeed solve much more complex problems simply by performing additional recurrences during inference. We demonstrate this algorithmic behavior of recurrent networks on prefix sum computation, mazes, and chess. In all three domains, networks trained simple problem instances able extend their reasoning abilities test time simply by "thinking for longer."
Introduction
In computational theories mind, an analytical problem is tackled by emhedding it in "working memory" and then iteratively applying transformations the representation until the problem is solved [addeleyy 2012 Baddeley and Hitch 1974). Iterative processes underlie the human ability to solve sequential reasoning problems, such complex question answering, proof writing, and even object classification [Liao and Poggio 2016 Kar et al., [019]. They also enable humans to extrapolate their knowledge solve problems of potentially unbounded complexity, including harder problems than they have seen before, by thinking for longer.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

This work examines whether recurrent neural networks trained on easy problems can extrapolate their knowledge to solve hard problems. We find that recurrent networks can indeed generalize to harder problems simply by increasing their test time iteration budget (i.e., thinking for longer than they did at train time). Moreover, we find that the performance of recurrent models improves as they recur for more iterations, even without adding parameters or re-training in the new, more challenging problem domain. This ability is specific to recurrent networks, as standard feed-forward networks rely on layer-specific behaviors that cannot be repeated to extend their reasoning power.
The behavior we observe in recurrent networks falls outside the classical notions of generalization in which models are trained and tested on the same distribution. Because we train and test on problems of different sizes/difficulties, our training and test distributions are disjoint, and systems must extrapolate to solve problems from the test distribution. Outside the field of machine learning, computers achieve a functionally similar extrapolation ability through the use of algorithms, which encode the process required to solve class of problems, and can therefore scale to problems of arbitrary size, albeit with longer runtime.
By training networks to solve problems iteratively, we hope to find models that encode a scalable method for solving problems rather than memorizing a mapping between input features and outputs. In short, the goal is to create recurrent architectures that are capable of learning an algorithm.
Our focus is three reasoning problems that classically solved using hand-crafted algorithms: computing prefix sums, solving mazes, and playing chess. Sequential reasoning tasks like these are ideal for our study because one can directly quantify the difficulty of problem instance. In the case of mazes, for example, we can easily swap to a more challenging domain by increasing the size of the search space.
For each class of problems, recurrent networks are trained on a set of "easy" problems using a fixed number of iterations of the recurrent module on the forward pass. After training is complete, we assess whether our models exhibit logical extrapolation behaviors by testing them on "hard" problems, with varying numbers of additional iterations. Remarkably, models trained on easy examples exhibit little extrapolative behavior until their iteration budget is increased - generalizing to harder problems requires thinking deeper. Moreover, extra iterations outperform the inflexible feed-forward models of comparable depth, often by a wide margin. Finally, we visualize the iterative behavior of the recurrent module gain insights into the problem solving process they discover.
find recurrent models tested with a sufficient number of
1.1 Related works
Our investigation into generalizing from easy to hard examples builds on several bodies of work. Logical extrapolation encompasses special kind of distributional shift. A number of existing works on domain generalization instead explore shifts, such as re-stylization and image corruptions, which do not represent increase in scale computational complexity [Arjovsky et al.) [019 Shu et al., 2020]. Also, the basic neural architectures we use are not new and build upon prior studies of weight sharing and recurrence [Pinheiro and Collobert] 2014 Liang and Hu 2015 Alom et al. 2018 Bai jet al. 2018 2019 Lan et al.) 2020 Jaegle et al. 2021]. Networks with variable numbers of test time iterations/layers have also been studied, including variable depth networks [Graves 2016 Huang
et al.
2016 Kaya et al. 2019 Eyzaguirre and Soto 2020).
Existing work algorithm learning involves recurrent neural network (RNN) based approaches. For example, neural turing machines and neural GPUs can learn simple algorithms for tasks such as binary addition and multiplication [Graves et al. 2014 Kaiser and Sutskever) 2015). Like most RNNs, the compute budget for these methods is inextricably tied to input length. Motivated by the fact that input sequence length is not necessarily correlated with the computational burden required to solve a problem. Graves 2016) develops a method for RNNs to adaptively select a compute time limit. This work considers only sequence inputs and shows the benefits of decoupling compute budget from input length. A differentiable extension of the technique can also be applied to visual question answering (Eyzaguire and Soto 2020).
The above works leverage neural networks with adaptive computation budgets to speed up and strengthen inference when learning on stationary distributions. In contrast, our work studies the logical extrapolation behaviors that recurrent networks possess when both computation budgets and problem difficulties are extended beyond the train-time regime. In the domain of constraint
2

---

satisfiability problems (CSPs), Selsam et al. (2018) show message passing neural networks trained on small CSPs can generalize larger problems if more messages are passed at test-time similar type of extrapolation to our methods, but for a very specific problem formulation.
The particular problems
study this type of extrapolation include prefix computation and maze solving, two problems analyzed in the classical algorithms literature. For example, there are many ways to solve mazes, both classical (e.g. breadth first search) and learned (e.g. value iteration networks), but our goal is not to develop the best solver, rather to use mazes as a test bed for logical extrapolation [Tamar et 2016]. Our third case study is the game of chess, which has also been the focus of much artificial intelligence work Romstad et al. Biswas and Regan 2015 Silver et al. 2017 Mcllroy- Young et 2020). However, those efforts play chess rely heavily on hand-crafter search algorithms, often paired with neural networks or opening books, and aim to play games from start to finish, both methods and goals that diverge from ours. As opposed to hard-coded algorithms, which scale by design, we are interested in studying whether learned processes can generalize from the data on which they are trained to even harder problems.
Dataset descriptions
We conduct experiments in three problem domains that classically solved using hand-crafted algorithms. For each, we define datasets that have quantifiable notions of difficulty. This makes possible to train models easy/small examples and test them on harder/larger ones. We consider the task of computing prefix sums modulo two of binary bit strings, solving two-dimensional mazes, and finding the best move in chess puzzles.
Prefix sums This problem is inspired by similar dataset used by Graves 2016). Each training sample is a binary string. The goal to output binary string of equal length, where each bit represents the cumulative and we consider longer strings to be more difficult to process than shorter ones. Each dataset contains 10,000 uniform random binary strings without duplicates. We use datasets with input lengths of 32, 44, and 48 bits. See Figure for an example input and the corresponding target output.
of input bits modulo two. Our models accept input strings of any size,
Input:
11000110111111011111111111111111 1.1.0.11111111111111111111111111
Target:
Figure 1: Prefix sum input and target example.
Mazes We consider mazes generated using depth-first search algorithm Hilll 2017). We train on 50,000 small (9 x 9) mazes, and we test on 10,000 larger (13 13) mazes. Our models are convolutional, and receive and the start and goal locations are red and green, respectively. The label for each maze is a binary two-dimensional mask containing the locations of positions along the shortest path solution. Our models output a two logits per pixel which are then thresholded to a binary mask of the whole input, and consider candidate solution correct only if it exactly predicts the labeled path. See Figure 10 for an example. More examples are available in Appendix A.I.2]
N x N three-channel image, where the maze walls black,
Figure An example maze input and target.
Figure An example of a chess puzzle input (left) and target (right). In the target, white represents one and black is zero.
The target is a binary classification label for each pixel indicating on/off the optimal path.

---

Chess puzzles The third dataset we use is corpus of chess puzzles. The data is furnished by Lichess, an online open-source chess server [Lichess] 202T]. From billions of games, Lichess compiles "puzzles" - mid-game boards for which a sequence of unique best moves is determinable (e.g. sequences of moves leading to a forced checkmate). From this database, we compiled labeled data where the inputs are 8 x 8 x 12 arrays indicating the position of each piece on the board (one channel per piece type and color) and the outputs are 8 x 8 binary masks showing the origin and destination positions for the optimal move. See the example in Figure 3 where it is white to move and the solution to the puzzle is to move the queen from F3 to F7.
The puzzles each have difficulty rating determined by an Elo-like system (a standard system for rating players using tournament play) [Elo, 1978). When Lichess users, each with an Elo rating, attempt to solve the puzzle, the rating of the player and puzzle is updated as if they "played" against each other. After enough players encounter the puzzle, the rating of the puzzle reaches an equilibrium which gets recorded in the database. We use these ratings to distinguish between easy and hard; 600,000 puzzles of difficulty rating less than 1, 1,385 are used for training, and testing is performed on 100,000 examples with ratings greater than 1,385.
Our models output confidence score between zero and one for each square on the board. We take the two highest scores and compare their locations to the target to measure correctness - only exact matches are considered correct.
3 Model architectures & training
In all of the experiments in this work, we employ network architectures based on ResNets (He et al. 2016]. Our feed-forward networks are slight deviations from the most commonly used ResNets, in that the width does not change except at the first layer and after the last residual block, and we do not use batch normalization. This is done so that the recurrent models, whose internal recurrent module has the same input and output dimensions, can be as similar as possible to the feed-forward ResNets. In fact, the only difference during training between a feed-forward and recurrent model of the same effective depth is that the weights are shared between the residual blocks in the recurrent models. We refer to the recurrent portion of the network as the recurrent module. Also, our models are fully convolutional with no fully connected heads. For solving prefix sums, which involves one- dimensional strings, we further deviate from classical ResNets by using mneddiensiooall convolutions. For complete architectural details, see Appendix A.2
We measure recurrent models in terms of iterations and effective depth. An iteration is repetition of the recurrent residual block, which contains four layers in all of our models. Therefore, the effective depth is equal to four times the number of iterations, plus non-recurrent encoder and head layers that sandwich the recurrent module, For example, the models used for computing prefix sums have one convolutional encoder layer, followed by the recurrent block and then by a three layer convolutional head. In this case, a 10-iteration model has effective depth 1 + 10 x 4+3 3 = 44 layers.
For each training sample we consider, the label is an array of binary classification variables, one per input pixel. The training loss simply the mean cross-entropy loss across output values. In general, hyperparameters were determined with the goal of finding convergent models. The specific batch sizes, learning rate and decay schedules, and other hyperparameter values are all available in Appendix A.3
4 Recurrent networks can generalize from easy to hard problems
We explore the ability of recurrent neural networks to generalize more difficult problems simply by thinking deeper. To this end, we train models of varying effective depth on easy training examples and test them harder problems. We find that recurrent models are even better at generalizing from easy to hard than their feed-forward counterparts. While there is only one way to test the feed-forward models, we take closer look at what happens when the recurrent models are allowed to think deeper about the harder problems. Formally, we use more iterations of the recurrent module within the recurrent models when performing inference on test data. Across all three problem types, find that
'Code to reproduce our experiments along with information about downloading the data we use is available wttptttw...como/////////eeaaaee hard

---

average values from several trials and the shaded the confidence of the model is a good surrogate for correctness. Therefore, when evaluating recurrent models, we use the output from the iteration which the network assigns the highest confidence.
4.1 Prefix sums
The first task which demonstrate the ability of recurrent neural networks to learn algorithm is one from the classical algorithms literature, namely computing prefix sums. Specifically, we study the problem of computing the prefix sums modulo of binary input strings.
When computing prefix sums, we employ models with effective depths from 40 to 68 layers. We train models on easy data consisting of 32-bit input strings and test harder 40-bit and 44-bit strings. In T it is clear that even when holding the depth constant at test time, recurrent models generalize from easy to hard better than feed-fore forward networks.
Table 1: Extrapolating to longer input strings. Shown here the average accuracies of models trained on 32-bit inputs and tested on 40-bit inputs. The effective depths listed below correspond to 9, 10, and 1l iterations recurrent models. We report average accuracy one standard error.
Effective Depth (Layers)
44
Recurrent
24.96 + 2.96
31.02 + 2.56
35.22
3.34
Feed-forward
22.17 1 0.85
24.78 +: 1.65
22.79 + 1.32
Models Trained With 10 Iterations on 32-bit Data
100
Recurrent, 40-bit data
Accuracy (%)
Reeurrent, 44-bit
60
Feed-Forward, 40-bit data Feed-Forward, 44-bit data
Training Regime
40
20
0
10
12
15
Test-Time Iterations
Figure 4: Generalizing from easy to hard prefix sums. The ability of networks to compute prefix sums sets with longer input strings than used for training (accuracy on 40-bit inputs in purple and on 44-bit inputs in red). We compare recurrent models to the best feed-forward models of comparable effective depth. The markers regions indicate + one standard error.
When the thought budget, or number of iterations, increased, we see that recurrent models can get upwards of 90% of the harder testing examples correct. In Figure ! we observe this large boost in the recurrent models' performance and a vast difference the accuracy recurrent models (with added iterations test time) and feed-forward networks. Note that the dotted lines represent the average accuracy of the deepest feed-for forward networks considered. That depth is 68 layers, or the effective depth of recurrent models with 16 iterations, and use this baseline in the plot specifically because the range depths corresponding to the numbers of iterations shown, these feed-forward models achieve the highest accuracy. In other words, recurrent models trained with relatively few iterations generalize well to harder data while similar and even much larger rredfforwrd networks fail to generalize in the same scenario.
The generalization we see in Figure indicates that these recurrent models learn processes that can be extended to harder problems by running for more iterations. In particular, the recurrence is both

---

the machinery that allows for varying the depth at test time, as well as force at training to push the model find parameters that make progress toward a solution with each reuse.
When these results are viewed through the lens of algorithm design, one might wonder how the receptive field, or the number of entries in the input that determine single entry in the output, affects these models. The feed-forward models, whose accuracies are shown in Figure 4 have the same receptive field as the recurrent models when tested with 16 iterations. This makes clear that the increase in accuracy of recurrent models does not simply occur because the receptive field grows with added iterations, rather occurs because they have learned a process that can extrapolate beyond the training distribution. Further discussion on receptive field is presented in Appendix B
4.1.1 Iterative outputs
One way dissect the learned process and compare it to known algorithms is plot the confidence of the model at each iteration. In Figure we show a representative example of a network's ' confidence that each bit in the output is one. Two striking observations can be made from this figure. The first is that the model is progressing to the solution with each iteration. The second observation is that it is resolving the prefix sum the earlier bits first and moving down the string, settling on the final bits only in the last iteration. This is remarkably similar to a naive algorithm one might implement for this task that marches from the first index until the end of the string computing prefix sums in order.
Index
Inp. #1
#2
#3
#4
#5
#6
#7
#8
#9
#10
#11
Tar.
Iterations
Figure 5: A recurrent model's output from each 11 iterations on a 40-bit input string. Shown here is the confidence that there is a at each index of the output. The first index is at the top for all vectors, the input is in the left-most column and the target is in the right-most column. The model used to produce this plot was trained with fewer iterations (10) shorter input strings (32-bit).
4.2 Mazes
For maze solving, we train models training set composed of the easier small mazes, and investigate the ability of networks to make the leap to larger, or harder, mazes at test time. In line with the findings above, show two important behaviors. First, the recurrent models make the leap from small to large mazes better than feed-forwan models. Second, when allowed to think deeper, the recurrent models exhibit even higher performance.
The networks employed here are fully convolutional and have 512 channels in the internal layers. In assessing the confidence of given output, average each pixel's 's classification confidence.
Table 2 shows that for a fixed effective depth, recurrent models always generalize to the hard mazes better than their feed-forward counterparts. Inspired by the upward trend in Table we shift focus to deeper models. In Figure 6 we show that recurrent models can extrapolate to harder problems better than feed forward models. When trained small mazes with 20 iterations (effective depth

---

Table 2: The average accuracy (%) of models trained on small mazes and tested on large ones. Over range of effective depths, we see that recurrent models generalize the harder mazes better than their feed-forward counterparts. Figures reflect averages over several trials + one standard error.
Effective Depth
20
24
28
36
44
Recurrent
12.66 0.44
14.02
0.39
19.95 + 0.31
22.96 1.03
29.72 + 1.22
Ferd-forward
7.94 +: 0.36
12.43
0.50
14.67 + 0.54
17.71 0.36
22.53 +
of 84 layers), these networks can solve about half of large mazes. However, when allowed to think for longer. the recurrent models correctly solve even higher proportion of large mazes. In fact, models trained with 20 iterations can achieve upward of 70% accuracy on large mazes using additional iterations at test time.
Models Trained With 20 Iterations on Small Mazes
100
Accuracy on Large Mazes (%)
Recurrent
Feed-Forward
80
Training Regime
60
40
20
0
20
21
22
23
24
25
26
27
Test-Time Test-Time Iterations
Figure 6: Generalizing from easy to hard mazes. We compare recurrent models to the best feed- forward models. The markers are at average values from several trials and the shaded regions indicate + one standard error.
Maze solving is another task for which global information needed. We investigate how dilated filters affect model performance. Dilation is way of changing the receptive field without adding new parameters or more depth. Table that dilations lead to slight improvements, however, the benefits of recurrence are still abundantly clear. Indeed, the difference in performance is even larger.
Table 3:
The average accuracy (%) of models with dilated filters trained on small mazes and tested on large ones. Figures reflect averages over several trials + one standard deviation.
Effective Depth
20
24
28
32
36
Recurrent
33.60 1.06
40.49
1.63
33.91
+
40.56
4.34
50.50
+ 7.97
Feed-forwant
19.73 + 0.72
21.59
0.22
21.18
+ 1.33
25.82
0.10
26.54
4 2.13
4.2.1 Iterative outputs
The recurrent maze solving networks also produce output at every iteration. Examining this output again leads to remarkable conclusion: these recurrent models are narrowing in on the answer with each successive iteration. In Figure ??] it is clear from the output on iteration four that the network has found two routes emanating from the red square. Moving through the iterations, the model refines the output, increasing the confidence for pixels on the path and decreasing the others until finally Iteration #7, the output matches the target. also interesting to observe here that the output consistently correct for two iterations, after which few pixels flip (Iteration #9).

---

1
1
1
1
F i
Iteration #1
Iteration #2
Heration
Heration
Ileration #5
L
L
L
L
Iteration #6
Tteration #7
Iteration #8
Iteration #9
Target
Figure 7: Input, target, and outputs from different iterations are shown to highlight the model's ability to think sequentially about mazes. We plot the model's confidence that each pixel belongs to the optimal path. This is representative example from model trained to solve small mazes in six iterations.
4.3 Chess puzzles
The third dataset comprises chess puzzles, or mid-game chess boards for which we seek the best next move. Unlike the other two datasets, the state of the art for chess playing algorithms is complex and has components that use algorithms like Monte Carlo tree search as well as neural network based elements for evaluating positions [Romstad et al. Silver et al. 2017 The complicated nature of these systems provides some context for how difficult these puzzles are. What makes these puzzles particularly useful for is that there is predetermined best next move. A move is defined as origin square, or the current location of the piece to be moved, and a destination square In order to generate target outputs for our models, we define move as an 8 array with zeros everywhere except at the entries corresponding to the origin and destination squares which are ones.
We compare recurrent and ferdadd networks of effective depths from 84 layers to 100 layers that take x 8 x 12 arrays as input. These fully convolutional networks have 512 channels in the internal layers, and the output is 8 x 2, corresponding binary classification at each input pixel. During training, we use an average of cross-entropy losses at every pixel. When evaluating these models, however, define the predicted move by the locations of the two highest confidence scores.
Models Trained With Iterations On Easy Puzzles
Accuracy on Hard Puzzles (%)
74.9
74.7
74.5
74.3
Recurrent
74.1
Feed-forward Training regime
69.0
67.0
65.0
63.0
61.0
20
21
22
23
24
Test-time Iterations
Figure 8: Generalizing from easy to hard chess puzzles. The ability of networks to solve harder puzzles than were used for training. We compare recurrent models to the best feed-forward models of comparable effective depth. The markers are average values from several trials and the shaded region indicate + one standard error.
"There are some cases, pawn promotions, where this information does not uniquely identify the move, and they overlooked in this project.

---

Once again, we see that recurrent models can solve more chess puzzles than their feed forward counterparts. Furthermore, by thinking deeper While the gains shown in Figure Bare are modest in comparison to the other two problem settings, the trend is clear recurrent models can solve more puzzles with more iterations.
time, recurrent models can perform even better.
4.3.1 Iterative outputs
Iteration
Iteration
Iteration
Iteration
A
Iteration #18
Iteration #19
Iteration #20
Target
Figure 9: Input, target, and outputs form different iterations are shown to highlight the model's 's ability think about the next move. We plot the model's s confidence that each pixel is one of the two that define move. In this example, black is to move next. For space consideration, iterations 2-14, which look like the first iteration, are left out of this plot. More examples are available in Appendix C
While the outputs from the other two datasets show the similarity between the learned iterative process and known sum and search algorithms, extracting that insight chess puzzles is much more difficult. Partly, this is because exploiting known search algorithms on such a large search space is hard to visualize. Nonetheless, the network's is output, shown Figure 9 tells fascinating story. First, the Iteration #1 plot shows that after one iteration, we observe equal confidence at every location on the board. In the next frame, Iteration #15, it is clear that the model is considering moving the D8 rook to multiple squares, and it also considers the intuitive idea of using the E5 queen to place the white king in check H2. With each successive iteration, the network becomes more confident first that the rook is the correct piece to move, and then where to move it to.
Discussion
More than answer, the results and conclusions in this paper posing question: Can learned models behave like classical algorithms the way they generalize to harder or larger problems?
Our discussion of this question and our observations begins with delineating the limitations of our work. The first major limitation is that we do not propose definitive answer. Rather, using representative cases, we demonstrate that recurrence can help neural models make the leap from easy training data hard testing examples. more subtle limitation of our work lies in how we split the data by difficulty. For prefix sum computation and for mazes, the classical algorithms approach to measuring problem complexity tied to problem size, so those settings we make intuitive easy/hard splits. With chess however, the issue is much more complex. Should puzzles with higher ratings require more memory or more computation? We carry out our work assuming the answer is yes, but we remain open minded to the possibility that the ratings assigned by Lichess may be weak surrogates for algorithmic complexity each puzzle. short, chess is an extremely difficult domain to analyze.
The observations above indicate that iterative models can learn processes that generalize beyond the training distribution with more iterations. One exciting use case is when the testing distribution is inaccessible, a setting where training on the harder distribution itself would be impossible. Many real life scenarios demand exactly this type of problem solving, from robots deployed in the real world after training in simulation humans who spend a lot of time practicing on easy math problems only to spend years difficult unsolved questions.

---

On a conceptual level, the recurrent model behavior we show is analogous to the human behavior of manipulating representations in working memory; in this analogy. the recurrent block performs the transformations and the activations it generates are the memory. It is not the goal of the experiments here to suggest that iterative models use mechanisms similar those in a human brain. Nonetheless, it is exciting to see, even in proof of concept setting, neural models that appear to deliberate on problem until is solved and can extend their abilities by thinking for longer.
This raises a questions that motivates future work. Can we build neural networks that can think for even longer? feasible to have models whose performance only increases with added compute time? Humans who are given more than enough time to solve maze, will not suddenly get it wrong after arriving the right answer, perhaps this awareness of when stop thinking can be built into networks like the ones we study here.
6 Conclusion
In this work, demonstrate that neural networks are capable of solving sequential reasoning tasks and then extrapolating this knowledge to solve problems of greater complexity than they were trained on. These recurrent models are largely inspired by the classical theory of mind, in which the brain iteratively applies primitive strategies to solve complex problems over time (Baddeley) 2012). Our models are recurrent versions of popular architectures and we acknowledge that variations to the model may be helpful. Thus, we leave an in depth investigation into other neural network designs for future work.
Interestingly, the resulting models excel at solving problems that are classically solved by hand- crafted algorithms; prefix sums computed using reduction trees, mazes are classically solved by depth/breadth first search, and chess is solved by Monte-Carle tree search. Even with the advances in machine learning that we have today, hand-crafted algorithms still play role in ofate-of-the-art reasoning systems. A prominent example is AlphaZero, which plays board games using Monte-Carlo tree search algorithms assisted by learned pruning function (Silver et al. 2017]. While moving away from this paradigm that includes hand-crafted elements is highly ambitious, this work suggests that it may be possible train gameplay systems without building them on top of a hand-crafted tree search engine. In other words, it may be possible to machine-lcarn these algorithmic behaviors end-to-end.
Acknowledgements
This project was supported by the ONR MURI program, AFOSR MURI program, the DARPA Young Faculty Award, and the National Science Foundation Division of Mathematical Sciences. Additional support was provided by Capital One Bank and JP Morgan Chase. Additionally, we thank Avrim Blum for thought-provon provokiig and insightful conversations.
References
Md Zahangir Alom, Mahmudul Hasan, Chris Yakopeic, Tarek M Taha, and Vijayan K Asari. Recurrent residual convolutional neural network based on u-net (r2u-net) for medical image segmentation. arXiv preprint 1802::80020666 06955, 2018.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint 19th::1997002993 2019.
Alan Baddeley. Working memory: theories, models, and controversies. Annual review of psychology, 63:1-29, 2012.
Alan D Baddeley and Graham Hitch. Working memory. In Psychology of learning and motivation, volume 8, pages 47-89. Elsevier, 1974.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Trellis networks for sequence modeling. In International Conference on Learning Representations, 2018
Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Information Processing Systems, 32:690-701, 2019.
10

---

Tamal Biswas and Kenneth Regan. Measuring level-k reasoning, satisficing, and human error in game- play data. In 2015 IEEE 14th International Conference on Machine Learning and Applications (ICMIA), pages 941-947, IEEE, 2015.
Arpad Elo. The rating of chessplayers, past and present. Arco Pub., 1978.
Cristobal Eyzaguirre and Alvaro Soto. Differentiable adaptive computation time for visual reasoning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12817-12825, 2020.
Alex Graves. Adaptive computation time for recurrent neural networks. 1603.0960088888 2016.
arXiv preprint
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv: 1410.5011, 2014.
arXiv preprint
K. He. X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pages 770-778, 2016.
Christian Hill Making a maze, Apr 2017. making-a-mmnn a-maze/
URL https://scipythonn wtt.lcocmm/...... blog/
Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q Weinberger. Deep networks with stochastic depth. European conference on computer vision, pages 646-661. Springer, 2016.
Andrew Jaegle, Felix Gimeno, Andrew Brock, Andrew Zisserman, Oriol Vinyals, and Joao Carreira. Perceiver: General perception with iterative attention. arXiv preprint arXiv:2103.03326, 2021.
Eukasz Kaiser and Ily Sutskever. Neural gpus learn algorithms. arXiv preprint / 2015.
Kohitij Kar, Jonas Kubilius, Kailyn Schmidt, Elias Issa, and James J DiCarlo. Evidence that recurrent circuits are critical to the ventral stream's execution of core object recognition behavior. Nature neuroscience, 22(6)997,-983, 2019.
Yigitcan Kaya, Sanghyun Hong, and Tudor Dumitras. Shallow-deep networks: Understanding and mitigating network overthinking. In International Conference on Machine Learning, pages 3301-3316 3310. PMLR, 2019.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self-supervised learning of language representations. In International Conference on Learning Representations, 2020.
Ming Liang and Xiaolin Hu. Recurrent convolutional neural network for object recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3367-3375, 2015.
Qianli Liao and Tomaso Poggio. Bridging the gaps between residual learning, recurrent neural networks and visual cortex. arXiv preprint 1rX4:1660.003640, 2016.
Lichess. Lichess open puzzles database. https::/databasse 1ichess serrs 2021. Accessed: 2021-04-01.
Reid Mcllroy- Young. Siddhartha Sen. Jon Kleinberg, and Ashton Anderson. Aligning superhuman ai with human behavior: Chess as model system. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1677-1687, 2020.
Pedro Pinheiro and Ronan Collobert. Recurrent convolutional neural networks for scene labeling. In International conference machine learning, pages 82-90. PMLR, 2014.
Tord Romstad, Marco Costalba, and et Kiiski, Joona. Stockfish: A strong open source chess engine. URL https://ssootffiscccess.oo

---

Avi Schwarzschild. Eitan Borgnia, Arjun Gupta, Arpit Bansal, Zeyad Emam, Furong Huang, Micah Goldblum, and Tom Goldstein. Datasets for studying generalization from easy hard examples. arXiv preprini arXiv:2108.0600 2021.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill. Learning a sat solver from single-bit supervision. arXiv preprint arXiv: 180.8.00....5,, 2018.
Manli Shu, Zuxuan Wu, Micah Goldblum, and Tom Goldstein. Preparing for the worst: Making networks less brittle with adversarial batch normalization. arXiv preprint arXiv:2009.08963, 2020.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint arXiv:1712.018155 2017.
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value iteration networks. arXiv preprint 160. 2016.
12


Reviews:
[{"review_id": "pd1HE3gJxv3", "reviewer": "Reviewer_iKnp", "summary": "The paper demonstrates generalization on 3 tasks: prefix sum, maze and chess.\nA fully convolutional net with a repeated recurrent block was able to generalize to larger input or harder cases without retraining.\nA higher amount of recurrent iterations was helpful on the harder cases.", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper correctly positions itself as a motivational paper, presenting important questions instead of a recipe for generalization.\nThe main weakness is that the paper is not aware of the solutions in the previous work:\n1) \"Neural GPUs Learn Algorithms\" ... Neural GPUs generalized to longer inputs.\n2) \"Value Iteration Networks\" ... explained that 2D mazes can be solved perfectly with convolution and max-pooling.\n3) \"Unbiasing Truncated Backpropagation Through Time\" ... the generalization to longer thinking time is related to truncated backprop.\n\nPros:\n- The paper is well written. Nicely readable.\n- Generalization to larger inputs and longer thinking time is an important problem.\n- The experiments are well done. The comparison to the feedforward nets is informative.\n- Nice visualizations of the iterative outputs.\n- Nice trick: Allowing to do more iterations and taking the output with the highest confidence.\n\nCons:\n- The paper does not provide an advice for generalization to longer thinking time. It would be helpful to mention the problematic parts of the training: truncated backprop, distribution shift without providing an ability to adapt, ...\n- The net has not achieved 99% accuracy on the 2D mazes. Value Iteration Networks worked better.\nIt would be helpful to report also the accuracy on the training set.\n\nMinor typos:\n- Line 138: \"as\" should be \"is\".\n- Line 214: \"form\" should be \"from\".\n- Figure 5: The input does not seem to correspond to the target.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "jC4LnBQvgcj", "reviewer": "Reviewer_Yvok", "summary": "The paper shows that recurrent neural networks, unlike feedforward ones, can generalize to harder tasks than they were trained on by increasing the number of recurrences during inference for tasks that allow such sequential reasoning. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main numerical results from the paper are interesting, by showing that while RNNs underperform feedforward nets of the same effective depth, running an RNN for more iterations at test time can lead to vastly improved performance on harder tasks. \n\nThe visualization results of iteratively getting closer to the solution in combination of the raw performances are indeed suggestive that more recurrences leads to more reasoning. \n\nIt would have been interesting however to compare the performances of these recurrent architectures to significantly deeper feedforward networks as well as networks trained on the harder version of the tasks as control. \n\nWhile the plots seems to suggest increasing recurrences usually helps, the Table 3 results seem to be showing saturation - the recurrent network drops 7% accuracy in performance while the feedforward gains nearly 3%. This suggests both that it would be worth checking deeper feedforward networks, as well as the fact that RNNs might be running into some sort of ceiling that should be explored here.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "L7ja6_3qNL2", "reviewer": "Reviewer_idGE", "summary": "This paper proposes the idea of learning an iterative refinement function within the deep learning framework using recurrence where training is done over a fixed number of iterations, but testing can be performed over an arbitrary number of iterations to let the learned model find a solution in case it needs to “think longer”. The authors have experimentally shown that the learned models can indeed solve more out-of-distribution problems if they're let run longer for three Prefix-sum, Maze and Chess Puzzles problems. They have also shown for the same out-of-distribution problems, a feed-forward model of the same effective depth performs poorly compared to their proposed recurrent model. Based on these results, the authors have claimed that the recurrent model has superior out-of-distribution generalization compared to its feed-forward counterpart. These out-of-distribution datapoints are specifically characterized as “larger” and “harder” throughout the paper, which in turn has paved the way to make the main claim of paper: RNNs can be used to train on easy problems and then generalize over the hard ones at the test time by letting them run longer.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \nThe idea of injecting the inductive bias of “iterative refinements through recurrence” into deep learning (or as the authors have put it “thinking longer”) and then arbitrary iterate over it at the test time is indeed an interesting and quite a useful idea, but it’s hardly a new one. In fact, people have incorporated the exact same idea in neural SAT and CSP solving. Here are two samples:\n\n-  Selsam, D., Lamm, M., Bünz, B., Liang, P., de Moura, L., & Dill, D. L. (2018). Learning a SAT solver from single-bit supervision. arXiv preprint arXiv:1802.03685.\n-  Amizadeh, S., Matusevych, S., & Weimer, M. (2019). PDP: A general neural framework for learning constraint satisfaction solvers. arXiv preprint arXiv:1903.01969.\n\n\nSignificance:\nWhile the experimental results are quite interesting (especially the behavior of the recurrent models with iterative outputs), the paper would have made a significant contribution on the top of the original idea by either providing a theoretical characterization of the sub-class of problems where such inductive bias is applicable OR implementing the idea in more practical applications such as Computer Vision where ConvNets are typically trained on a narrow distribution of image dimensions and generalization to completely different size images can be an issue. However, this work has provided neither of those two which makes the overall contribution somewhat marginal given that the main idea was used before in the literature.\n\n\nClarity:\nThe paper is very well-written with clear statements, explanations and enough details.\n\n\nQuality:\nThe overall quality of the paper is acceptable; however, there are a few significant issues that overshadow some of the main claims of the paper:\n\n-  Size vs hardness:\nThroughout the paper, the authors seem to confuse the notion of the “size” of a problem with its “hardness”. These are generally two different things. In SAT solving, for example, the size of a problem is determined by its number of variables; whereas, its difficulty is reflected by the ratio of the number of its clauses over the number of its variables. That is, a larger problem is not necessarily a harder one, and therefore scale-invariant algorithms are *not* necessarily guaranteed to generalize to “harder” problems. Now, for prefix-sum and maze problems, it seems to me that the test dataset contains “larger” problems and *not* the harder ones, due to the recursive sub-structure of those problems. For the chess puzzles, on the other hand, it seems the test data indeed contain harder examples; however, as the authors have also noticed, the gain is “modest”. Therefore, overall it seems one of the main claims of the paper that the proposed framework “generalizes from easy to hard” is not supported by the experiments.\n\nEven from the scale-invariance aspect, it’s hard to say how scale-invariant (if at all) the learned recurrent models are, given that the out-of-distribution results are only reported for 1 (Maze & Chess) or 2 (Prefix Sum) datapoints (i.e. distributions). Ideally, it’d be interesting to see (A) whether the learned model consistently scales up with larger and larger problems and if so, (B) at what rate the number of required iterations to solve a problem increases as the problem size grows. The latter would, in effect, show the effective complexity of the learned algorithm.   \n\n-  Generalization Comparison:\n“In other words, recurrent models trained with relatively few iterations generalize well to harder data while similar and even much larger feed-forward networks fail to generalize in the same scenario.”\nGenerally speaking, the hypothesis space of a feed-forward network is a superset of that of the recurrent model of the same effective depth. This means that in theory, given enough data and a good regularization scheme, the feed-forward model should be able to learn the same (if not better) function as that of the (rollout) recurrent model, unless it overfits of course (which seems to be a probable factor in this case, due to the over-parameterization of the feed-forward model compared to the recurrent model). In that sense, it’s not clear how much of the poor “out-of-distribution” (OOD) generalization of the feedforward model is attributable to the vanilla overfitting vs. an actual inability to generalize to OOD examples. To claim that it’s all the latter and NOT the former, it’d be necessary to report the results of “in-distribution” generalization for each model and experiment. Only if those numbers are close for the two models, one can claim that the observed gap between the two models on OOD examples is fully attributable to the superior OOD generalization of the recurrent model. In other words, it’s hard to make claims about the relative OOD generalization powers of two models when their relative in-distribution generalization powers are still in shadows. Therefore, I’d strongly recommend the authors to include the in-distribution test accuracies as well for all the experiments.\n\n\nVision:\nLastly, in final conclusions of the paper, the authors have stated: “In other words, it may be possible to machine-learn these algorithmic behaviors end-to-end.” While this might be an interesting theoretical exercise, I’m not sure it’s the right vision from the practical perspective. In fact, this goes against the main intuition of neuro-symbolic methods where symbolic algorithms are incorporated within the deep learning framework in order to exponentially reduce the amount of training data and time needed for learning anything useful. Aside from humongous amount training data one would need to learn such algorithms “end-to-end”, at the end of the day, there’s still no correctness and scale-invariance guarantees for a purely statistical model. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As for limitations of their work, the authors have gone to a great deal explaining them in Sec 5, which is all fair and well-explained. Although, as I explained above some of the main claims of the paper seem to be unsubstantiated or at best very specific to the experiments done. So in that regard, I'd strongly recommend authors to either provide more proof for those claims OR revise them by explicitly discussing their limitations.\n\nAs for societal impact, I agree with the authors that their work does not particularly pose any negative impact beyond that of the general field of AI.   ", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues with this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hrs"}, "extra_text": {}}, {"review_id": "IHJTVfhg_8D", "reviewer": "Reviewer_XL39", "summary": "This paper describes a method that allows models to extrapolate to larger problems than those they are trained on, a known limitation of many neural network architectures. It proposes a network with an encoder, a decoder and a recurrent unit (a 4 layer residual convolution network) that is iterated through several times during training, the output of an iteration being used as the input to the next. This amounts to a deep ResNet with shared middle layers. \n\nThe authors show that models trained with this architecture can generalize to larger problems by increasing the number of iterations of the recurrent unit during inference. This achieves better accuracy than feed-forward ResNets of equivalent depth.\n\nThree problems are considered: parity integration of a binary string, path finding in random mazes (encoded as binary images), and solving chess problems (generated from Lichess). The models are shown to generalize to longer strings, larger mazes, and, to a lesser extent, harder problems (measured by their Elo ranking).\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality** \nThe architecture proposed by the paper is inspired by the Adaptive Computation Time model (Graves 2017), and its successors. The authors provide references to this line of research. The building blocks are standard residual convolution networks. The problems studied have been considered by previous authors. The originality of the paper lies in leveraging the recurrent architecture to run more steps at inference, and generalize to larger problems. \n\nThere has been a lot of research on generalization to longer sentences in sequence to sequence models. Tree-LSTM (Arashahi, 2019) and attention mechanisms (Dubois, 2019) have been proposed, among others. This might be worth adding to the related work.\n\n**Quality** \nA very good paper, the methodology and the datasets considered are clearly exposed and the experiments and conclusions are very compelling. A number of additions might make it even better.\n\n1- The terms \"easy\" and \"hard\" are a little misleading. What seems to be demonstrated in the case of parity integration and mazes is extrapolation to **larger** problems (in terms of description length of their input and output). This is not the case for chess, and it might be a reason why the method is less efficient. It would be good to clarify this definition of \"hard problem\" in the introduction (or use a different word). \n\n2- For parity integration, the base operations over a long sequence uses no more memory or computation than those of a short one: every new output digit is a XOR between the previous output and the next token. It would be interesting to try a binary string problem where memory/computation increases with sequence length (e.g. computing square roots or any function where many or all previous input or output are needed at each step. \n\n3- At inference, it is shown that iterating improves accuracy on larger problems. What happens as one goes on iterating? Does accuracy saturate or does it ends up decreasing? If the iteration curves saturate, can a stop condition be derived, either from the confidence map, or successive iteration accuracies? Such a decision rule would turn the experimental technique described in the paper into a  solver for the problem considered. Proving that the solution stabilizes as the model iterates is an interesting theoretical result, because it makes inference a fixed point process.\n\n4- What about problems of the same size as those trained on? In the maze case, for a given dimension, one expects problem difficulty to be correlated with the length of the solution path, so there will be easy and hard problems inside the test set. Can iterating at inference improve test accuracy beyond training accuracy, over the same distribution? (This would be extremely interesting!) \n\n5- What about smaller problems?  Models trained on large problems often badly generalize to simple cases. Can the model \"dumb down\" by computing more?\n\n6- It is mentioned that parity integration is difficult to train. Could normalization help? More generally, a few ablation/architecture experiments on the shared parameters (less layers/lower dimension in the basic iteration blocks, normalization, maybe even a visual transformer layer) would be very welcome, and strengthen the paper.\n\n**Clarity** \nClearly written. Providing the source code is a great help. A sketch of the architecture (for the mazes, say), explaining the difference between the training and inference computation, would be very helpful: this is where the novelty lies. The chess experiments are much less compelling than the others, and as you note in the discussion, more difficult to interpret. It might be a good idea to move some of them in the supplementary, and improve the discussion of other cases in the main paper.\n\nIn the appendix : the B3 section is empty, the legend in figure 12 has a typo (100,000 to 150,000 is probably 1,000,000 to 1,050,000)\n\n**Significance** \nThis is an important paper, which addresses a longstanding issue with neural networks. The parity and maze examples are very compelling. There seem to be many options for generalizing this approach, by varying the encoders and decoders, and the archtecture of the internal blocks. A discussion of these future options would improve the paper significance.\n\n**Overall** \nA very good paper on an important subject. It could be greatly improved by running a few experiments on inference, trying small changes in the architecture, and detailing a little morethe very conclusive experiments on parity integration and maze paths in the main paper. A clear accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They have.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a genuinely interesting result, namely that by increasing the effective depth of a network through the repetition of learned dimensionality-preserving transformations within the network, the resulting test-time network obtains better extrapolatory performance without further training. It shows empirically on a diverse-enough set of toy-ish tasks to pique interest. I can see this paper generating quite a bit of discussion in a certain part of the NeurIPS community, in particular with regard to its application to Transformer-style architectures for which such an idea of adaptive depth could be easily applied.

There is a huge variance in scores, but thankfully, there was quite a bit of discussion, and the reviews are all fairly detailed (especially those in support of the paper). I'll be honest, I simply don't understand the argument made by Reviewer iKnp in favour of rejection. While it's true that the question "Can You Learn an Algorithm?" has been addressed by methods such as Neural GPUs, Turing Machines, Stacks etc circa 2014/2015, the matter is certainly not closed or solved in any substantial way, and a contribution such as that made by this paper is welcome. Aside from this point, I don't see a convincing argument in favour of rejection in Reviewer iKnp's comments.

Reviewer idGE offers a more substantial critical reading of the paper, which the authors should pay more heed to. I agree with some if this reviewer's point regarding the framing of the contribution, and being careful with the notion of hardness of problems. I urge the authors to consider fairly substantial edits to be a bit more diligent and conservative with their claims here, but at the end of the day would not consider rejecting the paper on this basis of this critique alone.

Reviewer Yvok seems satisfied with the author responses to their review, but has not updated their score past 6. However, I don't really see what outstanding issues they have that would prevent them from continuing in their support of the paper.

Finally, Reviewer XL39 has written substantially to champion the paper's acceptance, echoing however the issues raised by Reviewer idGE regarding terms such as "hard" which are used a little casually. I again recommend the authors take the task of editing the paper seriously to incorporate this feedback.

While on the face of it, this paper is borderline when it comes to scores, when weighing the reviewer recommendation by the strength of the arguments, and the detail of the reviews and discussions, I find that this paper is unambiguously acceptable and a strong contribution. It may not be perfect, but it will have good potential to influence others' work, and will add to the diversity of topics at the conference.
Decision: Accept (Poster)