PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphSkillEvo: Evolutionary Optimization of Graph-Structured Agent Skills

Rui Sun, Zhi Zheng, Zhenkun Wang, Zhichao Lu

arXiv:2609.21749v1cs.LG

TL;DR

Existing skill-optimization methods often use unstructured instructions with limited workflow guidance and a large, redundant search space. GraphSkillEvo represents skills as graphs and evolves a population of candidates using mutation and crossover. Averaged across five benchmarks, it outperforms SkillOpt by 4.01% on GPT-5.4-nano and 1.76% on GPT-5.4.

  • Problem

    Existing skill-optimization methods typically use unstructured instructions, leaving workflow guidance limited and the optimization search space large and redundant.

    Source: §1 · p. 2

  • Method

    GraphSkillEvo represents skills as execution-step graphs with context-dependent transitions and uses population-based evolution with structure-aware mutation and crossover to optimize them.

    Source: §1 · p. 2

  • Results

    Averaged across five benchmarks, GraphSkillEvo outperforms SkillOpt by 4.01% on GPT-5.4-nano and 1.76% on GPT-5.4.

    Source: §4.1 · p. 8

  • Takeaways & Limitations

    The paper concludes that graph structure supports skill execution and evolutionary optimization, with improved average performance over SkillOpt across the evaluated benchmarks.

    Source: §6 · p. 10

    Optimization changes only the skill artifact while holding LLM parameters and the execution harness fixed.

    Source: §2.1 · p. 3

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper proposes graph-structured skills to make agent workflows explicit and reduce redundancy, and introduces GraphSkillEvo to evolve them with population-based mutation and crossover.

1 INTRODUCTION

  • Skills provide reusable task-specific procedural guidance, and their portability allows procedures to carry across different LLMs as models are updated or replaced.Skills can encode workflows, domain knowledge, operational rules, and output constraints.Source: §1 · p. 2
  • Unstructured skills make execution difficult by offering coarse workflow guidance and make optimization inefficient through a large, redundant search space.The execution challenge is particularly severe for less capable LLMs that struggle with overlong instructions.Source: §1 · p. 2
  • Graph-structured skills encode execution steps as nodes and context-dependent transitions as directed edges, clarifying workflows and reducing representational redundancy.Each node contains self-contained operational guidance relevant to that step.Source: §1 · p. 2
  • GraphSkillEvo preserves diverse candidate skills and applies trajectory-based mutation and crossover to recombine effective graph components.These operators support broader exploration than purely LLM-based iterative self-refinement.Source: §1 · p. 2
  • GraphSkillEvo consistently outperforms strong skill-optimization baselines across two LLMs, two harnesses, and five benchmark settings.The introduction describes extensive experiments across diverse agent benchmarks.Source: §1 · p. 2

2 PRELIMINARY

The section defines skill optimization as improving an agent’s task performance by refining a natural-language skill, then describes prior optimization methods and the workflow and search-space limitations GraphSkillEvo addresses.

2.1 PROBLEM DEFINITION: SKILL OPTIMIZATION

  • An agent combines an LLM with an execution harness, and a skill is a natural-language artifact supplied during execution to help solve task instances.Skills may be manually written, generated in one shot, or refined through optimization.Source: §2.1 · p. 3
  • Optimization seeks a skill maximizing task performance while keeping the LLM and execution harness fixed, using training trajectories, validation for candidate assessment, and test data only for final evaluation.The dataset is divided into Dtrain, Dval, and Dtest for these respective roles.Source: §2.1 · p. 3

