💻 computer science

An In-depth Study of LLM Contributions to the Bin Packing Problem

本文通过证明大语言模型生成的启发式算法具有不透明性，且该问题实例实际上足够简单、足以由更高效、更具可解释性且更具泛化性的算法来解决，从而挑战了“大语言模型显著推进了装箱问题数学发现”这一观点，进而强调了对大语言模型生成的科学贡献进行严格验证的必要性。

原作者： Julien Herrmann, Guillaume Pallez

发布于 2026-06-19

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Julien Herrmann, Guillaume Pallez

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在经营一个巨大的仓库。每天都有各种尺寸的箱子运抵，你必须在它们到达时迅速将它们装入运输集装箱（箱子）中。你不知道下一个箱子会是什么样子，你只能快速做出决定：“我是把它放进 A 集装箱、B 集装箱，还是再开一个新的 C 集装箱？”

目标很简单：使用尽可能少的集装箱。这是一个经典的谜题，被称为装箱问题（Bin Packing Problem）。

最近，一项著名的研究（由 Romera-Paredes 等人进行）声称，大语言模型（LLMs）——即产生这些写文章和代码的相同 AI 技术——已经发现了一个“数学秘密”来解决这个装箱谜题，其表现甚至优于人类。他们说，AI 发现了一个聪明的规则，这个规则如此高明，以至于被视为一种“数学发现”。

Julien Herrmann 和 Guillaume Pallez 的这篇论文就像是一支由专家组成的侦探团队，受命来调查这一说法。他们戴上放大镜说：“等等。让我们看看这个 AI 到底做了什么。”

以下是他们发现的内容，解释如下：

1. AI 的“秘密”其实并不神秘

AI 生成了一套计算机指令（一种启发式算法），其装箱效果比人类的标准方法稍好。原研究声称这些指令是“可解释的”，意味着人类可以轻松阅读并理解其中的逻辑。

论文的现实检查：
作者们查看了 AI 的代码，发现它读起来就像是用一种奇怪的方言写的食谱。

“c12”代码： 这是一长串“如果……那么……”的规则。它是可读的，但逻辑非常混乱。这就像一位厨师说：“如果锅温在 7 到 8 度之间，就加盐；如果在 8 到 9 度之间，就少加一撮。”它有效，但并没有解释为什么有效。
“c14”代码： 这个甚至更糟。它是一个复杂的数学公式，看起来像天书。作者们不得不进行数千次实验，仅仅是为了猜测这段代码到底在做什么。他们意识到，尽管代码是用纯正的英语（Python）编写的，但其背后的推理过程却是隐藏的。它是一个戴着透明面具的“黑盒”。

类比： 想象一下，AI 给了你一个总是指向北方的神奇指南针。原研究说：“看，指南针是玻璃做的，所以你可以看到指针！它是完全可理解的！”而作者们说：“是的，我们可以看到指针，但我们完全不知道里面的磁铁是如何工作的。我们只知道它指向北方，是因为我们测试了它一百万次。”

2. AI 并没有发现新的物理定律

原研究声称 AI 做出了一项“数学发现”。作者们认为这种说法有些夸大其词。

论文的现实检查：
AI 是在非常特定、狭窄的场景下进行测试的（例如，所有箱子的尺寸都在 20 到 100 个单位之间）。作者们发现，AI 并没有发明一种新的思考方式，它只是找到了一个旧有的、简单技巧的微调版本。

他们意识到，AI 的“秘密配方”实际上只是两个简单的参数：

“如果一个箱子装得非常紧凑，就把它放进去。”
“如果它装得不紧凑，就把它放入剩余空间充足的集装箱。”

作者们提取了这个简单的想法，剥离了复杂的 AI 代码，并构建了一个全新的、极其简单的算法（称为 ab-FirstFit 或 ab-WorstFit）。

结果： 这个由人类创造的新算法比 AI 的复杂代码更快、更容易理解，而且效果更好。它甚至可以在不同的箱子尺寸类型下工作，而 AI 的代码在规则稍作改变时就会失效。

类比： 这就像 AI 通过发明一个带有 15 个环的复杂结，找到了一种稍微好一点的系鞋带方法。作者们观察后意识到：“噢，你只需要把鞋带拉紧，留出一点余地就行了。”并展示了一个简单的双结不仅效果更好，也更容易学习，且不需要获得结理论的博士学位。

