acceptodds
Under review as a conference paper at ICLR 2027

From Trajectories to Hierarchical Skill Graphs with Semantic Contracts

Abstract

External skills enable language-model agents to reuse experience without parameter updates. However, the quality of document-based skills depends on the ability of an LLM to preserve procedural knowledge during summarization, while static skill loading fails to adapt guidance to changing interaction phases. Graph-based representations support structured retrieval, but historical dependencies alone do not establish current action applicability. To address these limitations, we introduce Semantic Contract Graph (SCG), a framework that integrates hierarchical skill learning with semantic contract evaluation. Offline, SCG recursively composes recurring action sequences into a hierarchical graph of reusable skills. Online, it retrieves a phase-relevant subgraph and evaluates whether action preconditions hold in the current context. Together, the retrieved subgraph and semantic verdicts condition a frozen agent through prompt augmentation. Experiments on ALFWorld, ScienceWorld, SpreadsheetBench, and WebShop show that SCG improves task performance while reducing interaction rounds. Ablation studies reveal the contributions of graph structure and semantic guidance, highlighting the value of integrating skill graphs with live semantic contract checks.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM Agents, Hierarchical Skill Graphs, Phase-Aware Retrieval

Reviews

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

This paper proposes SCG, which guides LLM agents by combining procedures mined from past trajectories with the current task state. Offline, SCG recursively abstracts recurring action sequences into macros and stores their composition and observed transitions in a graph. Online, it retrieves a local subgraph, checks a candidate action’s preconditions with three-valued predicates, and injects the resulting guidance into the prompt. Experiments cover four environments and two LLMs, with ablations on components, sensor implementations, and hierarchical representation.

Critical strengths
  1. Well-motivated problem. The paper distinguishes knowing a procedure from knowing when it applies. A successful past trajectory does not imply its actions suit the current state, so grounding retrieved procedures in task state is a sensible design.
  2. Informative ablations. On ScienceWorld, full SCG (74.9%) clearly beats Graph-Only (60.0%) and Semantic-Only (62.5%), so the two components are complementary. Figs. 4 and 6c show that hierarchical representations consistently beat flat ones across three seeds and several node budgets, which supports preserving recursive composition.
Critical weaknesses
  1. The semantic checks are underspecified. Eq. (6) defines how predicate values yield a verdict, but the paper does not explain how predicates and action requirements are derived from a task, or why they can be trusted.
  • SpreadsheetBench: It is unclear how a new instruction becomes a checkable condition on the saved workbook behind output:verifiedoutput:verified. The row-deletion example shows a successful edit, but not how correctness is determined.
  • ScienceWorld: Appendix A.2 treats focus as terminal and requires goal:progressgoal:progress. The standard boiling task, however, requires focusing on the substance before any state change. Under the stated rule, this correct preliminary action would receive a negative verdict. Together, these examples raise doubts about whether the contracts reliably assess action applicability, which is the paper’s central contribution.
  1. The baseline comparisons are hard to interpret. The paper does not specify which offline trajectories the memory/skill baselines receive, or whether their interaction budgets match SCG’s. Several other details are also missing: evaluation set sizes, the definition of the seen/unseen splits, how evaluation tasks are separated from offline trajectories, and the scoring rule (e.g., whether SpreadsheetBench accuracy gives partial credit). Without these, the reported gains cannot be attributed to better reuse of comparable experience rather than to differences in the experience available.
Questions for authors
  1. For the ALFWorld step in Table 3 where the agent stops searching drawers, please show the selected macro, its current stage, the candidate action, and the injected semantic text. How does held=falseheld=false reach the prompt, given that it is absent from the go−togo-to contract? How is the macro stage updated when the agent deviates from the suggested action?
  2. In the spreadsheet row-deletion example, what condition does output:verifiedoutput: verified check, and how is that condition derived and evaluated? In ScienceWorld, how does the protocol handle a focus action that precedes the required state change? Please report the sensor outputs and verdicts for both cases.
  3. What offline trajectories and interaction budgets does each baseline receive, compared with SCG’s? Please also report evaluation set sizes, what the seen/unseen splits mean, how evaluation tasks are separated from offline data, and the scoring rule for each benchmark.
3 comments
AuthorsOpenReview ↗

Response to Reviewer Q7Wo [1/3]

We thank the reviewer for the constructive feedback. Below, we address each weakness and question.

W1: How predicates and action requirements are derived, and why they can be trusted

