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

We would like to thank the reviewer for their detailed comments and suggestions.

No code is provided, however, the authors promise to release it with the final version.

We have submitted the code along with this submission. Please let us know if you have any issues accessing it on Openreview.

Include limitations and discuss future directions.

Thank you for the suggestion. We have included a limitation and future direction section in Appendix D of the paper.

Are results in Table 1 with B = 1? When B > 1, will using an ensemble of models across different slice sequences enhance performance?

The results in Table 1 have $m=1$ shards and $B=1$ because we are comparing the performance of our sequential training with full training on the entire data.

Thank you for the suggestion. We perform a small-scale experiment to evaluate the impact of using an ensemble of models trained on different slice sequences. We report the results in Appendix C.3 (Ensemble of Slice Sequences). We observe that increasing the number of models improves performance initially, but this improvement plateaus as the model count increases. We do not use an ensemble of models within a shard to maintain a low inference cost and have a lightweight system.

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?

We evaluate this scenario by using an ensemble of models trained on slice sequences of different lengths. We report the results in the table below.

Specifically, we consider a ViT-base model trained on different slice sequences. We observe that a model trained with 3 slices achieves a similar performance to an ensemble of models trained with 3 and 2 slices. Including a model trained with a single slice hurts the overall performance. Therefore, using an ensemble of models instead of the best performing model may not be a good idea in the unlearning framework.

How does the net storage cost of S3T compare to SISA when B > L and B < L?

In $S^3$T, we need to store $B$ models per shard. Therefore, the total storage cost is $mB$, which grows linearly with the budget $B$.

The performance of ProtoSISA seems to be almost overlapping with SISA? Why is this so?

ProtoSISA uses a prototypical classifier along with SISA. Our experiments using the ViT-base transformer show that both SISA and the prototypical classifier achieved similar performance. Moreover, we use a weighted combination of the decisions of each of the predictors (SISA and prototypical) to obtain the final prediction.

In our current experiments, we assigned a weight of 0.9 to SISA and 0.1 to the prototypical classifier, which leads to similar results. We have added new experiments (Appendix C.2, Baseline Ablations) with SISA weights of 0.5 and 0.3. In these settings, we observe that ProtoSISA’s performance varies from SISA. Specifically, ProtoSISA can boost SISA’s performance when the number of deletion requests is high.

We would like to thank the reviewer for their detailed comments and suggestions.

What does "Total time" refer to in Figure 9, and in which units is it measured?

The total time in Figure 9 refers to the overall time spent processing $n$ unlearning requests. It is reported in hours. It includes both the retraining and checkpoint swapping time. We have mentioned this in the paper now.

Could you elaborate on the setting where budget B < L?

Thank you for the question. We believe this question is about how the sequence selection is performed when $B < L$.

Uniform prior. In this case, we generate $L$ sequences using the iterative cyclic rotation algorithm. For $B<L$, we can choose any $B$ out of the $L$ generated sequences as they are equally diverse and have maximum edit distance among each other.

Known prior. In this case, we generate $L$ sequences using the BMS algorithm. For $B<L$, we greedily select the top $B$ sequences with the maximum $score[\mathcal{S}, t]$.

Could you explicitly provide answers to RQ2 and RQ3 in the text, similar to how RQ1 is addressed?

Please find the responses below:

(RQ2): We find the S3T significantly improves the deletion rate of existing unlearning systems (as shown in the results of Figure 6). We also observe that the overall unlearning time of S3T is much better than the baselines (Section 4.3, Deletion Time). S3T requires more offline training and needs to train $B$ models per shard.

(RQ3): The sequence selection algorithms presented in the paper are effective. They perform significantly better than naively sampling sequences both in terms of sequence quality (when deletion prior is available) and diversity. The detailed results are shown in Figure 8 (Section 4.3).

We have incorporated these conclusions in Section 4.2 and Section 4.3 respectively.

In Figure 1, it’s unclear that the shards are disjoint—can you clarify this?

Thank you for pointing this out. The shards shown in the figure are disjoint. We have updated Figure 1 and its label to showcase the change.

