PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.03675v1cs.NEcs.AIcs.CL

TL;DR

Fixed-iteration comparisons can overlook the total cost of LLM-guided optimization. FrugalEvo pairs strong-model strategy exploration with cheaper code refinement and cache-efficient prompts, and reports competitive results across mathematical, systems, and algorithmic tasks.

  • Problem

    Fixed-iteration performance comparisons can overlook total costs, so higher scores alone do not establish greater efficiency.

    Source: §1 · p. 2

  • Method

    FrugalEvo uses a high-cost LLM to explore strategies and a cheaper LLM to implement and refine code, with prefix-sharing prompts and BA-AUC for fixed-budget quality.

    Source: §1 · p. 2

  • Results

    Across 20 tasks, FrugalEvo matches or surpasses baselines in solution quality, has higher BA-AUC on 9 of 10 mathematical and systems tasks, and leads average performance on 10 algorithmic tasks.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    BA-AUC complements final-score comparisons by tracking solution quality throughout a fixed LLM-cost budget.

    Source: §1 · p. 2

    FrugalEvo is tailored to settings where solution generation and evaluation occur in code; it does not readily extend to physical-world domains such as wet-lab biology.

    Source: §5 · pp. 9–10

Abstract

from arXiv · show

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.

1 INTRODUCTION

FrugalEvo shifts LLM-guided optimization toward solution quality per cost, combining strong-model strategy exploration with cheaper code refinement and cache-efficient prompts. It evaluates quality across cost budgets and reports competitive results across mathematical, systems, and algorithmic tasks.

1 INTRODUCTION

  • Fixed-iteration scores can obscure expenditure, so BA-AUC tracks solution quality across cost budgets alongside final scores.The paper argues that practical optimization should maximize performance gain per unit cost.Source: §1 · p. 2
  • FrugalEvo assigns strategy exploration to a strong, high-cost LLM and code implementation and refinement to a cheaper model.The framework focuses on LLM inference because it often accounts for the largest proportion of search costs in this domain.Source: §1 · p. 2
  • Its harness and prompts maximize shared prefixes across evolution steps, facilitating prompt-cache reuse.Inference systems and APIs can reuse cached key-value states for identical prompt prefixes, reducing latency and cost.Source: §1 · p. 2
  • On 9 of 10 mathematical and systems optimization tasks, FrugalEvo matches or outperforms OpenEvolve, ShinkaEvolve, AdaEvolve, and EvoX in final solution quality and BA-AUC.It also achieves the highest average performance across 10 algorithmic optimization tasks.Source: §1 · pp. 2–3
  • On Circle Packing, GLM-5.3 and Flash attain a sum of radii of 2.63599 for $0.55, surpassing baselines including multi-agent methods costing about $50 on average.FrugalEvo also matches or surpasses reported AlphaEvolve results on all four mathematical tasks with available comparisons.Source: §1 · p. 2

2 FRUGALEVO: COST-AWARE PROGRAM EVOLUTION

FrugalEvo formulates program evolution under a fixed cost budget and combines a high-cost strategy explorer with a low-cost solution generator. Its process also uses a cold start, an evolving search context, cache-efficient prompts, evaluation, and search memory.

2.1 PROBLEM FORMULATION

  • The search context combines task information, a parent program, sampled reference programs, evaluation results, and prior-attempt summaries; generated candidates are evaluated and recorded in a program database.Evaluation returns a task-specific score and auxiliary feedback.Source: §2.1 · p. 3
  • BA-AUC measures improvement efficiency within a fixed LLM cost budget using the best-so-far score over cumulative cost.For comparisons over the same budget interval, runs ending early hold their best-so-far score constant, while runs exceeding the budget are truncated.Source: §2.1 · p. 3

2.2 OUR APPROACH

  • FrugalEvo uses a high-cost LLM to propose strategies and a low-cost LLM to implement and refine them, repeating until the budget is exhausted and returning the best program found.The framework includes cold start, context building, strategy exploration, solution generation, evaluation, and search memory.Source: §2.2 · pp. 3–5
  • A low-cost LLM refines the initial program until its score stops improving, and the best result becomes the first incumbent and parent for strategy exploration.The context builder analyzes the problem description and evaluator code, then updates search context with incumbents, attempts, strategies, and feedback from search memory.Source: §2.2 · p. 4
  • Cache-efficient prompts place fixed content first, followed by less frequently changing context and then changing information, to maximize shared prefixes across attempts.Attempt feedback is appended at the end of the prompt.Source: §2.2 · p. 4
  • Island-based MAP-Elites search memory stores programs, results, proposed strategies, attempt outcomes, and failure feedback while maintaining program diversity.The evaluator uses task-specific scoring functions, and evolution stops when the remaining budget cannot cover further LLM calls.Source: §2.2 · p. 5

