CaSKG: Counterfactual-Causal Skill Graphs for Scalable Agent Skill Retrieval
Zhiyuan Li, Linyuan Gao, Xuechun Ding, Hongwei Chen, Yuan Wu, Yi Chang
cs.AI, cs.CL
2026-08-26
CaSKG scores skill-graph edges with remove/substitute/reorder probes. Versus GoS, six-model ScienceWorld rises 72.62 to 80.50 and ALFWorld success 80.01% to 86.79%.
Once an LLM agent’s skill library is large, retrieval is the main problem. Dumping the catalog into the prompt keeps coverage and drowns the policy in noise. Vector search keeps the context small and treats skills as unrelated text. Graph retrieval can pull in workflow neighbors, if the edges that carry relevance are real. Semantic similarity, co-occurrence, and interface fit can all draw an edge that is only an alternative or an unordered neighbor. Once relevance flows along those edges, the retrieved bundle is polluted. Scoring every ordered pair is also hopeless: the relation count grows with the square of the library.
CaSKG splits graph construction into high-recall discovery and edge-confidence calibration. Lexical, semantic, input/output, and structural signals induce a directed candidate graph; repair evidence and an optional LLM judge refine scores. A limited budget then selects a validation frontier. Each directed hypothesis gets three textual counterfactual probes:
Probe scores are pooled with a Beta(1,1) smoother into a reliability 𝑐𝑖𝑗 and binned as confirmed, uncertain, rejected, or unvalidated. Confirmed edges publish at full weight, uncertain ones are attenuated, rejected ones are dropped, and a few unvalidated edges stay as low-weight scaffolds. The graph is frozen offline. At run time, lexical and semantic seeds expand with a personalized PageRank-style update. The downstream policy and task interface do not change.
On Skill1000, ALFWorld ID-140 (140 episodes, success) and ScienceWorld U211 (211 episodes, official mean score), CaSKG is best in all twelve backbone-benchmark cells and uses fewer steps than GoS in every cell.
| Backbone | ALF GoS | ALF CaSKG | SW GoS | SW CaSKG |
| MiniMax-M2.7 | 63.60 | 73.57 | 55.85 | 68.33 |
| GLM-5.2 | 95.71 | 97.86 | 80.33 | 85.11 |
| Kimi-K2.6 | 93.60 | 95.00 | 76.82 | 83.88 |
| Qwen3.5-397B | 88.60 | 92.14 | 63.18 | 74.97 |
| DeepSeek-V4-Flash | 77.86 | 86.43 | 73.45 | 83.40 |
| GPT-5.6-Luna | 60.71 | 75.71 | 86.08 | 87.33 |
Six-model macro averages: ScienceWorld 72.62→80.50, ALFWorld 80.01%→86.79%. Mean steps fall from 16.39 to 15.29 on ScienceWorld and from 15.96 to 14.05 on ALFWorld. On ALFWorld, GPT-5.6-Luna drops to 55.00 with Vector and 60.71 with GoS, both below full-library Vanilla at 72.86; CaSKG recovers 75.71. Uncalibrated graph retrieval can be worse than no retrieval.
Across 24 ScienceWorld task types, CaSKG beats GoS on 21, ties 1, and loses 2 (non-living search, temperature measurement). Ablations on MiniMax / ALF / Skill1000: full 73.57%; publish-all-candidates 71.43%; no judge 71.43%; semantic-only candidates 67.14%. The gap over GoS holds from 200 to 2,000 skills.
The bottleneck in skill retrieval is the edges, not library size. CaSKG leaves the agent policy untouched and only swaps the retrieval graph, which weaker and stronger backbones both use. For stacks already on Graph-of-Skills or ToolNet-style memory, an offline “does this edge survive delete/swap/reorder” pass is a layer you can insert. Double-digit lifts on weaker models are the practical win.
There is no standalone Limitations section. The probes are textual edits of skill descriptions, not interventions in the environment, so LLM scores used as causal evidence can be self-consistent fiction. The graph is frozen; a trace-co-occurrence channel is reserved and unused in the static study. All eval is in ALFWorld and ScienceWorld text environments with a closed Skill1000 library. Construction and probe cost are not first-class metrics. The GPT-5.6-Luna contrast shows that a wrong graph can clearly hurt a strong model. Two of 24 task types go negative; extra hops can be noise on simple lookup tasks.