Making Neural Programming Architectures Generalize via Recursion

By Jon Z. Cai, Jonathon Cai, Richard Shin, Dawn Song. 2017

153 citations recorded by the source corpus.

Empirically, neural networks that attempt to learn programs from data have exhibited poor generalizability. Moreover, it has traditionally been difficult to reason about the behavior of these models beyond a certain level of input complexity. In order to address these issues, we propose augmenting neural architectures with a key abstraction: recursion. As an application, we implement recursion in the Neural Programmer-Interpreter framework on four tasks: grade-school addition, bubble sort, topological sort, and quicksort. We demonstrate superior generalizability and interpretability with small amounts of training data. Recursion divides the problem into smaller pieces and drastically reduces the domain of each neural network component, making it tractable to prove guarantees about the overall system's behavior. Our experience suggests that in order for neural architectures to robustly learn program semantics, it is necessary to incorporate a concept like recursion.

Subfields: Artificial Intelligence, Materials Chemistry, Natural Language Processing

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 Materials Chemistry

In Natural Language Processing

Citations in the corpus

Chain of Thought Prompting Elicits Reasoning in Large Language Models (2022, neutral): “Recent work along in this direction has included a number of architectural innovations (Cai et al., 2017; Dong et al., 2019; Yan et al., 2020), as well as the use of large language models (Chen et al.”
Programmable Agents (2017, background): “The majority of these works model their networks after an imperative programming style, although researchers have also begun to explore structuring their networks as functional (recursive) programs as well [7, 30].”
Scalable agent alignment via reward modeling: a research direction (2018, background): “Examples include modularity (Anonymous, 2019b), recursion (Cai et al., 2017), graph structure (Battaglia et al., 2018) or natural language (Andreas et al., 2018) in the latent space, differentiable external memory (Graves et al., 2016), or neural units designed to perform arbitrary arithmetic…”
Supervising strong learners by amplifying weak experts (2018, methodology): “Recursive model architectures: our work differs from recursive model architectures (Cai et al., 2017; Nowak and Bruna, 2016), in that the learned model doesn’t have a recursive structure.”
Neural Execution Engines: Learning to Execute Subroutines (2020, methodology): “Work in neural program synthesis [16, 18, 5, 1, 6]—which uses neural networks with the goal of generating and ﬁnding a “correct” program such that it will generalize beyond the training distribution—has also employed strong supervision in the form of execution traces [20, 21, 2].”
Neural Logic Machines (2019, background): “Some works tackle the issue of the systematical generalization by introducing extra supervision (Cai et al., 2017).”
Measuring Coding Challenge Competence With APPS (2021, background): “Inductive synthesis from example input-output behavior can provide an alternative to formal specification (Cai et al., 2017; Gulwani et al., 2017), but it is often hard to full specify behavior with examples, as any machine learning practitioner is well-aware.”
Relational Neural Expectation Maximization: Unsupervised Discovery of Objects and their Interactions (2018, background): “…(Battaglia et al., 2016; Chang et al., 2016), playing games (Denil et al., 2017; Kansky et al., 2017), learning algorithms (Bošnjak et al., 2017; Cai et al., 2017; Li et al., 2016; Reed & De Freitas, 2015), visual understanding (Ellis et al., 2017; Johnson et al., 2017), and natural language…”
Automatically Composing Representation Transformations as a Means for Generalization (2018, background): “The ﬁrst as-Automatically sumes pre-speciﬁed transformations and learns the structure (from dense supervision on execution traces to sparse-rewards) [13, 14, 18, 22, 25, 28, 65, 87, 90].”
Lifelong Learning of Compositional Structures (2020, background): “The majority of such methods either learn the structure for piecing together a given set of components [30, 4, 5] or learn the set of components given a known structure for how to compose them [3].”
Neural Program Synthesis with Priority Queue Training (2018, background): “…there have been promising results on the task of binary search (Nachum et al., 2017a), sorting an array of numbers (Reed & de Freitas, 2016; Cai et al., 2017), solving simple Q&A from tables (Neelakantan et al., 2016; 2017), visual Q&A (Andreas et al., 2016; Hu et al., 2017; Johnson et al.)”
Neural Program Repair by Jointly Learning to Localize and Repair (2019, background): “…(Gupta et al., 2017; Bhatia et al., 2018), program parse trees (Piech et al., 2015; Mou et al., 2016), program traces (Reed & de Freitas, 2015; Cai et al., 2017; Wang et al., 2018), and graphs (Allamanis et al., 2018) have been proposed for a variety of tasks including repair (Devlin et al.,…”
Decomposed Prompting: A Modular Approach for Solving Complex Tasks (2022, background): “Neural Programming Our work also relates to work on neural programming architectures (Reed & De Freitas, 2016; Neelakantan et al., 2016; Cai et al., 2017), which aims at building neural models that can represent and execute compositional programs, often focusing on algorithmic tasks of the type we…”
Neural Program Meta-Induction (2017, background): “…NTM [7], Stack RNN [11], NRAM [12] Neural Transducers [8], Learn Algo [21] Others [4, 20, 2, 13] Trace-Augmented Induction NPI [18] Recursive NPI [3], NPL [14] Non Example-Driven Induction (e.g., Natural Language-Driven Induction) Inducing Latent Programs [16] Neural Module Networks [1] k -shot…”
Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks (2020, unknown): “In contrast, neural algorithm induction [7, 9–12, 14, 15, 19] introduces architectures that are specially suited to learning algorithms from large numbers of input-output examples.”
Neural Symbolic Reader: Scalable Integration of Distributed and Symbolic Representations for Reading Comprehension (2020, background): “This is especially challenging for pure neural network approach, because discrete operators like addition and sorting learned by neural networks can hardly generalize to inputs of arbitrary size without specialized design (Reed & de Freitas, 2016; Cai et al., 2017; Kaiser & Sutskever, 2015).”
Deep learning type inference (2018, background): “is not out of the scope of these models, as was demonstrated for neural program inference using recursion [11].”
Learning to Synthesize Programs as Interpretable and Generalizable Policies (2021, background): “[31] Jonathon Cai, Richard Shin, and Dawn Song.”
Regression Planning Networks (2019, methodology): “Our network architecture design is inspired by recursive networks for natural language syntax modeling [20, 21] and program induction [22, 23].”