PaperlayerView exact revision on arXiv

Source-linked AI summary

ExpEvolve: Structuring and Reusing Experience for Open-Ended Discovery

Yongqiang Chen, Chenxi Liu, Deyu Zou, Zhenhao Chen, Tongliang Liu, Bo Han, Kun Zhang

arXiv:2610.29303v1cs.LGcs.CLstat.ML

TL;DR

Evolutionary coding agents often reuse programs and make low-level mutations, while high-level ideas can compound across scientific discovery. ExpEvolve extracts idea factors from scoring differences and uses them to guide exploration and exploitation; across 11 mathematical tasks it improves final performance in most settings, with gains up to 5.0×.

  • Problem

    Existing evolutionary coding agents reuse programs or summarized insights, but LLM guidance can focus on low-level details rather than the high-level contrasts that scientists use to accumulate ideas.

    Source: §1 · p. 2

  • Method

    ExpEvolve discovers high-level factors that explain score differences and uses them as bandit actions to guide idea exploration and exploitation.

    Source: §1 · pp. 2–3

  • Results

    Across 11 mathematical tasks, ExpEvolve improves final performance over SCS and ShinkaEvolve in most settings, with improvements up to 5.0×; it also improves OpenRSI’s mean final best-so-far score on all six MLS-Bench tasks.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Idea-based control supports exploitation of promising ideas while continuing to explore programs with varied ideas.

    Source: §1 · p. 3

    The studied tasks remain limited to small-scale verification and are relatively simple; broader problems with expensive verification remain to be explored.

    Source: A. Limitations and Future directions · p. 20

Abstract

from arXiv · show

Evolutionary coding agents such as AlphaEvolve are one of the notable successes in using Large Language Models (LLMs) to build AI Scientists. These agents tackle open-ended scientific problems by iteratively improving and evolving programs, leveraging the prior knowledge and reasoning capabilities of LLMs. Despite their success, mutations over programs are mostly low-level upon surface heuristics, without a persistent unit of control. In contrast, science compounds through ideas. In this work, we propose ExpEvolve, which injects idea-level extraction and control into evolution: it discovers and leverages the high-level factors from programs that explain scoring differences among different programs. We characterize theoretical conditions on when discovery with idea factors improves sample efficiency. We also build a practical framework to show that the extracted high-level idea factors are helpful for guiding exploitation from experience and exploration when discovery comes to a plateau. Across 11 open-ended mathematical tasks, ExpEvolve significantly improves the final performance and sample efficiency up to 5.0x. The improvements also transfer to 4 other LLMs and to 6 machine learning tasks from MLS-Bench. Analysis shows that ExpEvolve can discover idea-level factors to provide better exploration and exploitation for evolutionary discovery.

1. Introduction

Evolutionary coding agents reuse evaluated programs and textual insights, but their mutations can emphasize low-level details rather than scientific ideas. ExpEvolve extracts high-level factors from programs and uses them to guide exploration and exploitation; it improves performance across most tested settings, with gains up to 5.0×.

1. Introduction

  • The motivation is that scientific ideas compound during hypothesis evaluation, making experience reuse relevant to generating high-quality hypotheses.The passage gives avoiding repeated mistakes and encoding promising exploratory proposals as examples.Source: §1 · p. 1
  • Existing evolutionary agents reuse successful programs or summarized insights, while mutations span low-level details and high-level strategies that can affect scores.The paper contrasts this with scientists’ recognition and accumulation of high-level contrasts among programs.Source: §1 · pp. 1–2
  • Figure 1 contrasts low-level edits to a high-scoring parent, which score lower, with idea-level comparison that isolates a shared procedure factor found in higher-scoring programs.The identified factor is then inserted into programs with different structures.Source: Figure 1 · p. 2
  • The paper frames discovery as a POMDP and defines ideas as high-level mechanistic program properties that determine evaluation scores.Without ideas, revisions can be indistinguishable from low-level changes; identifying ideas also requires exploring programs where ideas vary.Source: §1 · p. 2
  • ExpEvolve identifies high-level factors that explain score differences, then uses them as bandit actions to control idea exploration and exploitation.It also reserves slots for random exploration and idea-guided exploration when evolution reaches a plateau.Source: §1 · pp. 2–3
  • Across 11 mathematical tasks, ExpEvolve improves final performance over SCS and ShinkaEvolve in most settings, with improvements up to 5.0× under smaller budgets.The evaluation uses a budget of 200 programs and two budget-parallelization configurations.Source: §1 · p. 3

