acceptodds
Under review as a conference paper at ICLR 2027

SkillVine: Agent Skill Evolution via Branching Exploration

Abstract

Agent skills encapsulate reusable procedural knowledge that enables LLM agents to perform tasks, and they can be improved automatically using trajectories from interactions with the environment. This is the classic problem of skill evolution. Existing approaches predominately follow a linear evolution paradigm, in which updates are sequentially applied to the latest skill-library version. As a result, they inevitably fall into local optima, leaving many promising evolution paths unexplored. We propose SkillVine, an automatic skill-evolution framework that formulates skill evolution as a graph search problem and employs a branching exploration strategy. Equipped with a trunk-branch collaborative searching mechanism, an intelligent parent-node selector, and an adaptive-granularity update rule, SkillVine achieves a balance between exploration and exploitation. We evaluate SkillVine on 5 benchmarks with two LLMs. Results show that SkillVine discovers better skill-library versions along branches than along the linear trunk and achieves the best test performance in nine of ten benchmark–model combinations.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Agent Skills, Self-Evolving Agents, Branching Exploration, LLM Agents, Skill Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_GbZSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

SkillVine replaces single-path skill optimization with a search over a graph of skill versions. A trunk follows the standard linear update, and at each step branches grow from historical versions selected by validation accuracy, expansion count, and complementarity with the trunk. When the trunk update is rejected, branches accept their edits one at a time. Across five benchmarks and two models, SkillVine achieves the best test score in nine of ten settings.

Critical strengths

S1. Framing skill evolution as search over a version graph is a natural and general extension of linear evolution. Keeping earlier versions and allowing new branches from them addresses a clear failure mode of linear methods, which stall when successive updates are rejected. The framework can also be built directly on top of existing linear optimizers.

S2. The evaluation covers five benchmarks and two models, and SkillVine achieves the best test score in nine of the ten settings. The ablations and the evolution-path analysis further show that the choice of where to branch affects the result.

Critical weaknesses

W1. The comparisons do not fully control for compute. Best-of-3 and Random try the same number of updates per step as SkillVine. However, when the trunk update is rejected, SkillVine tests each edit separately on the validation set, so it runs more validation evaluations in total. The paper acknowledges this extra cost but reports cost only for its own variants, not for any baseline. The paper itself also notes that producing more candidates increases the chance of finding a better version. It is therefore unclear how much of the gain comes from branching rather than from these extra evaluations.

W2. AGBU relies on an assumption that is not well supported. It assumes that if a training batch leads to harmful edits for the trunk, it will also lead to harmful edits for the branches. But each branch proposes its own edits from a different skill version, so this need not hold. The paper supports the assumption with only two selected examples. The rationale for using the trunk outcome to decide how branches are updated is therefore weak.

Questions for authors

Q1. Please report the training rollouts and validation evaluations used by every method, and compare SkillVine with methods such as Best-of-N under the same number of validation evaluations. This would show whether the gains come from branching or from the additional evaluations.

Q2. AGBU assumes that a batch harmful to the trunk is also harmful to the branches. How was this conclusion reached, and what evidence supports it?

Q3. What motivates the form of the selector score, and how were λexp = 0.08, λcomp = 0.5, and β = 1.6 chosen? The paper reports no sensitivity analysis for these coefficients. It also states that mixing discovery and refinement selectors yields more consistent gains, but reports no comparison with either selector alone.

8 comments
AuthorsOpenReview ↗

Response to Weakness-1 and Question-1

We thank the reviewer for recognizing the value of our version-graph search, its compatibility with existing linear optimizers, and the breadth and strength of our experimental results, and for the helpful suggestions.

The table below shows each method’s ratio of total validation rollouts to total training rollouts in the original Table 1:

ModelMethodSpreadsheetLiveMathOfficeQASearchQATABVERSE
DeepSeek-v4-FlashLinear1.09691.21532.25004.87502.6250
Best-of-31.01561.05322.08334.29822.5417
Random1.01561.05322.08334.52592.5417
SkillOpt0.88640.79551.55064.88372.2647
SkillOpt-Lite0.79770.39771.39563.60471.6471
Hermes-SE1.16932.20722.33334.54133.1755
SkillVine1.82811.37732.083310.86214.8750
Qwen3.8-FlashLinear1.09691.21532.25005.12502.6250
Best-of-31.01561.05322.08335.04172.5417
Random1.01561.05322.08335.04172.5417
SkillOpt0.88640.79551.55064.88372.2647
SkillOpt-Lite0.79770.66291.39564.76742.0588
Hermes-SE0.84651.78432.19878.82353.0320
SkillVine1.46251.37732.941710.08335.1667

