GraSP: Graph-Structured Skill Compositions for LLM Agents

• URL: http://arxiv.org/abs/2604.17870v1
• Date: Mon, 20 Apr 2026 06:31:11 GMT
• Title: GraSP: Graph-Structured Skill Compositions for LLM Agents
• Abstract summary: Skill ecosystems for LLM agents have matured rapidly, yet recent benchmarks show that providing agents with more skills does not monotonically improve performance.<n>We propose GraSP, the first executable skill graph architecture that introduces a compilation layer between skill retrieval and execution.<n>GraSP transforms flat skill sets into typed directed acyclic graphs (DAGs) with precondition-effect edges, executes them with node-level verification, and performs locality-bounded repair through five typed operators.
• Score: 29.818044584102456
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Skill ecosystems for LLM agents have matured rapidly, yet recent benchmarks show that providing agents with more skills does not monotonically improve performance -- focused sets of 2-3 skills outperform comprehensive documentation, and excessive skills actually hurt. The bottleneck has shifted from skill availability to skill orchestration: agents need not more skills, but a structural mechanism to select, compose, and execute them with explicit causal dependencies. We propose GraSP, the first executable skill graph architecture that introduces a compilation layer between skill retrieval and execution. GraSP transforms flat skill sets into typed directed acyclic graphs (DAGs) with precondition-effect edges, executes them with node-level verification, and performs locality-bounded repair through five typed operators -- reducing replanning from O(N) to O(d^h). Across ALFWorld, ScienceWorld, WebShop, and InterCode with eight LLM backbones, GraSP outperforms ReAct, Reflexion, ExpeL, and flat skill baselines in every configuration, improving reward by up to +19 points over the strongest baseline while cutting environment steps by up to 41%. GraSP's advantage grows with task complexity and is robust to both skill over-retrieval and quality degradation, confirming that structured orchestration -- not larger skill libraries -- is the key to reliable agent execution.

Related papers

• Generative Skill Composition for LLM Agents [58.47191648555256]
  LLM agents benefit from skills for solving complex tasks.<n>As skill libraries grow, selecting an appropriate skill composition has emerged as a central bottleneck.<n>We propose SkillComposer, which instantiates structured skill composition as task-conditioned skill sequence prediction.
  arXiv  Detail & Related papers  (2026-06-30T17:53:09Z)
• SkillComposer: Learning to Evolve Agent Skills for Specification and Generalization [99.18305770138677]
  Agent skills are reusable strategies that guide agent reasoning and action.<n>Current skill construction methods treat the problem as one-shot extraction.<n>We introduce SkillComposer, a framework that decomposes skill construction into three learnable operations.
  arXiv  Detail & Related papers  (2026-06-04T12:16:08Z)
• SkillDAG: Self-Evolving Typed Skill Graphs for LLM Skill Selection at Scale [54.70985426016736]
  We present SkillDAG, which models inter-skill relationships as a typed directed graph.<n>Each search returns vector matches, typed-edge neighbors, and conflict signals, and a propose-then-commit protocol lets the agent register execution-backed edges.<n>On ALFWorld and SkillsBench with MiniMax-M2.7, SkillDAG reaches 67.1% success and 27.3% reward.
  arXiv  Detail & Related papers  (2026-06-02T02:45:21Z)
• Exploiting Local Dynamics Regularity for Reusable Skills in Offline Hierarchical RL [48.61836486848426]
  We focus on abstractions that exploit the intuition of local dynamics.<n>We learn which skills to reuse and where to reuse them.<n>This information should benefit many HRL algorithms, where high-level policies have to reason about the low-level skills they use.
  arXiv  Detail & Related papers  (2026-05-25T22:39:14Z)
• SkillGraph: Skill-Augmented Reinforcement Learning for Agents via Evolving Skill Graphs [70.1970574147839]
  We propose SKILLGRAPH, a framework that represents reusable skills as nodes in a directed graph.<n>SKILLGRAPH retrieves not just individual skills, but an ordered skill subgraph that can guide multi-step decision making.<n> Experiments show that SKILLGRAPH achieves state-of-the-art performance against memory-augmented RL methods.
  arXiv  Detail & Related papers  (2026-05-12T12:21:49Z)
• Skill-R1: Agent Skill Evolution via Reinforcement Learning [84.35984979949502]
  Skill-R1 is a reinforcement learning framework for instance-level recurrent skill optimization from verifiable rewards.<n>It preserves black-box compatibility with both open- and closed-source models while making adaptation substantially cheaper than model-level updates.
  arXiv  Detail & Related papers  (2026-05-10T06:19:15Z)
• SkillLens: Adaptive Multi-Granularity Skill Reuse for Cost-Efficient LLM Agents [6.293920920196533]
  SkillLens is a hierarchical skill-evolution framework that organizes skills into a four-layer graph of policies, strategies, procedures, and primitives.<n>It retrieves semantically relevant skill seeds, expands them through degree-corrected random walk over the skill graph, and then uses a verifier to decide whether each visited unit should be accepted, decomposed, rewritten, or skipped.<n>Across MuLocbench and ALFWorld, SkillLens consistently improves over strong skill-based baselines.
  arXiv  Detail & Related papers  (2026-05-08T18:48:04Z)
