Instance Clustering and Selection: Reducing Evaluation Cost for Automated Algorithm Design in LLM-Assisted Evolutionary Search

Candidate evaluation is a computational bottleneck in LLM-assisted evolutionary search (LES) for automated algorithm design, as each generated algorithm must be evaluated on training instances to provide a search signal to guide the evolution. We identify instance redundancy as a key inefficiency and propose Behavior-based Dynamic Instance Clustering and Selection (B-DICS), a feature-free method that represents instances through their behavioral responses to candidate algorithms. B-DICS progressively uncovers latent instance structure during search by clustering instances in the behavior space and selecting representative core instances for efficient evaluation. We further integrate B-DICS into LES to form a co-evolving framework, B-DICS-LES, where emerging algorithms induce more discriminative behavioral signals that refine the instance structure over time. This closed feedback loop reduces evaluations while preserving the fidelity of search guidance and enabling structure-aware algorithm design. Experiments on three algorithm design tasks show that B-DICS-LES achieves state-of-the-art performance while reducing evaluation cost by an average of 29.8%, paving the way for the scalable deployment of the LES paradigm in real-world automated algorithm design.