SkillGraph: Graph Foundation Priors for LLM Agent Tool Sequence Recommendation

Hao Liu; Dongyu Li

cs.AIApr 7, 2026

SkillGraph: Graph Foundation Priors for LLM Agent Tool Sequence Recommendation

Authors: Hao Liu, Dongyu Li

Abstract

LLM agents must select tools from large API libraries and order them correctly. Existing methods use semantic similarity for both retrieval and ordering, but ordering depends on inter-tool data dependencies that are absent from tool descriptions. As a result, semantic-only methods can produce negative Kendall- $τ$ in structured workflow domains. We introduce SkillGraph, a directed weighted execution-transition graph mined from 49,831 successful LLM agent trajectories, which encodes workflow-precedence regularities as a reusable graph foundation prior. Building on this graph foundation prior, we propose a two-stage decoupled framework: GS-Hybrid retrieval for candidate selection and a learned pairwise reranker for ordering. On ToolBench (9,965 test instances; ~16,000 tools), the method reaches Set-F1 = 0.271 and Kendall- $τ$ = 0.096; on API-Bank, Kendall- $τ$ improves from -0.433 to +0.613. Under identical Stage-1 inputs, the learned reranker also outperforms LLaMA-3.1-8B Stage-2 rerankers.

Figures & tables

Fig. 1: The selection–ordering gap . For query “I want to convert dollars to euros”, semantic similarity ranks Convert first (sim = 0.048

>

0.018), inverting the required execution order: one must first call SuppCurrencies (short for supported_currencies_for_currency_converter_v2 ) to obtain the valid currency list before invoking Convert . SkillGraph, mined from LLM agent trajectories, encodes the dependency SC

\!\to\!

Conv (

P=0.78

) and restores the correct sequence.

Property	Value
Nodes (tools)	4,988
Directed edges	39,034
Communities (Louvain)	216
Modularity $Q$	0.892
Mean community purity	0.779
NMI (community vs. API category)	0.695

TABLE I: SkillGraph Statistics

Fig. 2: Top-10 SkillGraph communities (out of 216 total; Louvain modularity $Q{=}0.892$ ). Node size is proportional to community size (number of tools); arrow weight reflects inter-community transition probability. Communities align with API categories (NMI = 0.695 vs. RapidAPI taxonomy): domain-specific tools co-cluster naturally (e.g. Finance and Currency & Crypto exchange strongly, reflecting multi-step trading workflows), validating that SkillGraph encodes semantically coherent execution dependencies.

Fig. 3: SkillGraph subgraph for the currency-domain community (three API clusters). Intra-cluster edges carry high statistical transition probability: SC

\to

Conv (

w{=}0.78

n{=}23

) and CList

\to

Rate (

w{=}0.82

) encode workflow dependencies invisible in tool descriptions; clusters are self-contained with no inter-cluster statistical co-occurrence. The reverse edge Conv

\to

SC has

\text{transition\_prob}{=}0.00

(dashed), confirming that SkillGraph captures execution order , not merely semantic similarity between tools.

Panel of Figure 5 — Fig. 4: Transition probability $w(t_{a},t_{b})$ vs. semantic cosine similarity for all 39,034 SkillGraph edges (log-scale density). Spearman $\rho=-0.15$ ( $p<0.001$ ): the two signals are slightly negatively correlated, confirming they capture complementary aspects of tool relationships. High-probability transitions (e.g., SC $\to$ Conv : $w=0.78$ , $\mathrm{sim}=0.68$ ) can co-occur with moderate semantic similarity, yet the weak negative correlation shows that in aggregate, strong co-occurrence does not imply semantic overlap. This motivates the hybrid design in both stages of the framework.

Fig. 5: Conceptual overview of the two-stage decoupled framework. Stage 1 (GS-Hybrid) constructs a candidate tool set

\hat{\mathcal{S}}

of up to

K_{\mathrm{eval}}

tools by combining dense semantic retrieval with SkillGraph-guided candidate construction. Stage 2 (Learned Reranker) orders the candidates via a PairwiseMLP that combines eight features: semantic similarity and rank (f1–f2), SkillGraph transition probabilities (f3–f6), and positional priors (f7–f8). Decoupling the stages allows independent optimisation of set coverage and sequence ordering, eliminating the single-stage selection-ordering trade-off.

Single-Stage Methods
Method	Set-F1	Ord.Prec	Kendall- $\tau$	Trans.Acc	1st.Acc
Semantic Only	0.266	0.123	0.042	0.070	0.262
BM25	0.215	0.073	$-$ 0.001	0.041	0.143
Beam Search	0.240	0.149	0.089	0.099	0.206
Hybrid Sem-Graph	0.271	0.130	0.044	0.082	0.262
Two-Stage Methods (Stage 1: GS-Hybrid)