These ratios vary across benchmarks because we follow SkillOpt-Lite’s dataset splits, which use very different training and validation set sizes. For example, SearchQA and SpreadsheetBench both use 40 training examples per update, but each validation pass uses 200 examples on SearchQA and only 39 on SpreadsheetBench. Validation therefore costs more relative to training on SearchQA.

The original experiments did not enforce equal validation budgets for the following reasons:

  • Linear serves as the simplest single-path baseline.
  • Best-of-3 and Random add two branch attempts per step, matching SkillVine’s number of candidate updates. They do not use AGBU because it is one of our core designs in SkillVine. Adding AGBU would turn them into ablation variants of our method. For example, w/o Selector in Table 2 is Random + AGBU.
  • SkillOpt and SkillOpt-Lite keep their own components, including slow updates across epochs and meta updates for the optimizer. SkillVine does not use these components and uses branch exploration instead. The original experiments therefore compare the benefits of each method’s own components.

To make the source of our gains clearer, we added budget-matched experiments for all baselines except Linear, which remains a naive reference. Its budget-matched counterpart is effectively budget-matched Best-of-3. At each step, these baselines match SkillVine’s validation evaluation count while keeping their own update acceptance rules. All methods use exactly the same training-batch construction procedure. For Hermes-SE, we retain its node-selection and path-evolution logic within SkillOpt-Lite. Implementation details unrelated to path evolution, such as the prompts used to generate skill updates, remain the same as SkillVine’s. This allows us to compare search strategies under the same setup.

The results are as follows:

ModelMethodSpreadsheetLiveMathOfficeQASearchQATABVERSE
DeepSeek-v4-FlashLinear48.0443.4047.3073.3663.88
Best-of-363.7050.0045.2771.5063.88
Random66.9046.2352.7070.7962.65
SkillOpt65.4850.0048.6571.5062.45
SkillOpt-Lite66.5550.4852.0370.6462.86
Hermes-SE59.4337.7447.3069.7158.57
SkillVine71.5353.7755.4174.4367.35
Qwen3.8-FlashLinear66.9036.7950.0072.1460.82
Best-of-366.9034.9144.5970.9359.80
Random63.3537.7447.3070.7160.20
SkillOpt65.8436.6841.8972.2161.63
SkillOpt-Lite63.3538.6842.5771.2960.20
Hermes-SE62.2833.0247.3071.7960.61
SkillVine67.9739.6254.0572.4063.67

SkillVine still performs best with the same validation budget. This suggests that its gains come from using the budget more effectively, rather than simply running more evaluations.

AuthorsOpenReview ↗

Response to Weakness-2 and Question-2

Thank you for this helpful comment!

We analyzed the w/o AGBU runs to measure the correlation between the trunk’s acceptance or rejection and performance drops in both branches at the same training step. The results are shown below. “Both ↓” means that both branch candidates have lower validation scores than their own parents.

ModelTrunkBoth ↓Not both ↓
DeepSeek-v4-FlashAccepted36.4%63.6%
DeepSeek-v4-FlashRejected79.1%20.9%
Qwen3.8-FlashAccepted50.0%50.0%
Qwen3.8-FlashRejected83.9%16.1%

The table shows that both branches are much more likely to lose performance when the trunk update is rejected. This shows a strong association and supports using trunk acceptance or rejection as a signal for AGBU.

The reason is that updates are largely guided by the training trajectories. Even when the trunk and branches have different parents, they can learn the same skill from the same training batch. For example, one parent may lack that skill, so the update adds it. Another may have an older version, so the update replaces it with the same new skill. Both updates therefore lead to the same skill content.

AuthorsOpenReview ↗

Response to Question-3

Thank you for this helpful suggestion.

Equation (3) considers three factors:

  • Validation accuracy q(v)q(v) favors strong parent nodes. Improving an already strong version can help raise the best score found during evolution.
  • Complementarity λcompCt(v)\lambda_{\mathrm{comp}}C_t(v) encourages branches to explore capabilities that the trunk lacks. This helps branches follow different paths rather than spend the budget on similar directions.
  • The exploration bonus λexplog⁡(Nexp+1)/(nexp(v)+1)\lambda_{\mathrm{exp}}\sqrt{\log(N_{\mathrm{exp}}+1)/(n_{\mathrm{exp}}(v)+1)} gives less-expanded nodes more opportunities. When validation scores and complementarity repeatedly favor the same nodes, this bonus reduces concentration on a few paths and keeps other versions available for exploration.

