💬 NLP

SkillGraph: Skill-Augmented Reinforcement Learning for Agents via Evolving Skill Graphs

The paper proposes SKILLGRAPH, a framework that represents skills as nodes in an evolving directed graph to enable large language model agents to retrieve ordered skill subgraphs for compositional tasks, thereby improving both library maintenance and state-of-the-art performance in reinforcement learning.

Original authors: Xiaoyuan Li, Moxin Li, Keqin Bao, Yubo Ma, Wenjie Wang, Dayiheng Liu, Fuli Feng

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xiaoyuan Li, Moxin Li, Keqin Bao, Yubo Ma, Wenjie Wang, Dayiheng Liu, Fuli Feng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Flat List" vs. The "Recipe Book"

Imagine you are teaching a robot butler how to cook a complex meal.

Old Way (Flat Libraries): You give the robot a giant, flat list of 1,000 tips. It searches the list for keywords. If you ask it to "make a sandwich," it might find tips like "get bread," "get cheese," and "use a knife." But the list doesn't tell the robot which tip comes first, or that you can't put cheese on the bread before you get the bread. The robot gets confused, tries things in the wrong order, and fails.
The Paper's Solution (SKILLGRAPH): Instead of a flat list, the robot keeps a structured map (a graph). In this map, "Get Bread" is connected to "Put Cheese" with an arrow saying "Do this after." It knows that "Use Knife" helps "Cut Cheese," and that "Open Fridge" is a prerequisite for "Get Cheese."

How SKILLGRAPH Works: The Three-Step Loop

The paper proposes a system where the robot's "brain" (the policy) and its "skill map" (the graph) grow and improve together in a closed loop. Think of it like a student learning to play a video game while simultaneously writing the game's strategy guide.

1. Building the Map (Graph Construction)

The robot tries to solve tasks. Sometimes it wins, sometimes it loses.

The Teacher: A smart "Teacher AI" watches these attempts.
Distilling Skills: The Teacher turns successful attempts into short, reusable "skills" (like "Check the microwave"). It turns failures into lessons on what not to do.
Drawing Arrows: The Teacher doesn't just write the skills down; it draws arrows between them. It notes: "You must Pick Up the object before you can Heat it." It creates a web of connections showing which skills depend on others.

2. Reading the Map (Graph-Aware Retrieval)

When the robot faces a new task, it doesn't just search for keywords. It travels through the map.

Seed Selection: It finds the starting point (e.g., "I need to heat something").
Backward & Forward Travel: It looks backward to see what steps are needed before this (e.g., "I need to find the object first") and forward to see what comes after (e.g., "Then I need to place it").
The Ordered List: It pulls out a perfectly ordered list of steps, from simple to complex, ensuring the robot never tries to do step 5 before step 1.

3. Updating the Map (Graph Evolution)

This is the magic part. The map isn't static; it changes as the robot learns.

Fixing Mistakes: If a skill keeps failing (like "Open the fridge" but the robot always hits the wall), the system marks it as "Deprecated" (trash it).
Adding New Skills: If the robot fails because it doesn't know how to "Check the temperature," the Teacher invents a new skill for that and adds it to the map.
Merging & Splitting: If two skills are basically the same, the system merges them. If one skill is too vague, it splits it into two clearer ones.
Strengthening Paths: If a specific path on the map leads to a win, the system makes that path "thicker" (stronger) so the robot is more likely to use it next time.

The "Level Up" System (Progressive Unlocking)

Imagine a video game where you can't fight the final boss until you've mastered the basic sword moves.

SKILLGRAPH organizes skills into Levels.
Level 0: Basic skills (e.g., "Move forward").
Level 1: Intermediate skills (e.g., "Pick up object").
Level 2: Complex skills (e.g., "Cook a meal").
The robot is locked out of Level 2 skills until it proves it is good at Level 1. This prevents the robot from getting overwhelmed by complex instructions before it understands the basics.

What the Results Show

The researchers tested this on three types of challenges:

ALFWorld: A text-based house where the robot has to clean, cook, and organize.
WebShop: A simulated online store where the robot has to search for and buy specific items.
Search QA: Answering tricky questions that require looking up information in multiple steps.

The Outcome:

SKILLGRAPH beat almost every other method, including very smart "closed-source" models (like GPT-4o) and other memory-based systems.
It was especially good at complex tasks that required chaining many steps together.
It learned faster and made fewer mistakes because it didn't have to "re-invent the wheel" every time; it just followed the updated map.

In a Nutshell

SKILLGRAPH is a system that stops treating an AI's experience as a messy pile of notes. Instead, it organizes experience into a living, breathing map of skills. As the AI gets better, the map gets smarter, adding new paths, removing dead ends, and teaching the AI exactly which steps to take and in what order. It's the difference between giving a student a stack of random flashcards versus giving them a well-organized textbook that updates itself as they learn.

Technical Summary: SKILLGRAPH

Problem Statement

Large Language Model (LLM) agents have demonstrated capabilities in complex interactive tasks such as web navigation and embodied manipulation. However, current agents often treat tasks as isolated episodes, failing to learn from past successes or failures even when encountering structurally similar problems. While existing approaches utilize skill libraries to store reusable knowledge units, these libraries typically function as flat collections where skills are stored as independent entries and retrieved solely based on semantic similarity.

This flat organization presents two critical limitations for compositional tasks:

