In-the-loop Hyper-Parameter Optimization for LLM-Based Automated Design of Heuristics

Niki van Stein, Diederick Vermetten, Thomas BäckarXiv 2024 · DOI · OpenReview

TL;DR

This paper introduces LLaMEA-HPO, a novel framework that combines Large Language Models (LLMs) with Hyper-Parameter Optimization (HPO) to automate the design of heuristic algorithms. By offloading the computationally expensive task of hyper-parameter tuning to an HPO tool like SMAC, LLaMEA-HPO allows LLMs to focus on generating more creative and novel algorithmic structures, significantly reducing LLM query costs and improving overall efficiency.

What Problem Does This Paper Address?

Designing effective heuristic algorithms for complex optimization problems is a challenging and time-consuming task. While Large Language Models (LLMs) have shown promise in automatically generating and optimizing these algorithms, a major bottleneck is their inefficiency in fine-tuning the numerous hyper-parameters of the generated heuristics. This process often requires a vast number of LLM queries, leading to substantial computational and financial costs. Existing LLM-driven approaches tend to spend a disproportionate amount of LLM calls on hyper-parameter tuning rather than on generating fundamentally new algorithmic ideas. This paper aims to address this inefficiency by separating the creative task of algorithm design from the more mechanical task of hyper-parameter optimization.

Methods

The core innovation of this work is the LLaMEA-HPO framework, which builds upon the existing LLaMEA (Large Language Model Evolutionary Algorithm) framework. The key modification is the integration of a dedicated Hyper-Parameter Optimization (HPO) procedure, specifically SMAC3, into the evolutionary loop.

Here's how it works:

  1. Initial Generation: The LLM receives a task prompt and an example algorithm. It then generates a novel algorithm and, crucially, a configuration space (a Python dictionary) defining its hyper-parameters.
  2. Hyper-Parameter Optimization (HPO): Instead of the LLM tuning these parameters, the SMAC3 algorithm takes over. SMAC3 efficiently searches the provided configuration space using a subset of problem instances to find optimal hyper-parameter settings for the generated algorithm.
  3. Evaluation: The algorithm with its optimized hyper-parameters is evaluated on a set of benchmark problems.
  4. Feedback and Mutation: Performance feedback, including any errors, is fed back to the LLM. The LLM then uses this feedback to "mutate" or refine the algorithmic structure of the algorithm, generating a new candidate.
  5. Iteration: This cycle of HPO, evaluation, and LLM-driven mutation repeats until a stopping criterion is met.

This "in-the-loop" HPO approach ensures that LLMs are primarily used for their strengths in code generation and algorithmic innovation, while HPO handles the parameter tuning efficiently.

Datasets

The proposed LLaMEA-HPO framework was evaluated on three benchmark problems:

  • Online Bin Packing: A classic combinatorial optimization problem.
  • Black-Box Continuous Optimization (BBOB Suite): A suite of 24 noiseless benchmark functions designed to test algorithms across diverse optimization landscapes.
  • Traveling Salesperson Problem (TSP): Specifically, TSP instances with 100 locations (TSP100) and larger instances from the TSP-lib archive.

The paper does not introduce new benchmarks but utilizes established ones to demonstrate the effectiveness of the LLaMEA-HPO approach.

Key Insights and Ideas

  • LLMs are better at "what" than "how much": The research strongly suggests that LLMs excel at generating novel algorithmic structures and control flows ("what" the algorithm does) but are less efficient and cost-effective for fine-tuning numerical parameters ("how much" of a parameter to use).
  • Separation of concerns is key: By separating algorithm design (LLM) from hyper-parameter tuning (HPO), the framework achieves significant cost reductions and improved efficiency.
  • HPO significantly reduces LLM queries: The experimental results show a dramatic decrease in the number of LLM prompts required to achieve competitive or superior performance compared to existing LLM-driven methods.
  • LLaMEA-HPO maintains or improves solution quality: Despite reducing LLM usage, the hybrid approach consistently achieves comparable or better performance on the tested benchmarks.
  • LLM-driven optimization often defaults to hyper-parameter tuning: The study observed that a substantial portion of LLM-driven optimization in existing frameworks is dedicated to tuning parameters rather than proposing fundamentally new ideas, highlighting the need for the proposed separation.

Key Results

  • Reduced LLM Queries: LLaMEA-HPO significantly reduces the number of LLM queries needed. For instance, in the BBOB 5D benchmark, it achieved state-of-the-art performance with far fewer LLM queries than the EoH baseline.
  • Competitive/Superior Performance: The framework achieved superior or comparable performance across Online Bin Packing, BBOB, and TSP benchmarks compared to existing LLM-driven frameworks like EoH.
  • Cost-Effectiveness: By using a cheaper LLM (GPT-40) and reducing query counts, LLaMEA-HPO offers a more cost-effective solution for LLM-driven algorithm design.
  • Improved Algorithm Quality: The HPO component demonstrably improved the performance of algorithms generated by the LLM, showing an average AOCC score improvement of around 0.2 in the BBOB 5D experiments.
  • Novel Algorithm Structures: The generated algorithms, particularly for TSP, showcased complex class structures with internal memory mechanisms, which are beyond the capabilities of simpler LLM-based approaches like EoH.

Limitations and Future Work

  • LLM Choice: The paper notes that while GPT-4-Turbo is more expensive, it might offer different performance characteristics. The choice of GPT-40 was driven by cost-effectiveness.
  • Benchmark Representativeness: For TSP, the study observed that training instances might lead to overfitting, and the performance on real-world TSP-lib instances showed less significant differences between some methods.
  • Future Work:
    • Dynamic HPO Adjustment: Exploring ways to dynamically adjust the HPO budget based on the complexity of the generated algorithm.
  • Larger Population Sizes: Investigating the integration of HPO within LLM-driven frameworks that use larger population sizes (e.g., within EoH or LLaMEA with larger populations).
  • Broader Problem Domains: Extending the framework to more diverse problem domains to validate its generalizability.
  • Synergies with Advanced HPO: Exploring additional synergies between LLMs and more advanced HPO techniques.

Summary updated

Abstract

Large Language Models (LLMs) have shown great potential in automatically generating and optimizing (meta)heuristics, making them valuable tools in heuristic optimization tasks. However, LLMs are generally inefficient when it comes to fine-tuning hyper-parameters of the generated algorithms, often requiring excessive queries that lead to high computational and financial costs. This paper presents a novel hybrid approach, LLaMEA-HPO, which integrates the open source LLaMEA (Large Language Model Evolutionary Algorithm) framework with a Hyper-Parameter Optimization (HPO) procedure in the loop. By offloading hyper-parameter tuning to an HPO procedure, the LLaMEA-HPO framework allows the LLM to focus on generating novel algorithmic structures, reducing the number of required LLM queries and improving the overall efficiency of the optimization process. We empirically validate the proposed hybrid framework on benchmark problems, including Online Bin Packing, Black-Box Optimization, and the Traveling Salesperson Problem. Our results demonstrate that LLaMEA-HPO achieves superior or comparable performance compared to existing LLM-driven frameworks while significantly reducing computational costs. This work highlights the importance of separating algorithmic innovation and structural code search from parameter tuning in LLM-driven code optimization and offers a scalable approach to improve the efficiency and effectiveness of LLM-based code generation.
BibTeX
@misc{stein2024loop,
  author = {Niki van Stein and Diederick Vermetten and Thomas Bäck},
  title = {{In-the-loop Hyper-Parameter Optimization for LLM-Based Automated Design of Heuristics}},
  year = {2024},
  eprint = {2410.16309},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.16309},
}
Figure