Towards Scalable Exact Machine Unlearning Using Parameter-Efficient Fine-Tuning

## Abstract

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 – S equence-aware S harded S liced Training (S 3 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 3 T, 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 S 3 T to handle an increased number of deletion requests. Both theoretically and empirically, we demonstrate that S 3 T attains superior deletion capabilities and enhanced performance compared to baselines across a wide range of settings.

## 1 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., ; Team et al., ; Qayyum et al., ; Surden, ).
Once a 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, ; ; Shastri et al., ; Achille et al., ), removing stale or corrupt data (Biggio et al., ; Steinhardt et al., ), etc. Retraining an ML model entirely from scratch with each deletion request is expensive, especially for modern large-scale models (Brown et al., ; Achiam et al., ; Team et al., ). Machine unlearning (Nguyen et al., ; Xu et al., ) techniques focus on efficiently unlearning the influence of a data instance from a trained machine learning model.

Machine unlearning techniques are classified into two broad categories: approximate and exact unlearning (Xu et al., ). Approximate unlearning techniques (Guo et al., ; Liu et al., ) modify the parameters of a trained model to reduce the influence of 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. Moreover, auditing approximate unlearning is challenging due to the stochastic nature of ML optimization (Thudi et al., ). An alternative to this approach is exact unlearning (Cao & Yang, ; Bourtoule et al., ; Golatkar et al., ), which can guarantee the removal of a data instance’s influence from a trained model. Exact unlearning techniques use 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 a 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-aware Sharded Sliced Training (S^3T), which can exactly unlearn private fine-tuning data efficiently while minimizing the impact on performance.

The key idea behind our S^3T framework is to perform additional offline training before deploying the initial model to reduce retraining costs.
At the core of S^3T, we leverage a 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^3T achieves provably better deletion guarantees than existing approaches (Section 3.4).
We conduct extensive empirical evaluations to evaluate the effectiveness of S^3T 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^3T has superior deletion performance compared to existing methods in real-world settings.

## 2 Background

Machine unlearning techniques for deep learning is broadly classified into two categories: approximate and exact unlearning (Xu et al., ). Approximate unlearning techniques focus on reducing the influence of a deleted instance from a model after it has been trained. Exact unlearning techniques provide unlearning guarantees by ensuring model components trained on a 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., ). These techniques typically quantify the influence of an instance (Koh & Liang, ) and perform gradient ascent for unlearning (Golatkar et al., ; ; Neel et al., ; Sekhari et al., ; Gupta et al., ; Suriyakumar & Wilson, ; Liu et al., ). In contrast to these approaches, (Graves et al., )
stores the exact gradients encountered during training and uses them directly for gradient ascent. Another line of work (Tarun et al., ; ; Jia et al., ; Chen & Yang, ; Eldan & Russinovich, ; Patil et al., ; Kurmanji et al., ; Liu et al., ; Park et al., ; Zhang et al., ) focuses on unlearning in a batch setting, where they assume access to both a 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., ; Wang et al., ) and may have weak privacy guarantees in practice (Hayes et al., ; Łucki et al., ).

Figure: Figure 1: Schematic diagram of the Sharded, Isolated, Sliced, and Aggregated training (SISA) (Bourtoule et al., ) framework. An ensemble of models is individually trained on disjoint shards. (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.
Refer to caption: x1.png

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. 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., ). SISA uses an ensemble of models each trained on a disjoint shard of the dataset as shown in Figure 1 (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 1 (right)). If a deletion request affects a data instance within the 4^th slice of a shard, we must retrieve the checkpoint after the 3^rd slice and retrain using the remaining data within that shard. Several approaches focus on improving the components within SISA in application-specific settings like enhancing the dataset partitioning mechanism (Aldaghri et al., ; Yan et al., ), the retraining efficiency using light-weight adapters (Kumar et al., ; Dukler et al., ), or extending the modular approach for vision tasks by using compartmentalized diffusion models (Golatkar et al., ). However, these approaches are orthogonal to our work since they do not fundamentally modify the functioning of SISA. These modifications can be easily incorporated within our proposed framework.

SISA is a well-known framework that can guarantee exact unlearning and has found widespread applications. However, using SISA within production systems is challenging because retraining even a 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 a framework that improves upon the service availability and deletion capabilities of the SISA framework.

## 3 S equence-aware S harded S liced Training (S 3 T)

In this section, we describe the functioning of our proposed exact unlearning framework, Sequence-aware Sharded Sliced Training (S^3T). 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 a pre-trained model like BERT (Devlin et al., ) or Llama (Touvron et al., ) 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^3T, we partition a dataset $\mathcal{D}=\{\mathcal{D}_{1},\ldots,\mathcal{D}_{m}\}$ into $m$ disjoint shards. Each shard is further divided into $L$ slices: $\mathcal{D}_{i}=\{S_{1},\ldots,S_{L}\}$.
S^3T trains a separate model per shard and uses their aggregate decision.

Existing unlearning frameworks SISA (Bourtoule et al., ) use a similar setup described above. In SISA, within each shard, the model is 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 a 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 1 (right), if a deletion request arrives for a data instance in Slice 4, the model in production can be replaced with the checkpoint obtained after Slice 3. It is easy to see that the performance of the overall model will degrade with the number of deletion requests.

We present an exact unlearning framework, S^3T, 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, we utilize the model that minimizes performance degradation. To further reduce the training cost, we leverage PEFT techniques and present a novel sequential slice-wise fine-tuning strategy in Section 3.2. Our training strategy allows us 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.

Figure: Figure 2: (Left) We show the schematic diagram of the slice-wise training strategy in S^3T. We incrementally train the model – $i$^th layer (from the top) using slices $S_{1:i}$ while keeping the other layers fixed. (Right) We show the impact of deletion on models trained on different permutations of slices.
Refer to caption: x2.png

### 3.2 Sequential Slice-wise Training

