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
Published September 18, 2026 · on the feed September 21, 2026 · ▲ 18 · arXiv 2609.21749
The abstract
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.
The Brief
2:45A short podcast summary of the paper. Written and voiced by AI.
Transcript
GraphSkillEvo. Evolutionary Optimization of Graph-Structured Agent Skills. By Rui Sun and three others, from City University of Hong Kong, the National University of Singapore, and one other institution. Published on the eighteenth of September. Its code repository is worked out: about sixty-five source files, with a readme.
Skills can improve large language model agents by giving them task-specific procedural guidance, and skill optimization improves them further through iterative refinement. Existing optimization methods, though, usually represent skills as unstructured natural-language instructions, and that creates two challenges. Unstructured skills often lack explicit guidance at the level of the workflow, and they contain substantial redundancy, which makes them hard for a model to execute. And the search space of unconstrained natural-language skills is vast, which makes optimizing them ineffective. Put together, the two problems compound. A skill that is hard to follow is also hard to improve, because an optimizer searching free text has little to hold on to.
The proposal is to represent a skill as a graph-structured natural-language artifact. Each node is an execution step together with its operational guidance. Directed edges encode transitions between steps that depend on context. The skill is still written in natural language, but now it has a shape. Compared with unstructured text, such a skill gives clear workflow- level guidance, answering the first challenge. And the structure also makes the skill easier to optimize, answering the second.
GraphSkillEvo is built on that representation. It is a population-based evolutionary optimization framework, with mutation and crossover operators designed for graph-structured skills. It maintains multiple candidate skills at once and combines their effective components. That lets it explore the structured skill space more broadly and more comprehensively than iterative self-refinement driven purely by a language model, where a single skill is revised again and again. Mutation changes part of a candidate skill. Crossover combines parts from different candidates. Because the skills are graphs, those parts are steps and transitions, units that can be swapped meaningfully.
Across five agent benchmarks, GraphSkillEvo consistently outperforms the strong skill-optimization baseline SkillOpt. Average accuracy improves by four point zero one percent on GPT-5.4-nano and by one point seven six percent on GPT-5.4. The gains hold on a smaller model and a larger one, and they are measured against a baseline built for the same job, optimizing skills.
Structure does double duty in this work. It makes a skill easier for an agent to follow, and it gives an optimizer discrete pieces it can recombine. Evolution then searches more widely than a single model refining a single skill, by keeping several candidates alive and combining what works in each.
Paper Quest · 7 chapters · about 41 min
Play this paper
Learn it by doing: make the calls the authors made, guess the result before you see it, and defend it in a viva graded on your own words. Chapter 1 is right here.
Chapter 1 🧩 · The problem
A skill that is hard to follow is also hard to improve. Start there.
You give a language model agent a written skill: a long checklist of tips for a task. An optimizer keeps rewriting it from the agent's failures, and it grows longer and more repetitive.
The road ahead
- 1 · The problem ~7 min Skills written as long free-text checklists are hard for small models to follow and hard for an optimizer to improve.
- 2 · What came before ~3 min
- 3 · The key idea ~9 min Write a skill as a graph of steps joined by conditional transitions, then evolve a population of such skills by mutation and crossover.
- 4 · Choose your own research ~3 min
- 5 · Build the method ~8 min Write each skill as a graph, keep a population of candidates, and improve them with mutation and crossover.
- 6 · The experiment ~6 min You’ll guess: Over SkillOpt, did GraphSkillEvo's average accuracy gain more on the smaller GPT-5.4-nano or on GPT-5.4?
- 7 · The viva ~5 min Three questions from the examiners, answered in your own words. Win it for the paper’s trophy.
Free, with Google or an email address. Your stars and progress are kept.