TABLE II: Tool Sequence Recommendation Results on ToolBench (9,965 Test Instances). Best results in bold . Significance vs. GS-Hybrid+Sem-Sort (bootstrap, 10K resamples): ∗

p{<}0.05

, ∗∗

p{<}0.01

Method	Set-F1	Ord.Prec	Kendall- $\tau$	Trans.Acc
BM25	0.590	0.100	$-$ 0.100	0.10
Semantic Only	0.793	0.133	$-$ 0.433	0.15
Hybrid Sem-Graph	0.803	0.193	$-$ 0.293	0.19
GS-Hybrid + Hyb-Rerank	0.803	0.173	$-$ 0.333	0.19
GS-Hybrid + LR (ours)	0.803	0.647	+0.613	0.62
LLaMA-3.1-8B (3-shot)	0.945 $\ddagger$	0.747	–	–

TABLE III: Tool Sequence Recommendation Results on API-Bank Level-3 (50 instances, LOO-CV). In each fold, graph-based transition statistics are estimated from the other 49 API-Bank instances, while GS-Hybrid+LR reuses ToolBench-trained reranker weights zero-shot.

Method	Set-F1	Ord.Prec	Kendall- $\tau$	Trans.Acc
GS-Hybrid + LR (ours)	0.254	0.140	0.097	0.084
GS-Hybrid + Hyb-Rerank	0.254	0.132	0.081	0.082
GS-Hybrid + LLaMA (0-shot)	0.254	0.116	0.048	0.083
GS-Hybrid + LLaMA (3-shot)	0.257	0.110	0.043	0.071

TABLE IV: Comparison with LLM-Based Stage-2 Reranking on ToolBench (Sampled

n=300

, Fair: All Methods Use Identical Stage-1 Output). Set-F1 is equal across LR/HR/LLaMA-0shot (same Stage-1); LLaMA-3shot differs marginally due to list-reordering affecting tool parsing.

Stage-2 HR $\alpha$ sensitivity (Stage-1: GS-Hybrid fixed)
Configuration	Ord.Prec	Kendall- $\tau$	Trans.Acc
$\alpha=0.0$	0.134	0.052	0.084
$\alpha=0.1$	0.152	0.087	0.097
$\alpha=0.4$ (ours)	0.154	0.092	0.098
$\alpha=0.7$	0.153	0.089	0.097
$\alpha=1.0$	0.152	0.087	0.097

TABLE V: Ablation Study on ToolBench (9,965 test instances). Top : Stage-2 Hybrid-Rerank mixing coefficient

\alpha

(Stage-1: GS-Hybrid fixed). Set-F1 improves from 0.266 (

\alpha{=}0

) to 0.271 (

\alpha{=}0.4

); ordering metrics are

\alpha

-stable for

\alpha\in[0.1,1.0]

, confirming stage decoupling. Middle : Stage-2 strategy comparison (Stage-1: GS-Hybrid,

\alpha{=}0.4

). Bottom : LR feature-group ablation (inference-time zeroing; Set-F1 fixed at 0.271 for all).

Panel of Figure 11 — Fig. 6: $\alpha$ sensitivity of GS-Hybrid+Hybrid-Rerank on ToolBench (Stage 1 fixed; Stage 2 Hybrid-Rerank weight varied). All three metrics jump sharply from $\alpha{=}0$ (semantic only) to $\alpha{=}0.1$ (graph added), then plateau over $\alpha\!\in\![0.3,\,0.7]$ , confirming that Stage 1 and Stage 2 can be optimised independently.

Panel of Figure 12 — Fig. 7: LR feature-group ablation on ToolBench (Set-F1 fixed at 0.271 for all variants; inference-time zeroing). Graph transition features (f3–f6) contribute most: removing them drops Kendall- $\tau$ by $16\%$ and Ord.Prec by $5\%$ . Positional priors (f7–f8) rank second ( $-11\%\,\tau$ ); semantic features (f1–f2) contribute least ( $-6\%\,\tau$ ), confirming SkillGraph as the primary ordering signal.

Length bucket	Semantic Only	GS-Hybrid+HR	GS-Hybrid+LR	LR vs. Sem. (%)
1–2 tools	0.044	0.085	0.098	$+$ 123%
3–4 tools	0.040	0.087	0.093	$+$ 134%
5 $+$ tools	0.049	0.111	0.108	$+$ 119%
All lengths	0.042	0.089	0.096	$+$ 129%

TABLE VI: Kendall-

\tau

by Ground-Truth Sequence Length on ToolBench. GS-Hybrid+LR consistently improves over Semantic Only across all sequence lengths by

119

–

134\%

Panel of Figure 14 — Fig. 8: Kendall- $\tau$ by ground-truth sequence length on ToolBench (9,965 instances). GS-Hybrid+LR (ours) improves over Semantic Only by $+$ 119–134% across all length buckets, confirming that SkillGraph dependency priors are beneficial regardless of workflow length. Percentages above bars indicate relative improvement of LR over Semantic Only.

