acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Skill libraries have emerged as a promising paradigm for enabling LLM agents to learn from experience, yet existing approaches typically treat skills as flat, independent units with limited explicit modeling of inter-skill relationships. Without such structure, compositional planning is weak, skill granularity is difficult to maintain, and relational signals between skills cannot be accumulated over training. To address these limitations, we propose SKILLGraph, which organizes skills into a structured skill graph with typed edges encoding prerequisite, enhancement, and co-occurrence relations. The framework revolves around three core stages: (1) Graph construction that distills skills from trajectories and organizes them into a directed dependency graph with typed relational edges; (2) Graph-aware retrieval that recovers dependency-respecting skill sequences through seed selection, graph expansion, and topological ordering; (3) Graph evolution that continuously adapts both skills via insertion, merging, splitting, and deprecation and their relations via RL-driven edge reinforcement, co-occurrence discovery, and pruning. These three stages form a closed training loop, enabling the skill structure and the policy to co-evolve. Experiments on ALFWorld, WebShop, and seven search-augmented QA tasks demonstrate state-of-the-art performance, with substantial gains on complex multi-step tasks requiring skill composition.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph, agent, evolution

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_KHmUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

SKILLGRAPH organizes natural-language skills into a directed graph with prerequisite, enhancement, and co-occurrence relations. It retrieves an ordered collection of skills to guide an LLM agent, updates skill nodes and relations using trajectory feedback and teacher-model operations, and progressively unlocks skills while optimizing the policy with GRPO. Experiments use Qwen2.5-7B-Instruct on ALFWorld, WebShop, and seven search-augmented QA benchmarks. The paper reports improvements over SkillRL and skill-free GRPO, together with graph interventions and analyses of training dynamics and computational cost.

Critical strengths
  1. A relevant and coherent approach to reusable agent knowledge. The paper addresses a meaningful limitation of independent skill retrieval: multi-step tasks can require both relevant advice and knowledge of how that advice composes. Sections 3.1–3.4 integrate retrieval, node maintenance, relation updates, and policy training in a coherent framework. The combination is practically useful, and the appendices provide skill schemas, prompts, hyperparameters, and maintenance details that make the proposal more concrete than a purely conceptual graph formulation.

  2. Encouraging results with interventions relevant to the proposed mechanism. Table 1 reports ALFWorld success of 93.1% versus 89.9% for SkillRL, and WebShop success of 84.4% versus 72.7% (task scores: 91.5 versus 85.2). These gains, especially on WebShop, warrant attention. The evaluation spans household interaction, shopping, and search-based QA. Table 8 further reports that removing prerequisite edges lowers ALFWorld success to 87.5% and WebShop score to 82.5, supporting the utility of those edges within the full system. Flat-library and static-graph controls, together with the cost analysis in Appendix I.3, strengthen the empirical contribution.

Critical weaknesses
  1. The origin and validity of prerequisite structure are not sufficiently established. Appendix A.2 explicitly initializes no prerequisite edges. Section 3.3.2 reinforces existing edges and discovers co-occurrence links, while Appendix A.4 creates prerequisite edges when a teacher splits a skill into ordered sub-skills. This provides one concrete construction mechanism, but the paper does not specify a general operation that discovers a new prerequisite relation between existing skills. It is consequently unclear how much of the claimed dependency discovery comes from execution evidence versus teacher-proposed decomposition. The Figure 2 discussion also attributes growth in prerequisite and enhancement edge counts to path reinforcement, although increasing an existing edge weight cannot itself increase the edge count.

I acknowledge that Appendix A.1 defines the prerequisite/enhancement dependency subgraph and excludes co-occurrence from level computation, and Appendix I.5 distinguishes the relation types. My concern is therefore not that all edge types are indiscriminately ordered. Rather, Equation (2) should explicitly identify its ordering graph, and the update procedure should explain cycle handling. Representative learned prerequisite edges with their provenance and supporting trajectories would help establish that the graph captures valid procedural dependencies.

Teacher-proposed dependencies are not inherently a weakness. The distinction matters because the source and validation of these relations determine what the method learns and whether the claimed dependency-discovery mechanism is reproducible.

  1. The evidence supports the full system more strongly than the proposed explanation of its gains. Appendix I.1 provides useful controls, but retrieval without topology removes dependency expansion and ordering together. Its ALFWorld drop from 93.1% to 59.4% therefore does not isolate order from changes in retrieved content. Prerequisite removal also affects both candidate expansion and ordering. Holding the selected skills fixed and shuffling only their presentation order would clarify whether ordered guidance contributes beyond skill selection. Such an evaluation would test the trained policy’s use of order; a training ablation would additionally be needed to attribute improved learning to order.

