Behaviour Space Analysis of LLM-driven Meta-heuristic Discovery

Niki van Stein, Haoran Yin, Anna V. Kononova, Thomas Bäck, Gabriela Ochoa

TL;DR

Researchers have begun using Large Language Models (LLMs) to "evolve" brand-new optimization algorithms from scratch. This paper moves beyond just measuring if these AI-designed algorithms work, using "behavior space analysis" to visualize and explain how they search and why specific prompting strategies—like combining code simplification with random perturbations—produce the most effective solvers.

What Problem Does This Paper Address?

Automated Algorithm Design (AAD) has traditionally involved picking and tuning pre-defined components. With the rise of LLMs, we can now generate entirely free-form code for meta-heuristics (algorithms like Genetic Algorithms or Particle Swarm Optimization).

However, we face a "black box" problem: while we can see that an LLM-generated algorithm performs well on a benchmark, we often don't understand its underlying search logic. Traditional tools for analyzing algorithms don't easily translate to a space where the "individuals" being evolved are snippets of Python code. This paper aims to bridge that gap by providing a holistic framework to analyze the structural evolution and dynamic behavior of LLM-driven algorithm discovery.

Methods

The authors utilize the LLaMEA (Large Language Evolutionary Algorithm) framework, where an LLM (in this case, OpenAI’s GPT-4o-mini) acts as the "evolutionary engine."

The core of the study compares six different LLaMEA configurations by varying two main factors:

  1. Mutation Prompts: Instructions given to the LLM, such as "Refine and Simplify," "Generate a new random algorithm," or "Adaptive mutation" (where the LLM is told exactly how much of the code to change).
  2. Search Paradigm: Comparing population-based approaches (keeping a pool of algorithms) versus "1+1 Elitist" strategies (keeping only the single best algorithm and trying to improve it).

To analyze the results, they introduce a multi-faceted toolkit:

  • Behavioral Metrics: Quantitative measures of exploration (how broadly the algorithm searches), exploitation (how intensely it searches near known good solutions), and stagnation.
  • Code Evolution Graphs (CEGs): Visual maps that track how the algorithm's source code changes (length, complexity, and lineage) over generations.
  • Search Trajectory Networks (STNs): Graph-based visualizations that map the "path" an algorithm takes through the abstract space of possible behaviors.

Datasets

The algorithms were evolved and tested using the BBOB (Black-Box Optimization Benchmarking) suite, a standard in the field.

  • Functions: 10 noiseless functions representing various landscapes (unimodal, multimodal, separable, etc.).
  • Dimensions: All problems were set to 5 dimensions (5D).
  • Setup: A "train-test" split was used, where algorithms were evolved on five instances of a function and then validated on ten unseen instances to ensure they weren't just "overfitting" to a specific problem.

Key Insights and Ideas

  • The "Simplify" Secret Sauce: The most successful variant (LLaMEA-4) used a prompt that specifically asked the LLM to "Refine and Simplify." This prevented "code bloat"—the tendency for evolved code to become unnecessarily complex—and often led to cleaner, more generalizable search logic.
  • Exploitation Wins: High-performing algorithms exhibited a distinct behavioral "footprint": they spent more time in intensive exploitation (small, local steps near the best-found solution) and converged faster with less time spent stuck in "stagnation" phases.
  • Elitism vs. Diversity: While population-based methods are standard in biology, the "1+1 Elitist" strategy (hill-climbing in the space of algorithms) was more stable and effective here. This suggests that in the expensive world of LLM calls, protecting the "best-so-far" algorithm is more crucial than maintaining a diverse pool of mediocre ones.
  • Visualizing Logic: The Search Trajectory Networks revealed that successful runs followed a direct, efficient path through behavior space, whereas failing runs often "wandered" or branched out into ineffective, scattered behaviors.

Key Results

  • Top Performer: LLaMEA-4 (which combined "Refine/Simplify" and "Random-new" prompts in a 1+1 elitist strategy) significantly outperformed the other five variants.
  • Performance Metric: Success was measured using AOCC (Area Over the Convergence Curve). LLaMEA-4 achieved the highest AOCC, meaning it found better solutions faster and more consistently across different problem types.
  • Stability: LLaMEA-4 showed the lowest variance between independent runs, suggesting that the combination of exploitation (refining) and exploration (random new ideas) is the most robust way to prompt an LLM for algorithm design.

Limitations and Future Work

The authors acknowledge several constraints:

  • Scale: The study was limited to 5D problems. Performance might shift significantly in high-dimensional spaces (e.g., 100D+).
  • Model Specificity: Only one LLM (GPT-4o-mini) was tested. Different models might have different "coding styles" or responses to the simplification prompts.
  • Sample Size: Due to API costs, only five independent runs were performed per configuration.

Future Directions: The authors propose creating a self-correcting loop. If the behavior analysis detects that an evolving algorithm is stagnating or exploring too much, the system could automatically adjust its own prompts to the LLM to steer the evolution back on track. This would move us closer to truly autonomous, "self-aware" AI scientists.

Summary updated

Abstract

We investigate the behaviour space of meta-heuristic optimisation algorithms automatically generated by Large Language Model driven algorithm discovery methods. Using the Large Language Evolutionary Algorithm (LLaMEA) framework with a GPT o4-mini LLM, we iteratively evolve black-box optimisation heuristics, evaluated on 10 functions from the BBOB benchmark suite. Six LLaMEA variants, featuring different mutation prompt strategies, are compared and analysed. We log dynamic behavioural metrics including exploration, exploitation, convergence and stagnation measures, for each run, and analyse these via visual projections and network-based representations. Our analysis combines behaviour-based projections, Code Evolution Graphs built from static code features, performance convergence curves, and behaviour-based Search Trajectory Networks. The results reveal clear differences in search dynamics and algorithm structures across LLaMEA configurations. Notably, the variant that employs both a code simplification prompt and a random perturbation prompt in a 1+1 elitist evolution strategy, achieved the best performance, with the highest Area Over the Convergence Curve. Behaviour-space visualisations show that higher-performing algorithms exhibit more intensive exploitation behaviour and faster convergence with less stagnation. Our findings demonstrate how behaviour-space analysis can explain why certain LLM-designed heuristics outperform others and how LLM-driven algorithm discovery navigates the open-ended and complex search space of algorithms. These findings provide insights to guide the future design of adaptive LLM-driven algorithm generators.
BibTeX
@misc{stein2025behaviour,
  author = {Niki van Stein and Haoran Yin and Anna V. Kononova and Thomas Bäck and Gabriela Ochoa},
  title = {{Behaviour Space Analysis of LLM-driven Meta-heuristic Discovery}},
  year = {2025},
  eprint = {2507.03605},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.03605},
}
Figure