Reusing Suffix Certificates Across Branch-and-Bound in Chordal SDP Verification

Semidefinite programming relaxations can prove that a neural network behaves safely in cases where cheaper linear relaxations fail. A semidefinite program, or SDP, is a convex optimization problem over matrices that must stay positive semidefinite. The cost is speed. The strongest such verifier, BaBSDP, splits the input region into smaller pieces whenever a proof is inconclusive and solves a fresh SDP for every piece. Its authors report runtimes reaching thousands of seconds per image (A Semidefinite Relaxation Based Branch-and-Bound Method for Tight Neural Network Verification). Much of this work is repeated. Two sibling pieces of the input region often produce nearly the same range of activations deep in the network, so the proof that "everything after layer $k$ is safe" gets redone from scratch many times.

We propose to solve that repeated piece once, store it, and reuse it. The proof for the back half of the network (layers $k$ through $L$) is a small SDP when the problem is split along its chordal sparsity, meaning the network's layer-by-layer structure lets one large matrix constraint break into small overlapping blocks. We store this "suffix certificate" keyed by a box of layer-$k$ activations. Before solving any later piece, we check whether that piece's layer-$k$ box fits inside a stored one; if it does, the piece is proved safe without solving anything. The obvious way to get cache hits on real-valued keys is to round them onto a grid, and that rounding is exactly where tightness gets lost. We avoid it with two devices. Cache lookup is a containment test on real-valued boxes. Each stored certificate is also deliberately inflated to the largest box it still provably covers, which is the SDP analogue of the margin-based pruning that let ArborEnum cache continuous decision-tree splits without binning.

Core Claim

In SDP-based branch-and-bound over deep feedforward networks, a large fraction of branch nodes can be closed by checking that their layer-$k$ box is contained in a previously certified box. This holds when certified boxes are enlarged by bisection on their own slack. On deep MNIST networks, the reuse should raise verified accuracy within a fixed time budget over both BaBSDP and a chordal BaBSDP without caching. It should also beat caches built by rounding bounds to a grid, which must either loosen bounds (losing proofs) or rarely hit. The claim is falsifiable at low cost: if sibling layer-$k$ boxes rarely nest inside inflated certified boxes, the idea fails, and we can measure this from logged BaBSDP trees before building anything.

Where This Sits

Three bodies of work supply the pieces, and none combines them.

Chordal decomposition supplies the method for making suffix proofs cheap. Grone's theorem says a matrix with a chordal sparsity pattern is positive semidefinite exactly when each block indexed by a maximal clique is. Feedforward networks yield a block-arrow pattern whose cliques follow adjacent layers (Exploiting Sparsity for Neural Network Verification). Using this, Newton and Papachristodoulou scaled exact SDP verification to 1,000 layers. Chordal-DeepSDP (Chordal sparsity for SDP-based neural network verification) proved equivalence to monolithic DeepSDP and verified Cart40 trajectories for 30 steps. Both are single-pass solvers with no search tree and no reuse. We use their decomposition for two purposes: the layer-$k$ clique separator defines a natural interface at which to cut, and the suffix cliques form a small, separate SDP.

BaBSDP motivates the proposal. It shows that branching on top of SDP relaxations closes gaps LP methods cannot: 80% verified accuracy on MNIST MLP-6x100 where LP verification gets 0%. It also solves a monolithic SDP at every node and never reuses anything.

Shared Certificates (Shared Certificates for Neural Network Verification) is the closest existing work. It precomputes box templates at hidden layers and skips downstream verification when a perturbation's zonotope fits inside a template. It reports subsumption of up to 95% of $2\times2$ patch perturbations on MNIST and end-to-end speedups of 1.2x to 2.9x. It differs from our proposal in three ways. Its templates are built offline for a known family of perturbations, whereas ours are generated online inside a branch-and-bound tree from nodes that just succeeded. It uses loose linear abstractions, whereas our suffix proofs are SDPs. And it does not enlarge templates by certified slack. Its high subsumption rate is our main evidence that intermediate-layer containment is common in practice.