Together, these terms guide the search toward promising but different evolution paths. Compared with Best-of-3, SkillVine avoids concentrating all updates on one current version. Compared with Random, it uses both node performance and complementarity with the trunk to guide exploration.

We set the current coefficients based on observations from actual runs to keep each term at an appropriate scale and ensure that variations in its value meaningfully distinguish candidate nodes.

We tested how λexp\lambda_{\mathrm{exp}} and λcomp\lambda_{\mathrm{comp}} in Eq. (3) affect performance on SpreadsheetBench using DeepSeek-v4-Flash. We changed one coefficient at a time while keeping the others fixed. The results are shown below:

λexp\lambda_{\mathrm{exp}}λcomp\lambda_{\mathrm{comp}}Test Score
0.0010.569.75
0.080.571.53
10.566.90
50.563.35
0.50.0565.12
0.50.2565.84
0.50.569.75
0.5167.97

The table shows that performance tends to drop when λexp\lambda_{\mathrm{exp}} increases or λcomp\lambda_{\mathrm{comp}} decreases. These changes make the selector rely more on node scores and exploration rewards, and less on complementarity. This highlights the importance of complementarity in node selection.

We also varied the gain reward and regression penalty coefficients in Eq. (4), while keeping λexp=0.5\lambda_{\mathrm{exp}}=0.5. We used the existing SkillVine run on SpreadsheetBench with DeepSeek-v4-Flash and recalculated branch node selection at each training step. Each calculation used only the nodes available at that step. We then checked how many steps kept the original parent choices before the first difference. The results are shown below:

Varied coefficientValuesMatching prefixFirst divergence
Gain reward0, 0.001, 0.1, 0.253/8Step 4
Gain reward0.5, 0.8, 1, 27/8Step 8
Gain reward5, 10, 100, 10008/8None
Regression penalty0, 0.001, 0.1, 0.53/8Step 4
Regression penalty0.8, 1, 2, 5, 107/8Step 8

The results show that increasing either coefficient puts more weight on complementarity. The selector then makes the same parent choices as the original run for more steps.

To address your second concern, we tested two alternatives to the mixed selectors: two refinement selectors and two discovery selectors. We used the same compute budget for comparison.

Using two refinement selectors corresponds to our budget-matched Best-of-3 experiment. The results are shown below:

ModelMethodSpreadsheetLiveMathOfficeQASearchQATABVERSE
DeepSeek-v4-FlashBest-of-363.7050.0045.2771.5063.88
SkillVine71.5353.7755.4174.4367.35
Qwen3.8-FlashBest-of-366.9034.9144.5970.9359.80
SkillVine67.9739.6254.0572.4063.67

For two discovery selectors, we tested the five model–benchmark combinations where parent choices differ from those in the original mixed-selector runs. The results are shown below:

ModelSelectorOfficeQASearchQATABVERSE
DeepSeek-v4-FlashDiscovery only—70.2956.33
Mixed (SkillVine)—74.4367.35
Qwen3.8-FlashDiscovery only50.6870.7160.20
Mixed (SkillVine)54.0572.4063.67

The results show that mixed selectors outperform refinement-only selection in all ten combinations and discovery-only selection in all five tested combinations. This supports using discovery and refinement together rather than either alone.

Reviewer_nYKnOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

See below.

Critical strengths

The paper propose a graph based structure help to select good evolution path. This structure will help the method avoid the cummulated errors and avoid the skill shadowing (this words are mentioned by authors). the paper looks technically good with comprehensive design and priciple design on reward and model selection. The experiments design looks good on 2 different base models, designed comparisons and 5 benchmarks.

Critical weaknesses

The contribution looks not very strong, as there is also some other kind of graph/tree based strategy before like GraphSkillEvo and MetaSkill-Evolve, the paper need a careful literature position not a very general position. Given the previous works on graph based skills edition and evolution, authors should provide other evidence that this paper is not just an incremental contribution. Or did much more desgn on this graph based framework. Another weakness would be the efficiency and storage cost, as it is a kind of tree based strategy and need to select parents from the pool.

Questions for authors
  1. How do you get equation 3, it looks like a bandit UCB style selection, will it have a follow up regret analysis?
  2. As the paper use a graph/tree based structure, the edit on child nodes will not only influence the edit of their direct parents, but also should have to consider about in direct parents node, for example, in the graph A->B, A->C, C->D, sometimes, use chunk on A to edit D is better than using Chunk on C. This is one of the cases, when think about graph frameworks, a more careful analysis on differnt atom units in the graph and special suggraph cases should be considered carefully.
  3. In experiment part, the efficiency on token cost for specifc preformance milestone should be reported. I’m also curious about the cross domain/tasks abilities.
