DAGER: Exact Gradient Inversion for Large Language Models

Authors: ivo  petrov
dimitar i dimitrov
maximilian  baader
mark niklas müller
martin  vechev
st  kliment ohridski
eth  zurich
logicstar  ai
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:19:48

Abstract: Federated learning works by aggregating locally computed gradients from multiple clients, thus enabling collaborative training without sharing private client data. However, prior work has shown that the data can actually be recovered by the server using so-called gradient inversion attacks. While these attacks perform well when applied on images, they are limited in the text domain and only permit approximate reconstruction of small batches and short input sequences. In this work, we propose DAGER, the first algorithm to recover whole batches of input text exactly. DAGER leverages the low-rank structure of self-attention layer gradients and the discrete nature of token embeddings to efficiently check if a given token sequence is part of the client data. We use this check to exactly recover full batches in the honest-but-curious setting without any prior on the data for both encoder and decoder-based architectures using exhaustive heuristic search and a greedy approach, respectively. We provide an efficient GPU implementation of DAGER and show experimentally that it recovers full batches of size up to 128 on large language models (LLMs), beating prior attacks in speed (20x at same batch size), scalability (10x larger batches), and reconstruction quality (ROUGE-1/2 > 0.99).

Main paper: 
 introduction: 
 While large language models (LLMs) have demonstrated exceptional potential across a wide range of tasks, training them requires large amounts of data. However, this data is sensitive in many cases, leading to privacy concerns when sharing it with third parties for model training. Federated learning (FL) has emerged as a promising solution to addressing this issue by allowing multiple parties to collaboratively train a model by sharing only gradients computed on their private data with the server instead of the data itself. In particular, FL has been used to finetune LLMs while protecting private data [1, 2, 3] in privacy-critical domains, such as law [4] and medicine [5] .Gradient Inversion Attacks Unfortunately, recent work has shown that this private data can be recovered from the shared gradients using so-called gradient inversion attacks, raising concerns about the privacy guarantees of federated learning [6] . While most prior work on gradient inversion attacks has focused on image data [7, 8, 9] , first works have demonstrated that text can also be recovered [6, 10, 11] . However, as these approaches are optimization-based, the discrete nature of text data poses a major challenge by inducing much harder optimization problems and limiting them to approximate recovery of small batch sizes and short sequences. Therefore, applying existing attacks methods on modern LLMs would be computationally infeasible or yield subpar reconstructions. Token length for the j-th sequence n max j b j -the length of the longest sequence b B j=1 n j -the total number of nonpadding tokensf 0Embedding function (maps tokens to embeddings)z ijThe j-th entry of the i-th position token's embedding.Input to the l-th attention layer M The attention maskW {Q,K,V } lQuery/key/value projection weights for the l-th attention layer {Q, K, V } l The query/key/value embeddings in the l-th attention layerf l iThe i-th token embedding after the l-th transformer blockT * iThe set of client tokens at position iS * iThe set of batch sequences up to position i s 1 , s 2 , ..., s P A sample sequence of P tokensS * bestThe set of the best reconstructed sequences D *The set of distances to the span for each token/sequenceτ rank lThe singular value threshold for determining the rank of the l-th layer τ lThe distance threshold for filtering token candidates on the l-th layer While most prior honest-but-curious attacks leverage optimization methods to approximately recover the client inputs [6, 23, 7, 8, 24, 9, 10, 11] , several works have shown that exact reconstruction is possible for batch size B = 1 under various conditions for different architectures [22, 26, 27] . Crucially, Dimitrov et al. [28] recently showed that B > 1 exact reconstruction from gradients of fully-connected layers is also possible. Our work, builds upon this result to show that exact gradient leakage is also possible for transformer-based LLMs.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: The main claim of our abstract and introduction sections is that we demonstrate the first algorithm to recover whole batches of input text exactly in the honest-but-curious setting. To this end, we provide an overview of DAGER in Sec. 4 and delve into further mathematical details in Sec. 5. The discussion encompasses relevant mathematical proofs, as well as a thorough description of the underlying algorithms, featuring a greedy approach for decoder-based architectures and an exhaustive heuristic search for encoder-based ones.Additionally, we claim that the proposed attack outperforms existing attacks under the same threat model in quality, speed and scalability. We substantiate this claim through multiple experiments across batch sizes up to B = 128 for different datasets and models, as showcased in Sec. 6. Finally, in the same section we support our claim that DAGER can be applied across a variety of settings through empirical evaluation, and through rigorous analysis in App. B.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
limitations: 
 Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We detail our limitations in a dedicated section (Sec. 7), discussing both theoretical and computational aspects of DAGER, for the latter of which we present a formal proof of complexity in App. B.5. We further describe any underlying assumptions in the "Related Work" and "Background" sections (Sec. 2 and Sec. 3 respectively).Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
