🤖 AI

BONSAI: Evolvability-Guided Tree Search over Skills

BONSAI is a novel skill-optimization framework for frozen agents that employs evolvability-guided Monte Carlo tree search to distinguish between overfitting spikes and improvable plateaus, significantly outperforming existing baselines in heldout accuracy.

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

Published 2026-08-10

📖 6 min read🧠 Deep dive

CC0 1.0

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

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a super-smart robot how to do a complex job, like fixing a spreadsheet or solving a tricky math problem. The catch? The robot is "frozen." Its brain is locked in place; you cannot retrain it, tweak its neurons, or let it learn from its mistakes the way a human student does. The only way to make it better is to write it a set of instructions—a "skill"—in plain English. Think of this skill not as a simple command, but as a detailed field manual that tells the robot exactly which tools to grab, what pitfalls to avoid, and how to double-check its work before handing in the answer.

The big question scientists are asking is: How do you write the perfect manual? If you just try a few changes, test them, and keep the ones that work, you might get stuck. It's like hiking up a mountain where the map only shows your current altitude. You might reach a tiny, sharp peak that looks high, but it's so narrow that the next step takes you straight off a cliff. Or, you might be on a wide, gentle plateau where every step forward leads to even higher ground, but you can't tell the difference just by looking at your current height. This paper introduces a new way to navigate this landscape, using a concept borrowed from biology called "evolvability"—the ability of a path to keep producing good results even when you take a wrong turn.

The Problem: The Trap of the "Sharp Peak"

The researchers at IBM Research noticed a flaw in how we usually improve these AI manuals. The standard method is simple: take a manual, ask the AI to rewrite it, test the new version, and if the score goes up, keep it. If it goes down, throw it away.

The problem is that this method is "blind." It only looks at the score of the current manual. It can't tell the difference between a manual sitting on a broad plateau (a safe, stable area where small changes usually lead to even better results) and a manual perched on a narrow, overfit spike (a fragile peak where the score is high, but any tiny change causes the score to crash). If you are on a spike, the next edit might fix one small error but break ten other things that were working perfectly. The standard method keeps walking off the cliff because it only sees the high score, not the danger.

The Solution: BONSAI and the "Evolvability" Compass

To fix this, the team created a new framework called BONSAI. Instead of just looking at how good a manual is right now, BONSAI asks: "How good is the neighborhood around this manual?"

They use a clever metaphor from nature: Evolvability. In biology, a species isn't just judged by how well it survives today, but by its ability to keep producing useful offspring in the future. A species on a "broad plateau" can mutate and still survive; a species on a "sharp spike" dies out if it changes even a little.

BONSAI treats the search for the perfect manual like growing a tree.

The Tree: It starts with one "seed" manual.
The Branches: Every time the AI tries to rewrite the manual, it grows a new branch (a child node).
The Compass: When deciding which branch to explore next, BONSAI doesn't just pick the branch with the highest score. It picks the branch that looks like it has the best future. It calculates a score called Evolvability, which is basically the average score of all the little changes (mutations) made to that manual.

If a manual is on a "spike," its neighbors will have terrible scores, and the evolvability score will be low. BONSAI avoids it. If a manual is on a "plateau," its neighbors will also have good scores, and the evolvability score will be high. BONSAI dives deep into these safe, productive areas.

How It Works: The "Graft" Trick

The researchers added a special feature called GRAFT. Imagine you have two branches of the tree: one branch learned how to handle "math problems," and another branch learned how to handle "spreadsheets." They are on different paths and never talk to each other.

Usually, the AI can't combine these skills because it only looks at one manual at a time. But GRAFT allows the AI to peek at the "math" branch, see a trick that works, and copy that trick into the "spreadsheet" manual. It's like a gardener taking a strong branch from one tree and grafting it onto another to give it new powers. This happens without breaking the tree structure, allowing the AI to mix and match the best ideas from different parts of its search.

The Results: Climbing Higher

The team tested BONSAI on three different challenges:

SpreadsheetBench: Fixing Excel files.
SearchQA: Answering quiz questions using search results.
LiveMathematicianBench: Solving math problems.

They used a frozen 30-billion-parameter AI agent (the "performer") and a separate AI to write the manuals (the "optimizer"). They compared BONSAI against two other methods, GEPA and SkillOpt, making sure everyone used the same amount of computing power (the same "budget").

The results were clear:

On SpreadsheetBench, BONSAI improved the accuracy by 5.71 points over the starting manual and beat the best competitor (GEPA) by 2.14 points.
On SearchQA, it improved by 6.57 points over the starting manual.
On LiveMathematicianBench, the gap was huge. BONSAI reached 64.91% accuracy, while the starting manual was only at 28.23%, and the competitor GEPA was at 56.14%.

The researchers found that when they turned off the "evolvability" compass and just let the AI greedily chase the highest score (like the old methods), the AI got stuck on those "sharp peaks" early and stopped improving. BONSAI, however, kept finding better solutions deeper into the search because it knew which paths were safe to explore.

The Takeaway

The paper suggests that to make frozen AI agents smarter, we shouldn't just look for the highest score right now. We should look for the most promising neighborhood. By using a tree-search method that values stability and future potential (evolvability) over immediate, fragile wins, BONSAI found better instructions for the AI to follow. It didn't need to retrain the AI's brain; it just needed to write a better field manual, and it did so by knowing which paths were safe to walk down.

Technical Summary: BONSAI – Evolvability-Guided Tree Search over Skills

1. Problem Statement

The paper addresses the challenge of optimizing skills for frozen agents. A "skill" is defined as a natural-language document (acting as a field manual rather than a simple prompt template) that guides a frozen Large Language Model (LLM) whose weights cannot be updated. Since the agent cannot learn from experience, any capability it lacks must be encoded in the skill text.

The standard approach to skill optimization involves an iterative loop: edit the skill based on agent failures, test on held-out tasks, and retain edits that improve the score. The authors identify a critical blind spot in this method: a single validation score cannot distinguish between a document resting on a broad plateau (robust to further edits) and one perched on a narrow spike (overfit and brittle). A document on a narrow spike may score highly but is a dead end, as further edits tend to break existing capabilities. Existing methods lack a way to measure the "evolvability" of a skill region—the capacity to produce viable variations under mutation—without incurring extra computational costs.

2. Methodology: BONSAI

BONSAI (Bonsai Optimisation via Natural-language Search and Adaptive Iteration) reframes skill optimization as a Monte-Carlo Tree Search (MCTS) guided by evolvability rather than just immediate fitness.

Core Components

Models: Two frozen models are used.
- Performer: The frozen agent (e.g., granite-4.1-30b) that executes tasks based on the skill.
- Optimizer: A second frozen model (e.g., DeepSeek-V3.2) that rewrites the skill based on the performer's failures.
Tree Structure: Skills are organized into a tree where the root is a seed document. Every edge represents a mutation (a reflective rewrite) of the parent node. This structure imposes a neighborhood topology on the document space.

Key Metrics

Fitness ( $v(n)$ ): The validation score of the document at node $n$ .
Evolvability ( $Q(n)$ ): Defined as the expected fitness of a skill's mutational neighborhood. It is estimated by the mean fitness of the node's lineage (the node itself plus all its descendants).
$Q(n) = \frac{1}{m(n)} \sum_{s \in L(n)} v(s)$
where $L(n)$ is the lineage and $m(n)$ is the count of scored members.
Brittleness ( $\sigma(n)$ ): The gap between current fitness and evolvability: $\sigma(n) = v(n) - Q(n)$ $σ (n) = v (n) - Q (n)$ .
- $\sigma > 0$ : Indicates a brittle, overfit peak (current score is higher than the neighborhood average).
- $\sigma \le 0$ : Indicates an evolvable region (the neighborhood holds up or improves upon the current score).

Search Algorithm

