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.
Figures & tables
Figure 1: Existing skill optimization methods (e.g., SkillOpt) maintain unstructured skills and optimize skills purely with LLM self-reflection, resulting in suboptimal performance. GraphSkillEvo solves this with graph-structured skills for giving more workflow-level guidance and providing a reduced search space for comprehensive population-based evolutionary search.
Figure 2: Four evolutionary operators used in GraphSkillEvo. Global-guidance mutation revises the global guidance of a parent skill based on its execution trajectories, while graph-structure mutation updates its nodes and edges by refining node instructions, adding or removing nodes, and adjusting execution paths. Global-guidance crossover recombines useful global guidance from two parent skills while preserving one parent’s graph structure, and graph-structure crossover recombines nodes and edges from two parent skills while preserving one parent’s global guidance.
Model
Skill source
SearchQA
Spreadsheet
DocVQA
LiveMath
ALFWorld
Average
No harness
GPT-5.4
No Skill
77.50
39.16
79.05
33.60
73.13
60.49
Human skill
77.71 +0.21
37.85 -1.31
84.04 +4.99
31.72 -1.88
81.84 +8.71
62.63 +2.14
LLM skill
78.19 +0.69
35.59 -3.57
88.23 +9.18
35.21 +1.61
75.86 +2.73
62.62 +2.13
SkillOpt
82.21 +4.71
64.87 +25.71
89.30 +10.25
47.58 +13.98
86.56 +13.43
74.10 +13.61
GraphSkillEvo
83.80 +6.30
69.40 +30.24
90.37 +11.32
48.65 +15.05
87.06 +13.93
75.86 +15.37
Table 1: Main results across five benchmarks, two LLMs, and two agent harnesses. Each entry reports the success rate on the test set. Higher values indicate better performance. Bold numbers mark the best-reported result among all skill sources for the same model and benchmark.
Figure 3: Optimization curve comparison between SkillOpt and GraphSkillEvo.
Model
Method
SearchQA
Spreadsheet
DocVQA
LiveMath
ALFWorld
Total
GPT-5.4
SkillOpt
38.11 M
11.16 M
3.69 M
2.86 M
25.26 M
81.08 M
GraphSkillEvo
12.54 M
8.82 M
4.56 M
3.50 M
32.53 M
61.94 M
GPT-5.4-nano
SkillOpt
44.68 M
25.22 M
3.67 M
1.78 M
28.18 M
103.54 M
GraphSkillEvo
12.69 M
9.16 M
3.44 M
2.90 M
47.75 M
75.94 M
Table 2: Token consumption of SkillOpt and GraphSkillEvo across different models and benchmarks. All values are reported in millions (M).
Skill
SearchQA
Spreadsheet
DocVQA
LiveMath
ALFWorld
Graph-structured
72.93
60.71
80.92
28.76
61.19
Unstructured
68.41 -4.52
58.21 -2.50
76.73 -4.19
27.41 -1.35
60.44 -0.75
Table 3: Effect of the graph-structured skill representation across five benchmarks. Each entry reports the test-set success rate, expressed as a percentage. The unstructured counterpart retains global guidance and node-level instructions without explicit workflow organization.
Skill
SearchQA
Spreadsheet
DocVQA
Average
GraphSkillEvo
72.93
60.71
80.92
71.52
w/o graph structure
68.83 -4.10
50.59 -10.12
72.81 -8.11
64.08 -7.44
w/o mutation
57.19 -15.74
35.11 -25.60
71.20 -9.72
54.50 -17.02
w/o crossover
71.80 -1.13
53.56 -7.15
74.41 -6.51
66.59 -4.93
Table 4: Ablation study of the graph structure and evolutionary operators.
Benchmark
Method
Baseline
Direct
Transferred
SearchQA
SkillOpt
77.50
82.21 +4.71
83.92 +6.42
GraphSkillEvo
77.50
83.80 +6.30
84.07 +6.57
Spreadsheet
SkillOpt
39.16
64.87 +25.71
53.21 +14.05
GraphSkillEvo
39.16
69.40 +30.24
71.78 +32.62
DocVQA
SkillOpt
79.05
89.30 +10.25
89.30 +10.25
GraphSkillEvo
79.05
90.37 +11.32
89.83 +10.78
Table 5: Cross-model transferability of optimized skills. Baseline denotes execution on GPT-5.4 without a skill. Direct denotes using a skill optimized with GPT-5.4 and then applied on GPT-5.4, and Transferred denotes using a skill optimized with GPT-5.4-nano and then applied on GPT-5.4.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Benchmark
Train
Validation
Test
SearchQA
400
200
1400
SpreadsheetBench
80
40
280
DocVQA
107
53
374
LiveMath
35
18
124
ALFWorld
39
18
134
Appendix
Table 6: Sizes of the training, validation, and test sets used in the experiments. The training set is used only for collecting rollout trajectories and failure feedback during optimization. The validation set is used for skill selection during optimization, while the test set is used only for final reporting.
Benchmark
Method
Run1
Run2
Run3
Run4
Run5
Avg
Std
p-value
SearchQA
SkillOpt
67.85
70.21
69.92
70.64
68.21
69.37
1.25
GraphSkillEvo
74.57
69.35
76.78
73.07
68.14
72.38
3.59
0.068734203
Spreadsheet
SkillOpt
46.78
45.35
42.85
50.35
54.64
47.99
4.60
GraphSkillEvo
59.64
59.28
63.57
59.64
46.07
57.64
6.70
0.016219296
ALFWorld
SkillOpt
41.79
47.76
57.46
54.47
58.95
52.09
7.18
GraphSkillEvo
67.16
60.44
58.20
61.19
53.73
60.14
4.88
0.038218293
Appendix
Table 7: The significance test between SkillOpt and GraphSkillEvo using GPT-5.4-nano without an agent harness. Avg and Std denote the mean and standard deviation, respectively. The reported p-values are computed using one-sided Welch’s t-tests.
Figure 4: A case study of a graph-structured skill on ALFWorld. The figure presents a graph excerpt from the graph-structured skill for ALFWorld together with three representative execution trajectories. Different colors distinguish the three task types and indicate their corresponding workflow guidance and execution trajectories. The examples illustrate how graph-structured skills provide clear and explicit workflow guidance across different situations within the ALFWorld task.
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.
Kounianhua Du, Jianxing Liu, Ruoshui Shan +4
Shanghai Jiao Tong University Shanghai, China · Purdue · Tencent
Agent skills provide a lightweight way to adapt LLM agents to specialized domains by storing reusable procedural knowledge in structured files. However, whether downloaded from third parties or self-generated, these skills are often unreliable, incomplete, or outdated. Existing skill-evolution methods often address these deficiencies through heuristic reflections without an explicit optimization formulation. In this paper, we propose SkillGrad, a gradient-descent-inspired framework for optimizing agent skills. SkillGrad treats the skill package as a structured parameter to optimize in a gradient descent fashion: task executions provide trajectory-level loss evidence, automatic diagnoses then provide text-based gradients that indicate the correction directions. To stabilize optimization across iterations, a momentum agent accumulates recurring diagnostic patterns into a persistent memory overlay. Finally, an LLM-based patcher executes the parameter update by applying layer-aware edits to the skill package. Evaluated on SpreadsheetBench Verified and WikiTableQuestions, SkillGrad consistently outperforms training-based skill evolution baselines across two backbone LLMs, improving over the strongest training-based baseline by 6.7 percentage points on average. Ablations further show that momentum and contrastive diagnosis both contribute to the final skill quality.
Hanyu Wang, Yifan Lan, Bochuan Cao +2
College of Information Sciences and Technology The Pennsylvania State University University Park, PA, USA
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.
Kaiwei Liu, Jiqian Dong, Liran Dong +7
The Chinese University of Hong Kong · Noah’s Ark Lab, Huawei Technologies