Dependency-ordered retrieval beats flat similarity search by 31 points on ALFWorld

Notes on SkillGraph: Skill-Augmented Reinforcement Learning for Agents via Evolving Skill Graphs (arXiv:2605.12039) — Xiaoyuan Li, Moxin Li, Keqin Bao, Yubo Ma, Wenjie Wang, Dayiheng Liu, Fuli Feng · May 2026

Note published July 23, 2026 · written by SkillFed’s research pipeline from the paper above · how these notes are made

AI-assisted notes · reviewed by SkillFed Skill retrieval

SkillGraph reframes an agent's skill library as a directed graph instead of a flat, similarity-ranked list. Each node is a skill distilled by a teacher model (OpenAI o3) from the agent's own successful and failed trajectories; each typed edge encodes one of three relations — prerequisite, enhancement, or co-occurrence — carrying a weight that strengthens or decays with experience. Given a new task, the system doesn't just pull the nearest skills by embedding distance: it seeds from task-relevant nodes, walks backward through prerequisite edges (depth 2) to recover what has to happen first, walks forward through a width-3 beam to find what builds on it, then topologically sorts the result into an ordered subgraph capped at eight skills — what the paper calls graph-aware retrieval. That ordered plan conditions the policy, and the graph keeps evolving during GRPO reinforcement learning: new skills get inserted from failures and near-duplicates get merged, while skills that succeed inconsistently get split apart and chronic failures get deprecated.

Across ALFWorld and WebShop, SkillGraph posts 90.6% and 84.4% success. That clears a plain GRPO baseline (77.6% / 66.1%), edges out SkillRL — the closest memory-augmented RL system, at 89.9% / 72.7% — and far outpaces prompting GPT-4o or Gemini-2.5-Pro directly (48.0% / 60.3% on ALFWorld). Trained on only two QA datasets, it also generalizes zero-shot to five more search-augmented QA benchmarks, averaging 48.9 across all seven versus 47.1 for SkillRL and 43.1 for EvolveR, the other reported baseline. The ablation is the clearest signal: swap the ordered graph retrieval back to flat similarity lookup over the identical skill pool, and ALFWorld success collapses to 59.4%, a 31-point drop that dwarfs the hit from removing the graph's typed structure (-0.7 points) or its evolution mechanism (-12.4 points). The skills sitting in the library aren't what's driving the gain here — the order they get served in is.

Key numbers

ALFWorld success rate	90.6%
WebShop success rate (vs. 72.7% prior best)	84.4%
7-task QA average score	48.9
ALFWorld drop with graph-aware retrieval removed	-31.2 pts (90.6% to 59.4%)
Gap over GPT-4o on ALFWorld	+42.6 pts

What this means for skill authors

For skill authors, this argues the atomic unit of a good library isn't a single self-contained skill — it's a skill plus its stated dependencies. If a skill silently assumes a precondition, an agent can't compose it reliably, and a similarity-only index has no way to signal that a prerequisite skill needs to run first. The practical takeaway for anyone writing a SKILL.md: state what a skill needs before it and what it enables afterward, even informally. SkillGraph's teacher model has to infer that structure from trajectories after the fact, at real inference cost — authors who declare it upfront skip that tax entirely.

For skill users and the agents calling them, retrieval quality is the lever, not skill count. A library stocked with strong skills but searched by similarity alone behaves like this paper's flat-retrieval ablation (59.4%), not its graph-aware one (90.6%) — despite drawing on the exact same skills. That's the argument for pairing semantic matching with structural metadata rather than trusting embedding nearest-neighbor search alone: dependency and composition information is precisely what a similarity score discards. It's the same instinct behind SkillFed vetting skills with more than one signal instead of ranking by description similarity alone.

One caveat: this graph is built and evolved within a single environment by a single agent's own trajectories, with a paid frontier model (o3) making every merge, split, and insert call. The paper doesn't test whether a graph grown on ALFWorld transfers to WebShop, so "the graph learns your task" is the accurate reading, not "the graph learns your domain." Treat the numbers as evidence that structured beats flat retrieval within a task family — not as proof that one skill graph would generalize across unrelated tools.

Skills related to this research

wiki-retrieve wiki-retrieve upgrades vault search from page-level to chunk-level granularity, combining contextual prefixes, BM25 sparse retrieval, and dense reranking to reduce retrieval failures. Setup is opt-in with built-in privacy gates: run fully on-machine with synthetic prefixes, or opt into Anthropic API or claude CLI tiers for better context generation.★ 10,007 seedance-recipes Seedance-recipes provides production-ready recipe patterns for video content across genres: product, lifestyle, drama, music video, landscape, commercial, animation, and more. Each recipe preserves core creative constraints while inviting customization of subject, camera, lighting, and sound. Use recipes as proven starting shapes, not rigid templates.★ 5,445 fine-tuning-with-trl This skill teaches post-training techniques for aligning language models to human preferences. It covers supervised fine-tuning, direct preference optimization (DPO), and online reinforcement learning methods like RLOO and GRPO, with complete workflows and practical examples.★ 221,503 fine-tuning-with-trl Fine-tuning with TRL provides post-training methods to align language models with human preferences through multiple approaches. Train models on instruction data with SFT, optimize for preference alignment via DPO without a separate reward model, or run full RLHF pipelines combining supervised fine-tuning, reward modeling, and PPO optimization. GRPO offers memory-efficient online reinforcement learning for resource-constrained setups.★ 11,165

Related notes

References

Li, Li, Bao, Ma, Wang, Liu, Feng — "SkillGraph: Skill-Augmented Reinforcement Learning for Agents via Evolving Skill Graphs", arXiv:2605.12039 (2026)
Shridhar et al. — "ALFWorld: Aligning Text and Embodied Environments for Interactive Learning" (benchmark used)
Yao et al. — "WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents" (benchmark used)
Jin et al. — "Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning" (baseline)
Yao et al. — "ReAct: Synergizing Reasoning and Acting in Language Models" (baseline)