Using Compressive Enumeration to Solve Algorithmic Tasks With Language Models

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.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Wang, Annie

Advisor dc:contributor.advisor

• Solar-Lezama, Armando

Statement dc:rights

• Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)
• Copyright retained by author(s)

Licence dc:rights.uri

• https://creativecommons.org/licenses/by-nc-nd/4.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/156810

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/156810