background and notation: 
 In this section, we introduce the background and notation required to understand our work. To this end, we first recall the basic operation of the transformer architecture in the context of LLMs, and then describe the result, first introduced in Dimitrov et al. [28] for linear layers, in the context of a self-attention layer showing that the gradients of its linear transformations have a low-rank structure.The notations used throughout this paper are summarized in Table 1 for clarity and ease of reference.In this paper, we consider LLMs based on both encoder and decoder transformer architectures trained using the FedSGD [36] protocol and a loss function L. While we mainly focus on the harder-to-attack binary-classification loss typically used for sentiment analysis, we demonstrate that DAGER is equally applicable to the next-token prediction loss in Sec. 6 , which contains more gradient information, as suggested by prior work Zhu et al. [6] . We denote the transformer's context length with P , its hidden dimension with d, the number of transformer blocks with L, the vocabulary of the tokenizer with V, and its size with V . We present our approach for single-headed self-attention but it can be directly extended to multi-head self-attention, and we experimentally apply DAGER in this context.Transformer Inputs We consider inputs batches consisting of B sequences of tokens, where n j is the length of the j th batch element. Sequences with length < n = max j (n j ) are padded. We denote the total number of non-padding tokens in a batch with b = B j=1 n j .Token Embeddings The discrete input tokens are usually embedded via a function f 0 : [V ]×[P ] → R d mapping a token's vocabulary index v and its position i in the sequence to an embedding vector z ij = f 0 (v, i). These embeddings z ij are then stacked row-wise to form the input Z 1 ∈ R b×d to the first self-attention layer. Note that f 0 is known to the server, as it is part of the model. Further, while f 0 differs between models, typically it maps token indices to embedding vectors before optionally adding a positional encoding and applying a LayerNorm. Crucially, f 0 is applied per-token.Self-Attention The stacked embeddings Z 1 are then passed through a series of self-attention layers. We denote the input to the l th self-attention layer as Z l ∈ R b×d , for 1 ≤ l ≤ L. A self-attention layer is a combination of three linear layers: The query Q l = Z l W Q l , key K l = Z l W K l , and value V l = Z l W V l layer, which are then combined to compute the self-attention output:attention(Q l , K l , V l ) = softmax M ⊙ Q l K T l √ d V l ,where M is the binary self-attention mask, ⊙ is the element-wise product, and the softmax is applied row-wise. M is chosen to ensure that padding tokens do not affect the layer's output. Further, for decoders, M ensures that only preceeding tokens are attended. For notational convenience, we denote as f l i : V P → R d the function that maps any sequence of input tokens to the i th input embedding at the 1 ≤ l ≤ L self-attention layer. Note that f l i is part of the model and, thus, known to the attacker.For a linear layer Y = XW + (b| . . . |b) T with a weight matrix W ∈ R n×m , a bias b ∈ R m , and batched inputs X ∈ R b×n and outputs Y ∈ R b×m , Dimitrov et al. [28] show that: Theorem 3.1 (Adapted from Dimitrov et al. [28] ). The network's gradient w.r.t. the weights W can be represented as the matrix product:EQUATIONFurther, when the batch size b ≤ n, m, the rank of ∂L ∂W is at most b.The rank limit follows directly from the dimensionalities of ∂L ∂Y ∈ R b×m and X ∈ R b×n in Eq. 1.In this work, we apply In this section, we provide a high-level overview of our method DAGER, illustrated in Fig. 1 . DAGER is an attack that recovers the client input sequences from the shared gradients of a transformer-based LLM. DAGER works for both encoder and decoder-based LLMs, however, for simplicity here we focus on decoder-only LLMs. While, in theory, one could enumerate all possible batches of input sequences, and check whether they produce the desired gradients, this is infeasible in practice as it requires computing V P ×B different gradients. We reduce the search space by leveraging the rank-deficiency of ∂L ∂W Q l , discussed in Sec. 3.2, combined with the finite number of possible inputs to each self-attention corresponding to one of the V P ×B gradients above. For the rest of the section, we assume rank-deficiency of∂L ∂W Q l , that is b < d.This assumption is in practice satisfied for reasonable input lengths and batch sizes. ∂L ∂W Q l = Z T l ∂L ∂Q l .It is unlikely that any incorrect embedding vector, part of one of theV P ×B incorrect inputs Z l , is part of colspan( ∂L ∂W Q l ) ⊂ R d ,as the hypervolume of this subspace is 0.We can efficiently filter out all incorrect client embeddings at any layer l without computing their gradient, simply by checking if they are in colspan( ∂L ∂W Q l ). However, applying this procedure naively still requires us to check all V P ×B different client batches. Instead, we leverage this filtering in a two-stage recovery algorithm that first recovers the client tokens T * i at position i using the rank deficiency of ∂L ∂W Q 1 (Token Recovery in Fig. 1 ), and then recovers the client batch of sequences S * based on T * i and the rank deficiency of ∂L ∂W Q(Sequence Recovery in Fig. 1 ).Token Recovery Our token recovery method relies on the observation that f 0 is computed pertoken. Therefore, the input embeddings in Z 1 are always part of the set{f 0 (v, i)|v ∈ [V ], i ∈ [P ]}.We apply our span check above to this set for the first layer gradients ∂L ∂W Q 1 to filter the incorrect embeddings and their corresponding client tokens v at position i, thus, constructing the set of correct client tokens T * i at position i.Sequence Recovery In our sequence recovery, we leverage the fact that f 1 i is computed persequence and that the decoder mask M ensures that the second layer input embeddings at position i do not depend on tokens with position > i, i.e., f 1 i (s 1 , . . . , s P ) = f 1 i (s 1 , . . . , s i ), for any sequence of tokens s 1 , . . . , s P . Crucially, for a correct client partial sequence s 1 , . . . , s i-1 of length i -1 this allows us to find the correct next token in T * i by simply extending it with all possible token s i ∈ T * i and then checking which of the resulting embedding vectorsf 1 i (s 1 , . . . , s i-1 , s i ) is correct, i.e, is in colspan( ∂L ∂W Q 2). We apply this procedure iteratively starting with the single token sequences S * 1 = T * 1 , extending them one token at a time to produce the partial sequence reconstructions S * i , until the sequences cannot be extended anymore and return the result.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: We provide rigorous proofs for all theorems directly following the statement, or have been deferred to App. B. All assumptions have been explicitly stated, discussed and further elaborated upon in App. B.2.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experimental result reproducibility: 
 Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We provide code and additional resources that are required to reproduce our results shown in Sec. 6 in our supplementary material. Furthermore, we describe in sufficient detail all specifics of the algorithm that are needed for reproduction in the technical and experimental sections (Sec. 5, Sec. 6 respectively), with additional information found in App. C. 
