用大模型发现优化问题的分布规律,自动生成高效求解器。
Distribution-Aware Algorithm Design with LLM Agents
- 通过样本推断问题分布结构,生成可复用的求解提示。
- 合成求解器平均质量达0.971,速度比经典方法快数十倍。
- 适合需要快速求解同类问题的工业场景或竞赛应用。
许多优化问题反复出现于固定但未知的分布中。尽管最坏情况下的问题难以求解,但该分布可能蕴含可重复利用的结构,如共现几何、分解模式或资源特征。本文研究如何从样本实例中推断这些结构,并将其编译为在后续实例上运行更快且保持解质量的求解代码。核心抽象是「求解提示」:从样本中推断出的、针对特定分布的结构化信息,用于定制化求解器。我们证明,经验上最快的样本一致求解器在正确性和运行时间上均优于固定求解库,且可通过多项式数量的样本恢复可识别提示。我们在7类问题的21个组合优化分布上,使用大模型代码代理实现了该框架。合成求解器的平均归一化质量达0.971,相比传统启发式、Gurobi及限时精确求解器快数个数量级;相较单次生成的Codex、Claude Code及最佳5次采样变体,其速度更快,质量更高,接近Codex水平但显著更高效。在PACE 2025支配集私有数据集上,合成求解器在100个图上均有效,速度比发布求解器快约75至125倍,解大小仅相差几个百分点。结果表明,大模型代理能发现分布特异性计算捷径并编译为高效求解代码。
原文摘要 · Abstract (English)
Many optimization problems arise repeatedly from a fixed but unknown distribution. Even when the worst-case problem is hard, this distribution may carry reusable structure, such as recurring geometry, decompositions, or resource patterns. We study how to infer such structure from sample instances and compile it into solver code that runs faster on future instances while preserving solution quality. Our central abstraction is a \emph{solver hint}: distribution-specific structure inferred from samples and used to specialize a solver. We prove that the empirically fastest sample-consistent solver generalizes in both correctness and runtime over fixed solver libraries, and that identifiable hints can be recovered from polynomially many samples. We instantiate the framework with LLM code agents on $21$ combinatorial-optimization distributions across $7$ problem classes. The synthesized solvers reach mean normalized quality $0.971$ while running orders of magnitude faster than classical heuristics, Gurobi, and time-limited exact backends, though they do not dominate every baseline on every family. Against LLM synthesis baselines, they are faster than one-shot Codex, one-shot Claude Code, and a best-of-$5$ open-model variant; they improve quality over Claude Code and best-of-$5$, while nearly matching Codex quality and running substantially faster. This isolates the contribution of the iterative synthesis loop without claiming uniform domination over every LLM baseline. On the PACE 2025 Dominating Set private instances, the synthesized solver is valid on all $100$ graphs and runs roughly $75\times$--$125\times$ faster than released competition solvers, within a few percent of their solution size. These results suggest LLM agents can discover distribution-specific computational shortcuts and compile them into efficient solver code.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。