We thank the reviewer for this point. The original Appendix A.2 was too terse. The revision expands it into Appendix A.3 (the protocols used in our experiments, with sensor outputs and verdicts at run time) and Appendix A.4 (Semantic Protocol Synthesis: prompt, template, validation checks, and run-to-run consistency).

  • How predicates and requirements are derived. Predicates and action requirements are defined once per environment, not per task. A single call to the base LLM receives a digest of N=24N=24 offline trajectories: the task instruction, the ordered actions, truncated observations, admissible commands, and the episode outcome. It also receives an action-verb histogram from the tokenizer ϕ\phi used for graph learning. The call returns a protocol with an action inventory, at most six three-valued predicates, a sensor for each predicate, and a contract for each action schema with Req(a)\mathrm{Req}(a), Add(a)\mathrm{Add}(a), Del(a)\mathrm{Del}(a), and Term(a)\mathrm{Term}(a) (Appendix A.4.1–A.4.3). Each task then instantiates the same protocol. The sensors evaluate every predicate from the live context xt=(q,ot,At,ht)x_t=(q,o_t,\mathcal{A}_t,h_t), so task-specific information enters through the instruction qq. For example, target:identified checks that the target object type has been parsed from the instruction.

  • Why they can be trusted. We provide four safeguards and measurements:

  1. Automatic validation (Appendix A.4.4). Every candidate protocol must pass seven mechanical checks. These include reachability: every predicate required by a terminal action must be established by some non-terminal action. Otherwise the terminal gate could never open. Failures are returned to the model for at most two repair turns, and no human edits the generated file.
  2. Stability across runs (Appendix A.4.5, Table 7). Across three independent syntheses per environment, all runs agree exactly on the terminal action and recover essentially the same action inventory. Meaning-level predicate agreement is 0.83 on ALFWorld and 0.82 on WebShop. Most disagreement is in naming and granularity, not in dependencies.
  3. Accuracy of predicate judgments (Section 4.5, Table 4). Against labels from explicit environment feedback, rule-based sensors reach 99.8–100.0% on ALFWorld target:held, 99.7% on SpreadsheetBench workbook:inspected, and 98.5% on WebShop product:selected.
  4. Conservative terminal rule (Eq. (6)). Sensors return Unknown, not False, when evidence is missing. A terminal action requires every precondition to be True, so an unverified predicate cannot commit the episode.
AuthorsOpenReview ↗

Response to Reviewer Q7Wo [2/3]

W2: Offline data, interaction budgets, evaluation sizes, splits, and scoring

We thank the reviewer for pointing out these missing details. We have added them to Section 4.1 and Appendix A.1–A.2. They are summarized below.

ALFWorldScienceWorldSpreadsheetBenchWebShop
Offline corpus D\mathcal{D}32 expert demonstrations (8 from each of 4 task categories) sampled from 206 in ReBel-ALFWorld-SFT-Trajectories118 self-generated trajectories (skill-free agent loop)145 self-generated trajectories (skill-free agent loop)5,029 expert trajectories with terminal reward 1.0
Step cap (identical for all methods)3010–12012 turns18
Evaluation setSeen: 140 games (official valid_seen); Unseen: 134 games (official valid_unseen)Seen: 194 variations (official valid split); Unseen: 211 variations (official test split); 24 task types200 held-out tasks from SpreadsheetBench-Verified (400 tasks, 1:1 train/test split)128 instructions, stratified by category (43 options / 43 hidden / 42 plain)
Scoring ruleBinary success; success rate × 100Binary success (episode score = 100); success rate over variationsBinary success: the output workbook passes all test cases (hard restriction, no partial credit)Binary success: final reward = 1.0 (reward ≥ 0.999); success rate × 100

All four benchmarks use binary success, so no reported accuracy includes partial credit.

  • Offline data. All experience-based baselines (SkillLens, ExpeL, Memp, GoS, and SkillTTA) receive the same offline corpus D\mathcal{D} as SCG. ReAct uses no offline data. The reported differences therefore come from how each method reuses the same experience, not from access to different experience.

  • Interaction budget. The step cap is matched across all methods within an environment, so every method in Table 1 operates under an identical budget (Appendix A.2.2). Caps differ across environments because the benchmarks have different natural horizons: ALFWorld requires navigation between receptacles, whereas a SpreadsheetBench turn executes a complete script. SCG adds no environment interactions. The retrieval budget Ksub=16K_{sub}=16 limits only the prompt content per step.

  • Splits and separation from offline data. On ALFWorld and ScienceWorld, the seen and unseen columns follow the official benchmark splits. ALFWorld uses valid_seen and valid_unseen, where unseen games take place in room layouts not seen during training. ScienceWorld uses the official valid (seen) and test (unseen) variations. On SpreadsheetBench, we split SpreadsheetBench-Verified 1:1 into train and test (seen) halves and evaluate only on the 200 held-out test (seen) tasks. We do not divide SpreadsheetBench further into seen and unseen sets, because it consists of isolated, self-contained operations (e.g., single formula or cell edits) with no natural notion of transfer. We do not split WebShop, because it combines a large product catalog with open-ended instructions, so any partition would be arbitrary or heavily overlapping.

  • Consolidated configuration. Appendix A.2 (Table 5) lists every graph-induction, retrieval, and inference parameter for each environment, together with the resulting graph sizes. Graph induction is deterministic given D\mathcal{D}, so a given corpus and these settings always reproduce the same graph.

