Ballad bandit routing for heuristic discovery — Lineage-credited model routing — What does it mean?
The news. On November 12, 2026, researchers from IIT Delhi and Google DeepMind posted Ballad on arXiv (2611.17241). They ran FunSearch-style searches on five NP-hard problems (travelling salesman, capacitated vehicle routing, online and offline bin packing, graph edit distance) with a pool of four models: gemini-2.5-flash, gemini-2.5-flash-lite, gemma-3-27b-it and gemma-3-12b-it. Aggregated across problems, Ballad matched or beat every single model, and it cost on average 2.86× less than always calling gemini-2.5-flash (a 65.6% average cost reduction). Read the paper →
Picture a test kitchen that runs for 1,000 tastings and only cares about the single best dish it serves at the end. Each round, the head chef picks one cook, hands that cook two earlier recipes, and asks for a better variation. Some cooks are expensive, and some work for free. The head chef's real question is not "who cooks well on average" but "who is most likely to produce the next prize dish" — and that is the question Ballad answers for LLMs. In automated heuristic discovery the recipes are short programs and an evaluator replaces the tasting panel. It is the evaluator-optimizer pattern run over a whole population, with a router choosing the model for each call.
The kitchen also shows why the obvious fix fails. The paper's first finding is that gemini-2.5-flash, the largest and most expensive model in the pool, did not reach the best result or rank on any of the five problems; the smallest model, gemma-3-12b-it, was best on vehicle routing. So "always hire the famous chef" wastes money, and "try every cook on every problem" multiplies the bill by the size of the pool.
A classic stochastic bandit router assumes each model's payoff comes from a fixed distribution and that one model's call does not change another model's payoff. This search breaks three of those assumptions, and Ballad adds one term to its score for each.
- The target is the best result, not the average. Ballad ranks a model by the 0.9 quantile (τ = 0.9, the value that 90% of draws fall below) of the bootstrapped maximum of its scores, blended with the best score it has actually produced (weight λ = 0.3 on that record). A cook who is usually mediocre but sometimes brilliant ranks above a cook who is always fine.
- Credit is shared across models. A cheap cook's old recipe can be the base for a pricey cook's prize dish. When a new program beats the elite median (the median score of the current top-K programs), Ballad walks back up to 4 generations of its family tree and gives each ancestor's model a share of the margin, shrunk by a factor of γ = 0.9 per generation.
- Payoffs drift. Improving a crude early program is easy, so only credit earned in the last W = 25 rounds counts, and the sum is divided by the natural log of how often the model was picked (never below 1), so a model is not rewarded just for being picked often.
A fourth term keeps every model tried early: a UCB-style bonus β·√(log T / n) that uses the total budget T = 1,000 instead of the current round, so it shrinks faster than standard UCB and leaves the late rounds for exploitation.
Here is the credit arithmetic for one round, with the paper's settings held fixed (γ = 0.9, depth limit 4, window 25 rounds) and an illustrative margin. A program written by gemini-2.5-flash beats the elite median by 0.40 (illustrative units). Following one branch of its family tree, its writer gets the full 0.40, its parent's writer (gemini-2.5-flash-lite) gets 0.9 × 0.40 = 0.36, and its grandparent's writer (the free gemma-3-27b-it) gets 0.81 × 0.40 = 0.324 — credit in a round where gemma was not even called. Now apply the exposure correction, with illustrative pick counts: if gemma has been picked 20 times, 0.324 / ln 20 ≈ 0.324 / 3.0 ≈ 0.108; if flash-lite has been picked 200 times, 0.36 / ln 200 ≈ 0.36 / 5.3 ≈ 0.068. The rarely used free model gains more lineage score from this round than the busy paid model, because its few contributions turned out to be unusually productive. The tail-score and exploration terms are added on top, so lineage shifts the ranking without deciding it alone.
The paper's vehicle-routing run shows the same effect at full scale. gemma-3-12b-it was the best standalone model there, yet Ballad mostly routed to gemini-2.5-flash-lite and gemma-3-27b-it and still produced the best vehicle-routing result of any configuration, which the authors read as good programs emerging from the mix of outputs, not from one model.
| Router | Ranks models by | Credits ancestor models? | Overall objective (lower is better) | Source |
|---|---|---|---|---|
| UCB | average score plus a bonus | No | 6.243 | Ballad paper, §4.5 |
| SW-UCB | average over a sliding window | No | 6.314 | Ballad paper, §4.5 |
| Thompson sampling | a random draw from each model's estimated payoff | No | 6.517 | Ballad paper, §4.5 |
| Ballad, lineage off (α = 0) | tail score plus bonus | No | 6.159 | Ballad paper, App. F |
| Ballad | tail score plus lineage plus bonus | Yes | 6.134 | Ballad paper, §4.5 |
Keep the size of these gains in proportion. Turning lineage credit off moved the overall objective only from 6.134 to 6.159, plain UCB was slightly ahead on the travelling salesman problem (6.194 vs 6.233, inside overlapping standard deviations), and every result comes from three runs of a 1,000-evaluation budget. The cost picture is clearer: Ballad was on average 2.86× cheaper and up to 5.30× cheaper than always calling gemini-2.5-flash, but on average 1.19× more expensive than always calling the cheaper gemini-2.5-flash-lite, while beating flash-lite's results on every problem. That trade is what the cost profile of an agent looks like when one loop makes a thousand calls: the model that takes the bulk of them sets the bill. In a nine-model follow-up that added GPT-5 and Claude Sonnet 5, the paper reports objectives improving on two problems and cost savings averaging 46.35% against always using GPT-5, assuming comparable token usage.
The durable lesson is the accounting rule: when one model's output becomes the next model's input, a router that credits only the last writer will undervalue the cheap models that laid the groundwork.
Goes deeper in: AI Agents → Workflow Patterns → Chaining + Routing
Related explainers
- Contextual-bandit tool routing — the average-reward bandit that Ballad's tail score replaces
- AgenticEvolve — a different upgrade to the same evolutionary program-search loop
- Dynamic LLM routers vs a cost-matched coin — why router benchmarks need a fair cost baseline