- Rating
- 3
- Confidence
- 3(−1)
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
MOSAIC is an LLM-driven automated heuristic design (AHD) framework for multi-objective combinatorial optimization (MCOP). A heuristic is represented as an ordered, variable-length sequence of executable "search modules", each implementing one search behavior. MOSAIC jointly evolves both the module behaviors (via LLM module rewriting: Behavioral Rewriting and Adaptive Refinement) and their organization (composition, order, and length, via architecture crossover plus structural mutation), with NSGA-II/MOEA/D survival selection over two HV-based objectives (mean and worst-case performance across instance types). Candidates are always evaluated as complete heuristics. The framework is evaluated on three bi-objective problems (Bi-TSP, Bi-KP, Bi-GVRP) plus a three-objective MOFJSP in the appendix, against multi-operator (E2OC, G-LNS) and single-operator (EoH, FunSearch, ReEvo, MCTS-AHD) baselines, with Wilcoxon + Holm significance tests, ablations, LLM-usage accounting, and cross-scale generalization tests.
Critical strengths
- Making operator organization (composition, order, length) an explicit, jointly-evolved design dimension is a well-motivated step over E2OC's fixed slots and G-LNS's fixed Destroy–Repair structure, and the permutation analysis of the four-module architecture provides concrete evidence of order-dependent synergy rather than a bare claim.
- The evaluation is unusually rigorous for this field: Wilcoxon + Holm significance tests, a matched evaluation budget, explicit LLM-usage accounting (Table 6) showing the gains are not bought with more tokens, ablations isolating the two rewriting modes and architecture variation, and released code.
Critical weaknesses
- The domain where the largest advantage is claimed, Bi-GVRP, is the one where statistical significance is absent (0/2 size groups vs all four single-operator baselines, 1/1 vs multi-operator). The "substantially outperforms" language is therefore stronger than the evidence supports where it matters most, and only three of five Bi-TSP size groups are testable because two contain a single instance.
- The contribution is an incremental assembly of established ingredients (LLM code generation, NEAT-style evolutionary architecture search, MOEA). The paper itself flags the semantic-drift and scalability limits, and the evaluation covers only three synthetic benchmark MCOPs (one more in the appendix), so the breadth of the "MCOP" claim is not yet established.
Questions for authors
- How is the reference Pareto front constructed for each instance, and does it include solutions produced by MOSAIC or any baseline? This determines whether the HV-gap and IGD metrics are fair and achievable.
- On Bi-GVRP, MOSAIC shows its largest HV-gap advantage (16.7% vs ~33% at the 100–199 scale) yet Table 3 reports no significant win against any single-operator baseline (0/2). Why is that margin not significant there, and is "substantially outperforms" the right characterization?
- MOSAIC's initial architectures already far outrank E2OC's initial designs on Bi-KP (49.9% vs 95.4% gap). How much of the final advantage is attributable to module-pool initialization versus the joint evolution, beyond what the Fixed-Arch ablation isolates?
- G-LNS's initial Destroy–Repair design scores 0.00 HV (99.7–100.0% gap) on all three Bi-KP test scales, so its "substantial improvement on Bi-KP" is recovery from a non-functional initialization. Is that initial configuration correct, and does the multi-operator comparison remain meaningful given this?
- What explains MOSAIC's advantage over E2OC? The paper reports the result but offers little analysis of the cause; please add a short discussion after the experiments.
9 comments
Response (2/7)
W2: Concerns about methodological contribution, limitations, and generality. The contribution is an incremental assembly of established ingredients (LLM code generation, NEAT-style evolutionary architecture search, MOEA). The paper itself flags the semantic-drift and scalability limits, and the evaluation covers only three synthetic benchmark MCOPs (one more in the appendix), so the breadth of the "MCOP" claim is not yet established.
Thank you for examining the methodological contribution and scope of applicability. We respond in terms of the core contribution, the limitations already discussed in the paper, and supplementary evidence across more diverse optimization settings.
-
Core contribution. Our motivation is to move beyond predefined operator organizations by incorporating module composition, execution order, and architecture length into automated search and optimizing them jointly with module behaviors. This enables the discovery of operator synergies while reducing reliance on manual configuration. Crossover, mutation, and MOEAs serve as the underlying tools; MOSAIC’s methodological contribution lies in the joint design of module behaviors and architecture organization. The motivation and core mechanisms are detailed in our response to Reviewer bDsc’s W1. MOSAIC’s architecture evolution mechanism offers advantages in exploring operator synergies, runtime efficiency, and token consumption. The runtime comparisons are detailed in our response to Reviewer bDsc’s W2, and the token consumption analysis is provided in our response to Reviewer bDsc’s Q2.
-
Semantic drift and scalability. Sections 4.2 and 4.3 and Appendix D.6 discuss these limitations and directions for improvement.
-
Semantic drift. Current LLM-based automated heuristic design methods commonly face this risk: natural-language prompts cannot strictly constrain the behavior of generated code, and executability and valid outputs do not guarantee faithful implementation of the intended design. By directly reorganizing existing modules, MOSAIC allows part of the search to proceed without regenerating code, reducing the number of generation steps that may introduce semantic drift. Future work will incorporate semantic consistency checks for intended search behaviors and investigate architecture search over verified module pools.
-
Scalability. MOSAIC allows the search space to be adjusted through the module pool size and maximum architecture length, while reusing existing code to explore different module combinations. In Section 4.2, the fixed-module-pool experiment with module rewriting disabled shows that performance generally improves as the pool grows from 200 to 1,000 modules, but declines at 2,000. Appendix D.5 likewise shows that increasing the architecture length upper bound does not consistently yield improvements. These results indicate that larger search spaces require more effective use of a limited evaluation budget. Future work will investigate module selection, redundancy control, and more efficient architecture search to better exploit larger search spaces.
-
-
Supplementary evidence of broader applicability. To further assess the framework’s applicability, we add experiments on MONRP, MOSCP, three-objective MOQAP, and five-objective PPP. Together with Bi-TSP, Bi-KP, and Bi-GVRP in the main text and three-objective MOFJSP in the appendix, the evaluation now covers eight classes of combinatorial optimization problems.
Under the same evaluation budget, MOSAIC achieves higher mean HV than all six baselines in all 13 test-scale groups of the additional problems, providing further evidence of its applicability across different problem types, numbers of objectives, and test scales. The complete data sources, experimental settings, and results are provided in our response to Reviewer bDsc’s W3.
In summary, MOSAIC jointly searches module behaviors and architecture organization to discover operator synergies, while using module reuse to reduce reliance on LLM code generation. The paper explicitly discusses the limitations of semantic drift and architecture-search scalability, together with directions for improvement. The supplementary experiments extend the evaluation to eight classes of combinatorial optimization problems; MOSAIC achieves the highest mean HV in all 13 additional test-scale groups, providing further support for its applicability to broader MCOP settings.
Response (3/7)
Q1: Concerns about reference Pareto front construction. How is the reference Pareto front constructed for each instance, and does it include solutions produced by MOSAIC or any baseline? This determines whether the HV-gap and IGD metrics are fair and achievable.
Thank you for highlighting the need to clarify how the reference fronts are constructed. Public reference sets are available for Bi-TSP, Bi-KP, and Bi-GVRP, which we use to compute HV-gap and IGD. For the other problems, we report only HV. The following clarification concerns these three problems.
-
Construction of the reference front for each instance.
- Bi-TSP: We select the corresponding public results from the Paquete benchmark page. For euclid, random, and mixed instances, we use the files labeled “best non-dominated set found.” For kro instances, we use specified PD-TPLS results. For example,
kroAB100uses the result corresponding to 2,000 scalarizations and the3.first.ilsconfiguration. - Bi-KP: We use the
non dominated points/*.maxfiles accompanying the Xavier instances. We verify solution feasibility and objective values, remove invalid, duplicate, and dominated points, and use the remaining objective vectors as the reference set. - Bi-GVRP: We use
Approximate_Pareto_Frontsfrom the publicly available supplementary materials, remove invalid, duplicate, and dominated points, and use the remaining objective vectors as the reference set.
The reference files for all test instances are provided in the
test_sets/directory at this anonymous code link. - Bi-TSP: We select the corresponding public results from the Paquete benchmark page. For euclid, random, and mixed instances, we use the files labeled “best non-dominated set found.” For kro instances, we use specified PD-TPLS results. For example,
-
Whether solutions generated by MOSAIC or the baselines are included. No. The reference sets do not include solutions generated by MOSAIC or any baseline in our experiments.
-
Fairness and attainability of HV-gap and IGD. For each instance, all methods use the same reference set, normalization bounds, and HV reference point, ensuring consistent comparisons. Every objective vector in the reference set corresponds to a feasible solution satisfying that instance’s constraints. Thus, the HV-gap and IGD comparisons are fair, and their reference targets are attainable.
Response (1/7)
W1: Concerns about statistical evidence and performance claims. The domain where the largest advantage is claimed, Bi-GVRP, is the one where statistical significance is absent (0/2 size groups vs all four single-operator baselines, 1/1 vs multi-operator). The "substantially outperforms" language is therefore stronger than the evidence supports where it matters most, and only three of five Bi-TSP size groups are testable because two contain a single instance.
Thank you for highlighting the gap between the performance claims and the statistical evidence. We agree that mean performance improvements should be distinguished from statistical significance, and that the scope of the statistical conclusions should be explicit. We respond as follows.
Statistical evidence on Bi-GVRP. Table 3 shows that MOSAIC’s differences from the four single-operator design methods are not statistically significant in either Bi-GVRP size group. Against E2OC and G-LNS, the differences are significant in one of the two groups for each method. Although Tables 1 and 2 report higher mean HV and lower mean IGD for MOSAIC, these mean differences do not establish statistically significant superiority over all baselines on Bi-GVRP.
Revised performance descriptions. We have revised the phrases “substantially outperforms” and “the largest advantage” concerning Bi-GVRP in the “Comparison with LLM-driven Single-Operator Design Methods” paragraph of Section 3.2, explicitly limiting these descriptions to differences in mean performance.
Statistical testing and its scope. The “Statistical Significance Analysis” paragraph in Section 3.2 and Appendix C.5 already specify that we pair MOSAIC’s performance with each baseline’s performance on the same test instance, after averaging over five runs, and apply two-sided Wilcoxon signed-rank tests with Holm correction. Among the five Bi-TSP size groups, the 150- and 200-city groups each contain only one instance and therefore provide only one paired difference, which is insufficient for an instance-level significance assessment. These two groups were already excluded from statistical testing, with their p-values marked as “–” in Appendix Table 15. The statistical significance conclusions concern only the 100-, 300-, and 500-city groups.
In summary, we have revised the Bi-GVRP descriptions to distinguish mean performance differences from statistical significance. For Bi-TSP, Section 3.2 and Appendix C.5 already state the exclusion of single-instance groups, and the significance conclusions have consistently concerned the remaining three groups.