GraphSkillEvo: Evolutionary Optimization of Graph-Structured Agent Skills
Rui Sun, Zhi Zheng, Zhenkun Wang, Zhichao Lu
cs.LG
2026-09-18
GraphSkillEvo evolves graph-structured agent skills with mutation and crossover. On GPT-5.4-nano it beats SkillOpt by 4.01 points; SpreadsheetBench rises 50.11 to 60.71.
A skill is a reusable natural-language procedure for an LLM agent, portable across model swaps without retraining weights. Optimizers such as SkillOpt treat the skill as an unstructured manual and patch it from a single trajectory. Two problems follow. Weaker models get lost in long checklists and cannot tell which bullet applies now. Unconstrained text is a huge search space: the same workflow has countless phrasings, and the optimizer spends budget rewriting prose.
This paper draws the skill as a flowchart, then evolves a population of those graphs, crossing useful nodes and edges across candidates.
A graph-structured skill is global guidance hs plus a directed graph gs. Nodes are execution steps with their own rules (parse the goal, retrieve evidence, act, verify). Edges come from workflows, each with an applicability condition cm and a node sequence pm. Nodes can be shared.
GraphSkillEvo uses population size N=4 and T=5 generations. Each generation samples 15 training instances and keeps up to 5 failed trajectories per individual. Four operators rotate:
Parents are sampled with probability proportional to 1/(rank+N). New individuals are scored on the full validation set; the top N of parents plus children survive. Only the skill artifact changes; the LLM and harness stay fixed. The same LLM executes tasks and proposes new skills.
Baselines are no skill, a human skill, a one-shot LLM skill, and SkillOpt. Benchmarks are SearchQA, SpreadsheetBench, DocVQA, LiveMathematicianBench, and ALFWorld. Each setting is averaged over three optimization runs. ALFWorld is blank under the Codex harness because the standard adapter cannot hold a persistent environment.
Test success rates, no harness:
| Model | Source | SearchQA | Spreadsheet | DocVQA | LiveMath | ALFWorld | Average |
| GPT-5.4 | No skill | 77.50 | 39.16 | 79.05 | 33.60 | 73.13 | 60.49 |
| GPT-5.4 | SkillOpt | 82.21 | 64.87 | 89.30 | 47.58 | 86.56 | 74.10 |
| GPT-5.4 | GraphSkillEvo | 83.80 | 69.40 | 90.37 | 48.65 | 87.06 | 75.86 |
| GPT-5.4-nano | No skill | 58.12 | 35.12 | 36.72 | 23.93 | 41.29 | 39.04 |
| GPT-5.4-nano | SkillOpt | 69.52 | 50.11 | 77.80 | 29.56 | 57.46 | 56.89 |
| GPT-5.4-nano | GraphSkillEvo | 72.93 | 60.71 | 80.92 | 28.76 | 61.19 | 60.90 |
Versus SkillOpt, average gains are +1.76 (GPT-5.4, no harness), +4.01 (nano), and +1.33 (GPT-5.4 with Codex). Best in 13 of 14 model–harness–benchmark cells. The one loss is nano on LiveMath, 0.80 behind SkillOpt. Human and one-shot LLM skills often fall below no skill on Spreadsheet.
Stripping workflows from an optimized graph, leaving global guidance and node text, drops nano by 4.52 / 2.50 / 4.19 / 1.35 / 0.75 on the five benchmarks. Operator ablations on nano over SearchQA, Spreadsheet, and DocVQA take the 71.52 average to 64.08 without graph structure, 66.59 without crossover, and 54.50 without mutation. Mutation carries the execution feedback; removing it collapses the run.
SkillOpt spends 1.31× the tokens of GraphSkillEvo on GPT-5.4 (81.08M vs 61.94M) and 1.36× on nano (103.54M vs 75.94M). A graph skill evolved on nano and served to GPT-5.4 scores 71.78 on Spreadsheet, above the 69.40 skill evolved directly on GPT-5.4; the same transfer for SkillOpt is only 53.21.
Skill optimization is often bottlenecked by representation, not by how many times the model reflects. Smaller models benefit more from explicit workflows, and spreadsheet tasks that must hit the right cells show the widest gap. Crossover lets a population go further than single-skill self-patching, with fewer tokens, because the graph cuts redundant phrasings.
Cross-model transfer means a skill can be searched on a cheap model and served on a strong one. This is an incremental change, not a new agent architecture: the backbone and tools stay, the shape of the manual and the search over it change.
N=4 and T=5 is a shallow search; larger populations are not swept. Fitness is validation success, so a small or test-like val split can overfit. Nano loses on LiveMath, where graph structure helps multiple-choice reasoning less. The Codex path has no ALFWorld. The recipe assumes an executable scorer and a train/val/test split, which open-world tasks do not give for free. Combining this with parametric RL is listed as future work.