3 EXPERIMENTS

Across mathematical, systems, and algorithmic optimization tasks, FrugalEvo achieves strong final scores and cost-aware performance, with ablations supporting its model collaboration, cold start, and sequential feedback components.

3.1 EXPERIMENTAL SETUP

  • The evaluation covers 20 tasks across mathematics, ADRS systems, and ALE-Bench-Lite algorithmic optimization, using two model configurations and task-specific LLM cost budgets.Baselines include OpenEvolve, ShinkaEvolve, AdaEvolve, and EvoX; AlphaEvolve results are also reported for mathematical tasks.Source: §3.1 · p. 5

3.2 MAIN RESULTS

  • FrugalEvo achieves the highest mean BA-AUC on all five mathematical tasks under both model configurations and matches or exceeds AlphaEvolve on four tasks.It also has best or comparable mean performance on all five tasks with GPT-5.6 Terra and Luna, and on four with GLM-5.3 and Flash.Source: §3.2 · p. 5, Table 1 · p. 6
  • Circle Packing reaches total radii of 2.635996 for $1.68 and 2.635990 for $0.55, comparable to CORAL and SwarmResearch results costing about $50 on average.The initial program's sum of radii is 0.95976.Source: §3.2 · pp. 5–6, Figure 3 · p. 6
  • FrugalEvo achieves the best or comparable mean and best performance on all five systems tasks under both configurations, with the highest mean BA-AUC on four.On Transaction Scheduling, its combined score is 4405.29.Source: Table 2 · p. 7, §3.2 · p. 7
  • FrugalEvo establishes a performance advantage within the first $0.2 on three tasks and maintains it through the remaining search, with higher mean BA-AUC on all three.Figure 5 shows mean trajectories across three runs and best-performing-run trajectories.Source: Figure 5 · p. 8, §3.2 · p. 8
  • On ALE-Bench-Lite, FrugalEvo scores 1924.9, above OpenEvolve (1887.5) and AdaEvolve (1881.9).Figure 4 reports average private performance across 10 tasks with a $1 budget.Source: Figure 4 · p. 8, §3.2 · p. 8

3.3 ABLATIONS

  • Using either the high-cost or low-cost model for both stages yields lower mean and best performance than FrugalEvo on both ablation tasks.The authors suggest single-model high-cost runs spend budget on implementation, while low-cost-only runs may identify promising strategies less effectively.Source: §3.3 · pp. 8–9
  • Removing cold start lowers mean and best performance on both tasks, while removing sequential feedback lowers mean performance and increases run-to-run standard deviation.The authors describe initial-program refinement as a cost-effective support for strategy exploration and earlier-attempt feedback as improving refinement and stability.Source: §3.3 · p. 9

4 RELATED WORK

Prior LLM-guided evolutionary work often compares performance after fixed iteration counts, while FrugalEvo emphasizes gain per unit cost and allocates model capability to optimization tasks without extra model training or token-level probabilities.

4 RELATED WORK

  • LLM-guided evolutionary methods have advanced mathematical, algorithmic, and systems optimization, but prior approaches focus on performance gains over fixed iteration counts.The cited approaches include FunSearch, AlphaEvolve, OpenEvolve, ShinkaEvolve, AdaEvolve, EvoX, and multi-agent methods.Source: §4 · p. 9
  • Cost-efficient LLM inference research includes cascades, routing, reflection, and caching, alongside methods such as FrugalGPT and RouteLLM.Other cited work applies post-training or model-confidence signals to scientific discovery and verifier-free evolution.Source: §4 · p. 9
  • FrugalEvo allocates model capability according to computational optimization task characteristics without additional model training or token-level probabilities.This contrasts with prior approaches described as learning cascades or routing and using models' confidence signals.Source: §4 · p. 9

5 CONCLUSION

FrugalEvo combines high-cost strategy exploration with low-cost code implementation and refinement, and evaluates quality throughout a fixed cost budget. It matches or surpasses baselines in solution quality and achieves higher BA-AUC on most tasks, while its design remains tailored to automatically evaluated code environments.

