ReAL-AHD: Planning over Relational Algorithm Landscape for LLM-based Automatic Heuristic Design

Large Language Models (LLMs) have enabled a new paradigm of Automatic Heuristic Design (AHD), in which heuristics for combinatorial optimization problems (COPs) are generated as executable programs and improved through performance feedback. Existing methods either compress the search history into an elite population, discarding the relations produced along the way, or impose a single structure that captures only one view of the algorithm space. Moreover, they underutilize this history, neither adaptively allocating evaluations across families of similar algorithms nor jointly selecting parents and operators. We propose ReAL-AHD, which represents the discovered algorithm space as a Relational Algorithm Landscape with two complementary relations: a derivation graph that records lineages and supports credit assignment, and a similarity graph that groups heuristics into dynamic algorithm families based on PreferSim, which compares action preferences under aligned decision states. On this landscape, hierarchical graph planning turns accumulated history into the explicit basis for search decisions: family planning allocates the evaluation budget across families, node–operator planning jointly selects the parent node and the operator of each expansion, and graph-aware memory reuses relevant past outcomes. Across five COPs and three heuristic paradigms, ReAL-AHD consistently outperforms state-of-the-art LLM-based AHD methods and converts the evaluation budget into improvement efficiently.