Source-linked AI summary
Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, Sumit Gulwani
TL;DR
Real-time program synthesis from few examples is hindered by exponentially branching deductive search and limited data for purely neural methods. NGDS combines neural branch scoring with deductive search, retaining specification satisfaction while achieving strong generalization and up to 12× speed-up on challenging tasks.
Problem
Deductive search explores exponentially many specification-satisfying branches without estimating their quality, while real-time synthesis requires efficient selection among them.
Method
NGDS combines a branch-and-bound controller using neural score predictions with symbolic deductive search and casts production selection as supervised learning.
Results
NGDS learns intended programs in 68% of scenarios from one example, matches PROSE accuracy, and achieves up to 12× speed-up on challenging tasks.
Takeaways & Limitations
Deep integration of symbolic deductive inference and statistical techniques preserves correctness and generalization while improving synthesis-time performance.
Takeaways & Limitations
Attention-based models improve branch-score ordering but are too expensive at prediction time, and NGDS can be slower than PROSE when controller constraints trigger reevaluation.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Programming by Examples systems must produce correct programs, generalize to unseen inputs, and synthesize quickly, but symbolic and statistical approaches each have important weaknesses. NGDS combines deductive search with neural guidance to retain correctness and generalization while improving synthesis speed on real-world tasks.
- Programming by Examples synthesizes programs from example input-output mappings and is evaluated by correctness, generalization, and synthesis performance.Example-based specifications can be provided by end users without programming skills.
- Symbolic systems produce correct programs by construction and often need only one example, but require substantial engineering and struggle with real-time search.
- Statistical systems are easier to implement and train, but require extensive data, may generalize poorly from few real-world examples, and do not guarantee specification satisfaction.Post-hoc filtering and beam search can undermine real-time performance.
- NGDS combines deductive search with a statistical model and branch-and-bound controller that predicts branch quality and selects sub-problems for exploration.The symbolic search decomposes synthesis into smaller sub-problems using production rules from a domain-specific language.
- Deductive search is Markovian, enabling supervised learning from search decisions at every level, offline trace generation, and separate models for different sub-problem classes.
- On 375 real-world customer scenarios, NGDS generated more than 400,000 intermediate search decisions and achieved intended-program accuracy on 68% of scenarios from one example.NGDS also matched PROSE accuracy while providing up to 12× speed-up on challenging tasks.
- The proposed system uses a neural controller to select grammar rules efficiently and combines symbolic correctness with statistical guidance for real-time synthesis.
2 BACKGROUND
Program-by-example synthesis searches a DSL for programs that satisfy input-output constraints while ranking candidates for generalization. PROSE performs this deductively by decomposing specifications into recursive subproblems, but logical non-determinism can make the search exponential and motivate neural guidance.
- Domain-Specific Language: A domain-specific language (DSL) restricts program expressions to a task domain while keeping the synthesis search space manageable.The DSL is specified as a strongly typed context-free grammar whose productions apply operators to nonterminal symbols.
- Inductive Program Synthesis: Inductive program synthesis seeks programs in a DSL whose outputs satisfy all input-output constraints in a specification.An input state assigns values to program variables, while each output constraint describes the required execution result.
- Domain-Specific Language: In the running FlashFill DSL, programs concatenate constants or substrings extracted from input strings using absolute or regex-based position logic.Substring boundaries may be selected through absolute indices, regex occurrences, or regex pairs surrounding a position.
- Inductive Program Synthesis: A single example can admit overfitting programs, so synthesis ranks satisfying programs by generality, complexity, and behavior on available inputs.The ranking function may penalize overly specific regular expressions and empty outputs while favoring lower Kolmogorov complexity.
- Search Strategy: PROSE explores the DSL top-down, recursively deriving necessary and sufficient specifications for the parameters of each production.Alternative productions are united, while compound productions spawn smaller synthesis problems whose solutions guarantee satisfaction of the parent specification.
- Search Strategy: Logical non-determinism can make deductive search exponential because many branches satisfy the specification even though few produce highly ranked, generalizable programs.NGDS addresses this by predicting branch scores so PROSE can omit branches unlikely to produce the desired program.
3 SYNTHESIS ALGORITHM
NGDS combines deductive search with learned branch scoring and controllers to prioritize promising DSL productions while preserving specification satisfaction. Its search strategy balances speed against generalization by exploring branches near the predicted best or using branch-and-bound criteria.
- Predicting production quality: NGDS learns which production rules are likely to yield top-ranked programs for a specification, reducing branch selection to supervised prediction.The model predicts the score of the best specification-satisfying program obtainable from each production; impossible branches receive −∞.
- Predicting production quality: The score model encodes the specification and production rule with an LSTM-based architecture, optionally attending to input while encoding outputs.Both evaluated models embed the specification, encode the production, and use a feed-forward network to output f(Γ, ϕ).
- Unified neural-guided search: Branch selection must balance performance and generalization because too few branches can miss the intended program, while too many reproduce baseline search costs.The controller framework addresses the failure modes of both single-branch selection and exhaustive exploration.
- Controllers for branch selection: Threshold-based selection explores productions whose predicted scores are within θ of the maximum, reducing to argmax when θ = 0.This controller avoids committing exclusively to the single highest-scored branch when several branches appear nearly equivalent.
- Controllers for branch selection: Branch-and-bound explores branches in descending predicted-score order and continues only when the next branch could improve the current result.It also lowers the number of programs requested from later branches using the next predicted score as a lower bound.
- Unified neural-guided search: NGDS preserves deductive search’s specification-satisfying program construction while exploring only branches likely to produce generalizable programs.The unified algorithm combines PROSE’s symbolic search and ranking function with the learned score model and branch-selection controller.
4 EVALUATION
NGDS is evaluated on real-world string-manipulation tasks against neural and symbolic baselines, measuring generalization accuracy and synthesis time. It improves synthesis speed while retaining strong one-example generalization, though prediction errors and costly neural evaluations can cause slowdowns on some tasks.
- Setup: The evaluation uses 375 real-world customer tasks, with one example supplied as the specification and unseen examples used to assess generalization.Tasks cover applications including date/time formatting, address manipulation, name modification, and email-ID generation.
- Setup: NGDS is compared with RobustFill, DeepCoder, and PROSE using generalization accuracy and synthesis time as the key metrics.The baselines include neural systems and DeepCoder combined with PROSE; synthesis time is measured as wall-clock time median over five runs.
- Results: NGDS saves more than 50% of synthesis time over PROSE on average while remaining significantly more accurate than RobustFill and DeepCoder with one example.The comparison considers tasks requiring PROSE more than 0.5 seconds.
- Results: 12× speed-up is obtained on a common substring-extraction case by selecting the Atom branch and avoiding exhaustive exploration of the expensive Concat operator.Another reported case achieves 2.7× speed-up for extracting “Seattle-WA” from an address string.
- Model trade-offs: Attention models achieve higher score-flip accuracy but are omitted because their prediction cost eliminates potential synthesis speed-ups.Attention-based models reach 99.57/90.4/96.4% train/validation/test accuracy versus 96.09/91.24/91.12% without attention.
- Error analysis: NGDS can be slower than PROSE when inaccurate predictions trigger reconsideration of previously pruned branches and repeated neural-network evaluations.This is especially harmful when early-pruned branches must be revisited while PROSE already completes in under one second.
5 RELATED WORK
Related work spans neural program induction, neural program synthesis, symbolic synthesis, and hybrid search guidance. NGDS differs by guiding recursive deductive search toward generalizable programs using real-world training data while retaining symbolic correctness.
- Neural program induction: Neural program induction systems train neural networks to map example inputs to outputs, ranging from copying and sorting to binary multiplication and recursion.These systems learn program-like behavior directly rather than relying on the deductive search framework described for NGDS.
- Neural program synthesis: Neural program synthesis systems use a pretrained neural network to synthesize programs in a given language, either through sketches or end-to-end generation.Representative approaches include sketch-based systems, R3NN, and RobustFill.
- Hybrid synthesis: DeepCoder guides enumerative synthesis by prioritizing DSL operators according to a specification-driven likelihood distribution.NGDS instead guides search at each recursive level in a top-down, goal-oriented enumeration and trains on real-world data rather than random programs.
- Symbolic synthesis: Symbolic program synthesis includes enumerative search, constraint solving, and inductive logic programming, with roots extending to the 1960s.The cited symbolic approaches represent major traditions in programming-languages research.
- NGDS distinction: NGDS guides search toward generalizable programs while relying on the underlying symbolic engine to generate correct programs.This contrasts with closely related search guidance that need not address generalization.
6 CONCLUSION
The paper presents NGDS as a neural-guided extension of symbolic deductive synthesis for real-time program synthesis from few examples. Its reported advantages are correctness, improved one-example generalization, and faster synthesis, while future work targets better rule-selection models and broader grammars.
- Problem and approach: NGDS addresses real-time program synthesis when only a small number of input-output examples are available.The system builds on PROSE, a symbolic logic-based synthesis system.
- Reported advantages: NGDS guarantees that generated programs satisfy the given input-output specification.This correctness property is attributed to retaining the deductive system’s symbolic foundation.
- Reported advantages: Around 60% of test cases yield the user-intended program from one example, compared with 16% for existing neural synthesis techniques.The conclusion reports this as NGDS’s generalization advantage over the cited neural systems.
- Reported advantages: Most test cases can be solved in less than 0.1 sec while providing performance gains over neural and symbolic systems.The conclusion lists synthesis time as a separate advantage alongside correctness and generalization.
- Future work: The paper identifies better production-rule selection models and applications to more diverse, powerful grammars as future research directions.These directions are proposed after emphasizing integration of symbolic deductive inference with statistical techniques.
A ROBUSTFILL PERFORMANCE WITH DIFFERENT BEAM SIZES
The RobustFill analysis varies beam size and the number of training examples, reporting their effects on generalization accuracy and performance. The supplied passages provide the table’s comparison dimensions but not its individual values.
- Comparison dimensions: RobustFill is evaluated across different beam sizes and numbers of training examples.The table is intended to compare how these settings affect the system’s behavior.
- Reported measures: The table reports RobustFill’s generalization accuracy and performance for each beam-size and training-example configuration.No row-level metric values are included in the supplied passages.
B PERFORMANCE OF BEST NGDS MODEL ON ALL NON-TRAINING TASKS
The table compares PROSE and NGDS across test/validation tasks using runtime, speed-up, and correctness columns.
- The table is organized by task number and test/validation designation.
- Runtime is reported separately for PROSE and NGDS in seconds.
- The comparison includes speed-up and correctness indicators for both systems.
C ML-BASED RANKER
This section evaluates NGDS with a machine-learning-based ranking function against PROSE. The reported comparison shows approximately 2× average speed-up while maintaining comparable generalization accuracy.
- The ranking function is treated as a high-quality black-box component rather than learned within this work.
- NGDS and PROSE are evaluated using a competitive machine-learning-based ranking function.
- ≈2× average speed-up is reported for NGDS over PROSE with comparable generalization accuracy.
- The section includes a table comparing generalization accuracy and speed-up across NGDS variants versus PROSE.