In this section, we introduce Sequence-aware Sharded Sliced Training (S^3T) 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 S^3T using the PEFT technique, LoRA (Hu et al., ), but our method is general can be easily extended to other PEFT techniques. LoRA introduces a small number of trainable low-rank ($r\ll d$) parameters, $(\bf X,\bf Y)$, while the pre-trained weights $\mathbf{\overline{W}}$ remains fixed as shown below:

$$ $\mathbf{W}=\mathbf{\overline{W}}+\mathbf{X}^{\top}\mathbf{Y},\text{ where } \mathbf{X},\mathbf{Y}\in\mathbb{R}^{r\times d},\mathbf{\overline{W}}\in\mathbb {R}^{d\times d}.$ (1) $$

Our key idea involves training different LoRA layers using different data slices.
This approach allows us to selectively deactivate (zero out) the LoRA parameters ($\bf X$ or $\bf Y$) associated with a 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 1 in the figure)
using slice 1 while LoRA parameters from all other layers are switched off. In the next stage, we train second last layer (Layer 2) using slices 1 & 2, 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 to 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-wise training process ensures that the LoRA parameter updates at the $i$-th layer are a function of the data instances within slices $\{1,\ldots,i\}$. Therefore, if a deletion request affects the $i$-th slice, the same model can still be used by deactivating the LoRA parameters corresponding to slices $\{i,\ldots,L\}$ (see details in Algorithm 4). For example, if a deletion request affects slice $S_{3}$ 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 1 & 2 were not affected by instances in $S_{3}$. 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.

Now we consider the scenario where deletion requests affect multiple slices. This is shown in the 2^nd sequence of Figure 2 (right), where slices $S_{1}$ and $S_{3}$ are affected. In this case, we observe that a model trained on the default ordering of the sequence $\{S_{1},\ldots,S_{5}\}$ is rendered useless when $S_{1}$ and $S_{3}$ 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 3^rd 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 a 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 to achieve the optimal deletion performance.

Figure: 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 $L=3$ and a diverse set of sequences for budget $B=3$ is 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 $B>L$ by generating cyclic rotations of the subsequences.
Refer to caption: x3.png

### 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 a permutation tree (Bhattacharya, ), 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 $(S_{1},S_{2},S_{3})$, $(S_{1},S_{3},S_{2})$, 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 2 (right)). To address this and reduce the retraining cost, we should ensure we 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 are considered diverse if no element appears at the same position, e.g., $(S_{1},S_{2},S_{3})$ and $(S_{2},S_{3},S_{1})$. An example is illustrated in Figure 3 (left), where a diverse set of 3 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 to 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 a budget $B$, depending on whether or not prior deletion probabilities are available.

Figure: Figure 4: 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 ($\rightarrow$) indicate the selected edges and dotted arrows ($\mathrel{\mathchoice{\mathrel{}\mathrel{\mathop{\dabar@\dabar@}\limits} \mathrel{\mathchar 0\relax\symAMSa 04B}{}}{\mathrel{}\mathrel{\mathop{\dabar@ \dabar@}\limits}\mathrel{\mathchar 0\relax\symAMSa 04B}{}}{\mathrel{}\mathrel{ \mathop{\dabar@\dabar@}\limits}\mathrel{\mathchar 0\relax\symAMSa 04B}{}}{ \mathrel{}\mathrel{\mathop{\dabar@\dabar@}\limits}\mathrel{\mathchar 0\relax \symAMSa 04B}{}}}$) the feasible ones.
Refer to caption: x4.png

Uniform Deletion Prior. In the setting, where each slice has a uniform (or unknown) deletion prior, we can generate diverse sequences by using cyclic permutations of the original sequence. Given a sequence $(S_{1},S_{2},S_{3})$, the cyclic permutations are (shown in Figure 3 (middle)):

$$ $(S_{1},S_{2},S_{3})\rightarrow(S_{3},S_{1},S_{2})\rightarrow(S_{2},S_{3},S_{1}).$ (2) $$

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 existing sequences and performing cyclic rotations of the subsequences. For example, for $(S_{1},S_{2},S_{3})$ we perform cyclic rotation of the 2^nd and 3^rd element to obtain the sequence: $(S_{1},S_{3},S_{2})$ (more examples in Figure 10). We provide the general iterative cyclic rotation algorithm in Appendix B.1.

Non-uniform Deletion Prior. In scenarios, where we have prior knowledge of the deletion probabilities, sequences generated by cyclic rotation may not be ideal. For example, consider the deletion probabilities are: ($S_{1}$: 0.5, $S_{2}$: 0.4, $S_{3}$: 0.1). Then, the first sequence in Eq. 2 is a 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 at 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: $\mathcal{S}=(p_{1},\ldots,p_{L})$ by computing the expected number of functioning slices after $t$ deletions: $\mathrm{score}[\mathcal{S},t]=\sum_{i=1}^{L}i.\left(1-\sum_{j=1}^{i}p_{j}
\right)^{t}$, where $t$ is a hyperparameter.

We present a 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.
An illustration of BMS is shown in Figure 4. BMS iteratively selects elements of sequences by constructing a 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, $\mathrm{score}[\mathcal{S},t]$.
Selecting the next element then is equivalent to finding a maximum weight perfect matching (Galil, ) using the Hungarian algorithm (Kuhn, ) 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 a budget. Here, we will bring all of the components together and illustrate the functioning of S^3T using a simple example. We consider a setting with $m=3$ shards, $L=4$ slices, and budget $B=4$. Initially, for every shard, the available models are trained on sequences:

$$ $\displaystyle(1,2,3,4),(4,1,2,3),(3,4,1,2),(2,3,4,1)$ $$

Next, if a deletion request affects slice 1 for the 3^rd shard. Then, the available models for the 3^rd 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^3T doesn’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^3T continues to function with the best model $(3,4)$. This continues until no models are available in any shard, at which point S^3T 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 et al., ) and introduce the definition of deletion rate for exact unlearning systems.

