FrugalEvo: Towards Cost-Aware LLM-Guided Program Evolution

Hui Chen; Xuan Qi; James Xu Zhao; Zhaopeng Feng; Shilong Liu; Kuang Xu; Pang Wei Koh; Bryan Hooi

cs.NEOct 2, 2026

FrugalEvo: Towards Cost-Aware LLM-Guided Program Evolution

Authors: Hui Chen, Xuan Qi, James Xu Zhao, Zhaopeng Feng, Shilong Liu, Kuang Xu, Pang Wei Koh, Bryan Hooi

Organizations: National University of Singapore · University of Washington · Princeton University · Stanford University

Abstract

LLM-guided evolutionary methods, such as AlphaEvolve, have emerged as powerful approaches for challenging computational optimization problems, such as circle packing. However, prior work typically optimizes performance gain over a fixed number of iterations. We argue that practical optimization should maximize gain per unit cost. To this end, we propose FrugalEvo, a cost-aware evolutionary framework where a stronger, higher-cost LLM explores solution strategies, and a cheaper LLM implements them and iteratively refines the resulting code. We also design a cache-efficient evolution process, where our harness and prompts maximize the sharing of prefixes across different evolution steps, to improve cache reuse. To measure solution quality throughout a fixed cost budget, we introduce Budget-Aware Area Under the Curve (BA-AUC), defined as the area under the best-so-far evaluation score curve over cumulative LLM cost, up to the budget. Across 10 mathematical and systems optimization tasks, FrugalEvo matches or surpasses state-of-the-art baselines, including OpenEvolve, ShinkaEvolve, AdaEvolve, and EvoX, in final solution quality and achieves higher BA-AUC on 9 tasks. It also achieves higher average performance than these baselines on 10 algorithmic optimization tasks from ALE-Bench-Lite. Notably, on circle packing, FrugalEvo achieves new state-of-the-art performance with GPT-5.6 Terra and Luna for only 1.68 USD and with GLM-5.3 and its Flash variant for only 0.55 USD, matching or surpassing all baselines, including multi-agent methods such as CORAL and SwarmResearch, which cost approximately 50 USD on average.

Figures & tables

Panel of Figure 1 — Figure 1: High-level overview of FrugalEvo . (a) compares the FrugalEvo framework with those of prior work. (b) and (c) evaluate methods on the circle packing task: (b) plots solution quality against cumulative API cost, and (c) reports the average cost per iteration. FrugalEvo pairs GLM 5.3 with the cheaper GLM 5.3 Flash, whereas all other methods use GLM 5.3 alone. Results are averaged over three runs, each given a budget of $1 (USD).

Figure 2: The FrugalEvo framework. It comprises six main components: (1) a cold-start module, (2) a context builder, (3) a strategy explorer, (4) a solution generator, (5) an evaluator, and (6) a search memory. Our search memory uses island-based MAP-Elites ( Mouret and Clune, 2015 ; Tanese, 1989 ) algorithm.

	GPT-5.6 Terra/Luna ($2)			GLM-5.3/Flash ($1)
Method	Avg.	Best	BA-AUC@2	Avg.	Best	BA-AUC@1
Circle Packing ( $\uparrow$ ) AlphaEvolve: $2.635000$
OpenEvolve	$2.634206_{\pm 0.0015}$	$2.635983$	$1.9709_{\pm 0.0007}$	$2.555418_{\pm 0.0321}$	$2.598002$	$0.9438_{\pm 0.0157}$
ShinkaEvolve	$2.630981_{\pm 0.0003}$	$2.631285$	$1.9653_{\pm 0.0098}$	$2.504844_{\pm 0.0837}$	$2.615012$	$0.9280_{\pm 0.0259}$
AdaEvolve	$2.632514_{\pm 0.0031}$	$2.634305$	$1.9653_{\pm 0.0039}$	$2.618077_{\pm 0.0088}$	$2.628041$	$0.9375_{\pm 0.0162}$
EvoX	$2.635420_{\pm 0.0010}$	$2.635983$	$1.9549_{\pm 0.0228}$	$2.599142_{\pm 0.0434}$	$2.630972$	$0.9497_{\pm 0.0337}$

Table 1: Results on mathematical optimization problems. We report mean

\pm

sample standard deviation and best scores over three independent runs. “(

\uparrow

)” means the higher the better, while “(

\downarrow

)” means the lower the better. Bold indicates the best result for each metric within each task and model configuration. Light green highlights the best performance within each task across both model configurations.

Figure 3: Visualization of FrugalEvo solutions on the circle packing task. Left : initial program; Middle : FrugalEvo solution generated by GPT-5.6 Terra and Luna; Right : FrugalEvo solution generated by GLM 5.3 and its Flash variant.

	GPT-5.6 Terra/Luna ($1)			GLM-5.3/Flash ($0.5)