dager: exact sequence recovery for transformers: 
 In this section, we present the technical details of DAGER. Specifically, we first theoretically derive of our filtering procedure based on the rank-deficiency of ∂L ∂W Q l in Sec. 5.1. We then describe how we apply it on the gradients of the first and second self-attention layers to respectively recover the client tokens (Sec. 5.2) and sequences (Sec. 5.3).Below, we discuss the technical details of our filtering procedure, outlined in Sec. 4, and prove its correctness. We first show that, under mild assumptions, the embedding vectors forming Z l are linear combinations of the columns of ∂L ∂W Q l , restating this in terms of rowspan(Z l ) and colspan( ∂L∂W Q l ): Theorem 5.1. If b < d and the matrix ∂L ∂Q l is of full rank (rank b), then rowspan(Z l ) = colspan( ∂L ∂W Q l ).Note that the assumption that ∂L ∂Q l is full-rank holds in practice, as shown empirically in Dimitrov et al. [28] , and that further b < d is almost always satisfied, i.e., that the total number of tokens in the input is smaller than the internal dimensionality of the model, for practical LLMs. We discuss the assumptions in further detail in App. B.2. The latter then directly implies the rank-deficiency of Combining Theorems 5.1 and 5.2, we arrive at our main result stating that, if b < d, an embedding vector z that is part of the client self-attention inputs Z l belongs to colspan( ∂L ∂W Q l ), while random embedding vectors that are not part of Z l almost surely do not.Span Check Implementation While the above result holds under real, i.e., infinite precision, arithmetic, for our method to work in practice, we require an implementation that is both fast and robust to numerical errors caused by floating-point arithmetic. We, therefore, introduce the metric d, the distance between a candidate embedding vector z and its projection on the colspan( ∂L∂W Q l ): d(z, l) = ∥z -proj(z, colspan( ∂L ∂W Q l ))∥ 2 .(2)Intuitively, the closer d(z, l) is to 0, the more likely z is part of the span. To allow for efficient computation of the projection in Eq. 2, we first pre-compute an orthonormal basis for ∂L ∂W Q l using an SVD and truncating the eigenvalues below a chosen threshold τ rank l . We can then trivially compute this projection, as the sum of projections onto each basis vector. Finally, we say that a vector z is in colspan( ∂L ∂W Q l ), if the distance d(z, l) < τ l is below a chosen per-layer threshold τ l .Algorithm 1 Recovering Individual Tokens1: function GETTOK( ∂L ∂W Q 1 , V, P, f 0 , τ 1 ) 2:n ← 0 3:EQUATIONif d < τ 1 thenEQUATIONT * i ← T * i + {v} 9:D * i ← D * i + { d} 10: return n, {T * i } n i=0 , {D * i } n i=0We now describe how DAGER leverages the above filtering procedure to recover the input tokens exactly. To this end, we consider the set of all tokens in the model's vocabulary v ∈ [V ] at every possible position i ∈ [P ] and compute their input embeddings at the first layer via the per-token embedding function f 0 . We then filter out token-position tuples (v, i) whose embedding vectors f 0 (v, i) do not lie in colspan( ∂L ∂W Q) to obtain the set input tokens (across batch elements) at position i:EQUATIONWe formalize this process in Algorithm 1, where we simply enumerate all token position tuples (v, i).Additionally, we compute the length of the longest input sentence n as the largest position i of any recovered tuple (v, i) (Line 7). If f 0 is position-independent, e.g. when rotary instead of absolute positional embeddings are used, we recover the set of all input tokens T * = i T * i for every position. Our algorithm handles this at the sequence recovery stage at the price of slightly higher computational costs (see Theorem B.4). While conceptionally simple, this approach is exceptionally effective and robust to the distance threshold τ 1,2 , as we demonstrate in Fig. 2 for the GPT-2 model [12] (d = 768) and a batch of B = 32 sequences consisting of b = 391 tokens. Despite the total number of tokens b exceeding half the model dimensionality d, even our single layer (L1) filtering approach narrows the set of possible starting tokens, which are independent of the rest of the input, down to less than 300 from GPT-2's vocabulary of V ≈ 50K across a wide range of thresholds. Adding a second filtering stage using second-layer filtering, described next, allows DAGER to recover the exact 32 starting tokens. This is used to exactly narrow down the first token for each sequence, allowing us to inductively reconstruct the whole sentence for decoder-only models.Given the set of input tokens, recovered above, we now describe how to recover input sequences by applying our filtering procedure to the inputs of the second self-attention layer Z 2 . We first define the set S = T * 1 × • • • × T * P of all sequences formed using the recovered token sets T * i . As the second layer input embeddings z 2 = f 1 (s) are computed independently for each sequence s, one can naively enumerate all s ∈ S, compute their second layer embedding vectors f 1 (s) and apply the span check for every position i to obtain the true set of client sequences:S * = {s ∈ S | d(f 1 i (s), 2) < τ 2 , ∀i ∈ [P ]}.Algorithm 2 DAGER for Decoders1: function ATTDEC(B, ∂L ∂W Q 1 , ∂L ∂W Q 2 , V, P, f 0/1 , τ 1/2 ) 2: n, T * , D * ←GETTOK( ∂L ∂W Q 1 , V, P, f 0 , τ 1 )3:S * 0 ← {{}} B j=1 4:for i ← 1, . . . , n do 5:TokenFound ← False 6:S i ← S * i-1 × T * i 7:S * i ← {} Recovering Decoder Sequences Due to the causal attention mask M in decoder architectures, the i th input of the second-self attention layer f 1 i (s) depends only on the first i tokens of the input sequence s. We can thus apply a span check on the results of f 1 i to check arbitrary sequence prefixes of length i. We leverage this insight in Algorithm 2 to iteratively recover the sets S * i (Line 10) of input sequence prefixesS * i = {s ∈ S * i-1 × T * i | d(f 1 i (s), 2) < τ 2 },starting from the set of empty sequences S 0 and extending them one token at a time (Line 6) until none of our sequences can be extended any further (Line 12). Recovering Encoder Sequences For encoders, all secondlayer embeddings f 1 i (s) depend on all input tokens. We thus cannot use the greedy reconstruction discussed above but have to enumerate all sequences in S. To make this search tractable, we leverage the following heuristics. We can determine the positions i of end-of-sequence (EOS) tokens in the input to determine the input sequence lengths n j . This allows us to recover input sequences by increasing length and eliminate the tokens constituting the recovered sequences from the token sets T * i . Additionally, we truncate the proposal token sets T * i to the batch size B token closest to colspan( ∂L ∂W Q∆ b =10 ∆ b =20 ∆ b =40 ∆ b =80 d GPT-2). Finally, we always consider at most 10M sequences from S before returning the ones closest to colspan( ∂L ∂W Q).We demonstrate the effectiveness of our heuristics in Fig. 4 for the base BERT model and different batch sizes B and note that for B = 1 we can still recover inputs perfectly, as |T * i | = 1. We provide more details on DAGER for encoder-architectures in App. B.6.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We provide a Python implementation, alongside detailed instructions for both setup and execution. Most of the data and architectures we used belong to the public domain.The only exception is that one must request access to the private HuggingFace repository for all LLaMa models. Instructions on how to approach this have also been included. We discuss the licensing and availability for all assets in App. D. Guidelines:• The answer NA means that paper does not include experiments requiring code. Justification: We discuss the implications of our work on user privacy in federated learning in our Broader Impact statement in App. A. To prevent malicious uses of our code we plan to release it under a license that prohibits any non-research related uses. We note that our work does not introduce new datasets or architectures and that we rely on only publicly available datasets, whose licenses we appropriately discuss in App. D. 