2.2 SKILL OPTIMIZATION METHOD

  • SkillOpt applies trajectory-derived update patches to an initial skill and retains a candidate only when it improves validation performance.It executes the current skill on training instances, uses an agent to analyze the trajectories and propose patches, then repeats the validation-based selection process.Source: §2.2 · p. 3
  • Prior methods include EvoSkill’s failure analysis and Pareto-based selection, Trace2Skill’s parallel merging of trajectory patches, and SkillX’s multi-level skills and iterative library expansion.These methods automatically construct or distill skills from execution trajectories and interaction experience.Source: §2.2 · p. 3
  • GraphSkillEvo structures skills as workflow graphs and evolves a population through mutation and crossover to address redundancy and limited workflow guidance in prior methods.The graph representation makes execution workflow explicit, while the operators support broader exploration than pure LLM-based self-refinement.Source: §2.2 · p. 3

3 METHODOLOGY: GRAPHSKILLEVO

GraphSkillEvo represents skills as graph-structured natural-language artifacts and optimizes them with a population-based evolutionary framework using mutation and crossover. The graph representation provides explicit workflow guidance and a structured search space.

3.1 GRAPH-STRUCTURED SKILLS

  • A graph-structured skill combines global guidance, reusable execution-step nodes, and condition-specific workflows that define ordered paths and transitions between nodes.Different workflows can share nodes while specifying different paths.Source: §3.1 · p. 4
  • Reusable nodes reduce repeated instructions, while explicit stepwise paths help agents follow precise workflows and give GraphSkillEvo a more compact, structured search space.The optimizer searches over execution steps and dependencies rather than many unstructured textual realizations of similar workflows.Source: §3.1 · p. 4

3.2 EVOLUTIONARY OPTIMIZATION OVER GRAPH-STRUCTURED SKILLS

  • Its four operators mutate either global guidance or graph structure, and cross over either guidance or graph components while preserving the other component from one parent.Graph-structure mutation can refine node instructions, add or delete reusable nodes, and adjust workflows.Source: Figure 2 · p. 5, §3.2 · p. 6
  • GraphSkillEvo maintains multiple high-quality skills, uses execution-trajectory feedback for mutation, and uses crossover to transfer beneficial components between skills.The framework is designed to explore the structured skill space more comprehensively than optimizing a single skill at a time.Source: §3.2 · p. 5
  • After generating and evaluating new skills on the validation set, GraphSkillEvo retains the N highest-fitness skills and returns the best skill after T generations.The optimization loop executes current skills on sampled training instances and retains failed trajectories as reflection information for mutation.Source: §3.2 · pp. 5–6

4 EXPERIMENTS

Across five benchmarks, GraphSkillEvo outperforms SkillOpt in most model–harness–benchmark settings, with improvements in average success rate and lower optimization token consumption. Its optimization curve also reaches better validation performance than SkillOpt in the reported GPT-5.4-nano setting.

4 EXPERIMENTS

  • The evaluation spans five benchmarks and reports average test-set success using exact match, workbook-wide correctness, or interaction-limited pass rate, depending on task.The benchmarks cover question answering, spreadsheet manipulation, visual document understanding, mathematical multiple-choice reasoning, and embodied interaction.Source: §4 · p. 6

4.1 MAIN RESULTS

  • GraphSkillEvo achieves the best result in 13 of 14 settings and beats SkillOpt by 1.76%, 4.01%, and 1.33% in GPT-5.4 no-harness, GPT-5.4-nano no-harness, and GPT-5.4 Codex settings, respectively.Results are averaged over three repeated skill-optimization runs.Source: Table 1 · p. 7, §4.1 · pp. 7–8
  • In GPT-5.4-nano without a harness, GraphSkillEvo’s validation score converges to a better performance level than SkillOpt’s as optimization tokens accumulate.SkillOpt converges early, whereas GraphSkillEvo continues to improve; both curves average three experiments.Source: Figure 3 · p. 7, §4.1 · p. 8
  • SkillOpt consumes 1.31 times as many total optimization tokens as GraphSkillEvo with GPT-5.4 and 1.36 times as many with GPT-5.4-nano.GraphSkillEvo therefore combines stronger performance with lower total optimization-token consumption in both model settings.Source: Table 2 · p. 8, §4.1 · p. 8
  • GraphSkillEvo’s gains over SkillOpt are 10.60% on SpreadsheetBench and 3.73% on ALFWorld, but it trails by 0.80% on GPT-5.4-nano LiveMath.The paper suggests graph-structured workflow guidance is especially helpful for procedural tasks, particularly when agents interact with an external environment.Source: §4.1 · p. 8

