- Rating
- 3
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces RPOS (Reusable Partial-Order Skills), a probabilistic model for learning reusable skill libraries from action-labeled agent traces.
The key contribution is jointly inferring skill boundaries, assignments, and shared partial-order precedence constraints using semi-Markov dynamic programming. The paper demonstrates that partial-order representations better capture real procedural flexibility than total-order models, enabling 86.97% reduction in token usage during downstream execution (120 paired retail tasks) while maintaining task success rates.
Validation spans synthetic data recovery, TaskBench workflow composition, and τ³-Retail real-world traces with qualitative skill structure analysis.
Critical strengths
-
Novel partial-order representation with principled inference. The use of partial-order templates with exact semi-Markov dynamic programming is technically sound and well-motivated. Unlike total-order models, this approach naturally handles alternative orderings, repetitions, and repairs without adding cycles to the shared graph—a consequential architectural innovation.
-
Compelling downstream results demonstrating practical value. The 86.97% token reduction on 120 paired synthetic retail tasks (Table 2: N=23.1k tokens vs. G=3.01k tokens per task) directly validates the utility of learned skill structure. The executor maintains strict task success (120/120) despite dramatic token savings, showing the model captures genuine procedural relationships rather than spurious correlations.
Critical weaknesses
-
Severely limited evaluation scope with generalization uncertainty. Evaluation concentrates on τ³-Retail (436 traces, 24 CPA labels) and TaskBench synthetic workflows. The paper provides no evidence the approach generalizes to other agent trace datasets (robotics, web tasks, NLP workflows). Missing comparisons with recent partial-order and sequence discovery methods (e.g., Leemans & van Zelst 2025 POWL) on the same data—only SEQ-HSMM is directly compared.
-
Unaddressed scalability and critical design choices lack validation. No runtime complexity analysis or convergence diagnostics (R̂, ESS) provided. The method assumes fixed K and action dictionary specified in advance, severely limiting applicability. Key assumptions (no self-transitions, validity as scalar, partially collapsed orderings) are never ablated on real data. RPOS actually underperforms SEQ-HSMM on τ³-Retail 20-trace final test (NLL 1.600 vs. 1.303), yet this critical failure is dismissed rather than investigated.
Questions for authors
-
Why does RPOS achieve worse NLL (1.600) than SEQ-HSMM (1.303) on the τ³-Retail 20-trace final test? This contradicts the claim of superiority. Can you provide concrete examples of failure modes or data characteristics where total-order models outperform partial orders?
-
How does the method scale with trace length and number of skills K? What is the computational complexity, and what are the wall-clock runtimes vs. baselines? The paper runs 4,000 MCMC sweeps but provides no convergence diagnostics (Gelman-Rubin R̂, ESS, mixing time).
-
Can RPOS infer unknown K or automatically discover the number of skills? How sensitive is the model to misspecification of K and the action dictionary?
-
Can you provide ablation studies on τ³-Retail validating key design choices: (a) the validity state in repeat modeling, (b) the partially collapsed ordering (Prop. 1), (c) hyperparameter sensitivity (β, λ_rep, λ_back)?
2 comments
Thank you again for your feedback. We have incorporated the clarifications discussed above into the revised uploaded manuscript:
-
Q1 — Retail prediction: Section 5.3 now explicitly acknowledges the predictive gap, gives the correct baseline values, and distinguishes predictive accuracy from structural inference (lines 415–419).
-
Q2 — Complexity and convergence: The main text now states the forward-pass complexity and clarifies the limits of finite-run MCMC conclusions (lines 290–294), with detailed costs in Appendix H. The Retail fitting budget is documented in lines 1608–1612, and its sampling diagnostics and interpretation appear in lines 1855–1860.
-
Q3 — Fixed K: We added discussion of K as a representation-granularity choice (Appendix G.1, line 1619 and lines 1652–1653) and explicitly state that automatic K selection is not implemented (Limitations, lines 503–507).
-
Q4 — Modelling choices and existing evidence: The revised discussion explains the validity-ablation trade-off (lines 357–366), the Full-Marg/Full-Cond comparison (lines 317–323), and the no-self-transition modelling restriction (lines 193–205). Broader-domain and annotation limitations are stated in lines 503–504. These revisions clarify the existing evidence; they do not represent additional Retail hyperparameter-sensitivity experiments.
We thank the reviewer for the detailed feedback. We address the main concerns below.
Q1. Retail predictive performance.
We acknowledge that RPOS underperforms sequence baselines on Retail. To clarify, NLL 1.303 belongs to the bigram baseline, while SEQ-HSMM achieves 1.305 and RPOS achieves 1.600 (K=5).
Our primary contribution is joint inference of reusable partial-order structures, rather than universal superiority in sequence prediction. Sequence models capture observed local transitions, whereas RPOS aims to distinguish essential dependencies from incidental execution order. When local transitions are highly predictable, simpler sequence models may achieve better NLL. This is a possible explanation, not a verified diagnosis. We acknowledge the Retail predictive gap while noting that synthetic experiments evaluate structural recovery and TaskBench evaluates unseen valid orderings.
Q2. Computational complexity and convergence.
Appendix H.1 already provides complexity analysis. With precomputed block scores, the factorised semi-Markov forward pass reduces complexity from O(NJDK2) to O(NJK2+NJDK), excluding block-score construction and structural proposals.
The Retail experiments use four independent runs per capacity, each with 30,000 MCMC sweeps, not 4,000 (Appendix G.1).
Our MCMC procedure explores a high-dimensional, combinatorial posterior over latent skill structures and assignments, rather than seeking a single globally optimal DAG. In a potentially multimodal posterior, finite runs may not explore all structural modes. We therefore do not claim global posterior convergence. Proposition 1 establishes posterior invariance of the update kernel, not convergence of finite runs. Available R^, ESS, and between-run diagnostics are reported in the appendices, with incomplete exploration explicitly acknowledged.
Q3. Fixed number of skills and action dictionary.
Fixing K and the CPA dictionary is a deliberate modelling choice that separates observable action definitions from latent structural inference. Skill boundaries, assignments, and partial orders remain unknown and are jointly inferred.
Importantly, K controls the granularity of the learned representation: small K may merge distinct procedures into overly broad skills, while large K may produce fragmented or redundant skills. We evaluate K∈{4,5,6,8} on Retail, observing modest predictive variation, although this does not establish structural stability. Automatically selecting K and adapting the vocabulary are valuable extensions beyond the present scope.
Q4. Ablations and modelling choices.
Our existing controlled experiments evaluate the principal methodological components:
These targeted experiments assess the core methodological contributions in settings where their effects can be meaningfully isolated. Further Retail-specific ablations and broader comparisons would be valuable, but our primary objective is joint probabilistic inference of reusable partial-order skill structures, rather than exhaustive evaluation of every modelling variant. We will clarify the existing evidence and limitations in the revision.