PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-of-Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills

Dawei Liu, Zongxia Li, Hongyang Du, Xiyang Wu, Shihang Gui, Yongbei Kuang, Lichao Sun

arXiv:2604.05333v4cs.AI

TL;DR

Large skill libraries make full-context loading expensive and semantic retrieval incomplete because prerequisites can be missed. GoS builds an executable skill graph and retrieves bounded dependency-aware bundles through hybrid seeding, reverse-aware diffusion, and budgeted hydration. It leads across all six model–benchmark blocks while reducing prompt cost, with its strongest reported gain being 7.0 reward points over full loading.

  • Problem

    Full skill loading becomes costly at scale, while semantic retrieval can miss functionally necessary prerequisite skills.

  • Method

    GoS builds an executable skill graph offline and retrieves bounded bundles using hybrid semantic-lexical seeding, reverse-aware diffusion, and budgeted hydration.

  • Results

    GoS attains the highest average reward in all six model–benchmark blocks and, on 1,000-skill SkillsBench with GPT-5.2 Codex, gains 7.0 absolute points over full loading while cutting total tokens by 56.7%.

  • Takeaways & Limitations

    The ablations indicate that reverse traversal, rather than graph diffusion alone, is the key mechanism behind the reported gain.

  • Takeaways & Limitations

    GoS depends on graph quality: isolated skills and stochastic or incomplete relations constrain structural retrieval, especially for sparsely documented libraries.

Abstract

from arXiv · show

As LLM agents act across personal applications, web browsers, and other interfaces, their reusable skill libraries can scale to thousands of skills. This scale introduces two challenges. First, loading the full library saturates the context window, driving up token costs, hallucination, and latency. Second, semantic retrieval surfaces topically relevant skills but can miss upstream and downstream prerequisite skills, creating a prerequisite gap that leaves the retrieved bundle insufficient for execution. We present Graph-of-Skills (GoS), an inference-time structural retrieval layer for large skill libraries. GoS constructs an executable skill graph offline from skill packages, then retrieves a bounded, dependency-aware bundle through hybrid semantic-lexical seeding, reverse-aware Personalized PageRank, and context-budgeted hydration. Across SkillsBench and ALFWorld, with three model families (Claude Sonnet 4.5, MiniMax M2.7, and GPT-5.2 Codex), GoS attains the highest average reward in all six model-benchmark blocks, at a fraction of the token cost of loading the full library. On SkillsBench with GPT-5.2 Codex it raises average reward by 7.0 absolute points over full skill loading, a 25.6% relative gain, while cutting total tokens by 56.7%. Ablations isolate the mechanism: replacing reverse traversal with forward propagation costs 9.1 reward points, a larger loss than removing the graph altogether. The gain thus comes from traversing dependencies backwards, not from graph diffusion as such. A budget-matched retrieval study holding seeding, reranking, hydration, and context budget fixed reproduces the same ordering, with dependency-pair co-recovery falling from 0.654 to 0.362. Code is available at https://github.com/davidliuk/graph-of-skills

1 Introduction

Large skill libraries make retrieval a central bottleneck: full loading is costly and noisy, while semantic retrieval can omit functionally necessary prerequisites. Graph-of-Skills addresses this gap with structural retrieval that assembles compact, dependency-aware execution bundles.

  • Skill inventories growing from dozens to thousands shift the challenge toward retrieving a sufficient set rather than selecting whether to use a skill.
  • Full-library loading scales poorly because token cost grows with library size and important constraints become buried in overloaded contexts.
  • Semantic retrieval improves efficiency but can miss semantically weak prerequisites such as parsers, converters, setup utilities, or preprocessors.
  • GoS builds a directed multirelational graph offline and uses hybrid seeding plus reverse-aware Personalized PageRank to recover structurally important skills.
  • GoS targets the smallest local-library subset sufficient to execute a task, complementing ecosystem systems that organize or create skills.
  • Across two benchmarks and three model families, GoS leads every model–benchmark block; on 1,000-skill SkillsBench with GPT-5.2 Codex, reward rises 7.0 points while tokens fall 56.7% versus full loading.

2 Related Work

