Interaction-Aware Co-Evolution for Automated Algorithm Design

Large language models (LLMs) enable automated algorithm design (AAD) by generating and refining executable heuristics. In solver–instance co-evolution, heuristics are improved alongside instance generators that expose their weaknesses. However, performance feedback in LLM-based AAD does not directly explain why a solver struggles: a high error may arise from limited overall solver capability, general instance difficulty, or a specific solver–instance interaction. Distinguishing these factors is therefore important for guiding AAD toward targeted improvements. We propose Interaction-Aware Co-Evolution (IACE), an evidence-guided framework for AAD that connects interaction diagnosis with controlled validation and evidence reuse. IACE constructs a solver–instance performance matrix and extracts interaction residuals after accounting for average solver and instance effects. These residuals identify candidate weaknesses and guide hypotheses about the instance conditions under which a heuristic struggles. A bidirectional controlled validation procedure compares parent–child heuristics across paired original and modified instances to assess whether a proposed change addresses the targeted weakness. The resulting records are organized in a structured evidence memory, separating validated findings from unverified hypotheses and unsuccessful attempts. By retrieving relevant evidence for both heuristic modification and instance generation, IACE supports informed search across AAD iterations. Throughout this process, LLM parameters and the solver backbone remain fixed, while a designated heuristic component evolves. Experiments demonstrate state-of-the-art performance on widely recognized combinatorial optimization datasets. IACE brings diagnosis, validation, and evidence reuse into a unified process for AAD.