2. Related Work

Related work covers LLM-based AI scientist agents and experience reuse in evolutionary coding agents. ExpEvolve differs by discovering and exploiting high-level idea factors rather than treating texts or programs as the unit of experience.

2. Related Work

  • Evolutionary coding agents integrate LLMs into program search scored by explicit evaluators and have been applied across mathematics, materials science, biology, and LLM development.The passage also notes that validation can become a main cost as generation scales and promising ideas may degrade when executed.Source: §2 · p. 3
  • Existing agents reuse evaluated programs or textual summaries, and some use experience to select inspirations across diverse strategy clusters.The cited approaches include conditioning on programs, summarizing insights, and search control.Source: §2 · p. 3
  • ExpEvolve differs by discovering and exploiting high-level idea factors to guide program mutations, rather than using texts or programs as the experience unit.Source: §2 · p. 3

3. Theoretical Formulation of Evolutionary Discovery

The section formalizes evolutionary discovery and introduces ideas as a way to describe mechanistic properties of programs. It begins by framing scientific discovery as uncovering mechanisms through interaction with the world.

3. Theoretical Formulation of Evolutionary Discovery

  • The section formalizes evolutionary discovery and introduces the notion of ideas.Source: §3 · p. 3
  • The section’s formalization connects evolutionary discovery with the introduction of ideas as a concept.Source: §3 · p. 3

3.1. Evolutionary Discovery as a POMDP

  • Scientific discovery is framed as uncovering causal mechanisms underlying a problem through interactions with the world.Source: §3.1 · p. 3
  • In evolutionary discovery, the agent interacts with the problem through an evaluator.Source: §3.1 · p. 3
  • The problem’s mechanism, denoted θ_sci, is the object of the discovery framing.Source: §3.1 · p. 3
  • The framing treats the mechanism as something the agent seeks to uncover through its interactions with the problem.Source: §3.1 · p. 3

A. Evolutionary coding agent loop B. Temporal graphical model

Evolutionary discovery is modeled as interaction with an evaluator under a static hidden mechanism, with memory guiding later proposals. The section argues that structured reuse through ideas can reduce the evaluations needed, while identifying ideas requires exploration that contrasts them.

A. Evolutionary coding agent loop B. Temporal graphical model

  • Figure 2 depicts an iterative loop in which memory informs candidate programs, an evaluator scores them under a hidden mechanism, and scored programs update the archive and memory.Source: Figure 2 · p. 4

3.2. Reusing Experience with Ideas

  • With a limited evaluation budget, experience reuse matters because scores reveal only partial information about the hidden mechanism.Evaluations can be expensive, including model training or physical experiments.Source: §3.2 · p. 5
  • Without shared structure across programs, evaluating one program does not inform the others, leaving the agent to evaluate every candidate to find the best.Source: §3.2 · p. 5
  • Theorem 3.1 contrasts structured reuse under a bounded representation and coverage condition with treating programs as unrelated.The structured setting assumes scores are linear in a known representation; the unrelated setting assigns arbitrary means to programs.Source: §3.2 · p. 5
  • Reusing high-level design choices can improve sample complexity from Ω(K) to O(d log K) when K ≫ d.Here K counts candidate programs and d is determined by score-affecting design choices.Source: §3.2 · p. 5
  • An idea is an interpretable mapping from programs to binary or categorical values that describes a shared high-level mechanistic property.Examples include construction family, initialization, and optimization procedure.Source: §3.2 · p. 5
  • Under a faithful idea representation, the score depends on a program only through its ideas, allowing the structured-reuse result to apply using a one-hot encoding of those ideas.Source: §3.2 · p. 5
  • When explored programs agree on candidate ideas, their scores cannot distinguish which idea determines performance, so identifying ideas requires contrasting programs with and without them.Source: §3.2 · pp. 5–6

4. ExpEvolve: Discovering and Exploiting Ideas from Experience

