Proof-Carrying Compression of Verified Networks for Microcontrollers

Some neural networks, such as the collision-avoidance networks for unmanned aircraft, are shipped only after a formal verifier has proven safety properties about them. Tools for designing networks around a specific chip, known as hardware-aware neural architecture search (automated search for layer shapes that meet a device's latency and memory limits), cannot keep those proofs. Any change to the network voids the guarantee, and re-verifying means trusting a large, fast-moving verifier that has shipped false "proven" verdicts before. We propose to shrink an already-verified network for a target microcontroller using only rewrites that come with their own certificate. Such rewrites include deleting a neuron that is provably always off on the operating input range, or collapsing a layer that is provably always linear there. Each certificate is a small arithmetic witness that a checker of a few hundred lines can confirm in exact rational arithmetic. Composed with the original safety proof, these certificates prove that the smaller deployed network satisfies the same properties.

In two sentences: formal verification tells us which parts of a trained network are provably dead weight on the inputs that matter, and hardware cost models tell us which of those parts are worth the effort to prove. We combine the two so that every compression step is independently checkable and the original safety proof carries over to the compressed network without re-running the verifier.

Core Claim

The claim is that certificate-carrying structural reduction, steered by measured device cost, gives larger hardware savings per unit of proof effort than proving redundancy wherever it happens to be found. We also claim it removes two trust dependencies that current pipelines keep. The first is trust in the verifier that found the redundancy. The second is trust in a commercial linear-programming solver used to check the proof.

The key technical observation is that most claims we need are linear-programming infeasibility claims. "Neuron $i$ is never positive on input box $D$" becomes "the relaxed constraint set plus $z_i > 0$ has no solution". An infeasible linear system $Ax \le b$ has a Farkas witness, a vector $y$ that proves no solution exists and can be verified with one matrix-vector product:

$$y \ge 0,\quad y^\top A = 0,\quad y^\top b < 0,$$

where $A$ and $b$ encode the network's weights, the input box, and the relaxed activation constraints. Checking this in exact rational arithmetic needs no external solver. Claims that the relaxation alone cannot prove are split on unstable neurons into a small tree, in the format of Activation Pattern Tree Proofs, with a Farkas witness at every leaf.

To go beyond exact equivalence, we add bounded-deviation rewrites. A neuron whose activation varies only within $[a,b]$ on $D$ is replaced by the constant $(a+b)/2$, and the resulting output change is bounded by $\varepsilon$ through downstream weight norms. The safety property transfers from the original network $f$ to the reduced network $g$ whenever

$$\sup_{x \in D} \|f(x) - g(x)\|_\infty \le \varepsilon < \delta,$$

where $\delta$ is a margin by which $f$ satisfies the property. That margin is itself certified by re-checking the original proof with the threshold shifted by $\delta$.

Position Relative to Prior Work

Three papers supply the method. Simplifying Neural Networks Using Formal Verification (NNSimplify) queries the Marabou solver to prove that ACAS Xu neurons are never active and removes them without retraining. It found 535 of roughly 13,500 hidden nodes removable, about 4% on average and up to 10% in one network. It emits no independent certificate, ignores hardware cost, and considers only neuron deletion.

Generating and Checking DNN Verification Proofs (also; Generating and Checking DNN Verification Proofs; Generating and Checking DNN Verification Proofs) introduces Activation Pattern Tree Proofs and an 800-line checker. That checker caught a real soundness bug in NeuralSAT and reported a 9s versus 204s median checking time against Marabou's checker. However, it validates each leaf by calling Gurobi, a closed commercial solver, and it certifies safety of a fixed network rather than a relation between two networks. We reuse its tree format, replace its leaf oracle with exact Farkas checking, and apply it to equivalence and bounded deviation instead of safety alone.

The proof-logging tradition in SAT solving motivates the design principle. The DRAT certificates for Lam's problem (A SAT-based Resolution of Lam's Problem) and the Ramsey certificates (Verified Certificates via SAT and Computer Algebra Systems for the Ramsey R(3, 8) and R(3, 9) Problems) follow it: let the fast search be untrusted and make the checker small.

