acceptodds
Under review as a conference paper at ICLR 2027

MO-EoH: Multi-Objectivization Evolution of Heuristics with Large Language Models

Abstract

In recent years, Automated Heuristic Design (AHD) based on Large Language Models (LLMs) has achieved significant success. However, existing single-objective optimization methods use only the optimal performance on the target problem as the sole guidance signal during evolution, making it difficult to accurately assess heuristic performance and causing the search to become trapped in local optima. To address this issue, we introduce helper objectives into the original heuristic design objective, transforming the Single-Objective Optimization Problem (SOP) into a Multi-Objective Optimization Problem (MOP), while maintaining the ultimate goal of discovering better solutions to the original SOP. We refer to this process as multi-objectivization. Building on this idea, we propose Multi-Objectivization Evolution of Heuristics (MO-EoH), the first framework to introduce multi-objectivization into LLM-based AHD. Furthermore, we design a Lexicographic-Pareto mechanism that prioritizes the original heuristic design objective, thereby improving search efficiency. Experiments across eight classical planning benchmark domains demonstrate that MO-EoH consistently outperforms existing state-of-the-art LLM-based methods, achieving an average improvement of 24.5% on the original objective.

Primary area:
optimization
Keywords:
Large Language Models, Automated Algorithm Design, Multi-Objectivization

Reviews

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

The paper proposes MO-EoH, an LLM-based method for automatically designing heuristics. It adds search time and expanded nodes as helper objectives, and prioritizes the number of solved tasks. Experiments show that MO-EoH outperforms several existing LLM-based methods.

Critical strengths
  1. The idea is simple and practical.
  2. The method shows improvements over several LLM-based baselines.
Critical weaknesses
  1. All figures are missing. It is very difficult to believe the authors proofread their paper before submission.
  2. The experiments lack a control without helper objectives. It is unclear whether the improvement comes from multi-objectivization or other changes in the method.
Questions for authors
  1. Can you provide the missing figures and complete prompts, especially the helper-objective results?
  2. How does MO-EoH perform without helper objectives while keeping all other components unchanged?
  3. Were all baselines given the same LLM budget and final heuristic selection rule?
  4. Please provide the code and data for review.
Reviewer_FK5gOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper tackles a limitation of LLM-based Automated Heuristic Design (AHD): retaining individuals solely according to their performance on the original objective provides an insufficient evolutionary signal and tends to trap the population in local optima. To address this, the authors introduce the idea of multi-objectivization from evolutionary computation into LLM-AHD for the first time. The original single objective is reformulated into a multi-objective vector that includes helper objectives; a Lexicographic-Pareto Mechanism (LPM) is designed to keep the original objective as the top priority; and evolution is driven by four operators, namely LOS (l1/l2) and PGS (p1/p2). Evaluated on eight classical planning domains from IPC 2023, the method is compared against LLM-based baselines (LHG/FunSearch/EoH/ReEvo), traditional hand-crafted heuristics, and the neural method hWLF_GPR, and reports SOTA-level performance.

Critical strengths
  1. Reformulating a single objective into multiple objectives is a novel and well-motivated idea. Existing methods such as EoH/ReEvo retain individuals only along a single original objective. The paper draws a clear boundary between two distinct routes—"directly solving a multi-objective problem (MEoH)" and "reformulating a single-objective problem as a multi-objective one while ultimately returning to the original single objective (the proposed MO-EoH)." Using helper objectives as a search scaffold to preserve differentiated individuals and maintain population diversity as a means of escaping local optima is a sound and convincing motivation.
  2. The LPM mechanism mitigates the objective drift introduced by helper objectives. In conventional unified Pareto sorting, helper objectives can easily overshadow the original objective. The proposed lexicographic design—first tiering individuals by the original objective and then applying non-dominated sorting on helper objectives within each tier—effectively alleviates this problem, and the claim is supported by ablation experiments.
Critical weaknesses
  1. Figures 1–4 fail to render in the current manuscript, which impedes the review of key claims. The authors are advised to ensure that all figures are clearly embedded in the submission version and remain accessible at their corresponding locations in the main text.
  2. Neither the validation coverage nor the model configuration adequately supports the generality claim. First, experiments are restricted to eight classical planning domains and do not cover the combinatorial optimization benchmarks commonly used in related work (e.g., TSP, BPP, CVRP, and TSP in EoH/ReEvo/FunSearch), leaving the generalization claim under-evidenced. Second, the main experiments rely on the relatively outdated GPT-4o-mini as the default; although GPT-3.5-turbo and GPT-5.1 are additionally tested, the paper lacks a systematic comparison against a broader set of open-source or up-to-date models.
Questions for authors
  1. How should helper objectives be selected? The search time and the number of expanded nodes used here are manually specified, and the authors themselves acknowledge in the conclusion that this remains an open question. Have the authors encountered cases where a poorly chosen helper objective instead harms f₁? Could a sensitivity analysis over different helper-objective combinations be added?
  2. Could the rigor and coverage of the experiments be strengthened? This would include evaluation on more combinatorial optimization scenarios and experiments with more recent models.
Reviewer_nuDuOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes MO-EoH, a multi-objectivization framework for LLM-based automated heuristic design. Instead of evaluating a generated heuristic only by the number of tasks it solves, MO-EoH also uses search time and the number of expanded nodes as helper objectives. The paper further proposes a Lexicographic-Pareto mechanism (LPM): the original objective is given highest priority, while Pareto ranking over the helper objectives is used to distinguish heuristics with the same or similar performance on the original objective. Experiments on eight classical planning domains from the IPC 2023 Learning Track report better solved-task counts than several LLM-based baselines. The paper also compares against handcrafted and neural heuristics and presents ablations on two domains.

Critical strengths
  1. Giving the original objective priority while using helper objectives to maintain useful diversity is intuitive and potentially valuable. The distinction between multi-objectivization and ordinary multi-objective optimization is also clearly motivated.

  2. MO-EoH achieves the best or tied-best solved-task count in every proposed tasks and improves the total over the strongest LLM-based baseline by about 24.5%.

Critical weaknesses
  1. Incomplete presentation: Figures 1-4 are missing from the submitted PDF. As a result, important parts of the architecture, implementation, prompts, and helper-objective results cannot be inspected. This makes both the method and its experimental evidence difficult to understand and assess from the submitted version.

  2. Insufficient support for the central claim: The results are encouraging, but they do not yet show clearly when and why the helper objectives improve the search. The paper lacks a concrete case study of the search process, and its key LPM ablation covers only two tasks. The evaluation is also limited to classical planning, where the chosen helper objectives are closely related to the main objective. This leaves the claimed usefulness in broader domains uncertain.

Questions for authors
  1. Can the authors provide all missing figures, especially the helper-objective results and the prompt and operator details?

  2. How is the population partitioned into heuristic sets? Please define "same or similar" main-objective performance and explain how LPM ranks and selects heuristics within and across these sets.

  3. Please provide a search-trajectory case study. What proportion of selection decisions are changed by helper objectives? Among those changes, what proportion produces an offspring that improves the main objective?

  4. Does the LPM ablation show a similar benefit on the other six domains? Please report the results of ablation.

  5. How should helper objectives be selected in a new domain? Evidence on a representative non-planning benchmark (TSP, CVRP, OBP, etc), or a narrower statement of scope, would make the paper's contribution clearer.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.