7 comments
AuthorsOpenReview ↗

Response to Weakness-1

We thank the reviewer for recognizing the value of our graph-based evolution, the soundness of our method design, and the breadth of our experiments, and for the helpful suggestions.

We address the concerns raised in Weakness-1.

Regarding your first concern:

  • GraphSkillEvo and SkillVine operate at different conceptual levels in their graph elements and search focus. In GraphSkillEvo, nodes represent agent execution steps, edges represent conditional transitions between steps, and paths describe task execution. In SkillVine, nodes represent complete skill-library versions, edges represent parent–child updates, and paths trace version evolution process. GraphSkillEvo primarily designs the structural representation of skills and its mutation and crossover operators. SkillVine instead focuses on organizing, selecting, and scheduling the search over skill-library versions.

  • MetaSkill-Evolve selects skill versions based on their performance, their ability to produce better child versions, and an exploration bonus. SkillVine instead emphasizes cross-path comparison to guide both branch selection and branch updates. For branch selection, SkillVine considers each node’s capability complementarity with the trunk, encouraging exploration of alternative paths that address the trunk’s weaknesses. For branch updates, it uses the trunk’s acceptance or rejection as a signal to adjust update granularity, helping avoid repeating harmful updates. These cross-path signals provide a broader basis for search decisions and more effective use of the exploration budget.

Regarding your second concern:

  • Latency overhead. Node selection reuses cached validation scores. This requires no additional model inference. According to our measurements, searching and ranking candidate nodes takes only 0.01–2.39 seconds. Branch updates within each step can run in parallel, so adding more branches does not necessarily increase runtime proportionally.

  • Compute overhead. The trade-off between computation and performance is inherent to branch-based search and unavoidable. The key is to use the compute budget efficiently. In our additional experiments, all methods use the same number of validation rollouts per step. SkillVine still performs better, showing that it uses the evaluation budget more efficiently. Please see our response to Question 3 below for details.

  • Storage overhead. In our experiments, each node takes about 5 KB–1.8 MB, including its skill snapshot and metadata. The full version graph takes 2.1–115.7 MiB, so it adds little storage overhead.

  • For larger production systems, we could consider dynamically pruning the version graph to keep it small and make search and storage efficient. We could also use Git-style storage, where each node stores only its changes from its parent. We will discuss these costs and possible improvements in the paper.

AuthorsOpenReview ↗

Response to Question-1 (Part - 1/2)

We thank the reviewer for this comment!

Equation (3) considers three factors:

  • Validation accuracy q(v)q(v) favors strong parent nodes. Improving an already strong version can help raise the best score found during evolution.
  • Complementarity λcompCt(v)\lambda_{\mathrm{comp}}C_t(v) encourages branches to explore capabilities that the trunk lacks. This helps branches follow different paths rather than spend the budget on similar directions.
  • The exploration bonus λexplog⁡(Nexp+1)/(nexp(v)+1)\lambda_{\mathrm{exp}}\sqrt{\log(N_{\mathrm{exp}}+1)/(n_{\mathrm{exp}}(v)+1)} gives less-expanded nodes more opportunities. When validation scores and complementarity repeatedly favor the same nodes, this bonus reduces concentration on a few paths and keeps other versions available for exploration.

Together, these terms guide the search toward promising but different evolution paths. Compared with Best-of-3, SkillVine avoids concentrating all updates on one current version. Compared with Random, it uses both node performance and complementarity with the trunk to guide exploration.

Standard UCB regret analysis does not directly apply to our setting for two reasons.

  • First, standard UCB estimates an arm’s expected reward from repeated observations under a fixed reward distribution. In our setting, each expansion uses a different training batch. Even for the same parent node, the gain can vary greatly across batches. Its average gain on earlier batches may therefore be a poor estimate of its gain on the current batch. Our node score measures current performance and complementarity, rather than estimating future expansion gains.

  • Second, the node pool grows during evolution. Selecting and expanding a node creates new versions and changes the paths available for later steps.

We therefore use a UCB-style bonus to encourage exploration of less-expanded nodes, but do not claim a standard UCB regret guarantee. We nevertheless provide a regret bound for our selector, followed by a short proof:

A. Definition and interpretation

Let s=1,…,Ms=1,\ldots,M index node-selection decisions that apply Eq. (3), and let As\mathcal A_s be the nonempty eligible parent-node pool at decision ss. Write

fs(v)=q(v)+λcomp,sCs(v),f_s(v)=q(v)+\lambda_{\mathrm{comp},s}C_s(v),

