# Differentially Private Attention Computation

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 89 references that are in the map.
- First posted on arXiv 8 May 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [YOLOv3: An Incremental Improvement](https://mlsanity.com/paper/1804.02767/) (2018)
- [Vision-Language Models for Vision Tasks: A Survey](https://mlsanity.com/paper/2304.00685/) (2023)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [ChauffeurNet: Learning to Drive by Imitating the Best and Synthesizing the Worst](https://mlsanity.com/paper/1812.03079/) (2018)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Space of Transferable Adversarial Examples](https://mlsanity.com/paper/1704.03453/) (2017)
- [A Review of Robot Learning for Manipulation: Challenges, Representations, and Algorithms](https://mlsanity.com/paper/1907.03146/) (2019)
- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [VLM: Task-agnostic Video-Language Model Pre-training for Video Understanding](https://mlsanity.com/paper/2105.09996/) (2021)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [On Provable Copyright Protection for Generative Models](https://mlsanity.com/paper/2302.10870/) (2023)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019)
- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [An Over-parameterized Exponential Regression](https://mlsanity.com/paper/2303.16504/) (2023)
- [Faster Dynamic Matrix Inverse for Faster LPs](https://mlsanity.com/paper/2004.07470/) (2020)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [Privately Fine-Tuning Large Language Models with Differential Privacy](https://mlsanity.com/paper/2210.15042/) (2022)
- [Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models](https://mlsanity.com/paper/2304.02207/) (2023)

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

- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers](https://mlsanity.com/paper/2405.05219/) (2024)
- [InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding](https://mlsanity.com/paper/2306.04933/) (2023)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models](https://mlsanity.com/paper/2306.02295/) (2023)
- [How to Protect Copyright Data in Optimization of Large Language Models?](https://mlsanity.com/paper/2308.12247/) (2023)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time](https://mlsanity.com/paper/2408.13233/) (2024)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Zero-th Order Algorithm for Softmax Attention Optimization](https://mlsanity.com/paper/2307.08352/) (2023)
- [Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyond](https://mlsanity.com/paper/2405.03251/) (2024)
- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Provable Differentially Private Computation of the Cross-Attention Mechanism](https://mlsanity.com/paper/2407.14717/) (2024)
- [A Unified Scheme of ResNet and Softmax](https://mlsanity.com/paper/2309.13482/) (2023)
- [Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weights](https://mlsanity.com/paper/2310.12462/) (2023)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformer](https://mlsanity.com/paper/2311.13624/) (2023)
- [Subquadratic Algorithms and Hardness for Attention with Any Temperature](https://mlsanity.com/paper/2505.14840/) (2025)
- [Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis](https://mlsanity.com/paper/2306.03356/) (2023)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)
- [On Differentially Private String Distances](https://mlsanity.com/paper/2411.05750/) (2024)

## Abstract (arXiv)

Large language models (LLMs), especially those based on the Transformer architecture, have had a profound impact on various aspects of daily life, such as natural language processing, content generation, research methodologies, and more. Nevertheless, a crucial concern regarding the inference results of large language models is the issue of security and privacy. Given that large language models can generate results that may leak sensitive confidential or copyright information in many scenarios, it is crucial to compute the attention matrix with provable privacy guarantees, as attention is all you need. In this work, we propose a novel and efficient algorithm for approximating the attention matrix while providing differential privacy (DP) guarantees. To achieve this, we build on recent advancements in fast attention computation and differentially private matrix publishing.