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.
Figures & tables
Model
Metric
TSP
CVRP
Online BP
Offline BP
GED
Overall
gemma-3-12b-it
Obj.
6.396 ± 0.028
10.753 ± 0.031
2.510 ± 0.000
215.719 ± 0.000
4.953 ± 0.091
48.066 ± 0.045
Rank
3.333 ± 0.471
1.667 ± 0.471
3.000 ± 0.000
4.000 ± 0.000
4.667 ± 0.471
3.333 ± 0.365
gemma-3-27b-it
Obj.
6.934 ± 0.003
15.735 ± 4.348
2.593 ± 0.059
215.719 ± 0.000
4.804 ± 0.040
49.157 ± 1.945
Rank
4.667 ± 0.471
5.000 ± 0.000
4.333 ± 0.943
4.000 ± 0.000
2.333 ± 0.471
4.067 ± 0.516
gemini-2.5-flash-lite
Obj.
6.258 ± 0.064
10.776 ± 0.070
1.574 ± 0.217
204.750 ± 0.034
4.792 ± 0.032
45.630 ± 0.108
Rank
1.333 ± 0.471
2.333 ± 0.943
1.667 ± 0.471
1.667 ± 0.471
1.667 ± 0.943
1.733 ± 0.699
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.
Figure 1: LLM selection share across search steps (rolling window of 100 calls). Each panel shows, for a combinatorial optimization problem, the fraction of LLM calls routed to each model by Ballad over the course of the evolutionary search. The dotted horizontal line marks the uniform-allocation baseline (1/K=25% here), corresponding to a policy with no preference over arms. Deviations from this baseline reflect the learned routing policy by Ballad favors models with selection share above 1/K due to higher estimated utility.
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/Minputand0.40/M output tokens, Flash at 0.30/Minputand2.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%.
Model
Metric
TSP
CVRP
Online BP
Overall
Random
Obj.
6.243 ± 0.037
10.851 ± 0.087
2.071 ± 0.621
6.378 ± 0.363
UCB
Obj.
6.194 ± 0.051
10.896 ± 0.088
1.640 ± 0.616
6.243 ± 0.360
SW-UCB
Obj.
6.306 ± 0.072
10.885 ± 0.118
1.752 ± 0.087
6.314 ± 0.094
Thompson Sampling
Obj.
6.294 ± 0.004
10.861 ± 0.023
2.398 ± 0.112
6.517 ± 0.066
Ballad ( λ=0 )
Obj.
6.255 ± 0.043
10.869 ± 0.086
1.603 ± 0.162
6.242 ± 0.108
Ballad ( λ=1 )
Obj.
6.250 ± 0.020
10.729 ± 0.017
1.988 ± 0.422
6.322 ± 0.244
Table 2: Ablation Study: The first four rows are baseline arm-selection strategies. λ=0 and λ=1 denote quantile- and maximum-based variants, respectively; α=0 disables lineage-aware exploitation. τ controls the upper-tail level. Exp. bonus ∝logt uses standard UCB exploration. Cost-Penalized Exp. accounts for LLM call costs and penalises exploration for expensive arms. Bold and underline denote the best and second-best, respectively. Due to computational constraints, we evaluate the ablations on three problems.
Symbol
Description
Setting
Problem and Search Space
P
Problem specification
–
IP
Set of problem instances
–
fP
Scoring/Objective function
–
h
Candidate heuristic (code)
–
h0
Seed heuristic
–
Table 3: Notations and Hyperparameter Settings for Ballad
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Problem
Problem Size
Constraints
Train
Val
Test
Routing
TSP
50
-
64
64
1,000
CVRP
50
W=50
10
64
64
Bin Packing
Online BP
5,000
C∈{100,500}
2
5
5
Offline BP
500
C=150
5
64
64
Appendix
Table 4: Benchmark dataset configurations. Problems are grouped by type. Problem Size denotes the average instance size: number of cities/nodes for routing problems, number of items for packing problems, and (∣V∣,∣E∣) for graph problems. Problem-specific constraints, such as vehicle capacity W (CVRP) and bin capacity C (BP), are listed in the Constraints column. Instance counts are given per split.
Figure 3: Best test objective vs. number of LLM calls for Ballad (lower is better). After each call, all programs generated so far are evaluated on the test set, and the best-performing program is retained. The blue line shows the mean across three runs, with the shaded region indicating ± 1 standard deviation. The green dashed line marks the best objective achieved across all runs. Insets zoom in on the second half of the search to highlight smaller improvements. Since the best program is selected using test performance at each step, these curves provide an optimistic estimate of the results in Table 1 , where selection is based on validation performance. The final mean is comparable to or better than the corresponding table value.
Model
Offline BP
GED
Ballad (Scaled, α=0 )
204.734 ± 0.109
5.178 ± 0.238
Ballad (Scaled)
204.539 ± 0.242
4.706 ± 0.026
Ballad (Table 1 , 4 models)
204.693 ± 0.323
4.789 ± 0.022
Appendix
Table 5: Scaling to Frontier Models: Objective values on Offline BP and GED for four- and nine-model pools, with and without lineage-aware exploitation. Scaled denotes the nine-model pool. Bold and underline denote the best and runner-up values, respectively.
Dataset
Ballad (Scaled)
GPT-5 only
Savings (USD)
Offline BP
22.629
29.948
7.319 (24.4%)
GED
9.745
30.739
20.994 (68.3%)
Appendix
Table 6: Cost Comparison: Average cost per run (USD) of Ballad (Scaled) versus pricing the same token volume entirely at GPT-5’s rate. Relative savings are shown in parentheses.
Large language model routing selects models, tools, experts, or inference strategies to balance answer quality, cost, latency, and deployment constraints.
Centre for Machine Intelligence and Data Science (C-MInDS) Indian Institute of Technology Bombay · Department of Electrical Engineering Indian Institute of Technology Bombay