Ballad：基于多臂老虎机的 LLM 路由方法用于自动启发式发现
Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery
这篇论文很实在：跑 AHD 时贵模型不一定赢，用 bandit 动态挑模型，成本最多省 65.6% 还能超过单模型。做组合优化、进化搜索或者想省钱跑 LLM ensemble 的开发者都该看看。
论文提出 Ballad（Bandit-based LLM Routing for Automated Heuristic Discovery），一种在线多臂老虎机算法，用于在自动启发式发现（AHD）流程中动态选择调用哪个 LLM。作者首先用实验反驳了一个常见假设：在多个 NP-hard 组合优化问题上，更大、更贵的模型并没有稳定优势。
技术上，Ballad 的选择策略偏好罕见的、高分启发式结果而非稳定平均值，通过基于 DAG 的信用传播机制沿启发式种群的谱系回溯贡献，并对过期观测做折扣以跟踪各模型当前效用。由于一个 LLM 的输出会成为后续调用的上下文，奖励信号是非平稳且相互纠缠的，这违反了经典在线决策的独立性假设，是该算法要解决的核心难点。
在五个 NP-hard 组合优化问题上、混合 4 个能力与价格各异的模型时，Ballad 至少追平事后最优的单个模型，多个场景下超过所有单个模型，同时相比始终用最强模型最多降低 65.6% 的 API 成本。
Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery
Modern automated heuristic discovery (AHD) systems increasingly rival hand-crafted heuristics by leveraging Large Language Models (LLMs) to iteratively mutate and refine solutions. A natural assumption is that more powerful and more expensive models consistently yield better heuristics. We challenge this empirically: across multiple NP-hard combinatorial optimization problems, we find no consistent advantage for larger, costlier models. This raises a deeper question: given a pool of LLMs spanning frontier and freely hosted or open-weight models, how should one adaptively select which model to invoke at each step of the search? The challenge is non-trivial. The optimal LLM may shift over the course of a run, and because one LLM's output seeds the context for subsequent calls, each model's reward signal is non-stationary and entangled across the heuristic population, thus violating the independence assumptions of classical online decision-making settings. We address this through Ballad (Bandit-based LLM Routing for Automated Heuristic Discovery), an online bandit algorithm that learns to orchestrate a pool of LLMs into an ensemble that matches or exceeds what any soloist LLM achieves alone. This orchestration is powered by an LLM selection policy that favors rare, high-scoring heuristics over stable averages, a DAG-based credit propagation mechanism through the genealogy of the heuristic population, and discounting of stale observations to remain attuned to each model's current utility. Across five NP-hard combinatorial optimization problems and a pool of four models of varying capability and cost, Ballad not only matches the best individual LLM in hindsight but, in several cases, surpasses every individual model while reducing API cost by up to 65.6% relative to always using the strongest model.
This report is categorized under AITOP's "Papers" desk. Within our cross-regional analytical framework, it directly maps to AI developer toolchains, coding agents, and engineering workflows. Key entities and technical topics under continuous tracking include LLM, 多臂老虎机, 组合优化, AHD.
Source attribution: curated from arXiv cs.AI (@Samidha Verma, Ankit Anand, Sayan Ranu).