基于分布感知的算法设计与LLM代理

# 基于分布感知的算法设计：利用LLM智能体

**来源：** https://arxiv.org/html/2605.14141

**Saharsh Koganti** 德州农工大学 saharshk11@tamu\.edu  
**Priyadarsi Mishra** 德州农工大学 priyadarsimishra@tamu\.edu  
**Pierfrancesco Beneventano** 麻省理工学院 pierb@mit\.edu  
**Tomer Galanti** 德州农工大学 galanti@tamu\.edu

###### 摘要

我们研究当学习对象是可执行的求解器代码而非预测器时如何进行学习。在这一设定中，正确性是不够的：两个求解器在部署分布上可能都返回有效解，但运行时间却相差巨大。给定来自未知任务分布的样本，学习器返回的代码需要通过解的质量和执行时间来评估在新的实例上的表现。我们的核心抽象是**求解器提示**：从样本中推断出的可重用结构，并被编译到专门的求解器代码中。我们证明，在固定的求解器库中，经验上最快的样本一致性求解器在正确性和运行时间上都能泛化，并且统计上可识别的提示可以从多项式数量的样本中恢复并编译成代码。在实验上，我们使用LLM代码智能体，在七个问题类别中的21个结构化组合优化目标分布上实例化了该框架。合成的求解器达到了平均归一化质量0.971，比平均启发式池提高了+0.224，比质量最好的启发式提高了+0.098，并且分别比质量最佳启发式、Gurobi和所选的有时间限制的精确后端快336.9倍、342.8倍和16.1倍。在已发布的PACE 2025支配集私有实例上，合成的求解器在所有100个图上都有效，运行速度比顶级比赛求解器快约两个数量级，质量差距适中。检查发现，许多增益来自于改变计算规模：用编译后的特定于分布的计算替换了环境指数级搜索或通用优化。

## 1 引言

