Most LLM jailbreak defences are tested, not proven. A team runs a suite of known attacks, the attack success rate drops, and the defence ships. Then an adaptive attacker who knows the defence finds a new prompt and the number goes back up. SmoothLLM and most guard classifiers live in this world: useful, measurable, and without a guarantee.
Certified robustness is the other world. A certificate is a proof that for a stated input and every perturbation inside a stated threat set, the system's decision does not change. No attack inside the set can succeed, including attacks nobody has invented yet. The price is that the threat set is narrow, the proof covers a specific decision rule, and the cost is often large.
This article explains what a certificate means from first principles, derives the tight randomized smoothing radius most later work builds on, shows why it does not transfer cleanly to tokens, and then works through erase-and-check, the best known certificate for LLM safety filtering. It ends with how to deploy it, what it does not cover, and a checklist.
What a certificate is
Formally, a classifier f is certifiably robust at input x for threat set S(x) if f(x') = f(x) for every x' in S(x), and the claim is established by an argument, not by sampling attacks. Three parts of that sentence matter in practice:
- At input x. Certificates are usually pointwise. A system can be certified on 92 percent of a test set and have no guarantee at all on the rest.
- For threat set S(x). The proof says nothing about perturbations outside the set. A certificate against appended tokens is silent about paraphrases.
- The decision. The certificate covers the classifier, often a smoothed or wrapped version of a base model, not the base model itself.
Certified accuracy is the fraction of test inputs that are both correctly classified and certified. It is always at most clean accuracy, and comparing it with empirical robust accuracy from attacks tells you how loose the certificate is.
Threat sets for text
For images the standard threat set is an L2 or L-infinity ball around the pixels. Text has no natural ball: a one-token change can flip meaning, and a distance in embedding space does not correspond to anything an attacker controls, since the attacker edits tokens, not vectors. Certified NLP work therefore uses discrete threat sets:
| Threat set | What the attacker may do | Typical certification approach |
|---|---|---|
| Synonym substitution | Replace words with listed synonyms | Interval bound propagation; smoothing over substitutions |
| Bounded word edits | Change up to k words anywhere | Smoothing by random masking or ablation |
| Adversarial suffix | Append up to d tokens | Erase-and-check, suffix mode |
| Adversarial insertion | Insert a block of up to d tokens anywhere | Erase-and-check, insertion mode |
| Adversarial infusion | Insert up to d tokens at arbitrary positions | Erase-and-check, infusion mode |
The suffix row matches the attacks that matter most for LLMs today: optimisation attacks such as GCG append a string of tokens to a harmful request. That is why the insertion family of threat sets has become the practical target.
Randomized smoothing, the origin
Randomized smoothing (Cohen, Rosenfeld and Kolter, 2019) is the idea every later method borrows. Take any base classifier f. Define a smoothed classifier g(x) as the class f returns most often on x plus Gaussian noise with standard deviation sigma. If the top class has probability at least pA and the runner-up at most pB, then g is constant within an L2 radius of sigma / 2 x (inverse-normal(pA) minus inverse-normal(pB)). With pB = 1 minus pA this is sigma x inverse-normal(pA).
The probabilities are unknown, so they are estimated by Monte Carlo with a one-sided Clopper-Pearson lower bound. The certificate then holds with probability 1 minus alpha over the sampling. If the lower bound is not above one half, the smoothed classifier abstains.
from scipy.stats import beta, norm
def certify(count_top, n, sigma, alpha=0.001):
"""Return the certified L2 radius, or None to abstain.
count_top: how many of n fresh noisy samples voted for the class picked in a separate selection run.
"""
if count_top == 0:
return None
p_lower = beta.ppf(alpha, count_top, n - count_top + 1) # one-sided Clopper-Pearson
if p_lower <= 0.5:
return None
return sigma * norm.ppf(p_lower)Worked example: with n = 1,000 samples, 990 votes for the top class and alpha = 0.001, the lower bound is about 0.976 and the radius is about 0.49 for sigma = 0.25. Even 1,000 out of 1,000 votes only gives a lower bound of about 0.993 and a radius of about 0.62: the sample count, not the model, caps the certificate. With 600 votes the radius collapses to about 0.03.
Three lessons carry over to LLMs. Certificates come from wrapping the model in a procedure, not from the model's weights. They cost many forward passes per input. And they hold only for the procedure that was certified: if you deploy the base model alone you deploy no guarantee.
From pixels to tokens
Applying Gaussian noise to token embeddings gives a radius in embedding space, which is rarely a meaningful threat model. Text certification work replaced the noise with discrete randomisation: replacing words with random synonyms from a fixed table, or masking a random fraction of words and classifying the masked text. The certificate then bounds how many word substitutions or edits can change the majority vote. A separate line, interval bound propagation, pushes the set of allowed substitutions through the network layer by layer and proves the output stays on one side of the boundary; it gives deterministic certificates but scales poorly to large transformers.
These methods were developed for classifiers such as sentiment models. For generative LLMs the decision that matters for security is usually a binary one, harmful request or not, made by a safety filter in front of the model. That observation is what makes erase-and-check practical.
Erase-and-check
Erase-and-check (Kumar et al.; arXiv 2309.02705, published at COLM 2024) wraps a safety filter. Given a prompt, it erases tokens in every way the threat model allows, up to d tokens, runs the filter on each resulting subsequence, and rejects the prompt if any of them is labelled harmful.
The proof is one line. Suppose an attacker takes a harmful prompt P and adds an adversarial sequence of at most d tokens in the allowed way. Erasing exactly those tokens recovers P, which is one of the checked subsequences. If the filter flags P, the procedure flags the attacked prompt, whatever the attacker added. So the certified detection rate on harmful prompts equals the filter's detection rate on clean harmful prompts.
def erase_and_check_suffix(tokens, d, is_harmful):
"""Suffix mode: reject if the prompt, or any version with up to d trailing tokens erased, is harmful."""
candidates = [tokens[: len(tokens) - i] for i in range(0, min(d, len(tokens) - 1) + 1)]
return any(is_harmful(c) for c in candidates) # batch these calls in production
def erase_and_check_insertion(tokens, d, is_harmful):
"""Insertion mode: erase every contiguous block of length 1..d, plus the prompt itself."""
n = len(tokens)
candidates = [tokens]
for length in range(1, d + 1):
for start in range(0, n - length + 1):
candidates.append(tokens[:start] + tokens[start + length:])
return any(is_harmful(c) for c in candidates)Counting the checks shows where the cost goes. For a 70-token input (a 50-token request plus a 20-token attack) and d = 20, suffix mode runs 21 filter calls. Insertion mode, one block anywhere, runs 1,211. Infusion mode, any d tokens anywhere, needs the sum of C(70, i) for i up to 20, about 2.6 x 10^17, which is why infusion is only practical for very small d: with d = 3 it is 57,226 calls. The paper reports that against adversarial suffixes of length 20, its Llama 2 based filter certifiably detected 92 percent of harmful prompts while labelling 97 percent of safe prompts correctly. It also trained a smaller classifier as the filter to cut cost, and proposed randomised, greedy and gradient-guided variants that check only a subset of erasures; those variants are cheaper but are empirical defences, not certified ones.
What the guarantee does not cover
Read the guarantee exactly. It says: if the filter flags the clean harmful prompt, the attacked prompt is flagged too. It does not say:
- That harmful prompts the filter misses cleanly are caught. Certified detection is capped by the filter's clean recall.
- That safe prompts pass. Every extra subsequence is another chance for a false positive, so the false positive rate on benign traffic rises with d and with the mode. Measure it on your own traffic, not only on benchmark prompts.
- Anything about rewrites. Paraphrase attacks, role-play framing, attacks that change the request rather than add to it, and multi-turn attacks such as those in jailbreak defence are outside the threat set.
- Anything about the model's output. The certificate covers the input decision. Harm that arises from benign-looking input still needs output-side filtering.
- That the attacker cannot exceed d. An attack of d + 1 tokens is simply uncertified. Choose d from the attack lengths you need to cover, and treat longer prompts conservatively.
Deploying it
In production the constraints are latency and cost. Practical patterns:
- Use a small, fast filter. A fine-tuned encoder classifier or a compact guard model such as Llama Guard makes hundreds of checks affordable; the certificate does not require the filter to be large, only that it flags clean harmful prompts.
- Batch subsequences. All candidates share most tokens, so they batch well; a prefix-caching engine reuses the common prefix in suffix mode almost for free.
- Short-circuit. Stop at the first harmful verdict. Benign prompts pay the full cost, harmful ones usually do not.
- Tier by risk. Run suffix mode on all traffic and insertion mode only where an endpoint is exposed to untrusted, automated callers.
- Log what was certified. Record mode and d per decision, so you can say which traffic carried a guarantee when an incident review asks.
A worked sizing example shows how the modes differ operationally. Take an endpoint whose prompts average 300 tokens and a target of d = 20. Suffix mode adds 21 sequences of 280 to 300 tokens per request; they fit in one batched forward pass of a small classifier, so latency grows by roughly one filter call, and throughput cost grows about twenty-fold on the filter only, which is usually small next to the generating model. Insertion mode on the same prompt needs about 300 x 20 = 6,000 subsequences of nearly 300 tokens each, close to two million tokens of filter input per request. That is more than the generation itself costs for most chat workloads. The practical answer is to cap d lower for insertion mode, restrict it to short prompts or high-risk endpoints, or accept an empirical variant there and document that the certificate covers suffixes only.
Trade-offs
| Approach | Guarantee | Cost per prompt | Main weakness |
|---|---|---|---|
| Guard classifier alone | None, empirical | 1 call | Adaptive attacks against the guard |
| SmoothLLM style voting | Empirical | Tens of model calls | No formal bound against adaptive attackers |
| Erase-and-check, suffix | Certified for suffixes up to d | d + 1 filter calls | Narrow threat set |
| Erase-and-check, insertion | Certified for one block up to d | About n x d calls | Latency on long prompts |
| Erase-and-check, infusion | Certified for d scattered tokens | Combinatorial | Only feasible for tiny d |
The honest framing for a security review is layered: certified suffix checking closes the cheapest automated attack class with a proof, empirical defences and red teaming cover the rest, and nobody claims the system is certified against jailbreaks in general.
What to do next
- Write down the threat set you want covered: suffix, insertion or infusion, and the maximum attack length d.
- Measure your safety filter's clean recall on harmful prompts; that number is your certified detection ceiling.
- Implement suffix-mode erase-and-check with batched filter calls and early exit; measure p50 and p99 latency.
- Measure the false positive rate on a sample of real benign traffic for several values of d.
- Add insertion mode only on endpoints where automated adversaries are realistic.
- Keep empirical defences and universal suffix red teaming for everything outside the certified set.
- Log mode and d with every decision, and state the guarantee precisely in documentation.