Can You Improve My Code? Optimizing Programs with Local Search

Fatemeh Abdollahi, Saqib Ameen, Matthew E. Taylor, Levi H. S. Lelis

Abstract

While modern Large Language Models (LLMs) excel at generating boilerplate code and completing snippets, they often struggle with the iterative optimization of existing logic to meet specific performance targets. This paper introduces POLIS (Program Optimization with Locally Improving Search), a framework designed to optimize human-written programs through a hill-climbing local search strategy. By decomposing the complex task of whole-program synthesis into manageable, line-by-line synthesis problems, POLIS significantly improves program performance while maintaining the original structure and interpretability. Evaluated through user studies on reinforcement learning tasks and bug-fixing benchmarks, POLIS improved 100% of participant programs, demonstrating the power of human-AI symbiosis in code optimization.

Introduction

Traditional program synthesis—the act of generating code from scratch based on a specification—is notoriously difficult due to the "state-space explosion" problem. As the desired program length increases, the number of possible code combinations grows exponentially, making brute-force search computationally infeasible for programs of significant length. Conversely, while AI assistants like GitHub Copilot are proficient at generating initial drafts, they lack a mechanism to "grind" for numerical objectives, such as maximizing a score in a game or minimizing latency in data processing.

POLIS addresses these challenges by shifting the focus from synthesis to optimization. Instead of generating a program from a blank slate, POLIS takes a working, human-provided program and iteratively "polishes" it. By leveraging the high-level structure provided by the human author, the system focuses its computational power on refining individual lines of code to maximize a specific performance metric.

POLIS operates on the principle of local search, specifically a hill-climbing algorithm that treats each line of a program as a mini-synthesis task. The process follows several key steps:

1. Line-by-Line Iteration

The system iterates through every line of the input program. For each line, it attempts to find a replacement that increases the program's overall score according to a defined objective function.

2. Bottom-Up Search (BUS)

To find these replacements, POLIS employs a Bottom-Up Search algorithm. Within a Domain Specific Language (DSL), the system enumerates potential code fragments to find a line that, when substituted into the original program, yields the highest performance gain. This approach makes synthesis feasible because searching for a single line is significantly faster than searching for a whole program.

3. Optimization Techniques

To enhance efficiency and effectiveness, POLIS incorporates several advanced search strategies:

  • Bayesian Optimization: This is used to fine-tune real-valued constants within the code, ensuring that numerical thresholds are optimized beyond simple integer increments.
  • State Highlights: Rather than evaluating every code change on all possible inputs—which is computationally expensive—POLIS evaluates changes on a subset of "important" or representative states.
  • Restarts: To mitigate the risk of getting stuck in local optima, the system can restart the search from different initial configurations.

Experimental Evaluation

The authors evaluated POLIS through two primary methods: a controlled user study and a proof-of-concept bug-repair task.

User Study: Lunar Lander and Highway

Twenty-seven participants, primarily computer science students, were tasked with writing programs to solve two reinforcement learning environments: Lunar Lander (landing a spacecraft) and Highway (navigating traffic). These environments provide clear numerical scores based on performance (e.g., fuel efficiency, distance traveled, and collision avoidance).

Stack Overflow Bug Repair

To test the system's ability to handle logic errors, the authors selected four buggy programs from Stack Overflow, including three sorting algorithms and one cumulative sum problem. The goal was to see if POLIS could "fix" these programs by treating correctness as an optimization objective.

Results and Key Insights

The results demonstrate that POLIS is a highly effective "finisher" for human-written code:

  • Universal Improvement: POLIS improved 100% of the programs written by the 27 participants. In the Highway task, every participant's program was optimized to an average score exceeding the best unassisted human score.
  • Safety and Efficiency: In the Highway environment, POLIS drastically reduced collisions. In several instances, collision rates dropped from over 20 per episode to fewer than three.
  • Logic Repair: The system successfully repaired all four buggy programs from the Stack Overflow dataset. By adjusting indices or comparison operators (e.g., changing < to <=), POLIS framed "fixing a bug" as "optimizing for correctness."
  • Interpretability: Because POLIS only modifies lines within the existing human-provided structure, the resulting code remains recognizable and interpretable to the original author. This stands in stark contrast to "black-box" neural network policies, which are often impossible for humans to audit or modify.

Discussion and Limitations

While POLIS is powerful, it is subject to the inherent limitations of local search. Because it optimizes one line at a time, it can fall into "local optimum" traps where a necessary improvement requires changing multiple lines simultaneously (e.g., renaming a variable used in multiple locations).

Furthermore, the system currently relies on a manually defined DSL and a clear, real-valued objective function. It cannot optimize for subjective qualities like "readability" or "elegance" without a mathematical proxy for those traits. Future work may involve integrating LLMs to guide the search process, potentially allowing for more complex, multi-line edits and reducing the dependency on task-specific DSLs.

Conclusion

POLIS represents a significant step toward human-AI symbiosis in software development. By allowing humans to provide the high-level logic and control flow while the AI handles the granular numerical optimization, POLIS transforms the programming process. It proves that even when humans provide a functional starting point, there is almost always room for automated improvement, turning a "working" program into an "optimal" one.

Summary updated

BibTeX
@inproceedings{abdollahi2023can,
  author = {Fatemeh Abdollahi and Saqib Ameen and Matthew E. Taylor and Levi H. S. Lelis},
  title = {{Can You Improve My Code? Optimizing Programs with Local Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/328},
}
Figure