Comparative Approaches to Agent Retrieval over Large Skill Libraries
Indivara Kolluru, Nathan Sportsman
cs.AI
2026-08-06
Over 690 skills, adding an LLM-built knowledge graph to retrieval scores -11.2 points; 98.6% of its edges duplicate embedding neighbors, so it can't extend reach.
An agent backed by a large skill library has to decide which skills to load and in what order on every task. The lazy option is to dump all 690 skills into context, but that costs roughly 46.9k tokens a task and leaves a pile of unstructured entries the agent cannot sequence on its own. Two fixes are common: a retriever that pulls the few most relevant skills on demand, or a knowledge graph that encodes relations like "run A before B" and "A's output feeds B".
The paper asks a direct question: how much does stacking the graph on top of retrieval actually help over retrieval alone? And, more fundamentally, where do the graph's edges come from, and does that source doom the graph from the start?
Two systems are compared over the same 690-skill corpus.
The retrieval side is a hybrid ranker fusing BM25 keyword scores with all-MiniLM-L6-v2 dense-vector similarity (384 dims). BM25 is sharp on exact identifiers and rare tokens and doubles as an off-topic gate; the dense side handles paraphrase. The fused version is the production default.
The graph side is a typed knowledge graph with three edge layers: curated, derived from metadata, and LLM-inferred. The LLM layer uses claude-haiku-4-5 under forced tool use: take each skill's top-8 embedding neighbors as candidates, then label an edge with one of eight relations (requires, feedsinto, precedes, and so on). Building the full 690-skill graph yields 1,421 edges for about $2.70 in 15.5 minutes.
The decisive design choice is the matched-token-budget control. The graph is not added for free; the candidate count held out for the agent is fixed. At a budget of six, one arm spends it as one ranked result plus five graph neighbors, the other as six ranked results, and the paper asks which wins.
On 117 realistic queries that do not echo skill descriptions, the hybrid ranker reaches hit@5 of 73.5% ± 8.0, leaving a quarter of queries unserved within the top five.
| Arm | hit@5 | Note |
| Graph alone, no ranker | 0.9% | about chance |
| 1 ranked + 5 graph | 63.2% | budget 6 |
| 6 ranked | 74.4% | budget 6 |
At matched budget the graph trails pure retrieval by 11.2 points (McNemar p=0.0007). The cause is a pre-filter topology bound: candidate edges are drawn from the embedding top-K, so the graph can only connect skills the retriever already surfaces together. Of 1,022 distinct typed pairs, 1,008 (98.6%) are also embedding-neighbor pairs, leaving 14 graph-exclusive pairs. Adding all 1,421 edges changes no connectivity metric: no newly connected node, no merged component.
The other blow lands on evaluation method itself. On 37 author-written queries, hit@5 reads 0.946 because the queries reuse the descriptions' vocabulary. Swapping in the 117 non-echoing queries drops keyword retrieval 44.2 points and hybrid 21.1 points. Had the authors stopped at their own queries, none of the graph-does-not-help results would be visible.
Two practical takeaways for anyone shipping agents.
First, do not rush to bolt a graph onto retrieval. In a neighborhood a strong ranker already covers, added structure yields roughly zero marginal gain, and the paper supplies a reproducible matched-budget protocol to falsify whatever you were about to add. That is more honest than most retrieval papers that report only gains.
Second, never evaluate with author-written queries. They manufacture up to 44 points of false headroom and erase the real gap. A test set must deliberately avoid sharing vocabulary between queries and descriptions.
For agent frameworks already on vector retrieval, this is a receipt exempting them from the graph for now, with the caveat that their setting matches the paper's single-hop, non-saturated regime.
The authors list them plainly: 117 queries means one query is 0.85 points; the precision audit is 48 edges, single judge, description-only; no latency measured; hit@5 only checks whether the gold skill is in the batch, not whether the agent completes the task with those skills; single corpus, single organization, single embedding model, no claims about other libraries.
The boundary worth pushing is generalization. The paper uses all-MiniLM-L6-v2, a relatively small embedding model, and the topology bound says the graph cannot escape the embedding's neighborhood structure. A stronger retriever, or an approach like Graph-of-Skills that builds edges from the dependency structure baked into skill packages rather than from the retriever's neighbors, could loosen the bound. The authors concede that dependency-derived edges are a different path. The defensible claim is that a graph whose edges come from the same embedding as the retriever cannot help, not that the graph idea is dead.