基于大语言模型的数据驱动动态算法调度

# 基于大语言模型的数据驱动动态算法调度
来源：https://arxiv.org/html/2608.21584
## 基于大语言模型的数据驱动动态算法调度
致谢：本材料基于美国国防部高级研究计划局（DARPA）资助的项目，协议编号为 HR00112490488。

Rushil Shah
单位：美国麻省理工学院计算机科学与人工智能实验室
邮箱：[email protected]
[email protected]
[email protected]
[email protected]
Emmanuel Lujan
单位：美国麻省理工学院计算机科学与人工智能实验室
Rabab Alomairy
单位：美国麻省理工学院计算机科学与人工智能实验室
Alan Edelman
单位：美国麻省理工学院计算机科学与人工智能实验室

###### 摘要

我们提出了一种由大语言模型驱动的方法，用于在高性能线性代数中生成动态算法调度启发式策略。通过结合提示工程、LLaMA 3 模型以及一个精心整理的性能数据库，该模型学习合成选择启发式策略，利用结构模式来识别快速的算法选择。一项针对 LU 分解的案例研究展示了该模型复现专家设计策略的能力。这项工作是 DARPA-MIT SmartSolve 项目的一部分，突显了 LLM 在算法发现以及开发更自适应、更快速的线性代数软件方面的潜力。

###### 索引术语：

大语言模型、LLM、Pareto 分析、动态算法调度、LU 分解、线性代数。

## I 引言

