Comparative Approaches to Agent Retrieval over Large Skill Libraries

The paper addresses the problem of skill selection for AI agents backed by large skill libraries: which skills to load, and in what order. The authors study a corpus of 690 skills across five departments, where each skill is a SKILL.md file with a name and one-line description. The naive approach of loading everything costs ∼46.9k tokens per task, paid on every invocation regardless of need.

Two access routes define the setting: a pull route where an agent issues a query and receives a ranked list of candidates (served by the ranker, and the route evaluated in the paper), and a push route with per-turn advisory injection (not evaluated). Critically, neither route answers given the skill I am now using, what comes next? — the gap the knowledge graph was designed to fill.

1. Typed Knowledge Graph. The graph has three edge layers: curated edges (hand-authored or LLM-generated; both empty in the current corpus except LLM), derived edges (from related metadata; empty), and an inferred similar to backbone of embedding nearest neighbours (1626 pairs). The curated layer has eight typed relations: requires, specializes, feeds into, routes to, precedes, complements, alternative to, and verifies, each carrying a traversal priority. Four types must stay acyclic. Generation is coarse-to-fine: for each skill, take top-K=8 embedding neighbours (coarse step), then make one LLM call (claude-haiku-4-5) under forced tool use to emit typed edges (fine step). The full backfill produced 1421 typed edges with zero failed API calls in ∼15.5 minutes, at a cost of ∼ 2.70; incremental cost is ∼ 0.005 per edited skill. A precision audit of 48 edges (six per type) found loose precision (Correct+Plausible) of 41/48 (∼85%) and strict 29/48 (60%), with direction-based types (precedes, verifies, routes to) falling to 67–83%, while direction-independent types (requires, specializes, complements) were 100% correct-or-plausible. Validation dropped 113 hallucinated cyclic edges.

2. Hybrid Ranker. Scores catalogue entries on name + description alone (full bodies are not indexed; a sibling effort found body indexing degrades retrieval under this short-context encoder). Three rankers: keyword (BM25), semantic (all-MiniLM-L6-v2, 384-dim, mean-pooled, L2-normalised), and a hybrid fusion that is the production default. Sparse on-demand retrieval costs ∼560 tokens per task versus 46,915 for load-all — a 98.8% reduction. Graph traversal costs ∼330 tokens, so the saving comes from loading less rather than from loading smarter.

On the primary evaluation set of 117 task-to-skill cases across roughly 15 domains with k=5, designed so queries deliberately do not echo target skill descriptions, the hybrid ranker achieves hit@5 of 73.5% (62.8% when the user describes a symptom rather than naming the skill). Retrieval is therefore not solved: roughly 31 of 117 queries are still yet to be answered.

Five converging measurements show the graph does not improve retrieval:

1. Substitution at matched budget is significantly worse: At budget 6, hybrid@1+graph(6) scores 0.632 versus hybrid@6 at 0.744 — a deficit of 11.2 points (McNemar p = 0.0007). The graph is significantly worse at matched budget on this corpus. Hybrid@10 reaches 0.803; graph alone (no ranker) scores 0.009 (≈chance).

2. The LLM edge layer adds nothing over free neighbours: similar to alone (free local kNN) scores 0.632; typed edges alone (the 1421 LLM-generated edges) score 0.607; both layers together score 0.632. The entire LLM edge-generation step contributes zero measurable retrieval value over neighbours obtained free from a local embedding pass.

3. 73% of missed queries are unreachable: Of 30 queries hybrid@6 misses, only 6 (20%) are reachable within 1 hop from hybrid's top-1 result, 2 (7%) at 3 hops, and 22 (73%) are unreachable within 3 hops. The headroom is structurally out of the graph's reach.

4. Search recovers twice as often when the entry guess is wrong: When hybrid's top-1 is wrong (n=58), retrieving more ranked results recovers 48.3% of cases while graph neighbours recover 25.9%.