Panel of Figure 15 — Fig. 9: Set-F1 vs. Ordered Precision on ToolBench (9,965 instances) for representative methods. GS-Hybrid+LR ( $\bigstar$ ) is the sole Pareto-optimal point, achieving the highest value on both axes simultaneously. Single-stage methods ( $\bullet$ ) trade Set-F1 for Ord.Prec or vice versa. Two-stage non-learned methods ( $\blacktriangle$ ) improve ordering without sacrificing Set-F1, but fall short of the learned reranker.

Panel of Figure 16 — Fig. 10: Error analysis of GS-Hybrid+LR vs. GS-Hybrid+Sem-Sort on ToolBench. (a) 92% of instances are unaffected; LR improves 515 instances ( $+$ 5.2%) and degrades 243 ( $-$ 2.4%). Improved cases share high SkillGraph transition asymmetry; degraded cases are predominantly single-tool sequences where pairwise signal is uninformative. (b) LR improves global ordering (Ord.Prec $+17\%$ ; Kendall- $\tau$ $+88\%$ ) at a small cost to first-tool accuracy ( $-$ 2.8 pp), a known property of pairwise ranking objectives that optimise aggregate agreement rather than position 1.

$K$	Method	Set-F1	Kendall- $\tau$	$\Delta\tau$
3	Semantic Only	0.269	0.037	–
3	GS-Hybrid+LR	0.274	0.095	$+$ 156%
5	Semantic Only	0.237	0.052	–
5	GS-Hybrid+LR	0.243	0.107	$+$ 106%
8	Semantic Only	0.195	0.068	–
8	GS-Hybrid+LR	0.197	0.121	$+$ 79%

TABLE VII: Fixed-

K

Robustness on ToolBench (9,965 test instances). Semantic Only uses top-

K

retrieval; GS-Hybrid+LR uses hybrid graph-semantic stage 1 truncated to

K

, then the learned reranker. Oracle uses

K=\max(|S^{*}|,3)

as the reference.

\Delta\tau

= relative improvement in Kendall-

\tau

Tool-Using Language Agents

Tool-using language agents combine language models with APIs, code, and other tools to answer questions and carry out multi-step tasks.

See all 58 papers

Graph-of-Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills
Apr 7, 2026Dawei Liu, Zongxia Li, Hongyang Du +4Tool-Augmented Language Model Agents Graph-Based Retrieval
University of Pennsylvania · University of Maryland · Brown University +2
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
GraSP: Graph-Structured Skill Compositions for LLM Agents
Apr 20, 2026Tianle Xia, Lingxiang Hu, Yiding Sun +5LLM Agent Orchestration LLM Agent Workflow Optimization
Tencent

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

Graph-of-Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills

Dawei Liu, Zongxia Li, Hongyang Du, Xiyang Wu+3

University of Pennsylvania · University of Maryland · Brown University+2

Tool-Augmented Language Model Agents Graph-Based Retrieval LLM Agent Skill Retrieval LLM Agents

Open paper AskPDF arXiv

As LLM agents act across personal applications, web browsers, and other interfaces, their reusable skill libraries can scale to thousands of skills. This scale introduces two challenges. First, loading the full library saturates the context window, driving up token costs, hallucination, and latency. Second, semantic retrieval surfaces topically relevant skills but can miss upstream and downstream prerequisite skills, creating a prerequisite gap that leaves the retrieved bundle insufficient for execution. We present Graph-of-Skills (GoS), an inference-time structural retrieval layer for large skill libraries. GoS constructs an executable skill graph offline from skill packages, then retrieves a bounded, dependency-aware bundle through hybrid semantic-lexical seeding, reverse-aware Personalized PageRank, and context-budgeted hydration. Across SkillsBench and ALFWorld, with three model families (Claude Sonnet 4.5, MiniMax M2.7, and GPT-5.2 Codex), GoS attains the highest average reward in all six model-benchmark blocks, at a fraction of the token cost of loading the full library. On SkillsBench with GPT-5.2 Codex it raises average reward by 7.0 absolute points over full skill loading, a 25.6% relative gain, while cutting total tokens by 56.7%. Ablations isolate the mechanism: replacing reverse traversal with forward propagation costs 9.1 reward points, a larger loss than removing the graph altogether. The gain thus comes from traversing dependencies backwards, not from graph diffusion as such. A budget-matched retrieval study holding seeding, reranking, hydration, and context budget fixed reproduces the same ordering, with dependency-pair co-recovery falling from 0.654 to 0.362. Code is available at https://github.com/davidliuk/graph-of-skills

Abstract

Tool-Using Language Agents

Explore similar work

Graph-of-Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills

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

GraSP: Graph-Structured Skill Compositions for LLM Agents