Paper deep dive
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
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.03675v1
- Canonical: https://arxiv.org/abs/2610.03675v1
Trouble viewing inline? Open PDF directly →
Full Text
61,992 characters extracted from source content.
Expand or collapse full text
FrugalEvo: Towards Cost-Aware LLM-Guided Program Evolution Hui Chen †thanks: Correspondence to: hui.chen@nus.edu.sg Affiliation: National University of Singapore Xuan Qi Affiliation: University of Washington James Xu Zhao Affiliation: National University of Singapore Zhaopeng Feng Affiliation: National University of Singapore Shilong Liu Affiliation: Princeton University Kuang Xu Pang Wei Koh Bryan Hooi Affiliation: National University of Singapore Affiliation: University of Washington Affiliation: Stanford University[0.25em] Code: https://github.com/chchenhui/frugalevo 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 and with GLM-5.3 and its Flash variant for only $0.55, matching or surpassing all baselines, including multi-agent methods such as CORAL and SwarmResearch, which cost approximately $50 on average. (a) Comparison of frameworks. (b) Solution quality vs. cost. (c) Average cost per iteration. Figure 1: High-level overview of FrugalEvo. (a) compares the FrugalEvo framework with those of prior work. (b) and (c) evaluate methods on the circle packing task: (b) plots solution quality against cumulative API cost, and (c) reports the average cost per iteration. FrugalEvo pairs GLM 5.3 with the cheaper GLM 5.3 Flash, whereas all other methods use GLM 5.3 alone. Results are averaged over three runs, each given a budget of $1 (USD). 1 Introduction Rapid advances in large language models (LLMs) have accelerated scientific discovery across diverse domains (Feng et al., 2026b; Liu et al., 2026a; Wang et al., 2026). In particular, LLM-guided evolutionary methods, such as AlphaEvolve (Novikov et al., 2025), OpenEvolve (Sharma, 2025), and ShinkaEvolve (Lange et al., 2026), have shown promise in computational optimization problems, including mathematics (Glazer et al., 2024), systems (Cheng et al., 2025), and algorithmic optimization (Imajuku et al., 2026). These methods typically maintain a pool of high-performing programs or solutions; they iteratively select a parent from this pool, prompt an LLM to propose a mutation, and then evaluate the resulting candidate. Progress is often measured as performance after a given number of evolutionary iterations (Liu et al., 2026b; Cemri et al., 2026), with curves plotted against the number of LLM-generated candidates or evaluator calls. However, focusing on performance after a fixed number of iterations may overlook a key practical constraint in computational optimization: the total cost. This cost may include API fees or GPU compute costs for LLM inference, CPU compute costs for evaluator execution, and other CPU/GPU resource costs associated with task execution. On many challenging tasks, AI agents achieve better performance with more inference-time computation, a phenomenon known as test-time scaling (Snell et al., 2024; Brown et al., 2024; Muennighoff et al., 2025). Consequently, higher performance alone does not establish greater efficiency, as it may simply reflect higher expenditure. We therefore argue that methods should be assessed by their performance-cost trade-offs and their ability to maximize solution quality under a fixed cost budget. This shifts the focus from gain per iteration to gain per unit cost. To measure gain per unit cost, we introduce a new metric, Budget-Aware Area Under the Curve (BA-AUC), based on the performance achieved at each cost budget. Next, we propose FrugalEvo, a cost-aware LLM-guided evolutionary framework for computational optimization. Since LLM inference often accounts for the largest proportion of search costs in this domain, compared with those of evaluator execution and other CPU/GPU operations, we focus on improving the cost efficiency of LLM inference. As shown in Figure 1(a), FrugalEvo splits candidate program generation into two steps and uses two different models to carry them out: a strong, high-cost LLM explores diverse, promising design strategies, while a weaker, low-cost LLM implements them as executable programs and iteratively refines the resulting code. Beyond model collaboration, we design a cache-efficient evolution process for FrugalEvo. Inference systems and APIs that support prompt caching can reuse cached key-value (KV) states for identical prompt prefixes, reducing latency and cost. To facilitate this reuse, we design our harness and prompts to maximize the sharing of prefixes across different evolution steps, improving cache reuse. We evaluate FrugalEvo on 20 tasks spanning mathematical, systems, and algorithmic optimization (Section 3). With two model configurations—GPT-5.6 Terra and Luna (OpenAI, 2026), and GLM-5.3 and its Flash variant (Z.ai, 2026b; Z.ai, 2026a)—FrugalEvo matches or outperforms OpenEvolve (Sharma, 2025), ShinkaEvolve (Lange et al., 2026), AdaEvolve (Cemri et al., 2026), and EvoX (Liu et al., 2026b) in final solution quality and BA-AUC on 9 of 10 mathematical and systems optimization tasks. It also achieves the highest average performance across 10 algorithmic optimization tasks and matches or surpasses the reported AlphaEvolve (Novikov et al., 2025) results on all four mathematical tasks with available comparisons. Notably, as shown in Figure 1(b), FrugalEvo achieves a sum of radii of 2.63599 on Circle Packing using GLM-5.3 and its Flash variant for only $0.55, surpassing all baselines, including multi-agent methods which cost approximately $50 on average. Moreover, Figure 1(c) shows that FrugalEvo substantially reduces the average cost per iteration. In summary, our contributions include: • We argue that practical LLM-guided evolutionary search in computational optimization should focus on improving performance gain per unit cost. In this work, we introduce Budget-Aware Area Under the Curve (BA-AUC) to assess solution quality throughout a fixed LLM cost budget, complementing evaluation based on final scores. • We propose FrugalEvo, a cost-aware evolutionary framework that combines strategy exploration by a strong, high-cost model with code implementation and refinement by a low-cost model, and design a cache-efficient evolution process. • We evaluate FrugalEvo on 20 real-world computational optimization tasks. FrugalEvo matches or surpasses all baselines, including OpenEvolve, ShinkaEvolve, AdaEvolve, and EvoX, in solution quality and achieves higher BA-AUC on 9 of 10 mathematical and systems optimization tasks. It also achieves the highest average performance on 10 algorithmic optimization tasks. 2 FrugalEvo: Cost-Aware Program Evolution 2.1 Problem Formulation Following prior work (Novikov et al., 2025; Romera-Paredes et al., 2024), we formulate LLM-guided evolutionary search as a program optimization process under a fixed budget. Candidate Evaluation. Let X denote the program space and let x0∈x_0 be an initial program, which is an example given by the task. An evaluator evaluates each candidate x∈x and returns a task-specific score and auxiliary feedback: E(x)=(s(x),a(x)),E:→ℝ×,E(x)=(s(x),a(x)), E:X ×A, (1) where s(x)∈ℝs(x) is the task-specific score to be maximized and a(x)∈a(x) contains auxiliary feedback. Program Database and Search Context. Evaluated programs and their results are stored in a program database. Evaluating the initial program x0x_0 initializes the database as 0=(x0,s0,a0)D_0=\(x_0,s_0,a_0)\. At iteration t, a search strategy S constructs a search context CS(t)C_S(D_t) by combining the task description and analysis with a parent program, sampled reference programs, their evaluation results, and summaries of previous attempts retrieved from tD_t. Conditioned on this context, an LLM GLLMG_LLM generates a new candidate, which is then evaluated: xt+1∼GLLM(⋅∣CS(t)),E(xt+1)=(st+1,at+1).x_t+1 G_LLM\! (· C_S(D_t) ), E(x_t+1)=(s_t+1,a_t+1). (2) The resulting record is added to the database as t+1=t∪(xt+1,st+1,at+1)D_t+1=D_t∪\(x_t+1,s_t+1,a_t+1)\. Optimization Goal. As cost is a key factor in determining the practical utility of an approach, we focus on maximizing solution quality s⋆=max(x,s,a)∈Bs = _(x,s,a) _Bs (3) under a fixed cost budget B. Budget-Aware AUC. We introduce Budget-Aware Area Under the Curve (BA-AUC) to measure how efficiently a method improves solution quality within a fixed LLM cost budget. Let q(c)q(c) denote the best-so-far evaluation score at cumulative LLM cost c. For a fixed cost budget B, we define BA-AUC(B)=∫0Bq(c)c.BA -AUC(B)= _0^Bq(c)\,dc. (4) To compare all methods over the same cost interval [0,B][0,B], we hold the best-so-far evaluation score constant up to B if a run ends before reaching the budget, and truncate the curve at B if the run exceeds it. Figure 2: The FrugalEvo framework. It comprises six main components: (1) a cold-start module, (2) a context builder, (3) a strategy explorer, (4) a solution generator, (5) an evaluator, and (6) a search memory. Our search memory uses island-based MAP-Elites (Mouret and Clune, 2015; Tanese, 1989) algorithm. 2.2 Our Approach Overview. Figure 2 presents an overview of our approach, which proceeds as follows: (1) starting from an initial program, the cold start module establishes an “incumbent”—the best-performing program found so far—as the parent code for strategy exploration and solution generation; (2) the context builder combines the problem context, task analysis, and incumbent program with information from search memory; (3) the strategy explorer uses a high-cost LLM to propose multiple design strategies; (4) the solution generator uses a low-cost LLM to implement and refine the proposed strategies; (5) the search memory updates the search context for the next round of strategy exploration; and (6) the process repeats until the budget is exhausted, returning the best program found. A detailed algorithm description is provided in Appendix A and prompts of strategy explorer and solution generator can be found in Appendix D. Cold Start. The strategy explorer generates design strategies based on a parent program. Using a weak initial program as the parent may lead to low-quality strategies and inefficient use of the cost budget. We therefore introduce a cold-start phase in which a low-cost LLM iteratively refines the initial program until the evaluation score no longer improves. The best resulting program becomes the initial incumbent and serves as the parent for the first round of strategy exploration. Context Builder. The context builder organizes task information and search history to guide strategy exploration. At the start of evolution, the context builder uses a high-cost LLM to analyze the problem description and evaluator code to identify the optimization objective and evaluation constraints. It combines this information with the incumbent program established by cold start and its evaluation feedback to construct the initial search context. As the search progresses, it updates the context with the latest incumbent and attempted programs, strategies, and evaluation feedback retrieved from the search memory, guiding subsequent strategy exploration. Cache-Efficient Prompt Construction. Specifically, to reduce input-token costs, we construct cache-efficient prompts by placing shared content at the beginning, enabling prefix reuse through API prompt caching.11 1 A couple of LLM API providers support prompt caching, allowing repeated prompt prefixes to be reused at a lower input-token cost; e.g., OpenAI: https://developers.openai.com/api/docs/guides/prompt-caching. To maximize prefix reuse between attempts, each prompt begins with fixed content (task instructions, output requirements, etc.). This is followed by information which changes less frequently, e.g., contextual examples, with island-best and elite programs appearing first before randomly sampled programs, lastly followed by frequently changing information, preserving the maximum amount of shared prefix across successive attempts. Additionally, feedback from each attempt is appended to the end of the prompt, allowing cache usage. Strategy Explorer. Since algorithmic design can substantially affect solution quality, we use a strong, high-cost LLM to explore diverse design strategies. Given the search context, including the parent program, evaluation feedback, and previously explored strategies, it proposes multiple distinct strategies in a single API call. Each strategy provides a concrete plan for modifying the parent program, explaining what to change, why it may improve performance, and what computational limits to follow. The proposed strategies are then passed to the solution generator for implementation and refinement. Solution Generator. The solution generator uses a low-cost LLM to implement and refine the proposed strategies. It first generates one trial implementation per strategy and ranks the strategies by their evaluation scores. It then follows this ranking to select strategies for further refinement. Each refinement round fixes one strategy and the current incumbent as the parent program, allowing up to M sequential implementation attempts. Each attempt is evaluated, and feedback from unsuccessful attempts informs subsequent prompts while the parent remains unchanged. As soon as an attempt improves the incumbent, the round ends, the improved program becomes the new incumbent, and another round begins with the same strategy and the updated parent. If a round ends without improvement, the generator moves to the next strategy. Evaluator and Search Memory. The evaluator assesses each generated candidate program using task-specific scoring functions. Search memory uses island-based MAP-Elites (Mouret and Clune, 2015; Tanese, 1989) to maintain program diversity. It stores candidate programs and their evaluation results, along with proposed strategies, the results of strategy attempts, and failure feedback. The evolution process stops when the remaining budget cannot cover further LLM calls and returns the best program found. 3 Experiments 3.1 Experimental Setup Tasks. We evaluate FrugalEvo on 20 real-world optimization tasks, including 5 mathematics optimization problems (Sharma, 2025), 5 systems optimization tasks from the ADRS benchmark (Cheng et al., 2025), and 10 algorithmic optimization problems from ALE-Bench-Lite (Imajuku et al., 2026). Benchmark details are provided in Appendix B. Baselines. We compare FrugalEvo against strong LLM-guided evolutionary methods, including OpenEvolve (Sharma, 2025), ShinkaEvolve (Lange et al., 2026), AdaEvolve (Cemri et al., 2026), and EvoX (Liu et al., 2026b). For mathematical tasks, we additionally report state-of-the-art results from AlphaEvolve (Novikov et al., 2025). Model Configurations and Budget. We use two model configurations in our evaluation. In the first configuration, FrugalEvo uses GPT-5.6 Terra (OpenAI, 2026) for strategy generation and GPT-5.6 Luna (OpenAI, 2026) for code implementation and refinement, while all four baselines use GPT-5.6 Terra. Each run receives an LLM cost budget of $2 per run for mathematical optimization tasks and $1 for systems and algorithmic optimization tasks. In the second configuration, FrugalEvo uses GLM-5.3 (Z.ai, 2026b) for strategy generation and GLM-5.3 Flash (Z.ai, 2026a) for implementation and refinement, while other baselines use GLM-5.3. The corresponding budgets are $1 for mathematical tasks and $0.5 for systems optimization tasks. Model Pricing details are provided in Appendix C. 3.2 Main Results Results on Math Optimization Tasks. Table 1: Results on mathematical optimization problems. We report mean ± sample standard deviation and best scores over three independent runs. “(↑ )” means the higher the better, while “(↓ )” means the lower the better. Bold indicates the best result for each metric within each task and model configuration. Light green highlights the best performance within each task across both model configurations. 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: 2.6350002.635000 OpenEvolve 2.634206±0.00152.634206_± 0.0015 2.6359832.635983 1.9709±0.00071.9709_± 0.0007 2.555418±0.03212.555418_± 0.0321 2.5980022.598002 0.9438±0.01570.9438_± 0.0157 ShinkaEvolve 2.630981±0.00032.630981_± 0.0003 2.6312852.631285 1.9653±0.00981.9653_± 0.0098 2.504844±0.08372.504844_± 0.0837 2.6150122.615012 0.9280±0.02590.9280_± 0.0259 AdaEvolve 2.632514±0.00312.632514_± 0.0031 2.6343052.634305 1.9653±0.00391.9653_± 0.0039 2.618077±0.00882.618077_± 0.0088 2.6280412.628041 0.9375±0.01620.9375_± 0.0162 EvoX 2.635420±0.00102.635420_± 0.0010 2.6359832.635983 1.9549±0.02281.9549_± 0.0228 2.599142±0.04342.599142_± 0.0434 2.6309722.630972 0.9497±0.03370.9497_± 0.0337 FrugalEvo 2.635989±0.00002.635989_ 0.0000 2.6359962.635996 1.9925±0.00281.9925_ 0.0028 2.635422±0.00082.635422_ 0.0008 2.6359902.635990 0.9939±0.00390.9939_ 0.0039 Signal Processing (↑ ) OpenEvolve 0.55003±0.02640.55003_± 0.0264 0.580450.58045 1.0802±0.03081.0802_± 0.0308 0.66438±0.07460.66438_± 0.0746 0.742450.74245 0.6297±0.06620.6297_± 0.0662 ShinkaEvolve 0.55604±0.03010.55604_± 0.0301 0.590120.59012 1.0854±0.02511.0854_± 0.0251 0.66246±0.04750.66246_± 0.0475 0.715550.71555 0.6305±0.03210.6305_± 0.0321 AdaEvolve 0.72031±0.02240.72031_± 0.0224 0.736770.73677 1.2520±0.02251.2520_± 0.0225 0.67621±0.00680.67621_± 0.0068 0.682810.68281 0.6315±0.00860.6315_± 0.0086 EvoX 0.64383±0.03770.64383_± 0.0377 0.665740.66574 1.1706±0.04281.1706_± 0.0428 0.67441±0.05350.67441_± 0.0535 0.709250.70925 0.6401±0.06090.6401_± 0.0609 FrugalEvo 0.77791±0.01450.77791_ 0.0145 0.789120.78912 1.4819±0.03081.4819_ 0.0308 0.78404±0.00340.78404_ 0.0034 0.786410.78641 0.7539±0.00680.7539_ 0.0068 Heilbronn Convex (13) (↑ ) AlphaEvolve: 0.030940.03094 OpenEvolve 0.02314±0.00240.02314_± 0.0024 0.025530.02553 1.3757±0.11461.3757_± 0.1146 0.02854±0.00210.02854_± 0.0021 0.030770.03077 0.8666±0.04980.8666_± 0.0498 ShinkaEvolve 0.02450±0.00280.02450_± 0.0028 0.027690.02769 1.4499±0.13251.4499_± 0.1325 0.02453±0.00280.02453_± 0.0028 0.027580.02758 0.6531±0.17480.6531_± 0.1748 AdaEvolve 0.02349±0.00110.02349_± 0.0011 0.024700.02470 1.4224±0.03481.4224_± 0.0348 0.02797±0.00210.02797_± 0.0021 0.030240.03024 0.8371±0.09500.8371_± 0.0950 EvoX 0.02248±0.00020.02248_± 0.0002 0.022620.02262 1.3840±0.05551.3840_± 0.0555 0.02896±0.00080.02896_± 0.0008 0.029850.02985 0.8279±0.02080.8279_± 0.0208 FrugalEvo 0.02751±0.00050.02751_ 0.0005 0.027810.02781 1.7405±0.03931.7405_ 0.0393 0.03079±0.00020.03079_ 0.0002 0.030940.03094 0.9614±0.00730.9614_ 0.0073 Heilbronn Triangle (↑ ) AlphaEvolve: 0.036530.03653 OpenEvolve 0.03417±0.00340.03417_± 0.0034 0.036530.03653 1.7517±0.18331.7517_± 0.1833 0.03139±0.00420.03139_± 0.0042 0.035980.03598 0.7256±0.13590.7256_± 0.1359 ShinkaEvolve 0.03030±0.00040.03030_± 0.0004 0.030610.03061 1.4825±0.08191.4825_± 0.0819 0.03051±0.00100.03051_± 0.0010 0.031680.03168 0.7561±0.02550.7561_± 0.0255 AdaEvolve 0.03077±0.00190.03077_± 0.0019 0.032730.03273 1.5951±0.04851.5951_± 0.0485 0.03337±0.00100.03337_± 0.0010 0.034560.03456 0.8192±0.05050.8192_± 0.0505 EvoX 0.03188±0.00410.03188_± 0.0041 0.036530.03653 1.6444±0.20311.6444_± 0.2031 0.03486±0.00160.03486_ 0.0016 0.036170.03617 0.8316±0.02600.8316_± 0.0260 FrugalEvo 0.03480±0.00080.03480_ 0.0008 0.035680.03568 1.8733±0.01321.8733_ 0.0132 0.03463±0.00170.03463_± 0.0017 0.036530.03653 0.8659±0.08930.8659_ 0.0893 Min-Max-3 (↓ ) AlphaEvolve: 4.1658504.165850 OpenEvolve 4.165783±0.00004.165783_ 0.0000 4.1657834.165783 1.9602±0.00251.9602_± 0.0025 4.168021±0.00394.168021_± 0.0039 4.1657834.165783 0.9740±0.01800.9740_± 0.0180 ShinkaEvolve 4.166404±0.00114.166404_± 0.0011 4.1657834.165783 1.9356±0.00961.9356_± 0.0096 4.167856±0.00194.167856_± 0.0019 4.1657834.165783 0.9737±0.00430.9737_± 0.0043 AdaEvolve 4.165783±0.00004.165783_ 0.0000 4.1657834.165783 1.9464±0.01171.9464_± 0.0117 4.165784±0.00004.165784_± 0.0000 4.1657834.165783 0.9820±0.00790.9820_± 0.0079 EvoX 4.165783±0.00004.165783_ 0.0000 4.1657834.165783 1.9419±0.00201.9419_± 0.0020 4.166583±0.00144.166583_± 0.0014 4.1657834.165783 0.9798±0.00510.9798_± 0.0051 FrugalEvo 4.165783±0.00004.165783_ 0.0000 4.1657834.165783 1.9769±0.01591.9769_ 0.0159 4.165783±0.00004.165783_ 0.0000 4.1657834.165783 0.9956±0.00040.9956_ 0.0004 We evaluate five tasks spanning geometric packing, extremal geometry, distance-ratio minimization, and multi-objective signal filtering. As shown in Table 1, FrugalEvo achieves the highest mean BA-AUC on all five tasks under both model configurations. It also achieves the best or comparable mean performance on all five tasks using GPT-5.6 Terra and Luna and four using GLM-5.3 and the Flash variant. Compared to the strong reported results in the closed-source AlphaEvolve, FrugalEvo matches or exceeds AlphaEvolve on four tasks, including Circle Packing, Heilbronn Convex (13), Heilbronn Triangle, and Min-Max-3. Figure 3: Visualization of FrugalEvo solutions on the circle packing task. Left: initial program; Middle: FrugalEvo solution generated by GPT-5.6 Terra and Luna; Right: FrugalEvo solution generated by GLM 5.3 and its Flash variant. Solution Analysis. Beyond aggregate scores, FrugalEvo discovers qualitatively distinct solutions across different tasks. On Circle Packing, it finds a packing with a total radius of 2.635996 by evolving five-row layouts with asymmetric displacements, refining them through constrained SLSQP optimization and fixed-center radius linear programming, and applying small radius increases within the evaluator’s tolerance. Figure 3 visualizes the solutions discovered by FrugalEvo and compares them with the initial program on Circle Packing. It shows that 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. These results are better than or comparable to those of CORAL (Qu et al., 2026) and SwarmResearch (Virk et al., 2026), which cost approximately $50 on average to achieve 2.635985 and 2.635996, respectively, demonstrating substantial cost savings. Moreover, on Signal Processing, FrugalEvo reaches 0.78912 by adaptively blending Savitzky–Golay, Butterworth, and spectral filters while suppressing minor reversals. On Heilbronn Convex (13), FrugalEvo matches AlphaEvolve through multistart hill climbing, linear programming refinement, and convex-hull area reduction. These results indicate the effectiveness of our approach: using a stronger model to explore strategies and a weaker model to iteratively refine solutions. Results on Systems Optimization Tasks. Table 2: Results on systems optimization problems. We report mean ± sample standard deviation and best scores over three runs. “(↑ )” means the higher the better, while “(↓ )” means the lower the better. Bold indicates the best result for each metric within each task and model configuration. Light green highlights the best performance within each task across both model configurations. GPT-5.6 Terra/Luna ($1) GLM-5.3/Flash ($0.5) Method Avg. Best BA-AUC@1 Avg. Best BA-AUC@0.5 EPLB (↑ ) OpenEvolve 0.1346±0.00970.1346_± 0.0097 0.14570.1457 0.1291±0.00060.1291_± 0.0006 0.1352±0.01010.1352_± 0.0101 0.14680.1468 0.0672±0.00460.0672_± 0.0046 ShinkaEvolve 0.1348±0.00970.1348_± 0.0097 0.14600.1460 0.1314±0.00440.1314_± 0.0044 0.1404±0.00940.1404_± 0.0094 0.14690.1469 0.0678±0.00270.0678_± 0.0027 AdaEvolve 0.1295±0.00040.1295_± 0.0004 0.12970.1297 0.1293±0.00030.1293_± 0.0003 0.1291±0.00120.1291_± 0.0012 0.12980.1298 0.0643±0.00050.0643_± 0.0005 EvoX 0.1355±0.00990.1355_± 0.0099 0.14700.1470 0.1320±0.00440.1320_± 0.0044 0.1294±0.00060.1294_± 0.0006 0.12980.1298 0.0641±0.00020.0641_± 0.0002 FrugalEvo 0.1435±0.00580.1435_ 0.0058 0.14710.1471 0.1408±0.00470.1408_ 0.0047 0.1471±0.00030.1471_ 0.0003 0.14730.1473 0.0724±0.00080.0724_ 0.0008 PRISM (↑ ) OpenEvolve 26.2307±0.040026.2307_± 0.0400 26.256026.2560 25.9249±0.099525.9249_± 0.0995 26.2560±0.000026.2560_ 0.0000 26.256026.2560 12.9947±0.044712.9947_± 0.0447 ShinkaEvolve 26.2136±0.027626.2136_± 0.0276 26.233226.2332 25.9399±0.110425.9399_± 0.1104 26.2560±0.000026.2560_ 0.0000 26.256026.2560 12.8018±0.113812.8018_± 0.1138 AdaEvolve 25.9493±0.170725.9493_± 0.1707 26.081826.0818 25.1931±0.497225.1931_± 0.4972 26.2539±0.003526.2539_± 0.0035 26.256026.2560 12.8213±0.177512.8213_± 0.1775 EvoX 25.8464±0.336825.8464_± 0.3368 26.220026.2200 24.9843±0.562324.9843_± 0.5623 26.2217±0.059426.2217_± 0.0594 26.256026.2560 12.7215±0.238412.7215_± 0.2384 FrugalEvo 26.2560±0.000026.2560_ 0.0000 26.256026.2560 26.0695±0.184426.0695_ 0.1844 26.2560±0.000026.2560_ 0.0000 26.256026.2560 13.1117±0.003013.1117_ 0.0030 LLM-SQL (↑ ) OpenEvolve 0.7165±0.00100.7165_± 0.0010 0.71750.7175 0.6263±0.02580.6263_± 0.0258 0.7262±0.00520.7262_± 0.0052 0.72960.7296 0.3349±0.00440.3349_± 0.0044 ShinkaEvolve 0.7204±0.00580.7204_± 0.0058 0.72710.7271 0.6818±0.00770.6818_± 0.0077 0.7236±0.00660.7236_± 0.0066 0.73070.7307 0.3397±0.01210.3397_± 0.0121 AdaEvolve 0.7190±0.00040.7190_± 0.0004 0.71930.7193 0.6502±0.00470.6502_± 0.0047 0.7259±0.00760.7259_± 0.0076 0.73210.7321 0.3374±0.00640.3374_± 0.0064 EvoX 0.7183±0.00090.7183_± 0.0009 0.71920.7192 0.6426±0.03190.6426_± 0.0319 0.7239±0.00840.7239_± 0.0084 0.73020.7302 0.3370±0.00800.3370_± 0.0080 FrugalEvo 0.7248±0.00850.7248_ 0.0085 0.73130.7313 0.7161±0.00570.7161_ 0.0057 0.7336±0.00090.7336_ 0.0009 0.73460.7346 0.3566±0.01210.3566_ 0.0121 Cloudcast (↓ ) OpenEvolve 618.103±0.000618.103_± 0.000 618.103618.103 0.1572±0.00210.1572_± 0.0021 637.112±17.314637.112_± 17.314 627.100627.100 0.0702±0.00630.0702_± 0.0063 ShinkaEvolve 618.098±0.004618.098_± 0.004 618.093618.093 0.1568±0.00270.1568_± 0.0027 725.286±19.810725.286_± 19.810 705.094705.094 0.0575±0.00690.0575_± 0.0069 AdaEvolve 618.098±0.000618.098_± 0.000 618.098618.098 0.1578±0.00080.1578_ 0.0008 785.177±216.772785.177_± 216.772 627.132627.132 0.0622±0.01260.0622_± 0.0126 EvoX 618.103±0.000618.103_± 0.000 618.103618.103 0.1572±0.00150.1572_± 0.0015 630.026±9.204630.026_± 9.204 622.617622.617 0.0638±0.00870.0638_± 0.0087 FrugalEvo 618.093±0.016618.093_ 0.016 618.075618.075 0.1565±0.00160.1565_± 0.0016 622.601±4.506622.601_ 4.506 618.098618.098 0.0776±0.00130.0776_ 0.0013 Transaction Scheduling (↑ ) OpenEvolve 4091.92±169.164091.92_± 169.16 4237.294237.29 3893.72±150.823893.72_± 150.82 4052.41±193.964052.41_± 193.96 4291.854291.85 1971.43±130.541971.43_± 130.54 ShinkaEvolve 4023.16±203.944023.16_± 203.94 4149.384149.38 3734.62±111.633734.62_± 111.63 3952.25±240.143952.25_± 240.14 4115.234115.23 1840.84±71.761840.84_± 71.76 AdaEvolve 3858.51±119.853858.51_± 119.85 3984.063984.06 3720.02±38.423720.02_± 38.42 4047.19±237.884047.19_± 237.88 4255.324255.32 1955.27±93.631955.27_± 93.63 EvoX 3913.30±271.063913.30_± 271.06 4219.414219.41 3674.87±162.273674.87_± 162.27 3975.20±265.473975.20_± 265.47 4184.104184.10 1800.25±116.931800.25_± 116.93 FrugalEvo 4252.11±110.394252.11_ 110.39 4405.294405.29 4133.73±124.124133.73_ 124.12 4288.01±98.334288.01_ 98.33 4366.814366.81 2107.07±42.862107.07_ 42.86 Table 2 reports results on five real-world systems optimization tasks from the ADRS benchmark (Cheng et al., 2025). It shows that FrugalEvo achieves the best or comparable mean and best performance on all five tasks under both model configurations, with the highest mean BA-AUC on four tasks. Qualitatively, FrugalEvo discovers effective approaches to systems optimization. On EPLB, it achieves a score of 0.1473 with an expert load-balancing algorithm that combines greedy expert replication, load-aware block assignment, and pairwise swap refinement. On Transaction Scheduling, it achieves a combined score of 4405.29 with a scheduler that combines multistart regret-guided insertion, exhaustive local window reordering, and transaction relocation to reduce makespan. Results on Algorithmic Optimization Tasks. We evaluate FrugalEvo on 10 algorithmic optimization tasks from ALE-Bench-Lite (Imajuku et al., 2026), derived from AtCoder Heuristic Contests, and report the results in Figure 4. Following prior work (Lange et al., 2026), all methods start from solutions produced by ALE-Agent (Imajuku et al., 2026) and are evaluated using private scores. Figure 4: Average private performance across 10 ALE-Bench-Lite tasks. FrugalEvo uses GPT-5.6 Terra and Luna and other baselines use GPT-5.6 Terra. The budget is $1. As shown in Figure 4, FrugalEvo achieves the highest score of 1924.9, outperforming strong baselines OpenEvolve (1887.5) and AdaEvolve (1881.9). It discovers diverse algorithmic optimization solutions. On AHC016 (graph classification), FrugalEvo constructs graphs from disjoint cliques and their complements, identifying noisy graphs by comparing the sorted numbers of neighbors per vertex with noise-adjusted expectations. On AHC027 (cleaning route), FrugalEvo uses dirt accumulation rates, time since the last visit, and travel distances to plan routes that revisit areas requiring more frequent cleaning. Performance-For-Cost Curves. Figure 5: Best-so-far score curves on signal processing, heilbronn convex, and transaction scheduling. FrugalEvo uses GPT-5.6 Terra and Luna, while the baselines use GPT-5.6 Terra. The top row shows mean trajectories across three runs, and the bottom row shows the trajectory of the best-performing run for each method. BA-AUC values are printed along with method names. To compare cost efficiency, we plot performance-for-cost curves of different methods on Signal Processing, Heilbronn Convex (13), and Transaction Scheduling. As shown in Figure 5, FrugalEvo establishes a clear performance advantage within the first $0.2 on all three tasks and maintains it throughout the remaining search. Its higher mean BA-AUC values on all three tasks further quantify this advantage over the cost interval. These results indicate that FrugalEvo achieves higher search efficiency within a given cost budget. 3.3 Ablations In this section, we present ablation studies on key components of FrugalEvo (model collaboration, cold start, and sequential feedback in code refinement) and the results are shown in Table 3. Impact of Model Collaboration. Our framework assigns strategy exploration and solution generation to different models to improve search efficiency. As shown in Table 3, using either the high-cost or low-cost model for both stages yields lower mean and best performance than FrugalEvo on both tasks under the same cost budget. In particular, using only the high-cost model leads to a larger drop in mean performance, possibly because implementation calls consume a substantial portion of the budget, leaving less for further exploration. Moreover, using only the low-cost model reduces the best final score, particularly on Signal Processing. This may be because the low-cost model is less effective at identifying promising strategies. These results suggest that combining strategy exploration by a strong, expensive model with low-cost code implementation improves search efficiency under a fixed cost budget. Table 3: Ablation results with GPT-5.6 Terra and Luna. Method Performance Avg. Best Circle Packing (↑ ) FrugalEvo 2.635989±0.00002.635989_ 0.0000 2.6359962.635996 - Terra + Terra 2.632278±0.00632.632278_± 0.0063 2.6359832.635983 - Luna + Luna 2.634565±0.00252.634565_± 0.0025 2.6359832.635983 w/o cold start 2.632417±0.00312.632417_± 0.0031 2.6359832.635983 w/o seq feedback 2.633659±0.00212.633659_± 0.0021 2.6359962.635996 Signal Processing (↑ ) FrugalEvo 0.77791±0.01450.77791_ 0.0145 0.789120.78912 - Terra + Terra 0.68534±0.03520.68534_± 0.0352 0.707060.70706 - Luna + Luna 0.74865±0.00970.74865_± 0.0097 0.759730.75973 w/o cold start 0.75576±0.02400.75576_± 0.0240 0.779730.77973 w/o seq feedback 0.76072±0.02090.76072_± 0.0209 0.774380.77438 Impact of Cold Start and Sequential Feedback. We introduce a cold-start phase to provide a stronger initial incumbent for strategy exploration. As shown in Table 3, removing this phase and using the initial program directly as the parent reduces both mean and best performance on both tasks. This suggests that refining the initial program with a low-cost model is a cost-effective way to support high-quality strategy exploration. Moreover, we also incorporate sequential feedback into code refinement in the solution generator. Removing this feedback lowers mean performance and increases the standard deviation across runs, suggesting that feedback from earlier attempts helps the low-cost model refine programs more effectively and improves search stability. 4 Related Work LLM-Guided Evolutionary Methods. Recent work combining LLMs with evolutionary search has produced notable results (Agrawal et al., 2026; Novikov et al., 2025) for mathematical (Feng et al., 2026c; Feng et al., 2026d; Feng et al., 2026b), algorithmic (Mang et al., 2025), and systems (Cheng et al., 2025) optimization. For example, FunSearch (Romera-Paredes et al., 2024) combines LLM generation with automated evaluation to evolve mathematical solutions. AlphaEvolve (Novikov et al., 2025) extends this approach from evolving individual functions to larger programs. Subsequently, OpenEvolve (Sharma, 2025) and CodeEvolve (Assumpção et al., 2025) provide open-source frameworks, and ShinkaEvolve (Lange et al., 2026) introduces a sample-efficient evolution method. ThetaEvolve (Wang et al., 2025) and T-Discover (Yuksekgonul et al., 2026) apply Reinforcement Learning (RL) to improve the LLM generator at test time. More recently, AdaEvolve (Cemri et al., 2026) and EvoX (Liu et al., 2026b) adapt the search process, while SwarmResearch (Virk et al., 2026) and CORAL (Qu et al., 2026) coordinate multiple coding agents to improve search performance. These methods focus on performance gains over a fixed number of iterations, while our work emphasizes gain per unit cost. Cost-Efficient LLM Inference. Prior work explores LLM cascades (Chen et al., 2023), routing (Ong et al., 2025; Feng et al., 2026a), reflection (Agrawal et al., 2026; Zhang et al., 2026a), and caching (Zhang et al., 2026b) to improve cost efficiency. For instance, FrugalGPT (Chen et al., 2023) learns model cascades to balance cost and accuracy, while RouteLLM (Ong et al., 2025) learns to route queries between strong and weak models using preference data. For scientific discovery, SimpleTES (Ye et al., 2026) post-trains an open-source model for long-horizon AI discovery by assigning each attempt the final outcome of the trajectory it helped produce. Meanwhile, Squeeze Evolve (Maheswaran et al., 2026) coordinates multiple models for verifier-free evolution using models’ own confidence signals, such as token log-probabilities. Our approach allocates model capability based on the characteristics of computational optimization tasks, without additional model training or access to token-level probabilities. 5 Conclusion We introduce FrugalEvo, a cost-aware LLM-guided evolutionary framework for computational optimization, that combines strategy exploration by a strong, high-cost model with code implementation and refinement by a low-cost model, and design a cache-efficient evolution process. To assess solution quality throughout a fixed cost budget, we propose Budget-Aware Area Under the Curve (BA-AUC). 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. Limitations and Future Work. FrugalEvo splits candidate program generation in computational optimization tasks into two steps and assigns them to two different models. This design is tailored to settings where both solution generation and evaluation take place entirely within a code environment, so that candidates can be executed and scored automatically. As a result, our method does not readily extend to scientific domains that require interaction with the physical world, such as biology, where evaluating a solution may involve wet-lab experiments that cannot be automated through code execution. Moreover, guiding the model to explore effective strategies relies on carefully crafted instructions. Our current instructions are manually designed for computational optimization tasks rather than automatically derived from each task. Finally, future work includes extending this approach to other domains that require interaction with the physical world, and develop methods that automatically generate strategy exploration instructions. AI Use Statement In preparing this submission, we used LLMs as general-purpose writing assistants and coding agents to implement the algorithm and run experiments. The human authors were responsible for the entire research process, including initial ideation, experimental design, and data analysis. For the experiments, the authors first developed an experimental plan and prepared the codebase and datasets, then instructed coding agents to implement the proposed method and execute the experiments. During writing, the authors drafted each section, including all core ideas and technical details, and used LLMs to improve clarity, coherence, and grammar. All scientific claims and findings presented in this paper originate from the authors, who take full responsibility for the final content. Ethics Statement Our work adheres to the ICLR Code of Ethics. The primary ethical considerations for this research involve the use of solutions generated by our algorithm across 20 optimization tasks. Although assessed by task evaluators, these solutions have not been validated by human experts and are intended for research reference only. Reproducibility Statement We are committed to ensuring the reproducibility of our research. To this end, we will publicly release all code, data, and supplementary materials upon publication. References Agrawal et al. (2026) L. A. Agrawal, S. Tan, D. Soylu, N. Ziems, R. Khare, K. Opsahl-Ong, A. Singhvi, H. Shandilya, M. J. Ryan, M. Jiang, et al. Gepa: reflective prompt evolution can outperform reinforcement learning. In International Conference on Learning Representations, Vol. 2026, p. 8479–8565. Cited by: §4, §4. Assumpção et al. (2025) H. Assumpção, D. Ferreira, L. Campos, and F. Murai CodeEvolve: an open source evolutionary coding agent for algorithmic discovery and optimization. arXiv preprint arXiv:2510.14150. Cited by: §4. Brown et al. (2024) B. Brown, J. Juravsky, R. Ehrlich, R. Clark, Q. V. Le, C. Ré, and A. Mirhoseini Large language monkeys: scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787. Cited by: §1. Cemri et al. (2026) M. Cemri, S. Agrawal, A. Gupta, S. Liu, A. Cheng, Q. Mang, A. Naren, L. E. Erdogan, K. Sen, M. Zaharia, et al. Adaevolve: adaptive llm driven zeroth-order optimization. arXiv preprint arXiv:2602.20133. Cited by: §1, §1, §3.1, §4. Chen et al. (2023) L. Chen, M. Zaharia, and J. Zou Frugalgpt: how to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05176. Cited by: §4. Cheng et al. (2025) A. Cheng, S. Liu, M. Pan, Z. Li, B. Wang, A. Krentsel, T. Xia, M. Cemri, J. Park, S. Yang, et al. Barbarians at the gate: how ai is upending systems research. arXiv preprint arXiv:2510.06189. Cited by: Table 5, §1, §3.1, §3.2, §4. Feng et al. (2026a) T. Feng, F. Yu, H. Zhang, Z. Dai, L. Yuan, Z. Lei, W. Zhang, K. Zhu, H. Yue, K. Xuan, et al. LLMRouter: unified infrastructure for developing, evaluating, and deploying llm routers. arXiv preprint arXiv:2608.06867. Cited by: §4. Feng et al. (2026b) T. Feng, J. Jung, S. Kim, C. Pagano, S. Gukov, C. Tsai, D. Woodruff, A. Javanmard, A. Mokhtari, D. Hwang, et al. Aletheia tackles firstproof autonomously. arXiv preprint arXiv:2602.21201. Cited by: §1, §4. Feng et al. (2026c) T. Feng, T. Trinh, G. Bingham, J. Kang, S. Zhang, S. Kim, K. Barreto, C. Schildkraut, J. Jung, J. Seo, et al. Semi-autonomous mathematics discovery with gemini: a case study on the erdős problems. arXiv preprint arXiv:2601.22401. Cited by: §4. Feng et al. (2026d) T. Feng, T. H. Trinh, G. Bingham, D. Hwang, Y. Chervonyi, J. Jung, J. Lee, C. Pagano, S. Kim, F. Pasqualotto, et al. Towards autonomous mathematics research. arXiv preprint arXiv:2602.10177. Cited by: §4. Glazer et al. (2024) E. Glazer, E. Erdil, T. Besiroglu, D. Chicharro, E. Chen, A. Gunning, C. F. Olsson, J. Denain, A. Ho, E. d. O. Santos, et al. Frontiermath: a benchmark for evaluating advanced mathematical reasoning in ai. arXiv preprint arXiv:2411.04872. Cited by: §1. Imajuku et al. (2026) Y. Imajuku, K. Horie, Y. Iwata, K. Aoki, N. Takahashi, and T. Akiba Ale-bench: a benchmark for long-horizon objective-driven algorithm engineering. Advances in Neural Information Processing Systems 38. Cited by: Table 6, §1, §3.1, §3.2. Lange et al. (2026) R. Lange, Y. Imajuku, and E. Cetin Shinkaevolve: towards open-ended and sample-efficient program evolution. In International Conference on Learning Representations, Vol. 2026, p. 74026–74078. Cited by: §1, §1, §3.1, §3.2, §4. Liu et al. (2026a) A. Liu, A. Ho, A. M. Droste, D. Martin, E. Wong, E. Zhou, I. Zhou, J. Park, J. Jiao, K. Skelly, et al. LifeSciBench: evaluating language models on realistic, expert-level tasks in the life sciences. bioRxiv, p. 2026–08. Cited by: §1. Liu et al. (2026b) S. Liu, S. Agarwal, M. Maheswaran, M. Cemri, Z. Li, Q. Mang, A. Naren, E. Boneh, A. Cheng, M. Z. Pan, et al. Evox: meta-evolution for automated discovery. arXiv preprint arXiv:2602.23413. Cited by: §1, §1, §3.1, §4. Maheswaran et al. (2026) M. Maheswaran, L. Lakhani, Z. Zhou, S. Yang, J. Wang, C. Hooper, Y. Hu, R. Tiwari, J. Wang, H. Singh, et al. Squeeze evolve: unified multi-model orchestration for verifier-free evolution. arXiv preprint arXiv:2604.07725. Cited by: §4. Mang et al. (2025) Q. Mang, W. Chai, Z. Li, H. Mao, S. Zhou, A. Du, H. Li, S. Liu, E. Chen, Y. Wang, et al. Frontiercs: evolving challenges for evolving intelligence. arXiv preprint arXiv:2512.15699. Cited by: §4. Mouret and Clune (2015) J. Mouret and J. Clune Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909. Cited by: Figure 2, §2.2. Muennighoff et al. (2025) N. Muennighoff, Z. Yang, W. Shi, X. L. Li, L. Fei-Fei, H. Hajishirzi, L. Zettlemoyer, P. Liang, E. Candès, and T. B. Hashimoto S1: simple test-time scaling. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, p. 20286–20332. Cited by: §1. Novikov et al. (2025) A. Novikov, N. Vũ, M. Eisenberger, E. Dupont, P. Huang, A. Z. Wagner, S. Shirobokov, B. Kozlovskii, F. J. Ruiz, A. Mehrabian, et al. Alphaevolve: a coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506.13131. Cited by: §1, §1, §2.1, §3.1, §4. Ong et al. (2025) I. Ong, A. Almahairi, V. Wu, W. Chiang, T. Wu, J. E. Gonzalez, M. Kadous, and I. Stoica Routellm: learning to route llms from preference data. In International Conference on Learning Representations, Vol. 2025, p. 34433–34448. Cited by: §4. OpenAI (2026) OpenAI GPT-5.6 system card. Technical report OpenAI. External Links: Link Cited by: §1, §3.1. Qu et al. (2026) A. Qu, H. Zheng, Z. Zhou, Y. Yan, Y. Tang, S. Y. Ong, F. Hong, K. Zhou, C. Jiang, M. Kong, et al. Coral: towards autonomous multi-agent evolution for open-ended discovery. arXiv preprint arXiv:2604.01658. Cited by: §3.2, §4. Romera-Paredes et al. (2024) B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. Ruiz, J. S. Ellenberg, P. Wang, O. Fawzi, et al. Mathematical discoveries from program search with large language models. Nature 625 (7995), p. 468–475. Cited by: §2.1, §4. Sharma (2025) A. Sharma OpenEvolve: an open-source evolutionary coding agent. GitHub. External Links: Link Cited by: §1, §1, §3.1, §3.1, §4. Snell et al. (2024) C. Snell, J. Lee, K. Xu, and A. Kumar Scaling llm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314. Cited by: §1. Tanese (1989) R. Tanese Distributed genetic algorithms for function optimization. University of Michigan. Cited by: Figure 2, §2.2. Virk et al. (2026) Y. Virk, Z. Edds, C. S. Xia, and L. Zhang SwarmResearch: orchestrating coding agents for open-ended discovery. arXiv preprint arXiv:2607.02807. Cited by: §3.2, §4. Wang et al. (2026) M. Wang, R. Lin, K. Hu, J. Jiao, N. Chowdhury, E. Chang, and T. Patwardhan FrontierScience: evaluating ai’s ability to perform expert-level scientific tasks. arXiv preprint arXiv:2601.21165. Cited by: §1. Wang et al. (2025) Y. Wang, S. Su, Z. Zeng, E. Xu, L. Ren, X. Yang, Z. Huang, X. He, L. Ma, B. Peng, et al. Thetaevolve: test-time learning on open problems. arXiv preprint arXiv:2511.23473. Cited by: §4. Ye et al. (2026) H. Ye, H. Lin, J. Tang, Y. Luo, C. Yang, C. Su, R. Thapa, R. Yang, R. Liu, Z. Li, et al. Evaluation-driven scaling for scientific discovery. arXiv preprint arXiv:2604.19341. Cited by: §4. Yuksekgonul et al. (2026) M. Yuksekgonul, D. Koceja, X. Li, F. Bianchi, J. McCaleb, X. Wang, J. Kautz, Y. Choi, J. Zou, C. Guestrin, et al. Learning to discover at test time. arXiv preprint arXiv:2601.16175. Cited by: §4. Z.ai (2026a) Z.ai GLM-5.3-Flash: frontier intelligence, flash cost. Technical report Z.ai. External Links: Link Cited by: §1, §3.1. Z.ai (2026b) Z.ai GLM-5.3: frontier coding with emergent cyber capabilities. Technical report Z.ai. External Links: Link Cited by: §1, §3.1. Zhang et al. (2026a) Q. Zhang, C. Hu, S. Upasani, B. Ma, F. Hong, V. Kamanuru, J. Rainton, C. Wu, M. Ji, H. Li, et al. Agentic context engineering: evolving contexts for self-improving language models. In International Conference on Learning Representations, Vol. 2026, p. 86069–86100. Cited by: §4. Zhang et al. (2026b) Q. Zhang, M. Wornow, and K. Olukotun Agentic plan caching: test-time memory for fast and cost-efficient llm agents. Advances in Neural Information Processing Systems 38, p. 103270–103296. Cited by: §4. Appendix Appendix A Algorithm Description Algorithm 1 describes our algorithm, which mainly contains four phases: (1) cold start, (2) strategy exploration, (3) initial code implementation and strategy ranking, and (4) iterative code refinement. Algorithm 1 FrugalEvo: Cost-aware LLM-guided program evolution 1: Budget B; task d; evaluator E; packages P; evaluated database D 2: High-cost LLM hG_h; low-cost LLM lG_l; opening cap N0N_0; strategy count K; round cap M 3: Consecutive-invalid limit F; tolerance ϵε; flags I0,IrefI_0,I_ref 4: ℋ←∅H← ; x⋆←argmaxx∈valids(x)x ← _x _valids(x) 5: Phase I: Cold start 6: (,x⋆)←ColdStartAndCheapClimb(l,,x⋆,N0,M,F,ϵ,I0,B)(D,x )← ColdStartAndCheapClimb(G_l,D,x ,N_0,M,F,ε,I_0,B) ⊳ Cheap search until stalled 7: A←AnalyzeOnce(h,d,E,,B)A← AnalyzeOnce(G_h,d,E,P,B) ⊳ Cache evaluator and task analysis 8: while BudgetAvailable(B) do ⊳ New strategy portfolio 9: Phase I: Strategy exploration 10: x¯←x⋆ x← x ; ←Context(,x¯)C← Context(D, x) ⊳ Build search context 11: (Sii=1k,xref)←Explore(h,x¯,,ℋ,A,K,Iref,B)(\S_i\_i=1^k,x_ref)← Explore(G_h, x,C,H,A,K,I_ref,B) ⊳ Propose K strategies 12: (,x⋆,x¯,,ℋ)←ProcessReference(xref,,x⋆,x¯,,ℋ,ϵ)(D,x , x,C,H)← ProcessReference(x_ref,D,x , x,C,H,ε) ⊳ Evaluate reference; use as shared parent if improved 13: Phase I: Initial code implementation and strategy ranking 14: (,,,x⋆)←ParallelTrials(l,Sii=1k,x¯,,,x⋆,B)(T,q,D,x )← ParallelTrials(G_l,\S_i\_i=1^k, x,C,D,x ,B) ⊳ One trial per strategy; shared parent 15: ℋ←RecordTrials(ℋ,)H← RecordTrials(H,T); π←StableArgsorti(−qi)π _i(-q_i) ⊳ Rank strategies by trial scores 16: Phase IV: Iterative code refinement 17: for j=1,…,kj=1,…,k do 18: while BudgetAvailable(B) do 19: b←s(x⋆)b← s(x ) ⊳ Cache the incumbent score 20: (ℛ,,x⋆)←SequentialImprove(l,Sπ(j),,x⋆,M,F,ϵ,B)(R,D,x )← SequentialImprove(G_l,S_π(j),D,x ,M,F,ε,B) ⊳ Up to M attempts; end round on improvement 21: Δ←s(x⋆)−b ← s(x )-b; ℋ←Record(ℋ,Sπ(j),ℛ,Δ)H← Record(H,S_π(j),R, ) ⊳ Record global improvement 22: if Δ≤ϵ ≤ε then 23: break ⊳ Move to the next strategy 24: end if 25: end while 26: end for 27: end while 28: return x⋆x Appendix B Benchmark Details We evaluate FrugalEvo on 20 optimization problems spanning mathematical optimization (5 problems), systems optimization (5 problems), and algorithmic challenges (10 problems). B.1 Mathematical Optimization Table 4: Mathematical optimization tasks. Summary of optimization tasks used to evaluate FrugalEvo, including geometric optimization and signal processing problems. Problem Objective Description Circle Packing (Square) max∑i=126ri _i=1^26r_i 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 (n=13n=13) maxAmin/Ahull A_ /A_hull 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 (n=11n=11) maxAmin/AT A_ /A_T 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 AT=3/4A_T= 3/4. Min-Max Distance Ratio (3D) max(dmin/dmax)2 (d_ /d_ )^2 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. B.2 Systems Optimization Table 5: Systems optimization tasks. Benchmarks drawn from ADRS-Bench (Cheng et al., 2025), capturing realistic optimization problems from production systems. 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. B.3 Algorithmic Challenges Table 6: Algorithmic optimization tasks. Summary of the 10 algorithmic optimization problems from ALE-Bench-Lite (Imajuku et al., 2026), drawn from AtCoder Heuristic Contests, used to evaluate FrugalEvo. 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. ahc026 (Box Stacking) 1 Rearrange box stacks to remove boxes in increasing label order with minimum relocation energy. ahc027 (Cleaning Route) 1 Find a closed route covering every grid cell to minimize average dirt under repeated traversal. ahc039 (Fishing Net) 1 Enclose mackerels while avoiding sardines using a simple rectilinear polygon under perimeter and vertex limits. ahc046 (Skating with Blocks) 1 Visit targets in order with minimum actions using steps, slides, and block placement or removal. Appendix C Model Pricing We present the token prices for the two model configurations used in our experiments: GPT-5.6-Terra with GPT-5.6-Luna, and GLM-5.3 with GLM-5.3-Flash in Table 7. Table 7: Model pricing. Prices were retrieved from the official OpenAI website and OpenRouter on September 4, 2026, for the GPT and GLM models, respectively. All prices are in USD per million tokens. 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 — Appendix D Prompts Below are the prompts used for strategy exploration and code implementation and refinement. Strategy Exploration Prompt You are the strategy designer for a program-evolution system. Propose exactly K distinct strategies to improve the current program’s evaluated score. Inputs: - Task specification and validity constraints - Current program and evaluated metrics - Evaluator-aware guidance, when available - Previous strategies, implementation results, and failures Each strategy must describe: 1. Mechanism family: a short identifier for the approach. 2. Replacement scope: the function, phase, or block to replace. 3. Compute budget: explicit limits on additional computation. 4. Gain mechanism: the bottleneck addressed or new degree of freedom introduced. Propose different mechanisms, not variations in random seeds, tolerances, or iteration counts. For K >= 3, include local refinement, subsystem replacement, and structural exploration. Use previous results to avoid repeating exhausted approaches. Make every plan self-contained and immediately implementable. Preserve public interfaces and hard validity constraints. Do not rely on unavailable tools, fabricated data, or an unspecified future optimization step. Explain why the proposed change can improve the actual scoring objective. Compare quantities on the same scale. End each plan with a concise gain check: either a justified score estimate or a testable hypothesis tied to a specific new mechanism. A fallback or an accept-only-if-better rule is not itself evidence of improvement. Return each strategy in this format: <STRATEGY_TITLE>[mechanism-family] short title</STRATEGY_TITLE> <STRATEGY> Mechanism family: ... Replacement scope: ... Compute budget: ... Gain mechanism: ... Implementation plan and expected-gain check. </STRATEGY> When requested, also return one complete, executable portfolio reference program in <REFERENCE_IMPLEMENTATION> tags. It is an independent candidate, not assigned to any strategy. Keep program code outside the strategy blocks. Code Implementation and Refinement Prompt You are the implementation model in a program-evolution system. Implement the supplied strategy to improve the current program. Inputs: - Task specification and validity constraints - Current parent program and evaluated metrics - Strategy to implement - Previous implementation feedback, when available Implement the strategy faithfully. Replace the specified mechanism and remove superseded code when safe. Do not substitute an unrelated idea, make only a cosmetic change, or append another complete optimization pipeline. Ensure that the new mechanism executes on the normal return path. Preserve public interfaces, permitted edit boundaries, and hard validity constraints. Keep added computation within the strategy’s budget. A valid fallback may be retained, but returning only the fallback does not implement the strategy. If the parent already implements the proposed mechanism, refine that mechanism rather than adding a duplicate. Check dimensions, data types, mutability, API calls, and consistency between function definitions and call sites. For a pilot implementation, build the smallest executable version that exercises the strategy’s distinctive mechanism. For subsequent refinement attempts, use evaluated metrics and errors to repair failures or revise unsuccessful choices. Do not repeat failed patches or merely change random seeds. For timeouts, reduce work or replace the expensive stage while preserving the strategy’s gain mechanism. Return code in the required output format. For SEARCH/REPLACE edits, copy each SEARCH block exactly from the current parent and ensure that it matches uniquely. Previous attempts do not replace the parent as the edit target. When repairing a supplied failing program, return a complete, coherently corrected program rather than a diff against the failed attempt.