5 DISCUSSION

The discussion finds that explicit graph workflows strengthen skill execution and optimization, mutation and crossover contribute complementary search capabilities, and GraphSkillEvo skills remain effective when transferred across the evaluated models.

5.1 EFFECT OF GRAPH-STRUCTURED REPRESENTATION ON SKILL EXECUTION

  • Removing graph structure lowered success rates by 4.52 percentage points on SearchQA, 2.50 on Spreadsheet, 4.19 on DocVQA, 1.35 on LiveMath, and 0.75 on ALFWorld.Explicitly organizing global guidance and node instructions into context-specific workflows helps agents apply them more effectively during execution.Source: §5.1 · p. 9

5.2 ADVANTAGE OF GRAPH REPRESENTATION IN SKILL OPTIMIZATION

  • GraphSkillEvo’s average performance fell from 71.52 to 64.08 without graph structure, showing that population-based evolution alone was insufficient.The graph representation organizes procedural components and dependencies into a more structured search space.Source: §5.2 · p. 9, Table 4 · p. 9
  • Without crossover, performance fell to 66.59; removing mutation yielded 54.50, the largest drop, as mutation uses execution feedback for local refinement and crossover recombines components across candidates.The ablation results average three repeated experiments.Source: §5.2 · pp. 9–10, Table 4 · p. 9

5.3 TRANSFERRING SKILLS ACROSS LLMS

  • 71.78 on SpreadsheetBench for transferred GraphSkillEvo skills exceeded its directly optimized counterpart (69.40) and transferred SkillOpt (53.21); transferred skills beat no-skill baselines on all three benchmarks.Skills optimized with GPT-5.4-nano were deployed on GPT-5.4.Source: Table 5 · p. 9, §5.3 · p. 10

6 CONCLUSION … A.2 GRAPH FOR AGENT SKILL

GraphSkillEvo represents skills as graphs of procedural guidance and optimizes them with evolutionary operators; experiments and analyses support benefits in performance, token use, execution, and skill transfer. The paper distinguishes this approach from prior work on skill optimization and graph-based retrieval or composition, and outlines directions for extending the framework.

6 CONCLUSION

  • Across five benchmarks, two LLMs, and two execution settings, GraphSkillEvo improves average performance over SkillOpt and uses fewer aggregate optimization tokens.Further analyses support graph structure for skill execution and evolutionary optimization, and effective transfer from GPT-5.4-nano to GPT-5.4.Source: §6 · p. 10
  • GraphSkillEvo formulates skills as graph-structured natural-language artifacts and uses population-based evolutionary computation with structure-aware mutation and crossover.Nodes make workflow guidance explicit and organize reusable execution steps into a structured search space.Source: §6 · p. 10
  • Future work includes combining GraphSkillEvo with parametric optimization, richer graph composition, and methods for merging graph-structured skills across domains.Source: §6 · p. 10

A.1 AGENT SKILL OPTIMIZATION

  • Prior skill-optimization work uses execution-trajectory feedback, deep-learning-style controls, reinforcement-learning coevolution, or personalized and cross-user skill construction.The passage cites these approaches as examples: EvoSkill, Trace2Skill, SkillX, AutoRefine, SkillOpt, EvolveR, SAGE, SKILLRL, AutoSkill, and SkillClaw.Source: §A.1 · p. 14
  • Existing skill-optimization methods generally use unstructured natural-language instructions, which can lack workflow guidance, introduce redundancy, and leave a large search space.The paper contrasts this with graph-structured skills optimized through population-based evolution, which provides explicit guidance, reduces redundancy, and makes optimization more tractable.Source: §A.1 · p. 14