经典学习理论（Valiant, 1984 (https://arxiv.org/html/2605.14141#bib.bib33); Vapnik and Chervonenkis, 1971 (https://arxiv.org/html/2605.14141#bib.bib38); Vapnik, 1998 (https://arxiv.org/html/2605.14141#bib.bib39)）主要围绕正确性和泛化展开。但当学习对象是**可执行程序**（Singhal等人，2025 (https://arxiv.org/html/2605.14141#bib.bib37)），例如算法、求解器或代码时，正确性只是目标的一部分。两个程序在部署分布上可能都返回有效解，但运行时间却相差巨大。在这种情况下，它们的学习程度并不相同。学习对象不仅要在质量上泛化，还要在计算上泛化。我们通过**分布感知的程序学习**来研究这一点：从未知的部署分布样本中，学习器返回的求解器代码通过解的质量和运行时间来评估在新鲜实例上的表现。对于决策问题，质量即是正确性；对于优化问题，质量衡量与最优解的接近程度。目标不仅仅是解决一般的环境问题类别，而是要学习一个专门针对目标场景的算法。

我们的核心抽象是**求解器提示**：从样本中推断出的可重用结构，并被编译到求解器代码中。提示可以是SAT中的后门、图问题中的潜在分解、包装问题中的活动资源模式，或路由问题中的几何结构。因此，从样本到求解器的映射可以分解为：  
S ⟼ ĥ_S ⟼ ĉ_S = Comp(ĥ_S)。  
这个分解也是我们解释LLM合成的方式。智能体最好不被视为一次性编写求解器；它提出结构假设，从样本中估计可重用的摘要，并根据这些摘要编写部署求解器。

求解器提示是计算捷径。例如，在SAT中，提示可能是一个可重用的后门集。正确性不需要学习：一个完整的求解器总可以当作后备方案。样本学习的是编译哪个捷径，以便未来的实例能更快求解。正确性与学习到的计算之间的这种分离，是我们理论和实验的核心。

这个框架连接了复杂性理论中一个长期存在的问题：一个问题**平均**困难意味着什么？最坏情况复杂性有一个清晰的主要对象——语言，但平均情况复杂性（Levin, 1986 (https://arxiv.org/html/2605.14141#bib.bib40); Impagliazzo, 1995 (https://arxiv.org/html/2605.14141#bib.bib41); Bogdanov and Trevisan, 2006 (https://arxiv.org/html/2605.14141#bib.bib42)）还需要一个分布。在实践中，部署分布往往缺乏适合经典分析的闭式描述。平滑分析（Spielman and Teng, 2004 (https://arxiv.org/html/2605.14141#bib.bib43)）、参数化复杂性（Downey and Fellows, 2013 (https://arxiv.org/html/2605.14141#bib.bib44)）和结构化后门（Williams等人，2003 (https://arxiv.org/html/2605.14141#bib.bib45)）各自提供了手动设计的途径来实现特定分布的可处理性。我们提出一种互补的构造性途径：将分布视为仅通过样本可访问，直接针对它学习一个求解器，并将学习到的求解器作为特定分布可处理性的见证。

**贡献。** 在本文中，我们做出以下贡献：

1. 我们引入了**分布感知的程序学习**：一种设定，其中学习对象是可执行的求解器代码，成功通过解的质量和部署运行时间来衡量。关键抽象是**求解器提示**，即从样本中推断出的分布特定结构的可重用描述，并被编译到专门的求解器代码中。
2. 我们形式化了样本何时能够改善计算。对于固定的求解器库，经验上最快的样本一致性求解器在正确性和运行时间上都能泛化。对于结构化的提示类，统计上可识别的提示可以从多项式数量的样本中恢复并编译成专门的求解器。一个隐藏的SAT后门模型使机制具体化：后备方案保证正确性，而恢复的提示在部署分布上实现每个实例的指数级加速。
3. 我们用LLM合成方法实例化了从样本到提示再到求解器的观点，其中每个候选解包括一个分布假设、一个训练时分析程序和一个部署求解器。在21个结构化组合优化目标分布上，合成的求解器达到平均归一化质量0.971，比平均启发式池提高了+0.224，比质量最好的启发式提高了+0.098，并且分别比质量最佳启发式、Gurobi和所选的有时间限制的精确后端快336.9倍、342.8倍和16.1倍。
4. 我们检查了合成的求解器，发现许多增益来自于改变计算规模：生成的代码通常用低阶的、特定于分布的计算替换了环境指数级搜索或完整的通用优化。作为外部诊断，在已发布的PACE 2025 (https://arxiv.org/html/2605.14141#bib.bib72) 支配集私有实例上，合成的求解器在所有100个图上都返回有效解，运行速度比顶级比赛求解器快约两个数量级，质量差距适中。

```
访问 D → 学习到的表示 → 部署求解器
最坏情况算法设计：无（对D的最坏情况），算法具有最坏情况保证
平均情况复杂性：分析指定D，算法针对D调优
本文：样本 S ~ D^n，学习器输出求解器提示 ĥ_S ∈ H，编译器生成求解器 ĉ_S ∈ C
有效类：Comp(H) ⊆ C
```

**图1:** 针对分布 D 设计求解器的三种访问模型。最坏情况设计假设无分布信息，而平均情况复杂性假设 D 的分析规格。我们研究中间的样本访问机制：从 S ~ D^n，学习器推断求解器提示 ĥ_S ∈ H，并将其编译为部署求解器 ĉ_S = Comp(ĥ_S)。因此，有效搜索空间是结构化子族 Comp(H) ⊆ C。我们的智能体近似这个样本到提示再到求解器的映射。

## 2 相关工作

我们将**执行运行时**视为泛化的一部分，当学习对象是可执行的求解器代码时。已有几个成熟的文献涉及这一图景的部分内容。因此，我们窄化地定位贡献：主要的新颖之处不在于数据可以改善计算这一宽泛的想法，而是明确的**样本 → 提示 → 求解器**形式化以及围绕它构建的理论加基准测试包。

**平均情况和超越最坏情况分析。** 平均情况复杂性（Levin, 1986 (https://arxiv.org/html/2605.14141#bib.bib40); Impagliazzo, 1995 (https://arxiv.org/html/2605.14141#bib.bib41); Bogdanov and Trevisan, 2006 (https://arxiv.org/html/2605.14141#bib.bib42)）探讨了问题在输入分布下何时变得可处理，但通常需要在分析开始前有一个分析性分布。平滑分析（Spielman and Teng, 2004 (https://arxiv.org/html/2605.14141#bib.bib43)）、参数化复杂性（Downey and Fellows, 2013 (https://arxiv.org/html/2605.14141#bib.bib44)）和SAT后门分析（Williams等人，2003 (https://arxiv.org/html/2605.14141#bib.bib45)）各自提供了手动设计的途径来实现特定分布的可处理性。我们的框架是互补且基于样本的：部署分布通过样本访问，学习到的求解器充当该场景可处理性的构造性见证。

**算法选择、组合和超启发式。** 最接近的经典路线是算法选择（Rice, 1976 (https://arxiv.org/html/2605.14141#bib.bib1)）和基于特征的组合，如SATzilla、Hydra和AutoFolio（Xu等人，2008 (https://arxiv.org/html/2605.14141#bib.bib2)，2010 (https://arxiv.org/html/2605.14141#bib.bib3); Lindauer等人，2015 (https://arxiv.org/html/2605.14141#bib.bib4); Kotthoff, 2014 (https://arxiv.org/html/2605.14141#bib.bib6); Kerschke等人，2019 (https://arxiv.org/html/2605.14141#bib.bib5)）。我们的固定库机制在精神上相近：一旦给定求解器库，为部署实例选择最佳成员。更广泛的相邻文献研究超启发式和自动化启发式设计，其目标是为优化问题族选择、组合或生成启发式。这些路线已经表明数据可用于减少运行时间。我们的主要对象更窄且更具结构性：从样本推断出的可重用求解器提示，编译成求解器代码，可能产生任何预定义库中不存在的求解器。

**学习增强算法、自适应计算和摊销。** 我们的部署标准符合那些认为最坏情况复杂性对于实际性能过于粗糙的研究（Roughgarden, 2019 (https://arxiv.org/html/2605.14141#bib.bib7)），以及学习增强算法，其中预测或建议修改固定算法的行为，同时当建议不准确时保持鲁棒性（Lykouris and Vassilvitskii, 2018 (https://arxiv.org/html/2605.14141#bib.bib9); Mitzenmacher and Vassilvitskii, 2022 (https://arxiv.org/html/2605.14141#bib.bib10)）。共同动机是数据可以帮助计算。不同之处在于学习对象：这些工作从一个固定的算法模板开始，研究建议如何改变其行为，而我们则探讨样本是否能揭示一个可重用的提示，编译成**不同的可执行求解器**。该框架也可以被解读为摊销：不是为每个实例支付推理时计算，而是针对样本支付一次合成成本，然后部署一个每个实例成本更低的求解器。

**程序合成、草图和代码智能体。** 我们的合成机制与从示例或自然语言进行程序合成相联系（Gulwani, 2011 (https://arxiv.org/html/2605.14141#bib.bib78); Balog等人，2017 (https://arxiv.org/html/2605.14141#bib.bib24); Devlin等人，2017 (https://arxiv.org/html/2605.14141#bib.bib25)），并且在精神上最接近学习搜索的中间引导（如草图）而非预测完整程序的工作（Nye等人，2019 (https://arxiv.org/html/2605.14141#bib.bib26)）。它也与代码生成和智能体编码基准相关（Hendrycks等人，2021 (https://arxiv.org/html/2605.14141#bib.bib27); Li等人，2022 (https://arxiv.org/html/2605.14141#bib.bib28); Jimenez等人，2024 (https://arxiv.org/html/2605.14141#bib.bib30); Huang等人，2024 (https://arxiv.org/html/2605.14141#bib.bib31)）。我们的贡献不是发起自动化启发式设计或智能体代码生成。相反，我们通过分布感知程序学习的视角重新诠释了这类系统的一个重要场景：运行时是目标的一部分，中间对象是求解器提示，并且实证研究的设计使得恢复的结构假设在合成后可以被检查。

## 3 问题设置

我们研究当学习对象是可执行求解器且部署标准包括运行时时的学习。经典统计学习通过准确性衡量泛化：一个假设如果在来自D的新样本上表现良好，就是好的（Valiant, 1984 (https://arxiv.org/html/2605.14141#bib.bib33); Vapnik and Chervonenkis, 1971 (https://arxiv.org/html/2605.14141#bib.bib38); Vapnik, 1998 (https://arxiv.org/html/2605.14141#bib.bib39)）。对于求解器，准确性是不完整的。两个求解器可能在同一个部署分布上都返回有效解，但运行时间却相差巨大。因此，我们问一个学习器如何能从样本中识别出一个计算专门针对D的求解器。这将问题置于最坏情况分析和平均情况分析之间。最坏情况设计假设无分布信息，而平均情况复杂性假设一个分析性分布。我们研究样本访问机制：给定来自未知部署分布的S = (x_1, ..., x_n) ~ D^n，学习器为来自相同D的未来实例返回求解器代码。

形式上，让X成为实例空间，V(x, z) ∈ {0,1}指示z是否是x的有效解。求解器c ∈ C是一个映射x ↦ c(x)的程序，执行时间为T(c,x) ∈ R_{≥0}。我们通过部署误差Err_D(c) := Pr_{x~D}[V(x,c(x))=0]和期望部署运行时间Run_D(c) := E_{x~D}[T(c,x)]来评估c。正确性是一个可行性约束：在满足Err_D(c)=0的求解器中，两个求解器在Run_D(c)上可能任意不同。对于求解器类C，定义类相对分布感知运行时最优值为Run_D^⋆(C) := inf_{c∈C: Err_D(c)=0} Run_D(c)。这是t