Appendix A.3 credits every retrieved skill when an episode succeeds. The maintenance statistics therefore measure successful exposure, not independent utility. This is a plausible heuristic, and I do not require a new causal-credit algorithm. However, the rising node-success curve should not itself be interpreted as validation of skill quality; a targeted maintenance ablation would be useful supporting evidence.

The reported results lack seed-level uncertainty and clearly stated evaluation-set sizes. Appendix I.3 says the supplementary comparisons reuse public SkillRL SFT data, and Appendix I.5 fixes the base model; these are useful controls. However, the paper should consolidate which comparisons also match interaction, teacher, and prompt budgets. This is particularly

Reporting inconsistencies further limit interpretation. The seven SKILLGRAPH entries in Table 2 average to approximately 48.64, consistent with 48.6 in Section 4.2 and Appendix I.4, but not 48.9 in Tables 2 and 6. Table 3 is captioned as success rate and reports WebShop 84.4, matching Table 1 success, whereas Appendix C calls Table 3 task score. These are correctable issues, not evidence that the experiments are invalid, but the quantitative support should be made internally consistent.

Questions for authors
  1. Which operations create prerequisite edges, and how many edges originate from each? If splitting is the only source, please state this explicitly and provide examples showing that the resulting directions reflect genuine prerequisites.

  2. What graph is ordered in Equation (2), and how are cycles handled? How do depth-two backward expansion, the eight-skill cap, and active-skill filtering interact? Please clarify whether returned skills retain all required prerequisites.

  3. With the trained policy and selected skills fixed, how does shuffling only skill order affect success? This is my highest-priority additional experiment, because it directly tests whether the policy uses the ordering. Separate maintenance or unlocking ablations would be useful supporting evidence, rather than prerequisites for answering this question.

  4. Can you report repeated-seed results and evaluation counts for the primary SkillRL comparison, clarify matched budgets, and reconcile the QA averages and WebShop ablation metric? Appendix E also calls step 200 the best-average checkpoint: was it fixed in advance, or selected using held-out QA benchmark results?

Reviewer_tughOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper builds a DAG of "skills" which are short text records written by a teacher model (o3). These skills are created by showing o3 successful and unsuccessful trajectories. Edges are weighted and typed. There is a retrieval step that eventually outputs at most 8 skills which are then prepended to the agent LLM's (qwen model) context. The paper claims SOTA perf on two benchmarks (alfworld and webshop).

Critical strengths

the idea to use more structured forms of skill composition during inference is good. The results are also impressive.

Critical weaknesses

Weaknesses and questions:

  1. It seemed like your method got a cold start with SFT, but wasn't clear if the RL baselines also did? What is the benefit of the proposed graph vs doing SFT on the base model?
  2. Simple baselines missing: a lot of experience based learning claims around how the weights are updated in the graph. But a lot of pruning steps precede the edge-based sampling of the skills. Could you use the tag-matched skills in the context and let the agent decide if they are helpful? Maybe the next two steps as well? What if you just asked the teacher model (o3) to prepend the relevant skills itself based on a task and context description?
  3. The paper borrows a lot of HRL vocabulary (e.g., skills and skill graphs; see Deep Skill Graphs by Bagaria et al, ICML 2021 for instance), but doesnt really engage with it and does not place its contribution in context. Another example is the seminal paper of McGovern et al, ICML 2001, that established the idea of discovering skills based on successful and unsuccessful trajectories.
  4. How did you get the tags for Webshop and QA? You had an example for robots, which made me think that these "tags" were available from the benchmark, but I couldnt figure out where they came from for other domains. Was all the information about the tasks used by your approach--like these tags---made available to all the baselines as well?
Questions for authors

see above

Reviewer_5g5qOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes an evolving graph of natural-language skills for LLM agents. Skills are connected through prerequisite, enhancement, and co-occurrence relations; the paper retrieves them via graph traversal and topological ordering and updates them alongside a policy trained with GRPO. Experiments cover ALFWorld, WebShop, and seven search-augmented QA datasets. The motivation is reasonable, and the reported WebShop gains are promising. However, inconsistencies in the experimental record, an unclear separation between adaptation and evaluation, and insufficient isolation of the graph’s contribution weaken the conclusions.

Critical strengths
  1. Explicitly representing relationships between reusable skills is a sensible approach to multi-step agent tasks. The method is interpretable and integrates with existing policies through textual guidance.
  2. Evaluation covers several task families. The reported WebShop improvements over SkillRL, 6.3 points in task score and 11.7 percentage points in success rate, are potentially meaningful.
  3. The appendices provide useful interventions, threshold sensitivity, teacher costs, and runtime measurements.
