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

LLM agents can solve complex tasks using reusable Agent Skills, aSKILL.md file with scripts and references, but only if they can find the right ones. Skill retrieval is challenging because task instructions state goals while skills describe tools: an instruction asks the agent to accomplish something, and the key skill that accomplishes it is typically named nowhere in the request or has a completely different naming convention. Recent work proposes closing this gap with a dependency graph over the skill library. We test this idea at the scale of a real registry, building two graphs over the same 27,210 skills, askill dependency graph with typed skill–skill edges, and aconcept-enriched graph in which skills connect only indirectly through shared LLM-extracted concept, tool, and input/output nodes. The approaches are evaluated on SkillsBench (87 agent tasks, 230 required-skill labels). Neither graph substantially improves on a well-tuned hybrid retriever (dense embeddings fused with BM25). The dependency graph’s small gains (+0.057 Recall@10 over the baseline) come almost entirely from re-ranking skills the retriever already found, not from discovering new ones. One cause is built into its construction: candidate edges are proposed by nearest-neighbor search in the same embedding space the retriever uses, so the graph inherits the retriever’s blind spots. The concept-enriched graph, designed to avoid exactly this circularity, fails the same way. Both graphs infer their edges from skill text, and neither can distinguish skills that are used together from skills that merely look alike. An audit of the best pipeline’s remaining misses shows that most are loose labels rather than genuine retrieval failures. The largest real improvement comes from the text side: an LLM listwise reranker using only skill names and one-line descriptions raises Recall@10 from 0.612 to 0.767. Two narrower roles remain for the graph: placing the correct skill first without a query-time LLM call, and recovering prerequisite skills the instruction never explicitly mentions. All of our evidence comes from the retrieval stage, with no agent run on the skills we retrieved.