Differential Privacy of Cross-Attention with Provable Guarantee

Q4: Has the problem of private distance queries been studied in the literature? If so, it would be helpful to include some related work.

Private distance queries have been studied in the literature [2,3,4]. We have updated them in Section 4.2 in the revised version Line 349-354.

Q5: The initialization time complexity and query time complexity in the abstract do not include $d$. Is this a typo?

Thank you for your observation. This is not a typo. We use the polynomial kernel method, which maps a $d$-dimension vector to $r$-dimension, where $r \ge d$ by the polynomial method. Thus, our initialization and query time depends on $d$, which is contained in $l=O(r\log(dR/(\epsilon_s p_f)))$ Line 249, and we use $\widetilde{O}$ to hide the log dependence. We have revised the paper to contain a formal definition of $\widetilde{O}$ in Line 154-157.

[1] Dwork, C., & Roth, A. (2014). The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science.

[2] Huang, Z., & Roth, A. (2014). Exploiting metric structure for efficient private query release. In Symposium on Discrete Algorithms (SODA’14).

[3] Backurs, A., Lin, Z., Mahabadi, S., Silwal, S., & Tarnawski, J. (2024). Efficiently Computing Similarities to Private Datasets. ICLR’24.

[4] Liu, E., Hu, J. Y. C., Reneau, A., Song, Z., & Liu, H. (2024). Differentially private kernel density estimation. arXiv preprint arXiv:2409.01688.

[5] Song, Z., Woodruff, D. P., & Zhong, P. (2019). Relative error tensor low rank approximation. In Symposium on Discrete Algorithms (SODA’19).

[6] Wang, S., Gittens, A., & Mahoney, M. W. (2019). Scalable kernel k-means clustering with nystrom approximation: Relative-error bounds. Journal of Machine Learning Research (JMLR’19).

We thank the reviewer for their valuable suggestions. We provide our response below and hope it will address your concerns.

W1.1: It is unclear what information is protected in this paper. It is necessary to clearly state which parts of the input are private (K and V?) and which parts of the output are public (Q?).

K and V are values stored in the memory and disks, and Q is obtained only when the user types its input. Thus, K and V are private assets protected in the model, and Q is public. We want to emphasize that we ensure the whole cross-attention process is DP ensuring privacy guarantee. We revised our paper to add this discussion in Line 223-226.

W1.2: Moreover, since each row of K is derived from one word in the input, the proposed algorithm seems to only protect word-level privacy.

We thank the reviewer’s valuable comments. We agree that our neighbor dataset is defined based on word-level so that we protect word-level privacy. Our methods can still provide some sentence-level privacy as we protect every word, e.g., every token in a sentence may be perturbed. How to build a data structure designed for sentence-level privacy protection is an interesting and challenging topic. One thought is to use the notion of group privacy in [1] which states the neighbor dataset can differ in multiple entries. We are willing to discuss more per the reviewer’s request.

W2: The paper does not contain any experiments, making it difficult to evaluate whether the obtained errors fall within a reasonable range.

Thank you for the thoughtful feedback. We acknowledge that empirical validation can offer valuable insights into real-world performance; however, implementing our theoretical framework would require significant engineering effort to address system-level challenges, such as developing distributed algorithms and efficiently implementing polynomial kernel methods on GPUs. These challenges fall beyond the scope of our theoretical contribution.

Our primary contribution lies in providing the first mathematically rigorous privacy guarantees for cross-attention, with provable bounds on error, computational complexity, and memory requirements. We aimed to address the fundamental question: "Is it possible to make cross-attention differentially private with provable guarantees?" Our work answers this affirmatively, offering concrete mathematical bounds. We believe is a significant contribution in itself, which is also supported by Reviewer s8of that “the paper is already in the current state fairly dense.”

W3: Does this imply that the algorithm can be modified to involve only additive errors, or does the $n^{-1}\epsilon_s$ term still exist?

