MultiEvoSkill: Structure-Aware Multi-Agent Skill Evolution for Generalizable Skill Artifacts

Kounianhua Du; Jianxing Liu; Ruoshui Shan; Yucheng Zhang; Ke Li; Xing Sun; Weinan Zhang

cs.AIOct 25, 2026

MultiEvoSkill: Structure-Aware Multi-Agent Skill Evolution for Generalizable Skill Artifacts

Authors: Kounianhua Du, Jianxing Liu, Ruoshui Shan, Yucheng Zhang, Ke Li, Xing Sun, Weinan Zhang

Organizations: Shanghai Jiao Tong University Shanghai, China · Purdue · Tencent

Abstract

Skill documents are becoming the default adaptation surface for frozen large language model (LLM) agents, but current skill generators face two key limitations. First, humans and different LLMs differ in how they organize procedural knowledge and approach task solving. Skills authored from a human or single-model perspective may therefore fail to align with the reasoning behaviors of other backbones, limiting cross-model generalization. Second, sequential skill descriptions inadequately represent procedures with parallel branches and explicit dependencies, while existing skill optimizers primarily operate on prose and lack explicit support for graph-structured skill evolution. We introduce MultiEvoSkill, a skill-optimization framework comprising three core components: 1) Skill compiler casts the skill as a typed graph with tailored operators, producing a compact, informative representation with explicit procedural topology; 2) Heterogeneous agent system proposes revision advices using collective intelligence, where minimal and informative issues are identified based on multiple sets of experiences. 3) Structure-aware debate and evolution mechanism organizes candidate edits into a heterogeneous graph, resolves them under dependency and importance constraints, and distills the collective proposal into the artifact. Multi-dimensional gating ensures the information gain and topological correctness of each evolution. Optimal skills are then obtained when the system converges at a consistent state. Various experiments and ablations against SOTA methods validate the effectiveness and generalization of MultiEvoSkill.

Figures & tables

Panel of Figure 1 — Figure 1: Illustration of two key advantages of our approach. (a) Graph-form skills explicitly encode procedural dependencies, branch conditions, and reusable actions, unlike linear prose. (b) Collective intelligence enables heterogeneous agents to exchange complementary experience and consolidate it into a single generalizable skill artifact.

Figure 2: Overview of MultiEvoSkill. Heterogeneous executors collect evidences for reflection; issue-specific proposer debates produce patches against one fixed parent. A hierarchical revisor merges patches, and the gate commits or rejects the resulting graph. Selection data enter the gate, not proposal generation.

Graph element	Procedural meaning
Decision 7	Decide whether results must remain formula-driven.
$7\xrightarrow{\mathrm{true}}8$	Create formulas with correct references when recalculation is required.
$7\xrightarrow{\mathrm{false}}9$	Compute and write materialized values when requested.
$8\to 10$ , $9\to 10$	Continue to row merging after the selected branch.
Node 10 label	Preserve existing order; append only missing keys.
Edge note	Explain a guard or ordering rationale.

Table 1: Graph–document correspondence for the spreadsheet formula/value branch. Original node IDs are retained.

Method	WikiHow	ToolAlpaca	WebShop	SearchQA	SpreadsheetBench
Trace2Skill	53.04	35.30	28.69	86.88	50.00
CoEvoSkills	53.90	33.13	31.58	87.78	83.93
SkillOpt	53.39	53.54	34.54	88.14	82.14
SkillBoost	54.24	35.81	28.72	80.80	83.21
SkillGen	54.56	33.65	29.12	87.38	58.21
MultiEvoSkill	55.58	53.88	34.77	88.25	86.07

Table 2: Test-set scores across five benchmarks. Bold indicates the best result in a column.

Sample type	Required procedure	Why prose is fragile	Graph behavior
Lookup	Identify key row and target column; return exact cell value.	Aggregation and formatting rules are irrelevant but appear in the same prose skill.	Activate lookup branch only; skip aggregation and formatting subgraphs.
Aggregation	Infer row filter, select numeric range, compute requested statistic, validate units.	Dependency order is implicit; model may compute before fully resolving the range.	Use explicit prerequisite and data-flow edges from range selection to computation.
Formula preservation	Detect formula-bearing cells, determine dependency relation, copy or extend formula safely.	Global instruction to “compute values” can conflict with formula preservation.	Activate formula branch guarded by formula-detection decision node.
Conditional formatting	Parse condition, locate cells, apply formatting, verify affected region.	Formatting is a separate operation but prose may mix it with value computation.	Activate formatting branch with its own validation node.

Table 3: The illustrative prose skill combines several workflows in one paragraph, whereas a typed skill graph explicitly represents different branches for different samples while sharing common upstream nodes.

Variant	WikiHow	ToolAlpaca	WebShop
w/o $\delta_{1}$	45.88	27.71	31.53
w/o $\delta_{2}$	50.75	43.85	32.88
w/o $\delta_{3}$	50.75	45.69	33.03
w/o $\delta_{4}$	54.64	51.69	33.45
Full	55.58	53.88	34.77

Table 4: Proposer-panel ablations.

Variant	WikiHow	ToolAlpaca	WebShop
w/o $g_{1}$	42.32	45.95	30.53
w/o $g_{2}$	41.23	45.40	30.11
w/o $g_{3}$	40.84	47.06	31.35
w/o $g_{4}$	49.07	46.88	33.31
w/o $g_{5}$	53.19	49.02	33.24
Full Gate	55.58	53.88	34.77

