人类与大模型协作，突破算法对抗实例的长期难题
The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics
- 用大模型生成初始解，人类专家迭代优化构造
- 在多个经典问题上刷新最差情况下的性能下界
- 适合对算法鲁棒性、理论计算机科学感兴趣的读者
我们展示了人类与大语言模型协作在解决理论计算机科学开放问题中的强大能力。聚焦组合优化，通过迭代优化FunSearch算法[Romera-Paredes et al., Nature 2023]的输出，我们为标准启发式算法推导出当前最优的下界。具体目标是生成使这些启发式算法表现不佳的对抗性实例。通过该方法，我们在层级k-中位数聚类、装箱问题、背包问题以及Lovász汽油问题的一个推广形式上获得了改进的构造——其中一些问题在过去十余年中鲜有进展，尽管间歇性受到关注。这些结果表明，专家监督能够有效从基于大模型的进化方法中提取算法洞见，从而突破长期存在的瓶颈。我们的研究强调，虽然大模型提供关键的初始模式，但人类专业知识对于将这些模式转化为数学严谨且富有洞察力的构造至关重要。这项工作凸显了大模型在数学与计算机科学研究中作为强力协作工具的价值。
原文摘要 · Abstract (English)
We demonstrate the power of human-LLM collaboration in tackling open problems in theoretical computer science. Focusing on combinatorial optimization, we refine outputs from the FunSearch algorithm [Romera-Paredes et al., Nature 2023] to derive state-of-the-art lower bounds for standard heuristics. Specifically, we target the generation of adversarial instances where these heuristics perform poorly. By iterating on FunSearch's outputs, we identify improved constructions for hierarchical $k$-median clustering, bin packing, the knapsack problem, and a generalization of Lovász's gasoline problem - some of these have not seen much improvement for over a decade, despite intermittent attention. These results illustrate how expert oversight can effectively extrapolate algorithmic insights from LLM-based evolutionary methods to break long-standing barriers. Our findings demonstrate that while LLMs provide critical initial patterns, human expertise is essential for transforming these patterns into mathematically rigorous and insightful constructions. This work highlights that LLMs are a strong collaborative tool in mathematics and computer science research.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。