After removing $\alpha$, relative error $n^{-1} \epsilon_s$ would still exist since it is introduced by the polynomial kernel method in Section I Lemma I.5. Also if $n$ gets larger, the relative error would be smaller. Besides, relative errors are actually good criteria and many existing works use relative errors, e.g., [3,5,6].

Q1: The definition of differential privacy in the article is unclear.

The $n \times d$ matrix we study can be viewed as a set of $d$ vectors with length $n$. And in our Algorithms, we initialize the $n \times d$ matrix as $d$ times of a dimension $n$ DPTREE data structure, which utilizes $\mathbb{R}^n$ as inputs. Thus, the definition of DP applies to this scenario.

Q2: I do not understand why we can directly discard D in this context.

$D$ depends on $A$, which is calculated using $Q$ and $K$, serving as a normalizing factor that gathers all the information. As discussed in W1.1, we consider $K$ and $V$ as private assets. In our data structure, we store both $K$ and the corresponding noises. When computing $AV$, we use the perturbed $K$ to ensure DP guarantees, while for computing $D$, we use the original $K$ without perturbation. By the post-processing property of DP (Fact B.5, Line 1114), the entire cross-attention mechanism remains DP. This is what we mean by $D$ containing no sensitive information. Our current design consequently guarantees an inversely proportional relationship between error and input context length $n$, aligning with the intuition that a larger number of tokens blends the information, enhancing privacy and utility. We have revised the paper to elaborate further on this. We add this discussion in our revised paper Line 229-231.

Q3: In Algorithm 3, the variables $P_{wx}$ and $s_{wx}$ are used without adding any noise. Can you explain why the resulting algorithm still preserves differential privacy?

This is because of the post-processing property of DP (Fact B.5, Line 1114), which states in an algorithm that if one step is DP, all the following steps are DP. Since we have the weighted distance term being DP, our whole process is DP.

We are so glad that you appreciate our revision of the proof. We will answer your follow-up questions. We also upload the third version of our revision for your reference.

Q1: Error bound of Theorem I.8

Thanks for your comment. We revised the proof in Line 2401-2422 for more details about how we control the error bounds.

Q2: Privacy parameters of Algorithm 1

Thanks for your valuable suggestion. We agree that the $d+1$ denominator should be applied. We add a Remark 3.2 in Line 269-273.

Q3: How to bound $K_j - \widetilde{K}_j$

Thank you for your peruse and insightful question! After careful checking, we found a better way to prove our utility bound, and we can get tighter and more elegant results than the second version revision, where we can directly get $|D\_{i,i} - \tilde{D}\_{i,i}|$ by our Theorem. We revised our proof to be more clear and improve our error bound. See Line 2546-2671.

Q4: Texts need to update

Thanks for your careful reading. We revised the paper’s text more. See Line 2326-2333.

We are so happy during the discussion with you. Your suggestion helps us a lot. We are so thankful that you asked those valuable questions. We are willing and glad to improve our draft if the reviewer has more suggestions.

We sincerely thank you for your careful check and valuable questions. Based on your comments, we can improve our analysis further.

Q1: Relative error

We thank the reviewer point this out. We agree with the reviewer that the relative error cannot be combined when a negative term exists, we did not notice that in our previous round rebuttal.

In the fourth version, to fix this issue, we improve our DPTree data structure to remove the relative error term related to $\alpha$. In the original version (before the rebuttal discussion), we introduced the idea of removing the $\alpha$ term in Section 5 Discussion, paragraph “How to remove the relative error parameter $\alpha$?” in Line 503-510. Based on these ideas, in Line 298-308 and 1337-1403, we update our DPTree, such that there is only an additive error in Line 1404-1474. Then, there is no relative error combination issue anymore. We refer the reviewer to the fourth version revision for more details.

Q2: Absolute value

We have fixed these typos in Line 1881-1889 and all other places.

We deeply appreciate that the reviewer helped us improve the paper's results and quality!

We thank the reviewer for their valuable suggestions. We provide our response below and hope it will address your concerns.

W1: The comparison with DP-SGD is limited.

