Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper is focused on training networks to solve problems via extrapolation, e.g. solving large mazes by learning to solve small mazes. In order to achieve this, two modifications to recurrent convolutional networks are proposed: a) adding a concatenating skip connection from the input to the recurrent layers that stabilizes extrapolation (Fig. 2), and b) using a modified training method and loss that encourages the network to learn computations independent of current iteration (Alg. 1). Together, these techniques lead to substantial improvements in results on the problems of computing prefix sums, solving 2D mazes and solving chess puzzles.
main_review: The paper is well written and easy to read and understand. It builds directly on recent work by Schwarzschild et al. [2021a, 2021b, 2021c], and is essentially about addressing the limitations of that work on the challenging tasks identified in that work that involve learning from "easy" instances of a task and generalizing to "hard" instances. This is an interesting line of work that could lead to useful insights, and this paper's contributions certainly to make significant progress on the challenges considered.

In particular, the authors have already conducted various analyses to answer follow-up questions that a curious reader might have (and I had) about the working of the proposed techniques. The results of these experiments will be very useful and instructive to readers interested in these problems.

I would like to point out two "weaknesses" of this paper:

1. The first out of the proposed two techniques, the Recall skip connection, appears to be fixing what one may call a mistake made by Schwarzschild et al. in recent work during model design. This is because if one looks at prior literature on models that are stable when unrolled longer than training time, one immediately find this model design, based on theoretical insights from control theory, see Ciccone et al. [A] and the non-autonomous networks therein. This is not to say that the contribution of this paper isn't useful, but it should be put in context of past work that has already established strong theoretical results directly related to the behavior of interest. I find it interesting that in this paper, no conditions on weights were necessary in practice to achieve stability.

2. I'm concerned that the authors are playing fast and loose with the term "thinking" in this line of work. This is very loaded metaphor, and in my opinion every paper that decides to use it must at least include a clear note that "thinking" is just a fancier term for a particular type of processing here, and these networks are not really thinking in any regular sense of the term. Otherwise, we can say that any classifier or detector is also thinking. I realize that this is not just something unique to this paper and some other papers have used such terms without such clarification, but this is only a review of this paper, and I'd appreciate if the authors think about this issue and try to do better than prior work.

[A] Ciccone, M., Gallieri, M., Masci, J., Osendorfer, C., & Gomez, F. (2018). Nais-net: Stable deep networks from non-autonomous differential equations. arXiv preprint arXiv:1804.07209.
summary_of_the_review: The paper proposes simple techniques that clearly addresses the limitations of recent work on solving tasks in the easy-to-hard benchmark dataset.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes two extensions to the recently proposed recurrent 'thinking systems', in order to enable them to better generalize from training on simple problems to testing on more complex problems. The proposed extensions involve 1) giving the model access to a cure indicating the to-be-solved problem at each time step ('recall') and 2) a method intended to prevent the model from learning behaviors specific to particular iterations (so as to enable generalization to more complex problems via a larger number of iterations). When combined, these extensions enable generalization to significantly more complex problem instances across three separate task domains.
main_review: Both the underlying approach, and the proposed extensions, are compelling, and the results are promising. It is good to see results across a range of task domains. The analyses on convergence and overthinking in the latter part of the paper are also very nice. I think there are a few issues that need to be sorted out, but am happy to raise my score if the authors can address these concerns:

- The only baseline considered is a feedforward version of the primary model (i.e. in which parameters are not shared across iterations). This seems like a good comparison, but other baselines should be considered as well. How important is the particular recurrent architecture employed here, in which the output is fed back into the model as input? How might an LSTM, with a recurrent hidden state, or a model with an external memory, perform on the generalization benchmarks that are considered in this paper?
- The proposed 'progressive loss' seems to be useful primarily for getting these kinds of models to solve the task in the shortest number of iterations of possible. The reason seems to be that a model trained only on a fixed number of iterations has no reason to arrive at the correct answer any sooner than the point at which a loss will be computed. Given that, I wonder whether the proposed method is the simplest or best way to accomplish this. Would it work to simply train models on a randomly sampled number of iterations, or to penalize longer processing (as is done in 'adaptive computation time')? It would be good to compare the proposed approach to these alternatives.
- In the appendix, the authors state that 'when we compute averages, we only include models that trained beyond a threshold training accuracy.' Does this mean that the reported results are only for a subset of models that reached some training criterion? How many models failed to reach this criterion, and are the results qualitatively different when no such criterion is used?
- Models are evaluated by taking the iteration with the highest confidence, rather than simply using the final iteration. Do the models still perform just as well at generalization to more complex problems if the final iteration is used? 
- On the prefix sum and maze problems, the 'recall' element seems to be useful primarily for preventing the 'overthinking' phenomenon, and, for those task domains, this element of their proposal appears to be highly effective (as it prevents overthinking even without the 'progressive loss'). However, on the chess problems, the version of the model with recall, but without the 'progressive loss', still suffers from overthinking. What might explain this discrepancy?

