Tracing Privacy Leakage of Language Models to Training Data via Adjusted Influence Functions

Assume that $L$ is smooth and convex, and a model is well-trained on a training set using empirical risk minimization. The optimized parameters can be represented as $\theta_{0}=\operatorname*{arg\,min}_{\theta\in\Theta}\frac{1}{n}\sum_{i=1}^{n}L(z_{i},\theta).$ If the weight of a sample $z_{k}$ is marginally reduced by $\epsilon_{k}$, the parameters are re-optimized as $\theta_{\epsilon_{k}}=\operatorname*{arg\,min}_{\theta\in\Theta}[\frac{1}{n}\sum_{i=1}^{n}L(z_{i},\theta)-\epsilon_{k}L(z_{k},\theta)].$ HIFs with respect to parameters $I^{hif}_{param}$ are derived as follows:

where $H_{\theta_{0}}$ is the Hessian matrix of the trained model (Koh and Liang 2017). The HIFs with respect to loss $I^{hif}_{loss}$ can be formulated as:

HIFs have found applications across various domains (Fisher et al. 2023; Lee et al. 2020; Chen et al. 2023; Xia et al. 2024), and a variety of methods have been proposed to mitigate computational costs (Agarwal, Bullins, and Hazan 2017; Martens and Grosse 2015; George et al. 2018; Schioppa et al. 2022). As discussed above, to mitigate the issue that IFs always trace back to a small group of training samples, RelatIF formulates the task of tracing the most influential training samples as an optimization problem, with an additional constraint:

By simplifying this optimization problem, $\theta$-RelatIF is obtained, which essentially performs a sample-wise normalization:

To reduce the computational cost, the Hessian matrix in IFs sometimes is assumed as identity matrix $Id$. With that, derived from $\theta$-RelatIF, we have Gradient Cosine IF $I^{cos}_{loss}(z_{test},z_{k}):=\frac{\nabla_{\theta}L(z_{test},\theta_{0})\nabla_{\theta}L(z_{k},\theta_{0})}{\|\nabla_{\theta}L(z_{test},\theta_{0})\|_{2}\|\nabla_{\theta}L(z_{k},\theta_{0})\|_{2}}.$

However, in (Barshan, Brunet, and Dziugaite 2020), the constraint in (5) lacks theoretical support, and the evaluation metrics do not provide direct evidence that the traced samples are indeed the most influential for the test samples under examination.

As stated in Section 2.1, effectively utilizing HIFs needs assumptions which do not hold in most deep learning settings. Thus, TTIFs model the training trajectory of up/down weighting training sample to avoid these assumptions (Pruthi et al. 2020; Schioppa et al. 2023).

Consider a deep learning model trained by mini-batch SGD optimizer. For each training step, model parameters are updated as:

where $\eta_{t}$ is learning rate (LR) at $t$ step, $\mathcal{L}_{t}(\epsilon_{k},\theta_{\epsilon_{k},t})$ denotes the mini-batch loss at $t$ step after up/down weighting the training sample $z_{k}$. That said, the parameters trained after T time steps are:

where $\theta_{init}$ is the initial parameter before training.

To capture the actual influence with SGD training, $I_{param}^{sgd}(z_{k})$ is defined as the derivative of $\theta_{\epsilon_{k},T}$ with respect to $\epsilon_{k}$:

where $H_{t}$ is the Hessian matrix of $\mathcal{L}_{t}$. To avoid computation of $H_{t}$, TracIn (Pruthi et al. 2020) ignores $II$ in (9) resulting in:

where $batch_{t}$ is mini-batch used at $t$ time step. While TracIn provides an effective way to track training trajectories, the additive assumption is questioned by (Guu et al. 2023; Schioppa et al. 2023) and $II$ in (9) cannot be simply dropped.

When $II$ in (9) is brought into consideration, IFs are encountered a theoretical challenge, as discussed below. Assume that both $\mathcal{L}_{t}$ and $\nabla_{\theta}\mathcal{L}_{t}$ with respect to $\theta$ are Lipschitz continuous with a Lipschitz constant $G$, and that $\sup_{t,\theta\in R}\|\mathcal{L}_{t}(\epsilon_{k},\theta)-\mathcal{L}_{t}(0,\theta)\|\leq C\epsilon_{k}$, where $C$ is a constant. By Gronwall inequality (Gronwall 1919), Schioppa et al. (Schioppa et al. 2023) derive an upper bound for model divergence with respect to $\epsilon_{k}$:

