DyCA Improves LLM-Assisted Algorithm Design Robustness.

This paper introduces Dynamic Instance Clustering and Specialized Algorithm Design (DyCA), a novel framework for Large Language Model-assisted Evolutionary Search (LES). Existing LES methods typically focus on optimizing for average performance, which often leads to algorithms that perform well on common instances but struggle with outliers or less frequent problem types, resulting in poor tail robustness and limited real-world reliability. DyCA addresses this by treating instance clustering as an integral, co-evolving component of the search process. It reuses accumulated evaluation data as feature-free signals to progressively partition problem instances into clusters based on similar algorithmic response patterns. This dynamic clustering decomposes the mixed objective into a set of structure-aware sub-objectives. This finer-grained approach enables more adaptive guidance for designing specialized algorithms tailored to each cluster. Experimental results across four diverse algorithm design tasks demonstrate that DyCA significantly outperforms state-of-the-art LES baselines, improving tail robustness by an average of 15.2% and overall performance by 7.1%, while maintaining competitive performance on average.