Minor issues and additional questions:

- How does confidence evolve over time? Do the models generally become more confident with a greater number of iterations? If so, could confidence be used as a signal for autonomously selecting how many iterations to perform, rather than having to select this by hand?
- When reading the paper for the first time, it is unclear where the results in Figure 1 come from. I'm assuming these results employ both of the proposed extensions, but it would be helpful to specify that this is the case (i.e. that 'vanilla' thinking systems would not be capable of producing these results).
- The legend for table 1 of the appendix says 'perfrom' instead of 'perform'.
- The legend for table 4 in the appendix references the prefix sum task, but the table appears to contain results from the maze task.
- At the end of the main section with results on the maze task, the reader is directed to section A.3 to see an example of a 201x201 maze, but this is actually in section A.7.



summary_of_the_review: The proposed approach is compelling, and the results are promising, but there are a few issues that needed to be sorted out, including some additional baselines, and clarification of the selection criteria for the reported results.

Update after discussion period: the authors included a number of supplementary results and informative additional control experiments. I still think that the results would be more convincing if compared to a broader range of competitive baselines, but I think these new results/experiments are a significant enough improvement to merit a score increase.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes two modifications to recurrent neural networks that help improve generalization on three synthetic tasks. In particular, the authors implement a recall mechanism through residual connections to prevent the recurrent network from losing original input information after many iterations. In addition, they randomly apply truncated backpropagation through time to the computation graph to build an auxiliary loss, which diminishes overfitting to the number of recurrent steps. The trained network can solve significantly harder problems by performing more recurrent iterations, showing strong generalization ability.

main_review: Pros:
- The paper gives solid extensions to the idea of deep thing networks (Schwarzschild et al., 2021). The writing is generally clear and easy to follow. The modifications are well-motivated,  addressing the weaknesses of the original model.
- The experiments demonstrate well the effectiveness of the modifications, outperforming the baselines by a significant margin. There are detailed ablation studies and behaviour analyses that give insights into the inner working of the model.  
Cons:
- The modifications are incremental, using common techniques like residual connection and truncated backpropagation through time. Unsurprisingly, using these techniques will help improve the performance. 
- The tasks are toyish. It would be more persuasive if the method could work for realistic data or some classical benchmarks. 
- The main manuscript misses some details of the method (see questions below).

Overall, I like the idea of this paper, which proposes an interesting way to exhibit logical generalization by allowing recurrent networks to "think" more during inference. However, as mentioned above, compared to the original work, the proposed modifications are marginal. It is straightforward that using residual connections is critical to training deep networks (to combat missing input information or gradient vanishing, etc.).  The progressive loss is more interesting, yet it is unclear from the writing that this is a novel contribution to the training of RNNs (e.g., compared to other auxiliary training for RNN as in Trinh et al., (2018), what is the difference and advantage of using the proposed method). 

Regarding experimental results, only Chess Puzzle data seems real. But here, the result is not impressive as there is only a 4% improvement in terms of peak accuracy. The performance of the proposed method on the other two synthetic data is promising.  I am curious whether the method only works for these specific tasks or is extendable to other problems: sequential inputs such as Copy, Associative Recall, graph reasoning (Graves et al., 2016) or natural data (text, images).

Questions and comments:

- It is reasonable to use CNN architecture for image-like inputs. However, for prefix-sum, the input is a sequence of 0 and 1. Did you apply CNN here? 
- What is the loss function? To make the paper self-contained, in Sec. 3 or 4, you should describe the output format and the loss used to train the model (from Appendix A, it seems that the final output is a 2d bitmap?).
- The procedure of selecting the inference iteration for performance measurement should be mentioned in the main manuscript. 
- The analysis would be more informative if the authors could compare the results of other iterations with that of the peak one (how much difference? Did they converge to the final output as suggested in Fig. 9?)
- For prefix-sum, did you test with longer sequences? Can your method generalize to 1024-bit? Why there is no performance visualization for maze 201x201?
- In the paper, the feed-forward model is a weak baseline. The experiments could be stronger with advanced architectures such as Transformer or self-attention model.  
- Fig. 8, More explanation on why the new loss helped more in the setting will be appreciated.
- Fig. 9, the y-axis values go up to 10^10. How's that possible? How does the new loss help in this case?
summary_of_the_review: Overall, I like the idea of this paper, However, compared to the original work, the proposed modifications are marginally significant.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes two modifications to recurrent neural networks that enable them to extrapolate to larger problems than seen during training.