The decision-tree literature supplies the lesson about continuous keys. CODT omitted caching on the stated belief that repeated subproblems are rare with continuous features (Search Strategies for Optimal Classification and Regression Trees). ArborEnum showed the belief is wrong once subproblems are identified by structure rather than literal real values, and once margins let one evaluation cover a whole interval of thresholds (ArborEnum: Decision Tree Rashomon Sets over Continuous Features); it finished 63x faster than SORTeD on Bike. We transfer the margin idea, not the bitset key, to a convex setting.

Research Program

The suffix certificate. Write $z_k$ for the layer-$k$ activation vector, $T=[c-t r,\,c+t r]$ for a box at layer $k$ with center $c$, half-widths $r$ and scale $t$, and $\phi(z_k)\le 0$ for the safety specification applied to the network's output. The suffix SDP looks for nonnegative multipliers $\lambda$ that satisfy one condition:

$$\sum_{j\in\mathcal{C}_{\ge k}} E_j^\top M_j(\lambda;\,T)\,E_j \preceq 0 .$$

Here $\mathcal{C}_{\ge k}$ is the set of cliques covering layers $k$ through $L$, each $M_j$ is the small matrix for clique $j$, assembled from the box constraint on $z_k$, the ReLU quadratic constraints and the specification, and each $E_j$ selects that clique's entries. If such $\lambda$ exists, every activation in $T$ maps to a safe output. That makes containment-based reuse sound by construction, with no approximation in the lookup.

Inflation. After a node is verified, we take its layer-$k$ box. If the suffix SDP certifies that box, we bisect on $t$ to find the largest scale that still certifies, and store the inflated box. For fixed $t$ the problem is an SDP, so bisection costs a few small solves.

Lookup and search. At every node the solver first runs a containment query over stored boxes at a small set of candidate cut layers, using an R-tree index. If a stored box contains the node's box, the node is closed. Otherwise the solver runs the full chordal SDP, decides whether to store a certificate, and branches as BaBSDP does.

Two points of honesty about tightness. First, summarizing the layer-$k$ set by a box is itself an information loss, so a suffix proof is weaker than the full SDP. The cache therefore never replaces the full solve; it only skips it when containment holds. Second, a parent's box contains its children's boxes, but the parent failed, so hits must come from verified siblings and cousins, or across specifications for the same network. We will measure which sources dominate.

Design questions to study. We will study which layer to cut at, when the extra cost of storing a certificate pays for itself, and whether richer keys beat boxes. One richer key is an ellipsoid read off the dual solution of the full SDP on the separator clique; we treat it as an extension.

Baselines

The naive reference point is BaBSDP as published (A Semidefinite Relaxation Based Branch-and-Bound Method for Tight Neural Network Verification), run with MOSEK on the same CPU hardware and the same per-instance timeout. Its reported numbers are 80% verified accuracy on MNIST MLP-6x100, 47% on MLP-9x100 (versus 35% for LayerSDP), and 18% on a CIFAR-10 convolutional network. We will first reproduce these figures under our timeout.

The strongest competitor that isolates our contribution is chordal BaBSDP without a cache. This is our reimplementation that solves each node with the Chordal-DeepSDP decomposition (Chordal sparsity for SDP-based neural network verification), dualized via Dualization.jl, which those authors report gives over 10x speedups on DeepSDP. It uses the same branching rule and timeout. It matters because a large share of any speedup may come from decomposition alone, so caching must win beyond it. No reported result exists on Lacuna for chordal decomposition inside branch-and-bound. Beating it means higher verified accuracy at equal wall-clock budget, or equal accuracy with at least 2x fewer full SDP solves per instance.

