{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/156932"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/156932","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Overcoming the Expressivity-Efficiency Tradeoff in Program Induction","abstract":"People are incredibly flexible and efficient inductive reasoners. On the other hand, current approaches in program synthesis show strong domain-specific performance, but are both less sample-efficient and less flexible. Large language models improve upon this sample-efficiency and domain-generality, but lack robustness and still fall far short of people and traditional approaches on difficult induction tasks. In this thesis, we propose two hypotheses for how people seemingly overcome this trade-off between flexibility and efficiency. In the first, we propose that people may operate over an incredibly vast language which is made tractable via a strong, bottom-up proposal model. In the second, we propose that, alternatively, people may relax the necessity of such a strong proposal model by learning task-specific reasoning languages through experience. We build models operationalizing both hypotheses and show that they can improve the generality and efficiency of previous models.","abstract_html":"People are incredibly flexible and efficient inductive reasoners. On the other hand, current approaches in program synthesis show strong domain-specific performance, but are both less sample-efficient and less flexible. Large language models improve upon this sample-efficiency and domain-generality, but lack robustness and still fall far short of people and traditional approaches on difficult induction tasks. In this thesis, we propose two hypotheses for how people seemingly overcome this trade-off between flexibility and efficiency. In the first, we propose that people may operate over an incredibly vast language which is made tractable via a strong, bottom-up proposal model. In the second, we propose that, alternatively, people may relax the necessity of such a strong proposal model by learning task-specific reasoning languages through experience. We build models operationalizing both hypotheses and show that they can improve the generality and efficiency of previous models.","abstract_has_math":false,"creators":["Acquaviva, Samuel"],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences","school":null,"contributors":[],"advisors":["Pu, Yewen","Tenenbaum, Joshua B."],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-05","date_published":"2024-05","updated_at":"2026-07-22T22:20:54Z","subjects":[],"languages":[],"rights":["Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","Copyright retained by author(s)"],"rights_urls":["https://creativecommons.org/licenses/by-nc-nd/4.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/156932","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Pu, Yewen","Tenenbaum, Joshua B."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences"]},{"key":"dc:creator","label":"Author","values":["Acquaviva, Samuel"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2024-09-24T18:21:27Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2024-09-24T18:21:27Z"]},{"key":"dc:date.issued","label":"Date","values":["2024-05"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master","Master of Engineering in Computation and Cognition"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","Copyright retained by author(s)"]},{"key":"dc:rights.uri","label":"Rights URI","values":["https://creativecommons.org/licenses/by-nc-nd/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/156932"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["People are incredibly flexible and efficient inductive reasoners. On the other hand, current approaches in program synthesis show strong domain-specific performance, but are both less sample-efficient and less flexible. Large language models improve upon this sample-efficiency and domain-generality, but lack robustness and still fall far short of people and traditional approaches on difficult induction tasks. In this thesis, we propose two hypotheses for how people seemingly overcome this trade-off between flexibility and efficiency. In the first, we propose that people may operate over an incredibly vast language which is made tractable via a strong, bottom-up proposal model. In the second, we propose that, alternatively, people may relax the necessity of such a strong proposal model by learning task-specific reasoning languages through experience. We build models operationalizing both hypotheses and show that they can improve the generality and efficiency of previous models."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:title","label":"Title","values":["Overcoming the Expressivity-Efficiency Tradeoff in Program Induction"]}]}],"canonical_facts":{"dc:contributor.advisor":["Pu, Yewen","Tenenbaum, Joshua B."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences"],"dc:creator":["Acquaviva, Samuel"],"dc:date.accessioned":["2024-09-24T18:21:27Z"],"dc:date.available":["2024-09-24T18:21:27Z"],"dc:date.issued":["2024-05"],"dc:description.abstract":["People are incredibly flexible and efficient inductive reasoners. On the other hand, current approaches in program synthesis show strong domain-specific performance, but are both less sample-efficient and less flexible. Large language models improve upon this sample-efficiency and domain-generality, but lack robustness and still fall far short of people and traditional approaches on difficult induction tasks. In this thesis, we propose two hypotheses for how people seemingly overcome this trade-off between flexibility and efficiency. In the first, we propose that people may operate over an incredibly vast language which is made tractable via a strong, bottom-up proposal model. In the second, we propose that, alternatively, people may relax the necessity of such a strong proposal model by learning task-specific reasoning languages through experience. We build models operationalizing both hypotheses and show that they can improve the generality and efficiency of previous models."],"dc:description.degree":["M.Eng."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/156932"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","Copyright retained by author(s)"],"dc:rights.uri":["https://creativecommons.org/licenses/by-nc-nd/4.0/"],"dc:title":["Overcoming the Expressivity-Efficiency Tradeoff in Program Induction"],"dc:type":["Thesis"],"thesis:degree_name":["Master","Master of Engineering in Computation and Cognition"]},"updated_at":"2026-07-22T22:20:54Z"}