- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The authors presents a neurosymbolic approach for verifying oblique decision tree policies for reach-avoid specifications (of which safety specifications are a special case). The main idea is to learn abstractions of the reachable states in the form of unions of polytopes and subsequently verify these candidate abstractions using LP/MILP-based symbolic verification. The learning and verification procedures are combined in a counterexample-guided loop. The MountainCar, QuadRotor, and CartPole benchmarks are used to demonstrate the approach. Compared with axis-aligned decision tree policies and axis-aligned abstractions, considerably fewer polytopes are needed in the considered examples.
Critical strengths
- The addressed problem is relevant.
- Learning is used to obtain suitable abstraction candidates, while the final containment properties are checked using LP/MILP formulations. This is thus a contribution to the promising direction of "learning for verification".
- Experiments demonstrate that the number of sets required is reduced.
- The authors also consider unbounded-horizon safety through invariant sets.
- The paper contains theoretical results on the existence of ODT certificates for robustly safe ODT policies.
Critical weaknesses
-
The system is formally introduced through a discrete-time successor function, and the paper states that this successor function is given by Runge-Kutta RK4 equations. For CartPole, the original continuous dynamics are integrated with RK4 using a control period of 0.02 to obtain the successor function. RK4, however, only approximates the solution of the underlying differential equations. The verification therefore appears to establish properties of the RK4-discretized model rather than of the original continuous-time system. Unless the numerical integration error is rigorously bounded and incorporated into the reachable sets, it is unclear to me how the claimed guarantees transfer to the continuous dynamics. This distinction is particularly important for a paper whose primary objective is formal safety verification.
-
The considered control systems are restricted to a discrete set of actions. This is explicitly part of the system definition, and the experiments use, for example, eight discrete actions for QuadRotor and two actions for CartPole. This substantially restricts the applicability of the approach. Many real-world cyber-physical control problems involve continuous control inputs. This requires an appropriate justification.
-
The main quantitative comparison emphasizes the number of polytopes. The authors show impressive reductions compared with the axis-aligned baseline. However, this metric alone does not establish computational efficiency. Axis-aligned boxes have particularly simple representations and operations, whereas general polytopes, and especially unions of polytopes, can require substantially more expensive computations. In fact, the proposed containment verification for a union introduces binary variables and an MILP formulation. I am missing a convincing runtime and complexity comparison. Without such a comparison, it is unclear whether reducing the number of sets actually results in computational improvements.
-
Previous reachability and abstract-interpretation approaches have already considered general polytopes. The paper argues that it learns polytopic flowpipes directly and represents abstractions as unions of polytopes. The manuscript should explain much more explicitly what the non-trivial methodological step is in going from existing polytope abstractions to the proposed unions of learned polytopes.
-
The experimental evaluation is too small to assess scalability: MountainCar is two-dimensional, CartPole is reduced from four states to a two-dimensional subsystem for verification, and QuadRotor has six state variables but has additional structure that the implementation exploits. For example, at each QuadRotor step the authors group states according to variables that take only 1–4 distinct values and learn polytopes over only (x,y)(x,y)(x,y) for each group. These are useful proof-of-concept examples, but they provide little evidence that the method scales to higher-dimensional CPS problems.
-
The presentation and language need improvement. There are numerous grammatical problems and typographical errors. Some parts are difficult to understand.
Questions for authors
-
What exactly is formally verified when RK4 is used for the successor relation? Is the guarantee only with respect to the RK4-discretized dynamics, or is there also a guarantee for the original continuous-time differential equations? If the latter, where is the RK4 truncation error bounded and incorporated into the abstraction?
-
Could the authors provide a formal treatment of numerical integration error? In particular, could an interval or set-valued enclosure of the RK4 error be incorporated into succ so that verification also covers trajectories of the underlying continuous dynamics?
-
How could the approach be extended to continuous control actions? The formulation assumes a finite action set and exploits the fact that every ODT leaf corresponds to one fixed action. Is this assumption fundamental to the proposed verification formulation?
-
What is the computational complexity of NeSyVerif? How does it depend on the state dimension, the number of policy leaves, the number of polytopes, the number of inequalities per polytope, and the number of time steps? The scalability with respect to the number of continuous state variables is the most important one.
-
Can the authors provide runtime comparisons with the axis-aligned baseline? A reduction from 8241 boxes to 84 polytopes sounds substantial, but fewer sets do not necessarily imply a faster verification procedure because general polytope operations and MILPs are more expensive.
-
How much of the improvement is attributable to the ODT policy and how much to the oblique abstraction? Interestingly, the appendix already reports NeSyVerif on an AADT policy for MountainCar: 153 polytopes versus 1481 for VeriXAI, while NeSyVerif with an ODT policy requires 129. This suggests that comparing AADT/ODT policies and axis-aligned/oblique abstractions separately could provide considerably more insight.
-
What is the essential novelty of using unions of polytopes compared with previous work on polytope abstractions? Is the contribution the representation, the adaptive construction of that representation, the loss functions, or the counterexample-guided learning procedure? This should be made more explicit.
-
Could the authors provide at least one substantially higher-dimensional benchmark where the special low-dimensional reductions used for CartPole and QuadRotor are unavailable?
9 comments
A6. In short: the ODT policy ensures better policy efficiency (better reward and/or fewer leaves), while the ODT abstractions ensure fewer polytopes and make invariants possible. Notice that AADT abstractions cannot handle ODT policies, while ODT abstractions handle AADT policies better than AADT abstractions.
The appendix results decompose the two effects. With the AADT policy fixed, replacing VeriXAI’s axis-aligned abstraction with our oblique abstraction reduces the polytope count from 1481 to 153. With our oblique abstraction, switching from AADT to ODT reduces it further to 129, partly because the ODT policy also performs better (reward –109 vs. –126). Most of the improvement therefore comes from the oblique abstraction. The axis-aligned abstraction with ODT policy combination cannot be evaluated, since VeriXAI does not support ODT policies, whereas NeSyVerif supports both.
A7. Both VeriXAI and NeSyVerif use unions of polytopes. The difference lies in the shape of the polytopes used in the abstraction. Previous work on polytope abstraction uses fixed polytope templates (axis-aligned hyperrectangles); that is, it does not learn the shape of the polytopes. Our contributions are therefore threefold: (i) an adaptive representation of the abstraction; (ii) adaptive learning, in which we learn the oblique DT and thereby the structure and shape of the polytopes; and (iii) novel loss functions for the discrete-time, discrete-action setting, which differ from those in existing work. And most importantly, Theorem 2 establishes that ODT invariants are sufficient for ODT policies.
A8. Existing work focuses on learning certificates for continuous systems, with continuous-time and continuous-action, and the set of baselines available for comparison for systems with discrete actions in discrete time is limited. We use the baselines from VeriXAI (NeurIPS’23) as is; no special reductions or modifications were made for this work. These environments are challenging, and the fact that our method handles them successfully is itself a contribution, in particular for finding and proving an invariant. For perspective, Fossil 2.0, which was extended to handle discrete actions in discrete time, uses 2D baselines and failed to learn an invariant for the CartPole environment. Extending the method to higher dimensions is planned for future work.
Formal guarantees and computational complexity
The results do not seem to be formally correct and the computational complexity is exponential in the number of system dimensions. Pointing to another paper that is also not formally correct is not helping much in my opinion.
We thank the reviewer for the constructive review. We have answered the questions and addressed the weaknesses, and we will update the PDF in the following days.
A1. We consider the exact same setting as in the [VeriXai, NeurIPS'23] paper. Namely, on line 150, we assume that the dynamics is given by an RK4 equation.
[VeriXAI]: Schilling, Christian, et al. "Safety verification of decision-tree policies in continuous time." NeurIPS’23.
A2. Errors can be incorporated in the verification process. For instance, in Theorem 2, if a policy is ϵ-robustly safe, then there exists an invariant for any ϵ′-perturbed system for ϵ′<ϵ. In practice, the closer ϵ′ is to ϵ, the narrower the invariant will be, and it will be very hard to find. Still, we could account for ϵ′=ϵ/2 errors without too many issues. That being said, errors were not part of the [VeriXAI] setting, so we did not incorporate them.
A3. Few works have succeeded in producing concrete results for systems with discontinuities, unlike for continuous systems where many works can be applied. We thus focused on this more challenging discrete-action, discrete-time setting; handling continuous actions has already been dealt with by others.
A4. The learning part handles high dimensions (number of continuous variables) well. Concerning the verification part, we need to check that Next(⋃i≤nPi) is included into ⋃j≤mPj′. The complexity is linear in m, polynomially in the number of equations k of each P, and potentially exponential in nj<n, the number of polytopes Pi whose image intersects a given Pj′: the complexity is in O(∑jknj). There are ways to efficiently compute that when nj is not too big (in the paper, brute force was efficient because nj was 1 or 2). The number n depends linearly on the number of leaves in the policy. ODT ensures that n is reasonably small (compared e.g. to AADT or ReLU NN).
A5. Since training and verification are performed offline (once only), computational efficiency is not crucial. Rather, we claim that more expressive certificates make it possible to synthesize certificates that VeriXAI cannot. Regarding global runtime, our method finds an invariant for CartPole in 1 hour, whereas Fossil 2.0 fails to find one even after 4 hours.
The verification part, which is based on LP and the abstraction-refinement loop, takes negligible time: 1.3 seconds for CartPole invariant. The learning part is what takes time (with the current PyTorch implementation, which is not very efficient). For instance, it took 1 hour to learn sequentially the 2 polytopes to obtain the invariant.
VeriXAI, the axis-aligned baseline, performs reachability analysis alone and does not provide an invariant certificate, so a direct runtime comparison is not meaningful. Moreover, invariants are not axis-aligned in general. Learning an invariant is very challenging for systems with discontinuities (see above for FOSSIL 2.0).
Our main contribution is theoretical, with Theorem 2 showing that simple ODT invariants are sufficient, and experiments show that this is also learnable in practice (in different cases of ODT policies, but also AADT policies in the appendix).
continued...