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.05333v3cs.AI

TL;DR

Large skill libraries make full-context loading expensive and semantic retrieval execution-incomplete when prerequisites are missed. GoS constructs an executable skill graph offline and retrieves bounded dependency-aware bundles through hybrid seeding, reverse-aware diffusion, and budgeted hydration. Across SkillsBench and ALFWorld, it improves rewards while reducing token use, including a 25.55% peak reward gain and 56.72% token reduction on one GPT-5.2 Codex setting.

  • Problem

    Full skill loading raises token costs in large libraries, while semantic retrieval can miss functionally necessary prerequisite chains and return execution-incomplete bundles.

  • Method

    GoS builds a typed executable skill graph offline and uses hybrid semantic-lexical seeding, reverse-aware Personalized PageRank, reranking, and budgeted hydration at inference time.

  • Results

    GoS improves reward over both baselines across all six model–benchmark blocks while reducing average token usage in every block and runtime in five.

  • Takeaways & Limitations

    GoS retrieves a small jointly sufficient bundle containing target skills and the parsers, preprocessors, and dependencies needed for execution as libraries scale.

  • Takeaways & Limitations

    Evaluation covers only SkillsBench and ALFWorld with three model families, excluding multimodal embodied, web-browsing, and other interactive settings.

Abstract

from arXiv · show

Modern LLM agents increasingly rely on reusable skills, and as they interact with personal applications, web browsers, and other interfaces, skill libraries can scale to thousands of skills. Scaling to larger skill sets introduces two key challenges. First, loading the full skill set saturates the context window, driving up token costs, hallucination, and latency. Second, semantic retrieval surfaces topically relevant skills but misses their prerequisite chain of upstream and downstream skills, creating a prerequisite gap that leaves the retrieved bundle execution-incomplete. In this paper, 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 at inference time retrieves a bounded, dependency-aware skill bundle through hybrid semantic-lexical seeding, reverse-aware Personalized PageRank, and context-budgeted hydration. On SkillsBench and ALFWorld, GoS consistently delivers substantial reward improvements and token savings across three model families (Claude Sonnet 4.5, MiniMax M2.7, and GPT-5.2 Codex). On SkillsBench, GoS achieves a peak reward increase of 25.55% while reducing total tokens by 56.72% over the vanilla full skill-loading baseline using GPT-5.2 Codex. Ablations confirm this pattern across skill libraries from 200 to 2,000 skills.

1 Introduction

Large skill libraries make retrieval—not merely tool invocation—the central challenge: 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 retrieval becomes a major bottleneck as agent skill libraries scale from dozens to thousands of candidates.
  • Full-library loading scales poorly because token costs grow with library size and important constraints can be overlooked in overloaded contexts.
  • Semantic retrieval improves efficiency but can miss semantically weak prerequisites such as parsers, converters, setup utilities, and preprocessors.
  • GoS builds a directed multirelational graph offline, then uses semantic and lexical seeds with reverse-aware diffusion to recover structurally important skills.
  • 25.55% peak reward gain and 56.72% lower total tokens were achieved on 1,000-skill SkillsBench with GPT-5.2 Codex versus full skill loading.

2 Related Work

Related work spans tool retrieval, reusable skill ecosystems, and graph-based retrieval, but these lines address different stages or substrates than GoS's dependency-aware retrieval of local skills.

  • Tool Use, Tool Discovery, and Tool Retrieval for Agents: Early tool-use research assumed relatively small fixed toolsets and focused on invocation decisions and call formatting.
  • Tool Use, Tool Discovery, and Tool Retrieval for Agents: As tool collections expand, research shifts toward tool discovery and retrieval, with systems such as Gorilla and API-Bank supporting this transition.
  • Agent Skills Ecosystems: Skill ecosystem systems emphasize reusable assets, categorization, ontology construction, dynamic chaining, and large-scale organization.
  • Agent Skills Ecosystems: SkillsBench shows that many available skills do not guarantee reliable use, motivating retrieval methods beyond library availability alone.
  • Graph-Based Retrieval and Relational Memory: Graph-based retrieval has been applied to documents, long-term memory, and tool graphs, whereas GoS targets executable skill dependency structure.

3 Methodology