To be Taylor expanded, IFs make critical assumptions that $\|\theta_{\epsilon_{k},T}-\theta_{0,T}\|$ is $O(\epsilon_{k})$ and $\|\frac{d(\theta_{\epsilon_{k},T}-\theta_{0,T})}{d\epsilon_{k}}\|$ is $O(1)$. However, (11) shows that the assumption of $\|\theta_{\epsilon_{k},T}-\theta_{0,T}\|$ being $O(\epsilon_{k})$ may not hold. This leads to the conclusion that IFs may only be able to accurately estimate influences within a very limited time step.

While (11) seems to pose a theoretical challenge for IFs, this study derives a less conservative bound, and proves that the effectiveness of IFs is determined by the norm of gradient. Furthermore, this paper not only shows the necessity of introducing delta $\delta$ in (5), but also mitigate the crisis raised by (11) which indicates that the influence of a sample may not be estimated by a function of $\epsilon_{k}$.

Let $z_{i}\in D$ consists of $m$ labels $z_{i}=\{z_{i,1},...z_{i,m}\}.$ The loss function for each label $z_{i,j}$ is represented by $l$, and the overall loss $L(z_{i},\theta)$ is given by the average of the individual losses, i.e., $L(z_{i},\theta)=\frac{1}{m}\sum_{j=1}^{m}l(z_{i,j},\theta)$.

Assume that $z_{target}\in D$ encapsulates unique knowledge that directly or indirectly lead to model output $z_{test}$ (e.g., privacy leakage) during inference stage. The objective of this work is to utilize IFs to identify $\widehat{z_{target_{t}}}$ such that:

A successful trace is one where the traced target $\widehat{z_{target}}$ matches the ground truth $z_{target_{t}}$; otherwise, it is considered a failed trace. Accordingly, the tracing accuracy is defined as:

where $N_{success}$ is the count of successful traces and $N_{tracing}$ represents the total number of test cases during the inference stage.

Assume models are trained by a mini-batch SGD optimizer and a Learning Rate (LR) scheduler. After a sample is slightly down weighted, the change of model parameters at each training step is:

