Ballad
An online multi-armed bandit algorithmic framework for automated heuristic discovery (AHD). Through non-stationary bandit strategies, DAG-based credit propagation and observation discounting mechanisms, it dynamically orchestrates multiple LLM calls to optimize search quality and cost.
Timeline (last 90 days)
The Ballad study directly challenges the widely assumed premise that "calling a more parameter-heavy, more expensive LLM will yield higher-quality evolved heuristic solutions."
After a systematic comparison across multiple NP-hard combinatorial optimization problems, the research team found that larger, more expensive models did not show a stable advantage.
Ballad designed an online bandit (multi-armed bandit) algorithm that orchestrates a set of LLMs into an ensemble.
Ballad's selection strategy deliberately favors those models that can produce "rare and high-scoring" heuristics, rather than being locked in by models with mediocre average performance but low variance.
Ballad uses a directed acyclic graph (DAG) to track the evolutionary relationships of the heuristic population and propagates the final score backward along the genetic chain for credit assignment.
Ballad applies a discount to old observations so that decisions focus more on the model's recent actual utility, thereby keeping up with the non-stationary reward distribution.
The study validated Ballad on five NP-hard combinatorial optimization problems, with a model pool containing four models of varying capability and cost.
Ballad matched the best single LLM in hindsight (hindsight best), and on some problems even surpassed all single models.
Compared with the naive strategy of "always use the strongest model," Ballad reduced API cost by up to 65.6%.
All Facts (9)
The Ballad study directly challenges the widely assumed premise that "calling a more parameter-heavy, more expensive LLM will yield higher-quality evolved heuristic solutions."
50%UnverifiedAfter a systematic comparison across multiple NP-hard combinatorial optimization problems, the research team found that larger, more expensive models did not show a stable advantage.
50%UnverifiedBallad designed an online bandit (multi-armed bandit) algorithm that orchestrates a set of LLMs into an ensemble.
50%UnverifiedBallad's selection strategy deliberately favors those models that can produce "rare and high-scoring" heuristics, rather than being locked in by models with mediocre average performance but low variance.
50%UnverifiedBallad uses a directed acyclic graph (DAG) to track the evolutionary relationships of the heuristic population and propagates the final score backward along the genetic chain for credit assignment.
50%UnverifiedBallad applies a discount to old observations so that decisions focus more on the model's recent actual utility, thereby keeping up with the non-stationary reward distribution.
50%UnverifiedThe study validated Ballad on five NP-hard combinatorial optimization problems, with a model pool containing four models of varying capability and cost.
50%UnverifiedBallad matched the best single LLM in hindsight (hindsight best), and on some problems even surpassed all single models.
50%UnverifiedCompared with the naive strategy of "always use the strongest model," Ballad reduced API cost by up to 65.6%.
50%