Illustrative image: the main building of IIT Delhi, where lead author Samidha Verma and senior author Sayan Ranu are based. Image: Wikimedia Commons / TheVyomanaut, CC BY-SA 4.0
TL;DR: Ballad algorithm LLM routing explained in one line: researchers at IIT Delhi and Google DeepMind built a bandit algorithm that picks which AI model to use at each step of automated heuristic discovery, cutting API costs by up to 65.6% while matching or beating the strongest single model. The surprise behind it: the biggest, most expensive model was not the best on any of the five problems tested.
Key Highlights
- New paper "Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery" (arXiv:2611.17241), posted 12 November 2026 by Samidha Verma and Sayan Ranu of IIT Delhi with Ankit Anand of Google DeepMind.
- Across five NP-hard optimisation problems, the largest and most expensive model tested, Gemini 2.5 Flash, was best on none of them. The smallest model, Gemma-3-12b-it, won on vehicle routing; Gemini 2.5 Flash-Lite was the most consistent.
- Ballad learns online which model to call at each step. It matched or beat the best single model overall while costing up to 65.6% less than always using the strongest model.
- Code is public at github.com/idea-iitd/Ballad, and Ballad drops into FunSearch- and AlphaEvolve-style pipelines with no retraining or extra labelled data.
What happened?
Automated heuristic discovery (AHD) is one of the quieter success stories of applied AI. Instead of a human expert hand-designing the rules that solve a hard optimisation problem — say, the shortest route visiting 50 cities — systems such as Google DeepMind's FunSearch and AlphaEvolve ask a large language model to write candidate heuristics as code, test them, keep the best, and mutate them again. After thousands of rounds, the machine-discovered rules can rival or beat hand-crafted ones.
The catch is cost: a single AHD run needs thousands of LLM calls, so the choice of model matters enormously, and the default assumption has been that the biggest, most expensive model is worth paying for. The Ballad paper, posted to arXiv on 12 November 2026, tests that assumption head-on and finds it does not hold. If no single model is best everywhere — and the best model can change as the search progresses — the smart move is to stop committing to one model up front and learn, during the run, which model to call next. That is what Ballad does.
Ballad Algorithm LLM Routing Explained: How It Works
Ballad treats model selection as an online bandit problem: each model in the pool is an "arm" of a slot machine, and each pull is one LLM call whose reward is the score of the heuristic it produces. Textbook bandit algorithms do not fit this setting, though, because AHD breaks three of their core assumptions — and Ballad is built around three fixes, one for each.
First, the goal is not a good average score but a single best heuristic, so Ballad ranks models by their upper-tail quality — their ability to produce rare, high-scoring breakthroughs — rather than by their mean performance. Second, models do not work independently: one model's output becomes the prompt context for the next model's call, so a good result may really belong to an earlier model whose idea seeded it. Ballad tracks this with a directed acyclic graph (DAG) of the mutation genealogy, passing credit backwards through the family tree of heuristics. Third, a model's usefulness changes as the search evolves, so old evidence goes stale; Ballad discounts older observations with a sliding window. Combined into one per-model index, these ideas let Ballad explore early and then concentrate calls on the models actually delivering — with no offline training data and no changes to prompts or scoring, which is why the authors call it a drop-in replacement for the fixed-model generator in any FunSearch- or AlphaEvolve-style pipeline.
.jpg?width=900)
Illustrative image: a one-armed bandit — the classic metaphor for the bandit algorithm Ballad uses to choose between AI models. Image: Wikimedia Commons / TaurusEmerald, CC BY 2.0
What the experiments found
The team ran Ballad on five NP-hard problems: the travelling salesman problem and the capacitated vehicle routing problem (both 50 nodes), online bin packing (5,000 items) and offline bin packing (500 items), and graph edit distance on Linux program-dependence graphs. The pool mixed two paid closed models (Gemini 2.5 Flash and Flash-Lite) with two free open-weight models (Gemma-3-12b-it and Gemma-3-27b-it). Each method ran 1,000 evaluations per problem, repeated three times. The headline table, on overall objective value (lower is better), tells the story:
| Method | Overall objective (lower is better) | Average rank |
|---|---|---|
| Ballad | 45.577 | 1.733 |
| Gemini 2.5 Flash-Lite | 45.630 | 1.733 |
| Gemini 2.5 Flash (strongest, priciest) | 46.187 | 3.467 |
| Gemma-3-12b-it (smallest, free) | 48.066 | 3.333 |
| Gemma-3-27b-it (free) | 49.157 | 4.067 |
Ballad finished with the best overall objective and the joint-best average rank, and on several individual problems it beat every single model — evidence, the authors argue, that it is not merely picking the best model but composing calls across models in ways no solo model can replicate. The cost side is just as striking: against always using Gemini 2.5 Flash, Ballad was up to 5.30 times cheaper on a single problem and 2.86 times cheaper on average, an average API cost reduction of 65.6%. Costs were computed from public Gemini 2.5 list prices, with the Gemma models free. Notably, the saving is a side effect: Ballad's scoring never looks at price — it simply discovers that the expensive model is not consistently worth calling.
Why it matters for India readers
The India angle is direct: the research was led from IIT Delhi, with lead author Samidha Verma and senior author Sayan Ranu both based there, alongside Google DeepMind's Ankit Anand. It is a reminder that some of the most practical AI-systems research — the kind that decides how much a real deployment costs — is being done in Indian labs, not just in the big US companies' research arms.
The practical stakes are broader and very relevant to India's large developer and startup ecosystem. AHD-style pipelines are how teams now search for better scheduling rules, delivery routes, warehouse packing and chip layouts — exactly the optimisation problems Indian logistics, e-commerce and manufacturing firms run every day. If a team can get equal or better heuristics while paying roughly a third of the API bill, smaller teams can afford to run these systems at all, and larger ones can run them far more often. The paper also points the same way as the recent AI-assisted proof of the 18-year-old Aaronson-Ambainis conjecture: the frontier of AI research is increasingly about orchestrating models cleverly, not just scaling them up.
Should you care?
✅ Yes, if you run LLM pipelines — and as a signal even if you don't. If you pay per-token API bills for search, optimisation or agent loops, Ballad's lesson is immediately usable: test cheaper and open-weight models before defaulting to the flagship, and consider routing calls adaptively instead of fixing one model. If you are a researcher or student, the paper is a clean example of turning a surprising negative result (bigger is not better) into a new algorithm. If neither applies, the takeaway still matters: the cost of advanced AI is falling not only because models get cheaper, but because we are learning to use them more cleverly.
Limitations and what happens next
Three caveats keep this honest. First, this is a preprint, not yet peer-reviewed — the results are the authors' own, from three runs per problem, and independent replication is still to come. Second, the evidence covers five combinatorial optimisation benchmarks and four Google models; whether the same pattern holds on other problem families or other vendors' models is untested. Third, the cost figures rest on public Gemini 2.5 list prices at the time of writing, and API prices change. What to watch: whether the open-source implementation gets picked up by FunSearch-style projects, whether other labs reproduce the 65.6% saving on their own workloads, and whether the idea spreads from heuristic discovery to wider multi-model routing — the same question behind the samsara++ sampler work and the AIOA autonomous optimisation results covered earlier on TechByCountry.
FAQs
What is automated heuristic discovery?
Automated heuristic discovery (AHD) is a method where an AI system, usually a large language model, writes, tests and iteratively improves heuristic rules — the shortcut rules used to solve hard optimisation problems such as routing or packing — instead of a human expert designing them by hand. Systems such as FunSearch and AlphaEvolve use this approach, and their machine-discovered heuristics can rival or beat hand-crafted ones.
What is the Ballad algorithm?
Ballad (Bandit-based LLM Routing for Automated Heuristic Discovery) is an online bandit algorithm from IIT Delhi and Google DeepMind that learns, during a run, which language model to call at each step of heuristic discovery. It ranks models by their rare best results rather than their average, shares credit through the family tree of generated heuristics, and forgets stale evidence — beating or matching the best single model at up to 65.6% lower API cost.
Does a bigger LLM always give better results?
No — and that is the Ballad paper's central finding. Across five NP-hard problems, the largest and most expensive model tested, Gemini 2.5 Flash, was best on none of them, while the smallest model, Gemma-3-12b-it, won on vehicle routing and the mid-priced Gemini 2.5 Flash-Lite was the most consistent. Model size did not predict performance in this setting.
How much cheaper is Ballad than using the strongest model?
Compared with always using Gemini 2.5 Flash, Ballad cut API costs by 65.6% on average — up to 5.30 times cheaper on one problem and 2.86 times cheaper on average — while matching or beating the best single model's results. The figures are the authors' own, computed from public Gemini 2.5 list prices, with the Gemma models free.
Takeaway
The most expensive AI model is not always the best one — and a clever routing algorithm that learns this during the run can deliver better results for roughly a third of the price. For anyone paying per-token API bills, that is a finding worth testing on their own workload.
If you run LLM pipelines, the paper's code is public — try Ballad's routing idea on your own optimisation task and see whether the cheaper models surprise you too.
Sources
arXiv:2611.17241 — Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery (abstract)
arXiv full text — Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery
Ballad code repository — github.com/idea-iitd/Ballad
PaperDeck summary of the Ballad paper
Comments
Post a Comment