acceptodds
Withdrawn from ICLR 2027

Heuristic Sets over a Space of Distributions: LLM-based Evolution of Heuristics Beyond a Single Instance Generator

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Large language models can design heuristics for combinatorial problems by evolving program code, but the resulting heuristics are designed and tested on instances from a single generator, and independent evaluations report that their advantage disappears, sometimes falling behind hand-written rules, once the instances come from elsewhere. Complementary heuristic sets, as in EoH-S, answer this with several heuristics, but they too are evolved on one generator. We study this problem on online bin packing. We first show that it is not only a weakness of the search: we construct two item-size distributions and compute their optimal policies exactly, and at the same packing state the two require different actions, so no single heuristic minimizes the expected number of bins on every distribution. This grounds the set in the problem and moves the question to what it is evolved on. We construct , a family of 20000 item-size distributions selected from 180000 random candidates by farthest-point sampling in total variation distance, with measured coverage, and we propose , which extends EoH-S to evolve its set over this family: each generation is scored on a fresh mini-batch of distributions, on which surviving members are re-scored before comparison. To use the set online, a selector chooses a member from a prefix of the item stream, by retrieval under TV or or by lookahead simulation. On a BPPLIB suite of 6,064 instances, where six published heuristics designed on Weibull instances are all behind Best Fit, the sets have the lowest gap ( against for Best Fit and for EoH-S on its fixed instance set), and on the Weibull benchmark they never saw they are ahead of Best Fit; a lookahead selector realizes part of this online, beating or matching the best fixed choice made in hindsight.

Primary area:
optimization
Keywords:
automated heuristic design, large language models, evolutionary computation, online bin packing, heuristic sets, distribution shift, generalization, combinatorial optimization

Reviews

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

This paper studies the cross-distribution generalization of LLM-generated heuristics for online bin packing. It introduces DistSpace-OBP, a training family of 20,000 item-size distributions selected through farthest-point sampling under total variation distance, and DiSE, which extends EoH-S with distribution mini-batches and re-evaluation of surviving members. The paper also provides a finite-horizon example demonstrating conflicting optimal decisions under different distributions and explores prefix-based heuristic selection for online deployment. Under per-instance best-of-set evaluation, DiSE improves over the original EoH-S on BPPLIB while retaining an advantage over Best Fit on the Weibull benchmark.

Critical strengths

1. An interesting focus on the often-overlooked role of data distributions in LLM-based heuristic design.

Performance degradation outside the design distribution is an important issue in automated heuristic design. Investigating the distributions used to evaluate candidate programs offers a useful direction for improving generalization.

2. The external evaluation provides encouraging evidence.

The BPPLIB evaluation covers 6,064 instances across 12 datasets. Under per-instance best-of-set evaluation, DiSE achieves a dataset-averaged gap of 5.92%, compared with 6.32% for EoH-S and 7.11% for Best Fit. The prefix-based selection experiments also attempt to translate the potential of the heuristic set into executable online performance.

Critical weaknesses

1. The independent contribution of the coverage-based distribution construction is insufficiently established.

DiSE largely inherits the representation, search operators, and complementary selection mechanism of EoH-S, placing its main contribution in training-distribution construction and evaluation scheduling. Although the experiments vary the number of training distributions, they lack a controlled comparison between TV-based farthest-point sampling and random sampling from the same candidate pool, using the same number of distributions and matched budgets. A single heuristic trained on the same diverse distributions is also missing. Consequently, the results do not adequately separate the contributions of coverage-based selection, general training diversity, and the set structure. Comparisons with representative adaptive training-instance construction methods discussed in the paper are also limited.

2. The final discovered heuristics are neither presented nor sufficiently analyzed.

Although candidates are described as consisting of natural-language descriptions and executable code, the paper does not show the actual code or strategy descriptions of the final DiSE members. This limits direct verification of the reported results and makes it difficult to understand what the search discovered. Moreover, because the main results use per-instance best-of-set evaluation, the observed improvements could arise from more robust individual members, complementary specialists, or both. Beyond the best-fixed-action references in Tables 5, 8, and 9, the paper does not report a per-member cross-distribution performance matrix or marginal contributions to the set.

