LLM Driven Design of Continuous Optimization Problems with Controllable High-level Properties

Technical Summary: LLM Driven Design of Continuous Optimization Problems with Controllable High-level Properties

Problem Statement
Benchmarking in continuous black-box optimization is currently hindered by the limited structural diversity of existing test suites, such as the BBOB (Black-Box Optimization Benchmarking) suite. As noted in prior work, these suites often cover only narrow regions of the problem space, which restricts the generalization of Automated Algorithm Selection (AAS) models and makes evaluation highly dependent on data splits. While previous attempts to generate new problems—such as affine combinations of existing functions or random tree-based generators—have been proposed, they either offer limited novelty or lack the ability to control specific high-level landscape properties. This paper investigates whether Large Language Models (LLMs), embedded within an evolutionary loop, can be used to automatically synthesize optimization problems that exhibit clearly defined, interpretable high-level landscape characteristics.

Methodology
The authors propose a framework extending LLaMEA (Large Language Model–driven Evolutionary Algorithm), originally designed for algorithm generation, to the domain of problem generation. The methodology follows a three-step process:

1. Feature Model Definition:
   The authors target five high-level properties derived from Exploratory Landscape Analysis (ELA): multimodality, separability, basin-size homogeneity, search-space homogeneity, and global–local optima contrast. Machine learning models (specifically XGBoost regressors) are trained on the BBOB dataset to predict these properties based on ELA features extracted from Latin hypercube samples. For separability, a direct numerical test using finite-difference estimates of variable interactions is employed instead of a predictive model.

2. LLM Problem Generation:
   The LLaMEA framework evolves executable Python code representing optimization functions. The LLM (specifically gpt5-nano was selected for its balance of performance and efficiency) receives natural-language prompts describing the target properties.

   • Fitness Evaluation: Generated candidates are scored by the trained property prediction models.
   • Diversity Mechanism: To prevent the population from converging on redundant landscapes, the authors introduce an ELA-space fitness-sharing mechanism. This adjusts an individual's fitness based on its density in the ELA feature space (using z-standardized Manhattan distances), penalizing solutions that are too similar to others and encouraging exploration of diverse geometric structures. An adaptive niche radius ensures robustness across generations.

3. Property Verification:
   Because the predictive models are approximations, a rigorous verification step is applied. This involves a basin-of-attraction analysis (iteratively searching for improving paths to identify local optima and basin sizes) and statistical testing. This step is computationally expensive and is primarily applied to 2D instances to confirm that the generated functions truly exhibit the intended structural traits.

Key Contributions

• First LLM-Driven Problem Synthesis: This work presents the first use case of LLM-driven evolutionary computation for the automatic synthesis of optimization problems with pre-specified high-level properties, moving beyond the generation of solvers to the generation of problem instances.
• Adaptive Fitness Sharing: The paper extends the LLaMEA framework with a novel fitness-sharing mechanism operating in the ELA feature space to promote diversity among generated landscapes.
• Verification Framework: The authors propose and apply a multi-faceted verification approach combining predictive modeling, basin-of-attraction analysis, and visual inspection to validate the structural integrity of generated problems.
• Open Library: The result is a reproducible, interpretable library of benchmark problems with specific high-level properties, made available as a Python library.

Results

• Model Selection: Preliminary experiments compared five LLMs. gpt5-nano achieved the highest success rate (98.7%) for generating problems with specific property combinations (e.g., basin-size homogeneity and separability) and was selected for the main study.
• Diversity: The fitness-sharing mechanism was shown to significantly increase the diversity of generated landscapes. Distributions of nearest-neighbor distances in ELA space shifted toward larger values when fitness sharing was active, confirming that the mechanism successfully steers the generator away from redundant solutions.
• Property Verification: Basin-of-attraction analysis confirmed that many generated functions exhibited the intended traits. For instance, problems optimized for multimodality consistently contained multiple basins of attraction, and those optimized for high global–local contrast showed significant fitness differences between the global optimum and local optima.
• Problem Space Expansion: A t-SNE visualization of the generated problems against the BBOB set demonstrated that the LLM-generated instances expand the existing problem space rather than forming an unrelated cluster. They fill gaps in the feature space, particularly in regions under-represented by standard benchmarks.

Significance and Claims
The paper claims that LLM-driven problem generation is a "promising and flexible direction" for creating interpretable benchmarks. By linking groups of ELA features to qualitative, human-readable descriptions, the approach allows for the generation of diverse and verifiable landscapes without requiring expert knowledge to select numerical feature targets. The resulting library offers a broad set of problems that can benefit landscape analysis and downstream tasks like automated algorithm selection. The authors modestly note that while the approach is effective, future work is needed to structurally compare it with other generators, systematically examine sensitivity to LLM choice, and verify whether these instances improve the generalization of algorithm selectors on unseen problem sets.