A.2 GRAPH FOR AGENT SKILL

  • Prior graph-based skill research mainly targets retrieval or composition, whereas this work represents each skill as a graph and optimizes it with structure-aware mutation and crossover.Examples include Graph-of-Skills and SkillDAG for retrieval, GraSP for composition, SSL representations for retrieval and risk assessment, and HiSkill for retrieving task-relevant skill subsets.Source: §A.2 · p. 14

B METHODOLOGICAL DETAILS · B.1 BENCHMARKS

B.1 describes five benchmarks spanning text and image question answering, spreadsheet coding, mathematical multiple choice, and interactive household tasks. SpreadsheetBench uses iterative code execution without a harness but a single generation round with the Codex harness.

B.1 BENCHMARKS

  • SearchQA (Dunn et al., 2017) tests answering from textual evidence, while DocVQA (Mathew et al., 2021) tests answering questions using document images.Source: §B.1 · p. 15
  • SpreadsheetBench (Ma et al., 2024) tests programmatic manipulation of real .xlsx workbooks using Python with the standard library, openpyxl, and pandas.Generated code runs in an execution environment that returns output or execution-level failure diagnostics for possible revision.Source: §B.1 · p. 15
  • Without a harness, SpreadsheetBench permits up to 30 code-generation rounds; with the Codex harness, each task uses one round.Source: §B.1 · p. 15
  • LiveMathematicianBench (He et al., 2026) evaluates mathematical multiple-choice problems by having the agent select a provided answer option.Source: §B.1 · p. 15
  • ALFWorld (Shridhar et al., 2020) tests interaction in a persistent text-based household environment, with each episode limited to 50 steps.At each step, the agent observes the current state, chooses an admissible action, and receives the next observation.Source: §B.1 · p. 15

B.2 DATASET SPLITS · B.3 GRAPH STRUCTURE VALIDATION · B.4 COMPLETE OPTIMIZATION ALGORITHM

The appendices specify GraphSkillEvo’s data partitioning, structural validator, and complete evolutionary loop. The loop generates validated candidates, uses validation fitness to guide selection, and returns the best skill.

B.2 DATASET SPLITS

  • Benchmarks use deterministic, disjoint train, validation, and test partitions with split seed 42; training supports optimization, validation guides selection, and test is reserved for final evaluation.All baselines use the same partitions, and Table 6 reports their set sizes.Source: §B.2 · p. 15, Table 6 · p. 15

B.3 GRAPH STRUCTURE VALIDATION

  • A script validator checks schema compliance and consistency between declared nodes and workflows; invalid skills are discarded and regenerated.It verifies that referenced workflow nodes are declared and every declared node appears in at least one workflow.Source: §B.3 · p. 16

B.4 COMPLETE OPTIMIZATION ALGORITHM

  • The algorithm initializes a population with the supplied graph skill and generated candidates, then evaluates candidates using the training set, validation set, population size, generations, sample size, and failure budget.Generated initial candidates are regenerated until they pass structural validation.Source: §B.4 · p. 16
  • Each generation samples B training instances, runs parent skills, collects up to K failed trajectories, and uses the reflections during mutation.The algorithm also ranks parents by validation fitness and assigns sampling weights proportional to 1/(rank + N).Source: §B.4 · p. 16
  • Four operators—global mutation, graph mutation, global crossover, and graph crossover—are applied in round-robin order to generate children from rank-weighted parents.Mutation prompts also receive the selected parent’s reflection information.Source: §B.4 · p. 16
  • After full validation-set scoring, the algorithm retains the top N skills from parents and children, then returns the population member with the highest validation fitness..Source: §B.4 · p. 16

C ADDITIONAL EXPERIMENTS … D BASELINES & LICENSES

The additional experiments assess whether GraphSkillEvo significantly outperforms SkillOpt and illustrate graph-structured skill execution with an ALFWorld case study. Reported significance is strongest on procedural benchmarks, while question-answering gains are more modest.

