# Protecting the Undeleted in Machine Unlearning

arXiv: https://arxiv.org/abs/2602.16697 · HTML: https://mlsanity.com/paper/2602.16697/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Machine unlearning, one of 12 directions in LLM safety and security.
- Builds on 19 of its 32 references that are in the map.
- First posted on arXiv 18 Feb 2026.

## Placed in

- LLM safety and security / [Machine unlearning](https://mlsanity.com/safety/machine-unlearning/)

## Builds on (most cited first, 19 of 19)

- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [The Privacy Onion Effect: Memorization is Relative](https://mlsanity.com/paper/2206.10469/) (2022)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Forget Unlearning: Towards True Data-Deletion in Machine Learning](https://mlsanity.com/paper/2210.08911/) (2022)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Formalizing Data Deletion in the Context of the Right to be Forgotten](https://mlsanity.com/paper/2002.10635/) (2020)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [Deletion Inference, Reconstruction, and Compliance in Machine (Un)Learning](https://mlsanity.com/paper/2202.03460/) (2022)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries](https://mlsanity.com/paper/2403.00028/) (2024)
- [Control, Confidentiality, and the Right to be Forgotten](https://mlsanity.com/paper/2210.07876/) (2022)
- [Auditing Approximate Machine Unlearning for Differentially Private Models](https://mlsanity.com/paper/2508.18671/) (2025)
- [Deletion-Compliance in the Absence of Privacy](https://mlsanity.com/paper/2201.03499/) (2022)
- [The Space Complexity of Learning-Unlearning Algorithms](https://mlsanity.com/paper/2506.13048/) (2025)

## Built on by (most cited first, 4 of 4)

- [Client-Side Probing of Deleted Ridge Statistics in Federated Unlearning](https://mlsanity.com/paper/2609.04475/) (2026)
- [Machine Unlearning as Private Retroactive Algorithms](https://mlsanity.com/paper/2609.05329/) (2026)
- [Modeling Deletion Requests in Machine Unlearning](https://mlsanity.com/paper/2610.04310/) (2026)
- [Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees](https://mlsanity.com/paper/2610.17993/) (2026)

## Abstract (arXiv)

Machine unlearning aims to remove specific data points from a trained model, often striving to emulate "perfect retraining", i.e., producing the model that would have been obtained had the deleted data never been included. We demonstrate that this approach, and security definitions that enable it, carry significant privacy risks for the remaining (undeleted) data points. We present a reconstruction attack showing that for certain tasks, which can be computed securely without deletions, a mechanism adhering to perfect retraining allows an adversary controlling merely ω(1) data points to reconstruct almost the entire dataset merely by issuing deletion requests. We survey existing definitions for machine unlearning, showing they are either susceptible to such attacks or too restrictive to support basic functionalities like exact summation. To address this problem, we propose a new security definition that specifically safeguards undeleted data against leakage caused by the deletion of other points. We show that our definition permits several essential functionalities, such as bulletin boards, summations, and statistical learning.