Source-linked AI summary
CaSKG: Counterfactual-Causal Skill Graphs for Scalable Agent Skill Retrieval
Zhiyuan Li, Linyuan Gao, Xuechun Ding, Hongwei Chen, Yuan Wu, Yi Chang
TL;DR
Reusable skill libraries make procedural knowledge reusable but create a retrieval problem: compact text matching can miss dependencies, while graph retrieval depends on reliable edges. CaSKG calibrates directed skill relations offline with counterfactual evidence before task-conditioned graph expansion, and it achieves the best reported task score across all twelve benchmark–backbone settings. The results support edge-confidence calibration as a route to compact, executable skill retrieval without changing the downstream agent policy or task interface.
Problem
Skill retrieval must expose compact procedural context when prerequisites and other necessary skills are not textually matched, while graph propagation can transmit relevance through weak relations.
Method
CaSKG builds a high-recall directed candidate graph, calibrates selected edges with direction-conditioned counterfactual probes, and publishes a state-filtered weighted graph for task-conditioned retrieval.
Results
CaSKG achieves the highest reported task score in all twelve model–benchmark settings, improving GoS macro-averages from 72.62 to 80.50 on ScienceWorld and from 80.01% to 86.79% on ALFWorld.
Takeaways & Limitations
Edge-confidence calibration is a useful design principle for scalable agent memory because selective graph publication preserves operational structure while retrieving compact skill context.
Takeaways & Limitations
The evaluation is limited to simulated ALFWorld and ScienceWorld environments, benchmark-defined protocols, and aggregate task outcomes.
Abstract
from arXiv · showhide
Reusable skill libraries allow large language model (LLM) agents to reuse procedural knowledge across tasks, but they also turn memory access into a challenging retrieval problem. Full-library prompting preserves coverage at high context cost, vector retrieval returns compact neighborhoods but treats skills as independent text, and graph-based retrieval can recover workflow context only when the edges that carry relevance are reliable. We propose CaSKG, a counterfactual-causal skill graph framework that calibrates procedural relations before retrieval. CaSKG first builds a high-recall directed candidate graph from semantic, lexical, input/output, and structural evidence, with repair evidence and an optional LLM judge further refining candidate scores. It then applies direction-conditioned textual counterfactual probes that remove, substitute, and reorder skill pairs, aggregates the evidence with Bayesian smoothing, and publishes a state-filtered weighted graph for task-conditioned expansion. The graph is constructed offline and used without changing the downstream agent policy or task interface. Across six LLM backbones on ALFWorld ID-140 and ScienceWorld U211, CaSKG achieves the highest task score in all twelve combinations of model and benchmark. Relative to Graph-of-Skills (GoS), it improves the six-model macro-average ScienceWorld score from 72.62 to 80.50 and ALFWorld success from 80.01\% to 86.79\%, while reducing mean environment steps on both benchmarks. Qualitative and ablation analyses further show that calibrated edges help retrieval preserve prerequisites, state-changing actions, verification routines, and final completion steps. These results position edge-confidence calibration as an effective route to compact and executable skill retrieval at scale\footnote{Code is available at: https://github.com/ZhiyuanLi218/Caskg }.
1 Introduction
CaSKG frames skill retrieval as calibrating which directed relations should carry relevance, then uses the calibrated graph to provide compact procedural context. It reports consistent gains across two interactive benchmarks and six LLM backbones.
- 1 Introduction: Skill retrieval must recover prerequisites, state changes, verification, and recovery procedures that may not textually match the task instruction.Full-library exposure preserves recall but adds irrelevant alternatives, while dense retrieval usually treats skills as independent text units.
- 1 Introduction: Publishing weak graph edges can pollute retrieved context, while aggressive pruning can remove useful paths and exhaustive pair assessment scales quadratically with library size.The paper formulates this trade-off as a budgeted edge-confidence calibration problem.
- 1 Introduction: CaSKG builds a high-recall directed candidate graph from heterogeneous skill signals and assesses selected relations with counterfactual probes before runtime retrieval.Candidate induction uses semantic, lexical, input/output, and structural evidence, with repair evidence and an optional LLM judge refining scores.
- 1 Introduction: Bayesian-smoothed probe evidence determines whether edges are confirmed, downweighted, rejected, or retained as low-weight scaffolds for coverage.The published graph is state-filtered and weighted before evaluation.
- 1 Introduction: CaSKG achieves the highest reported task score in all twelve model–benchmark groups, while improving GoS macro-averages from 72.62 to 80.50 on ScienceWorld and from 80.01% to 86.79% on ALFWorld.The method also reduces mean environment steps on both benchmarks.
2 Related Work
Prior work moves from tool invocation and independent text retrieval toward graph-structured memory and causal reasoning about directional dependence. CaSKG sits at this intersection by using counterfactual evidence to assess procedural graph relations.
- 2 Related Work: Tool-augmented language models evolved from local API-call decisions toward retrieval over large reusable capability libraries.Toolformer learns API insertion, ReAct couples reasoning with environment actions, and later systems address growing tool repositories.
- 2 Related Work: CaSKG combines structured graph retrieval with counterfactual relation assessment to produce compact procedural context from reusable skill libraries.Its overview separates candidate induction, edge calibration, graph publication, and task-time retrieval.
- 2 Related Work: Dense retrieval and RAG scale query-to-memory matching but generally score memory units independently, whereas graph retrieval adds relations among units.Graph-based systems use query-biased propagation over links to recover related capabilities.
- 2 Related Work: Causal graph retrieval distinguishes directional dependence from statistical association through interventions and counterfactuals.This perspective motivates assessing whether procedural relations reflect operational dependencies rather than topical similarity or unordered co-occurrence.
3 Method
CaSKG constructs a high-recall directed candidate graph, calibrates selected relations with direction-conditioned counterfactual probes, and publishes state-gated weights for task-time retrieval. This separates association discovery from reliability assessment so graph expansion can preserve useful procedural context while limiting weak-edge propagation.
- Framework overview: CaSKG builds a directed candidate graph over ordered skill pairs and uses it to provide compact procedural context without changing the downstream agent policy or task interface.Candidate relations represent hypotheses that a source skill provides operational support for a target skill.
- Candidate graph induction: Candidate induction combines semantic, lexical, input/output, structural, and optional repair evidence, while prioritizing coverage for later calibration.An optional LLM judge can further refine candidate scores; trace co-occurrence and existing-relation channels are extension points for self-evolving libraries, not active inputs here.
- Candidate graph induction: The initial association score averages active normalized signals, applies a structural floor when warranted, and clips the resulting edge weight to [0,1].Unavailable signals do not become negative evidence, and pairs outside the candidate graph have no candidate edge.
- Counterfactual edge probing: A budgeted validation frontier sends selected candidate edges to counterfactual probes, while the remaining candidates stay unvalidated rather than becoming negative evidence.The association score ranks edges for this limited validation pass and remains available as discovery support during publication.
- Counterfactual edge probing: Removal, substitution, and reordering probes test necessity, source specificity, and directionality for each selected source-to-target relation.The probes respectively remove the source, replace it with a low-overlap skill, or reverse the proposed workflow order.
- Bayesian calibration and publication: Bayesian smoothing aggregates probe evidence into relation reliability, then state-gated publication confirms, attenuates, removes, or scaffolds edges for retrieval.Confirmed edges retain full support, uncertain edges are downweighted, rejected edges are removed, and selected unvalidated edges remain attenuated scaffold links.
- Task-conditioned retrieval: The published graph freezes edge states and weights for task-conditioned expansion, allowing query relevance to propagate through calibrated procedural relations.The retrieval stage starts from task-relevant seeds and ranks skills using the resulting relevance distribution.
4 Experiments
CaSKG evaluates calibrated graph retrieval against full-library, vector, and GoS baselines on two interactive benchmarks using six fixed LLM backbones. It achieves consistently stronger task performance and lower interaction cost, with qualitative analyses linking gains to more coherent procedural skill bundles.
- Experimental setup: The evaluation compares four offline retrieval settings on ALFWorld ID-140 and ScienceWorld U211 using six LLM backbones and fixed evaluation conditions.The Skill1000 library and retrieval structures remain fixed during evaluation, without online skill-store adaptation or a separate planner.
- Main results: CaSKG achieves the highest task score for every backbone on both benchmarks and uses fewer mean steps than GoS in all twelve model–benchmark settings.Across six backbones, ScienceWorld rises from 72.62 with GoS to 80.50, while ALFWorld success rises from 80.01% to 86.79%.
- Main results: CaSKG preserves graph-based workflow context while filtering propagation through counterfactual edge evidence, producing compact bundles shaped by validated procedural relations.This differs from full-library exposure, which leaves filtering to the agent, and vector retrieval, which treats skills as independent text items.
- Main results: On ScienceWorld, CaSKG improves over GoS across all six backbones, with gains of 12.48 points for MiniMax-M2.7 and 1.25 points for GPT-5.6-Luna.The advantage narrows for stronger backbones but remains positive, indicating particular value when retrieval must supply missing procedural structure.
- Main results: On ALFWorld, CaSKG improves over GoS by 9.97 percentage points for MiniMax-M2.7 and recovers the best success rate for GPT-5.6-Luna.The comparison shows that graph propagation can underperform full-library exposure when weak links are not suppressed.
- Main results: CaSKG reduces mean steps to 15.29 on ScienceWorld and 14.05 on ALFWorld, using fewer steps than GoS in all twelve settings and the fewest overall in eleven.The aggregate interaction-cost pattern concerns environment interactions, not token usage, latency, graph-construction cost, or success-conditioned efficiency.
- Qualitative analysis: Task-type and trajectory analyses connect the aggregate gains to retrieval that preserves prerequisites, state changes, verification, and final completion steps.Figure 2 reports unweighted six-backbone gains for all 24 ScienceWorld task types; CaSKG improves on 21, ties one, and trails GoS on two.
- Qualitative analysis: The qualitative examples illustrate complementary baseline failures: full-library access creates noisy choices, vector retrieval misses non-lexical dependencies, and weak graph edges can mislead propagation.These examples explain the retrieval failure modes but are not independent proof of the aggregate results.
5 Ablation Study
The ablation study tests CaSKG across library scales and isolates how broad candidate induction, selective publication, and judge-assisted scoring contribute to retrieval quality. Results support broad candidate recall followed by selective, confidence-weighted graph publication.
- 5.1 Sensitivity to Skill Library Size: CaSKG improves success over GoS at every tested library size for both MiniMax-M2.7 and Qwen3.5-397B-A17B.The scale comparison covers 200, 500, 1,000, and 2,000 skills; gains are largest at 500 skills for both backbones.
- 5.1 Sensitivity to Skill Library Size: CaSKG uses fewer mean environment interactions than GoS at every tested scale for both evaluated backbones.The reductions are 1.48, 3.12, 1.25, and 2.61 steps for MiniMax-M2.7, and 1.75, 4.46, 2.55, and 4.16 steps for Qwen3.5-397B-A17B.
- 5.2 Component Analysis of Graph Construction: Selective publication yields the strongest ablation configuration: 73.57% success with 18.44 mean steps while publishing 3,292 of 9,937 candidate relations.The full-candidate variant publishes all 9,937 relations and reaches 71.43% success with 18.74 mean steps.
- 5.2 Component Analysis of Graph Construction: Full CaSKG outperforms the semantic-only variant by 6.43 percentage points in success and lowers mean step count by 0.77 steps.The semantic-only variant constructs 3,982 candidate relations and publishes 2,698, reaching 67.14% success with 19.21 mean steps.
- 5.2 Component Analysis of Graph Construction: The no-judge variant shows that the optional judge signal adds 2.14 percentage points of success and reduces mean steps from 18.79 to 18.44.Candidate and published graph sizes remain close to the full configuration, indicating additional calibration rather than a major change in graph scale.
- 5.2 Component Analysis of Graph Construction: The ablations support a graph-construction design that is broad during candidate induction and selective during relation publication.Multi-signal induction captures non-lexical procedural dependencies, while counterfactual state-gated publication concentrates propagation on higher-confidence relations.
6 Conclusion
CaSKG addresses scalable LLM-agent skill retrieval by separating high-recall association discovery from edge-confidence calibration and task-conditioned graph expansion. Across ALFWorld and ScienceWorld, it achieves the best reported task score in all twelve model–benchmark settings while using fewer observed environment interactions.
- 6 Conclusion: CaSKG constructs a directed candidate graph, calibrates selected edges with counterfactual evidence, and publishes a state-filtered weighted graph for compact task-conditioned retrieval.The retrieved bundle is shaped by calibrated procedural structure while the downstream agent policy and task interface remain unchanged.
- 6 Conclusion: CaSKG achieves the best reported task score in all twelve model–benchmark settings across ALFWorld and ScienceWorld.Relative to GoS, the six-model macro-average ScienceWorld score increases from 72.62 to 80.50 and ALFWorld success from 80.01% to 86.79%.
- 6 Conclusion: The findings suggest that broad candidate recall combined with selective graph publication can preserve operational structure while retrieving compact skill context.Analyses are consistent with calibrated relations preserving prerequisites, state-changing actions, verification routines, and completion steps.
Ethics and Privacy Statement
The study uses simulated ALFWorld and ScienceWorld environments with reusable skill libraries and aggregate task outcomes. It does not collect personal data, involve human subjects, or infer sensitive attributes.
- Ethics and Privacy Statement: The experiments are limited to simulated ALFWorld and ScienceWorld environments, reusable skill libraries, and aggregate task outcomes.The study does not collect personal data, involve human subjects, or infer sensitive attributes.