Spending the Execution Budget Wisely: Bayesian Optimization over LLM Code Proposals

Language-model agents that speed up real software are bottlenecked less by their ability to write candidate patches than by how they decide which patches to try, keep, and build on. Each honest check of a performance patch means running the project's test suite and a realistic workload, which can take minutes. Current agents spend that budget badly. They accept the first small speedup and stop. They make "optimizations" that are actually slower about 30% of the time. On real repositories, frontier models reach under a quarter of expert speedups. This note proposes to treat that decision as a problem for Bayesian optimization, a method for optimizing an expensive black-box function by fitting a cheap probabilistic model (a surrogate) to past evaluations and using its uncertainty to choose what to evaluate next.

The key design choice goes against the obvious transfer. Latent space Bayesian optimization, as used in molecule design, trains an autoencoder to map discrete objects into a continuous space, searches that space, and decodes points back into objects. We keep the continuous space and the uncertainty-guided search. We drop the decoder. The language model remains the only thing that writes code. The continuous space is the embedding of programs that have actually been proposed. A Gaussian process (GP) surrogate over those embeddings predicts both speedup and the probability that tests pass. It uses those predictions to decide which proposals are worth executing and which programs to refine next.

Core Claim

When execution is the scarce resource, a surrogate fitted online to the current task's own execution results allocates that budget better than an agent's self-judgment, a fixed static judge, or evolutionary selection. The surrogate models the joint chance that a patch is both correct and faster, and it explores where it is uncertain. Concretely, we claim that at a matched number of workload executions, the method reaches higher expert-relative speedup on SWE-fficiency and lowers the rate of accepted regressions. It should do so specifically by pushing search into functions the agent would otherwise never edit.

The idea differs from its closest neighbors in a precise way. BODE-GEN runs a GP over a projected embedding space of prompts and decodes prompts that a base model then turns into code. It reports that HumanEval+ accuracy for ChatGPT-3.5 rises from 61% to 89%. Its objective is test-pass rate, and it has no model of the code itself. The Latent Program Network searches a learned program latent by gradient ascent through a differentiable neural executor. It cannot pass gradients through a real compiler or profiler, and it has no uncertainty model. Our surrogate lives over the programs themselves, handles non-differentiable execution, and targets a non-functional objective (speed) under a hard constraint (correctness).

Research Program

The loop runs per task. A profiler identifies candidate hotspot functions. An LLM proposes a batch of patches starting from a parent program. Every proposal is embedded with a pretrained code-embedding model, projected to a low-dimensional space as in BODE-GEN, and scored by two GPs. The first predicts log speedup. The second is a classification GP that predicts the probability of passing tests. Only the top-scoring proposals are executed. Their results update both GPs, and the process repeats.

Proposals are scored with constrained expected improvement. This is the recipe that constrained antibody design uses to maximize binding while respecting thermostability, carried over here with tests in the role of thermostability:

$$a(x) = \mathrm{EI}_{s}(x)\cdot \Pr(\text{pass} \mid x),$$

In this expression, $x$ is a candidate patch's embedding, $\mathrm{EI}_{s}$ is the expected improvement in log speedup over the best correct program found so far, and $\Pr(\text{pass}\mid x)$ comes from the correctness GP.

Parent selection borrows the local trust region from LOL-BO. LOL-BO restricts search in a molecule latent space to a box around the incumbent, growing it after successes and shrinking it after failures, which prevents collapse in high dimensions. In our version, the region is a neighborhood of the incumbent in embedding space. When the region shrinks after repeated failures, the search restarts from a different hotspot rather than stopping. This is the mechanism we expect to counter satisficing.

Two further ingredients test whether the continuous space earns its place. First, we compare embedding whole programs against embedding the edit, meaning the diff relative to the parent. We expect the diff space to make speedup smoother, because edits that differ by a few tokens should often have similar effects. LOL-BO's "smoothness gap" warns that a representation trained only to reconstruct need not be smooth in the objective. We measure this directly. Second, the fine-tuned static judge from Rethinking Code Refinement is used as the GP's prior mean. That judge is a 1.3B-parameter model trained on execution comparisons. With this setup, the surrogate starts from the judge's general knowledge and corrects it with task-specific measurements.

We deliberately sidestep the decoder misalignment problem that InvBO addresses. In InvBO's setting, decoding a latent point gives an object other than the one whose score was recorded. Because every point our GP sees is the embedding of a program that was actually executed, that problem cannot arise. Molecule-style designs such as CLaSMO map a fixed scaffold to a fixed set of editable fragments. We take a looser version of that idea: interface signatures are frozen and search is restricted to hotspot function bodies. The goal is to avoid the "partial migration" crashes reported for A₂DEPT, where a data representation changes in one function but not in the functions that consume it.

