Verifying the local robustness of neural networks under ℓ0 perturbations is inherently combinatorial, as it must reason over all sparse subsets of ε perturbed pixels. This paper presents FocusBranch, a combinatorial branch-and-bound framework for ℓ0 robustness verification. The key insight is to make the ℓ0-ball decomposable and branchable using a node abstraction, which consists of a focus pixel set S and a level l, permitting at most ε−l pixels outside S. This abstraction unifies two branching mechanisms: concrete nodes branch through upper shadows to fix additional perturbed locations, while super nodes branch through covering designs to cover many perturbation cases with fewer child nodes. FocusBranch proves node safety by concretizing linear relaxations over node-constrained ℓ0-balls and recursively branches on unknown nodes. Rather than relying on a fixed verification plan, it samples nodes across levels to estimate safe rates and costs, then selects a starting level and branching strategy predicted to minimize verification time. Experiments on fully connected and convolutional classifiers for MNIST, Fashion-MNIST, and CIFAR-10 show that FocusBranch verifies ℓ0 robustness effectively across architectures and outperforms state-of-the-art verifiers. The code is available at: https://github.com/simpl-group/FocusBranch.
Figures & tables
Figure 1: Overview of FocusBranch . After choosing ls and R(ls) by sampling, FocusBranch runs branch-and-bound over node-constrained ℓ0 -balls, branching via covering designs (super node) or upper shadows (concrete node). Unknown, unbranchable nodes fall back to MILP.
Figure 2: (a) A node o admits at most ϵ−o.l perturbed pixels (dots) outside o.S (purple). (b) Every 2-subset of o.S lies in some child. (c) Each child adds one pixel v∈/o.S (orange).
Figure 3: Closed-form node bound with illustrative contributions Δv . The node bound takes P∪Q , whereas the full ℓ0 -ball takes the top- ϵ pixels {2,4,5,6} , so the node bound is tighter.
Dataset
Network
Neurons
Img
CC
ϵ
Cand.
FocusBranch
CoVerD + top - t - GP
R ↑
R/Cand. ↑
Time (s) ↓
R ↑
R/Cand. ↑
Time (s) ↓
MNIST
afc1
512
100
100
3
90
90
100.0%
0.3
90
100.0%
26.6
4
72
70
97.2%
10.1
67
93.1%
165.7
5
57
52
91.2%
17.8
30
52.6%
203.3
6
46
29
63.0%
53.7
13
28.3%
257.1
afc2
1024
100
100
3
94
94
100.0%
0.3
94
100.0%
37.2
Table 1: Main evaluation results. Neurons is the number of neurons in the network, Img is the number of evaluated images, and CC is the number of correctly classified images. Cand. denotes the number of verification candidate instances at the target budget ϵ , after excluding images for which an adversarial example within the budget is already known. R is the number of verified images, R/Cand is the verified rate, and Time reports the mean verification time (in seconds) over each tool’s verified instances. Refer to Figures 4 , 7 and 8 for sample-wise comparison.
Figure 4: Comparison between FocusBranch , CoVerD and CoVerD + top - t - GP at ϵ=5 .
Figure 5: Ablation study on afc5 at ϵ=5 . “w/o policy 1” disables super-node branching by always starting from Θ0 , while “w/o policy 2” disables concrete-node branching by always starting from Θϵ .
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Network
Neurons
Img
CC
ϵ
Cand.
R
T/O
R/Cand.(%)
Time (s)
ls<ϵ
\textscBranchcon
ls=ϵ
MNIST
afc1
512
100
100
3
90
90
0
100.0%
0.3
90
21
0
4
72
70
2
97.2%
10.1
69
28
1
5
57
52
5
91.2%
17.8
52
30
0
6
46
29
17
63.0%
53.7
28
22
1
afc2
1024
100
100
3
94
94
0
100.0%
0.3
94
14
0
4
88
87
1
98.9%
6.1
87
36
0
Appendix
Table 2: Main results of FocusBranch on pixel-wise ℓ0 robustness verification. For each benchmark and perturbation budget ϵ , we report the number of correctly classified images, candidate instances, verified instances, timed out instances, mean runtime on verified instances, starting level statistics and number of instances where concrete branching applied.
Figure 6: Qualitative examples. Each pair shows a correctly classified image that FocusBranch verifies at budget ϵ (left), and an adversarial example at budget ϵ+1 with the perturbed pixels marked in red (right).
Figure 7: Comparison between FocusBranch , CoVerD and CoVerD + top - t - GP at ϵ=3 .
Figure 8: Comparison between FocusBranch , CoVerD and CoVerD + top - t - GP at ϵ=4 .
Figure 9: Comparison between FocusBranch , CoVerD and CoVerD + top - t - GP at ϵ=6 .
Dataset
Network
Method
0
1
2
3
4
5
6
7
8
9
MNIST
bcv4
CoVerD + top - t - GP
1286.4
1008.5
T/O
1002.5
1397.5
T/O
1248.2
905.5
-
784.9
FocusBranch
554.2
448.3
T/O
367.6
611.0
3145.6
557.1
363.3
-
299.0
CIFAR-10
bcv5
CoVerD + top - t - GP ∗
1608.0
1540.0
1698.0
-
-
T/O
-
T/O
-
-
FocusBranch
132.3
133.2
141.6
-
-
801.1
-
T/O
-
-
Appendix
Table 3: Sample-wise comparison between FocusBranch and CoVerD + top - t - GP on bcv4 and bcv5. Those incorrectly classified images and images containing adversarial examples within the perturbation budget are marked “-” in the table. The timeout for bcv4 is 3600s and for bcv5 is 1800s. ∗ As we failed to run CoVerD + top - t - GP on bcv5 with 50 MILP instances on our machine, this row is taken from the results table in [ 42 ] directly, and thus it is not directly comparable.
Method
#Verified
Average Time (s)
MILP
1245
58.7
FocusBranch FC
1599
44.6
FocusBranch all
2799
67.7
Appendix
Table 4: Comparison between FocusBranch and an MILP solution that aggregates ϵ∈{3,4,5,6} . FocusBranch FC denotes our results aggregating across all fully connected networks while FocusBranch all denotes our results aggregating across architectures.
Figure 10: Sample-wise ablation study on afc5 at ϵ=5 .
Figure 11: Ablation study on fully connected instances at ϵ∈{5,6} .
Dataset
Network
Neurons
Img
CC
ϵ
Cand.
FocusBranch
CoVerD + top - t - GP
Speedup ↑
R↑
R/Cand. ↑
Time (s) ↓
R↑
R/Cand. ↑
Time (s) ↓
MNIST
afc1
512
100
100
5
57
38
66.7%
275.0
26
45.6%
116.4
4.7 ×
6
46
20
43.5%
136.8
10
21.7%
378.0
5.1 ×
afc2
1024
100
100
5
79
37
46.8%
124.2
28
35.4%
264.9
5.7 ×
6
68
20
29.4%
211.8
13
19.1%
649.0
16.7 ×
afc3
1536
100
100
5
74
39
52.7%
103.5
32
43.2%
475.8
5.4 ×
Appendix
Table 5: Main results without parallelization on a single GPU at ϵ∈{5,6} , except for bcv4 and bcv5 at ϵ=3 . Neurons is the number of neurons in the network, Img is the number of evaluated images, and CC is the number of correctly classified images. Cand. denotes the number of verification candidate instances at the target budget ϵ , after excluding images for which an adversarial example within the budget is already known (from any run, including the 4-GPU main results, so Cand. is the same as there). R is the number of verified images, R/Cand is the verified rate, and Time reports the mean verification time (in seconds) over each tool’s verified instances. Speedup is how many times faster FocusBranch is than CoVerD + top - t - GP (geometric mean over the instances verified by both tools).
ϵ
Verified
Instances invoking MILP
Share
3
952
57
6.0%
4
839
85
10.1%
5
641
54
8.4%
6
367
10
2.7%
All
2799
206
7.4%
Appendix
Table 6: Share of verified instances that invoke the MILP solver at least once.