Vulcan：通过 LLM 驱动搜索实现实例最优的系统启发式算法

论文信息

标题: Vulcan: Instance-Optimal Systems Heuristics Through LLM-Driven Search

作者: Rohit Dwivedula, Divyanshu Saxena, Sujay Yadalam, et al.

发布日期: 2025-12-31

arXiv ID: 2512.25065v1

PDF 链接: 下载 PDF

3 分钟速览

研究问题：现代操作系统和分布式系统中的缓存、调度、内存管理等任务极度依赖手工设计的启发式算法，这些算法无法适应不断变化的硬件、工作负载和环境，手工重设计成本高昂且耗时。
核心方法：提出 Vulcan 框架，将政策（决策逻辑）与机制（底层实现）分离，把启发式设计转化为对 Value 或 Rank 接口下 LLM 驱动的代码生成与进化搜索。
关键结果：在缓存淘汰任务中，Vulcan 合成的策略在多个实例上最高超越现有最优人工算法 69%（见论文图 8）；内存分层场景下性能提升 2.5‑7.9%（见论文图 11）。
主要局限：搜索空间受限于预定义的 Value/Rank 接口，机制实现仍需人工搭建；进化搜索依赖离线评估器，可能与生产环境存在偏差；论文未讨论策略在极端安全或实时场景下的可靠性。
适合读者：从事系统资源管理、缓存设计、内存分层，或希望将 LLM 应用于自动化搜索的工程师和研究人员。

论文背景和研究动机

资源管理是系统软件的核心，但数十年来的实践表明：不存在一种通用的最佳启发式。比如缓存淘汰，不同的工作负载、缓存大小、硬件配置下，最优算法各不相同（论文图 1 显示在 CloudPhysics 数据集的 106 条 trace 中，没有单一算法能在超过半数 trace 上夺冠）。同样，拥塞控制算法需要针对互联网和数据中心各自调优，内核队列规则、集群调度器也被迫不断适配新的场景。每一次环境变化，开发者都不得不手工重新设计或调整启发式，而这个过程既耗时又昂贵。

更棘手的是，现代系统已经不再追求 “万能” 算法，而是渴望实例最优 —— 为每一个具体的 “工作负载‑硬件” 组合定制策略。然而手工实现这种定制化根本不现实。此前，基于神经网络的策略虽能自动学习，却引入不透明性、高推理延迟与复杂的部署管道，难以在性能敏感的核心路径上落地。

大语言模型（LLM）的出现带来了新的可能：将启发式搜索视为代码生成问题。但直接让 LLM 生成完整的系统启发式代码会遭遇政策与机制深度耦合的困境：Linux 的 CFS 调度器政策与红黑树机制绑定，现代缓存的 FIFO‑重插入、S3‑FIFO 等算法涉及复杂的状态变迁。LLM 目前难以在如此复杂的机制代码中保持正确性（论文 §2.3 给出多函数、状态化代码生成的困难）。因此，核心挑战变为：如何发挥 LLM 在表达高层决策逻辑上的优势，同时避免让它去实现繁复的低层机制。

核心方法和技术细节

Vulcan 的解决方案是以接口分离政策与机制，将搜索空间压缩为一个纯函数。它引入两种通用接口：

Value 型：输入一组系统状态特征 $X$ ，计算并返回一个数值（如拥塞窗口大小、CPU 频率、副本数）。
Rank 型：输入一个对象集合及其特征，对每个对象打分，然后由外部机制完成排序并选出 top‑K（如选择要淘汰的缓存对象、要提升的内存页）。

这一分离使得 LLM 只需生成一个无状态的打分函数 value(X) 或 score(X, obj)，而所有复杂的数据收集、队列维护、迁移操作都由用户编写的脚手架（scaffolding）负责（论文图 4）。Vulcan 对打分函数的正确性要求极低：任何返回实数的函数都是合法的策略，只是性能好坏不同，从而避免了传统代码生成中常见的崩溃错误。

用户通过三个步骤启动 Vulcan：

选择接口并搭建脚手架：确定任务是 Value 还是 Rank，提供系统状态特征、对象元数据，并实现决策后的动作逻辑（例如设置带宽、执行淘汰）。对于 Rank，脚手架还提供排序机制的选择 ——FullSort（全排序）、SampleSort（采样排序以减少开销）或 PriorityQueue（增量更新优先级队列）。
定义实例：实例是 “工作负载‑硬件” 的具体组合。可以人工指定，也可以通过 Vulcan 的自动实例生成器来划分。论文在缓存案例中，对 CloudPhysics 的 106 条 trace 提取 15 维特征，用 KMeans 聚类得到 10 个实例（ $C_0$ – $C_9$ ），每个实例代表一类相似访问模式。
启动进化搜索：提供描述目标和可用特征的自然语言模板，以及一个评估器（如缓存模拟器或真实硬件上的测试床）。搜索循环维护一个候选策略库，每轮用 LLM（如 GPT‑4o‑mini）基于历史优秀策略生成一批新代码，编译成政策模块，交由评估器打分，高分策略进入下一轮。这个过程反复进行，直到性能收敛或满足要求。