Q1: In the Table 8 ALFWorld example, how do retrieval, the rendered state, and the contract gate produce the observed trace?

At the first step, retrieval selects the macro go-to → take → go-to → move at stage 1/4, with candidate go-to(?destination). The go-to contract has no requirements, so the gate is "allowed". target:held=false still reaches the prompt for two reasons. The controller renders the full grounded state on every round, independent of the candidate's contract. That fact also turns on the adapter's search control ("Target is not currently available… prefer unvisited open surfaces"). The worker's reasoning cites this control when it moves from drawer 1 to countertop 1. The contract acts later: once the butterknife is held, the terminal move is gated on operation:complete=false until the agent cleans it.

Macro stages are not stored pointers. Each round, every candidate macro's stage is recomputed by aligning the recent action history with the macro's plan prefixes, restarting at step 1 if nothing matches, and the seed is re-selected. A deviation therefore either resets the stage or leads to a macro consistent with the new history. For example, after an unsuggested clean, the next seed is clean → go-to → move at stage 3/3. We will add this per-step trace to the appendix and correct the wording "the contract (held=false) leaves drawers".

AuthorsOpenReview ↗

Response to Reviewer Q7Wo [3/3]

Q2: How are output:verified (SpreadsheetBench) and the focus verdict (ScienceWorld) determined?

We thank the reviewer for pointing out these missing details.

SpreadsheetBench. output:verified checks that the saved workbook passed a task-specific verification after the edit. A rule-based sensor derives it from the execution history, with no LLM call and no access to the grader. It becomes True only if code run after a successful write reports an explicit pass (e.g., "validation passed") or the saved output is re-inspected. It is a precondition of the terminal submit contract and is shown to the policy as guidance. In row-deletion task 374-31, output:verified remained False throughout, because the agent's code printed the saved output but reported no explicit verification result. The submit requirement on output:verified was therefore reported as unsatisfied.

ScienceWorld. The protocol treats focus as the terminal commitment, and its verdict depends on whether the required state change is visible. A focus issued before the change is treated as a non-terminal step, not as task completion. We add a "freeze lead" example in Appendix A.3.1. Before the freeze, the sensors report goal:progress=true and device:activated=unknown, and the state change is not yet visible. focus(?object) is therefore non-terminal (terminal_ready=false), while activate(?object) has its requirement location:known satisfied and is selected, so the agent activates the freezer. After "The lead is frozen solid.", device:activated=true, and focus(?object) becomes terminal with requires=[goal:progress]. That requirement is satisfied, so terminal_ready=true, and the agent focuses on the lead. These verdicts serve as guidance to the policy.

We hope these clarify the details.

Q3: Offline trajectories and budgets per baseline, evaluation sizes, split meaning, separation from offline data, and scoring rules

Please see our response to W2, which reports all of these per benchmark.

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

This work addresses two limitations of existing skill representations for LLM-based agents: their reliance on LLMs' ability to extract useful skills and the inflexibility of static skill loading during dynamic execution. Specifically, the authors propose SCG, a framework that constructs hierarchical macro-action graphs from offline agent trajectories and dynamically retrieves local subgraphs during online execution. SCG further incorporates environment-specific semantic contracts, grounded through rule-based or LLM-based sensors, to provide prompt-level checks of action preconditions and expected effects. Experiments across four diverse benchmarks and two base models show that SCG outperforms multiple baselines in both task accuracy and interaction efficiency. Comprehensive ablation studies are also conducted to evaluate the contributions of its key components.

Critical strengths
  1. SCG addresses two key limitations of existing skill representations through hierarchical skill graphs and semantic contracts. These two components serve complementary functions rather than being arbitrarily combined, making the overall design well motivated.

  2. SCG is a training-free framework, which makes it attractive for practical deployment. The paper also reports both task accuracy and token consumption, showing that the performance improvements come with comparable or lower token costs.

Critical weaknesses
  1. SCG is positioned as a graph-based skill representation method, yet the paper lacks direct comparisons with closely related graph-based skill methods. This makes it difficult to assess its advantages over existing approaches and establish the novelty of the proposed representation.
  2. Semantic contracts are a core component of SCG, but their construction process is under-specified. Appendix A.2 states that an LLM generates predicates, sensor implementations, and action contracts from trajectories, but provides little detail about the generation prompts, quality control, human intervention, or consistency across runs. It is therefore unclear how automated this process actually is, how much domain-specific engineering is required for a new environment, and whether the contract construction process itself can be learned directly from trajectories. These omissions also raise concerns about reproducibility.
  3. Since contract verification depends on environment-specific predicates and their evaluation mechanisms, additional discussion or evaluation of predicate-level reliability would strengthen the paper. Where feasible, quantitative results on predicate judgments and a comparison between rule-based and LLM-based verification would help characterize their respective strengths, limitations, and applicability across environments.
  4. The paper describes the main stages of graph construction, but some implementation choices may require further clarification. A consolidated summary of key parameters, filtering thresholds, stopping conditions, and experimental configurations would make the method easier to reproduce. Sensitivity analyses for the most consequential parameters would also help establish the robustness of the reported results.
