Graph-of-Skills：面向大规模 Agent 技能依赖感知的结构化检索 Graph of Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills
图结构+反向扩散，让 Agent 检索到可执行的最小技能包。
前置知识
LLM Agent 与可复用技能（Skill）
LLM Agent 通过调用外部工具、API 或技能包完成任务。技能（Skill）通常以结构化包形式存在，包含 SKILL.md 说明、脚本入口、I/O 字段、依赖与示例任务等元信息。随着个人应用、Web 浏览器接口被封装成技能，单个 Agent 可访问的技能数量已从几十增长到数千甚至上万。
本文正是围绕“技能库从几十扩展到几千”这一规模跃迁提出的问题，必须先理解“技能≠单条 API”，它是一份可被解析、可被检索、可被执行的完整包，才能体会 GoS 对节点/边的设计。
向量检索（Vector Retrieval）与 HNSW 索引
向量检索把查询与文档都映射到稠密向量空间，通过余弦相似度找出 top-k 邻居；常用 ANN 索引如 HNSW（Hierarchical Navigable Small World）能在百万级向量上做毫秒级近邻搜索。语义相似但执行上不一定充分，是其固有局限。
GoS 与 Vector Skills 基线共享同一嵌入模型（openai/text-embedding-3-large, 3072 维），并共用 HNSW 索引作为语义种子来源。读懂向量检索是看懂“语义命中不等于执行充分”这一核心论点的前提。
BM25 与词法检索（Lexical Retrieval）
BM25 是基于词频与文档长度归一化的概率相关性框架，对具体文件名、API 名等"硬词"鲁棒，但对同义改写几乎无效。GoS 用 $\eta$ 把词法打分与语义打分融合为 $z_i = \eta s_\text{semi} + (1-\eta)s_\text{lex}$。
去除词法+重排序后 GoS 在 SkillsBench 上 reward 从 34.4 跌到 26.7（↓7.7），是消融里掉得最多的组件，说明“词法种子质量”对依赖恢复至关重要。
Personalized PageRank (PPR)
PPR 是 PageRank 的个性化版本：从种子节点集合 $p$ 出发，以 $\alpha$ 概率"传送回"种子、以 $(1-\alpha)$ 概率沿边游走，得到每个节点相对种子集的稳态相关性分数。GoS 用反向感知版本让相关性从匹配上的高层技能沿依赖边扩散到上游前提技能。
PPR 是 GoS 把“命中节点”扩展为“可执行包”的核心算法，没有反向传播就只能拿到 top-k 相似，无法补齐缺失的解析器/转换器/预设工具。
Reverse-aware Typed Diffusion（反向感知类型化扩散）
GoS 在 PPR 上做两点扩展：(1) 边带类型与独立反向权重 $\gamma_r$；(2) 统一转移算子 $T=\sum_r \lambda_r(T_r^\to+\gamma_r T_r^\leftarrow)$，让相关性既正向沿 workflow 走、也反向沿依赖边回溯前提。
这是 GoS 与 GraphRAG/ToolNet 等“无向相似图+普通 PPR”工作的本质差异——类型化的反向传播使检索方向与“前提→目标”的执行方向对齐，而非简单的相似度平滑。
研究动机
随着个人应用、Web 浏览器接口被打包为技能，单个 Agent 可访问的技能库规模从几十跃迁到几千。两种主流策略都有硬伤：(1) Vanilla Skills 把全量技能直接拼到 prompt 前，技能数从 200 涨到 2000 时输入 token 从 1.85M 暴增到 5.84M（约 3×），模型在超长上下文里既难定位关键约束（lost-in-the-middle），又因 token 成本和幻觉累积而延迟上升；(2) Vector Skills 用稠密检索取 top-k 语义相似技能，看似解决成本，但长链路任务上命中率堪忧——SkillsBench 上 Claude 从 25.0 跌到 19.3、M2.7 从 17.2 跌到 10.4、GPT-5.2 从 27.4 跌到 21.5。症结是"语义相似≠执行充分"：高层求解器需要配合解析器、转换器、预处理等上游技能，这些技能词面与 query 弱相关，vector 几乎召回不了，留下"前提鸿沟"，让 agent 只能靠 from-scratch 兜底。
本文的目标是本文的目标是设计一个推理时的结构化检索层 Graph-of-Skills（GoS），在严格的 context 预算 $\tau$（per-skill 2400 字符、global 12000 字符）下，返回一个“语义相关 + 依赖完整 + 体量紧凑”的技能包 $B(q)$。形式化目标为 $\max_B \sum_{v\in B} \text{rel}(v,q) + \beta \sum_{(u,v)\in E_\text{dep}} \mathbb{1}[u\in B \wedge v\in B]$，subject to $\text{cost}(B) \le \tau$，即在相关性与依赖完整性之间取加权最优。在 SkillsBench 1000-skill 配置下用 GPT-5.2 Codex 评测，作者要求相对 Vanilla Skills 实现 reward +25.55%、token 减少 56.72%；同时在 200–2000 skill 区间所有规模上都保持对 Vector Skills 的稳定优势。
与已有工作不同的是，现有图检索工作（GraphRAG 偏文档摘要、ToolNet 偏工具规划导航、ControlLLM 偏控制图、HippoRAG 偏长期记忆）要么目标不是“恢复一个可执行子集”、要么不是面向“本地大规模技能库”的检索前层。本文抓住的盲点是：(a) 现有工具图把工具当成扁平列表，不编码 I/O 类型化依赖；(b) 检索方向往往是“从 query 出发沿相似度扩散”，而非“从匹配节点反向回溯前提”；(c) 没有把“前提完整性”显式写进检索目标函数。GoS 的切入点是：构建一个 typed directed skill graph，依赖边由 I/O schema 匹配自动产生，工作流/语义/替代边由稀疏 LLM 验证补充，再用反向感知 PPR 在混合语义-词法种子上做扩散，从根本上把“前提恢复”建模为图上的结构化扩散而非 flat 检索。
核心方法
GoS 是"离线建图 + 在线结构化检索"的两阶段流水线。离线阶段：解析每个 skill 包里的 SKILL.md，规范化节点字段（name/inputs/outputs/domain_tags/tooling/entrypoints/source_path），LLM 只做节点级语义补全；对节点两两做 I/O overlap 检查，>ζ=0.6 自动加 dependency 边 u→v；再用 lexical+semantic+I/O 三候选池组成 top-k=8，由 LLM 在 {dep, wf, sem, alt} 四类关系中验证并写入边，得到 typed directed graph。在线阶段：query 映射成轻量 schema，dense+lexical 召回前 20+20 候选，按 z_i=η s_semi+(1-η)s_lex 融合为种子分布 p，用反向感知 PPR 迭代 s^(ℓ+1)=αp+(1-α)T^⊤s^(ℓ)，最后按 ρ_i=s_i*+μ m_i 重排后在 per-skill 2400 + global 12000 字符预算下 hydrate 出可消费技能包。
GoS 的核心创新在于把“前提恢复”建模为反向类型化图扩散（reverse-aware typed diffusion）而非 top-k 相似检索，本质区别有三点：(1) 依赖边由 I/O schema 兼容性自动产生，不是相似度近似，从而保留“u 可产出 v 消费的产物”这一可执行语义；(2) 转移算子对每类边独立配置反向权重 $\gamma_r$（dependency=1.0、workflow=0.5、semantic=0.2、alternative=0.1），让相关性既可正向沿 workflow 推进也可反向沿依赖边回溯，从匹配上的高层求解器回到上游解析器/转换器；(3) 检索目标函数同时最大化相关性与依赖完整性 $\max_B \sum_v \text{rel}(v,q) + \beta \sum_{(u,v)\in E_\text{dep}} \mathbb{1}[u,v\in B]$，并用 budgeted hydration 在有限上下文里把“紧凑+可执行”作为硬约束。这三点合起来，使得 GoS 返回的不是一份“语义邻居列表”，而是一份“接近任务可执行分解”的技能包。
方法步骤详情
流程分两阶段共 8 步。离线 4 步：(1) 解析 SKILL.md 提取节点字段，对缺失语义字段调 LLM 做节点级补全且强制 edges=[]；(2) 对有序对 (u,v) 计算 outputs(u) 与 inputs(v) 的 schema overlap，>ζ=0.6 则加 dependency 边 u→v；(3) 对每节点 v 构造候选池（lexical+semantic+I/O），取 top-k=8 送 LLM 验证器，把通过的 wf/sem/alt 边写入 E；(4) 建 HNSW 向量索引并持久化。在线 4 步：(5) 取 semantic top-20 + lexical top-20，按 z_i=η s_semi+(1-η)s_lex 归一为种子分布 p；(6) 按 T=RowNorm Σ_r λ_r(T_r^→+γ_r T_r^←) 构造反向类型化转移算子，迭代 PPR 至收敛（α=0.2，最大 50 步）；(7) 用 ρ_i=s_i*+μ m_i 重排取 top-N=8；(8) 按 ρ_i 降序 hydrate 在双重预算下截断。
技术新颖性
相对 GraphRAG/HippoRAG/ToolNet/ControlLLM 这一谱系，GoS 的新颖性有四点：(1) 显式把“前提完整性”作为检索目标函数的第二项并用 budgeted hydration 落到工程层面，而非仅做“文档摘要”或“长期记忆联想”；(2) 把依赖边与 I/O 类型对齐、且只让 dependency 边获得最大反向权重，使图的方向与“前提→目标”的执行方向对齐，避免把图退化成无向相似图；(3) 稀疏 LLM 验证（k=8/node）把构造复杂度从 $O(N^2)$ 降到 $O(|V_\text{new}|N)$，增量建图也可控；(4) 引入 hybrid semantic-lexical seeding 并消融证明：去掉词法+重排序后 reward 从 34.4→26.7（↓7.7）比去掉图传播的 34.4→29.3（↓5.1）掉得更多，说明“种子质量”比“扩散步骤”更关键——这一发现对后续 graph-RAG 系统的设计顺序有直接借鉴意义。
实验结果
6 个 model×benchmark block 上 GoS 都拿最高平均 reward。SkillsBench：Claude GoS 31.0% vs Vanilla 25.0%/Vector 19.3%；M2.7 GoS 18.7% vs 17.2%/10.4%；GPT-5.2 GoS 34.4% vs 27.4%/21.5%，相对 Vector 平均 +10.97 分。ALFWorld：Claude GoS 97.9% vs 89.3%/93.6%；M2.7 GoS 54.3% vs 47.1%/50.7%；GPT-5.2 GoS 93.6% vs 89.3%/92.9%，平均 +2.87 分。Token：ALFWorld Claude GoS 仅 27,215（Vanilla 1,524,401，-98.2%）；SkillsBench GPT-5.2 GoS 1,379,773。库大小（GPT-5.2）500/1000/2000 技能下 GoS 31.4/34.4/31.3 始终领先。消融：完整 34.4，去图传播 29.3，去词法+重排 26.7。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| SkillsBench 1000-skill, Claude Sonnet 4.5 | 平均 reward (%) / 总 tokens | GoS 31.0% / 860,315 tokens | Vanilla 25.0% / 967,791；Vector 19.3% / 894,640 | 相对 Vanilla +6.0 分 reward 且 -11.1% tokens；相对 Vector +11.7 分 reward |
| SkillsBench 1000-skill, MiniMax M2.7 | 平均 reward (%) / 总 tokens | GoS 18.7% / 867,452 | Vanilla 17.2% / 942,113；Vector 10.4% / 852,881 | 相对 Vanilla +1.5 分 reward 且 -7.9% tokens；相对 Vector +8.3 分 reward |
| SkillsBench 1000-skill, GPT-5.2 Codex（主指标） | 平均 reward (%) / 总 tokens | GoS 34.4% / 1,379,773 | Vanilla 27.4% / 3,187,749；Vector 21.5% / 1,243,648 | 相对 Vanilla reward +25.55%、tokens -56.72%；相对 Vector reward +12.9 分 |
| ALFWorld 140 episodes, Claude Sonnet 4.5 | 成功率 = 平均 reward (%) / 总 tokens | GoS 97.9% / 27,215 | Vanilla 89.3% / 1,524,401；Vector 93.6% / 28,407 | 相对 Vanilla +8.6 分且 -98.2% tokens；相对 Vector +4.3 分 |
| ALFWorld 140 episodes, MiniMax M2.7 | 成功率 / 总 tokens | GoS 54.3% / 65,227 | Vanilla 47.1% / 2,184,823；Vector 50.7% / 66,109 | 相对 Vanilla +7.2 分且 -97.0% tokens；相对 Vector +3.6 分 |
| ALFWorld 140 episodes, GPT-5.2 Codex | 成功率 / 总 tokens | GoS 93.6% / 46,462 | Vanilla 89.3% / 1,435,614；Vector 92.9% / 34,436 | 相对 Vanilla +4.3 分且 -96.8% tokens；与 Vector 接近但 token 略多 |
| SkillsBench 库大小敏感性 (GPT-5.2 Codex, 500/1000/2000) | 平均 reward (%) | 31.4 / 34.4 / 31.3 | Vanilla 26.0 / 27.4 / 26.7；Vector 20.7 / 21.5 / 23.8 | 在 500–2000 区间相对 Vanilla +4.6 至 +7.0 分、相对 Vector +7.5 至 +12.9 分 |
| GoS 组件消融 (SkillsBench 1000-skill, GPT-5.2 Codex) | 平均 reward (%) | 完整 GoS 34.4 | 去掉图传播 29.3；去掉词法+重排 26.7 | 图传播贡献 +5.1 分；词法+重排贡献 +7.7 分（更关键） |
局限与改进
作者承认三点：(1) Graph construction quality——依赖离线 skill 图质量，文档不全或 I/O schema 歧义会让边质量退化（如 earthquake-phase-association 案例 GoS 召回 bundle 不完整导致任务失败）；(2) Static graph——图离线构建不从下游执行轨迹或用户反馈更新，错的依赖或漏掉的关系无法自纠；(3) Evaluation scope——只在 SkillsBench 与 ALFWorld 和三种模型上评估，未覆盖多模态 embodied agent、Web 浏览 agent。我的观察：(a) adaptive-cruise-control 三种方法都召回相关技能却全部 reward 0.0，说明检索已非瓶颈、执行链对齐是独立问题；(b) GoS 在 ALFWorld 的 token 优势（97–98% 缩减）部分来自任务结构而非算法；(c) Vector Skills 在 2000-skill 下反超 Vanilla（23.8 vs 26.7 差距缩小）。
独立分析的弱点
我的独立观察：(1) 静态图缺乏在线纠错：当某条 dependency 边诱导错误，GoS 无法回传信号，建议引入 execution-trace 级 implicit feedback；(2) 词法重排成为最关键组件的副作用是 brittle：去除词法+重排掉得最多（-7.7）说明种子质量仍依赖具体词命中，对 query 改写敏感，建议加入 query-side synonym normalization 或 sub-token BM25 变种；(3) per-skill 2400/global 12000 字符是硬截断，长 skill 包可能丢失关键字段，建议改用 budgeted selection——把字符预算纳入 ILP 目标联合选 skill 子集与每 skill 截断比例；(4) GoS 在 200-skill 库上反而比 Vanilla 低 0.4 分（32.1 vs 32.5），应引入库大小自适应切换，库<300 时直接走 Vanilla；(5) 缺乏 noise edge 鲁棒性测试，建议用 synthetic noise injection 量化。
未来方向
作者提出扩展到多模态 embodied 与 web 浏览 agent。基于结果可延伸：(a) Online graph update——用对比学习微调边权重 γ_r；(b) Coupling with skill synthesis——可与 SkillNet 按需合成互补，graph retrieval 找不到合适技能时触发 skill creation；(c) Cross-corpus skill migration——把图结构迁移到 ALFWorld/custom 库，研究 typed graph 可移植性；(d) Personalized budget——不同任务设不同字符上限；(e) 用 G-Retriever 等现代 graph retriever 替换 PPR，结合 attention-based 反向传播；(f) 与 ToolLLM、Gorilla 等 API 检索 benchmark 对齐；(g) 把执行完整性作为可验证指标，要求 bundle 包含 verifier 所需全部 domain tags。
复现评估
复现友好度较高。代码已在 GitHub 开源（github.com/davidliuk/graph-of-skills），核心超参与实现细节全部公开：(a) Table 4 列出实现选择；(b) Table 6 给出 4 类边权重（dependency 1.0/1.0、workflow 0.7/0.5、semantic 0.4/0.2、alternative 0.3/0.1）；(c) Table 7 列出全部默认超参（PPR α=0.2、最大 50 步、ζ=0.6、k=8、seed pool 20、top-N=8、per-skill 2400、global 12000）；(d) 两 benchmark 公开可下载。算力需求低——GoS 无需训练，仅依赖一个外部 embedding API + 稀疏 LLM 调用做离线建图；在线检索常数时间 PPR 迭代，硬件门槛接近笔记本。复现难点：(1) 离线建图依赖 SKILL.md 格式；(2) 换模型需重调 reranker 阈值；(3) Vector 与 GoS 共用向量索引，公平比较关键是 embedding 模型一致。
论文图表
三栏对照：Vanilla Skills 把全量库拼到 context、Vector Skills 用 top-k 语义相似但漏掉前提、GoS 用 hybrid seeds + graph diffusion 恢复出可执行 bundle，箭头展示 T1–T12 节点在不同方法下进入 system context 的差异。
这是论文最核心的概念图，把“前提鸿沟”（prerequisite gap）这一关键论点可视化，对快速理解 GoS 解决什么问题至关重要。