Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples

By Ashwin K. Vijayakumar, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, Sumit Gulwani. 2018

178 citations recorded by the source corpus.

Synthesizing user-intended programs from a small number of input-output examples is a challenging problem with several important applications like spreadsheet manipulation, data wrangling and code refactoring. Existing synthesis systems either completely rely on deductive logic techniques that are extensively hand-engineered or on purely statistical models that need massive amounts of data, and in general fail to provide real-time synthesis on challenging benchmarks. In this work, we propose Neural Guided Deductive Search (NGDS), a hybrid synthesis technique that combines the best of both symbolic logic techniques and statistical models. Thus, it produces programs that satisfy the provided specifications by construction and generalize well on unseen examples, similar to data-driven systems. Our technique effectively utilizes the deductive search framework to reduce the learning problem of the neural component to a simple supervised learning setup. Further, this allows us to both train on sparingly available real-world data and still leverage powerful recurrent neural network encoders. We demonstrate the effectiveness of our method by evaluating on real-world customer scenarios by synthesizing accurate programs with up to 12x speed-up compared to state-of-the-art systems.

Subfields: Artificial Intelligence, Hardware and Architecture, Information Systems

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 Hardware and Architecture

In Information Systems

Citations in the corpus

Learning to Infer Graphics Programs from Hand-Drawn Images (2017, methodology): “Neurally Guided Deductive Search (NGDS: [17]) is a recent neurosymbolic approach; combining our work with ideas from NGDS could be promising.”
Program Synthesis and Semantic Parsing with Learned Code Idioms (2019, background): “In the last decade, it has advanced dramatically thanks to the novel neural and neuro-symbolic techniques [5, 10, 19], ﬁrst mass-market applications [28], and massive datasets [9, 39, 41].”
Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation (2023, methodology): “program synthesis techniques have been developed, including deductive synthesis [18, 31, 53], programming by examples [19, 48] and neural-guided synthesis [25].”
Robust Text-to-SQL Generation with Execution-Guided Decoding (2018, methodology): “This line of work includes DeepCoder (Balog et al. 2017), Neurosymbolic synthesis (Parisotto et al. 2017), Neo (Feng et al. 2018), and NGDS (Kalyan et al. 2018).”
Neural Guided Constraint Logic Programming for Program Synthesis (2018, methodology): “Contributions generally fall under three general categories: differentiable programming [1, 2, 3], direct synthesis [4, 5], and neural guided search [6, 7].”
AutoPandas: neural-backed generators for program synthesis (2019, methodology): “One class of machine learning approaches predict programs directly using neural networks [Devlin et al. 2017; Parisotto et al. 2017] while another employs neural networks to guide the symbolic techniques above [Balog et al. 2016; Bunel et al. 2018; Kalyan et al. 2018].”
Synthetic Data for Deep Learning (2019, background): “Learning-based program synthesis (earlier attempts were based on logical inference [392]) began with learning string manipulation programs [218] and soon branched into deep learning, using recurrent architectures to guide search-based methods [614] or to generate programs in encoder-decoder architec”
Learning Performance-Improving Code Edits (2023, background): “Recent work leverages machine learning to assist program synthesis (Balog et al., 2016; Bunel et al., 2018; Devlin et al., 2017a;b; Kalyan et al., 2018; Parisotto et al., 2016; Odena & Sutton, 2020; Nye et al., 2019; Meng et al., 2011; Jain et al., 2022; Austin et al., 2021; Xiong & Wang, 2022; Camb”
Automatic Program Synthesis of Long Programs with a Learned Garbage Collector (2018, result): “This is in contrast to some recent work [8, 5, 16], focused on string processing, where success is measured on unseen samples.”
Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks (2020, background): “whether it will be useful in the search [16].”
SpreadsheetCoder: Formula Prediction from Semi-structured Context (2021, methodology): “On the other hand, in (Vijayakumar et al., 2018), they design a neural network to guide the deductive search performed by PROSE (Polozov & Gulwani, 2015), a commercial framework for input-output program synthesis.”
Grounded Copilot: How Programmers Interact with Code-Generating Models (2022, background): “…captured our imagination for several decades now, giving rise to a rich body of work from both the programming languages [Ferdowsifard et al. 2020; Miltner et al. 2019; Ni et al. 2021; Raychev et al. 2014] and the machine learning [Guo et al. 2021; Kalyan et al. 2018; Xu et al. 2020] communities.”
Neurosymbolic Programming (2021, methodology): “NGDS learns a policy π : φ → Rk, where k denotes the number of sub-problems at a given search depth to prioritize selection of promising sub-problems amongst all possible decompositions.”
HOUDINI: Lifelong Learning as Program Synthesis (2018, background): “A few recent approaches to program synthesis do combine symbolic and neural methods [11, 6, 12, 28, 18].”
A large-scale benchmark for few-shot program induction and synthesis (2021, methodology): “Machine learning, and deep learning in particular, have been increasingly used to improve the search over programs (Parisotto et al., 2016; Kalyan et al., 2018; Brockschmidt et al., 2018; Ellis et al., 2019; Nye et al., 2020).”
Jigsaw: Large Language Models meet Program Synthesis (2021, methodology): “The literature on using machine learning for program synthesis is vast [8, 17, 18, 21, 22, 25, 28, 35, 41] and we restrict to works which are closest to Jigsaw (synthesizing code for large APIs using large models and multi-modal specifications).”