PaperlayerView exact revision on arXiv

Source-linked AI summary

AdaEvolve: Adaptive LLM Driven Zeroth-Order Optimization

Mert Cemri, Shubham Agrawal, Akshat Gupta, Shu Liu, Audrey Cheng, Qiuyang Mang, Ashwin Naren, Lutfi Eren Erdogan, Koushik Sen, Matei Zaharia, Alex Dimakis, Ion Stoica

arXiv:2602.20133v1cs.NEcs.AIcs.CL

TL;DR

Static schedules in LLM-guided evolutionary search do not adapt to non-stationary progress, potentially misallocating computation between stagnating and promising populations. AdaEvolve uses an accumulated improvement signal to coordinate local exploration, bandit-based global resource routing, and meta-guidance. Across 185 problems, it consistently outperforms open-source baselines and often matches or exceeds human or AI solutions.

  • Problem

    LLM-guided evolutionary systems commonly use static exploration rates, prompts, and resource schedules that do not adapt to changing search progress.

  • Method

    AdaEvolve is a hierarchical adaptive optimizer that uses accumulated improvement signals to coordinate local adaptation, global bandit scheduling, and meta-guidance.

  • Results

    Across 185 algorithm design and optimization problems, AdaEvolve consistently outperforms open-source baselines and often matches or exceeds the best human or AI-generated solutions.

  • Takeaways & Limitations

    A single adaptive controller can regulate exploration, resource routing, and strategy generation for diverse inference-only program-generation and optimization tasks.

Abstract

from arXiv · show

The paradigm of automated program generation is shifting from one-shot generation to inference-time search, where Large Language Models (LLMs) function as semantic mutation operators within evolutionary loops. While effective, these systems are currently governed by static schedules that fail to account for the non-stationary dynamics of the search process. This rigidity results in substantial computational waste, as resources are indiscriminately allocated to stagnating populations while promising frontiers remain under-exploited. We introduce AdaEvolve, a framework that reformulates LLM-driven evolution as a hierarchical adaptive optimization problem. AdaEvolve uses an "accumulated improvement signal" to unify decisions across three levels: Local Adaptation, which dynamically modulates the exploration intensity within a population of solution candidates; Global Adaptation, which routes the global resource budget via bandit-based scheduling across different solution candidate populations; and Meta-Guidance which generates novel solution tactics based on the previously generated solutions and their corresponding improvements when the progress stalls. We demonstrate that AdaEvolve consistently outperforms the open-sourced baselines across 185 different open-ended optimization problems including combinatorial, systems optimization and algorithm design problems.

1 Introduction

AdaEvolve addresses the rigidity of static LLM-guided evolutionary search by using accumulated fitness improvements to adapt exploration, resource allocation, and solution tactics. Across 185 optimization and algorithm-discovery problems, it improves over open-source baselines and often matches or exceeds human or prior AI solutions.

  • Motivation: Inference-time search reframes program generation from one-shot generation into sequential decision-making, but fixed operators and schedules limit adaptation to search feedback.Existing methods often use fixed temperatures, rigid prompts, and discard failed-attempt history.
  • Motivation: LLM-guided evolutionary algorithms use LLMs as semantic mutation operators for discrete, non-differentiable search spaces.This extends evolutionary search beyond traditional random syntactic mutations.
  • Motivation: Fitness-improvement trajectories provide a gradient analogue: gains indicate productive search directions, while vanishing gains signal stagnation requiring increased variance or redirection.AdaEvolve derives adaptive behavior from this signal rather than gradients.
  • AdaEvolve: AdaEvolve unifies local exploration intensity, global resource allocation, and strategy generation under one history-based improvement signal.The framework replaces ad-hoc heuristics with a cohesive adaptive optimizer.
  • AdaEvolve: A globally normalized bandit scheduler routes computational budget toward productive subpopulations instead of islands refining poor or stale solutions.The scheduler evaluates progress relative to the global best solution.
  • Results: AdaEvolve improves over open-source baselines across 185 problems and reaches or matches the best known human or prior AI solutions in several benchmark groups.It does so with identical hyperparameters throughout: 4/6 mathematical optimization tasks and 6/7 ADRS systems benchmarks meet or exceed those solution levels.

2 Related Works

