FrugalEvo: Towards Cost-Aware LLM-Guided Program Evolution

AI summary

Overview

Research area: LLM-guided evolutionary program search for computational optimization (cs.NE), with a focus on inference cost efficiency.

Technical level: Intermediate. The ideas are conceptually accessible (strong model plans, cheap model codes, cost is the budget), but the evaluation uses evolutionary-search terminology, prompt-caching mechanics, and area-under-curve metrics.

Scope: The paper proposes FrugalEvo, a cost-aware framework that splits LLM-guided program evolution between an expensive strategy-proposing model and a cheap code-writing model, introduces the Budget-Aware Area Under the Curve (BA-AUC) metric, and evaluates on 20 optimization tasks against four evolutionary baselines plus reported AlphaEvolve, CORAL, and SwarmResearch results.

What This Paper Is About

Most LLM-guided evolutionary systems (AlphaEvolve, OpenEvolve, ShinkaEvolve, AdaEvolve, EvoX) are judged by how good a solution they reach after a fixed number of iterations or LLM calls. That framing ignores money: because AI agents often improve with more test-time compute, a better final score may simply mean a larger bill. FrugalEvo reframes the goal as maximizing solution quality per unit of cost under a fixed budget, and asks whether splitting the work between a strong (expensive) model and a weak (cheap) model produces better programs per dollar.

Key Contributions

1. A cost-centric evaluation argument and metric. The authors argue that practical LLM-guided evolution should maximize gain per unit cost, and introduce Budget-Aware Area Under the Curve (BA-AUC), the integral of the best-so-far evaluation score over cumulative LLM cost up to a budget B.
2. The FrugalEvo framework. A cost-aware evolutionary framework in which a strong, high-cost LLM explores design strategies while a weaker, low-cost LLM implements those strategies as executable code and iteratively refines them.
3. A cache-efficient evolution process. The harness and prompts are structured so that fixed content comes first and frequently changing content last, maximizing shared prompt prefixes and therefore API prompt-cache reuse across evolution steps.
4. Broad empirical evaluation. FrugalEvo is tested on 20 real-world optimization tasks (5 mathematics, 5 systems from ADRS, 10 algorithmic from ALE-Bench-Lite), matching or surpassing OpenEvolve, ShinkaEvolve, AdaEvolve, and EvoX in solution quality and achieving higher BA-AUC on 9 of the 10 mathematics and systems tasks.

Main Findings

• Better BA-AUC on 9 of 10 tasks. Across the 10 mathematics and systems optimization tasks, FrugalEvo matches or surpasses the baselines in final solution quality and achieves higher BA-AUC on 9 tasks.
• All five mathematics tasks. FrugalEvo achieves the highest mean BA-AUC on all five mathematics tasks under both model configurations, and the best or comparable mean performance on all five with GPT-5.6 Terra and Luna and on four with GLM-5.3 and the Flash variant.
• Circle packing state of the art. FrugalEvo improves the sum of radii on Circle Packing from 0.95976 to 2.635996 using GPT-5.6 Terra and Luna for $1.68, and to 2.635990 using GLM-5.3 and its Flash variant for $0.55. The abstract also states a sum of radii of 2.63599 for $0.55 with GLM-5.3 and Flash. In Table 1, the GPT-5.6 Terra/Luna mean is 2.635989 ± 0.0000 with best 2.635996 and BA-AUC@2 of 1.9925 ± 0.0028; the GLM-5.3/Flash mean is 2.635422 ± 0.0008 with best 2.635990 and BA-AUC@1 of 0.9939 ± 0.0039.
• Dramatic cost gap versus multi-agent methods. CORAL and SwarmResearch achieve 2.635985 and 2.635996 respectively but cost approximately $50 on average, compared with $1.68 and $0.55 for FrugalEvo.
• Matches or beats AlphaEvolve on four tasks. FrugalEvo matches or exceeds the reported AlphaEvolve results on Circle Packing, Heilbronn Convex (13), Heilbronn Triangle, and Min-Max-3.
• Systems optimization. On the five ADRS tasks (EPLB, PRISM, LLM-SQL, Cloudcast, Transaction Scheduling), FrugalEvo achieves the best or comparable mean and best performance on all five under both model configurations, with the highest mean BA-AUC on four tasks. Examples include EPLB best 0.1471 with GPT-5.6 Terra/Luna ($1 budget) and 0.1473 with GLM-5.3/Flash ($0.5 budget), and Transaction Scheduling best 4405.29 and 4366.81 respectively.
• Highest average on ALE-Bench-Lite. On the 10 algorithmic optimization tasks, FrugalEvo scores 1924.9, ahead of OpenEvolve (1887.5) and AdaEvolve (1881.9).
• Faster early progress per dollar. On Signal Processing, Heilbronn Convex (13), and Transaction Scheduling, FrugalEvo establishes a clear performance advantage within the first $0.2 and maintains it throughout the remaining search.
• Qualitatively distinct solutions. On Circle Packing it evolves five-row layouts with asymmetric displacements, refining them through constrained SLSQP optimization and fixed-center radius linear programming. On Signal Processing it adaptively blends Savitzky–Golay, Butterworth, and spectral filters while suppressing minor reversals. On Heilbronn Convex (13) it uses multistart hill climbing, linear programming refinement, and convex-hull area reduction. On AHC016 (graph classification) it constructs graphs from disjoint cliques and their complements; on AHC027 (cleaning route) it plans revisits using dirt accumulation rates, time since the last visit, and travel distances.
• Ablations confirm both design choices matter. With GPT-5.6 Terra and Luna, using the high-cost model for both stages (Terra + Terra) drops Signal Processing mean performance to 0.68534 ± 0.0352, and using only the low-cost model (Luna + Luna) gives 0.74865 ± 0.0097, versus 0.77791 ± 0.0145 for full FrugalEvo. Removing the cold start gives 0.75576 ± 0.0240 and removing sequential feedback gives 0.76072 ± 0.0209 on the same task.