Table 5: Gating ablations.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Route	Representative methods
Trajectory distillation	Trace2Skill ( Ni et al., 2026 ) , SkillCAT ( Chen et al., 2026 ) , SkillEvolver ( Zhang et al., 2026a ) , Memento-Skills ( Zhou et al., 2026a ) , WikiSkill ( Tang et al., 2026 )
Execution-feedback refinement	SkillOpt ( Yang et al., 2026 ) , SkillBoost ( Lin et al., 2026 ) , SkillGrad ( Wang et al., 2026 ) , SkillRevise ( Liu et al., 2026 ) , EmbodiSkill ( Ju et al., 2026 )
Multi-agent evolution	CoEvoSkills ( Zhang et al., 2026b ) , SkillGen ( Ma et al., 2026 ) , MIND-Skill ( Li et al., 2026b ) , SkillHone ( Li and Hu, 2026 )
Population-based evolution	AgentPSO ( Hwang et al., 2026 ) , MOCHA ( Tanjim et al., 2026 ) , GEPA ( Agrawal et al., 2025 ) , EvoSkill ( Alzubi et al., 2026 )
Reinforcement-learning-based	D2Skill ( Tu et al., 2026 ) , SkillRL ( Xia et al., 2026a ) , SkillOS ( Ouyang et al., 2026 ) , Skill1 ( Shi et al., 2026b )

Appendix

Table 6: Major routes for agentic skill evolution.

Domain	$n_{0}$	$e$	$b$	$\epsilon$	$\tau$	$q_{0}$
WikiHow	40	4	40	.03	.01	.5
ToolAlpaca	40	4	40	.03	.01	.5
WebShop	40	4	40	.03	.01	.5
SpreadsheetBench	40	4	40	.10	.02	.5
SearchQA	40	4	40	.02	.01	.5

Appendix

Table 7: Evolution hyperparameters used in our experiments: initialization examples

n_{0}

, epochs

e

, batch size

b

, regression base tolerance

\epsilon

, mean-gain threshold

\tau

, and non-decrease fraction

q_{0}

Domain	Train	Selection	Test
WikiHow	157	53	52
ToolAlpaca	56	19	18
WebShop	80	27	26
SpreadsheetBench	80	40	280
SearchQA	400	200	1400

Appendix

Table 8: Dataset split sizes and evaluation protocol.

LLM Agent Skill Learning

Large language model agent skill learning studies how agents acquire, represent, reuse, and refine procedures for multi-step tasks.

See all 402 papers

GraphSkillEvo: Evolutionary Optimization of Graph-Structured Agent Skills
Sep 18, 2026Rui Sun, Zhi Zheng, Zhenkun Wang +1LLM Agent Skill Learning Agent Skill Learning
City University of Hong Kong · National University of Singapore · Southern University of Science and Technology
SkillSpec: Consensus-Gated Agent Skill Evolution via Representation Specialization
Sep 30, 2026Huancheng Chen, Xiaodi Sun, Zhaoqiong Huang +3LLM Agent Self-Improvement LLM Agent Skill Learning
Microsoft AI
CoEvoSkills: Self-Evolving Agent Skills via Co-Evolutionary Verification
Apr 2, 2026Hanrong Zhang, Shicheng Fan, Henry Peng Zou +11LLM Agent Skill Learning Self-Evolving Agents
Steve · University of Illinois Chicago · MBZUAI +4

Sep 18, 2026J/K move · Enter open · S save

GraphSkillEvo: Evolutionary Optimization of Graph-Structured Agent Skills

Rui Sun, Zhi Zheng, Zhenkun Wang, Zhichao Lu

City University of Hong Kong · National University of Singapore · Southern University of Science and Technology

LLM Agent Skill Learning Agent Skill Learning Evolutionary Optimization

Open paper AskPDF arXiv

Skills can improve the performance of Large Language Model (LLM) agents by providing task-specific procedural guidance, while skill optimization further improves their effectiveness through iterative refinement. However, existing skill optimization methods typically represent skills as unstructured natural-language instructions, creating two key challenges: 1) Unstructured skills often lack explicit workflow-level guidance and contain substantial redundancy, making them difficult for LLMs to execute; 2) the vast search space of unconstrained natural-language skills makes skill optimization ineffective. To address these challenges, we propose representing skills as graph-structured natural-language artifacts. In graph-structured skills, each node represents an execution step together with its operational guidance, while directed edges encode context-dependent transitions between steps. Compared to unstructured skills, graph-structured skills can provide clear workflow-level guidance. Moreover, the proposed graph-structured skill can also facilitate skill optimization. Building on this structured representation, we introduce GraphSkillEvo, a population-based evolutionary optimization framework with mutation and crossover operators for graph-structured skills. By maintaining multiple candidate skills and combining effective components, GraphSkillEvo enables broader and more comprehensive exploration of the structured skill space than purely LLM-based iterative self-refinement. Extensive experiments across five agent benchmarks demonstrate that GraphSkillEvo consistently outperforms the strong skill optimization baseline SkillOpt, improving average accuracy by 4.01% on GPT-5.4-nano and 1.76% on GPT-5.4. Our code is available at https://github.com/ruisun7/GraphSkillEvo.

Abstract

LLM Agent Skill Learning

Explore similar work

GraphSkillEvo: Evolutionary Optimization of Graph-Structured Agent Skills

SkillSpec: Consensus-Gated Agent Skill Evolution via Representation Specialization

CoEvoSkills: Self-Evolving Agent Skills via Co-Evolutionary Verification