3. “发现”仅仅是因为缺乏前置研究

原研究声称他们发现了“新东西”，因为之前没有人针对这些特定的箱子尺寸发表过论文。

论文的现实检查：
作者们指出，没有人研究过这些特定的箱子尺寸，并不是因为它们太难或太神秘，而是因为它们并不重要。这就像声称你通过寻找在特定形状的花园里堆叠鹅卵石的最佳方法而取得了“科学突破”一样。这是一个有效的问题，但这并不是一项基础性的发现。

作者们认为，如果 AI 真的发现了一个深刻的数学真理，其他研究人员应该能够阅读 AI 的代码，理解其原理，并将其用于解决其他问题。然而，事实是，没有人能做到这一点。这种“洞察力”随着 AI 编写的特定代码而消亡了。

核心结论

论文总结道，虽然利用 AI 来辅助设计算法是一个很酷的想法，但我们需要对这些炒作保持警惕。

AI 并没有做出“数学发现”。 它只是通过试错法找到了一种完成简单任务的稍好方法。
AI 的代码并非真正“可解释”。 它的逻辑难以理解，其“逻辑”只能通过实验推测得出，而不是通过阅读代码本身获得的。
人类可以做得更好。 通过理解 AI 偶然发现的简单原则，人类创造了一个更简单、更快速、更可靠的工具。

最终的比喻：
AI 就像一只在打字机上敲字的猴子。最终，它敲出了一个有意义的句子。原研究说：“看！这只猴子发现了生命的意义！”而本文的作者们说：“不，这只猴子只是为这个特定的段落敲出了一个行得通的句子。我们可以写出一个更好的句子，清晰地解释它，并将其应用到整本书中，而不需要依赖猴子。”

该论文敦促科学家们要严谨：仅仅因为 AI 产生了一个看起来很聪明的结论，并不意味着它真正理解了问题，也不意味着它做出了改变数学思维方式的发现。

技术摘要：关于大语言模型（LLM）对装箱问题贡献的深入研究

1. 问题定义与背景

本文调查了 Romera-Paredes 等人 [2024] 关于大语言模型（LLM）在组合优化领域做出“数学发现”这一主张的有效性。研究重点在于在线装箱问题（Online Bin Packing Problem, OBPP），在该问题中，大小不一的物品按顺序到达，必须被装入固定容量的箱子中，且在装箱时无法预知未来物品的信息。其目标是最小化所使用的箱子总数。

本研究审视了 FunSearch 框架，该框架在进化算法中使用 LLM（Codey）来为特定随机 OBPP 实例生成启发式算法。目标实例的物品大小取自 Uniform(20, 100) 和 Weibull(3.0, 45) 分布。尽管 Romera-Paredes 等人声称这些由 LLM 生成的启发式算法代表了新的科学发现且具有可解释性，但本文指出，这些实例此前之所以未被研究，是因为它们相对简单，且生成的启发式算法缺乏真正的可解释性和泛化能力。

2. 研究方法

作者采用多维度的研究方法来重新评估 LLM 生成的启发式算法：

代码分析与可解释性评估： 作者手动分析了表现最佳的 LLM 生成启发式算法（针对 Uniform 分布记为 c12，针对 Weibull 分布记为 c14，以及来自 Liu 等人 [2024] 的 EoH 启发式算法）的源代码。他们评估了逻辑对于领域专家是否透明，或者是否需要大量的实验才能理解。
行为逆向工程： 对于不透明的启发式算法（特别是 c14），作者通过将其与基准策略（如 WorstFit、BestFit）进行逐项比较，以推导其底层的决策规则。他们分析了剩余箱容量和决策阈值，从而构建出一个人类可读的算法行为近似模型。
简化算法的推导： 基于行为分析，作者提出了一类新的双参数启发式算法（分别记为 ab-FirstFit、ab-BestFit 和 ab-WorstFit）。这些算法将观察到的模式形式化为：
1. 如果一个箱子可以容纳该物品，使得剩余空间 $\le a$ （紧凑拟合），则应用特定策略（例如 BestFit）。
2. 如果剩余空间 $> b$ （宽松拟合），则应用基准策略（例如 FirstFit 或 WorstFit）。
3. 否则，开启一个新箱子。
实证评估： 作者将提出的 ab-Baselines 与 LLM 生成的启发式算法（c12、c14、EoH）以及标准基准（BestFit、FirstFit）在原始分布及额外的变体（不同的 Uniform 和 Weibull 参数）上进行了基准测试。评估指标包括使用的箱子数量和泛化能力。

