BONSAI: Evolvability-Guided Tree Search over Skills

arXiv:2608.07056 · cs.AI · Submitted 2026-08-07 · Read on arXiv

Listen

Transcript

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.

Yash Priya Shastri, Anand Eswaran, Adnan Qidwai, Pankaj Thorat, Sachin Joshi

IBM Research

cs.AI

Submitted: 2026-08-07

Updated: 2026-08-10

License: http://creativecommons.org/publicdomain/zero/1.0/

Importance score: 70/100

The gist: The paper addresses the problem of optimizing skills—natural-language documents that steer a frozen agent whose weights cannot be updated—for task performance.

Key concepts

Skill: A short, practical text document that instructs a frozen AI model on how to perform tasks—which library to use, what to verify, and how to handle edge cases. It's the only thing the optimizer can edit, and every accuracy improvement must come through rewriting this prose.
Evolvability: A property of a skill's mutational neighborhood—how likely future edits are to keep improving performance, rather than just how well the skill scores now. A skill on a broad plateau is evolvable; one on a narrow spike is brittle and likely to collapse with the next edit.
Tree search with upper-confidence bound: The optimizer builds a tree where each child is a mutation of its parent. A selection rule balances exploitation (using evolvability estimates) and exploration (trying weak branches). Progressive widening limits children per node, and grafting transfers successful techniques between branches.
Free measurement of evolvability: Evolvability is estimated by the average fitness of a node's lineage—all descendants reached by mutation. This uses fitness scores the search already computed, so it costs no extra model calls. The estimate sharpens as the search probes a node more, making it both free and self-improving.

Terminology

Benchmark — 25× in this paper · explained in 2 episodes
Accuracy — 12× in this paper · explained in 1 episode
Aggregation — 4× in this paper · explained in 1 episode
Robustness — 4× in this paper · explained in 5 episodes
Steering — 3× in this paper · explained in 2 episodes
Ablation — 1× in this paper · explained in 1 episode
Adaptation — 1× in this paper · explained in 1 episode
Agent Skills — 1× in this paper · explained in 1 episode
Core — 1× in this paper · explained in 2 episodes
Generalization — 1× in this paper · explained in 13 episodes
Iterative Refinement — 1× in this paper · explained in 3 episodes
Reinforcement Learning — 1× in this paper · explained in 4 episodes

Summary

The paper addresses the problem of optimizing skills—natural-language documents that steer a frozen agent whose weights cannot be updated—for task performance. The authors frame the core difficulty: A frozen agent cannot learn from experience: its weights are fixed, so it cannot be trained further. Whatever it is to do well must instead be told to it, in text. Since the skill is the only object an optimiser can touch, and every point of accuracy must be bought with prose, the standard recipe—keep any edit that raises a held-out score—is blind in a specific way: a single score cannot tell a document perched on a narrow, overfit spike from one resting on a broad plateau, even though only the second can still be improved.

The paper draws an analogy to optimization theory (flat vs. sharp minima) and biology: biology treats evolvability, the ability of a lineage to keep producing useful variants, as a property separate from present fitness. The authors note that What has been missing for skills is a way to measure this property that does not cost more than the search it guides.

The paper states three contributions. First, it identif[ies] robustness under mutation, that is, evolvability, as the property a skill optimiser should steer by, and give[s] a measurement of it that costs no extra model calls. Second, it turns that measurement into a search: "Growing skills as a tree whose every child is a mutation makes the mean fitness beneath a node a measure of its region's evolvability, and we steer an upper-confidence tree search by that measure, with a selection rule that blends a skill's own fitness with its neighbourhood's. Third, on SpreadsheetBench at equal and measured budget, BONSAI improves on the seed document it starts from by 5.71 accuracy points on held-out tasks and exceeds the strongest budget-matched baseline by 2.14," with the same ordering on SearchQA and LiveMathematicianBench.

Two models play distinct roles, neither trained: The performer is the frozen agent: it reads the skill, attempts a task, and is scored automatically. The optimizer is a second model that never attempts tasks itself, reading a small number of the performer's scored attempts (task, produced answer, reason for incorrectness) and returning a rewritten skill. Data is split into train (small batches prompt each rewrite), validation (used to score whole skills during search), and test (touched once at the end).

