Source-linked AI summary
SE-GoS: Self-Evolving Graph-of-Skills for Skill Library at Scale
Dawei Fu, Cheng Jiang, Sitian Qian, Huainan Wang, Zhongkai Hao
TL;DR
Large skill libraries make retrieval difficult because static graphs and semantic matching can miss useful prerequisite structure. SE-GoS evolves a GoS retrieval graph from execution traces through topology, weight, and description updates while preserving the retrieval procedure. Across the evaluated settings, it improves reward and reduces tokens, with one representative evolution round increasing reward from 52.4% to 59.4% and transferring to held-out tasks.
Problem
As skill libraries scale, existing retrieval graphs do not systematically use execution traces to improve retrieval structure or establish transfer to unseen tasks.
Method
SE-GoS applies training-free topology, edge-weight, and retrieval-facing description updates to an existing GoS graph while leaving skill content and retrieval code unchanged.
Results
Across three LLMs on SkillsBench, SE-GoS consistently improves reward while reducing input tokens relative to full loading; one round raises reward from 52.4% to 59.4%.
Takeaways & Limitations
One evolution round produces transferable retrieval structure: the graph improves on a disjoint held-out split while the retrieval pipeline remains unchanged.
Takeaways & Limitations
The evaluation covers SkillsBench at 1,000 skills, ALFWorld development data, and three model families, without claims about other scales or backbones.
Abstract
from arXiv · showhide
Modern LLM agents increasingly rely on reusable skills, yet as skill libraries scale to thousands of entries, effective retrieval becomes a bottleneck. Graph-of-Skills (GoS) addresses this challenge by exploiting dependency-aware graph structure for scalable skill retrieval, while SkillDAG further demonstrates that skill graphs can accumulate execution-backed structure online. However, these approaches leave open whether historical execution traces can be systematically distilled into a better retrieval graph that generalizes to unseen tasks. We present Self-Evolving Graph-of-Skills (SE-GoS), a training-free framework that evolves an existing GoS graph from execution traces while preserving the original retrieval pipeline. SE-GoS performs three complementary updates: topology evolution that discovers and prunes skill relationships from execution evidence, edge-weight evolution that reinforces retrieval-relevant relationships based on historical effectiveness, and description evolution that optimizes retrieval-facing skill descriptions using execution feedback. Across three LLMs on SkillsBench, SE-GoS consistently improves task reward while reducing input tokens relative to full skill loading, with gains varying across model families. In a representative setting, one evolution round improves reward from 52.4\% to 59.4\% while reducing input tokens by approximately one-third relative to full skill loading, and the resulting graph transfers to a disjoint held-out split with a 5.4-point improvement over the static GoS baseline. These results show that skill graphs can be improved from execution experience without model training, changes to the retrieval algorithm, or modifications to skill content, turning a static retrieval graph into an evolving retrieval infrastructure.
1 Introduction
Large skill libraries make retrieval the bottleneck: full loading overloads context, while vector retrieval misses functionally necessary prerequisites. SE-GoS evolves GoS from execution traces through topology, edge-weight, and description updates without changing the retrieval pipeline.
- Skill retrieval becomes a bottleneck as repositories scale, because full loading is costly and can hide key skills in overloaded contexts.
- Vector retrieval selects semantic matches but can miss lower-level parsers or setup utilities that function as prerequisites.
- GoS uses a typed directed graph and reverse-aware Personalized PageRank to return bounded, dependency-aware execution bundles.
- SE-GoS uses successful co-occurrence, historical effectiveness, and execution feedback to evolve topology, edge weights, and skill descriptions without training or retrieval-code changes.
- The evaluation compares one evolution round with flat, vector, static-graph, and self-evolving baselines, repeated updates, and a held-out split.
2 Related Work
SE-GoS differs from prior skill-graph and experience-accumulation systems by evolving dependency-aware retrieval structure directly from execution traces without training models, using an LLM prior for relations, or modifying skill content.
- Prior systems evolve skill graphs or agent competence, but their distinguishing mechanisms include model-judged relations, reinforcement learning, or changes to what the agent knows and does.
- SE-GoS assigns inter-skill structural judgment to execution evidence rather than an LLM prior over which skills are related.
- Table 1 distinguishes SE-GoS by combining evolving retrieval, training-freeness, LLM-prior-freeness, and skill selection.
- SE-GoS refines retrieval-facing descriptions while selecting among existing skills, rather than adding or rewriting skills.
3 Background
GoS represents executable skills as a typed directed graph and retrieves a compact, execution-complete bundle through hybrid seed retrieval, reverse-aware graph diffusion, and budgeted reranking. SE-GoS preserves this retrieval procedure while evolving its substrate.
- GoS normalizes skill packages into graph nodes connected by weighted, typed edges representing dependency, workflow, semantic, and alternative relations.
- Given a query and context budget, retrieval returns a relevant, compact bundle that is execution-complete when possible.
- SE-GoS inherits the GoS retrieval procedure unchanged while evolving the graph it reads.
- Hybrid seed retrieval: Hybrid seed retrieval combines semantic and lexical scores, while SE-GoS sets ξ = 0 and uses lexical seeding without an embedding service.
- Reverse-aware typed diffusion: Reverse-aware Personalized PageRank propagates relevance from matched seeds toward structurally important prerequisites.
- Budgeted reranking and hydration: The converged graph score is combined with field-level query evidence, and skills are hydrated in descending rank under per-skill and global budgets.
4 Method
SE-GoS uses execution traces to evolve graph topology, edge weights, and retrieval-facing descriptions while keeping retrieval fixed. The resulting experience-aware ranking incorporates evolved structure, historical effectiveness, and updated descriptions.
- SE-GoS starts from a deterministic semantic-only graph and uses execution feedback to supply workflow, dependency, and avoid structure.
- Trace artifacts record queries, rewards, retrieved bundles, used skills, and token counts, including skills used outside the retrieved bundle.
- The three updates act separately on the discrete edge set, continuous edge weights, and node text.
- Topology Update: Topology induction adds workflow edges from successful retrieval-to-use co-occurrence, dependency edges from ordered schema-confirmed use, and avoid edges from failed co-occurrence, while pruning misleading edges.
- Topology Update: Dependency induction requires ordered skill-use traces, and the full-benchmark protocol records that order.
- Topology Update: Soft pruning halves incoming semantic weights for frequently surfaced but never-used skills, removing edges that fall below a floor.
- Edge-Weight Update: Edge-weight reinforcement increases incoming weights for skills used on positively rewarded trials, scaling credit by reward.
- Node Update: Node updates target used-but-low-ranked skills on trials below rsucc=0.9, using one textual-gradient edit-and-select round.
5 Experiments
The experiments evaluate SE-GoS against flat, vector, static-graph, and self-evolving baselines across benchmark, held-out, and multi-round settings. One evolution round improves reward and preserves transferable gains, while repeated evolution eventually degrades performance.
- Experimental setup: SE-GoS is evaluated against Vanilla, Vector, static GoS, and SkillDAG under the original GoS configuration across SkillsBench and ALFWorld.The study also includes held-out evaluation, multi-round evolution, and a factorial ablation of update contributions.
- Main results: 59.4% reward makes one-round SE-GoS the best SkillsBench configuration, improving static GoS by 7.0 points.Static GoS reaches 52.4%, while SkillDAG reaches 55.3%.
- Main results: 3.45M input tokens per attempt puts SE-GoS 32% below Vanilla full loading while retaining the highest SkillsBench reward.Vanilla uses 5.06M tokens per attempt; Vector uses 3.11M but obtains lower reward.
- Held-out evaluation: 58.3% held-out reward improves static GoS from 52.9% by 5.4 points on 37 disjoint evaluation tasks.Tokens remain essentially unchanged at 3.30 → 3.19M per attempt, with comparable runtime.
- Multi-round evolution: 59.4 reward at round 1 rises only to 59.8 at round 2 before dropping to 54.0 at round 3.The decline accompanies graph growth to 1,502 edges, supporting one-shot deployment rather than repeated evolution.
6 Conclusion
SE-GoS turns execution traces into an evolving retrieval substrate without training model parameters, changing retrieval code, or modifying skill content. One round improves benchmark retrieval and transfers to unseen tasks, whereas repeated updates eventually reverse the gains.
- Contribution: SE-GoS evolves topology, edge weights, and retrieval-facing descriptions from execution traces while leaving model parameters, retrieval code, and skill content unchanged.Its central mechanism is rewiring the graph that the fixed PPR-based retrieval pipeline reads.
- Conclusion: One evolution round makes the static graph strongest on the benchmark while reducing input tokens relative to full loading and transferring gains to unseen tasks.Repeated evolution plateaus and then reverses, making the update a one-shot deployment step rather than a training loop.
Limitations
The paper’s evaluation and update protocol impose explicit scope boundaries. Performance is reported after one evolution round, with limited characterization of longer horizons, indirect skill use, convergence, and broader settings.
- Update horizon: 59.8% at round 2 and 54.0% at round 3 motivate reporting the graph after one evolution round.The protocol excludes finer-grained reward signals and longer horizons.
- Trace evidence: Indirect skill use can undercount evidence because topology and weight updates depend on the trajectory-derived used-skill set U_t.
- Evaluation scope: Results are bounded to SkillsBench at 1,000 skills and the ALFWorld dev split under three model families.The paper makes no claim about other backbones or 200-, 500-, or 2,000-skill scales.
- Convergence: Cold-start and long-horizon convergence are only partially characterized despite confidence-weighted interpolation protecting low-evidence edges.
- Supporting analysis: The appendix contains method details, additional analyses and ablations, and reproducibility and fidelity materials.
A Method and Protocol Details
SE-GoS evolves a static graph offline from execution traces while leaving GoS inference unchanged. The protocol extracts trace signals, applies topology, edge-weight, and node updates, then runs the existing retrieval procedure on the evolved graph.
- Pipeline: SE-GoS separates offline evolution into signal extraction and dependency-ordered graph updates, followed by unchanged GoS inference.Phase A scans traces; Phase B applies topology, edge, and node updates.
- Signal extraction: Execution traces count successful workflow co-occurrences, ordered schema-supported dependencies, failed co-occurrences, and used-but-missed skills.These counts produce the signal tuple used by the evolution phase.
- Topology evolution: Topology updates add workflow and dependency edges, add zero-weight avoid edges for repeated failure-only pairs, and prune incoming semantic weights for never-used heads.The evolved graph starts from the static graph and returns updated edges, weights, and descriptions.
- Description evolution: Node descriptions are revised for used skills that were ranked below the node-update threshold, using a skill-local textual critique-and-edit procedure.The prompts critique retrieval failure before producing a revised description.
- Inference: Retrieval computes lexical or evolved-description seeds, propagates scores with reverse-aware PPR over evolved weights, reranks, and returns a bounded execution bundle.Retrieval-side hyperparameters are held fixed across benchmarks and library sizes.
- Structural substrate: SE-GoS reconstructs workflow structure from execution feedback rather than assuming GoS’s LLM relation-validation pass.Its cold-start graph uses deterministic semantic-similarity edges, while lexical and I/O-index channels remain available without an embedding service.
- Trace processing: Used-skill extraction scans tool calls for references to hydrated skill source paths and maps those paths to normalized skill nodes.The procedure was validated on a subset with expert-annotated skill sets.
A.5 Qualitative Analysis
The qualitative analysis makes the evolution edits inspectable and explains the deployment choices behind the graph substrate. Execution-derived relations and weight changes are contrasted with deterministic, model-free construction choices.
- Inspectable deltas: Topology edits include execution-grounded workflow, dependency, and avoid relations, while semantic weights into repeatedly unused skills are softened.The reported avoid set is empty in the k=1 full-benchmark substrate and contains one edge in the denser k=8 head cell.
- Inspectable deltas: Rewarded use increases target-edge weights, and used-but-missed skills receive retrieval-facing description edits.The per-round edge and node-edit totals are reported in Table 4.
- Semantic substrate: Signature-token Jaccard overlap provides a deterministic, model-free semantic substrate that remains recomputable after description edits.This avoids dependence on an embedding service or an immutable precomputed index.
- Configuration rationale: SE-GoS replaces GoS’s LLM-derived workflow prior with workflow edges reconstructed from observed retrieval-to-use behavior.
- Typed relations: The static graph contains only semantic edges because SE-GoS targets deployed graphs lacking execution structure and supplies that structure from feedback.
- Seed design: Lexical-only seeding retains the channel that GoS’s ablation identifies as more influential than graph propagation for hybrid seed quality.The cited ablation reports a 7.7-point cost for dropping lexical retrieval and reranking versus 5.1 for removing graph propagation.
A.7 Design Rationale (full arguments)
SE-GoS evolves graph structure, weights, and retrieval-facing descriptions from execution evidence while preserving a fixed retrieval consumer. The design emphasizes graph-mediated transfer, safeguards against sparse evidence, and explicit scope boundaries around relation induction and repeated updating.
- Deployment boundary: Repeated experience-aware updating can overfit traced tasks: the multi-round curve plateaus at round 2 and overfits by round 3.Windowed deployment is measured only through the reported single-round and multi-round regimes, not characterized beyond them.
- Deployment safeguard: Confidence-weighted interpolation keeps sparse or unseen edges near the static prior and shifts retrieval toward experience as evidence accumulates.In the evaluated single-round protocol, this safeguard is retained for multi-round and cold-start regimes rather than exercised.
- Graph-mediated adaptation: Graph-structured updating lets successful transitions from u to v create future skill–skill transfer that independent per-skill experience scores cannot express.When u leads to successful use of v, future queries retrieving u gain a path to v.
- Design scope: SE-GoS updates the retrieval substrate through topology, edge-weight, and node-description changes while keeping the retrieval procedure fixed.The graph’s mutable components are updated in dependency order; the node set and per-relation weights remain fixed.
- Relation design: The topology update induces workflow, dependency, and avoid relations from execution, but not alternative relations because traces directly witness co-loading harm rather than interchangeability.Alternative relations would require counterfactual evidence or an LLM prior; the assumed traces do not provide that.
B.1 Component Ablations
The factorial ablation finds that all three evolution levers improve the static graph, with edge-weight evolution contributing most and the full combination achieving the highest reward. Calibration against the reported variability band favors the direction of effects over precise single-lever magnitudes.
- Factorial results: 59.4 reward is the best factorial cell, exceeding edge+node at 59.1 and topology+edge at 58.8.The full method is the best overall cell in the 2^3 component ablation.
- Component effects: Edge-weight evolution has the largest main effect at +4.7, versus +1.4 for topology and +1.3 for node content.Leave-one-out results also identify edge weights as the only appreciable removal effect.
- Single-lever cells: Topology reaches 54.1 (+1.7), edge reaches 57.3 (+4.9), and node reaches 53.6 (+1.2) on static.These are the reported single-lever cells and gains in the k=1 component ablation.
- Calibration: Pairwise cells containing the edge update gain +6.4 and +6.7, while the full method gains +7.0.These effects reach or exceed the reported ±6–7-point variability band, unlike the single-lever gains.
- Interpretation: Calibration supports the ordering edge weights first, followed by node content and topology, rather than sharply resolved component magnitudes.Single-lever gains of +1.2 to +4.9 remain inside the reported variability band.
B.2 Retrieval-Interface Ablation
The interface ablation holds the evolved graph and ranking fixed while comparing fused-bundle retrieval with a SkillDAG-style multi-channel interface. Their pooled reward difference is negligible at this benchmark scale, though sparse conflict evidence limits what the comparison tests.
- Experimental control: The comparison holds the evolved graph and lexical-seed/PPR ranking fixed while varying only the fused-bundle versus three-channel presentation.The alternative exposes matches, typed neighbors within two hops, and conflicts as exclusion-only.
- Outcome: +1.0 pp pooled reward separates the two interfaces, with a 3.4 pp standard error across 87 tasks.Fourteen tasks favor each interface and 59 tie.
- Interpretation: The result shows no measurable reward effect from channel presentation at this scale and on this backbone.The reported contrast is an interface ablation rather than a comparison of different rankings or evolved graphs.
- Scope: The near-empty conflicts channel and workflow-dominated typed-neighbor channel mean the test emphasizes presentation more than richer conflict or neighbor evidence.Only one avoid edge is induced under the denser substrate and two-attempt task budget.
- Evaluation scope: The evaluation follows SkillDAG’s deployment-utility convention by generating and re-measuring traces on all 87 SkillsBench tasks, then adds a held-out split to separate memorization from transfer.The held-out evaluation evolves the graph on one task subset and measures on another.
C.2 Benchmark-Fidelity Audit
The benchmark-fidelity audit finds the instructions, reward verifiers, and resource settings byte-identical to upstream SkillsBench v1.1. Differences are confined to build-layer accommodations, including two pinned web dependencies, while oracle behavior does not determine reward.
- Task inputs: 0 of 87 instruction.md files differ from the upstream v1.1 snapshot.The agent prompts were unchanged across all evaluated task packages.
- Reward verification: 0 of 87 tests/ directories differ, including the reward verifier and scoring scripts.The verifier threshold and reward computation files were unchanged.
- Execution constraints: 0 of 87 task.toml files differ in timeouts, CPU, memory, storage, or network policy.The resource and execution constraints match upstream v1.1.
- Build-layer differences: Four tasks use cached build artifacts, one removes unused Oracle JDKs, and two web tasks pin different Next.js versions.These changes are confined to Docker build layers; the web dependency pins are the only true dependency-version difference.
- Oracle scope: The oracle script difference is limited to an error-message string, and oracles never determine reward.The audit therefore attributes no reward change to the oracle discrepancy.