\sqrt{\frac{\log(N_{\mathrm{exp},s}+1)} {n_{\mathrm{exp},s}(v)+1}}.$$ Here, $f_s(v)$ combines validation accuracy and complementarity, and $b_s(v)$ is the exploration bonus. The expansion counts are those available when the selector is called. The selected parent satisfies $$v_s\in\arg\max_{v\in\mathcal A_s}\{f_s(v)+b_s(v)\}.$$ This allows the Discovery selector and Refinement selector to use different coefficients. It also allows the reference trunk, complementarity scores, and eligible node pool to change. The validation-accuracy and complementarity terms have an exact gain–regression interpretation. Let $m=|D_{\mathrm{val}}|$, let $p_s$ be the reference trunk’s validation accuracy, and define $$g_s(v)=\frac{|D_v^+\cap D_{\mathrm{tr},s}^-|}{m}, \qquad \ell_s(v)=\frac{|D_{\mathrm{tr},s}^+\setminus D_v^+|}{m}.$$ These are the fractions of validation examples newly solved and lost relative to the trunk. Since $q(v)=p_s+g_s(v)-\ell_s(v)$, Eq. (4) gives $$\begin{aligned} f_s(v) ={}&p_s+ \left(1+\frac{\lambda_{\mathrm{comp},s}}{1-p_s}\right)g_s(v)-\left(1+\frac{\lambda_{\mathrm{comp},s}\beta}{p_s}\right)\ell_s(v). \end{aligned}$$ Thus, complementarity increases the reward for unique gains and the penalty for regressions. This identity assumes $0<p_s<1$. The bounds below only require finite scores and also allow an explicit finite convention for empty denominators. The coefficients control this trade-off; they are not derived from a confidence inequality. Define node-selection regret as $$R_M^{\mathrm{sel}}= \sum_{s=1}^{M} \left[ \max_{v\in\mathcal A_s}f_s(v)-f_s(v_s) \right].$$ It measures the combined validation-accuracy and complementarity score given up when the exploration bonus leads to a different parent choice. The comparison uses the same eligible pool on the version graph actually generated by SkillVine. Any parents excluded from selection are also excluded from the comparison.
AuthorsOpenReview ↗

Response to Question-1 (Part - 2/2)

B. Node-selection bound

Assume that, for every decision,

\qquad N_{\mathrm{exp},s}\le E.$$ Also assume that, at the $j$-th selection of any parent node $v$, $$n_{\mathrm{exp},s}(v)+1\ge j.$$ Let $m_v$ be the number of decisions selecting $v$, and let $K=|\{v:m_v>0\}|$. Then $$\begin{aligned} R_M^{\mathrm{sel}} &\le \bar\lambda\sqrt{\log(E+1)} \left(2\sum_{v:m_v>0}\sqrt{m_v}-K\right)\le2\bar\lambda\sqrt{KM\log(E+1)}. \end{aligned}$$ Proof. Let $v_s^\star\in\arg\max_{v\in\mathcal A_s}f_s(v)$. The selection rule gives $$f_s(v_s)+b_s(v_s) \ge f_s(v_s^\star)+b_s(v_s^\star).$$ Since the exploration bonuses are nonnegative, $$0\le f_s(v_s^\star)-f_s(v_s) \le b_s(v_s)-b_s(v_s^\star) \le b_s(v_s).$$ Summing and grouping decisions by selected parent gives $$R_M^{\mathrm{sel}} \le \bar\lambda\sqrt{\log(E+1)} \sum_{v:m_v>0}\sum_{j=1}^{m_v}j^{-1/2}.$$ The first bound follows from $$\sum_{j=1}^{m}j^{-1/2} \le1+\int_1^m x^{-1/2}\,dx =2\sqrt m-1.$$ The second follows from Cauchy–Schwarz: $$\sum_{v:m_v>0}\sqrt{m_v} \le\sqrt{K\sum_v m_v} =\sqrt{KM}.$$ C. Parallel branches and scope Assume each parent selection produces at least one evaluated child that increases its expansion count. If at most $h-1$ earlier expansions of that parent have not yet updated the count, then at its $j$-th selection, $$n_{\mathrm{exp},s}(v)+1\ge\max\{1,j-h+1\}\ge j/h.$$ The same proof gives $$R_M^{\mathrm{sel}}\le2\bar\lambda\sqrt{hKM\log(E+1)}.$$ If counts are updated before the next batch of $k$ branch assignments, we may take $h\le k$. This bound measures the current score given up for exploration on ranking decisions. It does not guarantee future evolution gains or final-library performance. We will include a more detailed proof and analysis in the revised paper’s appendix.
Reviewer_vhzaOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

