GraphSkillEvo: Evolutionary Optimization of Graph-Structured Agent Skills

AI summary

Overview

• Research area: Machine learning / large language model (LLM) agents, specifically automatic optimization of prompt-level "skills" — reusable natural-language procedural guidance given to an agent at execution time.
• Technical level: Intermediate. The paper assumes familiarity with LLM agents, prompt-level skills, and evolutionary computation concepts (populations, mutation, crossover), but the core idea is explained through an accessible flow-diagram analogy.
• Scope: The paper proposes representing agent skills as graph-structured natural-language artifacts and optimizing them with a population-based evolutionary framework called GraphSkillEvo, evaluated across five agent benchmarks, two LLMs, and two execution harnesses.

What This Paper Is About

Existing skill-optimization methods represent a skill as unstructured natural-language instructions, which produces lengthy, redundant text that gives only coarse workflow-level guidance and leaves the optimizer searching a large space of textual variants that do not correspond to meaningful procedural changes. This paper instead formulates each skill as a graph: nodes are execution steps with their own instructions, rules, and constraints, and directed edges encode context-dependent transitions, so different task conditions induce different execution paths. Building on that representation, the authors introduce GraphSkillEvo, a population-based evolutionary framework with mutation and crossover operators that search this more compact, structured space for higher-quality skills.

Key Contributions

1. Graph-structured skill formulation. Agent skills are formulated as graph-structured natural-language artifacts consisting of global guidance h_s and a directed graph g_s = (V_s, E_s), where nodes are reusable execution steps and edges are defined through M workflows {(c_m, p_m)}, each pairing an applicability condition with an ordered execution path.
2. A population-based evolutionary framework. GraphSkillEvo maintains a population of N candidate skills and evolves them with four structure-aware operators: global-guidance mutation, graph-structure mutation, global-guidance crossover, and graph-structure crossover — selected in a round-robin schedule and followed by validation-based population selection.
3. Broad empirical validation. Experiments across five agent benchmarks, two LLMs, and two agent harnesses show GraphSkillEvo outperforming the strong skill-optimization baseline SkillOpt, with average accuracy gains of 4.01% on GPT-5.4-nano and 1.76% on GPT-5.4.
4. Evidence that graph structure and both operator classes matter. Ablations and representation-swap experiments isolate the contributions of the graph representation, mutation, and crossover, and a transfer experiment tests whether optimized skills remain useful on a different LLM.

Main Findings

• Best result in 13 of 14 settings. Across the 14 model–harness–benchmark settings in Table 1, GraphSkillEvo achieves the best reported result in 13. All reported results are averages over three repeated skill optimization runs.
• Gains over no-skill execution. GraphSkillEvo improves the average success rate by 15.37% in the GPT-5.4 no-harness setting, 21.86% in the GPT-5.4-nano no-harness setting, and 10.31% in the GPT-5.4 Codex-harness setting.
• Gains over SkillOpt. Compared with SkillOpt, GraphSkillEvo achieves average gains of 1.76% under GPT-5.4 without a harness, 4.01% under GPT-5.4-nano without a harness, and 1.33% under GPT-5.4 with the Codex harness.
• Smaller models benefit most. Averaged across the five benchmarks, the improvement over SkillOpt is 4.01% on GPT-5.4-nano versus 1.76% on GPT-5.4.
• Procedural benchmarks improve the most. GraphSkillEvo improves over SkillOpt by 10.60% on SpreadsheetBench and 3.73% on ALFWorld, which the authors attribute to the clearer workflow guidance helping tasks that require procedural execution, especially with an external environment.
• One exception. On LiveMath with GPT-5.4-nano, GraphSkillEvo trails SkillOpt by 0.80%.
• Lower token consumption. SkillOpt uses 1.31 times as many tokens as GraphSkillEvo with GPT-5.4 and 1.36 times as many with GPT-5.4-nano. Totals in Table 2: GPT-5.4 SkillOpt 81.08 M versus GraphSkillEvo 61.94 M; GPT-5.4-nano SkillOpt 103.54 M versus GraphSkillEvo 75.94 M.
• Explicit workflow organization helps at execution time (RQ1). Replacing graph-structured skills with unstructured counterparts that retain global guidance and node-level instructions reduces success rates by 4.52, 2.50, 4.19, 1.35, and 0.75 percentage points on SearchQA, Spreadsheet, DocVQA, LiveMath, and ALFWorld respectively.
• Graph structure helps optimization, not just execution (RQ2). In the ablation, removing graph structure lowers the three-benchmark average from 71.52 to 64.08; removing crossover lowers it to 66.59; removing mutation produces the largest drop, to 54.50.
• Crossover supports broader exploration. Removing crossover drops average performance to 66.59 — the variant can be viewed as multiple parallel SkillOpt-style self-refinement trajectories, suggesting crossover combines effective components discovered along different search trajectories.
• Mutation provides trajectory-driven refinement. Removing mutation causes the largest degradation (to 54.50), indicating execution feedback is important for locally refining individual skills, with crossover complementing it through cross-candidate recombination.
• Skills transfer across LLMs (RQ3). Skills optimized with GPT-5.4-nano and deployed on GPT-5.4 outperform the no-skill baseline on all three tested benchmarks. The largest advantage is on SpreadsheetBench, where the transferred GraphSkillEvo skill achieves 71.78, exceeding both its directly optimized counterpart (69.40) and the transferred SkillOpt skill (53.21).
• Different convergence behavior. In the optimization curves for GPT-5.4-nano without a harness, SkillOpt shows early convergence on performance while GraphSkillEvo converges to better performance via continuous updates; each curve is averaged over three experiments.

Methodology in Plain English