GoS converts local skill packages into a typed executable graph and retrieves compact bundles through hybrid seeding, reverse-aware diffusion, reranking, and budgeted hydration.

  • Problem Setup: GoS constructs a typed directed graph whose nodes are normalized executable skills and whose edges carry weighted relation types.
  • Problem Setup: The retrieval objective seeks bundles that are relevant, execution-complete when possible, and compact under a context budget.
  • Offline Graph Construction: Offline indexing normalizes skill records from package specifications and assets, while graph construction adds dependency, workflow, semantic, and alternative relations.
  • Offline Graph Construction: Sparse validation limits non-dependency relation inference to top-k candidate pools, reducing validation complexity from O(N^2) to O(Nk).
  • Online Structural Retrieval: Hybrid seeding combines semantic and lexical retrieval after mapping the query into task goals, operations, artifacts, and normalized keywords.
  • Online Structural Retrieval: Reverse-aware diffusion propagates relevance from matched high-level skills toward upstream prerequisites through typed forward and reverse transitions.
  • Online Structural Retrieval: GoS combines diffusion scores with field-level query evidence, then hydrates candidates under per-skill and global budgets into a bounded execution bundle.

4 Experiments

The experiments compare GoS with flat full-library access and semantic retrieval across SkillsBench and ALFWorld, using three model families. GoS achieves the strongest reward broadly while reducing token usage, and trajectory evidence links this advantage to more executable skill bundles.

  • 4.2 Main Results: GoS attains the highest average reward across all six model–benchmark blocks.It reduces average token usage relative to Vanilla Skills in all six blocks and reduces agent runtime in five.
  • 4.2 Main Results: GoS improves reward over Vector Skills in every model–benchmark block while keeping token usage in the same compressed regime.The comparison isolates dependency-aware structural retrieval from general retrieval-time compression.
  • 4.2 Main Results: Vector Skills often misses indirect prerequisites needed for long-horizon tasks, producing incomplete skill sets and lower task completion rates.SkillsBench tasks commonly require environment setup, preprocessing, or output-formatting utilities that are not lexically salient in the task description.
  • 4.2 Main Results: On ALFWorld, GoS reaches 97.9% average success under Claude Sonnet 4.5 versus 93.6% for Vector Skills and 89.3% for Vanilla Skills.It also reduces average total tokens from 1,524,401 to 27,215 relative to flat prompting.
  • 4.3 Qualitative Analysis: For pedestrian traffic counting, GoS retrieves a compact bundle and achieves the highest score, 0.417, versus 0.267 for Vanilla Skills and 0.041 for Vector Skills.The retrieved skills center on video counting, frame extraction, and vision processing, supporting a short but complete visual pipeline.
  • 4.3 Qualitative Analysis: The trajectory example suggests GoS helps by exposing a bundle close to the task’s executable decomposition, enabling earlier commitment to a verifier-aligned plan.Vector retrieval provided relevant context but not a workable end-to-end plan.

5 Ablation Study

A library-size study and component ablations examine how GoS scales and which retrieval stages support its performance. Retrieval compresses prompt growth, while both graph propagation and lexical reranking contribute to reward.

  • 5.1 Sensitivity to Skill Library Size: As the library grows from 500 to 2,000 skills, Vanilla Skills input tokens rise from 1.93M to 5.84M, roughly a 3× increase.Vector Skills stays near 1.10M–1.24M tokens and GoS near 1.14M–1.38M tokens over the same range.
  • 5.1 Sensitivity to Skill Library Size: GoS maintains a reward advantage at every tested scale once the library is moderately large.At 500, 1,000, and 2,000 skills, rewards are 31.4, 34.4, and 31.3 for GoS versus 26.0 / 20.7, 27.4 / 21.5, and 26.7 / 23.8 for Vanilla Skills / Vector Skills.
  • 5.1 Sensitivity to Skill Library Size: At 200 skills, Vanilla Skills remains slightly ahead of GoS, with rewards of 32.5 versus 32.1.The advantage reverses as the repository becomes larger.
  • 5.1 Sensitivity to Skill Library Size: Both retrieval-based methods are slower than Vanilla Skills at most GPT scales, reflecting search overhead before execution.The reduced-runtime pattern is unique to GPT-5.2 Codex, likely because of caching mechanisms for fixed skill libraries.
  • 5.2 Component Analysis of Retrieval Pipeline: Removing graph propagation lowers average reward from 34.4 to 29.3 while reducing average token usage from 1.38M to 0.89M.The ablation disables expansion beyond seed skills to structurally related prerequisites.
  • 5.2 Component Analysis of Retrieval Pipeline: Removing lexical retrieval and reranking lowers average reward from 34.4 to 26.7 and average token usage from 1.38M to 1.01M.The larger reward degradation suggests seed quality is especially important for recovering useful prerequisite structure.