ExpEvolve discovers high-level program factors that explain score differences, then uses those factors to guide exploration and exploitation. It also changes its exploration strategy at plateaus to restore variation in ideas.

4. ExpEvolve: Discovering and Exploiting Ideas from Experience

  • ExpEvolve structures experience as idea factors and uses them to control exploration and exploitation during evolutionary discovery.Its framework also retains theoretical guidance to keep exploring programs where ideas vary.Source: §4 · p. 6, §4.2 · p. 7

4.1. Discovering Ideas from Experience

  • Explainability measures whether idea representations predict which of two programs scores better, rather than predicting exact scores.Pairwise ranking is scale-invariant and more robust to noise than scores.Source: §4.1 · p. 6
  • ExpEvolve finds unexplained program pairs, proposes factors that distinguish them, and admits factors whose annotated values have adequate support and separate scores.The idea memory stores factors with names, code-pattern descriptions, types, and value sets, with each program annotated by an LLM.Source: §4.1 · pp. 6–7

4.2. Exploiting Idea Factors for Discovery

  • Each generation reserves at least a fraction ρ of slots for random exploration and assigns the remaining slots to idea-guided actions selected by a multi-armed bandit.Actions encode edits such as adding or removing a factor; rewards compare generated-program scores with random exploration in the same generation, normalized to reduce score drift and cross-task scale differences.Source: §4.2 · pp. 7–8
  • After κ generations without best-score improvement, ExpEvolve masks actions dependent on ideas shared by top-scoring programs and increases diversified random exploration.The mutator is instructed to avoid those dependent ideas, addressing plateaus where widely used ideas stop varying and their roles cannot be identified.Source: §4.2 · p. 8

5. Experiments

ExpEvolve is evaluated on mathematical discovery and machine-learning engineering tasks, with comparisons spanning final performance, evaluation efficiency, model transfer, and search behavior. It generally improves performance and sample efficiency, including when experience is reused to guide exploration and exploitation.

5.1. Experimental Setup

  • The evaluation covers 11 mathematical tasks with 200-program budgets in two generation configurations, comparing ExpEvolve with SCS and ShinkaEvolve.Experiments use DeepSeek-V4-Flash by default, three seeds per setting, and untuned additional hyperparameters.Source: §5.1 · p. 8

5.2. Main Results

  • At 200 evaluated programs, ExpEvolve improves mean and best final performance over SCS and ShinkaEvolve in most settings, robustly across budget parallelizations.The two configurations use 10 generations of 20 programs or 20 generations of 10 programs.Source: Table 1 · p. 9, §5.2 · p. 9
  • On four tasks, ExpEvolve reaches SCS’s final score with 1.7× to 26.2× fewer evaluations under both configurations.Figure 6 plots best-so-far scores over the evaluation budget for Hadamard, Sums and differences, Heilbronn, and Minimum overlap.Source: Figure 6 · p. 9, §5.2 · p. 9
  • ExpEvolve’s advantage transfers to DeepSeek-v4-pro, GLM-5.2, and Gemini-3.7-Flash; SCS+meta helps early, but its improvement slows while ExpEvolve keeps improving.Figure 7 compares SCS and ExpEvolve across other LLMs, and compares SCS, SCS+meta, and ExpEvolve.Source: §5.2 · p. 9, Figure 7 · p. 10
  • In a Sums and differences run, idea-guided slots produced 6 of 11 new best programs; 92 such slots selected 7 actions, with all six from two actions.Figure 8 also shows the highest-weight idea factor for each task.Source: §5.2 · p. 10, Figure 8 · p. 10

5.3. Additional Experiments on Machine Learning Engineering Tasks

  • On six MLS-Bench tasks, OpenRSI+ExpEvolve outperforms OpenRSI on all six, with the largest gains on Online bandit and Anomaly detection.Example trajectories show idea-guided exploration and exploitation helping improve performance at plateaus.Source: Figure 9 · p. 11, §5.3 · p. 11

6. Conclusions

The conclusion presents ExpEvolve as a way to structure evolutionary-discovery experience into idea factors that guide search, reporting improved performance and sample efficiency across mathematical and MLS-Bench tasks. The paper limits its demonstrated scope to relatively simple, small-scale verification and situates its approach alongside related work on evolutionary agents, learned mutators, and causal discovery.