We acknowledge the success of DP-SGD as the standard approach for applying DP to ML. However, it limits the scope of DP to the optimizer. In contrast, we propose a novel perspective on integrating DP directly into the attention mechanism, supported by strong theoretical analysis and guarantees. Given the resource-intensive nature of LGM training, our technique offers a practical alternative for models trained with standard SGD, which lack privacy guarantees. In such cases, DP-SGD would require retraining the models, which is computationally expensive, while our method does not. Exploring the practicality of our method and improving its efficiency will be our focus for future work. We added the DP-SGD discussion in the revised version Line 124-129.

W2.1: For linear queries, the matrix mechanism [1] generally outperforms the binary tree. I would be interested in hearing more discussion on the matrix mechanism.

Thanks for your insightful suggestion. For the matrix mechanism [1], a preliminary thought would be: Consider $A = \exp (Q K^\top)$ defined in Line 74. The $Q$ of size $m \times d$ can be viewed as the query matrix with $m$ linear queries in Definition 4 of [1] and $K$ is then the database. Then we could use the results from [1] to design an alternative algorithm to improve the current binary tree data structure DPTREE. We added the corresponding discussion in the revised version Line 484-488.

W2.2: Could you also provide an estimate of the width of the binary tree (i.e., the number of leaves) in your algorithm?

Our method requires $n$ number of leave nodes for one DPTREE data structure in Algorithm 2 Line 288.

Q1.1: It gives me a feeling that the mechanism is $(\epsilon,\delta+p_f)$-DP.

