Forgetting Through a Narrow Channel: Ordinal Distillation for Recommender Unlearning

When a user invokes the right to be forgotten, a recommender system has to remove that user's influence from its trained model, not just delete their rows from a database. The usual shortcut is distillation: a "student" copy of the model is trained to imitate the original "teacher" model on everyone who stayed. The trouble is that in collaborative filtering, where a model recommends items by pooling patterns across users, the departed user's influence lives inside the teacher's scores for everyone else. Each retained user's score for a film is slightly shaped by who else watched it. Asking the student to copy those scores exactly therefore copies some of the forgotten influence back in.

We propose to limit what passes from teacher to student. Instead of the teacher's raw scores, the student would see only each retained user's top-ranked items plus one coarse "intensity bit" per ranked pair, saying whether the teacher's preference gap is large or small. The design comes from social choice theory. That field measures how much welfare is lost when a voting rule sees only rankings instead of true utilities; it calls this loss distortion, the worst-case ratio between the cost of the rule's choice and the cost of the best choice. Its main finding is that one well-placed threshold bit recovers most of the lost welfare. Our bet is that the same coarse channel keeps the useful part of the teacher (who prefers what, and roughly how strongly) while dropping the fine score detail where the forgotten user's traces sit. A second bet is that a quantized target resists the slow drift that builds up over many deletion requests.

Core Claim

In distillation-based unlearning for recommenders, the information content of the distillation target should be treated as a design variable. We claim that targets consisting of top-$p$ rankings plus a single threshold bit sit on a strictly better frontier than full-score distillation or ranking-only distillation. The frontier trades three things against each other: utility for retained users, resistance to membership inference on forgotten users, and stability across sequential deletions.

The stability argument is simple. Suppose each deletion round distills from a quantized version of the previous model's outputs. Then score drift smaller than the quantization margin is snapped back to the same target, so small errors do not compound. With continuous targets, every round's error becomes part of the next round's target.

The social choice results tell us where to look, but they do not prove our claim. Approximating Optimal Social Choice under Metric Preferences shows that rankings alone cap achievable welfare. Awareness of Voter Passion Greatly Improves the Distortion of Metric Social Choice shows that a single bit at threshold $\tau = 1+\sqrt{2}$ cuts two-candidate distortion from 3 to about 1.83, against about 1.41 with full cardinal strengths. Improved metric distortion via threshold approvals obtains distortion $1+\sqrt{2}$ from threshold approval sets alone. Together these suggest that most of the useful cardinal information is coarse.

Those bounds are worst-case guarantees over adversarial metric spaces, and recommender scores are not distances. We therefore treat $\tau$ as a tuned hyperparameter, with $1+\sqrt{2}$ as the starting point the theory suggests. We do not claim the guarantee transfers.

Research Program

The method builds on three prior lines of work.

Distillation Robustifies Unlearning introduces UNDO. It first suppresses the unwanted behavior in a teacher, then adds Gaussian noise to a student copy's weights, then distills on non-hazardous data. This makes LLM unlearning resist relearning attacks. We reuse its key structural insight: if the student starts partly scrambled, the distillation target becomes the main conduit of information. UNDO distills full next-token distributions and never asks what that conduit should carry.

RankDistil: Knowledge Distillation for Ranking contributes the $p$-focused loss. That loss matches the teacher's order among its top $p$ items and penalizes high scores on items the teacher ranks low. RankDistil is a compression method with no deletion procedure; we use its loss as the ordinal part of our target.

Obliviate: Efficient Unlearning in Recommender Systems is the closest existing system. It uses full-score distillation from the pre-deletion teacher as a trust-region regularizer during calibration. That is precisely the high-bandwidth channel we hypothesize leaks forgotten influence.

Concretely, an unlearning step proceeds as follows. We remove the forgotten user's interactions and embedding. We perturb the shared item and user parameters with noise, as in UNDO. Then, for a sampled set of retained users, we compute targets from the current teacher. Each target is the teacher's top-$p$ list. Each adjacent pair $(a, b)$ in that list, together with each pair of the form (top item, boundary negative), is labeled with a bit

$$z_{ab} = \mathbb{1}\left[c(b) \ge \tau \, c(a)\right],$$

where $c(\cdot)$ is a positive cost obtained from the teacher's score through a fixed monotone transform (for example $c = \exp(-s/T)$, with $s$ the score and $T$ a temperature fit once on the original model).

The student minimizes two terms. The first is the $p$-focused ranking loss on the list. The second is a margin loss that pushes its own cost ratios to the correct side of $\tau$ whenever $z_{ab}$ is set, with a hinge band around $\tau$ so that pairs already on the correct side receive no gradient.

For sequential deletions, round $t$ distills from the round-$(t-1)$ student's quantized targets. Because pairs on the correct side of the band contribute no gradient, drift smaller than the band is absorbed rather than propagated.

The channel carries at most $\log_2\big(\binom{N}{p}\, p!\big) + O(p)$ bits per retained user, where $N$ is the item count. We report this alongside the float-score channel so that bandwidth is explicit. We then sweep $p$, $\tau$, and the number of thresholds (zero, one, or two bits per pair) to trace the full frontier.

The analysis component asks a question that standard ranking metrics hide. Selective and collaborative influence function for efficient recommendation unlearning and ERASE -- A Real-World Aligned Benchmark for Unlearning in Recommender Systems both report HR@k and NDCG@k only. These metrics count whether liked items appear near the top. They do not register an unlearned model that keeps the ranking order but demotes a user's strongly preferred items in favor of mildly preferred ones.