Methodology in Plain English

FrugalEvo keeps a pool of candidate programs and their scores, and runs a loop until the money runs out.

First, a cold-start phase uses the cheap model to iteratively polish the task's initial program until its score stops improving, so the search does not begin from a weak parent. A context builder then uses the expensive model to read the problem description and evaluator code, identify the optimization objective and constraints, and assemble a search context from the incumbent program and retrieved history.

Each round, a strategy explorer (the strong, high-cost LLM) proposes several distinct design strategies in a single API call, each explaining what to change, why it might help, and what computational limits apply. A solution generator (the cheap LLM) turns each strategy into code, ranks strategies by the scores of their first implementations, and then refines the best ones over up to M sequential attempts, feeding back what failed. As soon as an attempt beats the incumbent, the incumbent is updated and a new round starts; otherwise the generator moves to the next strategy.

Two cost-saving tricks are central. The prompts are ordered so that fixed task instructions and output requirements come first, then slowly changing context (island-best and elite programs before randomly sampled ones), and finally frequently changing content — maximizing shared prefixes so API prompt caching can reuse key-value states. And the search memory uses island-based MAP-Elites to preserve diversity while storing programs, scores, attempted strategies, and failure feedback.

Evaluation is by task-specific scoring functions. To compare methods fairly, they fix a cost budget ($2 or $1 for mathematics depending on the model configuration, $1 or $0.5 for systems and algorithmic tasks), hold the best-so-far score flat if a run finishes early, and truncate the curve if it overshoots. All results are averaged over three independent runs.

Why This Matters

Impact on research. The paper shifts the evaluation target for LLM-guided evolutionary search from "best score after N iterations" to "best score per dollar," and supplies a concrete metric (BA-AUC) for doing so. It also shows that heterogeneous model pairing — strong model for strategy, cheap model for implementation — is a viable design axis, without any model training, token-logprob access, or verifier signals.

Real-world applications (drawn from the tasks evaluated):

• Geometric packing problems such as circle packing, where FrugalEvo found layouts with a sum of radii of 2.635996 / 2.635990.
• Signal processing filter design, where it blends Savitzky–Golay, Butterworth, and spectral filters to reach 0.78912.
• Systems infrastructure, including expert load balancing (EPLB) and transaction scheduling that reduces makespan (combined score 4405.29).
• Heuristic algorithm design for competitive-programming-style tasks, including graph classification (AHC016) and cleaning route planning (AHC027).

Industry relevance. The headline numbers are economic: a $0.55 or $1.68 run that matches or beats methods costing roughly $50 on average is a large cost reduction on a per-task basis. Cache-aware prompt construction and explicit budget-based stopping are directly relevant to anyone running LLM-based search in production, where API spend rather than iteration count determines viability.

Future Directions

• Extending beyond code-evaluable domains. The authors state that the two-model split depends on solutions being generated and evaluated entirely inside a code environment, so the method does not readily extend to domains requiring physical-world interaction, such as biology where evaluation may require wet-lab experiments.
• Automating strategy instructions. Current strategy-exploration instructions are manually designed for computational optimization tasks rather than automatically derived from each task; the authors list automatic generation of these instructions as future work.
• Broadening the cost model. The work focuses on LLM

Authors’ 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.