# Sound active-neuron pruning for SDP verification

- ID: 391
- Canonical URL: https://synthcore.org/idea/391/sound-active-neuron-pruning-for-sdp-verification
- API JSON: https://synthcore.org/api/idea/391.json
- API Markdown: https://synthcore.org/api/idea/391.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.03232](https://arxiv.org/abs/2607.03232)
- Category: optimization
- Solves: speedup, scalability, memory
- ML areas: training, regularization, inference-speedup, memory
- Math tags: optimization, convex-analysis, linear-algebra
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## 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.

## 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.

## Key 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.$$

## 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

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: 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.

### Mechanism check

- Verdict: 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.
- Confidence: 8/10
- 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.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 1
- Paired wins: 0/8
- Benchmark verdict: no measurable effect

## Artifacts

- [bench_report.json](https://synthcore.org/code/1284/bench_report.json)
- [mini_experiment.py](https://synthcore.org/code/1284/mini_experiment.py)
- [pruning_mvp.py](https://synthcore.org/code/1284/pruning_mvp.py)
- [report.md](https://synthcore.org/code/1284/report.md)
- [report_bench_2026-09-04T114047.md](https://synthcore.org/code/1284/report_bench_2026-09-04T114047.md)
- [results.json](https://synthcore.org/code/1284/results.json)
- [stage2_bench.py](https://synthcore.org/code/1284/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/1284)

## Disclaimer

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