△ Mechanism confirmed, baseline not beaten 2026

Sound active-neuron pruning for SDP verification

Implementation & benchmark of arXiv:2607.03232 — Fast SDP certification of neural networks : towards large multi-class datasets

Usefulness6/10

Difficulty5/10

Novelty6/10

Optimization Speedup Scalability Memory Training Regularization Inference speedup Memory Optimization Convex analysis Linear algebra

Source paper: Fast SDP certification of neural networks : towards large multi-class datasets arXiv:2607.03232 ⓘ · analyzed Aug 30, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Reduce the SDP dimension by removing ReLU neurons that are provably inactive, always active, or incapable of changing the current worst-case margin. The verifier keeps exact affine substitutions for fixed-sign neurons and retains only genuinely unstable neurons whose activation can cross zero under the perturbation set. A stronger optional rule removes an unstable neuron when its certified maximum possible contribution is below a user-controlled tolerance, with an exact mode that prunes only zero-contribution neurons.

Formulas

$$UP^{1}_{k+1,j}=\sum_{l=0}^{k-2}\sum_{\substack{i\in{\cal J}_k,\ i\ \mathrm{unstable}\\ A_l^i>0}}UP^{1}(z_l^i,z_{k+1}^j)+\sum_{l=0}^{k-2}\sum_{\substack{i\in{\cal J}_k,\ i\ \mathrm{unstable}\\ A_l^i\le 0}}LO^{1}(z_l^i,z_{k+1}^j),$$

$$UP^{2}_{k+1,j}=\sum_{l=0}^{k-2}\sum_{\substack{i\in{\cal J}_k,\ i\ \mathrm{unstable}\\ A_l^i>0}}UP^{2}(z_l^i,z_{k+1}^j)+\sum_{l=0}^{k-2}\sum_{\substack{i\in{\cal J}_k,\ i\ \mathrm{unstable}\\ A_l^i\le 0}}LO^{2}(z_l^i,z_{k+1}^j).$$

$$\text{prune neuron }i\text{ if }L_i\ge0\text{ or }U_i\le0;\qquad \text{optional contribution pruning if }|w_i|\max(|L_i|,|U_i|)\le\tau.$$

$$\mathrm{ReLU}(a_i)=a_i\ \text{when }L_i\ge0,\qquad \mathrm{ReLU}(a_i)=0\ \text{when }U_i\le0.$$

Mathematical statement

For each neuron i at layer l, let A_l^i be its preactivation interval or nominal activation bound, and call it unstable when its interval contains zero. The paper's bound propagation separates positive and nonpositive coefficients: an upper bound uses an upper product bound UP^1(z_l^i,z_{k+1}^j) when A_l^i>0 and a lower product bound LO^1(z_l^i,z_{k+1}^j) when A_l^i<=0, with an analogous second bound. In the extracted recursion, UP^1_{k+1,j}=sum over unstable i with A_l^i>0 of UP^1(z_l^i,z_{k+1}^j) plus sum over unstable i with A_l^i<=0 of LO^1(z_l^i,z_{k+1}^j), and similarly for UP^2. Here UP^r and LO^r are valid upper and lower bounds on the r-th bilinear lifted product, z_l^i is a hidden neuron, and z_{k+1}^j is a downstream variable. Fixed-sign neurons do not need binary/sign ambiguity in the SDP. A sound contribution test is |w_i| U_i <= tau, where w_i is the downstream coefficient and U_i=max(|L_i|,|U_i|) is the interval magnitude; exact pruning uses tau=0, while tau>0 is an incomplete speed/accuracy tradeoff.

Implementation notes

