CaSKG: Counterfactual-Causal Skill Graphs for Scalable Agent Skill Retrieval

AI summary

Overview

Research area: Artificial intelligence, specifically LLM agent tool/skill retrieval, graph-based retrieval, and causal/counterfactual reasoning over procedural memory.

Technical level: Advanced. The paper assumes familiarity with retrieval-augmented generation, graph propagation (personalized PageRank), Bayesian smoothing (Beta distributions), and counterfactual reasoning.

Scope in one sentence: The paper proposes CaSKG, an offline framework that builds a directed skill graph from a high-recall candidate pool and then calibrates which edges are trustworthy using LLM-simulated counterfactual probes, so that runtime retrieval returns compact, executable skill bundles for LLM agents.

What This Paper Is About

LLM agents increasingly accumulate libraries of reusable "skills," but exposing a large library to a model creates a retrieval problem: full-library prompting costs context, vector retrieval treats each skill as an isolated text unit, and graph retrieval propagates relevance through edges that may connect skills that are merely topically similar, unordered, or otherwise operationally unsuitable. CaSKG's goal is to decide which candidate relations between skills deserve to influence retrieval, by assessing those relations with counterfactual tests before the graph is used.

Key Contributions

1. A new problem formulation. The authors formulate scalable skill-graph construction as a budgeted edge-confidence calibration problem: given a high-recall candidate pool, the system must decide which edges deserve assessment, how much confidence each assessed relation receives, and how that confidence controls graph propagation.

2. The CaSKG method. An offline graph-construction pipeline that combines multi-signal candidate induction (semantic, lexical, input/output, and structural evidence, plus repair evidence and an optional LLM judge) with direction-conditioned textual counterfactual probes and Bayesian state-gated publication.

3. A specific mechanism for edge reliability. Three probes — removal, substitution, and reordering of skill pairs — produce oriented support scores that are aggregated with a Beta-form accumulator, then mapped into confirmed / rejected / uncertain / unvalidated states that determine published edge weights.

4. Evaluation across twelve model–benchmark combinations. Six LLM backbones on ALFWorld ID-140 and ScienceWorld U211 (Table 1), plus qualitative task-type breakdowns, trajectory examples, library-scale records, and graph-construction ablations.

Main Findings

• Highest task score in all twelve settings. CaSKG achieves the highest reported task score in every combination of the six backbones and two benchmarks. Against Graph-of-Skills (GoS), the six-model macro-average ScienceWorld score rises from 72.62 to 80.50, and ALFWorld success rises from 80.01% to 86.79%.

• Largest gains appear on weaker or retrieval-dependent backbones. On ScienceWorld, CaSKG beats GoS by 12.48 points for MiniMax-M2.7 and 9.95 points for DeepSeek-V4-Flash, narrowing to 4.78 points for GLM-5.2 and 1.25 points for GPT-5.6-Luna. On ALFWorld, MiniMax-M2.7 improves over GoS by 9.97 percentage points and over both non-graph settings by more than 27 points; GLM-5.2 is described as already near the success ceiling.

• Failure modes differ per baseline. Vanilla Skills keeps the whole Skill1000 catalog and shifts selection burden to the agent; Vector Skills reduces context but ignores procedural links; GoS adds relational propagation but depends on edge reliability. For GPT-5.6-Luna on ALFWorld, Vector Skills and GoS fall sharply below Vanilla Skills, while CaSKG recovers the best success rate among all settings.

• Fewer environment steps, not more. CaSKG reduces the ScienceWorld six-model mean to 15.29 steps versus 16.39 for GoS and roughly 18 for the two non-graph settings; on ALFWorld it averages 14.05 steps versus 15.96 for GoS and roughly 16.7–16.8 for the non-graph settings. It uses the fewest steps in five of six ALFWorld backbones; the sole exception is GPT-5.6-Luna, where Vanilla is marginally shorter (17.74 versus 17.79) but less successful. Across both benchmarks, CaSKG uses fewer steps than GoS in all twelve settings and has the lowest mean step count in eleven.

• Task-type analysis on ScienceWorld. Across the 24 U211 task types, CaSKG improves on 21, ties on one, and trails GoS on two (non-living-thing search and temperature measurement). The largest gains are in tertiary- and secondary-color mixing, plant growing, unknown conductivity, and energy classification — categories the authors describe as requiring multiple dependent operations.

• Qualitative mechanism. Calibrated edges help retrieval preserve prerequisites, state-changing actions, verification routines, and final completion steps.

• What is not measured. The paper states that Steps measures observed interaction consumption, not token usage, wall-clock latency, retrieval latency, or graph-construction cost; the step findings are described as an aggregate interaction-cost pattern, not a claim about success-conditioned efficiency. CaSKG is built offline and frozen before evaluation, and does not change the downstream agent policy, task interface, or episode-time planning.

Methodology in Plain English

The pipeline has four stages, all of them offline except retrieval.

