2608.07056-BONSAI: Evolvability-Guided Tree Search over Skills

Introduction to the show: ident: Paper Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "BONSAI: Evolvability-Guided Tree Search over Skills".

Jane: The paper was written by Yash Priya Shastri, Anand Eswaran, Adnan Qidwai, Pankaj Thorat and Sachin Joshi from IBM Research.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Paper summary: Tom: This paper from IBM Research has me properly excited. Picture a frozen eye model — weights fixed, no training possible. Whatever it does well has to be told to it in text, and that text is what they call a skill.

Jane: So the skill is the only object an optimizer can touch. Every point of accuracy must be bought with prose.

Tom: Exactly. The skill is a short field manual, not a prompt template. It tells the model which library to reach for and what to verify before answering. And optimizing a skill means editing that prose against a score.

Jane: The standard recipe — keep any edit that raises a held-out score. Sounds harmless.

Tom: It has a blind spot. A validation score is one number over a finite task set, and two documents that score alike can sit in very different terrain. One is on a broad plateau where further edits keep paying off. The other is on a narrow spike that the next edit knocks it off of.

Jane: Same number, opposite futures. The score can't tell them apart.

Tom: Biology has a word for the property you need in that situation — evolvability. Not present fitness, but the ability of a lineage to keep producing useful variants. BONSeye steers the search by that.

Jane: And the search itself is a tree. Every child document is a mutation of its parent, and an upper-confidence rule decides where to descend.

Tom: The exploitation term blends a skill's own fitness with the fitness of its mutational neighborhood. Budget flows to regions that keep improving.

Lu: While the exploration term keeps a currently weak branch in contention.

Jane: Give me the headline numbers.

Tom: With a frozen 30-billion-parameter agent, averaged over three benchmarks, BONSeye lifts held-out accuracy by 23.13 points over the skill-free agent. It beats two budget-matched baselines, GEPA and SkillOpt, by 3.87 and 3.97 points.

Jane: Same budget, same performer, same optimizer. The margin is attributable to the search strategy.

Meng: And the thing that measures evolvability is free?

Tom: Totally free. It reuses fitness scores the search already paid for. That's a big deal — a measurement that costs more than the search it guides is worthless.

Lalam: The bigger picture is wider than these three benchmarks. Any system where text steers a frozen model could borrow this.

Jane: I want to see that blind spot up close. Where does the paper start?

Page 1 of the paper: Jane: The thesis is on the table, so we're building from here. Page one pins down exactly why the score is blind.

Tom: The key line is early: a validation score is one number over a finite task set. Two documents that score alike may be quite different objects.

Jane: One rests on a broad plateau that further edits keep improving. The other on a narrow spike the next edit displaces.

Tom: And a spike is a dead end. Any edit that repairs one remaining failure tends to break something the document already handled.

Jane: That's the trap. A document that looks nearly finished can be one edit away from collapse.

Tom: The score can't tell you which situation you're in, because the score is just that one number. It carries no information about the surrounding landscape.

Jane: They point out the distinction is familiar elsewhere. Optimization theory contrasts flat minima with sharp ones and expects flat ones to generalize better.

Tom: There's a whole literature on flat minima in neural networks — Sharpness-Aware Minimization is in their references. Same intuition: the geometry around a solution tells you about its future, not just the solution itself.

Jane: And biology treats evolvability as a property separate from present fitness. A lineage can be fit today and still be a dead end tomorrow.

Lu: So the idea has pedigree. What's been missing for skills is a way to measure it.

Tom: The crucial constraint: the measurement must not cost more than the search it guides. If you double the model calls to measure evolvability, you've lost before you've started.

Jane: That's the bar they set for themselves on page one.

Tom: The contributions are listed there too. Identify evolvability as the steering signal, give a free measurement of it, turn that into a tree search, and demonstrate it on benchmarks.

Meng: They also frame the skill nicely — a field manual rather than a template. It states which library to reach for, which edge cases cause failures, what to verify before returning.

Tom: That phrase matters because it sets the scale. These documents are short, dense, and practical. The optimizer isn't writing poetry; it's patching operational knowledge.

Jane: And the optimizer is a separate model that never attempts tasks itself. It reads scored attempts — the task, the answer, and why it was judged incorrect — and rewrites the document.

Tom: There are three splits already at the end of page one: train feeds the rewrites, validation scores the search, test is touched once at the very end.

Jane: So the structure of the whole method is already visible. What I want to know is how they define that measurement precisely. That's page two.

Page 2 of the paper: Jane: We left off needing a precise definition. Page two delivers the machinery.

