- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes Verifiable Task Decomposition (VTD) to address the limited corrective value of online policy distillation when learning from failed student trajectories. Rather than distilling teacher actions, VTD uses a symbolic graph of verifiable milestones and dependencies constructed before interaction. Environment-verified milestone completion supplements final task success during training, while graph distillation enables students to generate graphs without teacher access at inference. Experiments with Qwen2.5 models on ALFWorld, WebShop, and TextCraft show that VTD outperforms existing baselines, while ablation studies confirm the contributions of verified progress and graph distillation.
Critical strengths
-
The paper effectively reformulates teacher supervision for long-horizon agents by replacing error-prone, trajectory-conditioned token guidance with task-level symbolic representations, particularly benefiting settings where teachers are accessible only through black-box APIs.
-
The paper demonstrates strong empirical performance across three environments and two model scales, supported by informative ablations of progress verification and compelling evidence of compositional generalization on held-out ALFWorld tasks.
Critical weaknesses
- The contribution of the symbolic graph structure is insufficiently isolated. Eq. (5) rewards milestone completion but ignores dependency edges, and existing ablations do not compare against flat milestone lists or ordered plans. Structural acceptance checks formatting rather than semantic correctness, so it remains unclear whether the gains come from graph distillation or milestone-based reward shaping.
- The evidence for the proposed OPD failure mechanism is incomplete. Decreases in KL divergence and increases in late-stage action agreement are consistent with weakened corrective supervision, but alternative explanations exist (e.g., hard-to-recover states, fewer meaningful actions, repetition). No controlled teacher-based OPD comparison is provided, and SDAR’s self-distillation design does not test VTD against the external-teacher supervision that motivates the paper.
Questions for authors
- Does the dependency structure and semantic quality of the generated graph materially affect performance?**Could the authors compare the full graph against the same milestones with removed or randomized edges, or against a flat milestone list? Please also clarify how often teacher- and student-generated graphs are semantically complete and correct, rather than merely structurally accepted.
- Can the authors provide more direct evidence for the claimed degradation of teacher supervision?**What is the teacher’s task-completion rate when taking over from different prefixes of failed student trajectories, compared with matched successful prefixes? A teacher-based OPD comparison under a comparable teacher or compute budget would also clarify whether VTD specifically addresses the proposed failure mode.
4 comments
[Cons 2a & Q2a. Direct evidence for the degraded supervision?] We want to make clear that the degradation comes from conditioning on the failed history, and direct measurements rule out each alternative explanation. We let each teacher take over a failed student trajectory at turn t and act for 30 more steps, with either the failed history or only the task and the environment's description of the current state. We use the 128 tasks and both teachers of Figure 1.
| Teacher | Context at takeover | t = 0 | t = 10 | t = 20 | t = 30 | t = 40 |
|---|---|---|---|---|---|---|
| Qwen2.5-7B (pretrained) | Failed history | 66.8 | 26.8 | 17.4 | 11.9 | 6.3 |
| Qwen2.5-7B (pretrained) | Task and current state | 66.4 | 48.1 | 54.1 | 50.0 | 51.2 |
| Qwen2.5-1.5B (GRPO-adapted) | Failed history | 92.2 | 61.7 | 52.2 | 41.4 | 35.9 |
| Qwen2.5-1.5B (GRPO-adapted) | Task and current state | 92.8 | 75.2 | 80.5 | 78.3 | 77.3 |
For the 25 tasks where the student has both a successful and a failed trajectory, we also compare takeovers after the first 10 turns of each.
| Teacher, takeover at t = 10 (25 tasks) | From the start | After a successful prefix | After a failed prefix |
|---|---|---|---|
| Qwen2.5-7B (pretrained) | 81.0 | 78.0 | 55.0 |
| Qwen2.5-1.5B (GRPO-adapted) | 96.0 | 94.0 | 77.0 |
Both teachers continue a successful prefix almost as well as they solve the task from the start, while a failed prefix sharply lowers their success. Given only the task and the current state, the teachers succeed far more often from the same states, so these states remain recoverable.
On the failed trajectories of Figure 1, we also count the admissible actions at each turn. We then recompute the teacher's action agreement on turns where the student neither repeats one of its previous five actions nor takes an invalid action.
| Failed student trajectories of Figure 1 | Turns 1–10 | Turns 41–50 |
|---|---|---|
| Admissible actions per turn | 28.0 | 28.5 |
| Action agreement of Qwen2.5-7B, without repeated or invalid actions | 53.6% | 80.9% |
Late turns offer as many admissible actions as early turns, so fewer choices cannot explain the late agreement. Removing repeated and invalid actions leaves the rise in agreement intact. Conditioning on the failed history removes the teacher's corrective ability, which is the failure mode VTD avoids.
[Cons 2b & Q2b. Teacher-based OPD under a comparable budget?] We emphasize that VTD outperforms on-policy distillation (OPD) from the strongest available teacher while using far fewer teacher tokens. OPD needs the teacher's token distribution on the student's outputs, so its teacher must be an open-weight model with the student's tokenizer. On ALFWorld, we train the same student with GRPO and a reverse-KL term toward Qwen2.5-72B-Instruct, the strongest such model, under VTD's training budget and evaluation.
| Qwen2.5-1.5B, ALFWorld | Teacher | Tokens per teacher query | Total teacher tokens | Success |
|---|---|---|---|---|
| GRPO | — | — | — | 72.8 |
| OPD | Qwen2.5-72B-Instruct | 7,795 | 200M | 84.6 |
| VTD | GPT-5.5 | 1,236 | 4.4M | 92.2 |
Both methods train for 200 steps with 128 student trajectories per step. OPD runs the teacher over all 25,600 of these trajectories, whereas VTD only asks the teacher to write one graph for each of the 3,553 training tasks. OPD thus uses 45 times as many teacher tokens yet stays well below VTD. Each OPD signal is computed on the student's own trajectory, so it inherits the loss of corrective value under a failed history. VTD surpasses OPD from the strongest open teacher with 2% of OPD's teacher tokens, and it can learn from black-box teachers that OPD cannot use.
Dear Reviewer kkNf,
Thank you for your review. We posted our response a few days ago, reporting the comparisons you asked for against removed or randomized edges and a flat milestone list, together with how often teacher and student graphs are semantically complete and correct. To give direct evidence for the degraded supervision, we measured teacher takeover from failed and matched successful prefixes and checked the alternative explanations you listed. We also compared VTD with teacher-based OPD, including the teacher tokens each method uses.
While the discussion phase is open, we would be glad to know whether the response answers your questions.
Sincerely,
The Authors
Dear Reviewer kkNf,
Thank you again for your review. As the discussion phase closes tomorrow, we would be glad to know whether our response answers your questions.
Sincerely,
We thank the reviewer for recognizing that VTD reformulates teacher supervision for black-box teachers through task-level symbolic structure and achieves compelling compositional generalization. We address each concern below.
[Cons 1a & Q1a. Contribution of the dependency structure?] We emphasize that Eq. (5) scores milestones without edges by design, so every control below receives exactly the same reward. However, to directly address the reviewer's question, we keep the teacher milestones and verified progress fixed on TextCraft and vary only how the dependencies reach the student.
Under the same reward, success follows the dependency content. The ordered plan keeps every prerequisite as a topological order of the same graph, so it matches the full graph in overall success. The flat milestone list and randomized edges both lower success. Without graph distillation, the student writes a valid graph for only 3.4% of items, and success collapses. VTD's gains come from the dependency structure and its distillation, which milestone-based reward shaping alone cannot provide.
[Cons 1b & Q1b. Semantic quality of the graphs?] Our results show that teacher and student graphs are semantically correct at high rates, and that their semantic content materially affects performance. A graph is semantically complete and correct when its milestones and dependencies match the task's ground truth.
To measure whether this quality matters, we keep the trained student fixed and replace the graph it writes at test time with the ground-truth graph, another item's graph, or no graph.
A correct graph keeps success high, while another item's graph or no graph lowers it. The student's own graphs perform almost as well as the ground-truth graph. On ALFWorld, a graph from another task family also lowers success (87.2 vs. 99.2). The semantic quality of the graph materially drives VTD's performance.