The search arranges skills into a tree: "The root is the fixed seed document, and an edge from node n to node c means that c was produced by mutating n, that is, by one reflective rewrite. This single construction choice is what the remainder of the method rests upon: it converts an unordered collection of candidate documents into a space with neighbourhood structure, and a neighbourhood is something that can be measured."

The paper defines fitness v(n) as the validation score—the fraction of held-out tasks it solves—noting Fitness is a point estimate, and two documents that score alike can differ sharply in what surrounds them. Evolvability is defined as "the expected fitness of a skill's mutational neighbourhood: for a mutation operator that maps a skill to a child, the evolvability of a skill s is ϵ(s) = E[v(s′)], the expectation taken over the children s′ mutation produces from s, and, transitively, over the region of skill-space reachable from s by repeated mutation. Evolvability belongs to a region rather than to a single document, reporting not how a skill performs today but how well its future is likely to perform."

Since the region is unbounded, the search tree provides a free, self-improving estimator. Letting L(n) = n ∪ desc(n) be node n's lineage and m(n) count lineage members scored so far, the lineage's mean fitness estimates ϵ(n), called the node's evolvability value: Q(n) = (1/m(n)) Σ s∈L(n) v(s). The gap σ(n) = v(n) − Q(n) is called brittleness: A large positive σ marks a brittle, overfit peak. A σ at or below zero marks a document typical of, or even bettered by, a strong neighbourhood, the signature of an evolvable region.

Two properties make Q worth having: "First, it is free: every term in (1) is a fitness value the search already paid for, so no extra calls are spent measuring it. Second, it sharpens itself: each expansion beneath n adds a sample to Q(n), so the nodes probed most heavily are exactly those whose evolvability estimate becomes best resolved."

BONSAI is a Monte-Carlo tree search with a selection rule built to steer by evolvability. Starting at the root, the search descends, choosing at each level the child maximizing:

U(s) = v(s) + λ(Q(s) − v(s)) + c√(ln N(p)/N(s))

At λ = 1, which we use throughout, the exploitation term is exactly Q(s), so evolvability leads the search. At λ = 0 the rule reduces to plain fitness. The exploitation term is rescaled to [0,1] by the smallest and largest fitness recorded anywhere in the tree, a running normalisation adapted from MuZero—this makes the exploration constant c scale-free across benchmarks. The third term is the standard exploration bonus: a node whose neighbourhood currently appears weak still draws visits, so that an early verdict can be revised rather than standing.

Expansion and acceptance: The optimizer proposes one child, kept only if it strictly improves on the same batch of training tasks the optimizer was shown: Σ i∈B g i(c) > Σ i∈B g i(n), where g i is per-task score and B the batch. Judging the proposal on the batch that produced it keeps the acceptance test aligned with the evidence behind the edit. An accepted child is scored on the full validation split to obtain fitness v(c).

Backup: An accepted child sends its value up the ancestry: for every ancestor a, N(a) += 1 and W(a) += v(c), where W accumulates backed-up scores and Q(a) = W(a)/m(a). A rejected mutation produces no document and no score, so it backs up a visit only: m(a) += 1, N(a) += 1, with m(a) and W(a) unchanged. The paper stresses: "Keeping the two counters apart matters more than it may appear. A failure indicates where not to look. It is not a sample of a region's quality... Conflating the counters would allow a run of failed rewrites to depress the estimate of a region that was never shown to be worse."

Widening: A node's children ceiling grows sublinearly in its number of value samples: children(n) < c w m(n) α, 0 < α < 1, standard progressive widening. "Keying (7) on m rather than on N has a consequence worth stating: a stream of rejected mutations raises N but not m, so it can never reopen a node for further offspring. A node earns more children only by producing scored ones."

Shipping: When budget is exhausted, BONSAI ships n* = arg max n v(n), the plain highest-fitness document, and evaluates test once on it. "Evolvability decides only where budget is spent, and shipping is deliberately kept separate. Any rule that discounted a document by its brittleness would penalise the nodes the search probed most: a well-probed node has a visible σ, whereas an unprobed leaf has Q = v and no gap to charge, so such a rule would reward ignorance. The search never reads the test set."

The graft operator addresses the problem that Capability can end up divided across lineages: one branch of the tree learns to handle a family of tasks that another branch continues to fail. The selected node A acquires a capability that a cross-lineage node B demonstrably possesses and that A lacks. The operator is "deliberately asymmetric: rather than combine two documents into a third, it produces a revision of A that enters the tree as an ordinary child of A, with the donor B playing the role the reflection batch plays in any other expansion, namely that of evidence rather than ancestry. The donor receives neither a visit nor a value sample."