6 Conclusion

GoS addresses the retrieval bottleneck in massive skill libraries by selecting a small, jointly sufficient bundle rather than exposing the full library or relying on topical similarity alone. Across the reported benchmarks and model families, it improves reward while reducing token use, including as libraries scale from 200 to 2,000 skills.

  • 6 Conclusion: GoS retrieves a small, jointly sufficient bundle containing target skills plus the parsers, preprocessors, and dependencies needed for execution.On 1,000-skill SkillsBench with GPT-5.2 Codex, it gains 25.55% reward while reducing total tokens by 56.72% over full loading.

Limitations

GoS is constrained by offline graph quality and a limited evaluation scope. Documentation and schema ambiguity can degrade dependencies, while the static graph cannot learn from execution feedback.

  • Poor documentation or ambiguous I/O schemas can degrade graph edges, with resulting errors propagating into retrieval.
  • The offline-built graph cannot self-correct wrong induced dependencies or missed useful relations because it does not update from execution traces or user feedback.
  • Evaluation covers SkillsBench and ALFWorld across three model families, excluding multimodal embodied, web-browsing, and other interactive settings.

A Appendix Overview

The appendix is organized as a roadmap for supplementary evidence that complements the main paper across implementation, interface, retrieval, and empirical-analysis concerns.

  • The appendix complements the main paper along four axes: implementation fidelity, prompt/interface design, retrieval mechanics, and trajectory-grounded empirical analysis.
  • Table 3 summarizes each supplementary section’s role and how it complements the main paper.

B Implementation Details

GoS combines deterministic skill normalization and typed graph construction with sparse LLM augmentation, hybrid query seeding, reverse-aware diffusion, and budgeted hydration. These choices produce a compact bundle intended to retain prerequisite structure while remaining executable and context-efficient.

  • Pipeline: GoS has offline and online phases: it parses skill packages, constructs typed relations, retrieves through hybrid seeding and graph diffusion, then returns a reranked budgeted bundle.
  • Skill normalization: Each skill is normalized into structured and textual fields, including capabilities, I/O, tags, tooling, entrypoints, compatibility notes, and a stable source path.
  • Graph construction: Dependency edges are directed and typed: an edge u → v indicates that u can provide an artifact consumed by v, preserving prerequisite direction.
  • Graph construction: Non-dependency relations are validated sparsely within bounded candidate pools formed from lexical overlap, semantic neighbors, and I/O expansion.
  • Retrieval: GoS combines semantic and lexical seeding, reranking, and per-skill and global context budgets to hydrate only the highest-value skills for agent execution.
  • Retrieval: Reverse-aware diffusion propagates relevance from matched skills toward likely prerequisites rather than collapsing the graph into an undirected similarity graph.

C Prompt and Interface Examples

GoS uses constrained internal prompts for normalization, relation validation, and optional query rewriting, then an agent-facing interface that operationally governs retrieval use and downstream behavior.

  • Internal prompts: Internal prompts restrict LLMs to node normalization, optional query rewriting, and sparse relation validation rather than unconstrained graph construction.
  • Internal prompts: Semantic completion extracts retrieval-critical fields for one skill, preserves canonical information, and emits no graph relationships when uncertain.
  • Internal prompts: Relation validation operates on a small candidate pool and favors sparse, high-precision dependency, workflow, semantic, and alternative edges.
  • Query rewriting: Optional query rewriting exposes goals, operations, artifacts, constraints, and keywords, while deterministic lexical normalization remains the fallback.
  • Agent interface: The agent interface requires targeted retrieval before coding, distinguishes SKILL_HIT from NO_SKILL_HIT, and directs reuse of retrieved scripts and exact source paths.
  • Agent interface: The interface is part of the method because it constrains when retrieval occurs, how bundles are interpreted, and how strongly agents favor local implementations.

D Core Retrieval Pseudocode

