SimpleEvol: An Agent-Loop Framework for LLM-Driven Automated Heuristic Design with Minimal Human Priors

• The paper asks whether increasing AHD framework complexity improves the conversion of stronger LLM capabilities into better optimization outcomes.Source: §1 · p. 2
• Across ten backbone LLMs and three combinatorial optimization problems, frameworks with fewer human priors consistently achieve higher ICE.Source: §1 · p. 2
• The authors introduce AHI to quantify framework handcraftedness and ICE to measure how effectively model intelligence gains translate into heuristic quality.Source: §1 · p. 2
• SimpleEvol achieves the highest ICE on primary benchmarks, remains robust across models and evaluation choices, and performs best under most backbone models on each task.Source: §1 · p. 2
• SimpleEvol is a deliberately minimal agent-loop framework that maximizes model autonomy while minimizing human priors.Source: §1 · p. 2
• SimpleEvol’s intelligence-conversion advantage is not obtained through disproportionate computational expenditure.Source: §1 · p. 2
• The results suggest that lightweight, model-centric agent-loop frameworks may better exploit future advances in foundation models as the AHD bottleneck shifts toward model intelligence.Source: §1 · p. 2

2.1 AHD and LLM-based AHD

• AHD seeks a heuristic that maximizes expected performance over a task-specific training distribution, with candidate heuristics operating on problem instances to construct or improve feasible solutions.Source: §2.1 · p. 3
• In LLM-based AHD, an LLM generates and refines candidate heuristics, and evaluation feedback guides subsequent generations.Source: §2.1 · p. 3
• The search is represented as structured heuristic states containing code, quality, design descriptions, runtime, errors, and evaluation order, enabling summaries conditioned on more than fitness alone.Source: §2.1 · p. 3

2.2 Scaling Behavior and the Bitter Lesson

• The bitter lesson motivates reducing handcrafted structure because general methods using available computation tend to outperform handcrafted systems over the long run.Source: §2.2 · p. 3

3.1 AHD Handcraftedness Index (AHI)

• AHI sums functional complexity, LLM-operation diversity, and the log-scaled average number of LLM calls to describe externally prescribed framework scaffolding.It counts orchestration components that select or route candidates, distinct LLM invocation types, and interaction scale—not implementation effort or components that only format or retain context.Source: §3.1 · p. 4

3.2 Model Intelligence Metric

• I(m) estimates framework-agnostic backbone capability using four benchmarks normalized to the weakest model and aggregated by geometric mean.The benchmarks are MMLU-Pro, IFBench, AIME2025, and LiveCodeBench; the geometric mean preserves relative differences across benchmarks without letting one dominate.Source: §3.2 · pp. 4–5

3.3 AHD Performance Metric

• P(A, m) measures a framework’s best-found heuristic quality under a fixed model, using a reciprocal test-gap transformation so higher scores indicate better optimization performance.The authors average test performance over independent runs and evaluated problem sizes; the reciprocal makes improvements in the low-gap regime more salient.Source: §3.3 · p. 5

3.4 Intelligence Conversion Efficiency (ICE)

• ICE(A) is the regression slope of framework performance against model intelligence, summarizing fitted performance change per unit increase in intelligence across evaluated models.The authors use it as a global first-order trend even though the true relationship may not be strictly linear, and report sensitivity checks for benchmark choice, evaluation budget, and individual models.Source: §3.4 · pp. 5–6

4 The Simple Evolution (SimpleEvol) Framework

• SimpleEvol maintains one evolving heuristic trajectory, generating an offspring from the task and prior attempts, then evaluating it and feeding meta-information back into the next iteration.Evaluation feedback can include objective value, execution time, and error messages.Source: §4 · p. 6
• Every k iterations, SimpleEvol compresses prior results and the best-so-far candidate into working notes, retaining useful search history while removing older records.The notes capture successful or ineffective structural patterns and common implementation errors, without adding a separate planner or reflection module.Source: §4 · p. 6
• The design removes explicit population management and multi-operator coordination while relying on open-ended planning, trajectory-based reflection, and self-directed generation.Recording heuristic states gives the LLM recent experiments and compressed earlier trajectories to identify recurring failures and promising directions.Source: §4 · p. 7
• The framework tests whether a simpler design with fewer structural constraints can convert stronger LLM reasoning, coding, and self-improvement capabilities into optimization performance more effectively.The authors present this as a bitter-lesson-style hypothesis and evaluate whether SimpleEvol remains competitive.Source: §4 · p. 7

5 Experiments

• The study compares FunSearch, EoH, ReEvo, and SimpleEvol across TSP, CVRP, and FSSP, spanning constructive search, ACO, and GLS settings in routing and scheduling.Across all experiments, the maximum number of generated heuristics is fixed at 820.Source: §5 · p. 7

5.1 Intelligence conversion across AHD frameworks

