- 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.