GoS’s pseudocode separates offline graph construction from online structural retrieval. The pipeline normalizes skill packages, induces typed relations, propagates query relevance through a reverse-aware graph, and hydrates a bounded execution bundle.

  • Offline graph construction: Offline construction parses each skill package into normalized executable records and builds a typed directed graph plus vector index.The presentation covers parser-first normalization, relation induction, embedding indexing, and persistence of retrieval metadata.
  • Offline graph construction: Producer–consumer overlap between one skill’s outputs and another’s inputs induces typed dependency edges.Candidate relations are formed from lexical similarity, semantic neighbors, and I/O-based expansion before constrained validation.
  • Online structural retrieval: Online retrieval merges semantic and lexical seed candidates, constructs a seed distribution, and builds a typed transition matrix.The query may optionally be rewritten into a compact schema containing goals, operations, artifacts, constraints, and keywords.
  • Online structural retrieval: Reverse-aware Personalized PageRank adds relation-specific reverse mass, emphasizing dependency edges, before candidate reranking with graph and field-level query evidence.The resulting scores identify structurally important skills beyond isolated semantic matches.
  • Online structural retrieval: The system hydrates ranked skills into agent-facing payloads and truncates them under per-skill and global context budgets.Hydrated payloads include exact Source: paths and concise execution notes.

E Error Analysis

The error analysis distinguishes retrieval misses, incomplete prerequisite bundles, downstream execution failures, and infrastructure failures. These categories clarify which failures GoS can address and where retrieval quality alone is insufficient.

  • Retrieval failures: Retrieval misses occur when the correct repository skill is never surfaced, forcing the agent onto a generic from-scratch path.The paper attributes downstream failure in this regime primarily to retrieval rather than execution.
  • Retrieval failures: A dapt-intrusion-detection miss omitted pcap-analysis and returned irrelevant skills, whereas a stronger baseline reused tested helper code and passed the verifier.The example illustrates how absent relevant skills can turn the task into failing from-scratch implementation.
  • Partial retrieval: Partial retrieval includes a relevant high-level skill but omits prerequisite helpers such as parsers, converters, preprocessing utilities, or setup routines.Reverse-aware propagation is intended to recover structurally connected skills that are weak semantic matches to the raw query.
  • Partial retrieval: Structural retrieval helps only when the recovered neighborhood is sufficiently complete to support the downstream pipeline.In earthquake-phase-association, GoS retrieved a partially relevant seismic bundle, but the task still failed with reward 0.0.
  • Downstream and infrastructure failures: Some failures arise despite broadly adequate bundles because agents overgeneralize, ignore authoritative interfaces, or fail to align outputs with the verifier.The paper treats these as execution failures rather than retrieval misses and separately identifies infrastructure failures such as setup crashes and timeouts.

F Qualitative Analysis

The qualitative cases show that GoS often exposes compact bundles close to a task’s executable decomposition, but retrieval completeness, trajectory efficiency, and verifier alignment remain separate bottlenecks.

  • Success and intermediate cases: GoS surfaced a compact visual pipeline for pedestrian traffic counting and achieved the strongest outcome among the three conditions, with reward 0.417.The bundle centered on gemini-count-in-video, video-frame-extraction, and openai-vision.
  • Success and intermediate cases: GoS exposed the required flood-risk-analysis chain with less search friction and passed with reward 1.0, while Vanilla Skills also succeeded.The chain combined usgs-data-download, nws-flood-thresholds, and flood-detection.
  • Success and intermediate cases: GoS converted dialogue parsing into a full pass with a compact dialogue_graph-centered bundle, whereas Vector Skills reached only a substantial partial score.The strongest GoS trajectory also included structural and parser-oriented helpers.
  • Failure cases and boundaries: GoS failed earthquake phase association because its recovered neighborhood remained incomplete relative to the execution-complete all-skills pipeline.The GoS bundle omitted required components such as obspy-data-api and obspy-datacenter-client and included an irrelevant distraction skill.
  • Success and intermediate cases: When all methods recovered a geometry-centered bundle for 3D scan calculation, all could succeed; the difference was how directly that bundle was exposed.GoS, Vanilla Skills, and Vector Skills all passed after recovering mesh-analysis or related geometry skills.
  • Failure cases and boundaries: Adaptive cruise control failed under all three conditions despite plausible control bundles, indicating that long control-design and verifier-alignment chains can remain execution bottlenecks.Energy-market-pricing similarly showed that trajectory quality can differ even when both all-skills and GoS pass.
Loading 2604.05333v3…