{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/156810"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/156810","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Using Compressive Enumeration to Solve Algorithmic Tasks With Language Models","abstract":"Large language models are useful tools for generating and synthesizing short code snippets that solve straightforward programming problems. However, their performance on more advanced code generation tasks remains limited, due to the complex algorithmic nature of these tasks. Yet, large language models are often capable of crafting nearly-correct answers to such questions; model-generated responses are prone to small errors that may render an otherwise-correct program incorrect. To address this issue, we investigate whether large language models can be combined with enumerative program synthesis techniques to build solutions to difficult algorithmic problems. This thesis presents and evaluates compressive enumeration as a strategy for improving large language model performance on code generation tasks. Given a question q and a corpus P of model-generated responses to q, compressive enumeration isolates shared code components within P; combining these components in novel ways may make it possible to generate a new solution to q. Experimentation with the Stitch library learning algorithm shows that compressive enumeration is able to generate a working solution for a small number of questions. However, its best performance is typically attained on problems that are already solvable by current large language models. This suggests that compressive enumeration has limited practical value as a code generation strategy; however, future improvements to the technique may make it more widely applicable.","abstract_html":"Large language models are useful tools for generating and synthesizing short code snippets that solve straightforward programming problems. However, their performance on more advanced code generation tasks remains limited, due to the complex algorithmic nature of these tasks. Yet, large language models are often capable of crafting nearly-correct answers to such questions; model-generated responses are prone to small errors that may render an otherwise-correct program incorrect. To address this issue, we investigate whether large language models can be combined with enumerative program synthesis techniques to build solutions to difficult algorithmic problems. This thesis presents and evaluates compressive enumeration as a strategy for improving large language model performance on code generation tasks. Given a question q and a corpus P of model-generated responses to q, compressive enumeration isolates shared code components within P; combining these components in novel ways may make it possible to generate a new solution to q. Experimentation with the Stitch library learning algorithm shows that compressive enumeration is able to generate a working solution for a small number of questions. However, its best performance is typically attained on problems that are already solvable by current large language models. This suggests that compressive enumeration has limited practical value as a code generation strategy; however, future improvements to the technique may make it more widely applicable.","abstract_has_math":false,"creators":["Wang, Annie"],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Solar-Lezama, Armando"],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-05","date_published":"2024-05","updated_at":"2026-07-22T22:21:09Z","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/156810","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Solar-Lezama, Armando"]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Wang, Annie"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2024-09-16T13:50:36Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2024-09-16T13:50:36Z"]},{"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 Electrical Engineering and Computer Science"]}]},{"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/156810"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Large language models are useful tools for generating and synthesizing short code snippets that solve straightforward programming problems. However, their performance on more advanced code generation tasks remains limited, due to the complex algorithmic nature of these tasks. Yet, large language models are often capable of crafting nearly-correct answers to such questions; model-generated responses are prone to small errors that may render an otherwise-correct program incorrect. To address this issue, we investigate whether large language models can be combined with enumerative program synthesis techniques to build solutions to difficult algorithmic problems. This thesis presents and evaluates compressive enumeration as a strategy for improving large language model performance on code generation tasks. Given a question q and a corpus P of model-generated responses to q, compressive enumeration isolates shared code components within P; combining these components in novel ways may make it possible to generate a new solution to q. Experimentation with the Stitch library learning algorithm shows that compressive enumeration is able to generate a working solution for a small number of questions. However, its best performance is typically attained on problems that are already solvable by current large language models. This suggests that compressive enumeration has limited practical value as a code generation strategy; however, future improvements to the technique may make it more widely applicable."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:title","label":"Title","values":["Using Compressive Enumeration to Solve Algorithmic Tasks With Language Models"]}]}],"canonical_facts":{"dc:contributor.advisor":["Solar-Lezama, Armando"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Wang, Annie"],"dc:date.accessioned":["2024-09-16T13:50:36Z"],"dc:date.available":["2024-09-16T13:50:36Z"],"dc:date.issued":["2024-05"],"dc:description.abstract":["Large language models are useful tools for generating and synthesizing short code snippets that solve straightforward programming problems. However, their performance on more advanced code generation tasks remains limited, due to the complex algorithmic nature of these tasks. Yet, large language models are often capable of crafting nearly-correct answers to such questions; model-generated responses are prone to small errors that may render an otherwise-correct program incorrect. To address this issue, we investigate whether large language models can be combined with enumerative program synthesis techniques to build solutions to difficult algorithmic problems. This thesis presents and evaluates compressive enumeration as a strategy for improving large language model performance on code generation tasks. Given a question q and a corpus P of model-generated responses to q, compressive enumeration isolates shared code components within P; combining these components in novel ways may make it possible to generate a new solution to q. Experimentation with the Stitch library learning algorithm shows that compressive enumeration is able to generate a working solution for a small number of questions. However, its best performance is typically attained on problems that are already solvable by current large language models. This suggests that compressive enumeration has limited practical value as a code generation strategy; however, future improvements to the technique may make it more widely applicable."],"dc:description.degree":["M.Eng."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/156810"],"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":["Using Compressive Enumeration to Solve Algorithmic Tasks With Language Models"],"dc:type":["Thesis"],"thesis:degree_name":["Master","Master of Engineering in Electrical Engineering and Computer Science"]},"updated_at":"2026-07-22T22:21:09Z"}