SKALOS: Learning to Distinguish Similar Skills with Capability Graphs

Wenhan Xiao; Ziwei Zhang; Xingcheng Fu; Chuanyue Yu; Haonan Yuan; Qingyun Sun; Runhua Xu; Jianxin Li

cs.AIOct 26, 2026

SKALOS: Learning to Distinguish Similar Skills with Capability Graphs

Authors: Wenhan Xiao, Ziwei Zhang, Xingcheng Fu, Chuanyue Yu, Haonan Yuan, Qingyun Sun, Runhua Xu, Jianxin Li

Organizations: Beihang University, Beijing, China · Guangxi Normal University, Guilin, China · Nankai University, Tianjin, China · Tsinghua University, Beijing, China

Abstract

Skills provide LLM agents with reusable procedural knowledge, making appropriate skill selection essential for reliable agent behavior. As skill libraries expand, distinguishing semantically similar candidates becomes increasingly difficult. Existing methods encode or rewrite skill descriptions for relevance-based ranking, yet heterogeneous descriptions can obscure capability differences. To address this challenge, we propose SKALOS, a graph-native reranker that compares skills via explicit capability evidence. Its multi-hierarchy graph aligns equivalent expressions across skills while preserving skill-specific capability evidence. Since individually relevant capability elements may not jointly support a query, semiring-based capability witness learning scores each branch by its weakest evidence, checks joint support for the extracted requirements within one implementation, and selects the strongest alternative. To reduce the influence of extraction errors, we develop ranking-feedback graph calibration that adjusts unreliable evidence for candidate comparison. Experiments on SkillRet show that SKALOS improves NDCG@10 by 2.68 percentage points over a matched text-only reranker. Witness-guided skill selection also increases ALFWorld task success rate from 22% to 29%.

Figures & tables

Figure 1. Three challenges in capability-aware skill selection: heterogeneous descriptions, implicit relations in text, and errors in extracted structures. Equivalent expressions may receive different embeddings; serialized relations must be recovered from textual context; structure extraction may introduce missing or spurious relations.

Figure 2. Overview of SKALOS. Multi-hierarchy capability graphs organize shared and skill-specific evidence; semiring-based witness learning aggregates requirement-covering branches anchored to one implementation; ranking-feedback graph calibration adjusts unreliable evidence used for skill reranking. The framework constructs multi-hierarchy capability graphs from skill documents, encodes query-conditioned graph evidence, forms requirement-covering capability witnesses using a Max-Min semiring, and calibrates evidence confidence through ranking feedback.

Panel of Figure 3 — Figure 3. A constructed skill graph with four node types and three typed relations. Its OCR method produces CSV tables under an English-only constraint. A skill description on the left is represented by four typed nodes and their relations in JSON on the right.

Figure 4. Max–Min path scoring: each branch is limited by its weakest node or relation. Candidate supporting paths are compared by their bottleneck scores. The strongest path for each requirement contributes to a multi-branch witness anchored to one implementation.

RAG retrieval baselines
Method	Skill input	Model size	NDCG@5	NDCG@10	Recall@10	Comp.@10
Naive-RAG	Full SKILL.md	—	56.46	59.10	67.18	52.09
HippoRAG 2	Full SKILL.md	—	44.80	47.15	55.55	39.23
RAPTOR	Full SKILL.md	—	59.23	62.16	69.08	53.35
General-purpose rerankers
jina-reranker-v2	Meta	0.3B	69.92	73.14	83.93	73.06

Table 1. Retrieval and reranking on SkillRet (percentages). Meta denotes skill metadata. Underlines mark the best published-protocol reranker; matched comparisons appear in a separate group.

Figure 5. NDCG@10 gains by score-gap quartile (Q1: smallest gap). Error bars show 95% CIs. Graph reranking improves NDCG at 10 in every score-gap quartile. Gains are 3.23, 3.27, 2.88, and 1.36 percentage points from the smallest to largest gap. Error bars show paired bootstrap confidence intervals.

Figure 6. NDCG@10 gains from embedding fusion (+Embed) and graph augmentation (+Graph) across base rerankers. Grouped bars compare embedding-score fusion and Graph-Aware Score fusion across five rerankers. Each graph module is trained separately for its reranker. Graph augmentation improves all five rerankers and consistently exceeds embedding-score fusion.

Method	NDCG@10	Recall@10	Comp.@10
First-stage Retrieval	78.03	85.42	75.09
Text-only Pairwise Reranker	84.07	93.39	87.41
Full SKILL.md Reranker	83.06	93.24	87.22
Node-as-Text Reranker	84.21	93.48	87.43
Graph-as-Text Reranker	84.09	93.17	86.66
SKALOS	86.76	94.57	89.59

Table 2. Comparison of skill representations.

Method	NDCG@4	Pair Acc.	Margin
Text Reranker	94.97	95.40	0.0129
Witness	97.27	97.53	0.0391

Table 3. Requirement-coverage stress test after removing 10% of graph nodes and relations.

