Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery
arXiv cs.AI · 13 Nov 2026, 04:28 AEST
Ballad is an online bandit algorithm designed for automated heuristic discovery using Large Language Models. It adapts model selection to optimize performance and reduce costs across various NP-hard combinatorial optimization problems.
Key facts
- Modern automated heuristic discovery (AHD) systems increasingly rival hand-crafted heuristics by leveraging Large Language Models (LLMs) to iteratively mutate and refine solutions.
- We challenge this empirically: across multiple NP-hard combinatorial optimization problems, we find no consistent advantage for larger, costlier models.
- 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.
- 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.
Read aloud
Ballad is an online bandit algorithm designed for automated heuristic discovery using Large Language Models. It adapts model selection to optimize performance and reduce costs across various NP-hard combinatorial optimization problems. Modern automated heuristic discovery AHD systems increasingly rival hand-crafted heuristics by leveraging Large Language Models L L M s to iteratively mutate and refine solutions. We challenge this empirically: across multiple NP-hard combinatorial optimization problems, we find no consistent advantage for larger, costlier models. The optimal L L M may shift over the course of a run, and because one L L M's output seeds the context for subsequent calls, each model's reward signal is non-stationary and entangled across the heuristic population. Ballad not only matches the best individual L L M in hindsight but, in several cases, surpasses every individual model while reducing A P I cost by up to sixty five point six percent relative to always using the strongest model.
Sources in this cluster
- Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery
arXiv cs.AI · 13 Nov 2026, 04:28 AEST