Each node accumulates at no additional cost a record C n of per-task scores. Over tasks on which A and B have both been scored, define the payload B+ = i: C B(i) > C A(i) and the guardrail A+ = i: C A(i) > C B(i). Membership is a per-task score comparison rather than a solved/unsolved cutoff, so partial credit transfers correctly. Grafting fires only when B+ ≥ τ. This one-sided gate admits even a donor that dominates A outright, the most informative case, which a symmetric criterion would refuse. The shown set S = B+ ∪ A+ ∪ D also carries anchors D—tasks on which the two already score alike, so the comparison is not taken purely on the tasks that separate them. The child is admitted only if Σ g(c) > Σ g(A) and g i(c) ≥ g i(A) for all i ∈ A+ ∩ S. The second makes the operator safe: because A+ is by construction the tasks on which A outscores the donor, a child that merely reproduces the donor scores no higher than the donor there, below A, and is rejected. When A+ is empty, an additional condition requires the child to beat the donor's total on S.

Benchmarks: SpreadsheetBench (instruction + input.xlsx workbook; performer writes a Python script, executed in a sandbox, compared cell-by-cell against golden output; split 80 train / 40 validation / 280 test). SearchQA (quiz-style question with retrieved passages; single short answer scored by exact match; split 400 train / 200 validation / 1400 test). LiveMathematicianBench (mathematical statement with five candidate answers; single choice label scored by exact match; split 60 train / 60 validation / 57 test). Within each benchmark the objective is exact match alone. Partial credit is computed and logged but never steers the search.

Models: The performer is granite-4.1-30b, frozen, at temperature 0, and the optimizer is DeepSeek-V3.2 at temperature 0.7 throughout. Budgets: roughly 2400 performer rollouts on SpreadsheetBench, 18,000 on SearchQA, and 3000 on LiveMathematicianBench, with every reported search result being a single run at seed 42. Constants: λ = 1, c w = 1, α = 1/2, first layer of 4 children.

Baselines: GEPA [1], a reflective prompt-evolution method that keeps a Pareto frontier of candidates, a set in which each member is best on at least one validation task, with its machinery untouched and only shared inputs matched, with both arms counting only uncached performer calls so a rollout means the same in each. SkillOpt [14], which treats the skill as trainable state—it reflects on minibatches of trajectories but "routes those edits through an evidence-blind aggregation: a hierarchical merge reconciles and deduplicates them and a ranking step keeps the top edits under a learning-rate budget, both stages seeing the edits and their written justifications but not the trajectories that produced them."

SpreadsheetBench (Table 1): No skill 7.50%; Seed skill 17.50% (+10.00); GEPA 21.07% (+13.57); SkillOpt 20.00% (+12.50); BONSAI 23.21% (+15.71); BONSAI + GRAFT 25.00% (+17.50). The paper notes: writing the seed by hand is worth 10.00 points over giving the agent no instruction at all, and searching onward from it adds a further 5.71.

SearchQA: No skill 72.50%; Seed skill 72.43% (−0.07); GEPA 78.29% (+5.79); SkillOpt 75.57% (+3.07); BONSAI 79.00% (+6.50); BONSAI + GRAFT 78.93% (+6.43). the seed is a bare stub rather than a field manual and a skill-free agent already answers 72.50% of the questions, so essentially the whole of BONSAI's 6.57-point gain over the seed is attributable to the search.

LiveMathematicianBench: No skill 17.74%; Seed skill 28.23% (+10.49); GEPA 56.14% (+38.40); SkillOpt 59.65% (+41.91); BONSAI 64.91% (+47.17); BONSAI + GRAFT 63.16% (+45.42). LiveMathematicianBench is where the gap is widest: BONSAI reaches 64.91% against a seed of 28.23% and a skill-free 17.74%, clearing GEPA by 8.77 points.

The abstract summarizes: averaged over three benchmarks, BONSAI lifts held-out accuracy over the skill-free agent by 23.13 points and improves on two budget-matched baselines, GEPA and SkillOpt, by 3.87 and 3.97 points respectively.

SkillOpt's shortfall is "concentrated in aggregation rather than reflection. The per-minibatch analyst edits are useful, but the merge and rank stages compress them sharply, a single step routinely dropping from seventeen candidate edits to three... the method depends on the optimizer's ability to judge edits in the abstract more than the single grounded rewrite GEPA and BONSAI use."

