Towards Scalable Exact Machine Unlearning Using Parameter-Efficient Fine-Tuning
Authors: Somnath Basu Roy Chowdhury
Krzysztof Marcin Choromanski
Arijit Sehanobish
Kumar Avinava Dubey
Snigdha Chaturvedi
Venue: ICLR 2025 Poster (2025)
Keywords: Machine Unlearning
Data Deletion
Exact Unlearning
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: An efficient framework for exact machine unlearning.

Abstract: Machine unlearning is the process of efficiently removing the influence of a training data instance from a trained machine learning model without retraining it from scratch. A popular subclass of unlearning approaches is exact machine unlearning, which focuses on techniques that explicitly guarantee the removal of the influence of a data instance from a model.  Exact unlearning approaches use a machine learning model in which individual components are trained on disjoint subsets of the data. During deletion, exact unlearning approaches only retrain the affected components rather than the entire model. While existing approaches reduce retraining costs, it can still be expensive for an organization to retrain a model component as it requires halting a system in production, which leads to service failure and adversely impacts customers.  To address these challenges, we introduce an exact unlearning framework -- Sequence-aware Sharded Sliced Training  (S3T), which is designed to enhance the deletion capabilities of an exact unlearning system while minimizing the impact on model's performance. At the core of S3T, we utilize a lightweight parameter-efficient fine-tuning approach that enables parameter isolation by sequentially training layers with disjoint data slices. This enables efficient unlearning by simply deactivating the layers affected by data deletion. Furthermore, to reduce the retraining cost and improve model performance, we train the model on multiple data sequences, which allows S3T to handle an increased number of deletion requests. Both theoretically and empirically, we demonstrate that S3T attains superior deletion capabilities and enhanced performance compared to baselines across a wide range of settings.

