智客 ZICQ
EN 登录 / 注册
智客前沿 智能体 #SailSearch #AI智能体 #组合优化 #Market Split #最大独立集

SailSearch双智能体为18个Market Split开放实例找到CPU可行解

Mr.Xu 的头像

文 / Mr.Xu 智客前沿编译 · 审校

发布时间:

中文阅读 (Chinese) English Version
共读互动 选中正文任意句子即可高亮划线、写下你的技术批注,或一键生成金句引用卡。 直达讨论区 ↓

摘要:SailSearch 提出一个由人类引导、两个语言模型智能体协作的组合优化研究工作流。在 Market Split 任务中,系统跨多个格基搜索,把计算分配给枚举与持续格基约化;在每个实例 10 个随机种子、双核 CPU 运行 24 小时的条件下,论文报告为 33 个原开放 QOBLIB 实例中的 18 个找到首个纯 CPU 解,每个种子解出 156 个基准中的 130 至 133 个。针对 MIS,作者把带 XOR 约束的图生成已知最优解的实例;7 个 1,752 至 3,996 顶点实例上,受测求解器 8 小时结果仍距最优 5 至 15 个顶点。智能体参与算法发现有潜力,但模型、成本、消融和最优性证明仍待核验。


核心结果

SailSearch 是一套由人类引导、两个语言模型智能体参与的组合优化算法研究工作流。其最强结果来自 Market Split:在双 CPU 核心、24 小时截止时间下,论文对每个实例运行 10 个随机种子,报告为 33 个此前开放的 QOBLIB 实例中的 18 个找到首个已报告的纯 CPU 可行解;不同种子对应的单次运行可解出 156 个基准中的 130 至 133 个。

这里的 solutions 不等同于已经证明最优。24 小时任务首先产生的是可行 incumbents,能解决一个实例代表找到满足约束的候选解,并不代表完成了最优性证明。CPU-only 也应准确理解:论文强调的是此前没有已报告的纯 CPU 结果,而不是这些实例从未存在 GPU、数学推导或其他形式的解。

工作流与技术机制

摘要确认该系统包含两个语言模型智能体与人类引导,但没有公开两个代理使用的模型、具体角色、通信协议或提示模板。最保守的工程抽象是:智能体参与算法或实现的迭代,执行器在真实基准上运行,人类根据中间结果调整研究方向,外部验证器检查输出是否可行。代理究竟负责搜索代码、提出数学推导,还是只承担实现与诊断,必须以论文正文和代码为准。

Market Split 的多格基搜索

Market Split 的经典求解路径与格基约化及枚举紧密相关。格基定义了搜索所处的整数坐标几何:枚举负责沿当前结构寻找候选划分,持续格基约化则改变坐标基,使后续搜索更可能覆盖有效区域。SailSearch 不依赖单一格基,而是在多个格基之间搜索,以减少一次糟糕基选择造成的搜索浪费。

多基搜索本质上构成一个随机 portfolio:每个基提供不同的枚举方向,持续约化则把计算从已经枯竭的区域移向更有希望的格空间。它增加命中高价值解的机会,但不会自动把问题变成多项式时间算法;枚举最坏情况仍可能随维度和候选空间急剧增长,反复约化也会消耗额外 CPU 时间。

若用 E_b 和 R_b 分别表示第 b 个格基上的枚举与约化工作,粗略预算模型为 W ≈ Σ_b(E_b + R_b)。在双核且有效并行效率为 η 时,理想墙钟时间约为 W/(2η);实际系统还会受到串行阶段、进程调度和存储访问影响。24 小时双核运行的名义上限是 48 核时,但论文没有披露实际 CPU 利用率、内存峰值或每个阶段的耗时比例。

MIS 实例生成与最优解认证

MIS 部分与 Market Split 的角色不同。作者把带 XOR 约束的组合结构编码成图,并构造已知且可认证的最优解。在 1,752 至 3,996 个顶点的 7 个实例上,受测求解器运行 8 小时后,最好结果仍比最优值少 5 至 15 个顶点。

这组结果主要证明现有求解器在特定 XOR 图结构上仍有明显最优性差距,并不表示 SailSearch 已经求出了这些 MIS 实例。带 planted structure 的生成器虽然能提供可靠的 ground truth,却也可能形成与真实业务图不同的难度分布,因此生成器价值与算法发现价值应分别评估。