3. The validation of practical online performance and broader applicability remains limited.

The main BPPLIB results measure the potential of the set through hindsight selection. For BPPLIB specifically, Table 8 uses an earlier DiSE run trained on 4,096 distributions under W₁, rather than the final TV-based, 20,000-distribution configuration. Table 5 evaluates the final configuration on Weibull, but its online performance on BPPLIB remains unverified. Furthermore, the investigation is restricted to heuristic construction for online bin packing. The experiments therefore support conclusions within this problem, while the broader applicability of the approach to other heuristic-design tasks remains unestablished.

Questions for authors

1. How much improvement comes specifically from the coverage-based construction?

Please provide a comparison between random sampling and TV-based farthest-point sampling from the same candidate pool, with equal numbers of distributions and matched budgets, together with a comparison between a single heuristic and a heuristic set trained on the same distributions. Could the paper also include a representative adaptive instance-construction baseline, or explain the concrete limitations preventing a comparable evaluation?

2. What are the actual search and evaluation budgets for each DiSE configuration?

Please clarify whether DiSE also uses 2,000 samples per run and report the total generated and valid candidates, offspring per generation, total generations, completed epochs, number of distinct training distributions visited, and total packing evaluations including re-scoring. Please specify which budget is matched against EoH-S and provide individual-run results or uncertainty across runs.

3. Can the final programs and their cross-distribution behavior be made available for inspection?

Please provide the final heuristic code and natural-language descriptions corresponding to the reported results, identifying the configuration, run seed, and version. Please also explain representative decision rules and report member-level performance across distributions and contributions to the set, to distinguish individual robustness from complementarity among specialists.

Reviewer_HMSxOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper looks at why LLM-evolved heuristics for online bin packing fail to transfer beyond the generator they were trained on. It shows with a small counterexample that no single heuristic can be optimal for every item-size distribution. It then builds a family of 20k distributions and extends EoH-S to evolve a heuristic set over this family. A prefix-based selector picks one heuristic from the set online.

Critical strengths
  • The problem is real: it is known that LLM-AHD heuristics overfit their generator, and evolving over a distribution family is a sensible direction. DistSpace-OBP, with its measured coverage, could be useful to others working on this problem.
Critical weaknesses
  • The headline numbers are hindsight best-of-set, and it is not shown that distribution diversity is what helps . Tables 3–4 score each set by its best member per instance and then compare against single heuristics. Any set benefits from this, even EoH-S beats Best Fit under this scoring. Once you have to pick a member online, the gain over Best Fit is only about +0.24 pp (Table 8). On top of that, Table 8 comes from an earlier DiSE run, not the set reported in the paper. The claim that lookahead beats the best fixed choice also does not hold at M=50 (Table 5, one seed). On Weibull, DiSE is actually worse (0.97 vs. 0.77). Results do not improve as the family grows (DiSE-128 is better than DiSE-4,096). DiSE's LLM budget is not stated, and there is no k=1 ablation (a single heuristic evolved on DistSpace).

  • Limited novelty and the baselines are missing. Technically, DiSE is EoH-S plus distribution mini-batches and re-scoring. Heuristic set + selector from a prefix is essentially the classical algorithm portfolio / per-instance algorithm selection setting (Rice; Kerschke et al., 2019, both cited). Thm. 1 (different distributions need different optimal actions) is an expected result. The baselines that would test whether LLM evolution is needed are missing: (i) a portfolio of existing rules (BF, FF, Worst Fit, Harmonic, plus the six published LLM heuristics) under the same selector; (ii) Sum-of-Squares (Csirik et al., 2006), which is distribution-agnostic and has guarantees; (iii) the closest LLM4AD works (e.g., HiFoPrompt, Pathwise, RAISE, ASRO, MOSAIC, DASH), none of which appear in Tables 3–4.

Questions for authors
  1. What LLM-sample budget does DiSE use, compared with EoH-S's 2,000?
  2. What are the online (selector) results on BPPLIB for the actual DiSE and EoH-S sets, rather than for the earlier run?
  3. Can you give mean ± std over at least 3 seeds, and add a k=1 ablation?
  4. No code is provided. Could the authors share an anonymous repo?
  5. How does a portfolio of existing hand-written rules plus the published LLM heuristics perform under the same lookahead selector?
