Before a robot runs a plan from a generative policy, we would like a statement such as "with 95% confidence, at least 90% of this policy's plans satisfy the safety rule." Statistical model checking, which estimates the probability that a system satisfies a formal specification by sampling many random runs and applying a statistical test, is the standard way to get such a statement. Diffusion policies make it very expensive. A diffusion model generates by gradually denoising random noise into a sample, so every sampled run costs tens to hundreds of sequential network calls, and a certificate needs hundreds or thousands of runs. We propose to pay for most of those runs with a cheap "draft" sampler, such as a few-step solver or a small model. The draft is statistically tied to the expensive "target" sampler, and a small number of paired target runs measure and correct the draft's bias. The certificate stays valid for the target model itself.
The idea borrows the central move of speculative decoding, in which a cheap model proposes and an expensive model checks, and applies it to verifying a policy rather than generating from it. If a draft run and its coupled target run almost always agree on whether the specification holds, the target model's satisfaction probability equals the draft's plus a small correction term. That correction can be estimated from few expensive samples. A sequential test, meaning one that stops as soon as the evidence is conclusive, then gives the same Type I and Type II error guarantees as ordinary statistical model checking on the target. Draft quality affects only how many expensive samples are needed, never whether the answer is correct.
Core Claim
Let $\phi(\tau)\in\{0,1\}$ indicate whether trajectory $\tau$ satisfies a temporal-logic specification. Let $\tau_T$ be a target-sampler trajectory and $\tau_D$ a draft trajectory produced from the same randomness through a coupling. The quantity to certify, $p_T = \Pr[\phi(\tau_T)=1]$, decomposes as
$$p_T = p_D + \mathbb{E}\big[\phi(\tau_T)-\phi(\tau_D)\big],$$
where $p_D$ is the draft's satisfaction probability. Because the paired difference is nonzero only when the two runs disagree on $\phi$, its variance is at most the disagreement probability $\delta=\Pr[\phi(\tau_T)\neq\phi(\tau_D)]$. For a confidence interval of half-width $\varepsilon$, plain sampling needs roughly $p_T(1-p_T)/\varepsilon^2$ target runs. The coupled estimator needs roughly $\delta/\varepsilon^2$ target runs, plus cheap draft runs to pin down $p_D$. This follows from standard variance arguments for sample means.
Our claim is twofold. First, for diffusion planners under realistic specifications, well-chosen couplings make $\delta$ much smaller than $p_T(1-p_T)$ near the decision threshold. Second, a sequential test built on this estimator reaches a certified accept or reject decision with several times fewer target network calls than standard sequential model checking, and it keeps its nominal error rates when the draft is poor.
Relation to Prior Work
The statistical side comes from the model-checking literature. Sequential acceptance sampling, surveyed in Statistical Model Checking: Past, Present, and Future and used in Monte Carlo Model Checking and Planning and Verification for Stochastic Processes with Asynchronous Events, stops sampling once a sequential likelihood-ratio statistic crosses a boundary set by the error rates. These methods treat every trace as equally costly and come from one simulator. We add a second, cheap, correlated simulator. Because the paired difference is not a single Bernoulli variable, the classical probability ratio test does not apply directly. We therefore use an anytime-valid confidence sequence on the combined estimator, which is the same stopping logic in a more general form.
The coupling side comes from speculative sampling. Accelerated Diffusion Models via Speculative Sampling drafts several future diffusion states cheaply and uses Reflection-Maximal Coupling to accept or correct them, so that outputs exactly follow the target model. It reports CIFAR-10 FID 2.34 with 35 target calls against 2.45 with 100. For discrete generators, Coupling without Communication and Drafter-Invariant Speculative Decoding couples draft and target tokens through shared Gumbel noise. Both papers use the coupling to produce target samples faster. We reuse the same couplings for a different purpose: the draft half of each coupled pair becomes a correlated, cheap estimate of the target's property outcome. The draft side of that paper's coupling is exactly what our estimator needs.
The application side is the work on temporal logic for diffusion planners. LTLDoG steers denoising with gradients of finite-trace linear temporal logic satisfaction and lifts Maze2d-Large satisfaction from about 10% to 99%. Diverse Controllable Diffusion Policy with Signal Temporal Logic applies robustness gradients only in late denoising steps and reports a 0.077 collision rate at 0.379 s per inference on NuScenes. These papers motivate our work: they make policies more likely to satisfy specifications, but they do not certify how likely. Our method is complementary, because it can certify their guided policies.
Two further papers limit what we should claim. SPRINTER and AC-Sampler accept approximate verification: a small classifier or a propose-until-accept jump chain that deliberately introduces bias. They show that approximate checks are cheap, but they provide no bounded risk. Our design keeps approximation confined to efficiency and never lets it enter the guarantee. This addresses the exact-versus-approximate tension noted in the file.
Research Program
We will build a sequential certifier that takes three inputs: a target sampler, one or more draft samplers, and a specification with a threshold $\theta$. Each round it draws a batch of cheap draft runs and, with an adaptively chosen probability, a batch of coupled draft-target pairs. It then updates a confidence sequence for $p_T$ and stops when the sequence falls entirely above or below $\theta$. The mixing fraction follows standard multi-fidelity allocation, trading the cost ratio between target and draft against the estimated disagreement $\delta$ and draft variance $p_D(1-p_D)$. It is re-estimated online without invalidating the confidence sequence, because the allocation depends only on past observations.
We will study three couplings, since the coupling is the component that determines efficiency.
- Independent draws. Draft and target runs share no randomness, so the estimator gets no correlation benefit. This is the control condition.
- Shared initial noise. For deterministic ODE samplers, the draft and target start from the same noise. For stochastic samplers, they share an aggregated Brownian path.
- Speculative coupling. Reflection-Maximal Coupling from Accelerated Diffusion Models via Speculative Sampling, where the draft is the frozen-target or independent drafter. In this case, a paired sample that was fully accepted costs only parallel verification calls, and its paired difference is exactly zero.
We will also derive per-specification bounds on $\delta$ from temporal-logic robustness. Disagreement requires the draft trajectory to lie within the trajectory-space distance between draft and target of the specification boundary. This bound predicts in advance when the method will help.
Baselines
The naive reference is fixed-sample Monte Carlo on the target sampler, sized by a Hoeffding bound for the chosen $\varepsilon$ and $\alpha$. It gives the cost of a certificate made without any cleverness.
The standard statistical model-checking baseline is a sequential probability ratio test on target runs alone, with the same indifference region and error rates. This baseline is what the literature above would actually deploy.
The strongest existing competitor is that same sequential test run on target samples generated by speculative sampling as in Accelerated Diffusion Models via Speculative Sampling. It is the strongest because it already reduces sequential target calls per sample by roughly the ratio implied by its reported 35-versus-100 calls on CIFAR-10, while preserving exactness. To beat it, our certifier must reach the same decisions at matched empirical error rates with at least twofold fewer total target network calls and lower wall-clock time to decision. Our certifier uses the same speculative sampler for its paired target runs, so any gain comes from the estimator rather than from a faster generator. No reported result was found on Lacuna for the certification cost of diffusion policies under any of these baselines, so we will measure all of them ourselves.
A biased reference runs the sequential test on the draft sampler alone, for example a 5-step DPM-Solver or a distilled model. It is the cheapest option, and it shows what the guarantee is worth.
The key ablation compares the three couplings under an identical estimator and stopping rule. This isolates whether correlation, rather than the sequential test itself, drives the savings.
All methods share the same models, specifications, $\alpha=\beta=0.05$, indifference half-width, batch size, and hardware. Hyperparameters, meaning allocation priors and drafter step count, are tuned on specifications held out from evaluation.
Why not just…?
Why not just certify the fast few-step or distilled sampler, since it is what we would deploy anyway? Sometimes that is the right answer, and our method then collapses to ordinary model checking on the cheap model. But the high-quality target is often what is deployed, and fast samplers shift the output distribution. AC-Sampler reports DPM-v3 at FID 12.41 with 5 calls, far from full-step quality, and a satisfaction rate can shift similarly. The draft-only baseline will show directly how often the certificate's decision about the target is wrong.
Why not just share random seeds between a cheap and expensive sampler and use a textbook control variate? This is a serious alternative, and it is one of our coupling arms rather than something we argue against. For deterministic ODE samplers, shared initial noise may yield disagreement as low as speculative coupling. If it does, we will report that the contribution is the valid sequential multi-fidelity certifier, and that the speculative coupling earns its place only for stochastic samplers and token-level generators. The ablation settles this per setting.
Why not just use rare-event importance sampling? Importance sampling targets probabilities near zero. Certification thresholds such as $\theta=0.9$ put $p_T$ in a moderate range, where the bottleneck is per-sample cost rather than rarity. The two approaches compose, and we leave the combination to follow-up work.
Why not just run more target samples in parallel? Batching reduces wall-clock time but not total network calls. Our primary metric is compute to decision, and batching helps every method equally.
Proposed Experiments
The main testbed is Maze2D from D4RL, with the LTLDoG specifications and policies, both unguided at roughly 10% satisfaction and guided at roughly 99% as reported by LTLDoG. We add thresholds placed near each policy's true rate, which is where testing is hardest. The second testbed is PushT with avoidance and visitation specifications. The third is NuScenes with the signal temporal logic rules and policies of Diverse Controllable Diffusion Policy with Signal Temporal Logic. As a generality check outside planning, we will certify an autoregressive language model's rate of passing unit tests on HumanEval, using a small drafter coupled through Gumbel noise as in Coupling without Communication and Drafter-Invariant Speculative Decoding.
For each setting we compute ground-truth $p_T$ from a very large target sample. We then repeat each certifier several hundred times and report five measures:
- empirical Type I and Type II error
- mean and tail target calls to decision
- wall-clock time to decision
- the measured disagreement $\delta$
- agreement between $\delta$ and our robustness-based bound
Three checks decide whether the idea holds. First, error rates must stay at or below 0.05 even when the draft is deliberately bad, for example a 2-step solver. In that case cost should degrade gracefully toward the plain sequential test and never fall below its accuracy; if errors exceed nominal levels, the idea fails. Second, the speedup over speculative-sampling-plus-sequential-testing should track the predicted ratio $p_T(1-p_T)/\delta$ across specifications. Third, the coupling ablation must show whether the speculative coupling beats shared noise on the stochastic samplers.
References
- Statistical Model Checking: Past, Present, and Future
- Monte Carlo Model Checking
- Planning and Verification for Stochastic Processes with Asynchronous Events
- Accelerated Diffusion Models via Speculative Sampling
- Coupling Without Communication and Drafter-Invariant Speculative Decoding
- LTLDoG: Satisfying Temporally-Extended Symbolic Constraints for Safe Diffusion-Based Planning
- Diverse Controllable Diffusion Policy With Signal Temporal Logic
- Speeding up Speculative Decoding via Sequential Approximate Verification
- AC-Sampler: Accelerate and Correct Diffusion Sampling with Metropolis-Hastings Algorithm
- D4RL: Datasets for Deep Data-Driven Reinforcement Learning.