Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

The 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. 

It 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. 

While 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.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 

The 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.

Three 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).


main_review: **Originality** 
The 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. 

There 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.

**Quality** 
A 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.

1- 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). 

2- 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. 

3- 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.

4- 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!) 

5- What about smaller problems?  Models trained on large problems often badly generalize to simple cases. Can the model "dumb down" by computing more?

6- 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.

**Clarity** 
Clearly 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.

In 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)

**Significance** 
This 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.

**Overall** 
A 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.
limitations_and_societal_impact: They have.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: Originality: 
The 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:

-  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.
-  Amizadeh, S., Matusevych, S., & Weimer, M. (2019). PDP: A general neural framework for learning constraint satisfaction solvers. arXiv preprint arXiv:1903.01969.


Significance:
While 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.


Clarity:
The paper is very well-written with clear statements, explanations and enough details.


Quality:
The overall quality of the paper is acceptable; however, there are a few significant issues that overshadow some of the main claims of the paper:

-  Size vs hardness:
Throughout 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.

Even 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.   

-  Generalization Comparison:
“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.”
Generally 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.


Vision:
Lastly, 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. 
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.

As 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_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper demonstrates generalization on 3 tasks: prefix sum, maze and chess.
A fully convolutional net with a repeated recurrent block was able to generalize to larger input or harder cases without retraining.
A higher amount of recurrent iterations was helpful on the harder cases.
main_review: The paper correctly positions itself as a motivational paper, presenting important questions instead of a recipe for generalization.
The main weakness is that the paper is not aware of the solutions in the previous work:
1) "Neural GPUs Learn Algorithms" ... Neural GPUs generalized to longer inputs.
2) "Value Iteration Networks" ... explained that 2D mazes can be solved perfectly with convolution and max-pooling.
3) "Unbiasing Truncated Backpropagation Through Time" ... the generalization to longer thinking time is related to truncated backprop.

Pros:
- The paper is well written. Nicely readable.
- Generalization to larger inputs and longer thinking time is an important problem.
- The experiments are well done. The comparison to the feedforward nets is informative.
- Nice visualizations of the iterative outputs.
- Nice trick: Allowing to do more iterations and taking the output with the highest confidence.

Cons:
- 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, ...
- The net has not achieved 99% accuracy on the 2D mazes. Value Iteration Networks worked better.
It would be helpful to report also the accuracy on the training set.

Minor typos:
- Line 138: "as" should be "is".
- Line 214: "form" should be "from".
- Figure 5: The input does not seem to correspond to the target.
limitations_and_societal_impact: No negative societal impact.
review_title: null

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)