Reviewer_zx4zOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper investigates the generalization ability of LLM-designed heuristic sets under shifts in input distributions, using online bin packing as the target problem. The authors first construct two input distributions with conflicting optimal decisions and prove that, within the considered class of decision functions that are unaware of the generating distribution, no single heuristic can be optimal for both. They then introduce DistSpace-OBP, a training environment comprising 20,000 distributions selected through farthest-point sampling under total variation (TV) distance. Building on EoH-S, they propose DiSE, which retains the original search and set selection mechanisms while introducing distribution-batch rotation and re-scoring of surviving members. Experiments are conducted on two external benchmarks, Weibull and BPPLIB. Under per-instance hindsight best-member evaluation, DiSE outperforms EoH-S. The authors also investigate how the potential benefits of heuristic sets translate into actual online improvements through prefix-based retrieval and lookahead simulation selectors.

Critical strengths

The paper investigates how training distributions should be constructed for heuristic design in online bin packing and proposes methods for online heuristic selection. I recognize the research value of training instance generation and algorithm selection.

Critical weaknesses

1. Limited methodological novelty and insufficient justification for the rationale and generalizability of the training-distribution construction.

The paper reiterates the familiar intuition that different input distributions may require different optimal heuristics, while the connection between this theoretical result and the proposed method remains relatively limited. DiSE largely retains the heuristic generation, evolutionary operators, and set selection mechanisms of EoH-S, with the main changes lying in the training distributions and evaluation procedure. Consequently, the algorithmic novelty is limited.

Furthermore, the construction of DistSpace-OBP relies on the probability distribution of item sizes in online bin packing, and it remains unclear whether this approach can be generalized to other combinatorial optimization problems. More importantly, although the authors increase the diversity of training distributions through farthest-point sampling, they do not adequately explain why such diversity should lead to better algorithmic performance, nor do they establish a clear connection between the generated training distributions and the actual target distributions.

2. The experiments lack critical fair comparisons, making it difficult to assess the actual incremental contribution of the proposed method.

The paper compares DiSE with methods such as EoH-S, but these methods differ not only in their training distributions but also in training data size and evaluation procedures. It is also unclear whether their actual computational budgets are comparable. In particular, the paper lacks a comparison between farthest-point sampling and random sampling across multiple distributions under matched numbers of training instances and computational budgets. As a result, the current experiments do not adequately distinguish whether the performance improvements arise from the specific distribution construction method proposed in this paper or simply from more diverse training data. DiSE is also not directly compared with the adaptive instance-generation or generator-construction methods discussed in the paper.

Furthermore, the results reported on BPPLIB, which contains multiple input distributions, are based on per-instance hindsight best-member evaluation and therefore do not directly reflect actual online performance. Although the authors provide additional online selection experiments on BPPLIB in the appendix, these experiments use 4,096 training distributions constructed under Wasserstein-1 (W1W_1) distance, whereas the main DiSE experiments use training distribution sets constructed under TV distance. Thus, the online experiments and the main performance comparisons are not based on the same training configuration, making it difficult to establish whether the advantages of the DiSE heuristic sets reported in the main paper can be realized in actual online settings.

Questions for authors
  1. Under the same EoH-S search mechanism, number of training distributions, and comparable evaluation budgets, how much consistent improvement does TV-based farthest-point sampling provide over randomly selecting distributions from the same candidate pool? Are there any directly comparable approaches among the existing instance-generation or training-environment construction methods discussed in the paper?

  2. When the target or test distribution is unknown, why is geometric coverage of the constructed candidate pool, with equal weighting across distributions, an appropriate training objective? Is there evidence that improved coverage can predict improvements in algorithmic performance or complementarity among heuristic set members?

  3. How does the current TV-based version perform on BPPLIB when using the same prefix lengths and selectors? Does DiSE still outperform EoH-S when EoH-S is equipped with the same selector?

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

Related papers

Discussion (0)

Sign in to comment.