Skill graphs - typed links between agent skills

A skill graph stores an agent's skills as nodes and the relations between them as typed edges: this skill needs that one, this one is a special case of that one, these 2 conflict. A flat skill library has no such links. It retrieves each skill on its own merit, usually by semantic search on its description.

The flat approach breaks in 3 ways as a library grows:

• The prerequisite gap. Search finds the skill that matches the task, but not the upstream skill it needs to run. The bundle looks right and fails on execution.
• Context saturation. Loading every skill costs tokens, latency and accuracy.
• Composition. Multi-step tasks need several skills in the right order, and similarity search returns a set, not an order.

The main use case in 2026 is large libraries of Agent Skills, the SKILL.md format Anthropic published as an open standard. The same idea exists in robotics, job-market taxonomies and hierarchical planning.

The 2026 research at a glance

The approaches

1. SKILL.md and progressive disclosure: the baseline

A skill is a folder with a SKILL.md: YAML front matter with name and description, then instructions, plus optional scripts/ and references/. At startup the agent loads only the name and description of every skill. It reads the full file, and the files it links to, only when a task needs it.

Portable, light, and the base for everything below. Any graph is implicit: a skill can say "run company-research first", but nothing checks it and retrieval doesn't know about it.

2. Graph-of-Skills: retrieve the prerequisites too

Graph-of-Skills (Liu et al.) builds the graph offline. Each node is a normalised skill package: name, capability summary, input and output schemas, tags. Edges are typed: dependency (from matching outputs to inputs), workflow, semantic and alternative. Rules propose most edges, and a sparse LLM pass validates them.

Retrieval at run time:

1. Seed with hybrid search: embeddings plus lexical (BM25) matching.
2. Spread with Personalized PageRank, weighted to walk dependency edges backwards, from the skill that matches to the skills it needs.
3. Hydrate a bundle within a fixed context budget.

Results, on SkillsBench and ALFWorld with Claude Sonnet 4.5, MiniMax M2.7 and GPT-5.2 Codex:

• Highest average reward in all 6 model and benchmark combinations.
• With GPT-5.2 Codex on SkillsBench: +7.0 reward points over loading the full library (+25.6% relative), with 56.7% fewer tokens.
• The direction matters most. Forward propagation instead of reverse costs 9.1 points, more than removing the graph altogether.

3. IBM's reality check at 27,210 skills

An IBM Research study (Lin et al., ISWC 2026) built 2 graphs over a real registry of 27,210 skills and tested them on SkillsBench (87 tasks).

• Neither graph beat a well-tuned hybrid retriever by much. The dependency graph added +0.057 Recall@10, almost all from re-ranking skills the retriever had already found.
• Why: the candidate edges came from nearest neighbours in the same embedding space as the retriever, so the graph inherits its blind spots. Edges inferred from text can't tell skills used together from skills that only look alike.
• The biggest gain came from the text side. An LLM reranker that reads only skill names and 1-line descriptions raised Recall@10 from 0.612 to 0.767.
• 2 roles remain for the graph: put the right skill first without an LLM call at query time, and recover prerequisites the instruction never names.
• The study measures retrieval only. No agent ran the retrieved skills.

GoS and IBM don't contradict each other. GoS wins on prerequisite recovery and tokens. IBM shows that at registry scale, a good retriever and good descriptions do most of the work.

4. SkillDAG: the agent reads and edits the graph

SkillDAG (Bai et al.) stops hiding the graph inside a retrieval pipeline. The agent gets it as tools:

Edge types: depends_on, specializes, composes_with, similar_to and conflicts_with. Every committed edit passes 3 checks: the backbone stays acyclic, no edge contradicts another, and an append-only log allows rollback. A cold start builds the first graph from 2 embedding views and LLM typing.

With MiniMax-M2.7, SkillDAG beat the strongest Graph-of-Skills result by 12.8 points on ALFWorld (54.3% to 67.1% success) and 8.6 points on SkillsBench. With GPT-5.2 Codex, the 2 tie at 93.6% on ALFWorld: a strong model gains less. The ranking held when the skill pool grew 10 times, which degraded the fixed pipeline.

5. SkillGraph: graph and policy trained together

SkillGraph (Li et al.) distils skills from successful and failed trajectories. Edges are weighted and typed: prerequisite, enhancement and co-occurrence.

• Retrieval: start from seed skills, expand backwards for prerequisites, expand forwards with beam search, then sort the subgraph into an execution order.
• Evolution: reinforcement learning feedback inserts, merges, splits and deprecates nodes, and reinforces, decays and prunes edges. Skills unlock progressively by level.
• Results: state of the art against memory-augmented RL methods on ALFWorld, WebShop and 7 search-augmented QA tasks, with the largest gains on tasks that compose several skills.

This one trains the model, so it's for teams with an RL loop, not for a prompt-level skill library. The name is also taken: a different arXiv paper (2604.17503) uses "SkillGraph" for multi-agent collaboration.

6. HiSkill: skills above executable actions

HiSkill (Hao et al.) builds a 2-level graph from interaction trajectories:

• Skill nodes: reusable high-level procedures.
• AtomicOp nodes: executable action templates.
• Typed edges: decomposition, temporal transition, compatibility, support and recovery.

At run time it retrieves a small task subgraph. A symbolic task state, the active skill and the subgraph then guide the agent to switch skills, pick an AtomicOp and ground it as an action, step by step. It beat the baselines on 3 interactive environments with fewer tokens.