The mechanism is indeed $(\epsilon,\delta+\delta')$-DP as proved.

• The $\delta$ is DP failure probability.
• The $\delta’$ controls a hidden constant term as discussed in Remark 4.3 Line 439.
• The failure probability $p_f$ is to control the success probability of the adaptive query error control detailed in Section H, which boosts the constant probability to arbitrary high probability.

Though with a similar name, the failure probability parameter $p_f$ is not related to or participated in the DP failure probability $\delta$.

Q1.2: What's the value of $p_f$ in practice?

In practice, $p_f$ can be set to 0.001 to ensure a high success rate of 0.999.

[1] Li, C., Miklau, G., Hay, M., McGregor, A., & Rastogi, V. (2015). The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB journal, 24, 757-781.

We thank the reviewer for their valuable suggestions. We provide our response below and hope it will address your concerns.

W1 & W2: The appeal of cross attention is its superior empirical performance. The paper adapts the algorithm in several ways without evidence of how the algorithm's performance is changed.

Thank you for the thoughtful feedback. We theoretically show how our method’s error and time and memory cost change. We acknowledge that empirical validation can offer valuable insights into real-world performance; however, implementing our theoretical framework would require significant engineering effort to address system-level challenges, such as developing distributed algorithms and efficiently implementing polynomial kernel methods on GPUs. These challenges fall beyond the scope of our theoretical contribution.

Our primary contribution lies in providing the first mathematically rigorous privacy guarantees for cross-attention, with provable bounds on error, computational complexity, and memory requirements. We aimed to address the fundamental question: "Is it possible to make cross-attention differentially private with provable guarantees?" Our work answers this affirmatively, offering concrete mathematical bounds. We believe this is a significant contribution in itself, which is also supported by your comments that “the paper is already in the current state fairly dense.”

Q1: How do you guarantee that $K_{i,j} \in [0,R]$ and $V_{i,j} \in [−R,R]$? Is this done by clipping? If so, what effect does that have on the performance of the algorithm?

Yes, we could use clipping or quantization techniques to ensure the range of $K$ and $V$. Also, we can view $R$ as the maximum absolute value of the $K$ and $V$ entries. We assume in advance that the range is clipped for theoretical proof purposes.

Q2: What is the scope of the adjacency relation? Is it leaving out individual tokens? If so, in practice secrets may reach across many tokens and the DP guarantees would not provide meaningful privacy.

We thank the reviewer’s valuable comments. We agree that our neighbor dataset is defined based on word-level so that we protect individual token privacy. Our methods can still provide some sentence-level or many tokens privacy as we protect every word, e.g., every token in a sentence may be perturbed. How to build a data structure designed for sentence-level privacy protection is an interesting and challenging topic. One thought is to use the notion of group privacy in [1], which states that the neighbor dataset can differ in multiple tokens. We are willing to discuss this further per the reviewer’s request.

[1] Dwork, C., & Roth, A. (2014). The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science.

We thank the reviewer for their valuable suggestions. We provide our response below and hope it will address your concerns.

W1: Lack of Innovation in Core Techniques

As indicated, the polynomial kernel method and DP noise techniques have been proposed before. However, we would like to emphasize that our analysis offers a new view to combine the two in a clear way.

• We are the first work to reformulate the cross-attention computation to a weighted distance problem and then successfully apply those techniques. If we do not follow this approach, we cannot leverage the polynomial kernel method to approximate the $\mathsf{Softmax}$ function, which complicates the analysis of the DP guarantee. Additionally, we would lose the opportunity to utilize our simple yet efficient DPTREE data structures for solving the weighted distance problem. From our perspective, we believe our formulation and analysis are novel.
• We also handle the adaptive query case that is critical in practice for an intentional attacker. We thank the reviewer’s appreciation of this contribution in the third point of the Strength section.

W2: Limited Generalization and Practicality

We thank the reviewer for pointing out this concern. We admit that our analysis is tailored to cross-attention due to technical hardness. To the best of the author’s knowledge, we are the first work to provide differential privacy for cross-attention.

To extend to other settings, such as self-attention, we discussed this in Section 5, Line 479. In summary, the self-attention mechanism requires dynamic updates to tree nodes for each query, which are not supported in our current analysis. Our approach relies on separating the query and key-value matrices to pre-construct data structures. Applying this to self-attention necessitates dynamic updates, introducing challenges in DP analysis when supporting the update function in our DPTREE. However, with a carefully crafted and efficient design for handling dynamic updates, particularly in managing the varying length of the query matrix, these challenges can potentially be mitigated. With dynamic updates, it is possible to apply our current approach to self-attention. We leave this as future work.

W3: Computational and Initialization Costs

Our problem formulation abstracts scenarios where the key and value matrices are precomputed and stored in memory or disk, such as in RAG or system prompts (e.g., the latest example from Claude in this link). These pre-computed matrices are used to construct our data structure, so the inference time is not affected by the initialization time.

Q1: How well does it generalize to other attention mechanisms or model architectures, especially in high-dimensional or heterogeneous data scenarios?

We discuss the extension to self-attention in Section 5 in Line 479 and leave it as our future work. As for other model architectures, if the model can be reformulated into a weighted distance problem, our method can still apply. For the heterogeneous data scenarios, as our method did not depend on data distribution, we believe our methods can handle this situation.

Q2: What strategies does the DPTREE mechanism have in place to manage potential approximation errors that may accumulate during adaptive querying?

The error bound is guaranteed, as proved in Line 260, and is robust to adaptive queries, as demonstrated in Section H. While the error is controlled for individual queries, handling long chains of dependent queries falls outside our initial scope. Still, our current approach provides robustness to adaptive queries, which can provide the foundation for handling long chains of dependent queries. For example, our methods can ensure sentence-level or multi-token privacy by protecting each individual word—e.g., every token in a sentence can be perturbed. Designing a data structure specifically for sentence-level privacy protection presents an interesting and challenging problem. One potential approach is to leverage the concept of group privacy as outlined in [1], which allows neighboring datasets to differ by multiple tokens. We are open to further discussion and exploration of this topic based on the reviewer’s feedback.

Q3: Are there specific types of datasets or applications where DPTREE demonstrates significantly better or worse performance?

Our method does not assume data distribution and thus may hold for any dataset. For the application side, as the input context length increases, the error decreases. Our methods may perform better in long context datasets.

[1] Dwork, C., & Roth, A. (2014). The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science.