RAISE: LLM-based Automated Heuristic Design with Ro... | AI Research

RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search
Automated Heuristic Design (AHD) uses Large Language Models (LLMs) to create high-quality algorithms for complex optimization tasks. While these models excel at solving problems they have seen during training, they often fail when faced with real-world "distributional shifts"—situations where the data encountered in deployment differs from the data used during training. The RAISE framework addresses this by integrating an adversarial search process into the LLM’s design loop, ensuring that the resulting heuristics are not just optimized for a single set of examples, but are robust enough to handle a wide range of unpredictable conditions.

A New Approach to Robustness

RAISE treats the design of a heuristic as a "minimax" problem. In this setup, the LLM acts as the designer, trying to create the best possible heuristic, while an adversarial process acts as an opponent, constantly searching for the most difficult instances within a specific range of the training data. By repeatedly exposing the LLM to these "worst-case" scenarios, the framework forces the heuristic to adapt and improve its performance against challenging, shifted distributions, rather than simply memorizing the patterns of a static training set.

How the Framework Works

The RAISE framework operates through two distinct, coupled loops:

• The Outer Loop: This is the LLM-based evolutionary search. It maintains a population of candidate heuristics and uses the LLM to generate, refine, and evolve them based on their performance.

• The Inner Loop: This is an LLM-free mechanism that runs periodically to find the "hardest" instances for the current best heuristic. It uses a basis distribution parameterization to explore potential problem variations. By projecting these variations onto an "epsilon-ball"—a defined boundary of similarity around the original training data—the system ensures that the adversarial instances remain realistic and relevant to the problem domain.

Key Findings and Performance

Experiments across three major optimization tasks—Online Bin Packing, Online Job Shop Scheduling, and Online Vehicle Routing—demonstrate that existing LLM-based AHD methods can suffer from significant performance degradation when faced with distribution shifts. In some cases, these methods performed up to 19 times worse than they did on their training data.
In contrast, RAISE consistently maintained strong performance across all tested distributions and problem scales. It outperformed existing methods without requiring the large, diverse training datasets that other robustness-focused approaches rely on. This suggests that by actively searching for weaknesses during the design phase, the framework can produce more reliable and adaptable algorithms for real-world deployment.

Important Considerations

While RAISE provides a significant leap in robustness, it is important to note that the framework uses an instance-level approximation of distributionally robust optimization. It is designed as an engineering solution to improve performance under uncertainty rather than a formal, theoretical guarantee for all possible distribution shifts. Additionally, the framework relies on a chosen robustness radius (epsilon) to balance the trade-off between high performance on known data and resilience against unknown, shifted data.