Title: Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples,
Abstract: 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.