Timezone: »
Program synthesis is a class of regression problems where one seeks a solution, in the form of a source-code 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 input-output 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 well-chosen 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 Solar-Lezama (MIT)
Leslie Kaelbling ((organization))
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Poster: Selecting Representative Examples for Program Synthesis »
Wed. Jul 11th 04:15 -- 07:00 PM Room Hall B #129
More from the Same Authors
-
2023 : Demystifying the Role of Feedback in GPT Self-Repair for Code Generation »
Theo X. Olausson · Jeevana Priya Inala · Chenglong Wang · Jianfeng Gao · Armando Solar-Lezama -
2023 : Building Community Driven Libraries of Natural Programs »
Leonardo Hernandez Cano · Yewen Pu · Robert Hawkins · Josh Tenenbaum · Armando Solar-Lezama -
2023 : Prof. Armando Solar-Lezama (MIT): Neurosymbolic Learning as a Path to Learning with Guarantees »
Armando Solar-Lezama -
2022 : Session 3: New Computational Technologies for Reasoning »
Armando Solar-Lezama · Guy Van den Broeck · Jan-Willem van de Meent · Charles Sutton -
2022 : Session 1: New Reasoning Problems and Modes of Reasoning »
Robert Ness · Rosemary Nan Ke · Armando Solar-Lezama -
2022 Workshop: Beyond Bayes: Paths Towards Universal Reasoning Systems »
Zenna Tavares · Emily Mackevicius · Elias Bingham · Nan Rosemary Ke · Talia Ringer · Armando Solar-Lezama · Nada Amin · John Krakauer · Robert O Ness · Alexis Avedisian -
2021 : RL Foundation Panel »
Matthew Botvinick · Thomas Dietterich · Leslie Kaelbling · John Langford · Warrren B Powell · Csaba Szepesvari · Lihong Li · Yuxi Li -
2021 Poster: A Language for Counterfactual Generative Models »
Zenna Tavares · James Koppel · Xin Zhang · Ria Das · Armando Solar-Lezama -
2021 Spotlight: A Language for Counterfactual Generative Models »
Zenna Tavares · James Koppel · Xin Zhang · Ria Das · Armando Solar-Lezama -
2021 Poster: A large-scale benchmark for few-shot program induction and synthesis »
Ferran Alet · Javier Lopez-Contreras · James Koppel · Maxwell Nye · Armando Solar-Lezama · Tomas Lozano-Perez · Leslie Kaelbling · Josh Tenenbaum -
2021 Spotlight: A large-scale benchmark for few-shot program induction and synthesis »
Ferran Alet · Javier Lopez-Contreras · James Koppel · Maxwell Nye · Armando Solar-Lezama · Tomas Lozano-Perez · Leslie Kaelbling · Josh Tenenbaum -
2019 Poster: Learning to Infer Program Sketches »
Maxwell Nye · Luke Hewitt · Josh Tenenbaum · Armando Solar-Lezama -
2019 Oral: Learning to Infer Program Sketches »
Maxwell Nye · Luke Hewitt · Josh Tenenbaum · Armando Solar-Lezama -
2019 Poster: Predicate Exchange: Inference with Declarative Knowledge »
Zenna Tavares · Javier Burroni · Edgar Minasyan · Armando Solar-Lezama · Rajesh Ranganath -
2019 Poster: Graph Element Networks: adaptive, structured computation and memory »
Ferran Alet · Adarsh Keshav Jeewajee · Maria Bauza Villalonga · Alberto Rodriguez · Tomas Lozano-Perez · Leslie Kaelbling -
2019 Oral: Predicate Exchange: Inference with Declarative Knowledge »
Zenna Tavares · Javier Burroni · Edgar Minasyan · Armando Solar-Lezama · Rajesh Ranganath -
2019 Oral: Graph Element Networks: adaptive, structured computation and memory »
Ferran Alet · Adarsh Keshav Jeewajee · Maria Bauza Villalonga · Alberto Rodriguez · Tomas Lozano-Perez · Leslie Kaelbling