###### Definition 1 (Deletion Rate) .

The deletion rate, $\delta(S)$, of an exact unlearning system $S$, is the expected number of deletion requests until the system needs to be retrained from scratch.

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^3T and compare it with that of SISA.

###### Lemma 1 .

For uniform deletion prior and dataset size $N\gg r$, where $r$ is the number of deletion requests, the deletion rate of S^3T is $\delta({S\textsuperscript{3}T})\sim O(mL\log(m\min(B,L)))$ and for SISA it is $\delta(\mathrm{SISA})\sim O(mL\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 improve by increasing the budget $B$ beyond $L$. This shows that the optimal deletion rate can be achieved using only $L$ sequences (instead of $L!$). The complete proof is presented in Appendix A.1.

Next, we analyze the impact of deletion requests on the system’s performance. We perform a fine-grained analysis focusing on the performance of an individual shard. In this setting, we consider the real-world scenario where we do not retrain every time a slice is impacted instead work with the best available model. For S^3T, this means switching off the necessary PEFT layers, while for SISA, it 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 on $k$ slices. The exact formulation of $F(\cdot)$ depends on several factors like the dataset, model size, etc. We analyze the performance retention while processing deletion requests.

###### Lemma 2 (Performance Retention) .

Given a set of randomly selected $B>1$ sequences and uniform deletion prior of slices, the difference in the probability that a shard retains a performance, $F_{r}(\cdot)$ of at least $F(k)$ after $r$ deletion requests, between S^3T and SISA, is shown below

$$ $\forall k\in[1\ldots L],\;\mathbb{P}\left[F_{r}({S\textsuperscript{3}T})\geq F (k)\right]-\mathbb{P}\left[F_{r}(\mathrm{SISA})\geq F(k)\right]=\zeta(1-\zeta^ {B^{\prime}-1}),$ (3) $$

where $\zeta=1-(1-k/L)^{r}$ is a positive fraction and $B^{\prime}=\min\left\{B,\frac{L!}{(L-k)!}\right\}$.

The above result demonstrates that compared to SISA, S^3T significantly enhances performance by increasing the probability that the system maintains at least $F(k)$ performance.
Eq. 3 shows that increasing the training budget $B$ helps improve the performance of the unlearning system. The proof is presented in Appendix A.2. Another takeaway from the above lemma is that to ensure the system performance of $F(k)$, there is no point in increasing the budget $B$ beyond $\frac{L!}{(L-k)!}$.

###### Definition 1 (Deletion Rate) .

###### Lemma 1 .

###### Lemma 2 (Performance Retention) .

## 4 Experiments

In this section, we outline the experimental setup and evaluate the unlearning performance of S^3T across various setups. The goal of the experiments is to evaluate the functioning of individual components and the unlearning capabilities of S^3T. Specifically, we design experiments to answer the following research questions:

- (RQ1)
Does S^3T training (Section 3.2) impact the model’s performance compared to full training?
- (RQ2)
Does S^3T 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^3T can achieve performance comparable to full training. Note that S^3T is not designed as a new fine-tuning technique that outperforms the baselines. The goal of S^3T is to achieve parameter isolation for data slices without impacting the overall performance. We perform a 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.1.

In Figure 5, we report the performance of fine-tuning on vision, GLUE, and SuperGLUE benchmarks. We use ViTBASE (Dosovitskiy et al., ) (for CIFAR10 & CIFAR100 (Krizhevsky et al., )), ViTLARGE (for Tiny ImageNet (Le & Yang, )), and RoBERTaLARGE (Liu et al., ) (for GLUE (Wang et al., ) & SuperGLUE (Wang et al., )). We observe that S^3T achieves comparable performance to full training (FT) across all settings. In some of the settings, we also observe that S^3T is able to outperform FT (e.g., S^3T obtains 2.5% accuracy gain on TinyImagenet using ViT-large). Next, we conduct experiments to evaluate the effectiveness of S^3T while using large language models (LLMs). Specifically, we perform instruction tuning of Llama2-7B (Touvron et al., ), Llama2-13B, and Llama3-8B using Alpaca dataset (Taori et al., ). Then, we evaluate each instruction-tuned model on a range of tasks to evaluate the model’s general/world knowledge (MMLU (Hendrycks et al., ), OpenBookQA (Mihaylov et al., )), truthfulness in QA (TruthfulQA (Lin et al., )), and commonsense reasoning (PIQA (Bisk et al., ), HellaSwag (Zellers et al., ), Winogrande (Sakaguchi et al., ), ARC (Clark et al., )). We use LLM-evaluation suite (Gao et al., ) report the zero-shot performance for all datasets. Similar to the previous setup, in Table 1, we observe that S^3T achieves comparable performance to full finetuning across all datasets and even outperforms FT on many datasets across different model sizes. These experiments provide the answer to (RQ1) demonstrating that S^3T is an effective way to fine-tune Transformer models, enabling us to achieve parameter isolation for data slices without impacting the model’s performance.

**Table 1: Performance comparison of LLMs before and after instruction tuning using Alpaca dataset. We report the performance of Llama2-7B, Llama2-13B, and Llama3-8B models for the following settings: pre-trained model, full training (FT), and slice-wise training (S^3T). We observe S^3T achieves comparable performance to FT, even outperforming FT’s performance in several datasets. This shows that S^3T allows parameter isolation without affecting the task performance.**
| Model | MMLU | HellaSwag | PIQA | Winogrande | ARC-c | ARC-e | TruthfulQA | OBQA |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Llama2-7B | 41.3(0.4) | 76.0(0.4) | 79.1(1.0) | 69.1(1.3) | 46.3(1.5) | 74.6(0.9) | 39.0(1.4) | 44.2(2.2) |
| Llama2-7B (FT) | 43.3(0.4) | 77.4(0.4) | 79.9(0.9) | 69.6(1.3) | 50.4(1.5) | 74.7(0.9) | 46.3(1.6) | 46.8(2.2) |
| Llama2-7B (S^3T) | 43.6(0.4) | 77.7(0.4) | 79.7(0.9) | 70.5(1.3) | 51.4(1.5) | 74.1(0.9) | 43.0(1.5) | 46.4(2.2) |
| Llama2-13B | 50.5(0.4) | 79.4(0.4) | 80.5(0.9) | 72.2(1.3) | 49.0(1.5) | 77.5(0.9) | 36.9(1.4) | 45.2(2.2) |
| Llama2-13B (FT) | 51.8(0.4) | 81.3(0.4) | 82.0(0.9) | 72.2(1.3) | 55.0(1.5) | 79.3(0.8) | 38.8(1.5) | 46.6(2.2) |
| Llama2-13B (S^3T) | 51.6(0.4) | 80.9(0.4) | 81.8(0.9) | 72.8(1.3) | 54.5(1.5) | 80.6(0.8) | 39.6(1.5) | 46.2(2.2) |
| Llama3-8B | 62.2(0.4) | 79.1(0.4) | 80.6(0.9) | 73.6(1.2) | 53.2(1.5) | 77.6(0.9) | 43.9(1.4) | 45.0(2.2) |
| Llama3-8B (FT) | 59.2(0.4) | 80.8(0.4) | 80.9(0.9) | 72.2(1.3) | 59.0(1.4) | 79.6(0.8) | 46.6(1.6) | 46.8(2.2) |
| Llama3-8B (S^3T) | 59.6(0.4) | 80.2(0.4) | 82.4(0.9) | 73.8(1.2) | 57.0(1.5) | 80.5(0.8) | 48.5(1.6) | 47.0(2.2) |

Figure: Figure 5: Comparison of the performance between slice-wise training and full training on vision datasets and GLUE & SuperGLUE benchmarks. We report the overall Matthew’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.
Refer to caption: x5.png

### 4.2 Deletion Performance

In this section, we evaluate the performance of S^3T as deletion requests are received. In Figure 6 (left), we report the performance of S^3T, SISA (Bourtoule et al., ), and ProtoSISA (Yan et al., ) on CIFAR-10 and CIFAR-100 datasets (all systems use $m=5$ shards, $L=4$ slices). In this experiment, we consider a uniform deletion prior over all slices. We also report the performance of full re-training, which retrains the model after each deletion request and serves as an upper performance bound. We report S^3T’s performance under various budgets. We observe that S^3T can achieve very close performance to the full budget ($B=24$) with a significantly smaller budget, $B=4$. For SISA and ProtoSISA, 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^3T can handle more deletion 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), we 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 provides empirical evidence to our theoretical result in Lemma 2, which claims that the performance improves with an increased budget.

