LLM Program Optimization via Retrieval Augmented Search

Sagnik Anupam, Alexander Shypula, Osbert Bastani · 2025

Read LLM Program Optimization via Retrieval Augmented Search by Sagnik Anupam, Alexander Shypula, Osbert Bastani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18916.txt.

Introduction

Sagnik Anupam, Alexander Shypula, and Osbert Bastani teach language models to speed up computer programs by showing them the right past examples. Models can rewrite code to run faster, but they need good hints. Their 2025 method searches a store of slow-fast program pairs at each step of a beam search.

A key trick is to look up examples by a plain-words summary of the code, not by the code itself. That choice beat code-based lookup by a wide margin. A second tool breaks training examples into tiny single edits, making model steps easier to read. Together, the methods more than doubled past best scores on one test set and lifted speed ranks on another.

Catalog record

CREATORSagnik Anupam, Alexander Shypula, Osbert Bastani
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-18916

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

LLM Program Optimization via Retrieval Augmented Search Sagnik Anupam, Alexander Shypula, Osbert Bastani Abstract 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. 1 Introduction Given the success of large language models (LLMs) in writing code, there has been significant interest applying them to programming tasks. A particularly interesting task is program optimization, a long-standing problem in programming languages. Recent work has shown that LLMs have difficulty with this task out-of-the-box ( Shypula et al., 2024 ) —intuitively, data on program performance is simply not widely available in traditional training datasets, making adaptation necessary. To address this problem, they propose the “Performance Improving Edits (PIE)” benchmark, and use it to test a number of carefully designed adaptation strategies to identify effective algorithms for improving performance, including blackbox (i.e. prompting-based) adaptation strategies such as instruction prompting ( Mishra et al., 2022 ) , in-context learning ( Brown et al., 2020 ) , chain-of-thought prompting ( Wei et al., 2022 ) , and retrieval augmented generation ( Lewis et al., 2020 ) . They find dynamic code retrieval to be most effective; this approach retrieves a handful of slow-fast program pair examples from the training set at test time that are most relevant to the current instance (based on embedding similarity). These pairs are then used as in-context examples to prompt the LLM. Intuitively, this approach makes effective use of the training set, which contributes to its success. This existing approach is “end-to-end” in the sense that it takes an input program and asks an LLM to directly output an optimized version of that program. However, it differs significantly from how modern compilers work. Rather than making edits inspired by a handful of end-to-end examples, they systematically modify the program through a series of compiler passes , each of which is designed to perform a specific kind of optimization. These optimizations are inspired by existing examples, but in a way that generalizes them so they apply to new programs. Thus, a natural question is whether breaking end-to-end optimization into more incremental steps can improve performance. Inspired by modern compiler design, we propose a novel retrieval-based adaptation strategy, retrieval augmented search (RAS) 1 1 1 Code and data available at https://sagnikanupam.com/papers/llmprogramoptimization . Correspondence to first author: sanupam<at>seas.upenn.edu . , which combines two insights to improve dynamic retrieval. First, rather than retrieve based on the code itself, it uses contextual retrieval , where it retrieves examples from the training set based on an LLM-generated natural language description of the program, abstracting the core algorithms and data structures used by the program from how they are implemented on a superficial level. Second, rather than retrieve a fixed set of programs, we perform beam search by iteratively performing the retrieve-optimize-evaluate loop. These two techniques result in a state-of-the-art blackbox technique for adapting LLMs to program optimization. However, this technique still produces large changes that can be hard to interpret. To further address this issue, we propose Atomic Edit GuIded Search ( Aegis ), an additional preprocessing step to distill generalizable insights from the training data. In particular, we prompt the LLM to decompose a single slow-fast program pair in the training set into a sequence of atomic edits , which are incremental modifications associated with a natural language description of the edit, and then explain why the edit might improve performance. The description is intended to be generalizable, abstracting away specifics of the training example from which they are derived. After generating a dataset of atomic edits and examples associated with each edit, when given a new program, we use RAS to first search over incremental edits to this program. Each edit to this program is achieved by retrieving the most relevant atomic edit in our database and then prompting the LLM to apply this atomic edit to the new program. We then perform beam search over sequences of incremental edits to select the resulting program that achieves the greatest performance gain while preserving correctness. We evaluate our approach using the PIE benchmark ( Shypula et al., 2024 ) for C++ program optimization and the Mercury benchmark ( Du et al., 2024 ) for Python program optimization. On PIE, RAS significantly outperforms dynamic retrieval, a state-of-the-art blackbox adaptation strategy, achieving an 8.70 \times average speedup compared to 4.23 \times for dynamic retrieval using Qwen3-Coder. Furthermore, Aegis achieves a 6.08 \times average speedup using GPT-4o, while reducing the average edit size (measured by string edit distance) by 17% when compared to RAS (with GPT-4o) and by 30% when restricting to the first edit in the search process (which is the most substantial one). Hence, RAS performs upto 2.06 \times better than dynamic retrieval, while Aegis performs 1.37 \times better. We also use RAS to achieve a state-of-the-art performance of 9.18 \times average speedup using DeepSeek 3.2. Then, we show that by executing RAS on Mercury and comparing against our best-performing baselines, we can improve the mean runtime percentile by 10.27 for Qwen2.5-7B-Instruct, significantly narrowing its performance gap as compared to more recent reasoning models. Related work. Code optimization has long been a problem of interest in programming languages. However, these approaches typically operate at a lower level of abstraction and are incapable of producing high-level optimizations such as changing algorithms and data structures. Thus, there has been recent interest in leveraging LLMs to augment existing, symbolic techniques. One approach that directly uses LLMs to perform program optimization is the Search-Based LLM (SBLLM) ( Gao et al., 2024 ) , which proposes an evolutionary search framework to iteratively optimize Python and C++ programs. However, in their framework, retrieval and search are not integrated, and they do not use contextual retrieval. Furthermore, they only report speedups of 1.55 \times on the PIE benchmark (using GPT-4), so even the existing dynamic retrieval approach studied in PIE substantially outperforms their approach. Finally, Qiu et al. (2025) studies capabilities of LLMs for Python program optimization, finding significant gaps compared to human experts. We focus on optimizing C++ code since performance can be measured in a reproducible way using a simulator ( Shypula et al., 2024 ) . Retrieval augmented generation is broadly known to improve code generation ( Wang et al., 2024 ) . The specific idea of dynamically retrieving relevant in-context examples from a larger training set was first proposed in

Read the complete text