FrugalEvo: Towards Cost-Aware LLM-Guided Program Evolution
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
| GPT-5.6 Terra/Luna ($2) | GLM-5.3/Flash ($1) | |||||
| Method | Avg. | Best | BA-AUC@2 | Avg. | Best | BA-AUC@1 |
| Circle Packing ( ) AlphaEvolve: | ||||||
| OpenEvolve | ||||||
| ShinkaEvolve | ||||||
| AdaEvolve | ||||||
| EvoX | ||||||
| GPT-5.6 Terra/Luna ($1) | GLM-5.3/Flash ($0.5) | |||||
| Method | Avg. | Best | BA-AUC@1 | Avg. | Best | [email protected] |
| EPLB ( ) | ||||||
| OpenEvolve | ||||||
| ShinkaEvolve | ||||||
| AdaEvolve | ||||||
| EvoX | ||||||
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| Problem | Objective | Description |
| Circle Packing (Square) | 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 ( ) | 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 ( ) | 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 . | |
| Min-Max Distance Ratio (3D) | 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. |
| 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. |
| 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. |
| 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 | — |
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