We would like to thank the reviewer for their detailed comments and suggestions.

Explain how S3T has stronger privacy guarantees

$S^3$T is an exact unlearning technique. Exact unlearning techniques function by eliminating or retraining all model components that use the unlearnt instances. Since these techniques do not use any component trained on the unlearnt instance, they provide stronger privacy guarantees.

$S^3$T performs unlearning by switching off PEFT layers trained using the unlearnt request. Therefore, the model at any point does not have any component that was trained using the unlearnt instance. This is how $S^3$T provides strong privacy guarantees.

We have added a line to explain this in Section 2, Lines 98-99.

Explain the utility of increased training cost to reduce re-training in the context of LLMs

Minimizing retraining costs for production systems is crucial, as it requires taking the system offline every time a deletion request is spawned, directly impacting consumers. Moreover, if the deletion requests affect the same slice, it can lead to redundant re-training.

Even though we are training multiple models, this process can be easily parallelized and it is quite fast in practice since we only train PEFT parameters in Transformer models. In contrast to this, the re-training process is sequential and it is dependent on the deletion request.

The paper could conduct another experiment in which the slice’s arrival probability is more unpredictable.

We have added a new experiment to evaluate the deletion rate of $S^3$T when the deletion requests are sampled from a non-uniform prior. Please see the details of the setup in Appendix C.3 (Deletion with non-uniform prior). We observe that $S^3$T can handle significantly more deletion requests compared to the uniform prior, as the prior is known. Overall, we observe that the deletion rate shows a gradual increase as the budget rises; however, it remains notably high even with a low budget.

Would incorporating a retraining strategy improve the deletion rate? Question about the necessity of retraining.

Yes, your observation is correct that the deletion rate does not scale linearly.

In fact, increasing the budget $B$ beyond the number of slices $L$ doesn’t improve the deletion rate at all. We prove this in Lemma 1 (where the deletion rate is a function of $\min(B, L)$) and show this linear growth empirically in Figure 6 (right). Even though budgets $B>L$ don’t improve the deletion rate they help improve the performance of the available models (shown in Lemma 2).

Retraining after a certain point will help improve the performance. However, frequent retraining should be avoided, as multiple deletion requests affecting the same data slice could lead to redundant retraining of the same layer. The user should set a performance threshold based on their application and retrain the components only when the overall performance drops below it.

How does increasing the number of shards and slices impact model accuracy and storage requirements? An ablation study on this would add valuable insight.

We perform an experiment to investigate the impact of shard count. We train ViT-base using different shard counts on the CIFAR100 dataset. In the table below, we observe a slight decline in performance as the number of shards increases. This is expected as each model is trained on a smaller number of instances. This observation is similar to the observation made by the authors in [1] (see Figure 6 in [1]).

We conducted experiments to investigate the impact of the number of slices (and the number of PEFT layers allocated to each slice) on model performance, as detailed in Figure 13 (Appendix C.2). We observe that using either too many or too few slices negatively impacts performance. Ideally, we should select a balanced setting to optimize performance using this experiment. Additionally, the number of slices doesn’t have any impact on the storage as all the updates are stored in the same model.

[3] Machine Unlearning, Bourtoule et al., 2020

A comparison of S3T’s efficiency in terms of time or FLOPs against the baseline would clarify its computational advantages.