1. Integration point: add a pruning pass to the verifier after interval bound propagation and before constructing SDP variables and product constraints. For every hidden preactivation a_l^i, store lower and upper bounds L_l^i,U_l^i under the input perturbation set. 2. Pseudocode: for each layer l and neuron i, if L_l^i>=0, mark fixed-active and substitute z_l^i=a_l^i; else if U_l^i<=0, mark fixed-inactive and substitute z_l^i=0; otherwise mark unstable and allocate the SDP activation and lift variables. For each retained downstream edge i->j, compute a coefficient w_ij and contribution bound c_ij=abs(w_ij)*max(abs(L_l^i),abs(U_l^i)); in exact mode prune only c_ij=0, while approximate mode prunes c_ij<=tau and records tau. Rebuild the paper's UP^1, UP^2, LO^1, and LO^2 bound sums using only unstable neurons, selecting UP or LO according to the sign of A_l^i. 3. The interval sign substitutions are mathematically sound; tau-based pruning is empirical and must be reported as a relaxation-quality tradeoff. Never prune an unstable neuron in the exact certificate unless its outgoing coefficient is identically zero. 4. First experiment: run a ReLU CNN verifier on MNIST and CIFAR-10 at epsilon=0.1 and 8/255, comparing no pruning, sign-only pruning, and tau values 1e-6, 1e-4, and 1e-3. Measure SDP variable count, peak memory, solve time, solver failures, certified accuracy, and certificate margins. Success means at least 30% fewer variables and 1.5x lower verification time with unchanged certificates in exact mode; approximate mode should expose a measured, monotone loss in certified accuracy as tau increases.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: No measurable effect

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built a readable interval-bound ReLU pruning MVP with exact fixed-sign substitutions and optional contribution pruning. Across 32 seeded networks, exact sign pruning reduced the SDP-variable proxy from 44 to 22 on average (50%), with zero fixed-substitution error and no violations among 5,000 independent sampled outputs; tolerance pruning was monotone, reaching 58.9% average reduction at tau=1.0. The claimed soundness/dimension-reduction phenomenon is real in this toy setting, but no actual SDP solver speedup or CNN verification win was established.

Agent confidence: 8/10

Baseline: Mean proxy: 44 hidden-neuron variables; mean interval propagation time 0.000136 s; 0/5000 sampled soundness violations.
Idea: Exact sign: 22 variables mean, 50.0% reduction, 11 fixed-sign neurons, exact certificate equality in all 32 cases. tau=0.1: 21.94 variables, 50.14% reduction; tau=0.3: 21.69, 50.71%; tau=1.0: 18.06, 58.95%. Fixed substitutions had maximum error 0.0 and the 6,561-point grid had 0 interval violations.

Limitations: This is not an SDP implementation and uses a variable-count proxy rather than constructing or solving SDP constraints. It tests small randomly generated 2D MLPs, not MNIST/CIFAR CNNs; no peak memory, solver failures, certified accuracy, or verification-time speedup was measured. The approximate tau modes report pruning counts but do not compute a relaxed certificate or quantify certificate-quality loss.

How to run: python3 pruning_mvp.py && /home/maxwelhelp/main/bin/python3 mini_experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.03232) Sep 4, 2026

No significant difference vs. the tuned baseline (−-0.0%, p=1, wins 0 / 8 paired seeds).

Benchmark: Vision (image classification)
Model: cnn_small
Paired seeds: 8
Baseline mean: 0.8762
Idea mean: 0.8762
Effect (Δ): 0 (−-0.0%; negative = idea better)
Wins: 0 / 8 paired seeds
p-value: 1 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±0.0%
Mechanism: Confirmed ✓
Practical effect: No effect
Baseline tuning: swept over 3 configs

Limitations:

This stage-2 transfer test used the small 400-train/200-test vision subset and 3 epochs for runtime; it did not construct or solve an SDP, measure verifier wall-clock speed, peak SDP memory, solver failures, certified accuracy, or approximate tau certificate degradation. The fixed-sign signature measures interval classifications on trained CNN activations, not an actual SDP implementation.

How to run: python3 stage2_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 4, 2026 latest Failed ✗

Agent confidence: 9/10

Built a local stage-2 benchmark for the structurally matched vision/CNN track, using the canonical cnn_small architecture, paired seeds, equal learning-rate sweeps, and the standard CIFAR-10 subset error metric. Baseline and idea produced identical mean test error (0.87625), paired delta 0.0, and permutation p-value 1.0; therefore the idea did not improve neural-network training. The trained-model signature observed 54.24% fixed-sign ReLU instances with zero substitution error, but this inference-time property did not transfer into a task-metric gain.

Baseline: Best lr=0.001; full 8-seed mean err=0.8762499839, std=0.0248432582.
Idea: Best lr=0.001; full 8-seed mean err=0.8762499839, std=0.0248432582; paired delta=0.0; permutation p=1.0.
Mechanism signature: fixed_sign_fraction=0.5423773306, fixed_sign_mean=959721.5, unstable_mean=809750.5, total_relu_instances_mean=1769472.0, max_fixed_substitution_error=0.0, confirmed=true

Benchmark result