The search proceeds in iterations using an Upper Confidence Bound (UCB) selection rule:
$U(s) = v(s) + \lambda(Q(s) - v(s)) + c\sqrt{\frac{\ln N(p)}{N(s)}}$

Exploitation: The term $\lambda(Q(s) - v(s))$ steers the search toward regions with high evolvability. When $\lambda=1$ , the search prioritizes $Q(s)$ (evolvability) over raw fitness $v(s)$ .
Exploration: The standard UCB term ensures weak branches are revisited.
Acceptance: A proposed child is accepted only if it strictly improves on a small training minibatch (Eq. 4).
Backup: Accepted children update the lineage statistics ( $N$ , $m$ , $W$ ). Rejected mutations update only the visit count $N$ , preventing failed rewrites from artificially depressing the evolvability estimate of a region.
Widening: Nodes have a sublinear capacity for children based on the number of scored samples, ensuring the search remains deep rather than wide.

Grafting (Optional Operator)

To address capability fragmentation across different branches of the tree, BONSAI includes a graft operator. If a node $A$ lacks a capability that a cross-lineage node $B$ possesses (determined by comparing per-task scores on training data), the optimizer is asked to rewrite $A$ to incorporate $B$ 's technique. The donor $B$ acts as evidence, not ancestry, and receives no visit updates.

Shipping

Upon exhausting the budget, BONSAI ships the single document with the highest validation score ( $\arg\max v(n)$ ), not the one with the highest evolvability. This ensures the final output is the best-performing document found, while evolvability serves solely as a steering mechanism for the search budget.

3. Key Contributions

Evolvability as a Steering Metric: The authors identify robustness under mutation (evolvability) as the critical property for skill optimization, distinguishing it from present fitness.
Cost-Free Estimation: They propose a method to measure evolvability ( $Q$ ) that incurs zero extra model calls. It reuses fitness scores already paid for during the search to estimate the quality of the mutational neighborhood.
Tree-Based Search Framework: BONSAI converts an unordered collection of candidates into a structured search space where neighborhood properties can be measured and optimized via MCTS.
Asymmetric Capability Transfer: The introduction of the graft operator allows the transfer of specific capabilities between lineages without merging documents, addressing the issue of skills diverging in capability.

4. Experimental Results

The framework was evaluated on three benchmarks using a frozen 30B performer and a DeepSeek-V3.2 optimizer.

SpreadsheetBench: BONSAI improved the seed document by 5.71 accuracy points and outperformed the budget-matched baseline GEPA by 2.14 points. With Grafting enabled, it reached 25.00% accuracy.
SearchQA: BONSAI improved over the seed by 6.57 points and outperformed GEPA by 0.71 points (79.00% vs 78.29%).
LiveMathematicianBench: BONSAI achieved 64.91% accuracy, outperforming the seed (28.23%) by a large margin and beating GEPA by 8.77 points.
Comparison with SkillOpt: Across all benchmarks, BONSAI outperformed the second baseline, SkillOpt, by an average of 3.97 points. The authors attribute SkillOpt's shortfall to its aggregation stage, which compresses edits without seeing the underlying trajectories.
Ablation (Evolvability vs. Greedy): When the selection signal was changed to pure greedy fitness ( $\lambda=0$ ), performance dropped significantly across all benchmarks (e.g., -7.02 points on LiveMathematicianBench), confirming that steering by evolvability is the primary driver of success.

5. Significance and Claims

The paper claims that BONSAI successfully steers the search budget toward regions of the skill space that continue to yield improvements, rather than getting trapped on narrow, overfit peaks. By treating evolvability as a distinct property from fitness, the method avoids the "blind spot" of standard score-based optimization.

The authors emphasize that this improvement is achieved at no extra cost beyond the standard accept-if-better loop, as the evolvability metric is derived from existing search data. The framework demonstrates that for frozen agents, the "terrain" of the skill space (its capacity to evolve) is as important as the current "elevation" (score). The results suggest that organizing skill optimization as a tree search guided by mutational robustness yields superior generalization on held-out tasks compared to existing reflective prompt evolution or trainable-state approaches.