We have reported these results in the main paper. Please find the unlearning time comparison in Figure 9 (Section 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.

Figure 9 does include the retraining time of models. The small steps in the plot for $S^3$T and SISA indicate the retraining stages where the time required is more. The flat portions of the curve indicate the checkpoint-swapping phase.

We report the exact numbers for the plot below:

Average re-training time for $S^3$T: 4.32 hours

Average re-training time for SISA: 4.85 hours

Checkpoint swapping time (same for both): 1.62 seconds

How does S3T’s storage requirement compare to SISA’s, particularly with frequent deletion requests?

The storage requirements of these systems are independent of the deletion requests. They are a function of the number of shards ($m$), slice count ($L$), and budget ($B$).

SISA: $mL$ (for each of the $m$ shards, one checkpoint after training each of $L$ slices)

$S^3$T: $mB$ (for each of the $m$ shards one checkpoint the allocated budget $B$)

Note that $S^3$T doesn’t need to store a checkpoint after training each slice as they are stored in the PEFT layers of the same model.

We would like to thank the reviewer for their detailed comments and suggestions.

Question about top-to-bottom training strategy, the reasoning behind it, and use of pre-trained models.

The top-to-bottom training strategy in $S^3$T does not use completely different data slices while training each model layer. We take a cumulative approach during training. For example, we train the final layer using slice $S_1$, the next layer is trained data from slices $S_1+S_2$, and this continues. We found that this approach leads to better convergence compared to training different layers separately on just slices $S_1$, $S_2$, and so on.

You are correct that it may not be possible to apply this approach for training a model from scratch. In our work, we assume that the user trains a pre-trained model on private data, as this is the most commonly used setting in modern times. We state this assumption in the problem setting, Lines 144-145.

We did try training models in a bottom-up fashion but it doesn’t converge. It seems that training only the bottom layers while completely freezing all the top layers is not effective for fine-tuning. This is intuitive because several past works [1, 2] have shown that the final layers are affected most during fine-tuning.

[1] What Would Elsa Do? Freezing Layers During Transformer Fine-Tuning. Lee et al. 2019 [2] How fine can fine-tuning be? Learning efficient language models. Radya-Dixit et al. 2020

Question about whether PEFT is integral to the technique.

The choice of the PEFT method is not integral to our fine-tuning technique. This layer-wise training can be performed while using other PEFT (like adapters) or even full-finetuning of the layers. We use LoRA in our work as it is the most popular PEFT technique.

We present the results of layer-wise full fine-tuning of ViT-base on various datasets in the table below. We observe that layer-wise finetuning progressively improves performance similar to PEFT methods. It is also able to achieve a similar performance to the overall full-finetuning of the model.

Novelty of S3T and comparison with approximate unlearning baselines.

We would like to clarify that BMS is not an off-the-shelf method. We propose BMS to select sequences with a given deletion prior. BMS uses bipartite matching to select the next element in the constructed sequences. Similarly, layer-wise training and switching off of LoRA layers haven’t been used in the context of exact unlearning.

The mentioned approaches (E2URec, Bad-T, NegGrad, NegKL, RecEraser) are approximate unlearning techniques while our method $S^3$T is an exact unlearning method. These approaches are not directly comparable to our exact unlearning method, $S^3$T.

Approximate unlearning techniques post-process model parameters to ensure unlearning. Since this is not exact, the unlearnt instances can still have a non-zero influence on the model, which is evaluated on benchmarks. In contrast, exact unlearning can guarantee perfect unlearning because it eliminates or retrains all model components that use the unlearnt instance.

Even though the unlearning is perfect, exact unlearning is more expensive than approximate techniques. Therefore, most of the evaluation is focused on the efficiency of unlearning compared to full retraining and other exact unlearning baselines. We provide extensive experiments to evaluate the efficiency and overall model performance in Section 4 and Appendix C.3.

Utility of initial LORA layers

You are correct that if the deletion requests are not affecting the final layers the initial LORA layers are not impacted and therefore are not switched off. However, these layers are still being used for performing inference and are pivotal for the overall model performance.

Please let us know if you have any further details or additional questions.

Details of SISA implementation

We consider the setting where SISA falls back to the best available checkpoint instead of retraining after each deletion request. We use this setting for all baselines and experiments. This setup is realistic since taking down a production system for retraining can affect customers and disrupt business operations. This also helps us measure the deletion rate – the expected number of deletion requests a system can handle without requiring to be retrained.

SISA stops working after 40 deletion requests because it does not have any available checkpoints. This is different from the implementation in [3], where SISA components are retrained after every deletion request. We observe that $S^3$T can handle significantly more deletion requests while incurring a lesser performance impact.

[3] Machine Unlearning, Bourtoule et al. 2020