LM-Landmarks: Language Model Guided Landmark Generation for Classical Planning with Formal Soundness Guarantees

Language models (LMs) excel at surface-level knowledge about task structure but struggle to generate executable plans reliably (Valmeekam et al., 2023). We identify a more productive role for LMs in classical planning: generating candidate landmark facts from natural-language problem descriptions, which are then formally verified against the PDDL model and used to augment landmark-count heuristics in a classical planner. We call this framework LM-Landmarks. We prove that (i) any LM-generated landmark that passes our delete-relaxation verification is a true planning landmark, (ii) the augmented landmarkcount heuristic remains admissible, and (iii) under a mild bounded-recall assumption the expected number of expanded nodes decreases by a factor $\Omega(R * \kappa)$ where $r$ is the landmark recall of the LM and $\kappa$ is the average landmark cost. Experiments on 8 IPC domains using Fast Downward (Helmert, 2006) show that LM-Landmarks improves coverage by 7.5 percentage points over FF and by 3.1 points over LAMA while reducing search nodes by 41% and 37% respectively, with no loss of plan optimality. Critically, LMs never directly control the planner: every landmark is verified before use, guaranteeing soundness even when the LM hallucinates.