- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper verifies reach-avoid properties of high-dimensional, discrete-time, deterministic systems with unknown dynamics from i.i.d. one-step samples. An input convex neural network (ICNN) encoder with additional architectural constraints ("CICO") maps the state to a low-dimensional latent space. Regions of interest are mapped to the latent space with epsilon-RandUP over-approximations. The set-valued latent dynamics are learned with an "Inclusion GP", which lifts the difference inclusion to a function of the latent state and an unobserved coordinate. A nondeterministic transition system (NTS) is then built from GP error bounds, and its verification results are mapped back to the original space. Experiments cover a 3D system, a 6D system, and a 26D LiDAR-based navigation system, each reduced to 2D, on which the authors perform finite-state abstraction.
Critical strengths
- The research problem the paper targets is relevant: abstraction-based verification does not scale with dimension, and a learned latent space is a natural route around this.
- The Inclusion GP idea, lifting a difference inclusion to a single-valued function, is interesting.
- Restricting the encoder to be convex so that regions can be mapped and decoded with sampling and optimization is a reasonable design choice, and the paper states this restriction as a limitation in the conclusion.
- The introduction is well written.
Critical weaknesses
My main concern is that the paper's results are presented as stronger and more general than what is proven. The assumptions the guarantees require are introduced piece by piece across Sections 2-4 and the appendix, while the abstract, the introduction, and the related-work section claim generality and soundness that the technical sections do not support. Several technical statements are also incorrect as written.
W1) Lemma 1 is false as stated. Consider the encoder h_e: \R^2 \to \R built from one skip block followed by an output layer:
- first layer A_1 x = (x_1, −x_1, x_2) (injective),
- SoftPlus activation (strictly monotone),
- A_2 = [[1, 1, 0], [0, 0, 1]] (full row rank, nonnegative),
- injective skip layer A_3 = diag(0.01, 1),
- output layer [1, 0] (full row rank, nonnegative). This satisfies conditions (i)-(iii) of Section 4.1 and the ICNN constraints. The resulting encoder is h_e(x) = sp(x_1) + sp(−x_1) + 0.01*x_1. The pre-image of z = 1.5 is the two parallel lines x_1 \approx −0.702 and x_1 \approx 0.660 (times \R), which is disconnected. The proof in Appendix C.1 breaks where it states that M = \Psi(TS) is "a convex set defined with intervals over the first n dimensions". This only holds when A_1 is axis-aligned: \Psi acts coordinate-wise in the original coordinates, so the change of coordinates T does not commute with \Psi. Here M = {(sp(x_1), sp(−x_1), sp(x_2))} is a curved surface. More generally, a convex function folds at its minimum, so convexity and the absence of folding are at odds. The same example also contradicts the claim in Section 4.3 that "the boundary of a mapped convex set must come from the boundary of the input set": on r = [−1, 1]^2, the lower end of the image is attained at the interior point x_1 \approx −0.02. The end of Appendix C.1 mentions a Jacobian-rank or submersion condition that is not part of the CICO definition. Please correct Lemma 1 and its proof, or state the missing hypothesis. Please also state which later steps depend on it: the "non-conservative" claim for the Inclusion GP (Section 4.1), the region mapping (Section 4.3), and the decoding (Appendix B.6).
W2) The established guarantee is probabilistic, and its confidence level is not accounted for correctly. The abstract and contributions promise that "the abstraction contains the true behaviors" and a "provably correct mapping". That the guarantees hold only with confidence 1 − \delta first appears in Section 4.3. That they additionally need the Lipschitz constant of the encoder only appears in Proposition 3 (Appendix B.1). On Theorem 2 specifically:
- As far as I understand, the randomness comes only from the one-time epsilon-RandUP sampling. If all containment events hold, the simulation argument is deterministic for every k and every x. So the result can be a trajectory-wide guarantee, but the proof does not formalize it that way. Definition 3 (conditions 2–3) states P(\omega_x(k) \in \cdot) >= 1 − \delta separately for each k, which mixes up the sampling randomness with the (deterministic) trajectory. Read literally, this is a stepwise statement, and turning it into a statement about a whole trajectory would need a union bound over infinitely many steps.
- Section 4.3 says the domain property holds "with probability at least 1 − \delta", whereas Lemma 2 states (Pre_{h_e}(Zḃar Z) \cap X\bar X) ⊆\subset X deterministically.
- Section 5 sets \delta = 10^-5, "ensuring abstraction confidence of at least 99.99%". But 1 − 10^-5 is 99.999%, and Appendix B.7 uses \delta = 0.0001. Which one is it?
- Lemma 3 (Appendix D) gives confidence (1 − \delta)^{|AP|−|L(x)|} "by union bound". A product form needs independence, whereas a union bound gives 1 − (|AP| − |L(x)|)\delta. Theorem 3 then drops the confidence level altogether ("guaranteed to satisfy \Phi"). Please restate Theorem 2 as "with probability at least 1 − \delta", with a single and correctly split confidence budget. Please also make the confidence level explicit in the abstract and the contributions.
W3) The RKHS assumption behind Theorem 1 is not justified for a learned kernel, and it fails in the main example.
- Section 4.4 (lines 307–308) states that the Sobolev space H^s with s > n_p/2 "contains continuous functions; \tilde g is continuous and therefore lives in this RKHS". However, the inclusion is the reverse: H^s embeds in the continuous functions, but not every continuous function is in H^s.
- Appendix B.4 assumes "without loss of generality" that the target is within 10^-10 of a function in the squared-exponential RKHS, calling this "a standard assumption". Universality only gives an approximating function, whose RKHS norm can grow without bound as the tolerance shrinks. The bound in Proposition 1 needs the target itself to be in the RKHS with a known norm bound B, and the 10^-10 approximation error does not appear in the bound.
- The kernel \kappa_Z depends on networks \psi_c and \psi_l learned from data ("we assume sufficient data to learn an accurate kernel representation", Section 4.4). Proposition 1 and the bound on B from Skovbekk et al. (2025) are, as I understand them, stated for a kernel fixed before the data is seen. Learning the kernel changes the RKHS, and with it the hypothesis that the target function belongs to it.
- Appendix B.7.3 states that h_e \odot f is discontinuous for the 26D example. This contradicts the assumption in Appendix C.3 that T is in the RKHS of \kappa_X, and the continuity of f that Lemma 1 needs. Please state precisely which function is assumed to be in which RKHS, how B is computed for the learned kernel, and which guarantees still hold for the 26D case study.
W4) The addressed setting is much narrower than claimed, and the restrictions are spread across the paper. The introduction states that the method handles "arbitrary continuous systems" (p. 2) and AI-enabled systems with camera or LiDAR inputs. The guarantees actually need all of the following:
- discrete-time, fully observable, Markovian, deterministic, and noise-free dynamics (Section 2, Section 3);
- compact and convex X, X_G, and every u_i \in X_U (Section 2);
- i.i.d. one-step samples (Section 2), whereas data recorded along trajectories are dependent;
- a known reachable domain \bar X (Section 4.3), which is \bar X = X in every experiment (Appendix B.7), so X is implicitly assumed forward invariant, and the domain-exclusion step is never applied;
- an ICNN encoder with strictly monotone activations, which importantly excludes ReLU (Section 4.1, Remark 1);
- Lipschitz constants for the encoder and for the dynamics (Proposition 3, Section 4.4);
- the RKHS assumptions of W3. Stacking x = (s, y) with y = o(s) places the data on an n_s-dimensional manifold inside a convex set X \subset R^{n_x}. Appendix B.7 then samples only "kinematically feasible" points, which is not the uniform sampling that Proposition 3 assumes. The conclusion notes that it is open how to incorporate noise, yet the 26D controller is trained in a noisy environment, and the paper does not discuss stochastic abstraction methods such as interval Markov decision process (IMDP) abstractions. Cauchi et al. (2019) and Gracia & Lahijanian (2025) are cited, but not in the related-work section.
I strongly advice the authors to collect all assumptions in one place in Section 2 and align the claims in the abstract and the introduction with them. This level of rigor also leads into my next concern.
W5) Related work is described inaccurately, and "sound" is used without a definition. The paper states that Chen & Sankaranarayanan (2016), Awan and Zamani (2025), and Schon et al. (2025) "have strong assumptions on the form of the dynamics", and then: "Unlike the aforementioned literature, this work provides soundness guarantees." As I read these works, their simplified models are approximate on purpose (for example, a linear or reduced-order model), and the approximation error is carried through the guarantee. The present paper's latent dynamics are also only approximately preserved, and its assumptions (W4) are not weaker. The sentence reads as saying those methods are unsound. Similarly, the claim that "no existing method enables formal verification in a latent space while also providing correctness guarantees for both the mapping of specifications into the latent representation and the learned latent dynamics" needs qualification: Lutkus et al. (2025) provide stability and safety guarantees for latent-space control through certificate functions. The paragraph on abstractions for unknown dynamics cites only Skovbekk et al. (2025) and Reed et al. (2023), although the broader data-driven abstraction literature exists (e.g., Kazemi et al., 2024, which the paper cites later). "Sound" and "soundness" appear about 24 times and are never defined. Please describe each cited work by the guarantee it gives, or name the specific assumption that is stronger than the ones in Section 2 and Section 4.1. Please remove or qualify the "no existing method" sentence and the "unlike the aforementioned literature" sentence, and define "soundness" once if you insist on using it.
W6) Specification class and problem statement.
- Section 2 states that LTL specifications "reduce to reach-avoid properties over an extended state space via a finite abstraction … without loss of generality". This holds for syntactically co-safe or bounded-time fragments, which give a deterministic finite automaton. General LTL needs a Buchi or Rabin acceptance conditions that are not reach-avoid.
- Problem 1 asks for a "maximal" initial set. The method returns Q_yes, a sound under-approximation that depends on the discretization, and the paper does not show maximality.
- Section 4.4 describes Q_no as "states that can never satisfy \Phi". In Appendix B.7.2, roughly 60% of the trajectories that start in Q_no are safe and reach the goal. Under an over-approximating abstraction, Q_no cannot have that meaning. Please restrict the reduction claim to the fragment it holds for, replace "maximal" with what is actually computed, and correct the definition of Q_no.
W7) Experimental evidence. The only baselines are the authors' own abstraction in the original space. There is no comparison with other latent-space or data-driven verification methods, and no empirical check of soundness. Please report the fraction of sampled original-space trajectories from Q_yes that violate \Phi, and compare against at least one approach outside this research line, such as a sampling-based or stochastic-abstraction method.
Questions for authors
- Under what additional hypothesis does Lemma 1 hold, given the counterexample in W1? Which results depend on connected pre-images?
- Is the 1 − \delta in Theorem 2 a confidence level over the epsilon-RandUP samples that holds simultaneously for all trajectories and all time steps? How is \delta split between the domain, the goal, and the unsafe sets?
- Which of \delta = 10^-5 and \delta = 0.0001 was used?
- Which function is assumed to be in which RKHS, and how is the norm bound B obtained for a kernel whose feature maps \psi_c and \psi_l are learned from the data? Does Proposition 1 (Reed et al., 2025, Theorem 2) cover a data-dependent kernel?
- Which guarantees still hold for the 26D case study, given that h_e \odot f is discontinuous there (Appendix B.7.3) and Lemma 1 assumes that f is continuous?
- Does the state x = (s, y) give Markovian dynamics in the 26D example, where the obstacle map is not part of s? How does sampling only kinematically feasible points fit the uniform-sampling assumption of Proposition 3?
- Is the encoder architecture a free choice of the user, independent of the system's own controller? How does the convexity restriction limit the achievable latent dimension or the conservatism of the abstraction?
10 comments
W2/Q2/Q3: Confidence notes
W2/Q2: Confidence notes
We argue that a probabilistic or confidence-based guarantee is a provable guarantee and is the standard for data-driven abstraction in literature. PAC-, scenario-, conformal prediction-, and Gaussian process-based abstractions all have varying results on the level of confidence in the correctness of the abstraction but all result in a provable guarantee. We can make this explicit in the introduction.
-
The reviewer's interpretation of the probability is correct, and the relation holds for every and ; hence, not requiring a union bound over an infinite trajectory.
-
Section 4.3 outlines how the deltas are defined such that the confidence for each region holds at as independent events.
-
Lemma 2 is not intended to be read as a deterministic statement. We will move the confidence statement prior to to avoid this possible confusion.
-
It is the definition of the space itself that holds with confidence, there is no confidence related to steps in a trajectory.
-
We use ; the is a typo we will correct.
-
We will replace confidence with probability in Theorem 2 as requested and ensure Theorem 3 in the appendix keeps the confidence explicit as in Theorem 2.
W3, Q4, and Q5: RKHS assumptions and bounds
W3: RKHS assumption
-
We clarify that the Sobolev argument in lines 307–308 is intended for sufficiently smooth . Specifically, suppose has continuous derivatives, bounded up to the boundary of a bounded Lipschitz domain, where is the input dimension of . Then belongs to the Sobolev space . By choosing a Matérn kernel with smoothness parameter such that , its RKHS contains . We will clarify these conditions in the revised version.
-
The SE kernel is universal, so it can approximate any continuous arbitrarily well on a compact domain (Steinwart and Christmann, 2008, Chapter 4). However, the approximating functions may have unbounded RKHS norm as . As is common practice, we assume there exists in the SE RKHS such that for some known bound . Our verification results hold for , which we take to be effectively (with neglected due to its small value, e.g., ).
We emphasize that this is for practical application and is not a limitation of theory, as current tooling allows for the propagation of the SE base kernel. The dropping of this small term is common throughout literature that makes use of the SE kernel to model functions.
-
The deep kernel is learned in a first stage and then held fixed. All subsequent results, including Proposition 1 and the norm bound , are conditional on the learned parameters of and and are stated for the resulting fixed kernel and its RKHS . The assumption is therefore that the target function lies in with , where is computed for the frozen kernel.
-
Finally, continuity of ensures that dynamics remain connected in the latent space, which allows an inclusion GP to capture the evolution in a non-conservative manner. A discontinuous can still allow discontinuity in the dynamics of the latent space, and the Inclusion GP must then predict a connected set that contains this jump, potentially making the GP predictions more conservative. This does not break correctness, as the latent abstraction will simply contain more behaviors than the true system and will make results more conservative.
Q4: RKHS norm bound
Following the discussion on W3 above, theoretically the would be in the RKHS of some kernel and all associated theorem hold. Practically, we assume there exists some function in the RKHS of the deep kernel with the SE kernel as a base kernel that is arbitrarily close to the function being modeled. This follows from universality of the SE base kernel. Any RKHS error bound holds for a deep kernel, the norm is influenced by the neural network prior and must be determined after the neural network weights are fixed. The RKHS norm can be approximated from data following the methods outlined in the subsection Latent RKHS Constants below Theorem 1.
Q5: Guarantees for the 26D example
As discussed above and in Appendix B.7.3, our framework still provides guarantees for this example. Note that, in our framework, Inclusion GP models the lifted dynamics , where the additional variable allows the original discontinuous evolution to be represented within a conservative set-valued model. In particular, the lifted representation can include additional behaviors that do not correspond to the original dynamics, introducing conservatism rather than false positives.
The theoretical guarantees therefore depend on the regularity and RKHS assumptions of the lifted dynamics, rather than the smoothness of the original closed-loop dynamics. As discussed above, these assumptions can be satisfied using an appropriately chosen Matérn kernel for sufficiently smooth lifted dynamics, or formulated for a fixed SE deep kernel with an explicit RKHS norm bound and treatment of any approximation error.
We will further clarify this distinction and the associated assumptions in Appendix B.7.3.
W1/Q1: Correctness of Lemma 1
We thank the reviewer for this detailed review.
We thank the reviewer for this counterexample. We agree that Conditions (i)-(iii) do not exclude folds on their own as noted, but the counterexample violates the Jacobian rank condition (the Jacobian vanishes at x1≈−0.02), as stated in the proof of Lemma 1 (see Lines 987-989 in Appendix C.1 of the initial submission). We have made this requirement explicit in the text of Lemma 1 in the revised version of the paper (it is also state below for the reviewer's convenience). Under the condition that the Jacobian of the network has rank np, every fiber is connected by a short constructive argument (flowing any point onto the fiber along a bounded right inverse of the Jacobian), which replaces the convexity-based proof.
Note that convexity of the encoder is not needed for connectedness; it is retained for the convex optimization in decoding. Also note that "the boundary of he(X) comes from the boundary of X" is true if the encoder is an open map on the interior of X, and the Jacobian condition gives exactly that, since a submersion is open.
The only aspect that relies on connected inclusion dynamics are needed only for the inclusion GP to be non-conservative by design. If the dynamics in the latent space are disconnected (e.g., if the original dynamics are discontinuous), then it is not clear how to learn a latent space such that these discontinuities do not inhibit verification. This is seen in the 26D example, where discontinuities force the inclusion GP to be overly conservative around the edges of obstacles.
Below is the restated lemma.
To ensure clarity, we have updated the proof in the revised version of the paper (see Appendex C.1).