Certified Robustness via Randomized Smoothing

Randomized smoothing certifies predictions by majority vote over Gaussian-noised copies of the input: if the top class’s lower confidence bound pA_low exceeds 0.5, no ℓ2 perturbation smaller than σ·Φ⁻¹(pA_low) can change the vote, except with probability α. A 2022 diffusion-based pipeline certifies 71.1% of ImageNet images at ℓ2 radius 0.5.

That radius is small in the units most attacks use: on a 224×224 RGB image, ℓ2 radius 0.5 covers an ℓ∞ budget of only 0.33/255, against the 4/255 that RobustBench uses for ImageNet. The original setup also spent 100,100 forward passes per certified input, and the smoothed model abstains on part of its traffic.

How the certificate is built

The smoothed classifier g returns whichever class the base classifier f predicts most often under Gaussian noise:

g(x) = argmax_c P( f(x + ε) = c ),   ε ~ N(0, σ²I)

Cohen, Rosenfeld and Kolter proved that if the top class has probability at least pA_low and every other class at most pB_high, g returns the same class everywhere within ℓ2 distance R = σ/2 · (Φ⁻¹(pA_low) − Φ⁻¹(pB_high)) of x, where Φ⁻¹ is the inverse standard normal CDF.

A network’s class probabilities under noise cannot be computed exactly, so CERTIFY samples them: n0 noisy copies choose a candidate class, a separate batch of N copies counts how often it wins, and a one-sided Clopper-Pearson interval turns that count into pA_low. It then sets pB_high = 1 − pA_low, which reduces the radius to R = σ·Φ⁻¹(pA_low), and abstains when pA_low < 0.5. The paper uses n0 = 100, N = 100,000 and α = 0.001. The guarantee: with probability at least 1 − α over CERTIFY’s own sampling, if it returns a class and radius, g predicts that class everywhere inside the radius.

What the certificate does not say:

• It is pointwise. The radius belongs to one input; a neighbouring input can have a smaller radius or none.
• It covers g, not f. The base classifier alone is as attackable as before, and g is only as accurate as f is on noisy inputs, which is why Cohen et al. train f with Gaussian data augmentation at variance σ².
• It is in [0,1] pixel units. On the paper’s scale, an ℓ2 radius of 1.0 could change one pixel by 255, ten pixels by 80, 100 pixels by 25, or 1,000 pixels by 8.

CERTIFY and PREDICT in PyTorch

This condensed version of the locuslab/smoothing reference code batches the draws, so GPU memory rather than N sets the batch size. The model must accept [0,1] pixels and normalise internally, so noise and radius live in the same space.

import torch
from scipy.stats import binomtest, norm
from statsmodels.stats.proportion import proportion_confint

ABSTAIN = -1

def sample_counts(model, x, sigma, num, batch, num_classes):
    counts = torch.zeros(num_classes, dtype=torch.long)   # x: one input, shape (C, H, W)
    with torch.no_grad():
        while num > 0:
            b = min(batch, num)
            noisy = x.unsqueeze(0).repeat(b, 1, 1, 1)
            noisy = noisy + sigma * torch.randn_like(noisy)
            counts += torch.bincount(model(noisy).argmax(dim=1).cpu(), minlength=num_classes)
            num -= b
    return counts

def predict(model, x, sigma, n=1_000, alpha=0.001, batch=400, num_classes=1000):
    top2 = sample_counts(model, x, sigma, n, batch, num_classes).topk(2)
    n_a, n_b = top2.values.tolist()
    if binomtest(n_a, n_a + n_b, p=0.5).pvalue > alpha:
        return ABSTAIN
    return top2.indices[0].item()