Prior work scales inference-time search through reasoning paths, search trees, and evolutionary scaffolds, with LLMs serving as semantic variation operators. AdaEvolve differs by dynamically regulating exploration and stagnation responses using inference-only adaptive control.

  • Test-Time Scaling and Search Algorithms: Test-time scaling methods improve search by sampling diverse reasoning paths or constructing structured search trees with techniques such as Chain-of-Thought, Self-Consistency, and MCTS.These methods allocate additional inference computation to explore solution spaces.
  • LLM-Guided Evolutionary Search: LLM-guided evolutionary search iteratively proposes, evaluates, and refines candidates, establishing LLMs as semantic variation operators for automated discovery.FunSearch and ELM are cited as demonstrations of this paradigm.
  • LLM-Guided Evolutionary Search: Related approaches evolve prompts, language-space candidates, mutation operators, or generation policies, often combining reflection with diversity maintenance.GEPA maintains a Pareto set of strong-but-diverse prompt candidates.
  • LLM-Guided Evolutionary Search: Open-source island-based frameworks differ in their mechanisms, including parent sampling, code rewrites, adaptive LLM ensembles, and island-based genetic search.OpenEvolve, ShinkaEvolve, and CodeEvolve exemplify these directions.
  • AdaEvolve: AdaEvolve dynamically regulates the exploration-exploitation tradeoff and mitigates stagnation without manual threshold tuning, focusing on inference-only evolutionary scaffolds.This distinguishes its adaptation focus from learning-based variants such as ThetaEvolve, FLEX, and TTT-Discover.
  • Adaptive Optimization and Control: AdaEvolve applies the adaptive-gradient principle to discrete search by treating fitness-improvement trajectories as an analogue of gradient information.Adaptive gradient methods use exponential moving averages of gradient moments to normalize updates.

3 The AdaEvolve Framework

AdaEvolve formulates LLM-driven program synthesis as hierarchical optimization over executable programs and adapts search using a shared accumulated improvement signal. Its three feedback levels adjust within-island exploration, allocate computation across islands, and generate new tactics when global progress stalls.

  • 3.1 Problem Formulation: AdaEvolve maximizes program fitness over a discrete space of executable programs under a computational budget.The search uses parallel subpopulations called islands, each maintaining a local archive and asynchronously applying selection, LLM mutation, evaluation, and state updates.
  • Accumulated Improvement Signal: The accumulated improvement signal summarizes recent progress using an exponential moving average of squared normalized improvements.It decays during stagnation and acts as a real-time volatility measure: high values indicate productive trajectories, while low values indicate convergence or stagnation.
  • 3.2 Level 1: Local Adaptation: Local Adaptation increases exploration when an island stagnates and favors exploitation when its recent productivity is high.Exploration probability lies between Imin = 0.1 and Imax = 0.7; exploration samples parents uniformly, whereas exploitation selects parents proportionally to fitness.
  • 3.3 Level 2: Global Adaptation: Global Adaptation treats islands as bandit arms and routes computational budget toward those most likely to yield future improvements.AdaEvolve uses UCB selection with decayed rewards and visit counts, while unvisited islands receive an initial visit.
  • 3.3 Level 2: Global Adaptation: Global normalization values improvements against the best solution across all islands, avoiding poor-island bias and stale early breakthroughs.Ring migration exchanges top programs every M iterations, and migrated programs update local state without changing UCB statistics.
  • 3.4 Level 3: Meta-Guidance: Meta-Guidance generates alternative high-level solution tactics when all islands stagnate and numerical adaptation fails to produce progress.A separate LLM analyzes the problem, evaluator, and failed attempts, then injects proposed tactics into mutation prompts; new islands can also be spawned under global stagnation.

4 Experiments