SkillVine addresses the limitations of linear LLM agent skill evolution, which often overwrites useful prior skills and gets trapped in local optima, by formulating the process as a budget-constrained graph search problem. Its core contributions include a recoverable version graph with a trunk-branch update strategy, a complementarity-aware node selector to branch from historical checkpoints that address the trunk's weaknesses, and an adaptive-granularity branch update rule to filter out noisy or harmful edits. Evaluated across five benchmarks and two base LLMs against six baselines, SkillVine achieved the highest test performance in nine of ten benchmark and model combinations, with every optimal final skill library discovered along an exploratory branch rather than the linear trunk.

Critical strengths
  • Reframing lifelong skill evolution from sequential linear patching to a recoverable graph search over skill-library snapshots, which combines a continuous trunk with complementarity-aware side branches, is consequential because it directly overcomes skill overwriting and local optima within a fixed optimization budget.
  • Achieving top performance in nine of ten benchmark and model combinations, with every optimal final skill library discovered along an exploratory branch rather than the linear trunk, provides unambiguous evidence that branching exploration unlocks superior skill libraries compared to linear evolution.
Critical weaknesses
  • Evaluating candidate skill libraries on a validation distribution for both the optimization objective and node selection incurs substantial inference overhead, limiting applicability in open-ended lifelong settings where clean validation sets are unavailable.
  • Evolving each exploratory branch on only a subset of training batches and selecting a single winning node at the end discards useful complementary skills learned along separate branches or the trunk rather than merging them into a unified library.
Questions for authors
  • Since node selection and update evaluation both require testing candidate skill libraries on a validation set, how much total inference cost is spent on validation relative to training, and do the six linear baselines receive an equivalent total compute budget?
  • Because parent selection and update acceptance rely heavily on validation accuracy, how does SkillVine perform when the validation set is small, noisy, or shifted relative to the test distribution?
  • Could a post-hoc merge or distillation operator be introduced to combine non-conflicting skills from multiple top branches into a single unified library, rather than discarding useful skills discovered on sibling branches?
5 comments
AuthorsOpenReview ↗

Response to Weakness-1 and Question-2

We thank the reviewer for recognizing the value of our graph-based skill evolution, branch exploration, and experimental results, and for the helpful suggestions.

We address the concerns raised in Weakness-1 and Question-2 below.

  • Regarding the inference overhead, SkillVine does not rely on a specific node validation method. Our focus is on finding better skill evolution paths more effectively within a limited exploration budget. How the validation performance is obtained is a separate design choice. Our current implementation builds on SkillOpt-Lite and uses the full validation set for each evaluation, so the cost depends on the size of the validation set. Cheaper alternatives, such as scoring on just a handful of representative examples, could also be used. In addition, the selector can reuse cached validation scores without evaluating the nodes again. To further address your concern, we ran additional experiments matching each baseline’s per-step validation budget to SkillVine’s. As reported in our response to Q1, SkillVine still achieves the best overall performance. It also achieves the highest validation score at the most milestones in 8 of the 10 model–benchmark combinations (See our response to Question-3 of Reviewer-nYKn for details). These results suggest that even when the baselines receive the same compute budget as SkillVine, SkillVine still uses the compute budget more efficiently.

  • Regarding the concern about the lack of clean validation sets, this work follows the validation-gated skill optimization setting used by SkillOpt and SkillOpt-Lite: within the target domain, we use training trajectories to propose skill updates, then accept or reject them based on validation performance. Our focus is on choosing better evolution paths when performance scores for skill versions are available. Evolution in open-ended settings raises an orthogonal question: how to obtain reliable validation data in more challenging settings. We agree that this is a valid practical concern. One promising direction is to continually add representative samples to the validation set while pruning the version graph and refreshing node scores. We will discuss this setting in the paper and explore it in future work.

AuthorsOpenReview ↗

Response to Weakness-2 and Question-3

We thank the reviewer for the insightful comment!

We agree that different branches can acquire complementary skills, and we have also explored merging skills from different branch nodes into a single final library. However, we found that merging does not consistently improve performance and may require substantial extra evaluation.

