Research
Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery
Ballad is an online bandit algorithm that orchestrates a pool of LLMs during automated heuristic discovery, adaptively selecting which model to invoke at each step. The method uses a selection policy favoring rare high-scoring heuristics, DAG-based credit propagation through the heuristic genealogy, and discounting of stale observations. Across five NP-hard combinatorial optimization problems and four models of varying capability and cost, Ballad matches the best individual LLM in hindsight and in several cases surpasses every individual model. It also reduces API cost by up to 65.6% relative to always using the strongest model.
LLM routingautomated heuristic discoverycombinatorial optimization