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.