6. Conclusions

  • ExpEvolve discovers idea factors from unexplained program pairs, uses them as multi-armed-bandit actions, and explores varied ideas through random and idea-guided exploration at plateaus.The analysis states that faithful idea representations can reduce evaluations from Ω(K) to O(d log K), when K ≫ d.Source: §6 · p. 11

A. Limitations and Future directions

  • The evaluation remains limited to relatively simple tasks with small-scale verification; broader problems with expensive signals, including biology and medicine, remain to be explored.The paper notes that task-background knowledge could also guide factor discovery.Source: A. Limitations and Future directions · p. 20

B. Related Work

  • Related work spans evolutionary coding agents and search-control methods, while ExpEvolve assigns credit to ideas discovered during search; its fixed LLM and harness distinguish it from learned-mutator and self-improving approaches.The paper also contrasts its program-derived idea variables and adaptively chosen interventions with prior causal-discovery work.Source: B. Related Work · pp. 20–21

C. A Causal View of the Formulation

The appendix frames scientific discovery as inference about a hidden world through program evaluations, then explains why high-level ideas require varied evaluations to identify. It also formalizes limits on what scores reveal within and across evaluation environments.

C.1. Formulation of Scientific Discovery

  • The AI Scientist is modeled as a POMDP: it proposes programs, observes evaluator outcomes, and updates memory about the unknown scientific world.The recurrent loop uses each program outcome as evidence for the next decision.Source: §C.1 · p. 21, Figure 10 · p. 22

C.2. Ideas and Causal Representation Learning

  • Ideas summarize high-dimensional program designs at a higher level, and faithfulness requires expected scores to depend on designs only through their ideas.The paper relates this condition to causal feature learning and causal abstraction.Source: §C.2 · pp. 22–23
  • Idea representations differ from causal representation learning because they are interpretable program functions, need only explain the score, and can be probed through program edits.An edit may also change other ideas, so it is not necessarily an intervention on only one idea.Source: §C.2 · p. 23

C.3. Essentiality of Causal Knowledge for AI Scientists

  • Scores from evaluated programs may leave competing causal explanations indistinguishable, so identifying relevant knowledge requires evaluating programs that separate those explanations.For example, shared initialization and refinement in circle-packing programs cannot reveal which factor explains performance.Source: §C.3 · p. 23
  • When K≫d, a correct causal representation can yield exponential or multiplicative sample-efficiency gains over a black-box baseline under finite budgets.For K=2^d, the structured upper bound grows polynomially in d while the black-box lower bound grows exponentially.Source: §C.3 · pp. 23–24
  • If competing ideas agree on every evaluated program, expected regret is at least Δ/2 under one hypothesis, regardless of budget.Exploration must include programs where the ideas differ; plateau-aware revision is one way ExpEvolve targets such programs.Source: §C.3 · p. 24

C.4. Transfer of Scientific Knowledge across Environments

  • Source-environment scores can be identical under hypotheses with different target-optimal programs, making target suboptimality unavoidable for some hypothesis at every budget.The appendix leaves a full study of cross-environment knowledge transfer to future work.Source: §C.4 · p. 24

D.2–D.4. Setup and belief updates

  • The formal setup treats scientific knowledge as a fixed hidden instance while environments vary evaluation or deployment protocols, and represents evaluation outcomes probabilistically, including deterministic evaluators as a special case.Bayesian belief updates condition on the program and observed outcome; for deterministic evaluation, the posterior restricts hypotheses to those consistent with the outcome.Source: §D.2 · p. 25, §D.3 · pp. 25–26, §D.4 · p. 26

E.3. Formal statement and proof

This proof formalizes a sample-efficiency contrast between structured and black-box program search. Under a covered linear representation, estimating the weights from basis programs supports a near-optimal recommendation; the black-box class has a separate lower bound.