experimental evaluation: 
 We now describe our extensive experimental evaluation of DAGER. Our results demonstrate significant performance improvements compared to prior methods, on a variety of settings. We also present ablation studies for isolating the effects of each DAGER component.We evaluate DAGER on both encoder-and decoder-based models including BERT [14] , GPT-2 [12] , and variations of LLaMa [13, 37] . We consider three sentiment analysis datasets -CoLA [15] , SST-2 [16] , and Rotten Tomatoes (RT) [17] , featuring sequences of varying lengths between typically 4 and 27 words. Additionally, we consider the ECHR [18] dataset, which contains sentences exceeding 1000 words to demonstrate the scalability of our approach in sequence length. We provide a more detailed description of our architectures and datasets in App. C. Following previous work, we report the mean and error of the ROUGE-1/2 [38] scores, i.e., the overlap rate of unigrams and bigrams, respectively, over 100 batches, excluding padding tokens. We report the error as the 95% confidence interval given by twice the standard error. Wherever we cannot assume normality of the mean's distribution, we estimate the interval by generating 10 000 random samples by bootstrapping. Additional details regarding computational requirements and hyperparameters can be found in App. C.Comparison against baselines First, we compared our performance against the state-of-the-art algorithms TAG [10] and LAMP [11] with batch sizes ranging between B = 1 and B = 8. We run the two attacks for 2500 iterations per experiment, making use of the hyperparameters described in their respective studies. As Balunović et al. [11] provide two variations of the LAMP algorithm based on different objective functions -LAMP L2 + L1 and LAMP Cos , we only report results from the variation with the higher ROUGE-1 score. In Table 2 , we show results on GPT-2 BASE and BERT BASE , assessing the performance on decoder-based and encoder-based models respectively.The results indicate that for decoder-based models, such as GPT2, DAGER achieves near-perfect reconstructions across all datasets and batch sizes, significantly outperforming the baseline algorithms in every setting. Importantly, as further elaborated in App. C.1, DAGER achieves that while also being significantly more efficient -100 batches of size 8 on RT took 3.5 hours vs TAG and LAMP which required ≈ 10 and 50 hours, respectively. Additionally, we confirm the claims made by Balunović et al. [11] that LAMP outperforms TAG in the majority of settings. Examples of reconstructed sentences can be seen in Table 9 in App. C.3. We note that while we observe non-perfect ROUGE-2 scores on the SST-2 dataset, this is entirely due to an artifact of our metric library that assigns ROUGE-2 score of 0 to the SST-2's single-word sequences. We kept this behaviour to avoid having to rerun the baseline experiments, that also relied on this. Further, Table 2 shows a significant improvement over prior work on encoder-based models like BERT, with near-perfect reconstruction for B = 1, 2, and an average of 43% more tokens recovered for larger batch sizes. A significant advantage of DAGER over the baselines is its ability to more accurately recover the sentence structure, as evidenced by the much higher ROUGE-2 scores.Main experiments While prior attacks' performances become very poor for batch sizes as little as 8, we now demonstrate that DAGER is only limited by the embedding dimension of the model. To this end, in Table 3 we compare two decoder-only models, GPT-2 BASE with d = 768, and LLaMa-2 7B with d = 4096 on B as large as 128.The results are consistent with our claims that DAGER produces almost perfect reconstructions in all cases when the total number of client tokens is not extremely close to the embedding dimension d. Further, while on LLaMa-2 DAGER achieves near-perfect reconstructions even up to a batch size of 128, for GPT-2 DAGER shows partial or complete failure for B = 64, 128. This suggests that despite the significant computational costs of > 2 hours per batch for B = 128 on LLaMa-2, larger models have the potential to leak significantly more information. This is especially concerning given the current trend of ever-increasing model sizes. Finally, we observe the effect of attempting a best-effort reconstruction by establishing a rank threshold, as described in Sec. 5.3, when the gradients are of full rank. This allows DAGER to achieve a ROUGE-1 score of 30.3 (instead of 0) for GPT-2 on CoLA B = 128. A thorough ablation study on the advantage of this heuristic can be found in App. C.2.Table 2 : Comparison of sequence reconstruction from gradients between DAGER and the baseline algorithms TAG and LAMP on various batch sizes and datasets. R-1 and R-2 denote the ROUGE-1 and ROUGE-2 scores respectively. Table 3 : Main experiments on the GPT-2 BASE and LLaMa-2 (7B) models with higher batch sizes on various datasets. R-1 and R-2 denote the ROUGE-1 and ROUGE-2 scores respectively. 100.0 ± 0.0 100.0 ± 0.0 97.9 ± 0.5 97.8 ± 0.5 99.7 11 . These results reaffirm that DAGER is applicable to common fine-tuning methods.B = 1 B = 2 B = 4 B = 8 R-1 R-2 R-1 R-2 R-1 R-2 R-1 R-2 GPT-2 CoLA TAG 7.0 ± 2.5 0.54 ± 0.54 8.0 ± 2.0 1.4 ± 1.3 7.8 ± 1.2 0.8 ± 0.5 5.3 ± 0.7 0.4 ± 0.2 LAMP 73.3 ± 4.EQUATIONEQUATIONPrior work [11, 10] suggests that the size of a model, as well as, the degree of pre-training significantly affects the amount of leaked client information. To this end, in Table 5 we evaluate DAGER on the larger (GPT-2 LARGE ) and Table 5 : Experiments on GPT-2 variations in different settings on the Rotten Tomatoes dataset. R-1 and R-2 denote the ROUGE-1 and ROUGE-2 scores respectively.B = 16 B = 32 B = 64 B = 128 R-1 R-2 R-1 R-2 R-1 R-2 R-1 R-2GPT-2 BASE 100.0 ± 0.0 99.9 pre-trained for 2 epochs (GPT-2 FineTuned ) variants of GPT-2 on the RT dataset for batch sizes up to 128. We observe very little difference in performance. In fact, the GPT-2 LARGE 's larger embedding dimension allows us to approximately reconstruct more tokens at larger batch sizes. We further note that a larger vocabulary does not negatively impact DAGER, as can be seen from the applications on LLaMa3.1-8B and LLaMa3.1-70B (see Table 11 ), which feature a vocabulary size of 128,256 tokens.Reconstruction under Next-Token Prediction Additionally, we evaluate our model on the nexttoken prediction task to demonstrate DAGER's efficacy under different contexts. We again achieve near-perfect results with ROUGE-1/2 scores of > 99. DAGER does not reach perfect scores because the last token in each client sequence only acts as a target and it is, thus, masked out from the input.Reconstruction of Long Sequences Finally, to demonstrate our robustness to long sequences, we conducted a single experiment with B = 1 on the ECHR dataset truncated to 512 tokens. We obtain a perfect score of 100.0 ± 0.0 for ROUGE-1 and ROUGE-2 on GPT-2 BASE , emphasizing the general applicability of DAGER. In contrast, in the same setting LAMP achieves a ROUGE-1 of 10.1 ± 2.3. 