Three ablations isolate the key ingredients. The first is the same cache with inflation disabled, so stored boxes are just the node's own box; this tests whether certified enlargement, the anti-discretization step, matters. The second is a grid-keyed cache that rounds layer-$k$ bounds outward to a uniform grid at several resolutions and hashes them, the standard way to make continuous memoization "trivial." The third is a warm-started variant of chordal BaBSDP that passes parent duals to children, solved with ADMM (Fast ADMM for semidefinite programs with chordal sparsity) so that warm starts are meaningful.

As an external reference we report α-β-CROWN, the VNN-COMP winner in 2021 and 2022 (First three years of the international verification of neural networks competition (VNN-COMP)), on the same MNIST networks with its default GPU configuration. We report it with its hardware stated, not as a like-for-like comparison.

Why not just…?

Why not just warm-start each child SDP from its parent's solution? This is the most serious threat to the speedup claim. Warm starts are effective for first-order solvers like ADMM. A warm start still solves every clique at every node, whereas a cache hit skips the suffix entirely. Interior-point solvers such as MOSEK, which BaBSDP uses, gain little from warm starts. The warm-start ablation settles this directly. If warm-started ADMM matches the cache in solves avoided and wall-clock time, the cache is not worth its complexity, and we would report that. We also test the combination, since the two are compatible.

Why not just round bounds to a grid and hash them? Rounding inward is unsound. Rounding outward loosens the box, so stored certificates either fail to verify or require coarser, weaker suffix proofs; making the grid fine enough to keep tightness drives hits to zero. This is the same coarse-versus-fine dilemma ArborEnum documents for binarized trees, where 20 binarized features at depth 4 already give $8.4\times10^{18}$ candidate trees. The grid-cache ablation, swept over resolutions, will plot hit rate against lost proofs. Our prediction is that no resolution matches containment plus inflation.

Why not just use GPU linear-relaxation branch-and-bound like α-β-CROWN? On wide, shallow networks it may well win, and we will say so. The evidence for SDPs is specific to depth: BaBSDP reports LP verification at 0% on MLP-6x100 against 80% with SDP. Our target regime is deep networks, where suffix reuse is also most plausible. A further limitation is that our pipeline is CPU-bound, because high-precision SDP solvers lack GPU support. That gap is a known weakness that this work does not fix.

Why not use offline templates as in Shared Certificates? Offline templates need a known perturbation family to generate them. Branch-and-bound creates its subregions adaptively, so the useful templates are only discovered during search. We include a variant that seeds the cache with Shared-Certificates-style templates computed before search, to measure how much online generation adds.

Proposed Experiments

Pilot. The first experiment is a cheap go/no-go test that requires no new solver. We run BaBSDP on MNIST MLP-6x100 and MLP-9x100, log every node's intermediate bounds and outcome, and compute offline how often a later node's layer-$k$ box would fall inside an earlier verified node's box, with and without inflation. If the inflated containment rate is below roughly 10% of nodes at every cut layer, we stop and redirect.

Main study. If the pilot passes, we compare all baselines on MLP-6x100, MLP-9x100 and the CIFAR-10 network from BaBSDP. We report verified accuracy under a fixed timeout, full SDP solves per instance, cache hit rate by source (sibling, cousin, cross-specification), extra time spent on inflation, and cache memory.

Depth test. The second setting is reachability for the unrolled cart-pole controllers Cart10 and Cart40 used by Chordal-DeepSDP. There, Chordal-DeepSDP-2 took about 10 seconds against over 1200 for DeepSDP at Cart10 with 7 steps, and DeepSDP ran out of memory beyond 8 steps. We add branching on the initial-state set and extend the horizon to 30 steps. Depth here is extreme, so suffix reuse should be strongest; failure on this benchmark would be decisive evidence against the idea.

Sensitivity analysis. Finally, we vary network width at fixed depth on synthetic feedforward networks in the style of Newton and Papachristodoulou. This tests whether wide layers, which create large cliques, shrink the containment rate. Our hypothesis is that boxes on wide layers are less likely to nest, which would bound where the method applies.