• Figure 2 shows a positive overall relationship between model intelligence and AHD performance on TSP and CVRP, with SimpleEvol showing the steepest, most consistent fitted trend.Individual-model relationships are not monotone.Source: Figure 2 · p. 8, §5.1 · p. 8
• SimpleEvol has the highest ICE and lowest AHI on both TSP Constructive and CVRP-ACO, while ReEvo has the lowest ICE and highest AHI.The comparison uses regression-based ICE alongside AHI.Source: Table 2 · p. 8, §5.1 · p. 8
• Under GPT-5-mini, SimpleEvol achieves the lowest gaps across all reported settings, and its within-model advantage grows with model intelligence, particularly on CVRP-ACO.Figure 3 ranks frameworks by average gap and encodes relative gap improvement over the methods’ within-model mean.Source: Figure 3 · p. 8, §5.1 · p. 9, Table 3 · p. 9

5.2 Extension to FSSP-GLS and other benchmarks

• On FSSP, SimpleEvol has the highest in-distribution ICE and best Taillard performance under 8 of 10 backbones; on TSPLIB, it has the best average gap and most top-1 results.These evaluations extend beyond the primary TSP and CVRP benchmarks.Source: §5.2 · p. 9

5.3 Cost Efficiency Analysis

• On CVRP-ACO, SimpleEvol’s Qwen3-235B-Instruct and GPT-5-mini instances lie on the cost–performance Pareto frontier, while its overall monetary cost remains comparable to other frameworks.DeepSeek-v3 and Qwen3-235B-Thinking instances lie near the frontier.Source: Figure 4 · p. 9, §5.3 · p. 9

5.4 Ablation Study

• Removing best-of-so-far retention causes the largest ablation performance drop; removing summarization or meta-information, or summarizing less often, also degrades results.The ablation uses GPT-4.1-nano; Table 4 reports gaps on TSP and CVRP at size 50.Source: Table 4 · p. 9, §5.4 · p. 10

6 Conclusion

• Across ten backbone LLMs and three combinatorial optimization problems, AHI and ICE show a consistent inverse relationship, and SimpleEvol has the highest ICE on all primary benchmarks while remaining cost-competitive.The conclusion favors a lighter, more model-centric alternative and suggests greater LLM autonomy over planning, reflection, and memory.Source: §6 · p. 10

A Related Work

• Prior LLM-based AHD work increasingly engineers outer-loop components, making performance differences reflect both the model and its orchestration; this paper instead analyzes framework complexity and intelligence conversion.The related-work discussion also contrasts Neural Combinatorial Optimization, which places more problem-solving inside trained models than in symbolic test-time code-search loops.Source: A Related Work · p. 15

B Prompts Used in SimpleEvol

• The system prompt asks the LLM to plan the heuristic-discovery process rather than follow prescribed parent-heuristic operations, using a record–reflect–compare–plan loop.The prompt supplies the experiment limit and general requirements.Source: B Prompts Used in SimpleEvol · p. 16
• Trajectory summaries capture strategy performance and recurring failures as descriptive, non-prescriptive experience, then enter later reasoning as compressed memory.The user generator prompt is updated with progress and elite-heuristic meta-information when an elite heuristic and first summary are available.Source: B Prompts Used in SimpleEvol · p. 16

C Experimental Setups

• Experiments fix temperature at 1.0, the maximum evaluated heuristics at 820, and context compression frequency at five, while matching baseline configurations and solver protocols.The appendix gives task-specific training and testing procedures.Source: §C.1 · p. 17, C Experimental Setups · p. 17

C.2 Selection of Large Language Models

• The study selects seven non-reasoning and three reasoning models to span a wide range of intelligence, using models with benchmark scores available on open leaderboards.GPT-5-mini has the highest intelligence score among the selected models.Source: §C.2 · pp. 17–18

C.3 Implementations of Datasets

• TSP training uses 64 random Euclidean instances with 50 nodes, and testing uses three independently generated 64-instance sets at 50, 100, and 200 nodes.All methods share training and test instances under identical random seeds; selection uses training performance and reporting uses held-out tests.Source: §C.3 · p. 18
• CVRP training uses 10 random 50-customer instances, while testing uses three independent 64-instance sets at 50, 100, and 200 customers.Training and testing share an ACO configuration of 30 ants and 100 iterations.Source: §C.3 · p. 18
• FSSP training uses 64 random instances with 50 jobs and 2–20 machines; testing follows the Taillard benchmark sets used by EoH.Processing times are sampled uniformly from 1 to 100; adapted baselines use the same evaluation protocols as SimpleEvol and EoH.Source: §C.3 · p. 19

C.4 Baseline Implementation