limitations: 
 As discussed in Sec. 5 and demonstrated in Sec. 6, the performance of DAGER on decoder-based models is only constrained by the embedding dimension d. While an exact reconstruction for a number of tokens b > d is unachievable, we showed that the attack's effectiveness decreases only gradually with b. Given our robust performance in an undefended setting, an interesting avenue for future work is to improve DAGER against different defense mechanisms, including but not limited to using the Differential Privacy SGD optimization process (DPSGD) [40] .On the other hand, applying DAGER on encoder-based architectures for larger batches (B >> 8) becomes challenging due to the high-order polynomial growth of the search space volume with respect to the batch size. These computational constraints make comprehensive exploration of the search space nearly impossible, thereby reducing the likelihood of achieving a feasible reconstruction. This issue extends to longer sequences, where the size of the search space expands exponentially with the maximum sequence length. To mitigate these effects, we propose that future research could focus on exploring further heuristics to efficiently reduce the search space. 
conclusion: 
 We introduced DAGER, the first gradient inversion attack for transformers able to recover large batches of input text exactly. By exploiting the rank-deficiency of self-attention layer gradients and discreteness of the input space, we devised a greedy algorithm and a heuristic search approach for decoder-based and encoder-based architectures, respectively. Our results show that DAGER achieves exact reconstruction for batch sizes up to 128 and sequences up to 512 tokens. We further demonstrate DAGER's effectiveness across model sizes, architectures, degrees of pre-training, and federated learning algorithms, establishing the widespread applicability of our attack.Our work demonstrates that recent decoder-based LLMs are particularly vulnerable to data leakage, allowing adversaries to recover very large batches and sequences in the absence of a robust defense mechanism. This underlying vulnerability highlights the need for increased awareness and development of effective countermeasures in privacy-critical applications. We hope this paper can facilitate further research into creating reliable frameworks for effective and private collaborative learning.Importantly, DAGER does not assume any prior knowledge of the labels or the lengths of each sequence in the batch nor access to the gradients of the embedding layers which have been shown to leak significant information [26] . Further, we require no language priors and operate under the honest-but-curious setting which does not allow malicious changes to model weights. Finally, sub-differentiability is sufficient for applying DAGER.In practice, DAGER requires much fewer assumptions than existing works in the honest-but-curious setting while being successful in a variety of common LLM tasks, e.g., next-token prediction and sentence classification. While these tasks use the cross-entropy loss, DAGER can be applied to any loss function that non-trivially depends on every input token. This ensures the full-rankness of ∂L ∂W Q l .To confirm its generality, we apply DAGER with a Frobenius norm-based loss and ReLU activation functions. We use a custom loss function L(s 1 , s 2 , . . . , s P ) = ∥f L (s 1 , s 2 , . . . , s P )∥ F , where ∥.∥ F is the Frobenius norm, which is equivalent to an MSE loss with 0 as a target vector. We report the results of applying DAGER with these modifications on Rotten Tomatoes using GPT-2 with B = 16 in Table 11 , achieving ROUGE-1 and ROUGE-2 scores of >99% in both cases. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We discuss this paper's implications in the Broader Impact section (App. A), where we describe the necessity of our work and associated privacy considerations.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [Yes]Justification: Upon publicly releasing the code, we plan on attaching a license that prohibits any non-academic use.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: All datasets and models used are either publicly available, or have been properly attributed. We have also appropriately credited the authors of the baselines' code, which is publicly available. We discuss the licenses and terms and conditions explicitly in App. D.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes]Justification: We provide a Python implementation, alongside detailed instructions for both setup and execution. Our work does not introduce new architectures or datasets. We discuss licenses for all external assets in App. D.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We establish that DAGER can be effectively used to attack clients employing FedAvg updates under mild assumptions. First, we show that it is possible to theoretically apply Theorem 5.1 to the protocol directly on the first layer, and under reasonably low model updates for further layers. We then demonstrate experimentally that DAGER can be successfully applied across a wide range of parameters, namely the number of epochs E, learning rate η and mini-batch size b mini .Spanchecks for FedAvg updates Let X e l = f l (s e 1 , s e 2 , . . . , s e bmini ) denote the input embedding vectors to the relevant l-th layer query projection matrix for a mini-batch of size b mini . Obtaining X e l in the forward pass is equivalent to sampling the corresponding rows in the full-batch representation X l = f l (s e 1 , s e 2 , . . . , s B ), as each sequence in a batch is independent from all the rest. Therefore, we can rewrite each local gradient update ∂L∂W Q l = X e l T ∂L ∂Q e las X l T ∂L ∂Q l , where the i-th column of ∂L ∂Q l is the zero vector 0 if s i is not present in the mini-batch. Therefore, we are able to simply disregard the mini-batch sampling and focus only on the total number of iterations E, assuming that every sequence in the original batch is sampled at least once.Let the input embedding vectors to the l-th layer at timestep t < E be X t l . The final weight W E l after E steps can be written as:EQUATIONUnder the assumption that the changes in model weights are relatively small, we can approximate X t l = X 0 l . This is always the case for l = 0, as the embeddings before the first layer are independent of the model weights. This allows us to rewrite W E as:EQUATIONAs the server has knowledge of the starting weight W 0 l and the final weight W E l , it is able to compute the sum of all gradient steps, i.e we will be able to apply Theorem 5.1 to X 0 l T (ηE t=0 ∂L ∂Q t l). We still require E t=0 ∂L ∂Q t l to be full-rank, which is satisfied under standard DAGER assumptions.Further experimental details We further empircially demonstrate that DAGER can effectively utilise the assumption of consistent feature embeddings across epochs under a reasonable learning rate and number of iterations. As shown in Table 4 , we observe near-exact reconstruction rates for most configurations, with metrics only slightly declining as the number of epochs increases. The key factor that influences the success of DAGER is observed to be the learning rate η, as the aforementioned assumption might be invalidated at large η. However, learning rates exceeding η ≥ 10 -3 are typically too high for the model to converge, particularly in multi-client settings. Therefore, we can conclude that DAGER is highly effective in the FedAvg context.In this section, we discuss how DAGER can be extended to work on LoRA weight decomposition. Under LoRA, the linear layer weight updates for a weight W ∈ R d×d are performed on a low-rank representation: W = W 0 + AB, where A ∈ R d×r , B ∈ R r×d . As we obtain the gradient weights for both A and B, we can apply Theorem 5.1 to A with Z A = XA, namely because ∂L ∂A = X T ∂L ∂Z A . Assuming that ∂L ∂XA is full-rank and that b < r, our work is directly applicable. This can replace the spanchecks to be performed on A instead of W for each layer, after which DAGER can be applied directly. In practice, LoRA finetuning typically initializes W = W 0 and B to only contain zeroes which reduce the rank of ∂L ∂A for the first few optimization steps. We therefore train the LLaMa-3.1 8B model on the Rotten Tomatoes dataset using a batch size of 4 with r = 256 (following [39] ) for 3 epochs before applying DAGER. We report results in Table 11 and observe an excellent R1 and R2 of about 95%.A key point of DAGER is the algorithm's exceptional computational efficiency on decoder-based models. In order to quantify the dependency of runtime on relevant variables, we describe the asymptotic complexity for both decoder-and encoder-based models. Below we list and prove several lemmas that assist us in the complete proof of our assertion for the complexity of DAGER. When not specified, a batch size of B = 1 is implied for any inputs. Lemma B.1. The product of two matrices M 1 ∈ R n×m and M 2 ∈ R m×p can be naively computed in O(nmp).Proof. We write down the product:(M 1 M 2 ) ij = k M 1 ik M 2 kjTo produce the entire matrix we explore all integers i = 1 . . . n, j = 1 . . . p and k = 1 . . . m, and in particular any combination of the 3. This implies that we make nmp iterations, from which a time complexity of O(nmp) follows.Lemma B.2. For any matrix M ∈ R d×n and vector v ∈ R d , we can compute the projection of v on the subspace spanned by the columns of M in O(d 2 n) time.Proof. Projecting onto the column space of a matrix can be done by projecting the vector onto individual columns and then summing all projected components. We compute this using Einstein notation, while denoting the resulting vector as p ∈ R d . Then, we obtain: Proof. We follow the notation defined in Sec. 3.1. The embedding representation of the sequence is denoted as z ∈ R b×d . We then obtain the query, key and value vectors Q, K, V by multiplying with the weight matricesp k = i,j M ki M ji v jW Q 1 , W K 1 , W V 1 ∈ R d×d .According to Lemma B.1, we can accomplish this in a time of O(bd 2 ).Computing the attention scores is dominated by computing QK T , which by applying Lemma B.1, can be done in O(b 2 d).A = softmax(M ⊙ QK T √ d ) ∈ R b×b and V ∈ R b×d in time O(b 2 d).We note that computing the row-wise softmax operations can be amortized and take a total of O(b 2 ) time, which is dominated by O(b 2 d). The total computation up until this point can, therefore, be done in O(bd 2 + b 2 d).To produce the output of the transformer block, we pass the self-attention through an MLP layer, which can be represented by a set of simple matrix multiplications (of the same complexity). Therefore, applying Lemma B.1 once again, this step requires time O(bd MLP d).We can sum up all components to obtain a total complexity of O(bd Having explored in-depth each smaller component of the algorithm, we can now determine the complexity of DAGER. We explore 3 instances of our algorithm, namely separating decoder-and encoder-based models, while also differentiating between absolute positional encodings and RoPE. We summarize our findings in a single theorem: As can be inferred by Theorem 5.1, the complexity of the spancheck is O(P Bd 2 ). We perform this for every token in the vocabulary for an additional factor of V , making the total complexity O(P BV d 2 ). We note that for models which employ positional embeddings before the first transformer block, we repeat this step P times, while we only have to do it once for those that don't. This respectively results in time complexities of O(P 2 BV d Sequence reconstruction Having recovered the individual tokens, we detail the resulting time complexity of reconstructing the entire sequences. We describe each step for decoder-based models, before proceeding to encoder-based ones.• For decoder-based models we begin by describing the number of tokens we obtain per position. If the model applies positional embedding before the first transformer layer, we assume that for each position i we recover a set of tokens T * i , such that |T * i | = O(T ) for some variable T that depends on our input parameters and setup. Similarly, for models that do not have positional embeddings before the first transformer layer, we only recover a single set of tokens T * of size |T * | = O(P T ).• We now show the complexity required for performing the forward pass and span check for a single sequence. For a sequence length n, according to Lemma B.3 the forward pass takes time O(nd 2 + n 2 d), and the span check per token is of complexity O(P Bd 2 ) (as per Lemma B.2). This implies a time complexity of O(nP Bd 2 ) per sequence for the span check, leading us to an overall complexity of O(nP Bd 2 + nd 2 + n 2 d).• Finally, we apply our observations to the full reconstruction. We further assume that at each step of the greedy reconstruction, we maintain O(B) possible sequences, which is usually the case when performing a greedy reconstruction. By repeating the above propagation for every combination per sequence length yields a total runtime of O(T × B × (nd2 + n 2 d + nP Bd 2 )) = O(P T B 2 d 2 n) and O(P T × B × (nd 2 + n 2 d + nP Bd 2 )) = O(P 2 T B 2 d 2 n)in the cases described in statement 1a) and 1b) respectively.• Summing over all lengths yields a time of O(P n=1 P B 3 d 2 n) = O(P 3 T B 2 d 2 )for the former. Analogically, for the latter we obtain a complexity of O(P 4 T B 2 d 2 ).• In practice, we observe that T = αB for some factor α between 1 and 10, hence we can assume that T = O(B). This is a practically correct assumption for a reasonably defined threshold τ 1 . This makes the final time complexity for recovering sequencesO(P 3 T B 2 d 2 ) = O(P 3 B 3 d 2 ) for case 1a) and O(P 4 T B 2 d 2 ) = O(P 4 B 3 d 2 ) for 1b).On the other hand, in the case of encoder-based models, we need to exhaust all possible token combinations over all positions.• We again assume that for each position i we recover a set of tokens T * i , such that |T * i | = O(T ).• Because we have to explore all possible combinations, that results in a total number ofP i=1 |T * i | = P i=1 O(T ) = O(T P ) sequences.• We now show the cost of the span check on a single sequence. We leverage our finding that one such span check takes time O(P Bd 2 ) (we again substitute that the rank r = O(P B) and apply Lemma B.2), meaning all span checks take time O(P 2 Bd 2 ) per sequence.• Additionally, the forward pass takes O(P d 2 + P 2 d) time.• Finally, because we reconstruct each sequence separately, we repeat the reconstruction algorithm O(B) times. This leads to the complexity for this step -O(T P B(P2 Bd 2 + P d 2 + P 2 d)) = O(T P B 2 P 2 d 2 ).• As above, we assumeT = O(B), leading us to a final complexity of O(B P B 2 P 2 d 2 ) = O(B P P 2 d 2 ).Combining our conclusions for steps 1 and 2 yields the stated complexities for each setting.The key points to highlight is that DAGER is polynomial across both sequence length and batch size for decoders, regardless of the type of positional encoding. Meanwhile, for encoders the we observe that DAGER is exponential in length and polynomial with high degree in terms of batch size. To this end, the heuristics we described are crucial to significantly reduce the search space. Algorithm 3 DAGER for Encoders1: function ATTENC(T, B, ∂L ∂W Q 1 , ∂L ∂W Q 2 , V, P, f 0/1 , τ 1/2 ) 2: n, T * , D * ←GETTOK( ∂L ∂W Q 1 , V, P, f 0 , τ 1 ) 3:T * ←TOPBTOKENS(T * , D * , B)4:N ← {} T * i ← T * i \ {EOS} 9:for i ∈ SORT(N ) do 10:S i ← T * 1 × • • • × T * i 11: S corr i ← {s ∈ S i | d(f 1 p (s), 2) < τ 2 .∀p ∈ [i]} 12:for s ∈ S corr i do 13:for p ← 1, . . . , i do 14:T * p T * p \ {s p } 15: S * best ←TOPUNIQUE( l i=1 S i , ∂L ∂W Q 2 , B) 16:return S * best In this section, we provide pseudocode for DAGER when applied to encoderbased LLMs. We provide it in Algorithm 3, where we first find the set of client sequence lengths n j and store them in N (Line 4 to Line 8). We then go through the n j s from the smallest to the largest (Line 9), enumerating all possible sequences s ∈ S i of length i (Line 10). Importantly, when a correct sentence s ∈ S corr i is found its tokens are removed for the token sets T * i (Line 14). Finally, we return the deduplicated best reconstructions across different sequence lengths S * best (Line 15). We note that when S i is larger than 10M combinations, we sample 10M random combinations from it instead.In this section we describe additional details regarding the experimental setup for DAGER.In particular, we explore its feasibility on the base variant GPT-2 BASE , featuring a 12-layer transformer with a 768-dimensional hidden state, 12 attention heads and a feed-forward filter of size 3072. Additionally, we examine the effects of model size by considering GPT-2 LARGE , which contains 36 layers, a 1280-dimensional hidden state, 20 attention heads, and a feed-forward filter of size 5120. To demonstrate the versatility of our approach, we also evaluate our attack in a next-token prediction context on the GPT-2 BASE model. We further demonstrate the efficacy of our attack on LLaMa 2-7B [13] and BERT BASE [14] to illustrate our performance on a state-of-the-art decoder and an encoder-only model, respectively. All models were sourced from HuggingFace [41] in their pre-trained form, following standard practice in language modeling research [42] . Full specification details for all models can be found in Table 6 .Datasets In our evaluation, we utilize three binary classification datasets with varying sentence lengths, namely the Corpus of Linguistic Acceptability (CoLA) [15] , the Stanford Sentiment Treebank (SST-2) [16] , which are part of the GLUE benchmark [43] , as well as the Rotten Tomatoes [17] sentiment analysis dataset. While our algorithm is data-independent, previous studies have indicated that text size can affect reconstructability [11, 6] . We demonstrate robustness to this factor by selecting the aforementioned datasets, with CoLA featuring text typically ranging from 4 to 9 words, SST-2from 4 to 13 words, and Rotten Tomatoes -from 10 to 27 words. We note that the binary classification setting has been shown to be a less vulnerable than next-token prediction which can be attacked via label reconstruction attacks [35] , however, we conduct an additional experiment to substantiate the claim in this setting. Finally, to showcase DAGER's capability to handle arbitrarily long sequences, we leverage the European Court of Human Rights (ECHR) [18] dataset which includes sentences that are over 1000 words long, far exceeding the maximum input length of any of the aforementioned models. Table 8 : Ablation study on GPT-2 BASE with and without the rank threshold heuristic. We report scores of 0 for any example that has full-rank gradients. R-1 and R-2 denote the ROUGE-1 and ROUGE-2 scores respectively. Reference plays like the old disease-of-the-week small-screen melodramas. DAGER plays like the old disease-of-the-week small-screen melodramas. LAMP Cos plays it like the old screen impactnorm disease . small-screen like melodramas.B = 16 B = 32 B = 64 B = 128 R-1 R-2 R-1 R-2 R-1 R-2 R-1 R-In section Sec. 5.3, we described that for full-rank matrices we attempt a best-effort reconstruction by artificially restricting the rank by a threshold b. Here we demonstrate the effect of this component by showing the performance of DAGER without attempting to recover any part of the sentence. Any time we observe a sample with full-rank gradients at either the first or second layers, we immediately fail and report a score of 0. The results can be seen in Table 8 .In Table 9 we show sample reconstructions between the best-performing baseline LAMP_Cos for a batch size B = 1. We note that DAGER achieves exact reconstruction, while LAMP_Cos can predict less than half of the sentence correctly.In this section, we show how DAGER performs under a defended setting, in particular by adding random Gaussian noise with variance σ 2 to all gradients. We explore the range σ ∈ [10 -5 , 5 × 10 -4 ], as for any σ ≥ 10 -3 , the sentiment prediction accuracy of the converged model drops to below 80% from > 87%. We apply DAGER on the GPT-2 model for the Rotten Tomatoes dataset at B = 1. Due to the highly random nature of this type of defense, we cannot simply filter the sequences by measuring the single span check distance at layer l = 2. Instead, we utilise that further layers l > 3 retain the same property that the input embeddings only depend on previous tokens, and measure the average d =L DP l=2 d(f l-1 i (s), l)for a certain number of layers L DP , which we optimise as a hyperparameter. Further, because any noise will make the gradient updates full-rank, for computation purposes we set a constant rank of r = 100, which is much higher than the length of any sentence. While it has been shown [45] that differencial privacy provides provable guarantees for protecting privacy, we provide promising initial results, as seen in Table 10 . We believe that there are numerous improvements one could make, but leave these for future work.Table 10 : Experiments on the differential privacy setting under Gaussian noise on the GPT-2 model with a batch size of 1 on the Rotten Tomatoes dataset. R-1 and R-2 denote the ROUGE-1 and ROUGE-2 scores respectively. -1.9σ = 10 -5 σ = 5 × 10 -5 σ = 10 -4 σ = 5 × 10 -4 R-1 R-2 R-1 R-2 R-1 R-2 R-1 R-2 74.0 ± 3.0.9 +3.3 -0.7Table 11 : Miscallaneous experiments, referenced in the evaluation section. We applied DAGER on the Rotten Tomatoes dataset for B = 16, if not specified otherwise.LLaMa-3 70B (B = 1) LLaMa-3.1 8B Frobenius norm loss ReLU activation LoRA (r = 256) R-1 99.9 Any other experiments, namely the ones on LLaMA-3 70B, LLaMa-3.1 8B, DAGER under LoRA training, or DAGER using different loss functions are included in Table 11 .In our work, we use the publicly available datasets CoLA, SST-2, Rotten Tomatoes and ECHR. CoLA is licensed under the MIT license. No public licensing information was found for SST-2 and Rotten Tomatoes. Furthermore, we use ECHR under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY 4.0) license. For privacy concerns, ECHR has issued a statement of protection of personal data that ensures private data was handled appropriately 1 .In terms of Large Language Model architectures, we use GPT-2 under the MIT license and BERT under the Apache License. All aforementioned licenses permit our use of the underlying assets for the purposes of this paper. We obtained access to LLaMa-2 through the Llama 2 Community License Agreement2 which permits the model's use in commercial and research settings.Finally, we obtain the code for the LAMP and TAG attacks through the public repository for LAMP which is licensed under the Apache License 2.0.NeurIPS Paper Checklist• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).The statement can be found under https://www.echr.coe.int/privacy.The full license can be found under https://ai.meta.com/llama/license/. 


