End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking | Summary

This article explains the key points of End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking.

• 2022-02-11 (arXiv), 36th Conference on Neural Information Processing Systems (NeurIPS 2022)
• Bansal, Arpit, Schwarzschild, Avi, Borgnia, Eitan, Emam, Zeyad, Huang, Furong, Goldblum, Micah, Goldstein, Tom.
• University of Maryland, University of Chicago, New York University
• Paper (v3, revised 2022-10-14)

Read this article in Korean

Summary

• The paper asks how a neural network trained on small reasoning problems can solve much larger ones without its answers deteriorating when computation continues. After training on 9 × 9 mazes, its recurrent model with input recall and progressive loss reaches 97.30% peak accuracy on 59 × 59 mazes, compared with 0% for the standard recurrent and feed-forward baselines.
• Input recall supplies the original problem to a shared recurrent block at every iteration; progressive loss trains the block to improve randomly selected intermediate states. On 512-bit prefix sums, or cumulative sums modulo two, after training on 32-bit strings, the combined model reaches 97.12% peak accuracy, while the standard recurrent baseline reaches 0%.
• Experiments also show improved stability on chess puzzles and recovery after perturbations, but the evidence covers three benchmark domains and does not establish universal convergence. Reported averages exclude runs that fail to reach 99% training accuracy, including about half of chess runs.

1 Introduction

Algorithmic extrapolation means solving more difficult test problems using a process learned from easier training examples. Deep Thinking (DT) networks reuse a recurrent block for additional test-time iterations, but their outputs can deteriorate beyond the training regime, a failure the paper calls overthinking [22].

The examples illustrate a model trained on small mazes being applied to much larger inputs by increasing its recurrent computation.

2 Related work

The paper situates its approach among algorithm learning, adaptive computation, and logical extrapolation. It builds on weight-sharing thinking networks that learn complete solutions without supervision of individual algorithmic steps [22]; the authors distinguish these from prior adaptive models primarily evaluated on the training distribution.

3 Methods

A DT network embeds input x with p, applies a shared recurrent block r for m iterations, and maps the resulting features to output with h: f(x;m) = h(r^m(p(x))). The implementation uses a four-layer residual recurrent block and increases m at test time to provide more computation.

3.1 Recall architectures

DT-Recall concatenates the original input with the feature map, the block’s intermediate representation, at each recurrent iteration and uses a convolution to restore the feature shape. This gives the network direct access to the problem even if its evolving features lose information.

3.2 Promoting forward progress through optimization

Progressive training samples n uniformly from {0, …, m−1} and k uniformly from {1, …, m−n}; it computes the first n iterations without gradients, then trains on the result after k further iterations. The objective combines this progressive loss with the full m-iteration loss using weight α, encouraging useful updates from intermediate states.

3.3 Datasets

The easy-to-hard-data benchmark [21] includes prefix sums modulo two, where each output bit is the parity of the input prefix; optimal-path maze solving; and best-move chess puzzles. Training uses 32-bit strings, 9 × 9 mazes, and the 600K easiest chess puzzles; the main chess plot evaluates puzzles 600K–700K, while harder sets are also tested. Section 3.3 describes the test range as 700K–1.1M, whereas Figure 5 and Table 5 use 600K–700K.

4 Extreme extrapolation

Models use at most 30 recurrent iterations during training and are compared with standard DT and equal-effective-depth feed-forward networks. On 512-bit strings, recall with progressive loss peaks at 97.12 ± 1.88% after 237 iterations, versus 96.19 ± 3.73% after 466 iterations for recall alone and 0% for standard DT; the standard DT baseline uses a maximum-confidence exit rule.

On 59 × 59 mazes, recall with progressive loss peaks at 97.30 ± 0.68%, versus 82.72 ± 15.14% for recall alone and 0% for both non-recall recurrent variants and the feed-forward baseline. It solves 74 of 100 tested 201 × 201 mazes exactly; on chess puzzles 600K–700K, its peak is 82.69 ± 0.27%, compared with 78.81 ± 1.04% for standard DT.

On 512-bit inputs, progressive training makes the recall model reach high accuracy substantially sooner than recall alone; models without recall remain much less accurate.

5 The overthinking problem

On 48-bit prefix sums and 13 × 13 mazes, models without recall initially improve but lose accuracy as iterations continue. Recall models remain stable in these tests, while the chess experiment shows that progressive loss is also needed to retain accuracy over many iterations.

Both recall curves outperform the non-recall models on 59 × 59 mazes, and the progressive-loss curve reaches a higher plateau.

The combined model retains its chess accuracy as iterations increase, whereas the other recurrent variants eventually decline.

5.1 Manipulating feature maps

Adding zero-mean, unit-standard-deviation Gaussian noise to maze features after one iteration leaves recall models able to solve 13 × 13 mazes, while models without recall fail. When features are zeroed after 50 iterations, recall models regenerate a representation and solve the maze again.

The dashed non-recall curves peak and then decline on both tasks, while recall curves stay near their high accuracy.

5.2 Manipulating inputs

After a bit is flipped in an already solved 48-bit prefix-sum input, recall models recover, with recovery time decreasing for later bit positions. When features from a different maze are substituted after 50 iterations, recall models recover the solution for the maze still supplied as input.

5.3 Converging to a fixed point

The authors measure the Euclidean norm of the difference between successive feature maps. This difference decreases for recall models and grows for models without recall in the displayed maze experiment, providing empirical evidence consistent with convergence rather than a proof of it.

6 Conclusion

The authors conclude that recall and progressive training improve easy-to-hard generalization while reducing observed overthinking. They explicitly limit their findings to the tested domains and call for evaluation in other settings.

The panels show recovery after a bit flip, recovery after swapping maze features, and decreasing feature changes for recall models.

Appendix

• A.1–A.4 specify architectures, resources, loss, and hyperparameters: widths are 400 for prefix sums, 128 for mazes, and 512 for chess; training uses Nvidia GeForce RTX 2080Ti GPUs. Prefix sums train in under one hour on one GPU, mazes in up to eight hours on one GPU, and chess in 24–48 hours on four GPUs; 20% of training data is held out for validation. The loss averages binary classification loss over positions and examples, with α controlling the progressive term.
• A.5–A.8 report extended and in-distribution results, hard-to-easy tests, and perturbation studies. Runs below 99% training accuracy are excluded from reported averages; harder chess results show an apparent generalization ceiling, and models without recall also overthink on easier 24-bit inputs. The appendix also reports validation on problems of the same difficulty as training and recovery from feature perturbations.
• A.9 and A.10 show 201 × 201 and 801 × 801 maze examples. The paper gives inconsistent iteration counts for the 801 × 801 example: Section 4 says 20,000, while its figure caption says 10,000.

Brief Thoughts

The ablations support distinct roles for the two changes: recall enables large-maze extrapolation, and progressive loss improves its accuracy and speeds up the 512-bit prefix-sum solution. The excluded unconverged runs and the limited task set qualify the reported gains, and the feature-map measurements demonstrate observed stability rather than guaranteed convergence.