When a generative model is asked to carry out a long task described in temporal logic (a formal language for statements like "eventually reach A, then always avoid B until C"), two things can cause failure. The specification may be too complex, or the underlying pretrained model may be unable to produce some step the specification requires. This proposal argues that the second cause dominates, and that it can be measured one step at a time. Any finite-trace specification, whether written in standard Linear Temporal Logic or in more expressive logics that can count and track periodic patterns, can be compiled into a finite automaton, a small state machine whose edges are the individual sub-tasks. We propose to estimate, by direct sampling, how often a fixed diffusion model (a generator that produces trajectories by gradually denoising random noise) succeeds at each kind of edge. We then predict and plan task success from those per-edge rates alone.
The core claim has two parts. First, at a fixed base model, success on a specification is predicted by the best accepting path through the product of the specification's automaton and an empirically estimated "capability graph" of the model. It is not predicted by the specification's syntactic size or by where its logic sits in the expressivity hierarchy. Second, a planner that searches this product graph can satisfy specifications beyond standard LTL, such as modular counting, at no extra cost. It also beats existing logic-guided diffusion planners precisely where the offline data has coverage gaps, because it routes around edges the base model cannot reliably produce, and when no route exists it says so before execution.
What the two directions contribute
The base-model-ceiling literature documents that downstream controllers steer but do not create. Hierarchical diffusion planners for LTL tasks are, by their authors' own account, bounded by whether the offline data contains the needed behavioral fragments (DOPPLER). The zero-shot STL planner of Zero-Shot Trajectory Planning for Signal Temporal Logic Tasks fails when its learned time predictor proposes waypoints the diffusion model cannot connect. OGBench shows that coverage dominates: pick-and-place success fell from 99% to 6% when data lacked noise. In video, NeuS-V finds that text-to-video models degrade as prompts move from one to three or more temporal operators, and that they substitute camera motion for real interaction. These papers motivate the proposal. They establish that a ceiling exists, but none of them decomposes it into parts.
The temporal-logic literature contributes the method and a useful lens. Synthesis for LTL and LDL on Finite Traces shows that Linear Dynamic Logic on finite traces ($LDL_f$), which adds regular expressions inside temporal operators, captures all regular properties. It does this with the same worst-case synthesis complexity as $LTL_f$, because both reduce to finite automata. The Transformation Logics classifies regular properties algebraically: star-free properties (expressible in LTL), properties that need modular counting (solvable groups), and full regular properties. We use this classification to build specification suites that are matched on edge requirements but differ in logic class. That pairing lets us test whether the logic class itself matters for a generator.
We set aside the context-free logics in the file, including POTL/POPACheck and RecLTL. On finite horizons with bounded nesting, the properties we can actually test become regular. Claiming otherwise would overstate the contribution.
What is and is not new
The obvious idea at this intersection is "condition a diffusion planner on $LDL_f$ instead of LTL." We think this is close to trivial for hierarchical planners. DOPPLER and the zero-shot STL planner already act on automaton progress, and an $LDL_f$ formula compiles to a deterministic automaton just as an $LTL_f$ formula does. We include this as a baseline and do not present it as the contribution.
What is new is an explicit, specification-independent, empirically calibrated model of the base generator's capabilities, defined on automaton edges. It is used for three purposes: to predict success, to plan, and to certify infeasibility before execution. DOPPLER learns option selection with reinforcement learning, so any capability knowledge stays implicit and tied to the training tasks. The zero-shot STL planner's time predictor estimates durations, not success probabilities.
Research Program
We fix a base diffusion trajectory model trained on an offline dataset. We partition the state space into labeled regions, which serve as the atomic propositions of the specification. For each pair of regions $(u,v)$ and each invariant label $I$, we sample $n$ short chunks from the model. Each chunk is conditioned to go from $u$ to $v$ while staying inside $I$. We record the empirical success rate $\hat p(u \to v \mid I)$ along with a Beta posterior over it. The result is the capability graph. It is computed once per base model, does not depend on any specification, and its cost is reported.
For a specification $\varphi$ with deterministic automaton $A_\varphi$, we form the product of $A_\varphi$ with the capability graph. The predicted success is
$$\hat P(\varphi) = \max_{\pi \in \Pi_{acc}(\varphi)} \prod_{e \in \pi} \hat p(e),$$
where $\Pi_{acc}(\varphi)$ is the set of accepting paths in the product and $\hat p(e)$ is the estimated success of the chunk realizing edge $e$. The product form assumes that chunk outcomes are roughly independent given the endpoints. That assumption is the "stitching over stretching" premise of the zero-shot STL planner, and testing it is part of the study.
Planning means finding the path that achieves this maximum, which is a shortest-path problem in log-probabilities, and executing it chunk by chunk. If a chunk fails, we replan from the realized state. If the maximum falls below a threshold, the system reports that the specification is infeasible under this base model, together with the offending edges. That report doubles as a data-collection recommendation.
We will also try a lighter transfer to video. There, edges are transitions between atomic events, and per-edge rates are estimated by generating short clips and scoring them with NeuS-V's perception and model-checking pipeline. The question is whether NeuS-V's drop with operator count is explained by the product of per-transition rates.
Baselines
The naive reference point is the same base diffusion model sampled without planning. Each full-horizon sample is checked against $A_\varphi$, and the best is kept under a fixed budget of diffusion calls equal to our total budget, including the cost of building the capability graph amortized over the specification suite. This baseline is rejection sampling done fairly. Beating it means higher satisfaction at equal calls.
The strongest existing method on Maze2D-type tasks is DOPPLER (DOPPLER), which reports LTL satisfaction of "around 90-95%" on Maze2d against 10–70% for LTLDoG and Diffuser. We run it with the automaton compiled from each specification, including the $LDL_f$ and counting specifications. It uses the same offline data, the same diffusion backbone where its design allows, and the same tuning budget. Its high-level policy is trained with its own procedure, and we report that training cost.
For STL-expressible specifications, we also run the zero-shot STL planner (Zero-Shot Trajectory Planning for Signal Temporal Logic Tasks). It reports about 70–92% success on Maze2D Large and 80–90%+ for most templates on OGBench AntMaze and Cube, while a robustness-guided diffuser scored 0%.
Beating these methods on full-coverage data is not the goal; we expect parity there. Beating them means a statistically clear margin on coverage-ablated data and on counting specifications, with no loss on full-coverage LTL specifications.
Two ablations isolate the key ingredient. The first replaces $\hat p$ with a geometric cost (shortest accepting path by distance). The second replaces $\hat p$ with a time-predictor-style feasibility estimate that ignores sampled success. If either ablation matches the full method, the empirical capability graph is not doing the work.
Why not just…?
Why not just compile $LDL_f$ to an automaton and hand it to DOPPLER? This is the real threat. When every required edge is well covered, we expect it to match us, and we will report that honestly. The gap should appear when some edges are unsupported. DOPPLER's option selection has no explicit estimate of which options the generator can realize from a given state. It also cannot report infeasibility before execution, and adapting it to a new specification requires retraining. The coverage-ablation experiment below decides this question.
Why not just reject-sample with a model checker, as NeuS-V could be used? The robustness-guided diffuser's 0% on complex Maze2D Large tasks (Zero-Shot Trajectory Planning for Signal Temporal Logic Tasks) suggests that full-horizon samples rarely satisfy multi-stage specifications. Our equal-budget naive baseline measures this directly instead of assuming it.
Why not just apply logic-robustness gradients at every denoising step? Diverse Controllable Diffusion Policy With Signal Temporal Logic reports that full-step guidance in the style of CTG takes over 9 seconds per inference, against 0.379 seconds for its late-stage guidance. A more basic problem is that robustness gradients are not defined for counting properties: there is no smooth robustness score for "an even number of visits." Guidance also cannot create behavior outside the data's support, which is exactly the regime we target.
Why not just collect more data or fine-tune the base model? That raises the ceiling instead of measuring it. The capability graph says which edges need data. We test this cheaply by restoring only the flagged fragments and checking whether recovery exceeds that of restoring an equal amount of randomly chosen data.
Proposed Experiments
The specification suites live on D4RL Maze2D Large (D4RL) and on OGBench AntMaze and Cube, using the navigate and stitch datasets. For each environment, we build triples of specifications that share the same multiset of required region-to-region edges. One member of each triple is star-free LTL. One requires counting modulo 2 or 3, for example "patrol A and B, returning to A an even number of times before C." One is full regular, written in $LDL_f$.
The first decisive check is predictive. Across all specifications, we regress realized satisfaction on $\hat P(\varphi)$, on formula size, on operator count, and on logic class. We report calibration error. The claim survives only if $\hat P$ explains most of the variance and logic class adds little once $\hat P$ is controlled for.
The second check is interventional. We delete trajectory fragments from the stitch datasets to remove specific edges, then retrain the base model. The capability graph should predict which specifications break, and our planner should keep satisfaction on specifications that have an alternative accepting path, where DOPPLER and the zero-shot STL planner should not. On specifications with no alternative path, the infeasibility report should be correct, which we measure by precision and recall against realized zero success.
The third check transfers the analysis to video using the NeuS-V benchmark's 360 prompts. We estimate per-transition rates for an open video model and test whether the product of those rates predicts multi-event NeuS-V scores better than operator count does. NeuS-V reports no absolute satisfaction numbers, so this experiment is about relative prediction and has no comparison to a published figure. We are also limited by the reliability of its vision-language perception module, which we will audit on a hand-labeled subset.
A negative result would also be informative. If realized success depends on logic class even after controlling for edges, then counting and periodic structure strain the generator in ways that per-edge rates miss, for example through accumulated drift across loops. We will look for this by plotting per-chunk success against the number of repetitions completed.
References
- Diffusion Meets Options: Hierarchical Generative Skill Composition for Temporally-Extended Tasks
- Zero-Shot Trajectory Planning for Signal Temporal Logic Tasks
- OGBench: Benchmarking Offline Goal-Conditioned RL
- Neuro-Symbolic Evaluation of Text-to-Video Models using Formal Verification
- Synthesis for LTL and LDL on Finite Traces
- The Transformation Logics
- POPACheck: A Model Checker for Probabilistic Pushdown Automata
- Temporal Logic with Recursion
- Diverse Controllable Diffusion Policy With Signal Temporal Logic
- D4RL: Datasets for Deep Data-Driven Reinforcement Learning.