1. Build a broad candidate graph. For every ordered pair of skills, CaSKG gathers multiple kinds of evidence — how similar their wording is, how similar their meanings are, whether their inputs/outputs fit together, and where they sit in a workflow. Repair evidence and an optional LLM judge refine the scores of pairs already in the set. These signals are combined into a weighted average, with a "structural floor" that keeps strong workflow evidence intact when it exceeds a threshold. The goal here is recall: bring in plausible relations, not yet judge them.

2. Probe a limited subset. Because the number of ordered pairs grows quadratically with library size, only a budgeted subset of candidate edges is tested. For each selected pair, an LLM is asked three counterfactual questions about the directed relation: What if the source skill is removed (does the target break — necessity)? What if the source is replaced by an unrelated skill (is the source specific — specificity)? What if the order is reversed (does the workflow still make sense — directionality)? Each returns a score in [0, 1].

3. Turn probe scores into edge reliability. The three scores are converted into binary support votes and evidence weights (using a minimum evidence floor so near-midpoint judgments are not discarded), then accumulated into a Beta distribution initialized at Beta(1,1). The normalized Beta mean becomes a reliability score. Depending on a confirmation threshold, each probed edge is labeled confirmed, rejected, or uncertain; unprobed candidates are labeled unvalidated. Confirmed edges keep full weight, uncertain edges are downweighted, rejected edges are removed, and a bounded set of unvalidated edges survives as a low-weight scaffold for coverage. The result is a frozen published graph.

4. Retrieve over the calibrated graph. At task time, lexical and semantic matching identifies seed skills, which become an inverse-rank-weighted starting distribution. A personalized PageRank-style diffusion walks over the published graph — edge weights controlling how much relevance flows — to produce a compact skill bundle for the unchanged agent loop.

Experimental setup: Two interactive benchmarks (ALFWorld ID-140 with 140 in-distribution household episodes, scored as success rate; ScienceWorld U211 with 211 evaluated science episodes, scored by the official best score) and a Skill1000 library built offline and held fixed. Four settings are compared: Vanilla Skills, Vector Skills, GoS, and CaSKG. Six backbones: MiniMax-M2.7, GLM-5.2, Kimi-K2.6, Qwen3.5-397B-A17B, DeepSeek-V4-Flash, and GPT-5.6-Luna. Within each benchmark, methods share task cohort, prompt, evaluator, episode limits, and interaction loop.

Why This Matters

Impact on research. The paper reframes skill retrieval as a question about edge trustworthiness rather than graph size or similarity ranking. It connects the causal-inference toolkit (interventions, counterfactuals, directionality) to practical agent memory, and it isolates the effect of the retrieval graph from the downstream policy — the graph changes, nothing else does. This gives the agent-memory community a concrete lever to study: which relations should be allowed to carry relevance.

Real-world applications (as implications of the method, not measured in the paper):

• Enterprise agent platforms with large tool catalogs, where an agent must select a coherent sequence of API calls rather than a single best match.
• Robotics and household assistants, the domain of the ALFWorld benchmark, where task success depends on ordering navigation, pickup, state change, and placement.
• Scientific and laboratory automation, the domain of ScienceWorld, where procedures require setup, transformation, observation, and classification steps.
• Self-evolving skill libraries, where agents accumulate new executable procedures over time and need a principled way to decide which stored relations survive into the retrieval graph.

Industry relevance. The work is a collaboration between Jilin University and Ant Group, and it targets a practical bottleneck — context cost and irrelevant alternatives as procedural memory grows. The framework is designed to be dropped in without changing the agent policy or the task interface, and the code is released at https://github.com/ZhiyuanLi218/Caskg.

Future Directions

• Activating the reserved extension channels. The paper defines trace co-occurrence and relation-history channels for self-evolving libraries, but in this static study they remain extension points rather than active inputs. Future work would let execution logs and prior relations feed back into edge calibration.

• Scaling the validation budget. Candidate relations grow quadratically with library size, so deciding which edges to probe under a fixed budget remains a central open problem. The interaction between budget size and retrieval quality is not resolved here.

• Truthfulness of the counterfactual probes. Edge reliability rests on LLM judgments of removal, substitution, and reordering effects on skill descriptions. How well those textual probes track real operational dependence in execution is not established by the reported results.

• Broadening the cost accounting. The evaluation reports task score and environment steps only. Token usage, retrieval latency, wall-clock latency, and the cost of graph construction itself are explicitly outside the measurement, and whether the step savings hold under different episode limits or as conditions on successful episodes remains untested.

Target Audience

Researchers and engineers working on LLM agents, tool and skill retrieval, graph-based retrieval, and retrieval-augmented generation; practitioners building agent platforms where a large library of reusable procedures must be narrowed to a small, executable working set; and readers interested in applying causal or counterfactual reasoning to structured memory. Familiarity with graph propagation and probabilistic scoring is helpful, but the paper's motivation and results are accessible to anyone tracking agent-memory retrieval.

Authors’ abstract

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 }.