- 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 : 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 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 .
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
-
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.
-
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 to under suffix-conditioned assignment are meaningful contributions.
Critical weaknesses
-
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 , 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.
-
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.
-
Structure identification may be the main computational bottleneck. Once a structural representation is known, assignment or sorting is cheap. The expensive operation is evaluating , 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
Questions for authors
-
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 chosen?
-
What criterion determines whether a learned assignment/suffix model is accurate enough to trust for selecting an order?
-
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?
-
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 ?
-
Can the authors comment on scalability to larger full-network request sets? The strongest complete full-network results appear to be at or , while the larger- results are mainly obtained in simpler ridge/frozen-head settings.
-
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 would be particularly informative.
-
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?
-
I found an apparent mismatch in the Kumar comparison used for Table 28. For seed 0, the plan appears to use superclasses , while the corresponding evaluated instance appears to use . Am I misunderstanding the code, or are the plans and reported scores based on different request sets?
-
What exact repository versions or commits were used for the external NegGrad+/SCRUB and SalUn implementations?