acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 to . 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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
machine unlearning, sequential unlearning, permutation optimization, path dependence, quadratic assignment

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_dCZrOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper shows how to order a fixed batch of machine unlearning requests. Given a fixed initial model, deletion requests, update rule, and terminal objective, they show that different permutations can lead to different final models.

The paper studies two possible simplifications of the resulting objective J(π)J(\pi): position additivity, where the objective can be represented by request-position costs and optimized using assignment or sorting, and suffix localization, where the distant prefix becomes largely irrelevant once the final LL requests are fixed. The paper analyzes these structures under shared affine updates, studies how quadratic interactions obstruct additivity, proves that the two notions are independent, and derives a suffix-conditioned assignment approximation with error scaling as O(ρ2L)O(\rho^{2L}).

The experiment section evaluates these structures in frozen head and full network unlearning settings and studies whether structural models identified from a subset of executed orders generalize to unseen permutations.

Critical strengths
  1. I found the structural view of deletion ordering useful. In particular, separating position additivity from suffix localization clarifies two different ways in which a combinatorial ordering problem can simplify: reducing interactions versus reducing dependence on distant history.

  2. The theoretical analysis is the strongest part of the paper. The characterization of quadratic interactions, the distinction between approximate and exact tractability, and the improvement from O(ρL)O(\rho^L) to O(ρ2L)O(\rho^{2L}) under suffix-conditioned assignment are meaningful contributions.

Critical weaknesses
  1. The end-to-end method is not sufficiently clear. The paper provides a structural theory, but I found it difficult to extract a concrete procedure that could be applied to a new unlearning problem. The intended workflow seems to involve executing some orders, fitting one or more structural models, deciding which structural family is appropriate, choosing the suffix length LL, and then optimizing the resulting surrogate. However, it is not clear how the identification orders should be selected, how many executions are required, how one should choose among sorting, assignment, suffix localization, or suffix-conditioned assignment, or what criterion determines whether the learned structure is reliable enough to use. The theory is much clearer than the actual practical algorithm.

  2. The tractable structural families seem fairly restrictive. Position additivity assumes that most of the objective can be captured by request-position costs, while suffix localization assumes that relevant history can be summarized by a short suffix. Suffix-conditioned assignment allows some conditional dependence, so I do not think the paper completely ignores interactions. However, more general effects remain outside the proposed tractable families, such as adjacency effects, interactions between non-local positions, or higher-order interactions among multiple requests. The paper is explicitly about identifying cases where tractability is possible, so I do not expect it to solve the fully general problem. My concern is instead that the current experiments do not establish that realistic unlearning objectives are commonly close enough to these particular structural families for the framework to be broadly useful.

  3. Structure identification may be the main computational bottleneck. Once a structural representation is known, assignment or sorting is cheap. The expensive operation is evaluating J(π)J(\pi), since this requires actually running a sequence of unlearning updates. The strongest sample-efficiency results are obtained in relatively simple ridge/frozen-head settings. In the full-network setting, the paper uses 112 identification executions and 336 held-out executions per instance, and explicitly describes this experiment as testing structural extrapolation rather than search efficiency. For practical use, the relevant cost is closer to