The hardware side supplies the steering and constrains the design. HW-NAS-Bench shows that operation counts are a poor stand-in for latency: correlation with latency is as low as 0.18 on the Edge TPU, and rank correlation falls below 0.5 on several devices. It also shows that per-layer lookup tables miss compiler fusion. Both findings mean our cost model must come from measurement on the device, not from neuron counts. DUCCIO reports that fitting layers into the GAP8 chip's on-chip L2 buffer gave 54–61% speedups on Tiny ImageNet. This is exactly the kind of threshold effect that makes some certified removals worth far more than others. ConNAS treats device budgets as hard constraints rather than loss penalties, and satisfied them in 100% of runs. We adopt its hard-constraint framing, but our search space is the set of certifiable rewrites of one trained network rather than a space of architectures trained from scratch.

The runtime monitor in Formal Verification of Neural Certificates Done Dynamically checks a fixed controller online and emits no checkable artifact. It shows that a different trust model exists, but it does not address compression.

Research Program

The system has three parts.

Prover. An untrusted prover computes neuron bounds on the operating domain, identifies candidate rewrites, and produces certificates for them. It uses fast floating-point bound propagation to find candidates and then solves exact linear programs to extract Farkas witnesses. The candidate rewrites are:

  • deleting a stably inactive neuron;
  • deleting an entire convolutional channel that is inactive at every spatial position;
  • collapsing a layer whose neurons are all stably active into its neighbour by multiplying the two weight matrices;
  • replacing a near-constant neuron with a constant under a certified $\varepsilon$.

Checker. A small checker, targeted at under 1,000 lines, verifies witnesses in rational arithmetic. It verifies the composition rule that chains rewrite certificates with the original safety proof.

Scheduler. A hardware-guided scheduler decides which candidate rewrites to attempt and in what order. Its value estimate is measured latency and peak memory saved on the target device, and its cost estimate is predicted proof effort (the number of unstable neurons that would need splitting). It maximises savings subject to a total proof budget, and it treats flash and SRAM limits as hard constraints in the ConNAS sense. The scheduler matters because a proof that one neuron out of fifty is dead saves little, while a proof that a whole layer is linear, or that enough channels are dead for a layer to fit in on-chip memory, can cut latency sharply.

We treat quantization honestly. Certificates are stated over the rational-valued network. Separately, we measure whether the certified rewrites change the int8 compiled model's outputs on test inputs and on the verified domain grid. We report this as an empirical gap, not a proven one.

Baselines

Do nothing. The first reference point is the original verified network deployed unchanged. It gives the latency, SRAM and flash figures against which every saving is measured, and its safety proof is re-checked with our checker to confirm the checker agrees with the original verifier.

NNSimplify. This is the strongest existing method on the exact question of provably equivalent reduction (Simplifying Neural Networks Using Formal Verification). Its reported result on ACAS Xu is 4% of nodes removed on average, 535 of about 13,500 in total. We rerun it on the same 45 networks, input domains and wall-clock budget. We then measure the latency its reduced networks actually achieve on the target devices, which the paper does not report, and feed each of its removal claims into our checker. Beating it means either larger measured latency or memory savings at equal proof time, or the same savings with every claim independently certified. We would regard matching its node count while adding certificates as a partial result, not a win.

Heuristic compression plus re-verification. The strongest practical competitor from the hardware side is magnitude or channel pruning to the same device budget, followed by fine-tuning, followed by re-verifying every original property with a branch-and-bound verifier that emits APTP proofs. Those proofs are checked by the published APTPchecker. We give this pipeline the same device budget, the same total compute including fine-tuning and verification, and the same tuning budget for its pruning ratio. No reported result found on Lacuna for this pipeline on ACAS Xu or the APTP suite, so we will establish it ourselves. Beating it means reaching equal or better device cost with a higher fraction of properties preserved and lower total wall-clock. It also means preserving properties the pipeline never re-checked, which only equivalence or bounded-deviation certificates can guarantee.