Method	Avg.	Best	BA-AUC@1	Avg.	Best	[email protected]
EPLB ( $\uparrow$ )
OpenEvolve	$0.1346_{\pm 0.0097}$	$0.1457$	$0.1291_{\pm 0.0006}$	$0.1352_{\pm 0.0101}$	$0.1468$	$0.0672_{\pm 0.0046}$
ShinkaEvolve	$0.1348_{\pm 0.0097}$	$0.1460$	$0.1314_{\pm 0.0044}$	$0.1404_{\pm 0.0094}$	$0.1469$	$0.0678_{\pm 0.0027}$
AdaEvolve	$0.1295_{\pm 0.0004}$	$0.1297$	$0.1293_{\pm 0.0003}$	$0.1291_{\pm 0.0012}$	$0.1298$	$0.0643_{\pm 0.0005}$
EvoX	$0.1355_{\pm 0.0099}$	$0.1470$	$0.1320_{\pm 0.0044}$	$0.1294_{\pm 0.0006}$	$0.1298$	$0.0641_{\pm 0.0002}$

Table 2: Results on systems optimization problems. We report mean

\pm

sample standard deviation and best scores over three runs. “(

\uparrow

)” means the higher the better, while “(

\downarrow

Figure 4: Average private performance across 10 ALE-Bench-Lite tasks. FrugalEvo uses GPT-5.6 Terra and Luna and other baselines use GPT-5.6 Terra. The budget is $1.

Figure 5: Best-so-far score curves on signal processing, heilbronn convex, and transaction scheduling. FrugalEvo uses GPT-5.6 Terra and Luna, while the baselines use GPT-5.6 Terra. The top row shows mean trajectories across three runs, and the bottom row shows the trajectory of the best-performing run for each method. BA-AUC values are printed along with method names.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Problem	Objective	Description
Circle Packing (Square)	$\max\sum_{i=1}^{26}r_{i}$	Pack 26 circles with variable radii into the unit square, maximizing the sum of their radii subject to non-overlap and containment constraints.
Signal Processing	Maximize composite score	Filter noisy, non-stationary time series, balancing directional reversals, recent and overall tracking errors, false reversals, correlation with the clean signal, noise reduction, and run success across five test signals.
Heilbronn Convex ( $n=13$ )	$\max A_{\min}/A_{\mathrm{hull}}$	Arrange 13 points in the plane to maximize the smallest triangle area over all point triples, normalized by the area of the convex hull of all 13 points.
Heilbronn Triangle ( $n=11$ )	$\max A_{\min}/A_{T}$	Place 11 points inside or on a fixed equilateral triangle of side length one, maximizing the smallest triangle area over all point triples, normalized by the container area $A_{T}=\sqrt{3}/4$ .
Min-Max Distance Ratio (3D)	$\max(d_{\min}/d_{\max})^{2}$	Arrange 14 points in three-dimensional Euclidean space to maximize the squared ratio of the minimum to maximum pairwise Euclidean distance, without a prescribed bounding region.

Appendix

Table 4: Mathematical optimization tasks. Summary of optimization tasks used to evaluate FrugalEvo , including geometric optimization and signal processing problems.

Problem	Objective	Description
EPLB (Expert Parallelism Load Balancer)	Maximize composite score	Replicate and place MoE experts across GPUs using recorded expert loads, balancing load across expert replicas while reducing rebalancing and simulation runtime.
PRISM (GPU Model Placement)	Minimize max KV-cache pressure	Assign models to GPUs under memory constraints, minimizing the maximum ratio of SLO-weighted request load to memory remaining for the KV cache.
LLM-SQL (Prefix Caching)	Maximize cache reuse and speed	Optimize column orderings when serializing table rows into LLM prompts, maximizing shared-prefix cache hits while minimizing reordering runtime across five datasets.
Cloudcast (Multi-Cloud Broadcast)	Minimize total cost	Construct partitioned broadcast routes from one source region to multiple destinations, exploiting shared relay paths to reduce egress and instance costs under heterogeneous bandwidths and pricing.
Transaction Scheduling	Minimize makespan	Order transactions with read–write and write–write conflicts on shared data items to minimize total simulated makespan across three workloads.

Appendix

Table 5: Systems optimization tasks. Benchmarks drawn from ADRS-Bench ( Cheng et al., 2025 ) , capturing realistic optimization problems from production systems.

Problem / Category	Count	Description
ahc008 (Territory)	1	Build partitions to maximize humans’ reachable space while reducing the number of pets sharing it.
ahc011 (Sliding Puzzle)	1	Slide tiles to form the largest tree; minimize moves once all tiles are connected.
ahc015 (Candy Clustering)	1	Tilt a box to cluster candies by flavor, maximizing the sum of squared cluster sizes.
ahc016 (Graph Classification)	1	Design graphs robust to edge noise and vertex relabelling, balancing classification errors against graph size.
ahc024 (Map Compression)	1	Minimize occupied map cells while preserving district connectivity and all adjacencies, including the exterior.
ahc025 (Weight Balancing)	1	Partition items of unknown weight using limited balance queries; minimize variation in group weights.

Appendix

Table 6: Algorithmic optimization tasks. Summary of the 10 algorithmic optimization problems from ALE-Bench-Lite ( Imajuku et al., 2026 ) , drawn from AtCoder Heuristic Contests, used to evaluate FrugalEvo .

Model	Input	Output	Cache Read	Cache Write
GPT-5.6-Terra	$2.00	$12.00	$0.20	$2.50
GPT-5.6-Luna	$0.20	$1.20	$0.02	$0.25
GLM-5.3	$1.15	$3.50	$0.10	—
GLM-5.3-Flash	$0.075	$0.25	$0.015	—

Appendix

Table 7: Model pricing. Prices were retrieved from the official OpenAI website and OpenRouter on September 4, 2026, for the GPT and GLM models, respectively. All prices are in USD per million tokens.

Large Language Model-Guided Optimization

Large Language Model-Guided Optimization uses language models to propose, steer, and refine solutions to hard search and design problems.

See all 587 papers

Feb 10, 2026

ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search

LLM-guided evolutionary computation, most notably AlphaEvolve, has been remarkably successful in discovering novel mathematical constructions by solving challenging optimization problems. The standard approach is to evolve a monolithic program that directly outputs a candidate solution. We present ImprovEvolve, an algorithmic alternative that drastically reduces cognitive load on the LLM. Instead of prompting the model for an end-to-end optimizer, we evolve a program with three specialized operators of initialization, local improvement, and perturbation. We then approach the optimum by iteratively applying local improvements and intensity-scheduled perturbations, effectively driving a basin-hopping search with LLM-evolved subroutines. For hexagon in hexagon packing, ImprovEvolve discovers new state-of-the-art packings of 11, 12, 15, and 16 hexagons, and additionally for 14, 17, and 23 hexagons after minimal expert tuning of the generated code. For the second autocorrelation inequality, the evolved and human-scaled program pushes the lower bound from 0.96102 to 0.96258. For spherical codes, the ImprovEvolve program lowers the best-known maximum cosine for the majority of 90 randomly chosen diverse state-of-the-art spherical codes, achieving relative improvements of up to 2.4%.

Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

1MIRIAI, Russia · 2FusionBrain Lab, Russia · 3AXXX, Russia +1

Large Language Model-Guided Scientific Discovery Evolutionary Optimization Metaheuristic Optimization Large Language Model-Guided Optimization Combinatorial Optimization Global Optimization+2

Ask PDF

Apr 12, 2026

TurboEvolve: Towards Fast and Robust LLM-Driven Program Evolution

LLM-driven program evolution can discover high-quality programs, but high API cost and run-to-run variance hinder reliable progress. We propose TurboEvolve, a multi-island evolutionary framework that improves sample efficiency and stability under matched API-cost budgets. Inspired by multiple-offspring strategies in evolutionary algorithms, TurboEvolve introduces Verbalized Sampling, which elicits K diverse candidates in one LLM call while using self-assigned probabilities only as generation signals, together with an online scheduler that adapts K to expand exploration under stagnation and reduce redundant generation during steady progress. To exploit existing solution pools, TurboEvolve further introduces island-aware initialization, which clusters seed programs into mode-specific subpopulations and applies controlled cross-cluster mixing with elitist preservation to balance diversity, sharing, and refinement. We also curate a reusable cross-task solution-pool dataset to support warm-start initialization studies and matched-resource comparisons. Across mathematical discovery and GPU-kernel optimization tasks, TurboEvolve achieves stronger cost-quality trade-offs and more stable performance than controlled baselines, while reaching competitive reported scores.

Yang Yang, Zining Zhong, Jindong Li +5

Artificial Intelligence Thrust, Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China.

Large Language Model-Guided Optimization Evolutionary Optimization LLMs for Evolutionary Optimization

Ask PDF

Sep 4, 2026

LLM-Guided Program Evolution for Circle Packing: Breaking 10 Packomania Records for $28

We present Discovery Loop, a lightweight system that uses a large language model (LLM) to iteratively evolve optimization algorithms. Starting from a simple seed solver, the LLM proposes algorithmic improvements guided by a scoreboard of results and a history of prior ideas. Each candidate is evaluated against an independent verifier; improvements are kept and failures discarded. Applied to the Packomania circle-packing benchmark (csqv: maximize the sum of radii of N variable-radius circles in the unit square), the system improved the best known solutions for 10 values of N in the range 101-114, with gains of 2.4%-5.4% over prior records, all within 15 iterations and at a total LLM cost of $27.72. These results have been independently accepted by Packomania. We describe the method, analyze cost-efficiency dynamics including an adaptive plateau-detection mechanism, and discuss implications for democratizing automated scientific discovery.

Wes Sander

Practical Systems Mason, Ohio, USA

Automated Algorithm Discovery Large Language Model-Guided Optimization LLM-Based Program Synthesis

Ask PDF

Abstract

Large Language Model-Guided Optimization

Explore similar work

ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search

TurboEvolve: Towards Fast and Robust LLM-Driven Program Evolution

LLM-Guided Program Evolution for Circle Packing: Breaking 10 Packomania Records for $28