• Baseline frameworks retain their original algorithmic configurations and are evaluated under a unified protocol; reference gaps use LK-based TSP values, DeepACO CVRP values, and Taillard FSSP values.The TSP references are typically optimal through 315 nodes and approximate for larger instances.Source: §C.4 · pp. 19–20

C.5 Search Framework Configurations

• Search-framework hyperparameters are summarized by task, with GLS iteration limits controlling search depth and CVRP ACO ants and iterations controlling exploration and convergence.The table’s Dtrain and Dtest denote separate synthetic training and testing datasets.Source: Table 5 · p. 20, §C.5 · p. 20

D Details of the Problems Evaluated and the Seed Heuristics

• In step-by-step TSP construction, the heuristic receives the current and destination nodes, unvisited nodes, and distance matrix, then selects the next node.The task is symmetric TSP and the objective is a minimum-length tour.Source: D Details of the Problems Evaluated… · p. 20
• For CVRP-ACO, the heuristic maps distance, coordinates, demands, and capacity to edge-preference scores combined with pheromone trails to guide probabilistic route construction.The seed heuristic for other AHD frameworks is inverse-distance; SimpleEvol does not require a seed heuristic.Source: D Details of the Problems Evaluated… · pp. 21–22
• For FSSP-GLS, the evolved heuristic updates the execution-time matrix and selects jobs for perturbation during local search, which seeks a job sequence minimizing makespan.GLS uses local-search operators such as Swap and Relocate and a heuristic-guided penalty mechanism.Source: D Details of the Problems Evaluated… · p. 21
• SimpleEvol starts without an added seed heuristic, using problem descriptions to let the LLM define its initial exploration; other frameworks use random TSP selection and inverse-distance CVRP-ACO seeds.The appendix also provides seed implementations for the other problem settings.Source: D Details of the Problems Evaluated… · pp. 21–22

E.1 Calculations of AHD Complexity Score (AHI)

• AHI(A) combines framework modules, distinct LLM operation types, and average LLM calls, with calculations based on official implementations rather than paper descriptions.Initialization is excluded from operation types because all frameworks require an initial generation stage; contextual-only components are not counted separately.Source: §E.1 · p. 22
• Across 216 tested weight combinations, AHI–ICE correlations remain negative on TSP and CVRP, with median Spearman correlation −1.0 and mean approximately −0.944.SimpleEvol has the lowest AHI in 174 settings (80.56%), and the original AHI ranking is preserved in 168 (77.78%).Source: §E.1 · p. 23

E.2 Details of Model Intelligence Score I(m)

• I(m) aggregates four benchmarks covering knowledge and reasoning, instruction following, mathematics, and code generation as a relative proxy for AHD-related intelligence.The benchmarks capture distinct capability dimensions; I(m) is not intended as an all-encompassing intelligence measure.Source: §E.2 · pp. 23–24, Table 6 · p. 24

F.1 Heuristics Evolved by SimpleEvol

• The stronger model improves not only objective value but also structural sophistication, synthesizing insertion-based reasoning, scale-normalized regret, and topology-aware priors; the weaker model tends toward simpler greedy rollout strategies.The weighted nearest-neighbor rollout estimates full completion cost by greedy nearest-neighbor chaining to the destination, then combines immediate distance and rollout estimate with alpha = 0.75 × (1 − progress_ratio) + 0.25 × progress_ratio and beta = 1 − alpha, emphasizing immediate distance more strongly early.Source: §F.1 · p. 25
• The paper reports that heuristic quality can scale substantially with model intelligence under a fixed AHD framework, with the primary bottleneck potentially shifting toward model intelligence.The comparison uses the same SimpleEvol framework and identical evaluation budget.Source: §F.1 · p. 25
• 5.97 versus 6.15 fitness scores: GPT-5-mini’s TSP heuristic scores lower than GPT-4.1-nano’s under the same framework and evaluation budget.Lower fitness is better; the paper reports GPT-5-mini as having approximately twice GPT-4.1-nano’s intelligence score.Source: §F.1 · pp. 25, 27

F.2 Results on TSPLib

• 10.26% average optimality gap and 8 top-1 results across 15 instances: SimpleEvol leads the compared AHD methods on TSPLIB.The evaluation averages over three runs with different starting nodes; per-instance best results are marked in the table.Source: §F.2 · p. 28, Table 7 · p. 28

F.3 Robustness of AHI–ICE relationship

• SimpleEvol remains the highest-ICE framework under leave-one-out model removal and an alternative intelligence index; adding MCTS-AHD preserves the inverse AHI–ICE ordering.The leave-one-out framework ordering is SimpleEvol, FunSearch, EoH, ReEvo, then MCTS-AHD on both tasks.Source: §F.3 · pp. 28–29, Table 8 · p. 29

F.3.1 Statistical Uncertainty of ICE Differences

