# Neural Program Synthesis with Query

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 49 references that are in the map.
- First posted on arXiv 8 May 2022.

## Builds on (most cited first, 24 of 24)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [InfoGAN: Interpretable Representation Learning by Information Maximizing Generative Adversarial Nets](https://mlsanity.com/paper/1606.03657/) (2016)
- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs](https://mlsanity.com/paper/2010.11465/) (2020)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [Write, Execute, Assess: Program Synthesis with a REPL](https://mlsanity.com/paper/1906.04604/) (2019)
- [Deep Active Learning: Unified and Principled Method for Query and Training](https://mlsanity.com/paper/1911.09162/) (2019)
- [Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis](https://mlsanity.com/paper/1805.04276/) (2018)
- [Learning to Infer Graphics Programs from Hand-Drawn Images](https://mlsanity.com/paper/1707.09627/) (2017)
- [Learning to Infer and Execute 3D Shape Programs](https://mlsanity.com/paper/1901.02875/) (2019)
- [Synthesize, Execute and Debug: Learning to Repair for Neural Program Synthesis](https://mlsanity.com/paper/2007.08095/) (2020)
- [BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration](https://mlsanity.com/paper/2007.14381/) (2020)
- [Automatic Program Synthesis of Long Programs with a Learned Garbage Collector](https://mlsanity.com/paper/1809.04682/) (2018)
- [Learning to Represent Programs with Property Signatures](https://mlsanity.com/paper/2002.09030/) (2020)
- [Synthetic Datasets for Neural Program Synthesis](https://mlsanity.com/paper/1912.12345/) (2019)
- [Interactive Program Synthesis](https://mlsanity.com/paper/1703.03539/) (2017)
- [Neural Program Synthesis with a Differentiable Fixer](https://mlsanity.com/paper/2006.10924/) (2020)
- [FlashProfile: A Framework for Synthesizing Data Profiles](https://mlsanity.com/paper/1709.05725/) (2017)
- [Learning to Acquire Information](https://mlsanity.com/paper/1704.06131/) (2017)
- [Information-Geometric Set Embeddings (IGSE): From Sets to Probability Distributions](https://mlsanity.com/paper/1911.12463/) (2019)

## Built on by (most cited first, 2 of 2)

- [Online Symbolic Regression with Informative Query](https://mlsanity.com/paper/2302.10539/) (2023)
- [Deterministic Graph-Walking Program Mining](https://mlsanity.com/paper/2208.10290/) (2022)

## Abstract (arXiv)

Aiming to find a program satisfying the user intent given input-output examples, program synthesis has attracted increasing interest in the area of machine learning. Despite the promising performance of existing methods, most of their success comes from the privileged information of well-designed input-output examples. However, providing such input-output examples is unrealistic because it requires the users to have the ability to describe the underlying program with a few input-output examples under the training distribution. In this work, we propose a query-based framework that trains a query neural network to generate informative input-output examples automatically and interactively from a large query space. The quality of the query depends on the amount of the mutual information between the query and the corresponding program, which can guide the optimization of the query framework. To estimate the mutual information more accurately, we introduce the functional space (F-space) which models the relevance between the input-output examples and the programs in a differentiable way. We evaluate the effectiveness and generalization of the proposed query-based framework on the Karel task and the list processing task. Experimental results show that the query-based framework can generate informative input-output examples which achieve and even outperform well-designed input-output examples.