- 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
- 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.
- 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
- 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 . The row-deletion example shows a successful edit, but not how correctness is determined.
- ScienceWorld: Appendix A.2 treats focus as terminal and requires . 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.
- 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
- 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 reach the prompt, given that it is absent from the contract? How is the macro stage updated when the agent deviates from the suggested action?
- In the spreadsheet row-deletion example, what condition does 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.
- 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
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.
| ALFWorld | ScienceWorld | SpreadsheetBench | WebShop | |
|---|---|---|---|---|
| Offline corpus | 32 expert demonstrations (8 from each of 4 task categories) sampled from 206 in ReBel-ALFWorld-SFT-Trajectories | 118 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) | 30 | 10–120 | 12 turns | 18 |
| Evaluation set | Seen: 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 types | 200 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 rule | Binary success; success rate × 100 | Binary success (episode score = 100); success rate over variations | Binary 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 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 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 , 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".
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.
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=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 ϕ 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), Add(a), Del(a), and 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), so task-specific information enters through the instruction q. For example,
target:identifiedchecks that the target object type has been parsed from the instruction.Why they can be trusted. We provide four safeguards and measurements:
target:held, 99.7% on SpreadsheetBenchworkbook:inspected, and 98.5% on WebShopproduct:selected.