Similar agent skills stop being judged by description alone: a capability graph scores the weakest link and lifts ALFWorld success from 22% to 29%
Synopsis
As skill libraries grow, semantically similar skills become hard to tell apart from descriptions alone. SKALOS builds a multi-hierarchy capability graph of capability, method, artifact and constraint nodes, uses Max–Min witness learning to require that one implementation jointly covers every query requirement, and calibrates extraction errors with ranking feedback. On SkillRet its NDCG@10 is 2.68 points above a matched text-only reranker; on controlled ALFWorld tasks, witness-guided skill selection raises success from 22% to 29%.
Interpretation
Skill reranking now compares whether a candidate's internal capability evidence supports one implementation, instead of only how semantically relevant its description is to the query. Earlier skill retrieval and reranking encoded or rewrote skill descriptions and ranked by relevance, so differently worded but equivalent capabilities received different representations, and relevance did not show whether requirements were met jointly by one implementation. On the same SkillRet candidate pool, SKALOS reaches 86.76 NDCG@10 against 84.07 for the matched text-only pairwise reranker, a 2.68-point gain with a paired-bootstrap 95% confidence interval of [2.263, 3.103].
Each skill becomes a graph with typed relations, and how query requirements are covered on that graph enters the score directly. Capability canonicalization first clusters skills in embedding space, then merges semantically equivalent capability, method, artifact and constraint expressions of the same type within each cluster; nodes used by several skills go to a shared layer and single-skill nodes stay local. Witness learning scores each supporting branch by its weakest node or relation, requires one implementation to cover all requirements, and selects the strongest alternative; on a controlled four-candidate test over 93 source-disjoint skills, the witness raises NDCG@4 from 94.97 to 97.27.
Extracted graphs can contain wrong mappings or relations, so ranking feedback is used to reduce the weight of unreliable evidence. Earlier graph methods mainly organized dependencies and invocation relations between skills, and extracting structure did not by itself settle how equivalent evidence should be compared or how extraction errors should be handled. Masking each graph element and measuring the change in the positive–negative ranking margin estimates its contribution; at a 20% human-inspected error budget, full calibration recovers 33.58% of pair-margin and 32.45% of score deviations, versus 29.60% and 29.33% without the attribution loss.
Perspective
The demonstrated setting is the SkillRet skill-retrieval benchmark and controlled ALFWorld tasks, where each task pairs one valid skill with three textually similar negatives that each corrupt one critical requirement, executed by the same Qwen2.5-7B controller. The witness treats query requirements as mandatory conjunctions; optional, disjunctive and preference-based requests fall outside that definition.
The witness handles conjunctive requirements only, and extending it to optional and disjunctive requirements is stated as future work. Error detection weakens at 75% corruption though it stays above random, and calibration recovers only about a third of pair-margin and score deviations at the 20% budget. The ALFWorld result comes from controlled negatives and tests the witness mechanism rather than unconstrained deployment.