Published as a conference paper at ICLR 2025
TOWARDS SCALABLE EXACT MACHINE UNLEARNING USING ERRAMETER-EFFICINT FINE- TINE-TUNING
Somnath Basu Roy Chowdhury', Krzysztof Choromanski Arijit Sehanobish", Avinava Dubey², Snigdha Chaturvedi!
UNC Chapel Hill, ?Googe DeepMind, $Columiia University, "Independent, Research.
{ [somaath, snigdha] } @cs. .unc edu, {kchoro, avinavadubey ) 8goog ee com
ABSTRACT
Machine unlearning is the process of efficiently removing the influence of training data instance from trained machine learning model without retraining it from scratch. A popular subelass of unlearning approaches is exact machine unlearning, which focuses on techniques that explicitly guarantee the removal of the influence of a data instance from a model. Exact unlearning approaches use a machine learning model in which individual components trained on disjoint subsets of the data. During deletion, exact unlearning approaches only retrain the affected components rather than the entire model. While existing approaches reduce retraining costs, it can still be expensive for an organization to retrain a model component as it requires halting a system in production, which leads to service failure and adversely impacts customers. To address these challenges, we introduce an exact unlearning framework Sequence-aware Sharded Sliced Training (T' which is designed to enhance the deletion capabilities of an exact unlearning system while minimizing the impact on model's performance. At the core of S we utilize lightweight parameter-efficient fine-tuning approach that enables parameter isolation by sequentially training layers with disjoint data slices. This enables efficient unlearning by simply deactivating the layers affected by data deletion. Furthermore, to reduce the retraining cost and improve model performance, we train the model multiple data sequences, which allows S$T to handle an increased number of deletion requests. Both theoretically and empirically, we demonstrate that T attains superior deletion capabilities and enhanced performance compared to baselines across wide range of settings.
INTRODUCTION
In recent years, the growing success of machine learning (ML) has led to its widespread deployment across a range of applications (Achiam et al., 2023; Team et al., 2023; Qayyum et al., 2020; Surden, 2021). Once machine learning model has been trained, it is often necessary to unlearn specific training data instances for various reasons, like complying with user data deletion requests (Mantelero, 2013; European Parliament & Council of the European Union; Shastri al., 2019; Achille al., 2024), removing stale or corrupt data (Biggio et al., 2012; Steinhardt et al., 2017), etc. Retraining an ML model entirely from scratch with each deletion request is expensive. especially for modern large-scale models (Brown et al., 2020; Achian et al., 2023; Team et al., 2023). Machine unlearning (Nguyen et al., 2022; Xu et al., 2023) techniques focus on efficiently unlearning the influence of a data instance from trained machine learning model.
Machine unlearning techniques are classified into two broad categories: approximate and exact unlearning (Xu et al., 2024). Approximate unlearning techniques (Guo et al., 2020; Liu et al., 2024a) modify the parameters of a trained model to reduce the influence the deleted data instance. While cost-effective in practice, approximate unlearning cannot guarantee the complete removal of an instance's ' influence and it may still retain non-zero influence on the model. Morcover, auditing approximate unlearning is challenging due to the stochastic nature of ML optimization (Thudi et al., 2022). An alternative to this approach is exact unlearning (Cao & Yang, 2015; Bourtoule et al., 2021; Golatkar et al., 2023), which can guarantee the removal of data instance's 's influence from a trained

---

Published as a conference paper at ICLR 2025
model. Exact unlearning techniques a modular system, where different components within the system are trained on disjoint data subsets (Section 2). When a deletion request occurs, only the affected component needs to be retrained. However, in real- world settings, halting production system to even retrain a single component can result in service failure and significant expenses. The alternative is to function without the affected component, which may result in reduced performance, ultimately impacting end users. To address these challenges, we introduce Sequence-awar Sharded Sliced Training (S* which can exactly unlearn private fine-tuning data efficiently while minimizing the impact on performance.
The key idea behind our S framework is to perform additional offline training before deploying the initial model to reduce retraining costs. At the core of S'T, we leverage novel lightweight fine-tuning approach that allows parameter isolation by sequentially training model layers using disjoint data slices (Section 3.2). Due to this parameter isolation, it is possible to efficiently perform exact unlearning by deactivating the layers associated with the deleted instance, rather than discarding the entire checkpoint. We efficiently train multiple models using different sequences of the same data slices depending on a training budget. The training budget decides the number of models we can train. We show that increasing the training budget before deployment can significantly reduce retraining costs and improve the model's performance. We also observe that it is important to train the model using diverse sequences and provide several approaches for selecting diverse sequences (Section 3.3). Furthermore, we formalize the notion of deletion rate for exact unlearning systems and theoretically show that S achieves provably better deletion guarantees than existing approaches (Section 3.4). We conduct extensive empirical evaluations to evaluate the effectiveness of S using Transformers with parameter counts ranging from 86M to 13B on a range of tasks. Finally, in Section 4, we empirically validate the sequence selection algorithm and show that S has superior deletion performance compared existing methods in real- real-world settings.
2 BACKGROUND
Machine unlearning techniques for deep learning is broadly classified into two categories: approxi- mate and exact unlearning (Xu et al., 2024). Approximate unlearning techniques focus reducing the influence of deleted instance from a model after it has been trained. Exact unlearning techniques provide unlearning guarantees by ensuring model components trained on deleted instance are not used during inference. In this section, we discuss each of these categories in detail.
Approximate Machine Unlearning. These techniques focus on approximating the model parameters as if the deleted data instance was not there in the training set from the beginning (Guo et al., 2020). These techniques typically quantify the influence of an instance (Koh & Liang, 2017) and perform gradient ascent for unlearning (Golatkar et al., 2020a;b; Neel et al., 2021; Sekhari et al., 2021; Gupta et al., 2021; Suriyakumar& & Wilson, 2022; Liu et al., 2024a). In contrast to these approaches, (Graves et al., 2021) stores the exact gradients encountered during training and uses them directly for gradient ascent. Another line of work (Tarun et al., 2023a;b; Jia et al., 2023; Chen & Yang, 2023; Eldan & Russinovich, 2023; Patil et al., 2023; Kurmanji et al., 2024; Liu al., 2024b; Park et al., 2024; Zhang et al., 2024) focuses on unlearning in a batch setting, where they assume access to both retention set and a forget set of data instances for approximate unlearning- While efficient in practice, auditing approximate unlearning techniques is challenging due to the stochastic nature of the optimization process (Thudi et al., 2022; Wang et al., 2024) and may have weak privacy guarantees in practice (Hayes et al., 2024; Lucki et al., 2024).
Exact Machine Unlearning. These techniques focus on developing a modular machine learning system, where individual components are trained using disjoint subsets of the data. Such a system offers the advantage that when a deletion request is received for an input instance, we only need to retrain the affected component rather than the entire model. Exact unlearming systems can guarantee unlearning and privacy as none of its components is affected by the deleted instance. However, these systems require modifying the original training process of the model. The seminal work for such a modular unlearning system is Sharded, Isolated, Sliced, and Aggregated training (SISA) (Bourtoule et al., 2021). SISA uses an ensemble of models each trained on disjoint shard of the dataset as shown in Figure (left). To further reduce retraining costs, each shard is divided into slices, and the models are incrementally trained on these slices, with their checkpoints stored sequentially (shown in Figure I (right)). If a deletion request affects a data instance within the 4th slice of a shard, we must retrieve the checkpoint after the 3rd slice and retrain using the remaining data within that shard. Several
2

---

Published as a conference paper at ICLR 2025
Training Strategy
Retraining Strategy during deletion
Aggregate
1,2,3,4,5
1, 3,2,3,45
f
f
1,2,3,4
1,2,3,
D1
24
1,
1,2,3
Slices
1,2
1,2
Shards
Figure 1: Schematic diagram of the Sharded, Isolated, Sliced, and Aggregated training (SISA) (Bour- toule et al., 2021) framework. An ensemble of models is individually trained on disjoint shards (D; 's). (Left) Each shard is further divided into slices. (Right) Each model is sequentially trained on the slices and checkpoints are stored. After deletion, retraining resumes from the best available checkpoint.
settings like approaches focus on improving the components within SISA in application-spern enhancing the dataset partitioning mechanism (Aldaghri et al., 2021; Yan et al., 2022), the retraining efficiency using light-weight adapters (Kumar et al., 2023; Dukler et al., 2023), or extending the modular approach for vision tasks by using compartmentalized diffusion models (Golatkar et al., 2023). However, these approaches are orthogonal to work since they do not fundamentally modify the functioning of SISA. These modifications can be easily incorporated within our framework.
SISA is well-known framework that can guarantee exact unlearning and has found widespread applications. However, using SISA within production systems is challenging because retraining even single component would result in downtime, thereby reducing the service level agreement (SLA). Furthermore, in the worst-case scenario, if deletion requests impact the first slice in all the shards, the entire service goes down, necessitating retraining the model from scratch. In this work, we leverage parameter-efficient fine-tuning to introduce framework that improves upon the service availability and deletion capabilities of the SISA framework.
3 -AQUE SHARDED SLICED TRAINING (S²
In this section, we describe the functioning of our proposed exact unlearning framework, Sequence- aware Sharded Sliced Training (S* This framework leverages parameter-efficient fine-tuning (PEFT) to build an exact unlearning framework.
3.1 PROBLEM SETTING
We consider the general setting where the user fine-tunes pre-trained model like BERT (Devlin et al., 2019) or Llama (Touvron et al., 2023) on private data using PEFT techniques. We assume that the deletion requests affect only the private fine-tuning data, not the pre-training data. In S²T we partition a dataset D = =DD P into m disjoint shards. Each shard is further divided into L slices: D.- {S1,.. .3, Sz). S trains separate model per shard and uses their aggregate decision.
Existing unlearning frameworks SISA (Bourtoule er al., 2021) use a similar setup described above. In SISA. within each shard, the model trained in multiple stages sequentially on the slices (training stages are Slice 1, Slice 1+2, and so on), and their checkpoints are stored. However, a key weakness of SISA is that if deletion requests affect Slice 1 of all shards, then the entire service goes down necessitating retraining from scratch. Another drawback of SISA is that individual models within the ensemble need to be retrained whenever a deletion request is executed. Retraining even on single slice is expensive for large-scale models in production serving a huge customer base. A naive alternative would be to use the last known usable checkpoint and perform retraining after regular intervals. For example, in Figure/ (right), if deletion request arrives for data instance in Slice the model in production can be replaced with the checkpoint obtained after Slice It is easy to see that the performance of the overall model will degrade with the number of deletion requests.
3

---

Published as a conference paper at ICLR 2025
Sequential Slice-wise Training
Deletion Strategy
Slage
y
Stage 2
V
Stage L
Si
x
S2
x
W:
S1
Ws
Wi
X1 P
S2
S4
Wa
W;
W2
x
Ss
X
S3
X
Ss
x
S/4
S
8/g
Wz
Wz
SW
x
8s
S1
1
(1)
(2)
(3)
Figure 2: (Lefft) We show the schematic diagram of the slice-wise training strategy in S We incrementally train the model n layer (from the top) using slices S while keeping the other layers fixed. (Right) We show the impact of deletion on models trained on different permutations of slices.
We present an exact unlearning framework, S to address these challenges. The core idea involves training several copies of each model (within the ensemble) using different slice sequences. When deletion requests occur, utilize the model that minimizes performance degradation. To further reduce the training cost, we leverage PEFT techniques and present a novel sequential dise fine- tuning strategy in Section 3.2. Our training strategy allows to use the same model by deactivating certain layers without the need to swap checkpoints in case of a deletion. In the following sections, we introduce the fine-tuning strategy and sequence selection process.
3.2 SEQUENTIAL SLICE-WISE TRAINING
In this section, we introduce Sequence- aware Sharded Sliced Training (S² a lightweight fine-tuning approach using parameter-efficient fine-tuning (PEFT) for efficient exact unlearning. This fine-tuning approach enables parameter isolation by sequentially training PEFT layers using different data slices. Due to this parameter isolation, it is possible to efficiently handle deletion requests by deactivating layers associated with the instance.
We describe T using the PEFT technique, LoRA (Hu et al., 2021), but our method is general can be casily extended to other PEFT techniques. LoRA introduces a small number of trainable low-rank (r < d) parameters, (X, Y), while the pre-trained weights W remains fixed as shown below:
W W YY, where X, Y E Re W RRax
(1)
Our key idea involves training different LoRA layers using different data slices. This approach allows us selectively deactivate (zero out) the LoRA parameters (X Y) associated with particular layer in the event of data deletion from that slice. In Figure 2 (left), we illustrate the training process in detail, where we follow a sequential top-to-bottom training approach. At stage 1, we train the final model layer (Layer in the figure) using slice while LoRA parameters from all other layers are switched off. In the next stage, we train second last layer (Layer 2) using slices & while keeping the LoRA parameters from the Layer 1 frozen. This process continues for the rest of the layers. Note that the training does not need proceed in a single layer-wise fashion, we can even train multiple LoRA layers per slice. We discuss more details about the design choice in Appendix C.2.
The sequential slice- dise training process ensures that the LoRA parameter updates at the i-th layer are a function of the data instances within slices iI. Therefore, if deletion request affects the i-th slice, the same model can still be used by deactivating the LoRA parameters corresponding to slices (i...., L} (see details in Algorithm 4). For example, if deletion request affects slice S3 only the subsequent LoRA layers need to be deactivated to ensure exact unlearning, as shown in the first example of Figure 2 (right). This is because during training the parameters of layers I & were not affected by instances in Sy. During this deletion process, we use the same model checkpoint and switch off LoRA layers, resulting in an L-time reduction in storage cost compared to SISA.
4

---

Published as a conference paper at ICLR 2025
Slices I. 3. Budget
Iterative Cyclic Rotation
[B = L]
[B >
L
S
S+
S
S
S2
S
S
S
S₂
S
S
S
S
S
S
S
S
S
S
S
S₂
S
S
S
S
S
S:
S
S:
S
S:
Figure 3: Illustration of the slice sequence selection problem with uniform deletion prior under a budget constraint, B. (Left) An example of a permutation tree with I. = 3 and a diverse set of sequences for budget B = 3 shown in green. (Center) We show the functioning of the cyclic rotation algorithm, where we generate cyclic permutations of the original sequence. (Right) We iteratively extend the algorithm when budget > L by generating cyclic rotations of the subsequences.
Now we consider the scenario where deletion requests affect multiple slices. This is shown in the 2nd sequence of Figure 2 (right), where slices Si and S3 are affected. In this case, we observe that model trained on the default ordering of the sequence {S S3} is rendered useless when S and S3 are affected. This motivates us to train multiple models using different permutations of the slices. This would enhance the service time and system performance by selecting a model trained with the most effective ordering (e.g., the 3rd sequence in Figure 2 (right) yields the best-performing model). However, training on all L! slice permutations is prohibitively expensive. In the following section 3.3, we present strategies to select diverse set of permutations under budget constraints. Using these selection approaches, in Section 3.4 we theoretically show that we do not need more than L sequences achieve the optimal deletion performance.
3.3 TRAINING UNDER BUDGET CONSTRAINTS
The training strategy discussed in the previous section requires training the same model on L! slice sequences, which is expensive in practice. In this section, we discuss strategies to select sequences under a budget, B (maximum number of sequences that can trained). First, we show that there exists an optimal subset of B slice sequences and randomly selecting B sequences may not be effective. To illustrate this idea, we use permutation tree (Bhattacharya, 1 1994), where all possible permutation sequences are embedded into a tree structure.
In Figure 3 (left), we show an example of a permutation tree with L = 3 slices, paths from the root to the leaves correspond to unique permutation sequences (S1, S2 53). (Si, S3, S2), and so on. From the previous section, we know that the topmost slice is the most sensitive because if a deletion request affects the topmost slice the entire model needs to be retrained (shown in Figure (right)). To address this and reduce the retraining cost, should ensure train models on sequences with different top slices. Building on this intuition, in the general setting we should train the model on diverse permutation sequences. Two sequences position, e.g., (S,,S2, 53) and (S2, S3, 51). An example is illustrated in Figure 3 (left), where a diverse set of sequences is marked in green (where no identical slices occupy the same position). Selecting diverse permutations is challenging as relying solely on random sampling may not always yield the best results. Moreover, in certain scenarios, it is possible have prior knowledge about the deletion probabilities of data slices; for example, younger users might be more likely to request data deletion than older users. Therefore, we present two strategies for selecting diverse permutation sequences for budget B, depending on whether or not prior deletion probabilities are available.
considered diverse if no element appears at the same
Uniform Deletion Prior. In the setting, where each slice has a uniform (or unknown) deletion prior, we can generate diverse sequences by using eyclic permutations of the original sequence. Given a sequence (51, S2, S2), the cyclic permutations are (shown in Figure 3 (middle)):
(S1, S2, S3) + (Sy, S1.55 + (S2, Sz, S1).
The above approach guarantees that no element is repeated in the same position. However, it can only generate up to L different sequences. For budget B > L. we extend the cyclic rotation algorithm to generate more sequences. In Figure 3 (right), we generate new sequences by iterating over the
5

---

Published as a conference paper at ICLR 2025
Step 1
Step 2
Step
Step
2
3
0.4
0.3
0.2
0.1
3
score([2 10) scorelit, scorelf4, 31) scoreti3,
Edge Weights
Selected Slice Sequences
Illustration of the BMS algorithm. BMS selects one element for each permutation at a time. This is done by constructing a bipartite graph with all feasible edges to the next node, where edge weights are the current sequence scores. We compute the maximum weight matching on this graph. The dark gray arrows (-+) indicate the selected edges and dotted arrows (--> ) the feasible ones.
Figure 4:
existing sequences and performing cyclic rotations of the subsequences. For example. for (S1, S2, S3) perform cyclic rotation of the 2nd and 3rd clement to obtain the sequence: (S1, Sg. S2) (more examples in Figure 10). We provide the general iterative cyclic rotation algorithm in Appendix B.
Non-uniform Deletion Prior. In scenarios, where have prior knowledge of the deletion probabil- ities, sequences generated by cyclic rotation may not be ideal. For example, consider the deletion probabilities are: (S1: 0.5, S2: 0.4, S3: 0.1). Then, the first sequence in Eq. is bad choice because two of the slices most likely to be deleted are placed at the top. It is possible to select better sequences while satisfying the diversity criteria (no repeated slices the same position). Before describing the selection algorithm, we show how to evaluate the quality of a sequence. We evaluate a sequence with deletion probabilities: (p1....,PL) PL) by computing the expected number of functioning slices
after / deletions: score|S, = - d. (1 (1- E1-E)m1)) where / is a hyperparameter.
We present bipartite-matching based sequence (BMS) selection algorithm. We will provide an intuitive explanation of the algorithm here and refer to Appendix B.2 for complete details. illustration of BMS shown Figure BMS iteratively selects elements of sequences by constructing bipartite graph between one level to the next one (where edges are incident on feasible elements for the current sequence). The edges are weighted by the score of the current sequence, (S, Selecting the next element then is equivalent to finding a maximum weight perfect matching (Galil, 1986) using the Hungarian algorithm (Kuhn, 1955) shown by the bold lines in Figure 4. This continues till all sequences have L elements. The BMS algorithm can generate up to L sequences. For a budget B > L, we use conditional sampling to randomly generate sequences according to their deletion probabilities (see details in Appendix B.2).
Overall Workflow. So far, we have discussed the sequential training procedure and the sequence selection approach within budget. Here, will bring all of the components together and illustrate the functioning of S²T using a simple example. We consider a setting with m = 3 shards, I, = slices, and budget 4. Initially, for every shard, the available models are trained on sequences:
(1, 2, 4), (4, 1, 2, (3, 4, 1), 42
Next, if deletion request affects slice I for the 3rd shard. Then, the available models for the 3rd shard are: (4), (3, 4), (2, 3, 4). Notice how all the PEFT layers at or below slice 1 have been switched off. In this scenario. S doesn't 't perform any retraining but continues to function with the best available model: (2, 3, 4) (as it is trained on maximum slices). If the following deletion requests affect slice 2, then the available models are: (4), (3, 4). S continues to function with the best model (3, 4). This continues until no models are available in any shard, at which point S is retrained from scratch.
3.4 THEORETICAL ANALYSIS
In this section, we theoretically analyze the performance of exact unlearning system. For this, we draw inspiration from approximate unlearning literature (Sekhari al., 2021) and introduce the definition of deletion rate for exact unlearning systems.
Definition 1 (Deletion Rate). The deletion rate, 5(S). of an exact unlearning system S, is the expected number of deletion requests until the system needs to be retrained from scratch.

---

Published as a conference paper at ICLR 2025
The deletion rate captures the effectiveness of an exact unlearning system by quantifying the expected number of deletion requests it can handle. Next, we theoretically quantify the deletion rate for S'T and compare it with that of SISA.
Lemma 1. For uniform deletion prior and dataset size N > T, where is the number of dele- tion requests, the deletion rate of T 8(S²T) O(mL O (m min(B, L))) and for SISA it is ((IIAA) ~ O log m.), where m is the number of shards and L is the number of slices per shard.
The above result states that the deletion rate doesn't ''t improve by increasing the budget B beyond This shows that the optimal deletion rate can be achieved using only I. sequences (instead of L!!. The complete proof is presented in Appendix A.
Next, we analyze the impact of deletion requests on the system's 's performance. We perform fine- grained analysis focusing on the performance of an individual shard. this setting, we consider the real-world scenario where we do not retrain every time slice is impacted instead work with the best available model. For S this means switching off the necessary PEFT layers, while for SISA, means reverting to the best available checkpoint. The unlearning system experiences performance degradation with an increasing number of deletion requests, as we are compelled to utilize a model trained on fewer data slices (we show this empirically in Section 4.2). To quantify the performance retention we use a monotonically increasing function F(k), which indicates a model's performance when trained & slices. The exact formulation of F-(-) depends on several factors like the dataset, model size, etc. We analyze the performance retention while processing deletion requests.
Lemma (Performance Retention). Given a set of randomly selected B > sequences and uniform deletion prior of slices, the difference in the probubility that shard retains performance, F-(-) of at least (l) after r deletion requests, between S and SISA, is shown below
Vk: E [1. [1...]], L), (F)(S)) 2 F()) - (F.(SA)))) 2 F(()]= 5(1 - (
(3)
where Ç - 1 - (1 -1-kk k/L)" is a positive fraction and B' = min { { (1 (L-N))
(1
The above result demonstrates that compared to SISA, S significantly enhances performance by increasing the probability that the system maintains at least F(k) performance. Eq. shows that increasing the training budget B helps improve the performance of the unlearning system. The proof presented in Appendix A.2. Another takeaway from the above lemma is that ensure the system performance of F(k), there is no point in increasing the budget B beyond 1
[L-
4 EXPERIMENTS
In this section, outline the experimental setup and evaluate the unlearning performance of S across various setups. The goal of the experiments is to evaluate the functioning of individual components and the unlearning capabilities of S² Specifically, we design experiments to answer the following research questions:
(RQ1) Does S training (Section 3.2) impact the model's performance compared to full training?
(RQ2) Does S enhance the deletion capabilities of unlearning, and what is its cost tradeoff?
(RQ3) Is the sequence permutation selection algorithm (Section 3.3) effective in practice?
4.1 SEQUENTIAL SLICE- WISE TRAINING PERFORMANCE
In this section, we evaluate the effectiveness of slice-wise training. The objective of the experimental setup is to demonstrate that S can achieve performance comparable to full training. Note that S is not designed as new fine-tuning technique that outperforms the baselines. The goal of S is to achieve parameter isolation for data slices without impacting the overall performance. We perform range of experiments with different Transformer model sizes ranging from 86M up to 13B. We provide the details of the experimental setup and hyperparameters in Appendix C.I.
In Figure 5, report the performance of fine-tuning vision, GLUE, and SuperGLUE benchmarks. We use ViT (Dosovitskiy et al., 2020) (for CIFARIO & CIFAR100 (Krizhevsky et al., 2009)), ViT ViTlaRGE (for Tiny ImageNet (Le & Yang, 2015)), and RoBERTa (Liu et al., 2019) (for
7

---

Published as a conference paper at ICLR 2025
Model
MMLU
HellaSwag
PIQA
Winogrande
ARC-c
ARC-e
TruthfulQA
OBQA
Llama2-7B
41.3
76.0
79.1(1.)
69.1c.3)
46.3
74.6,99)
39.0c.a
44.2,22)
Llama2-7B (FT)
43.3
77.40.4)
79.9
69.6(.3)
50.40.5)
74.7
46.3
46.8,22)
Llama2-7B (SPT)
43.6
m7.7
79.7,o9
70.5
51.4..5
74.1a0
43.0
46.4,2
Llama2-13B
50.5
79.4g..
80.5
72.2(1.3)
49.0
77.5
36,91.
45.2gm
1aB (FT)
51.8
8..3
82.0
72.2
55.0
79.3
38.8
46.622.2)
Llama2-13B (S'T)
51.6,0.4)
80.9,.44
81.8,0
72.8.13)
54.5
80.6,ax)
39.6.1.5
46.2
Llama3-8B
62.2.0.4)
y9.1
80.6 60,6,0.)
73.6
53.2.15)
77.6,09)
43.91.4
45.0(22)
Llama3-8B (FT)
59.2.0.4)
p0.8
80.9
72.2(1.)
(9.0
79.6
46.621.6
46.8(22)
Llama3-8B (S"T)
59.6g.4)
80.2
82.4
73.8
57.0
80.5
48.5(1.))
47.0kam
Table 1: Performance comparison of LLMs before and after instruction tuning using Alpaca dataset.
We report the performance of Llama2-7B. Alama2-13B, and Llama3-8B models for the following settings: pre-trained model, full training (FT), and slice-wise training (S* We observe S achieves comparable performance to FT, even outperforming FT's performance in several datasets. This shows that S allows parameter isolation without affecting the task performance.
Vision
GLUE
SuperGLUE
SPT Training
100-
100-
100
Performance
80
40
CIFAR1O Tinylnagenet
60
SST2
QNL
40
COPA
BoolQ
Comparison of the performance between slice-wise training and full training on vision datasets and GLUE & SuperGLUE benchmarks. We report the overall Matthew's 's correlation for CoLA, Pearson correlation for STS-B, and accuracy for other tasks. We observe that slice-wise training achieves similar performance to full training across all datasets.
Figure 5:
GLUE (Wang et al., 2018)& & SuperGLUE (Wang et al., 2019)). We observe that S achieves comparable performance full training (FT) across all settings. In some of the settings, also observe that S is able to outperform FT (e.g., S obtains 2.5% accuracy gain on TinyImagenet using Vi ViT-larrge rge). Next, we conduct experiments evaluate the effectiveness of S²T while using large language models (LLMs). Specifically, we perform instruction tuning of Llama2-7B (Touvron al., 2023), Llama2-13B. and Llama3-8B using Alpaca dataset (Taori et al., 2023). Then, we evaluate each instruction-tuned model on a range of tasks to evaluate the model's general/world knowledge (MMLU (Hendrycks et al., 2020), OpenBookQA (Mihaylov et al., 2018)), truthfulness in QA (TruthfuQQA (Lin et al., 2022)). and commonsense reasoning (PIQA (Bisk et al., 2020), HellaSwag (Zellers et al., 2019), Winogrande (Sakaguchi et al., 2021), ARC (Clark et al., 2018)). We use LLMeevaluation suite (Gao et al., 2023) report the zero-shot performance for all datasets. Similar to the previous setup, in Table I. we observe that S achieves comparable performance to full finetuning across all datasets and even outperforms FT many datasets across different model sizes. These experiments provide the answer to (RQ1) demonstrating that S is an effective way to fine-tune Transformer models, enabling to achieve parameter isolation for data slices without impacting the model's performance.
4.2 DELETION PERFORMANCE
In this section, we evaluate the performance of S as deletion requests are received. In Figure 6 (left), we report the performance of S SISA (Bourtoule al., 2021), and ProtOSISA (Yan et al., 2022) on CIFAR-10 and 100 datasets (all systems use = 5 shards, L = 4 slices). In this experiment, we consider a uniform deletion prior over all slices. We also report the performance full re-training, which retrains the model after each deletion request and serves as an upper performance bound. We report S S'T's performance under various budgets. We observe that S can achieve very close performance to the full budget (B 24) with significantly smaller budget, B 4. For SISA and PIotoSISA, we observe that the plot ends after approximately 40 deletion requests as these systems do not have functioning models beyond this point. We observe that S can handle more deletion
8

