Skills give large language model agents reusable procedural knowledge, and selecting the right skill is essential for reliable behavior. As skill libraries grow, distinguishing semantically similar candidates becomes harder. Existing approaches encode or rewrite skill descriptions for relevance ranking, but heterogeneous descriptions often hide capability differences. To tackle this, we introduce SKALOS, a graph-native reranker that compares skills using explicit capability evidence. SKALOS builds a multi‑hierarchy capability graph that aligns equivalent expressions across skills while preserving skill‑specific evidence. Because individually relevant capability elements may not jointly support a query, we employ semiring‑based capability witness learning: each branch is scored by its weakest evidence, joint support for extracted requirements is checked within a single implementation, and the strongest alternative is selected. To mitigate extraction errors, ranking‑feedback graph calibration adjusts unreliable evidence during candidate comparison. Experiments on the SkillRet benchmark show that SKALOS improves NDCG@10 by 2.68 percentage points over a matched text‑only reranker and raises ALFWorld task success from 22% to 29%.
Review: SKALOS’s explicit capability graph and semiring scoring enable fine‑grained discrimination of similar skills, leading to notable gains in retrieval quality and downstream task performance, and offering a scalable approach for managing large LLM skill libraries.