评估器的选择需要在速度与保真度之间权衡：基于缓存模拟器 libcachesim 能在几毫秒内完成一次评估，支持数百次迭代；而内存分层实验在真实 CXL 模拟节点上跑完整应用，单次评估需要数十秒，计算成本更高，但也更贴近实际。论文为每个任务专门设计了优化目标，例如 Silo 数据库的目标是同时最大化吞吐与最小化延迟。

创新点和贡献

Vulcan 的最大贡献在于重新定义了系统启发式设计的范式：从手工编织机制与政策的耦合体，变为 LLM 在严格的、机制无关的接口下搜索单纯的政策逻辑。这带来三方面优势：

降低自动化门槛：将策略搜索限制为一个无状态函数，使得即使是小型的廉价 LLM（如 GPT‑4o‑mini）也能稳定生成可执行、可编译的代码，无需复杂的代理或代码库遍历。
保持系统性能与安全性：生成的启发式是简洁的 C++ 或 eBPF 代码，不包含任何神经网络推理，因而在关键路径上不会引入不可预测的开销，完全透明可审计，避免了传统 ML‑for‑systems 方案的黑盒风险。
实现真正的实例最优：由于每次搜索成本极低（缓存搜索每实例仅消耗几十次 API 调用，内存分层整个 150 次迭代总成本约 $37），Vulcan 使为每个微小的环境变化（如缓存容量比例、访问模式漂移）定制策略变为经济可行。

此外，论文通过 LLM 辅助的文献调查（扫描 2021‑2025 年 OSDI 和 NSDI 共 660 篇论文），发现约 5 篇中就有 1 篇的核心资源管理任务可抽象为 Value 或 Rank 形式，表明这两种接口的普适性（见附录 A）。

实验结果分析

缓存淘汰（§4）。在 Rank 接口下，使用 PriorityQueue 机制，Vulcan 为 10 个聚类分别搜索了专用的淘汰打分函数。与 S3‑FIFO、SIEVE、GDSF 等 13 个基线相比，Vulcan 策略在多个集群上实现最高 69% 的命中率提升（ $C_2$ 集群），在 $C_1$ 、 $C_3$ 上分别领先 21.4% 和 1.94%。在所有集群中，它要么性能第一，要么紧随 GDSF 之后排名第二或第三（见图 8）。

论文进一步探索了高效队列拓扑（§4.2）：将缓存策略限制为至多 5 个 FIFO/LRU 队列及对象迁移规则。这样，策略实现仅需常数时间操作，天然适合高吞吐场景。Vulcan 在此空间中为 $C_7$ 和 $C_8$ 搜索到的拓扑在对象命中率上分别比所有 17 个基线高出 1.0%（对比 TwoQ）和 3.2%（对比 S3‑FIFO），证明即使在受限搜索空间内，自动化设计也能超越精心手工调校的结构。

内存分层（§5）。以 ARMS 为基线，Vulcan 搜索的页面热度评分函数为 GUPS、GapBS（BC/PR）、Silo 四个应用带来 2.5‑7.9% 的性能改进。进化搜索在 150 次迭代内即收敛，并且仅需 $37 的 API 费用。生成的代码体现了对工作负载特性的自适应：如 GUPS 策略对 NVM 带宽饱和施加额外惩罚（论文 Listing 1），而 Silo 策略检测访问的突发性并降低此类页面的提升优先级（论文 Listing 2），这些逻辑是 ARMS 固定系数所不具备的。

实践建议

对于希望在自己的系统中采用 Vulcan 的工程师，建议遵循以下路径：

任务建模：首先判断核心资源决策属于 Value 还是 Rank。绝大多数调度、缓存、准入控制都可归入这两类。明确可用的系统状态特征（如访问计数、最后使用时间、队列长度），并注意特征频度和延迟是否能在决策路径上及时获取。
机制解耦：实现数据收集与执行动作的脚手架，确保政策模块仅输出纯数值。对于 Rank 任务，可先采用 FullSort 保证排序精度，若性能评估表明开销过大，再替换为 PriorityQueue 或 SampleSort。务必为脚手架编写完整的回归测试，以确保 LLM 生成的任意数值都不会导致系统崩溃。
实例定义与评估器：使用自动化聚类（如 KMeans）或领域知识划分实例。构建评估器时，用高保真模拟器或真实测试床快速迭代，同时准备少量真实环境验证，防止模拟偏差。目标函数要清晰反映业务指标（延迟、吞吐、命中率），并考虑多目标赋权。
搜索执行：选择开源进化搜索框架（如 OpenEvolve 或 Policysmith），搭配廉价 LLM（GPT‑4o‑mini 即可胜任）。初始种群可手工提供几个简单基线（LRU、LFU），设置适当的迭代轮次和每轮生成数量（论文用 25 个候选，取前 2 保留）。注意监控生成代码的编译通过率和运行稳定性，及时剔除因幻觉造成的无效函数。
上线与监控：将搜索出的政策模块注入生产系统（C++ 编译、动态链接或 eBPF 加载）。部署后持续监控系统指标，一旦出现工作负载漂移，可重新触发离线搜索，实现策略的持续优化。

Vulcan 展现出的能力表明，通过精心设计的接口隔离，LLM 驱动的启发式搜索正在成为系统软件自动化的可行路径。即使没有深厚的机器学习背景，系统开发者也能以极低成本为各自的应用场景定制最优策略。