Decision: DAGER is a method to reconstruct input text for Centralized Federated Learning. In this problem there is a federated learning aggregating server (that is honest but curious) that is aggregating gradient updates and performs the model weight updates. 
The proposed method leverages the low-rankness of self-attention gradients to find the correct embeddings and reconstruct training data. 
This is is a narrow but interesting problem. Overall the reviewers were positive (but not enthusiastic) about this manuscript. The authors did a good job in the rebuttal and the paper should be accepted as a poster.

Reviews: review: paper_summary: paper_summary: In this paper, the authors propose the DAGER algorithm which leverages the low-rankness of self-attention layer gradients in order to filter out incorrect embedding vectors and recursively reconstruct true input text. DAGER works within the Centralized Federated Learning setting, where the server is honest in aggregating updates and performing model updates, but is curious to try to recover personal information from each client.
strength_weakness: strength_weakness: 1. I'm curious about the computational complexity of DAGER. It seems that the search space can be extremely large (even when heuristics are used), and recovering individual tokens could take awhile.
2. (minor) In the related works it would be nice to go deeper into research within the gradient leakage in the text domain. A specific breakdown of how this paper differs from the current methods.
questions: questions: Would this be able to work within the decentralized FL environment (i.e. could a single client, acting as the aggregator, decipher other agent text)? 