First, a skill usually brings both gains and regressions across validation examples. Here are some concrete examples:

  • SearchQA, Qwen3.8-Flash: The skill “Use surname only for historical figures if commonly referred to as such” helped questions requiring “Gogol” but hurt those requiring full names, such as “Charles Dickens” or “James Boswell.” The version containing this skill corrected five validation examples but lost six previously correct answers.

  • Tabverse, DeepSeek-v4-Flash: A skill treated facts absent from the table as unsupported. This helped identify missing evidence about a staff member’s dismissal, but changed a correct “false” answer about an athlete’s non-participation to “not enough information,” despite the table showing the athlete’s tournament results.

  • SearchQA, DeepSeek-v4-Flash: A skill encouraged plural answers for “these” questions and group names. It helped produce the correct toy name “Furbies,” but changed the correct shared surname “Sharpe” for Shannon and Sterling to “the Sharpes.” The expected answer was their shared surname, “Sharpe.”

Most skills, like the three examples above, help on some samples but hurt on others. The full library’s performance depends on how all its skills work together. When merging two skill libraries without seeing the validation and test samples, it is hard to tell from the skill text alone how much a skill would help or hurt the library’s performance. In addition, there are also many ways to split and combine the skills, so testing every combination is not practical, either.

Second, most skills do not show clear semantic conflicts, but they can still affect each other. For example:

  • Tabverse, DeepSeek-v4-Flash: Skill A required listing answers in table row order, while Skill B covered true-or-false claims. Despite no clear conflict, adding A to a library containing B also changed true-or-false answers: it corrected a claim about Lauryn Williams’s races but lost a correct answer about a staff member’s dismissal.

  • SearchQA, Qwen3.8-Flash: Skill A says not to use prefixes such as “Answer:”. Skill B tells the model how to choose factual answers from the context. We added Skill A to a library containing Skill B. The two skills have no clear conflict, but factual answers also changed. The model corrected a question about an Ohio city but got a previously correct question about checking drinking age wrong.

These examples show that it is hard to quantify how each pair of skills may affect each other from their text alone. With so many possible skill combinations, testing each skill’s effect through separate ablations on the validation set is also impractical.

In fact, each evolution path already performs selective accumulation. It accepts skills that improve the parent’s performance and rejects those that do not. Merging does something similar: it selects skills learned from a subset of training batches and combines them into the final skill library.

Exploiting complementary knowledge across branches is a valuable direction. We will add this discussion to the paper and explore better ways to reuse knowledge across branches and nodes in future work.

AuthorsOpenReview ↗

Response to Question-1

We thank the reviewer for this comment!

For each of the 10 model–benchmark combinations, we computed each method’s ratio of total validation rollouts to total training rollouts over the full training process. The results are as follows:

ModelMethodSpreadsheetLiveMathOfficeQASearchQATABVERSE
DeepSeek-v4-FlashLinear1.09691.21532.25004.87502.6250
Best-of-31.01561.05322.08334.29822.5417
Random1.01561.05322.08334.52592.5417
SkillOpt0.88640.79551.55064.88372.2647
SkillOpt-Lite0.79770.39771.39563.60471.6471
Hermes-SE1.16932.20722.33334.54133.1755
SkillVine1.82811.37732.083310.86214.8750
Qwen3.8-FlashLinear1.09691.21532.25005.12502.6250
Best-of-31.01561.05322.08335.04172.5417
Random1.01561.05322.08335.04172.5417
SkillOpt0.88640.79551.55064.88372.2647
SkillOpt-Lite0.79770.66291.39564.76742.0588
Hermes-SE0.84651.78432.19878.82353.0320
SkillVine1.46251.37732.941710.08335.1667

The ratios vary widely across benchmarks because we use SkillOpt-Lite’s data splits, which differ significantly by benchmark. For example, SearchQA and SpreadsheetBench both use training batches of 40 examples, but their validation sets contain 200 and 39 examples, respectively.

In the original experiments, all methods used the same train/validation/test splits, training batches, and number of training steps. However, we did not enforce the same total compute budget across methods, for the following reasons:

  • Linear serves as the simplest single-path evolution baseline.
  • Best-of-3 and Random add two branch attempts per step, matching SkillVine’s number of candidate updates. They do not use AGBU because it is a core component of SkillVine. Adding AGBU would make them ablation variants of our method. In fact, w/o Selector in Table 2 is Random + AGBU.
  • SkillOpt and SkillOpt-Lite keep their own components, such as slow updates to learn from past epochs and meta updates to improve the optimizer. SkillVine does not include these components and uses branch exploration instead. The original experiments treat each method’s own components as its strengths.

Following the reviewer’s suggestion, we added budget-matched experiments for all baselines except Linear. We keep Linear as a naive baseline. The budget-matched version of Best-of-3 is effectively the budget-matched version of Linear. At each training step, all baselines except Linear run the same number of validation evaluations as SkillVine. Each method keeps its own rules for accepting or rejecting updates. For Hermes-SE, we use its node-selection and path-evolution logic in the SkillOpt-Lite framework. Other parts, such as skill updates and training batches, are the same as in SkillVine. This lets us compare the search strategies under the same setup.