针对经典线性代数算法的专用变体已被开发出来，以利用输入数据的结构模式，通常能显著提升性能。一个关键例子是矩阵分解，其中选择合适的策略可能对求解线性系统、计算特征值以及执行统计估计的效率产生关键影响。在这些方法中，LU 分解因其能够将问题简化为三角求解而被广泛使用。像带状 LU 和 KLU[1 (https://arxiv.org/html/2608.21584#bib.bib1)]这样的变体专门设计用于利用数据属性（如稀疏性和块模式），相比密集或通用方法，实现了显著的速度提升和内存节省。

当前的数值软件——包括 Julia、Python 和 MATLAB 中的软件——都内置了启发式规则来指导算法调度。随着矩阵结构模式和求解器设计日益多样化[2 (https://arxiv.org/html/2608.21584#bib.bib2)]，这些规则面临越来越多挑战，因此存在大量优化机会。随着针对不同矩阵的研究不断引入专用算法，依赖手工设计的启发式规则变得越来越困难。

为解决这一挑战，DARPA-MIT SmartSolve 项目[3 (https://arxiv.org/html/2608.21584#bib.bib3)]提出了一个基于 Julia 的框架，旨在通过生成优化算法和架构选择的动态调度启发式策略来加速计算。SmartSolve 方法应用于线性代数时，首先从一个发现过程开始，该过程系统地评估各种算法——如前述的带状 LU 和 KLU——在来自 Matrix Depot[5 (https://arxiv.org/html/2608.21584#bib.bib5)]的多样化矩阵模式（如 Hilbert、Vandermonde 和 Toeplitz）上的表现，同时考虑多种数据格式、混合精度策略和计算机架构。对于每种组合，收集各种指标，包括矩阵模式的特征（如维度、稀疏性和条件数）以及性能指标（如类型转换开销、计算运行时间和数值精度）。这些测量结果被聚合到一个性能数据库中。然后，自动化的 Pareto 分析识别速度与精度之间的最佳权衡[6]。生成的数据库用于训练一个数据驱动模型，该模型根据输入矩阵生成选择算法和架构最佳组合的启发式策略。这些新开发的启发式策略旨在提高现代线性代数库（如在 Julia 中提供线性求解算法快速实现的 LinearSolve.jl）的性能。

大语言模型可以作为识别基准数据模式并合成决策逻辑的强大机制。早期的项目如 ChatHPC 表明，LLM 可以生成高性能的数值代码，甚至提出新颖的优化策略[4, 5]。最近，Google Deepmind 发布了 AlphaEvolve[4 (https://arxiv.org/html/2608.21584#bib.bib4)]，这是一个用于发现和优化通用算法的 LLM 代理。它设计了一种仅用 48 次标量乘法实现 4×4 复数矩阵乘法的方法——比 Strassen 1969 年的算法少一次，标志着半个多世纪以来的首次已知改进。

在此，我们介绍我们在 SmartSolve 项目中的最新进展：一种用于动态算法调度的 LLM 驱动方法。

我们的主要贡献如下：(1) 一种 LLM 驱动的方法，用于自动生成针对计算线性代数的动态算法调度启发式策略。

(2) 一个使用 LLaMA 3 重新发现 LU 分解调度启发式策略的案例研究，该策略适用于 MatrixMarket.jl 提供的广泛矩阵。通过这些贡献，我们旨在将 SmartSolve.jl 框架扩展到传统基于机器学习的策略之外。

## II 方法

如图 1 [https://arxiv.org/html/2608.21584#S2.F1] 上半部分所示，我们的方法利用提示工程来指导 LLM 生成动态算法调度启发式策略。

图片说明

图 1：我们生成线性代数中动态算法调度启发式策略的 LLM 驱动方法概述。提示设计遵循三个通用准则：(1) 首先向模型提供其角色和目标的明确描述。例如，指示 LLM 充当矩阵分解专家有助于将其推理限制在相关领域，并促进更专业的回应。(2) 将包含各种算法基准测试结果的 SmartSolve.jl 性能数据库作为提示的一部分。这使模型获得了超出其原始训练语料库的信息，使其能够学习输入矩阵特征与算法性能之间的相关性，从而有助于生成有依据的调度启发式策略。(3) 要求 LLM 根据定义的输出格式，使用数据库生成所需的启发式策略。指示 LLM 使用 if/else 语句生成树状调度算法，以增强人类可解释性。这对于缓解 LLM 输出的变异性至关重要，否则可能会包含不一致的格式或引用数据集之外的算法。

最后，如图 1 [https://arxiv.org/html/2608.21584#S2.F1] 下半部分所示，生成的启发式策略将输入矩阵的特征映射到可用的最高效算法。该启发式策略最终旨在集成到现代线性代数系统中，例如 Julia 的 LinearSolve.jl。

## III 结果与讨论

我们的案例研究重点在于使用我们的 LLM 驱动方法重新发现 SmartSolve 的一个基于 LU 的动态调度启发式策略。首先使用 SmartSolve.jl 生成一个全面的性能数据库，该数据库在结构多样的矩阵上对多种 LU 分解策略（包括密集、稀疏和带状求解器）进行基准测试。然后应用自动化的 Pareto 分析来识别在运行时间和数值精度之间实现最佳权衡的配置。如图 2 [https://arxiv.org/html/2608.21584#S3.F2] 所示，带部分选主元的密集 LU 算法（xGETRF）表现出更高的计算成本。通过将矩阵转换为稀疏表示并利用专用求解器（如非对称多前端法（UMFPACK）、KLU 或带状 LU 分解（xGBTRF）），可以在计算成本的一小部分内达到相当的精度。

生成的 Pareto 最优选择随后用于指导 LLM 生成所需的启发式策略。此处呈现的结果是使用双精度计算获得的。

图片说明

图 2：LU 在 2122^{12}x2122^{12} Poisson 矩阵上的时间和精度权衡，用于指导 LLM 生成的调度启发式策略。提示是按照 II [https://arxiv.org/html/2608.21584#S2] 节中概述的准则构建的。对应准则 (1) 和 (3) 的部分——为任务提供上下文信息和输出约束——可能广泛适用于更广泛的算法类别，包括 QR 分解、SVD 和 FFT。相比之下，与准则 (2) 相关的部分则特定于为目标算法生成的性能数据库。该案例研究在一个基于 Julia 的笔记本中实现，使用了通过 Ollama v0.9.4 的 7B Mistral v0.3。代码在 SmartSolve.jl GitHub 仓库中公开提供[3 (https://arxiv.org/html/2608.21584#bib.bib3)]。

我们的结果证明成功重新发现了所需的 LU 调度启发式策略。然而，虽然模型能够产生有意义的决策逻辑，但其固有的统计特性可能导致输出存在变异性。因此，通常需要进行迭代细化——例如提示重新措辞或多轮生成——才能获得可靠的结果。另一点需要考虑的是，提示工程受限于模型预训练知识的有限输入空间。微调可以通过调整模型的内部参数来内化大规模性能数据库，从而缓解这些限制，提供更具可扩展性的解决方案。

本研究为 LLM 在生成动态算法调度启发式策略方面的可行性提供了证据，同时强调了关键局限性——即其概率性导致的变异性和提示大小限制。

我们期望这能影响更快线性代数软件的设计，并催化 SmartSolve.jl 等框架的创新。

## 参考文献

- [1](2010)Algorithm 907: klu, a direct sparse solver for circuit simulation problems. ACM Trans. Math. Softw. 37(3). 外部链接: ISSN 0098-3500, [Link (https://doi.org/10.1145/1824801.1824814)], [Document (https://dx.doi.org/10.1145/1824801.1824814)] 引用于: §I [https://arxiv.org/html/2608.21584#S1.p1.1].
- [2]X. S. Li (2005) An overview of SuperLU. ACM Trans. Math. Softw. 31(3), pp. 302–325 (en). 引用于: §I [https://arxiv.org/html/2608.21584#S1.p2.1].
- [3]E. Lujan, R. N. Shah, R. Alomairy, and A. Edelman (2025) SmartSolve.jl: ai for algorithmic discovery. Zenodo. 外部链接: [Document (https://dx.doi.org/10.5281/zenodo.15784217)], [Link (https://doi.org/10.5281/zenodo.15784217)] 引用于: §I [https://arxiv.org/html/2608.21584#S1.p3.1], §III [https://arxiv.org/html/2608.21584#S3.p3.1].
- [4]A. Novikov, N. Vũ, M. Eisenberger, E. Dupont, P. Huang, A. Z. Wagner, S. Shirobokov, B. Kozlovskii, F. J. R. Ruiz, A. Mehrabian, M. P. Kumar, A. See, S. Chaudhuri, G. Holland, A. Davies, S. Nowozin, P. Kohli, and M. Balog (2025) AlphaEvolve: a coding agent for scientific and algorithmic discovery. 外部链接: 2506.13131, [Link (https://arxiv.org/abs/2506.13131)] 引用于: §I [https://arxiv.org/html/2608.21584#S1.p4.1].
- [5]W. Zhang and N. J. Higham (2016) Matrix depot: an extensible test matrix collection for julia. PeerJ Computer Science 2, pp. e58. 引用于: §I [https://arxiv.org/html/2608.21584#S1.p3.1].