---

Published as a conference paper at ICLR 2025
CIFAR-10
CIFAR-100
59
68.75
m
2500
68
Accuracy (%)
SPT (Budgetm8)
Deletion Rate
69.25-
5 (Bangetm4)
98.00-
SISA
5 (Full Budget)
2500
07.75
Proto SISA
Rutl training
1000
97.50
07.25
M
500-
5 (m 5, 64)
07.00
25
40
62
to
10
60
10
10
20
30
40
50
60
Number of Deletion Requests (m 5, I. 4)
Budget
Figure 6: (Left) We report the impact on performance of S and baselines with an increasing number of deletion requests. We observe that S can handle a higher number of deletion requests while maintaining high performance with relatively low budget (Ø) indicates the failure points). (Right) We report the deletion rate of S with an increasing budget and observe steady growth.
1297
S Bound
SISA Bound
2000
(Busget
(Bucget
1750
5"T (lusiet 14)
6 (ludget 140
Deletion Rate
1002
1200
dlusget
(Budget
800
Studget
Shunget
002
1250
2.3x
SISA
1000
3x
692
750
000-
432
1.6x
207
515A
S (B-8)
SPT (8-32)
Number of Shards
Number of Slices
Figure 7: We report the deletion rate of S and compare it with baselines. (Left) We compare the deletion rates of ST under varying budgets with SISA and observe significant gains. (Center) We report the deletion rates with an increasing number of shards and (Right) an increasing number of slices. In both scenarios, we observe that S' deletion rate grows significantly faster than SISA.
requests while consistently outperforming the baseline approaches. Note that increasing the budget B > L does not help improve the deletion rate but increases the probability of a better-performing model (as observed in Lemma 1).
Next, we extensively evaluate the impact of increasing the training budget B on the deletion rate (with m 5 shards & L = 64 slices). In Figure 6 (right), observe that there is a steady growth in the deletion rate with an increasing budget. The growth is slightly higher in the initial stages when the budget is low and slows down gradually. This experiment helps answer (RQ2) and provides empirical evidence to our theoretical result Lemma 2, which claims that the performance improves with an increased budget.
4.3 ANALYSIS
In this section, conduct analysis experiments to evaluate different components within S We also report several other analysis experiments in Appendix C.3.
Deletion Ablations. We evaluate the deletion capabilities of S and compare with the theoretical bounds. In Figure 7 (left), we report the deletion rate of S²T and SISA for the setup (with m 5 shards, L == 32 slices). We observe that with small budget B S can achieve 1.6x gains in the number of deletion requests handled, We also plot the theoretical bounds derived in Section 3.4 and show that they hold in practice.
In Figure 7 (center & right), we report the model performance with varying shard and slice counts. As expected, we observe that both increasing the shards and slicing the data more helps in improving the deletion performance. However, the rate of growth in deletion rate is more significant for S resulting up to 2.3x and 3x gains over SISA for the same number of shards and slices respectively.
9

---

Published as a conference paper at ICLR 2025
Slices /.
Budget = I.
Budget B I.
Cycli Rotation
350
BMS
Avg. Edit Distance
Samp ing
Avg. Edit Distance
300
Conditional Samping
Optimal y =
Scorc(S,
200-
30-
150-
Mmmwy
20-
BMS
50
10
Conditional Sampling
40
100
20
20
30
40
Budget (8)
Slices (T.)
Slices (f.)
Figure 8: We evaluate the performance of iterative cyclic rotation and bipartite matching- based selection (BMS). (Left) We observe that cyclic rotation selection consistently outperforms random sampling for all budgets, 1 S B < 120 (with fixed L = 5). (Center) We evaluate the average edit distance of the sequences generated by BMS and observe that it achieves the optimal edit distance (L). (Right) We also observe that sequences from BMS achieve higher scores than random sampling.
Sequence Selection. We evaluate the quality of the sequences generated by the iterative cyclic rotation and BMS algorithm (Section 3.3). Ideally, we want the selected sequences be diverse and should have a high edit distance between sequences. Therefore, report the average edit distance within selected subset, O: Enco [dotit (o, o')]. First, we consider the setting where the deletion prior is uniform and compare cyclic rotation with random sampling. In Figure 8 (left), we report the average edit distance with varying budget (B) while the slice count (I.) is fixed. We observe that cyclic rotation produces significantly better sequences than random sampling. Second, we consider slices associated with a deletion prior. We present the results by averaging over 10 deletion priors sampled from Dirichlet distribution. In Figure 8 (center right), we observe that BMS consistently outperforms random sampling both in terms of diversity (avg. edit distance) and chosen sequence scores (score Ss, f).. These experiments help answer (RQ3), showcasing the effectiveness of the proposed sequence selection algorithms in practice.
10a
25x
Total Time
102
2.8x
10a
SISA
S S (B
Full Re-training
10
0
200
400
600
B00
1000
Number of Deletion Requests
Figure 9: We compare the deletion time as the number of deletion requests increases. S requires the lowest deletion time com- pared to SISA and full re-training.
Deletion Time. Unlearning in S is cost-effective; it primarily involves selecting the best checkpoint and swapping it with the current one. The main cost is incurred when a large number of deletion requests necessitate re-training from scratch. In Figure 9, we report the total deletion time (in hours) as the number of deletion requests increases, which includes the checkpoint swapping and re-training time. In this experiment, we compare the deletion time of S with SISA and full re-training on CIFAR10 dataset. Full re-training retrains the model after each deletion request. For SISA and S the step jumps indicate that the system requires retraining. Overall, SºT achieves the lowest deletion time. S'T reduces the total deletion time (after 1000 requests) by 2.8x compared to SISA and 25x compared to full retraining. This experiment shows the efficacy of S in reducing the deletion time.
CONCLUSION
In this paper, we introduced S²,, an effective framework for performing exact unlearning. S uses modular machine learning model that trained using disjoint shards of the data. Each shard used to train different model using a lightweight fine-tuning approach that enables parameter isolation, which allows us to execute unlearning requests efficiently. The key idea behind S is to train multiple models using different sequences of slices before deploying the system. This helps reduce retraining costs and improve the model's performance while the model is in production. Both theoretically and empirically, show that S has significantly improved deletion capabilities compared to existing approaches. Future work can focus on developing techniques for finer-grained parameter isolation to further improve S3 performance.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
We have submitted the implementation of S in the supplementary materials. We have extensively discussed the details of our experimental setup, datasets, baselines, and hyperparameters in Section and Appendix C. We have also provided the details of our training procedure and sequence selection algorithms in Appendix B. We will make our implementation public once the paper is published.
ETHICS STATEMENT
In this paper, introduce exact unlearning framework, S to enable the efficient unlearning of training data from large-scale models. S has been developed to enable users to remove the impact of private and harmful data from ML models. However, it is crucial to assess whether the deletion requests are initiated by legitimate users. An adversarial user could exploit this feature to degrade the model's performance. In work, use publicly available datasets and open-sourced models.
ACKNOWLEDGMENTS
The authors thank Anneliese Brei, Anvesh Rao, Archiki Prasad, Haoyuan Li, Nicholas Monath, Rajeev Ambati, Rakesh Menon, Shounak Chattopadhyay. and Vinayshekhar Bannihatti Kumar for helpful discussions and feedback on the draft. This work was supported in part by NSF grant DRI.-2112635.
AUTHOR CONTRIBUTIONS
SBRC proposed the unlearning idea, conducted all the experiments, and led the project. KC proposed the diverse permutation selection algorithm using bipartite graph matching. AS contributed to deriving the theoretical results and designing the empirical studies. AD and SC provided ideas and served as project advisors, offering extensive assistance in organizing the manuscript. All authors contributed the writing of the manuscript.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.085 03.77777777. 2023.
Alessandro Achille, Michael Kearns, Carson Klingenberg, and Stefano Soatto. Ai model dis- gorgement: Methods and choices. Proceedings of the National Academy of Sciences, 121(18): e2307304121, 2024.
Nasser Aldaghri. Hessam Mahdavifar, and Ahmad Beirami. Coded machine unlearning. IEEE Access, 9:88137-88150, 2021.
P Bhattacharya. The representation of permutations by trees. Computers & Mathematics with Applications, 28(9):67-71, 1994.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. arXiv preprint arXiv: 2389,6.99.... 2012.
Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. Piqa: Reasoning about physical commonsense natural language. Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 7432-7439, 2020.
Gunnar Blom, Lars Holst, and Dennis Sandell. 7.5 coupon collecting i, 7.6 coupon collecting ii, and 15.4 coupon collecting iii. Problems and Snapshots from the World of Probability, New York: Veringgr-Verlag, pp. 85-87, 1994.
Lucas Bourtoule, Varun Chandrasekaran Christopher A Choquette- Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 2021 IEEE Symposium Security and Privacy (SP), pp. 141-159. IEEE, 2021.
11

---

Published as a conference paper at ICLR 2025
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020. 2020.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE symposium on security and privacy, pp. 166.-80. IEEE, 2015.
Jiaao Chen and Diyi Yang. Unlearn what you want to forget: Efficient unlearning for llms. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv preprint arXiv:/803.05457, 2018.
Jacob Devlin, Ming- Wei Chang, Kenton Lec, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Pupers). pp. 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 10.18653/v1/N19- 1423. https / ac www.:caannhoooooooooooooooo 9-4233.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x 6 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2020.
Yonatan Dukler, Benjamin Bowman, Alessandro Achille, Aditya Golatkar, Ashwin Swaminathan, and Stefano Soatto. Safe: Machine unlearning with shard graphs. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 7108-11718, 2023.
Ronen Eldan and Mark Russinovich. Who's 's harry potter? approximate unlearning in Ilms. arXiv preprint arXiv:2310.02238, 2023.
European Parliament and Council of the European Union. Regulation (EU) 2016/679 of the European Parliament and of the Council. URL https:
europa
679/
oj.
Zvi Galil. Efficient algorithms for finding maximum matching in graphs. ACM Computing Surveys (CSUR), 18(1):23-38, 1986.
Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding. Jeffrey Hsu, Alain Le Noac'h, h. Haonan Li, Kyle McDonell, Niklas Muennighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopi, Aviya Skowron, Lintang Sutawika, Eric Tang, Anish Thite, Ben Wang. Kevin Wang, and Andy Zou. framework for few-shot language model evaluation, 12 2023. URL https: zenodo. org/ reworde/osssee 10225686..6
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Etemaal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9304 9312, 2020a.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. In European Conference on Computer Vision, pp. 383-398, 2020b.
Aditya Golatkar, Alessandro Achille, Ashwin Swaminathan, and Stefano Soatto. Training data protection with compositional diffusion models. arXiv preprint arXiv:2308.01937. 2023.
Laura Graves, Vineel Nagisetty, and Vijay Ganesh. Amnesiac machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 1 11516-11524, 2021.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference on Machine Learning, pp. 3832-3842. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2025
Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed SharifiMMalvajeret and Chris Waites. Adaptive machine unlearning. Advances in Neural Information Processing Systems, 34:16319- 16330, 2021.
Jamie Hayes, Ilia Shumailov, Eleni Triantafillou, Amr Khalifa, and Nicolas Papernot. Inexact unlearning needs more careful evaluations to avoid a false sense of privacy. arXiv preprint arXiv:2403.01228. 2024.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In International Conference on Learning Reprexentations, 2020.
Edward Hu, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang. Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. In International Conference Learning Representations, 2021.
Jinghan Jia, Jiancheng Liu, Parikshit Ram, Yuguang Yao, Gaowen Liu, Yang Liu, Pranay Sharma, and Sijia Liu. Model sparsification can simplify machine unlearning. arXiv preprint arXiv:2304.0493. 2023.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pp. 1885-1894. PMLR, 2017.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-93 97, 1955.
Vinayshekhar Bannihatti Kumar, Rashmi Gangadharaiah, and Dan Roth. Privacy adhering machine un-learning in nlp. In Findings of the Association for Computational Linguistics: IJCNLP-AACL 2023 (Findings), pp. 268-277, 2023.
Meghdad Kurmanji, Peter Triantafillou, Jamie Hayes, and Fleni Triantafillou. Towards unbounded machine unlearning. Advances in Neural Information Processing Systems, 36, 2024.
Jeffrey Lagarias. Euler's constant: Euler's work and modern developments. Bulletin of the American Mathematical Society, 50(4):527 628, 2013.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
Stephanie Lin, Jacob Hilton, and Owain Evans. TruthfulQA: Mcasuring how models mimic human falsehoods. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 3214 3252, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10. 10.118663/11/2022.aclllll 229.
URL https: http::::///alaaahhlooooooo
awl-
Jiaqi Liu, Jian Lou, Zhan Qin, and Kui Ren. Certified minimax unlearning with generalization rates and deletion capacity. Advances in Neural Information Processing Systems, 36, 2024a.
Sijia Liu, Yuanshun Yao, Jinghan Jia, Stephen Casper, Nathalie Baracaldo, Peter Hase, Xiaojun Xu, Yuguang Yao, Hang Li, Kush Varshney, et al. Rethinking machine unlearning for large language models. arXiv preprint arXiv:2402.08787, 2024b.
Yinhan Liu. Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis. Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: /907. 1692, 2019.
Jakub łucki, Boyi Wei, Yangsibo Huang, Peter Henderson, Florian Tramèr, and Javier Rando. adversarial perspective machine unlcarning for ai safety, arXiv preprint arXiv:2409.18025 2024.
Alessandro Mantelero. The eu proposal for a general data protection regulation and the roots of the "right to be forgotten'. Computer Law & Security Review, 29(3):229-233 2013.
13

---

Published as a conference paper at ICLR 2025
Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. Can suit of armor conduct electricity? new dataset for open book question answering. In Conference on Empirical Methods in Natural Language Processing, 2018. URL https://apa http:///pp..smaaiiio.oe. www.ttcscchoaaa.ooooo...........
CorpusTD: ID: 5377777
Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajerde Descent-to-delete Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pp. 931-962. PMLR, 2021.
Thanh Tam Nguyen, Thanh Trung Huynh, Phi Le Nguyen, Alan Wee-Chung Liew, Hongzhi Yin, and Quoe Viet Hung Nguyen. A survey of machine unlearning. arXiv preprint arXiv:2209.02299 2022.
Yong-Hyun Park, Sangdoo Yun, Jin-Hwa Kim, Junho Kim, Geonhui Jang, Yonghyun Jeong, Junghyo Jo, and Gayoung Lee. Direct unlearning optimization for robust and safe text-to- exxttto-image models. arXiv preprint 20Xiv:240..21035, 2024.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Vaidehi Patil, Peter Hase, and Mohit Bansal. Can sensitive information be deleted from Ilms? objectives for defending against extraction attacks. In The Twelfth International Conference on Learning Representations, 2023.
Adnan Qayyum, Junaid Qadir, Muhammad Bilal, and Ala Al-Fuqaha. Secure and robust machine learning for healthcare: A survey. IEEE Reviews in Biomedical Engineering, 14:156-180, 2020.
Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: adversarial winograd schema challenge at scale. Communications of the ACM, 64(9):99-106, 2021.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34: 00188875118888 2021.
Supreeth Shastri, Melissa Wasserman, and Vijay Chidambaram. The seven sins of (Personal-Dade processing systems under {GDPR). In 1Ith USENIX Workshop on Hot Topics in Cloud Computing (HorCloud 19), 2019.
Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data poisoning attacks. Advances in neural information processing systems, 30, 2017.
Harry Surden. Machine learning and law: An overview. Research Handbook on Big Data Law, pp. 171-184, 2021.
Vinith Suriyakumar and Ashia C Wilson. Algorithms that approximate data removal: New results and limitations. Advances in Neural Information Processing Systems, 15:18892-18803. 2022.
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An follloiion llama model. 2023.
https: http:://gitee httpt/gttbbb.t///// com/cottuu Lab/ st
Ayush K Tarun, Vikram S Chundawat, Murari Mandal, and Mohan Kankanhalli. Fast yet effective machine unlcarning. IEEE Transactions on Neural Networks and Learning Systems, 2023a.
Ayush Kumar Tarun, Vikram Singh Chundawat, Murari Mandal, and Mohan Kankanhalli. Deep regression unlearning. In International Conference on Machine Learning, pp. 33921-33939. PMLR, 2023b.
Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk. Andrew M Dai, Anja Hauth, et al. Gemini: a family highly capable multimodal models. arXiv preprint arXiv:2312. 1805, 2023.
14

---

Published as a conference paper at ICLR 2025
Anvith Thudi, Hengrui Jia, Ilia Shumailov, and Nicolas Papernot. On the necessity of auditable algorithmic definitions for machine unlearning. In 3/st USENIX Security Symposium (USENIX Security 22), pp. 4007-4022, 2022.
Nobuaki Tomizawa. On some techniques useful for solution of transportation network problems. Networks, 122)1133-19, 1971.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprini arXiv:2307.09288 2023.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 353-355, 2018.
Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Superglue: stickier benchmark for general-purpon language understanding systems. Advances in neural information processing systems, 32, 2019.
Cheng-Long Wang, Qi Li, Zihang Xiang, and Di Wang. Has approximate machine unlearning been evaluated properly? from auditing to side effects. arXiv preprint arXiv:2403. 2024.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, al. Huggingface's transformers: Statc-of the-art natural language processing. arXiv preprint arXiv:1910.037771 2019.
Heng Xu, Tianqing Zhu, Lefeng Zhang, Wanlei Zhou, and Philip S. Yu. Machine unlearning: A
survey. ACM Comput. Surv, 56(1), aug 2023. ISSN 0360-0300. doi: 10. 00.1145/360620. URL. https://doi. 2trg/10.. 111111361666362
Jie Xu, Zihan Wu, Cong Wang, and Xiaohua Jia. Machine unlearning: Solutions and challenges.
IEFE Transactions on Emerging Topics Computational Intelligence, 2024.
Haonan Yan, Xiaoguang Li, Ziyao Guo, Hui Li, Fenghua Li, and Xiaodong Lin. Arcane: An efficient architecture for exact machine unlearning. IJCAI, volume pp. 19, 2022.
Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can machine really finish your sentence? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 4791-4800, 2019.
Ruiqi Zhang, Licong Lin, Yu Bai, and Song Mei. Negative preference optimization: From catastrophic collapse effective unlearning. arXiv preprint 4004 240400888, 2024.
15

---

Published as a conference paper at ICLR 2025
A MATHEMATICAL PROOFS
CONTENTS
A.I Proof of Lemma
16
A.2 Proof of Lemma
17
A.3 Proof of Lemma
17
A.1 PROOF OF LEMMA
In S since the sequences are selected to be diverse (Figure 4), the topmost slice in each sequence is different. Therefore, we have B' min(B, L) different slices at the topmost position. This implies that for T to encounter service failure, total of mB' slices must be affected by deletion requests, where m the number of shards. Considering deletion requests affect all slices uniformly we need to compute the expected time till all slices affected. This setup is similar the coupon collector problem (Blom et al., 1994).
Proof. The deletion rate is the expected number of requests to delete all mB slices (m shards, B' unique slices per shard). Using linearity of expectation, the deletion rate total time is:
8(S = ETT] = E1[t +... ... + tm [[t1] +... E.mBl
(5)
where E[4,] 1/pt, where p; the probability that the i-th slice is affected after (i 1) slices deleted. Let N = (D) the dataset size and r be the number of deletion requests seen so far. The expression of p; is shown below:
P: {mB' (d-1)]88
(6)
N-r
N Nmin(B/ (B/ L, 1) 1)86 P:
(7)
N T
P: min(B/L, 1) (i 1)/(mL)
(8)
1 rr/N
mB' (i - P
(9)
mL
where s; the size of each slice. Replacing this result in Eq. 5, we get:
mL mB -0 mB'
mL
mL 1
8(ST)) <
+
(10)
mL
+
+
(11)
2
mB
mL. HmL
(12)
1
L
-L log + ymL + +0
(13)
mB
where HmB denotes the mB'-th Harmonic number and is the Euler's constant (Lagarias, 2013).
The above result proves the first portion of the lemma, 6(S*T) ~ O(mL logmB').
The second part of the lemma is about SISA. For SISA to experience failure, only the first slice of each shard (total of m slices) needs to be affected by deletion. this case, we can write:
(m (i 1)}80
N/L (i 1)sb
1 1 (i 1)/m m (i 1)
(14)
N -
N
L(1 L(1-T/N)
mL
16

---

Published as a conference paper at ICLR 2025
Replacing the above result in Eq. 5, we get:
OSISA) & mL
1
+ 2
1
(15)
m
mL.Hm
(16)
mL log(m) + + + +
(17)
2
m
This proves the second portion of the lemma: 8(STSA) ~ (mLllogma logm). m).
A.2 PROOF OF LEMMA 2
We begin by proving the retention result for SISA as it is simpler to understand. Each model within SISA is trained on single sequence of slices.
Proof. The probability maintains performs better than F(k is equivalent showing that none of the top-k elements (out of L) are affected after r deletion requests:
[ -1- T.
P (SI(A) 2 F(K))
(18)
In ST each model is trained on B such sequences. Therefore, we need to compute the probability that at least one sequence is better than F(k), which is:
P [F,(ST)) 2 F(A) =1 1100)=1-111 (1 (1-(1111-1))
(19)
However, the above result suggests that the probability can be increased indefinitely by increasing B. This is inaccurate because to maintain a performance of F(k) there has be at least one prefix of length & that has not been affected. Since there only P(L,k) TZ-A]t permutations of length k extending the budget beyond P(L, k) doesn't work. Therefore, the correct probability is:
8'
2 F(+)] =1 (1-(11(1-11)
P [[F,((T))= 2
(20)
where B' min (B, k)).
Taking the difference between Eq. 20 and Eq. 18 and setting a = (1 - L), we get:
P [FF((S)) 2 F(k) (SISA)) 2 F(+)
1 (1 a) a)B²
= (1 - a - (1 - a) B'
= ((1 - B')))
(21)
where -=1- -1----11--1 This completes the proof.
Discussion, In the above proof, we assumed that sequences are randomly selected. In practice, we select diverse sequences using the iterative eyclic rotation algorithm. However, deriving closed- form theoretical performance bound for the sequences generated using cyclic rotation is non-trivial. Intuitively, expect the performance be better selecting diverse sequences means that the probability of a length-k prefix getting affected is reduced. We leave the theoretical proof of these results to future work.
A.3 PROOF OF LEMMA 3
This lemma states that BMS selects the most diverse sequences. First, we revisit our definition of sequence diversity. Two sequences are considered diverse if no element appears at the same position, e.g., (S1, S2, Sz, S,) and Ss, S4, S1). Since want diverse sequences, BMS performs maximum weight perfect matching, ensuring that no two elements appear in the same position. Therefore, in this proof, we show that perfect matching exists all levels, [1, T.), in Algorithm 2.
17

---

Published as a conference paper at ICLR 2025
Proof. Let the bipartite graph, G, consist of vertices VUV. such that the edges E C V V. For perfect matching to exist, every subset W c V should satisfy:
W| (W),
(22)
where (- is the neighbourhood defined using the graph, G.
In our setup, the graph G has vertices V = {1, L and V = - 1.), elements in the permutation sequence. Every vertex E V has (T- 1) edges to unique vertices in V' at the i-th iteration of the algorithm. Therefore, for all iterations E (...... L} (shown in Line 6 in Algorithm the condition Eq. 22 is satisfied and perfect matching exists.
which indicate the
Since perfect matching selects a unique element in V', therefore no element is repeated at the same position in the BMS output. Therefore, BMS generates diverse sequences.
18

---

Published as a conference paper at ICLR 2025
Algorithm Iterative Cyclic Rotation
P) 3: for [1..... .... P.longhh) do
function
2:
R R= { set of all rotations
4:
R R U P
5:
P rolaleRight(P)
6: end for
7: return R
8: end function
9:
10: function IFFEATTTEECYLLCCROTTTOOXIICC count: L, Budget: B)
11: O CycliePormutation(I..... LJ) // initialize the set with cyclic permutations
Riter // set the iteration count
13: while |O| < B do
Riter Ritter +
15:
for E O do // iteratively expand each of the existing permutation of: Vitter,, oftiter :] // set the prefix and suffix // rotate the suffix with same prefix
prefix,
17:
= (prefix Up for p E CycllcPermuttaiion(ssfss)))))
19:
O OUP
20:
end for end while
21:
22: return Ol: B) // return output permutations
23:
end function
B IMPLEMENTATION DETAILS
In this section, discuss the details of various algorithms and workflows within S
CONTENTS
B.I
Iterative Cyclic Rotation
19
B.2
Bipartite-mathinng based Sequence Selection
20
B.3
S Training Procedure
22
B.4
Deletion Procedure
22
B. ITERATIVE CYCLIC ROTATION
In the setting, where the deletion probabilities are uniform we use the cyclic rotation algorithm select diverse permutations. In Figure 3 (middle), we observe that we can easily generate L diverse sequences using cyclic permutation of the original sequence. We can iteratively expand on this idea to generate more sequences when the budget is B > L. An illustration of the different sequences selected using iterative cyclic rotation for different budgets is shown Figure 10.
We present the pseudocode of the iterative cyclic rotation mechanism in Algorithm 1. First, we set the initial set to cyelic permutations of the original sequence (Line 11). If the budget exceeds the current set of output permutations, we iteratively expand the selected permutations by rotating their suffixes (Line 18). This continues till the output set has at least B sequences. Please note that Algorithm is simplified version of the actual algorithm. For some corner case budget values, apply certain heuristics to select the right permutations to expand (Line 18). Empirically, we observe that iterative cyclic permutation significantly outperforms random sampling (Figure 8). We conjecture that iterative cyclic rotation generates the most diverse set of permutations when all slices have equal deletion probabilities. We will leave the theoretical proof to future research.
19

---

Published as a conference paper at ICLR 2025
Budget 4
S
%
S
Budget B 8
S
S
S
S
S
S
S
S
S
S
S
%
%
Budget B =
13
%
S
S
S
S
S
S
S
S
S
S
S
S
S
S
&
S
S
S
&
&
S
S
S
S
S
S
S
S
S
S
&
S
%
&
%
&
S
S
S
S
S
S
S
S
S,
S
S
Figure 10: An illustration of the sequences selected by the iterative cyclic rotation algorithm for different budgets. We observe that for budget B < L the algorithm selects sequences generated by rotating the entire sequence. For budget I. < B < L(I. 1). the algorithm generates newer sequences by rotating the rotating subsequences starting from the second element. This continues as the budget increases and smaller subsequences are rotated.
B.2 BIPARTITE-MATCIING BASED SEQUENCE SELECTION
Before describing the bipartite selection algorithm, we discuss the scoring function for sequences with given deletion probabilities. Given a slice sequence with deletion probabilities S = Sp,,P2,P3,1
the scoring function computes the expected number of surviving slices after deletions:
score(S, f] = 4.(1 -p P2 p4)² +3.(1 (1-.11112)) -1 P2 pp3) +2. -P - P2) + (1--))) p. (23)
The above equation function of t, which needs to be set by the user. In the general case, Eq. 23 can be written as:
score (S,
Σ
Σ Pj
(24)
jm1
Next, we describe the details of the Bipartite-mathing based selection (BMS) algorithm in Algo- rithm 2. The objective of BMS is to select set of B S I. diverse permutation sequences where sequences have high score (Eq. 24). This algorithm starts by selecting I. different starting elements for the sequences in Line Then, BMS iteratively selects the next element within each sequence. This involves constructing bipartite graph between the last elements of the sequences seen far and the next set of elements. The edge weights are set to the score of the sequence that is a concatenation of the current sequence, o, and the next node, v'. The edges incident on feasible next elements (elements not seen in a permutation sequence so far) as shown in Line 12. We perform a maximum weight perfect graph matching on the graph, G, using the Hungarian algorithm (Kuhn, 1955). Based
20

---

Published as a conference paper at ICLR 2025
Algorithm 2 BMS Sequence Selection Algorithm
function B.SssSlice count: L. Budget: B)
2:
== {
3:
for I E (I.....L]
L} do initializing the sequence set with first element
4:
0 = OU
5: end for
6:
for i E (2...., L} do iterations to select the 2nd to the L-th element
7:
G = [} 1/l/IInin Initialize Graph
8:
for E O do // Iterate over sequences
9:
v = o.pop() // Collect final element of each sequence
10:
for v' {1, .1...... [.} do // Iterate and add all feasible edges w = scorelo U wf] compute score for the sequence o o (Eq. 24) v' then G.add edde(, v', , // check for feasibility
11:
13:
end for end for
15:
(V. V') = Maximum Weight // use Hungarian algorithm (Kuhn, 1955)
for o E O do
17:
// select vertex associated with each sequence from perfect matching (v/lo/ V A o.pop())
19:
OU // add to sequence
20:
end for end for
21:
22:
OB = fo Olo is among top B sequence with highest score[o]}
23:
return On
24: end function
Φ
0.1
0.3
0.6
S
S2
S3
S
S
S
S
S
S
S
S
S
S
S2
Sj
Figure 11: Illustration of conditional sampling of slice sequences. For each sequence, one slice is sampled at a time based on their deletion probabilities. We observe that conditional sampling selects sequences that has slices with relatively lower deletion probabilities towards the top.
on the matching, we select the next element for each permutation sequence (Line 18). BMS continues this process till all sequences E have elements. Based on the budget, we output sequences from O that have the highest sequence scores. For maximum weight perfect matching, (Tomizawa, 1971) provides an efficient algorithm with time complexity O(n²), where n is the number of nodes. Using this algorithm, the overall time complexity of BMS is O(L*), where L the number of slices. The following result shows that BMS generates the most diverse sequence set.
Lemma 3. For a budget < L, BMS returns the most diverse set of permutations.
We also validate the above result empirically and find that BMS produces a range of sequences with high scores (Figure 8). However, remains an open question whether these outputs are optimal (while considering both diversity and scores).
The BMS algorithm can output up to L diverse permutations. Extending for a budget > L is non-trivial. Therefore, in this setting, use conditional sampling approach to generate diverse sequences. conditional sampling, for each sequence, we sample slices one at a time based on their deletion probabilities (low deletion probabilities have higher chance of being sampled). If
21

---

Published as a conference paper at ICLR 2025
Algorithm S Training Procedure
1: Input: Dataset D, Shard Count: m, Slice Count: L, Budget: B
2: F 0 // initializing model set
3: for d E [DI..... m do // partition the dataset into shards and iterate over them
4:
S .S...... Sr partition into slices, U,S d
5:
IT Select SgleetTriningSSquenees. I., B) // using cyclic or BMS algorithm
6:
do for
7:
S x(S) // order the slices according to the permutation
8:
Wise SSiceeWieerainnnggSS...
9:
== FUf
10: end for
11: end for
12: return F.
Algorithm S Deletion Procedure
I: Input: Model set F, Deletion instance:
2: m' LocateShard(z:) (x) get original shard ID, m'
3: F = () set of modified models
4: for f E Fox do // iterate over models trained on m/-th shard
5:
= LLocaeeSlcce x, f) get original slice ID, I' of a within f
6:
for E (I',...,,L) L do
7:
DeactivateLayer(ff end for
// deactivate PEFT layers
8:
9: if >> then FU // ensuring all layers aren't switched off
10: end for
11: F == F Fm // remove older models
12: F FUF // introduce updated models
return
sampled sequence already exists in the selected set, it discarded. illustration of the conditional sampling approach is shown in Figure 11. We observe that the selected samples (shown in green) have slices with relatively lower deletion probabilities at the top.
B.3 S TRAINING PROCEDURE
In this section, we provide an outline for the training procedure within the S framework in Algorithm S proceeds by dividing the entire dataset into m shards. Each shard is further divided into L. disjoint slices. Based on the budget B, we obtain the permutation sequences to perform slice-wise training. We train each model f on unique sequence of slice sequence, (S)) We return the complete set of models, F. During inference, the user selects the best-performing model within each shard and deploys an ensemble of those models production.
B.4 DELETION PROCEDURF
In this section, describe the procedure when deletion request arrives for instance in Algorithm 4. We first locate the shard II), m', where the instance x belonged and iterate over all models trained that shard. For each of these models, all layers .l' L} (as shown in Line 7). After that, if the model f is still active, we add it to the set of modified models, ST uses the updated set to perform inference till new deletion request arrives. Note that the deletion process can occur entirely offline without impacting the production system, provided that the deleted instance does not influence any of the ensemble models.
locate the slice ID, 1', of and deactivate
22

---

Published as a conference paper at ICLR 2025
Table 2: We report the hyperparameters used in our experiments for fine-tuning S across different benchmarks and Transformer model variants.
# SLICES
# LAYERS/
LORA
LORA LEARNING
EPOCHS
DATASET
MODEL
(L)
SLICE
RANK (r) (a)
RATE
GLUE Benchmark
SST-2
ROBERTaLARGE
16
10 10-5
10
COLA
RoBERTaLARGE
4.10
30
STS-B
RoBERTai MARRI
16
32
10
30
QNLI
RoBERTE BLARGE
7
16
5.10
30
QQP
RoBERTA BL ALAGG
16
32
5.10
30
MRPC
RoBERT BLARGE
5.10
30
MNLI
RoBER TALARTE LAAGGE
10
30
SuperGLUE Benchmark
RTE
ROBERTALARGE TLARGE
16
32
10
30
WIC
RoBERTaL LAAGGE
12
16
32
10-4
30
CB
RoBERTar BLAGGI
12
16
10-4
30
COPA
RoBERTa SEEERTaLARCE BLARGI
12
10-5
30
BoolQ
RoBERTaL LLLAGE
16
32
10
30
MultiRC
RoBERTa TABARTE
16
32
10
30
Vision Benchmark
CIFAR-10
BATE
6
16
32
2.10
15
CIFAR-100
BIT
16
32
2.10
15
TinyImagenet
VATLARGE
2.10
15
Instruction Tuning
Alpaca
Llama2-7B
32
2.10
3
Alpaca
Llama2-133
4
10
32
64
2.10
3
Alpaca
Llama3-8B
32
64
2.10-5
3
C EXPERIMENTS
In this section, describe experimental setup and present additional analysis experiments evaluate the functioning of S
C.I EXPERIMENTAL SETUP
We perform all experiments using PyTorch (Paszke al., 2019) and Huggingface (Wolf al., 2019) framework. Our experiments were run on NVIDIA A6000 GPUs. In Table 2, report the common set of hyperparameters for S fine-tuning experiments. All hyperparameters were set using grid search with the Weights & Biases framework. We use AdamW optimizer with the corresponding learning rates for each dataset (reported in Table 2). During fine-tuning of the models, we perform full-preciste precision training for all settings except instruction tuning where 8-bit training.
C.2 DESIGN CHOICES
We discuss the rationale behind the design choices for the proposed slice- wise training approach. First, we used top-to-bottom fine-tuning because found the top layers were easier train the start and bottom-up approach didn't converge. Note that our training process does not need to proceed layer-wise fashion, we can even train multiple LoRA layers per slice. Second, we train layers in a cumulative manner where the i-th layer is trained using slices (1...., .... We found that this way of training helps in better convergence compared the setup where we train every layer using a different slice. Third, we analyze the cost of slice-wer wise training and find it to be comparable full training. Considering that training cost is (nn)), where n the dataset size and / the number of trainable layers (empirical evidence in Appendix C.3). For slice-wise training, we observe that E
({) O (n(), which is of the same order full training.
23

---

Published as a conference paper at ICLR 2025
Image Classification
Instructing Tuning
Text Classification
Performance Drop (96)
-12
10
CHFARIO CIFARLDO Tinytmagelit
-12
MMLU
OpentfockCA
NNL
ARC
PIQA
MRPC
COLA
Hellawing
Winegrande
ONLI
551-2
Number of Deleted Slices
Figure 12: Relative performance drop with an increasing number of deleted slices. We observe relatively small performance drop for image classification and instruction tuning tasks while noticing a considerable drop for a few of the text classification datasets.
Number of Slices
6
8
10
11
12
13
14
15
16
17
18
19
20
21
23
PPA
3
STOP
Pit
STT
Number of Layers per Slice
4
RV-
FQLR
A6.S
Rendom Performance
Poor Performance
10
BDD
Average Performance
Good Performance
Excellenn Performance
12
67:4
22
Figure 13: Performance impact of S when allocated a different number of layers per slice: We observe that simply increasing the number of slices can lead significant performance drop. There an optimal tradcoff between the total number of slices and the number of layers per slice.
C.3 ADDITIONAL EXPERIMENTS
In this section, report analysis experiments to evaluate the S²'''s deletion capabilities and training.
Performance Degradation with Slice Deletion. In Figure 12, we report the relative performance drop with an increasing number of slices affected by deletion requests. For vision datasets in Figure 12 (left), we only observe small drop in performance (<5%). For instruction tuning in Figure 12 (middle), we observe negligible performance drop for most datasets except MMLU & ARC. which are more challenging open- open-ended QA benchmarks. For text classification in Figure 12 (right), we observe an increased drop performance for a few of the datasets. We hypothesize that this occurs because the RoBERTai, pre-trained model compared to Ilama and ViT. We also observe that the performance can vary based on the task and overall it is dependent on both the task and the model being fine-tuned. For unlearning, a lower performance drop is better as suggests that we can continue using the same model without retraining for a longer time.
(used in text classification tasks) is relatively weaker
Layer Allocation per Slice. This experiment aims to answer the question: how many slices can we pack into model while still achieving good performance? We conduct experiment where allocate different numbers of PEFT layers per slice and also vary the number of slices. We report the results the RTE dataset using RoBERTaLARCE in Figure 13. We observe that the performance is
24

---

Published as a conference paper at ICLR 2025
CI
CIFAR-100
S
ST Sequantaal
Sequential
Performance
91.0
Time (s)
15 Number of layers
10
20
Number of Slices
Figure 14: (Left) Comparison of sequential training with S using a PEFT model. We observe that S performance gradually improves as is trained on a larger number of slices, ultimately achieving similar performance to sequential training while being more efficient.
Budget
Model (GB)
PEFT (GB)
Del. Rate
B =
1.2
0,21
66.4
B 2
1.2
0,42
86.9
B 3
1.2
0.63
100.8
B
1.2
0.84
107.8
B 5
1.2
1.05
110.1
B
1.2
1.26
124.1
Table 3: Storage cost of S under different training budgets. We show how the deletion rate increases with increased storage cost. The overall storage cost of PEFT layers is minimal and is equivalent to storing an additional model.
poor when the number of layers per slice low. For example, when the number of layers per slice 1, the performance improves we increase the number of slices but again drops when the slice count too high. This shows that it may not be feasible to train model using many slices without a drop in performance. Overall, the performance variation depends the underlying task and model, so the developer should select these hyperparameters based on their performance requirements.
Sequence-based Training. In this experiment, compare T' performance with sequential training. Sequential training involves training the entire PEFT model on a sequence of slices. This used in (Kumar al., 2023) improve the retraining efficiency of SISA. In Figure 14, report the performance of S and sequential training using ViTBASE on CIFAR-10 and CIFAR- 100 datasets. We observe that the performance of S gradually increases is trained more slices. Overall, we observe that S'T achieves quite similar or outperforms sequential training. It is important to note that S trains significantly smaller number of parameters (L times reduction compared to sequential training) but still achieves competitive performance.
Storage Costs. In this experiment, we evaluate how the storage cost of S grows with an increasing budget and its effect on the overall deletion rate. In Table 3, we report the storage costs and deletion rate training LÁTLARGE model with m 5 shards and L = 6 slices per shard. We observe that the storage cost of PEFT layers (with LoRA rank=16) is considerably less compared to the full model size. As budget and storage cost increases there an improvement in the deletion rate. However, the rate of improvement of the deletion rate slows down with an increased budget, indicating there is a lesser return on increasing the budget.
Training Time. In this experiment, evaluate the training time with varying number of PEFT layers. In Figure 14 (right), we report the average training time over a constant number steps using RoBERTaLARGE model. We observe that training time linearly increases LoRA layers are trained. This shows the effectiveness our proposed S framework, which only trains small number of PEFT layers each training stage.
increased number of
BMS vs. Cyelic rotation with Deletion prior. this setting, we compare the BMS selection algorithm with variant of cyclic rotation when the prior deletion probabilities available. We
25

---

Published as a conference paper at ICLR 2025
250
Sorted Cyclic Rotation
W
300K
(m=5,L=32
98.4
98.6
Proto SISA (w 0.9)
SSA
Deletton Rate (8)
250K
98.2
S15A
Proto SISA (M 0.3)
Score
200K
38.0
150
130K
97.8
100
10nK
57.6
97.4
50-
97.2
97.0
20
Slice count
50
10
20 Budget (8)
25
Number of deletions
23
Figure 15: (Left) We compare the scores (Eq. 24) of the generated sequences by BMS and sorted cyclic rotation. We observe BMS consistently outperforms cyclic rotation. (Center) We show the variation in deletion with increasing budget B under non-uniform deletion prior over the slices. (Right) We report the performance of SISA and ProtoSISA with varying weights.
perform cyclic rotation by first sorting the slices based on their deletion probabilities. For example, we sort the sequence with deletion probabilities: (S1: 0.5, S2: 0.4, S3: 0.1) as: S2, S1). Then, for budget B 3, the stored sequences are: (S, S1). (S1, S3. S2). (52, Sz). In this variant, the slices most likely to be deleted are not at the top of any sequences. We follow the experimental setup in Section 4.3 and sample deletion priors using a Dirichlet distribution (over 10 runs). In Figure 15 (left), we report the total sequence scores (Eq. 24) obtained by BMS and sorted cyclic rotation for budget, B L. We observe that BMS consistently outperforms sorted cyclic rotation for all budgets. Please note that the average edit distance achieved by both methods is the same as cyclic rotations are guaranteed to produce the maximum diversity for budgets: B S L.
Deletion with Non-uniform Prior. In this setting, we evaluate the impact of increasing the budget B when the deletion prior is non-uniform. We use m shards and L, 32 slices. For each shard, we sample a deletion prior over the slices distributions from Dirichlet distribution. Using these priors, we select sequences to train the model using the BMS algorithm. Since the BMS algorithm always generates L sequences, we greedily select the top B sequences based on the sequence score defined in Eq. 24. In Figure 15 (center), we report the deletion rate of S²T under varying budget sizes, B, when the deletion requests deletion prior, S can handle significantly more deletion requests (compared to the uniform prior setting in Figure 6 (right)). Overall, the deletion rate shows gradual increase as the budget rises; however, it remains notably high even with low budget.
sampled from the prior. We observe that when we have access the
Baseline Ablations. In this setting, we investigate the performance of ProtoSISA under different settings. ProtoSISA uses the same setup as SISA along with prototypical classifier. During inference, we use
90.6-
90.4-
weighted combination of the logits of SISA and the prototypical classifier. In this experiment, we vary the
Accuracy
weight assigned to the SISA component and report the results in Figure 15 (right). We observe that ProtoSISA achieves slightly better performance with lower weights when the number of deletion requests is high.
89.8
Ensemble of Slice Sequences. In this experiment, we evaluate the impact of using ensemble of models trained on different slice sequences. These slice se- quences include data within the same shard. We use ViT-base model on the CIFAR 100 dataset (m = 5, L = 4). In Figure 16, we observe that increasing the number of models initially enhances performance; however, this improvement plateaus as the model count increases.
89.6
2 Number of Sequences
10
Figure 16: We report the model perfor- mance using an ensemble approach where individual models are trained on different slice sequences. We observe an initial im- provement in performance, which eventu- ally plateaus.
26

---

Published as a conference paper at ICLR 2025
D LIMITATIONS & FUTURE DIRECTIONS
In this paper, we present a novel exact unlearning framework, S²T. S improves the deletion rate of existing unlearning systems at the cost of additional offline training. The training process be cime-consuming if we are fine-tuning larger models and have a higher performance requirement (thereby high budget B). However, this is inherent tradeoff between offline training and losing revenue due to re-training costs. The developer should adjust their budget according to the tradeoff in their specific application.
The primary goal of an exact unlearning system is to maintain a finely modular structure, enabling efficient retraining of individual components upon data deletion. Therefore, it important have sample efficient learning methods so that components achieve high performance while using less data. To further improve T this would involve research develop more expressive marameter-efficien fine-tuning approaches that can perform well when trained with small amounts of data.
E BROADER IMPACT
We present scalable approach to perform exact unlearning in production systems. We hope that this framework will be adopted by organizations and enable cost-effective way to ensure the privacy requests of various users. In general, unlearning systems are susceptible to attacks where adversary may design deletion requests in a way modify the model behavior according to their needs. Therefore, it is important to ensure that the deletion requests executed on the unlearning system are not malicious. However, this is a limitation of unlearning systems in general and not specific to proposed framework, T. Future works can focus the identification of malicious unlearning requests.
27


Reviews:
[{"review_id": "tFOE4odrn3", "reviewer": "Reviewer_LNAn", "summary": "This paper presents a machine unlearning framework using parameter-efficient fine-tuning. The approach integrates LoRA-based adapters into the layers of pre-trained networks, which can be trained sequentially or using sequence selection algorithm like BMS. When a data deletion request is made, the associated LoRA parameters tied to the associated data shards are zeroed out, allowing deletions without full retraining. This technique hence enhances deletion efficiency while retaining overall model performance, even after handling multiple unlearning requests.", "questions": "1.\tWith higher deletion budgets, the deletion rate does not scale linearly. Would incorporating a retraining strategy improve this? Retraining is mentioned briefly, but further details on when it’s necessary and whether this decision is empirical or rule-based would be helpful.\n2.\tHow does increasing the number of shards and slices impact model accuracy and storage requirements? An ablation study on this would add valuable insight.\n3.\tA comparison of S3T’s efficiency in terms of time or FLOPs against the baseline would clarify its computational advantages.\n4.\tIn Figure 9, does the SISA baseline include retraining of models, or does it simply use the latest checkpoint? This clarification is necessary for a fair comparison.\n5.\tHow does S3T’s storage requirement compare to SISA’s, particularly with frequent deletion requests?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and easy to follow. The paper is well-written and easy to follow, with a clear explanation of the LoRA-based adapters’ role in isolating model layers for efficient data deletion Validation is performed on a diverse set of tasks and datasets, which strengthens the generalizability performance. The technique effectively handles deletion requests under high budgets, with minimal loss in generalizability.", "weaknesses": "W1.\tThere are some concerns with the proposed top-to-bottom training strategy. First, since different layers are trained with varying data shards, this could cause performance degradation due to inconsistent data exposure across layers. The use of a pretrained base model might mask this potential degradation, as the presented performance relies on the ensemble of pretrained layers with LoRA adapters. It would be beneficial to see results when the model is trained from scratch to evaluate this strategy fully. Additionally, why does a bottom-to-top or other ordering not work well? Some theoretical justification for the chosen order would be helpful.\n\nW2.\tIt is unclear whether PEFT is essential to this approach or primarily used for computational savings. Could similar outcomes be achieved with additional classification heads or adapters? A discussion on whether PEFT is integral to the technique would be great.\n\nW3.\tThe novelty of the proposed technique is limited considering the use of off-the-shelf techniques like BMS and LORA to reduce the complexity. A comparison with several recent works like E2URec, Bad-T, NegGrad, NegKL, and RecEraser is missing. \n\nW4.\tFor a random deletion request unless it is for the slice associated with the final layer, the initial LORA parameters are using not participating for majority of the requests. This raises the question of whether the pretrained model’s representation power makes LoRA adapters in initial layers unnecessary. Any clarifications on this?\n\nW5.\tI am a bit confused for the implementation of the baseline SISA. Why the SISA models do not work in your implementation after 40 requests? (In the original paper, the performance does not even visibly drop for tens of deletion requests). It is also mentioned following Lemma 1 that considering real-world scenario, you do not allow retraining of model as originally proposed in SISA. It this is how it is implemented for comparison in the experimental section too? \n\nMy score is based on the weaknesses mentioned above. Give clarifications, I am willing to raise my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vxJ3fQH58I", "reviewer": "Reviewer_tCTF", "summary": "This paper proposes S3T, a new solution for machine unlearning. Different from Shared, Isolated, Sliced, and Aggregated training (SISA) techniques, S3T allows isolation between parameters by sequentially training model layers using disjoint data slices. S3T trains the pre-trained model multiple times with different training orders to avoid re-training from scratch. The experimental results show that S3T can effectively reduce the re-training parameters after receiving the deletion request, compared with SISA methods.", "questions": "Please refer to the comments in Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "++ This paper points out a strong limitation of current SISA-based machine unlearning methods: the deletion request of the bottom slices will lead to retraining all the above slices. S3T’s solution effectively reduces the re-training time cost.\n\n++ The LoRA-based training solution makes S3T practical in application as it is compatible with many Transformer-Based models, including small and large models. \n\n++ The theoretical analysis of S3T’s deletion rate and performance retention metrics is rigorous. \n\n++ The writings and figures of the paper are easy to follow.", "weaknesses": "-- In Section 2, the paper claims that “approximate unlearning techniques… may have weak privacy guarantees in practice.” However, it does not explain whether S3T has a stronger privacy guarantee mechanism.\n\n-- Although S3T outperforms other SISA-based methods, it significantly increases the training burden of the model providers (Even after applying the permutation-tree-based method, S3T still requires training the same model multiple times). I think the paper should further explain whether it is worth increasing the training cost several times or even dozens of times to reduce the cost of re-training, especially in the context of training LLMs. \n\n-- The sequence-order selecting algorithm in Section 3.3 depends on the deletion rate of each slice. In other words, its performance is related to the distribution of each slice’s deletion request’s arrival probability. Therefore, In Section 4.2’s evaluation, the uniform deletion prior over all slices may not be enough to fully evaluate the algorithm’s performance.  The paper could conduct another experiment in which the slice’s arrival probability is more unpredictable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5JNeGEh9XQ", "reviewer": "Reviewer_U5Bx", "summary": "The paper tackles machine unlearning,  the process of efficiently removing the influence of a specific training data instance from a machine learning model without retraining it entirely. There are two main types of unlearning: approximate and exact. This paper focuses on exact machine unlearning, a category that guarantees the complete removal of a data instance's influence from the model. Exact unlearning methods rely on training individual components of the model on distinct, disjoint subsets of the data.\n\nThe authors introduce a new framework for exact unlearning called Sequence-aware Sharded Sliced Training ($S^3T$). $S^3T$ is designed to improve the ability to delete data instances from a model while minimizing any negative impact on the model's overall performance. Both theoretical and empirical results show that $S^3T$ outperforms existing methods in terms of deletion capability and performance across a variety of scenarios.\n\nThe key innovation of the $S^3T$ framework is the use of additional offline training before the model is deployed, which significantly reduces retraining costs. The authors compare their approach with Sharded, Isolated, Sliced, and Aggregated (SISA) training. A major drawback of SISA is that if deletion requests target Slice 1 across all shards, the entire system becomes compromised, necessitating complete retraining. The S3T framework addresses this issue by introducing more robust deletion strategies.\n\nAdditionally, the authors use LoRa for slicewise training and present methods for selecting diverse permutations under budget constraints.", "questions": "- What does \"Total time\" refer to in Figure 9, and in which units is it measured?\n- Could you elaborate on the setting where budget B < L?\n- Could you explicitly provide answers to RQ2 and RQ3 in the text, similar to how RQ1 is addressed?\n- In Figure 1, it’s unclear that the shards are disjoint—can you clarify this?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Theoretically shown that S3T achieves provably better deletion guarantees than existing approaches.\n\n- Empirical results show that S3T is an effective method for fine-tuning Transformer models, enabling parameter isolation for data slices without compromising the model's performance.", "weaknesses": "- The paper exhibits minor weaknesses due to lack of clarity and ambiguity; for detailed points, please refer to the questions provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bsruhsaJGr", "reviewer": "Reviewer_Masp", "summary": "This paper presents a new framework for exact machine unlearning, called S$^3$T, inspired from SISA. S$^3$T leverages PEFT on disjoint shards of data. Different from SISA, S$^3$T sequentially trains PEFT layers following a slice sequence. By using multiple slice sequences, S$^3$T provides granular isolation and superior deletion capabilities, enhancing the deletion rate while maintaining good performance. The authors propose two algorithms to choose slice sequences, for uniform and non-uniform deletion priors. Extensive experiments and ablations on several vision and language benchmarks demonstrate the effectiveness of S$^3$T in comparison to SOTA baselines.", "questions": "1) Are results in Table 1 with B = 1? When B > 1, will using an ensemble of models across different slice sequences enhance performance?\n2) On similar lines as the previous question, will using an ensemble of available models improve performance over just using the model trained on the maximum number of slices pertaining to a deletion request?\n3) How does the net storage cost of S$^3$T compare to SISA when B > L and B < L?\n4) The performance of ProtoSISA seems to be almost overlapping with SISA? Why is this so?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This is a well written paper.\n- The paper focuses on a very relevant setting involving PEFT for unlearning. \n- Rethinking slicing from SISA into a layerwise training while leveraging PEFT is a clever design. It was interesting to see that such a design does not introduce significant trade-offs. \n- The experimental evaluation is extensive, spanning several datasets and model sizes. The authors cover all the important questions relevant to S$^3$T in their evaluations, including its training performance, deletion performance and ablation studies. The diversity and scale of experiments strengthens the contributions of the paper.\n- The appendix discusses several important aspects of the work including storage costs, training time, design choices, etc. In particular, it was interesting to note why the top-down approach was chosen over a bottom-up approach.", "weaknesses": "- Depending upon the model and the dataset, S$^3$T can result in lower training performance compared to full training. \n- No code is provided, however the authors promise to release it with the final version.\n\nThe paper can be further improved by adding a limitations section that could summarize all potential trade-offs and discussing future directions to improve the same. It would also be nice to see some performance numbers in the abstract itself, such as S$^3$T improves the deletion rate by $1.6\\times$ over SISA.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)