The results are as follows:

ModelMethodSpreadsheetLiveMathOfficeQASearchQATABVERSE
DeepSeek-v4-FlashLinear48.0443.4047.3073.3663.88
Best-of-363.7050.0045.2771.5063.88
Random66.9046.2352.7070.7962.65
SkillOpt65.4850.0048.6571.5062.45
SkillOpt-Lite66.5550.4852.0370.6462.86
Hermes-SE59.4337.7447.3069.7158.57
SkillVine71.5353.7755.4174.4367.35
Qwen3.8-FlashLinear66.9036.7950.0072.1460.82
Best-of-366.9034.9144.5970.9359.80
Random63.3537.7447.3070.7160.20
SkillOpt65.8436.6841.8972.2161.63
SkillOpt-Lite63.3538.6842.5771.2960.20
Hermes-SE62.2833.0247.3071.7960.61
SkillVine67.9739.6254.0572.4063.67

The results show that SkillVine still performs best under the same budget. This suggests that its gains come from using the budget more effectively, rather than from having extra compute.

Comments on the paper

1 comment

Thank you for your thoughtful follow-up and for clarifying your remaining concerns.

Novelty and Comparison with Existing Work

  • Our paper identifies a conflict between diverse exploration and sustained experience accumulation. Multi-path search aims to explore different evolution directions rather than repeatedly follow similar ones. However, frequently switching starting points can spread the budget across many short paths, leaving each with too few consecutive updates to build on earlier improvements. A selector alone cannot reliably solve this problem. Based on this insight, SkillVine explicitly assigns different roles to the trunk and branches. The trunk maintains a continuous path that processes every training batch, while branches explore alternative directions. Unlike methods such as MetaSkill-Evolve, SkillVine enforces the distinct roles of the trunk and branches through its path structure rather than relying solely on node ranking to decide which paths to extend. We believe this insight and design provide a useful principle for future work on branching agent skill evolution.

  • Our cross-path comparison goes beyond search and node selection. The trunk serves two distinct roles: its validation results show which capabilities branches can complement, while its current update outcome determines how finely branch edits are evaluated. SkillVine uses the trunk’s update outcome at the same training step to control the branch update operator. We analyzed the w/o AGBU runs to examine the relationship between trunk acceptance or rejection and branch performance drops at the same step. “Both ↓” means that both branch candidates score strictly lower than their own parents.

ModelTrunkBoth ↓Not both ↓
DeepSeek-v4-FlashAccepted36.4%63.6%
DeepSeek-v4-FlashRejected79.1%20.9%
Qwen3.8-FlashAccepted50.0%50.0%
Qwen3.8-FlashRejected83.9%16.1%

Both branches are much more likely to lose performance when the trunk update is rejected. This association supports using the trunk’s outcome to guide branch updates.

Q1. UCB-like Node Selection Strategy

In our agent self-evolution setting, future training batches are not visible at the current step. The outcome of an update depends heavily on the training data used to generate it. Without knowing future batches, it is therefore difficult to predict from a node’s skill content alone how well it will perform after an update based on those unseen batches. Existing work in similar settings, such as MetaSkill-Evolve, GraphSkillEvo, SkillOpt-Lite, and SkillOpt, does not provide rigorous theoretical guarantees on the gains from updates based on unseen future training batches or on the quality of the final skill produced by evolution. We also believe that gains from past child nodes cannot precisely predict the gains of future children when future training data are unknown.

Our goal is to explore diverse, high-quality evolution paths, including those missed by linear evolution, and increase the chance of finding high-quality skills. The complementarity term encourages branches to explore directions different from the trunk’s. Our UCB-style exploration bonus does not assume that a low visit count means higher future gains. Instead, it aims to avoid repeatedly spending the exploration budget on nodes that may have structural problems. In the frequently selected nodes we inspected, some skill libraries contained many broad requirements without clear conditions, exceptions, or priorities. Even with high validation and complementarity scores, these nodes may struggle to incorporate new skills without causing regressions. Repeatedly spending more budget on these nodes can therefore be wasteful. As their expansion counts increase, the exploration bonus decreases, giving other nodes more opportunities.

The UCB-style exploration bonus also helps distinguish nodes when validation and complementarity scores are too similar, spreading the exploration budget more evenly.

We would greatly appreciate your further feedback and the opportunity to continue this discussion. We are willing to make any further improvements needed to strengthen our work and make a useful contribution to the community.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.