Program synthesis is a class of regression problems where one seeks a solution, in the form of a sourcecode program, mapping the inputs to their corresponding outputs exactly. Due to its precise and combinatorial nature, program synthesis is commonly formulated as a constraint satisfaction problem, where inputoutput examples are encoded as constraints and solved with a constraint solver. A key challenge of this formulation is scalability: while constraint solvers work well with a few wellchosen examples, a large set of examples can incur significant overhead in both time and memory. We describe a method to discover a subset of examples that is both small and representative: the subset is constructed iteratively, using a neural network to predict the probability of unchosen examples conditioned on the chosen examples in the subset, and greedily adding the least probable example. We empirically evaluate the representativeness of the subsets constructed by our method, and demonstrate such subsets can significantly improve synthesis time and stability.
Author Information
Yewen Pu (MIT)
Zachery Miranda (MIT)
Armando SolarLezama (MIT)
Leslie Kaelbling ((organization))
Related Events (a corresponding poster, oral, or spotlight)

2018 Poster: Selecting Representative Examples for Program Synthesis »
Wed Jul 11th 06:15  09:00 PM Room Hall B
More from the Same Authors

2019 Poster: Learning to Infer Program Sketches »
Maxwell Nye · Luke Hewitt · Josh Tenenbaum · Armando SolarLezama 
2019 Oral: Learning to Infer Program Sketches »
Maxwell Nye · Luke Hewitt · Josh Tenenbaum · Armando SolarLezama 
2019 Poster: Predicate Exchange: Inference with Declarative Knowledge »
Zenna Tavares · Javier Burroni · Edgar Minasyan · Armando SolarLezama · Rajesh Ranganath 
2019 Poster: Graph Element Networks: adaptive, structured computation and memory »
Ferran Alet · Adarsh Keshav Jeewajee · Maria Bauza Villalonga · Alberto Rodriguez · Tomas LozanoPerez · Leslie Kaelbling 
2019 Oral: Predicate Exchange: Inference with Declarative Knowledge »
Zenna Tavares · Javier Burroni · Edgar Minasyan · Armando SolarLezama · Rajesh Ranganath 
2019 Oral: Graph Element Networks: adaptive, structured computation and memory »
Ferran Alet · Adarsh Keshav Jeewajee · Maria Bauza Villalonga · Alberto Rodriguez · Tomas LozanoPerez · Leslie Kaelbling