acceptodds
Under review as a conference paper at ICLR 2027

SkillWorld: World-Indexed Skill Graphs with Governed Self-Evolution

14 views

Abstract

Composing skills from growing libraries for task execution requires reasoning about dependencies, alternatives, and conflicts among them. The information needed to infer these relations is distributed across skill descriptions, and their applicability may vary with the task and execution context. This calls for a reusable skill graph that supports context-dependent interpretation while remaining consistent as the underlying skill knowledge evolves. We present SkillWorld, which derives skill relations from typed skill descriptions and a shared ontology to provide a relational knowledge layer over large skill libraries. At runtime, it evaluates relation applicability in the current task and execution context. As the skill library grows, SkillWorld evolves the shared ontology to incorporate new skill knowledge and re-derives relations to maintain consistency with the updated model. On SkillsBench, SkillWorld with evolved static graphs outperforms graph-based and retrieval baselines, achieving gains of 11.1–15.3 percentage points in task success rate over the strongest baseline for each evaluated model. On ALFWorld, the full system produces 43.5–72.4% fewer invalid environment actions than BM25 skill retrieval, while achieving 85.1–85.8% task success within 15 environment actions across two models. We also deploy and evaluate SkillWorld in a large company's internal services. From the deployment traces, we select 36 tasks that are difficult to complete without skills. SkillWorld achieves a mean success rate of 72.2% over three runs.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
LLM agents, skill composition, skill graphs, ontology evolution, neuro-symbolic reasoning, context-aware retrieval

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_KHvNOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

SkillWorld has an LLM extract a typed manifest for each skill (capability, ports, preconditions, effects, constraints) against a shared ontology. Fixed Datalog rules (Soufflé) then compile five provenance-carrying relation types: CanFeed, Enables, AlternativeTo, Specializes and ConflictsWith. At runtime, a deterministic three-valued (Strong–Kleene) projection labels each relation confirmed, unknown or rejected under the current symbolic state and resource bindings. An LLM then selects skills from a relation-annotated candidate pool expanded from BM25 seeds. Between releases, "governed self-evolution" proposes ontology edits from manifest evidence and compilation diagnostics. An LLM picks an edit or abstains, a Lean-verified checker confirms source consistency, affected manifests are re-extracted, and a checked successor release is published atomically. Lean 4 proofs cover projection soundness and the authorization and publication invariants. Results: on 72 SkillsBench tasks, the evolved graph reaches 54.2% (Qwen) and 66.7% (Opus), 15.3/11.1 points above the best baseline. On ALFWorld it reaches 85.1–85.8% SR@15 with 43–72% fewer invalid actions than BM25. On 36 internal-service tasks it reaches 72.2%.

Critical strengths
  1. Separating a release-level "potential" relation graph from its state-conditioned applicability, with explicit unknowns under partial observation and rule-based derivation with provenance, is a clean and reusable idea for skill graphs. The ALFWorld ablations (no relation labels, static or random state) support it, with consistent reductions in invalid actions.
  2. The system is engineered with unusual rigor: mechanized Lean proofs, recompilation that propagates ontology corrections, and atomic publication. It is evaluated in three settings, including a real deployment.
Critical weaknesses
  1. Evolution drives all of the SkillsBench gain, but the paper does not explain why (beyond one traced example in App. G) or rule out leakage. The base graph is on par with the baselines (36.1 vs 33.3–38.9 for Qwen; 54.2 vs 50.0–55.6 for Opus). The 12–18 point improvement comes entirely from 41–51 evolution rounds (168–379 edits). The paper does not show which edits matter or how retrieved top-5 sets change on newly solved tasks. It also does not state clearly whether any SkillsBench task, instruction, verifier or outcome informs evolution: Appendix D mentions checking "configured task cases" in CHECKEDINPUT. Appendix G indicates that the Qwen run's evolution calls use qwen3.8-max, i.e., each evaluated model evolves its own graph, so it is unclear whether the evolved graph is generally better or tuned to that model. Governance is the claimed novelty, yet there is no ablation against ungoverned LLM ontology edits, and the token/time cost of evolution is not reported (only the budget mechanism is described). The Lean results certify the three-valued projection logic and the authorization/publication bookkeeping (tokens, CAS, frame conditions), but not the semantic accuracy of the LLM-extracted manifests and the relations derived from them, which Appendix A treats as an assumption ("the accuracy of manifest extraction and grounding determines the reliability of decided judgments"). So the formal machinery's contribution to task success is not established.
  2. The evaluation design leaves comparisons confounded or under-powered. SkillWorld uses an LLM selector over structured relation context, while several baselines (BM25, vector, co-use graph) rank by retrieval score alone. BM25 and BM25+LLM reranking give identical results for both models (25/72, 37/72), which should be checked. There is no CI on 72 tasks × 3 runs, where gaps among baselines are 1–4 tasks. On ALFWorld several conditions are identical across all three repeats (e.g., Qwen Full 114/114/114, BM25 101/101/101), so the repeats are not independent samples; per-game paired tests are needed for the 1.5–4 pp gaps to SkillDAG. The internal-service tasks are drawn from SkillWorld's own deployment traces, which favors the deployed system, and are not reproducible. The paper is also very hard to read: dense terminology (release pinning, quarantine bits, certificates, write tokens) buries the core idea, while key experimental details (edit statistics, extraction accuracy, cost) are missing.
