🤖 AI

ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search

ImprovEvolve introduces an LLM-guided evolutionary search that evolves specialized initialization, improvement, and perturbation operators to drive a basin-hopping process, successfully discovering new state-of-the-art solutions for hexagon packing, autocorrelation inequalities, and spherical codes while significantly reducing the cognitive load on the language model.

Original authors: Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

Published 2026-06-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a incredibly difficult puzzle, like fitting a specific number of oddly shaped hexagons into a container without them overlapping, or finding the perfect mathematical curve that maximizes a certain value. These are "optimization problems," and they are notoriously hard because the landscape of possible solutions is full of tiny hills and deep valleys (local optima). If you take a wrong step, you might get stuck in a shallow valley and never find the deepest one.

For a long time, researchers tried to teach Artificial Intelligence (specifically Large Language Models, or LLMs) to solve these puzzles by asking the AI to write a single, giant program that does everything at once: it has to figure out where to start, how to move, and when to stop. It's like asking a chef to not only cook a meal but also design the kitchen, invent new utensils, and write the recipe book all in one go. The paper calls this approach "AlphaEvolve." While it works sometimes, it often overwhelms the AI, leading to clumsy or incomplete solutions.

The New Idea: ImprovEvolve

The authors of this paper, Alexey Kravatskiy and colleagues, propose a smarter way called ImprovEvolve. Instead of asking the AI to build the entire "super-optimizer" from scratch, they break the job down into three small, manageable tasks. They ask the AI to write a "toolbox" containing three specific tools:

The Starter (generate_config): A tool that just creates a random, valid starting point for the puzzle.
The Polisher (improve): A tool that takes a messy solution and makes it slightly better, smoothing out the edges.
The Shaker (perturb): A tool that randomly jiggles the solution to see if shaking it loose helps it fall into a deeper, better valley.

The "Basin-Hopping" Dance

Once the AI has built this toolbox, the researchers don't just run it once. They use a classic mathematical strategy called Basin-Hopping. Think of it like a hiker trying to find the lowest point in a foggy mountain range:

Start: The hiker drops a random spot (using the Starter).
Polish: They walk downhill to the nearest valley bottom (using the Polisher).
Shake: They take a big, random leap (using the Shaker) to a new spot, hoping to land in a different, deeper valley.
Repeat: If the new spot is lower, they stay. If not, they might try again. They do this over and over, gradually taking smaller leaps as they get closer to the bottom.

By separating the "thinking" (what the AI does) from the "searching" (the Basin-Hopping loop), the AI only has to focus on being good at one specific thing at a time. This reduces the "cognitive load" on the AI, much like how a human is better at solving a complex problem if they break it into small steps rather than trying to hold the whole thing in their head at once.

The Results: New Records

The paper tests this method on three very tough mathematical challenges:

Hexagon Packing: Imagine trying to pack 11, 12, or even 23 hexagons into the smallest possible hexagonal box. The new method found new world-record packings for several of these numbers, beating previous records set by other AI systems and even human experts.
The Autocorrelation Inequality: This is a complex math problem about finding the perfect shape of a wave. The AI improved the known mathematical limit (the "lower bound") from 0.96102 to 0.96258. This was done by taking a good solution found by a previous AI and using the new "Polisher" tool to refine it further.
Spherical Codes: This involves arranging points on a sphere so they are as far apart as possible (like seeds in a pomegranate). The new method improved the arrangement for the majority of 90 different test cases, finding configurations that were slightly more efficient than anything previously known.

The Human Touch

Interestingly, the paper notes that while the AI did the heavy lifting, a human expert made a few tiny tweaks to the code (like changing a specific setting or switching a mathematical tool) to get the absolute best results. This suggests that the best results come from a partnership: the AI generates the core structure and logic, and the human provides the final "fine-tuning" that the AI might miss.

In Summary

The paper argues that instead of asking an AI to be a "super-genius" that solves a whole problem in one go, we should ask it to be a "specialist" that builds a set of tools. Then, we use those tools in a smart, iterative loop (Basin-Hopping) to explore the solution space. This approach, ImprovEvolve, proved to be more effective, robust, and capable of finding new mathematical records than previous methods that tried to do everything at once.

Technical Summary: ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search

Problem Statement

The paper addresses the challenge of using Large Language Models (LLMs) to solve complex mathematical optimization problems, particularly those with rugged, non-convex, and non-smooth landscapes (e.g., packing problems, functional inequalities, and spherical codes). While prior work like AlphaEvolve successfully evolved monolithic programs to output candidate solutions directly, the authors argue that this approach places an excessive cognitive load on the LLM. The model must simultaneously design an initialization scheme, a search strategy, and termination criteria, often leading to generated programs that rely on off-the-shelf routines (like L-BFGS-B) which fail to handle the specific constraints and non-convexity of the problem effectively. Consequently, LLM-generated solutions often blend mathematical insight with heuristics rather than rigorously solving the optimization task, and they struggle to generalize to unseen problem sizes or improve upon expert-constructed solutions.

Methodology: ImprovEvolve

The authors propose ImprovEvolve, an algorithmic alternative that decomposes the optimization task into specialized subroutines, effectively integrating Basin-Hopping global optimization techniques with LLM-guided evolutionary search.

Core Decomposition

Instead of evolving a single function that outputs a solution, ImprovEvolve evolves a Python class implementing three distinct operators:

