Laplace-Bridged Randomized Smoothing for Fast Certified Robustness

Daniel Takabi; Feng Yu; MD Saifur Rahman Mazumder; Miao Lin; Rui Ning

arxiv: 2604.24993 · v1 · submitted 2026-04-27 · 💻 cs.LG

Laplace-Bridged Randomized Smoothing for Fast Certified Robustness

Miao Lin , MD Saifur Rahman Mazumder , Feng Yu , Daniel Takabi , Rui Ning This is my paper

Pith reviewed 2026-05-08 03:42 UTC · model grok-4.3

classification 💻 cs.LG

keywords randomized smoothingcertified robustnessLaplace approximationadversarial robustnessedge computinganalytic methodsmachine learning

0 comments

The pith

Laplace-Bridged Smoothing replaces Monte Carlo sampling in randomized smoothing with an analytic Laplace bridge to achieve faster certified robustness.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Randomized smoothing can certify that classifiers resist small adversarial changes but requires many noisy evaluations and often special training. Laplace-Bridged Smoothing introduces an analytic Laplace bridge to handle the certification in a simpler probability space instead of repeated sampling. This keeps the formal guarantees the same but avoids extra training and speeds up the process greatly. On standard datasets it provides better certified results at lower cost, and on small devices it runs hundreds of times faster.

Core claim

The paper establishes Laplace-Bridged Smoothing as an analytic reformulation of randomized smoothing. It replaces high-dimensional Monte Carlo sampling with efficient low-dimensional probability space computations via a Laplace bridge. This preserves formal robustness guarantees without noise-augmented training and reduces the certification burden, leading to stronger certified robustness on CIFAR-10 and ImageNet with nearly an order of magnitude lower per-sample costs, and speedups up to 494 times on edge devices like NVIDIA Jetson Orin Nano and Raspberry Pi 4, with theoretical justification provided for the formulation and validity.

What carries the argument

The Laplace bridge as an analytic approximation that enables the shift from high-dimensional input sampling to low-dimensional probability computations while preserving certificate validity.

If this is right

Stronger certified robustness than standard randomized smoothing on CIFAR-10 and ImageNet.
Certification cost per sample reduced by nearly an order of magnitude.
Speedups of up to 494 times on NVIDIA Jetson Orin Nano and Raspberry Pi 4.
Certified robustness deployment made practical on edge devices without noise-augmented training.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The efficiency gains could support real-time robustness verification in deployed systems.
Similar analytic bridges might apply to other Monte Carlo based certification methods.
Further study of the approximation could enable extensions to additional noise distributions.

Load-bearing premise

The Laplace bridge gives a close enough analytic stand-in for the many random noisy checks used in standard randomized smoothing, and this stand-in keeps the robustness certificates mathematically valid.

What would settle it

If tests reveal that LBS-certified models can be fooled by attacks within the certified distance, or if LBS radii are consistently smaller than those from full Monte Carlo on the same inputs.

Figures

Figures reproduced from arXiv: 2604.24993 by Daniel Takabi, Feng Yu, MD Saifur Rahman Mazumder, Miao Lin, Rui Ning.

**Figure 1.** Figure 1: Certified accuracy of RS (Cohen et al., 2019) on CIFAR10 (left) and ImageNet (right) under different Gaussian perturbation levels σ (Solid lines: standard, non-noise-augmented training; dashed lines: standard, noise-augmented training). Computational limitation. Another major drawback of RS is that, for neural network base classifiers, the class probabilities cannot be computed in closed form. Consequen… view at source ↗

**Figure 2.** Figure 2: Overview of RS and LBS. RS: Certification is performed by repeatedly adding high-dimensional noise to the input and running the base classifier multiple times, relying on repeated noisy forward passes to estimate class probabilities. LBS: Certification first computes logits from a single forward pass of the base classifier, then applies a LB approximation and performs lowdimensional Dirichlet sampling, … view at source ↗

**Figure 3.** Figure 3: Certified accuracy of LBS on CIFAR10 (left) and ImageNet (right) under different perturbation levels σ with N =100,000, η = 0.001 (top), various Dirichlet sample size N with σ = 0.25, η = 0.001 (middle) and confidence levels η with σ = 0.25, N =100,000 (bottom). 5.1. LBS Certification view at source ↗

**Figure 4.** Figure 4: Certified accuracy of LBS on the NVIDIA Jetson Orin Nano (left) and the Raspberry Pi 4 (right) using a SqueezeNetbased classifier on CIFAR-10 under different perturbation levels σ, with N = 100,000 and η = 0.001. Jetson Orin Nano Raspberry Pi 4 ResNet110 SqueezeNet SqueezeNet ShuffleNet RS 91.8 33.3 690.9 240.2 LBS 2.8 1.2 1.4 0.9 Speedup 33× 28× 494× 267× view at source ↗

