FrugalEvo: Towards Cost-Aware LLM-Guided Program Evolution

FrugalEvo. Towards Cost-Aware LLM-Guided Program Evolution. By Hui Chen and seven others, from the National University of Singapore, the University of Washington, and two other institutions. Published on the second of October. Its code repository is worked out: about three thousand source files, with a readme and a licence.

Evolutionary methods guided by large language models, AlphaEvolve being the example named, have become powerful tools for hard computational optimisation problems such as circle packing. The way such work is usually judged is by how much performance it gains over a fixed number of iterations. The authors argue that this is the wrong target. An iteration can be cheap or expensive depending on which model runs it and how, and practical optimisation should maximise gain per unit of cost, not gain per step.

FrugalEvo is a cost-aware evolutionary framework built on a division of labour between two models. A stronger, higher-cost model explores solution strategies. A cheaper model implements those strategies and iteratively refines the resulting code. The expensive model is spent on deciding what to try, and the inexpensive one on the work of trying it.

A second saving comes from caching. The evolution process is designed to be cache-efficient: the harness and the prompts are arranged to share as much prefix as possible across evolution steps, so that more of the cache can be reused from one step to the next.

To judge quality throughout a fixed budget rather than only at the end, the authors introduce Budget-Aware Area Under the Curve, or BA-AUC. It is the area under the curve of the best evaluation score so far, plotted against cumulative model cost, up to the budget. A method that gets good early and cheaply scores higher than one that gets there late.

Across ten mathematical and systems optimisation tasks, FrugalEvo matches or surpasses state-of-the-art baselines, namely OpenEvolve, ShinkaEvolve, AdaEvolve and EvoX, in final solution quality, and achieves higher BA-AUC on nine of the tasks. On ten algorithmic optimisation tasks from ALE-Bench-Lite it achieves higher average performance than the same baselines.

Circle packing gives the sharpest cost comparison. FrugalEvo sets a new state of the art there using GPT five point six Terra and Luna, for only one point six eight dollars, and using GLM five point three with its Flash variant, for only zero point five five dollars. Those runs match or surpass all baselines, including multi-agent methods such as CORAL and SwarmResearch, which cost approximately fifty dollars on average.

The reframing is the contribution as much as the system. Once cost sits on the horizontal axis instead of iteration count, splitting the work between an expensive planner and a cheap implementer, and reusing the cache, become the natural things to optimise.