Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks

By Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, Tom Goldstein. 2021

115 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Model Architectures

Citations in the corpus

Least-to-Most Prompting Enables Complex Reasoning in Large Language Models (2022, methodology): “In this respect, it shares the same spirit as the methods in (Graves, 2016; Dehghani et al., 2019; Dong et al., 2019; Schwarzschild et al., 2021; Wang et al., 2021; Wei et al., 2022; Wang et al., 2022).”
Measuring and Narrowing the Compositionality Gap in Language Models (2022, background): “…to solve harder problems has been previously explored in both language (Graves, 2016; Seo et al., 2017; Dong et al., 2019; Schwartz et al., 2020; Schwarzschild et al., 2021; Nye et al., 2021; Wei et al., 2022b; Zhou et al., 2022) and vision (Bolukbasi et al., 2017; Huang et al., 2018; Wang et…”
Faith and Fate: Limits of Transformers on Compositionality (2023, background): “for A(x) x = [7,49] function multiply (x[1.”
Weak-to-Strong Generalization: Eliciting Strong Capabilities With Weak Supervision (2023, methodology): “We use the dataset originally introduced in Schwarzschild et al. (2021b), which contains chess puzzles from the lichess . org website (lic).”
Large Language Models Are Zero-Shot Time Series Forecasters (2023, background): “It is likely that the limitations on compute and tokens spent may make this composition unnecessarily hard, and that additional recursive structure, for example from a scratchpad [33], Chain of Thought (CoT) prompting [47], or adaptive computation [41, 3], would make this task easier.”
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes (2022, background): “Another line of work aims to discover algorithms that perform well on a distribution of inputs [27, 75, 70, 3, 29, 64, 63] (as opposed to algorithms with guarantees on their worst-case performance).”
Combinatorial optimization and reasoning with graph neural networks (2021, methodology): “While initially applied only to path-finding and spanning-tree algorithms, the prescriptions listed above have been applied for heuristically solving bipartite matching (Georgiev and Lió, 2020), mazes (Schwarzschild et al., 2021; Bansal et al., 2022), max-flow/min-cut (Awasthi et al.”