Prior work addresses tool use, skill acquisition, skill ecosystems, and graph-based retrieval, but GoS focuses on selecting dependency-complete subsets from a fixed local skill corpus. Its distinction is retrieval for executable local bundles rather than capability growth, ecosystem organization, or broad graph propagation.

  • Tool Use, Discovery, and Retrieval for Agents: As toolsets expand and tasks become longer, prior tool-use research increasingly addresses tool discovery and retrieval rather than only invocation.
  • Skill Acquisition and Self-Improvement: Skill-acquisition methods grow capabilities through experience, embodied accumulation, program induction, or self-generated feedback, whereas GoS assumes a fixed corpus and selects what to load.
  • Agent Skills Ecosystems: Skill ecosystems package, categorize, chain, and search reusable skills, but availability alone does not guarantee reliable use.
  • Graph-Based Retrieval and Relational Memory: Graph-based systems support document synthesis, associative memory, or broad tool ecosystems, while GoS targets dependency-complete local bundles.

3 Methodology

GoS converts local skill packages into a typed graph and retrieves a compact execution bundle through hybrid seeding, reverse-aware diffusion, and budgeted reranking and hydration. The design explicitly favors upstream prerequisites while preserving direct query evidence and context limits.

  • Offline Graph Construction: GoS builds a typed graph offline from normalized executable skill records, with weighted edges encoding dependency, workflow, semantic, and alternative relations.
  • Retrieval Objective: The retrieval objective balances query relevance, dependency-complete bundles, and prompt cost under a context budget, motivating a three-stage approximation.
  • Skill Normalization: Normalization extracts canonical names, capabilities, I/O fields, tags, tooling, entrypoints, compatibility notes, and stable source paths into retrieval units.
  • Typed Relation Induction: Dependency edges are induced from I/O compatibility, while workflow, semantic, and alternative relations are added through sparse candidate validation whose comparisons scale as O(Nk).
  • Hybrid Seeding: Hybrid seeding combines dense semantic retrieval, which finds visible top-level skills, with lexical retrieval, which better matches concrete artifacts and filenames.
  • Online Structural Retrieval: Reverse-aware diffusion lets a retrieved high-level solver transfer relevance to upstream parsers, setup utilities, and preprocessors that are weak semantic matches.
  • Budgeted Reranking and Hydration: Budgeted reranking combines diffusion with field-level query evidence, then hydrates candidates in score order into a bounded agent-consumable bundle.

4 Experiments

Across two benchmarks and three model families, GoS achieves the highest reward while reducing token usage versus full-library access. Its advantage reflects dependency-aware retrieval: semantic retrieval can miss prerequisites, whereas GoS often returns more execution-ready bundles, though connected prerequisite neighborhoods are not guaranteed.

  • Main results: GoS achieves the highest average reward in all six model–benchmark blocks, reduces tokens in every block, and beats Vector Skills on reward throughout.It also reduces runtime in five of six blocks.
  • Main results: On SkillsBench, Vector Skills falls below full-library exposure in all three model blocks, while GoS improves on both baselines with substantially fewer tokens.The reported full-library-to-vector declines are 25.0 to 19.3, 17.2 to 10.4, and 27.4 to 21.5 for Claude Sonnet 4.5, MiniMax M2.7, and GPT-5.2 Codex, respectively.
  • Main results: On ALFWorld, GoS reaches 97.9% success versus 93.6% for Vector Skills and 89.3% for Vanilla Skills under Claude Sonnet 4.5.It cuts average total tokens from 1,524,401 to 27,215 in that block.
  • Main results: Under GPT-5.2 Codex on ALFWorld, GoS differs from Vector Skills by one episode and uses more tokens and runtime, showing a trade-off rather than a universal win.The reported success rates are 93.6% versus 92.9%.
  • Trajectory analysis: Across ten trajectory cases, GoS surfaced a complete visual-processing pipeline and scored 0.417, whereas Vector Skills returned related context that did not become a workable plan and scored 0.041.The earthquake-phase-association case also shows that structural retrieval can fail when the required neighborhood is only partially recovered.

5 Analysis

