Source-linked AI summary
GraSP: Graph-Structured Skill Compositions for LLM Agents
Tianle Xia, Lingxiang Hu, Yiding Sun, Ming Xu, Lan Xu, Siying Wang, Wei Xu, Jie Jiang
TL;DR
Skill-based agents face an orchestration gap: more retrieved skills can hurt, while flat execution leaves dependencies and recovery implicit. GraSP inserts a compilation layer that builds typed DAGs with verified execution and local repair, and it outperforms baselines across four benchmarks and eight backbones while reducing environment steps.
Problem
Skill availability is no longer the bottleneck: focused skill sets outperform excessive retrieval, exposing a need for structured orchestration between retrieval and execution.
Method
GraSP compiles retrieved skills into typed DAGs with explicit dependencies, executes nodes with verification, and repairs failures through locality-bounded typed operators.
Results
+19 points reward and 41% fewer environment steps are achieved against the strongest baseline across four benchmarks and eight LLM backbones.
Takeaways & Limitations
Across four interactive benchmarks and eight LLM backbones, GraSP achieves the best performance in every configuration, with advantages that grow with task complexity.
Takeaways & Limitations
The DAG assumption excludes cyclic execution patterns, so iterative refinement tasks may require loop constructs or DAG unrolling.
Abstract
from arXiv · showhide
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.
1 Introduction
GraSP addresses the shift from skill availability to skill orchestration by compiling retrieved skills into executable causal graphs. Across four benchmarks and eight LLM backbones, it improves performance while reducing execution steps.
- 2–3 focused skills yield the largest gains, whereas 4+ skills show diminishing returns and comprehensive documentation hurts performance.
- Flat skill execution overloads context and forces agents to infer skill selection, ordering, and conditions as task complexity grows.
- GraSP compiles retrieved skills into typed DAGs with explicit precondition–effect dependencies, enabling causal execution and local repair from O(N) to O(dh).
- Its four stages retrieve skills, compile a verified DAG, execute with node-level checks, and repair failures locally, with reactive fallback when confidence is low.
- +19 points reward and 41% fewer environment steps are achieved against the strongest baseline across four benchmarks and eight backbones.
- GraSP identifies missing compilation between retrieval and execution as the root cause of flat-sequence brittleness.
2 The GRASP Architecture
The GRASP architecture combines memory-conditioned retrieval, typed DAG compilation, verified execution, and locality-bounded repair. Its graph representation makes dependencies explicit while preserving verified progress during failures.
- The task setting gives an LLM agent a goal, initial state, typed skill library, and experience memory for interactive execution.
- A GraSP is an acyclic, reachable, goal-complete, executable DAG whose edges are typed as state, data, or order dependencies.
- Flat sequences are a special case, while DAGs support parallel branches, typed dependencies, bounded failure propagation, and pruning of redundant skills.
- Retrieval fuses semantic matching with successful episodic experience, then selects a focused top-M skill subset and computes calibrated confidence.
- Compilation validates invocations, infers typed edges, resolves cycles by removing low-confidence soft edges, and attaches verifiers.
- Execution traverses the DAG topologically, checks preconditions and postconditions, and marks successful nodes verified before proceeding.
- Five typed repair operators modify failed nodes or local structure while preserving DAG validity and unaffected verified nodes.
- Repair is restricted to an h-hop neighborhood and bounded patch size, escalating to global replanning or ReAct when local repair fails.
3 Experiments
Across four interactive benchmarks and eight LLM backbones, GRASP consistently improves performance and execution efficiency over baseline agents. Ablations and stress tests indicate that DAG compilation, local repair, and structured orchestration are especially valuable as tasks lengthen or retrieved skills become excessive or lower quality.
- Main results: GRASP outperforms every baseline in all 48 model–split cells, averaging +12.7 points over ExpeL and reducing environment steps by approximately 24% versus ReAct.The best-case step reduction reaches 41%, with gains spanning reasoning-focused, general-purpose, and open-weight models.
- Main results: On ALFWorld, GRASP uses 10.2–18.9 steps per episode versus 14.8–23.3 for ReAct, while ScienceWorld long-horizon unseen tasks reach a 41% reduction.For Gemini 2.5 Pro on ScienceWorld, steps decrease from 19.1 to 11.3.
- Component analysis: DAG compilation is the most critical component, while replacing local repair with global replanning loses 3.2/3.1 points.Experience memory, DAG compilation, local repair, and routing each contribute positive ablation gains; compilation filters irrelevant skills and exposes dependency order.
- Graph structure: GRASP’s advantage over ExpeL grows from approximately 6% on short tasks to approximately 18% on long tasks as local repair limits failures to affected subgraphs.With typical out-degree d≈2 and repair radius h=2 on ALFWorld, the affected subgraph remains four to five nodes rather than scaling with total plan length.
- Graph structure: Typed repair recovers from precondition failures at 84.2% versus 61.8% for global replanning and leads by approximately 16% on postcondition failures.Typed edges identify why a node failed, enabling targeted recovery of upstream dependencies instead of rediscovering the full chain.
- Orchestration over volume: Flat execution peaks around M=3 and declines with more skills, whereas GRASP remains above flat-at-optimum at M=8 and loses approximately 5% versus approximately 9% under quality degradation.Compilation filters disconnected skills, while verification and typed repair support graceful degradation.
4 Related work
Prior work equips agents with reusable skills, structures reasoning or retrieval, and supports recovery, but existing approaches do not combine these capabilities for LLM-based skill invocation with environmental effects.
- Skill-based agents and skill ecosystems: Skill-based agents retrieve reusable behaviors from libraries, while experience-driven methods improve selection through episodic insights or retries.
- Graph-structured reasoning and execution: Graph-of-Thought and related approaches structure internal reasoning traces, whereas GraSP targets executable skill graphs with environmental side effects.
- Graph-structured reasoning and execution: Classical planning methods provide structured execution and recovery, but they are not designed for LLM skill invocation with natural-language preconditions and effects.
5 Conclusion
GraSP addresses the shift from skill availability to orchestration by compiling retrieved skills into verified typed DAGs and repairing failures locally. Across four benchmarks and eight backbones, it achieves the best performance in every configuration, with stronger advantages as tasks become more complex.
- GraSP compiles flat skill sets into typed DAGs with explicit precondition–effect dependencies, verifies nodes during execution, and uses five typed operators for local failure repair.
- Across four interactive benchmarks and eight LLM backbones, GraSP achieves the best performance in every configuration and reduces execution steps.
- GraSP’s advantages grow monotonically with task complexity and remain robust to skill over-retrieval and skill quality degradation.
- The conclusion identifies structured orchestration, rather than larger skill libraries, as the key to reliable long-horizon agent execution.
6 Limitations and discussion
GraSP is constrained by its acyclic graph assumption and has so far been demonstrated only in text-based interactive environments. Its formal repair machinery imposes validity, typing, verification, and locality constraints on graph patches.
- The DAG assumption excludes cyclic execution patterns, so iterative refinement may require loop constructs or DAG unrolling.
- GraSP is demonstrated on four text-based interactive environments, while multimodal, API-based, and multi-agent extensions remain future work.
- A valid repair patch must remain acyclic, use library skills, type-check arguments, verify affected nodes, preserve unaffected verified ancestors, and stay within node and edge budgets.
C Ablation experiment design and hyperparameters
The experiments use shared default hyperparameters across all eight LLM backbones and four benchmarks, with sensitivity analyses sweeping a subset of them. The local repair procedure tests operators and accepts only valid GraSP patches.
- Hyperparameters: Sensitivity analyses sweep a subset of the default hyperparameters.
- Local graph repair: Local graph repair iterates over repair operators and returns a patch only when it satisfies GraSP validity conditions.
- Hyperparameters: Default hyperparameter values are shared across all eight LLM backbones and four benchmarks unless otherwise stated.
C.2 Component ablations
The ablations isolate the contributions of memory, DAG structure, local repair, confidence routing, and global replanning. Together, they test how each component affects GraSP execution and recovery.
- Removing experience memory isolates the contribution of episodic grounding in skill retrieval.
- Executing retrieved skills as a flat sequence removes dependency tracking and partial execution provided by the typed DAG.
- Disabling local repair forces failures into global replanning or ReAct fallback, isolating locality-bounded recovery.
- Removing confidence routing always executes GraSP, testing whether adaptive control improves robustness.
- Global replanning discards and recompiles the entire graph after any failure under the same repair budget, directly contrasting global and local repair.
C.3 Sensitivity analyses
The sensitivity analyses vary routing thresholds, repair budgets, memory size, and skill-library quality to test robustness and resource trade-offs.
- Varying τlow and τhigh measures how confidence thresholds affect success rate and fallback frequency.
- Repair budgets Rmax ∈{0, 1, 2, 3, 5} are evaluated using success rate and average steps to identify repair investment effects.
- Varying memory size k ∈{0, 1, 3, 5, 10} tests its contribution through retrieval confidence and downstream success.
- Removing 25% or 50% of skills tests GraSP’s robustness to degraded skill-library quality against baselines.
D Per-task-type breakdown
GraSP improves performance across task types in ALFWorld and ScienceWorld, with especially strong benefits on multi-step tasks that use structured execution and repair.
- ALFWorld: GraSP improves across all 6 ALFWorld task types, with the largest gains on multi-step Clean and Heat tasks.
- ScienceWorld: GraSP consistently improves on ExpeL across 6 representative ScienceWorld categories, especially multi-step Heating and Mixing procedures.
E Case study: heating a potato in ALFWorld
The ALFWorld case study shows GraSP compiling retrieved skills into a dependency-aware execution graph, detecting a failed heating precondition, and repairing locally. It completes the task in 8 steps, compared with ReAct’s 18 steps and roughly 38% failure rate on Heat tasks.
- Retrieval: Memory-conditioned retrieval returns four candidate skills with confidence cret = 0.82 for the potato-heating task.
- DAG Compilation: DAG compilation links find→pick-up by state, pick-up→heat by data, and heat→place by state dependencies.
- Execution with failure and repair: Execution verifies each node’s preconditions and postconditions, then invokes local repair when a check fails.
- Execution with failure and repair: The heat-object action fails because the microwave is closed, triggering INSERTPREREQ to add open-receptacle before heating.
- Outcome: 8 total steps complete the task after one inserted node, while ReAct requires 18 steps and has SR 61.4% on Heat tasks.
- Implementation: The compilation prompt represents the task as a DAG of subtasks with skills, action steps, postconditions, and conditional branches.
- Implementation: The repair prompt diagnoses the failed step, selects an operator, and outputs a repaired procedure while preserving progress.
- Broader impacts: The framework describes structured and verifiable execution as potentially supporting interpretability and controllability, without introducing new harmful capabilities.