where $B_{z_{i},t}=\left\{\begin{aligned} &1&\text{if }z_{i}\in batch_{t}\\ &0&\text{otherwise}\end{aligned}\right.$.

Proof of Lemma 1 can be found in Appendix A.1.

As discussed in Section 2, the fundamental assumption of IFs is $\lim_{T\to\infty}I_{param}^{sgd}(z_{k,j})$ is $O(1)$. The following theorem demonstrates a sufficient condition for the existence of IFs in most deep learning settings.

Proof of Theorem 1 can be found in Appendix A.2.

Notably, the definition of LR scheduler in Theorem 1 aligns with default HuggingFace (Wolf et al. 2020) and most LMs LR schedulers with or without warmup stage, such as Linear, Constant and Exponential LR schedulers. Theorem 1 leads to a strong conclusion that the influence of $z_{k,j}$ may not exist if the gradient norm of $z_{k,j}$ is not decreasing or approaching to 0.

Additionally, even if $I^{sgd}_{param}(z_{k,j})$ converges, the estimated LOOR parameters $\theta_{\epsilon_{k,j},T}^{if}=\theta_{0,T}+\epsilon_{k,j}I_{param}^{sgd}(z_{k,j})$ may not be accurate. Removing a token from a dataset typically causes minor changes in parameters, which implies that $\|\theta_{\epsilon_{k,j},T}\|_{2}$ should be small. If the gradient norm of a token is large, the RHS of (16) will also be large, probably resulting in inaccurate estimation of $\theta_{\epsilon_{k,j},T}$. Therefore, we infer that the accurate estimation should be obtained by computing $I^{sgd}_{param}(z_{k,j})$ for tokens with small gradient norm.

Next, we use Lemma 1 to identify the conditions under which $I_{param}^{sgd}(z_{k,j})=I_{param}^{hif}(z_{k,j})$, and show that the estimation errors between current IFs and $I_{param}^{sgd}(z_{k,j})$ can be amplified by the gradient norm of $z_{k,j}$.

Proof of Corollary 1 can be found in Appendix A.4.

As demonstrated by Corollary 1 and 2, the upper bound of errors for HIFs and TTIFs can increase as the gradient norm becomes larger. More importantly, we conducted the experiment on MNIST dataset used in (Koh and Liang 2017), which verifies the consistency between $I_{loss}^{hif}$ and LOOR. We also trained a Logistic Regression Model on the same dataset with $batch\_size=50$ and $T=5000$, but changing the optimizer to mini-batch SGD. For 100 training samples, we computed HIF and TTIF as well as performed LOOR. The results on the discrepancies among the approximated $\theta_{\frac{1}{n},k}^{if}$ with IFs and the accurate $\theta_{\frac{1}{n},k}^{loor}$ with respect to the gradient norm of the samples are shown in Figure 1. Note that $\epsilon_{k}=\frac{1}{n}$ here, which means removing the corresponding sample from the dataset. It is clear that the estimation errors of IFs grow linearly with respect to gradient norms, aligning with the theoretical analysis above.

In our experiments on privacy tracing, we observed that current IFs always traced back to training samples containing tokens with large gradient norms. However, by performing LOOR, the actual influence on model parameters can be very small, sometimes even zero (examples can be found in Appendix A.8). When the influences of tokens with large gradient norms are overestimated, the well-estimated influence of $z_{target}$ can be overshadowed. Therefore, in the next section, we propose Adjusted Influence Functions to reduce the weights of influence scores calculated from large gradient norms.

Based on (10), we adjust TTIFs by introducing a function $A$ of the gradient norm, which yields:

where $A(v)=W(\|v\|_{2})v$, and $W:R\rightarrow R$ is monotonically decreasing function. $W$ serves an index of estimated influences, assigning larger weights to smaller gradient norms. $A$ is applied twice to further penalize the sample with large norm of gradient. Similarly, based on (4), HIFs can be adjusted as:

To reduce computational cost, by only considering last time step, we propose HAIF to trace the most influential training samples with the following form:

In our experiments, HAIF utilizes $A(v)=\frac{v}{\|v\|_{2}}$. HAIF-T is defined as $I_{loss}^{haif-t}(z_{test},z_{k}):=\nabla_{\theta}L(z_{test},\theta_{0,T})\sum_{j=1}^{m}A(\nabla_{\theta}l(z_{k,j},\theta_{0,T}))$ which only adjusts gradient token-wise serving as an ablation study. In comparison with $\theta$-RelatIF (6), which performs sample-wise gradient normalization, HAIF adjusts the weight of each token based on its gradient norm. If tokens with large gradient norms are not adjusted, their gradients may dominate the overall sentence gradient, thereby affecting the tracing performance.

We detail the algorithm for implementing HAIF in Appendix A.5, which is more computationally efficient than current IFs and can accurately trace the most influential samples.

In order to answer the previous questions, we begin with synthesizing two datasets to have groundtruth for tracing: PII Extraction (PII-E) dataset and PII Complex Reasoning (PII-CR) Dataset. Dataset examples can be found in Appendix A.6. Please note that, all PIIs (e.g. name, date of birth and phone number) in this work are synthesized with Faker ¹¹1https://github.com/joke2k/faker. No real individual privacy is compromised.

We use classical GPT2 series and QWen1.5 series (one of the SOTA open-source LLMs (Huang et al. 2023)), and use PII-E and PII-CR datasets to fine-tune models with various series and scales. Generally, increased parameters and advanced architectures enhance PII extraction, with all PII types except DOB posing extraction challenges due to their length and uniqueness variations. A similar pattern is observed in models trained on PII-CR dataset, but the need for reasoning alongside memorization reduces prediction accuracy compared to the PII-E dataset. More details can be found in Appendix A.7.

Let us revisit a key statement from Sections 3.1 and 4.1, which considers the groundtruth $z_{target}$ for a prediction $z_{test}$ is the corresponding pretraining data from the same virtual data subject.

Previous researchers (Koh and Liang 2017) regard LOOR as the gold standard . However, due to its sensitivity to training hyperparameters (K and Søgaard 2021), detection of poisoned training data is argued to be a better metric. In our context, considering the uniqueness of PIIs, pretraining data leading to PII leakage aligns with the definition of poisoned data.

We perform LOOR on PII-E and PII-CR and training details can be found in Appendix A.9. Table 1 shows the agreement ratio (which equivalent to tracing accuracy of LOOR) of the expected target and LOOR.

For PII-E dataset, the agreement ratio reaches 100%. Despite the dispute over the gold standard and long tail issue, IFs should identify the most influential pretraining sample for all $z_{test}$s in PII-E dataset. However, the agreement ratio on PII-CR dataset is low. We believe this is because predicting the correct PII requires the model to remember the knowledge in the corresponding pre-training data and reason based on this knowledge, which is influenced by other pre-training data. Both factors affect the loss of $z_{test}$.

We compare the tracing accuracy of five SOTA influence functions (IFs) on various model series, scales, datasets, and PII types. We select five SOTA IFs discussed in Section 2 as baselines, i.e. EK-FAC (Grosse et al. 2023), LiSSA (Bae et al. 2022; Koh and Liang 2017), RelatIF (Barshan, Brunet, and Dziugaite 2020), TracInCP (Pruthi et al. 2020), GradientProduct and GradientCosine. The detailed configurations of IFs are listed in Appendix A.10.

To further validates the effectiveness of the proposed HAIF, we conduct experiments on the real-world pretraining dataset, CLUECorpus2020 (Xu, Zhang, and Dong 2020) The text is tokenized and concatenated to form the pretraining dataset, where $n=100$ and $m=256$. The test set mirrors the training set, with the addition of two hyperparameters, offset and length, to control the test loss, defined as $L(z_{test_{i}},\theta)=\sum_{j=offset}^{offset+length}l(z_{i,j},\theta)$. Here, the offset simulates the user prompt, and the length denotes the model response length. Through LOOR experiments, each $z_{i}$ is the most influential training sample for $z_{test_{i}}$. According to previous experiments, the best baseline occurs while using QWen1.5-0.5B; thus it is employed to test various IFs under different lengths and offsets.

Fig. 2(a) illustrates that without introducing token offset, RelatIF, EK-FAC, GradientCosine, and HAIF exhibit comparable tracing accuracy as token length varies. This can be attributed to the fact that large gradient norms are mainly found in the initial tokens. Therefore, when the $offset=0$, $z_{test_{i}}$ and $z_{i}$ share identical gradients with large norms, enabling RelatIF, EK-FAC and GradientCosine to maintain high tracing accuracies. However, as depicted in Fig. 2(b), the introduction of an offset (which simulates user prompts) leads to a decrease in tracing accuracy for all IFs, with the exception of HAIF. The robustness of HAIF is further demonstrated in Fig. 2(c), where HAIF maintains its performance trend, unaffected by the increase in token offset. It is noteworthy that the tracing accuracy improves with token length, regardless of token offsets. Considering that user prompts are typically not empty and privacy information typically comprises a limited number of tokens, HAIF outperforms all SOTAs in such scenarios.

This work implements IFs to trace back to the most influential pre-training data to address the concern in privacy leakage in LMs. Our analysis reveals that tokens with large gradient norms can increase errors in LOOR parameter estimation and amplify the discrepancy between existing IFs and actual influence. Therefore, we propose a novel IF, HAIF, which reduces the weights of token with large gradient norms, providing high tracing accuracy with less computational cost than other IFs. To better validate the proposed methods, we construct two datasets, PII-E and PII-CR, where the groundtruth of privacy leakage can be located. Experiments on different model series and scales demonstrate that HAIFs significantly improve tracing accuracy in comparison with all SOTA IFs. Moreover, on real-world pretraining data CLUECorpus2020, HAIF consistently outperforms all SOTA IFs exhibiting strong robustness across varying prompt and response lengths.