Across library sizes and controlled ablations, GoS preserves its reward advantage while keeping prompt cost nearly flat; reverse-aware traversal, rather than graph diffusion alone, accounts for the main gain.

  • 5.1 Sensitivity to Skill Library Size: From 500 to 2,000 skills, GoS leads both baselines by 5.4, 7.0, and 4.6 absolute reward points while retrieval keeps token growth near-flat.Vanilla Skills rises from 1.93M to 5.84M tokens, whereas Vector Skills remains at 1.10M–1.24M and GoS at 1.14M–1.38M.
  • 5.1 Sensitivity to Skill Library Size: Retrieval overhead is roughly constant with library size, whereas flat exposure’s prompt cost grows, making the prompt rather than retrieval the scaling bottleneck.Under GPT-5.2 Codex retrieval is slower in agent-only runtime, but the ordering reverses for Claude Sonnet 4.5 and MiniMax M2.7.
  • 5.2 Component Ablation Study: Removing lexical retrieval and reranking lowers reward from 34.4 to 26.7, while removing graph propagation lowers it to 29.3, showing that seed quality contributes more than expansion.The corresponding token costs are 1.01M and 0.89M, compared with 1.38M for the full system.
  • 5.2 Component Ablation Study: Removing reverse transitions causes the largest ablation loss: reward falls from 34.4 to 25.3, 9.1 points, exceeding the 5.1-point loss from removing propagation.Because edges run producer →consumer, forward diffusion favors downstream consumers instead of missing upstream prerequisites.
  • 5.3 Isolating the Graph Operation: In the budget-matched retrieval study, reverse-aware PPR leads every control, with available-recall gains of +0.085 over forward PPR and +0.033 over both No-Graph and One-Hop.Forward propagation is worse than not using the graph, while No-Graph and One-Hop coincide to three decimals despite differing in precision, size, and latency.
  • 5.3 Isolating the Graph Operation: Dependency-pair co-recovery is 0.654 for reverse-aware PPR, versus 0.481 for flat and one-hop retrieval and 0.362 for forward propagation.The matched evaluator isolates propagation under fixed seeding and budgets, explaining how a small recall margin can accompany larger end-to-end gains.
  • 5.4 Graph Quality, Cost, and Robustness: The graph’s benefit depends on LLM-validated relations, while 59 of 200 nodes are isolated and typed-edge assignments remain the weak point.A 40-edge audit found all relations valid but only 34/40 best-typed; repeated builds yielded typed-directed edge Jaccard 0.607 with frozen manifests.
  • 5.4 Graph Quality, Cost, and Robustness: Construction costs $0.29 at 200 skills and $2.36 at 2,000, while online propagation adds about 1.5 ms at p50 and threshold sweeps change recall by less than 0.005.The reported threshold robustness does not remove the graph-quality limitation from imperfect typed relations.

6 Conclusion

GoS addresses retrieval bottlenecks in massive skill libraries by returning compact, jointly sufficient bundles. It achieves the highest average reward across all six model–benchmark blocks, with its strongest reported gain reaching 7.0 absolute points over full loading.

  • 6 Conclusion: GoS retrieves a small, jointly sufficient bundle containing target skills and required parsers or preprocessors, rather than loading or selecting skills independently.Its design targets both the cost of vanilla loading and the prerequisite gap of semantic retrieval.
  • 6 Conclusion: GoS attains the highest average reward in all six model–benchmark blocks, with a 7.0-point gain over full loading in the 1,000-skill GPT-5.2 Codex SkillsBench setting.

Limitations

GoS is limited by imperfect, static graph construction and an evaluation scope that leaves several important settings and measurements unresolved.

  • 59 of 200 nodes are isolated, so structural retrieval reduces to flat retrieval for a substantial minority of skills.Thin or ambiguous documentation can further degrade edge quality, and graph reconstruction is only partially reproducible.
  • The relation taxonomy omits conflicts, deprecation, externally conditioned dependencies, and negative or conditional relations.Because the graph is built offline and not revised from execution traces or feedback, incorrect or missing relations persist.
  • Evaluation covers only two benchmarks, three model families, and 200–2,000-skill libraries without every oracle skill required by the tasks.The study lacks human-annotated prerequisite graphs, does not separate retrieval from the surrounding system end to end, and leaves larger, independent, multimodal, and web-browsing settings open.

Ethical Considerations

The paper states that it advances machine learning and identifies no additional societal consequences requiring separate discussion.

  • The authors identify no additional societal consequences requiring separate discussion.

A Appendix Overview

The appendix roadmap organizes supplementary material around implementation fidelity, prompt and interface design, retrieval mechanics, and trajectory-grounded empirical analysis.

  • The appendix complements the main paper across four axes: implementation fidelity, prompt/interface design, retrieval mechanics, and trajectory-grounded empirical analysis.Table 4 summarizes how the supplementary sections are organized.