def certify(model, x, sigma, n0=100, n=100_000, alpha=0.001, batch=400, num_classes=1000):
    c_a = sample_counts(model, x, sigma, n0, batch, num_classes).argmax().item()  # selection
    n_a = sample_counts(model, x, sigma, n, batch, num_classes)[c_a].item()       # fresh draws
    p_a_low = proportion_confint(n_a, n, alpha=2 * alpha, method="beta")[0]      # one-sided bound
    if p_a_low < 0.5:
        return ABSTAIN, 0.0
    return c_a, sigma * norm.ppf(p_a_low)                                         # pB_high = 1 - pA_low

Two details carry the guarantee. Selection and estimation must use independent draws; if the same noise both picks the class and vouches for it, the bound is biased upward. And alpha=2 * alpha is how the reference code gets a one-sided 1 − α bound from a two-sided routine. PREDICT is the cheap path: a two-sided binomial test of the top count against the runner-up, abstaining unless it rejects at level α. With probability at least 1 − α it abstains or returns g(x), but it gives no radius.

A worked CERTIFY example with real numbers

Take the paper’s settings (n0 = 100, N = 100,000, α = 0.001) and suppose class A, picked by the selection draws, wins 99,900 of the 100,000 estimation draws. The raw frequency is 0.999, but the certificate uses the one-sided 99.9% Clopper-Pearson lower bound, 0.99865, and Φ⁻¹(0.99865) ≈ 3.00. The certified radius is 3.00σ: 0.75 at σ = 0.25, 1.50 at σ = 0.50, 3.00 at σ = 1.00.

The first row is a hard ceiling. When every draw agrees, the Clopper-Pearson bound is α^(1/N), so no model, however stable under noise, certifies more than σ·Φ⁻¹(α^(1/N)). Cohen et al. give that formula and note that certifying 4σ at 99.9% confidence needs about 10⁵ samples. The ceiling rises slowly with the budget:

Each tenfold increase in forward passes buys less: +0.74σ from 1,000 to 10,000 draws, +0.61σ from 10,000 to 100,000. Published tables sit under these lines: Cohen’s σ = 0.25 ImageNet model certifies 0% at radius 1.0 and the σ = 0.50 model 0% at 2.0, and Carlini et al., at N = 10,000, report 0.0 at radius 1.0 for σ = 0.25. Certified accuracies computed at different N or α compare sampling budgets as well as models. Both tables follow from the formulas; this reproduces them:

from scipy.stats import norm
from statsmodels.stats.proportion import proportion_confint

N, alpha = 100_000, 0.001
for hits in (100_000, 99_900, 95_000):  # ceiling table: hits = N, vary N
    p_low = proportion_confint(hits, N, alpha=2 * alpha, method="beta")[0]
    print(hits, round(p_low, 5), [round(s * norm.ppf(p_low), 2) for s in (0.25, 0.5, 1.0)])

What a certificate costs per image

Every certified prediction runs the base model n0 + N times. Published wall-clock figures cover some settings; measure the rest.

The ImageNet figures work out to 1.1 to 1.5 ms per noisy ResNet-50 evaluation on Cohen et al.’s 2019 setup (110 s ÷ 100,100; 1.5 s ÷ 1,000), and cost grows linearly with N; a newer GPU changes the constant, not the shape. To fill the blank rows, time one batched forward pass and multiply by the batches CERTIFY needs:

import time, torch, torchvision

model = torchvision.models.resnet50().cuda().eval()  # weights do not change the timing
B = 400
x = torch.rand(B, 3, 224, 224, device="cuda")
with torch.no_grad():
    for _ in range(10):
        model(x)  # warm-up
    torch.cuda.synchronize()
    t0 = time.perf_counter()
    for _ in range(20):
        model(x)
    torch.cuda.synchronize()
