Source-linked AI summary
SkillDAG: Self-Evolving Typed Skill Graphs for LLM Skill Selection at Scale
Tong Bai, Zhenglin Wan, Pengfei Zhou, Xingrui Yu, Yang You, Ivor W. Tsang
TL;DR
Large skill libraries make selection difficult because similarity matching can miss prerequisites and include redundant or conflicting skills. SkillDAG exposes and evolves a typed relation graph during execution, and reports improved task reward and intrinsic retrieval over Graph of Skills while remaining robust as the skill pool expands. Its long-horizon behavior under single-observation self-evolution remains open.
Problem
Flat retrieval over large skill libraries can omit structurally necessary skills and select redundant or interfering ones because similarity matching does not represent inter-skill relations.
Method
SkillDAG gives the LLM an agent-callable typed graph interface with separate matches, neighbors, and conflicts, plus execution-backed propose-then-commit graph edits.
Results
SkillDAG improves MiniMax-M2.7 reward over Graph of Skills by +12.8 points on ALFWorld and +8.6 points on SkillsBench, while SkillsBench Ret@K rises from 65.5 to 78.2 under matched queries.
Takeaways & Limitations
The gains are associated with retrieval that remains robust under 10× pool expansion and online edits that add structure without evicting prior hits.
Takeaways & Limitations
Long-horizon behavior from single-observation self-evolution remains an open question.
Abstract
from arXiv · showhide
As LLM agents adopt large skill libraries, selecting the right subset becomes a structural problem rather than a similarity-matching one: skills depend on, conflict with, specialize, or duplicate one another, a structure invisible to both full enumeration and embedding similarity. We present SkillDAG, which models inter-skill relationships as a typed directed graph and exposes it to an LLM agent as an inference-time, agent-callable structural retrieval interface, queried and evolved during execution rather than baked into a fixed retrieval pipeline: each search returns vector matches, typed-edge neighbors, and conflict signals, and a propose-then-commit protocol lets the agent register execution-backed edges so the graph accumulates structure across episodes. On ALFWorld and SkillsBench with MiniMax-M2.7, SkillDAG reaches 67.1% success and 27.3% reward, exceeding the strongest reported Graph-of-Skills baseline by +12.8 and +8.6 points; the advantage ports to gpt-5.2-codex, and intrinsic SkillsBench Ret@K rises from 65.5 to 78.2 under matched queries. These gains trace to isolable mechanisms: candidate ranking that stays robust as the pool grows 10x where a fixed seeding-diffusion pipeline degrades, and set-monotone online edits that enlarge ground-truth recall without evicting prior hits.
1. Introduction
SkillDAG frames skill selection as a structural problem because flat retrieval can omit prerequisites while including redundant or interfering skills. It exposes a typed graph to the LLM for direct reasoning and online evolution, achieving strong benchmark results across ALFWorld and SkillsBench.
- Motivation: Flat retrieval can omit functionally necessary prerequisites while selecting redundant or interfering skills because similarity matching hides inter-skill structure.These failures become more consequential as libraries grow and retrieval replaces manual curation.
- Approach: SkillDAG exposes typed relations through an agent-callable interface, replacing a fixed graph-ranking policy with structural evidence that the LLM reasons over directly.The interface supports search, inspection, and graph editing during execution.
- Approach: The method combines an online propose-then-commit edit protocol with a two-view cold-start constructor that recovers cross-functional pairs missed by flat self-similarity.The graph accumulates execution-backed structure across episodes.
- Main results: 67.1%/93.6% ALFWorld success and 27.3%/36.8% SkillsBench reward are reported for SkillDAG across MiniMax-M2.7 and gpt-5.2-codex.The reported outcomes cover both benchmarks and both backbones.
2. Related Work
Prior work covers tool and skill retrieval, graph-based organization, structured RAG, self-evolving agents, and agent benchmarks, but runtime exposure of inter-skill structure remains limited. SkillDAG is positioned against this landscape as an editable, agent-facing alternative to fixed retrieval.
- Skill and tool libraries: Graph-based systems organize skills or repair execution DAGs, but prior work does not expose inter-skill structure to the agent at runtime.SkillNet targets developer navigation, while CUA-Skill and GraSP focus on executable or intra-task DAG structure.
- Skill retrieval and structured RAG: GraphRAG, HippoRAG, LightRAG, and GeAR inject graph structure into retrieval or expansion, while Graph of Skills remains the closest fixed-bundle skill-retrieval baseline.Graph of Skills uses reverse-aware Personalized PageRank and passes an opaque context bundle to the agent.
- Self-evolving agents: Self-evolving agents such as ReAct, Reflexion, Self-Refine, ExpeL, AutoAct, and Agent-Pro reuse reasoning, corrections, experiences, or policies, but the cited work does not establish SkillDAG’s inter-skill graph interface.The related work distinguishes experience reuse from graph-based skill-relation editing.
- Agent benchmarks: ALFWorld and SkillsBench represent evaluation settings spanning embodied tasks and containerized code-generation tasks, where retrieval over growing capability surfaces is measurable.The paper places these benchmarks within a broader landscape of agent environments and tool-use settings.
3. Method
SkillDAG makes typed graph structure an agent-callable retrieval interface rather than an opaque ranking substrate. It separates semantic matches, typed neighbors, and conflicts, initializes relations with two embedding views, and evolves them through evidence-backed edits under structural constraints.
- 3.2. Typed graph: SkillDAG treats typed relations as operational semantics: prerequisite and specialization edges organize progressions, composition and similarity surface alternatives, and conflicts mark combinations to avoid.Conflicts are used for pruning rather than traversal, while depends_on and specializes form an acyclic directed backbone.
- 3.3. Agent-callable retrieval: Search returns semantic matches, typed neighbors, and conflicts as separate evidence channels instead of one fused ranked bundle.This lets the agent selectively load fields, re-query during execution, and retain a reasoning trace for selections or exclusions.
- 3.4. Cold-Start Graph Construction: Cold-start construction embeds each skill in self and needs views, applies an adaptive cosine threshold, and uses an LLM classifier to materialize static relation types.The needs view recovers functional bridges that self-description similarity can miss.
- 3.4. Cold-Start Graph Construction: conflicts_with is reserved for online evolution because co-use harm cannot be inferred from static text alone.Cold-start graphs are therefore necessarily incomplete and require execution evidence for some relations.
- 3.5. Online Graph Evolution: The propose-edge dry run previews pair history before edit-edge commits an add, deletion, or retyping with a reason and execution trace.Commits are agent-driven and must satisfy invariants including acyclicity, non-contradiction, and reversibility.
4. Experiments
Experiments compare SkillDAG with full-library prompting, vector retrieval, and GoS across ALFWorld and SkillsBench, then isolate retrieval scale and online-edit effects. SkillDAG improves task reward and retrieval quality, transfers edits to held-out episodes, and preserves recall as the skill pool expands.
- 4.2. Main Results: 67.1% and 27.3% are SkillDAG’s MiniMax-M2.7 rewards on ALFWorld and SkillsBench, exceeding GoS by +12.8 and +8.6 points, respectively.On gpt-5.2-codex, ALFWorld ties GoS at 93.6% and SkillsBench improves from 34.4 to 36.8 (+2.4).
- 4.3. Scale and Edit-Transfer Ablations: 67.1/65.0/67.1% for MiniMax-M2.7 and 92.3/90.7/93.6% for gpt-5.2-codex across train/test-initial/test-edited show edit transfer to held-out episodes.Test-edited recovers the train number after edits are disabled, supporting persistence of committed structure.
- 4.3. Scale and Edit-Transfer Ablations: 1.984 versus 1.915 mean ground-truth skills per query follows 27 single-observation commits, while zero queries lose a previously retrieved ground-truth skill.The untruncated union of matches and BFS neighbors makes the edit effect set-monotone for recall, not for context-budget performance.
- 4.3. Scale and Edit-Transfer Ablations: SkillDAG’s retriever remains ahead of GoS at every pool scale and loses only 3.5 Ret@5 points across a 10× expansion from 200 to 2000 skills.The largest reported margins are +16.1/+17.2/+17.2 at 200 skills and +13.8/+16.1/+16.3 at 2000 for Ret@5/Ret@1/MRR.
5. Conclusion
SkillDAG exposes typed graph structure as an agent-callable interface rather than hiding it inside a fixed ranking policy. The agent can route with structural evidence, while retrieval and online edits support the reported reward and scale gains.
- 5. Conclusion: SkillDAG exposes search, show, propose-edge, and edit-edge so the LLM reasons over typed relations instead of receiving an opaque graph-ranked bundle.The interface lets the agent load only needed neighbors and skill bodies.
- 5. Conclusion: MiniMax-M2.7 reward rises from 54.3 to 67.1 on ALFWorld and from 18.7 to 27.3 on SkillsBench against GoS.Matches-field retrieval wins every reported pool-scale metric, supporting interface-based routing over opaque policy ranking.
Limitations
The online self-evolution protocol can commit an edge from a single execution observation, subject to structural guardrails rather than statistical confidence thresholds. Long-horizon behavior under this regime remains open.
- Limitations: Single-observation edge commits are permitted under acyclicity, non-contradiction, and reversibility guardrails, leaving long-horizon self-evolution unresolved.The paper identifies this behavior as a direction for future work.
A. End-to-End Algorithms
The end-to-end workflow first constructs a typed cold-start graph, then runs an online episode loop in which the agent retrieves, acts, observes, and conditionally commits edits. The algorithms enforce typed relations and commit-time invariants while maintaining an append-only, reversible history.
- A. End-to-End Algorithms: Algorithm 1 builds the initial graph by combining self-description and need-summary embeddings, adaptive candidate thresholds, and pair-classifier edge typing.The classifier assigns depends_on, specializes, composes_with, similar_to, or none; conflicts_with is reserved for online edits.
- A. End-to-End Algorithms: Algorithm 2 loops over tasks and episodes, using agent search/show calls before actions and proposing an edit only when execution evidence supports it.An edit is committed only if edit-edge passes the structural invariants, then it is appended to a reversible history log.
B.1. ALFWorld Failure Modes
The 30-task ALFWorld pilot’s 11 failures fell into grounding loops, model-specific output leakage, and exhaustion of the 30-step budget.
- Failure categories: 8/11 failures were tight loops in which agents repeatedly acted on objects outside the current room without navigating.The graph supplied the correct procedural skills, but failures occurred when agents could not ground instructions in valid environment actions.
- Failure categories: 1/11 failures involved MiniMax </think> tag leakage that caused reasoning tokens to enter action output and produced hallucinated observations.The passage characterizes this as a model-specific artifact rather than a skill-selection failure.
- Failure categories: 2/11 failures exhausted the 30-step budget during otherwise correct exploration of longer multi-subtask sequences.Cleaning an object, for example, requires locating, picking up, washing, and navigating between locations.
- Operational definitions: The typed edge taxonomy distinguishes prerequisites, composition, redundancy, conflict, and specialization using operational success-rate tests.depends_on is transitive, composes_with and conflicts_with are symmetric but non-transitive, similar_to marks substitutable redundancy, and specializes is transitive within specialization hierarchies.
D. Reproducibility Details
Reproducibility details fix search, model, embedding, budget, logging, and cold-start settings across the ALFWorld and SkillsBench evaluations.
- Search budgets: Search uses K=5 vector matches and bidirectional BFS neighbors through depth D=2, with agents choosing the number and timing of calls.Query strings are selected on the agent’s own schedule.
- Models and embeddings: Agent runs use MiniMax-M2.7 and gpt-5.2-codex, while cold-start pair classification uses gpt-5-nano and runtime queries use text-embedding-3-large.The embedding configuration matches each Graph-of-Skills workspace.
- Step and attempt budgets: ALFWorld episodes allow 30 steps and 2 attempts, while SkillsBench uses 1 attempt for MiniMax retrieval replay and 2 attempts for main reward and codex retrieval evaluations.The codex retrieval row replays agent queries under the same 2-attempt budget.
- Online edit logging: Each accepted graph edit logs its origin, natural-language reason, and supporting task ID in edge metadata.This records whether an edit came from cold-start or online evidence.
- Cold-start cost: At scale 1000, cold-start construction requires approximately 200 batched gpt-5-nano calls plus one embedding call per skill for each of two views.The views are e_self and e_needs.
E. Worked Example Subgraph
The worked subgraph illustrates how SkillDAG separates similarity matches, typed neighbors, and conflicts while supporting inspectable and auditable graph edits.
- Search interface: Matches return the top-K skills ranked by cosine similarity between the query embedding and each node’s pre-computed embedding.This is the vector-retrieval channel of the interface.
- Search interface: Neighbors are found by bidirectional BFS over specializes, composes_with, depends_on, and similar_to edges up to depth D, with typed paths and distances exposed.conflicts_with edges are excluded from traversal, and already matched skills are omitted.
- Search interface: Conflicts returns one-hop conflicts_with edges separately because they identify skills that should not be co-selected.Conflict expansion is not transitive.
- Agent-facing semantics: The interface exposes separate matches, neighbors, and conflicts channels so the agent can reason over structural evidence instead of a single fused ranking.Edges retain explicit types and reasons, documenting selection and exclusion decisions.
- Graph mutation: propose-edge previews an edit and related history, while edit-edge commits an auditable entry containing task ID, reason, and timestamp.The protocol separates inspection from mutation before updating the graph.
- Graph initialization: Cold-start candidates use self-description and prerequisite-oriented needs embeddings, with adaptive thresholding before relation classification into depends_on, composes_with, or none.Pairs classified as none are discarded; retained pairs become cold-start edges with the LLM’s reason.