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.NE, cs.AI, cs.CL
2026-10-03
FrugalEvo assigns strategies to a costly LLM and code to a cheap one. BA-AUC is higher on 9 of 10 math and systems tasks; circle packing reaches 2.63599 for $0.55.
AlphaEvolve, OpenEvolve, and ShinkaEvolve ask an LLM to edit a program, keep the high-scoring versions, and mutate those parents. Curves are drawn against iteration count. A frontier-model step can cost an order of magnitude more than a cheap-model step, so matching round counts does not match spend.
On these tasks the LLM call usually costs more than the evaluator. Hitting a final score at the end of the budget is a different outcome from locking it in by $0.20. FrugalEvo pushes quality up inside a fixed dollar budget. BA-AUC is the integral of the best-so-far score over cumulative LLM spend, up to that budget. If a run stops early, the score is held flat until the cap before the area is computed.
Each candidate is split in two. The expensive model only proposes strategies. One call returns several distinct edits, each naming the region to change, why the score might rise, and a compute cap. The cheap model writes the code. It tries every strategy once, ranks them by score, then refines in that order. The parent stays fixed for a set number of attempts. The first program that beats the incumbent becomes the new parent, and the same strategy continues. A strategy that never improves is dropped.
A cold start runs before that loop. The task's example program is usually weak, and spending the strong model on it burns budget on poor ideas. The cheap model edits the example until the score stalls. That program is the first parent.
Prompts are ordered for prefix caching. Task instructions and the output format come first, island-best and elite programs next, random samples after that, and fresh feedback last. A shared prefix reuses cached KV states and is billed at the cache-read rate. The archive is island-based MAP-Elites, which also stores which strategies worked. Search stops when the remaining budget cannot pay for another call.
Both setups share a dollar budget and report the mean of three runs. FrugalEvo uses GPT-5.6 Terra for strategies and Luna for code. The baselines use Terra for every call. Math tasks get $2. Systems and algorithm tasks get $1. The second setup pairs GLM-5.3 with the cheaper Flash variant against baselines that use only GLM-5.3, at $1 for math and $0.50 for systems. Terra is $2 per million input tokens and $12 per million output tokens. Luna is $0.20 and $1.20.
Circle packing places 26 variable-radius circles in the unit square and maximizes the sum of radii. The initial program scores 0.95976. Terra plus Luna reaches 2.635996, and the cost to that solution is $1.68. GLM-5.3 plus Flash reaches 2.635990 for $0.55. AlphaEvolve's published number is 2.635000. CORAL and SwarmResearch report about 2.635985 and 2.635996, at roughly $50 on average. The GPT setup ties SwarmResearch. The GLM setup is 0.000006 lower and still above CORAL. Under the shared $1 GLM budget, FrugalEvo's mean is 2.635422, AdaEvolve is next at 2.618077, and OpenEvolve is at 2.555418. Average cost per iteration on this task is $0.0097 for FrugalEvo and $0.0435 for OpenEvolve.
Final scores sit on top of each other once a task is saturated. With the GPT budget, EvoX already averages 2.635420 on circle packing, against FrugalEvo's 2.635989. The separation shows up on signal filtering and transaction scheduling. On signal filtering, FrugalEvo's mean and best are 0.77791 and 0.78912, AdaEvolve's are 0.72031 and 0.73677, and OpenEvolve's mean is 0.55003. BA-AUC for those three is 1.4819, 1.2520, and 1.0802. On transaction scheduling, FrugalEvo averages 4252.1 with a best of 4405.3, against OpenEvolve at 4091.9 and 4237.3. On all three plotted tasks the lead is in place before $0.20 and holds through the rest of the budget.
Across the 10 math and systems tasks, final quality is matched or better in most cells, and BA-AUC is higher on 9. The miss is Cloudcast under GPT, where every method finishes near a cost of 618.1. On the four math tasks with published AlphaEvolve numbers, the stronger of the two setups matches or beats those numbers. The two Heilbronn tasks reach 0.03094 and 0.03653 only with GLM. On ten ALE-Bench-Lite contests, every method starts from ALE-Agent programs. Mean private score is 1924.9 for FrugalEvo, 1887.5 for OpenEvolve, and 1881.9 for AdaEvolve.
The signal-filtering ablation is the clean comparison. Terra for both stages drops the mean to 0.68534. Luna for both stages scores 0.74865. The split reaches 0.77791. The all-expensive setup falls further, which the paper attributes to implementation calls consuming the budget. Removing cold start drops the mean to 0.75576. Removing sequential feedback drops it to 0.76072 and widens the spread.
Code repair is most of the calls. Strategy choice does more to shape the solution. The strong model stays on strategies and can emit several in one call. The cheap model implements them in rank order and patches failures.
Set the budget in dollars and read BA-AUC when the question is who improves early. After prefixes are aligned, Terra's cache reads cost $0.20 per million tokens, against $2 for a normal input. The paper never isolates cache hit rate, so that saving is mixed with the model split.
Against AdaEvolve, the signal-filtering mean moves from 0.72031 to 0.77791. Against OpenEvolve it moves from 0.55003 to 0.77791. Transaction scheduling's best moves from 4237.3 to 4405.3. Those quality gains are incremental. On circle packing the score ties multi-agent runs that cost about $50, at $0.55 with the GLM pair or $1.68 with the GPT pair.
The loop assumes every candidate can be executed and scored in code. It does not transfer to a wet-lab setting, where evaluation is a physical experiment. The strategy instructions are hand-written for computational optimization, not derived from each task.
Each cell is three runs. On Cloudcast with GLM, AdaEvolve's standard deviation is 216, so that mean is shaky. BA-AUC holds an early score flat out to the budget cap, which keeps awarding area to a method that found a good program quickly and then stopped. Caching has no ablation of its own. AlphaEvolve's cost is marked unknown in the figure, so a per-dollar comparison is not available.
Baselines were locked to the expensive model. The Terra-for-both and Luna-for-both ablations are the control, and both lose on signal filtering. What remains if OpenEvolve itself can call Flash or Luna is unmeasured. The last digits on circle packing come from raising radii inside the evaluator's tolerance, as the paper states. Whether that is a better geometry has no expert check. The ethics statement says the programs on all 20 tasks were only scored automatically.