Data-Driven Reachability Analysis via Diffusion Models with PAC Guarantees

Yanliang Huang; Peng Xie; Wenyuan Wu; Zhuoqi Zeng; Amr Alanwar

eess.SYMar 31, 2026

Data-Driven Reachability Analysis via Diffusion Models with PAC Guarantees

Authors: Yanliang Huang, Peng Xie, Wenyuan Wu, Zhuoqi Zeng, Amr Alanwar

Organizations: School of Computation, Information and Technology, Technical University of Munich, Munich, Germany. · School of Engineering, Hainan Bielefeld University of Applied Sciences, Hainan, China.

Abstract

We present a data-driven framework for reachability analysis of nonlinear dynamical systems that requires no explicit model. A denoising diffusion probabilistic model learns the time-evolving state distribution of a dynamical system from trajectory data alone. The predicted reachable set takes the form of a sublevel set of a nonconformity score derived from the reconstruction error, with the threshold calibrated via the Learn Then Test procedure so that the probability of excluding a reachable state is bounded with high probability. Experiments on three nonlinear systems, a forced Duffing oscillator, a planar quadrotor, and a high-dimensional reaction-diffusion system, confirm that the empirical miss rate remains below the Probably Approximately Correct (PAC) bound while scaling to state dimensions beyond the reach of classical grid-based and polynomial methods.

Figures & tables

Fig. 1 : Pipeline overview for the data-driven reachability analysis via diffusion models. From left to right: (1) trajectory data is collected from the nonlinear dynamical system at discrete time steps; (2) a time-conditioned DDPM is trained to denoise states, with the reconstruction error serving as a nonconformity score; (3) the LTT procedure selects a threshold

q_{k}

for the nonconformity score that controls the false negative rate with PAC guarantee; (4) the predicted reachable set is the sublevel set of all states whose score does not exceed

q_{k}

Method	IoU	Precision	FNR(%)
Christoffel [ 11 ]	0.381	0.381	0.00
NF	0.689	0.726	0.08
DDPM (Ours)	0.887	0.918	0.08

TABLE I : Baseline comparison on the Duffing oscillator. All methods except Christoffel use LTT calibration.

Panel of Figure 3 — Fig. 2 : Predicted reachable sets for the Duffing oscillator at six time steps $k$ .

Ablation	$N$	Size	Params	IoU	$T_{\mathrm{query}}$ (ms)
Data Size	$10$	$2048{\times}12$	107.5M	0.070	0.137
	$10^{2}$			0.133
	$10^{3}$			0.329
	$10^{4}$			0.605
	$10^{5}$			0.803
	$10^{6}$			0.887

TABLE II : Ablation studies on the Duffing oscillator.

Panel of Figure 5 — Fig. 3 : Ablation visualizations at $k{=}149$ . Top row: effect of training data size $N$ (model $2048{\times}12$ ). Bottom row: effect of model capacity (hidden dim ${\times}$ layers, $N{=}10^{6}$ ).

Panel of Figure 6 — Fig. 4 : Predicted reachable sets for the planar quadrotor projected onto $(x,h)$ at $t{=}5.0$ .

Panel of Figure 7 — Fig. 5 : Sensitivity analysis for the Gray-Scott system at $t{=}29$ . (a) Acceptance rate under Gaussian perturbation. (b),(c) Score distributions for clean in-set, perturbed in-set, and different-parameter samples.

Reachability Analysis

Reachability analysis determines which states a system can enter from given initial conditions, actions, and disturbances.

See all 78 papers

On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity
Jul 21, 2026Jixian Liu, Ihab Tabbara, Hussein Sibai +1Reachability Analysis Sample Complexity
Department of Electrical and Computer Engineering, Johns Hopkins University · Department of Computer Science, Washington University in St. Louis
Parallel Differentiable Reachability for Learning and Planning with Certified Neural Dynamics and Controllers
May 25, 2026Keyi Shen, Glen ChouRobotic Control Neural Network Verification
Georgia Institute of Technology, Atlanta, GA 30308
Data-driven Reachable Set Estimation with Tunable Adversarial and Wasserstein Distributional Guarantees
Apr 14, 2026Georgios Pantazis, Michelle S. ChongDistribution Shift Robustness
Dynamics and Control (D&C) section at the Department of Mechanical Engineering, Eindhoven University of Technology, the Netherlands.

Jul 21, 2026J/K move · Enter open · S save

On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity

Jixian Liu, Ihab Tabbara, Hussein Sibai, Enrique Mallada

Department of Electrical and Computer Engineering, Johns Hopkins University · Department of Computer Science, Washington University in St. Louis

Reachability Analysis Sample Complexity

Open paper AskPDF arXiv

Reachability analysis is central to safety-critical control, robotics, and neural network verification, but classical computational methods, such as Hamilton--Jacobi reachability and set propagation, scale poorly with state dimension. Sampling-based methods have emerged as a promising alternative, often providing finite-sample guarantees that bound the probability-mass left uncovered. However, an explicit account of how the geometry of the initial set, the dynamics, and the sampling law affect the accuracy of the estimator is not fully available in the literature. We study this by casting sampling-based reachable-set recovery as geometric support estimation over a family of problems specified by an initial set, its dynamics, and a sampling law. First, we identify two regularity properties, positive reach of the initial set's complement and Lipschitz continuity of the dynamics, that together make recovery well-posed: a probability-mass coverage guarantee can be upgraded to accuracy

r

in Hausdorff distance. Second, we bound the resulting sample complexity: recovery is achievable with

\tilde{\mathcal{O}}\big((e^{3LT}/r)^n\big)

samples, exponential in both the state dimension and the time horizon. Third, we show that neither can be removed: an minimax lower bound of

Ω\big((e^{LT}/r)^n\big)

holds for every estimator, so the exponential dependence on dimension and the degradation over the horizon are both intrinsic, not artifacts of a particular method. Experiments on nonlinear systems confirm that adversarial sampling improves constants but not the scaling.

Abstract

Reachability Analysis

Explore similar work

On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity

Parallel Differentiable Reachability for Learning and Planning with Certified Neural Dynamics and Controllers

Data-driven Reachable Set Estimation with Tunable Adversarial and Wasserstein Distributional Guarantees