### 4.3 Analysis

In this section, we conduct analysis experiments to evaluate different components within S^3T. We also report several other analysis experiments in Appendix C.3.

Figure: Figure 6: (Left) We report the impact on performance of S^3T and baselines with an increasing number of deletion requests. We observe that S^3T can handle a higher number of deletion requests while maintaining high performance with a relatively low budget ($\mathbf{\bigotimes}$ indicates the failure points). (Right) We report the deletion rate of S^3T with an increasing budget and observe steady growth.
Refer to caption: x6.png

Figure: Figure 7: We report the deletion rate of S^3T and compare it with baselines. (Left) We compare the deletion rates of S^3T 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^3T’s deletion rate grows significantly faster than SISA.
Refer to caption: x7.png

Deletion Ablations.
We evaluate the deletion capabilities of S^3T and compare with the theoretical bounds. In Figure 7 (left), we report the deletion rate of S^3T and SISA for the setup (with $m=5$ shards, $L=32$ slices). We observe that with a small budget $B=8$, S^3T 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^3T resulting in up to 2.3x and 3x gains over SISA for the same number of shards and slices respectively.

Figure: 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\leq B\leq 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 achieves higher scores than random sampling.
Refer to caption: x8.png

Figure: Figure 9: We compare the deletion time as the number of deletion requests increases. S^3T requires the lowest deletion time compared to SISA and full re-training.
Refer to caption: x9.png

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 to be diverse and should have a high edit distance between sequences. Therefore, we report the average edit distance within a selected subset, $O$: $\mathbb{E}_{o\in O}[d_{\mathrm{edit}}(o,o^{\prime})]$. 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 ($L$) 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 a 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 ($\mathrm{score}[\mathcal{S},t]$).

Deletion Time. Unlearning in S^3T is cost-effective; it primarily involves selecting the best checkpoint and swapping with the current one. The main cost is incurred when a large number of deletion requests necessitate re-training the system from scratch. In Figure 9, we report the total deletion time 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^3T with SISA and full re-training on CIFAR10 dataset. Full re-training retrains the model after each deletion request. For SISA and S^3T, the step jumps indicate that the system requires retraining. Overall, S^3T achieves the lowest deletion time. S^3T 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^3T in reducing the overall deletion time.

## 5 Conclusion

In this paper, we introduced S^3T, an effective framework for performing exact unlearning. S^3T uses a modular machine learning model that is trained using disjoint shards of the data. Each shard is used to train a 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^3T 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, we show that S^3T has significantly improved deletion capabilities compared to existing approaches. Future work can focus on developing techniques for finer-grained parameter isolation to further improve S^3T’s performance.

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

## 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 to the writing of the manuscript.

## Appendix A Mathematical Proofs

### A.1 Proof of Lemma 1

In S^3T, since the sequences are selected to be diverse (Figure 4), the topmost slice in each sequence is different.
Therefore, we have $B^{\prime}=\min(B,L)$ different slices at the topmost position.
This implies that for S^3T to encounter service failure, a total of $mB^{\prime}$ slices must be affected by deletion requests, where $m$ is the number of shards. Considering deletion requests affect all slices uniformly we need to compute the expected time till all slices are affected.
This setup is similar to the coupon collector problem (Blom et al., ).