B Implementation Details

GoS combines deterministic skill parsing and executable dependency induction with sparse LLM validation, hybrid query seeding, reverse-aware diffusion, and budgeted hydration.

  • B Implementation Details: GoS operates offline by normalizing skill packages, adding I/O-matched dependency edges, and augmenting them with sparse workflow, semantic, and alternative relations.Dependency edges provide the executable backbone, while other relations are validated within restricted candidate pools.
  • B Implementation Details: Each skill node retains normalized fields, raw content, rendered snippets, entrypoints, and a stable Source: path for retrieval and direct execution.The graph and vector index use normalized fields, while hydration exposes concise, usable payloads without path reconstruction.
  • B Implementation Details: Dependency edges are directed because a producer can provide an artifact consumed by a consumer, making prerequisite direction irreducible to undirected similarity.The system induces these edges deterministically from asymmetric I/O compatibility.
  • B Implementation Details: At query time, GoS merges semantic nearest neighbors with lexical overlap across normalized skill fields before graph diffusion.Optional query rewriting produces a compact schema, but deterministic lexical normalization remains a fallback rather than a mandatory dependency.
  • B Implementation Details: Reverse-aware Personalized PageRank sends relevance backward from matched skills toward likely prerequisites, with the largest reverse coefficients assigned to dependency edges.After diffusion, candidates are reranked and hydrated under a context budget into agent-usable payloads.
  • B Implementation Details: The implementation is an interface contract: constrained offline prompts govern semantic structure entering the graph, while the external interface governs retrieved structure entering the agent context.This separates node-level semantic completion from unconstrained graph-relation generation.

E Matched Offline Retrieval Protocol

The matched evaluator isolates graph propagation by holding seeding, reranking, hydration, budgets, payload format, and graph-build replication fixed. Reverse-aware PPR yields the strongest structural retrieval outcomes, while deterministic-only structure provides a narrower advantage.

  • Design: Only the graph operation changes: all arms share queries, lexical seeds, reranking, top-N=8 selection, hydration, character budgets, execution notes, and source paths.Three independently constructed graphs carry construction variance through the comparison.
  • Metrics: The evaluator uses 76 availability-conditioned tasks for Ravail and completeness, while full-oracle recall uses all 87 tasks because 11 lack any oracle skill in the library.This conditioning prevents empty-oracle tasks from contributing vacuous perfect scores.
  • Results: Reverse-aware PPR improves available-oracle recall over forward-only PPR on builds A, B, and C: 0.612 versus 0.488, 0.549 versus 0.475, and 0.563 versus 0.506.The reverse-over-forward ordering holds on every individual graph, not only in aggregate.
  • Deterministic core versus full graph: On the deterministic core, reverse traversal improves completeness by +0.053 and co-recovery from 0.342 to 0.500, but its recall advantage over flat retrieval is not established.The recall difference versus forward propagation is +0.026 with an interval spanning zero, and versus No-Graph is −0.004 with an interval spanning zero.
  • Results: Reverse-aware PPR leads every control on recall and completeness across the matched retrieval comparison.The paired analysis averages three graph replicates within each task; its precision advantage over flat and one-hop controls is not distinguishable from zero.

F Graph Quality, Cost, and Robustness

Graph quality is shaped by sparse, variable LLM-validated relations and by metadata quality, while construction and corpus differences constrain interpretation. Documentation quality matters more for retrieval robustness than I/O completeness, and offline retrieval effects do not directly measure agent reward.

  • Graph sparsity: The primary graph has average total degree 1.73, with 59 of 200 nodes isolated, so GoS often falls back to seeding and reranking.Precision-oriented relation construction limits the structural margin over a budget-matched flat retriever.
  • Precision–coverage tradeoff: A stricter re-gated replay removes 23 edges and raises isolates from 59 to 73, while available-oracle recall changes only from 0.575 to 0.567.The tradeoff buys relation precision at a small coverage cost, with retrieval nearly unchanged.
  • Graph quality: Relation audits estimate precision, not recall: measuring missed true relations would require a human-annotated prerequisite graph that does not exist for SkillsBench.Every sampled relation in the held-out audit was operationally valid, but six of forty received a different type label.
  • Construction stability: Freezing normalized manifests makes deterministic candidate sets exactly reproducible, while end-to-end rebuilds vary because LLM-completed fields are unstable.Across three relation-only builds, typed-directed Jaccard averaged 0.607; repeated semantic completion produced pairwise Jaccard values as low as 0.265 for example tasks.
  • Construction cost: The 2,000-skill construction column is not directly comparable in wall time because concurrency differs and only 477 of 2,000 nodes have complete metadata.Construction cost at that scale therefore mixes size with corpus quality and metadata completeness.
  • Scope: SkillsBench recall is corpus-specific because 11 of 87 tasks have no oracle skill in the 200-skill library, bounding absolute recall values.Availability-conditioned metrics use the remaining 76 tasks.

