Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery

Samidha Verma, Ankit Anand, Sayan RanuarXiv 2026 · arXiv

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:

  1. 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.
  2. 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.
  3. 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:

  1. Traveling Salesman Problem (TSP): Finding the shortest route through 50 nodes.
  2. Capacitated Vehicle Routing Problem (CVRP): Routing vehicles with capacity constraints.
  3. Online Bin Packing: Assigning items to bins as they arrive.
  4. Offline Bin Packing: Assigning a fixed set of items to the minimum number of bins.
  5. 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.
LLM selection share across search steps showing how BALLAD adaptively shifts between models over time.

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.
Table 1: Test-set performance. We report the best program (selected on validation) evaluated on the test set. For each model, we show mean ± std (over 3 runs) for Task-Specific Objective (Obj.) (↓) and Rank (↓), where lower is better for both Obj, since we benchmark on minimization problems, and rank. Ranks are integer-valued; draws at full precision share the lowest rank, and the next rank is skipped. Overall is the mean of per-problem means; its std is the root-mean-square of per-problem stds.
  • 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).
Figure 2: LLM API cost per run. Total monetary cost (USD) of one evolutionary search run on each task, averaged over three independent runs (mean ± std as error bars). Costs are computed from per-call input/output token counts using public Gemini 2.5 list prices: Flash-Lite at $0.10/M input and $0.40/M output tokens, Flash at $0.30/M input and $2.50/M output tokens. gemma-3 models incur no monetary cost, hence not shown. Average cost reduction relative to gemini-2.5-flash using BALLAD is 65.6%.
  • Efficiency: As shown in the performance curves, BALLAD often finds high-quality solutions earlier in the search process than individual models.
Best test objective vs. number of LLM calls, showing BALLAD's convergence.

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

Abstract

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.
BibTeX
@misc{verma2026ballad,
  author = {Samidha Verma and Ankit Anand and Sayan Ranu},
  title = {{Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery}},
  year = {2026},
  eprint = {2611.17241},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17241},
}
Figure