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

Paper: arXiv:2604.05333 Code: davidliuk/graph-of-skills Code reference: main @ 69f2ab2f (2026-05-04)

1. Motivation (研究动机)

这篇论文要解决的是“大规模 agent skill library 怎么检索”的问题，而不是“要不要给 agent 写 skill”。当 skill 从几十个扩展到上千甚至上万个时，直接把所有 SKILL.md 放进上下文会产生三个问题：token 成本线性增长、长上下文里关键约束容易被模型忽略、推理延迟与幻觉风险上升。论文把这个瓶颈称为从 skill authoring 转移到 reusable skill retrieval。

第二个问题是单纯向量检索有“Prerequisite Gap”。很多真实工程任务的 query 只显式提到高层目标，例如“分析某个数据集”或“生成某类报告”，但真正可执行的 skill bundle 还需要 parser、preprocessor、环境初始化、格式转换、上传/下载脚本等前置能力。这些 prerequisite skill 与 query 的语义相似度可能不高，所以 flat vector top-k 容易只找回“主 solver”，缺少把任务跑通的底层工具。

Figure 1 解读：Vanilla Skills 追求最高召回，但把完整 skill library 塞进上下文；Vector Skills 只取语义相近的点，token 更少但可能断掉依赖链；GoS 的核心目标是在两者之间恢复“结构完整性”，即围绕任务取一个小而可执行的依赖子图。

这个问题值得研究，是因为 agent skill 越多，检索失败越不只是“少看了一条说明”，而是会直接导致执行链断裂：模型可能知道要调用某个分析 skill，却没有加载产生输入文件、规范路径、处理格式或验证结果的辅助 skill。GoS 的目标就是让 agent 在有限上下文内看到足够完整的执行 bundle。

2. Idea (核心思想)

核心思想：把 skill library 从一堆独立文档变成一个带类型边的可执行图，然后在推理时做 dependency-aware structural retrieval。GoS 不是简单把向量召回 top-k 做大，而是先用语义+词法检索找到入口点，再用带反向依赖权重的 Personalized PageRank 沿图扩散，把上游 prerequisite skill 一起拉进候选集合，最后在上下文预算内 rerank + hydrate。

与 Vanilla Skills 的本质区别是：GoS 不追求把所有 skill 暴露给模型，而是通过图结构保留“足够执行”的子集。与 Vector Skills 的本质区别是：Vector Skills 只看 query 和 skill 文档的相似度；GoS 额外显式建模 dependency / workflow / semantic / alternative 关系，使检索能从高层目标反推所需的 parser、setup、converter 等低层能力。

这个想法最关键的地方在于“依赖方向要反着走”。如果边 $u \to v$ 表示 skill $u$ 产出 artifact 给 skill $v$ 消费，那么 query 往往先命中 $v$ 这样的高层 solver；为了补齐上下文，检索必须允许分数从 $v$ 回流到 $u$ 。论文用 reverse-aware typed diffusion 实现这个回流，而不是依赖模型在过长上下文里自己发现缺失的前置步骤。

3. Method (方法)

3.1 Overall framework：离线建图 + 在线结构检索

GoS 分成两个阶段。离线阶段把每个 skill package 解析成规范化节点，并根据 I/O 兼容性、workflow、语义邻近、替代方案关系构造 typed directed graph。在线阶段把用户 query 转成轻量 retrieval schema，用 semantic/lexical seed 找入口，然后做 reverse-aware Personalized PageRank、field-level reranking 和 budgeted hydration。

Figure 2 解读：左侧是 offline indexing，把本地 skill package 变成带 name / capability / I/O / domain tags / tooling / entrypoints / compatibility / source_path 的结构化记录；中间是 typed graph，边类型区分依赖、workflow、语义邻近和 alternative；右侧是 online retrieval，把 query 映射为 schema 后进行 hybrid seeding、reverse-aware PPR、rerank 和 hydration，最终输出可直接塞给 agent 的 bounded execution bundle。

3.2 Problem setup：预算约束下的 dependency-complete bundle