GRAFT results: where lineages converge on nearly the same tasks it rarely triggers and defaults to the ordinary rewrite—this is what SearchQA and LiveMathematicianBench show, within a single held-out task of the base method. On SpreadsheetBench, where lineages differentiate more, grafting is active throughout the run and the shipped skill reaches 25.00%.

"Budget is unevenly allocated: the five most-visited nodes below the root take 58 percent of all visits, and the tree reaches depth 4 across 32 documents, deep rather than wide, as selection on Q should produce. Brittleness stays low, with 27 of the 32 nodes at σ ≤ 0 and the range spanning −0.069 to +0.089. The acceptance test (4) is selective, admitting 31 of 131 proposals... Optimizer calls number 131, and evolvability adds to neither, since (1) reuses scores already paid for."

To isolate evolvability's contribution, the same search is rerun with λ = 0 (exploitation term is raw fitness v rather than Q). Only the selection signal changes. On all three benchmarks, steering by evolvability wins on held-out test: SpreadsheetBench 23.21 vs 20.00 (+3.21); SearchQA 79.00 vs 76.86 (+2.14); LiveMathematicianBench 64.91 vs 57.89 (+7.02). The mechanism: Greedy selection reaches a validation peak early and then stalls, spending the rest of the budget on a region that no longer improves, while evolvability keeps discovering higher-scoring documents deeper into the run. For example, on SearchQA the greedy run's best validation score stops rising at iteration 13 (0.760) while the evolvability run climbs to 0.775 by iteration 23. Because both arms ship arg max v and share every other component, the held-out gap is attributable to the selection signal alone.

The paper acknowledges: "The evidence is a single run per benchmark with one performer and optimizer pairing. Because BONSAI and the baseline differ both in tree structure and in the selection signal (λ = 1 on Q), the reported gain against the baseline reflects the search strategy as a whole—though Section 3.4 isolates the evolvability component holding the tree fixed. The scratchpad is described but not evaluated, and the acceptance test (4) is decided on a small batch of five to eight tasks, so its reliability bounds what any search built on it can achieve... a limitation shared with the baseline and one that binds hardest where a small batch discriminates weakly, as it does on SearchQA."

The paper distinguishes BONSAI from GEPA: "Its notion of diversity is therefore instance diversity: a candidate survives because it is exceptional on some subset of the validation tasks. Our notion of diversity is completely different. A node survives because its neighbourhood remains productive under mutation... A Pareto frontier over validation instances encourages preservation of prompts that explain idiosyncratic variation in the sampled validation set. BONSAI instead allocates budget according to mutational robustness, a property of the optimisation landscape rather than of a finite validation sample. Against SkillOpt: it cannot reconsider a region it has left and splits reflection from composition such that the composition step leans on optimizer strength where our single grounded rewrite does not. Both decide on a point estimate. BONSAI can also return to an earlier region when a later one stops paying."

"BONSAI turns skill optimisation into an evolvability-guided search: by growing every child as a mutation and descending with the upper-confidence rule (3), whose exploitation term weighs a region's evolvability against a skill's own fitness, it steers budget toward the regions that keep improving. On SpreadsheetBench, at an equal budget, it beats the strongest budget-matched baseline by 2.14 held-out points and the document it starts from by 5.71, at no added cost."

The appendix describes a per-lineage scratchpad giving mutation a memory. After each rewrite attempt, the optimizer is asked to name, in two or three short lines, exactly what it changed, filed at the version it revised as a success or did-not-work entry. Only did-not-work entries are ever resurfaced, so the optimizer is not steered toward proposing the same change twice under a different phrasing. Entries compose along the tree—when a version is selected, its did-not-work entries plus those on the path back to the root are gathered, oldest first, deduplicated, most recent kept when the path is long. An Observer compacts a version's own list once it reaches five new entries, merging near-duplicates and holding it to six. Neither model is ever told it is exploring a tree: an entry is phrased only as a change already tried on this instruction and the outcome it had, so the vocabulary of the search itself never leaks into a prompt.

Improvements for AI systems

An improved AI system based on BONSAI would be a skill optimizer for frozen LLM agents that treats every natural-language skill as a node in a mutation tree and steers search by evolvability rather than raw validation accuracy. Concretely, it can:

Find broad, improvable skill regions instead of overfit spikes.