C.1 SIGNIFICANCE TEST

  • The robustness experiment compares GraphSkillEvo with SkillOpt using five individual skill-optimization runs per benchmark and one-sided Welch’s t-tests.For each benchmark, the reported results include the mean, standard deviation, and p-value.Source: §C.1 · p. 17, Table 7 · p. 17
  • Spreadsheet and ALFWorld show statistically significant GraphSkillEvo gains over SkillOpt, with one-sided Welch’s t-test p-values below 0.05.The significance test uses GPT-5.4-nano without an agent harness; Table 7 reports results for five individual optimization runs and their mean, standard deviation, and p-value.Source: Table 7 · p. 17, §C.1 · p. 17
  • SearchQA and DocVQA show more modest GraphSkillEvo gains over SkillOpt, with p-values in the 0.05 to 0.10 range.The p-values come from one-sided Welch’s t-tests.Source: Table 7 · p. 17, §C.1 · p. 17

C.2 CASE STUDY

  • The ALFWorld case study presents a graph-structured skill excerpt alongside three representative agent execution trajectories.Figure 4 is provided to illustrate how graph-structured skills guide agent execution.Source: §C.2 · p. 17

D.1 BASELINE IMPLEMENTATION DETAILS

This section specifies four baselines: no-skill, human-written skill, one-shot LLM-generated skill, and SkillOpt. The first three use fixed skill conditions, while SkillOpt applies iterative optimization with validation gating.

D.1 BASELINE IMPLEMENTATION DETAILS

  • The no-skill baseline evaluates the agent with an empty skill artifact and no procedural guidance beyond the benchmark’s native task prompt.Source: §D.1 · p. 17
  • The human-skill baseline uses a manually written, benchmark-specific skill that remains fixed during evaluation and is not optimized.Source: §D.1 · p. 17
  • The LLM-skill baseline uses a fixed one-shot skill generated by GPT-5.4 from the benchmark task description, without evolutionary optimization or validation feedback.Source: §D.1 · p. 17
  • SkillOpt uses rollout reflection, textual edit selection, skill updating, and validation gating across four optimization epochs.Each rollout batch contains 40 examples; reflection and merge minibatches are 8, edit budgets are 4 and 2, and the edit budget follows a cosine schedule. Slow update uses 20 samples with validation-gated acceptance, and meta-skill memory is enabled.Source: §D.1 · p. 17

D.2 LICENSES · E PROMPTS AND OPTIMIZED SKILL EXAMPLES

This section presents prompts for initializing and evolving graph-structured skills, with ALFWorld and spreadsheet examples illustrating structured workflows and an unstructured checklist counterpart. It also provides dataset and method-code links and licenses.

D.2 LICENSES

  • Figure 4 illustrates graph-structured skill workflow guidance through an ALFWorld graph excerpt and three representative execution trajectories.Different colors distinguish three task types and their corresponding guidance and trajectories.Source: Figure 4 · p. 18
  • Table 8 lists links and licenses for datasets and method code.The text identifies it as the table of links and licenses for baselines.Source: §D.2 · p. 17, Table 8 · p. 18

E PROMPTS AND OPTIMIZED SKILL EXAMPLES

  • The four evolutionary operators mutate or recombine either global guidance or graph structure, and each prompt requires a complete graph-structured skill in response.Global guidance and node lists define skill components; task graphs specify workflows through applicability conditions and ordered node sequences, with consecutive nodes defining edges.Source: §E.1 · p. 19, E PROMPTS AND OPTIMIZED SKILL EXAMPLES · p. 19