Questions for authors
  1. Could the authors clarify the main technical differences between SCG and representative graph-based skill-learning or hierarchical-planning methods? If direct comparisons are feasible under comparable settings, one or two representative baselines should be included.
  2. Beyond the existing ablations and Flat--Hier comparison, what evidence indicates when hierarchical graph organization provides the greatest benefit, and how does its contribution interact with semantic contracts?
  3. The authors should provide a more detailed description of SCG, particularly the steps involving handcrafted components or human intervention. Clarifying which parts are fully automated, which require domain-specific engineering, and how the different components interact would help readers better understand the framework's design and mechanisms, while also improving reproducibility.
4 comments
AuthorsOpenReview ↗

Response to Reviewer u7cp [1/4]

We thank the reviewer for the constructive feedback. Below, we address each weakness and question.

W1: Missing comparison with graph-based skill methods (need to update)

We thank the reviewer for pointing this out. We add two concurrent methods as baselines (Section 4.1 and Table 1): SkillTTA, which formulates skills dynamically at test time, and GoS (Graph-of-Skills), which uses a graph as the skill representation. Results are as follows (accuracy % / mean rounds):

DeepSeek-V4-Flash

MethodALFWorld seenALFWorld unseenScienceWorld seenScienceWorld unseenSpreadsheetBenchWebShop
SkillTTA94.3 / 8.289.8 / 8.166.0 / 14.267.3 / 17.637.5 / 4.132.8 / 10.3
GoS92.9 / 9.888.8 / 11.372.2 / 11.469.2 / 13.436.0 / 4.048.4 / 7.6
SCG96.4 / 10.290.3 / 11.776.8 / 13.073.0 / 14.476.0 / 3.350.0 / 8.7

Qwen-3.6-Flash

MethodALFWorld seenALFWorld unseenScienceWorld seenScienceWorld unseenSpreadsheetBenchWebShop
SkillTTA77.1 / 10.076.9 / 9.962.9 / 14.363.5 / 16.725.0 / 10.333.6 / 9.5
GoS90.0 / 14.183.6 / 14.158.2 / 13.855.5 / 17.140.0 / 6.641.4 / 8.3
SCG90.7 / 13.087.3 / 12.966.0 / 13.759.2 / 16.943.5 / 2.549.8 / 8.7

SCG outperforms GoS in all 12 settings and SkillTTA in 11 of 12. The only exception is ScienceWorld unseen with Qwen-3.6-Flash (59.2 vs. 63.5). SkillTTA uses fewer rounds on ALFWorld, but it needs lots of tokens to generate skill as shown in updated Figure 3. These results indicate that combining graph-based skill representation with dynamic, state-dependent guidance outperforms either approach alone.

W2: Construction of semantic contracts is under-specified

We thank the reviewer for this point. We have expanded the original Appendix A.2 into Appendix A.3, which lists the protocols and the run-time sensor outputs, and Appendix A.4, which gives the prompt, output template, validation checks, and consistency results.

  • Synthesis. A single LLM call per environment, made before any evaluation, reads a digest of N=24N=24 offline trajectories and an action-verb histogram from the tokenizer ϕ\phi. It returns a complete protocol: an action inventory, at most six three-valued predicates with their sensors, and a contract per action schema (Req\mathrm{Req}, Add\mathrm{Add}, Del\mathrm{Del}, Term\mathrm{Term}). The prompt, template, and checks are shared across environments, and only the trajectory evidence changes. Predicates must be checkable from the recorded context, never from privileged simulator state.
  • Quality control. Each candidate must pass seven automatic checks (Appendix A.4.4). For example, every predicate a terminal action requires must be established by some non-terminal action. Failures go back to the model for at most two repair turns, and no human edits the result.
  • Consistency (Appendix A.4.5, Table 7). Across three independent runs per environment, all runs pick the same terminal action and nearly identical action inventories. Meaning-level predicate agreement is 0.83 on ALFWorld, 0.82 on WebShop, and 0.47 on SpreadsheetBench. Most differences are in naming and granularity, not in dependencies.
AuthorsOpenReview ↗

Response to Reviewer u7cp [2/4]

W3: Reliability of predicate-level judgments