Non-compositional Retrieval: Complex tasks often require an ordered sequence of skills with specific dependencies (e.g., heating an object before placing it). Flat retrievers can identify relevant skills but fail to indicate their execution order or prerequisite relationships.
Unstructured Maintenance: Without explicit structural cues, flat libraries lack mechanisms to determine when skills should be merged, split, or removed, making it difficult to manage redundancy or evolve the library alongside the agent's improving policy.

Methodology: SKILLGRAPH

The authors propose SKILLGRAPH, a framework that organizes reusable skills into a structured, directed dependency graph and co-evolves this graph with the agent's policy through Reinforcement Learning (RL). The framework operates in a closed loop comprising three primary stages:

1. Graph Construction

The system distills skills from agent trajectories (both successful and failed) using a teacher language model.

Nodes: Represent skills categorized as either general (domain-independent strategies) or task-specific. Each node tracks usage counts and empirical success rates.
Edges: Typed edges explicitly model relationships between skills:
- Prerequisite ( $A \to B$ ): Skill $A$ must be applied before $B$ .
- Enhances ( $A \to B$ ): A general skill improves the effectiveness of a task-specific skill.
- Co-occurs ( $A \leftrightarrow B$ ): Skills frequently appearing together in successful episodes.
Levels: Nodes are assigned topological levels based on dependency hierarchies (Level 0 for foundational skills with no prerequisites).

2. Graph-Aware Retrieval

Instead of retrieving a set of isolated skills, the system retrieves a dependency-ordered subgraph to guide multi-step decision-making.

Seed Selection: Identifies task-relevant entry points (general skills and task-matched skills) from the currently "unlocked" active set.
Graph Expansion:
- Backward Expansion: Traverses incoming prerequisite edges to recover foundational skills.
- Forward Expansion: Uses beam search to explore outgoing edges, prioritizing paths with high edge weights.
Topological Ordering: The retrieved nodes are sorted topologically to produce a coherent skill sequence that mirrors the logical flow of sub-tasks (simple to complex).

3. Graph Evolution

The skill graph is dynamically updated during training based on trajectory-level feedback, ensuring the library adapts to the agent's growing competence.

Node-Level Adaptation:
- Insert: Generates new skills to address specific failure modes identified in trajectories.
- Merge: Combines redundant skills with high neighborhood overlap.
- Split: Decomposes overly broad skills that show moderate success rates despite high usage.
- Deprecate: Removes skills that are frequently retrieved but consistently fail.
Edge-Level Adaptation:
- Reinforcement: Increases weights of edges traversed in successful trajectories.
- Discovery: Adds new co-occurrence edges when skills appear together in success.
- Decay & Pruning: Applies multiplicative decay to edge weights and removes weak edges to prevent stale relations.
Progressive Unlocking: Implements a curriculum where higher-level skills are only activated once the average success rate of the current foundational level exceeds a threshold.

Policy Optimization

The agent policy is optimized using GRPO (Group Relative Policy Optimization). The policy is conditioned on the task description and the retrieved, ordered skill sequence. The system minimizes a clipped surrogate objective with a KL penalty anchored to a reference policy initialized via Supervised Fine-Tuning (SFT).

Key Contributions

Graph-Structured Skill Formulation: The paper introduces a novel formulation where skills are connected by explicit prerequisite, enhancement, and co-occurrence relations, moving beyond flat semantic retrieval.
SKILLGRAPH Framework: A closed-loop system enabling dependency-aware skill retrieval and structured skill updates (insertion, merging, splitting) during RL training.
Empirical Validation: Extensive experiments demonstrating that structured skill graphs improve sample efficiency and performance on complex, multi-step tasks compared to flat memory-augmented RL methods.

Experimental Results

The framework was evaluated on ALFWorld (embodied manipulation), WebShop (web navigation), and seven search-augmented QA benchmarks.

ALFWorld & WebShop: SKILLGRAPH achieved state-of-the-art performance, significantly outperforming closed-source LLMs (e.g., GPT-4o, Gemini-2.5-Pro) and prompt-based/memory-augmented baselines. Notably, it surpassed the strongest prior method, SkillRL, by 11.7 points on WebShop. The gains were most pronounced in subtasks requiring strict ordering (e.g., "Clean" and "Heat" in ALFWorld).
Search-Augmented QA: Trained on NQ and HotpotQA, SKILLGRAPH generalized zero-shot to five unseen datasets (TriviaQA, PopQA, 2Wiki, MuSiQue, Bamboogle), achieving the highest average performance (48.9) among all baselines.
Ablation Studies: Removing graph-aware retrieval caused the largest performance drop on ALFWorld (-31.2%), confirming the necessity of ordered skill sequences. Removing graph evolution had the largest impact on WebShop (-14.1%), highlighting the value of a dynamically refining skill set.
Efficiency: The graph-guided retrieval maintained shorter prompt lengths compared to flat retrieval, improving inference cost and signal-to-noise ratio.

Significance and Claims

The paper claims that SKILLGRAPH addresses the core limitations of flat skill libraries by enabling compositional planning through dependency-aware retrieval and principled evolution through structured updates. The authors assert that explicitly modeling inter-skill relations allows agents to:

Transfer compositional knowledge from simpler tasks to more complex ones.
Reduce redundant exploration by providing structured guidance.
Continuously refine both the skill library and the agent policy in a mutually reinforcing loop.

The work positions itself as a step toward agents that can accumulate structured knowledge from experience, improving sample efficiency and reliability in domains like household assistance and information retrieval. The authors acknowledge limitations regarding the reliance on a strong teacher model for graph operations and the current confinement to single-environment training, suggesting cross-environment transfer and lightweight self-distillation as future directions.