# Provable Differentially Private Computation of the Cross-Attention Mechanism

arXiv: https://arxiv.org/abs/2407.14717 · HTML: https://mlsanity.com/paper/2407.14717/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in Robustness, privacy and adversarial aspects, one of 14 directions in Diffusion models.
- Builds on 62 of its 95 references that are in the map.
- First posted on arXiv 20 Jul 2024.

## Placed in

- Diffusion models / [Robustness, privacy and adversarial aspects](https://mlsanity.com/diffusion/robustness-privacy-and-adversarial-aspects/)

## Builds on (most cited first, 30 of 62)

- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Photorealistic Text-to-Image Diffusion Models with Deep Language Understanding](https://mlsanity.com/paper/2205.11487/) (2022)
- [Scalable Diffusion Models with Transformers](https://mlsanity.com/paper/2212.09748/) (2022)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Prompt-to-Prompt Image Editing with Cross Attention Control](https://mlsanity.com/paper/2208.01626/) (2022)
- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [CrossViT: Cross-Attention Multi-Scale Vision Transformer for Image Classification](https://mlsanity.com/paper/2103.14899/) (2021)
- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Multi-step Jailbreaking Privacy Attacks on ChatGPT](https://mlsanity.com/paper/2304.05197/) (2023)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Is A Picture Worth A Thousand Words? Delving Into Spatial Reasoning for Vision Language Models](https://mlsanity.com/paper/2406.14852/) (2024)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Dynamic Prompt Learning: Addressing Cross-Attention Leakage for Text-Based Image Editing](https://mlsanity.com/paper/2309.15664/) (2023)
- [JailbreakZoo: Survey, Landscapes, and Horizons in Jailbreaking Large Language and Vision-Language Models](https://mlsanity.com/paper/2407.01599/) (2024)
- [Differentially Private Language Models for Secure Data Sharing](https://mlsanity.com/paper/2210.13918/) (2022)
- [Mixed Differential Privacy in Computer Vision](https://mlsanity.com/paper/2203.11481/) (2022)
- [Privacy in Large Language Models: Attacks, Defenses and Future Directions](https://mlsanity.com/paper/2310.10383/) (2023)
- [On the Role of Attention in Prompt-tuning](https://mlsanity.com/paper/2306.03435/) (2023)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Why Larger Language Models Do In-context Learning Differently?](https://mlsanity.com/paper/2405.19592/) (2024)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [On Sparse Modern Hopfield Model](https://mlsanity.com/paper/2309.12673/) (2023)
- [Local Differential Privacy and Its Applications: A Comprehensive Survey](https://mlsanity.com/paper/2008.03686/) (2020)
- [On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis](https://mlsanity.com/paper/2402.04520/) (2024)
- [Privately Fine-Tuning Large Language Models with Differential Privacy](https://mlsanity.com/paper/2210.15042/) (2022)

## Built on by (most cited first, 14 of 14)

- [Circuit Complexity Bounds for RoPE-based Transformer Architecture](https://mlsanity.com/paper/2411.07602/) (2024)
- [Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time](https://mlsanity.com/paper/2408.13233/) (2024)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [HSR-Enhanced Sparse Attention Acceleration](https://mlsanity.com/paper/2410.10165/) (2024)
- [Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers](https://mlsanity.com/paper/2412.18040/) (2024)
- [Integrating Large Language Models for Automated Structural Analysis](https://mlsanity.com/paper/2504.09754/) (2025)
- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method](https://mlsanity.com/paper/2408.11267/) (2024)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)

## Abstract (arXiv)

Cross-attention has emerged as a cornerstone module in modern artificial intelligence, underpinning critical applications such as retrieval-augmented generation (RAG), system prompting, and guided stable diffusion. However, this is a rising concern about securing the privacy of cross-attention, as the underlying key and value matrices frequently encode sensitive data or private user information. In this work, we introduce a novel data structure designed to enforce differential privacy (DP) for cross-attention mechanisms, accompanied by provable theoretical guarantees. Specifically, letting n denote the input sequence length, d the feature dimension, R the maximum magnitude of query and key matrices, Rw the maximum magnitude of the value matrix, and r, s, εs the parameters for polynomial kernel methods, our proposed structure achieves widetildeO(ndr2) space and initialization complexity, with a query time of widetildeO(d r2) per token. Moreover, we demonstrate that our mechanism satisfies (ε, δ)-DP, incurring an additive error of widetildeO((1-εs)-1 n-1 ε-1 R2s Rw r2) and a relative error of 2εs/(1-εs) with respect to the ground truth. Crucially, our framework maintains robustness against adaptive queries, ensuring security even in adversarial settings. To the best of our knowledge, this constitutes the first approach providing provable differential privacy for cross-attention, establishing a foundation for future privacy-preserving algorithms in large generative models (LGMs).