MovieLens supplies 1–5 star ratings, so we can measure this directly with an empirical welfare ratio. For each retained user, we take the held-out star-weighted value of the top-$k$ list from the retrained-from-scratch model and divide it by the value under the unlearned model. We average over users and report the worst decile. This is a distortion-style measure computed against the retrained model, which is the legal reference point for a deletion. Our hypothesis predicts that ranking-only distillation scores well on NDCG but poorly on this ratio, and that the intensity bit closes most of the gap.

Baselines

The naive reference points come first. The original undeleted model is the "do nothing" option. It has the best utility and the worst forgetting, and it fixes the top-left corner of every frontier plot. Retraining from scratch without the forgotten data is the gold standard for both legal compliance and utility. On ML-1M, Selective and collaborative influence function for efficient recommendation unlearning reports retraining at HR@20 = 0.6758.

The strongest existing recommender unlearning method in the file is SCIF. It updates only the parameters most affected by the deletion using influence functions, and fills deleted interactions with collaborative averages. That paper reports HR@20 = 0.5928 on ML-1M with a 28.5× speedup over retraining, against 0.4293 for the sharding method RecEraser. ERASE independently finds SCIF the most consistent and robust method under sequential deletion; ERASE reports no per-method numbers we can quote.

Obliviate is the strongest distillation-based competitor. It uses an Adam-statistics curvature downdate followed by full-score distillation on retained interactions. It reports a 57.2-second unlearning step against 1984 seconds of retraining for LightGCN on Yelp 2018. The file has no per-dataset HR numbers for it on ML-1M; no reported result found on Lacuna for Obliviate HR@20 on ML-1M.

Fairness rules apply to all methods. Every method runs on the same LightGCN and matrix-factorization backbones, the same deletion samples, and the same 20-request sequential protocol. We rerun SCIF and Obliviate from their papers' settings under our splits rather than quoting their numbers. Every method gets an equal hyperparameter search budget, roughly 30 configurations, selected on a validation forget/retain split. Wall-clock time is reported against retraining, using ERASE's argument that deployment requires roughly 1,000× speedup.

Four ablations isolate the key ingredient, the contents of the channel. The full-score variant keeps our noise-then-distill pipeline but uses the teacher's float scores, which is UNDO transplanted to recommenders. The ranking-only variant uses the $p$-focused loss with zero bits. The matched-noise variant uses float scores plus Gaussian noise, with the noise scale chosen so that its utility equals ours. Finally, our method is run with zero, one, and two thresholds, and with $\tau$ swept with $1+\sqrt{2}$ included.

We beat the baselines if two conditions hold. First, at equal or lower membership-inference advantage on forgotten users, our method stays within 0.02 HR@20 of retraining on ML-1M; SCIF's reported gap is about 0.08. Second, after 20 sequential deletions, our utility loss is at most half of SCIF's and of full-score distillation's.

Why not just…?

Why not just distill full scores, as Obliviate and UNDO do? It is the simplest choice, and it may turn out that the forgotten user's influence on retained-user scores is too small to matter. If so, our premise fails. We test this directly. The full-score ablation and our method share every other component. If full-score distillation matches our membership-inference resistance and our 20-round stability at equal utility, the narrow channel adds nothing and we will say so. UNDO's own observation of a roughly 4.88% MMLU drop under restricted distillation budgets suggests that budget and target choices matter, but it does not settle the question for recommenders.

Why not just add noise to the teacher's scores, in the style of differential privacy? This is the most serious threat. Quantization is one way to reduce channel information, and calibrated noise is another that comes with cleaner privacy accounting. The matched-noise baseline exists to settle this. We compare the two on the utility-versus-membership-inference frontier, not at a single point, and separately on drift over 20 rounds. Our specific prediction is that noise does not create fixed points: drift accumulates under noise but is absorbed by the hinge band. If noise dominates on both axes, the proposal reduces to recommending noise.

Why not just distill rankings alone with RankDistil's loss? This variant transmits even less, so it might forget as well as our method or better. The distortion literature predicts that it gives up utility in a way NDCG does not see. The welfare-ratio measure on MovieLens stars is built to expose exactly that cost. If ranking-only matches our welfare ratio, the intensity bit is unnecessary.

Why not just use SCIF, which ERASE already finds most stable? SCIF is a first-order influence method with no distillation. Its stability is the bar we have to clear, not an argument against trying. If SCIF beats every distillation variant on the sequential protocol, that is a useful negative result for the distillation line of unlearning work.

Proposed Experiments

We run on ML-1M, chosen for its star ratings and published SCIF numbers, and on Yelp 2018 and Amazon Fashion, which are sparse and match Obliviate's settings. Backbones are LightGCN and matrix factorization. For sequential stress we use the ERASE collaborative-filtering protocol with 20 deletion requests.

Forgetting is measured three ways. The first is a trained membership-inference oracle following SCIF. The second is a likelihood-ratio membership test, reporting attacker advantage at low false-positive rates. The third is a relearning attack: we fine-tune briefly on the forgotten interactions and measure how fast the forgotten user's held-out items return to their top-20, compared with the retrained model.

Utility is measured by HR@20 and NDCG@20 on retained users and by the star-weighted welfare ratio against retraining.

Three checks decide the outcome. First, on the utility-versus-membership-inference frontier, the one-bit channel must dominate both full-score and matched-noise distillation. Second, over 20 deletions, our method's HR@20 curve must stay flat while full-score distillation's degrades. The prediction specifically attributes this to the hinge band, so removing the band should bring the drift back. Third, the welfare ratio must separate ranking-only from one-bit distillation even when their NDCG values are within noise of each other. This last check would show that the ordinal-cardinal gap has a measurable cost in unlearning, and that standard recommender unlearning benchmarks do not see it.