###### Proof.

The deletion rate is the expected number of requests to delete all $mB^{\prime}$ slices ($m$ shards, $B^{\prime}$ unique slices per shard). Using linearity of expectation, the deletion rate or total time is:

$$ $\displaystyle\delta({S\textsuperscript{3}T})=\mathbb{E}[T]$ $\displaystyle=\mathbb{E}[t_{1}+\ldots+t_{mB^{\prime}}]$ (4) $\displaystyle=\mathbb{E}[t_{1}]+\ldots+\mathbb{E}[t_{mB^{\prime}}],$ (5) $$

where $\mathbb{E}[t_{i}]=1/p_{i}$, where $p_{i}$ is the probability that the $i$-th slice is affected after $(i-1)$ slices are deleted. Let $N=|\mathcal{D}|$ the dataset size and $r$ be the number of deletion requests seen so far. The expression of $p_{i}$ is shown below:

$$ $\displaystyle p_{i}$ $\displaystyle=\frac{\{mB^{\prime}-(i-1)\}s_{b}}{N-r}$ (6) $\displaystyle p_{i}$ $\displaystyle=\frac{N\min(B/L,1)-(i-1)s_{b}}{N-r}$ (7) $\displaystyle p_{i}$ $\displaystyle=\frac{\min(B/L,1)-(i-1)/(mL)}{1-r/N}$ (8) $\displaystyle\Rightarrow p_{i}$ $\displaystyle\geq\frac{mB^{\prime}-(i-1)}{mL},$ (9) $$

where $s_{b}$ is the size of each slice. Replacing this result in Eq. 5, we get:

$$ $\displaystyle\delta({S\textsuperscript{3}T})$ $\displaystyle\leq\frac{mL}{mB^{\prime}-0}+\frac{mL}{mB^{\prime}-1}+\ldots+ \frac{mL}{1}$ (10) $\displaystyle=mL\left(\frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{mB^{\prime}}\right)$ (11) $\displaystyle=mL.H_{mB^{\prime}}$ (12) $\displaystyle=mL\log(mB^{\prime})+\gamma mL+\frac{1}{2}+O\left(\frac{L}{mB^{ \prime}}\right),$ (13) $$

where ${H}_{mB^{\prime}}$ denotes the $mB^{\prime}$-th Harmonic number and $\gamma$ is the Euler’s constant (Lagarias, ).
The above result proves the first part of the lemma, $\delta({S\textsuperscript{3}T})\sim O(mL\log mB^{\prime})$.

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. In this case, we can write:

$$ $p_{i}=\frac{\{m-(i-1)\}s_{b}}{N-r}=\frac{N/L-(i-1)s_{b}}{N-r}=\frac{1-(i-1)/m} {L(1-r/N)}\geq\frac{m-(i-1)}{mL}$ (14) $$

Replacing the above result in Eq. 5, we get:

$$ $\displaystyle\delta(\mathrm{SISA})$ $\displaystyle\leq mL\left(\frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{m}\right)$ (15) $\displaystyle=mL.H_{m}$ (16) $\displaystyle=mL\log(m)+\gamma m+\frac{1}{2}+O\left(\frac{1}{m}\right).$ (17) $$

This proves the second part of the lemma: $\delta(\mathrm{SISA})\sim O(mL\log m)$.
∎

###### Proof.

### 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 a single sequence of slices.

###### Proof.

The probability it maintains performs better than $F(k)$ is equivalent to showing that none of the top-$k$ elements (out of $L$) are affected after $r$ deletion requests:

$$ $\mathbb{P}\left[F_{r}(\mathrm{SISA})\geq F(k)\right]=\left(1-\frac{k}{L}\right )^{r}.$ (18) $$

In S^3T, 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:

$$ $\mathbb{P}\left[F_{r}({S\textsuperscript{3}T})\geq F(k)\right]=1-\left(1-\left (1-\frac{k}{L}\right)^{r}\right)^{B}.$ (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 to be at least one prefix of length $k$ that has not been affected. Since there only $P(L,k)=\frac{L!}{(L-k)!}$ permutations of length $k$ extending the budget beyond $P(L,k)$ doesn’t work. Therefore, the correct probability is:

$$ $\mathbb{P}\left[F_{r}({S\textsuperscript{3}T})\geq F(k)\right]=1-\left(1-\left (1-\frac{k}{L}\right)^{r}\right)^{B^{\prime}},$ (20) $$

where $B^{\prime}=\min\left\{B,P(L,k)\right\}$.

Taking the difference between Eq. 20 and Eq. 18 and setting $\alpha=(1-k/L)^{r}$, we get:

$$ $\displaystyle\mathbb{P}\left[F_{r}({S\textsuperscript{3}T})\geq F(k)\right]- \mathbb{P}\left[F_{r}(\mathrm{SISA})\geq F(k)\right]$ $\displaystyle=1-(1-\alpha)^{B^{\prime}}-\alpha$ $\displaystyle=(1-\alpha)\{1-(1-\alpha)^{B^{\prime}-1}\}$ $\displaystyle=\zeta(1-\zeta^{B^{\prime}-1}),$ (21) $$

where $\zeta=1-\alpha=1-(1-k/L)^{r}$. This completes the proof.
∎

Discussion. In the above proof, we assumed that
$B$ sequences are randomly selected. In practice, we select diverse sequences using the iterative cyclic rotation algorithm. However, deriving a closed-form theoretical performance bound for the sequences generated using cyclic rotation is non-trivial. Intuitively, we expect the performance to be better as 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.

###### Proof.

### 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., $(S_{1},S_{2},S_{3},S_{4})$ and $(S_{2},S_{3},S_{4},S_{1})$. Since we 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 at all levels, $[1,L]$, in Algorithm 2.

###### Proof.

Let the bipartite graph, $G$, consist of vertices $V\cup V^{\prime}$, such that the edges $E\subseteq V\times V^{\prime}$. For a perfect matching to exist, every subset $W\subset V$ should satisfy:

$$ $|W|\leq N_{G}(W),$ (22) $$

where $N_{G}(\cdot)$ is the neighbourhood defined using the graph, $G$.

In our setup, the graph $G$ has vertices $V=\{1,\ldots,L\}$ and $V^{\prime}=\{1^{\prime},\ldots,L^{\prime}\}$, which indicate the elements in the permutation sequence. Every vertex $v\in V$ has $(L-i+1)$ edges to unique vertices in $V^{\prime}$ at the $i$-th iteration of the algorithm. Therefore, for all iterations $i\in\{2,\ldots,L\}$ (shown in Line 6 in Algorithm 2) the condition in Eq. 22 is satisfied and a perfect matching exists.

Since perfect matching selects a unique element in $V^{\prime}$, therefore no element is repeated at the same position in the BMS output. Therefore, BMS generates diverse sequences.
∎

###### Proof.

## Appendix B Implementation Details

In this section, we discuss the details of various algorithms and workflows within S^3T.
\localtableofcontents

Figure: Algorithm 1 Iterative Cyclic Rotation

### B.1 Iterative Cyclic Rotation

In the setting, where the deletion probabilities are uniform we use the cyclic rotation algorithm to 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 in Figure 10.

We present the pseudocode of the iterative cyclic rotation mechanism in Algorithm 1. First, we set the initial set to cyclic 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 1 is a simplified version of the actual algorithm. For some corner case budget values, we 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 $B$ permutations when all $L$ slices have equal deletion probabilities. We will leave the theoretical proof to future research.

Figure: Figure 10: An illustration of the sequences selected by the iterative cyclic rotation algorithm for different budgets. We observe that for budget $B\leq L$ the algorithm selects sequences generated by rotating the entire sequence. For budget $L<B\leq L(L-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.
Refer to caption: x10.png

Figure: Algorithm 2 BMS Sequence Selection Algorithm

### B.2 Bipartite-matching 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 $\mathcal{S}=(p_{1},p_{2},p_{3},p_{4})$, the scoring function computes the expected number of surviving slices after $t$ deletions:

$$ $\mathrm{score}[\mathcal{S},t]=4.(1-p_{1}-p_{2}-p_{3}-p_{4})^{t}+3.(1-p_{1}-p_{ 2}-p_{3})^{t}+2.(1-p_{1}-p_{2})^{t}+(1-p_{1})^{t}.$ (23) $$

The above equation is a function of $t$, which needs to be set by the user. In the general case, Eq. 23 can be written as:

$$ $\mathrm{score}[\mathcal{S},t]=\sum_{i=1}^{n}i.\left(1-\sum_{j=1}^{i}p_{j} \right)^{t}.$ (24) $$

Next, we describe the details of the Bipartite-matching based selection (BMS) algorithm in Algorithm 2. The objective of BMS is to select a set of $B\leq L$ diverse permutation sequences where sequences have a high score (Eq. 24). This algorithm starts by selecting $L$ different starting elements for the sequences in Line 4. Then, BMS iteratively selects the next element within each sequence. This involves constructing a bipartite graph between the last elements of the sequences seen so 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^{\prime}$. 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, ). Based on the matching, we select the next element for each permutation sequence (Line 18). BMS continues this process till all sequences $o\in\mathcal{O}$ have $L$ elements. Based on the budget, we output $B$ sequences from $\mathcal{O}$ that have the highest sequence scores.
For maximum weight perfect matching, (Tomizawa, ) provides an efficient algorithm with time complexity $O(n^{3})$, where $n$ is the number of nodes. Using this algorithm, the overall time complexity of BMS is $O(L^{4})$, where $L$ is the number of slices. The following result shows that BMS generates the most diverse sequence set.

###### Lemma 3 .

For a budget $B\leq L$, BMS returns the most diverse set of $B$ permutations.

We also validate the above result empirically and find that BMS produces a range of sequences with high scores (Figure 8). However, it remains an open question whether these outputs are optimal (while considering both diversity and scores).

Figure: 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.
Refer to caption: x13.png

The BMS algorithm can output up to $L$ diverse permutations. Extending it for a budget $B>L$ is non-trivial. Therefore, in this setting, we use a conditional sampling approach to generate diverse sequences. In conditional sampling, for each sequence, we sample slices one at a time based on their deletion probabilities (low deletion probabilities have a higher chance of being sampled). If a sampled sequence already exists in the selected set, it is discarded. An 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.

###### Lemma 3 .

### B.3 S 3 T Training Procedure

In this section, we provide an outline for the training procedure within the S^3T framework in Algorithm 3. S^3T 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 a unique sequence of slice sequence, $\pi(\mathcal{S})$. We return the complete set of models, $\mathcal{F}$. During inference, the user selects the best-performing model within each shard and deploys an ensemble of those models to production.

Figure: Algorithm 3 S^3T Training Procedure

Figure: Algorithm 4 S^3T Deletion Procedure

### B.4 Deletion Procedure

In this section, we describe the procedure when a deletion request arrives for an instance $x$ in Algorithm 4. We first locate the shard ID, $m^{\prime}$, where the instance $x$ belonged and iterate over all models trained on that shard. For each of these models, we locate the slice ID, $l^{\prime}$, of $x$ and deactivate all layers $\{l^{\prime},\ldots,L\}$ (as shown in Line 7). After that, if the model $f$ is still active, we add it to the set of modified models, $\overline{\mathcal{F}}$. S^3T uses the updated set to perform inference till a 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.

## Appendix C Experiments

In this section, we describe our experimental setup and present additional analysis experiments to evaluate the functioning of S^3T.

### C.1 Experimental Setup

We perform all experiments using PyTorch (Paszke et al., ) and Huggingface (Wolf et al., ) framework. Our experiments were run on NVIDIA A6000 GPUs. In Table 2, we report the common set of hyperparameters for S^3T fine-tuning experiments. All hyperparameters were set using a grid search with the Weights & Biases framework. We use an AdamW optimizer with the corresponding learning rates for each dataset (reported in Table 2). During fine-tuning of the models, we perform full-precision training for all settings except instruction tuning where we use 8-bit training.

**Table 2: We report the hyperparameters used in our experiments for fine-tuning S^3T across different benchmarks and Transformer model variants.**
|  |  | # Slices | # Layers/ | LoRA | LoRA | Learning | Epochs |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Dataset | Model | ($L$) | Slice | Rank ($r$) | ($\alpha$) | Rate |  |
| GLUE Benchmark |  |  |  |  |  |  |  |
| SST-2 | RoBERTaLARGE | 7 | 3 | 16 | 32 | $10^{-5}$ | 10 |
| COLA | RoBERTaLARGE | 7 | 2 | 8 | 16 | $4.10^{-4}$ | 30 |
| STS-B | RoBERTaLARGE | 7 | 3 | 16 | 32 | $10^{-4}$ | 30 |
| QNLI | RoBERTaLARGE | 7 | 3 | 8 | 16 | $5.10^{-5}$ | 30 |
| QQP | RoBERTaLARGE | 7 | 3 | 16 | 32 | $5.10^{-5}$ | 30 |
| MRPC | RoBERTaLARGE | 7 | 3 | 16 | 32 | $5.10^{-5}$ | 30 |
| MNLI | RoBERTaLARGE | 7 | 3 | 16 | 32 | $10^{-4}$ | 30 |
| SuperGLUE Benchmark |  |  |  |  |  |  |  |
| RTE | RoBERTaLARGE | 8 | 4 | 16 | 32 | $10^{-5}$ | 30 |
| WIC | RoBERTaLARGE | 12 | 2 | 16 | 32 | $10^{-4}$ | 30 |
| CB | RoBERTaLARGE | 12 | 2 | 16 | 32 | $10^{-4}$ | 30 |
| COPA | RoBERTaLARGE | 12 | 2 | 32 | 64 | $10^{-5}$ | 30 |
| BoolQ | RoBERTaLARGE | 7 | 3 | 16 | 32 | $10^{-4}$ | 30 |
| MultiRC | RoBERTaLARGE | 7 | 3 | 16 | 32 | $10^{-4}$ | 30 |
| Vision Benchmark |  |  |  |  |  |  |  |
| CIFAR-10 | ViTBASE | 6 | 2 | 16 | 32 | $2.10^{-3}$ | 15 |
| CIFAR-100 | ViTBASE | 6 | 2 | 16 | 32 | $2.10^{-3}$ | 15 |
| TinyImagenet | ViTLARGE | 6 | 4 | 16 | 32 | $2.10^{-3}$ | 15 |
| Instruction Tuning |  |  |  |  |  |  |  |
| Alpaca | Llama2-7B | 4 | 8 | 32 | 64 | $2.10^{-5}$ | 3 |
| Alpaca | Llama2-13B | 4 | 10 | 32 | 64 | $2.10^{-5}$ | 3 |
| Alpaca | Llama3-8B | 4 | 8 | 32 | 64 | $2.10^{-5}$ | 3 |

### 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 we found the top layers were easier to train at the start and a bottom-up approach didn’t converge. Note that our training process does not need to proceed in a 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,\ldots,i\}$. We found that this way of training helps in better convergence compared to the setup where we train every layer using a different slice.
Third, we analyze the cost of slice-wise training and find it to be comparable to full training. Considering that training cost is $c=O(nl)$, where $n$ is the dataset size and $l$ is the number of trainable layers (empirical evidence in Appendix C.3). For slice-wise training, we observe that $c=\sum_{i=1}^{k}(\frac{in}{k})(\frac{l}{k})=O\left(\frac{nl}{2}\right)$, which is of the same order as full training.

### C.3 Additional Experiments

In this section, we report analysis experiments to evaluate the S^3T’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 a small drop in performance (<5%). For instruction tuning in Figure 12 (middle),
we observe a negligible performance drop for most datasets except MMLU & ARC, which are more challenging open-ended QA benchmarks. For text classification in Figure 12 (right),
we observe an increased drop in performance for a few of the datasets.
We hypothesize that this occurs because the RoBERTaLARGE (used in text classification tasks) is a relatively weaker pre-trained model compared to Llama 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 it suggests that we can continue using the same model without retraining for a longer time.

Figure: Figure 12: Relative performance drop with an increasing number of deleted slices. We observe a relatively small performance drop for image classification and instruction tuning tasks while noticing a considerable drop for a few of the text classification datasets.
Refer to caption: x14.png

Figure: Figure 13: Performance impact of S^3T when allocated a different number of layers per slice: We observe that simply increasing the number of slices can lead to a significant performance drop. There is an optimal tradeoff between the total number of slices and the number of layers per slice.
Refer to caption: x15.png

Layer Allocation per Slice. This experiment aims to answer the question: how many slices can we pack into a model while still achieving good performance? We conduct an experiment where we allocate different numbers of PEFT layers per slice and also vary the number of slices. We report the results on the RTE dataset using RoBERTaLARGE in Figure 13. We observe that the performance is poor when the number of layers per slice is low. For example, when the number of layers per slice = 1, the performance improves as we increase the number of slices but again drops when the slice count is too high. This shows that it may not be feasible to train the model using many slices without a drop in performance. Overall, the performance variation depends on the underlying task and model, so the developer should select these hyperparameters based on their performance requirements.

Figure: Figure 14: (Left) Comparison of sequential training with S^3T using a PEFT model. We observe that S^3T’s performance gradually improves as it is trained on a larger number of slices, ultimately achieving similar performance to sequential training while being more efficient.
Refer to caption: x16.png

Sequence-based Training. In this experiment, we compare S^3T’s performance with sequential training. Sequential training involves training the entire PEFT model on a sequence of slices. This was used in (Kumar et al., ) to improve the retraining efficiency of SISA. In Figure 14, we report the performance of S^3T and sequential training using ViTBASE on CIFAR-10 and CIFAR-100 datasets. We observe that the performance of S^3T gradually increases as it is trained on more slices. Overall, we observe that S^3T achieves quite similar or outperforms sequential training. It is important to note that S^3T trains a significantly smaller number of parameters ($L$ times reduction compared to sequential training) but still achieves competitive performance.

Training Time. In this experiment, we evaluate the training time with a varying number of PEFT layers. In Figure 14 (right), we report the average training time over a constant number of steps using RoBERTaLARGE model. We observe that training time linearly increases as an increased number of LoRA layers are trained. This shows the effectiveness of our proposed S^3T framework, which only trains a small number of PEFT layers at each training stage.

Figure: Figure 15: We compare the scores (Eq. 24) of the generated sequences by BMS and sorted cyclic rotation. We observe BMS consistently outperforms cyclic rotation.
Refer to caption: x18.png

BMS vs. Cyclic rotation with Deletion prior. In this setting, we compare the BMS selection algorithm with a variant of cyclic rotation when the prior deletion probabilities are available. We perform cyclic rotation by first sorting the slices based on their deletion probabilities. For example, we sort the sequence with deletion probabilities: ($S_{1}$: 0.5, $S_{2}$: 0.4, $S_{3}$: 0.1) as: ($S_{3},S_{2},S_{1}$). Then, for a budget $B=3$, the stored sequences are: ($S_{3},S_{2},S_{1}$), ($S_{1},S_{3},S_{2}$), ($S_{2},S_{1},S_{3}$). 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, we report the total sequence scores (Eq. 24) obtained by BMS and sorted cyclic rotation for a 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 are the same as cyclic rotations are guaranteed to produce the maximum diversity for budgets: $B\leq L$.

**Table 3: Storage cost of S^3T under different training budgets. We show how the deletion rate increases with an increased storage cost. The overall storage cost of PEFT layers is minimal and is equivalent to storing an additional model.**
| Budget | Model (GB) | PEFT (GB) | Del. Rate |
| --- | --- | --- | --- |
| $B=1$ | 1.2 | 0.21 | 66.4 |
| $B=2$ | 1.2 | 0.42 | 86.9 |
| $B=3$ | 1.2 | 0.63 | 100.8 |
| $B=4$ | 1.2 | 0.84 | 107.8 |
| $B=5$ | 1.2 | 1.05 | 110.1 |
| $B=6$ | 1.2 | 1.26 | 124.1 |

Storage Costs. In this experiment, we evaluate how the storage cost of S^3T grows with an increasing budget and its effect on the overall deletion rate. In Table 3, we report the storage costs and deletion rate of training ViTLARGE 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 the budget and storage cost increases there is 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.

## Appendix D Broader Impact

We present a scalable approach to perform exact unlearning in production systems. We hope that this framework will be adopted by organizations and enable a cost-effective way to ensure the privacy requests of various users. In general, unlearning systems are susceptible to attacks where the adversary may design deletion requests in a way to 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 our proposed framework, S^3T. Future works can focus on the identification of malicious unlearning requests.

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 3
presentation: 3
questions: 1.	With 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.
2.	How does increasing the number of shards and slices impact model accuracy and storage requirements? An ablation study on this would add valuable insight.
3.	A comparison of S3T’s efficiency in terms of time or FLOPs against the baseline would clarify its computational advantages.
4.	In 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.
5.	How does S3T’s storage requirement compare to SISA’s, particularly with frequent deletion requests?
soundness: 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.
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.
weaknesses: W1.	There 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.

W2.	It 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.

W3.	The 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. 

W4.	For 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?

W5.	I 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? 

My score is based on the weaknesses mentioned above. Give clarifications, I am willing to raise my score.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Please refer to the comments in Weaknesses.
soundness: 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.

++ The LoRA-based training solution makes S3T practical in application as it is compatible with many Transformer-Based models, including small and large models. 

++ The theoretical analysis of S3T’s deletion rate and performance retention metrics is rigorous. 

++ The writings and figures of the paper are easy to follow.
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.
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.

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

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

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: - What does "Total time" refer to in Figure 9, and in which units is it measured?
- Could you elaborate on the setting where budget B < L?
- Could you explicitly provide answers to RQ2 and RQ3 in the text, similar to how RQ1 is addressed?
- In Figure 1, it’s unclear that the shards are disjoint—can you clarify this?
soundness: 3
strengths: - Theoretically shown that S3T achieves provably better deletion guarantees than existing approaches.

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

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

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

Additionally, the authors use LoRa for slicewise training and present methods for selecting diverse permutations under budget constraints.
weaknesses: - The paper exhibits minor weaknesses due to lack of clarity and ambiguity; for detailed points, please refer to the questions provided.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
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?
2) 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?
3) How does the net storage cost of S$^3$T compare to SISA when B > L and B < L?
4) The performance of ProtoSISA seems to be almost overlapping with SISA? Why is this so?
soundness: 4
strengths: - This is a well written paper.
- The paper focuses on a very relevant setting involving PEFT for unlearning. 
- 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. 
- 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.
- 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.
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.
weaknesses: - Depending upon the model and the dataset, S$^3$T can result in lower training performance compared to full training. 
- No code is provided, however the authors promise to release it with the final version.

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

Meta-review: This work proposes a method for exact unlearning that a relies on learning (and combining) multiple models on disjoint data shards. Learning of the models leverages parameter efficient fine-tuning to enable parameter isolation. The methodology is clearly described and positioned with respect to the state of the art. The authors produced compelling experimental evidence to validate the approach, suggesting strong performances. They also discussed the computational complexity of the method. Most reviewers voted for acceptance and all were satisfied with the clarifications provided by the authors during rebuttal.

Decision: Accept (Poster)