工程权衡

SailSearch 的主要优势是把智能体放进一个带外部计算反馈的研究闭环。语言模型不必直接计算数千维格点,而可以提出、修改并通过执行结果修正搜索策略;确定性求解器承担数值计算,外部约束检查器承担正确性兜底。这种分工比让模型直接输出组合优化答案更可审计。

代价同样明显。人类在环能够纠正错误方向,却会引入不可量化的干预预算,并削弱完全自动化复现性。双核 CPU 降低了硬件门槛,但 24 小时运行仍意味着显著的累计算力;论文也没有报告模型调用次数、Token 消耗、API 成本或每次代理迭代的延迟。多格基策略用更多重复工作换取更低的坏种子风险,而持续格基约化与枚举争用同一资源时,调度策略会直接影响有效搜索深度。

此外,公开摘要没有给出内存占用。格基搜索通常不需要大模型推理那样的 GPU 显存,但不能据此推断其内存成本可以忽略;高维格基、枚举队列和并行进程仍可能产生可观开销。

评测可信度

评测设计有三项明显优点:QOBLIB 是外部公开基准,18 个此前开放实例提供了较强的新颖性信号;固定双核和 24 小时预算便于复现实验;10 个随机种子避免只报告偶然成功一次。

但当前材料不足以确认多项关键结论。论文摘要没有列出绝对目标值、距最优值 gap、可行性证明状态、对比求解器、CPU 型号、编译与格约化库配置,也没有报告双智能体相对单智能体、无智能体程序合成或随机程序搜索的匹配算力消融。因此无法区分收益究竟来自语言模型、随机多基策略、长时间 CPU 搜索,还是人类干预。

公平复现至少应设置三组基线:相同核时预算下的经典 Market Split 求解器;相同 seed 与核心小时数的随机程序或随机多基搜索;以及完整双智能体工作流。所有运行都应记录 incumbent 值、可行性状态、是否取得最优性证明和逐实例时间线。first reported 的优先权还需要独立核对 QOBLIB 状态更新记录,而不能只依据论文自述。

MIS 评测则需要补充不同 planted ratio、约束密度和随机图基线。7 个实例足以暴露求解器缺口,却不足以证明生成器在真实 MIS、调度图或生物网络上的代表性。

开发者落地建议

  1. 固定可复现环境。 锁定模型版本、temperature、system prompt、agent transcript、seed、CPU 型号、编译器与数学库版本、格基约化实现、超时策略及代码提交哈希。
  2. 使用独立验证器。 对 Market Split 划分逐项检查约束,对 MIS 候选检查图的独立集性质;不要仅接受智能体或求解器自身输出的可行性判断。
  3. 保存可恢复的搜索状态。 记录每个格基、约化版本、枚举节点、目标值和证明状态,使长时间任务能够断点续跑,并区分“找到可行解”与“证明最优”。
  4. 隔离代理生成的代码。 在沙箱中限制文件、网络和进程权限,固定依赖版本,并把代码执行、结果分析和最终合入分开。
  5. 按 anytime solver 使用。 将已验证 incumbent 持续写入外部存储并配套超时回退策略;在没有证书时,不要把启发式解包装成精确答案。
  6. 先做匹配预算消融。 在自有实例上同时运行无代理、单代理、双代理和纯随机多基版本,以核验智能体是否真的提高单位 CPU 小时的解质量。

结论

SailSearch 最有价值的信号,是智能体并非在抽象地讨论组合优化,而是通过代码、格基搜索和外部基准反馈参与算法发现,并把双核 CPU 时间转化为此前开放实例上的可行解。不过,当前证据仍支持将其视为研究原型,而非已经验证的自主优化系统或最优性证明器。


消息来源:ArXiv AI (cs.AI) (2026-11-20)

—— 完 ——

主题标签: #SailSearch #AI智能体 #组合优化 #Market Split #最大独立集

编辑部与事实核查说明:本篇专刊由智客前沿资讯管线根据官方技术公告、学术论文及开源工程文档整理编译,经算法实体核验与人工编辑审校后发布。若发现技术事实纰漏,欢迎依据勘误方针或一键向编辑部发送勘误反馈。

读完这篇,你的第一判断是?
🚀 去【作品】晒出你的相关实践

社区整体评论区

正在加载实时智能评论与划词标注…