**Figure 5.** Figure 5: Certified accuracy of LBS on CIFAR-10 (top row) and ImageNet (bottom row). Left: with the different perturbation levels σ and N = 10,0000, η =0.001. Middle: with the different number of samples N and σ = 0.25, η =0.001. Right: with the different confidence levels η and N =100,000, σ = 0.25. We evaluate the robustness of LBS under an ℓ∞ adversarial threat model. Given a lower bound pA on the smoothed class … view at source ↗

**Figure 6.** Figure 6: and view at source ↗

**Figure 7.** Figure 7: Certified accuracy of LBS on CIFAR-10. Left: varying σ, with N = 100,000 and η = 0.001. Middle: varying N, with σ = 0.25 and η = 0.001. Right: varying η, with N = 100,000 and σ = 0.25. A.6. On-device LBS Certification In Section 5.3, we conduct experiments on two representative on-device platforms with different computational profiles: an NVIDIA Jetson Orin Nano and a Raspberry Pi 4. The Jetson Orin Nano r… view at source ↗

**Figure 8.** Figure 8: reports the certified accuracy of LBS (SqueezeNet backbone) on two on-device platforms, with the left columns corresponding to NVIDIA Jetson Orin Nano and the right columns to Raspberry Pi 4. Across both devices, increasing the number of samples N improves certified accuracy, with diminishing returns beyond N=10,000, while smaller values of η produce more conservative but stable certificates. These trends … view at source ↗

**Figure 9.** Figure 9: Certified accuracy of LBS on CIFAR-10 on two edge platforms under ℓ∞ perturbation, with radius scaled by ×255. Left two columns: NVIDIA Jetson Orin Nano; right two columns: Raspberry Pi 4. For each platform, the left panel varies σ with fixed N = 100,000 on Jetson and 10,000 on Pi; the right panel varies N with fixed σ = 0.25. ℓ1 radius → 0.5 1.0 1.5 2.0 2.5 3.0 Jetson Orin Nano 83.8 80.1 79.1 77.0 76.2 75… view at source ↗

read the original abstract

Randomized Smoothing (RS) offers formal $\ell_2$ guarantees for arbitrary base classifiers but faces two key practical bottlenecks: (i) it often relies on noise-augmented training to achieve nontrivial certificates, which increases training cost, can reduce clean accuracy, and weakens RS as a genuinely post-hoc defense; and (ii) certification is computationally expensive, typically requiring tens of thousands of noisy forward passes per input, which hinders deployment, especially on resource-constrained edge devices. To address both limitations, we propose Laplace-Bridged Smoothing (LBS), an analytic reformulation of RS that replaces high-dimensional input-space Monte Carlo (MC) sampling with efficient computations in a low-dimensional probability space. LBS preserves formal robustness guarantees without requiring noise-augmented training while substantially reducing certification burden. On CIFAR-10 and ImageNet, LBS attains stronger certified robustness than RS and reduces per-sample certification cost by nearly an order of magnitude. Notably, on NVIDIA Jetson Orin Nano and Raspberry Pi 4, LBS achieves speedups of up to $494\times$, enabling practical certified deployment on real-world edge devices. Finally, we provide theoretical justification for the analytic formulation and certificate validity of LBS.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

LBS replaces Monte Carlo sampling in randomized smoothing with a Laplace approximation in probability space, delivering big speedups on edge hardware while claiming to keep the formal ℓ2 guarantees.

read the letter

The main thing to know is that this paper replaces the usual high-dimensional Monte Carlo sampling in randomized smoothing with an analytic Laplace-bridged computation in probability space. That change lets them certify without noise-augmented training and cuts per-sample cost by roughly an order of magnitude, with reported speedups up to 494× on Jetson Orin Nano and Raspberry Pi 4. On CIFAR-10 and ImageNet they also report stronger certified radii than standard RS under the same base classifiers. Those practical numbers on real edge devices are the clearest win here; anyone who has tried to run RS on constrained hardware will see the appeal immediately. The authors also avoid the accuracy drop that often comes with noise-augmented training, which is another practical plus. The derivation itself is presented as a direct reformulation rather than a learned surrogate, so there is no obvious circularity in the certificate formula. The soft spot is exactly where the stress-test note points: the Laplace bridge is an approximation, and the formal ℓ2 radius only stays valid if the computed p_A is a valid lower bound on the true smoothed probability. If the approximation can overestimate p_A or underestimate the gap to the runner-up, the derived radius becomes unsound. The abstract states they supply theoretical justification for certificate validity, but the letter would need to see the precise error bounds or one-sided guarantee in the full derivation to be convinced the approximation never goes the wrong way. Minor additional questions are whether the reported robustness gains hold under the same number of effective samples and whether they verified the certificates against actual adversarial examples inside the claimed radii. This work is aimed at researchers and practitioners who want certified robustness on edge devices without retraining. If the soundness argument holds up under review, it is worth citing for the deployment angle; otherwise the speed claim is still interesting but the guarantee is not. I would send it to peer review so a referee can check the derivation and the direction of the approximation error in detail.