Tom: First the cast: two models, neither trained. The performer is the frozen agent that reads the skill and attempts tasks. The optimizer is a second model that never attempts tasks itself — it reads scored failures and returns a rewritten skill.

Jane: There's also the data split: train, validation, test. That split is fixed once and identical across runs.

Tom: Then the tree. The root is the seed document, and an edge from node to child means one reflective rewrite. Every child is a mutation of its parent.

Jane: That single construction choice does the heavy lifting. It turns an unordered pile of candidate documents into a space with neighborhood structure.

Tom: And a neighborhood is something you can measure. That's the bridge from the biology intuition to an algorithm.

Jane: So how do they define evolvability?

Tom: Epsilon of a skill is the expected fitness of its mutational neighborhood — the expectation over children mutation produces from it, and transitively over the region reachable by repeated mutation.

Jane: It belongs to a region, not to a single document. Reports not how a skill performs today, but how well its future is likely to perform.

Tom: The region is unbounded, so you can't read epsilon directly. But the tree gives a free estimator. Take the lineage of a node — the node plus every document later grown from it.

Jane: Every descendant was reached by mutation, so the lineage's mean fitness estimates the region's evolvability.

Tom: They call that Q of n. And then comes the crucial comparison: the node's own fitness minus Q gives brittleness, sigma.

Jane: A large positive sigma marks a brittle, overfit peak. The neighborhood scores far lower than the document itself.

Tom: A sigma at or below zero means the neighborhood holds up. That's the signature of an evolvable region.

Jane: Two properties make Q worth having. First, it's free.

Tom: Every term in that average is a fitness value the search already paid for. No extra model calls to measure evolvability.

Jane: Second, it sharpens itself.

Tom: Each expansion beneath a node adds a sample to Q. The nodes probed most heavily get the best-resolved estimates. The search invests in measurements it trusts.

Lu: A self-improving estimate. That's elegant.

Meng: And the figure in the paper makes it visual — green nodes and red nodes, with circle areas showing value samples.

Tom: The green ones are the survivors. The red ones are where the next edit collapses.

Jane: So we have a measure. Next question: what rule turns that measure into a search?

Tom: Page three has the rule, and it's an upper-confidence bound with a twist.

Page 3 of the paper: Jane: Our measure is in hand. Page three gives the selection rule that walks the tree.

Tom: It's a Monte-Carlo tree search, and the selection score looks familiar at first: v of s, plus an exploration bonus, plus c times the square root of log N of the parent over N of s.

Jane: Standard upper-confidence stuff. What's the twist?

Tom: The exploitation term is v of s plus lambda times the gap between Q and v. At lambda equal to one — which they use throughout — that term collapses to Q exactly. Evolvability leads the search.

Jane: And at lambda zero it's plain fitness. That's the ablation they'll run later.

Tom: The exploration term keeps a currently weak branch in contention. An early verdict can be revised.

Jane: There's also a normalization detail I want to get right.

Tom: They rescale the exploitation term to zero-one using the smallest and largest fitness in the tree, adapted from MuZero. That makes the exploration constant scale-free.

Jane: One value of c behaves the same whether scores cluster near ten percent or near ninety. You don't retune per benchmark.

Tom: Then the expansion and acceptance. The optimizer proposes one child, and it's kept only if it strictly improves on the same batch of training tasks the optimizer was shown.

Jane: The acceptance test stays aligned with the evidence. If the optimizer saw those failures, it has to actually fix them.

Tom: An accepted child gets scored on the full validation split. Then the backup: the child sends its value up the ancestry, and every ancestor gains a visit and a value sample.

Jane: And a rejected mutation?

Tom: It produces no document and no score, so it backs up a visit only. No value sample.

Jane: Why keep those two counters apart?

Tom: Because a failure indicates where not to look, not a sample of a region's quality. If you conflated them, a run of failed rewrites would depress the estimate of a region that was never shown to be worse.

Jane: So rejected proposals decay the exploration term and move the search on, but Q stays untouched.

Lu: The counters are doing epistemology, not just bookkeeping.

Tom: Exactly. The search learns from failures without letting them poison its map of the terrain.

Jane: One thing still bothers me. A node could be expanded forever. What stops that?

Page 4 of the paper: Tom: Page four answers that. Progressive widening — a node may hold only so many children, and the ceiling grows sublinearly with its number of value samples.

Jane: Standard device for spaces with unlimited actions, and text rewrites are unlimited.

Tom: But the subtle part is keying the cap on m rather than N. A stream of rejected mutations raises N but not m, so failures can never reopen a node for further offspring.

Jane: A node earns more children only by producing scored ones. That's a nice incentive structure.

