REVIEW 4 major objections 6 minor 2 cited by
Learning Lifted STRIPS Models from Action Traces Alone: A Simple, General, and Scalable Solution
T0 review · 4 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read The paper claims that a hidden lifted STRIPS planning domain can be reconstructed from action traces alone, with the learned domain provably equivalent to the hidden one whenever the traces are complete, and it implements this claim in a…
desk verdict SIFT's feature-consistency test is a real advance, but the 'sound and complete from action traces alone' claim only holds for extended traces that satisfy an unverifiable completeness condition—which the paper's own plain-trace protocol violates. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the feature f = ⟨k, B⟩: a guessed predicate of arity k together with a non-empty set B of action patterns a[t], where a is an action name and t is a tuple of argument positions binding the atom's variables to the action's arguments. The mechanism that carries the argument is the consistency test: from action traces one extracts pattern constraints (inequalities for patterns that appear consecutively while affecting the same ground atom, equalities for fork patterns around a shared state) and asks whether the signs of the patterns can be assigned 0/1 to satisfy them. The test reduces to 2-CNF satisfiability and runs in time linear in the number of patterns, which is what lets SIFT scale to state graphs with half a million edges.
What would settle it
Take a hand-built STRIPS domain with a predicate of arity 3 whose only effect is through one action pattern set, enumerate all extended traces up to a modest bound from a complete-data protocol, and run SIFT on the full state graph; if any feature outside Dmax survives the consistency test on all complete traces, the equivalence guarantee of Theorem 20 is false. A practical version is the paper's own Grid domain: if plain traces sampled from the initial state ever reach 100% verification on larger instances, the claim that Grid is not learnable from plain traces alone is falsified.
Extended reading notes
Core claim
On its own terms, the paper's central discovery is that the hard part of learning a lifted STRIPS domain—finding the predicates and which actions affect them—can be reduced to a consistency test on features. A feature f = ⟨k, B⟩ is the hypothesis that the hidden domain contains an atom f(x1,...,xk) whose truth value is changed by exactly the action patterns in B (an action name plus a tuple of argument positions). From the traces one reads off two kinds of constraint: consecutive occurrences of patterns that both affect the same ground atom must have opposite signs (one adds, one deletes), while fork patterns—patterns whose ground actions diverge from or converge to a common state—must have the same sign. A feature is admissible when these constraints are satisfiable, and the admissible features become the predicates of the learned domain once preconditions are filled in from the observed truth values. The paper shows that every feature of the hidden domain is admissible over any traces from it, that invalid features are ruled out by some finite set of extended traces, and hence that the learned domain can be equivalent to the hidden domain, with experiments reporting 100% verification on all benchmark domains when the inputs are full or partial state graphs.
Load-bearing premise
The guarantees rely on the training traces being complete for the hidden instance: drawn from its initial state, affecting every predicate of the domain, and carrying enough information to recover the initial truth values of the affected atoms; a learner cannot verify this completeness from the traces themselves.
Editorial extensions
If this is right
- In any domain whose traces are complete, SIFT yields a learned instance in which every training trace is applicable and every action that is inapplicable after a trace in the hidden instance is inapplicable in the learned instance (Theorem 15).
- A finite set of extended traces distinguishes valid features from invalid ones: a feature is consistent with all of them exactly when it appears in the maximal domain Dmax, so the learned domain becomes equivalent to the hidden domain (Theorem 20).
- Full and partial state graphs, which carry state equalities, yield 100% verification in all tested domains including n-puzzle with about 500,000 edges; plain traces alone fail in Grid (0%) and Sokoban (4%), and the paper argues Grid is not learnable from plain traces alone.
- Because the learned domain is equivalent to the hidden one on complete traces, the learned schemas generalize to larger instances than the one used for training, which is how the paper verifies its results.
- The 2-CNF consistency test is polynomial, so feature pruning is cheap; the main scalability win comes from generating typed, ordered features from trace-level type information, cutting candidate counts by orders of magnitude.
Reading between the lines
- Theorems 15 and 20 suggest that state equalities are the real currency of trace-based learning; adding even sparse pairwise state equalities to plain traces may rescue domains like Grid without requiring a full state graph, a testable extension of the partial-graph experiments.
- The redundant predicates SIFT learns (Dmax features such as an undirected 'on' relation in Blocksworld) are exactly the derived predicates that can be tracked by action effects, so the learned domain could double as a library of useful abstractions for planning rather than merely a ground-truth replica.
- The paper mentions a robust variant that prunes a feature only after it is inconsistent with k traces; observing how verification degrades as trace length or trace count shrinks would give a practical calibration of how much data completeness actually needs.
- The hard cases are sampling problems, not learning problems: Grid and Sokoban fail only because random walks get trapped in dead-ends, which predicts that guided traces from a strong planner would succeed where random traces fail.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces SIFT, a method that learns a lifted STRIPS domain — including predicate symbols and arities — from action traces, extended traces (with state equalities), or labeled state graphs, with no prior knowledge of the domain predicates. The central device is a 'feature' f = ⟨k, B⟩, an assumption that a k-ary predicate is affected exactly by the action patterns in B. Features are tested for consistency with the traces through equality/inequality constraints over pattern signs induced by consecutive and forking occurrences; the test reduces to 2-CNF satisfiability (Theorem 9). Consistent ('admissible') features define the learned domain's predicates and effects, while preconditions are derived by intersecting literals true in all trace nodes where the action is applied (Definition 10). The main results are: truth-value determinacy over connected traces (Theorem 12); soundness and completeness of the learned instance for complete trace sets (Theorem 15, Definition 14); validity of hidden-domain features (Theorems 17 and 19); and an existential statement that some finite extended-trace set makes consistency coincide with validity, so the learned domain is equivalent to the hidden one (Theorem 20). Experiments on 13 domains, including full state graphs with up to about 500,000 transitions (n-puzzle, Logistics), achieve 100% verification on full and partial graphs across all domains, while plain traces fail on Grid (0%) and Sokoban (4%).
Significance. If the results hold, this is a material advance over both LOCM (scalable but heuristic, limited arity handling) and SAT-based approaches (sound and complete but graph-only and small-scale): the consistency test is elegant and scalable, the learned features are interpretable and largely match the predicted maximal description Dmax, and the experiments validate on instances larger than the training instances, with public code and data. The paper is unusually honest about the cases where the method fails (Grid, Sokoban on plain traces) and about the non-constructive nature of Theorem 20. The main caveats are: (i) the formal guarantees require trace completeness in the sense of Definition 14, a condition that the paper's own plain-trace protocol violates and that the learner cannot verify; (ii) the type-based feature pruning in the implementation is not covered by the theorems; and (iii) the completeness claim is existential. These caveats mean the abstract's unqualified 'sound and complete' phrasing is stronger than what is established, but they are addressable through sharper claim-scoping rather than through reworking the core mechanism, which I found sound.
major comments (4)
- [Experiments (Training Data); Definition 14; Theorem 15] The formal guarantees are stated only for trace sets that are complete in the sense of Definition 14: all traces drawn from the initial state of P (hence connected), every hidden predicate affected by some action in T, and I agreeing with A(D,T) up to signs. The plain-trace protocol described in the Experiments section violates the connectedness requirement by construction: the first trace is sampled from s0 but traces 2–5 start from states reached in m random steps with 2L ≤ m ≤ 5L, and plain traces carry no state equalities, so the trace set shares no common state. Theorem 12's truth-value propagation, on which the proof of Theorem 15 rests, requires exactly that connectedness, and Definition 10's intersection-based precondition learning requires the resulting determinacy. Consequently, Theorems 15 and 20 do not apply to the plain-trace columns of Table 1, and the abstract's unqualified claim of being 'sound and complete' when learning 'from action traces alone' is substantiated only for complete extended traces. The observed failures (Grid Verif 0%, Sokoban Verif 4%) are consistent with this gap rather than being explained as isolated sampling artifacts. I recommend stating the scope of the guarantee explicitly (complete, connected trace sets from the initial state) and presenting the plain-trace results as empirical findings outside the theorem coverage; notably, the extended-trace inputs (full and partial graphs) do satisfy the connectedness requirement, and SIFT achieves 100% verification there, which is consistent with the theory's intended scope.
- [Implementation (Features)] The feature space is reduced by the type-extraction and type-merging heuristic before consistency testing, but no lemma establishes that this pruning preserves the set of valid or admissible features. The completeness guarantees (Theorem 15, part 2, and Theorem 20) are stated for the full set F(T), so the implemented system is not literally covered by the theory. Moreover, preservation is not automatically true: a valid feature f = ⟨k, B⟩ can be lost when the objects bound to an argument of f through different action patterns in B never coincide on the merged positions, so that the feature type for f is never enumerated — for example, if f is affected by patterns a[1] and b[1] and the objects appearing at position 1 of a are disjoint from those appearing at position 1 of b in the given traces. Please provide a preservation lemma with its conditions, or explicitly mark the typing step as a heuristic whose safety is currently established only empirically by the 100% verification rates.
- [Generalization (Theorem 20); Appendix proofs] Theorem 20 is purely existential: it asserts the existence of a finite extended-trace set that separates consistent from valid features, without constructing it or bounding its size, and its appendix proof is a three-sentence sketch. The paper itself concedes in the Generalization section that identifying such a set or proving validity 'is not simple and may even be undecidable in general.' Combined with Definition 14 — whose conditions (connectedness from the initial state, predicate coverage, initial-state agreement with A(D,T)) are properties of the hidden world that the learner cannot check — this means the completeness half of the 'sound and complete' claim is not an algorithmic guarantee. I do not see a circularity here, only an existentiality gap; admissibility is a genuine necessary condition for validity (Theorem 17), and the missing direction is the non-constructive one. I suggest that the abstract and introduction be qualified accordingly, and that the proofs of Theorems 17, 19, and 20 (and the existence argument for the maximal domain Dmax) be expanded well beyond their current one-line form.
- [Experiments (Grid and Sokoban paragraph)] The statement that 'one can show that Grid cannot be learned correctly from plain traces alone' is load-bearing for the paper's interpretation of the Grid 0% verification as a learnability boundary rather than a limitation of SIFT, but no proof or even proof sketch is provided. Please include the argument in the appendix — for example, an information-theoretic obstruction or two Grid instances with the same set of plain traces but different hidden domains — or soften the claim to a conjecture. The Grid-Lock and Sokoban-Pull results provide indirect support for the sampling interpretation, but the direct 'one can show' claim is currently unsupported.
minor comments (6)
- [Discussion] Typo: 'the the elimination of redundant features' should read 'the elimination of redundant features.'
- [Preview] The don't-care symbol used in the motivational questions renders as an empty glyph in this version; choose an explicit token (e.g., '·' or '_') and use it consistently.
- [Tables 5–8] The feature tables contain several typos and ambiguities ('corrdinate,' 'has has,' 'black' for 'blank'); also, the left/right pattern convention (positive vs. negative signs) is only explained implicitly through the meanings column and should be stated in the table captions.
- [Static Predicates] Please specify how the per-action static atoms pa(o) are instantiated in the larger verification instances; as written they are true iff the ground action occurs in the trace set, which renders the static part of the verification vacuous, so the claim that learned domains are 'verified on larger instances' should be stated as covering the dynamic predicates.
- [Related Work, footnote 1] The informal use of 'SIFT, on the other hand, is complete' in the footnote is stronger than what is proved; tie it to the formal statements (Theorems 15 and 20) to avoid confusion about the scope of the guarantee.
- [Definitions 5–7] The two border conditions (a pattern instance acting as a fork with itself, and consecutive patterns across sub-traces connecting common states) are described only in prose; a precise formalization or a small example would clarify the edge cases of the consistency test.
Circularity Check
No significant circularity: SIFT's consistency test and learned-domain construction are not defined in terms of the hidden domain, and equivalence claims rest on explicit completeness assumptions rather than self-citations or definitional reductions.
full rationale
The derivation chain is self-contained. Feature consistency (Definition 8) is a genuine hypothesis test on the input traces: the constraints Cf(T) are extracted from pattern occurrence and state-equality information, and a feature is admissible only if a sign assignment exists. Theorem 17 and Theorem 19 show that every hidden-domain feature is admissible because the actual effect signs in D provide a satisfying valuation; this is a sound semantic argument, not a definitional equivalence. Definition 10 constructs preconditions as literals observed true before each action occurrence, so Theorem 15's first claim (each training trace is applicable in the learned instance) follows by construction; the paper explicitly says the precondition definition 'ensures that the traces in T are executable', so this is a stated design property rather than a concealed prediction. The load-bearing generalization claim, Theorem 15(2) and Theorem 20, depends on the hidden features being among the admissible features and on the completeness condition of Definition 14, which is a strong, unverifiable assumption about the hidden instance and the trace set; the paper does not define the learned domain in terms of the target equivalence. The main concerns raised by a skeptical reading are experimental-validity issues, not circularity: the plain-trace protocol starts four of five traces from non-initial states, so Definition 14's connectedness requirement is not met and Theorems 15/20 do not formally cover those columns; the trace length L is tuned to reach 100% validation, which is model selection rather than a fitted parameter renamed as a prediction; and Grid and Sokoban plainly fail on plain traces, which the paper discloses and explains. There is no load-bearing self-citation; the only self-citation is the code/data repository pointer. Accordingly, no circular step can be exhibited.
Assumptions & free parameters
free parameters (3)
- Trace length L =
Per-domain, e.g., blocks3: 65, driverlog: 350, npuzzle: 200 (Table 1)
- Number of traces n =
5 (default)
- Number of BFS sample states for partial graphs =
5, with 10, 30, and 20 for Delivery, Driverlog, and Logistics respectively
assumptions (4)
- domain assumption Assumption 1: The hidden STRIPS domain is well-formed, meaning the complement of every effect is an action precondition.
- domain assumption Trace completeness (Definition 14): traces must be drawn from the initial state, affect each predicate, and the initial state must contain exactly the atoms in A(D,T).
- ad hoc to paper Type extraction and merging preserves the complete set of valid features.
- domain assumption Existence of a finite separating trace set (Theorem 20).
invented entities (1)
-
Static predicate pa for each lifted action a
Cite this review
Pith. "Pith review of Learning Lifted STRIPS Models from Action Traces Alone: A Simple, General, and Scalable Solution." pith.science (2026). https://pith.science/paper/O54DP4ET
@misc{pith2026241114995,
author = {Pith},
title = {Pith review of: Learning Lifted STRIPS Models from Action Traces Alone: A Simple, General, and Scalable Solution},
year = {2026},
howpublished = {\url{https://pith.science/paper/O54DP4ET}},
note = {Machine review of arXiv:2411.14995}
}
read the original abstract
Learning STRIPS action models from action traces alone is a challenging problem as it involves learning the domain predicates as well. In this work, a novel approach is introduced which, like the well-known LOCM systems, is scalable, but like SAT approaches, is sound and complete. Furthermore, the approach is general and imposes no restrictions on the hidden domain or the number or arity of the predicates. The new learning method is based on an \emph{efficient, novel test} that checks whether the assumption that a predicate is affected by a set of action patterns, namely, actions with specific argument positions, is consistent with the traces. The predicates and action patterns that pass the test provide the basis for the learned domain that is then easily completed with preconditions and static predicates. The new method is studied theoretically and experimentally. For the latter, the method is evaluated on traces and graphs obtained from standard classical domains like the 8-puzzle, which involve hundreds of thousands of states and transitions. The learned representations are then verified on larger instances.
Figures
Forward citations
Cited by 2 Pith papers
-
From Next Token Prediction to (STRIPS) World Models
Transformers trained via next-token prediction on action traces can learn STRIPS action models that support planning over exponentially many unseen initial states and goals.
-
Learning Lifted Action Models From Traces of Incomplete Actions and States
SYNTH learns STRIPS+ action models with implicit action arguments and unobserved predicates from incomplete state-action traces, with conditional completeness guarantees and 100 percent verification in experiments.
Reference graph
Works this paper leans on
-
[1]
, " * write output.state after.block = add.period write newline
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
J.; and Onaindia, E
Aineto, D.; Celorrio, S. J.; and Onaindia, E. 2019. Learning action models with minimal observability. Artificial Intelligence, 275: 104--137
2019
-
[4]
Aineto, D.; and Scala, E. 2024. Action Model Learning with Guarantees. arXiv preprint arXiv:2404.09631
arXiv 2024
-
[5]
Arora, A.; Fiorino, H.; Pellier, D.; M \'e tivier, M.; and Pesty, S. 2018. A review of learning planning action models. The Knowledge Engineering Review, 33: e20
work page 2018
-
[6]
Asai, M. 2019. Unsupervised Grounding of Plannable First-Order Logic Representation from Images. In Proc. ICAPS
work page 2019
-
[7]
Asai, M.; and Fukunaga, A. 2018. Classical planning in deep latent space: Bridging the subsymbolic-symbolic boundary. In AAAI
work page 2018
-
[8]
Asai, M.; Kajino, H.; Fukunaga, A.; and Muise, C. 2022. Classical planning in deep latent space. Journal of Artificial Intelligence Research, 74: 1599--1686
2022
Show all 28 references
-
[9]
Bachor, P.; and Behnke, G. 2024. Learning Planning Domains from Non-Redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis. In Proc. AAAI, 20028--20035
2024
-
[10]
Balyo, T.; Suda, M.; Chrpa, L.; S afr \'a nek, D.; Dvo r \'a k, F.; Bart \'a k, R.; and Youngblood, G. M. 2024. Learning Planning Action Models from State Traces. arXiv preprint arXiv:2402.10726
2024 arXiv
-
[11]
Bonet, B.; and Geffner, H. 2020. Learning first-order symbolic representations for planning from the structure of the state space. In Proc. ECAI
2020
-
[12]
Bonet, B.; and Geffner, H. 2024. General policies, subgoal structure, and planning width. Journal of Artificial Intelligence Research, 80: 475--516
2024
-
[13]
Cresswell, S.; and Gregory, P. 2011. Generalised Domain Model Acquisition from Action Traces. Proc. ICAPS, 42--49
2011
-
[14]
N.; McCluskey, T
Cresswell, S. N.; McCluskey, T. L.; and West, M. M. 2013. Acquiring planning domain models using LOCM. The Knowledge Engineering Review, 28(2): 195--213
2013
-
[15]
Geffner, H.; and Bonet, B. 2013. A Concise Introduction to Models and Methods for Automated Planning. Morgan & Claypool Publishers
2013
-
[16]
Ghallab, M.; Nau, D.; and Traverso, P. 2016. Automated planning and acting. Cambridge U.P
2016
-
[17]
Gregory, P.; and Cresswell, S. 2015. Domain model acquisition in the presence of static relations in the LOP system. In Proc. ICAPS, volume 25, 97--105
2015
-
[18]
Haslum, P.; Lipovetzky, N.; Magazzeni, D.; and Muise, C. 2019. An Introduction to the Planning Domain Definition Language. Morgan & Claypool
2019
-
[19]
Lamanna, L.; Saetti, A.; Serafini, L.; Gerevini, A.; Traverso, P.; et al. 2021. Online Learning of Action Models for PDDL Planning. In IJCAI, 4112--4118
2021
-
[20]
S.; Juba, B.; and Stern, R
Le, H. S.; Juba, B.; and Stern, R. 2024. Learning Safe Action Models with Partial Observability. In Proc. AAAI, 20159--20167
2024
-
[21]
Lindsay, A. 2021. Reuniting the LOCM Family: An Alternative Method for Identifying Static Relationships. In Proc. ICAPS 2021 KEPS Workshop
2021
-
[22]
Lipovetzky, N.; and Geffner, H. 2012. Width and serialization of classical planning problems. In Proc. ECAI, 540--545
2012
-
[23]
P.; and Steedman, M
Mour \ a o, K.; Zettlemoyer, L.; Petrick, R. P.; and Steedman, M. 2012. Learning STRIPS operators from noisy and incomplete observations. In Proc. UAI, 614--623
2012
-
[24]
D.; Bonet, B.; Romero, J.; and Geffner, H
Rodriguez, I. D.; Bonet, B.; Romero, J.; and Geffner, H. 2021. Learning First-Order Representations for Planning from Black Box States: New Results. In Proc. KR, 539--548
2021
-
[25]
R.; and Srivastava, S
Verma, P.; Marpally, S. R.; and Srivastava, S. 2021. Asking the right questions: Learning interpretable action models through query answering. In Proc. AAAI, 12024--12033
2021
-
[26]
Xi, K.; Gould, S.; and Thi \'e baux, S. 2024. Neuro-Symbolic Learning of Lifted Action Models from Visual Traces. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 34, 653--662
2024
-
[27]
Yang, Q.; Wu, K.; and Jiang, Y. 2007. Learning action models from plan examples using weighted MAX-SAT. Artificial Intelligence, 171(2-3): 107--143
2007
-
[28]
H.; and Kambhampati, S
Zhuo, H. H.; and Kambhampati, S. 2013. Action-model acquisition from noisy plan traces. In Proc. IJCAI
2013
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.