The problems (generalizations) are 
1) pathfinding in a maze (larger mazes), 
2) binary prefix sums (larger bit strings)
3) Evaluate the best chess move given a position (harder positions).

The modifications are: 

1) Add the initial problem features to every step of the recurrent computation, coined "recall" in the paper.
2) train on a combination of a regular loss with m recurrent iterations and with a loss with m=n+k iterations where the gradient is not tracked for the first n iterations.

The paper shows that the modified recurrent network learns an algorithm that converges to the correct result with more recurrent iterations, thus overcoming the problem of "overthinking" (divergence really) as coined in earlier papers. 

The paper further shows that the learned convergent algorithm "extrapolates" to larger/harder problems. For instance, the networks are trained on 32-bit strings, and evaluated on 512-bit strings, and trained on 9x9 mazes and evaluated on up to 201x201 mazes.

The paper compares their method, ablations w.o. "recall" and modified loss, MLPs and MLPs with "recall", and show that only their proposed network learns a convergent solution that extrapolates to the larger/harder problem instances.
main_review: Strengths:
 - The paper clearly states the problem, and convincingly shows a solution.
 - The paper is pretty well written

Weakness
 - The paper is evaluated on a very new dataset, which seems ideal for the kind of method suggested, and the only real comparison is the work they directly build on. You can always find a dataset for which your method is the best, and this paper has a bit of that feeling. Except for the chess positions the examples are new and toy-like. Why do we need these new benchmarks? Why not evaluate on some more standard benchmarks, e.g. image classification/segmentation, simple QA (bAbI for instance), etc. 
Also the bit sums and maze path finding are trivially solved with standard hand-coded algorithms. Why would you want to use a neural net on them? If the benchmarks are not interesting problems in their own right, they might still be nice benchmarks because they nicely exemplify some specific problematic environments, but then it must be very clearly explained how this ties back into (better) solving real-world problems. The chess positions task is the nicest example problem, but then again, how does this compare to something like AlphaZero, or any other modern MCTS approach? What's the benefit? Computational? Generalization? This must be explicitly explained.

 - The paper doesn't discuss and compare to the very relevant work "Recurrent Relational Networks" (RRN) [1]. RRNs are recurrent graph neural networks, and very very similar. Both neworks have the same output(recurrent_with_recall(embed(x))) structure and the RRN measures a loss on every step of recurrent computation similar to the modified loss. The RRN also learns a convergent algorithm and generalizes to harder tasks. I would very much appreciate a comparison to a RRN network in all of the new benchmarks, or conversely evaluating on some of the same benchmarks as in [1]. I suspect the performance will be very similar for the two networks.

 - The loss weight alpha hyperparameter is kind of inelegant. Have the authors tried simply measuring a loss on every recurrent iteration like in [1]? This would also encourage a convergent algorithm, and would be simpler.

[1] - Palm, R. B., Paquet, U., & Winther, O. (2018). Recurrent Relational Networks. In 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada (Vol. 31, pp. 3368-2278).
summary_of_the_review: Decent paper, but should be evaluated on more common benchmarks / less toy settings and should discuss and compare to [1].
review_title: null

Meta-review: This is an interesting work, and I urge the authors to keep pushing this direction of research. Unfortunately, I feel like the manuscript, in its current format is not ready for acceptance.

The research direction is definitely under-explored, which makes the evaluation of the work a bit tricky. Still I think that some of the points raised by the reviewers hold, for e.g. the need of additional baselines (to provide a bit of context for what is going on)I understand that the authors view their work as an improvement of the previously proposed DT network, however that is a recent architecture, not sufficiently established not to require additional baseline for comparisons. This combined with the novely of the dataset makes it really hard to judge the work. 

The write-up might also require a bit of attention. In particular it seems a lot of important details of the work (or clarifications regarding the method) ended up in the appendix. A lot of the smaller things reviewer pointed out the authors rightfully so acknowledged in the rebuttal and propose to fix, however I feel this might end up requiring a bit of re-organization of the manuscript rather that adding things at the end of the appendix. I also highlight (and agree) with the word "thinking" being overloaded in this scenario.

Ablation studies (some done as part of the rebuttal) might be also a key component to get this work over the finish line. E.g. the discussion around the progressive loss. I acknowledge that the authors did run some of those experiments, though I feel a more in depth look at the results and interpretation of them (e.g. not looking just at final performance, but at the behaviour of the system), and integrating them in the main manuscript could also provide considerable additional insight in the proposed architecture. 

My main worry is that in its current format, the paper might not end up having the impact it deserves and any of the changes above will greatly improve the quality and the attention the work will get in the community.
Decision: Reject