Questions for authors

Clarifications:

  1. Does any SkillsBench information (task text, verifiers, outcomes, "configured task cases") enter evolution or validation? Appendix G shows the Qwen run evolved with qwen3.8-max; was the Opus column's graph evolved by Opus?
  2. What is the performance of a Qwen-evolved graph evaluated with Opus, and vice versa?
  3. Which edit types (e.g., type refinements like the light-curve example) account for the newly solved tasks?
  4. What is the precision of extracted Enables/CanFeed relations on a human-labeled sample?
  5. Cost (tokens, wall time) of evolution?
  6. Ablation: evolution without the source-consistency check and review gates.
  7. For ALFWorld, how were the ALFWorld-specific skills created, and how many are there? Suggestions: position the work against STRIPS/PDDL-style LLM planning more explicitly, since precondition/effect matching is classical. Move proof and system details to the appendix and bring evaluation details forward.

Score sensitivity: I could move to 3 if leakage is ruled out and evolution and governance are analyzed and ablated.

5 comments
AuthorsOpenReview ↗

Response to Reviewer KHvN (1/2)

We thank Reviewer KHvN for the thorough technical assessment and for stating clearly what would resolve the concerns. Your score-sensitivity note names three conditions; we address each with new evidence:

  1. Leakage is ruled out (§1): no SkillsBench text, verifier, or outcome enters evolution or validation, and evolution stops on its own.
  2. Evolution is analyzed (§2): edit taxonomy, provenance traces of newly solved tasks, audited edge precision (81.3% / 84.7%), and cross-model transfer (+9.72 / +8.33 pp).
  3. Governance is ablated (§2): without the gates, the same loop spends 1.28× the tokens, 18 of its 79 evaluated edits fail the Lean-verified check, and success drops by 17.13 pp.

§1. Leakage and model pairing (W1, Q1)

  • No SkillsBench information enters evolution. Offline extraction and evolution read only the 500 static skill documents, their extracted manifests, and Soufflé compilation diagnostics. No task text, instruction, verifier, trajectory, or outcome reaches candidate generation, LLM edit selection, quote review, or bundle validation.
  • configured task cases are offline structural checks, not benchmark tasks. In Appendix D (now clarified), this term means 500 per-round checks testing (i) that each manifest's source_hash matches its frozen skill file and (ii) edge consistency before and after the update.
  • No checkpoint selection. The number of rounds is not tuned: evolution runs until it stops on its own (no remaining menu candidates on Qwen after 51 rounds; LLM abstention on Opus after 41), and we evaluate that final release.
  • Model pairing. Yes: the Qwen3.8-Max column's graph was evolved by qwen3.8-max (51 rounds, 379 edits), and the Claude Opus 4.8 column's graph by Claude Opus 4.8 (41 rounds, 168 edits). Cross-model transfer below shows the result is not tied to the evolving model.

