# When Is Deletion Ordering Tractable? From Update Dynamics to Permutation Structure

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 29 references that are in the map.
- First posted on arXiv 1 Oct 2026.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [SalUn: Empowering Machine Unlearning via Gradient-based Weight Saliency in Both Image Classification and Generation](https://mlsanity.com/paper/2310.12508/) (2023)
- [Towards Unbounded Machine Unlearning](https://mlsanity.com/paper/2302.09880/) (2023)
- [Fast Machine Unlearning Without Retraining Through Selective Synaptic Dampening](https://mlsanity.com/paper/2308.07707/) (2023)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [What makes unlearning hard and what to do about it](https://mlsanity.com/paper/2406.01257/) (2024)
- [On Large Language Model Continual Unlearning](https://mlsanity.com/paper/2407.10223/) (2024)
- [Certified Unlearning for Neural Networks](https://mlsanity.com/paper/2506.06985/) (2025)
- [Permutation-Based SGD: Is Random Optimal?](https://mlsanity.com/paper/2102.09718/) (2021)
- [Optimal Task Order for Continual Learning of Multiple Tasks](https://mlsanity.com/paper/2502.03350/) (2025)
- [Ascent Fails to Forget](https://mlsanity.com/paper/2509.26427/) (2025)
- [Learning to Learn: How to Continuously Teach Humans and Machines](https://mlsanity.com/paper/2211.15470/) (2022)
- [Coordinating Distributed Example Orders for Provably Accelerated Training](https://mlsanity.com/paper/2302.00845/) (2023)
- [On the Impossibility of Retrain Equivalence in Machine Unlearning](https://mlsanity.com/paper/2510.16629/) (2025)
- [Linearizable special cases of the QAP](https://mlsanity.com/paper/1409.6510/) (2014)
- [Composition Orderings for Linear Functions and Matrix Multiplication Orderings](https://mlsanity.com/paper/2402.10451/) (2024)

## Abstract (arXiv)

Given a fixed set of pending deletion requests, retraining from scratch after each request is prohibitive, so a prescribed request-wise policy processes them sequentially. The resulting terminal model can depend on their order. Rather than prescribing an ordering rule, we study the permutation objective induced by the fixed policy and ask when it admits simpler structure. We identify two independent reductions: position additivity represents the objective by request--position costs, reducing optimization to assignment and, with a shared positional profile, sorting; suffix localization removes dependence on the distant prefix while retaining interactions among the surviving requests. Under shared affine updates, we characterize the quadratic interactions that obstruct additivity, prove the reductions' independence, and show that suffix-conditioned assignment improves the approximation rate from O(p^L) toO(p^(2L)). Experiments recover both structures in executed objectives. A controlled damped-Newton sweep shows that stronger contraction shifts the objective toward shorter, more suffix-specific dependence, while two full-network policies exhibit distinct positional and within-suffix structure. Structures identified from compact execution sets also predict unseen orders. These results frame deletion ordering as identifying the computational structure induced by the executed updates.