A visual, hands-on tour of the algorithm in VOUCH: Anytime-Valid Certificates for Machine Unlearning via Paired-Canary Hypothesis-Betting (Quang-Vinh Dang, accepted in Machine Learning, Springer). Every demo below runs live in your browser.
Mai asks a language-model provider to forget her records. The provider runs an unlearning method (gradient ascent, NPO, RMU…) and says: done. A regulator, or Mai, wants more than a promise. What evidence could there be?
The usual answers all have a hole:
| Common check | What goes wrong |
|---|---|
| Compare to a model retrained without Mai's data | Unaffordable at LLM scale, and ill-defined for multi-stage pipelines. |
| Membership-inference tests on her records | Only meaningful if the inclusion of the data was randomised. Otherwise a "member" and a "non-member" differ in many ways besides membership. |
| A fixed-sample statistical test | Valid only if you decide the sample size in advance. An auditor who watches evidence accumulate and stops when it looks good breaks the error guarantee (see demo 5). |
Before fine-tuning, the provider generates pairs of exchangeable synthetic records (same template, different random secrets), commits to the list with a hash, and then flips a fair coin per pair. The winning twin goes into the training set (and, later, into the forget set, so it travels through the entire unlearning pipeline). The other twin, the ghost, is never shown to any model.
Why this is powerful: if unlearning is exact, the final model has no information about which twin was trained on, so the two twins look statistically interchangeable. The null hypothesis is symmetric by construction. It needs no shadow models and no retrained reference.
Each pair has twin A and twin B. A fair coin decides which one is trained on (solid blue); the other is the ghost (dashed).
After unlearning, query the deployed model as a black box and score both twins (for example, mean token log-likelihood of the secret). For pair i take the difference Di = score(in-twin) − score(ghost) and keep only its sign, zi = 1[Di > 0].
Move the slider to change how much the model still remembers. Each dot is a pair; right of the line means the trained twin scored higher.
Instead of computing a p-value at a fixed time, VOUCH lets a gambler bet against the hypothesis you want to reject. Start with wealth 1. Each pair reveals a sign; the gambler stakes a fraction of wealth. If the hypothesis is true the game is fair or unfavourable: wealth is a nonnegative supermartingale. Ville's inequality then says the wealth ever reaches 1/α with probability at most α, at any time, ever. Watch the process as long as you like; stop when you like.
VOUCH runs three bettors at once:
| Bettor | Tries to reject | Reaching 1/α means |
|---|---|---|
| Cert ↑ | Δ ≥ +ε (too much leakage) | leakage is below +ε |
| Cert ↓ | Δ ≤ −ε (over-forgetting) | over-forgetting is above −ε |
| Revoke | Δ = 0 (exact unlearning) | alarm: the model still remembers |
Certificate = both Cert wealths cross 1/α (an (ε,α)-forgetting certificate). Revocation = the alarm crosses first. If the cohort runs out first, the verdict is undetermined: you did not collect enough evidence.
Set how much the model really leaks, pick a tolerance, and watch the three wealth processes (log scale). α = 0.05, so the threshold is ln 20 ≈ 3.0. Bets are a fixed mixture of stake fractions, as in the paper's default engine.
Try: Δ = 0, ε = 0.2 → certified after a few hundred pairs (about 1 run in 20 may raise a false alarm: that is the α budget at work, rerun a few times). Δ = 0.35 → revoked within tens of pairs. Δ = 0, ε = 0.1 → often still undetermined at 1,024 pairs, since a tighter tolerance needs far more evidence. Undetermined is the honest answer when the data cannot separate the model from the tolerance.
A fixed-sample test promises 5% false alarms if you look once, at a pre-chosen sample size. Auditors do not behave like that: they look at the running evidence and stop when it is convincing. Each extra look is another chance for noise to cross the line.
Every audit streams up to 500 pairs from a model with Δ = 0 (nothing to find). A red square means that audit raised a false alarm at some point. Left: a z-test checked after every pair. Right: the VOUCH revocation e-process.
Nominal level is 5% for both. The test, applied continuously, flags far more; the e-process stays within its budget by construction.
Deletion requests arrive in waves. To certify the whole history, how should the per-wave results combine? The intuitive move, multiply the e-values (evidence accumulates!), is wrong for certificates: one huge e-value can mask a bad wave. The paper proves the directions differ:
Good waves earn a certificate e-value of 40 (above 1/α = 20). The bad wave (true Δ above ε) cannot earn one. Illustrative numbers.
The threat model is honest-but-verifiable: the provider does not treat canaries differently. The paper measures how easily a perplexity filter can locate templated canaries and gives a design rule (entropy dilution) to make that harder, but cryptographic proofs of unlearning would be needed to close the gap fully. Certificates are per cohort, not per deletion request, and canaries must be planted before fine-tuning.
| Question | Finding |
|---|---|
| Is the certificate valid under dependence? | A fixed-boundary process breaches α eightfold (0.389 vs 0.05); the cohort version holds. |
| Are the obvious compositions safe? | The adaptive-mixture alternative (the authors' own earlier design) falsely certifies 99.6% of the time under an adversarial composite null; multiplying certificate e-values falsely certifies every history. |
| Real models? | TOFU and MUSE-News on GPT-2, Pythia-160M, Phi-1.5 (and a zoo up to 5.1B). Un-unlearned models are revoked on 16 of 18 benchmark runs; retraining, gradient ascent and NPO certify on 18 of 18 at ε = 0.2. |
| Beyond loss-based methods? | RMU, which acts on representations, lands near retraining on the certified quantity while barely moving forget-set likelihood. A forget-quality metric would rank it low; the certificate does not. |
| Attacks from outside F? | A LiRA shadow-model attack recovers Δ = +0.82 (TinyGPT) and +0.48 (GPT-2) on un-unlearned models and ≈ −0.02 to −0.03 on certified NPO. Intervals lie inside (−0.2, 0.2), so they support equivalence at ε = 0.2, not at 0.1 or 0.05. |
| Does the reveal order matter? | Replaying 468 saved audits with independent orders leaves the majority verdict unchanged in 450; headline ε = 0.2 counts barely move. |
| Cost? | 2Qm forward passes for m pairs and Q query wrappers. No retraining, no shadow models. |
from vouch.verify import VouchConfig, VouchVerifier
# pair_diffs[i][score] = score(in-twin) - score(ghost-twin)
v = VouchVerifier(["loss", "mink"],
VouchConfig(eps=0.2, alpha=0.05),
manifest_sha256="<commitment published before training>")
cert = v.run(pair_diffs, reveal_source="beacon") # drand beacon for the reveal order
print(cert.status, cert.t_stop, cert.delta_upper) # ISSUED / REVOKED / UNDETERMINED
For a real audit draw the reveal order from a public beacon (reveal_source="beacon"), not a seed; the certificate theorem needs the order to be independent of the signs. Repository: github.com/vinhqdang/VOUCH-Verifiable-Online-Unlearning-Certification-via-Hypothesis-betting.