AdaEvolve is evaluated across mathematical optimization, systems optimization, and open-ended algorithm design benchmarks under controlled model and budget settings. It consistently outperforms open-source baselines, with adaptive components helping especially when progress is deceptive, sparse, bursty, or stalled.

  • Experimental scope: AdaEvolve is evaluated on 185 problems spanning mathematical optimization, ADRS systems optimization, and Frontier-CS algorithm design.The benchmark suite contains 6 mathematical tasks, 7 ADRS systems tasks, and 172 Frontier-CS tasks.
  • Experimental setup: The evaluation uses shared backbones, evaluators, and iteration budgets for the principal comparisons, while reporting mean ± standard deviation and best-of-three results.The mathematical and ADRS experiments use GPT-5 and Gemini-3-Pro with T = 100 iterations; Frontier-CS uses GPT-5 and equal call budgets.
  • Mathematical optimization: AdaEvolve achieves the best results among open-source baselines across the mathematical optimization problems and sometimes exceeds Human/AlphaEvolve solutions.The comparison includes GEPA, ShinkaEvolve, and OpenEvolve, with AlphaEvolve and human results reported when applicable.
  • Adaptive behavior: On deceptive mathematical landscapes, fixed-policy baselines often plateau early, whereas AdaEvolve continues improving through adaptive search and Meta-Guidance.In circle packing, Meta-Guidance introduces SLSQP refinement after stagnation, improving the score from 2.5414 to 2.6095 and later to 2.636.
  • ADRS systems optimization: AdaEvolve wins all seven ADRS systems tasks across GPT-5 and Gemini-3-Pro, with the largest gains on tasks having sparse or bursty improvements.On TXN with GPT-5, performance increases from 4329 to 4348; smoother tasks show smaller differences while preserving competitive performance.
  • Ablations and case studies: Ablations indicate that all adaptive features contribute, with Meta-Guidance most helpful overall and bandit selection or local adaptation more useful on particular tasks.Removing Meta-Guidance causes the worst results in both circle packing and signal processing, while fixed-island experiments support dynamic spawning.

5 Conclusion

AdaEvolve unifies local exploration, global resource routing, and meta-level strategy generation through accumulated improvement signals. Across 185 problems, it consistently outperforms open-sourced baselines and often matches or exceeds human or AI solutions.

  • 5 Conclusion: AdaEvolve unifies local exploration, global resource routing, and meta-level strategy generation under one adaptive controller.The controller uses accumulated improvement signals from prior programs to adapt to non-stationary algorithm-discovery dynamics.
  • 5 Conclusion: 185 problems span mathematical optimization, ADRS systems tasks, and algorithm design, with AdaEvolve consistently outperforming open-sourced baselines.The evaluation covers 6 mathematical optimization tasks, 7 ADRS systems tasks, and 172 Frontier-CS algorithm design tasks.
  • 5 Conclusion: AdaEvolve often matches or exceeds the best human- or AI-generated solutions, including proprietary systems such as AlphaEvolve.The paper reports this pattern across the evaluated algorithm design and optimization problems.

A.1 AdaEvolve Algorithm Subroutines

The AdaEvolve subroutines construct prompts, generate tactics, and adapt parent selection using exploration intensity. Their control logic also tracks improvement and updates adaptive state during evolution.

  • A.1 AdaEvolve Algorithm Subroutines: The tactic generator uses the global best program, score, prior tactics, problem specification, and evaluator context to propose new tactics.Generated tactics are parsed, added to the tactic history, and returned for subsequent evolution.
  • A.1 AdaEvolve Algorithm Subroutines: Adaptive parent selection switches between diversity-oriented exploration and fitness-oriented exploitation according to search intensity.Exploration samples uniformly and chooses diverse inspirations, whereas exploitation samples from the top fitness quartile and chooses high-fitness inspirations.
  • A.1 AdaEvolve Algorithm Subroutines: The context builder combines a parent program, inspiration programs, and an optional tactic into an improvement prompt.It asks the LLM to improve the parent, consider alternative approaches, and implement the tactic when one is supplied.
  • A.1 AdaEvolve Algorithm Subroutines: Adaptive state updates use child fitness improvements to compute local normalized improvement and update UCB-related rewards and state.The supplied update procedure initializes reward at zero and assigns nonzero reward on improvement.
  • A.1 AdaEvolve Algorithm Subroutines: The evolution prompts distinguish exploitation from exploration and can inject a breakthrough tactic when global progress stagnates.Exploitation refines strong solutions or redesigns them strategically, while exploration searches alternative regions and approaches.
  • A.1 AdaEvolve Algorithm Subroutines: The tactics generator is instructed to analyze evaluator objectives, constraints, failure modes, and current-program bottlenecks before proposing implementable ideas.It is also instructed to avoid ideas fundamentally similar to previously failed attempts.

