Search papers, labs, and topics across Lattice.
This paper introduces RAISE, a novel framework that enhances Large Language Model (LLM)-based Automated Heuristic Design (AHD) by incorporating robust adversarial instance search to address performance degradation under distributional shifts. By integrating a constrained worst-case instance search within the evolutionary search loop, RAISE evolves heuristics while efficiently identifying challenging instances near the training distribution. Experimental results show that RAISE outperforms traditional LLM-based AHD methods, which can degrade by up to 19 times, by maintaining robust performance across various problem domains and distribution families.
RAISE keeps LLM-based heuristics resilient, outperforming traditional methods by up to 19 times under real-world distribution shifts.
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 for 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 distribution into the LLM-based evolutionary search loop. RAISE treats robust AHD as a constrained adversarial instance search problem: the outer loop evolves heuristics via LLM operators, while an LLM-free inner loop efficiently identifies hard instances within an epsilon-ball around the training instance set using a basis distribution parameterization with boundary projection. Comprehensive experiments on Online Bin Packing (OBP), Online Job Shop Scheduling (OJSP), and Online Vehicle Routing (OVRP) across five distribution families demonstrate that existing LLM-based AHD methods degrade by up to 19 times under distribution shift, while RAISE consistently maintains strong performance across all tested distributions and problem scales
ETH