• Graph of Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills [27.93279540484981]
  Graph of Skills (GoS) is an inference-time structural retrieval layer for large skill libraries.<n>GoS improves average reward by 43.6% over the vanilla full skill-loading baseline.<n>GoS consistently outperforms both vanilla skills loading and simple vector retrieval.
  arXiv  Detail & Related papers  (2026-04-07T02:09:11Z)
• SkillX: Automatically Constructing Skill Knowledge Bases for Agents [27.56549031749266]
  SkillX is a fully automated framework for constructing a plug-and-play skill knowledge base.<n>It operates through a fully automated pipeline built on three synergistic innovations.<n> Experiments show that SkillKB consistently improves task success and execution efficiency when plugged into weaker base agents.
  arXiv  Detail & Related papers  (2026-04-06T16:09:33Z)
• SKILL0: In-Context Agentic Reinforcement Learning for Skill Internalization [61.37478254738943]
  Inference-time skill augmentation is fundamentally limited.<n>We introduce SKILL0, an in-context reinforcement learning framework designed for skill internalization.<n>SKILL0 achieves substantial improvements over the standard RL baseline.
  arXiv  Detail & Related papers  (2026-04-02T17:03:05Z)
• Organizing, Orchestrating, and Benchmarking Agent Skills at Ecosystem Scale [28.43462779191672]
  AgentSkillOS is a principled framework for skill selection, orchestration, and ecosystem-level management.<n>AgentSkillOS comprises two stages: (i) Manage Skills, which organizes skills into a capability tree.<n> (ii) Solve Tasks, which retrieves, orchestrates, and executes multiple skills through DAG-based pipelines.
  arXiv  Detail & Related papers  (2026-03-02T18:46:47Z)
• SkillCraft: Can LLM Agents Learn to Use Tools Skillfully? [67.69996753743129]
  We introduce SkillCraft, a benchmark explicitly stress-test agent ability to form and reuse higher-level tool compositions.<n> SkillCraft features realistic, highly compositional tool-use scenarios with difficulty scaled along both quantitative and structural dimensions.<n>We propose a lightweight evaluation protocol that enables agents to auto-compose atomic tools into executable Skills, cache and reuse them inside and across tasks.
  arXiv  Detail & Related papers  (2026-02-28T15:44:31Z)
• SkillOrchestra: Learning to Route Agents via Skill Transfer [65.50924963973286]
  We introduce SkillOrchestra, a framework for skill-aware orchestration.<n>SkillOrchestra learns fine-grained skills from execution experience and models agent-specific competence and cost under those skills.<n>At deployment, the orchestrator infers the skill demands of the current interaction and selects agents that best satisfy them under an explicit performance-cost trade-off.
  arXiv  Detail & Related papers  (2026-02-23T10:17:25Z)
• SkillRL: Evolving Agents via Recursive Skill-Augmented Reinforcement Learning [83.98129545309277]
  We propose SkillRL, a framework that bridges the gap between raw experience and policy improvement.<n>Our approach introduces an experience-based distillation mechanism to build a hierarchical skill library SkillBank.<n> Experimental results on ALF, WebShop and seven search-augmented tasks demonstrate that SkillRL achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2026-02-09T03:17:17Z)
• TreeLoRA: Efficient Continual Learning via Layer-Wise LoRAs Guided by a Hierarchical Gradient-Similarity Tree [52.44403214958304]
  In this paper, we introduce TreeLoRA, a novel approach that constructs layer-wise adapters by leveraging hierarchical gradient similarity.<n>To reduce the computational burden of task similarity estimation, we employ bandit techniques to develop an algorithm based on lower confidence bounds.<n> experiments on both vision transformers (ViTs) and large language models (LLMs) demonstrate the effectiveness and efficiency of our approach.
  arXiv  Detail & Related papers  (2025-06-12T05:25:35Z)
• STAR: Learning Diverse Robot Skill Abstractions through Rotation-Augmented Vector Quantization [87.77475595961154]
  We present textbfSkill textbfTraining with textbfAugmented textbfRotation (textbfSTAR), a framework that advances both skill learning and composition to complete complex behaviors.
  arXiv  Detail & Related papers  (2025-06-04T11:54:42Z)
• Skill Set Optimization: Reinforcing Language Model Behavior via Transferable Skills [40.823689847227975]
  Large language models (LLMs) have recently been used for sequential decision making in interactive environments. We propose Skill Set Optimization (SSO) for improving LLM actor performance through constructing and refining sets of transferable skills. We evaluate our method in the classic videogame NetHack and the text environment ScienceWorld to demonstrate SSO's ability to optimize a set of skills and perform in-context policy improvement.
  arXiv  Detail & Related papers  (2024-02-05T17:59:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.