SkillDAG: Self-Evolving Typed Skill Graphs for LLM Skill Selection at Scale

# SkillDAG: Self-Evolving Typed Skill Graphs for LLM Skill Selection at Scale
Source: [https://arxiv.org/html/2606.03056](https://arxiv.org/html/2606.03056)
\\setheadertext

SkillDAG\\correspondingemail\\emailicon[yu\_xingrui@a\-star\.edu\.sg](https://arxiv.org/html/2606.03056v1/[email protected])∗Equal Contribution\.‡Corresponding Author\.

\\teaserfigure

![[Uncaptioned image]](https://arxiv.org/html/2606.03056v1/x1.png)

Figure 1:SkillDAGper\-episode workflow\. The agent issuessearchto obtain a three\-field response \(matches, neighbors, conflicts\), callsshowto fetch any skill body, acts in the environment, and may commit an evidence\-backed graph edit through thepropose\-edge/edit\-edgepair\. Every commit passes acyclicity and non\-contradiction checks with an append\-only log enabling rollback; the updated graph feeds subsequentsearchcalls\. The LLM, not a graph\-ranking policy, decides what to load\.Tong Bai1∗Zhenglin Wan2∗Pengfei Zhou2Xingrui Yu3‡Wangbo Zhao2Yang You2Ivor W\. Tsang3 1Fudan University2National University of Singapore3CFAR

###### Abstract

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 presentSkillDAG, 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: eachsearchreturns 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,SkillDAGreaches 67\.1% success and 27\.3% reward, exceeding the strongest reported Graph\-of\-Skills baseline by\+12\.8\+12\.8and\+8\.6\+8\.6points; the advantage ports togpt\-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 grows10×10\\timeswhere a fixed seeding–diffusion pipeline degrades, and set\-monotone online edits that enlarge ground\-truth recall without evicting prior hits\.

Code and data:[https://github\.com/Ericbai06/SkillDAG](https://github.com/Ericbai06/SkillDAG)

## 1Introduction

Large language model agents increasingly rely on external skill libraries to extend their capabilities beyond the procedural knowledge in model weights\. A skill is a self\-contained package: a unique identifier, a natural\-language description of when it applies, and a body of instructions or code the agent runs when invoked, often with auxiliary scripts and prerequisite notes\[li2026gos\]\. Voyager\[wang2023voyager\], JARVIS\-1\[wang2023jarvis\], and ToolLLM\[qin2024toolbench\]report large gains once an agent is equipped with a curated skill collection\. As collections grow to thousands of entries, the bottleneck shifts from authoring to skill*selection*: which subset to load cannot be decided from a name or embedding alone, and retrieval over large tool collections is itself a measurable failure mode of LLM agents\[shi2025toolret\]\.

Two strategies dominate practice\. Concatenating the whole library is feasible only at small scale: token cost grows linearly and descriptions are lost in an overloaded prompt\[liu\-etal\-2024\-lost\]\. Flat retrieval instead embeds the task and concatenates the top\-KKskills by cosine similarity\[karpukhin2020dpr,reimers2019sentencebert\]or BM25\[robertson2009bm25\]\. Both hide the library’s relational structure: the top match names the task while a functionally necessary prerequisite \(a parser, converter, or setup utility\) is silently omitted; analogous gaps arise from skills that interfere when co\-selected, near\-duplicates that waste context budget, and pairs that jointly enable a capability neither provides alone\. Curation can mask these failures at small scale, but its cost grows with the library\.

Prior work models inter\-skill structure but stops short of letting the LLM reason over it directly\.SkillNet\[skillnet2025\]builds a 500,000\-skill graph used for platform organization rather than runtime routing\. Graph of Skills\[GoS;li2026gos\]runs Personalized PageRank\[page1999pagerank,haveliwala2003topicsensitive\]over a typed skill graph at inference time and reports gains on SkillsBench and ALFWorld, but computes the bundle through a fixed seeding–diffusion–reranking pipeline and hands the agent opaque context: it cannot ask why a skill was chosen, retract a noisy retrieval, or record a relationship the offline pipeline missed\. XSkill\[xskill2025\]and CUA\-Skill\[cuaskill2025\]address skill acquisition and execution respectively, not inter\-skill relations\.

We proposeSkillDAG, built on the inverse design choice: rather than the substrate of a fixed retrieval algorithm, the graph is exposed to the LLM as an inference\-time, agent\-callable structural retrieval interface, on the same footing as the tools the agent already uses for execution\. The LLM, not a graph\-ranking policy, decides how structural evidence should affect execution; the graph in turn accumulates structural knowledge across episodes through evidence\-backed agent edits\.

Our contributions are summarized as follows:

- •We identify that flat retrieval over large skill libraries silently omits structurally necessary skills and concatenates redundant or interfering ones—a failure mode invisible to similarity matching alone\.
- •We proposeSkillDAG, an agent\-callable structural retrieval interface that exposes a typed skill relation graph to the LLM viasearch/show/propose\-edge/edit\-edge, replacing a fixed graph\-ranking policy with structural evidence the agent reasons over directly\.
- •We design an online propose\-then\-commit edit protocol under three structural invariants \(acyclicity, non\-contradiction, append\-only reversibility\) that grows the graph from single\-episode evidence, paired with a two\-view cold\-start constructor that recovers cross\-functional pairs flat self\-similarity misses\.
- •Experiments on ALFWorld\[shridhar2021alfworld\]and SkillsBench\[li2026gos\]with MiniMax\-M2\.7 andgpt\-5\.2\-codexshowSkillDAGreaches 67\.1%/93\.6% ALFWorld success and 27\.3%/36\.8% SkillsBench reward, with intrinsic Ret@K of 78\.2 stable across a10×10\\timesskill\-pool expansion\.

## 2Related Work

#### Skill and tool libraries\.

LLM agents are augmented with external capabilities exposed as tools\[schick2023toolformer,qin2024toolbench,patil2024gorilla\], skills\[wang2023voyager,wang2023jarvis\], code actions\[liang2023codeaspolicies,wang2024codeact\], or grounded primitives\[ahn2022saycan,huang2022innermonologue\]\. As libraries scale, selection rather than authoring becomes the bottleneck: ToolkenGPT\[hao2023toolkengpt\]learns per\-tool embeddings, AnyTool\[du2024anytool\]adds a hierarchical API retriever, CRAFT\[yuan2024craft\]creates and retrieves specialized tool\-sets, and library\-learning methods compress trajectories into documented reusable code\[grand2024lilo\]\.SkillNet\[skillnet2025\]organizes 500K\+ skills as a graph for developer navigation, CUA\-Skill\[cuaskill2025\]models skills as executable DAGs, and GraSP\[chen2026grasp\]adds DAG repair for intra\-task sequencing; none expose inter\-skill structure to the agent at runtime, so flat selection still misses prerequisites and conflicts as the library grows\.

#### Skill retrieval and structured RAG\.

Beyond flat top\-KKRAG\[lewis2020rag\], recent work injects structure: GraphRAG\[edge2024graphrag\]indexes a community graph for offline summarization, HuggingGPT\[shen2023hugginggpt\]composes models by task decomposition over a flat catalog, HippoRAG\[gutierrez2024hipporag\]retrieves by Personalized PageRank over a KG memory, LightRAG\[guo2025lightrag\]maintains an incrementally updated graph index, and GeAR\[shen2025gear\]performs agent\-driven graph expansion\. For tools specifically, Re\-Invoke\[chen2024reinvoke\]rewrites queries for zero\-shot retrieval and ToolGen\[wang2025toolgen\]folds lookup into generation via tool tokens\. Graph of Skills\[GoS;li2026gos\], the closest baseline, builds a typed skill graph offline and retrieves a bundle by reverse\-aware Personalized PageRank that is concatenated into context as opaque text\.SkillDAGinverts two choices: the graph is an agent\-callable structural retrieval interface rather than a fixed retriever’s substrate, and its edges are editable during execution rather than frozen at construction\.

#### Self\-evolving agent\.

ReAct\[yao2023react\]interleaves reasoning\[wei2022cot\]and action, extended by deliberate search\[yao2023tot\]; Reflexion\[shinn2023reflexion\]and Self\-Refine\[madaan2023selfrefine\]add verbal self\-correction; ExpeL\[zhao2024expel\], AutoAct\[qiao2024autoact\], and Agent\-Pro\[zhang2024agentpro\]distill experience into reusable insights or policies\. Closer to skill accumulation, Agent Workflow Memory\[wang2024awm\]induces reusable workflows online, ICAL\[sarch2024ical\]and STE\[wang2024ste\]abstract trajectories into memory, AutoGuide\[fu2024autoguide\]retrieves state\-conditioned guidelines, and OS\-Copilot\[wu2024oscopilot\]accumulates skills in a tool\-rich OS; surveys frame these as non\-parametric self\-evolution\[gao2025selfevolving\]\. Generative Agents\[park2023generative\]and MemGPT\[packer2023memgpt\]manage free\-text memory, and XSkill\[xskill2025\]updates individual skills\. Recent systems also externalize or compress agent execution context: AgentOCR renders interaction history into compact visual memory\[feng2026agentocr\], while CaveAgent treats a persistent runtime as the central state store with runtime\-integrated skill management\[ran2026caveagent\]\. In embodied settings, multi\-memory frameworks similarly structure spatial, temporal, episodic, and semantic experience for long\-horizon interaction\[lei2026robomemory\]\. Our propose/edit\-edge mechanism instead mutates a typed relational structure shared by all future agents, enabling precise, auditable updates\.

#### Agent benchmarks\.

We evaluate on ALFWorld\[shridhar2021alfworld\]and SkillsBench\[li2026gos\], within a landscape spanning cross\-domain tasks\[liu2024agentbench\], web environments\[zhou2024webarena\], general assistants\[mialon2023gaia\], desktop/OS control\[xie2024osworld\], API\-rich apps\[trivedi2024appworld\], tool\-agent\-user dialogue\[yao2024taubench\], and function calling\[patil2025bfcl\]\. All share the pressure point motivatingSkillDAG: retrieval over a growing capability surface is itself a measurable failure mode\[shi2025toolret\]\.

## 3Method

![Refer to caption](https://arxiv.org/html/2606.03056v1/x2.png)Figure 2:A six\-node subgraph from the post\-run ALFWorld graph exercising all five typed relations: cold\-startspecializes/similar\_toedges plus an agent\-registereddepends\_onand a laterconflicts\_withon the same pair\.### 3\.1Overview

SkillDAGstarts from a simple inversion: the typed graph is not hidden inside a fixed retrieval pipeline, but exposed as an agent\-callable interface the LLM can query, inspect, and revise during execution\. This makes graph structure an explicit part of the agent’s decision context rather than an opaque ranking heuristic\. The typed relation graph gives otherwise flat skill libraries operational structure: prerequisite and specialization edges organize reusable progressions, composition and similarity edges surface adjacent skills, and conflict edges mark combinations the agent should avoid\. Thesearch/showinterface turns that structure into action by returning semantic matches, typed neighbors, and conflicts as separate evidence channels while loading full skill bodies only on demand\. To initialize such structure before any episode runs, the cold\-start constructor links skills from two complementary views: what a skill does and what it needs\. Static structure is inevitably incomplete, however, so the online protocol lets the agent propose and commit execution\-backed edits while acyclicity, non\-contradiction, and append\-only reversibility keep the graph from drifting into incoherence\. The formal graph, interface, cold\-start constructor, and online edit protocol are specified in §[3\.2](https://arxiv.org/html/2606.03056#S3.SS2)–§[3\.5](https://arxiv.org/html/2606.03056#S3.SS5), with full pseudocode in Appendix[A](https://arxiv.org/html/2606.03056#A1)\.

### 3\.2Skill Relation Graph Definition

Prerequisites, alternatives, and conflicts collapse onto a single cosine score under the default retrieval baseline \(rank skills by self\-description similarity and concatenate the top\-KK\), so a hard prerequisite and an interchangeable alternative both surface as “high\-cosine neighbors,” even though loading the former unlocks the task while loading the latter wastes context and dilutes the agent’s attention\. To prevent this collapse, we elevate the relation*type*itself to be part of the agent\-facing semantics, so the LLM acts on*what kind of*relation it sees rather than merely*how similar*two skills look\. We instantiate this principle as a typed graph\. Let the skill library be a finite set𝒞=\{s1,…,sn\}\\mathcal\{C\}=\\\{s\_\{1\},\\ldots,s\_\{n\}\\\}of skill packages, wheresis\_\{i\}is also the unique identifier; the graphG=\(V,E,τ\)G=\(V,E,\\tau\)hasV=𝒞V=\\mathcal\{C\}and a typing functionτ\\tauassigning each edge one of five operationally specified types:depends\_on\(A,B\)\(A,B\)marksAAas requiring the prerequisiteBB;specializes\(D,A\)\(D,A\)marksDDas the narrower variant to prefer overAA;composes\_withmarks synergistic co\-use;similar\_tomarks functional redundancy \(pick one\); andconflicts\_withmarks pairs that should not be co\-selected\.

Two operational constraints make this typed graph usable as an agent\-facing interface\.*Conflicts as a pruning signal, not a navigation edge\.*We deliberately excludeconflicts\_withfrom traversal because navigating a conflict edge would actively undermine retrieval by surfacing the very skills the LLM has been told to avoid; the four positive types are walked by the retrieval interface, whileconflicts\_withis only used to exclude co\-selection \(§[3\.3](https://arxiv.org/html/2606.03056#S3.SS3)\)\.*Acyclicity on the backbone\.*We reservedepends\_onandspecializesas the directed backbone whose acyclicity givesSkillDAGits name; the invariant is enforced at commit time \(§[3\.5](https://arxiv.org/html/2606.03056#S3.SS5)\)\. Figure[2](https://arxiv.org/html/2606.03056#S3.F2)shows a six\-node post\-run ALFWorld subgraph exercising all five types\.

![Refer to caption](https://arxiv.org/html/2606.03056v1/x3.png)Figure 3:Cold\-start construction: read the library, embed each skill in two views \(eselfe\_\{\\text\{self\}\}for what it does,eneedse\_\{\\text\{needs\}\}for what it requires\), apply an adaptive cosine threshold, run an LLM pair classifier, and materialize the initial graph\.conflicts\_withis reserved for the online protocol because co\-use harm cannot be inferred from static text alone\.
### 3\.3Agent\-Callable Structural Retrieval Interface

Having typed the edges, we must decide how to expose the graph to the agent at inference time\. The default move in prior graph retrievers is to collapse typed structure back into one ranked bundle, but doing so would undo the work of §[3\.2](https://arxiv.org/html/2606.03056#S3.SS2), hiding from the LLM exactly the distinctions we built the graph to preserve\. We therefore designedsearch\(Figure[1](https://arxiv.org/html/2606.03056#S0.F1)\) as an agent\-callable interface that returns semantic matches, typed neighbors, and conflicts as three separate evidence channels the LLM reasons over independently\.

A singlesearch\(q,K,D\)\(q,K,D\)call returns three fields, each answering a distinct question the LLM would otherwise have to ask separately:matches\(“what is topically close toqq?”\), the top\-KKskills by query–node embedding cosine\[karpukhin2020dpr\];neighbors\(“what does the typed graph attach to those matches?”\), skills reached by bounded breadth\-first traversal of depthDDover the four walkable edge types; andconflicts\(“what should I not co\-load with them?”\), the one\-hopconflicts\_withedges incident to any match\.

We chose to keep these channels separate, rather than fusing them into a single score, because the decomposition gives the agent three capabilities that a ranked bundle cannot offer: it can drop an entire field under a tight context budget \(e\.g\., skipneighborswhen context is scarce\), schedulesearchcalls on its own initiative \(e\.g\., re\-query after partial progress\), and leave a reasoning trace documenting why each skill was selected or excluded\.

### 3\.4Cold\-Start Graph Construction

The interface of §[3\.3](https://arxiv.org/html/2606.03056#S3.SS3)assumes a graph already exists; we now describe how it is first populated, before the agent ever runs\. The obvious choice \(embed each skill’s self\-description and link nearest neighbors\) has a specific failure mode we set out to fix: skills that should be connected often describe different actions, where one provides what another requires\. A cooling skill and a pickup skill, for example, have disjoint self\-descriptions, yet the cooling skill requires “object in hand” produced by the pickup skill\. Self\-description similarity alone systematically misses such cross\-functional pairs, so we designed a two\-view embedding strategy that initializes the graph from staticSKILL\.mdtext while explicitly recovering these bridges\.

The key departure from single\-view retrieval is the second embedding\. For each skillvv,eself​\(v\)e\_\{\\text\{self\}\}\(v\)captures*what a skill does*\(identifier, description, body preview\), whileeneeds​\(v\)e\_\{\\text\{needs\}\}\(v\)captures*what it requires*: an LLM imagines a few invoking tasks and summarizes the shared prerequisites in one sentence \(HyDE\-style\[gao2023hyde\]\), then embeds the summary\.eselfe\_\{\\text\{self\}\}surfaces topical neighbors;eneedse\_\{\\text\{needs\}\}surfaces functional bridges, and a candidate pair appears if either ranking exceeds the adaptive cosine threshold\. An LLM classifier\[zheng2023llmasjudge\]then assigns one of the four static types ornone\. Figure[3](https://arxiv.org/html/2606.03056#S3.F3)traces these stages end to end: read library, embed in two views, threshold, classify, materialize\.

We reserveconflicts\_withfor the online protocol \(§[3\.5](https://arxiv.org/html/2606.03056#S3.SS5)\) by operational necessity: a conflict is, by definition, a pair whose co\-use predictably degrades success, and that evidence simply does not exist until execution is observed\. No amount of static reading recovers it\.

### 3\.5Online Graph Evolution

Even a well\-constructed cold\-start graph is necessarily incomplete\. By the argument just made it cannot containconflicts\_withedges at all; more broadly, many useful relations appear only during execution: a prerequisite the cold\-start LLM did not anticipate, an interference pair observable only when both skills are loaded together, a refinement of an existing relation after a near\-miss\. To close this gap, we make graph construction an online part of agency rather than offline preprocessing: the per\-episode loop in Figure[1](https://arxiv.org/html/2606.03056#S0.F1)includes apropose\-edge/edit\-edgepair through which the agent commits evidence\-backed edits at the same pace it acts in the environment\.

We split the edit into two calls so that committing is always a deliberate act rather than a side effect of execution\.propose\-edgeperforms a dry run: it previews the change and surfaces existing edges and history for the same skill pair, so the agent can reason about whether to commit\.edit\-edgethen commits the change with a natural\-languagereasonand the supporting execution trace; the same call can add, delete, or retype an existing edge, giving the agent an explicit retraction path for stale or mistaken relations\. We deliberately chose to gate commits only by the agent’s own reasoning, not by a downstream voting threshold or a human curator, so that a single execution episode suffices and the graph evolves at agent speed rather than curation speed\. The repeated pair in Figure[2](https://arxiv.org/html/2606.03056#S3.F2)illustrates why the preview surfaces pair history: a laterconflicts\_withdecision must be evaluated against earlierdepends\_onevidence on the same pair\.

Gating commits only by the agent’s reasoning raises the risk of single\-shot corruption, which we bound with three structural invariants every commit must pass; the invariants are chosen to limit the blast radius of a bad edit without second\-guessing the agent’s semantic judgment\.*Acyclicity*: adepends\_on/specializescommit that would close a backbone cycle is rejected, since a circular prerequisite chain would loop the agent through skills that each demand the next, voiding the DAG property declared in §[3\.2](https://arxiv.org/html/2606.03056#S3.SS2)\.*Non\-contradiction*: a pair cannot simultaneously carryconflicts\_withand a positive surfacing edge, preventing the navigation and pruning signals from cancelling each other\.*Reversibility*: an append\-only history log supports rollback by recency, so a spurious edit is bounded and recoverable\. These invariants are structural rather than semantic by design: they preserve the LLM’s authority over what each edge*means*while preventing the graph from drifting into incoherence\.

## 4Experiments

Our evaluation pursues four guiding questions about when and why the interface design pays off\. We first compareSkillDAGagainst full\-library prompting, vector retrieval, andGoSon end\-task reward—the strongest indicator that agent\-callable graph access actually beats the dominant baselines\. Replaying identical queries through both retrievers then isolates how much of the gain is already visible before any downstream execution\. Contrasting MiniMax\-M2\.7 withgpt\-5\.2\-codexshows how the effect changes with backbone reasoning strength\. Finally, a10×10\\timesskill\-pool expansion and an ALFWorld train/test split measure whether retrieval stays robust at scale and whether online edits transfer to held\-out episodes\. Setup is in §[4\.1](https://arxiv.org/html/2606.03056#S4.SS1), main results in §[4\.2](https://arxiv.org/html/2606.03056#S4.SS2), and ablations in §[4\.3](https://arxiv.org/html/2606.03056#S4.SS3)\.

Table 1:Main results\.R= reward \(%\); ALFWorldR= success rate\. SkillsBenchRat 1000\-skill scale\.Ret@K/Ret@1/MRR \(↑\\uparrow\) are intrinsic retrieval metrics\. Vanilla/Vector/GoSRquoted fromli2026gosTable 1;SkillDAGRfrom our runs\. Best per column in bold\.![Refer to caption](https://arxiv.org/html/2606.03056v1/x4.png)\(a\)ALFWorld train/test\.
![Refer to caption](https://arxiv.org/html/2606.03056v1/x5.png)\(b\)Cross\-scale retrieval on SkillsBench\.

Figure 4:Robustness experiments\. \(a\) ALFWorld success \(%\) across Train \(420 in\-domain, edits on\), Test\-initial \(140 held\-out on cold\-start graph\), and Test\-edited \(same 140 on train\-produced graph\), for both backbones\. \(b\) Same 87SkillDAGqueries through both retrievers, sharedtext\-embedding\-3\-large;SkillDAGoutranksGoSat every scale and stays flat across the10×10\\timesexpansion; scale\-1000 matches the MiniMax row of Table[1](https://arxiv.org/html/2606.03056#S4.T1)\.### 4\.1Experimental Setup

Benchmarks\.We evaluate on two benchmarks used byli2026gos, which exercise different aspects of skill selection at scale\.*ALFWorld*\[shridhar2021alfworld\]is a text\-based embodied environment whose six task types \(pick\-and\-place, examine\-in\-light, clean\-, heat\-, cool\-and\-place, pick\-two\-and\-place\) require composing navigation, manipulation, and state\-change behaviors; we run the 140\-episodevalid\_seensplit with a 37\-skill procedural library\.*SkillsBench*\[li2026gos\]is 87 containerized code\-generation tasks scored by unit\-test pass fraction, shipped at four skill\-pool scales \(200/500/1000/2000SKILL\.mddocuments\) so retrieval quality can be studied as the pool grows\.

Baselines\.We compare against three baselines fromli2026gos\.*Vanilla Skills*places the entire library in the prompt and acts via ReAct\[yao2023react\]\(the recall upper bound and context\-cost reference\)\.*Vector Skills*concatenates the top\-KKembedding\-cosine matches, using no graph structure\.*Graph of Skills*\(GoS\)\[li2026gos\]retrieves a bundle by hybrid semantic–lexical seeding plus reverse\-aware Personalized PageRank over a typed graph, reranked under a token budget, then concatenated into the prompt\.*SkillDAG*\(ours\) exposes the graph as an agent\-callable structural retrieval interface: the agent issuessearch/show/propose\-edge/edit\-edgeduring execution, acts on the three\-field search response, and commits evidence\-backed edges under the guardrail checks\.

Models & evaluation\.We report per\-episode rewardR\(%\); for ALFWorldRequals success rate\. TheVanilla/Vector/GoSRrows \(for both MiniMax\-M2\.7 andgpt\-5\.2\-codex\) are quoted fromli2026gosTable 1 and were not rerun locally; theSkillDAGRrows are our own runs on the same benchmark, backbone, task data, and skill pools, but are not paired seed\-matched reruns of the baselines\. The intrinsic retrieval columns are computed by us on identical inputs: the actualsearchqueries issued by theSkillDAGagent during its 87\-task run, evaluated by each pipeline on the scale\-1000 pool \(n=140n\{=\}140ALFWorld episodes,n=87n\{=\}87SkillsBench tasks\)\.

### 4\.2Main Results

Table[1](https://arxiv.org/html/2606.03056#S4.T1)reports task reward and intrinsic retrieval on both benchmarks and backbones\.

SkillDAGimproves most under MiniMax\-M2\.7: ALFWorld54\.3→67\.154\.3\\\!\\to\\\!67\.1\(\+12\.8\+12\.8\) and SkillsBench18\.7→27\.318\.7\\\!\\to\\\!27\.3\(\+8\.6\+8\.6\), while undergpt\-5\.2\-codexALFWorld ties at93\.6%93\.6\\%and SkillsBench narrows to34\.4→36\.834\.4\\\!\\to\\\!36\.8\(\+2\.4\+2\.4\); the routing aid signature is large where the backbone cannot reason past a poor bundle and vanishes once it can\. Intrinsic SkillsBench retrieval likewise improves overGoSon the same MiniMax query distribution: Ret@K65\.5→78\.265\.5\\\!\\to\\\!78\.2, Ret@150\.6→66\.750\.6\\\!\\to\\\!66\.7, MRR57\.3→71\.357\.3\\\!\\to\\\!71\.3, isolating a retrieval\-pipeline gain before any agent\-side execution; with embedding and queries held fixed,SkillDAG’smatches\-field cosine over typed\-graph node embeddings ranks more accurately thanGoS’s HNSW\[malkov2020hnsw\]seed\+\{\+\}PPR\[page1999pagerank\]diffusion\.

Ongpt\-5\.2\-codex,SkillDAGtiesGoSon ALFWorld \(93\.6%93\.6\\%\), remains best on SkillsBench \(36\.8%36\.8\\%\), and yields75\.9/70\.1/73\.075\.9/70\.1/73\.0Ret@5/Ret@1/MRR on codex trajectory queries\.

### 4\.3Scale and Edit\-Transfer Ablations

We isolate two effects behind the main results: whether the agent’s online edits persist as durable, recall\-safe structure, and whether the typed\-graph retriever stays robust as the skill pool grows\.

We measure online editing two ways: an ALFWorld train/test split that tests whether committed edges transfer, and a SkillsBench cold\-vs\-edited query replay that tests what an accepted edge does to retrieved recall \(Table[2](https://arxiv.org/html/2606.03056#S4.T2)\)\.

Table 2:SkillsBench scale\-1000 retrieval, replaying 316searchqueries from 65 tasks against the cold\-start vs\. edited graph\. “Mean GT/q” is the average number of ground\-truth skills retrieved per query \(mean ground\-truth size 2\.52 skills/task\)\.Committed edges persist as durable structure\.A 420\-episode in\-domain*train*run accumulates edits;*test\-initial*\(140 held\-out episodes, cold\-start graph\) and*test\-edited*\(same 140, train\-produced graph\) are then run with edits disabled\. On both backbones train and test\-initial sit within2\.12\.1points \(MiniMax\-M2\.767\.1/65\.0/67\.1%67\.1/65\.0/67\.1\\%;gpt\-5\.2\-codex92\.3/90\.7/93\.6%92\.3/90\.7/93\.6\\%; Figure[4\(a\)](https://arxiv.org/html/2606.03056#S4.F4.sf1)\): transfer holds to the held\-out split, and test\-edited recovers the train number, so committed edges persist as durable structure rather than training\-time stochastics\.

Online edits expand ground\-truth recall set\-monotonically\.Replaying all 316 scale\-1000searchqueries, the edited graph \(\+27 single\-observation commits\) retrieves more ground\-truth skills per query \(1\.9841\.984vs\.1\.9151\.915; Table[2](https://arxiv.org/html/2606.03056#S4.T2)\) and*zero*queries lose any ground\-truth retrieval\. This follows by construction: the scorer takes the untruncated union ofmatchesand BFS neighbors, so an accepted edge can only enlarge the retrieved set, never evicting a ground\-truth skill the cold\-start graph already surfaced; this is a recall property, not a context\-budget claim\.

SkillDAGranking stays robust as the pool grows10×10\\times\.With the embedding backbone held fixed,SkillDAG’s plainmatchescosine outranksGoSon every retrieval metric at every pool scale despite using no diffusion step:\+16\.1/\+17\.2/\+17\.2\+16\.1/\{\+\}17\.2/\{\+\}17\.2\(Ret@5/Ret@1/MRR\) at 200 skills and\+13\.8/\+16\.1/\+16\.3\+13\.8/\{\+\}16\.1/\{\+\}16\.3at 2000, narrowest at 500 \(\+4\.6/\+6\.9/\+6\.3\+4\.6/\{\+\}6\.9/\{\+\}6\.3\) whereGoS’s PPR pull happens to align with the gold target; across the10×10\\timespool expansion it loses only3\.53\.5Ret@5 points \(78\.2→74\.778\.2\\\!\\rightarrow\\\!74\.7\), scaling robustly to larger libraries \(Figure[4\(b\)](https://arxiv.org/html/2606.03056#S4.F4.sf2)\)\. This isolates the offline retrieval pipeline, not the typed\-edgeneighbors/conflictsfields the agent exercises during execution\.

## 5Conclusion

SkillDAGexposes a typed skill\-relation graph as an agent\-callable structural retrieval interface \(search/show/propose\-edge/edit\-edge\) rather than hiding it inside a fixed graph\-ranking policy\. The agent loads only the typed neighbors and skill bodies it needs, avoiding the context\-bloat failure where fixed\-bundle retrievers flood the prompt with marginally relevant skills and corrupt downstream reasoning\. AgainstGoS,SkillDAGlifts MiniMax\-M2\.7 reward on ALFWorld \(54\.3→67\.154\.3\\\!\\to\\\!67\.1\) and SkillsBench \(18\.7→27\.318\.7\\\!\\to\\\!27\.3\), withmatches\-field retrieval winning every metric at every pool scale—supporting the inversion claim that the graph works best as an interface for routing decisions, not as an opaque policy\.

## Limitations

The propose\-then\-commit protocol is intentionally agent\-driven: a single execution observation can suffice for the agent to commit an edge, bounded by structural guardrails \(acyclicity, non\-contradiction, reversibility\) rather than a statistical confidence threshold \(§[3\.5](https://arxiv.org/html/2606.03056#S3.SS5)\)\. Aggregate edit effects are reported \(§[4\.3](https://arxiv.org/html/2606.03056#S4.SS3)\), but the long\-horizon behaviour of single\-observation self\-evolution remains an open question we view as a direction for future work\.

## References

## Appendix AEnd\-to\-End Algorithms

Algorithms[1](https://arxiv.org/html/2606.03056#alg1)and[2](https://arxiv.org/html/2606.03056#alg2)together specify theSkillDAGworkflow end to end\. Algorithm[1](https://arxiv.org/html/2606.03056#alg1)builds the initial typed graph offline from the skill library \(§[3\.4](https://arxiv.org/html/2606.03056#S3.SS4)\); Algorithm[2](https://arxiv.org/html/2606.03056#alg2)runs the per\-episode online loop covering retrieval and graph edits \(§[3\.3](https://arxiv.org/html/2606.03056#S3.SS3), §[3\.5](https://arxiv.org/html/2606.03056#S3.SS5)\)\. The pair classifierψ\\psireturns one ofdepends\_on,specializes,composes\_with,similar\_to, ornone;conflicts\_withis reserved for the online phase\. Agent\-facing calls \(search,show,propose\-edge,edit\-edge\) and the three commit\-time invariants \(acyclicity, non\-contradiction, and append\-only reversibility\) appear inline in Algorithm[2](https://arxiv.org/html/2606.03056#alg2)\.

Algorithm 1Cold\-start graph construction\.0:Skill library

𝒞\\mathcal\{C\}; embedder

ϕ\\phi; pair classifier

ψ\\psi; per\-ranking adaptive thresholds

θself,θneeds\\theta\_\{\\text\{self\}\},\\theta\_\{\\text\{needs\}\}
0:Initial typed graph

G0=\(V,E,τ\)G\_\{0\}=\(V,E,\\tau\)
1:foreach

v∈𝒞v\\in\\mathcal\{C\}do

2:

eself​\(v\)←ϕ​\(SKILL\.md​\(v\)\)e\_\{\\text\{self\}\}\(v\)\\leftarrow\\phi\(\\text\{SKILL\.md\}\(v\)\)
3:

eneeds​\(v\)←ϕ​\(HyDE\-summary​\(v\)\)e\_\{\\text\{needs\}\}\(v\)\\leftarrow\\phi\(\\text\{HyDE\-summary\}\(v\)\)\{

⊥\\botif self\-contained\}

4:endfor

5:

Pself←\{\(i,j\):cos⁡\(eself​\(i\),eself​\(j\)\)≥θself\}P\_\{\\text\{self\}\}\\leftarrow\\\{\(i,j\):\\cos\(e\_\{\\text\{self\}\}\(i\),e\_\{\\text\{self\}\}\(j\)\)\\geq\\theta\_\{\\text\{self\}\}\\\}
6:

Pneeds←\{\(i,j\):eneeds\(i\)≠⊥∧cos\(eneeds\(i\),eself\(j\)\)≥θneeds\}P\_\{\\text\{needs\}\}\\leftarrow\\\{\(i,j\):e\_\{\\text\{needs\}\}\(i\)\\neq\\bot\\,\\land\\,\\cos\(e\_\{\\text\{needs\}\}\(i\),e\_\{\\text\{self\}\}\(j\)\)\\geq\\theta\_\{\\text\{needs\}\}\\\}
7:

E0←∅E\_\{0\}\\leftarrow\\emptyset;

τ0←\\tau\_\{0\}\\leftarrowempty map

8:foreach

\(a,b\)∈Pself∪Pneeds\(a,b\)\\in P\_\{\\text\{self\}\}\\cup P\_\{\\text\{needs\}\}do

9:

t←ψ​\(a,b\)t\\leftarrow\\psi\(a,b\)
10:if

t≠nonet\\neq\\texttt\{none\}then

11:

E0←E0∪\{\(a,b\)\}E\_\{0\}\\leftarrow E\_\{0\}\\cup\\\{\(a,b\)\\\};

τ0​\(a,b\)←t\\tau\_\{0\}\(a,b\)\\leftarrow t
12:endif

13:endfor

14:

G0←\(𝒞,E0,τ0\)G\_\{0\}\\leftarrow\(\\mathcal\{C\},\\,E\_\{0\},\\,\\tau\_\{0\}\)\{conflicts\_withreserved for online phase\}

15:return

G0G\_\{0\}

Algorithm 2Per\-episode online loop\.0:Initial graph

G0G\_\{0\}; task distribution

𝒯\\mathcal\{T\}; LLM agent

π\\pi; budgets

K,DK,D
0:Evolved graph

GGand append\-only history log

HH
1:

G←G0G\\leftarrow G\_\{0\};

H←∅H\\leftarrow\\emptyset
2:foreach task

T∈𝒯T\\in\\mathcal\{T\}do

3:whileepisode not terminateddo

4:

π\\picallssearch/showas needed, then acts and observes outcome

5:ifevidence supports an edit

Δ\\Deltathen

6:

\(preview,history\)←propose\-edge​\(G,Δ\)\(\\text\{preview\},\\text\{history\}\)\\leftarrow\\texttt\{propose\-edge\}\(G,\\Delta\)
7:ifedit\-edgecommits and

Apply​\(G,Δ\)\\textsc\{Apply\}\(G,\\Delta\)passes invariantsthen

8:

G←Apply​\(G,Δ\)G\\leftarrow\\textsc\{Apply\}\(G,\\Delta\); append

Δ\\Deltato

HH\{reversible by recency\}

9:endif

10:endif

11:endwhile

12:endfor

13:return

G,HG,\\,H

#### Cold\-start configuration\.

- •Embedder:text\-embedding\-3\-large
- •LLM classifier:gpt\-5\-nanofor pair classification
- •Candidate pair threshold: adaptive \(mean cosine similarity\+1​σ\+1\\sigma, clipped to\[0\.35,0\.75\]\[0\.35,0\.75\]\)
- •Maximum candidates per node: 12, with a minimum floor of 3

## Appendix BFailure Analysis

### B\.1ALFWorld Failure Modes

Among the 11 failures in the 30\-task pilot evaluation, we identify three categories:

#### Tight loops \(8/11\)\.

The agent enters a cycle of repeated actions that produce “Nothing happens” observations\. The most common pattern is attempting to interact with an object that is not in the current room, without recognizing the need to navigate elsewhere\. The graph provides the correct procedural skills, but the agent fails at the grounding level \(mapping skill instructions to valid environment actions\)\.

#### Meta\-mode confusion \(1/11\)\.

A single failure \(task index 17\) exhibited a pathological pattern where the model’s internal reasoning tokens leaked into the action output, causing the agent to hallucinate observations and believe the task was complete\. This is a model\-specific artifact \(MiniMax</think\>tag leakage\) rather than a skill\-selection failure\.

#### Step budget exhaustion \(2/11\)\.

The agent explores correctly but exhausts the 30\-step budget before completing all required subtasks\. These tasks involve longer action sequences \(e\.g\., cleaning an object requires finding it, picking it up, navigating to a sink, using the sink, then navigating to the target location\)\.

## Appendix CEdge Type Operational Definitions

We provide expanded operational definitions for each edge type, including the counterfactual tests that would ideally validate them:

#### depends\_on\(A,B\)\(A,B\)\.

Removing skillBBfrom the agent’s available set drops the success rate ofAAby a measurable margin\. This captures prerequisite relationships:BBprovides setup, context, or intermediate results thatAArequires\. Transitivity holds: ifAAdepends onBBandBBdepends onCC, thenAAimplicitly depends onCC\.

#### composes\_with\(A,B\)\(A,B\)\.

The joint success rate of tasks where bothAAandBBare selected exceedsmax⁡\(success​\(A\),success​\(B\)\)\\max\(\\text\{success\}\(A\),\\text\{success\}\(B\)\)by a measurable margin\. This captures synergistic combinations where skills complement each other\. Symmetry holds\. Transitivity does not, because composability is pairwise rather than chainable\.

#### similar\_to\(A,B\)\(A,B\)\.

SkillsAAandBBachieve comparable success rates on the same task distribution and can substitute for each other\. Co\-selecting both wastes context but does not cause harm\. This is the weakest relationship type: it signals redundancy rather than interaction\.

#### conflicts\_with\(A,B\)\(A,B\)\.

Co\-selecting skillsAAandBBcauses a measurable drop in success rate compared to selecting either alone\. This captures genuine interference: resource contention, contradictory instructions, state contamination, or protocol conflicts\. Symmetry holds\. Transitivity does not\.

#### specializes\(D,A\)\(D,A\)\.

SkillDDachieves higher success thanAAon a specific subdomain ofAA’s applicability, while inheritingAA’s core functionality\. WhenDDis available and the task falls in its subdomain,DDshould be preferred overAA\. Transitivity holds within specialization hierarchies\.

## Appendix DReproducibility Details

#### Search budgets\.

Allsearchcalls useK=5K=5vector matches and BFS neighbor depthD=2D=2\. The agent may issue any number ofsearchcalls per episode and chooses query strings on its own schedule\.

#### Models and embeddings\.

Agent runs use MiniMax\-M2\.7 \(via the official MiniMax Anthropic\-compatible endpoint\) andgpt\-5\.2\-codex\(via the OpenAI Codex CLI withreasoning\_effort=high\)\. Cold\-start pair classification usesgpt\-5\-nano\. Query embedding at runtime usestext\-embedding\-3\-large, matching eachGoSworkspace’s embedding configuration\.

#### Step and attempt budgets\.

ALFWorld episodes are capped at 30 steps withnattempts=2n\_\{\\text\{attempts\}\}=2followingli2026gos§4\.1\. SkillsBench usesnattempts=1n\_\{\\text\{attempts\}\}=1for the MiniMax cross\-scale retrieval replay andnattempts=2n\_\{\\text\{attempts\}\}=2for main task\-reward results; thegpt\-5\.2\-codexretrieval row replays the codex agent’s queries under the samenattempts=2n\_\{\\text\{attempts\}\}=2budget\.

#### Online edit logging\.

Each acceptededit\-edgewrites an entry withorigin\(cold\-start vs\. online\),reason\(natural\-language justification\), andtask\_id\(the episode that produced the supporting evidence\) into the graph’s edge metadata\.

#### Cold\-start cost\.

At scale 1000 the cold\-start construction takes approximately 200gpt\-5\-nanocalls in batched bucket mode \(one call per anchor skill, classifying all candidate pairs in that bucket\), plus one embedding call per skill for each of the two views \(eselfe\_\{\\text\{self\}\}andeneedse\_\{\\text\{needs\}\}\)\.

## Appendix EWorked Example Subgraph

Edges are unweighted \(present or absent\); the LLM decides whether to add, remove, or retype an edge based on execution evidence, not statistical accumulation\. Table[3](https://arxiv.org/html/2606.03056#A5.T3)lists the runtime role of each type; the main\-text Figure[2](https://arxiv.org/html/2606.03056#S3.F2)shows a worked subgraph exercising all five\.

Table 3:Edge type taxonomy; runtime roles\.
## Appendix FSearch Interface Field Semantics

#### Matches\.

Cosine similarity is computed between the query embedding and each node’s pre\-computed embedding; the top\-KKare returned, ranked by similarity\.

#### Neighbors\.

From the match set, BFS proceeds along walkable types \(specializes,composes\_with,depends\_on,similar\_to\) up to depthDD, traversed bidirectionally so the agent sees both ends of a relationship \(fordepends\_on, both the prerequisite and any skill requiring the match as setup\); the typed label travels with the edge\. Each neighbor records its shortest distance from a match, predecessor, and edge type\.conflicts\_withis not traversed\. Skills already matched are excluded\.

#### Conflicts\.

Allconflicts\_withedges incident to any match within one hop are returned separately\. They have opposite polarity from neighbors: skills that should*not*be co\-selected\. No transitive expansion \(conflicts\-of\-conflicts are undefined\)\.

#### Properties\.

\(i\) The agent issues queries on its own schedule and rephrases as understanding evolves, rather than receiving one episode\-start bundle\. \(ii\) The three\-field decomposition lets the agent drop a whole field under tight budget rather than truncating an opaque concatenation\. \(iii\) Edges carry an explicit type and reason, so the agent’s trace documents selection/exclusion\. Aftersearch, the agent issuesshowfor chosen candidates; the decision is unconstrained \(all matches, only typed neighbors, or skip the graph\)\.

## Appendix GOnline\-Edit Protocol Detail

The protocol separates inspection from mutation\.propose\-edgeperforms a dry\-run returning what the change would do and surfacing all existing edges and recent history entries for the same skill pair, so the agent sees what prior episodes established before proceeding\.edit\-edgecommits, appending a history entry with task ID, natural\-language reason, and timestamp\. The per\-editreasonandtask\_idlog preserve auditability without gating the edit, placing graph\-quality responsibility on the same agent that consumes it\. The three commit\-time invariants \(acyclicity of thedepends\_on/specializesbackbone; non\-contradiction, meaning noconflicts\_withedge on a pair that already carries a positive surfacing edge such asdepends\_on,specializes,composes\_with, orsimilar\_to; and rollback by recency or task ID via the append\-only log\) are enforced on bothpropose\-edgeandedit\-edge\.

## Appendix HCold\-Start Pipeline Detail

The first vieweself​\(v\)e\_\{\\text\{self\}\}\(v\)embedsvv’s identifier, description, and a body preview\. The second vieweneeds​\(v\)e\_\{\\text\{needs\}\}\(v\)prompts an LLM to imagine two or three concrete tasks invokingvvin a longer chain and summarize the shared prerequisites in one sentence, which is embedded; skills with no clear shared prerequisite emitself\-containedand are excluded from the second view\. Candidate pairs come from two rankings:cos⁡\(eself​\(i\),eself​\(j\)\)\\cos\(e\_\{\\text\{self\}\}\(i\),e\_\{\\text\{self\}\}\(j\)\)over all pairs, andcos⁡\(eneeds​\(i\),eself​\(j\)\)\\cos\(e\_\{\\text\{needs\}\}\(i\),e\_\{\\text\{self\}\}\(j\)\)for eachiiwith non\-empty needs\. A pair is kept when its cosine exceeds an adaptive thresholdmax⁡\(0\.35,min⁡\(0\.75,μ\+σ\)\)\\max\(0\.35,\\min\(0\.75,\\mu\+\\sigma\)\)\(μ,σ\\mu,\\sigmathe mean/SD of that ranking’s similarities\)\. The two\-view design exists becauseeselfe\_\{\\text\{self\}\}alone misses cross\-functional pairs: a cooling skill and a pickup skill are distant undereselfe\_\{\\text\{self\}\}, but the cooling skill’s needs text \(“object in hand”\) bridges to the pickup skill’s self\-description\. The candidate union is bucketed by anchor \(lower\-index skill\) and sent to an LLM in one call per bucket assigningsimilar\_to,specializes,depends\_on,composes\_with, ornone;nonepairs are discarded and the rest become cold\-start edges carrying the LLM’s reason\.