G Error Analysis

The error analysis separates retrieval misses, incomplete prerequisite bundles, execution failures, and infrastructure failures. Structural retrieval helps when it recovers a sufficiently complete neighborhood, but downstream execution and infrastructure remain distinct limits.

  • Retrieval Misses: A retrieval miss occurs when the correct repository skill is not surfaced, forcing a from-scratch path that fails the verifier.Typical causes include weak query-description overlap, downstream phrasing that hides upstream utilities, and semantic over-weighting of topical similarity.
  • Partial Retrieval: Partial retrieval occurs when a relevant high-level skill is present but prerequisite helpers such as parsers, converters, preprocessing utilities, or setup routines are missing.Reverse-aware propagation targets this regime by recovering structurally neighboring skills that may be weak semantic matches to the query.
  • Partial Retrieval: Structural retrieval helps only when the recovered neighborhood is complete enough to support the downstream pipeline, not merely when a few relevant skills are present.The earthquake-phase-association case received a partially relevant but incomplete bundle and failed with reward 0.0.
  • Good Retrieval, Bad Execution: Some failures arise despite broadly adequate retrieval because agents overgeneralize, ignore authoritative interfaces, add unnecessary functionality, or miss verifier alignment.These cases bound what can be credited to retrieval alone.
  • Infrastructure Failures: Infrastructure failures such as build errors, missing toolchains, and logging failures are excluded from method-quality interpretation because they do not measure retrieval quality.They remain operationally important for reruns and experiment hygiene.

H Qualitative Analysis

Across qualitative cases, GoS more often exposes a compact bundle close to the task’s executable decomposition rather than merely improving topical overlap. Vector and full-library methods can also succeed, while incomplete neighborhoods and execution bottlenecks mark clear boundaries.

  • Pedestrian Traffic Counting: GoS achieved the strongest pedestrian-traffic-counting outcome, 0.417, with a compact visual pipeline centered on video and vision skills.The case illustrates an intermediate regime in which Vanilla Skills eventually opened relevant helpers but underperformed the tighter bundle.
  • Flood Risk Analysis: GoS passed flood-risk analysis with the exact chain of measurement download, flood thresholds, and detection skills, reducing search friction relative to Vanilla Skills.Both methods succeeded, so the qualitative advantage is earlier exposure of the intended workflow.
  • Takeaway: Across the cases, Vector Skills succeeds when it recovers the right family, but those successful bundles often become qualitatively similar to the compact, coherent bundles GoS exposes directly.The qualitative evidence supports execution-ready context as the central distinction rather than universal superiority in topical relevance.
  • Network Intrusion Detection: GoS succeeded on network intrusion detection by pairing pcap-analysis with adjacent helpers, whereas vector retrieval returned unrelated automation skills and full access still failed.This is a direct case where structural adjacency translated into a downstream win.
  • Dialogue Parsing: GoS converted dialogue parsing into a full pass with a compact dialogue_graph-centered bundle, while Vanilla Skills and Vector Skills reached weaker structured completeness.Surfacing the latent-representation skill early made the pipeline easier to operationalize.
  • Earthquake Phase Association: GoS did not complete earthquake phase association: all-skills assembled a fuller seismic stack, while GoS surfaced a weaker subset plus an irrelevant distraction and failed.The case demonstrates that structural retrieval does not automatically produce an execution-complete neighborhood.
  • Execution boundaries: Energy-market pricing and adaptive-cruise-control show that adequate retrieved context can still leave trajectory efficiency or verifier alignment as separate bottlenecks.Both cases are therefore not simple retrieval misses.
Loading 2604.05333v4…