t_batch = (time.perf_counter() - t0) / 20
for N in (1_000, 10_000, 100_000):
    batches = -(-100 // B) + -(-N // B)  # n0 = 100 draws, then N draws
    print(N, f"{batches * t_batch:.2f} s per certified image")

Record t_batch and the single-image latency (the same loop on x[:1]); their ratio to the three certified estimates is the number to bring to whoever owns the latency budget.

Denoised smoothing raises the per-draw cost. Carlini et al. run a 552M-parameter diffusion model and a 305M-parameter BEiT classifier on each of 10,000 draws per ImageNet input. On CIFAR-10 they report 825 images per second through the diffusion model and a ViT on an A100 at batch size 1,000, which puts a 100,000-draw certificate at about two minutes (100,000 ÷ 825 ≈ 121 s).

Published certified accuracy by σ, 2019 to 2022

Certified accuracy at radius r is the fraction of test images CERTIFY classifies correctly, without abstaining, at radius r or more; at r = 0 it is the smoothed classifier’s clean accuracy. Each cell lists σ = 0.25/0.50/1.00, so no row splices models and the zeros show the ceilings.

ImageNet, percent:

CIFAR-10, percent:

• Protocols differ. Cohen et al. and SmoothAdv certify 500 ImageNet images at N = 100,000; MACER certifies 500 images per dataset. Carlini et al. certify 1,000 random ImageNet images at N = 10,000, which lowers their ceilings to 0.80/1.60/3.20. At 500 images, a 50% estimate carries about 2.2 points of standard error.
• The σ mix-up. Cohen et al.’s headline Table 1 picks the best σ per radius: 49% at 0.5 (σ = 0.25, 67% clean), 37% at 1.0 (σ = 0.50, 57% clean). Quoting “67% clean, 49% at 0.5, 37% at 1.0” as one classifier splices two models. Table 1 also labels its 19%-at-2.0 row σ = 0.50, which the 1.91 ceiling rules out; the repository table and Carlini et al.’s comparison both put that 19% on σ = 1.00, at 44% clean.
• What moved the numbers. SmoothAdv and MACER, which train the base model for the smoothed classifier, added 7 to 8 points at ImageNet radius 0.5; the off-the-shelf diffusion denoiser added 14 more with no training.
• The gap is not a proven limit. Yang et al. show real image datasets are separated, so robustness and accuracy should both be achievable with locally Lipschitz classifiers.

Certified accuracy also counts an abstention as a miss, which hides how much traffic the model declines. Cohen et al.’s PREDICT on ImageNet at σ = 0.25 abstained on 12% of inputs with n = 100, 4% with n = 1,000 and 1% with n = 10,000. Measure it for your own model with the reference script, which writes one row per image (idx, label, predict, radius, correct, time) and marks abstentions as predict = -1:

python code/certify.py imagenet model_output_dir/checkpoint.pth.tar 0.25 cert_N10k --alpha 0.001 --N0 100 --N 10000 --skip 1000 --batch 400

import pandas as pd

df = pd.read_table("cert_N10k")
print("abstain", (df["predict"] == -1).mean(), "wrong", ((df["predict"] != -1) & (df["correct"] == 0)).mean())
print("seconds per image", pd.to_timedelta(df["time"]).dt.total_seconds().median())
for r in (0.0, 0.25, 0.5, 1.0):
    print(r, ((df["correct"] == 1) & (df["radius"] >= r)).mean())

--skip 1000 certifies every 1,000th test image, a tenth of the papers’ 500-image subsample; rerun with --N 1000 and --N 100000 to fill the cost table end to end.

ℓ2 certificates against ℓ∞ threat models

An ℓ∞ perturbation of size ε can have ℓ2 norm up to ε√d, where d is the number of input values, so an ℓ2 certificate of radius r covers ℓ∞ perturbations only up to r/√d. Salman et al. state this conversion and used it to report 68.2% certified accuracy at ℓ∞ 2/255 on CIFAR-10, from ℓ2 radius 0.435, against 63.8% for prior work. FGSM and PGD are run against per-pixel budgets like these, and RobustBench fixes them at 8/255 for CIFAR-10 and 4/255 for ImageNet:

CIFAR-10’s 1.74 sits inside the σ = 1.00 ceiling, but at radius 1.75 no entry in MACER’s CIFAR-10 table exceeds 23%. ImageNet’s 6.09 would need σ above 1.6 even at N = 100,000 (6.09 ÷ 3.81), and the published tables stop at σ = 1.00, where clean accuracy is already down to 44% (Cohen) or 60% (Carlini).

Changing the noise does not fix this. Kumar et al. prove that for a vast class of i.i.d. smoothing distributions the largest certifiable ℓp radius shrinks as O(1/d^(1/2 − 1/p)) for p > 2 (1/√d for ℓ∞), and that Gaussian smoothing is within a constant factor of the best for p ≥ 2. Blum et al. show any distribution certifying ℓp robustness for all base classifiers with p > 2 needs per-pixel noise variance growing as d^(1 − 2/p), so on large images “the required noise will eventually dominate the useful information”. Yang et al. reach a matching barrier while improving ℓ1 certificates with noise shaped to the norm.

Smoothing vs IBP, α,β-CROWN and Lipschitz networks

Read it as a set of exclusions. None of these published operating points certifies ℓ∞ on full-resolution ImageNet; IBP-family training certifies ℓ∞ natively but only up to downscaled ImageNet. Among these methods, a deterministic ImageNet certificate means a Lipschitz network at about a quarter of the radius smoothing reaches. Smoothing is the only entry that certifies large, even off-the-shelf, architectures at ℓ2 radius 0.5 and beyond, and the only one whose certificates can be wrong by design.

Certified versus empirical robustness

Empirical defenses such as TRADES, MART and PGD adversarial training often report higher robust accuracy than smoothing certifies at the same budget, but only against the attacks that were run; Athalye, Carlini and Wagner broke a series of published defenses with adaptive attacks their authors had not tried. A certificate cannot be lowered by a stronger attack inside its ball. When a certified number goes into a contract, a regulatory filing or a benchmark, state its norm, radius, σ, N, α and test subset with it; without them it cannot be checked.

Choosing a method: four questions and a worked scenario

Answer these in order; the first one that fails decides.

1. Threat norm. For an ℓ∞ requirement ε, compute ε√d. If it exceeds σ·Φ⁻¹(α^(1/N)) at the largest σ whose clean accuracy you can accept, smoothing cannot certify it: use IBP-family certified training if the model is small enough, otherwise adversarial training checked with adaptive attacks as in evaluating robustness without fooling yourself.
2. Required radius r. Start at σ ≈ r/2 (every ImageNet row above has its best σ for radii 0.5, 1.0 and 2.0 at 0.25, 0.50 and 1.00) and confirm that the ceiling for your N clears r. At about 0.14 or below, if certificates must be deterministic and cost one forward pass, a Lipschitz network competes.
3. Forward-pass budget. Divide the per-request latency budget by the measured per-draw time. If n0 + N fits, certify online; if only PREDICT fits, serve PREDICT and run CERTIFY offline on an audit sample; if not even 100 draws fit, smoothing is out.
4. Abstention budget. Measure the abstention rate at the deployed σ and n, and give each abstention a route: a fallback model, a review queue or a refusal. A model that abstains on a fifth of traffic is a routing problem, not a drop-in replacement.

Worked scenario. An ImageNet-resolution classifier serves an API with a 250 ms per-request budget on one GPU. A contract requires a certified ℓ2 radius of 0.5 on an audit set, and the review team can absorb 5% of requests.

• Norm: ℓ2, so smoothing is eligible. Had the contract said ℓ∞ 4/255, the analysis would stop here at adversarial training, since 6.09 is out of reach.
• Radius: σ = 0.25, ceiling 0.95 at N = 100,000. The Lipschitz point (0.14) falls short, and no IBP or α,β-CROWN entry covers full-resolution ImageNet, so smoothing is the only candidate.
• Budget: at Cohen et al.’s 2019 rate of about 1.5 ms per draw, 250 ms buys about 160 draws. PREDICT with n = 100 fits (0.15 s); CERTIFY at N = 100,000 (110 to 150 s) does not. So PREDICT runs online and CERTIFY offline on the audit set, where Cohen’s σ = 0.25 model certifies 49% at 0.5 and MACER’s 57%.
• Abstention: at n = 100 and σ = 0.25, Cohen et al. measured 12%, more than twice what review can take. n = 1,000 brings it to 4% but took 1.5 s, six times the budget.

Decision: smoothing, conditional on one measurement. If the timing script shows 0.25 ms per draw or better, PREDICT with n = 1,000 fits in 250 ms and the system ships with a 4% review queue and an offline certificate. If not, the contract cannot be met as written: renegotiate the abstention budget, or drop the certificate and ship an adversarially trained model with an honest empirical evaluation.

Known limits since 2019

ℓ∞ hits a dimensionality wall. The Kumar, Blum and Yang results above mean no choice of noise rescues ℓ∞ certificates on full-resolution images.

Certificates are probabilistic. Each may be wrong with probability α. Hu et al. cite that false-positive rate, around 0.1%, together with the 100,000 extra inferences per input, as the case for deterministic Lipschitz certificates wherever their radii suffice.

Floating point breaks soundness. Voráček and Hein built a simple case where smoothing certifies radius 1.26 around a point with an adversarial example at distance 0.8, extended it to false certificates on CIFAR-10, and proposed a sound variant that runs at essentially the same speed.

The noise source is an attack surface. Dahiya, Shumailov and Anderson backdoored the random number generator and made smoothing falsely certify over- or underestimates of robustness by up to 81 times, and the randomness tests NIST suggests did not detect it. Pin and audit the RNG like any other security dependency.

Certificates can be spoofed. The Shadow Attack of Ghiasi, Shafahi and Goldstein applies large, inconspicuous perturbations that push an image far from the class boundary, so a certified classifier mislabels it and still issues a robustness certificate. A radius says the prediction is stable near this input, not that the input is clean.

Beyond ℓp balls. Fischer, Baader and Vechev certify rotations and translations by smoothing in parameter space. TSS covers Gaussian blur, rotation and more than ten other semantic transformations, with 30.4% certified accuracy against rotations within ±30° on ImageNet. Levine and Feizi de-randomize smoothing for patch attacks, reaching about 57.6% certified accuracy against 5×5 patches on CIFAR-10 at 83.8% clean, against 30.3% for an earlier IBP-based method. Smoothing has also been carried to text classifiers, where the perturbation set is a list of edits rather than a ball. Each certificate covers only its own family, which leaves unforeseen attacks and multimodal targets such as vision-language models outside every guarantee listed here.

FAQ

does randomized smoothing protect against l-infinity attacks?

Only weakly. An ℓ2 certificate of radius r implies ℓ∞ robustness of just r/√d, so on 224×224 RGB images a radius of 1.0 covers about 0.66/255 per pixel. Kumar et al. and Blum et al. prove that changing the noise distribution cannot escape this scaling on high-dimensional inputs, so ℓ∞ needs another method.

how many samples does randomized smoothing need?

Cohen et al. used 100 selection draws plus 100,000 estimation draws per certified input at α = 0.001, capping the radius at 3.81σ. At 10,000 draws the cap is 3.20σ; at 1,000 it is 2.46σ. PREDICT, which returns no radius, ran with 100 to 10,000 draws on ImageNet.

can i use randomized smoothing with a pretrained model?

Yes, with a denoiser in front of it. A classifier trained on clean images never sees noise, which is why Cohen et al. train with Gaussian augmentation at the smoothing σ. Carlini et al. instead denoise each noisy copy with an off-the-shelf diffusion model, certifying 71.1% of ImageNet at ℓ2 radius 0.5 without fine-tuning.

can a randomized smoothing certificate be wrong?

Yes, in three documented ways. Each certificate may fail with probability α, typically 0.001. Floating-point rounding can produce false certificates, which Voráček and Hein demonstrated on CIFAR-10. A backdoored random number generator can inflate or shrink radii by up to 81 times, and NIST’s suggested randomness tests did not catch it.