A.3 Solution Tactics Generates Examples

The code structure centralizes evolution state and adaptation in the database while the manager orchestrates prompting, generation, evaluation, and result return. Tactics are generated and injected when global stagnation is detected.

  • A.3 Solution Tactics Generates Examples: Table 5 presents example tactics across domains, pairing high-level solution strategies with representative computational approaches.The examples illustrate tactics produced by the tactic generator for different use cases.
  • A.3 Solution Tactics Generates Examples: The main controller initializes the search and invokes a single asynchronous evolution loop without directly managing islands, archives, or adaptation.It loads configuration, creates the database and manager, and inserts the initial program.
  • A.3 Solution Tactics Generates Examples: At each iteration, the manager obtains parents and inspirations, builds a mode-aware prompt, generates and evaluates a child, then returns results to the database.The prompt may include sibling, retry, or tactics context.
  • A.3 Solution Tactics Generates Examples: The database owns islands, archives, adaptive signals, migration, spawning, tactics tracking, sampling, insertion, and iteration finalization.This centralizes global search state and adaptation logic.
  • A.3 Solution Tactics Generates Examples: Islands maintain per-island archives for parent and inspiration sampling, elite replacement, and genealogy tracking, while adaptation remains separate from evaluation.The evaluator is invoked once per generated child by the manager, not by the database.
  • A.3 Solution Tactics Generates Examples: Per-island improvement signals determine search intensity, global UCB selection chooses the next island, and stagnation triggers tactics injection into later prompts.Tactic usage and lifecycle are tracked centrally and updated on successful additions.

B Benchmark Details

The benchmark-details section states that the evaluation tasks are described through their objectives, evaluation costs, and sources of noise.

  • B Benchmark Details: The evaluation describes task objectives, evaluation costs, and sources of noise.These dimensions define the benchmark details reported for the evaluated tasks.
  • B Benchmark Details: Benchmark details include the sources of noise affecting task evaluation.The passage identifies noise sources as part of the task descriptions.
  • B Benchmark Details: The section covers the evaluation characteristics needed to interpret the tasks, including objectives and computational costs.The passage explicitly names these categories but provides no task-specific values here.

B.1 ADRS

ADRS benchmarks provide challenging real-world systems optimization testbeds for evaluating adaptive search.

  • ADRS benchmarks comprise real-world systems optimization tasks with discrete design choices, noisy evaluators, and heterogeneous objectives.These characteristics make them representative and challenging testbeds for adaptive search.
  • The benchmark family evaluates adaptive search under discrete design choices and noisy evaluation conditions.
  • Heterogeneous objectives make ADRS suitable for testing adaptive search across varied systems optimization settings.

B.2 AlphaEvolve Math

The AlphaEvolve mathematical problems and ADRS tables define benchmark resources used to evaluate AdaEvolve.

  • The AlphaEvolve mathematical problems consist of classical combinatorial optimization problems with known formulations.They provide controlled testbeds for evaluating search efficiency and convergence behavior.
  • Table 6 presents ADRS systems benchmarks, with each task specifying a concrete systems optimization objective.
  • Table 7 lists the mathematical optimization benchmarks used in AdaEvolve, defined as in the AlphaEvolve paper’s Appendix B.

C AdaEvolve: Additional Results

AdaEvolve is additionally evaluated on ARC-AGI-2 to examine cross-domain generalization beyond optimization-centric tasks. The experiment uses matched inference budgets but is treated as exploratory because ARC-AGI-2 was not designed for evolutionary search and has strict train–test separation requirements.

  • AdaEvolve is evaluated on ARC-AGI-2 as an additional benchmark family beyond optimization-centric tasks.
  • ARC-AGI-2 evaluates abstract and compositional reasoning across 120 benchmark instances.
  • OpenEvolve and AdaEvolve use a matched inference budget of 30 LLM calls per task for training-split evolution before test-split evaluation.
  • Because ARC-AGI-2 is not designed for evolutionary search and assumes strict train–test separation, the experiment is exploratory rather than a direct optimization comparison.
  • Table 8 reports final accuracy for AdaEvolve on ARC-AGI-2 under a matched inference budget.
  • The results suggest that AdaEvolve maintains performance gains on reasoning-oriented tasks beyond traditional optimization settings.
Loading 2602.20133v1…