Thank you for this suggestion. Predicate reliability has two parts: whether the right predicates are defined for each environment, and whether each predicate is judged correctly at run time. We now address both.

  1. Reliability of predicate definitions (Appendix A.4). Protocols are synthesized by the base LLM from offline trajectories with a fixed prompt and template. Each candidate must pass automatic checks, including that every predicate required by a terminal action can be established by some non-terminal action. Across three independent runs per environment (Table 7, Appendix A.4.5), all runs select the same terminal action. Meaning-level predicate agreement is 0.83 on ALFWorld and 0.82 on WebShop. Disagreement comes mainly from naming and granularity rather than from different dependencies.
  2. Reliability of predicate judgments (Section 4.5). We evaluate individual predicate judgments on archived traces. We select predicates that both sensors support and whose truth is explicitly recorded by the environment, so reference labels can be constructed independently: ALFWorld target:held: the empty initial inventory and confirmed pickup/placement feedback. SpreadsheetBench workbook:inspected: execution-confirmed workbook information (e.g., sheet names, dimensions). WebShop product:selected: explicit product-page and results-page evidence.

A state is the context before an agent action, so one task can contribute several states. Accuracy is computed over labeled states where both sensors return True or False.

Environment / predicateEvaluated statesRule acc.LLM acc.
ALFWorld seen, target:held1,422100.0%87.2%
ALFWorld unseen, target:held1,36999.8%88.1%
SpreadsheetBench, workbook:inspected34099.7%99.4%
WebShop, product:selected77598.5%98.6%

When the evidence appears in the current observation, the sensors are comparably reliable. For target:held, which requires tracking pickups and placements across the episode, the LLM sensor trails by about 12 points. This agrees with Table 2, where SCG (rule) outperforms SCG (LLM) on ALFWorld (93.4 vs. 90.5) with fewer tokens (2.2M vs. 4.0M). Rule-based sensors run deterministically at no inference cost but cover only the cases their rules anticipate. LLM-based sensors can express semantic judgments but cost one call per step and are less reliable on history-dependent facts. These results support the per-predicate routing in our synthesis prompt (Appendix A.4.2): rules for keyword, regex, or action-history checks, and the LLM sensor only for semantic judgments. We have added this analysis as Section 4.5.

W4: Implementation details, consolidated parameters, and sensitivity

We thank the reviewer for this suggestion. We have added a consolidated configuration appendix with a sensitivity analysis (Appendix A.2).

  • Configuration (Table 5). Table 5 lists every graph-induction, retrieval, and inference parameter per environment, together with the resulting graph sizes. Algorithm 1 stops when the macro budget MM is reached or no candidate satisfies Eq. (1). Values that differ across environments are explained in Appendix A.2.2. The support threshold is set from corpus size before any evaluation, and step caps are matched across all methods. Graph induction involves no sampling, so a given corpus and these settings always reproduce the same graph.
  • Sensitivity (Appendix A.2.3, Table 6). We sweep the two thresholds that gate macro admission on ALFWorld and SpreadsheetBench: Lmax⁡L_{\max} is not an active constraint. Over {2, 3, 4, 6, 8, 12}, the induced graph is identical, with the same node set. Every admitted macro has two children because ties resolve toward the shortest pattern, so depth comes from recursive re-compression. nmin⁡n_{\min} changes the graph but not the outcome. Setting nmin⁡=2/3/5n_{\min}=2/3/5 yields 128/102/63 macros on ALFWorld and 63/41/26 on SpreadsheetBench, yet accuracy on a 12-task audit split is identical in all six runs. The released configuration thus lies in a flat region rather than at a tuned optimum. Retrieval returns at most Ksub=16K_{sub}=16 nodes per step, and high-support macros dominate the ranking, so the marginal low-support macros admitted at nmin⁡=2n_{\min}=2 rarely get retrieved.
AuthorsOpenReview ↗

Response to Reviewer u7cp [3/4]

Q1: Technical differences from graph-based skill and hierarchical-planning methods, and direct comparison

The core idea of SCG is that graph representation and dynamic skill formulation are complementary, and that neither alone is sufficient. We describe the differences along that axis.

  • Technical difference. Graph-based methods supply procedural structure but fix it offline. HiSkill (Hao et al., 2026) and SkillGraph (Li et al., 2026a) encode authored or learned relations. GraSP (Xia et al., 2026) is closest to us because it carries precondition–effect edges, but those preconditions are fixed at construction time and describe what held historically. Dynamic methods such as SkillTTA (Wang et al., 2026b) adapt guidance to the episode but carry no explicit precondition structure. SCG combines the two. The graph asserts what typically follows what, while a semantic contract, evaluated against the live context xtx_t at every step, asserts what currently holds. A graph can correctly encode that selection precedes purchase without establishing that this product satisfies this instruction. Two further points distinguish SCG. First, our macros come from a deterministic compression over tokenized trajectories, with no model call in the loop. Second, Eq. (6) grounds predicates with three values and an asymmetric rule: a non-terminal action requires that no precondition be False, whereas a terminal action requires all preconditions to be True, so Unknown cannot commit an episode.
  • Direct comparison. As described in our response to W1, we added Graph-of-Skills (graph-structured skill retrieval) and SkillTTA (dynamic skill formulation) as baselines. Both use the same worker model, offline corpus D\mathcal{D}, and step budget as SCG.

