{"id":"fe8efa6d-ff5e-4740-b62d-99fd0246e60e","arxiv_id":"2501.11411","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Across 6,064 bin-packing instances from 12 datasets, the hand-designed Best-Fit heuristic outperforms most LLM-evolved heuristics, which do not generalize beyond their training distributions.","lead":"This paper tests five AI-generated bin-packing heuristics against five simple classic heuristics on over 6,000 problem instances from 12 benchmark sets. It finds that the classic Best-Fit heuristic outperforms most AI-generated heuristics, which tend to beat standard methods only on the narrow instance types they were trained on.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound-based AEB may inflate the headline BF-vs-LLM gaps; an exact-optimum recomputation on a stratified sample should confirm the ranking before the quantitative claims are cited.","rationale":"The reader's weakest assumption identifies exactly the issue I consider most load-bearing: the AEB metric's reliance on a loose lower bound. I agree that this is the most plausible soft spot in the paper's quantitative claims. It does not, however, undermine the central argument that most LLM-evolved heuristics fail to generalise across a broad benchmark suite. That conclusion is corroborated by metrics that do not depend on the lower bound: the win-rate heatmap shows FSW winning a single instance in a single dataset, the Falkenauer metric shows the same broad ordering, and the BF advantage is also visible in raw bin-count terms. Moreover, the paper is methodologically transparent: it defines the bound explicitly, excludes datasets drawn from training distributions, provides shuffled datasets and code, and notes limitations such as FS2 results not being reported in the original FunSearch paper. The exact-optimum test I propose would settle whether the specific '20 times' and 'BF ranks best' quantitative statements are robust, but the qualitative verdict of acceptance does not hinge on that test. Hence the reader's ACCEPT verdict stands unchanged.","tokens_in":13040,"tokens_out":21142,"duration_ms":203419,"concrete_test":"Take a stratified sample of instances from each of the 12 datasets (e.g., all instances with n <= 200 plus a random sample of 100 instances from Randomly Generated) and compute exact optimal bin counts with an exact solver (branch-and-price or a MIP) or at least a much tighter lower bound (e.g., Martello-Toth L2 or dual feasible functions). Recompute the per-dataset AEB and the summed ranking in Figure 2d using this improved baseline. If BF remains first, FSW remains last, and the FSW/BF ratio changes by less than a factor of two, the quantitative claims stand; if the ranking changes, the headline numbers require revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline quantitative claims ('BF ranks best' and 'FSW has an AEB almost 20 times that of BF') are computed with 'optimal' set to the trivial cardinality lower bound LB = sum(item sizes)/C (Section 4, metric 1). Because LB can be far below the true offline optimum, especially for instances with item sizes that are large relative to C, the reported AEB values are not true optimality gaps. Dividing by LB also acts as a per-instance weighting: instances or datasets where the bound is loose contribute more to the average. The per-instance ordering of two heuristics by AEB always matches their ordering by bin count, so BF still beats FSW on any single instance where it uses fewer bins; however, the aggregate ranking and the factor-20 statement could change if a tighter lower bound or exact optimum were used, because the relative weighting across heterogeneous instances would change. This is the weakest link in the quantitative part of the central claim. The qualitative generalization claim is independently supported by the Wins and Falkenauer metrics, both of which are free of this lower-bound dependence.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper benchmarks five LLM-evolved bin-packing heuristics (FS1, FS2, FSW, EoH, EoC) against five classical online heuristics (FF, BF, WF, NF, AWF) on 6,064 instances from 12 datasets, using three metrics: average excess bins (AEB), Falkenauer fitness, and a wins-based metric. The authors report that the hand-designed heuristic BF ranks first overall on AEB, that FS1 is the best LLM heuristic but does not clearly beat BF, and that most LLM-evolved heuristics are specialist and generalise poorly outside their training distributions. They further tune the evolved constants with irace and use instance-space analysis on evolved 'winning' instances to visualise the niche of each heuristic.","tokens_in":13185,"tokens_out":10222,"duration_ms":109278,"significance":"This is a timely and useful study: it provides the first large-scale, multi-dataset benchmark of LLM-evolved bin-packing heuristics, explicitly excludes datasets from the training distributions, and ships shuffled benchmark data in a public repository. The qualitative conclusion that most LLM-evolved heuristics are specialists rather than generalists is important for the automated heuristic-design community. The main quantitative ranking, however, relies on an AEB metric whose 'optimal' baseline is only a lower bound, so the headline magnitudes (e.g., the factor-20 gap between FSW and BF) need verification before they are cited.","major_comments":[{"comment":"The AEB metric defines 'optimal' as LB = sum(size_i)/C (Section 4, metric 1). Since LB is only a lower bound, AEB is not a true optimality gap, and for instances with large item sizes it can be very loose (e.g., FSW has AEB values of 134.2 and 450.0 in Fig. 2a). Because the aggregate AEB sums per-instance percentages divided by LB, instances with a loose bound are overweighted in the total, so the aggregate ranking could change if the baseline were the true optimum or a tighter bound. I ask the authors to (i) rename the metric as 'excess over a lower bound' and soften the 'optimal' language, (ii) recompute the ranking on a stratified sample using exact optima or stronger lower bounds (e.g., L2/L3 or dual feasible functions) and report whether BF remains rank 1 and whether the 'almost 20 times' statement for FSW vs BF survives, and (iii) report a baseline-free aggregate such as mean or total bin count. The per-instance ordering by AEB equals the per-instance ordering by bin count, so the qualitative direction is probably robust, but the aggregate weighting and reported magnitudes are not.","section":"Section 4, metric 1; Fig. 2d; Section 7"}],"minor_comments":[{"comment":"The Falkenauer fitness formula is incomplete because the exponent k is never defined; please specify k (usually 2) and state whether empty bins are included in the average, otherwise the metric is not reproducible.","section":"Section 4, metric 2"},{"comment":"Since a 'win' is defined as being better or equal to the best value, the columns of Fig. 2b can sum to well over 1 (e.g., the Angelopoulos column sums to roughly 2.5). Please call this a 'not-worse-than-best' rate or additionally report exclusive wins, especially because Section 6 uses 'won' in the exclusive sense.","section":"Section 4, metric 3; Fig. 2b"},{"comment":"The evolved instances are generated specifically for each heuristic to win, so the ISA projections and the Table 4 fractions describe synthetic niches rather than general population performance; the paper acknowledges this only in part, and an explicit warning in the Section 6 opening or in the caption would prevent misinterpretation.","section":"Section 6; Table 4"},{"comment":"The 'Randomly Generated' dataset is described only by ranges for capacity and item count, with no generator or citation; please provide the exact generation procedure or a reference.","section":"Section 3.2; Table 1"},{"comment":"For EoC, the tuning-by-enumeration step is mentioned but the size of the enumeration search space is not given; please state the number of configurations considered.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"This is a solid empirical contribution and I would be happy to see it accepted after the AEB metric issue is addressed. The central qualitative message is likely robust, but the headline quantitative claims should not be cited in their current form without a sensitivity check against a tighter lower bound or exact optima on a stratified sample."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the useful news: this is the first benchmark that treats LLM-evolved heuristics for bin packing like actual algorithms. Ten heuristics, twelve datasets, 6,064 instances, three metrics, and the authors release their shuffled instances and code. They also exclude the distributions used during evolution, which is the obvious control that the original FunSearch and EoH papers skipped. The headline result—BF, a hand-designed heuristic from the 1970s, beats all five LLM heuristics on average, and most of the LLM heuristics are specialists that fail off-distribution—is credible and worth knowing.\n\nThe tuning study is a genuinely nice extra: it shows that the evolved numeric constants are not the reason these heuristics fail to transfer. Tuning gives small improvements where they were already good and small losses elsewhere. The instance-space analysis is well done, and the section that evolves new instances 'won' by each heuristic is explicitly and correctly framed as a stress test, not as evidence of superiority. That is the right way to use that tool.\n\nThe soft spot is the AEB metric. The paper defines 'optimal' as sum(item sizes)/C, the trivial cardinality lower bound. For bin-packing instances with large items relative to capacity, that bound is very loose, so the reported 'excess bins' are not true optimality gaps. Because the metric divides by that lower bound per instance, instances where the bound is loose get more weight in the average. The specific quantitative claims—'FSW has an AEB almost 20 times that of BF'—are not safe to cite. A recomputation against exact optima on a stratified sample would settle whether the ranking and the magnitudes survive. My guess is the ranking mostly survives, because BF also wins on the wins metric and the near-wins analysis in Table 4, both of which use actual bin counts. But the factor-20 number should not be quoted in its current form.\n\nMinor: there are no statistical significance tests, though the effect sizes are large enough that this is not a threat to the conclusion.\n\nBottom line: this is a useful, honest empirical paper. The qualitative claim is well supported and is independent of the AEB metric. The quantitative part needs a fix or a caveat before it is citable. I would send it to peer review, and I would bring it to a reading group.","headline":"First large-scale benchmark of LLM-evolved bin-packing heuristics; the qualitative generalization finding is solid, but the main quantitative metric relies on a weak lower bound and exact numbers should be re-verified.","tokens_in":13727,"tokens_out":3598,"would_cite":true,"duration_ms":32710,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A broad benchmark of bin-packing heuristics finds that the decades-old Best-Fit rule still outperforms most LLM-evolved heuristics, which specialize to the data they were trained on.","keywords":["LLM-evolved heuristics","bin packing","benchmarking","instance space analysis","generalization","online bin packing","evolutionary computation","Best-Fit heuristic"],"falsifier":"Run the same ten heuristics on freshly generated instances from distributions never seen in training (for example, log-normal or truncated exponential item sizes), or compute exact optimal bin counts for a subset of the smallest benchmarks, and compare; if an LLM-evolved heuristic beats Best-Fit on a majority of such datasets, the claim that most LLM heuristics do not generalise is false.","tokens_in":12804,"feed_emoji":"📦","tokens_out":7597,"duration_ms":66317,"temperature":0.7,"pith_summary":"This paper puts five LLM-generated bin-packing heuristics and five classic hand-designed ones to the same test: 6,064 instances from 12 datasets, scored by three metrics. Its central finding is that most LLM-evolved heuristics are specialists that perform well only on instances drawn from the same distribution they were trained on and do not generalise across the full benchmark suite. On the primary metric, average excess bins over a lower bound, the hand-designed Best-Fit heuristic ranks first overall, with the LLM heuristic FS1 a close second. The authors argue that the considerable cost of evolving heuristics with LLMs should be weighed against this narrow coverage.","feed_headline":"Best-Fit beats LLM-evolved heuristics on broad bin-packing tests","feed_subtitle":"LLM-evolved packing rules were tested on 6,064 instances; most only perform well on the distribution they trained on.","key_machinery":"The evaluation is carried by a portfolio of ten deterministic heuristics: five classic online bin-packing rules (Next-Fit, First-Fit, Best-Fit, Worst-Fit, Almost-Worst-Fit) and five LLM-evolved ones (FS1, FS2, FSW from FunSearch; EoC and EoH from the Evolution of Heuristics method). Three metrics are applied consistently across all instances: Average Excess Bins (AEB), computed as the mean percentage of bins above the lower bound $\\sum_i s_i / C$; the Falkanauer fitness; and the fraction of instances won. The specialization story is drawn from Instance Space Analysis, which projects 209 time-series features into two dimensions, and from an evolutionary instance generator that produces 100 instances won by each heuristic; the gap between 'wins within its niche' and 'performance on the 800 instances it did not win' quantifies generality.","core_discovery":"The paper claims that when LLM-evolved heuristics for online bin packing are evaluated across a broad suite of 12 diverse datasets rather than the single distribution used during evolution, most of them fail to match the classic hand-designed heuristics they were meant to improve. On the average excess bins metric, Best-Fit has the lowest overall score; FS1, evolved by the FunSearch program on OR-Library data, ranks second and ties Best-Fit on several datasets. Two heuristics trained on Weibull-distributed data, FSW and EoH, sit at the bottom of the ranking, with FSW's excess bins roughly 20 times that of Best-Fit. The paper also reports that the code-only variant EoC outperforms EoH on the broad suite, even though the original EoH paper found the opposite on Weibull-only data, and that tuning the evolved heuristics' numeric constants with a standard configuration tool does not rescue their performance. An instance-space analysis and an evolutionary search for 'winning' instances show that the LLM heuristics occupy distinct niches in feature space, with FS1 and FS2 generalising well within their training distribution but not across distributions.","pith_inferences":["A natural next test is to run FS1 against Best-Fit on instances from other combinatorial domains, such as scheduling or cutting stock, to see whether its near-generalist behaviour on bin packing extends beyond one problem.","The ISA projection suggests a practical portfolio: a meta-heuristic could compute the selected time-series features online and switch to the region's winning heuristic, which would likely outperform any single LLM heuristic on the full benchmark.","Because the AEB lower bound can be loose, re-ranking the same heuristics with exact optima on small instances (like Scholl_1) would show whether Best-Fit's margin over FS1 is an artifact of the bound or a true gap.","The cost figures cited for the LLM search process imply that an economic case for LLM heuristic design needs a prior on how often a generalist like FS1 emerges; the paper's data suggest that is the exception, not the rule."],"forward_implications":["If the claim holds, LLM-evolved heuristics should not be deployed blind: their expected advantage exists only when the target instance distribution is known in advance and matches the training distribution.","The reversal of EoC versus EoH on the broad suite warns that single-distribution leaderboards can flip when the test set broadens, so reported rankings in automated heuristic design should be treated as distribution-dependent.","The tuning experiment shows the evolved constants are not the bottleneck; the heuristics' structural logic is what limits them, so tuning alone will not turn a specialist into a generalist.","The instance-space maps provide a recipe for algorithm selection: after computing cheap features of an incoming instance, choose the heuristic that owns that region, potentially combining the best of specialist and generalist rules."],"supporting_citations":[{"why":"Supplies the three FunSearch-evolved heuristics FS1, FS2 and FSW, and describes the training distributions and costs used for comparison.","marker":"[25]"},{"why":"Supplies the two EoH heuristics EoC and EoH, and provides the original Weibull-only results that this paper reverses on the broad suite.","marker":"[17]"},{"why":"Defines the five hand-designed heuristics (Next-Fit, First-Fit, Best-Fit, Worst-Fit, Almost-Worst-Fit) that serve as generalist baselines.","marker":"[16]"},{"why":"Provides the OR-Library datasets used for the training distribution of FS1 and FS2 and as part of the benchmark suite.","marker":"[6]"},{"why":"Is the source of most of the 12 benchmark datasets, providing the broad range of instance classes used for the generalization test.","marker":"[1]"},{"why":"Provides the Weibull-based benchmark dataset and the shuffling procedure that produces online instances from offline data.","marker":"[3]"},{"why":"Provides the Instance Space Analysis methodology used to visualise where each heuristic wins in feature space.","marker":"[28]"},{"why":"Defines the Falkanauer fitness metric used as a secondary performance measure and as the objective for evolving winning instances.","marker":"[12]"},{"why":"Supplies the automatic configuration tool used in the tuning experiments, whose failure to improve most heuristics supports the specialization claim.","marker":"[18]"}],"fun_headline_variants":["LLM-evolved packing heuristics fail to generalize beyond training","Classic Best-Fit still tops LLM-evolved heuristics in bin packing","LLM heuristics: 20x worse than Best-Fit on diverse bin-packing suite","Specialist LLM heuristics underperform classic Best-Fit across 12 datasets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main ranking uses Average Excess Bins, which defines 'optimal' as the lower bound $\\sum_i s_i / C$; if that bound is loose for some datasets, the reported excess-bins figures overstate how far each heuristic is from a truly optimal packing.","fun_headline_variants_meta":{"raw":{"variants":["LLM-evolved packing heuristics fail to generalize beyond training","Classic Best-Fit still tops LLM-evolved heuristics in bin packing","LLM heuristics: 20x worse than Best-Fit on diverse bin-packing suite","Specialist LLM heuristics underperform classic Best-Fit across 12 datasets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000869,"raw_usage":{"total_tokens":3805,"prompt_tokens":1029,"completion_tokens":2776,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":645,"completion_tokens_details":{"reasoning_tokens":2690}},"tokens_in":645,"tokens_out":2776,"duration_ms":22018,"temperature":1.0,"reasoning_tokens":2690,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:17:18.756618+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same ten heuristics on freshly generated instances from distributions never seen in training (for example, log-normal or truncated exponential item sizes), or compute exact optimal bin counts for a subset of the smallest benchmarks, and compare; if an LLM-evolved heuristic beats Best-Fit on a majority of such datasets, the claim that most LLM heuristics do not generalise is false.","supporting_citations":[{"cited_title":"Nature625(7995), 468–475 (2024)","cited_arxiv_id":null,"evidence_quote":"Supplies the three FunSearch-evolved heuristics FS1, FS2 and FSW, and describes the training distributions and costs used for comparison."},{"cited_title":"In: Forty-first International Conference on Machine Learning (2024)","cited_arxiv_id":null,"evidence_quote":"Supplies the two EoH heuristics EoC and EoH, and provides the original Weibull-only results that this paper reverses on the broad suite."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the five hand-designed heuristics (Next-Fit, First-Fit, Best-Fit, Worst-Fit, Almost-Worst-Fit) that serve as generalist baselines."},{"cited_title":"Journal of the operational research society41(11), 1069–1072 (1990)","cited_arxiv_id":null,"evidence_quote":"Provides the OR-Library datasets used for the training distribution of FS1 and FS2 and as part of the benchmark suite."},{"cited_title":"https://site.unibo.it/ operations-research/en/research/bpplib-a-bin-packing-problem-library","cited_arxiv_id":null,"evidence_quote":"Is the source of most of the 12 benchmark datasets, providing the broad range of instance classes used for the generalization test."},{"cited_title":"Journal of Artificial Intelligence Research78, 1111–1141 (2023)","cited_arxiv_id":null,"evidence_quote":"Provides the Weibull-based benchmark dataset and the shuffling procedure that produces online instances from offline data."},{"cited_title":"ACM Computing Surveys55(12), 1–31 (2023)","cited_arxiv_id":null,"evidence_quote":"Provides the Instance Space Analysis methodology used to visualise where each heuristic wins in feature space."},{"cited_title":"In: ICRA","cited_arxiv_id":null,"evidence_quote":"Defines the Falkanauer fitness metric used as a secondary performance measure and as the objective for evolving winning instances."},{"cited_title":"Opera- tions Research Perspectives3, 43 – 58 (2016)","cited_arxiv_id":null,"evidence_quote":"Supplies the automatic configuration tool used in the tuning experiments, whose failure to improve most heuristics supports the specialization claim."}],"review_version":1}