Instead of keeping any edit that raises held-out score—which can land on a narrow, brittle peak—the system selects nodes using a lineage-mean fitness estimate Q(s). This measures the expected fitness of the mutational neighborhood around a skill. The improved system detects brittleness σ = v(s) − Q(s) and deprioritizes skills whose good score is not shared by nearby mutations.

Measure evolvability with zero extra model calls.

The system reuses every fitness score already computed during search as a sample of the region’s evolvability. So it can report which skill regions are likely to keep improving without spending additional budget on measurement.

Allocate search budget where future improvement is most likely.

Its selection rule blends a skill’s own fitness with its neighborhood’s evolvability, plus an exploration bonus: U(s) = v(s) + λ(Q(s) − v(s)) + c√(ln N(p)/N(s)). At λ=1, it descends into regions that are productively mutable, not merely currently accurate. This lets it keep discovering higher-scoring documents later in the run, where greedy fitness maximization stalls.

Use rejected mutations as information without contaminating region quality estimates.

The system keeps two counters: N (visits) and m (value samples). A failed rewrite increments N but not m or W, so a string of rejections cannot falsely depress the estimated quality of a region that was never shown to be worse. The improved system learns where not to look without penalizing unproven regions.

Judge each rewrite on the evidence that produced it.

A proposed child is accepted only if it improves on the same training batch shown to the optimizer: Σ g i(child) > Σ g i(parent). This keeps the acceptance test aligned with the edit’s actual rationale, reducing spurious improvements that do not generalize.

Transfer capabilities asymmetrically between lineages.

With GRAFT, the system lets one skill branch acquire a capability demonstrated by another branch, by producing a revision of A using donor B as evidence only—not as ancestry. It transfers only when B clearly outperforms A on enough tasks (B+ ≥ τ), preserves A’s own strengths via the guardrail A+, and rejects children that fail to retain A’s superior tasks. This lets capabilities converge instead of remaining fragmented across branches.

Ship the best-scoring document, not the most evolvable one.

At budget exhaustion, the system selects the plain highest-fitness validation document. Evolvability only decides where budget is spent; shipping is kept separate so that well-probed nodes are not penalized for having a visible brittleness gap.

Maintain per-lineage memory of failed rewrite attempts.

An optional scratchpad records what each mutation changed and whether it worked. Only did-not-work entries are resurfaced, oldest first, deduplicated along the tree path, so the optimizer does not repeatedly propose the same unsuccessful change under new phrasing. The improved system can avoid repeating its own past mistakes during skill search.

With these capabilities, the improved system can, for example:

Start from a single hand-written seed skill and automatically raise held-out task accuracy by +5.71 points on SpreadsheetBench, +6.50 on SearchQA, and +47.17 on LiveMathematicianBench over the seed, without training or updating the frozen performer.
Beat budget-matched skill optimizers GEPA and SkillOpt by +2.14 held-out points on SpreadsheetBench, +0.71 on SearchQA, and +8.77 on LiveMathematicianBench, using the same number of performer calls.
Continue improving past the point where greedy fitness-based search stalls, because it follows mutational robustness instead of a single current score.

Abstract

A skill is a naturallanguage document that steers a frozen agent whose weights cannot be updated so any capability the agent lacks must be supplied in prose Optimising a skill is therefore optimising text against a score and the standard recipe which keeps any edit that raises a heldout score is blind in a specific way a single score cannot tell a document perched on a narrow overfit spike from one resting on a broad plateau even though only the second can still be improved We introduce BONSAI a novel skilloptimisation framework that steers instead by evolvability the capacity of a region of documentspace to keep producing viable variation under further mutation a property biology treats as separate from present fitness BONSAI grows skills as a MonteCarlo search tree in which every child document is a mutation of its parent and descends it under an upperconfidence selection rule whose exploitation term blends a skills own fitness with the fitness of its mutational neighbourhood Because every child is a mutation the mean score recorded beneath a node estimates that neighbourhoods evolvability at no extra cost so the rule concentrates budget on regions that keep improving while its exploration term keeps a currently weak branch in contention BONSAI ships the single bestscoring document it finds at no cost beyond the acceptifbetter loop it replaces With a frozen 30B agent and averaged over three benchmarks BONSAI lifts heldout accuracy over the skillfree agent by 2313 points and improves on two budgetmatched baselines GEPA and SkillOpt by 387 and 397 points respectively