• 79.1%–99.9%: Bayesian-bootstrap posterior probabilities favor SimpleEvol’s higher ICE in all eight task–framework comparisons, with five exceeding 0.95.In leave-two-model-out checks, SimpleEvol’s ICE differences remain positive in at least 39 of 45 subsets for every baseline comparison.Source: §F.3.1 · pp. 29–30, Table 9 · p. 30

F.4 Search Dynamics and Budget-dependent ICE

• SimpleEvol maintains the lowest best-so-far gap over later search stages on TSP Constructive and CVRP-ACO, with competitive performance appearing early.The figure shows mean trajectories across independent runs with ±1 standard deviation; CVRP-ACO uses a symmetric-log scale.Source: Figure 11 · p. 30, §F.4 · p. 30
• From 200 evaluations onward, SimpleEvol has the highest ICE on both tasks, and its advantage generally grows at larger budgets.At very small budgets the ordering is less stable, consistent with limited search trajectory and initialization variability.Source: §F.4 · p. 31, Table 10 · p. 31

F.5 Extension to FSSP under the GLS Framework

• On FSSP-GLS synthetic IDD instances, fitted trends are positive across frameworks and SimpleEvol leads in ICE; simpler frameworks tend to convert intelligence more efficiently.The figure covers 64 held-out IDD instances and Taillard benchmark instances.Source: §F.5 · pp. 31–32, Figure 12 · p. 31
• On Taillard, fitted intelligence–performance slopes are negative across frameworks, yet SimpleEvol achieves the best performance score under 8 of 10 backbones.The paper attributes the distribution gap to differences between synthetic training instances and Taillard instances, including job sizes and machine counts.Source: §F.5 · p. 32

LLM queries

• ReEvo issues substantially more LLM queries than the other frameworks, while FunSearch and EoH use 820–829 queries and SimpleEvol falls between these groups.SimpleEvol’s additional calls primarily support periodic history summarization; ReEvo’s reflect separate reflection-generation calls, especially in crossover.Source: §F.6 · p. 32

Token consumption

• SimpleEvol uses the most input tokens because its single-trajectory design retains running meta-information and compressed summaries, but its output-token use is moderate and below ReEvo on both tasks.The paper notes that higher input consumption does not translate into disproportionately higher monetary cost because input tokens are priced substantially lower than output tokens.Source: §F.6 · p. 32

Runtime Consideration

• SimpleEvol’s runtime is moderate on CVRP but somewhat higher on TSP Constructive, partly because its single trajectory runs sequentially rather than parallelizing candidate generation and evaluation.Runtime also varies widely across methods and models, reflecting inference-speed differences, particularly among reasoning models; Figure 13 visualizes the computational-cost comparison.Source: §F.6 · pp. 32–33, Figure 13 · p. 33

Overall

• SimpleEvol’s ICE advantage does not come from substantially higher resource use; its main overhead is input tokens, while query and output-token use are comparable to or below ReEvo.The authors describe this overhead as a consequence of the context-rich, single-trajectory design and say it carries relatively moderate monetary cost under standard API pricing.Source: §F.6 · pp. 33–34

G Detailed Performance Results for ICE Computation

• The detailed results provide raw objective values, optimality gaps, average gaps across sizes, and performance scores P(m) used for the ICE analysis.Results are based on three independent runs, with the best results among models for each problem size marked in bold.Source: G Detailed Performance Results for ICE… · p. 34
• The appendix includes framework-specific TSP and CVRP test-set tables, plus a comparison across IDD and Taillard out-of-distribution instances.The IDD and Taillard comparison reports performance across AHD frameworks.Source: Table 12 · p. 34, Table 13 · p. 34, Table 14 · p. 35

H Limitations and Future Work

• Whether the empirical relationship between framework complexity and ICE generalizes beyond combinatorial optimization remains open, especially for domains with stochastic feedback or surrogate-mediated evaluation.The authors plan to broaden evaluation to additional domains.Source: H Limitations and Future Work · p. 40

I Broader Impact

• Potential benefits include improved understanding of LLM use in combinatorial optimization and simpler, more interpretable design pipelines, while unreliable unvalidated heuristics and computational cost are identified as risks.The authors state that candidates are evaluated with deterministic external solvers and feasibility constraints, and that human oversight remains important for deployment.Source: I Broader Impact · p. 40

J The Use of Large Language Models

• LLMs generate and iteratively refine heuristic code using structured feedback from external evaluation; manuscript use is limited to language polishing, not scientific claims or analysis.The authors say key ideas, methods, and findings were developed and verified by them.Source: J The Use of Large Language Models · p. 40

NeurIPS Paper Checklist

• The checklist says experimental details are provided in the appendix and main text, results are averaged over multiple runs, and leave-one-out means and standard deviations are reported.The code and prompts are documented and slated for release upon acceptance; the checklist also states that the introduction’s claims are supported by Section 5 results.Source: NeurIPS Paper Checklist · pp. 41, 43