Search papers, labs, and topics across Lattice.
This paper introduces Retrieval Augmented Search (RAS), a novel blackbox adaptation method for optimizing programs using large language models (LLMs) that leverages contextual retrieval from in-context examples based on natural language descriptions. The authors demonstrate that RAS significantly outperforms traditional retrieval methods based on source code, achieving up to 2.06 times better performance on C++ program optimization and improving Python program runtimes by 10.27 percentile points. Additionally, the AEGIS method enhances interpretability by breaking down training examples into atomic edits, resulting in smaller, more incremental changes with a performance boost of up to 1.37 times over existing strategies.
Contextual retrieval based on natural language descriptions can dramatically enhance program optimization performance, outperforming traditional methods by over 2x.
Recent work has demonstrated the potential of large language models (LLMs) for program optimization, a key challenge in programming languages. 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. We also propose AEGIS, a method for improving interpretability by decomposing training examples into''atomic edits''that are significantly more incremental in nature. We show that RAS performs up to 2.06$\times$ better than prior state-of-the-art blackbox adaptation strategies on optimizing C++ programs, and that AEGIS performs up to 1.37$\times$ better while making significantly smaller edits. We also show that using RAS improves the mean runtime percentile of Python programs by 10.27 compared to baselines.