Setting	NDCG@10	Recall@10	Comp.@10
SKALOS	86.76	94.57	89.59
W/O Graph	83.32	92.67	86.48
W/O Edge	80.35	93.00	86.58
W/O Relation Type	81.23	93.34	87.26
W/O Node Type	81.77	92.96	86.62
W/O Hierarchy	80.83	93.12	86.96

Table 4. Component ablation results.

Corruption	AUPRC	Recall@20%	Enrichment@20%
25%	$0.799\pm 0.015$	$78.3\%\pm 1.9\%$	$(3.92\pm 0.09)\times$
50%	$0.593\pm 0.004$	$57.6\%\pm 0.7\%$	$(2.88\pm 0.04)\times$
75%	$0.369\pm 0.014$	$37.9\%\pm 1.8\%$	$(1.89\pm 0.09)\times$
Random	0.090	20.0%	$1.00\times$

Table 5. Error detection under evidence corruption.

Setting	Perturbed (%)	Enrich. @20% ( $\times$ )	Pair rec. (%)	Score rec. (%)
Full (10%)	9.89	3.078	34.38	32.42
Full (20%)	20.10	3.029	33.58	32.45
Full (30%)	30.45	2.944	35.38	32.01
W/O Attr. (20%)	20.10	—	29.60	29.33

Table 6. Calibration under human-annotated errors. Error budgets and recovery scores are percentages.

Figure 7. ALFWorld task success by task family. Task-family success counts compare text relevance with capability witness selection on 200 ALFWorld tasks. Total successes rise from 44 to 58 with the same controller and candidate pools.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Split	Clusters	Skills/cluster	Cap.	Method	Art.	Const.
Train	100	101.23	420.87	19.25	17.95	20.03
Test	95	70.11	298.88	14.58	13.15	14.40

Appendix

Table 7. Capability-graph cluster and node statistics.

Component	Hyperparameter	Value
Text encoder	Status	Frozen
Graph encoding	Hidden size / layers / dropout	128 / 2 / 0.15
Optimization	Optimizer / weight decay	AdamW / $10^{-4}$
	Gradient clip / accumulation	1.0 / 8
Initialization	Epochs / LR / max negatives	3 / $5\!\times\!10^{-4}$ / 8
Graph training	Epochs / LR / max negatives	2 / $10^{-4}$ / 4

Appendix

Table 8. Hyperparameters for graph-reranker training.

Metric	Seed 42	Seed 43	Mean $\pm$ SD
NDCG@5	84.331	84.560	$84.446\pm 0.162$
NDCG@10	86.758	87.032	$86.895\pm 0.194$
Recall@10	94.568	94.959	$94.764\pm 0.276$
Comp.@10	89.591	90.353	$89.972\pm 0.539$

Appendix

Table 9. SKALOS results for two training seeds.

Graph	Mean (ms)	P95 (ms)	QPS	Memory (MiB)
Base	134.85	155.60	7.42	181.64
Augmented	146.97	168.47	6.80	184.16

Appendix

Table 10. Witness scoring efficiency for two graph inputs, using precomputed text embeddings.

Model/run	Time (s)	ms/query	QPS
Base reranker	446	89.45	11.18
Witness, run 1	623	124.95	8.00
Witness, run 2	674	135.18	7.40

Appendix

Table 11. Graph-scoring latency from full evaluation with precomputed embeddings.

Split	Stage	Total	Median/Skill	P95/Skill
Train	Clustering	128.96 min	–	–
Train	Graph extraction	23.21 h	24.34 s	38.47 s
Test	Clustering	64.63 min	–	–
Test	Graph extraction	24.25 h	22.80 s	28.00 s

Appendix

Table 12. Offline capability-graph construction cost.

Component	Parameters	Checkpoint	Training record
Base graph reranker	0.916M	3.51 MiB	33.68 h (3 epochs)
Graph-native reranker	1.999M	7.65 MiB	6.07 min (2 epochs)
Graph-calibration module	1,089	9.70 KiB	65.7 min (200 epochs)

Appendix

Table 13. Trainable model size and recorded training cost.

Comparator	Gain	95% CI	Holm $p$
Text-only	2.684	[2.263, 3.103]	$<0.001$
Full SKILL.md	3.703	[3.257, 4.174]	$<0.001$
Graph-as-Text	2.672	[2.237, 3.095]	$<0.001$

Appendix

Table 14. Paired NDCG@10 gains of SKALOS over matched internal baselines on all 4,997 test queries.

Reranker	Base	+Graph	$\Delta$
Qwen3-0.6B	79.06	87.97	+8.91
Jina-v2	75.91	87.67	+11.76
BGE-v2-m3	59.79	84.60	+24.81
Qwen3-4B	81.10	88.53	+7.43
Qwen3-8B	80.11	88.78	+8.67

Appendix

Table 15. Graph augmentation results (NDCG@10).

Model	Contrast	Gain	95% CI	Holm $p$
Qwen3-0.6B	vs. Base	8.913	[8.223, 9.599]	$<.001$
	vs. +Embed	8.312	[7.584, 9.046]	$<.001$
Jina-v2	vs. Base	11.758	[11.033, 12.489]	$<.001$
	vs. +Embed	8.106	[7.369, 8.862]	$<.001$