Referee Report

2 major / 2 minor

Summary. The paper proposes Laplace-Bridged Smoothing (LBS), an analytic reformulation of randomized smoothing (RS) that replaces high-dimensional Monte Carlo sampling over input noise with low-dimensional computations in probability space via a Laplace bridge. It claims this preserves formal ℓ₂ robustness certificates without requiring noise-augmented training, yields stronger certified accuracy than standard RS on CIFAR-10 and ImageNet, and reduces per-sample certification cost by nearly an order of magnitude (with speedups up to 494× on edge hardware such as NVIDIA Jetson Orin Nano and Raspberry Pi 4). Theoretical justification is asserted for both the analytic formulation and certificate validity.

Significance. If the Laplace-bridge approximation supplies a provably conservative (one-sided) lower bound on the smoothed class probability p_A and corresponding upper bounds on competitors, the work would meaningfully advance practical certified robustness by removing the training-time cost of noise augmentation and enabling fast, deployable certification on resource-constrained devices. The reported empirical gains and hardware speedups would then constitute a substantial practical contribution, provided the formal guarantee is not loosened by the approximation.

major comments (2)

[Theoretical Justification (certificate validity)] The load-bearing claim is that the analytic Laplace-bridged computation exactly preserves the formal ℓ₂ certificate (i.e., the derived radius r satisfying Φ⁻¹(p_A) − Φ⁻¹(p_B) > r/σ remains valid). The skeptic concern is well-founded: any approximation error that overestimates p_A (or underestimates the gap to the runner-up) produces an invalid certificate. The theoretical justification section must therefore supply an explicit one-sided error bound or proof that the bridged p_A is a lower bound on the true Monte-Carlo expectation; without it the formal guarantee does not follow from the reformulation.
[§4 (or equivalent analytic reformulation section)] The abstract states that LBS “preserves formal robustness guarantees” and provides “theoretical justification for … certificate validity,” yet the manuscript must clarify whether the Laplace bridge is used directly or whether any conservative adjustment (e.g., a worst-case bias term) is introduced to restore soundness. If the latter, the adjustment must be shown not to re-introduce the original computational burden or to degrade the reported accuracy gains.

minor comments (2)

[Method section] Notation for the Laplace bridge parameters (e.g., the choice of mean and covariance in probability space) should be defined explicitly before the certificate formula is derived, to allow readers to verify the dimensionality reduction.
[Experiments] The empirical tables should report both the certified accuracy at each radius and the exact number of forward passes (or equivalent FLOPs) used by LBS versus baseline RS, so that the claimed order-of-magnitude reduction can be directly compared.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed and constructive review. The comments correctly identify the need for transparent one-sided bounds to support the formal claims. We address each point below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [Theoretical Justification (certificate validity)] The load-bearing claim is that the analytic Laplace-bridged computation exactly preserves the formal ℓ₂ certificate (i.e., the derived radius r satisfying Φ⁻¹(p_A) − Φ⁻¹(p_B) > r/σ remains valid). The skeptic concern is well-founded: any approximation error that overestimates p_A (or underestimates the gap to the runner-up) produces an invalid certificate. The theoretical justification section must therefore supply an explicit one-sided error bound or proof that the bridged p_A is a lower bound on the true Monte-Carlo expectation; without it the formal guarantee does not follow from the reformulation.

Authors: We agree that an explicit one-sided bound is required for the certificate to be formally valid. Section 4 derives that the Laplace bridge yields a lower bound on p_A because the approximation is constructed via moment matching that systematically underestimates the top-class probability relative to the true Gaussian-smoothed expectation. We will revise the manuscript to state this bound explicitly, include a short proof sketch showing that the bridged value is always ≤ the Monte-Carlo estimate, and confirm that the resulting radius remains a valid (possibly slightly conservative) ℓ₂ certificate. No change to the reported empirical results is needed. revision: yes
Referee: [§4 (or equivalent analytic reformulation section)] The abstract states that LBS “preserves formal robustness guarantees” and provides “theoretical justification for … certificate validity,” yet the manuscript must clarify whether the Laplace bridge is used directly or whether any conservative adjustment (e.g., a worst-case bias term) is introduced to restore soundness. If the latter, the adjustment must be shown not to re-introduce the original computational burden or to degrade the reported accuracy gains.