generate_config(seed): Initializes a feasible solution from a random seed.
improve(x): Performs local optimization to refine a configuration $x$ , returning a solution $x'$ with fitness at least as good as $x$ .
perturb(x, \sigma): Randomly explores the search space at a specific intensity $\sigma$ .

Validation Scheme (Basin-Hopping)

The evolved class is utilized within a two-stage validation scheme (Algorithm 1) that mimics Monotonic Basin-Hopping ( $T=0$ ):

Stage A (Initialization): Multiple initial configurations are generated and refined via improve. The best result is selected as the starting point $x^*$ .
Stage B (Iterative Search): The algorithm performs $R$ $R$ rounds of perturbation and improvement. In each round, the perturbation intensity $\sigma$ $σ$ decays geometrically from $\sigma_{max}$ $σ_{ma x}$ to $\sigma_{min}$ $σ_{min}$ . The process involves:
1. Perturbing the current best solution: $x' = \text{perturb}(x^*, \sigma)$ .
2. Refining the perturbed solution: $x'' = \text{improve}(x')$ .
3. Monotonic Acceptance: $x^*$ is updated to $x''$ only if the fitness strictly improves.

This decomposition shifts the LLM's task from designing an end-to-end optimizer to encoding domain-specific heuristics for initialization, local search, and exploration, which are then orchestrated by the classical Basin-Hopping framework.

Evolutionary Framework

The system utilizes the GigaEvo framework with a MAP-Elites loop. The fitness of a candidate program is determined by running the full two-stage validation scheme on it. The LLM (Gemini 3 Pro for initialization, Gemini 3 Flash for evolution) mutates the code of the Improv class, guided by fitness feedback and lineage insights.

Key Contributions and Results

1. Hexagon Packing (HEX $n$ )

Task: Packing $n$ unit regular hexagons into the smallest enclosing regular hexagon.
Results:
- For $n=11$ , ImprovEvolve discovered a new state-of-the-art (SOTA) packing with side length $L=3.9245$ , improving upon AlphaEvolve's $3.9301$ and the previous human record of $3.9434$.
- The evolved program generalized to unseen problem sizes ( $11 \le n \le 24$ ) without re-evolution, finding new SOTA packings for $n=12, 15, 16$ .
- ImprovEvolve+E: With minor human edits (switching optimizers, adjusting penalty weights), the system found new SOTA packings for $n=14, 17, 23$ and provided structured packings for $n=25-30$ where no prior results existed.
Comparison: ImprovEvolve significantly outperformed the GigaEvo baseline (monolithic approach), which failed to generalize to $n > 11$ due to overlap errors.

2. Second Autocorrelation Inequality (ACI 2)

Task: Finding a non-negative function $f$ that maximizes the constant $C_2$ in the inequality $\|f * f\|_2^2 \le C_2 \|f * f\|_1 \|f * f\|_\infty$ .
Results:
- The base ImprovEvolve program achieved $C(f) = 0.9512$ , surpassing open-source baselines but falling short of AlphaEvolve's $0.96102$.
- ImprovEvolve+E: By resuming optimization from AlphaEvolve's solution and applying human-guided edits (progressive resolution scaling up to 1.6M steps, removing lower clipping), the system achieved a new SOTA lower bound of $C(f) = 0.96258$ .
Significance: This demonstrates the framework's ability to refine existing high-quality solutions provided by experts or other models, a capability monolithic LLM approaches struggle with.

3. Spherical Codes

Task: Arranging $N$ points on a unit sphere $S^{d-1}$ to minimize the maximum pairwise inner product (coherence).
Results:
- Evaluated on 90 diverse configurations from the Cohn catalogue ( $d \in [8, 16]$ ).
- ImprovEvolve++ (a calibrated general improver evolved across multiple dimensions) strictly lowered the maximum cosine for 53 of the 90 configurations, achieving a mean relative improvement of 0.1765%.
- This represents a 2.35 $\times$ improvement over the best prior program (ImprovEvolve).
- Diagnostics (UMAP and inner-product distributions) showed that ImprovEvolve++ performed global structural rearrangements, moving points into distinct regions of the search space, whereas other variants only made local adjustments.

Statistical Robustness

Multi-run studies confirmed that ImprovEvolve's improvements are statistically significant ( $p < 0.05$ ) compared to the GigaEvo baseline, validating that the modular decomposition offers a reproducible advantage over learning a monolithic optimizer.

Significance and Claims

The paper claims that decomposing optimization tasks into modular subproblems is a critical principle for LLM-guided discovery.

Reduced Cognitive Load: By separating initialization, local improvement, and perturbation, the LLM focuses on encoding mathematical structure and heuristics rather than orchestrating the entire search process.
Human-LLM Collaboration: The modular interface allows domain experts to apply targeted, minimal edits (e.g., changing optimizers, adjusting resolution schedules) to significantly boost performance, bridging the gap between LLM-generated code and expert-level tuning.
Generalization: The improve/perturb interface enables evolved programs to generalize to unseen problem sizes and to resume optimization from expert-provided solutions, overcoming the brittleness of monolithic end-to-end programs.

The authors position this work as a step toward scaling LLM-powered mathematical discovery, suggesting that future systems should combine such tailored decompositions with agentic workflows that autonomously decide which modules to refine. The paper remains modest regarding broader generalizability, noting that quantitative evaluation is currently limited to these three specific optimization domains.