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

arXiv: https://arxiv.org/abs/1804.01186 · HTML: https://mlsanity.com/paper/1804.01186/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2018.

## Built on by (most cited first, 30 of 39)

- [Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation](https://mlsanity.com/paper/2305.01210/) (2023)
- [Learning Performance-Improving Code Edits](https://mlsanity.com/paper/2302.07867/) (2023)
- [From Statistical Relational to Neurosymbolic Artificial Intelligence: a Survey](https://mlsanity.com/paper/2108.11451/) (2021)
- [How Efficient is LLM-Generated Code? A Rigorous & High-Standard Benchmark](https://mlsanity.com/paper/2406.06647/) (2024)
- [SpreadsheetCoder: Formula Prediction from Semi-structured Context](https://mlsanity.com/paper/2106.15339/) (2021)
- [A Survey on Neural-symbolic Learning Systems](https://mlsanity.com/paper/2111.08164/) (2021)
- [Latent Execution for Neural Program Synthesis](https://mlsanity.com/paper/2107.00101/) (2021)
- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [InstructABSA: Instruction Learning for Aspect Based Sentiment Analysis](https://mlsanity.com/paper/2302.08624/) (2023)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis](https://mlsanity.com/paper/2405.15880/) (2024)
- [Self-explaining deep models with logic rule reasoning](https://mlsanity.com/paper/2210.07024/) (2022)
- [Neurosymbolic Repair for Low-Code Formula Languages](https://mlsanity.com/paper/2207.11765/) (2022)
- [Context-NER : Contextual Phrase Generation at Scale](https://mlsanity.com/paper/2109.08079/) (2021)
- [Program Synthesis Guided Reinforcement Learning for Partially Observed Environments](https://mlsanity.com/paper/2102.11137/) (2021)
- [Learning to Combine Per-Example Solutions for Neural Program Synthesis](https://mlsanity.com/paper/2106.07175/) (2021)
- [NL2Formula: Generating Spreadsheet Formulas from Natural Language Queries](https://mlsanity.com/paper/2402.14853/) (2024)
- [Program Synthesis with Best-First Bottom-Up Search](https://mlsanity.com/paper/2310.04327/) (2023)
- [Scaling Neural Program Synthesis with Distribution-based Search](https://mlsanity.com/paper/2110.12485/) (2021)
- [From Examples to Rules: Neural Guided Rule Synthesis for Information Extraction](https://mlsanity.com/paper/2202.00475/) (2022)
- [Learning to Improve Code Efficiency](https://mlsanity.com/paper/2208.05297/) (2022)
- [Learning Program Behavioral Models from Synthesized Input-Output Pairs](https://mlsanity.com/paper/2407.08597/) (2024)
- [BF++: a language for general-purpose program synthesis](https://mlsanity.com/paper/2101.09571/) (2021)
- [EDM3: Event Detection as Multi-task Text Generation](https://mlsanity.com/paper/2305.16357/) (2023)
- [Synthesizing Programs with Continuous Optimization](https://mlsanity.com/paper/2211.00828/) (2022)
- [Bayesian Program Learning by Decompiling Amortized Knowledge](https://mlsanity.com/paper/2306.07856/) (2023)
- [NeuroCERIL: Robotic Imitation Learning via Hierarchical Cause-Effect Reasoning in Programmable Attractor Neural Networks](https://mlsanity.com/paper/2211.06462/) (2022)
- [Transformer Models for Type Inference in the Simply Typed Lambda Calculus: A Case Study in Deep Learning for Code](https://mlsanity.com/paper/2304.10500/) (2023)
- [Can You Improve My Code? Optimizing Programs with Local Search](https://mlsanity.com/paper/2307.05603/) (2023)
- [Learning Heuristics for Template-based CEGIS of Loop Invariants with Reinforcement Learning](https://mlsanity.com/paper/2107.09766/) (2021)

## Abstract (arXiv)

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.