[UC Berkeley] EvoX: Scaling Automated Discovery via Meta-Evolution of Search Strategies

TL;DR

Current AI-driven discovery tools often get stuck because they use a "one-size-fits-all" search strategy. EvoX changes the game by evolving the search algorithm itself alongside the solutions. Across 200 real-world tasks, it proved that an adaptive search strategy can break through plateaus where static SOTA methods like AlphaEvolve stall.

• The Hook: Instead of just using an LLM to "propose a better program," EvoX uses the LLM to "propose a better way to look for programs."
• Performance: Median score boosts of up to 63% on diverse algorithmic challenges.

1. The Stagnation Problem: Why Fixed Search Fails

In evolutionary computation, the "Search Strategy" dictates how we select parents from a population and how we mutate them (Exploration vs. Exploitation).

Most current systems (AlphaEvolve, OpenEvolve) use static knobs. For example, they might always spend 20% of their time on "Refinement" and 80% on "Diversity." However, the authors argue that the search landscape is non-stationary:

1. Across Tasks: A strategy that solves Circle Packing (geometric) might be useless for GPU Scheduling (combinatorial).
2. Across Time: Early search needs "structural variation" to find a rough design; late-stage search needs "local refinement" to polish it.

The result of fixed strategies? Stagnation. The red line in Figure 1(b) below shows a typical MAP-Elites strategy hitting a ceiling, while EvoX (blue) adapts and finds a breakthrough.

Figure 1: EvoX detects plateauing progress and evolves its search behavior to trigger new performance jumps.

2. Methodology: The Two-Level Loop

EvoX formalizes discovery as a nested optimization problem.

Phase I: Solution Evolution

This is the "inner loop" where the LLM (e.g., GPT-5) acts as the biological mutation engine. It takes a parent program and a variation operator (like REFINE or DIVERGE) to create the next candidate.

Phase II: Meta-Evolution (The Secret Sauce)

EvoX maintains a Strategy Database. It tracks:

• Strategy Code: The logic used to sample parents (e.g., Random, Greedy, UCB-based).
• Population State: A descriptor of the current solutions (diversity, score distribution).
• Effectiveness (J): How much progress the strategy actually made.

When progress stalls (below a threshold $au$), the Strategy Generator (a meta-LLM) analyzes the history and writes a new piece of code defining the next search strategy.

Equation: The performance score J rewards strategies that make progress when the starting score is already high (log-weighting).

3. Case Study: A Paradigm Shift in Circle Packing

Perhaps the most impressive result is how EvoX doesn't just tune numbers—it discovers new math.

In the Circle Packing task, early strategies used simple local heuristics (nudging circles around). When that reached its limit, EvoX evolved a strategy that emphasized structural variation. This forced the LLM to rethink the entire approach, leading to a breakthrough where it implemented a constrained SLSQP (Sequential Least Squares Programming) optimizer.

By switching from "heuristics" to "gradient-based optimization," the system achieved near-perfect density scores that static baselines could never reach.

4. Key Results & SOTA Comparison

EvoX was tested on 196 tasks. In the Frontier-CS (172 complex algorithms), the results were definitive:

Figure: Comparison across 172 Frontier-CS tasks shows EvoX (blue) dominating the distribution.

Systems Optimization: In tasks like GPU Placement (PRISM) and Cloud Data Transfer, EvoX surpassed human-best solutions by wide margins (e.g., 30.52 vs human 21.89 in PRISM).

5. Critical Analysis & Takeaways

The Cost of Evolution

A valid concern with meta-evolution is LLM cost. However, the authors show that EvoX is actually more cost-efficient. Because it adapts to find breakthroughs faster, it often reaches a target score using less total compute than a static strategy that circles the drain for hundreds of iterations.

Limitations

• Stagnation Recovery: If the initial population is extremely poor, the meta-strategy might not have enough signal to evolve meaningful improvements.
• LLM Benchmarking: The results are highly dependent on the "backbone" model. Using GPT-5 or Gemini 3.0 Pro is essential for the high-level reasoning required in the meta-loop.

Conclusion

EvoX proves that Search is a dynamic skill. By allowing the AI to observe its own failures and rewrite its search logic, we move closer to truly autonomous discovery systems that can solve "open-ended" problems in science and engineering.