Baselines

The naive reference is the agent run alone. The same LLM iterates on execution feedback, choosing for itself what to run, with the same number of executions allowed. The published ceiling for this style on SWE-fficiency is a speedup ratio of 0.225x for Claude 4.5 Opus and 0.157x for GPT-5 (SWE-fficiency). Those numbers come from unrestricted agent runs, not our budgets. We therefore re-run the agent with our chosen model at each budget rather than comparing against the published figures.

The strongest existing search method is evolutionary program-tree search in the style of A₂DEPT. It maintains lineages of programs, applies small-, large-scale, and crossover mutations, and selects programs by simulated annealing. It reports a 9.8% reduction in mean normalized optimality gap over ReEvo and MCTS-AHD on FrontierCO. No reported result was found on Lacuna for A₂DEPT on SWE-fficiency or Mercury, so we reimplement its selection and mutation scheme. This baseline shares our LLM, proposal count, execution budget, hotspot list, and interface freezing. The only difference is how parents and executions are chosen.

The static-judge reranker executes the proposals that the fine-tuned 1.3B judge ranks highest. On Python, that judge reports 72.49% pairwise accuracy and a Spearman rank correlation of 0.66 (Rethinking Code Refinement). This baseline is our method with the online GP removed.

The key ablations remove one ingredient at a time. We replace expected improvement with the GP mean, which removes exploration. We drop the correctness GP. We drop the trust region. We swap diff embeddings for whole-program embeddings. We swap the pretrained embedding for random features.

Every method is tuned with the same small budget on Mercury-train. Beating a baseline means a higher mean speedup ratio at matched execution budgets of 10, 25, and 50 workload runs, with bootstrap confidence intervals over tasks that exclude zero. It also means no increase in the rate of accepted patches that fail tests or are slower than the original.

Why not just…?

Why not just let a frontier agent iterate on execution feedback? Its gains flatten after two or three rounds. On CodeTransOcean, three rounds of self-debugging moved GPT-3.5 only from 48.57% to 52.57% (CodeTransOcean). On SWE-fficiency, over 68% of expert gains lie in functions that agents never touched. The agent-alone baseline at matched budget tests this directly. We also measure the share of our speedup that comes from expert-edited functions. If the agent alone matches our curve, the surrogate adds nothing and we will report that.

Why not just rerank with the static judge? This is the most serious threat. The judge is cheap, and at a Spearman correlation of 0.66 it is already informative. Our argument is that a judge is blind to the specific workload and hardware and gives no uncertainty to explore with. The judge is our prior mean, so the real question is whether online correction adds value. The decisive measurement is the Spearman correlation of GP predictions on held-out executed proposals within each task, as a function of the number of executions. If the GP never exceeds the judge's 0.66 within 50 executions, the method reduces to judge reranking, and the proposal should be cut back to that.

Why not just use evolutionary search like A₂DEPT? Evolutionary search works when hundreds of evaluations are affordable, and its authors note that this is expensive. On cheap Mercury tasks, we expect it to be competitive with our method. Our claim is limited to the low-budget regime, and the budget sweep will show where, if anywhere, the two curves cross.

Why not just run BO over prompts like BODE-GEN? Prompt search controls code only indirectly and was shown only on test-pass rate. We include prompt-space BO as an additional arm, optimizing speedup under the same budget. Our hypothesis is that it will explore poorly within a single hotspot.

Proposed Experiments

Mercury is the controlled testbed (Mercury). Its 256 evaluation tasks are cheap enough to execute every proposal. That lets us compute an exact ranking of all proposals, so we can measure simple regret (how far the chosen program is from the best available one) and surrogate calibration. The reported point of reference there is a Beyond score of 66.47 for DeepSeek-Coder-33B after preference tuning. Beyond is a percentile of runtime relative to human solutions.

SWE-fficiency's 498 tasks are the main test. There, the metric is speedup ratio relative to the expert, reported together with the rate of accepted regressions (to compare with the roughly 30% machine-regression rate) and the fraction of gains that come from expert-edited functions. A FrontierCO subset allows a like-for-like comparison with A₂DEPT on optimality gap.

Three results decide the question. First, the GP's within-task Spearman correlation must exceed the judge's 0.66 by the middle of the budget. Second, diff embeddings must show smoother speedup than whole-program embeddings, measured as correlation between embedding distance and difference in log speedup. Third, the expected-improvement arm must beat the greedy GP-mean arm specifically on tasks where the agent alone satisfices, meaning its first accepted patch is its final one. If the first result fails, the contribution is at most a better judge. If the third fails, exploration is not the lever, and the satisficing story is wrong.