5. Re-ranking is a null: Graph-boosted re-ranking gains a single query (+0.85 points; 6 gained, 5 lost; McNemar p ≈ 1.000; 95% interval −4.8 to +6.5 points), providing an upper bound on the effect excluding gains larger than 6.5 points.

The central mechanistic explanation: "When LLM edge generation draws candidates from an embedding's top-K neighbours, the resulting graph is confined to that embedding's topology. The LLM can enrich semantics by assigning a typed relation to a pair, but it cannot add reach, because it is never shown a pair the embedding did not already surface. Any method that pre-filters candidates by the same signal the ranker uses inherits this ceiling."

Measured directly: Of 1022 distinct typed pairs, 1008 (98.6%) are also similar to pairs; only 14 (1.4%) fall outside, attributable to seed/corpus drift. Adding all 1421 typed edges to the similar-to backbone leaves wired nodes at 594 (zero newly connected) and components at 112 (zero merged). The largest component is unchanged, and 3-hop mean reach rises 2.4%.

This bound holds specifically because both systems share the same embedding model: This shared embedding is not incidental: both systems rest on the same similarity signal, which is exactly why one bounds the other.

An earlier 37-query set written by the same author who built the system reports hit@5 of 0.946 for both keyword and hybrid, versus 0.504 and 0.735 on the non-echo set — a gap of 44.2 points for keyword and 21.1 points for hybrid. The mechanism is description echo: queries written while reading the corpus reuse description vocabulary, so an echoing query approximates a primary-key lookup. Crucially, on the author-written set the two rankers are level, and on the non-echo set they separate by more than 23 points — so a naive evaluation would have reported not merely inflated accuracy but a false equivalence between a lexical baseline and the production ranker.

At population scale, of 1022 distinct pairs, 298 (29.2%) carry more than one type, and 87 (8.5% of all pairs) are contradictory — including 20 carrying the same asymmetric type in both directions. Every contradiction category is a direction disagreement. The practical implication: shipping 'do X before Y' guidance at 8.5% reversed is worse than shipping nothing, because a wrong prerequisite actively misleads.

Three mechanisms: (1) Search is query-conditioned; the graph is not — search ranks against actual task text while graph adjacency is fixed at build time; (2) the topology bound confines the graph to a strict subset of the ranker's signal. A truncated view of a signal cannot beat the signal; (3) hybrid fusion already covers both failure modes the graph might have patched — BM25 covers lexical drift, the semantic channel covers paraphrase, which is why keyword sheds 44 points without echo but hybrid sheds only 21.

For ordering (what skill follows the current one), the graph could win: "The graph wins iff q > p, where p is search success probability and q is per-hop edge accuracy. Directional edge types run 0.67–0.83 accuracy, straddling the p=0.735 threshold, so the question cannot be settled without a skill-to-skill sequence dataset that does not yet exist. Also, enriching skill resolution with prerequisites/next-steps is an additive change with no adoption cost, provided the direction-error rate is first reduced."

Threats include: 117 queries (0.85pp per query); the non-echo set was built by a sibling effort; the precision audit is n=48, single-judge; no latency measured; no sufficiency testing; single-gold hit@5 penalises a graph that supplies a needed prerequisite but displaces the gold skill; and this is a single corpus, single organisation, single embedding model: no claim about other libraries, scales, or backends is supported.

Future work priorities: co-usage telemetry (an ordered skill-call log has shipped; observed co-usage is orthogonal to the embedding and is the one remaining candidate signal that is not embedding-confined); a sequence sufficiency experiment (needs runtime wiring and resolution of a known backfire effect); candidate generation beyond the embedding kNN — the only route that could give the graph reach the ranker lacks; disambiguation at scale; and body indexing under a long-context encoder.

SkillRouter studies retrieval over 80K skills, reporting bodies (not frontmatter) are the decisive signal, with 74.0% top-1 via two-stage retrieve-and-rerank. Graph-of-Skills builds a typed graph and retrieves dependency-aware bundles via PPR. The divergence: GoS derives edges from dependency structure in skill packages, not from the retriever's own embedding neighbourhood. Our generator does, and §5.3 shows the consequence.

