Privacy law already tells platforms what outcome to deliver. Under the "right to be forgotten," data a user deleted, or opted out of, must stop shaping what the system does. What regulators lack is a way to check that outcome on a recommender system, which retrains continuously, changes architecture without notice, and exposes only its recommendations to outsiders. Rules move slowly while the systems they govern change monthly. Any check tied to a particular model or training algorithm is out of date by the time it is written into guidance. We propose a check tied to behavior instead. An auditor creates a set of "canary" accounts, which are planted test users, and secretly flips a coin for each one: the canary either deletes its history or keeps it. Each canary interacts heavily with its own rarely-viewed "marker" item from the catalog. Separate probe accounts then watch whether those marker items keep getting promoted. If deleted canaries leave the same trace as kept ones, deletion is not happening.
The coin flips make this a controlled experiment rather than an observation. The auditor can therefore attach a calibrated false-alarm rate and a numerical lower bound on how much deleted data still leaks. The test needs no model weights, gradients or internal pipelines. It is also indifferent to whether the platform runs matrix factorization, a contextual bandit, or a federated system. A test with these properties stays valid across model generations, and that is exactly what regulatory lag demands.
Core Claim
Deletion compliance can be audited from outside as a statistical test of two hypotheses. The first is that the recommender's outputs are distributed the same way whether or not a deleted user's data was ever collected. This is a black-box, statistical reading of the real-world/ideal-world indistinguishability definition in Formalizing Data Deletion in the Context of the Right to be Forgotten. The second is that the outputs differ.
Our specific technical bet is that recommenders permit tight black-box audits from a single deployment period, which image classifiers do not. Privacy Audit as Bits Transmission: (Im)possibilities for Audit by One Run treats an audit as sending bits through a noisy channel. Each canary is a bit, and the auditor's attack is the decoder. That work shows one-run audits are feasible only when each canary occupies its own independent direction of noise. When canaries interfere with one another, black-box bounds become uninformative. A large item catalog supplies those independent directions for free. If each canary's influence is routed through its own long-tail marker item, the canaries barely interfere, and the recommendation output works as a wide, nearly parallel channel.
Concretely, give canary $i$ a hidden bit $b_i \in \{0,1\}$, where 1 means "deleted." Let a decoder guess $\hat b_i$ from how often probes see marker item $m_i$. Suppose the platform's deletion were $\varepsilon$-indistinguishable from never having collected the data. Then no decoder could beat accuracy $e^{\varepsilon}/(1+e^{\varepsilon})$; this follows from the standard hypothesis-testing view of $\varepsilon$-indistinguishability applied to each independent canary. An observed accuracy $\widehat{\mathrm{acc}}$ over $n$ canaries therefore certifies, with confidence $1-\alpha$:
$$ \varepsilon_{\text{lower}} = \log\frac{\mathrm{acc}_{\alpha}}{1-\mathrm{acc}_{\alpha}}, $$
where $\mathrm{acc}_{\alpha}$ is the one-sided lower confidence bound on $\widehat{\mathrm{acc}}$. We will use the tighter trade-off-function intervals from the bits-transmission paper in place of a Hoeffding bound. A compliant system yields $\varepsilon_{\text{lower}} \approx 0$. A platform that only hides the deleted user's own feed, but keeps that user's past updates in shared item representations, yields a clearly positive bound.
Research Program
The work has three parts.
The first part is the audit protocol. It consists of the canary and marker design, the randomized delete/keep assignment, the probe accounts, and the decoder. The probes are disjoint accounts seeded with profiles near each canary. They measure the exposure each marker item receives.
Two prior results shape the protocol. On Differentially Private Online Collaborative Recommendation Systems shows that any useful collaborative recommender leaks individual ratings through its output stream unless it adds randomized noise. That result is why we expect the recommendation channel to carry signal at all. Dynamic Global Sensitivity for Differentially Private Contextual Bandits shows that an online model's sensitivity to one user's input decays roughly as $O(1/t)$ as data accumulates. This constrains the design: a canary's trace on popular items washes out quickly. We predict that marker items drawn from the long tail, where $t$ stays small, keep canary influence detectable for much longer. We will measure that decay directly.
The second part is a ground-truth testbed. We build recommenders whose true deletion behavior we control. The model families are matrix factorization, private alternating least squares in the spirit of Private Alternating Least Squares, LinUCB and Private LinUCB-DGS, binary-code federated factorization as in LightFR, and chained federated training as in FedQ.
Each family gets four deletion behaviors:
- Full retraining without the user. This is the ideal world.
- Flag-only deletion, where data is hidden but still used for training.
- Partial unlearning, where the user's own embedding is dropped but their past updates to item vectors and to downstream chained clients remain.
- Opt-out that stops personalizing the display but keeps training on the user's data.
Partial unlearning is exactly the residue that the deletion-formalization paper notes is unresolved for collaborative models. We expect FedQ's chaining and LightFR's discrete codes to make it the realistic failure mode.
The third part addresses regulatory lag directly. We swap the underlying recommender partway through an audit, for example from factorization to a bandit, and ask whether the audit's verdict and error rates survive the change. Navigating Governance Paradigms documents that compliance boundaries became obsolete when a commercial model changed versions. Advancing Science- and Evidence-based AI Policy calls for pre-committed "if-then" thresholds and auditor safe harbors. A threshold written as "$\varepsilon_{\text{lower}}$ above $c$ at confidence $1-\alpha$ triggers review" is the kind of rule that stays meaningful when the technology underneath changes.
The Bottleneck in AI Governance and Oversight gives one reason such durability matters. It finds that bills referred to technology committees reach the floor far less often (odds ratio 0.34). Rules that get through should not need re-legislating with every architecture change. These policy papers motivate the work but supply no method. The method comes from the auditing and recommender papers cited above.
Baselines
The naive reference point is a do-nothing check: accept the platform's self-reported deletion. In the testbed, this certifies all four deletion behaviors as compliant, so its detection power against the three non-compliant behaviors is zero by construction. Every other method must beat this floor.
The strongest existing black-box method is the data-misuse metric of AuditAgent. It computes the Kullback–Leibler divergence between a sock-puppet user's recommendation distribution before and after that user opts out. It is the closest competitor because it is also external and behavioral, and it is aimed at the same legal question. We will run it on the same canary accounts, with the same query budget and over the same time window. We will also tune its divergence threshold on the same held-out calibration systems we use for our decoder.
We found no reported numeric result on Lacuna for AuditAgent's data-misuse metric. The comparison therefore has to be produced within this project. Beating it means higher detection power at a matched 5% false-positive rate on the partial-unlearning and opt-out-but-train systems. It also means keeping that false-positive rate under natural catalog drift and model retraining, where a before/after divergence on a single account cannot separate deletion from ordinary drift.
The white-box reference is a membership-inference audit in the style of ML Privacy Meter, run with full model access on each model snapshot. It is not a fair competitor for an external regulator. It serves as an upper reference on what is detectable. That paper's illustrative leakage figure is an attack AUC of 0.81 on a supervised classifier, against 0.5 for chance. The figure comes from a different task, so we do not treat it as a target. If our black-box audit's $\varepsilon_{\text{lower}}$ lands close to the white-box value, the claim that recommendation outputs form a wide channel is supported.
The key ablation removes marker items. Canaries interact with ordinary popular items, and everything else is held fixed. This ablation isolates whether the catalog-as-independent-directions idea is doing the work.
Why not just…?
Why not just use AuditAgent's before/after divergence? It measures change in one account across time, so anything else that changes in that window also counts as change: new items, retraining, seasonal taste. It also measures only the deleting user's own feed. That is precisely the surface a "hide but keep training" platform keeps clean while the user's influence persists in what other users see. Our randomized delete/keep assignment and disjoint probes address both problems. However, a randomized version of the divergence metric is a real threat. Comparing average divergence between randomly assigned delete and keep groups might already capture most of the gain. We include that randomized-divergence variant as a second baseline. If it matches our decoder, the contribution narrows to the marker-item design and the calibrated lower bound.
Why not just require providers to certify a differential-privacy budget? A stated $\varepsilon$ describes the training algorithm, not the deployed code. The bits-transmission audit found an unverified bug in an existing DP-SGD implementation that theory alone missed. Moreover, differential privacy limits influence during training and does not by itself implement deletion. The deletion-formalization paper needs differential privacy plus unlearning plus history-independent storage. A certificate is also tied to a mechanism, so it becomes stale when the architecture changes. Our version-swap experiment tests that failure mode directly.
Why not just use similarity or anonymization metrics on released data? Synthetic Data, Similarity-based Privacy Metrics, and Regulatory (Non-)Compliance shows these metrics fail in both directions. They passed a release that leaked half the population. They rejected samples drawn from the true distribution 72.6% of the time. They also say nothing about whether a live model still carries a deleted user's influence.
Why not just retrain from scratch on every deletion request? That is a remedy, not an audit. A regulator still needs evidence the retraining happened. Our testbed uses full retraining as the ideal world, and the audit must certify it as clean.
Proposed Experiments
The testbed uses MovieLens-1M and MovieLens 25M, LastFM (about 1,900 users and 17,600 artists), and Ciao, at 0.04% density. Each dataset is split so that canaries draw marker items from the bottom popularity decile. We check that each model family reaches sensible utility before auditing it. For the federated models, the reference point is FedQ's reported top-100 candidate accuracy on MovieLens 25M with 162,000 simulated clients: about 23.72% for FedQ against about 10.14% for federated averaging.
The primary metric is detection power at a 5% false-positive rate, broken down by deletion behavior and model family. Secondary metrics are the number of canaries and probe queries needed to reach 80% power, and the certified $\varepsilon_{\text{lower}}$.
Four checks decide the project. First, on full-retraining systems, the false-positive rate must stay at or below the nominal 5% across all families. This is the calibration test. Second, on partial-unlearning systems, the marker-item audit must reach higher power with fewer canaries than both the popular-item ablation and the randomized divergence baseline. If it does not, the wide-channel hypothesis fails. Third, power should fall with marker-item popularity in roughly the $1/t$ shape predicted by dynamic-sensitivity analysis. Fourth, in the version-swap runs, the audit's calibration and power must hold across the change. The comparison point is a check built on the provider's declared $\varepsilon$, which we expect to lose validity at the switch.
A negative result on the second check would also be informative. It would show that black-box deletion auditing of recommenders inherits the same impossibility found for one-run image-model audits, and that regulators must mandate gradient-level access rather than rely on outside observation.
References
- Formalizing Data Deletion in the Context of the Right to Be Forgotten
- Privacy Audit as Bits Transmission: (Im)possibilities for Audit by One Run
- On Differentially Private Online Collaborative Recommendation Systems
- Dynamic Global Sensitivity for Differentially Private Contextual Bandits
- Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates
- LightFR: Lightweight Federated Recommendation with Privacy-preserving Matrix Factorization
- A Privacy Preserving System for Movie Recommendations Using Federated Learning
- Navigating Governance Paradigms: A Cross-Regional Comparative Study of Generative AI Governance Processes & Principles
- Advancing Science- and Evidence-based AI Policy
- The Bottleneck in AI Governance and Oversight: Evidence from 1,419 State Bills
- AuditAgent: LLM Agent for Risks Auditing in Recommender Systems
- ML Privacy Meter: Aiding Regulatory Compliance by Quantifying the Privacy Risks of Machine Learning
- Synthetic Data, Similarity-based Privacy Metrics, and Regulatory (Non-)Compliance