论文把本地 skill corpus 表示为 $C = {d_{1}, \dots, d_{m}}$ ，并转换为 typed directed graph： $G = (V, E, w, ϕ), ϕ (e) \in {dep, wf, sem, alt} .$ 给定任务 query $q$ 和上下文预算 $τ$ ，目标是返回一个 skill bundle $B (q) \subseteq V$ ，同时满足相关、尽量执行完整、足够紧凑： $max_{B \subseteq V} \sum_{v \in B} rel (v, q) + β \sum_{(u, v) \in E_{dep}} I [u \in B \land v \in B] s.t. cost (B) \leq τ .$ 这个目标没有被精确求解；GoS 用三段近似：hybrid seed retrieval 先找入口，reverse-aware graph diffusion 补依赖，budgeted reranking + hydration 控制最终 prompt 成本。

3.3 Offline graph construction：节点标准化与四类边

每个 skill package 被解析成规范化 skill record。代码侧对应 parse_skill_document 和 SkillNode，包含 canonical name、capability summary、inputs/outputs、domain tags、tooling、example tasks、script entrypoints、compatibility、allowed tools、source path 和 rendered snippet。这个设计让检索结果不是抽象标签，而是能直接被 agent 消费的执行材料。

边分四类：

Dependency：当 $v_{i}$ 的 output type 与 $v_{j}$ 的 input type 兼容时，加入 $v_{i} \to v_{j}$ ；这是最重要的 executable prerequisite 边。
Workflow：连接常见多步流程中的相邻 skill。
Semantic：连接近义、主题相近或可互补的 skill。
Alternative：连接解决同一子问题的可替代策略。

论文避免全量 all-pairs LLM 判断。实际做法是先用 lexical similarity、semantic neighbors 和 I/O expansion 构造小候选池，再只在候选池内做 sparse validation。这一点很重要：图不是“把相似文档连起来”的普通知识图谱，而是尽量围绕可执行关系构造。

3.4 Online structural retrieval：hybrid seeding → reverse-aware PPR → hydration

在线检索先把原始 query 映射为 retrieval schema，包含 task goal、salient operations、referenced artifacts 和 normalized keywords。之后对每个候选 skill 计算 semantic seed score 与 lexical seed score，并线性融合： $z_{i} (q) = η s_{i}^{sem} (q) + (1 - η) s_{i}^{lex} (q), p_{i} = \frac{z _{i} ( q )}{\sum _{j} z _{j} ( q )} .$ 扩散阶段对每类关系 $r$ 构造 forward operator $T_{r}^{\to}$ 与 reverse operator $T_{r}^{\leftarrow}$ ，再合成统一转移矩阵： $T = RowNorm (\sum_{r \in R} λ_{r} (T_{r}^{\to} + γ_{r} T_{r}^{\leftarrow})) .$ 然后执行 Personalized PageRank： $s^{(ℓ + 1)} = α p + (1 - α) T^{⊤} s^{(ℓ)} .$ 最后只靠扩散分数还不够，因为 agent 看到的必须是紧凑且直接可用的 skill payload。GoS 用 field-level query evidence 做 rerank： $ρ_{i} (q) = s_{i}^{⋆} + μ m_{i} (q),$ 其中 $m_{i} (q)$ 汇总 query 与 skill name、capability summary、artifacts、entrypoints 等字段的直接匹配。候选按 $ρ_{i}$ 排序后，在 per-skill 与 global context budget 下 hydration，生成包含 source path、能力说明和执行 notes 的 bundle。

3.5 Implementation pseudocode (基于 released code)

def build_skill_graph(skill_files, engine):
    nodes = []
    for skill_file in skill_files:
        parsed = parse_skill_document(skill_file.read_text(), source_path=str(skill_file))
        if parsed is not None:
            nodes.append(SkillNode.from_lists(**parsed.to_node_fields()))
 
    edge_map = {}
    for node in nodes:
        candidates = engine._rank_link_candidates_for_node(node, nodes)
        for candidate in candidates:
            for edge in engine._dependency_edges_for_pair(node, candidate):
                engine._record_edge(edge_map, edge)
        for edge in engine._validate_candidate_relations(node, candidates):
            engine._record_edge(edge_map, edge)
    return nodes, list(edge_map.values())