Sparse ranked loading cuts context cost by roughly two orders of magnitude, a real and deployable gain. Retrieval is not solved — 73.5% hit@5 leaves roughly a quarter unfulfilled. The graph does not close the gap for a structural reason: 98.6% of the graph's edges connect skills the embedding layer had already connected, so the pre-filter that makes edge generation affordable also bounds the graph's topology. The contribution is a mechanistic account of why added structure does not improve retrieval over a strong ranker and identifying the conditions under which adding structural interdependence into the retrieval is optimal.

1. Replace load-all skill contexts with sparse hybrid retrieval.

Use BM25 + semantic embedding (e.g., all-MiniLM-L6-v2) over skill name and one-line description, and load only the top-k ranked skills into context.

Improved AI system can: cut context cost from 46.9k tokens per task to 560 tokens per task (98.8% reduction) while preserving 73.5% hit@5 on non-echo task queries.

2. Stop using LLM-generated typed knowledge graphs for retrieval ranking or re-ranking.

Because 98.6% of typed edges duplicate the embedding-neighbour backbone, graph-based re-ranking is a statistical null (McNemar p ≈ 1.000; upper bound +6.5 points).

Improved AI system can: avoid the cost and complexity of graph generation when the goal is retrieval, without losing accuracy.

3. If a typed graph is used, restrict it to next-step ordering, not candidate retrieval.

Use the graph only when per-hop edge accuracy q exceeds the search success probability p; directional edge types currently run 0.67–0.83, straddling p = 0.735.

Improved AI system can: decide adaptively whether graph traversal or ranked search is better for “what skill comes next,” and defer unsafe ordering decisions until q > p is measured.

4. Prune contradictory and direction-reversed graph edges before shipping.

The graph contains 8.5% contradictory pairs, including same-direction reversals, which actively mislead.

Improved AI system can: validate typed edges, drop cyclic and contradictory pairs, and only emit precedence/prerequisite guidance after direction-error rates are reduced toward zero.

5. Collect and exploit co-usage telemetry as the primary next-skill signal.

Co-occurrence and ordering of skill calls is orthogonal to the embedding signal and is the only identified candidate signal not confined by the embedding pre-filter.

Improved AI system can: learn skill-to-skill transitions from real ordered call logs, enabling sequence prediction that embedding-based graphs cannot provide.

6. Generate graph candidates from sources beyond the embedding kNN.

The topology bound occurs because LLM edge generation is fed only embedding neighbours. Use package dependency metadata, human curation, code co-occurrence, or full-catalog LLM scans to create edges the ranker cannot reach.

Improved AI system can: build a graph with genuinely new reach, breaking the ceiling where 98.6% of edges duplicate the embedding layer.

7. Use non-echo evaluation sets for any agent retrieval benchmark.

Author-written queries that echo skill descriptions inflate hit@5 by 21–44 points and can falsely equate lexical baselines with hybrid rankers.

Improved AI system can: benchmark on symptom-style, non-echo queries and report separate lexical/semantic/hybrid scores, avoiding overconfidence and false equivalence.

8. Index full skill bodies only under a long-context encoder.

Short-context encoders degrade retrieval when indexing full bodies; the paper’s gains come from name+description indexing.

Improved AI system can: use long-context encoders when body-level retrieval is needed, preserving or improving recall without the degradation seen in short-context settings.

9. Use differential diagnosis for missed queries.

Since 73% of missed queries are unreachable even within 3 graph hops, and ranked search recovers 48.3% of wrong-top-1 cases while graph neighbours recover only 25.9%, the system should expand ranked results rather than traverse the graph.

Improved AI system can: recover missed skills by retrieving more ranked results, not by following graph adjacency, and know when headroom is structurally out of graph reach.