Skip to content

SeaEvo: Advancing Algorithm Discovery with Strategy Space Evolution

🕒 Published (v1): 2026-04-27 12:06 UTC · Source: Arxiv · link

Why this paper was selected

Strategy space evolution improves LLM-guided algorithm discovery beyond scalar fitness

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

SeaEvo adds a modular strategy-space layer on top of existing LLM-driven evolutionary search frameworks, making natural-language strategic reasoning a persistent, population-level archive state rather than transient prompt context. Three coordinated modules—Strategy Articulation, Stratified Experience Retrieval, and Strategic Landscape Navigation—enable the system to cluster algorithmic strategies semantically, retrieve behaviorally complementary inspirations, and detect strategy-family saturation. Without altering the underlying evolutionary backbone, SeaEvo achieves a 20.6% average relative improvement across four systems optimization benchmarks.

Problem

LLM-guided evolutionary program search archives track state only as executable programs and scalar fitness scores. This causes three failure modes: (1) syntactically distinct programs implementing the same idea appear as genuine search progress; (2) fitness-based selection discards strategically promising but low-scoring candidates; (3) per-program fitness cannot detect when an entire strategy family has saturated. Natural-language signals used in prior work (heuristic descriptions, reflection) remain transient mutation context rather than persistent population-level state.

Method

SeaEvo augments each archive entry \((P_i, s_i)\) with a natural-language strategy description \(d_i\) and embedding \(e_i\), yielding a dual-space archive over both programs and semantic strategies. Three modules replace the base framework's context-builder while leaving selection and evaluation unchanged:

  • Strategy Articulation (SA): A single LLM prompt in diagnose–direct–implement format: given a parent program, retrieved inspirations, and optional landscape guidance, the model (i) diagnoses parent failure modes, (ii) proposes a concise strategy description \(d'\), then (iii) implements a new program \(P'\). Both \(P'\) and \(d'\) are persisted in the archive.

  • Stratified Experience Retrieval (SER): Partitions the archive via k-means over strategy embeddings into \(C\) clusters. For retrieval, it selects one intra-cluster inspiration and one cross-cluster inspiration by greedily maximizing marginal Complementary Coverage (ComCov)—the fraction of validation instances \(P_\text{ref}\) fails that \(P_i\) solves: $\(\text{ComCov}(P_i; P_\text{ref}) = \frac{1}{|V|}\sum_{k=1}^{|V|} \mathbf{1}\!\left[b^k_\text{ref}=0 \wedge b^k_i=1\right]\)$ Only strategy descriptions and fitness scores (not source code) are passed as inspiration, reducing prompt size by 1–2 orders of magnitude.

  • Strategic Landscape Navigation (SLN): Every \(\Delta\) generations, an LLM summarizes all archive strategy descriptions and fitness trends into structured guidance: effective directions, saturated directions, underexplored directions, and actionable mutation suggestions. This guidance \(L_t\) persists in the SA prompt until the next SLN update.

An \(\varepsilon\)-greedy scheme (default \(\varepsilon=0.2\)) bypasses all three modules with probability \(\varepsilon\) to preserve unguided exploration.

Key Contributions

  • Identifies the strategy-representation gap: existing LLM-evolutionary archives lack population-level semantic structure over strategic directions.
  • Introduces SeaEvo, a drop-in modular layer compatible with arbitrary LLM-driven evolutionary backbones (demonstrated on OpenEvolve, ShinkaEvolve, GEPA, AdaEvolve).
  • ComCov metric for behaviorally complementary retrieval across strategy clusters, with graceful scalar-only fallback.
  • Empirical demonstration that strategy-space guidance improves both solution quality and cost-efficiency (fewer API calls to reach the same fitness).

Results

  • Systems optimization (ADRS benchmark, 4 tasks, Gemini-3-Flash): SeaEvo\(_\text{SHINKA}\) achieves 32.1% average relative improvement in mean fitness over ShinkaEvolve; best single run on Prism scores ~3Ă— higher (78.00 vs. 26.54 best).
  • Overall systems average: 20.6% average relative improvement across four ADRS tasks.
  • Mathematical optimization (4 tasks): Gains are moderate; e.g., +4.3% on Circle Packing (Square) Avg with MiMo-V2-Pro; narrower solution spaces yield smaller gains.
  • Convergence: SeaEvo\(_\text{OPEN}\) crosses 2.6 on Circle Packing (Square) within 30 generations; OpenEvolve plateaus near 2.47 after 100 generations, while API cost grows slower for SeaEvo.
  • Ablation (Circle Packing Square, Gemini-3-Flash): Full SeaEvo (SA+SER+SLN) Avg = 2.6297, Std = 0.0077 (order-of-magnitude variance reduction vs. any two-module variant); SLN alone provides the strongest standalone average-fitness lift; SA+SER without SLN underperforms either module alone in average fitness.
  • Hyperparameter sensitivity: \(\Delta=10\), \(C=5\), \(\varepsilon=0.2\) are the best-performing defaults; results are relatively robust across the tested ranges.

Limitations

  • Gains diminish on constrained-solution-space tasks (e.g., LLM-SQL), where fitness-only baselines are already near-optimal.
  • High variance on Prism (Std = 29.78 for SeaEvo\(_\text{SHINKA}\)) suggests strategy-space navigation can occasionally amplify lucky exploration rather than reliably guide it.
  • Strategy embeddings (text-embedding-3-small) and SLN LLM calls add API overhead; the \(\varepsilon\)-greedy bypass partially mitigates this but the cost is not fully ablated.
  • The ComCov score requires instance-level binary success vectors; it degrades to fitness-based ranking in scalar-only settings (e.g., geometric tasks), limiting complementarity benefits there.
  • Experiments run for only \(T=100\) generations with 3 seeds; longer runs or more seeds could change the variance picture.

Relevance to Harnesses / Meta-Harnesses

SeaEvo is a textbook meta-harness: it wraps existing evolutionary algorithm-discovery frameworks (OpenEvolve, ShinkaEvolve, GEPA, AdaEvolve) as black-box backends and augments their orchestration layer with persistent semantic state—exactly the harness-of-harnesses pattern. The three-module architecture (SA, SER, SLN) operationalizes a strategy memory that survives across generations and feeds back into the mutation pipeline, showing how a meta-harness can improve efficiency and diversity without touching the inner loop. For researchers tracking harness design, the key insight is that the context-builder—the interface between the harness and the backbone—is the high-leverage intervention point, and enriching it with structured semantic population state (rather than flat code archives) is a transferable design principle.