Authors: The Laplace bridge is applied directly to the base classifier’s output probabilities; no separate bias term or post-hoc adjustment is added. The conservativeness is an intrinsic property of the bridge construction itself, as shown in the existing theoretical analysis. Consequently, the per-sample cost remains the low-dimensional analytic computation reported, with no re-introduction of Monte-Carlo sampling. We will insert a clarifying sentence in the revised Section 4 that explicitly states the direct usage and confirms that the computational and accuracy advantages are unaffected. revision: yes

Circularity Check

0 steps flagged

No significant circularity; analytic reformulation with independent theoretical justification

full rationale

The paper frames LBS as an analytic reformulation that replaces MC sampling with low-dimensional probability-space computations while asserting formal l2 certificate preservation via separate theoretical justification. No quoted equations or sections reduce the central certificate radius or probability bounds to a self-defined fit, a parameter tuned on the target data, or a load-bearing self-citation chain. The derivation chain remains self-contained against external RS baselines and does not exhibit any of the enumerated circular patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; cannot enumerate specific free parameters, axioms, or invented entities without the full derivation and experimental details.

pith-pipeline@v0.9.0 · 5524 in / 1196 out tokens · 36500 ms · 2026-05-08T03:42:52.847690+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

Since z∼ N(µ z,Σ z), we have thatE∥z−µ z∥2 2 = Tr(Σz)≤ √ D∥Σz∥F . Therefore,E∥r(z)∥ 2 ≤ M 2 E∥z−µ z∥2 2 ≤ M √ D 2 ∥Σz∥F , which implies that ∥E[π]−softmax(µ z)∥2 ≤ M √ D 2 ∥Σz∥F .(15) Define δπ :=π−E[π] =J softmax(µz)(z−µ z) + r(z)−E[r(z)] and let ˜r(z) :=r(z)−E[r(z)], J:=J softmax(µz). Then the covariance ofπcan be decomposed as Cov(π) =E[δ πδ⊤ π ] =E[J(...

work page 1960
[2]

and (IV) holds by using Jensen’s inequality. With the choice of α given in (20), we have ˜π= softmax(µ z) and Cov(˜π) =JΣ zJ ⊤, which leads to ∆mom = M √ D 2 ∥Σz∥F + M(D 2 + 3D+ 2) 1 2 D 1 4 ∥J∥ 2 · ∥Σz∥ 3 2 F + M 2(D2+3D+2) 4 ∥Σz∥2 F from (15) and (19). Plugging it into the inequality above, we conclude that KL(Pπ∥P ˜π)≤ M √ D∥H∥ 2 2 ∥Σz∥F +O(∥Σ z∥ 3 2 F...

work page 2020

[1] [1]

Since z∼ N(µ z,Σ z), we have thatE∥z−µ z∥2 2 = Tr(Σz)≤ √ D∥Σz∥F . Therefore,E∥r(z)∥ 2 ≤ M 2 E∥z−µ z∥2 2 ≤ M √ D 2 ∥Σz∥F , which implies that ∥E[π]−softmax(µ z)∥2 ≤ M √ D 2 ∥Σz∥F .(15) Define δπ :=π−E[π] =J softmax(µz)(z−µ z) + r(z)−E[r(z)] and let ˜r(z) :=r(z)−E[r(z)], J:=J softmax(µz). Then the covariance ofπcan be decomposed as Cov(π) =E[δ πδ⊤ π ] =E[J(...

work page 1960

[2] [2]

and (IV) holds by using Jensen’s inequality. With the choice of α given in (20), we have ˜π= softmax(µ z) and Cov(˜π) =JΣ zJ ⊤, which leads to ∆mom = M √ D 2 ∥Σz∥F + M(D 2 + 3D+ 2) 1 2 D 1 4 ∥J∥ 2 · ∥Σz∥ 3 2 F + M 2(D2+3D+2) 4 ∥Σz∥2 F from (15) and (19). Plugging it into the inequality above, we conclude that KL(Pπ∥P ˜π)≤ M √ D∥H∥ 2 2 ∥Σz∥F +O(∥Σ z∥ 3 2 F...

work page 2020