BGE-v2-m3	vs. Base	24.805	[23.973, 25.660]	$<.001$
	vs. +Embed	7.236	[6.473, 7.995]	$<.001$

Appendix

Table 16. Paired cross-reranker gains on NDCG@10.

Task family	Tasks	Text	+ Witness
Look in light	19	6	6
Pick and place	46	17	22
Clean and place	37	16	18
Cool and place	28	3	6
Heat and place	25	2	6
Pick two and place	45	0	0

Appendix

Table 17. ALFWorld execution success by task family. Text and + Witness report successful task counts.

Metric	25%	50%	75%
AUPRC	$0.799\pm 0.015$	$0.593\pm 0.004$	$0.369\pm 0.014$
Recall@20%	$78.3\%\pm 1.9\%$	$57.6\%\pm 0.7\%$	$37.9\%\pm 1.8\%$
Enrichment@20%	$(3.92\pm 0.09)\times$	$(2.88\pm 0.04)\times$	$(1.89\pm 0.09)\times$
Within-graph AUC	$0.875\pm 0.024$	$0.738\pm 0.025$	$0.609\pm 0.032$
Threshold F1	$0.845\pm 0.013$	$0.662\pm 0.012$	$0.411\pm 0.016$

Appendix

Table 18. Error detection under raw-evidence corruption. Columns indicate corruption levels; values are mean

\pm

SD.

Metric	Full 10%	Full 20%	Full 30%	W/O Attr. 20%
Perturbed (%)	$9.89\pm 1.20$	$20.10\pm 0.98$	$30.45\pm 1.09$	$20.10\pm 0.98$
Enrich.@20%	$3.078\pm 0.180$	$3.029\pm 0.001$	$2.944\pm 0.056$	–
Pair rec. (%)	$34.38\pm 0.85$	$33.58\pm 5.08$	$35.38\pm 4.32$	$29.60\pm 4.19$
Score rec. (%)	$32.42\pm 0.71$	$32.45\pm 4.43$	$32.01\pm 2.74$	$29.33\pm 3.16$

Appendix

Table 19. Calibration recovery and attribution ablation, with mean

\pm

SD across two recorded runs.

LLM Agent Skill Retrieval

Large language model agent skill retrieval finds and selects reusable procedures to help agents complete tasks.

See all 102 papers

Task Decomposition-Guided Reranking for Adaptive Agent Skill Retrieval
Jul 7, 2026Yanping Chen, Weijie Shi, Wen Yang +1LLM Planning LLM Reranking
School of Computer Science and Technology, Soochow University · The Hong Kong University of Science and Technology
SkillDAG: Self-Evolving Typed Skill Graphs for LLM Skill Selection at Scale
Jun 2, 2026Tong Bai, Zhenglin Wan, Pengfei Zhou +3LLM Agent Skill Retrieval Dynamic Graph Learning
Fudan University · National University of Singapore · CFAR, A*STAR
SkillSight: Calibrating Generic Content Bias for Skill Retrieval
Jul 21, 2026Jinying Xiao, Bin Li, Xiaopeng Li +7Lexical Retrieval LLM Agent Skill Retrieval
1National University of Defense Technology · 2Qinghai Normal University · 3Xizang University

Jul 7, 2026J/K move · Enter open · S save

Task Decomposition-Guided Reranking for Adaptive Agent Skill Retrieval

Yanping Chen, Weijie Shi, Wen Yang, Jiajie Xu

School of Computer Science and Technology, Soochow University · The Hong Kong University of Science and Technology

LLM Planning LLM Reranking LLM Agent Skill Retrieval Task Decomposition

Open paper AskPDF arXiv

Skill usage can significantly enhance the ability of modern agent systems to complete complex tasks. However, the growing scale of skill libraries makes accurate skill selection increasingly challenging. In real-world scenarios, ambiguous semantic matching often arises between a specific task requirement and multiple generic yet semantically similar candidate skills. Moreover, existing methods tend to overlook the dynamic influence of task difficulty and skill applicability when selecting the optimal target skill set. To address these issues, we propose SkillReranker, an inference-time reranking framework for adaptive skill selection. Specifically, we first perform semantic decomposition on both the task and skill sides, yielding informative subtask and execution-state descriptions as well as transition-state descriptions that characterize each skill's functionality. These descriptions are then used to construct a directed acyclic execution graph, where intermediate task states are modeled as nodes and candidate skills as edges, thereby establishing a structured task-skill correspondence. On this basis, SkillReranker determines whether each state node satisfies the split condition to identify subtask intervals. For each task interval, we employ a cross-encoder to perform comprehensive scoring over candidate skills and select the most suitable ones to form the final target skill set. Experiments on ALFWorld and ScienceWorld with three backbone LLMs show that SkillReranker effectively improves task performance, reduces environment interaction steps, and lowers token consumption compared with existing skill selection baselines.

Abstract

LLM Agent Skill Retrieval

Explore similar work

Task Decomposition-Guided Reranking for Adaptive Agent Skill Retrieval

SkillDAG: Self-Evolving Typed Skill Graphs for LLM Skill Selection at Scale

SkillSight: Calibrating Generic Content Bias for Skill Retrieval