def retrieve_skill_bundle(query, engine, budget):
    nodes = engine._load_all_nodes()
    edges = engine._load_all_edges()
    schema = engine._fallback_query_schema(query)  # released eval disables optional rewrite
 
    lexical = engine._lexical_seed_scores(query, nodes, budget.seed_candidate_top_k_lexical)
    semantic = engine._semantic_seed_scores(query, nodes, budget.seed_candidate_top_k_semantic, schema)
    seed_weights = merge_and_normalize(semantic, lexical)
 
    transition, name_to_index = build_transition_matrix(
        nodes,
        edges,
        reverse_weights={"dependency": 1.0, "workflow": 0.7, "semantic": 0.3, "alternative": 0.2},
    )
    personalization = build_personalization(nodes, seed_weights, name_to_index)
    graph_scores = personalized_pagerank(transition, personalization, damping=budget.ppr_damping)
 
    ranked = rerank_with_field_evidence(nodes, graph_scores, schema)
    return engine._fit_skills_to_context_budget(ranked, budget.max_chars_per_skill, budget.max_context_chars)

Code reference: main @ 69f2ab2f (2026-05-04) — pseudocode and mapping based on this commit

Paper Concept	Source File	Key Class/Function
Skill package parsing / normalization	`gos/core/parsing.py`	`parse_skill_document`, `ParsedSkillDocument`
Skill / edge / query schema	`gos/core/schema.py`	`SkillNode`, `SkillEdge`, `QuerySchema`, `RetrievalBudget`
Graph construction and relation induction	`gos/core/engine.py`	`SkillGraphRAG._dependency_edges_for_pair`, `_validate_candidate_relations`, `_link_all_skills`
Hybrid lexical / semantic seeds	`gos/core/engine.py`	`_lexical_seed_scores`, `_semantic_seed_scores`, `_fallback_query_schema`
Reverse-aware graph diffusion	`gos/core/retrieval.py`	`build_transition_matrix`, `build_personalization`, `personalized_pagerank`
Rerank and context-budgeted hydration	`gos/core/engine.py`	`_rerank_skill_score`, `_fit_skills_to_context_budget`, `async_hydrate_skills`, `async_retrieve`
CLI / MCP interfaces	`gos/interfaces/cli.py`, `gos/interfaces/mcp.py`, `gos/interfaces/claude_code.py`	`retrieve`, `search_skills`, `retrieve_skill_bundle`, `hydrate_skills`
Benchmarks	`evaluation/skillsbench/`, `evaluation/alfworld_run.py`	`graphskills_benchmark.py`, ALFWorld driver and `SkillModule` adapter

论文公式与 released code 实现差异：论文把 online retrieval 描述为可选 LLM query rewrite + semantic/lexical hybrid seeding；实验说明禁用了 optional query-rewrite module，released benchmark 路径强调 raw task instruction / deterministic schema，因此笔记中的实验解释按“无 query rewrite”理解。

4. Experimental Setup (实验设置)

Datasets / benchmarks. 论文使用两个完整 benchmark：SkillsBench 包含 11 个真实技术任务域，覆盖宏观经济去趋势、power-grid feasibility、3D scan analysis、financial modeling、seismic phase picking 等；ALFWorld 使用 full 140-episode split，在 text-only 环境中测试多步 household activity 的顺序决策能力。

Baselines. 三种方法对比：Vanilla Skills 把完整 skill library 直接暴露给 agent，最大化 recall 但没有检索压缩；Vector Skills 使用与 GoS 相同的 openai/text-embedding-3-large（3072 维）做 bounded semantic retrieval，用来隔离“有检索压缩”与“有图结构”的差异；GoS 使用相同 base embedding，但把 nearest-neighbor retrieval 替换为 dependency-aware graph retrieval。

Models. 主实验覆盖 Claude Sonnet 4.5、MiniMax M2.7、GPT-5.2 Codex。每个 model-method setting 跑两次并报告均值。评价指标是平均 reward / success（ $R ↑$ ）、平均 input tokens（ $T ↓$ ）和 agent-only runtime 秒数（ $S ↓$ ）。

Protocol / config. 主实验与 sensitivity 实验使用相同 retry policy：环境构造失败会最多 rebuild/rerun 两次；仍失败的任务作为 unresolved infrastructure failures 排除；agent 已经实质执行后 timeout 计 reward 0，启动前 timeout 则重跑。Sensitivity study 在 full SkillsBench + GPT-5.2 Codex 下把 library size 从 200、500、1,000 扩到 2,000 skills。

