[控场AI]
· 4 分钟阅读· 2,347 字

Ballad:用多臂老虎机调度LLM,自动启发式发现成本降65.6%

Ballad:用多臂老虎机调度LLM,自动启发式发现成本降65.6%

Ballad用在线bandit编排多LLM做启发式搜索,追平最佳模型并省65.6%成本。

文章介绍了一项名为 Ballad 的研究,挑战了自动启发式发现(AHD)领域“更大更贵的 LLM 带来更好结果”的默认假设。研究发现,模型优劣在搜索过程中会漂移,且各模型输出互为上下文导致奖励非平稳、信号纠缠,经典在线决策算法难以直接适用。Ballad 用在线 bandit 算法将多个模型编排为集成体,通过偏好稀有高分的选择策略、基于 DAG 的信用传播和对陈旧观测的折扣三项机制应对上述挑战。在五个 NP-hard 组合优化问题上,Ballad 追平甚至超越事后最佳单一模型,同时相比始终调用最强模型的策略最多降低 65.6% 的 API 成本,为 AHD 工程实践提供了兼顾效果与成本的模型调度思路。

当“更强模型=更好结果”的假设被打破

在自动启发式发现(Automated Heuristic Discovery, AHD)领域,一个被广泛默认的前提是:调用参数更多、价格更贵的LLM,迭代出的启发式解质量会更高。但一项名为 Ballad 的研究直接挑战了这一直觉。

研究团队在多个NP-hard组合优化问题上做了系统对比,结论相当反直觉:更大、更贵的模型并没有表现出稳定优势。换言之,仅靠堆模型规格来提升启发式质量,性价比并不成立。这引出了一个更实际的问题——当手头同时有前沿闭源模型和免费/开源的权重模型时,如何根据搜索进程自适应地选择每一步该调用谁?

这个问题的难点在于两点。其一,最优模型并非固定不变,它可能在一次搜索的不同阶段发生漂移;其二,一次LLM调用的输出会成为后续调用的上下文,导致每个模型的奖励信号既非平稳、又彼此纠缠,直接破坏了经典在线决策算法所依赖的独立性假设。

Ballad论文来源截图

自动启发式发现(AHD) 是算法设计与优化领域的一个新兴方向:给定一个组合优化问题(如旅行商、装箱、调度),让大语言模型反复生成、变异和筛选启发式规则或求解策略,最终自动“进化”出高质量的解。与传统手工设计启发式相比,AHD 把 LLM 当作搜索算子,通过多轮迭代逐步逼近更优解。正因为每一轮都需要调用模型,模型选择直接决定了搜索的质量上限与 API 开销,这也是 Ballad 关注“用哪个模型、何时用”的根本原因。

NP-hard 组合优化问题 指不存在已知多项式时间精确算法的一类问题,规模稍大就无法穷举求解,实践中依赖启发式或近似算法。本文实验涉及的典型代表包括旅行商问题、车辆路径问题、装箱问题等。这类问题的特点是:解空间巨大、评价函数不连续,偶尔一次“跳出局部最优”的启发式改写就能带来显著提升。因此“稀有高分”比“平均稳定”更有价值,这也解释了 Ballad 选择策略的设计动机。

Ballad 的三项核心机制

针对上述非平稳、信号纠缠的挑战,Ballad 设计了一套在线bandit(多臂老虎机)算法,把一组LLM编排成一个集成体。其目标不是简单地在模型间轮换,而是让整体表现匹配甚至超越任何单一模型。具体由三个组件支撑:

1. 偏好稀有高分而非稳定均值的LLM选择策略

传统bandit策略往往倾向于奖励均值稳定的选项,但在启发式搜索中,真正有价值的是偶尔出现的高分样本。Ballad 的选择策略刻意偏向那些能产生“稀有且高分”启发式的模型,而不是被平均表现平庸但方差小的模型锁死。这更贴合AHD任务中“偶尔突破即胜利”的特性。

多臂老虎机(multi-armed bandit) 是强化学习与在线决策中的经典框架:面对 K 个选项(“臂”),每轮选择一个并观测奖励,目标是在“探索未知”与“利用已知”之间权衡,使累计奖励最大化。经典算法如 UCB、Thompson Sampling 通常假设各臂奖励独立同分布且平稳。Ballad 面临的场景打破了这一假设——奖励随搜索阶段漂移,且各模型的输出互为上下文导致信号相关,因此需要对经典 bandit 做非平稳化与信用归因改造。

2. 基于DAG的信用传播

由于每个启发式由前序调用演化而来,模型之间存在谱系关系。Ballad 用有向无环图(DAG)来追踪启发式种群的“家谱”,并将最终得分沿基因链条反向传播,把功劳合理地归因给早期做出关键贡献的模型,而不是只看最后一步调用的模型。

信用分配(credit assignment) 是序贯决策中的核心难题:当一条长期链路最终得到好或坏的结果时,如何判断哪一步贡献最大。在 AHD 中,一个启发式往往由前几轮 LLM 调用逐代演化而来,形成树状或图状的“家谱”。Ballad 用 DAG(有向无环图) 记录这种演化关系,再把最终得分沿边反向传播,使早期做出关键改写的模型也能获得奖励信号。若只奖励最后一步,早期贡献会被系统性低估,模型选择策略将逐渐失真。

3. 对陈旧观测的折扣

搜索过程中模型的有效性会变化,早先的奖励记录可能不再代表当前能力。Ballad 对旧观测施加折扣,让决策更关注模型近期的实际效用,从而跟上非平稳的奖励分布。

实验表现:追平最佳,还省下大量API成本

研究在五个NP-hard组合优化问题上验证了Ballad,模型池包含四个能力与成本各异的模型。结果有两个关键数字值得关注:

  • Ballad 的表现不仅追平了事后看来最好的单个LLM(hindsight最佳),在部分问题上还超越了所有单一模型;
  • 与“始终使用最强模型”的朴素策略相比,Ballad 将API成本最多降低了65.6%。

这说明在AHD场景里,模型调度的价值可能不亚于模型本身的能力。盲目调用最贵模型既不是效果最优解,也不是成本最优解。

对AHD工程实践的启示

这项研究给自动启发式发现的落地带来几个现实参考。第一,构建模型池比押注单一模型更稳健——尤其是把免费或开源权重模型纳入候选,可以在不牺牲效果的前提下压低成本。第二,调度策略要能处理“功劳归因”,否则早期模型的贡献会被埋没,学习信号失真。第三,非平稳性是常态而非例外,静态的模型偏好会随着搜索推进而过时。

Ballad 的意义在于把“用哪个模型”从经验判断变成了可学习的在线决策问题。对于需要反复调用LLM做搜索优化的团队,这提供了一条兼顾效果与成本的路径。

#Ballad#LLM路由#自动启发式发现#多臂老虎机#组合优化#模型调度#API成本优化
分享:

相关推荐