In the Centralized FL environment, would asynchronous training affect the performance of DAGER or render it infeasible (asynchronous, stale updates)?

There's a small error in Figure 1 in Sequence recovery (middle part, 2nd sequence), AA_ should not be in the span and BA_ should be? In the diagram the opposite is true.

How does DAGER perform against noise (DP) or malicious users? Can it be ammended to combat this?

What happens if the vocabulary size is extremely large? Won't this process take a very long time (i.e. does it scale with |V|)?
How expensive is this enumeration process? Especially if the sequence is long?

Very cool insight about size of model and how that allows gradients to be reconstructed easier because they're low rank since d is increasing so rapidly. Bigger is not always better when it comes to privacy!
limitations: limitations: Yes.
paper_summary: paper_summary: This is the first paper to use low rank decomposition to attack the gradient of the self-attention layer to extract information for LLM.  It also provides a fast algorithm to recover the correct token first, then the sequence.
strength_weakness: strength_weakness: Notation is heavy and hard to follow. Could authors add a notation table, or input before algorithm so it is easier to follow? 

Some people might argue it not use latest model but working on llama3 could be resource consuming. It might be a weaknesses of the author's work, but it could also be a future direction.

If possible, could the author discuss a little bit about the usage of quantized models and the influence of lora for fine-tuning regarding reconstruction results?

