LLM Program Optimization via Retrieval Augmented Search
This addresses program optimization for programming languages research, offering incremental improvements over existing blackbox adaptation strategies.
The paper tackled program optimization using large language models by proposing Retrieval Augmented Search (RAS) and AEGIS, achieving 1.8× better performance than prior state-of-the-art blackbox methods and 1.37× better with smaller edits.
With the advent of large language models (LLMs), there has been a great deal of interest in applying them to solve difficult programming tasks. Recent work has demonstrated their potential at program optimization, a key challenge in programming languages research. We propose a blackbox adaptation method called Retrieval Augmented Search (RAS) that performs beam search over candidate optimizations; at each step, it retrieves in-context examples from a given training dataset of slow-fast program pairs to guide the LLM. Critically, we find that performing contextual retrieval based on an LLM-generated natural language description significantly outperforms retrieval based on the source code. In addition, we propose a method called AEGIS for improving interpretability by decomposing training examples into "atomic edits" that are significantly more incremental in nature. We show that RAS performs 1.8$\times$ better than prior state-of-the-art blackbox adaptation strategies, and that AEGIS performs 1.37$\times$ better while performing significantly smaller edits.