[KongchangAI]
· 2 min read· 1,290 words

Ballad: Scheduling LLMs with Multi-Armed Bandits for Automated Heuristic Discovery, Cutting Costs by 65.6%

Ballad: Scheduling LLMs with Multi-Armed Bandits for Automated Heuristic Discovery, Cutting Costs by 65.6%

Ballad uses online bandits to orchestrate multiple LLMs for heuristic search, matching the best model while saving 65.6% in costs.

The article introduces a study called Ballad that challenges the default assumption in Automated Heuristic Discovery (AHD) that larger, more expensive LLMs yield better results. It finds that model superiority drifts during search and that outputs serve as each other's context, causing non-stationary rewards and entangled signals that classical online decision algorithms cannot directly handle. Ballad orchestrates multiple models into an ensemble using an online bandit algorithm, with three mechanisms: preferring rare high scores, DAG-based credit propagation, and discounting stale observations. On five NP-hard combinatorial optimization problems, it matches or surpasses the best single model in hindsight while cutting API costs by up to 65.6% compared with always calling the strongest model.

When the Assumption "Stronger Model = Better Results" Breaks Down

In the field of Automated Heuristic Discovery (AHD), a widely held premise is that LLMs with more parameters and higher prices will iteratively produce higher-quality heuristic solutions. But a study called Ballad directly challenges this intuition.

The research team conducted systematic comparisons across multiple NP-hard combinatorial optimization problems, and the conclusion is quite counterintuitive: larger, more expensive models do not show a stable advantage. In other words, simply stacking model specifications to improve heuristic quality is not cost-effective. This raises a more practical question—when you have both frontier closed-source models and free/open-weight models on hand, how do you adaptively choose which one to call at each step based on the search progress?

The difficulty of this problem lies in two aspects. First, the optimal model is not fixed; it may drift across different stages of a single search. Second, the output of one LLM call becomes the context for subsequent calls, causing each model's reward signal to be both non-stationary and entangled with others—directly violating the independence assumptions that classical online decision algorithms rely on.

Ballad paper source screenshot

Automated Heuristic Discovery (AHD) is an emerging direction in algorithm design and optimization: given a combinatorial optimization problem (such as traveling salesman, bin packing, scheduling), LLMs repeatedly generate, mutate, and select heuristic rules or solving strategies, ultimately "evolving" high-quality solutions automatically. Compared with traditional manual heuristic design, AHD treats LLMs as search operators, progressively approaching better solutions through multiple rounds of iteration. Because each round requires a model call, model selection directly determines the quality ceiling of the search and the API overhead—this is the fundamental reason Ballad focuses on "which model to use, and when."

NP-hard combinatorial optimization problems refer to a class of problems for which no known polynomial-time exact algorithm exists; once the scale is even slightly large, they cannot be solved by brute force, and practice relies on heuristics or approximation algorithms. Typical representatives involved in this paper's experiments include the traveling salesman problem, vehicle routing problem, and bin packing problem. These problems are characterized by: enormous solution spaces, discontinuous evaluation functions, and the fact that occasionally a single heuristic rewrite that "escapes a local optimum" can bring significant improvement. Therefore, "rare high scores" are more valuable than "stable averages," which also explains the design motivation behind Ballad's selection strategy.

Ballad's Three Core Mechanisms

To address the aforementioned challenges of non-stationarity and entangled signals, Ballad designs an online bandit algorithm that orchestrates a set of LLMs into an ensemble. Its goal is not simply to rotate among models, but to make the overall performance match or even exceed any single model. Specifically, it is supported by three components:

1. An LLM Selection Strategy That Prefers Rare High Scores over Stable Means

Traditional bandit strategies tend to favor options with stable reward means, but in heuristic search, what is truly valuable is the occasional high-scoring sample. Ballad's selection strategy deliberately favors models that can produce "rare and high-scoring" heuristics, rather than being locked in by models with mediocre average performance but low variance. This better fits the characteristic of AHD tasks where "an occasional breakthrough is a victory."