E.3. Formal statement and proof

  • The theorem contrasts a structured linear upper bound with a lower bound for uniformly correct policies in the unstructured black-box class.The supplied formal-statement passages do not expose the bounds’ full expressions.Source: §E.3 · pp. 27–28
  • The structured construction evaluates every basis program n times, estimates the coordinates of the weight vector, and chooses the estimated best program.Its total evaluation budget is T=nd.Source: §E.3 · p. 28
  • T=nd evaluations suffice for the structured linear class to achieve simple regret at most 2ε with probability at least 1−δ.The construction estimates the unknown weight vector from repeated evaluations of d basis programs, then recommends the program with the highest estimated value.Source: §E.3 · pp. 27–28
  • The proof’s black-box lower bound constructs alternatives with different best programs and uses transcript distinguishability to constrain the evaluations required.The proof relates KL divergence between transcripts to the number of times the differing program is evaluated.Source: §E.3 · p. 29
  • With a deterministic evaluator, d basis evaluations recover the structured weight vector exactly and achieve zero simple regret.In the black-box class, a uniform worst-case guarantee instead requires evaluating all K programs at least once.Source: §E.3 · p. 30
  • The comparison assumes a finite program set and, for the structured upper bound, a covered representation with basis programs and Gaussian observation noise.The authors relate the lower-bound argument to best-arm identification and the upper bound to linear bandits.Source: §E.3 · p. 30

F.1. Formal statement and proof

The proof shows that evaluating only programs on which two candidate ideas agree cannot distinguish mechanisms whose optimal programs differ. It extends this non-identifiability logic to source and target environments, where additional source evaluations may not resolve the target choice.

F.1. Formal statement and proof

  • If a policy evaluates only programs where two ideas agree, then under one mechanism its expected regret is at least Δ/2 for every budget.The result assumes the mechanisms’ optimal programs differ with margin Δ.Source: §F.1 · p. 30
  • The proof establishes indistinguishability because agreeing ideas yield identical outcomes and noise models on every program in the agreement set.The resulting transcript and final-output distributions are the same under both mechanisms.Source: §F.1 · p. 30
  • Programs outside the ideas’ agreement set are necessary to identify which idea matters; plateau-aware revision targets such programs.This changes the proposal distribution when leading programs share ideas.Source: §F.1 · p. 31

G.2. Formal statement and proof

  • For cross-environment transfer, source observations can be identical under two hypotheses even when their unique target-optimal programs differ by margin Δ.The formal result applies to policies that interact only with the source environment.Source: §G.2 · p. 31
  • Under that source-indistinguishability condition, at least one hypothesis has expected target regret of at least Δ/2, regardless of the evaluation budget.The result holds for deterministic or stochastic evaluators because indistinguishability is stated for the full observation model.Source: §G.2 · pp. 31–32

G.3. Concrete examples satisfying the conditions

  • The examples instantiate the transfer barrier as public-test shortcut features that break under deployment shifts and relaxed verifiers whose rankings can change under exact validation.The examples illustrate settings in which source evaluations do not distinguish hypotheses but target-optimal choices differ.Source: §G.3 · p. 32

H. Implementation Details of ExpEvolve

ExpEvolve maintains an annotated idea memory, discovers factors that explain score contrasts, and uses bandit-selected actions to guide program generation. At plateaus, it probes the leading programs for shared properties and shifts search toward alternatives.

H. Implementation Details of ExpEvolve

  • The search loop generates and evaluates programs, updates the archive and idea memory, periodically discovers factors, and invokes plateau revision when progress stalls.Programs are evaluated once; failed evaluations or non-finite objectives are not repaired or retried, and failed generation calls count toward the budget.Source: H. Implementation Details of ExpEvolve · pp. 32–33

H.1. Idea Memory and Annotation

  • ExpEvolve stores each idea factor’s name, code-pattern description, type, and values, annotates programs, and updates score contrasts after each generation.Highly correlated factors are merged; degenerate evaluations are excluded from the statistics.Source: §H.1 · p. 33

H.2. Idea Discovery

  • Discovery targets unexplained score contrasts: it selects high-gap pairs initially or misranked pairs later, proposes candidate factors, annotates them, and admits supported, nonduplicate factors above a contrast threshold.Discovery is scheduled after the first generation when at least 15 successful programs are archived and fewer than 12 non-background factors are stored.Source: §H.1 · p. 34, §H.2 · pp. 34–35