Also, could authors add some reconstructed text for comparison?
questions: questions: see weakness above
limitations: limitations: see weakness above
paper_summary: paper_summary: The authors proposed a method to recover user training data from gradients in federated learning. The key observation is if a linear network component exists in the overall neural network, the gradient of the linear component parameter can be shown as a linear combination of the input to this linear component. Taking the the first layer of the transformer, the input token embeddings can then be recovered, assuming the number of tokens involved is smaller than the dimension of the embedding space. Extending the idea to the second layer helps to recover the whole training sequence. The authors show empirically the proposed method can significantly improve the state of the art.
strength_weakness: strength_weakness: 1. The theory development is weak. The idea is rather straightforward, however, the authors need to lay down more carefully the technical assumptions. For example, is there any requirement on the loss function, i.e., MSE or cross-entropy? Are there any requirements on the differentiability? For ReLU, the loss function is sub-differentiable, and how does this impact the method? 
2. The requirement that b<d needs better justification. The embedding space is usually not very large (e.g, 512, 768, or 1024). However, the number of tokens used by a single client in a single training step (or before synchronizing with the central server) can be considerably larger than this. The authors argue the condition is satisfied for reasonable input lengths and batch sizes, which I found to be less than convincing.
3. Conceptually it is not clear why the method in Algorithm 1 works so well, and some better explanation is needed. The embedded tokens are not linearly independent, and there can be significant false positives in this procedure, yet the authors observed otherwise. A more careful analysis is warranted.
questions: questions: Some questions are as given above. Additionally,
1. On page 6, it is mentioned that the second layer filtering allows it to recover the exact 32 "starting tokens". What does it mean here "starting tokens"? Why is this an important issue to mention here?
2. Would higher layers (L>2) also help? Why is this not considered?
limitations: limitations: Yes, it was discussed in the conclusion, particularly when B is large.

Comments: comment: Thanks for the response. I feel the authors will be able to make the expected improvement/clarification based on these questions/responses. I'll keep the score.