Critical weaknesses
  1. Important experimental results are inconsistent. The seven SkillGraph scores in Table 2 average to 48.64, not 48.9; the SkillRL scores average to 47.51, not 47.1. The supported improvement is therefore approximately 1.13 points rather than 1.8. Appendix I.4 gives the correctly rounded means, but the table remains uncorrected.

WebShop metrics are also unclear. Table 3 is captioned as reporting success rates, whereas Appendix C calls them task scores. Table 8 reports task scores but repeats the static-graph value of 70.3 from Table 3. Without clarification, the ablation drops are not reliably interpretable.

Compute accounting likewise requires correction: the four runs in Table 11 imply approximately 350.32 GPU-hours, exceeding the approximately 280 GPU-hours reported for all training runs in Appendix F.

  1. The separation between adaptation and evaluation is unspecified. Validation trajectories are used to generate skills, update statistics, discover relations, and unlock skills. They are therefore adaptation data. The paper does not clearly distinguish these data from checkpoint-selection and final evaluation sets.

For QA, Table 6 reports repeated validation evaluations on the five held-out transfer datasets, while Appendix E motivates the final checkpoint by its highest seven-dataset average. This does not establish leakage, but it leaves unclear whether held-out outcomes influenced graph updates or model selection. Both questions are consequential for the zero-shot claim.

  1. The central dependency-learning mechanism is incomplete. Appendix A.2 initializes no prerequisite edges. The only explicit mechanism for creating them is teacher-ordered splitting in Appendix A.4. It remains unclear how prerequisite relations between independently acquired skills are discovered. Path reinforcement changes existing weights and cannot explain the increase in edge counts attributed to it in Section 4.3.

Retrieval also requires clarification. Equation (1) selects all active general and category-matched skills, but seed-set sizes and category assignment are unspecified. When this set exceeds eight skills, the truncation rule may largely determine retrieval. The paper does not explain how truncation preserves relevant dependencies, how expansion respects locked skills, or how cycles are handled after graph updates.

  1. The feedback and ablations do not establish the claimed structural contribution. Appendix A.3 credits every retrieved skill when an episode succeeds, regardless of whether the policy used it. This measures successful exposure rather than individual usefulness. Similarly, co-occurrence does not establish a prerequisite relation. Neighborhood overlap also need not imply semantic redundancy, particularly under the category-based initialization.

The ablations leave these issues unresolved. Disabling graph evolution removes both content and relational adaptation. Removing topology changes both expansion and ordering. Neither intervention isolates the effect of meaningful relations. The ALFWorld gap between the flat library (89.9) and retrieval without topology (59.4) particularly requires an operational explanation. Controls that shuffle the same retrieved skills or vary edges while holding content and prompt budgets fixed would be more informative.

  1. Statistical support and contribution claims need qualification. Independent-run counts, seed-level variation, and confidence intervals are not clearly reported. ALFWorld splits, episode counts, and the “All” aggregation rule also need specification. These omissions matter for the 3.2-point ALFWorld gain and the corrected 1.13-point QA gain over SkillRL.

SkillRL already co-evolves skills and policy, while Graph of Skills addresses dependency-aware retrieval. The contribution therefore concerns the particular integration and adaptation of typed relations. Describing SkillRL as static obscures this distinction. Moreover, multi-step benchmark performance alone does not demonstrate compositional generalization without an evaluation on held-out skill combinations.

Limitations are:

The acknowledged teacher dependence, single base-model scale, and lack of cross-environment skill transfer are appropriate limitations. Exposure-based credit assignments should also be discussed. Dependency-ordered prompting does not enforce execution order, and progressive unlocking has not been established as a safety mechanism.

Questions for authors
  1. What data are used for policy training, graph adaptation, checkpoint selection, and final evaluation? Do held-out QA outcomes influence any updates or selection decisions, and is the graph frozen during evaluation?
  2. Can the authors reconcile the reported averages, WebShop metrics, and compute totals, and specify the ALFWorld aggregation protocol and which baselines were rerun?
  3. Which operation discovers prerequisites between existing skills? How are cycles, locked nodes, and dependency preservation under the retrieval cap handled?
  4. What precisely distinguishes the flat library and retrieval without topology variants? Are SFT initialization, skill content, teacher usage, and prompt budgets matched?
  5. Can the authors provide independent-run variability and a targeted control that changes only relations or ordering while retaining the same skills?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.