RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search

Automated Heuristic Design (AHD) with Large Language Models (LLMs) has shown remarkable progress in discovering high-quality heuristics. However, existing LLM-based AHD methods optimize heuristics on a fixed training instance set and may fail catastrophically when deployed under real-world distributional shifts. We propose Robust Adversary Instance Search (RAISE), a framework that integrates constrained worst-case instance search within a principled neighborhood of the training instance set into the LLM-based evolutionary search loop. RAISE consists of two loops: an LLM-free inner loop repeatedly discovers hard instances inside an $\epsilon$-ball around the training instance set using a basis distribution parameterization with boundary projection, and an LLM-driven outer loop evolves heuristics to optimize aggregate performance over the dynamically accumulated hard-instance set. Experiments across four different combinatorial optimization tasks, covering five distribution families, twelve size configurations, and 95 test datasets demonstrate that existing LLM-based AHD methods degrade by up to $19\times$ under distribution shift, while RAISE consistently maintains strong performance across different tested distributions and problem scales.