acceptodds
Under review as a conference paper at ICLR 2027

Interaction-Aware Co-Evolution for Automated Algorithm Design

Abstract

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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Automated Algorithm Design, Large Language Models, Algorithm

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_T5KnOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes IACE, a framework for automated algorithm design that co-evolves solver heuristics and challenging instance generators. It introduces interaction-residual diagnosis, matched controlled validation, and evidence-aware memory to guide targeted heuristic improvements. The authors provide theoretical analyses and evaluate the framework across five combinatorial optimization problems. Experimental results demonstrate promising performance improvements over existing methods.

Critical strengths
  1. Meaningful methodological contribution. The integration of interaction diagnosis, controlled validation, and evidence reuse provides a coherent approach to automated algorithm design.
  2. Solid theoretical and empirical support. The paper provides statistical guarantees, extensive experiments across multiple optimization problems, and ablation studies supporting the proposed framework.
Critical weaknesses
  1. Limited validation of the core mechanism. Although ablation studies show performance improvements, the paper provides insufficient direct evidence of how reliably interaction diagnosis and controlled validation identify genuine condition-specific improvements.
  2. Unclear computational efficiency. The framework introduces additional solver evaluations and validation procedures, but its end-to-end computational overhead relative to competing methods is not sufficiently quantified.
Questions for authors
  1. Can the authors report the success rates of interaction diagnosis and controlled validation, including the proportion of hypotheses accepted or rejected?
  2. How does IACE compare with the strongest baselines under matched total computational budgets, including solver evaluations and LLM calls?
  3. Can the authors provide a concrete example demonstrating how a diagnosed weakness leads to a validated improvement?
Reviewer_Zz7SOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes Interaction-Aware Co-Evolution (IACE) for LLM-based automated heuristic design. The framework maintains populations of heuristic programs and instance generators while keeping the underlying solver backbone and LLM parameters fixed. It applies double centering to a solver–instance performance matrix to identify unexpectedly poor outcomes after removing marginal solver and instance effects. Selected interactions motivate hypotheses, targeted heuristic modifications, and controlled variations of instance generators. Fresh matched evaluations compare parent and child heuristics under original and modified conditions, and the resulting records are stored with different evidential statuses for subsequent search. The paper provides conditional statistical guarantees for evidence promotion and evaluates the framework through TSP benchmarks, multi-domain instance-generation experiments, component ablations, and LLM-backbone comparisons.

Critical strengths

The parent–child comparison under both original and modified instance conditions is a concrete methodological strength. The contrast D = G_v − G_o tests whether a modification helps more under the targeted condition, rather than treating any performance improvement as support for the proposed explanation.

Critical weaknesses
  1. Raw objective values do not establish increased instance hardness. Section 4.1 and Figure 4 infer greater difficulty from higher costs or lower rewards across different instance distributions. These differences may instead reflect changes in the attainable optimum. For example, larger bin-packing items can require more bins even under an optimal solution. Thus, these experiments do not establish the claimed cross-domain increase in solver difficulty without reference-normalized gaps or comparable bounds.
  2. The practical operation of the central validation mechanism is not demonstrated. The evidence-promotion rule depends on the validation sample size, conservative scales, thresholds, and error budget. However, the experimental sections do not sufficiently specify these settings or report an actual validation record containing the observed A, G, D values and their bounds. The theoretical guarantee is conditional on these quantities; final performance tables alone cannot establish that the implemented system obtained and reused statistically supported evidence.
  3. The ablations do not isolate the claimed benefit of interaction-aware co-evolution. Table 1 removes entire modules but does not compare residual-guided repair against raw-gap-guided or random repair under matched budgets. Nor does it compare evolving generators against fixed, diverse generators while retaining diagnosis and validation. Consequently, the reported improvements cannot be specifically attributed to interaction-aware targeting and generator co-evolution, rather than additional evaluations or changes in candidate generation and selection.
Questions for authors
  1. Hardness measurement. Do the cross-domain conclusions in Figure 4 persist when measured using gaps to reliable reference solutions or bounds, rather than raw objectives? Please report the reference quality for both distributions.
  2. Validation in practice. What validation sample sizes, conservative scales, thresholds, and error budget were used? Please provide one complete validation record and the number of hypotheses promoted across runs.
  3. Attribution of improvements. Under matched generation and evaluation budgets, how does IACE compare with raw-gap or random screening, and with fixed diverse generators while retaining controlled validation and memory?
Reviewer_WuiwOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

To address the difficulty of distinguishing overall solver capability, general instance difficulty, and specific solver–instance interactions from performance feedback in Automated Algorithm Design (AAD), this paper proposes Interaction-Aware Co-Evolution (IACE). IACE combines interaction diagnosis, controlled validation, and structured evidence memory to guide the co-evolution of heuristics and instance generators. The paper provides a statistical analysis of evidence promotion and reports solver performance improvements on TSP benchmarks and hard-instance generation results across multiple combinatorial optimization tasks.

Critical strengths
  1. Clear motivation and coherent framework: IACE addresses attribution ambiguity in performance feedback by combining interaction diagnosis, controlled validation, and structured evidence memory to support targeted algorithm improvement.
  2. Statistical grounding: This paper provides error-control and sample-complexity analyses for finite-sample evidence promotion. It also states the assumptions required for these guarantees.
  3. Promising TSP results: IACE reports performance advantages on standard and hard instance distributions and TSPLIB. Ablation studies also provide initial support for its core components.
Critical weaknesses
  1. The benefit of residual-based screening is unclear. Interaction residuals provide a reasonable exploratory signal, but the current experiments do not isolate their benefit over raw-gap screening. Removing the entire RIM also removes hypothesis generation and targeted modification. I think a comparison that retains these steps and changes only the screening criterion would better support this design choice.
  2. Performance retention across evolving conditions is unclear. Controlled validation permits improvement under the target condition while allowing deterioration under the original condition. Subsequent performance-based selection can filter some such changes, but it uses an evolving instance panel. The final benchmark results are encouraging, yet the paper does not show whether later heuristics retain performance on previously encountered conditions.
  3. Key experimental evidence remains incomplete. The paper provides validation procedures and cost formulas, but does not sufficiently report the actual validation configuration, evidence-promotion statistics, or total computational costs. Keeping population sizes and iteration counts fixed also does not establish equal total search budgets across ablations. Moreover, the multi-domain hardness results in the appendix (Sec J.1 and J.4) rely on raw objective values. These comparisons alone cannot distinguish increased optimization difficulty from changes in instance optimal values.
Questions for authors
  1. Could the authors clarify whether residual-based screening is compared against raw-gap screening while keeping hypothesis generation, targeted modification, and the evaluation budget unchanged?
  2. Could the authors report the validation sample sizes, thresholds, error level, and conservative scales used in the experiments, together with the numbers of proposed and promoted hypotheses? How are total search budgets matched across the full method and its ablations?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.