5 CONCLUSION

  • Across diverse real-world computational optimization tasks, FrugalEvo matches or surpasses all baselines in solution quality and achieves higher BA-AUC on the majority of tasks.BA-AUC assesses solution quality throughout a fixed cost budget.Source: §5 · p. 9
  • FrugalEvo assigns strategy exploration to a strong, high-cost model and code implementation and refinement to a low-cost model, alongside a cache-efficient evolution process.The framework also introduces BA-AUC to measure solution quality throughout a fixed cost budget.Source: §5 · p. 9
  • FrugalEvo is tailored to code environments where both solution generation and evaluation are automatic, limiting its ready extension to domains such as biology that require physical-world experiments.The strategy-exploration instructions are manually designed for computational optimization rather than automatically derived for each task.Source: §5 · p. 10

AI USE STATEMENT

The authors used LLMs as general-purpose writing assistants and coding agents, while retaining responsibility for the research process and scientific claims.

AI USE STATEMENT

  • LLMs served as general-purpose writing assistants and coding agents to implement the algorithm and run experiments.The authors prepared the experimental plan, codebase, and datasets before directing coding agents to implement the method and execute experiments.Source: AI USE STATEMENT · p. 10
  • The human authors were responsible for the entire research process, including initial ideation, experimental design, and data analysis.Source: AI USE STATEMENT · p. 10
  • The authors drafted each section and used LLMs to improve clarity, coherence, and grammar.They drafted the core ideas and technical details.Source: AI USE STATEMENT · p. 10
  • The authors state that all scientific claims and findings originate from them and that they take full responsibility for the final content.Source: AI USE STATEMENT · p. 10

ETHICS STATEMENT

The authors report adherence to the ICLR Code of Ethics and limit the intended status of their generated solutions to research reference.

ETHICS STATEMENT

REPRODUCIBILITY STATEMENT

The authors say they will release code, data, and supplementary materials upon publication. The appendix contents list benchmark and algorithm sections, and describe FrugalEvo as a four-phase process.

REPRODUCIBILITY STATEMENT

Appendix

  • The appendix contents list mathematical, systems, and algorithmic challenge benchmark subsections, alongside algorithm-description and prompts headings.The contents also list model pricing.Source: Appendix · p. 13, C Model Pricing · p. 13

A ALGORITHM DESCRIPTION

  • FrugalEvo’s algorithm is described in four phases: cold start, strategy exploration, initial code implementation and strategy ranking, and iterative code refinement.Source: A ALGORITHM DESCRIPTION · p. 13
  • The algorithm begins with cheap search until stalled, then explores strategies with the high-cost LLM and runs low-cost-model trials before iterative refinement.The pseudocode ranks strategies by trial scores and records global improvement during refinement.Source: A ALGORITHM DESCRIPTION · p. 13

B BENCHMARK DETAILS

The benchmark suite covers 20 optimization problems across mathematical, systems, and algorithmic domains.

  • 20 optimization problems span mathematical optimization (5), systems optimization (5), and algorithmic challenges (10).Source: B BENCHMARK DETAILS · p. 14

B.1 MATHEMATICAL OPTIMIZATION

The benchmark details cover geometric and signal-processing problems, production-systems tasks, and algorithmic challenges from ALE-Bench-Lite.

B.1 MATHEMATICAL OPTIMIZATION

  • Mathematical optimization benchmarks include geometric optimization and signal processing problems.Source: Table 4 · p. 14

B.2 SYSTEMS OPTIMIZATION

  • Systems optimization benchmarks are drawn from ADRS-Bench and capture realistic production-systems problems.Source: Table 5 · p. 14

B.3 ALGORITHMIC CHALLENGES

  • The algorithmic benchmarks comprise 10 ALE-Bench-Lite problems drawn from AtCoder Heuristic Contests.Source: Table 6 · p. 15

C MODEL PRICING

The appendix reports model pricing and provides prompts for strategy exploration and code implementation and refinement.

C MODEL PRICING

  • Model-pricing details cover GPT-5.6 Terra/Luna and GLM-5.3/Flash token prices in USD per million tokens.Prices were retrieved from official OpenAI and OpenRouter sources on September 4, 2026, respectively.Source: Table 7 · p. 15, C MODEL PRICING · p. 15

D PROMPTS

  • The strategy prompt requests distinct, self-contained mechanisms with replacement scope, compute budgets, and an expected-gain check.It also directs the designer to use previous results and failures to avoid exhausted approaches.Source: D PROMPTS · p. 16
  • The implementation prompt supplies task constraints, a parent program, metrics, and a strategy; subsequent attempts use evaluation feedback to repair or revise implementations.It directs the model to implement the strategy faithfully, preserve validity and interfaces, and avoid repeating failed patches.Source: D PROMPTS · pp. 16–17
Loading 2610.03675v1…