Synthetic Datasets for Neural Program Synthesis

Richard Shin, Neel Kant, Kavi Gupta, Christopher Bender, Brandon Trabucco, Rishabh Singh, Dawn Song

Abstract

The goal of program synthesis is to automatically generate programs in a particular language from corresponding specifications, e.g. input-output behavior. Many current approaches achieve impressive results after training on randomly generated I/O examples in limited domain-specific languages (DSLs), as with string transformations in RobustFill. However, we empirically discover that applying test input generation techniques for languages with control flow and rich input space causes deep networks to generalize poorly to certain data distributions; to correct this, we propose a new methodology for controlling and evaluating the bias of synthetic data distributions over both programs and specifications. We demonstrate, using the Karel DSL and a small Calculator DSL, that training deep networks on these distributions leads to improved cross-distribution generalization performance.

Introduction

Program synthesis involves the automatic generation of code from specifications, such as input-output (I/O) pairs. Due to the scarcity of large-scale real-world datasets, researchers frequently rely on synthetic data generated from context-free grammars (CFGs). However, "randomly generated" data is rarely unbiased. Deep neural networks are highly sensitive to statistical regularities in training data, such as distributions of program length or complexity. When these models encounter real-world tasks with different distributions, performance often collapses. This paper investigates these biases and proposes a filtering methodology to improve generalization.

Methodology: Salient Variable Homogenization

To mitigate the impact of hidden biases, we introduce Salient Variable Homogenization. This technique involves three key steps:

  1. Identification of Salient Variables: We define features of the data that are likely to influence model performance, such as grid size, wall density, or nesting depth in the Karel domain.
  2. Filtering via Rejection Sampling: Instead of accepting all generated samples, we track the distribution of salient variables. If a new sample's features are already over-represented, it is discarded with a probability determined by a hyperparameter $\epsilon$.
  3. The $\epsilon$ Trade-off: This parameter balances the uniformity of the resulting dataset against the computational cost of generation. A smaller $\epsilon$ yields a more uniform distribution but requires more sampling iterations.

Experimental Setup

We evaluate our approach across two primary domains and a real-world benchmark:

  • Karel the Robot: A grid-world DSL where a robot performs tasks like moving and placing markers.
  • Calculator: A program induction task requiring the prediction of arithmetic expression results modulo 10.
  • Real-World Benchmark: 36 hand-designed Karel problems from educational sources like "Hour of Code," representing human-intended logic.
Karel domain examples showing input-output specifications and the corresponding synthesized program.

Results and Discussion

Our findings highlight several critical aspects of synthetic data bias. Notably, we observed an "Action-Only Paradox": baseline models often fail on simple action-only programs because training sets are frequently pruned to favor complex logic, leaving the model unable to handle basic cases. Furthermore, we found that bias in the input space (e.g., marker density) is just as detrimental as bias in the program space.

Generalization Performance

The "Uniform" model, trained on homogenized data, demonstrated superior robustness. On specialized "narrow" test distributions where baseline accuracy dropped to near zero, the Uniform model maintained 60% to 80% accuracy.

Accuracy of Baseline vs. Uniform models on various narrow test distributions, demonstrating the robustness of the homogenized training approach.

Real-World and Calculator Domains

On the 36 human-designed Karel problems, the Uniform model solved 19.4% (7/36) of tasks, nearly doubling the baseline's 11.1% (4/36). In the Calculator domain, homogenizing features like "Maximum Depth" led to consistent accuracy gains of 1% to 6% over standard sampling methods.

Conclusion

This work demonstrates that the distribution of synthetic data is a primary factor in the generalization of neural program synthesis models. While Salient Variable Homogenization significantly improves performance, it currently requires manual identification of relevant features. Future research should explore automated methods for discovering these salient variables to further scale this approach across diverse domains.

Summary updated

Abstract

The goal of program synthesis is to automatically generate programs in a particular language from corresponding specifications, e.g. input-output behavior. Many current approaches achieve impressive results after training on randomly generated I/O examples in limited domain-specific languages (DSLs), as with string transformations in RobustFill. However, we empirically discover that applying test input generation techniques for languages with control flow and rich input space causes deep networks to generalize poorly to certain data distributions; to correct this, we propose a new methodology for controlling and evaluating the bias of synthetic data distributions over both programs and specifications. We demonstrate, using the Karel DSL and a small Calculator DSL, that training deep networks on these distributions leads to improved cross-distribution generalization performance.
BibTeX
@inproceedings{shin2019synthetic,
  author = {Richard Shin and Neel Kant and Kavi Gupta and Christopher Bender and Brandon Trabucco and Rishabh Singh and Dawn Song},
  title = {{Synthetic Datasets for Neural Program Synthesis}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=obbTbXA2m5},
}
Figure