5. Experimental Results (实验结果)

5.1 Main results：GoS 在六个 model-benchmark block 中 reward 最高

主结果的整体结论很清楚：GoS 在所有六个 model-benchmark block 中都取得最高 reward；相对 Vanilla Skills，GoS 在全部六个 block 都减少 input tokens，并在五个 block 降低 runtime；相对 Vector Skills，GoS 在同样压缩的 token regime 下提高 reward。摘要报告的总体均值是：GoS 相比 full skill-loading baseline 平均 reward 提升 43.6%，同时 input tokens 降低 37.8%。

SkillsBench 关键数值： Claude Sonnet 4.5 下 Vanilla / Vector / GoS 的 reward 为 25.0 / 19.3 / 31.0；MiniMax M2.7 为 17.2 / 10.4 / 18.7；GPT-5.2 Codex 为 27.4 / 21.5 / 34.4。Vector Skills 在 SkillsBench 上经常低于 Vanilla，说明长程技术任务只取语义近邻会漏掉 prerequisites；GoS 同时保持压缩和结构补全。

ALFWorld 关键数值： Claude Sonnet 4.5 下 GoS 达到 97.9% success，而 Vector 为 93.6%、Vanilla 为 89.3%，同时 token 从 Vanilla 的 1,524,401 降到 27,215。MiniMax M2.7 下 GoS 54.3%，高于 Vanilla 47.1% 和 Vector 50.7%。GPT-5.2 Codex 下 GoS 93.6%，高于 Vanilla 89.3% 和 Vector 92.9%。

5.2 Library-size sensitivity：规模越大，flat exposure 越吃亏

Figure 3 解读：当 SkillsBench library 从 200 增加到 2,000 skills 时，Vanilla Skills 的 input tokens 从 1.85M / 1.93M / 3.19M 增到 5.84M，而 GoS 基本维持在 1.14M–1.38M。reward 上，GoS 在 500、1,000、2,000 skills 时分别为 31.4、34.4、31.3，均高于 Vanilla 的 26.0、27.4、26.7 和 Vector 的 20.7、21.5、23.8。200 skills 时 Vanilla 32.5 略高于 GoS 32.1，说明小库里全量暴露还可以工作；但库变大后，结构检索的优势明显。

5.3 Ablation：seed 质量和图传播都重要

Method	R ↑	T ↓	S ↓
Full GoS	34.4	1.38M	715.6
w/o graph propagation	29.3	0.89M	766.2
w/o lexical + rerank	26.7	1.01M	747.7

去掉 graph propagation 后，reward 从 34.4 降到 29.3，说明仅靠 seed skill 不足以恢复完整执行链；去掉 lexical retrieval + rerank 后，reward 进一步降到 26.7，说明入口点质量比“后面再图扩散”更基础：如果 seed 本身不对，图上能扩出来的 prerequisite neighborhood 也会偏。

5.4 Limitations / caveats

论文没有把 GoS 说成免费提升：它需要离线解析和建图，边质量依赖 skill 文档里的 I/O、entrypoint、compatibility 等字段是否足够清楚；如果 skill package 元数据很弱，仍需要轻量 LLM pass 或 sparse validation 补语义字段。另一个 caveat 是检索 step 本身有 overhead，尤其 GPT-5.2 Codex 的 agent-only runtime 在某些 retrieval setting 下不一定比 Vanilla 更低；不过论文认为主瓶颈仍是大规模 flat library 暴露导致的 prompt cost，而不是 graph traversal 或 vector search 本身。

Paper Notes

探索

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

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

1. Motivation (研究动机)

2. Idea (核心思想)

3. Method (方法)

3.1 Overall framework：离线建图 + 在线结构检索

3.2 Problem setup：预算约束下的 dependency-complete bundle

3.3 Offline graph construction：节点标准化与四类边

3.4 Online structural retrieval：hybrid seeding → reverse-aware PPR → hydration

3.5 Implementation pseudocode (基于 released code)

4. Experimental Setup (实验设置)

5. Experimental Results (实验结果)

5.1 Main results：GoS 在六个 model-benchmark block 中 reward 最高

5.2 Library-size sensitivity：规模越大，flat exposure 越吃亏

5.3 Ablation：seed 质量和图传播都重要

5.4 Limitations / caveats

目录