用AI自动优化图最小割算法，速度提升超10倍。
Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts
- 用大模型自主提出优化假设并验证，替代人工调优
- 在真实世界图上提速1.28倍（串行），32线程下1.63倍
- 对标准测试集DIMACS核心实例提速6.26至127倍，适合算法研究者
无向加权图的最小割问题要求将节点划分为两组，使割边权重和最小。我们此前开发了一系列快速算法，最快的确切算法利用不精确算法获取更优边界，结合依赖该边界的约简、改进的数据结构与并行收缩过程。该算法已开源于VieCut，在真实图上比之前最快求解器快1.25倍（串行）至12.9倍（并行）。本文引入代理式算法工程（AAE）方法，让自主的大语言模型代理在现有代码库中循环执行算法优化：提出性能瓶颈假设、实现修改、在固定实例集上基准测试，并保留或丢弃变更。尽管算法已经过人工深度调优，代理仍发现显著优化，尤其在DIMACS核心实例上：真实世界k-cores上分别提速1.28（串行）与1.63（32线程），在DIMACS核心实例上提速6.26与127倍。
原文摘要 · Abstract (English)
The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last years, we engineered a range of fast algorithms for this problem. Our fastest exact algorithm uses an inexact algorithm to obtain a better bound for the problem, reductions that depend on this bound, improved data structures and parallel contraction routines. It is available in the open-source package VieCut and, on real-world instances, outperformed the previously fastest solvers by a factor of up to 2.5 sequentially and up to 12.9 when run in parallel. We improve this algorithm using agentic algorithm engineering (AAE), a methodology that we introduce here, in which autonomous large language model agents run the algorithm engineering cycle on an existing code base: they form hypotheses about where running time is lost, implement them, benchmark the result on a fixed instance set and keep or discard the change. Even though we had already tuned our algorithm by hand extensively, the agent finds significant optimizations, in particular on the DIMACS core instances: factors of 1.28 (sequential) and 1.63 (32 threads) on real-world k-cores, and 6.26 and 127 on the DIMACS core instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。