E.1 PROMPTS FOR EVOLUTIONARY OPERATORS

  • Reflection-driven mutation revises global guidance or reusable nodes and workflows to address recurring failures while leaving the other skill component unchanged.Graph-structure mutation can refine, add, merge, remove, or reroute nodes and workflow branches while keeping global guidance unchanged.Source: §E.1 · pp. 19–20
  • Crossover recombines useful global guidance or graph components from two parent skills while preserving the other component from one parent.Global-guidance crossover combines useful principles while retaining Parent A’s node lists and task graphs; graph-structure crossover recombines nodes and workflows while retaining one parent’s global guidance.Source: §E.1 · pp. 21–22
  • Crossover prompts recombine or replace parent nodes and graph paths while removing redundancy and enforcing an executable, consistent skill document.They preserve Parent A’s Global Guidance and return a complete skill as JSON with brief change notes.Source: §E.1 · p. 22

E.2 PROMPT FOR SKILL INITIALIZATION

  • Initialization prompts derive task types from benchmark context, then build self-contained skills from reusable nodes connected into ordered, executable task workflows.They distinguish portable global principles from step-by-step procedures, and call for nodes that are specific yet reusable across benchmark tasks.Source: §E.2 · pp. 23–24

E.3 EXAMPLE OF OPTIMIZED GRAPH-STRUCTURED SKILLS

  • The example prioritizes correct final workbook cell contents, favors static values when formula evaluation is needed, and verifies written results and fill extent before saving.It also directs the agent to preserve unrelated workbook content and reopen the output to confirm expected results.Source: §E.3 · pp. 24–25
  • The spreadsheet skill example classifies the request, inspects workbook structure, identifies exact target cells, and resolves headers, keys, and destination areas.It centers the workflow on the actual workbook rather than previews and records target coordinates for later verification.Source: §E.3 · p. 25
  • The optimized skill favors Python-computed static values when formulas need not remain, and directs the agent to reopen the workbook, verify results, and recover from failures.When formulas must remain, the example calls for correct references and equivalent Python fallback logic; verification failures trigger recomputation, overwrite, resaving, and rechecking.Source: §E.3 · pp. 26–27
  • The optimized skill uses a common sequence of workbook inspection, target resolution, output, formatting, saving, and verification, with task-specific paths for formulas, lookups, reports, and row expansion.The example lists distinct workflows for in-place fills, formulas that must remain, cross-sheet matches, summary blocks, and expanded records.Source: §E.3 · pp. 27–28

E.4 EXAMPLE OF AN UNSTRUCTURED COUNTERPART

  • The unstructured counterpart prioritizes correct final workbook results and retains global guidance and node-level instructions while removing explicit workflow organization.Its guidance also emphasizes inspecting the actual workbook and verifying the saved output, rather than relying only on previews or unevaluated formulas.Source: §E.4 · pp. 28–29
  • Prefer static Python-computed values, using Excel formulas only when explicitly required and after understanding equivalent fallback logic; simple value transfer may suffice for direct-reference tasks.Formula patterns should use correct relative or absolute references and requested blank or error handling.Source: §E.4 · p. 29
  • Build a complete executable openpyxl and pandas script with stages for loading, helpers, source discovery, computation, formatting, saving, and verification.Translate the spreadsheet logic into Python-ready rules before writing outputs, and ensure the returned script is not truncated.Source: §E.4 · p. 29
  • Use reusable helpers for text normalization, dates, aggregation, and defaults to compute requested lookups, filters, totals, mappings, and outputs with exact blank handling.Write concrete results throughout the resolved target extent, including benchmark answer cells for single-cell tasks.Source: §E.4 · p. 29
  • For multi-value inputs, emit one destination row per required result, preserve ordering where possible, and clear obsolete generated content while protecting unrelated cells.Create report blocks, headers, or grouped outputs only when called for, and retain existing headers and unrelated regions.Source: §E.4 · p. 30
  • Apply only requested formatting, save to OUTPUT_PATH, then reopen the workbook to inspect target cells and fill extent; if verification fails, overwrite, resave, and recheck.Confirm expected concrete values are present and required cells are not None or unevaluated formulas when static results are needed.Source: §E.4 · p. 30
Loading 2609.21749v1…