Multi-armed bandit is a classic framework in reinforcement learning and online decision-making: faced with K options ("arms"), you select one each round and observe the reward, with the goal of balancing "exploring the unknown" and "exploiting the known" to maximize cumulative reward. Classic algorithms such as UCB and Thompson Sampling typically assume that the rewards of each arm are independent and identically distributed and stationary. The scenario Ballad faces breaks this assumption—rewards drift with the search stage, and the outputs of different models serve as each other's context, causing signals to be correlated. Therefore, classical bandits need to be modified for non-stationarity and credit attribution.

2. DAG-Based Credit Propagation

Since each heuristic evolves from prior calls, there are lineage relationships among models. Ballad uses a directed acyclic graph (DAG) to track the "family tree" of the heuristic population and propagates the final score backward along the genetic chain, fairly attributing credit to models that made key contributions early on, rather than only looking at the model called in the last step.

Credit assignment is a core challenge in sequential decision-making: when a long chain ultimately yields a good or bad result, how do you determine which step contributed the most? In AHD, a heuristic is often evolved generation by generation through several rounds of LLM calls, forming a tree- or graph-shaped "family tree." Ballad uses a DAG (directed acyclic graph) to record this evolutionary relationship, then propagates the final score backward along the edges, so that models that made key rewrites early on also receive reward signals. If only the last step is rewarded, early contributions will be systematically underestimated, and the model selection strategy will gradually become distorted.

3. Discounting of Stale Observations

During the search process, a model's effectiveness changes, and earlier reward records may no longer represent its current capability. Ballad applies discounts to old observations, making decisions focus more on the model's recent actual utility, thereby keeping up with the non-stationary reward distribution.

Experimental Performance: Matching the Best While Saving Substantial API Costs

The study validated Ballad on five NP-hard combinatorial optimization problems, with a model pool containing four models of varying capabilities and costs. Two key numbers from the results are worth noting:

  • Ballad's performance not only matches the best single LLM in hindsight but even surpasses all single models on some problems;
  • Compared with the naive strategy of "always using the strongest model," Ballad reduces API costs by up to 65.6%.

This shows that in AHD scenarios, the value of model scheduling may be no less than the capability of the models themselves. Blindly calling the most expensive model is neither the optimal solution for effectiveness nor for cost.

Implications for AHD Engineering Practice

This research offers several practical references for implementing automated heuristic discovery. First, building a model pool is more robust than betting on a single model—especially when free or open-weight models are included as candidates, which can lower costs without sacrificing effectiveness. Second, the scheduling strategy must handle "credit attribution"; otherwise, the contributions of early models will be buried and the learning signal will be distorted. Third, non-stationarity is the norm rather than the exception, and static model preferences will become outdated as the search progresses.

Ballad's significance lies in turning "which model to use" from an empirical judgment into a learnable online decision problem. For teams that need to repeatedly call LLMs for search optimization, this provides a path that balances effectiveness and cost.

One-line Summary

Ballad uses online bandits to orchestrate multiple LLMs for heuristic search, matching the best model while saving 65.6% in costs.

Paragraph Summary

This article introduces a study called Ballad, which challenges the default assumption in Automated Heuristic Discovery (AHD) that "larger, more expensive LLMs bring better results." The research finds that model superiority drifts during the search process, and that the outputs of different models serve as each other's context, causing rewards to be non-stationary and signals to be entangled, making classical online decision algorithms difficult to apply directly. Ballad uses an online bandit algorithm to orchestrate multiple models into an ensemble, addressing these challenges through three mechanisms: a selection strategy that prefers rare high scores, DAG-based credit propagation, and discounting of stale observations. On five NP-hard combinatorial optimization problems, Ballad matches or even surpasses the best single model in hindsight, while reducing API costs by up to 65.6% compared with the strategy of always calling the strongest model, offering a model scheduling approach for AHD engineering practice that balances effectiveness and cost.

#Ballad#multi-armed bandit#LLM routing#automated heuristic discovery#AHD#NP-hard combinatorial optimization#credit assignment#DAG#API cost reduction
Share:

Related articles