Q2: When does hierarchical organization help most, and how does it interact with semantic contracts?

Thank you for this question. The two components play different roles. The skill graph is procedural memory: it retrieves what has worked next in similar past contexts. The semantic contract checks whether a candidate action is feasible in the current state. Each macro stores a complete multi-step routine as one node, so under a fixed node budget the hierarchical graph retrieves whole routines rather than fragments of atomic actions. The benefit grows with the retrieval budget: Hier gains up to +4.33 on SpreadsheetBench at K=8K=8 and K=16K=16 (Figure 4). The graph's contribution is also largest when contracts alone leave substantial room for improvement. Over Semantic-Only, the graph adds +12.4 on ScienceWorld but only +0.4 on ALFWorld (Table 2).

To go beyond the existing ablations, we ran a new experiment that crosses graph organization (Flat vs. Hier) with semantic contracts (on vs. off) at K=16K=16 (Table 3).

BenchmarkContractsFlatHierHier − Flat
SpreadsheetBenchOn70.775.0+4.3
Off69.072.2+3.2
On − Off+1.7+2.8+1.1
WebShopOn43.545.8+2.3
Off39.841.4+1.6
On − Off+3.7+4.4+0.7

The bold cells are the interaction terms. Each is the Hier gain with contracts on minus the Hier gain with contracts off (4.3 − 3.2 = 1.1). Equivalently, it is the contract gain on Hier minus that on Flat (2.8 − 1.7 = 1.1). A positive value means the combined gain exceeds the sum of the isolated gains. The interaction is positive on both benchmarks (+1.1 and +0.7), so the two components are complementary. Hierarchy helps more when contracts are on (+4.3 vs. +3.2 on SpreadsheetBench; +2.3 vs. +1.6 on WebShop). Contracts help the hierarchical graph more than the flat one (+2.8 vs. +1.7; +4.4 vs. +3.7). This suggests that macros propose complete routines while contracts confirm whether each next step is feasible, allowing more of the retrieved routine to be used. We have added this experiment to Section 4.3.

AuthorsOpenReview ↗

Response to Reviewer u7cp [4/4]

Q3: Which parts are automated, which need domain-specific engineering, and how do the components interact?

We thank the reviewer for this point. The original Appendix A.2 was too terse. The revision expands it into Appendix A.3 (protocols used in the experiments and run-time sensor outputs) and Appendix A.4 (the synthesis pipeline, prompt, template, validation checks, and consistency). The table below summarizes how each component is produced.

StageComponentHow it is producedHuman or environment-specific input
OfflineTrajectory corpus D\mathcal{D}Public expert demonstrations (ALFWorld, WebShop) or self-generated trajectories from a skill-free agent loop (ScienceWorld, SpreadsheetBench)Choice of trajectory source (Appendix A.1)
OfflineSkill graph (Algorithm 1)Deterministic recursive compression; no LLM callPer-environment thresholds, set once from corpus size (Table 5)
OfflineSemantic protocolOne LLM call per environment, seven automatic checks, at most two repair turnsNone; no human edits
OnlinePredicate groundingRule-based sensors (no LLM call) or one LLM sensor call per stepNone
OnlineSeed selection and subgraph hydrationFixed scoring function and budget Ksub=16K_{sub}=16None
OnlineContract verdictEq. (6), deterministicNone
  • How the components interact at each step. The sensors first ground every predicate from the live context xtx_t. The retriever then scores macros by relevance, staged next action, utility, and transition support, selects a seed, and expands it into a subgraph of at most KsubK_{sub} nodes. The contract evaluates the candidate action with Eq. (6). The subgraph and the rendered verdict are concatenated into the prompt, and the frozen policy selects the next action. Appendix A.3.1 shows this sequence on a ScienceWorld episode, with the sensor outputs and verdicts at each decision point.
Reviewer_wEiDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This article introduces Semantic Contract Graph (SCG), which organizes action sequences from previous tasks into a hierarchical skill graph. When performing a new task, the system retrieves relevant processes and then checks whether the conditions for executing an action are met, adding this information to the prompts to help the model choose the next action without updating model parameters.

The authors evaluated it on four interactive benchmarks and two models, and used ablation studies to analyze the roles of the skill graph, semantic checking, and hierarchical structure. Overall results are pretty good, but the necessity of some key designs and experimental details still need further clarification.