The authors change what a "skill" is. Instead of a single blob of instructions, a skill becomes a small flowchart written in natural language. One shared section holds task-wide guidance (description, general principles, templates). Below that is a set of named steps, each carrying exactly the instructions needed for that step — for instance, "Explore Object," "Take Object," "Place Object." Finally, workflows define paths through those steps: each workflow has a "use when" condition and an ordered list of steps, and consecutive steps in a path become the edges of the graph. Because steps are reusable, guidance shared across several workflows is written once rather than repeated.

Optimization then works like a small breeding program rather than a single chain of self-edits:

1. Initialize. Start a population of N skills; beyond the initial skill, an LLM generates diverse alternatives from the task context. Every candidate is scored on the full validation set and that score becomes its fitness.
2. Execute. At each generation, sample a batch of B training instances, attach each candidate skill to the agent, and run. Failures are retained as "reflection information," capped at K failed trajectories per skill.
3. Generate new skills. Pick one of four operators in round-robin order, pick parent skill(s) with probability proportional to 1/(r + N) where r is the skill's fitness rank, and have an LLM produce the child. Mutations receive the parent's failed trajectories; crossovers do not. Global-guidance mutation rewrites shared guidance; graph-structure mutation refines node instructions, adds or deletes nodes, and adjusts workflows; global-guidance crossover swaps shared guidance while keeping one parent's graph; graph-structure crossover swaps nodes and edges while keeping one parent's global guidance.
4. Select. Score all new skills on the full validation set and keep the top N from the current population plus the new candidates. Repeat for T generations and return the highest-fitness skill.

In the experiments, N = 4, T = 5, the batch is 15 training instances, up to 5 failed instances feed reflection, and the four operators rotate round-robin. Both GPT-5.4 and GPT-5.4-nano are run at medium reasoning effort, with the same LLM used for execution and skill generation. Evaluation covers SearchQA, SpreadsheetBench (up to 30 code-generation rounds without a harness, a single round with Codex), DocVQA, LiveMathematicianBench, and ALFWorld (50 interaction steps per episode), under both a no-harness setting and a Codex harness (workspace-write sandbox, interactive approvals disabled). ALFWorld cells are left blank for the Codex harness because ALFWorld requires persistent environment interaction that the standard Codex adapter does not support. All experiments use the same deterministic partitioning with split_seed=42; splits are SearchQA 400/200/1400, SpreadsheetBench 80/40/280, DocVQA 107/53/374, LiveMath 35/18/124, and ALFWorld 39/18/134 (train/validation/test). Metrics are test-set success rates: exact match for SearchQA, DocVQA, and LiveMath; full-workbook correctness across all evaluation cases for SpreadsheetBench; and pass rate within an interaction limit for ALFWorld. A validator script checks each newly generated skill against the required graph schema. Baseline skill sources are no skill, human-written skill, one-shot LLM skill, and SkillOpt.

Why This Matters

Impact on research. The paper reframes skill optimization as a search over structured procedural artifacts rather than over unstructured prose, and shows that population-based evolutionary operators (mutation plus crossover) can outperform purely LLM-driven iterative self-refinement at lower token cost. It also connects skill optimization to existing work on graphs for skill retrieval and composition, while distinguishing itself: prior graph approaches use graphs to retrieve or orchestrate skills from large libraries, whereas this work treats each individual skill as a graph and optimizes within that representation.

Real-world applications.

• Spreadsheet and document automation: SpreadsheetBench is where the largest procedural gain over SkillOpt appears (10.60%), pointing to office-automation agents that manipulate workbooks and business documents.
• Enterprise document question answering: DocVQA and SearchQA gains suggest use in evidence-grounded QA over scanned documents and retrieved text.
• Embodied and environment-interacting agents: ALFWorld tests persistent household-environment interaction, relevant to robotics-adjacent and simulated-assistant settings where follow-the-steps discipline matters.
• Model-agnostic capability preservation: Because skills are external natural-language artifacts, an organization can optimize a skill once and keep using it when the underlying model is replaced — the transfer experiment between GPT-5.4-nano and GPT-5.4 directly tests this.

Industry relevance. Practitioners deploying agents cannot retrain a frontier model, but they can supply and iterate on prompt-level artifacts. The paper offers a concrete recipe for doing so with explicit workflows, structured search, and measured token cost — SkillOpt consumes 1.31 to 1.36 times as many optimization tokens as GraphSkillEvo in these experiments. The stated gains are largest on the weaker model (GPT-5.4-nano), which is the model tier most cost-sensitive deployments would use.

Future Directions

• Combine with parametric optimization. The authors list merging this approach with parametric optimization methods as future work.
• Richer graph composition mechanisms. Extending the framework beyond the current node/edge/workflow edits to richer composition is named as an open direction.
• Merging skills across domains. Developing methods for merging graph-structured skills from diverse domains is listed as future work.
• Address the LiveMath exception. The single setting where GraphSkillEvo trails SkillOpt (LiveMath with GPT-5.4-nano, by 0.80%) is not explained mechanistically, leaving open whether mathematical multiple-choice reasoning needs a different graph design.
• Statistical confidence reporting. The paper states that significance tests and a case study are provided in Appendix C.1 and C.2; those results are not present in the available content, so the robustness of the small margins is not verifiable here.

Target Audience

Researchers and practitioners working on LLM agents, prompt/skill optimization, and automated agent scaffolding. It is most useful to readers who already understand what an agent harness and a prompt-level skill are, and who want either a new representation for procedural guidance or a template for applying evolutionary search to language artifacts. Readers primarily interested in evolutionary computation may find the operator design reusable; readers interested in deployment may find the cross-model transfer results and token comparisons most actionable. Beginners can follow the graph-versus-checklist intuition but may need background on skill-optimization baselines such as SkillOpt to interpret the comparative numbers.

Authors’ 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.