Hardware-aware search from scratch. For the convolutional models we also run ConNAS-style constrained search to the same memory budget and then attempt verification. The reference figure is ConNAS's reported 0.14–0.65% accuracy gap to the best feasible architecture on NATS-Bench (Constraint-guided Hardware-aware NAS through Gradient Modification), though that figure says nothing about verifiability.

Ablations. Four ablations isolate the proposal's ingredients:

  • scheduler off: prove everything provable in arbitrary order under the same proof budget;
  • scheduler driven by neuron or operation counts instead of measured device cost;
  • Gurobi-trusted leaf checks instead of exact Farkas checks, which isolates the cost of removing solver trust;
  • exact-only rewrites versus rewrites that also allow bounded deviation.

Why not just…?

Why not just prune heuristically and re-verify the smaller network? This is the real threat, and it may win on raw compression, because fine-tuning can recover accuracy after aggressive cuts. Its weaknesses are that re-verification may simply fail on the pruned network, that it costs a full verification per candidate, and that it guarantees only the properties someone thought to list. Equivalence and bounded-deviation certificates preserve every property of the original on $D$, including behaviour matching the lookup table that ACAS Xu compresses. The re-verification baseline above settles this directly. If it reaches the same device cost with all listed properties preserved in less total time, our contribution narrows to the trust-reduction argument, and we will say so.

Why not just run NNSimplify and trust Marabou? The APTP authors found a verifier falsely claiming a property was proven (Generating and Checking DNN Verification Proofs), and the SAT community's audits of earlier nonexistence results make the same point. We will report how many of Marabou's removal claims our checker confirms. We will also inject known bugs into the prover, such as a wrong bound or a sign flip, and count how many the checker catches. Separately, NNSimplify's 4% average and its lack of hardware steering suggest that exact neuron deletion alone buys little on-device speed. That is why layer collapse, channel removal and bounded-deviation rewrites are part of the design.

Why not just search a new small architecture with hardware-aware search and verify it? A freshly searched network discards the original's validated behaviour and must be verified from scratch, with no guarantee the verifier succeeds. For regulated artefacts such as ACAS Xu, the original network is the object of approval. The search-from-scratch baseline measures how often verification of the new network succeeds within budget.

Why not just steer by neuron or operation counts? HW-NAS-Bench's correlations of 0.18 and below 0.5 suggest that such counts misrank savings. The count-driven scheduler ablation tests whether that misranking matters at the scale of these small networks, where it may not.

Proposed Experiments

Benchmarks and devices. We use the 45 ACAS Xu networks with their standard properties, and the APTP suite of 400 problems over 16 networks: CIFAR2020 convolutional networks of 41K–180K parameters and MNIST feed-forward networks up to 1.7M parameters. Most of these sizes are close to the 250 KB flash regime described in the Visual Wake Words work. The targets are the GAP8 chip used by DUCCIO and the Raspberry Pi 4 from HW-NAS-Bench. All latency, peak SRAM and flash figures are measured after compilation, never taken from lookup tables.

Metrics. We report:

  • measured latency and memory savings;
  • the fraction of original safety properties certified on the reduced network;
  • certificate size and checking time;
  • checker line count;
  • test accuracy change;
  • the observed gap between the rational-valued and int8 models.

First decisive check. Certificate composition must hold end to end: for every reduced network, the checker alone, with no verifier and no Gurobi, must confirm every original property.

Second decisive check. At equal proof budget, the hardware-guided scheduler must beat both the unguided ablation and NNSimplify on measured latency. If it does not, hardware steering adds nothing and the proposal reduces to a certificate format.

Third decisive check. We will measure how often whole layers or whole channels are stable on the operating domain. If this almost never happens on ACAS Xu and the CIFAR2020 networks, certified structural reduction has a small ceiling on real hardware. That would be a negative result worth publishing, and bounded-deviation rewrites would then become the main mechanism to test.

Fourth decisive check. The heuristic-prune-plus-re-verify comparison determines whether exact certificates buy compression or only trust.