3. 核心贡献

对可解释性的批判： 本文证明，虽然 LLM 生成的代码在语法上是可读的，但在语义上并不具备可解释性。启发式算法 c14 和 EoH 包含了不透明的数学运算（例如依赖于邻居的评分更新、复杂的指数项），这些运算并未揭示底层的逻辑。理解其行为需要通过实验观察而非代码检查，这与“提供可解释见解”的主张相矛盾。
识别潜在的简单性： 作者表明，LLM 启发式算法的性能提升依赖于两个特定条件：(H1) 需要调度的物品数量庞大，以及 (H2) 分布具有正的物品大小下界（防止极小物品填补巨大的空隙）。这些条件使得特定的实例变得相对简单。
提出更优且具泛化能力的启发式算法： 作者引入了 ab-Baselines，这是一类简单的双参数算法。这些启发式算法：
- 在其训练分布上达到或略微超过了 LLM 生成的启发式算法的表现。
- 计算效率显著更高（仅需数分钟的调优，而非数百万次 LLM 查询）。
- 能有效地泛化到 Uniform 和 Weibull 分布的其他参数化配置中，而 LLM 启发式算法在超出其特定训练簇后表现失效。
对“数学发现”的重新评估： 本文认为，所研究的实例（Uniform(20, 100) 和 Weibull(3.0, 45)）此前未被研究并非因为其难度大，而是因为它们可能被学术界视为无趣或平凡的。LLM 本质上是通过随机搜索重新发现了已知的优化模式（紧凑拟合与宽松拟合），而非生成了新的概念性洞察。

4. 结果

性能： 在 Uniform(20, 100) 分布上，简化的 ab-FirstFit（参数为 $a=5, b=24$ ）平均表现优于 LLM 启发式算法 c12 0.71%，优于 BestFit 2.71%。在 Weibull(3.0, 45) 分布上，ab-WorstFit（ $a=1, b=21$ ）优于 c14 0.12%，优于 BestFit 3.39%。
泛化能力： 当在不同参数的分布上进行测试时，LLM 启发式算法的性能显著下降，而 ab-Baselines 在各种 Uniform 和 Weibull 配置下均保持稳健的性能。
效率： ab-Baselines 的推导和调优在个人笔记本电脑上仅耗时数分钟，这与产生 c12 和 c14 所需的数天训练时间和数百万次 LLM 查询形成了鲜明对比。
可解释性差距： 作者成功地将 c14 的逻辑逆向工程为一条简单的规则（紧凑拟合用 BestFit，宽松拟合用 WorstFit，否则开新箱），证明了所谓的“发现”是对现有策略的重新参数化，而非新的算法概念。

5. 重要性与主张

论文最后对 LLM 在科学发现中的作用进行了审慎且关键的重新评估：

对“发现”的驳斥： 作者断言，基于 LLM 的进化框架并没有产生意义上的“数学发现”，即没有提供新的理论理解或概念性突破。相反，它充当了一个强大的超启发式算法（hyper-heuristic），针对一个特定的、狭窄且此前未被研究的实例优化了参数。
当前主张的局限性： 通过装箱问题的案例研究，作者认为“LLM 可以解决既有开放问题”这一主张缺乏充分支持。这些特定分布此前缺乏相关研究，并非因为其难度高，而是因为其缺乏被感知的研究价值。
未来方向： 本文倡导严格的验证协议。若要将 LLM 视为具有真正的科学贡献，必须将其应用于重要的、成熟的课题，且其产生的解决方案必须展现出优于现有最佳文献的改进，并能提供可迁移的概念性洞察，而非仅仅是在狭窄的合成实例上获得经验性的增益。
LLM 的角色： 作者将 LLM 定位为扩展遗传算法搜索空间和自动化启发式设计的工具，但强调在这种语境下，它们的功能是经验优化器，而非理论洞察的代理。