RobustFill: Neural Program Learning under Noisy I/O

By Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, Pushmeet Kohli. 2017

420 citations recorded by the source corpus.

The problem of automatically generating a computer program from some specification has been studied since the early days of AI. Recently, two competing approaches for automatic program learning have received significant attention: (1) neural program synthesis, where a neural network is conditioned on input/output (I/O) examples and learns to generate a program, and (2) neural program induction, where a neural network generates new outputs directly using a latent program representation. Here, for the first time, we directly compare both approaches on a large-scale, real-world learning task and we additionally contrast to rule-based program synthesis, which uses hand-crafted semantics to guide the program generation. Our neural models use a modified attention RNN to allow encoding of variable-sized sets of I/O pairs, which achieve 92% accuracy on a real-world test set, compared to the 34% accuracy of the previous best neural synthesis approach. The synthesis model also outperforms a comparable induction model on this task, but we more importantly demonstrate that the strength of each approach is highly dependent on the evaluation metric and end-user application. Finally, we show that we can train our neural models to remain very robust to the type of noise expected in real-world data (e.g., typos), while a highly-engineered rule-based system fails entirely.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Natural Language Processing, Reinforcement Learning

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 Natural Language Processing

In Reinforcement Learning

Citations in the corpus

Competition-level code generation with AlphaCode (2022, background): “, 2019), directly generate a target program (Devlin et al., 2017), or even generate programmatic policies in reinforcement learning settings (Trivedi et al.”
Show Your Work: Scratchpads for Intermediate Computation with Language Models (2021, neutral): “Neural networks that accurately represent the semantics of programs could enable a variety of downstream tasks, including program synthesis (Devlin et al., 2017), program analysis (Allamanis et al., 2018), and other algorithmic reasoning tasks (Velickovic & Blundell, 2021).”
Program Synthesis with Large Language Models (2021, methodology): “There has been a recent resurgence of interest in techniques (both symbolic and ‘neuro-symbolic’) for synthesizing programs [Balog et al., 2017, Devlin et al., 2017, Ellis et al., 2018, 2020, Odena et al., 2020], but these techniques have largely been applied to restricted domain-specific languages…”
Evaluating Large Language Models Trained on Code (2021, background): “Finally, Robust-Fill (Devlin et al., 2017) observed that the best way to ﬁnd a program consistent with input examples was to synthesize multiple samples through beam search.”
SPoC: Search-based Pseudocode to Code (2019, background): “However, most synthesized programs are relatively short, and works that consistently synthesize longer programs are in the domains where the intermediate computation is easier to recover from input and output, such as string [11, 28, 6] and data structure transformations [10, 38].”
Learning with Latent Language (2017, positive): “Coupling our inference procedure with an oracle RE evaluator, we essentially recover the synthesis-based approach of Devlin et al. (2017).”
Programmable Agents (2017, background): “Different approaches to this problem focus on networks that infer programs [3, 10, 22], on networks that execute programs [39, 30, 5] and on networks that jointly do both [14, 17, 38, 29, 13]; although there is much overlap between many of these approaches.”
Neural Execution Engines: Learning to Execute Subroutines (2020, background): “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, methodology): “Neural program induction and synthesis (Neelakantan et al., 2016; Reed & De Freitas, 2016; Kaiser & Sutskever, 2016; Parisotto et al., 2017; Devlin et al., 2017; Bunel et al., 2018; Sun et al., 2018) are recently introduced to solve problems by synthesizing computer programs with neural…”
UnifiedSKG: Unifying and Multi-Tasking Structured Knowledge Grounding with Text-to-Text Language Models (2022, neutral): “It is also interesting to compare the results between synthesis tasks like Spider that require predicting programs, and induction-style tasks like WikiTQ and TabFact, where a model directly outputs answers using latent representations of programs (Devlin et al., 2017).”
AutoML-Zero: Evolving Machine Learning Algorithms From Scratch (2020, background): “The synthesized programs—or algorithms—solve problems like sorting, addition, counting [74, 27, 70, 85], string manipulations [64, 61, 19], character recognition [38], competitionstyle programming [5], structured data QA [56, 45, 46],”
Programmatically Interpretable Reinforcement Learning (2018, background): “R OBUST F ILL ( Devlin et al., 2017), D EEP -”
code2seq: Generating Sequences from Structured Representations of Code (2018, methodology): “…code and natural language can be used for automatic code summarization (Allamanis et al., 2016), documentation (Iyer et al., 2016), retrieval (Allamanis et al., 2015b), and even generation (Balog et al., 2016; Rabinovich et al., 2017; Yin and Neubig, 2017; Devlin et al., 2017; Murali et al., 2017).”
Tree-to-tree Neural Networks for Program Translation (2018, background): “A recent line of research study using neural networks for code generation [5, 10, 25, 19, 26, 32].”
Neural Program Synthesis with Priority Queue Training (2018, background): “…et al., 2017; Riedel et al., 2016; Schaechtle et al., 2016; Zaremba et al., 2016; Barone & Sennrich, 2017; Beltramelli, 2017; Cai et al., 2017; Devlin et al., 2017; Hu et al., 2017; Guu et al., 2017; Johnson et al.; Liang et al., 2017; Murali et al., 2017; Parisotto et al., 2016; Rabinovich…”
Neural Program Repair by Jointly Learning to Localize and Repair (2019, background): “…& 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., 2017b; Allamanis et al., 2018), optimization (Bunel et al., 2017), and synthesis (Parisotto et al., 2017; Devlin et al., 2017a).”
Neural Program Meta-Induction (2017, background): “Devlin et al. [5], Duan et al. [6], and Santoro et al. [19] are able to perform induction using as few one I/O example, but these works assume that a large set of background tasks from the same task family are available for training.”
Neural Sketch Learning for Conditional Program Generation (2017, background): “A recent body of work (Parisotto et al., 2016; Balog et al., 2016; Devlin et al., 2017) uses neural techniques to solve this problem.”
Learning to Infer and Execute 3D Shape Programs (2019, background): “Here, we show how a purely end–to–end network can recover 3D graphics programs from voxels, conceptually relevant to RobustFill (Devlin et al., 2017), which presents a purely end-to-end neural program synthesizer for text editing.”