# Iterative Genetic Improvement: Scaling Stochastic Program Synthesis

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 101 references that are in the map.
- First posted on arXiv 26 Feb 2022.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [Neuro-Symbolic Program Synthesis](https://mlsanity.com/paper/1611.01855/) (2016)
- [Learning to Infer Graphics Programs from Hand-Drawn Images](https://mlsanity.com/paper/1707.09627/) (2017)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Where are we now? A large benchmark study of recent symbolic regression methods](https://mlsanity.com/paper/1804.09331/) (2018)
- [Program Synthesis using Natural Language](https://mlsanity.com/paper/1509.00413/) (2015)
- [SpreadsheetCoder: Formula Prediction from Semi-structured Context](https://mlsanity.com/paper/2106.15339/) (2021)
- [Program Synthesis and Semantic Parsing with Learned Code Idioms](https://mlsanity.com/paper/1906.10816/) (2019)
- [BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration](https://mlsanity.com/paper/2007.14381/) (2020)
- [Program Synthesis using Conflict-Driven Learning](https://mlsanity.com/paper/1711.08029/) (2017)
- [ARJA: Automated Repair of Java Programs via Multi-Objective Genetic Programming](https://mlsanity.com/paper/1712.07804/) (2017)
- [Latent Programmer: Discrete Latent Codes for Program Synthesis](https://mlsanity.com/paper/2012.00377/) (2020)
- [PonyGE2: Grammatical Evolution in Python](https://mlsanity.com/paper/1703.08535/) (2017)
- [SyGuS-Comp 2018: Results and Analysis](https://mlsanity.com/paper/1904.07146/) (2019)

## Abstract (arXiv)

Program synthesis aims to it automatically find programs from an underlying programming language that satisfy a given specification. While this has the potential to revolutionize computing, how to search over the vast space of programs efficiently is an unsolved challenge in program synthesis. In cases where large programs are required for a solution, it is generally believed that it stochastic search has advantages over other classes of search techniques. Unfortunately, existing stochastic program synthesizers do not meet this expectation very well, suffering from the scalability issue. Here we propose a new framework for stochastic program synthesis, called iterative genetic improvement to overcome this problem, a technique inspired by the practice of the software development process. The key idea of iterative genetic improvement is to apply genetic improvement to improve a current reference program, and then iteratively replace the reference program by the best program found. Compared to traditional stochastic synthesis approaches, iterative genetic improvement can build up the complexity of programs incrementally in a more robust way. We evaluate the approach on two program synthesis domains: list manipulation and string transformation. Our empirical results indicate that this method has considerable advantages over several representative stochastic program synthesizer techniques, both in terms of scalability and of solution quality.