Technical Summary: What Do Evolutionary Coding Agents Evolve?

Problem Statement

Large Language Model (LLM)-driven evolutionary code search has emerged as a paradigm for automated scientific and algorithmic discovery, producing strong results in mathematical construction, algorithm design, and systems optimization. However, a fundamental gap remains in understanding the internal dynamics of these systems. Current evaluation practices rely heavily on final benchmark scores, which obscure the mechanisms driving improvement. It is unclear whether progress stems from discovering novel algorithmic structures, retuning existing strategies, recombining internal model knowledge, or simply overfitting to specific evaluators. The paper posits that without inspecting the search process itself—rather than just the final outcome—it is impossible to distinguish between genuine structural discovery and other forms of optimization.

Methodology

To address this, the authors introduce a comprehensive framework for analyzing evolutionary coding traces, consisting of a dataset and a replay-based analysis tool.

1. EvoTrace: A Structured Dataset

The authors constructed EvoTrace, a dataset comprising 121 evolutionary runs across four distinct frameworks (OpenEvolve, GEPA, EvoX, ShinkaEvolve), five LLMs (including reasoning and non-reasoning models), and 16 tasks (6 Python mathematical constructions and 10 C++ competitive programming problems from ALE-bench Lite).

• Scope: The dataset includes 10,672 unique programs, 18,400 LLM calls, and full parent-child lineage graphs.
• Schema: Unlike standard logs, EvoTrace normalizes runs into a unified JSONL schema containing full source code (byte-identical), prompts, context, evaluator outputs, and execution metadata. This design prioritizes replayability, allowing any point in the search graph to be re-executed against the original evaluator.

2. EvoReplay: Diagnostic Tooling

Built on top of EvoTrace and the SkyDiscover framework, EvoReplay is a methodology and open-source package designed to reconstruct local search states and perform controlled interventions. It enables four key diagnostic capabilities:

• Static Analysis: Normalizing runs to measure program complexity, lineage depth, and budget utilization.
• LLM-as-Judge Annotation: A pipeline that classifies every parent-child code edit into one of nine recurring categories (e.g., Hyperparameter tuning, Architectural change, Bug fix, External dependency) using an LLM judge validated against blind human re-annotation.
• Bayesian Optimization (BO) Baseline: A method to isolate the "tuning gap" by fixing a program's structure and running BO on its exposed numeric constants to determine how much of an evolutionary gain is purely parametric.
• Stability Analysis: Re-running the exact generation prompts for breakthrough events to test reproducibility and measure the distribution of outcomes.

Key Contributions

The paper contributes two primary artifacts and a set of trace-level findings:

1. EvoTrace Dataset: A unified, replayable collection of evolutionary coding traces covering multiple frameworks, models, and domains.
2. EvoReplay Package: A tool for mechanistic analysis, enabling interventions such as same-prompt replay, ablation, and context substitution.
3. Empirical Findings: A characterization of how evolutionary coding agents actually behave, revealing specific inefficiencies and mechanisms.

Key Results

1. The Frequency-Utility Gap in Edits

Analysis of 10,000+ edits reveals a disconnect between what agents search for and what actually improves scores:

• Frequency: Hyperparameter tuning (changing numeric literals) is the most prevalent edit type, dominating the search distribution.
• Utility: The most helpful edits per unit are External dependency (adding libraries), Efficiency (optimizing complexity), and Architectural change (replacing core algorithms).
• Finding: The categories that most frequently improve a single edit are not the categories the search spends the most effort on. Most score gains come from a small, rare subset of edit types.

2. Deterministic Cycling

A significant portion of the search budget is wasted on "churn."

• Observation: Approximately 30% of code lines added during search are byte-identical re-introductions of lines previously deleted in the same lineage.
• Pattern: This cycling rate grows monotonically over the run in 118 of 121 cases. The median span between deletion and re-introduction is only 5 iterations.
• Implication: Agents frequently discard and then re-discover the same code fragments, suggesting a lack of memory or effective novelty filtering.

3. Replay Reproducibility

When re-running the exact prompt that generated a "best-so-far" program:

• Structural vs. Lexical: Replays almost always produce runnable programs (100% parse/eval success) but never reproduce the original program byte-for-byte (0% exact match).
• Score Recovery: Despite generating different code, replays recover a median of 76% of the original score.
• Conclusion: The score gain is a reproducible property of the prompt context and search state, but the specific program structure is just one draw from a wider distribution of valid solutions.

4. The Tuning Gap

The authors investigated how much of the evolutionary gain is structural versus parametric.

• Method: They applied Bayesian optimization to the hyperparameters of intermediate programs from the evolutionary runs.
• Result: On mathematical tasks, a 24-call BO pass on a single intermediate program often matches or exceeds the final-best score of the full 100-iteration evolutionary run.
• Implication: On math benchmarks, late-stage evolutionary iterations often perform parametric refinement that could be achieved post-hoc by tuning a single earlier program, suggesting the structural discovery happens early.

5. Overfitting on ALE Benchmarks

On competitive programming tasks (ALE-bench), public scores are unreliable indicators of generalization.

• Finding: Two of the four frameworks overfit on at least 30% of the problems. In some cases (e.g., problem ahc024), one framework showed a massive public score gain but a massive private score loss, while another showed the opposite.
• Conclusion: Public best-so-far chains are unreliable as single-number summaries for algorithmic engineering tasks.

Significance and Claims

The paper claims that benchmark gains in evolutionary coding agents arise from qualitatively different mechanisms, only some of which correspond to new algorithmic structure. By shifting the focus from final scores to search dynamics, the authors demonstrate that:

• Progress is not uniform: It depends jointly on the task, search procedure, evaluator, and model family.
• Inefficiencies are systemic: Significant search budget is consumed by re-introducing deleted code and by hyperparameter tuning that could be decoupled from structural search.
• Evaluation needs refinement: Current benchmarks may reward overfitting or parametric tuning rather than genuine algorithmic discovery.

The authors conclude that tools like EvoTrace and EvoReplay enable a more diagnostic evaluation, allowing researchers to determine whether a system is discovering new structures, retuning known patterns, or becoming trapped by its own history. They suggest that future system designs should incorporate interventions to prevent re-doing discarded work (e.g., lineage-aware credit assignment) and that benchmark reporting should include tuning ceilings and private-test generalization metrics to provide a complete picture of agent performance.