Tom: Then shipping. When the budget runs out, they ship the plain highest-fitness document — arg max v — and evaluate the test split once.

Jane: Given all that cleverness, that sounds almost too simple.

Tom: It's deliberate. Any rule that discounted a document by its brittleness would penalize the nodes the search probed most. A well-probed node has a visible sigma, while an unprobed leaf has Q equal to v and no gap to charge.

Jane: So such a rule would reward ignorance. Unprobed documents would look safe by default.

Tom: Shipping stays separate from steering. Evolvability decides where budget gets spent; the final answer is still the best-scoring document.

Jane: Then page four introduces the graft operator, and that's where things get spicy.

Tom: Grafting transfers a capability across lineages. One branch of the tree learns a family of tasks that another branch keeps failing, and no ordinary rewrite can recover that difference because the optimizer has no idea the technique exists elsewhere.

Jane: So the graft shows the optimizer a donor.

Tom: Deliberately asymmetric. The selected node gets revised into an ordinary child, and the donor plays the role of evidence rather than ancestry. The donor receives no visit and no value sample.

Jane: The tree structure stays a tree. Every quantity keeps its meaning.

Tom: Grafting has to earn its use. Each node accumulates per-task scores for free during selection, so they can compare. The payload is the set of tasks where the donor outscores the selected node; the guardrail is where the selected node outscores the donor.

Jane: Payload must be big enough, and only then does the graft fire.

Tom: And it's one-sided, which is clever. A donor that dominates the selected node outright is the most informative case, and a symmetric criterion would refuse it.

Jane: The optimizer restates the donor's technique in the selected node's own terms. The child is admitted only if it beats the parent on the shown set and doesn't lose any guardrail task.

Lu: So partial credit transfers correctly. A donor that lifts a task's score without fully solving it still contributes.

Meng: That's more subtle than solved-versus-unsolved.

Tom: And grafting shows up in the numbers on SpreadsheetBench. That's where the payoff lands.

Page 5 of the paper: Jane: The method is complete. Page five sets the stage for the experiments — and it's a carefully built stage.

Tom: Three benchmarks. SpreadsheetBench gives a natural-language instruction and an Excel workbook. The performer writes a Python script, it runs in a sandbox, and the output workbook is compared cell by cell against gold.

Jane: Fully objective grading. No human judgment anywhere in the loop.

Tom: Fixed split: 80 train, 40 validation, 280 test.

Jane: SearchQA?

Tom: Quiz questions with retrieved passages. The performer returns one short answer in a single attempt, scored by exact match after normalization. Four hundred train, two hundred validation, fourteen hundred test.

Jane: And LiveMathematicianBench?

Tom: Math statements with five closely-worded options. The performer returns one choice label. It's the smallest split — 60 train, 60 validation, 57 test — and the skill-free agent scores just 17.74 percent.

Jane: Huge headroom there. That's where the search can really stretch.

Tom: The performer is granite-4.1-30b, frozen, at temperature zero. The optimizer is DeepSeek-V3.2 at temperature 0.7. Same pairing for every arm.

Jane: Budgets?

Tom: Roughly 2,400 performer rollouts on SpreadsheetBench, 18,000 on SearchQA, 3,000 on LiveMathematicianBench. A rollout is one attempt by the performer at one task.

Jane: And every reported result is a single run at seed 42. They're honest about that later.

Tom: The constants are fixed: lambda one, cw one, alpha one half, first layer of four children.

Lu: What about the baselines?

Tom: GEPA keeps a Pareto frontier of prompts where each member is best on at least one validation task, and mutates a member sampled from it. SkillOpt treats the skill as trainable state, reflecting on minibatches but routing edits through an evidence-blind merge and ranking step.

Jane: Evidence-blind — that's the phrase. The merge stage sees the edits and their justifications, but not the trajectories that produced them.

Tom: Both are budget-matched. Same performer, same optimizer, same seed document, same splits, same scorer, same measured budget. Only the organization of the search differs.

Meng: Even the reflection minibatch structure is matched.

Jane: So when BONSeye pulls ahead, the margin is attributable to search strategy, not to better raw edits.

Tom: That's the cleanest possible comparison. And they evaluate no-skill and seed-skill rows to set the scale.

Jane: I'm ready for the scoreboard. Page six?

Page 6 of the paper: Jane: Page six is the scoreboard. Let's start with the headline numbers.

Tom: On SpreadsheetBench, no skill at all gets 7.50. The hand-written seed gets 17.50 — so writing the seed by hand is worth ten points. GEPA reaches 21.07, SkillOpt 20.00.

Jane: And BONSAI?

