r/MachineLearning • • 1d ago

Research Can LLM-guided evolution optimize the wrong objective? An empirical study of OpenEvolve, evaluator failures, and independently verified algorithm quality [R]

There is an interesting problem at the intersection of LLM-guided program synthesis, evolutionary computation, and automated scientific discovery.

What happens when an AI system successfully discovers a better algorithm, but the fitness function responsible for selecting it is incomplete?

Systems inspired by FunSearch and AlphaEvolve use an iterative process:

  1. An LLM proposes or modifies a program.
  2. An evaluator executes it and assigns a numerical score.
  3. High-scoring candidates influence subsequent generations.
  4. The system eventually selects the best-scoring candidate.

The assumption underlying this process is that improving the evaluator's score corresponds to improving the actual solution.

But that relationship depends entirely on what the evaluator measures.

If a task has requirements that are missing from the fitness function, evolutionary search may discover implementations that optimize the measured objective while violating the original specification.

This raises a broader question: Does increasing the search budget improve the quality of the final solution, or does it sometimes increase the probability of exploiting weaknesses in the evaluation process?

Experimental setup

A recent empirical study investigated this question using OpenEvolve 0.4.0 on two bounded algorithmic tasks.

Circle packing: Place 26 non-overlapping circles inside a unit square while maximizing the sum of their radii.

Approximate k-nearest neighbors: Return approximate nearest neighbors efficiently while satisfying requirements for neighbor indices and their corresponding squared distances.

The experiments used four Gemma 4 configurations: E4B, 12B, 26B A4B MoE, and 31B.

Three search conditions were considered.

Evolutionary search (L): Candidate programs are generated using an evolutionary population and information from previous evaluations.

Best-of-N (B): Independent candidate programs are generated from the original seed without evolutionary history, then ranked by the working evaluator.

Cloud-assisted evolution (LC): The evolutionary process is preserved, but approximately 10% of mutation calls are routed to Gemini 4 Argon rather than the local Gemma model.

Search budgets included 100, 500, and 1,000 LLM calls, depending on the experimental condition.

Crucially, the evaluation process had two separate components:

Working evaluator: The score used during evolutionary search to rank candidates and select a final program.

Independent re-check: A separate post-run evaluation that verifies task requirements and measures the selected program on additional test inputs.

The independent re-check was not used to guide candidate generation or working-score selection.

This separation makes it possible to distinguish the best program discovered during search from the program the system actually selects.

Finding 1: The search discovered valid solutions but selected invalid programs

This is arguably the most interesting observation.

Three evolutionary circle-packing runs were performed with a budget of 1,000 LLM calls each.

The best valid solutions discovered during these runs achieved scores of approximately:

RunBest valid solution foundSelected program's verified score
12.4322.432
22.2040
32.2580

In two of the three runs, the search successfully discovered a valid improvement.

However, the program selected by the working evaluator failed independent verification.

Because the initial program was also invalid, the registered evaluation protocol assigned those failed selections a verified score of zero.

The important distinction is between:

Discovery quality: How good was the best valid candidate found anywhere in the search?

Selection quality: How good was the program the system actually chose?

These are not necessarily the same.

The approximate selection regrets across the three runs were 0.000, 2.204, and 2.258.

The sample is too small to establish a general relationship between search budget and reliability. Nevertheless, it demonstrates a concrete failure mode: increasing the number of generated candidates can produce strong valid solutions without ensuring that the selection mechanism retains them.

Finding 2: Higher fitness scores frequently failed independent verification

The approximate kNN experiments revealed another type of evaluator mismatch.

The working evaluator rewarded a combination of neighbor recall and relative execution speed.

However, it did not fully verify that the returned squared distances were correct for the corresponding neighbor indices.

This allowed some programs to receive favorable scores while violating part of the task's required API contract.

In the cloud-assisted kNN condition:

60 of 213 candidate evaluations (28.2%) ranked above the initial program did not represent independently verified improvements.

Of those 60 evaluations, four involved invalid candidates. The other 56 passed validity checks but achieved a verified composite score no higher than the seed.

These are candidate evaluations, not necessarily unique programs. Repeated evaluations of the same code hash are included.

The broader implication is that an evaluator can reward improvements in the properties it measures while overlooking violations of properties it does not measure.

This matters particularly when the search process is capable of discovering implementation shortcuts that were not anticipated when the evaluator was designed.

Finding 3: Hybrid local/cloud evolution produced promising, but preliminary, results

The study also compared Gemma-only evolution against a hybrid configuration in which approximately 10% of mutation calls used Gemini 4 Argon.