+ \text{optimization cost} + \text{final execution cost}.$$ The paper does not convincingly show that this total cost is better than simpler alternatives such as random search, existing ordering heuristics, or generic optimization over permutations under the same execution budget. 4. The full-network experiments remain small in the number of requests. The motivating problem is combinatorial in $k$, but the complete full-network experiments are mainly at $k=4$ or $k=5$. The larger-$k$ studies, including $k=8$ and $k=15$, are primarily performed in simpler ridge/frozen-head settings. This makes it unclear whether the same position-additive or short-suffix structure persists when both the model and the number/diversity of deletion requests become large. This is particularly important because more complex request interactions may appear as $k$ increases. 5. The connection between the optimized objective and actual unlearning quality is not fully convincing. The main ordering objective is based on distance to a retain-only reference. This is a useful dense objective for studying structural properties of $J(\pi)$, but it is not itself equivalent to successful unlearning. The paper acknowledges that utility and forgetting are separate quantities, and the full-network reference objective appears to track retained behavior more closely than deleted-group accuracy. I therefore would like to see stronger evidence that selecting an order with lower predicted $J(\pi)$ consistently improves actual forgetting and utility metrics, rather than mainly improving the reference-distance objective. 6. The related-work positioning seems incomplete. I think two relevant areas are insufficiently discussed. First, there is existing work on black-box optimization over permutation spaces, including Bayesian optimization methods designed specifically for expensive permutation-valued objectives. This seems directly relevant because the practical problem here is also to find a good permutation while minimizing expensive evaluations of $J(\pi)$. These methods provide a natural alternative to spending evaluations identifying assignment or suffix structure, and I think a comparison or at least a substantive discussion is needed. Second, the paper should better position itself relative to work on learning permutations from structural objectives, including latent permutation methods such as Gumbel-Sinkhorn and more recent work on unsupervised tasks. The technical setting is different, but the conceptual relationship is close: structure in the objective is used to recover or optimize a permutation without direct supervision. The omission of GraB is also surprising given the discussion of example-ordering methods and the citation of later related work on distributed example ordering. I do not think these omissions invalidate the contribution, but they make the proposed "structure identification" viewpoint appear more isolated from existing permutation-learning and permutation-optimization literature than it is. 7. I found several reproducibility issues in the released code. The Kumar plans appear to be generated for different request sets than those used to report the Table 28 scores. For seed 0, for example, the plan uses superclasses $\{2,3,5,9\}$, while the corresponding reported evaluation appears to use $\{14,15,16,19\}$. If I understand the code correctly, this conflicts with the statement that the comparison is performed on the same instances. I could also only find SalUn runs for seeds 0--2, while the paper reports 10 instances. Finally, the NegGrad+ and SalUn implementations are loaded from external codebases that are not included in the released artifact, and I could not identify the exact repository commits used. This is particularly relevant here because the paper studies structural properties induced by the update dynamics, so implementation differences may directly change the object being measured. These issues may have straightforward explanations, but they currently reduce my confidence in parts of the empirical evaluation.
Questions for authors
  1. What is the intended end-to-end procedure for applying the method to a new unlearning problem? In particular, how are the identification orders selected, how many executions are needed, how is the structural family selected, and how is the suffix length LL chosen?

  2. What criterion determines whether a learned assignment/suffix model is accurate enough to trust for selecting an order?

  3. What is the total wall-clock/GPU cost of the structure-identification stage in the full-network experiments? Under the same execution budget, how does the method compare with random search, existing ordering heuristics, or generic black-box optimization over permutations?

  4. Can the authors provide stronger evidence that orders selected using the learned structural surrogate improve standard forgetting and retained-utility metrics, rather than primarily improving the retain-reference objective J(π)J(\pi)?

  5. Can the authors comment on scalability to larger full-network request sets? The strongest complete full-network results appear to be at k=4k=4 or k=5k=5, while the larger-kk results are mainly obtained in simpler ridge/frozen-head settings.

  6. How do the authors view the relationship between this work and black-box optimization over permutation spaces, such as Bayesian optimization methods for expensive permutation objectives? A comparison under a fixed number of evaluations of J(π)J(\pi) would be particularly informative.

  7. Why is GraB not discussed in the related-work section, given the paper's discussion of example ordering and its citation of later related work in this line?

  8. I found an apparent mismatch in the Kumar comparison used for Table 28. For seed 0, the plan appears to use superclasses {2,3,5,9}\{2,3,5,9\}, while the corresponding evaluated instance appears to use {14,15,16,19}\{14,15,16,19\}. Am I misunderstanding the code, or are the plans and reported scores based on different request sets?

  9. What exact repository versions or commits were used for the external NegGrad+/SCRUB and SalUn implementations?

Reviewer_bJUtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper addresses the problem of determining which order to remove training data dependence from a model. The authors formulate as a permutation optimization problem and identify properties of the objective that allow for reductions that make the problem tractable. Furthermore, these reductions yield approximations even if the objective cannot be reduced exactly. The authors establish NP-hardness of the permutation optimization problem, even under some restrictions such as contraction. Many real world objectives are evaluated to determine to which degree they admit reductions to these tractable approximate objectives.

Critical strengths

The problem addressed is very practical, and the setup gives good theoretical grounding to the problem.



The reductions identified are well defined and natural. These reductions are also interesting as they do not trivialize the problem, while still making it tractable. 



Establishing NP-hardness of optimization and independence of the two reductions provides nice theoretical context.

Critical weaknesses

Clarity of presentation is a persistent issue (I am not an expert in this area, and defer to higher confidence reviews if they disagree on this assessment). For example, when the term contraction is used, it is not clear what map it is referring to. (Likely it is that the transition induced by each request is a contraction, but this remains unstated.)



Although experiments provide interesting structural investigations, the performance of the proposed methods and approximations versus competing approaches are not evaluated.


Relatedly, it is hard to see exactly how the algorithm of Proposition 2 would be implemented in practice given its many assumptions.

Questions for authors

Why was a squared terminal objective chosen? In particular, this introduces added pairwise interactions, which is an additional complication. So, what is the added value in choosing this over a simpler terminal objective?

How is suffix error defined? 


Can you discuss if contraction is a fair and practical assumption?

Reviewer_edPuOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Approximate unlearning often processes pending deletion requests one at a time with a fixed policy, so the final model depends on their order. The paper studies the optimization problem over orders that such a policy induces. Using a model in which every request applies the same kind of affine update, it identifies two independent ways this problem can simplify: position additivity, which reduces ordering to assignment or sorting, and suffix localization, where only the last few requests matter. Experiments on frozen classifier heads and on full-network NegGrad+ and SalUn unlearning on CIFAR-100 find both structures, and structures fitted on a few executed orders predict unseen ones.

Critical strengths
  1. The theory is clean and correct, and shows the two structures are independent and finding the exact best order is NP-hard in general.
  2. The authors use careful controls and report negative results openly.
Critical weaknesses
  1. In appendix E.6, pooling the deletions outperforms the best sequential order by about 38%. I am confused by the motivation of this paper. Is there a real scenario where the requests are collected together but cannot be pooled and have to be sequential?
  2. In Table 23, the orders found don’t seem to be better than random search.
  3. The full-network experiments are very small (ResNet-18 on CIFAR-100, at most 8 requests).

The paper asks a new question and the analysis is clean, but it does not show that request ordering matters in practice, and its own appendix suggests it does not. A concrete setting where reordering helps and pooling is not possible, along with evidence under stronger unlearning, would raise my score.

Questions for authors

Is there a real scenario where the requests are collected together but cannot be pooled and have to be sequential?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.