TL;DR
BALLAD is an online bandit algorithm designed to intelligently route queries to a pool of diverse LLMs for automated heuristic discovery. By challenging the "bigger is better" assumption, it orchestrates ensembles that often outperform individual frontier models while slashing API costs by up to 65.6%.
What Problem Does This Paper Address?
Automated Heuristic Discovery (AHD) systems, such as Google DeepMind's FunSearch, use Large Language Models (LLMs) to iteratively evolve code-based heuristics for solving NP-hard combinatorial optimization problems. While effective, AHD is notoriously expensive, often requiring thousands of LLM calls per run.
The standard industry practice is to use the most powerful (and expensive) model available, assuming it will yield the best results. The authors of this paper challenge that assumption, finding that larger models do not consistently outperform smaller or open-weight alternatives in code mutation tasks.
However, simply picking a "best" model is hard because the optimal choice shifts as the search progresses. Furthermore, standard online decision-making tools (like Multi-Armed Bandits) fail here because:
- Extreme-Value Objective: We don't care about the average performance of a model; we only care about its ability to produce a single "diamond in the rough" breakthrough.
- Entangled Rewards: One model's output seeds the context for the next call. If Model A produces a decent heuristic that Model B later turns into a masterpiece, Model A deserves partial credit.
- Non-Stationarity: As the population of heuristics improves, the relative utility of different models changes.
Methods
The authors propose BALLAD (Bandit-based LLM Routing for Automated Heuristic Discovery), which treats LLM selection as an online bandit problem with a custom scoring function:
$$Score_\ell(t) = \text{Hybrid Extreme-Value} + \text{Lineage Credit} + \text{Exploration Bonus}$$
Key innovations include:
- Hybrid Extreme-Value Estimator: Instead of tracking mean scores, BALLAD uses a bootstrapped quantile-of-maxima estimator. This prioritizes models that show "flashes of brilliance" over those that are consistently mediocre.
- Mutation Genealogy DAG: BALLAD maintains a Directed Acyclic Graph (DAG) of the heuristic population. When a high-scoring heuristic is found, credit is propagated back through its ancestors. This ensures that "enabler" models—those that provide the foundation for later breakthroughs—are rewarded.
- Sliding-Window Normalization: To handle non-stationarity, the algorithm uses a windowed fertility score, focusing on which models are contributing to the current frontier of the search rather than their historical performance.
- Fixed-Horizon UCB: A modified Upper Confidence Bound (UCB) bonus that front-loads exploration when the budget is plentiful and focuses on exploitation as the run nears its end.
Datasets
The authors evaluated BALLAD across five classic NP-hard combinatorial optimization problems:
- Traveling Salesman Problem (TSP): Finding the shortest route through 50 nodes.
- Capacitated Vehicle Routing Problem (CVRP): Routing vehicles with capacity constraints.
- Online Bin Packing: Assigning items to bins as they arrive.
- Offline Bin Packing: Assigning a fixed set of items to the minimum number of bins.
- Graph Edit Distance (GED): Measuring dissimilarity between program dependence graphs.
The LLM pool included four models: Gemini 2.5 Flash, Gemini 2.5 Flash-Lite, Gemma 3 12B, and Gemma 3 27B.
Key Insights and Ideas
- The "Bigger is Better" Myth: In AHD, model size is a poor predictor of success. For instance, the smallest model (Gemma 3 12B) achieved the best standalone performance on CVRP, while the most expensive model (Gemini 2.5 Flash) often lagged behind.
- Orchestration vs. Selection: BALLAD doesn't just pick the best model; it learns a collaborative dynamic. It might use a smaller model to generate diverse candidates and a larger model to refine them. This "orchestration" allowed BALLAD to surpass the performance of every individual model in several benchmarks.
- Lineage Matters: Rewarding models for their "ancestral" contributions was crucial. Disabling the lineage-aware credit propagation significantly degraded performance on complex tasks like TSP and CVRP.
Key Results
- Superior Performance: Across all five problems, BALLAD consistently matched or exceeded the best individual LLM. In the "Overall" metric, it achieved the lowest (best) objective score and rank.
- Massive Cost Savings: By favoring cheaper models when they were effective, BALLAD reduced API costs by an average of 65.6% compared to a strategy of always using the strongest model (Gemini 2.5 Flash).
- Efficiency: As shown in the performance curves, BALLAD often finds high-quality solutions earlier in the search process than individual models.
Limitations and Future Work
- Black-Box Assumption: BALLAD treats LLMs as black-box generators with fixed prompts. The authors suggest that future work could allow the router to also select between different prompting strategies or mutation operators tailored to specific models.
- Fixed Hyperparameters: While BALLAD is robust, its performance is somewhat sensitive to hyperparameters like the lineage-aware weight ($\alpha$) and the tail level ($\tau$).
- Environmental Impact: While BALLAD reduces API costs, the authors acknowledge the general environmental considerations of running large-scale LLM evolutionary searches.
Summary updated