Critical strengths
  1. Overall speaking, combining offline skill graphs with live semantic contracts is a smart fix for the "context rot" problem. Instead of dumping a massive skill document into the prompt, retrieving just the relevant subgraph and checking if the preconditions actually hold in the current state keeps the agent focused and saves a ton of tokens.
  2. I think the ablation studies are clear. The case studies in Table 3 perfectly show why you need both pieces: the graph pushes the agent to the next procedural phase, while the semantic contract stops it from doing stupid things (like buying the wrong item or placing an uncleaned object).
Critical weaknesses

1.Comparison with closely related methods is not enough. The paper discusses SkillTTA and several graph-based skill methods but does not compare against them. Without representative comparisons, it is difficult to judge SCG’s advantages over existing approaches. 2. The separation between offline learning and evaluation is unclear. The paper does not clearly explain whether the trajectories used to build the graph and semantic contracts overlap with evaluation tasks, or whether the experience-based baselines use the same offline data. This makes it difficult to assess generalization and comparison fairness.

Questions for authors

1.Could you compare SCG with closely related methods, such as SkillTTA or a representative graph-based skill method, or explain why a fair comparison is not feasible? 2.How are the trajectories used for graph and contract construction separated from the evaluation tasks? Do SkillLens, ExpeL, and Memp use the same offline trajectory data? Please clarify the splits and any overlap. 3.Could you explain, with a concrete example, how a semantic sensor checks a condition such as “the output is verified”? This detail matters because different sensor judgments may lead to different action guidance, and the ALFWorld results suggest that semantic guidance is a key contributor to performance.

2 comments
AuthorsOpenReview ↗

Response to Reviewer wEiD [1/2]

We thank the reviewer for the constructive feedback. Overall, we reframe SCG as a combination of graph-based experience storage and online dynamic skill generation. Below, we address the main concerns and answer the questions.

W1: Missing comparison with closely related methods

We thank the reviewer for this helpful comment. We have added two representative concurrent baselines to the revised manuscript (Section 4.1 and Table 1): SkillTTA, which synthesizes task-specific skills on the fly at test time, and GoS (Graph-of-Skills), which uses a graph as the skill representation. The results are as follows (accuracy % / mean rounds):

DeepSeek-V4-Flash

MethodALFWorld seenALFWorld unseenScienceWorld seenScienceWorld unseenSpreadsheetBenchWebShop
SkillTTA94.3 / 8.289.8 / 8.166.0 / 14.267.3 / 17.637.5 / 4.132.8 / 10.3
GoS92.9 / 9.888.8 / 11.372.2 / 11.469.2 / 13.436.0 / 4.048.4 / 7.6
SCG96.4 / 10.290.3 / 11.776.8 / 13.073.0 / 14.476.0 / 3.350.0 / 8.7

Qwen-3.6-Flash

MethodALFWorld seenALFWorld unseenScienceWorld seenScienceWorld unseenSpreadsheetBenchWebShop
SkillTTA77.1 / 10.076.9 / 9.962.9 / 14.363.5 / 16.725.0 / 10.333.6 / 9.5
GoS90.0 / 14.183.6 / 14.158.2 / 13.855.5 / 17.140.0 / 6.641.4 / 8.3
SCG90.7 / 13.087.3 / 12.966.0 / 13.759.2 / 16.943.5 / 2.549.8 / 8.7

SCG outperforms GoS in all 12 settings and SkillTTA in 11 of 12. The only exception is ScienceWorld unseen with Qwen-3.6-Flash (59.2 vs. 63.5). SkillTTA uses fewer rounds on ALFWorld, but it needs lots of tokens to generate skill as shown in updated Figure 3. These results indicate that combining graph-based skill representation with dynamic, state-dependent guidance outperforms either approach alone.

W2: Unclear boundary between offline learning and evaluation

We apologize for the confusion. The offline corpus D\mathcal{D} is collected once before evaluation. Both graph learning and semantic protocol synthesis use it (Appendix A.1 and A.4.1). For ALFWorld, we use 32 expert demonstrations sampled from 206 in ReBel-ALFWorld-SFT-Trajectories. For WebShop, we use 5,029 expert trajectories with terminal reward 1.0. For ScienceWorld and SpreadsheetBench, we use 118 and 145 self-generated trajectories, collected with a simple agent loop without predefined skills.

To examine generalization, we report seen and unseen results on ALFWorld and ScienceWorld following the official splits. ALFWorld uses valid_seen (140 games) and valid_unseen (134 games), where unseen games take place in room layouts not seen during training. ScienceWorld uses the valid (194 variations) and test (211 variations) splits. On SpreadsheetBench, we split SpreadsheetBench-Verified 1:1 into train and test halves and evaluate on the 200 held-out test tasks.