H.3. Idea-Guided Actions

  • The action catalog encodes binary factors as ADD or REMOVE and categorical factors as SET actions; a bandit allocates idea-guided slots alongside random exploration.Action prompts provide a strategy instruction and example programs in the target state; warm-up slots also receive diversification instructions.Source: §H.3 · pp. 35–36

H.4. Idea-Guided Exploration at Plateaus

  • At plateaus, ExpEvolve probes top-scoring programs for shared properties, then masks dependent actions, increases random exploration, and diversifies demonstrations to seek alternatives.The probe records a property when at least 5 of the 8 top programs are annotated with it and at least 80% realize it; plateau changes are reverted when the best score improves.Source: §H.4 · pp. 36–37

I.1. Tasks

The experiments cover mathematical optimization and discovery tasks, compare ExpEvolve with evolutionary baselines, and use a shared budget of evaluated programs. Task-specific formulations and resource settings define the scope of those comparisons.

I.1. Tasks

  • Nine tasks come from the mathematical problems studied by SCS, and all methods use the same task evaluator with a 60-second limit except the uncertainty inequality’s 300 seconds.The uncertainty inequality uses a larger Hermite–Gaussian search space than the original formulation, so its results are not comparable with values from that original formulation.Source: §I.1 · pp. 37–38

I.2. Baselines

  • SCS samples three archived programs per prompt; SCS+meta adds up to five rewritten recommendations, while ShinkaEvolve uses five islands and generates one program per generation.SCS+meta is run on four specified tasks and configurations; ShinkaEvolve does not distinguish ExpEvolve’s two budget configurations.Source: §I.2 · p. 39

I.3. Budget and Resources

  • All methods evaluate each generated program once, and failures consume the budget; ShinkaEvolve begins with five initial-program copies and generates 199 programs, reporting final performance at 199 generated programs.ExpEvolve’s calls for proposing, annotating, probing, and judging idea factors do not evaluate programs or consume the budget.Source: §I.3 · p. 40

J. Additional Results

The additional-results section points to per-seed final scores and best-so-far trajectories, and defines a sample-efficiency comparison against SCS. The accompanying prompts specify how factors and plateau conditions are communicated to the mutator.

J. Additional Results

  • Tables 5–8 report per-seed final scores and best-so-far scores along the evaluation budget, while Table 9 reports evaluated-program counts for reaching SCS’s final best score.The sample-efficiency counts compare the first evaluation count at which each method’s seed-averaged best-so-far score reaches the relevant final score.Source: J. Additional Results · p. 40, Table 5 · p. 41, Table 6 · p. 42

K. Prompts

  • At a plateau, the prompt names the common combination among top programs, reports the stalled score and duration, and asks for alternative constructions or combinations.The background-probe prompt seeks shared structural properties among top-scoring programs so search can deliberately depart from that family.Source: K. Prompts · pp. 44–45
  • The annotator prompt requests JSON assignments for binary or categorical factors and permits null when a factor is unknown.The strategy prompt directs the mutator to use or avoid a binary pattern, or set a categorical factor to a specified value, while improving on the anchor program.Source: K. Prompts · pp. 40, 44

K.1. More Details of Experiments on Machine Learning Engineering

The paper integrates ExpEvolve’s idea discovery and search control into OpenRSI for six MLS-Bench tasks. The reported configurations improve mean final best-so-far scores across all six tasks.

K.1. More Details of Experiments on Machine Learning Engineering

  • The six tasks target machine-learning algorithm components under fixed task interfaces and evaluation protocols, using scores and execution feedback for search.The tasks are Online bandit, Anomaly detection, Clustering, Multi-objective optimization, Subgroup calibration shift, and Evolution strategy.Source: §K.1 · p. 45
  • The integration initializes idea memory from shared history, discovers factors from insufficiently explained score differences, and admits factors with support and score contrast.Each generation reserves two slots for Open exploration and schedules three for Guided search; guided actions select a compatible high-scoring parent and receive improvement-over-parent feedback.Source: §K.1 · p. 45
  • OpenRSI+ExpEvolve improves mean final best-so-far scores over OpenRSI on all six MLS-Bench tasks, with the largest gains on Online bandit and Anomaly detection.Scores average three seeds continuing from the same 20-slot history for 50 additional evaluations.Source: §K.1 · p. 45
Loading 2610.29303v1…