In approximate kNN, the cloud-assisted condition achieved a higher independently verified score in eight of nine matched runs.

The median paired difference was approximately +0.776.

In circle packing, the cloud-assisted condition performed better in seven of nine pairs, with one tie and one lower result.

These observations suggest that introducing a second model into the evolutionary search process may be useful in some settings.

However, this was an exploratory comparison involving small samples, incomplete planned conditions, and additional cloud-model computation.

It does not establish a general causal advantage for hybrid evolution.

More importantly, improved generation capability did not remove the need for independent verification.

Finding 4: Adding a correctness gate did not automatically solve the problem

A separate follow-up experiment investigated whether strengthening the working evaluator would improve the validity of the final selected program.

This experiment used six paired kNN runs with two evaluator configurations.

V1-matched: A timing-matched evaluator without a pre-fitness distance-correctness gate.

V2: The same timing framework, but with a distance-correctness gate applied before fitness evaluation.

Both conditions used the same local Gemma 4 12B model configuration and 20 LLM calls per run.

Independent verification produced the following results:

EvaluatorValid selected programs
V1-matched6/6
V25/6

The median paired score difference (V2 minus V1-matched) was +0.0290, with a range from −0.2241 to +0.7690.

The comparison is sensitive to individual runs and does not establish superiority or equivalence.

The interesting detail is the one invalid V2-selected program.

It achieved perfect neighbor recall on the holdout evaluation, but the independent checker identified 140 failures involving the returned squared distances.

In other words, the program could identify the correct neighbors while still violating the required distance contract.

A correctness gate had been added, but the final independent test still detected a failure.

This illustrates why adding a validation step and achieving complete specification coverage are different problems.

The measurement problem

A related difficulty emerged during kNN performance evaluation.

When several Docker sandboxes were benchmarked concurrently, the identical seed program received scores ranging from approximately 0.02 to 1.0.

Because runtime was part of the fitness function, system load could substantially affect candidate rankings.

The study therefore repeated timing measurements serially, using an otherwise idle machine.

This improved comparability, but measurable variability remained.

This raises an additional challenge for evolutionary program optimization: when performance is noisy, the fitness function can become a source of misleading feedback even if the correctness checks are well designed.

What can actually be concluded?

The results do not demonstrate that OpenEvolve is generally unreliable.

They do not show that evolutionary search is inherently worse than independent sampling.

They do not establish universal scaling relationships between model size, search budget, and algorithm quality.

The experiments cover two relatively small algorithmic tasks, with several exploratory comparisons and documented execution limitations.

What they demonstrate is narrower, but operationally important:

The highest fitness score observed during an evolutionary search is not necessarily a reliable measure of the final program's independently verified quality.

A system can discover a strong valid candidate and still select a weaker or invalid one.

This distinction becomes increasingly relevant as LLM-guided evolutionary systems move from benchmark optimization toward autonomous scientific and engineering work.

Questions for discussion

1. Should program-evolution systems use separate evaluators for search guidance and final candidate selection?

2. How can correctness constraints be expressed in a way that remains robust against unexpected implementation shortcuts?

3. Should algorithm-discovery benchmarks report both best-valid-discovered performance and independently verified selected-program performance?

4. How should noisy performance measurements be incorporated into evolutionary fitness without rewarding measurement artifacts?

5. Could larger search budgets systematically increase exposure to evaluator weaknesses, even when the population contains increasingly strong valid candidates?

The broader issue is not limited to OpenEvolve or any particular LLM.

It concerns the reliability of systems that use executable feedback to automate algorithm discovery.

Finding a high-scoring program is one achievement. Establishing that it is actually a better program is another.

0 Upvotes

3 comments sorted by

10

u/needlzor Professor 1d ago

If I wanted to read some LLM-generated stuff I would just ask the LLMs myself.

1

u/mv_soura 11h ago

The split you measured between discovery quality and selection quality is one of the most under discussed failure modes in automated evals. When an evolutionary loop or coding agent has enough budget, it naturally exploits any unmeasured contract like returning valid neighbor indices with wrong squared distances. Adding a single pre-fitness gate helps, but in compliance-critical pipelines we've had to decouple the search fitness score completely from an independent, specification complete verification oracle that runs out of band before any candidate is promoted.

-1

u/Unusual-Spot-5846 1d ago

For those interested in examining the underlying evidence:

Paper: https://doi.org/10.5281/zenodo.24415800

Experimental code and reproducibility artifacts: https://github.com/cyberdid/cloud-edge-ai-orchestrator

Happy to discuss the methodology, limitations, or evaluation design.