We do not divide SpreadsheetBench further into seen and unseen sets, because it consists of isolated, self-contained operations (e.g., single formula or cell edits) with no natural notion of transfer. We also do not split WebShop, because it combines a large, diverse product catalog with open-ended instructions, so any partition would be arbitrary or heavily overlapping. All experience-based baselines (SkillLens, ExpeL, Memp, GoS, and SkillTTA) use the same offline data as SCG, ensuring a fair comparison. We have added these details to Section 4.1 and Appendix A.1.

Q1: Comparison with SkillTTA or a graph-based skill method

Please see our response to W1. SkillTTA and GoS are now included in Table 1.

Q2: Separation of offline trajectories from evaluation, and data used by baselines

Yes. SkillLens, ExpeL, and Memp, as well as the newly added GoS and SkillTTA, use the same offline trajectories as SCG. The splits and their relation to the offline data are described in our response to W2, Section 4.1, and Appendix A.1.

AuthorsOpenReview ↗

Response to Reviewer wEiD [2/2]

Q3: Concrete example of how a sensor checks "the output is verified"

We thank the reviewer for this valuable question.

  • Sensor definition. A sensor is a three-valued function ft(p)=f(xt,p)∈True,False,Unknownf_t(p) = f(x_t, p) \in \text{True}, \text{False}, \text{Unknown} over the live context xt=(q,ot,At,ht)x_t = (q, o_t, \mathcal{A}_t, h_t) (Section 3.3.1). It reads only the instruction, the current observation, the available actions, and the interaction history. It never reads privileged simulator state or the grader. Unknown means the context does not provide enough evidence.
  • Example: output:verified in SpreadsheetBench. This predicate means that task-specific verification passed. The terminal action submit requires both output:exists and output:verified, and only verify-output establishes the latter (Appendix A.3). The rule-based sensor replays the step history for evidence about the saved workbook. It returns True on an explicit verifier outcome (e.g., "all cells match"). It returns False if the saved file was never read back. Otherwise it returns True only if a task-family rule is met (a read-back, a re-check, and a second read-back), and Unknown if not. Since Eq. (6) requires every precondition of a terminal action to be True, Unknown cannot commit the episode: submit is marked not ready, and the staged next action becomes verify-output.
  • Example: ALFWorld, "put a clean butterknife on the countertop" (Appendix B.3, Table 8). While target:held is False, the guidance steers the agent from drawer search to acquiring the knife. While operation:complete is False, placement is reported as blocked. After the agent cleans the knife, the sensor returns True, placement is reported as allowed, and the agent succeeds. Graph-Only lacks these predicates and loops over empty drawers until timeout. The verdict is added to the prompt and does not override the policy's action (Section 3.3.2).
  • Reliability of sensor judgments (Section 4.5, Table 4). Against labels from explicit environment feedback, rule-based sensors reach 98.5–100.0% accuracy. LLM-based sensors are within 0.3 points when the evidence is in the current observation. On the history-dependent target:held, they trail by about 12 points. This matches Table 2, where rule-based SCG beats LLM-based SCG on ALFWorld (93.4 vs. 90.5) with fewer tokens (2.2M vs. 4.0M).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal and Revisions

We thank all reviewers for their constructive feedback. The main changes are:

  1. New baselines (wEiD, u7cp). We added SkillTTA (dynamic test-time skills) and GoS (graph-based skills) to Table 1. SCG outperforms GoS in all 12 settings and SkillTTA in 11 of 12, with SkillTTA also using far more tokens (Figure 3). This supports our view that graph structure and dynamic guidance are complementary.

  2. Semantic contracts: construction and reliability (u7cp, Q7Wo).

    • Appendix A.3–A.4 now detail the protocols and the synthesis pipeline: one LLM call per environment, seven automatic checks, and no human edits.
    • The protocols are stable across three runs, which agree on the terminal action (Table 7).
    • Rule-based sensors reach 98.5–100% accuracy (new Section 4.5).
    • A conservative terminal rule keeps unverified states from ending an episode.
  3. Offline data, splits, and budgets (wEiD, Q7Wo). Section 4.1 and Appendix A.1–A.2 now document:

    • the offline corpora, which all experience-based baselines share with SCG;
    • the official seen/unseen splits;
    • step caps that are identical across methods;
    • binary success scoring with no partial credit.
  4. Configuration and sensitivity (u7cp). Table 5 gives the full parameter list. Table 6 shows that accuracy stays unchanged across graph-threshold settings, so our configuration is not tuned to an optimum.

  5. Hierarchy × contracts (u7cp). A new 2×2 experiment (Table 3) shows a positive interaction on SpreadsheetBench (+1.1) and WebShop (+0.7), confirming that the two components complement each other.

  6. Clarifications (u7cp, Q7Wo). We added a stage-by-stage table of what is automated, explained how SCG differs technically from prior graph-based methods, and added step-by-step traces for the ALFWorld, SpreadsheetBench, and ScienceWorld examples.

We hope these revisions address the reviewers' concerns and are happy to clarify further.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.