§2. What evolution learns and what governance contributes (W1, Q2–Q4, Q6)

  • Cross-model transfer (Q2, Table 2). The Opus-evolved graph evaluated with Qwen3.8-Max reaches 45.37 ± 2.89% (+9.72 pp over Qwen's Y0Y_0, 52.5% of Qwen's own evolution gain), and the Qwen-evolved graph evaluated with Opus reaches 62.04 ± 5.61% (+8.33 pp, 66.7% of Opus's gain). Without re-evolution, both transferred graphs beat every non-oracle baseline (+6.48 and +6.94 pp), showing that most of the learned ontology structure transfers across model families.
  • Governance ablation (Q6, Table 2). Running the same loop on Qwen with all gates off lets the LLM rewrite global state dimensions, forcing full-library re-extraction; by round 4 (80 edits) it exhausts its budget at 18.49M tokens (1.28× the full 51-round governed run) and an illegal abstract state parent (image_content_state) breaks compilation. Evaluating the 79 compilable edits shows the exact failures the gates block: (i) schema-breaking edits like the round-4 crash; (ii) 18 of 79 edits fail the Lean-verified SourceConsistent check on replay due to conflicting source claims; (iii) compiled edges jump by 75.6% in four rounds—e.g., merging distinct tool prerequisites into a generic dependencies_installed state adds at least 22 unsupported Enables edges from Python setup skills (setup-env, uv-package-manager) to external tools (ffmpeg, gh_cli, lean4). Success is 37.04 ± 2.12% on Qwen (−17.13 pp vs. governed, and below even the Opus-transferred graph) and 56.48 ± 2.89% under Opus (−5.56 pp vs. the governed Qwen-evolved graph under Opus, 62.04%). The governance gates—including Lean-verified source consistency—rather than LLM call volume, account for the task gain.

§3. Cost of evolution (Q5; Section 4.4, Table 13). Initial extraction costs 6.66M / 4.57M tokens (one call per skill); governed evolution costs 14.40M / 8.22M tokens over 51 / 41 rounds (412 / 194 re-extractions), 1.8–2.2× one extraction pass. Lean checking takes 0.44 / 0.69 s and compilation 2.32 s per 500-skill release on an Apple M4 Pro, without LLM calls.

AuthorsOpenReview ↗

Response to Reviewer KHvN (2/2)

§2 (cont.). Which edits matter (Q3) and edge precision (Q4)

  • Newly solved tasks trace to specific edits (Appendix E, Tables 9 and 12). Evolution changes the top-5 on 58/72 (80.6%) Qwen and 55/72 (76.4%) Opus tasks (membership changes on 47 and 46), and target/artifact types make up 59.4% / 65.5% of published edits. Across all newly solved task-runs (45 on Qwen, 41 on Opus over 3 runs), 29 / 29 change the top-5 skill set and 7 / 2 reorder the same five: specifically, 13 per model bring in a skill absent from the base (Y0Y_0) candidate pool via an evolved edge (13/13 Qwen and 12/13 Opus paths use target-type refinements), and 23 / 18 reselect or reorder within the base (Y0Y_0) candidate pool; the remaining 9 / 10 keep the same top-5 while receiving newly compiled relation witnesses alongside the loaded skills.
  • Example. In earthquake-plate-calculation (Opus), the round-24 edit adding geospatial_dataset under dataset retypes the output of the top BM25 seed geospatial-analysis on re-extraction; recompilation derives geospatial-analysis --CanFeed--> custom-distance-metrics, which enters the top-5 at rank 3, and the task is newly solved in runs 2 and 3. Appendix E adds an Enables example in drone-planning-control.
  • Edge precision (Q4). Human audit of 150 stratified edges per evolved graph (120 CanFeed, 30 Enables) against the skill texts gives 81.3% precision on Qwen (80.8% CanFeed, 83.3% Enables) and 84.7% on Opus (82.5% / 93.3%). Remaining errors come mainly from coarse shared types in peripheral domains; this directly measures the extraction accuracy placed outside the Lean TCB in Section 3.4 (Table 1).

§4. Evaluation controls and statistics (W2, Q7)

  • The LLM selector does not explain the gain. On SkillsBench, base SkillWorld (Y0Y_0) uses the same LLM selector, budget, pool, and harness as governed SkillWorld, yet stays near the retrieval baselines (35.65% / 53.70%) while domain types remain collapsed into dataset; governed evolution adds +18.52 / +12.50 pp. On ALFWorld (frozen ontology), graph-based runs use no separate LLM reranker.
  • Exact means and SDs. Tables 2 and 4 now report exact unrounded 3-run means and sample SDs instead of whole-task rounded means (e.g., Opus governed is 47.67/72 = 66.20%; internal services is 26.33/36 = 73.1%), and Appendix E (Table 11) lists SkillsBench per-run counts. Governed SkillWorld's runs (39/40/38 on Qwen; 47/46/50 on Opus) never overlap with any run of any non-oracle baseline (best single baseline runs: 29 and 42).
  • BM25 vs. BM25 + LLM reranking. Exact means are 25.00 vs. 24.67/72 on Qwen and 37.00 vs. 37.00/72 on Opus (runs 38/36/37 vs. 34/39/38); reranking wins 6 and loses 7 tasks on Qwen, and wins 7 and loses 7 on Opus. Within top-20 lexical hits, reranking only swaps borderline candidates, whereas typed CanFeed/Enables edges bring in non-lexical prerequisites.
  • Game-level paired tests on ALFWorld (Appendix F, Table 15). Two-sided sign-flip tests over the 134 unseen games (10,000 permutations, Holm–Bonferroni adjusted over 16 comparisons) show significant SR@15 gains for Full over No skills, graph-free search, and GoS on both models (adjusted p≤0.009p \le 0.009), and over BM25 and No relation labels on Qwen (adjusted p=0.0055,0.0126p = 0.0055, 0.0126; unadjusted p=0.0424,0.0321p = 0.0424, 0.0321 on DeepSeek, with 68.5%–72.4% fewer invalid actions). Against online-updating SkillDAG, frozen Full is +3.98 / +1.49 pp higher in SR@15 (unadjusted p=0.258,0.610p = 0.258, 0.610; not significant) while cutting invalid actions by 49.7% / 70.0% (74 vs. 147; 51 vs. 170) without online graph updates.
  • ALFWorld skills (Q7). We corrected Section 4.2: ALFWorld uses GoS's public skills_500 library unchanged—37 ALFWorld procedural skills from Liu et al. (2026), not derived from our runs, plus 463 general/external distractors.
  • Internal-service tasks. In this proprietary deployment case study, the 36 tasks were curated from trajectories where skill-free execution struggled—using no skill-based method's outcome—and all baselines (including graph-free search and SkillDAG) run under the same harness on the shared 903-skill library.

§5. Positioning and readability. Section 5 now relates typed manifests and Enables/ConflictsWith compilation to STRIPS/PDDL and LLM-PDDL planning (e.g., Fikes & Nilsson, 1971; Ghallab et al., 2004; Silver et al., 2024), contrasting open-ended skill documents and read-only K3\mathbb{K}_3 projection with closed-world planners; proof and system details moved to Appendices A–D so evaluation details appear earlier.

We believe these results meet the conditions in your score-sensitivity note, and we would be grateful if you would consider updating your score.

AuthorsOpenReview ↗

Follow-up on our response to Reviewer KHvN

Dear Reviewer KHvN,

As the discussion period wraps up soon, we wanted to briefly check in to see whether our response and revised manuscript resolve your questions—particularly on the three points highlighted in your review:

  • No benchmark leakage: Clarified that offline evolution reads only static skill texts, manifests, and compiler diagnostics (configured task cases are offline file-hash and edge checks), terminating automatically without checkpoint selection.
  • Evolution analysis: Added the edit taxonomy, provenance of newly solved tasks, human-audited edge precision (81.3% / 84.7%), and cross-model transfer (+9.72 / +8.33 pp without re-evolution).
  • Governance ablation & statistics: Disabling the gates spends 1.28× the offline tokens within 4 rounds yet reaches only 37.04% on Qwen (vs. 54.17% with governance), alongside exact 3-run statistics and ALFWorld paired tests.

If any questions remain before the window closes, we would be very glad to clarify. Thank you again for your thorough review!

Reviewer_mhZ1OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes SkillWorld, which organizes skills into a graph derived from skill descriptions and shared rules, capturing dependencies, alternatives, and conflicts between skills. It uses the agent's current execution state to determine which relations apply and proposes an offline process for updating the ontology and rebuilding the graph. Experiments on SkillsBench, ALFWorld, and an internal benchmark show improvements in task success and reductions in invalid actions.

Critical strengths
  1. The proposed method addresses the limitations of relevance-based retrieval by modeling skill dependencies, compatibility, and applicability to the current execution state.
  2. The evaluation measures downstream task performance across multiple settings and includes key ablations such as graph evolution and state-dependent relation filtering.
Critical weaknesses
  1. The presentation is difficult to follow. The paper introduces substantial notation, graph definitions, and operations before providing sufficient intuition. Figure 1 and the brief examples do not clearly explain how the components work together. An example that walks through actual skill documents, manifest extraction, relation construction, retrieval, and ontology evolution would make the method easier to understand.
  2. The skill-pool evaluation setting is insufficiently justified. The SkillsBench experiments use only 500 skills, without clearly explaining their provenance or overlap with the benchmark's task-specific curated skills. This small skill pool setting provides limited evidence for the need for such an elaborate retrieval framework. Table 1 also omits the original SkillsBench setting with task-specific curated skills supplied to the agent. This comparison is important for understanding whether the proposed retrieval pipeline recovers or improves upon the utility of the human-curated skills.
  3. Computational costs and scalability are insufficiently evaluated. The paper does not report the aggregated token or time cost of offline graph construction and evolution. It also does not provide a complete accounting of online overhead, including LLM-based state extraction and skill selection. With evaluation covering only 500 or 903 skills, scalability to 10,000 or more skills remains untested. Performance-cost comparisons, including the amortization of offline construction costs, are needed to establish practical value.
  4. The necessity of the complex pipeline is not established against a simpler alternative. The paper lacks a comparison with a graph-free agent that searches for skills during execution, refines search queries using current observations, and decides which skills to load. Such a baseline could address changing capability needs without ontology construction, graph compilation, or governed evolution. Comparing task success and total cost under matched conditions would clarify the value of the proposed method.
Questions for authors

Please see the weakness.

5 comments
AuthorsOpenReview ↗

Response to Reviewer mhZ1 (1/2)

We thank Reviewer mhZ1 for the concrete suggestions on presentation, the curated-skill oracle, cost accounting, and a simpler online baseline. Each is now in the revised paper.

W1: A concrete walkthrough before any notation. New Section 2 follows concrete skills through the whole pipeline in plain prose, before any formal definitions (a recorded Qwen extraction trace is in Appendix G):

  1. Manifest. An LLM reads each skill document once per ontology version into a typed manifest: capability, input/output types, preconditions, and effects. PrepareEnv declares the effect deps.ready = true; RunTests requires deps.ready = true.
  2. Relations. Fixed Datalog rules match manifests across the library and derive PrepareEnv --Enables--> RunTests, storing the matched condition and rule as provenance.
  3. Runtime retrieval. For a task that asks to run a test suite, lexical search finds RunTests, and one hop over the graph adds PrepareEnv. Without any LLM call, the edge is labeled confirmed if dependencies are missing (select both), unknown if their status is not yet observed, and rejected once they are installed (run the tests directly).
  4. Ontology evolution. Under the seed ontology, light-curve-preprocessing and box-least-squares both type their data as a generic dataset, so they stay disconnected. Four astronomy skills independently propose a finer light_curve type. After an LLM selects it and a Lean-verified checker confirms that the four manifests' recorded proposals support it exactly and without conflict, only the affected skills are re-extracted, and recompilation adds CanFeed edges from light-curve-preprocessing to three downstream skills.

Authorization tokens, CAS certificates, and refresh receipts have moved from the main text to Appendices A–D.

W2: Pool provenance, curated-skill overlap, and the task-curated oracle.

  • Provenance (Section 4.1, Appendix E). The 87-task SkillsBench suite references 195 unique curated skills; our 72-task subset references 148 (179 task–skill pairs). GoS's public skills_500 collection (Liu et al., 2026) already contained 162 of the 195; we replaced 33 unrelated Rube automation-connector skills with the 33 missing ones. The pool thus holds every curated skill for our tasks plus 305 external distractors (352 non-target skills for the 72-task subset).
  • Task-curated oracle (new row in Table 2). Supplying each task's official curated skills under the same harness reaches 61.57 ± 2.89% on Qwen3.8-Max (runs: 42/45/46) and 71.30 ± 4.88% on Claude Opus 4.8 (runs: 51/55/48), versus 18.98% / 30.56% with no skills. Governed SkillWorld thus recovers 82.6% / 87.5% of the gain that curated skills provide over no skills, versus 46.7% / 60.2% for the strongest baseline (SkillDAG on Qwen, BM25 + Co-use Graph on Opus). On our 903-skill internal library, SkillWorld recovers 83.8% of the human-selected oracle's gain over no skills (26.33/36, vs. 30.33/36 for the oracle and 5.67/36 with no skills; Table 4).
  • Why 500 skills already stresses retrieval. Even with every curated skill in the pool, replacing curation with retrieval—flat, graph-based, or online iterative search—leaves baselines at 33.80–38.89% (Qwen) and 50.46–55.09% (Opus). Governed evolution lifts SkillWorld from 35.65% to 54.17% and from 53.70% to 66.20%. Growing the pool tenfold from 200 to 2,000 skills, GoS's Recall@5 drops 17.56 pp (to 68.85%), whereas SkillWorld retains 81.76% (−3.56 pp, +12.91 pp over GoS at 2,000; Figure 3a, Table 10).
AuthorsOpenReview ↗

Response to Reviewer mhZ1 (2/2)

W3: Cost accounting and scaling (new Section 4.4 with Figure 2 and Table 13; new Section 4.5 with Figure 3 and Table 10).

  • Offline construction and evolution. Initial extraction makes one LLM call per skill (500 parallel calls, no pairwise scoring): 6.66M tokens on Qwen3.8-Max and 4.57M on Opus. Governed evolution re-extracts only affected skills (412 refreshes over 51 Qwen rounds; 194 over 41 Opus rounds) and costs 14.40M / 8.22M tokens, 1.8–2.2× one extraction pass and over 22× below re-extracting the full library each round. The one-time release (21.05M / 12.79M tokens) amortizes to 21.1k / 12.8k tokens per task over 1,000 tasks and transfers across model families without re-evolution.
  • Online overhead. K3\mathbb{K}_3 projection and candidate retrieval run locally without LLM calls in 0.85 s per step on an Apple M4 Pro. The only added online LLM calls are one selection call per SkillsBench task (13.9k tokens on Qwen including 9.0k thinking tokens; 7.9k on Opus) and state grounding on ALFWorld (2,254 tokens per episode).
  • Performance per cost. On Qwen, SkillWorld solves 1.54× as many tasks as the graph-free agent in W4. Including its full release cost, it breaks even on tokens per solved task at N = 61 tasks and uses 24.8% fewer tokens per solved task at N = 1,000 (1.83M vs. 2.43M; Figure 2b).
  • Scaling: retrieval quality to 2,000 skills, compilation to 10,000. On nested SkillsBench pools (Qwen3.8-27B), growing the pool tenfold from 200 (all 195 reference skills present) to 2,000 retains 81.76% Recall@5 for SkillWorld (−3.56 pp, from 85.32%) while GoS drops 17.56 pp (to 68.85%), with 23.3% / 22.4% fewer build tokens than GoS at 1k / 2k skills (3.92M / 7.85M vs. 5.11M / 10.12M). For compiler speed and memory on large dense graphs (Figure 3b, 16 GiB cap; 5k and 10k replicate the 500-skill pool 10× and 20×), batched compilation takes 2.32 s at 500 skills, 7.35 s at 1k, 169.54 s at 5k (3.19M edges), and 673.83 s at 10k (12.78M edges, 11.90 GiB peak).

W4: Graph-free iterative search. Following your suggestion, we added an agent that searches the skill pool during execution, rewrites its queries from current observations, and decides which skill documents to load, under the same model, harness, and turn/skill budgets on all three benchmarks:

BenchmarkGraph-free iterative searchSkillWorldGain
SkillsBench, Qwen3.8-Max (72 tasks × 3 runs)35.19 ± 2.12%54.17 ± 1.39%+18.98 pp
SkillsBench, Claude Opus 4.854.63 ± 2.12%66.20 ± 2.89%+11.57 pp
ALFWorld, Qwen3.8-27B (402 episodes)71.14% (254 invalid)85.07% (74 invalid)+13.93 pp
ALFWorld, DeepSeek V4.1 Flash68.16% (492 invalid)85.82% (51 invalid)+17.66 pp
Internal services (36 tasks × 3 runs, 903 skills)56.5 ± 8.0%73.1 ± 3.2%+16.7 pp
  • The baseline is strong where search has room to work. On open-ended internal tasks without a tight step cap, it beats one-shot BM25 by 19.4 pp and GoS by 25.9 pp. On SkillsBench, where domain types start collapsed into generic dataset under Y0Y_0, online query rewriting matches static baselines and base SkillWorld (35.65% / 53.70%), while governed evolution opens a +18.98 / +11.57 pp lead; on ALFWorld, frozen SkillWorld already leads iterative search by +13.93 / +17.66 pp.
  • Why lexical search, one-shot or iterative, falls short. Queries are built from what the agent currently observes, so they miss prerequisite skills written in different terms. Within ALFWorld's 15-step limit this causes premature actions (254 / 492 invalid actions vs. 74 / 51 for SkillWorld). Typed Enables and CanFeed edges bring in these prerequisites before trial-and-error failures.
AuthorsOpenReview ↗

Follow-up on our response to Reviewer mhZ1

Dear Reviewer mhZ1,

With the discussion period coming to a close soon, we wanted to briefly check in to see if our response and revised manuscript address your comments—specifically:

  • Readability: A new notation-free walkthrough of concrete skills in Section 2, with formal bookkeeping moved to Appendices A–D.
  • Pool provenance & curated-skill oracle: Clarified the 500-skill pool construction and added the task-curated oracle (Table 2), showing SkillWorld recovers 82.6% / 87.5% of curated skills' gain over no skills.
  • Cost & scaling: Added full offline/online token accounting (breaking even on tokens per solved task at N=61N = 61), retrieval scaling to 2,000 skills (81.8% Recall@5 vs. 68.9% for GoS), and compilation up to 10,000 skills (Sections 4.4–4.5).
  • Graph-free iterative search: Implemented your suggested online query-rewriting baseline across all three benchmarks, which SkillWorld outperforms by +11.6 to +19.0 pp.

Please let us know if anything remains unclear or if we can provide any further details before the deadline. Thank you again for your constructive suggestions!

Reviewer_FNZHOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces SkillWorld, which organizes skill descriptions into a skill graph enriched with type and provenance information. At runtime, it evaluates the applicability of relationships between skills based on the current state. Updates to the graph undergo a rigorous pipeline before being deployed, involving evidence verification, re-extraction, compilation, and formal verification (using Lean). The authors evaluate the framework on SkillsBench, ALFWorld, and a suite of internal service tasks, measuring metrics such as task success rate, the frequency of invalid actions, and the evolution of the skill graph.

Critical strengths
  1. The problem addresses a clear domain-specific need. As skill libraries and operational environments evolve, static skill graphs struggle to consistently support reliable task execution. This paper investigates this practical challenge.
  2. The overall framework and structure are well-developed. The paper clearly delineates three components (skill modeling, runtime state assessment, and graph evolution) with a consistent alignment between the proposed methodology, formal definitions, and system workflows.
  3. The system update process offers strong traceability. By maintaining provenance evidence, verifying update consistency, and implementing version control, the approach facilitates error localization, review of updates, and experimental reproducibility.
  4. The experimental design aligns effectively with the core research questions. SkillsBench is used to evaluate graph evolution, ALFWorld assesses state-dependent retrieval, and internal tasks test real-world execution. They collectively covering the paper's primary claims.
Critical weaknesses
  1. Lack of clearly defined boundaries for Lean-based verification. The paper does not clearly distinguish between the program properties that Lean can guarantee and those aspects that still rely on external models or human judgment, such as semantic intent or runtime state.
  2. Absence of a fixed-graph control condition at an equivalent cost. Since graph evolution entails additional model invocations, re-extraction, and re-compilation, it is currently difficult to determine whether the observed gains stem from the governance process itself or from the additional information acquired during these steps.
Questions for authors
  1. What specific problems does graph evolution actually address? Does it primarily resolve missing information, outdated relationships, or erroneous updates?
  2. Why is the distinction between "latent relationships" and "currently available relationships" sufficiently to support complex tasks?
  3. What is the overhead for the entire process, in terms of model invocations, re-extraction, compilation, and verification, and is it worth these additional costs?
3 comments
AuthorsOpenReview ↗

Response to Reviewer FNZH (1/2)

We thank Reviewer FNZH for recognizing the practical relevance of evolving skill graphs, the alignment between our method, formal definitions, and workflow, and the traceability of the update pipeline.

W1: Boundaries of Lean-based verification. New Section 3.4 and Table 1 draw this line explicitly:

Mechanically verified in Lean 4Outside the Lean TCB (evaluated empirically)
Projection soundness (Prop. 1): no false unknown when relevant state is observed; decided confirmed/rejected labels hold as more state is observed; formula IR matches AST semantics.LLM judgments: extracting manifests from skill text, grounding state and bindings from observations, picking menu candidates, checking cited quotes, selecting skills.
Source-bound authorization (Thm. 2): checkSource  ⟺  SourceValid\mathsf{checkSource} \iff \mathsf{SourceValid}, i.e., exact support from manifest unknowns, no active semantic conflict, and a non-transferable (c,v)(c,v) write binding.Host execution: Soufflé evaluation, JSON parsing/hashing, and filesystem CAS atomicity, covered by differential and fault-injection tests.
Refresh and publication safety (Thms. 3–4): exactly one refresh per selected skill, byte-identical untouched skills, full diff-review coverage, token/extraction caps, checkWF  ⟺  WF\mathsf{checkWF} \iff \mathsf{WF}, CAS publication invariants (given the host CAS result).Human input: only the seed ontology Y0Y_0 and optional administrative quarantine bits between releases; evolution and projection otherwise run without human input.

In short, given extracted manifests, grounded observations, and review records, Lean guarantees that projection never invents certainty or flips a decided label, and that governance never publishes unsupported, conflicting, unreviewed, or ill-formed updates. Outside Lean, extraction precision is audited directly (81.3% / 84.7%; Appendix E, Table 12), and Tables 2–3 measure the downstream effect of extraction and state grounding.

W2: Separating governance from extra LLM compute. The controls below keep the skill pool fixed and spend LLM compute in different places; governed evolution drives the gain (Qwen3.8-Max, Table 2):

ConditionGraphExtra LLM computeSR (%)
SkillWorld, seed ontology Y0Y_0fixednone35.65 ± 2.12
BM25 + LLM rerankingnoneonline reranking of top-20 hits34.26 ± 0.80
Graph-free iterative searchnoneonline query rewriting and skill loading35.19 ± 2.12
SkillWorld, ungoverned evolutionevolved, gates off18.49M offline tokens (1.28× governed)37.04 ± 2.12
SkillWorld, governed evolutionevolved, gated14.40M offline tokens54.17 ± 1.39
  • Ungoverned evolution spends 1.28× the offline tokens of governed evolution yet gains only +1.39 pp vs. +18.52 pp. It runs the same proposal, selective-refresh, and recompilation loop with all gates off. Without source checks, the LLM repeatedly rewrites global state dimensions, forcing full-library re-extraction (~6× more tokens per edit); by round 4 (80 edits) it exhausts its budget at 18.49M tokens—1.28× the full 51-round governed run—and an illegal abstract state parent breaks compilation. Evaluating the 79 compilable edits, 18 fail the Lean-verified SourceConsistent check on replay, and merging distinct tool prerequisites into a generic dependencies_installed=true adds at least 22 unsupported Enables edges (e.g., from setup-env and uv-package-manager to ffmpeg, gh_cli, and lean4). Evaluated with Claude Opus 4.8, this graph reaches 56.48%, 5.56 pp below the governed Qwen-evolved graph under Opus (62.04%). The gain thus comes from which edits the gates admit, not the number of LLM calls.
  • Re-extracting under a fixed Y0Y_0 cannot substitute for evolution. Manifest schemas restrict port and capability types to identifiers in Y0Y_0, and generic dataset matching is disabled, so types like light_curve stay collapsed into dataset (recorded only under unknowns) until Y0Y_0 is refined.
AuthorsOpenReview ↗

Response to Reviewer FNZH (2/2)

Q1: What does graph evolution address? Primarily missing information:

  1. Missing ontology types and links (the main target). Under an incomplete seed ontology, domain types collapse into generic ones (e.g., light_curve into dataset), and missing is_a links or state dimensions hide valid CanFeed, Enables, and Specializes edges. Target/artifact-type refinements make up 59.4% (225/379) of published edits on Qwen and 65.5% (110/168) on Opus. Of the 13 newly solved task-runs per model that trace to an evolved edge, all 13 on Qwen and 12 on Opus use such a refinement (Appendix E, Table 12).
  2. Outdated or overly coarse relations. When an ontology entry is refined or a skill document changes between releases, selective re-extraction (AffectedSkills) and recompilation replace stale derived edges. Step-by-step state changes within an episode are handled by read-only K3\mathbb{K}_3 projection without changing the graph.
  3. Erroneous updates. The governance gates (SourceConsistent, quote-bound diff review, CheckedInput/checkWF) block unsupported or conflicting edits before publication (see W2), and quarantine bits can disable a faulty edge between releases.

Q2: Why the latent/current distinction supports complex tasks. In multi-step tasks, the agent needs to see both upstream prerequisites across steps and what can run right now. Separating the two views provides both:

  • The latent view keeps what the agent may need next. Keeping only currently active edges would hide a blocked goal skill (RunTests while deps.ready=false) along with the prerequisite that unblocks it (PrepareEnv). Graph expansion therefore retains multi-hop prerequisites (Enables, CanFeed), substitutes (AlternativeTo), and hazards (ConflictsWith) around the goal.
  • The current view says what can run now. At each step, K3\mathbb{K}_3 projection labels each retained edge confirmed (usable now), unknown (state unobserved, so check first), or rejected (precondition violated, or already satisfied, e.g., PrepareEnv once deps.ready=true). Unlabeled latent edges lead to premature or repeated actions.
  • Evidence (ALFWorld, Table 3). Removing relation labels and relation-based ordering—while keeping dynamic state and per-skill applicability—raises invalid actions from 74 to 115 (Qwen) and from 51 to 162 (DeepSeek), and lowers SR@15 by 9.95 pp on Qwen (adjusted p=0.0126p = 0.0126). Freezing projection at the first observation raises invalid actions to 94 and 80.

Q3: End-to-end overhead, and whether it is worth it (Sections 4.4–4.5, Figures 2–3, Appendix E Tables 10 and 13).

Qwen3.8-MaxClaude Opus 4.8
Initial extraction (one-time, 1 call per skill)6.66M tokens4.57M tokens
Governed evolution (one-time; 412 / 194 re-extractions)14.40M tokens8.22M tokens
Release cost amortized over 1,000 tasks21.1k tokens/task12.8k tokens/task
Online selection (1 call per task)13.9k tokens (incl. 9.0k thinking)7.9k tokens
  • Evolution stays cheap because selective refresh re-extracts only affected skills (on average 8.1 / 4.7 skills per round, i.e., 1.6% / 0.9% of the pool): all 51 / 41 rounds together cost 2.16× / 1.80× one extraction pass, over 22× less than re-extracting the full library each round.
  • Symbolic steps need no LLM calls. On an Apple M4 Pro, Lean checking of a 500-skill release takes 0.44 / 0.69 s, compilation 2.32 s, and online projection plus retrieval 0.85 s per step; ALFWorld state grounding adds 2,254 tokens per episode.
  • The cost pays off. On Qwen, SkillWorld solves 1.54× as many tasks as graph-free iterative search. Including its full release cost, it breaks even on tokens per solved task at N = 61 tasks (fewer than our 72 benchmark tasks) and uses 24.8% fewer tokens per solved task at N = 1,000 (1.83M vs. 2.43M; Figure 2b). The evolved release also transfers across model families (+9.72 / +8.33 pp) without re-evolution.
  • Scale. From 200 to 2,000 skills (Qwen3.8-27B), SkillWorld retains 81.76% Recall@5 (−3.56 pp vs. −17.56 pp for GoS) while using 23.3% / 22.4% fewer build tokens at 1k / 2k skills, and compilation finishes a 20×-replicated 10,000-skill stress test (12.78M edges) in 11.2 min within 16 GiB RAM.
AuthorsOpenReview ↗

Follow-up on our response to Reviewer FNZH

Dear Reviewer FNZH,

As the author–reviewer discussion period concludes soon, we wanted to briefly check in to see whether our response and revised manuscript address all of your questions—in particular:

  • Lean 4 verification boundaries: Explicit separation of Lean-verified guarantees from empirical LLM components in new Section 3.4 and Table 1.
  • Governance vs. extra compute: Controlled comparisons showing that ungoverned evolution spends 1.28× the offline tokens of governed evolution yet reaches 37.04% vs. 54.17% on Qwen (alongside online LLM reranking and iterative search controls).
  • End-to-end overhead: Full offline/online cost and amortization analysis (Sections 4.4–4.5), reaching 24.8% fewer total tokens per solved task at N=1,000N = 1,000 with release cost included.

Please let us know if we can clarify anything further before the window closes. Thank you again for your thoughtful feedback!

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to All Reviewers and the AC

We thank all three reviewers for their detailed and constructive feedback. Reviewers found that SkillWorld addresses a practical need as skill libraries and environments evolve (FNZH), models skill dependencies and state-dependent applicability beyond relevance-based retrieval (mhZ1), cleanly separates a provenance-carrying potential graph from its Strong–Kleene (K3\mathbb{K}_3) runtime projection (KHvN), offers strong traceability (FNZH) and is engineered with unusual rigor, from mechanized Lean 4 proofs to atomic publication (KHvN), and is evaluated in three settings with key ablations (all reviewers).

We have revised the manuscript (main text still within 10 pages) and added the evidence below; the per-reviewer responses give details. The SkillsBench results table is now Table 2 (formerly Table 1). Number pairs are Qwen3.8-Max / Claude Opus 4.8 unless noted.

  1. No benchmark leakage (KHvN). Offline extraction and evolution read only the 500 skill documents, their manifests, and compiler diagnostics; no SkillsBench task text, verifier, or outcome enters evolution or validation. Evolution stops on its own, and we evaluate its final release.
  2. Governance is what makes evolution work (FNZH, KHvN). The same proposal–refresh–recompile loop with all governance gates disabled spends 1.28× the tokens of the full governed run by round 4, yet reaches only 37.04% on Qwen (+1.39 pp over the seed ontology), versus 54.17% (+18.52 pp) with governance.
  3. Evolution learns reusable domain structure (KHvN). Target/artifact types make up 59.4% / 65.5% of published edits, and edge provenance traces 13 newly solved task-runs per model to a skill that entered the candidate pool only through an evolved edge. A graph evolved by one model family lifts the other by +9.72 / +8.33 pp without re-evolution, beating every non-oracle baseline. Human-audited precision of compiled edges is 81.3% / 84.7%.
  4. Stronger baselines and an in-pool oracle (mhZ1). All 148 curated skills for our 72 tasks are in the 500-skill pool, and supplying them per task reaches 61.57% / 71.30% (Table 2); governed SkillWorld recovers 82.6% / 87.5% of the gain curated skills provide over no skills, versus 46.7% / 60.2% for the strongest baseline. A new graph-free agent that rewrites its search queries online trails SkillWorld on all three benchmarks: by 11.57–18.98 pp on SkillsBench, 13.93–17.66 pp on ALFWorld, and 16.7 pp on internal services.
  5. Cost and scale (all reviewers). The one-time offline release costs 21.05M / 12.79M tokens, i.e., 21.1k / 12.8k tokens per task over 1,000 tasks. On Qwen, SkillWorld solves 1.54× as many tasks as graph-free search and needs 24.8% fewer tokens per solved task at N = 1,000, release cost included. Growing the pool tenfold from 200 to 2,000 skills, it retains 81.76% Recall@5 (−3.56 pp vs. −17.56 pp for GoS), and compilation scales to a 20×-replicated 10,000-skill stress test (12.78M edges) in 11.2 min.
  6. Exact statistics (KHvN). Table 2 reports exact 3-run means with sample SDs and per-run counts (Appendix E, Table 11); ALFWorld adds game-level paired randomization tests (Appendix F, Table 15).
  7. Presentation (mhZ1, KHvN, FNZH). A new Section 2 walks concrete skills through extraction, compilation, projection, and one evolution round before any notation; Section 3.4 and Table 1 separate Lean-verified guarantees from empirical LLM components; authorization and publication bookkeeping moved to Appendices A–D; Section 5 positions SkillWorld against STRIPS/PDDL planning.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.