Tom: BONSeye hits 23.21, and with grafting enabled it reaches 25.00. That's 2.14 points over the strongest budget-matched baseline.

Jane: SearchQA is tighter.

Tom: No skill is already 72.50 there. The seed is a bare stub that basically doesn't help. BONSeye reaches 79.00 against GEPA's 78.29.

Jane: Slim margin, but still ahead.

Tom: LiveMathematicianBench is the blowout. Seed at 28.23, GEPA at 56.14, SkillOpt at 59.65, BONSeye at 64.91.

Jane: Clearing GEPA by 8.77 points on a 57-item test. That's a real gap.

Tom: The ablation in Table 2 is the cleanest evidence. Same tree, same acceptance rule, same shipped document rule — only the selection signal changes. Lambda one, evolvability, versus lambda zero, raw fitness.

Jane: And evolvability wins everywhere. Plus 3.21 on SpreadsheetBench, plus 2.14 on SearchQA, plus 7.02 on LiveMathematicianBench.

Tom: The mechanism shows up in when each search stalls. The greedy run hits a validation peak early and then churns. On SearchQA, the greedy best stops rising at iteration 13; the evolvability run keeps climbing to iteration 23.

Jane: Same pattern on the other benchmarks. Greedy reaches a peak quickly, evolvability keeps discovering higher-scoring documents deeper into the run.

Tom: The budget analysis on SpreadsheetBench is revealing too. Five nodes take 58 percent of all visits. The tree is deep rather than wide, exactly what selection on Q should produce.

Jane: And brittleness stays low — 27 of 32 nodes at sigma less than or equal to zero.

Tom: Acceptance is selective: 31 of 131 proposals admitted. Rejected proposals redirect the search rather than waste it.

Lu: The graft on SpreadsheetBench is active throughout the run and ships at 25 percent. On the other two benchmarks it rarely fires because lineages converge.

Jane: They also list limitations honestly. Single run per benchmark, one performer-optimizer pairing, small acceptance batches of five to eight tasks.

Tom: The small batch is the real ceiling. Its reliability bounds what any search built on it can achieve.

Jane: Still, three benchmarks, consistent ordering, and an ablation that isolates the signal. The pattern holds.

Conclusion: Jane: The scoreboard's done. Time to step back and ask what this paper actually leaves us with.

Tom: The final message is compact. BONSeye turns skill optimization into an evolvability-guided search, and every child in the tree is a mutation of its parent. The selection rule weighs a region's evolvability against a skill's own fitness.

Jane: Budget flows to regions that keep improving while a weak branch stays in contention. And the measurement costs nothing beyond the accept-if-better loop it replaces.

Tom: That's the part I keep coming back to. Free signal, self-sharpening, embedded in the search itself.

Jane: The numbers support it. Five-point-seven-one points over the seed on SpreadsheetBench, 2.14 over the strongest baseline there, and the biggest gap on LiveMathematicianBench.

Tom: And the ablation pins the gain to the idea rather than to the tree structure.

Jane: Same tree, same acceptance, same shipping — only the selection signal changed, and evolvability won on all three benchmarks.

Lu: I think the wider implication is the cost structure. If you can measure terrain productivity without extra evaluations, that technique generalizes beyond skills.

Meng: And grafting — asymmetric capability transfer with evidence rather than ancestry — feels like it could become a standalone tool.

Lalam: The larger arc: agents keep getting bigger and more frozen, so the instruction layer becomes the only handle. This paper makes that handle sharper.

Jane: There are open edges. Single runs, one performer-optimizer pair, the scratchpad in the appendix described but not evaluated.

Tom: A lineage memory for failed mutations, assembled fresh when needed, with an observer that compacts it. That's untested potential.

Jane: Think about what it costs to use this today. A team with a frozen model and a validation set can run it — no gradient, no fine-tuning cluster, just reflective edits arranged in a tree.

Tom: That accessibility matters. The technique is heavy in ideas, light in infrastructure.

Jane: And the biological framing might be the durable contribution. Evolvability separate from fitness — once you see it, you see it everywhere.

Tom: Optimization landscapes have shape, and the shape predicts the future.

Lalam: For the wider field, the message is that how you search matters as much as what you find.

Jane: The validation discipline deserves a mention too. The test set is touched exactly once, at the very end.

Tom: That discipline is what makes the held-out numbers trustworthy.

Jane: Untested potential is a good note to end on. This feels like the beginning of a line of work, not the end.

Tom: Agreed. A lot to watch from IBM Research.

Jane: And we've got the next paper waiting. Let's see what's on the stack.

Tom: Let's do it.