7. Other kinds of skill graph

• Inside 1 skill: the Agent Instruction Protocol. AIP models a single skill as an execution graph: a Skill node, Step nodes with typed inputs and outputs, scripts or text behind each step, and depends_on, parallel and one_of annotations, in schema-validated YAML.
• Robotics. Executable skills linked by preconditions and effects, used for planning and for checking that each step did what it should.
• Jobs and competencies. Knowledge graphs that link skills, occupations and learning paths, such as the EU's ESCO taxonomy. Used for matching people to roles and planning career paths. Same name, different problem.

For business people

• What it solves: an AI agent with 100s or 1,000s of skills needs to find the right ones for each task, including the ones the task doesn't mention. A skill graph records which skills need, replace or clash with which others.
• What it changes: fewer failed runs from a missing step, and lower token costs, because the agent loads a small, complete bundle instead of everything.
• When it matters: above roughly 100 skills, or when skills chain into each other. Below that, clear skill descriptions and plain search do the job.
• Cost: a graph adds a build step and upkeep. Self-evolving graphs add more: rules, logs and rollback.
• The honest finding: at large scale, better descriptions and an AI reranker gave IBM more than a graph did. Fix the descriptions first.

For technical people

A typed edge list

The minimum useful graph is an edge list next to the skills. An example with 4 of my own skills:

# skill-edges.yaml
- {from: init-client,   to: company-research, type: depends_on}
- {from: deck,          to: brand,            type: depends_on}
- {from: exec-summary,  to: meeting-recap,    type: similar_to}
- {from: meeting-recap, to: call-notes,       type: similar_to}

depends_on drives retrieval: when init-client matches, load company-research too. similar_to drives disambiguation: when 2 near neighbours both match, ask, or pick by a rule. conflicts_with goes further: never load both.

Reverse traversal in 10 lines

import networkx as nx

G = nx.DiGraph()
for e in edges:  # loaded from skill-edges.yaml
    G.add_edge(e["from"], e["to"], type=e["type"])

def bundle(seeds: list[str], budget: int = 5) -> list[str]:
    """Seed skills plus their prerequisites, prerequisites first."""
    deps = nx.DiGraph([(u, v) for u, v, t in G.edges(data="type") if t == "depends_on"])
    needed = set(seeds) | {d for s in seeds if s in deps for d in nx.descendants(deps, s)}
    order = list(reversed(list(nx.topological_sort(deps.subgraph(needed)))))
    return (order + [s for s in seeds if s not in order])[:budget]

GoS does the same thing with Personalized PageRank and weights, which ranks the prerequisites instead of taking all of them.

What works, across the papers

• Start with the open SKILL.md format. Every approach above can sit on top of it.
• Seed with hybrid search, embeddings plus BM25. Neither semantic search nor the graph alone wins.
• Type the edges, and walk depends_on backwards. Forward-only spreading did worse than no graph in GoS.
• Budget the bundle, per skill and in total.
• Gate every automatic edit: acyclic backbone, no contradictions, an undo log.
• Write trigger-oriented descriptions. In the IBM study, the text did more than the graph.
• Measure both levels: retrieval (Recall@K, prerequisites recovered) and task success, at more than 1 library size.

Gotchas

• Edges from embeddings repeat the retriever's mistakes. Prefer edges from input and output schemas, explicit requires lines, or real execution logs.
• Gains shrink with stronger models. SkillDAG's lead over GoS vanished with GPT-5.2 Codex on ALFWorld.
• Benchmarks are small and synthetic. SkillsBench has 87 tasks, ALFWorld is a text household simulator.
• The graph needs upkeep. A renamed or retired skill leaves dangling edges unless something checks them.

What it means for my setup

My NicAI library has 73 live skills, see The NicAI skills catalogue. That's below the size where retrieval breaks, and Claude Code loads all the descriptions anyway. So I don't need a retrieval graph.

I do have the 2 problems a graph names explicitly:

• Hidden dependencies. init-client runs company-research, and the visual skills read brand and logo first. Those links live in prose inside each SKILL.md. Nothing checks them when I rename a skill.
• Overlap. meeting-recap, call-notes, exec-summary and se-brief all start from a transcript. Only the descriptions keep them apart. That's a similar_to cluster, and the IBM result says the fix is sharper descriptions.

The cheap step: 1 edge file like the one above, plus a lint that fails when an edge points at a skill that doesn't exist. That's the useful 20% of a skill graph, without the research machinery.

Further reading

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

Liu et al., arXiv 2604.05333, April 2026

https://arxiv.org/abs/2604.05333

What Skill Dependency Graphs Are Really Good For: An Empirical Study

IBM Research, ISWC 2026

https://research.ibm.com/publications/what-skill-dependency-graphs-are-really-good-for-an-empirical-study

davidliuk/graph-of-skills

GoS code and data, Python, MIT

https://github.com/davidliuk/graph-of-skills

Equipping agents for the real world with Agent Skills

Anthropic engineering post on SKILL.md and progressive disclosure

https://www.anthropic.com/engineering/equipping-agents-for-the-real-world-with-agent-skills

• Agent Skills specification, the open standard
• SkillDAG code and HiSkill code
• SkillsBench and ALFWorld, the 2 benchmarks most papers use
• The NicAI skills catalogue, my own skills catalogue
• SkillOpt, Microsoft's method for training the text of a skill