A certified defense against data poisoning gives a mathematical guarantee that a model's prediction stays the same even if an attacker inserts, deletes, or relabels some number of training examples. The most practical guarantees come from partition-and-vote ensembles. The training set is split by a fixed hash into $k$ disjoint pieces, a separate small classifier is trained on each piece, and the final answer is a plurality vote. One bad training point can touch at most one piece, so it can flip at most one vote. A wide vote margin therefore proves robustness without sampling noise and without any probability of failure. The weak point is that each classifier sees only $1/k$ of the data. Every published system nonetheless drops in an architecture built for full datasets, such as a standard ResNet, and copies it $k$ times. Nobody has searched for the network that works best when trained on a sliver of data. The reason is cost: with $k$ between 50 and 1,000, scoring one candidate architecture honestly means training the entire ensemble.
This note proposes to make that search affordable. The certificate depends only on how base-model votes are distributed at each test point. Hash partitions are exchangeable, meaning no piece is systematically different from another. That distribution can therefore be estimated by training a handful of base models, perhaps 8 to 16, instead of all $k$. From those few models we can predict the certified-accuracy curve of the full ensemble, for any $k$, before building it. Plugged into ordinary architecture search, this estimator lets us choose the architecture and the partition count together. The deployed ensemble is then trained in full and certified exactly. The estimator guides the search but never enters the guarantee.
Core Claim
The certified poisoning size of a partition ensemble can be predicted from $m \ll k$ sampled base models with quantifiable error. Searching architectures with this predictor will find base learners that certify substantially more poisoning than the standard backbones used in Deep Partition Aggregation (DPA) and Finite Aggregation (FA), at a search cost of a few times one ensemble training rather than hundreds.
The second, more scientific claim is that what matters for certification is per-example vote agreement, not mean base-model accuracy. Two architectures with equal average accuracy on a $1/k$ slice can certify very differently, depending on whether their errors concentrate on the same test points. If that claim fails, the simpler method of ranking by single-model accuracy wins, and the experiments are designed to show this either way.
Research Program
The estimator. For a test point $x$ and candidate architecture $a$, let $p_c(x)$ be the probability that a base model trained on a random $1/k$ slice predicts class $c$. We estimate $\hat p_c(x)$ from the predictions of $m$ base models trained on $m$ distinct slices. We then model the $k$ votes as a multinomial draw with these probabilities. DPA certifies $x$ against $B$ poisoned points when the margin satisfies $B < \lceil (n_1 - n_2)/2 \rceil$, where $n_1$ and $n_2$ are the top and runner-up vote counts. The predicted certified accuracy at budget $B$ is
$$\widehat{\mathrm{CA}}_k(a,B) = \frac{1}{|T|}\sum_{x \in T} \Pr_{n \sim \mathrm{Mult}(k,\hat p(x))}\big[\, y_x \text{ wins and } n_1 - n_2 > 2B \,\big],$$
where $T$ is a held-out validation set and $y_x$ is the true label. The probability is computed by Monte Carlo over vote vectors. That simulation is cheap arithmetic, not model training. It also has no bearing on the final certificate.
Because $\hat p$ comes from $m$ models, its per-point error scales like $\sqrt{p(1-p)/m}$, the ordinary binomial standard error. We will report bootstrap intervals over the $m$ models and test empirically how small $m$ can be before candidate rankings degrade.
The base-model probability $p_c(x)$ depends on slice size $|D|/k$. To evaluate other values of $k$ without retraining, we fit the estimate at two or three slice sizes and interpolate.
FA's overlapping split-and-spread scheme makes votes correlated by design. For FA we will therefore check the estimator against FA's exact certificate rather than assume the independent-vote model carries over.
The search. The candidate pool combines NAS-Bench-201 cells with a small hand-built macro space. The macro space varies width, depth, normalization type, and residual connections, since the low-data regime may favor shallower and narrower networks than full-data search spaces do.
Search is regularized evolution scored by $\widehat{\mathrm{CA}}$ at a target budget $B$. It uses budgeted training of each of the $m$ base models, with the budget chosen by the rank-preserving procedure of Rethinking Performance Estimation in Neural Architecture Search. That paper prunes training budgets while preserving rank correlation with fully trained models. We adopt its method for the inner loop, not as our contribution.
Partition count $k$ is searched jointly with the architecture, since the best architecture should shift with slice size. Training on a $1/k$ slice is itself cheap, so each candidate costs roughly $m/k$ of one full ensemble.
The analysis. For every evaluated candidate we record mean base accuracy, per-point vote entropy, and pairwise error correlation across the $m$ models. This lets us test whether agreement adds predictive power beyond accuracy. It is the mechanism-level question that decides whether the method is needed at all.
Baselines
The do-nothing reference is DPA as published: the paper's standard backbone, replicated across $k$ hash partitions, with the paper's $k$. Deep Partition Aggregation reports a median certified robustness, the number of insertions certified for 50% of the test set, of 9 on CIFAR-10, 20 on GTSRB, and more than 500 on MNIST. We re-run it with our training recipe so that recipe differences are not credited to search. To beat it, we must exceed this median certified size at the same $k$ and the same data, and also dominate its full certified-accuracy-versus-$B$ curve.
The strongest existing method is FA (Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation), which tightens DPA's certificate through overlapping partitions. It reports certified-fraction gains over DPA of up to 3.87% on CIFAR-10, 4.77% on GTSRB, and 3.05% on MNIST. Because architecture choice and aggregation scheme are orthogonal, we compare against it two ways. First, does searched-architecture DPA beat standard-backbone FA? Second, does searched-architecture FA beat standard-backbone FA? Improving on FA by more than FA improved on DPA, at equal deployed compute, would count as a clear win.
A strong tuned baseline gives the standard backbone a hyperparameter sweep at $1/k$ data size, covering augmentation, learning rate, and weight decay, with the same total GPU budget our search uses. This separates "the architecture matters" from "someone finally tuned for small slices."
The key ablation keeps the identical search but scores candidates by the mean accuracy of the $m$ base models. That score discards the per-point vote structure. A second ablation searches only over $k$ with the architecture fixed. All search methods share the same candidate pool, training budget per base model, and wall-clock cap, and all report search cost in GPU days alongside the final exact certificates.
Why not just…?
Why not just rank candidates by single-model accuracy on one slice? This is the real threat. If base models fail independently given the test point, accuracy and margin move together and the vote-distribution estimator adds nothing. The literature hints otherwise: Jie Shi et al. argue that diversity and per-model sample efficiency matter more than ensemble size. That evidence is indirect. The accuracy-only ablation settles it directly. If Kendall's tau between accuracy-only scores and exact certified accuracy matches our estimator's tau, we will report that and recommend the cheaper method.
Why not just use an existing zero-cost proxy such as EZNAS or a few-shot proxy? These proxies score networks at initialization, before any training. EZNAS evolves proxies for full-data clean accuracy and reaches a Kendall tau of 0.65 on NAS-Bench-201, but it struggles within the top 10% of architectures. Zero-cost Proxy for Adversarial Robustness Evaluation shows that standard proxies correlate near zero with empirical robustness, while its own proxy reaches only 0.33 on Tiny-RobustBench. IBFS targets few-shot meta-learning, which differs from training a model from scratch on a data slice. None of these papers reports correlation with certified poisoning size. We will include EZNAS-A, NASWOT, and IBFS as search scorers and measure their correlation directly.
Why not just increase $k$? Hongwei Zhang et al. report diminishing returns as ensembles grow. DPA itself notes that base models collapse from data starvation when $k$ is too large. The $k$-only ablation measures how much of our gain is recoverable without changing the architecture.
Why not just use randomized smoothing? Smoothing replaces the exact guarantee with a probabilistic one. On MNIST 1/7, Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks reports bagging retaining 91.1% certified accuracy with 100 poisoned examples, where the compared smoothing defense's certified accuracy fell off with larger attacks. We stay within deterministic certification.
Why not a differentiable relaxation in the style of DSRNA? DSRNA makes test-time interval-bound certificates differentiable for a single network. A vote margin over $k$ separately trained models has no comparable gradient, and a shared supernetwork would leak poisoned data across partitions. That leak breaks the certificate. Our sampling approach avoids both problems.
Proposed Experiments
The first decisive check validates the estimator before any search. On CIFAR-10 and GTSRB, at DPA's published $k$, we fully train ensembles for about 30 diverse architectures. We then measure the absolute error of $\widehat{\mathrm{CA}}_k(a,B)$ against the exact certified accuracy at several budgets $B$, and the Kendall tau of the ranking, for $m \in \{4, 8, 16, 32\}$. Success means tau of at least 0.8 at $m=16$ and clearly above the accuracy-only score and the zero-cost proxies. We also test transfer across $k$ by fitting at small $k$ and predicting larger $k$. For FA we compare predictions against FA's exact certificate.
The second experiment runs the search on CIFAR-10, GTSRB, and MNIST. We report the exact DPA and FA certificates of the deployed ensembles against the baselines above, together with the search cost in GPU days. We also compare against the published DPA medians of 9, 20, and 500+ insertions, and against the reported FA gains, noting where our re-runs differ from published numbers.
The third experiment is the mechanism analysis. We regress exact certified accuracy on mean accuracy and on error correlation across the evaluated architectures, and we examine which architectural traits win at small slice sizes. Depth, width, and residual connections are of particular interest. Exact Certification of (Graph) Neural Networks Against Label Poisoning found that greater depth reduces certified robustness in the infinite-width graph setting, and we will check whether that holds for finite image classifiers inside partition ensembles. A negative result on this point is itself informative.
References
- Deep Partition Aggregation: Provable Defenses against General Poisoning Attacks
- Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation
- Rethinking Performance Estimation in Neural Architecture Search
- Where Does the Robustness Come from?: A Study of the Transformation-based Ensemble Defence
- EZNAS: Evolving Zero-Cost Proxies For Neural Architecture Scoring
- Zero-cost Proxy for Adversarial Robustness Evaluation
- Revisiting Neural Networks for Few-Shot Learning: A Zero-Cost NAS Perspective
- Defending Adversarial Examples by Negative Correlation Ensemble
- Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks
- DSRNA: Differentiable Search of Robust Neural Architectures
- Exact Certification of (Graph) Neural Networks Against Label Poisoning