Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Authors: Rahul Krishna Thomas
Louai Zahran
Erica Choi
Akilesh Potti
Micah Goldblum
Arka Pal
Venue: ICML 2025 poster (2025)
Keywords: LLMs
Privacy
Hidden States
Primary area: deep_learning->large_language_models
TL;DR: We devise a simple attack that breaks existing private LLM inference methods, and we further introduce a robust multi-party private inference scheme.

Abstract: Recent advances in Large Language Models (LLMs) have led to widespread adoption of third-party inference services, raising critical privacy concerns. In this work, we introduce a novel reconstruction technique that can recover original prompts from hidden states with nearly perfect accuracy across multiple state-of-the-art LLMs in the increasingly important open-weights setting. Although the attack is conceptually simple, it has not  -- to the best of our knowledge -- previously been described nor shown to work practically. Furthermore, our attack remains effective against various permutation and noise-based defenses, challenging assumptions about the security of previously proposed schemes. To address these vulnerabilities, we propose Cascade, a multi-party inference scheme that leverages sharding in the sequence dimension to retain privacy of the user input. Through theoretical analysis and empirical evaluation, we demonstrate that Cascade is secure against both our attack as well as previous methods, while maintaining computational and communication efficiency. Our findings highlight the importance of rigorous security analysis in privacy-preserving LLM inference and offer practical solutions for secure deployment.

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Rahul Thomas 12
Louai Zahran'
Erica Choi
Akilesh Potti
Micah Goldblum 13 Arka Pal
Abstract
third-party LLM inference services that host these models. This raises significant privacy implications, particularly in domains where confidentiality of data is paramount, such as healtheare, finance and legal applications, and in juris- dictions where data privacy is subject to regulations (e.g. GDPR in Europe). As such, growing area of research inter- est is the creation of inference methodologies and schemes that protect the privacy of user prompts.
Recent advances in Large Language Models (LLMs) have led widespread adoption of third- party inference services, raising critical privacy concerns. In this work, we introduce a novel re- construction technique that can recover original prompts from hidden states with nearly perfect accuracy across multiple state-of-the-ard LLMs in the increasingly important open-wes weights set- ting. Although the attack is conceptually simple, it has not to the best of our knowledge previ- ously been described nor shown to work practi- cally. Furthermore, our attack remains effective against various permutation and noise-base de- fenses, challenging assumptions about the secu- rity of previously proposed schemes. To address these vulnerabilities, we propose Cascade, a multi- party inference scheme that leverages sharding in the sequence dimension to retain privacy of the user input. Through theoretical analysis and em- pirical evaluation, we demonstrate that Cascade is secure against both our attack as well as pre- vious methods, while maintaining computational and communication efficiency. Our findings high- light the importance of rigorous security analysis in drivacy-preserving LLM inference and offer practical solutions for secure deployment.
One approach to
peeeeerinn--ifeeeeeeeee infennncifeeeneeeee to have multiple parties jointly perform the inference, with the idea that each party cannot reconstruct the input with the infor- mation that it is given in the protocol. This approach is known as Secure Multi-Party Computation (SMPC) and has a long history of application to general functions (Yao, 1982; Goldreich et al., 1987). Recently, the methodologies of SMPC have been applied to LLMs (Huang et al., 2022: Hao al., 2022; Pang et al., 2023; Akimoto et al., 2023; Dong et al., 2023b; Li et al., 2024). However, SMPC meth- ods introduce significant computational and communication overhead, particularly so at non-linearities in the model.
Thus, other works aim to mitigate the punitive costs of SMPC through statistical obfuscation. Recent work (Zheng et al., 2024; Yuan et al., 2024; Luo et al., 2024) has used the permutation permutationeequivaaaanee of transformers (Xu al., 2024) to propose permutation- based schemes for private inference. In these schemes, hidden states are revealed as permuted plaintext to the party performing inference. To justify secu- rity, these works refer to the extremely large permutation space and conclude that input reversal is infeasible.
1. Introduction
In this paper, we show that such permutation- -base schemes are in general not secure the open-weights setting. We devise novel vocab-matching attack' (see Figure 1) that can nearly perfectly decode the user input in this setting, improving on existing work (Wan et al., 2024). We show that this attack maintains near-perfect decoding performance across various permutation types, including those used by the schemes above. Furthermore, the attack is capable of decoding against common noising methods proposed the literature for private inference (Morris et al., 2023a).
Modern large language models (LLMs) now often comprise hundreds of billions of parameters, necessitating significant hardware resources for deploying them for inference. In particular, recent open-weights models demonstrate cutting- edge performance (DeepSeek-AI al., 2025; Qwen al., 2025), but remain difficult for many run. Individuals and organizations have therefore begun to increasingly rely on
Equal contribution 'Ritual AI Stanford University CColumbia University. Correspondence to: Arka Pal (Project Lead) Farka@ritual.nes
We then introduce new multi-party scheme, Cascade (see
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
OOur implementation is available at https://gitthnni com/z tratualllll aaal-nntt -net/ mam--eteeral..

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
User text
"Computer viruses are paresilic programs which are
Comreponding hidden states at layer
[h,,... ........e A. An]
B AttriNodss
U.A 1AI. 12 4.4.7711
otthowighh +m)-v
Hidden States
Goy
Choose tokan that matches observed hidden state
103.3.10
2.4.9.13
arginin (déxt(a, AJ)
+ q: k Layeneerm
h + q, A. Layernerm O-pray
+ q K
Goal: recover user text
CompNodes
Layemmor
Cygray
11 22,
11 22,-
[1.2, 5.9
J3, 4,
User text recovered so far: "Computer vruses are parasitic"
Predicted from Ntrate thoough sokans staps eevocabdary
Token indices: ....,
User text: "Computer viruses parasitic programs which
Figure 1. Left: High-level representation of the yocab-matching attack to decode user text from hidden states in the ppen-weights setting. This attack achieves nearly perfect decoding accuracy, even if hiddens are permuted or noised. Right: Schematic representation of our proposed srivacy-preservve multi-party inference scheme, Cascade, which prevents the vocab-matching attack.
Figure 1). which avoids our attack by leveraging token shard- ing. We show that Cascade is also resistant to existing re- versal approaches in the literature (Wan et al., 2024; Morris et al., 2023b). While Cascade does not provide the rigor- ous privacy guarantees of cryptographic MPC schemes, is much more efficient than them, and presents new paradigm in the trade-off between scalability and security.
our paper, we are instead concerned with the reversibility of full intermediate LLM states [h1,
E IR Nxd
The two closest previous works on reversibility in our set- ting are those of Wan et al. (2024) and Morris al. (2023b). The former deals with hidden state reversal, while the latter foeuses on logit output distribution reversal. In both papers, the authors train transformer- -ased network to reverse the sequence of hidden states into the original token inputs. Experiments are conducted on two decoder-based models, L.lam-2-7B and ChatGLM-6B. Average F1 scores of ap- proximately 60% are achieved across a range of datasets in Wan al. (2024) on hidden states near the last layers, and scores around 75% are achieved for logit reversal in Morris al. (2023b). Importantly, the latter paper does not assume adversary access to model weights, while the former deals with model provider performing inference on users' embeddings and is more analogous to our setting.
2. Setup& & Threat Model
We assume the setting of a user U who wishes to perform inference with an LLM model M on some input prompt æ, which can be considered an ordered sequence of tokens [21, 22, -..,--. xN We denote the size of the hidden state of the LLM by d, and the sequence length by N.
As the user U does not have the resources to perform the inference themselves, they rely on a set of third-parties P1. P...,, The model weights M, including the embedding lookup table, are known to all parties. We as- sume that the parties behave semi-honestly, as past works (Zheng et al., 2024; Luo et al., 2024; Dong et al., 2023b; Yuan et al., 2024). Semi-honest parties follow the defined protocol faithfully, but may attempt to recover the user's ' data from information that they receive during the protocol.
Petrov et al. (2024) propose an attack that shares some elements with ours, like the exploitation of the unidirectional nature of decoder-based LLMs and the finite lookup table. However, they focus on gradient reversal into original inputs in the federated training setting, distinct from our private inference setting. Also, their method relies on full-rank properties of the gradients, which are not always satisfied. By contrast, our method does not have any such restrictions.
3. Related Work
To the best of our knowledge, no existing work succeeds reversing permutations of LLM hidden states.
Several existing works have investigated the reversibility of LLM embeddings (Song& & Raghunathan, 2020; Morris et al., 2023a; Li et al., 2023b; Kugler et al., 2024) with rela- tively good decoding performance. Unlike our setting, these focus on the reversal of a single vector e = d(x)) E Rdd, where & is an embedding model that returns a single fixed- size vector from an N -ttoeen input æ = [æ1, Z2. v. In
4. Hidden State Reversal
We begin by considering the general case where one of the parties performing inference, Pk. receives hidden states h [b,, he...., hy] at some layer of the LLM M.
2

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Can the party Pk reverse the hidden states h to the input sequence of tokens -2,,, [v] that produced h?
current state-of-the-art LLMs.
(A4) The model weights are known to the party Pe. Later, in the settings of Yuan et al. (2024); Luo et al. (2024), we can relax this assumption.
4.1. Informal Attack Description
We outline our proposed attack below, and provide a visual depiction in Figure 1.
Generally, (A1) is not satisfied due to non-determinism.
The attack begins with batched forward pass over all length-1 sequences [v], where ranges over words in the vocabulary V. From this, the adversary gets V = [ candi- date layer hidden states h(v) E 1x They set the first predicted input token &1 to be the token v for which h(u)
4.2.2. NON-DETERMING
Assumption (A1) asserts the forward pass performed over the vocabulary matches the forward pass that generated the given hiddens exactly. In general, due to the non- associativity of foating-point operations (Villa et al., 2009), this does not hold. In the GPU setting with parallel asyn- chronous thread exccution and pooling without global syn- chronization, there can be considerable variation in the out- put (Shanmugavelu et al., 2024). In addition, differences in hardware, random number seeds, environment variables, and the state of initialized memory on the machine add to the variability, and these may not be known to the adversary.
exactly matches the first hidden state h1.
Next, the adversary performs batched forward pass over all length-2 sequences [2), 2) with U E V. to get V candidate layer hidden states h( v) E R2xd, Now, they set the second predicted input token B2 to be the token v where the second row of h ( v) equals the second hidden state hı2.
In general, the nith stage, using the first n predicted input tokens T1,..., -,, the adversary performs a for- ward pass over all length-n sequences [Tr,..., -n,-, v] with V E V. They obtain V candidate layer I hidden states fn-1, v) E Raxd, and set the rath predicted in- put token _, to be the token e where the nth (last) row of candidate states matches the with hidden state hn- Iterating over n 1, ...... NN. the adversary sequentially obtains the predicted input sequence è from the layer / hidden states h.
Due to the presence of this reducible and irreducible noise, exact matching cannot be used successfully with our attack. Thus, we loosen our matching requirements by computing the LI LI-distance between the last row of candidate hidden states and the given hidden state, and accept a match for token if the distance is below some threshold e. If no match is found, we choose the token with minimal L1-distance.
However, by allowing an c-ball for matching, we increase the possibility of collisions as stated above. Is our attack still successful - i.e. is assumption (A2) still satisfied even with this fuzzy matching? In Section 4.4, we find the answer is emphatically yes.
Naively, one might expect that an exact match of h. would re- quire an exponential brute-force search over all V possible sequences of tokens æ. However, we see that by exploiting the autoregressive property of transformers, this is reduced to linear search; the total cost of this attack is O(VN).
4.2.3. EFFICIENCY
4.2. Practical Implementation
We optimize runtime using a proposal model to provide a likelihood-basee order of iteration through the vocabulary. We find that this modification reduces the average number of tokens searched through at each step from V/2 to ~ 100, resulting in over 1000x speedup. Further, implement novel variation of rey-valuu-caching (K (KV-caching) to reduce the computational cost of our attack. Further details on these optimizations are given in Appendix A. With these improvements, we reduce the decoding time of prompts of length 50 from many hours to typically less than 30 seconds. We provide details on the scalability of our attack with respect to model size in Appendix B.
4.2.1. ASSUMPTIONS
The key assumptions necessary for our attack are as follows.
(A1) The forward pass over the vocabulary in the attack will match the forward pass that generated the given hiddens h.
(A2) Hidden states of LLMs are non-colliding: there are few matches between candidate tokens and hidden states hn at each step of the attack. If the average number of matches at each step is M, then the search space grows as MN which infeasible when M or N is large. Prior work (Dong et al., 2023a) has demonstrated the rank-reducing effects of attention, so is plausible that the size of the subspace in latter layers is too small to prevent collisions. Still, we will see this assumption holds in practice.
4.3. Formal Attack Description
We now provide a formalized description of our attack, incorporating the modifications for efficiency and handling the nondeterminism described above, in Algorithm 1. For step-by-step walkthrough, see Appendix C.
(A3) The LLM employs unidirectional attention. This holds for dnccoder-only architectures, which are de-facto for many
3

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Algorithm 1 Vocahulary-Matchingg Attack
Table 1. Percentage of perfectly decoded evaluation samples by bocab-matching at layers of Gemma-2-22 2-2--I IT and Llama-3. 3.1-BBBBBBB Instruct.
input Model M, layer hidden states h = , hNl, vocabulary V, proposal model P. L1-threshold e
output Decoded token sequence .. = [0i, F2,, ..., ØN]
1: Initialize empty sequence T
Layer
Gemma
Llama
2: for i to N do
3: Vordered -- argsort P(ø)) {Get ordered vocabulary from proposal model}
100%
100%
100%
100%
4: min_dist 4 00
11
100%
100%
5: best match + None
16
100%
100%
6: for v Vordered do
21 100%
99.9%
7: g <- ( ol) {Forward pass up to layer 1}
26
100%
99.7%
8:
dist 1g hi]l1 {Calculate L1 distance)
9:
if dist < min_dist then
10:
min_dist + dist
In the rare cases where perfect decoding not achieved, prompts contained formatting characters like newlines and hyphens, or grammatically incorrect word repetitions. These cause the proposal model to accept an incorrect token early when its LI error is below the e threshold, even when the correct token has a small L.1 error. Tuning with larger training set using full vocabulary search may mitigate these errors, but higher computational cost.
11:
best_match +-
12:
end if
13:
dist <e then
14:
2, 5~
15:
break
16:
end if
17:
end for
18:
if' dist 2 then
The success of our attack allows us to conclude that LLM hidden states are highly distinct and non-colliding
19:
E. < best_match
20:
end if
end for return
5. Permuted Hidden State Reversal
We now consider the case where one of the parties perform- ing inference receives permutation of the intermediate sequence of hidden states h at some layer / of the LLM M.
4.4. Experiments & Discussion
We conduct our experiments on two state-of-the open- source LLMs, Gem-a-2-2B-IT (Team et al., 2024) and Llama-3. Baama-3.1-8B-Inmee I-St-unstttct (Grattafiori et al., 2024). These mod- els have different sizes, training methods, and architectures. We test on samples from the Fineweb- -Edueeu-buuuue dataset (Penedo et al., 2024). The proposal model is the same as the model being attacked. To ensure that the dataset is unseen by the proposal model, we use the CC-MAIN-200 MAAAN--222410 10 data split, which postdates the models' training cutoff dates. To speed up evaluation, test on every fifth layer of the model, extracting hidden states at layers 6, 11, 16, 21, and 26.
5.1. Existing Work
Recently, number of works have proposed utilizing permu- tations to perform party-computation (MPC) setup.
inference in multi-
Zheng et al. (2024) introduce PermLLM. They permute at the non-linear components of the LLMs in order to re- veal them 'safely' to one of the parties, and therefore avoid expensive iterated inter-party communication. The permu- tation is done on the attention logits before the softmax, layer normalizations, and at the non-linear functions in the MLP block. The latter is purely elementwise function, so the authors can do a full permutation across the [N, d] elements, resulting in a permutation space of size (Nd)!. However, softmax and layer-norm are row-wise operations, so the permutation applied in this case a (distinct) permu- tation the columns, followed by permutation of the N rows, resulting in permutation space of size (d!)).
For each layer of interest, we tune e by performing a ternary search on a small training set of 50 prompts from Fine Web, to determine the optimal LI L1-threshold under which pre- dicted tokens are accepted as matches. We evaluate on 1000 held out prompts, and our results are shown Table 1. We find that nearly all evaluation samples are perfectly decoded. All values are given in Appendix D. Due to computa- tional constraints, each evaluation prompt was truncated to a maximum of 50 tokens; however, small-scale experiments with prompts over 200 tokens demonstrated that our results generalize to longer prompt settings vocab-ne vocab-matchin matching still perfectly decodes hidden states into their input tokens.
Yuan et al. (2024) introduce STIP. They permute both the model weights and the user prompt embeddings in the hid- den dimension, and the entire inference process (on the next token) is then carried out by a single party.

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Luo al. (2024) apply ideas from both of the above works to formulate Centaur. This permutes the model weights, utilizing additive secret-sharing for the linear layers, but relies on two-party permuted plaintext computation at the non-linearities (softmax, layer-norm and GeI.U). Permuta- tion is applied in the hidden d dimension.
instead use the sorted L L1-distance, which individually sorts the two vectors to be compared and then computes their L1- distance. Again, the existence of noise may appear to be significant obstacle to this approach. However, we find that even this relatively simple matching approach is robust enough to noise to achieve nearly perfect decoding. Our results are shown in Table 2.
5.2. Permuted Intermediate States Are Not Safe
5.2.3. FACTORIZED-2D PERMUTATION
We now propose a modification of our vocab-matching at- tack in Section 4, which breaks user input privacy for the above schemes in the open-weight setting. Extensions to the attack also break privacy in the closed-weije wwights setting that Yuan et al. (2024) and Luo al. (2024) originally consider: see Appendix for further details. Also, in Appendix J, we explain why theoretical claims on statistical permutation security from Luo et al. (2024) do not anticipate our attack.
We now consider the case of factorized two-dimensional permutation used in Zheng al. (2024), where a hidden- dimension permutation is applied to each hidden state, and then these resulting states are shuffled in the sequence di- mension. The adversary now has:
h perm = [ (1)( T2 m2(ho ...,, TN (ho
where o is a permutation of [M] and each क; permutes a d-dimensional vector. The attack in this setting again uti- lizes the sorted-L1 matching function, but now expands to consider all N rows of heaetppemm as in Section 5.2.1. Re- markably, even in this setting, the hidden states of both models are decoded nearly perfectly across layers (Table 2).
We present our modified attack in the sequence-dimension, hidden-dimension and factorized-2D permutation settings. See Appendix E for detailed pseudocode of the modifica- tions. Our experimental setup is the same as in Section 4.4.
5.2.1. SEQUENCE- -DIUN PERMUTATION
We conelude that permuted hidden states of LLMs are highly decodeable by our attack, and therefore schemes which expose them are not secure in the open- setting.
Assume that permutation has been applied to layer / hidden states = [b,, h2, AN] in the sequence dimension:
heeq.pem (1) (2): .... ho(N))]
where o is a permutation of [N] = {1,2,.... N.. Then, we modify the stage, now choose the vocabulary token u where the nth row of the corresponding candidate hidden state is within an LI-distance of from any row of heeq perm- Suppose this e-ball match is made with the ith row ha(i). We set the wthh predicted input token Fn to v, and remove hote) from consideration for hidden state matching in all future stages. Iterating over n = I...., N, we obtain the predicted input sequence ~ from requence-permutte hidden states peq..
Table 2. The percentage of evaluation samples that were perfectly decoded under sequence-dim. hidden-dim. and factorized-2D per- mutations, for Gemma 2-auma---2BBar 2-2B-IT and Llama-3. 3.1--B- In-ntuuuct.
attack as follows. At the nihh
Layer
Sequence-Din Dim
Hidden-Din
Factorized-2D
Gemma
Llama
Gemma
Llama
Gemma
Llama
99.7%
100%
100%
99.9%
98.4%
6
99.8%
100%
100%
98.5%
99.5%
91.8%
11
100%
100%
100%
99.2%
99.5%
98.9%
16
100%
100%
99.9%.
99.4%
99.2%
98.8%
21
99.8%
100%
98.2% 29.2%
98.9%
99.1%
98.0%
26
99.8%
100%
98.0%
98.2%
99.0%
97.6%
Compared to the vocab-matching attack. the opportunities for collision are now increased up to N-fold, as we match with up to N rows of h rather than one. However, we again observe very few collisions in practice and are able to decode essentially all input prompts: see Table 2.
6. Noised & Quantized Hidden State Reversal
Section 5 shows that modifications to our attack can decode sequence- dimenssood,esii.n -idden-dimension, and factorized-22 permutations of hidden states. We now examine the efficacy of our attack on methods of defense which aim to disrupt as- sumption (A2) in Section 1.2.1, by noising the hidden states or quantizing the model. With enough noise or quantization, decoding can be made impossible. However, high noise will likely disrupt LLM performance. Thus, any such de- fense is a delicate balancing act of ensuring security against our attack, while still maintaining downstream model per- formance. We find that generally, these methods are still not sufficient to defend against our attack. Due to space constraints, we provide much further detail in Appendix F.
5.2.2. HIDDEN- DIM PERMUTATION
Next we consider the case where permutation has been performed on the hidden dimension of h instead. That is, the party performing inference is now given:
perdennperm = [ =[T (hz), Tz (22)) ..., N (lx))
where each n; permutes elements of a d-dimensional vector. In this setting, it is no longer possible to use LI-distance directly to find the nearest vocabulary token match. We
5

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
7. Token-Sharded Multi-Party Inference
row-wise, with expsum(()) (+) == exp(x,) Also, e only performs an expsum after subtracting row-wise maximums, as in the numerically stable subtract-max form of softmax.
As we have found that permutations of hidden states are not secure, a natural follow-up question is whether sharded hid- den states are secure. We suggest the answer is affirmative for certain sharding schemes. We propose defense to the vocab-matching attack based on loken-dimension sharding of hidden states, which leads to a new multi-party inference scheme: Cascade
Tensor
Shape
Shards
Notation
h p q. u
(N, demb)
(Ri, x)
h h p th R q R, k n q k , q Rinss RRnss; b R,ns, a S6 Su a Ri86 Ri8
(H, N.d)
(+, Ri x)
7, k
(H, N,
(+, Sg. *)
q. k
(H, N.
(+, Rg n Sj.*)
Notably, Cascade does not use cryptographic primitives; the computations are nearly unchanged from a standard forward pass, so almost no additional computational overhead is incurred. There is also no degradation of performance, unlike SMPC schemes, no approximations need to be made to efficiently compute non-linearities. The scheme also does not require any trusted party interaction during inference.
a.s
(H, N)
(w)
a, 8
N,
(+, Rr, Sa))
a.s
(H, N)
a 5 9,86
(H, NJ
(+, (+,R.n J.R.SS... Sc))
a (8.0888 g (R.88
m Sk
(H, 1)
(+, R)
m R,8 e 8, 8, m (8:88))8 (R,
m
NH,
(+, +)
m 8, 8k
m &
e*
(H, [H)
(+, (, nS,. +)
(H,
(+, R,,))
u R
u
(II, (Se))
(t,
7.1. Scheme Description
(H, (S,) (S&))
(+, R. nS,,,
u (Ri88))8
At a high level, Cascade exploits the fact that only the self- attention mechanism in transformers has interaction among tokens in a sequence; for all other parts of the architecture, the tokens are treated like batch dimension elements.
Table 3. Sharding for intermediate LLM states, where is a full slice. In slicing notation, a (8, = al; Rs n Sj, St] and m (8,08)) m m [=, R4 n Sy. with Se as in Table 4.
Therefore, the CompNodes each receive only subset of the tokens, and perform the bulk of batch operations in the LLM. Then, self-attention is performed by separate AttnNodes, who each receive Q, K, -rproeections of sharded hidden states from the CompNodes. The AttnNodes send partial attention outputs at each layer back to the CompNodes, who can reconstruct shards of the full attention output.
Tensor Shape
Formula
Sk m e 8% S
(H, N. 1)
max Sx
(H, N, 1)
expsum (a Sh m Sk)
N,, (Sa))
softmax St (
Table 4. Tensors derived from sharded states a 80, uSA in Table 3.
Sharding In multi-headed attention, we let H and HRv be the attention head and kaluv head (for grouped-query attention) counts, N be the token count, dems be the hid- den dimension, and d be the attention hidden dimension. There are three axes of sharding used along the token di- mension: (1) the sharding of hidden states h E R Xdemb, (2) the sharding of query states q E IR Nxxxxx and (3) the sharding of key and value states k, E RH XN xd These involve splitting token indices [N] {1, .,, N into union of disjoint subsets { for hiddens, (5 for queries, and (T for keys and values, where a. y are shard counts. We also shard the positional embeddings E IR N xd and the attention mask s E R x which are initialized pre-inference, as well as the masked logits a E R N and attention output o E N Xdems.
Nodes
There are two types of nodes which hold the sharded states above: CompNodes and AttnNodes. We initialize a CompNodes and 882 AttnNodes, indexed as CompNode, and AttnNodejs for all E [a] and j, E [3].
Inference Cascade breaks single layer inference into the pre-pass by CompNodes, attention-pass by AttnNodes, and post-pass by CompNodes. We describe these in Al- gorithm 7, Algorithm 8, and Algorithm 9 in Appendix G. These form a single layer pass in Algorithm 2.
During Cascade layer / inference, each CompNode; begins with h R. at layer 1, and ends with h R. at layer | + This output is the input to CompNode, for layer + inference, inference for all layers can follow Algorithm 2.
Symmetrization In Appendix M, we show that we can make S and T sharding equal at no loss of security. Thus, from here on, replace T with S and y with 3.
A fter the last layer, CompNodes apply the LM head to get Rh-sharded logits, and the CompNode with the last token will use this to generate the next token's 's embedding". This is sent back to the CompNode with the next token index in R, Then, Cascade inference repeats to generate the next token. This can be sped up with K KV-caching: see Appendix Q.
Our symmetrized notation for any layer is in Table 3. Note that the last six rows rely on tensors that are not directly shards of LLM states, but are derived from them, as in Table 4. Here, max, softmax, and expsum are performed
'The logits can also he returned to the user if desired.
6

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Algorithm 2 Cascade Single Layer Forward Pass
Definition 7.1. We say subset of indices [N] is (c, sequence if it takes the following form for some i:
input R. layer from CompNode; for 1 S i S
output h R: layer 1 + to CompNode, for 1 S i isa
+ U.i+t...,,+c..... -
,....
+ -ritcll
1: for = to ot: CompNode; do
2: q q k. u < pre.pass(h" ..)
26 + 1, +00++i+11 28 + 1
28
10cc-1,,.. 1,...).
3: for j. = to 3: AutnNodeje jk gets
4:
RRS,, , Rr Sr
We focus on these strategies as they fulfill several security desiderata. We emphasize however that other strategies may be preferable to (c, ---hardin depending on the use-case.
5: end for
6: end for
7: for j.k to 3: AutnNodejx do
(e, 6) vs. Number of CompNodes Under (c, --sharding the minimum number of CompNodes a needed to ensure all indices in [A]] are held by some node is given by = [6/c].
8: m S, e St Sk &- attn attn_pass( ( ,, Sh (k))
9: for = to a: CompNode, gets
10: m (S. (R ( (S,
11: end for
7.2.1. LAYER O COMPNODE HIDDEN SECURITY
12: end for
We first consider the security of CompNodes at layer 0 of the scheme, who each hold some token embeddings of the input prompt æ. As embeddings are immediately reversible to their tokens through the lookup table, we conclude that Cascade should not be used when the security of every token is paramount. If individual token security is imperative, Cascade can be integrated with SMPC as in Appendix H.
13: for
1 to at CompNode; do 14: oR: post pass m R:Sk, e RRiSee u R. yam
15: RR +- mlp(h R, + R (Residual and MLP)
16:
end for
7.2. Security Analysis
Given that CompNode has access to some of the N to- ken embeddings, say (en, epg...., Cn,], the possibility of reconstruction of the full prompt is theoretically lower bounded by the entropy of the distribution
In this section, we examine the security properties of Cas- cade. Cascade does not employ cryptographic techniques, so we can only elucidate on statistical security. Nevertheless, we examine wide range of security considerations below. The security of Cascade is function of its implementation parameters: the number of nodes participating, well as the shurding strategy used, i.e. { and {
p((2, :j E [M] (MI...., mi3 Fngs ... Fnn)
The true distribution cannot easily be computed, but we may approximate it using masked token infilling, as in the train- ing of models like BERT (Devlin et al., 2019). RoBERTa (Liu et al., 2019), and ModernBERT (Warner et al., 2024). We use the recently released state-of-the-art ModernBERT: large to probe properties of this distribution under (c. 6)- sharding. We use 200 samples from Fine Web-Eedb to com- pute the ROUGE-L (Lin, 2004) score over argmax-toke token generation. Our results are shown in Figure 2. We see that ROUGE-L score diminishes as both and a increase; good security seems be achieved for c, a 2 8 and thus d 2 64.
Information Leakage To analyze information leakage, we examine isolated computational stages of nodes. In all stages (pre-pass, attention-pass, or post-pass) of Cascade, no information received during the computation. Therefore, all input leakage comes from the stage initialization. Thus, any leakage must occur from the following sharded tensors:
CompNode, + h R. .fm R.Sa, RiSk, uu R.5% 1 1k=11 AttnNode,, + 9º, Sc S
We will examine leakage to CompNodes from h in Sec- tion 1 and Section 7.2.2. We will analyze leakage from
7.2.2. LAYER > 0 COMPNODE HIDDEN SECURITY
q k. Si in Section 7.2.3. Finally, we consider all other sources of leakage to CompNodes in Section 7.2.4.
We now turn our attention to CompNode security of h at deeper layers of the L.M.. Can we select a sharding strategy that defends against our attack outlined in Section 4? Also, do we remain secure to learning-based attacks as in prior works Wan et al. (2024) and Morris et al. (2023b)?
Sharding Strategies When more nodes participate, each has access to fewer tokens and hidden states, which makes reversing the full input more difficult. Even holding the node count fixed, the choice of sharding may also affect the diffi- culty of reversal. For example, is it more secure for node to have access to [hi, lss hg, hıs] or [h,, h2, h12, hia]?
Definition 7.2. Let mmax be the maximum value of / for which an ad adversary has resources to perform V forward passes. Then we define the vocab-matching threshold p as == Imax + 1.
As the space of sharding strategies is vast, we focus on (c, b)-sharding strategies, where each sharded index set takes the form of arith or ( sequunce.
Vocab-Matching Attack matching to ensure large token gaps in nodes. For a
Our defense against vocab-
7

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
ROUGE Score of token-infilling. C vs a
larly analyze BLEU reconstruction scores (Papineni et al., 2002). When c, a 8, we have ROUGE-L score less than 0.25, indicating significant reconstruction difficulty, We also tested on c = 4, = 16 and c = 8, = 24 and obtained ROUGE--L scores scores of 0. and O. 0.144, supporting that security continues to improve by scaling c and a.
256
128
Averago ROUSE Score
64
32
Table 5. ROUGE-L scores of text reconstruction from the hiddens of layer 1 of Gemma-2-2B-IT for various values of c and o under (c, -hhardinn Increasing e or results worse reconstruction.
16
a 8
12
16 64
128
256
C
0.701
0.467
0.349
c 0.427
0.290
0.230
Figure 2. ROUGE-L scores for Layer 0 token prediction using ModerBBEKT-Large as a function of c, the number of 'clusters' in the sharding scheme, and a, the number of CompNodes. Higher a and higher e tend towards lower ROUGE-L, increasing security.
c 0.355
0.222
0.191
We examine the choice of hidden layer, and if Llama repre- sentations are decoded better, in Appendix L. We find simi- lar or better security across these other parameter choices.
(c, 5)-sharding scheme, in each shard, the distance from one 'cluster' of indices to the next is 8 - c 1. Thus, in order to carry out the attack, an attacker cannot perform a single run through V and obtain the next token match; they must search over length 5 c++ sequences of infilled words, like in Appendix C. The cost scales exponentially as V6-c+1 Because V (1100000) in typical modern LLMs² the vocab-matching threshold of any adversary is likely more than p = 3 in practice. Note 5 - c 1- = (a 1)c 1, so regardless of the value of p. we can increase a or c until - c 2 p to prevent vocab-matching. For p = 3, all a, 2 satisfy this.
7.2.3. ATTNNODE FULL SECURITY
So far, analyzed CompNode security. In Appendix M, we examine AttnNode security and show how to improve it through m-splitting, which makes S sharding more granular.
7.2.4. COMPNODE FULL SECURITY
In Section 7.2.1 and Section 7.2.2, we considered leakage to CompNodes from Ri Now, we consider how the shards mR R.S., uR.SS impact security. Our main result is a condition necessary to prevent modified vocab-matchin attack. For proof of this theorem, see Appendix P.
Learning-Basee Based Attacks We now consider learning- based reversal attacks. Although hidden states may not be as easily reversible as token embeddings, it may be the case that as attention propagates information among hidden states, the text-infilling task is easier at deeper layers of the LLM than at the purely textual level. We examine this hy- pothesis by fine-tuning Gemma-2-2B-IT and Llama-3. 1-BB-B-- Instruct on (c, -makeed input sequences from Webe Edu, with the target labels being the full input sequence. Note this is a 'worst-case' scenario where the adversary knows the and 8 parameters. We update both models to use a bidirectional mask, in line with the token-infilling nature of this task. We train until the evaluation loss on a held-out set converges over layer representations from each model, and evaluate on layer hidden states. Our ap- proach is similar Wan al. (2024); Morris et al. (2023b).
Theorem 7.3. Suppose s is unidirectional. For Cascade to be secure, each gap between clusters of consecutive indices in each R₃ must have size 2 p.
Note (c, 8)-shaddingg satisfies this for 5 2 c c In Ap- pendix P, we argue further that such (c, -)-hhrdding is suffi- cient for Layer 0 security, by demonstrating a reduction to an intractable linear program.
7.3. Communication and Computational Costs
We now enumerate communication and computational costs associated with Cascade. As in previous SMPC works (Li et al., 2023a; Dong et al., 2023b; Li al., 2024), we assume perfect parallel transport in communication, homogeneous node-wise bandwidth of B, and inter-node latency of T. We denote F as the number of bytes per element.
Our ROUGE-L scores for reconstructed Gemma-2-2B-IT prompts are shown in Table 5. In Appendix K, we simi-
7. THEORETICAL COSTS
"thhough knowledge of the input distribution can make the hase of the exponential smaller than V. the cost still scales expo- nentially, so large enough c++1 prevents the attack variant.
We first provide theoretical estimates of costs in Cascade.
Computation
There is almost no floating point overhead
8

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
in Cascade relative to vanilla inference: see Appendix N. We provide empirical evidence for this in Section 7.3.2.
Table 6. Total runtime means and 95% confidence intervals in sec- onds, for a single 128-token prompt forward pass on Bert-Base and Bert-Large for MPCFormer, Puma, and some Cascade settings.
Communication We present single layer communication byte and time overhead formulae, derived in Appendix O:
Scheme
Bert-Base (s)
Bert-Large (s)
CommBytes 3F + +d + 2H) N (L)
MPCFormer
55.320
141.222
Puma
33,913
73.720
CommTime = 27 + FF + +2Hxv)
max [Ra]
Cascade Ino Ray
0.11 [0.10, 10, 0.13]
0.32 10.23,1.07]
B
(2)
Cascade
0.32 [0.31, 0.36]
1.01 [0.97, 1.09]
F(d + 2
mnax (Syl.
Cascade
0.59 [0.51,0.69]
1.57 [1.44, 1.73]
B
Cascade 0.74 [0.62, 0.96]
1.58 [1.27, 1.97]
Note Equation (1) scales linearly with 3, so byte overhead minimized with fewest AttnNodes. Also, communication time is minimized when [8 max; [R:] and max; |Sy] are min- partition [N], then max; R 2 [N/a] and max, |sy| [N/3]- Equality holds when all R,, and all Sy. are around the same size. Thus, (c, -haarrig has optimal communication time.
Vanilla
0.09 [0.08,0.12]
0.27 [0.20, 0.99]
imal. For fixed a, 3, since {= and {S
We further benchmark Cascade with a = 4, 8, using a (c, 8) -h-shrdd scheme with = and no m-splits. We use clusters of and 18 machines for a = 4 and 8, with 4 cores per node. Performance in these cases is slower than for 1. due to communication overhead. Still, Cascade is 90 faster than MPCFormer and 45x faster than Puma for Bert-Large, even in its slowest setting. In Appendix R, we further test Cascade runtime across various model sizes, and find that it scales well to larger models.
7.3.2. PERFORMANCE EXPERIMENTS
We now evaluate the real-world performance of Cascade through the distributed computing framework Ray (Moritz et al., 2018). We run our experiments on Paperspace ma- chines with 16 vCPU and 64GB RAM, with the CPU model being Intel Xeon Gold 6226R CPU @ 2.90GHz. All ma- chines are colocated in the same region with an average bandwidth of 2 Gbps and latency of 0.38 ms. We repeat single forward pass on Bert- Base and Bert-Large with 128-token prompt& a total of 100 times.
Table 7. Communicated bytes for a 128-token prompt forward pass on Bert-Base and Bert- Large for MPCFormer, Puma, and Cascade.
Scheme
Bert-Base (GB)
Bert-Large (GB)
MPCFormer
12.089
32.577
Puma
10.773
27.246
Cascade.=1
0.009
0.025
We benchmark against two recent SMPC schemes for LLM inference, MPCFormer (Li et al., 2023a) and Puma (Dong et al., 2023b). For MPCFormer, we modify the Crypten implementation use public rather than private weights, to match our open-weights setting. Puma data is taken from Dong et al. (2023b), as it is built on SPU with its own set of optimizations. Our results are shown in Table 6.
Cascade
0.038
0.101
Cascade
0.076
0.203
Finally, we compare total communicated bytes for Cascade versus MPCFormer and Puma in Table 7 above. Even in the most expensive setting, Cascade is 160x x more efficient than MPCFormer and 140x more efficient than Puma. Thus, with significant improvements in computation and commu- nication cost, Cascade offers a new paradigm in the trade-off between scalability and security.
We first compare Cascade for a = 1 without Ray against vanilla inference, to estimate protocol overhead. The mean runtime is 109ms vs. m1 for vanilla inference for Bert- Base, and 320ms 273ms for Bert-L Profiling shows this minor increase is due to the attention-score compila- tion step discussed in Appendix N. Nevertheless, the mean runtime is within the 95% confidence interval of vanilla inference in both cases.
8. Conclusion & Future Work
We identify a new attack for decoding LLM hidden states into their original user text in the increasingly important open-weights setting. This nearly perfectly decodes even permuted hidden states, effectively invalidating the security of some existing MPC schemes. We also introduce a novel multi-party scheme, Cascade, that leverages token sharding to defend against our attack and existing attacks in the litera- ture. Future work could investigate the choice c threshold in our attack, or examine the security of alternative sharding strategies in Cascade.
Next, we compare the performance of Cascade with a and using Ray. As seen above, this is slower than not us- ing Ray by around factor of 3x. This slowdown can be attributed to framework-specife overhead, such as serial- ization. In other words, Cascade is so efficient that the distributed compuuttddccuuteeeeeeeee framework overhead now constitutes a significant proportion of its slowdown from vanilla infer- ence, rather than proocoo-sppecifi overhead.

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Impact Statement
Zhou, Y., Zhu, Y. X., Xu, Y., Huang, Y., Li, Y., Zheng,
Y., Zhu, Y., Ma, Y., Tang, Y., Zha, Y., Yan, Y., Ren, Z. Z Ren, Z., Sha, Z., Fu, Z., Xu, Z., Xie, Z., Zhang, Z., Hao, Z., Ma, Z., Yan, Z., Wu, Z., Gu. Z., Zhu, Z., Liu, Z.. Li,
This paper presents work whose goal is to advance the field
of Machine Learning, and particularly, of rrtvacy-preservee inference of LLMs. Our work may lead the enactment of more secure and scalable methods of private inference in the open-weights setting. There are many potential soci- etal consequences of this, none of which we feel must be specifically highlighted here.
Z., Xie, Z.,, Song, Z., Pan, Z., Huang, Z., Xu, 7 Zhang, Z. and Zhang, Z. Deepseek-rl: Incentivizing reasoning capability llms via reinforcement learning, 2025. URL /ttp:://aaxivvvii
abs /2w.b.////1..... 12948.
Devlin, J., Chang. M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for lan- guage understanding, 2019. URL https: //axxiv. org/ hts/abs/18810 04805.
References
Akimoto, Y.. Fukuchi, K., Akimoto, Y., and Sakuma, J. Privformer: Privacy-preservin transformer with mpc. In 2023 IEEE 8th European Symposium on Security and Privacy (EuroSP), pp. 392-410, 2023, doi: 10.1
Dong, Y., Cordonnier, J.-B., and Loukas, A. Attention is not all you need: Pure attention loses rank doubly expo- nentially with depth, 2023a. URL stttps://arxils org/ abaaab//22 22003/210..00 03404.
BaroSP57164.2023.00
Anderson, T. W. The integral of a symmetric unimodal func- tion over a symmetric convex set and some probability inequalities. Proceedings of the American Mathematical Society, 602):170 1955.
Dong, Y., jie Lu, W., Zheng, Y., Wu, H., Zhao, D., Tan, J., Huang, Z., Hong, C.,, Wei, T., and Chen, W. Puma: Secure inference of Ilama-7b in five minutes, 2023b. URL https: / /awpiv..vvvv.////////...///.avva org abss 2tabb////30..mm 12533.
BitsAndBytes. Bitsandbytes: Optimized 8-bit and 4-bit ma- trix multiplication routines. attps://giitiie com/ bi tritannbyyts-- wwwaanbbess-ouurattaaeeeeee 2025. Accessed: 2025-01-28.
Edelmann, D., Móri, T. F., and Székely, G. J. On relation- ships between the pearson and the distance correlation coefficients. Statistics & probability letters, 169:108960, 2021.
DeepSeek-AI, Guo, D., Yang, D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P. Bi, X., Zhang, X., Yu, X., Wu, Y., Wu, Z. F., Gou, Z., Shao, Z., Li, Z., Gao, Z., Liu, A., Xue, B., Wang, B., Wu, B., Feng. B., Lu, C., Zhao, C., Deng, C., Zhang. C., Ruan, C., Dai, D., Chen, D., Ji, D., Li, E., Lin, F., Dai, F., Luo, F. Hao, G., Chen, G., Li, G., Zhang, H., Bao, H., Xu, H. Wang, H., Ding, H., Xin, H., Gao, H., Qu, H., Li, H. Guo, J., Li, J.. Wang. J., Chen, J., Yuan, J.. Qiu, J., Li, J., Cai, J. L., Ni, J., Liang, J., Chen, J., Dong. K., Hu, K., Gao, K., Guan, K., Huang, K., Yu, K., Wang. L., Zhang, L., Zhao, L., Wang. L., Zhang, L., Xu, L., Xia, L., Zhang. M., Zhang, M., Tang, M., Li, M., Wang, M., Li, M.. Tian, N., Huang, P., Zhang, P., Wang. Q. Chen, Q. Du, Q., Ge, R., Zhang, R., Pan, R., Wang. R., Chen, R. J., Jin, R. L.. Chen, R., Lu, S., Zhou, S., Chen, S., Ye, S., Wang, S., Yu, S., Zhou, S., Pan, S., Li, S. S., Zhou, S., Wu, S.. Ye, S., Yun, T., Pei, T., Sun, T., Wang, T., Zeng, W., Zhao, W., Liu, W., Liang, W., Gao, W., Yu, W., Zhang, W., Xiao, W. L., An, W., Liu, X., Wang, X., Chen, X., Nie, X., Cheng, X., Liu, X., Xie, X., Liu, X., Yang, X., Li, X., Su, X., Lin, X., Li, X. Q. Jin, X., Shen, X., Chen, X., Sun, X., Wang. X., Song, X., Zhou, X., Wang,
Goldreich, O., Micali, S., and Wigderson, A. How to play any mental game. In Proceedings of the Nine- teenth Annual ACM Symposium on Theory of Comput- ing, STOC '87, pp. 218-229, New York, NY, USA, 1987. Association for Computing Machinery. ISBN 0897912217, doi: 10. 10.1145/283955.8.86 28420. URL https: 28420.
/ //doi.
Grattafiori, A., Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Vaughan, A., Yang. A., Fan, A., Goyal, A., Hartshorn, A., Yang, A., Mitra, A., Sravankumar, A., Korenev, A., Hinsvark, A., Rao, A., Zhang, A.. Rodriguez, A., Gregerson, A., Spataru, A.,, Roziere, B., Biron, B., Tang, B., Chern, B., Caucheteux, C., Nayak, C., Bi, C., Marra, C., McConnell, C., Keller, C., Touret, C., Wu, C., Wong, C., Ferrer, C. C.. Nikolaidis, C., Allonsius, D., Song, D., Pintz, D., Livshits, D., Wyatt, D., Esiobu, D., Choudhary, D.,. Mahajan, D., Garcia-Olano, D., Perino, D., Hupkes, D.,, Lakomkin, E., AlBadawy, E., Lobanova, E.,, Dinan, E., Smith, E. M. Radenovic, F., Guzmán, F., Zhang, F., Synnaeve, G., Lee, G., Anderson, G. L., Thattai, G., Nail, G., Mialon, G., Pang, G., Cucurell, G., Nguyen, H., Ko- revaar, H., Xu, H., Touvron, H., Zarov, I., Ibarra, I. A., Kloumann, I., Misra, I., Evtimov, I., Zhang, J., Copet, J., Lee, J., Geffert, J., Vranes, J., Park, J., Mahadeokar, J., Shah, J., van der Linde, J., Billock, J., Hong, J., Lee, J.,
X., Shan, X., Li, Y. K. Wang. Y. Q. Wei, Y. x., Zhang, Y. Xu, Y., Li, Y., Zhao, Y., Sun, Y. Wang. Y., Yu, Y., Zhang. Y. Shi, Y., Xiong, Y., He, Y., Piao, Y. Wang, Y. Tan, Y. Ma, Y., Liu, Y., Guo, Y. Ou, Y. Wang, Y., Gong, Y., Zou, Y., He, Y., Xiong, Y., Luo, Y. You, Y., Liu, Y.,
10

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Fu, J., Chi, J., Huang, J., Liu, J., Wang. J., Yu, J., Bitton, J. Spisak, J., Park, J., Rocca, J., Johnstun, J., Saxe, J., Jia, J., Alwala, K. V., Prasad, K., Upasani, K., Plawiak, K., Li, K. Heafield, K., Stone, K., El-Arini, K., Iyer, K., Malik,
Shojanazeri, H., Zou, H., Wang, H., Zha, H., Habeeb, H., Rudolph, H., Suk, H., Aspegren, H., Goldman, H., Zhan, H., Damlaj. I., Molybog, I., Tufanov, I., Leontiadis, I., Veliche, I.-E., Gat, I., Weissman, J., Geboski, J.. Kohli, J., Lam, J., Asher, J., Gaya, J.-B., Marcus, J.. Tang, J., Chan, J., Zhen, J., Reizenstein, J., Teboul, J., Zhong, J.. Jin, J., Yang. J., Cummings, J., Carvill, J., Shepard, J., McPhie, J., Torres, J., Ginsburg, J.. Wang. J.. Wu, K., U, K. H., Saxena, K., Khandelwal, K., Zand, K., Matosich, K., Veeraraghavan, K., Michelena, K., Li, K., Jagadeesh, K., Huang, K., Chawla, K. Huang. K., Chen, I.,, Garg, L.L.,iiee Silva, L., Bell, L.,, Zhang, L.,, Guo, L., Yu, L., Moshkovich, L.,, Wehrstedt, L.,, Khabsa, M., Avalani, M., Bhatt, M., Mankus, M., Hasson, M., Lennie, M., Reso, M., Groshev, M., Naumov, M., Lathi, M., Keneally, M.. Liu, M., Seltzer, M. L.. Valko, M., Restrepo, M., Patel, M. Vyatskov, M., Samvelyan, M., Clark, M., Macey, M., Wang, M., Hermoso, M. J., Metanat, M., Rastegari, M., Bansal, M., Santhanam, N., Parks, N., White, N., Bawa, N., Singhal, N., Egebo, N., Usunier, N., Mehta, N., Laptev, N. P., Dong, N., Cheng, N., Cherngguz, O., Hart, O., Salpekar, O., Kalinli, O., Kent, P., Parekh, P., Saab, P., Balaji, P., Rittner, P., Bontrager, P., Roux, P., Dollar, P., Zvyagina, P., Ratanchandani, P., Yuvraj, P., Liang, Q. Alao, R., Rodriguez, R., Ayub, R., Murthy, R., Nayani, R., Mitra, R., Parthasarathy, R., Li, R., Hogan, R., Battey, R., Wang, R., Howes, R., Rinott, R., Mehta, S., Siby, S., Bondu, S. J., Datta, S., Chugh, S., Hunt, S., Dhillon, S., Sidorov, S., Pan, S., Mahajan, S., Verma, S., Yamamoto, S., Ramaswamy, S., Lindsay, S., Lindsay, S., Feng, S., Lin, S., Zha, S. C., Patil, S., Shankar, S., Zhang, S., Zhang, S., Wang, S., Agarwal, S., Sajuyigbe, S., Chintala, S., Max, S., Chen, S., Kehoe, S., Satter- field, S., Govindaprasad, S., Gupta, S., Deng, S., Cho, S., Virk, S., Subramanian, S., Choudhury, S., Goldman, S., Remez, T., Glaser, T., Best, T., Koehler, T., Robinson, T., Li, T., Zhang, T., Matthews, T., Chou, T., Shaked, T., Vontimitta, V., Ajayi, V., Montanez, V., Mohan, V., Kumar, V. S., Mangla, V., Ionescu, V., Poenaru, V., Mi- hailescu, V. T., Ivanov, V., Li, W., Wang, W., Jiang, W., Bouaziz, W., Constable, W., Tang, X., Wu, X., Wang, X., Wu, X., Gao, X., Kleinman, Y., Chen, Y., Hu, Y., Jia, Y., Qi, Y., Li, Y., Zhang, Y., Zhang, Y., Adi, Y., Nam, Y., Yu, Wang, Zhao, Y., Hao, Y., Qian, Y., Li. Y., He, Y., Rait, Z., Vito, Z., Rosnbrick, Z., Wen, Z., Yang, Z., Zhao, Z., and Ma, Z. The llama 3 herd of models, 2024. URL https: : / arxiv org/ abs / 2400 21783.
K. Chiu, K., Bhalla, K., Lakhotia, K., Rantala- Yeary, L.. van der Maaten, L.. Chen, L., Tan, L., Jenkins, L.. Martin, L.,, Madaan, L., Malo, L., Blecher, L.., Landzaat, L., de Oliveira, L., Muzzi, M., Pasupuleti, M.. Singh, M., Paluri, M., Kardas, M., Tsimpoukelli, M., Oldham, M., Rita, M., Pavlova, M., Kambadur, M., Lewis, M., Si, M., Singh, M. K., Hassan, M., Goyal, N., Torabi, N., Bashlykov, N., Bogoychev, N., Chatterji, N., Zhang, N., Duchenne, O., Çelebi, O., Alrassy, P., Zhang. P., Li, P., Vasie, P. Weng, P. Bhargava, P., Dubal, P., Krishnan, P. Koura, P. S., Xu, P., He, Q. Dong, Q., Srinivasan, R., Ganapathy, R., Calderer, R., Cabral, R. S., Stojnic, R., Raileanu, R., Maheswari, R., Girdhar, R., Patel, R., Sauvestre, R., Polidoro, R., Sumbaly, R., Taylor, R., Silva, R., Hou, R., Wang. R., Hosseini, S., Chennabasappa, S., Singh, S., Bell, S., Kim, S. S., Edunov. S., Nie. S., Narang, S., Raparthy, S., Shen, S., Wan, S., Bhosale, S., Zhang, S., Vandenhende, S., Batra, S., Whitman, S., Sootla, S., Collot, S., Gururangan, S., Borodinsky, S., Herman, T., Fowler, T., Sheasha, T., Georgiou, T., Scialom, T., Speck- bacher, T., Mihaylov, T., Xiao, T., Karn, U., Goswami, V., Gupta, V., Ramanathan, V., Kerkez, V., Gonguet, V., Do, V., Vogeti, V., Albiero, V., Petrovic, V., Chu, W., Xiong, W., Fu, W., Meers, W., Martinet, X., Wang. X., Wang. X., Tan, X. E., Xia, X., Xie, X., Jia, X., Wang, X., Gold- schlag, Y.. Gaur, Y., Babaci, Y., Wen, Y., Song, Y., Zhang, Y., Li, Y. Mao, Y., Coudert, Z. D., Yan, Z., Chen, 7 Papakipos, Z., Singh, A., Srivastava, A., Jain, A., Kelsey, A., Shajnfeld, A., Gangidi, A., Victoria, A., Goldstand, A., Menon, A., Sharma, A., Boesenberg, A., Baevski, A., Feinstein, A., Kallet, A., Sangani, A., Teo, A., Yunus, A., Lupu, A., Alvarado, A., Caples, A., Gu, A., Ho, A., Poul- ton, A., Ryan, A., Ramchandani, A.. Dong, A., Franco, A., Goyal, A., Saraf, A., Chowdhury, A., Gabriel, A., Bharambe, A., Eisenman, A., Yazdan, A., James, B., Maurer, B., Leonhardi, B., Huang, B., Loyd, B., Paola, B. D., Paranjape. B., Liu, B., Wu, B., Ni, B., Hancock, B., Wasti, B., Spence, B., Stojkovic, B., Gamido, B., Montalvo, B., Parker, C., Burton, C., Mejia, C., Liu, C., Wang, C., Kim, C.. Zhou, C., Hu, C. Chu, C.-H., Cai, C., Tindal, C., Feichtenhofer, C., Gao, C., Civin, D., Beaty, D., Kreymer, D., Li, D., Adkins, D., Xu, D.,, Testuggine, D., David, D., Parikh, D., Liskovich, D., Foss, D., Wang. D., Le, D., Holland, D., Dowling, E., Jamil, E., Mont- gomery, E., Presani, E., Hahn, E., Wood, E., Le, E.-T., Brinkman, E., Arcaute, E., Dunbar, E., Smothers, E.. Sun, F. Kreuk, F., Tian, F., Kokkinos, F., Ozgenel, F., Cag- gioni, F., Kanayet, F., Seide, F., Florez, G. M., Schwarz, G. Badeer, G., Swee, G., Halpem, G., Herman, G., Sizov, G., Guangyi, Zhang, Lakshminarayanan. G., Inan, H.,
L., A. L.,
Hao, M., Li, H., Chen, H., Xing, P., Xu, G., and Zhang, T. Iron: Private inference on transformers. In Advances in Neural Information Processing Systems, volume 35, pp. 15718-15731, 2022.
Huang, Z., jie Lu, W., Hong, C., and Ding. J. Cheetah: Lean and fast secure two-party deep neural network inference.

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
In 31st USENIX Security Symposium (USENIX Security 22), pp. 809-826, 2022.
inference for transformers. Cryptology ePrint Archive, Pa- per 2023/1893, 2023. URL SRt.htttps///ppittt iacr/ org/2023/1893,
Kugler, K., Münker, S., Höhmann, J., and Rettinger, A. Invbert: Reconstructing text from contextualized word embeddings by inverting the bert pipeline. 2024. doi: 10.48694/JCLS.35722 URL https:/ /assss//ccssooo article/id/ 3572/.
Papineni, K., Roukos, S., Ward, T., and Zhu, W.-J. Bleu: a method for automatic evaluation of machine transla- tion. In Proceedings of the 40th annual meeting of the Association for Computational Linguisties, pp. 311-318, 2002.
Li, D., Shao, R., Wang, H., Guo, H., Xing, E. P., and Zhang, H. Mpcformer: fast, performant and private transformer inference with mpc, 2023a. URL https: /arxiv. org/abs/ 2211.. 01452.
Penedo, G., Kydllček, H., allal, L. B., Lozhkov, A., Mitchell, M., Raffel, C., Werra, L. V., and Wolf, T. The fineweb datasets: Decanting the web for the finest text data at scale, 2024. URL https: http://wwvv..g.oe.ee...oooo abs/ 17557.
Li, H., Xu, M., and Song, Y. Sentence embedding leaks more information than you expect: Generative embedding inversion attack to recover the whole sentence, 2023b.
Petrov, I., Dimitrov, D. I., Baader, M., Müller, M., and Vechev, M. Dager: Exact gradient inversion for large language models. Advances in Neural Information Pro- cessing Systems, 37:87801-8778 87830, 2024.
URL https: arxiv.iiiiv...... org/ abs 2305. 03010.
Li, Z., Yang, K., Tan, J., jie Lu, W., Wu, H., Wang, X., Yu, Y., Zhao, D., Zheng, Y., Guo, M., and Leng. J. Nimbus: Secure and efficient two-party inference for transform- ers, 2024. URL https: : / /awxiv.vvvvv/////i///a//////aava hbggg/bbs/244 15707.
Owen, :, Yang, A., Yang, B., Zhang, B., Hui, B., Zheng, B., Yu, B., Li, C., Liu, D., Huang, E., Wei, H., Lin, H., Yang, J., Tu, J., Zhang, J., Yang, J., Yang, J., Zhou, J., Lin, J., Dang, K., Lu, K., Bao, K., Yang, K., Yu, L., Li, M., Xue, M., Zhang, P., Zhu, Q. Men, R., Lin, R., Li, T., Tang, T., Xia, T., Ren, X., Ren, X., Fan, Y., Su, Y., Zhang, Y., Wan, Y., Liu, Y., Cui, Z., Zhang, Z., and Qiu, Z. Qwen2.5 technical report, 2025. URL https: //arxiv. .rg. abs/aba//2112 15115.
Lin, C.-Y. ROUGE: package for automatic evalua- tion of summaries. In Text Summarization Branches Out, pp. 74-81, Barcelona, Spain, July 2004. Asso- ciation for Computational Linguistics. URL https: //aclanthii logy- org//04-1010/3
Liu, Y.. Ott, M., Goyal, N., Du, Joshi, M., Chen, D., Levy,
Shanmugavelu, S., Taillefumier, M., Culver, C., Hernandez, O., Coletti, M., and Sedova, A. Impacts of floating point non-associattiitty on reproducibility for hpe and deep learning applications, 2024. URL https://arxx: org abs /
O., Lewis, M., Zettlemoyer, L.,, and Stoyanov, V. Roberta: A robustly optimized bert pretraining approach, 2019. URL https:ttp//oo /ttess///aaxxiie /ttp//axvvvv.///////ee///ae org/ abs/ 11692.
Luo, J., Chen, G., Zhang. Y., Liu, S., Wang. H., Yu, Y., Zhou, X., Qi, Y., and Xu, Z. Centaur: Bridging the impossible trinity of privacy, efficiency, and performance in privacy-preserving transformer inference, 2024. URL ht https: h/pp:://aaa //ariviaaiivv///aa//aa/eaaaaiiva org/ htggabb////ee abs 2412 10652.
Song, C. and Raghunathan, A. Information leakage in embedding models. CCS '20, pp. 377-390, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450370899, doi: 10.1145/ 3372297.3417270. URI. 11 1145/3372297.3411 3417270.
/ttp:://doi.ooo /rtp://///i.../1.....
Moritz, P., Nishihara, R., Wang. S., Tumanov, A., Liaw, R., Liang. E., Elibol, M., Yang, 7.,, Paul, Jordan, M. I., and Stoica, I. Ray: A distributed framework for emerging ai applications, 2018. URL https:://aat /ttp:s/.///xxvvo/g///// abs/ 05889.
Székely, G. J., Rizzo, M. L., and Bakirov, N. K. Measuring and testing dependence by correlation of distances. 2007.
Team, G., Riviere, M., Pathak, S., Sessa, P. G., Hardin, C., Bhupatiraju, S., Hussenot, L., Mesnard, T., Shahriari, B., Ramé, A., Ferret, J., Liu, P., Tafti, P., Friesen, A., Casbon, M., Ramos, S., Kumar, R., Lan, C. L., Jerome, S., Tsit- sulin, A., Vieillard, N., Stanczyk, P., Girgin, S., Momchew, N., Hoffman, M., Thakoor, S., Grill, J.-.., Neyshabur, B., Bachem, O., Walton A., Severyn, A., Parrish, A., Ahmad, A., Hutchison, A., Abdagic, A., Carl, A., Shen, A., Brock, A., Coenen, A., Laforge, A., Paterson, A., Bastian, B., Piot, B., Wu, B., Royal, B., Chen, C., Kumar, C., Perry,
Morris, J. X., Kuleshov, V., Shmatikov, V., and Rush, A. M. Text embeddings reveal (almost) as much text, 2023a.
URL https: / arxiv..vvvvv///ii//eaaaaaaaaavva org/ abs/2310 06816.
Morris, X., Zhao, W., Chiu, T., Shmatikov, V., and
Rush, A. M. Language model inversion, 2023b. URL
https: //arxiv...vv///////////aa//aaa org/ abs
Pang. Q., Zhu, J., Möllering, H., Zheng, W., and Schnei- der, BOLTT: Privacy- presevvie,,,,,ng, accurate and efficient
12

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
C., Welty, C., Choquette-Choo, C. A., Sinopalnikov, D., Weinherger, D., Vijaykumar, D., Rogozińska, D., Her- bison, D., Bandy, E., Wang, E., Noland, E., Moreira, E., Senter, E., Eltyshev, E., Visin, F., Rasskin, G., Wei, G., Cameron, G., Martins, G., Hashemi, H., Klimezak- Plucińska, H., Batra, H., Dhand, H., Nardini, I., Mein, J., Zhou, J., Svensson, J., Stanway, J., Chan, J., Zhou, P., Carrasqueira, J., Iljazi J., Beeker, J., Fernandez. J., van Amersfoort, J., Gordon, J., Lipschultz, J., Newlan, J., yeong Ji. J., Mohamed, K., Badola, K.. Black, K., Milli- can, K. McDonell, K., Nguyen, K., Sodhia, K., Greene, K., Sjoesund, L. L., Usui, L., Sifre, L... Heuermann, L., Lago, L., McNealus, L., Soares, L. B., Kilpatrick, L., Dixon, L., Martins, L.,, Reid, M., Singh, M., Iverson, M.. Görner, M., Velloso, M., Wirth, M., Davidow, M., Miller, M., Rahtz, M., Watson, M., Risdal, M., Kazemi, M.. Moynihan, M., Zhang, M., Kahng, M. Park, M., Rahman, M., Khatwani, M., Dao, N., Bardoliwalla, N., Devanathan, N., Dumai, N., Chauhan, N., Wahltinez, O., Botarda, P., Barnes, P., Barham, P., Michel, P., Jin, P. Georgiev, P., Culliton, P., Kuppala, P., Comanescu, R., Merhej, R., Jana, R., Rokni, R. A., Agarwal, R., Mullins, R., Saadat, S., Carthy, S. M., Cogan, S., Per- rin, S., Amold, S. M. R., Krause, S., Dai, S., Garg, S., Sheth, S., Ronstrom, S., Chan, S., Jordan, T., Yu, T., Eccles, T., Hennigan, T., Kocisky, T., Doshi, T., Jain, V., Yadav, V., Meshram, V., Dharmadhikari, V., Barkley, W., Wei, W. Ye, W., Han, W., Kwon, W., Xu, X., Shen, Z., Gong. Z. Wei, Z., Cotruta, V., Kirk, P., Rao, A., Giang, M. Peran, L.. Warkentin, T., Collins, E., Bar- ral, J., Ghahramani, Z.., Hadsell, R., Sculley, D., Banks, J. Dragan, A., Petrov, S., Vinyals, O., Dean, J., Has- sabis. D., Kavukcuoglu, K., Farabet, C., Buchatskaya, E., Borgeaud, S., Fiedel, N., Joulin, A., Kenealy, K., Dadashi, R., and Andreev, A. Gemma 2: Improving open language models at a practical size, 2024. URL https: /aaxivvvvvv./////////aa///aaaavv org/ abs/ 2408 00118.
White, C., Dooley, S., Roberts, M., Pal, A., Feuer, B., Jain, S., Shwartz-Ziv, R., Jain, N., Saifullah, K., Naidu, S., Hegde, C., LeCun, Y., Goldstein, T., Neiswanger, W., and Goldblum, M. Livebench: A challenging, contamination- free Ilm benchmark, 2024. URL https: /arxiv. azg/abs/2del 1991444466.111
Xu, H., Xiang, L., Ye, H., Yao, D., Chu, P., and Li, B. Permutation equivariance of transformers and its appli- cations, 2024. URL https: /arxiv.rrrxo /abs/
Yao, A. C. Protocols for secure computations. In 23rd Anmual Symposium on Foundations of Computer Science (sfcs 1982), pp. 160-164, 1982. doi: 10.1109/SFCS.198. 38.
Yuan, M., Zhang, L., and Li, X.-Y. Secure transformer in- ference protocol, 2024. URL https:tt////et / abs 2212. 00025.
Zheng, F, Chen, C., Zheng, X., and Zhu, M. Towards secure and practical machine learning via secret sharing and random permutation. Knowledge-Based Systems, 245: 108609, 2022.
Zheng, F., Chen, C., Han, Z., and Zheng, X. Permllm: Pri- vate inference of large language models within 3 seconds under wan, 2024. URL https:/ / /arxivv..vv wiv.ddo org/ /abs/ 2405.18744.
Villa, O., Shararria-Miranda. D., Gurumoorthi, V. Márquez, A., and Krishnamoorthy, S. Effects of floating- point non-associativity on numerical computations massively multithreaded systems. In Proceedings of Cray
User Group Meeting (CUG), volume 3, 2009.
Wan, Z., Cheng, A., Wang, Y., and Wang, L. Information leakage from embedding large language models, 2024. URL http:: / /awxiiiiiiive//.i///eaa//aaaavvv org/ abs/2405. 11916.
Warner, B., Chaffin, A.. Clavié, B., Weller, O., Hallström, O., Taghadouini, S., Gallagher, A., Biswas, R., Ladhak, F. Aarsen, T., Cooper, N., Adams, G., Howard, J., and Poli. I. Smarter, better, faster, longer: A modern bidi- rectional encoder for fast, memory efficient, and long context finetuning and inference, 2024. URL ht tps: //arxiv org/ abs 22122 13663.
13

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
A. Vocab-Matching Attack Optimizations
Although the cost of the attack outlined in Section 4 is linear in V, the size of vocabularies can be quite large in practice. For example, Gemma-2-2BB
has vocabulary size of 256000. Therefore we seek to optimize this by introducing a proposal model. The purpose of the proposal model is to provide a suggested ordering over the vocabulary, rather than iterate through it in an arbitrary order. It does by taking in the token sequence that has been partially decoded so far and producing the next-token logits. We then search through the next-token logits in decreasing order of probability, In practice, we find that this modification reduces the expected number of tokens searched through at each step from V/2 to approximately 100, thus representing a constant factor speedup of more than 1000
Moreover, we implement novel variation of key-value-cachne (K (KV-caching) to reduce the computational time of our attack. Note that the nth stage of the decoding, we are performing a V-batched forward pass on [61, .... - e| over V. where 6 ..,,,..................... Fn-1 are the tokens that we have already decoded. As this forward pass needs to be repeated many times for different but the same Z. we cache the keys and values associated to the T and reuse them across all forward passes. This is different from standard K KV-caching, which stores the keys and values for generation over a single sequence: here, we reuse keys and values across many sequences. In practice, this optimized caching gives a significant speedup in vocab-matching: across 10 evaluation prompts from Feb, the average caching speedup was around 20x, with speedups for all prompts in the range 15-30x.
B. Scalability of Attack
To assess the scalability of our attack with respect to model size, we conducted additional experiments across range of model scales, from billion to 27 billion parameters. Table 8 summarizes the results.
Table 8. Average attack time (in seconds) over 10 decodings for various model sizes.
Model Name
Model Size (Parameters)
Vocabulary Size Average Attack Time (s)
Mlama-3.2-BB-Instuue Gemma-2-2B-IT
IB
128,256
49
2B
256,000
124
-immma--.--B-Inttruue
8B
128,256
69
Gemma-2-27B-- (e =30)
27B
256,000
304
Gemma-2-27B-IT (E = 40)
27B
256,000
124
The attack time remains practical across all evaluated model sizes, typically on the order of minutes for perfect decoding of length 100 prompts. We observe that the computational cost is primarily function of the vocabulary size and the choice of e, rather than the total number of model parameters. Specifically, models with larger vocabularies (e.g.. 256,000 tokens) exhibit proportionally longer attack times compared to models with smaller vocabularies (e.g.. 128,256 tokens), regardless of parameter count. While a poorly chosen e leads to longer runtimes, it does not fundamentally impede the attack. These results demonstrate that the attack scales favorably to larger models, including recent LLMS with tens of billions of parameters.
C. Vocab-Matching Attack Walkthrough and Gap Generalization
Here, we provide an in-depth walkthrough of Algorithm 5 on example prompt, where the adversary receives layer L hidden states hi...., hy E Rd and attempts to recover the N-token input prompt. Then, we walk through variant where the adversary only receives some of these N hidden states but can perform a search over multiple unknown tokens.
Vanilla Attack Suppose a user provides the following prompt to an LLM inference provider hosting Gemma-2 2-2B-IT: "What is currently the most populated city in Spain?". After tokenization, this might be represented as the list [BOS, "What", "is", "currently", "the", "most", "populated", "city", "in", "Spain", "0r EOS], with BOS and EOS denoting special beginning or end of sequence tokens. These 12 tokens have layer 0 embeddings e1, ...... 61 Rd. and these give layer L embeddings fi,..., fu12 Rd. Denoting the stacked decoder layers in Gemma-2-2B-I1 as $1.... Oj. which are all unidirectional and assumed to be deterministic (for now), one sees for ΦLL = ΦL o Φ2 o Φ1 that
(er) = [hi] E Blxd @su(e1, [h,, ha] E 2xd (., = [h,,-.. h12] E 112dd
14

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
We first describe how the attacks works without the e-threshold, i.e. setting 6 < 0, and then describe how affects this.
First, the provider takes the Gemma-2-2B-IT vocabulary V with size V 256000. For each token v E V with embedding e, E IRd, they compute (c,) E IR xxd, and then set ê as some e, which minimizes the LI eтror [| (c,)) - h 111-- Without non-determinism, (e) = h1, so assuming no collisions (no other (e, = h1), we will have é = e1. Next, they compute Φ (c1, E 2xd for each v E V. and set 22 as some ev which minimizes ( ( Cx)2 - h1ll1- Again, without non-determinism and collisions, we have ह2 = E2. This continues until finally, they compute (e), Eu1, e,) E lIxd, and set ēT as some E. which minimizes [ G11, 6v) - h12 la, which will be e12. Now, the provider has true input embeddings [éi...., ē12l = e12]. which can be reversed into the 12 input tokens via the lookup table.
Here, non-determinism and non-collidingness are necessary for provable success of the attack, otherwise we may not have each 2; eq. Furthermore, a total of 12V (around 3 million) forward passes are performed in the worst case, with the exact count depending on the order of iteration in V. As this is expensive, we introduce e e-thresholding: instead of fully iterating through V. we stop once we find an e, with associated LI error S c. However, with a random order of iteration on V, we might not expect significant speedups from this, since the correct token (or other tokens with error S <) might appear late. Thus, we use a proposal model: this conditions each the order of iteration through V on already deciphered tokens, allowing the e-stopping condition to be met earlier. The optimizations from e and the proposal model make the forward pass count much less than 3 million in practice, but potentially at the cost of accuracy: if the proposal model suggests an incorrect token with LI error v 6 earlier than the correct token, the attack may not be able to decode any future tokens.
Generalized Attack Now, we discuss a generalization of the vanilla attack above, shown in Algorithm 3. Here, we discuss how it applies to the example from the last section, with the same notation. Since we do not implement this attack, and consider it primarily as a theoretical threat, we forgo details such as the proposal model and e, and we assume non-determinism. The generalized attack pertains to settings where the provider does not receive all N hidden states. For instance, suppose they only receive h22 ha, .10- Can they still recover all input tokens?
The answer is negative. For instance, none of these 3 hidden states are functions of c11, 612 so one cannot fully* guarantee recovery tokens 11 and 12. Nevertheless, our generalized attack, with sufficiently large computation cost, allows recovery of all tokens that the last hidden state 110 depends on, meaning the first 10 tokens.
First, since the provider does not know h1 they cannot carry out the first step of the vanilla attack to decipher et. However, from h3. they can obtain something stronger: 61, e2, E3. This is because [hı, h2, hs] = de (c1, E2, es), so assuming non-collidingness of the V possible 3-token forward passes { Eug: eug }o Ve, the provider can recover e1, 62, e3 in at most v forward passes. Next, from [h,,..., hs] = @sz(E1..... es) and non-collidingness of the V2 possible 2-token forward passes {Øen, (e1, E2, e3, Eviy Ev.) )ex)) ee, eV,, the provider can recover e4, 6t in at most 1/2 forward passes. Finally, from [hi...., h1o] = @EL(EI..... e1o) e10) and non- con-collidingness of the V possible 5-token forward passes (es1(e1....,, Cs, Eve. ".,.., evv. the provider can recover 66,... Cio in at most V forward passes.
Essentially, the provider has recovered the first 10 tokens in S V3 + V2 + VS5 forward passes, where exponents 3,2,5 5 correspond to gaps between indices of known hidden states. In general, if the provider gets hi...... hi, with 1 < i < ...< <. N, then they can carry out this attack to reverse the first i tokens in V + Viz-1 + +... + Vie-iz-1 forward passes. Although this attack seems quite powerful, the upper bound on forward passes can be quite large, so it is not always practical. For instance, the dominating term in /3 + /22 + / is V 2 1027, so even if only a fraction of the upper bound cost is achieved, it will time out. In general, as k < N = o(V) in practice, the cost bound V + Via-t + +...+ + V - is dominated by the maximum gap term / with = max,(1s41 - iz). Thus, whenever is large enough so that the adversary cannol perform V forward passes, we would expect the attack to time out, even with proposal models and other optimizations. The minimum value of g satisfying this is precisely the vocab-macchig threshold p from Definition 7.2.
Finally, we remark that the the generalized attack requires some stronger assumptions than the vanilla attack to succeed. For instance, in the vanilla attack, we only need non-collidingness across V forward passes at a time. But in our example, we need it across up to 5 forward passes, and in general, we need it across up to V forward passes. One interesting question along this line is to find (if it even exists) the minimum token gap where there are significant collisions at some layer, for various LLMs. With many gaps near this threshold, defenses like quantization and noise could prove more effective than they do in Appendix F. We leave such work as an interesting future direction.
*One could infer these from all previous tokens for certain prompts, so here, we mean without assuming a prior on text. For instance, in the example prompt, "?" and EOS could be inferred from the rest of the prompt. 5 AActualyy, since we are matching only the last row to hy all that needed is non-collidingness of the last row.
15

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Algorithm 3 Generalized Vocabulary-Mattching Attack
input Model M, indices I i < i2 < < i S N, layer hidden states [/,, hig.... high vocabulary V output Nearly decoded token sequence æ = [21, ........ Tog Tigl
Initialize empty sequence ã
2: ig 6
3: for to k 1 do
4: gap 1+11
5: dis t oc
6: best_match + None
7: for v1, U2...., : ligap do
8: 9 M<i v1 122 ... (gap)) {Forward pass up to layer 1}
9:
dist 1g , l [Calculate L1 distance)
10: if dist < min dist then
11:
min_dist +- dist
12:
best_match t-
13: end if
14: end for
15:
end for return
D. Optimal e for Decoding
We report the full set of optimal e thresholds in decoding, for each permutation type below. We observe that generally, the optimal e increases in later layers across all permutation types which may be due to the effect of the reducible and irreducible noise we mention in Section taking up a larger subspace volume propagates to deeper layers. We also observe that Llama tends have much lower values in general.
There is also an interesting layerwise distinction between Gemma and Llama: the optimal for the last hidden layer (26) in Gemma decreases by nearly 2 outside of the permutation case. But the opposite is the case for Llama: it increases by more than 2 at the last layer (32) for all but the no permutation case. Both Gemma and Llama have slightly decreased e at the last layer in the no permutation case. Investigating the reason for decreasing versus increasing e-ball collisions in the last few layers, based on distinctions in the architecture or weights of models like Gemma and Llama, and the type of permutation applied, is an interesting direction for future work on vocab-matching.
Table Optimal thresholds for hidden reversal without permutation, over various Gemma-2-2B-IT and Llama-3. 1---3-1----nttrree layers.
Layer
Gemma
Llama
22.0
0.6
6
70.0
7.1
11
204.0
18.3
16
293.0
29.0
400.0
76.0
26
318.0
156.0
32
150.0
16

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Table 10. Optimal thresholds for hidden state reversal with sequence dimension permutation, various Gemma-2-2B-u. and Llama-
3.1-8B 8--8-B-ttuee layers.
Layer
Gemma
Llama
12.8
1.4
6
72.6
3.3
11
229.0
7.4
16
301.0
7.4
385.0
26.6
26
220.0
29.6
32
105.0
Table Optimal thresholds for hidden reversal with hidden dimension permutation, over various Gemma-2-2B-1 and Llama- 3.1-8B- I--srruttct layers.
Layer
Gemma
Llama
12.5
0.5
6
25.0
3.5
11
45.0
3.7
16
73.0
5.2
118.0
6.3
26
61.0
9.8
32
30.0
Table Optimal thresholds for hidden state reversal with factorized 2D permutation, over various Gemma-2-22 2-2BB-1T and Llama-3, 1.1-B- Instruct layers.
Layer
Gemma
Llama
21.0
0.3
6
26.0
3.0
11
47.0
9.0
16
69.0
9.0
118.0
14.0
26
51.0
14.0
32
45.0
E. Vocab-Matching in Permuted Settings
In Section provided high-level description of how modify the attack in Section 4 to permuted setting. Below, provide exact psuedocode for the attack in sequence dimension. hidden dimension, and factorized 2D permutation settings.
17

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Algorithm 4 Attack on Sequence Dimension Permuted LLM Hidden States
input Model M, permuted layer hidden states h [ha(t), (a(t));n(()))) ho(2)) ... Ma(N)) vocabulary V, proposal model P. L1- threshold
output Decoded token sequence ã = [ T2, ENl
1: Initialize empty sequence < []
2: Initialize set of remaining hidden states H. (ho(1): (a(2)) .n bo(N))
3: for to N do
4: Vordered argsort (P v]() (Get ordered vocabulary from proposal model]
5: min dist 4 o
6: best.match + None
7: for Verdered do
8: 9 6 M<(([ [+) vi]) (Forward pass up to layer 1}
9: for h E do
dist [|g - hilli {Calculate LI ]istance]
11:
if dist < min_dist then
12:
min_dist +- dist
13:
best_maath +
14:
best +
15:
end if dist < c then
3.
18:
Remove h from 7.
break 20: end if
19:
21:
end for
22:
end for
if min_dist 2 c then 2, t best_match
25: Remove best h from H
26: end if
27:
end for
28:
return
18

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Algorithm 5 Attack on Hidden Dimension Permuted LLM Hidden States
input Model M, layer permuted hidden states h [ (h1), T2(h2), ... AN (Nw)),, vocabulary V, proposal model P. LI-threshold
output Decoded token sequence ã
[T1, 32
1: Initialize empty sequence E <-
2: for 1 to N do
3: Vordered f- argsort(P u| [)) {Get ordered vocabulary from proposal model]
4: din - xc
5: best_match + None
6: for Vordered do
7: 9 ( v|) {Forward pass up layer 1}
8: dist |sort(g)- (hr)l (Calculate L1 distance of sorted vectors)
9:
if dist < min dist then
10:
min_dist + dist
11:
best match +
12:
end if
if dist < 6 then
T +v break
15:
16:
end if
17:
end for
18:
if min dist 2 e then
19: 24 f best_
end if
21:
end for
22:
return ac
19

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Algorithm Attack on Factorized-2D Permuted LLM Hidden States
input Model M, permuted layer / hidden states h = [Ta (hr(1)); T2 T2(ho TN (ho(N))), vocabulary V, proposal model
P. L1-thresholdd e
output Decoded token sequence ã- = [T1, , NN]
1: Initialize empty sequence < []]
Initialize set of remaining hidden states H. { (b)())), (2(h)))))))) AN (ha(N))3
3: for to N do
4: Vordered argsort ([ (Get ordered vocabulary from proposal model]
5: min dist 0o
6: best.match + None
7: for Vordered do
8: 9 6 Mei [ vi) (Forward pass up to layer 1}
9: for h E H. do
dist [sort(g) sorl(h)]ll {Caleulate LI distance of sorted vectors)
11:
if dist min_dist then
12:
min dist +- dist best_match +
13:
14:
best h <
15:
end
if dist < c then
3.
18:
Remove h from 7.
break 20: end if
19:
21:
end for
22:
end for
if min_dis, 2 c then
24: T <- best_match
25: Remove best h from H
26: end if
27:
end for
28:
return
20

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
F. Noised & Quantized Hidden State Reversal
As mentioned in Section 6, we now examine the efficacy of our attack on methods of defense that modify the hidden states directly such as by adding noise, or by quantizing the model to lower precision. We investigate the following methods of modification to the permuted LLM hidden states:
Adding diagonal Gaussian noise with mean O and standard deviation o to each hidden dimension in the input embeddings. as proposed in Morris et al. (2023a).
Inserting a randomly generated embedding as a prefix the original sequence. This has the effect of modifying the subsequent hidden states via self-attention
Quantization of the model.
Clearly, with a sufficiently high degree of noise, decoding can be made impossible. However, high noise will also likely disrupt LLM performance. Therefore, the crux of any such defense is based on the delicate balancing act of ensuring security against our attack, whilst still maintaining downstream model performance. We further consider the combination of both permutation as well as the above noising methods.
F.. Experiments
We apply each of the above noising methods on Gemma-2-2B-IT. For diagonal Gaussian noise, we test with = 0.1, 0.01. For the random embedding prefix, we generate the embedding from a Gaussian with means and standard deviations of each hidden dimension set to the average over the token vocabulary V. For quantization, we test with reduction of the model from its original 16-bit to 8-bit and 4-bit, using the bitsandbytes library (BitsAndBytes, 2025). We apply each the above methods to all the permutation types described in Section 5, as well as the unpermuted hidden states. Our choice of dataset, number of evaluation samples, and method of choosing is the same as in Section 4.4. As perfect decoding is less commonly achieved with the addition of noise, now report the ROUGE-L score between the decoded reconstruction and the original prompt to measure decoding quality. We conduct testing again over layers 1, 6, 11, 16, 21 and 26, but report only the highest ROUGE-L, as this can be considered the weakest attack point.
To measure the downstream impact of the noising methods, we utilize LiveBench (White et al., 2024), a benchmark that tests across multiple different components of LLM performance, such as language, reasoning and math. Our results are given in Table 13 below. A full breakdown of the LiveBench scores by category and the ROUGE-L scores by layer of each of the above methods and permutation types is given in Appendix S.
Table 13, ROUGE-L reconstruction scores across 1000 evaluation samples for various noising methods and permutation types Gemma- 2-2B-IT. The 'Downstream Performance' column the normalized score on LiveBench (White et al., 2024), benchmark that tests broad components of LLM performance such as math, reasoning and language. Note that LiveBench scores carry some variability, and so the baseline, Gaussian with standard deviation 0.01, and random embedding prefix methods are all within noise in performance.
Method
Unpermuted
Sequence Perm
Hidden Perm
Factorized-2D
Downstream Performance
Baseline (no noise)
1.00
1.00
1.00
1.00
100.0%
Gaussian, 0.01
0.93
0.07
0.07
0.07
101.4%
Gaussian, 0.1
0.91
0.01
0.01
0.01
5.8%
Random emb. prefix
0.93
0.17
0.19
0.19
102.9%
8-bit quantization
0.89
0.86
0.75
0.73
97.6%
4-bit quantization
0.88
0.84
0.83
0.71
92.2%
We see that unpermuted hidden states are still highly decodeable via our attack under all methods tested - the ROUGE-L scores are above 0.8 in all cases, indicating significant similarity with the original text. Remarkably, even 4-bit quantization is not sufficient to introduce enough collisions to significantly mitigate our attack. We find that the combination of permutation and Gaussian noise with standard deviation 0.01 appears largely secure, with ROUGE-L scores below 0.1, and maintains downstream performance, and thus may represent a potential solution the insecurity of STIP and Centaur. However, this
21

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
result is only necessary for security, and not sufficient; it is possible that extensions of our attack family can succeed even in this setting. We leave further investigation of this to future work.
G. Cascade Scheme Details
Now, we describe the pre-pass, attention-pan pass, and post-pass components of Cascade, which were introduced in Section 7.1. All shard-specific slicing and concatenation operations are initialized in the node setup. Furthermore, we assume that all AttnNodes wait until all CompNodes finish the pre-pass do the attention-pass, and all CompNodes wait until all AttnNodes finish the attention-pass to do the post-pass.
Pre-pass At layer I, each CompNode; starts with the Rh-shedded hidden states ht and applies layer normalization if necessary. Then, it Q, K, V-projects these to get the Rhashedded query, key and value states q k v CompNode; then applies rotary or positional embedding to qdt k RR, using sharded positional embeddings p (the node can generate these upon setup to avoid any communication overhead, since it only depends on its index set Ry), and returns all of qB. RR BR; as described in Algorithm
Attention-pass After the pre-pass, each AumNode,; receives shards n K. R.Sa, R.SS from CompNode,. By con- catenating their rows over S i S a, AutNoodejk obtains go, , vSS,, For example, for q concatenation is in the order in which one concatenates elements of sorted R; n.S over S S a to get sorted Sj. Then, AttnNode, computes a S, = S (T + 5S,,,, where matrix multiplication is per-head and we broadcast Hxv to H. For the post-pass, AutNoodejk also stores row-wise maximums and subtract-mat expsums 5,55, eS,s,, Finally, AttnNode,, takes the row-wise softmax and performs value multiplication get SSS softmax(a" Si )o All of 9,s., S, S,S. are returned, as in Algorithm 8.
e
Post-pass Finally, after the attention-pass, each CompNode; receives m (R.nS,) e (R.nS))). u (R,88)) from each AttnNode jkr which are slices of its attention-pass outputs ms,S, eS,Su, SSSS along the second-to-last dimensions. Then, for each fixed 1 < k < B, CompNode, concatenates the rows of m (R.rss))s, e (R, u (R,nS))) over all S S 8 to obtain m RtS., e ent,S,, St. Next, CompNode; aims to combine these results m ft..s ent.S, u nrS. over S k S B into the R. sharded (pre O-proj) output of attention. Using slicing notation, treating matrix multiplication as per-head, and broadcasting H KV to H, this is
softmax(a)]:4. R,
Σ softmax(a){:.. R4, Selul., Sk] RR Hx
by blocked matrix multiplication. The terms in the summation are not known to Comp.Node,, since slicing here is performed post-softmax. To correct for this, observe that for row vector æ E NR- and any 1 S k S 3, again with slicing notation, expsum(<[[{a)
(eftmax(x)[{SA)
(oftiaxx(((sa) E R|
Σ, expsum x (S:))
Thus, the above summation can be simplified as follows, with @ denoting elementwise multiplication: Σ. expsum(al:; R,, Sul) O (softmax(al::. R2 SAl)ol: Sx))
(oftmax(a)]:... R2, :/u
Ee expsum( al: R4, Sp))
Σ k expsum a R.Sk) @ RR..5 Sx)
Σ. expsum a R....)
Σ. exp(m R,S. @ expsum(a R.S. m R2 O (softmax a R4 S
Σe exp(m @ expsum
R.S. R. R.S))
Σn exp(m R.S.) C S.S. o ou R.S. Σx exp(m R.S. n R(.)) 3 e R..Sc o U.S.
Σ. 5x.5 @ R.S.
expp(mR. n R. ) ② R.S.
with R. [x|[RX being the elementwise maximum of m R.S. [ over all 1 S k I B. The fraction is elementwise divison, and expsum is performed row-wise along the last dimension. This expression is numerically stable because each m R2Sa n Sz < 0 and each e St < 1. Now, each aggregate term in the numerator and denominator summations is known to the CompNode. In essence, the CompNode is performing a weighted average of concatenated AttNooe u results, with the weights also coming from Atmnodes m, e results. To get the final output of attention corresponding to row indices in R, the CompNode finally performs O-projection. Algorithm implements this.
22

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Algorithm/ 7 CompNode; Single Layer Pre-Pass
input R. pdt
output q"d a kR B
1: q +- q-proj(h
2: k" n4 f k proj(h ni)
3: Re & v-proj(h* Ri)
4: q + cotary-pos_emblee Ri
p" R.)
5: k R: &- rotary potary_pos_embll pos_emb(k Ri R)
6: return qu, k k", v
Algorithm 8 AttnNode,j Single Layer Attention-Part -ass
input S v SS,Sa
output SiSk, S, S
1: S* kv
2: S t- kvpeat Sk
3: S + q5:(k (k (1)) + S,Sk
4: m Sn t- row max a S3St
St + exp(a S,5, m Sa) 5: a S
6: S, + row row-sum(a$;3) Se S
7: a S
8: SySe S
9: return S,S S, 8
Algorithm 9 CompNode; Single Layer Post-Pass Pass
input m R.S. RR u. R,S for 1 < k: < 3 output RR.
1: Initialize R. with zeroes and shape like u R.S.
2: Initialize "h with zeroes and shape like e ItSS
3: n, + elementwise_mmee max(mm R.
k=1
4: for k = 1 to do
5: R: t Ri + exp(m R.S, n RiSk) 2 RiSe
6: l oh + exp(m S.S. n R.S. ) o R.So o u R.S.
7: end for
8: R. o Rw.
9: o o-orj(oo
10: return li,
23

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
H. Integrating Cascade with SMPC
In Section 1.2.1, we concluded that Cascade should only be used when it is safe to reveal some number of tokens, but we mentioned that integration with SMPC could alleviate this requirement. Here, we describe how Cascade can be fused with a number of SMPC schemes to improve token security at the expense of computational and communication cost, The idea is to form an L-layered Cascade-SMPC split, where a general SMPC scheme is executed on the first L LLM layers and Cascade is carried out thereafter.
We begin with the SMPC stage for layers < L. Denote the layer O input embeddings as æ, and the layer L hidden states as h. For the first L layers, we execute any SMPC protocol & based on additive secret sharing. Suppose & involves nodes .N,..., ,N, Then & begins by additively splitting æ E ss with each share æs given to N. By decomposing LLM layers into SMPC ff functions or approximations, allows each node N, to compute some additive share h, of the layer L hidden states, such that h- --. h,, A key ingredient of SMPC schemes based on additive secret sharing is computational indistinguiishability; no node gains any information about during the execution of Φ.
Once each N₂ gets hg, we aim to execute Cascade for layers > L in the LLM. We initialize a Cascade sharding scheme {Ra). { and nodes (CompNode,) ). JAttNoodej J. which are some superset of the SMPC nodes Then, for each i, each No sends the slice h. h, R2. :] E Tia Rx to CompNode,, Finally, CompNooe; adds its received sliced shares to get E'= hnt h n.. Since each CompNode, has R,-sharded layer L hidden states, we can execute Cascade for all future layers of the LLM with the Cascade nodes.
In this process, by computational indistiguishability, SMPC nodes gain no information about the input, and thus have no direct token access. Likewise, computational indistiguishability ensures that sliced shares he give CompNode, no additional information about the input. That is, Cascade nodes no longer have direct access tokens: information leakage only comes from the usual exposed shards at layers > L. Thus, even though the execution of & on the first L layers may be more expensive than Cascade, token security is improved. To determine the optimal choice of L, further analysis should be conducted on how information leakage from all exposed Cascade shards varies across layers.
I. Breaking Closed- Permutation-
Schemes
We now describe how our attack in Section 5 can be modified to the closed-weight setting. We break our analysis into three sections: describing the protocols in the closed- weightt setting, explaining how our attack applies in these settings if public embedding layer (lookup table) access is assumed, and showing how to relax the lookup table assumption.
L.1. Closed-Weight Scheme Descriptions
We first give more detail on the original boosed-weigh implementations of the STIP and Centaur schemes from Section 5.1.
STIP In STIP, there are three parties: the model developer Pi, the model server P2 (who carries out inference), and the user Ps. The goal of STIP is to have P2 carry out inference on P3's 's input, protect P1 's private model weights Q from P2 and Ps. and protect P3's private input data from P1 and Ps. This is done with random permutation in the hidden dimension. At initialization, Pi sends random x d permutation matrices n,, Te to the user P3. where d is the token embedding dimension. They also randomly permute each weight matrix or vector in the row and/or column dimensions, to obtaín the altered model weights O'; these are given to the model server P2, who cannot recover é from them. Then during inference. instead of sending their private input data X E IR Nxd. the user encrypts it with permutation æ, i.e. they send Xx. Next, standard transformer forward pass is carried out, but with the weights θ (unknown to P2) replaced by permuted weights O', Finally, the results are sent to the user, who applies permutation Te to obtain the output of the inference. The STIP authors show through orthogonality of permutation matrices that the final output obtained is the same output as vanilla inference.
Centaur Centaur follows the three-party threat model of STIP, and attempts to reconcile two problems. On the model weight privacy side, they aim to prevent exposure of the lookup table to the user. On the user privacy side, they wish avoid exposing certain unpermuted intermediate results. For example, the authors observe that during the computation of attention, the caleulation of QKT at each layer in STIP is insecure due to the Q and K permutations canceling. Therefore the authors apply the cryptographically based technique of additive secret sharing between the developer P, and server P2 at most
'That is, unless there more SMPC nodes than Cascade nodes. But this is usually never the case in practice, because most SMPC schemes based on additive secret sharing involve or 3 parties.
24

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
stages of self-attention, only requiring reconstruction of additive shares (by the developer) during nonlinearities. Although this resolves the previous two concerns, it is still the case that permutations of true layer hidden states are exposed the model developer at nonlinearities.
1.2. Public Embedding Layer
We now describe the implications of the efficacy of our family of attacks for the above schemes, well as PermLLM, assuming the embedding layer of the LLM is publicly known.
PermLLM Recall that PermLLM reveals the permuted hidden states at the non non-linearities to the parties performing inference; and that the hiddens at the softmax and layer-norm non-linearities, in particular, undergo factorized-2DD permutation as they are row-wise operations. Therefore, any party that receives the hidden states at these non-linearities, at any layer, can directly apply the attack described Section 5. We note that PermLLM claims to avoid such permutation security pitfalls by ensuring that the user is one of the parties performing inference, and the only one with access to permuted hidden states. However, such user involvement, while protecting against our attack, makes PermLLM entirely impractical for larger models; the user must still do the bulk of computational cost in matrix multiplications during additive secret sharing.
STIP Recall that in STIP, party P2 carries out inference using a model with permuted weights O', on permutation of the input, Xx, in the hidden dimension. Apart from an additional detail regarding access to the embedding layer, which we expand on below in Appendix I.3, this is analogous to the hidden-dimension permutation setting. A forward pass from the altered transformer model with weights O' up to layer will allow P2 to recover hidden- wwweeniion-pemmmeeeeeee layer hidden states, and apply the attack from Section 5 to recover the input.
Centaur Centaur operates similarly to STIP from the perspective of our attack; at the non-linearities, hidden-dimension- permuted hidden states are revealed to the parties performing inference; and party P2 has access to the permuted weights O'. Therefore, the attack of Section 5 can also be used on Centaur.
L.3. Private Embedding Layer
In the above section, we assumed public lookup table access in order to perform forward passes over the vocabulary in the attack. However, in both STIP and Centaur, the party P2. which performs inference, has access to the entire set of permuted model weights O' except for the token embedding layer, which is only revealed to the user P3. As such, without direct access to the possible token embeddings, the adversary cannot immediately carry out our attack as described in Section 5. Here, we explain how an adversary can still carry out our attack in the private embedding layer setting, by covering two cases: one where the embedding matrix is tied to the LM (language-modeling) head, and one where it is not.
Tied Embedding In many modern LLM families, the embedding matrix is simply the tranpose of the LM head, whose permutation in row and column dimensions) is known to Ps. Therefore, the vocabulary embedding vectors to search over in this case are simply permuted columns of this permuted language-modeling head - and these permutations can be uncovered by matching against the permuted input embedding vectors received from the user at inference.
Explicitly, denoting W as the original TR Vxd embedding matrix, P2 has access to the permuted language- modeling head T.W'" πV R where TV, Ta are V x V,d d permutation matrices. In inference, the user Pa first applies d x d permutation π the input embeddings e....., eN E Fd;; these are rows of W. Therefore, Pa sees permuted embedding vectors T. ... T E Rdd Now, assuming the uniqueness of sorted rows of W, each ,, can be obtained by applying the permutation -1 d on exactly one column of T TT'' .y. Thus P2 can recover न by looking for a sorted match between the columns of TTWTT TV and each ę,,. Once obtained, they can compute गग. ' T TV = n W whose columns are precisely all π r-permuted vocabulary embeddings. With these, because the altered transformer forward pass is carried out on --permuted embeddings, P2 can carry out our attack on any permuted layer hidden states it obtains.
To confirm the plausibility of the above, we examined the embedding matrices of Gemma, Llama and Mistral models and found that it is indeed the case that for these modern LLM families, the rows of W are unique even when sorted.
Non-Tied Embedding Even if the language-modeling modeling head is not the transpose of the embedding matrix, P2 can collect the set of sorted input embeddings over the course of many inference requests. After sufficiently many calls, they can then perform our attack by iterating through this collection of embeddings, permuting them to match the initial permuted input embeddings. The only difference in this case is that P2 must wait for more inference requests in order to carry out the attack, rather than being able to perform it immediately.
25

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
The final step to decoding by the adversary is then mapping the embeddings back into tokens. Note that this is essentially isomorphic to breaking simple substitution cipher. Again, by collecting data over many queries and using simple methods such as frequency analysis and positional information, P2 can learn to decode this into the original tokens; substitution ciphers are in general easily broken given sufficient data.
J. Distance Correlation Does Not Guarantee Permutation Security
We now contextualize statistical arguments on the security permuted hidden states. In particular, we clarify why they do not anticipate our attack. Both Yuan al. (2024) and Luo al. (2024) rely on results from distance correlation theory (Székely et al., 2007) support their arguments about the security of permuted hidden states, and thus claim their schemes are secure. Citing Zheng et al. (2022), both papers quote the following result:
Ex Bx Wageea [Discorr(z, (z, xWAT)] S Enne [Diccorr xWBxBB)
(3)
Discorr the distance correlation function and æ E2 is the input vector chosen from data distribution. Here, the expectations are taken over WA and Wn sampled from standard random normal distributions and sampled uniformly over all d! permutation matrices. This result demonstrates that the expected distance correlation between any vector and the same inmeensionality-preervii
vector with a random permuted between the vector and the same vector with I I-dimensional compressing linear map applied. Therefore, the authors claim that permuted LLM hidden states retain less information about the input embeddings than 1-D projection.
linear map applied is less than the expected distance correlation
In each the following three subsections, we provide a separate reason for why this result cannot be used to make strong guarantees on the security of their schemes.
J.1. Reconstruction From Random 1D Projections Is Feasible
The authors assert that reconstructing inputs after random 1-dimensional linear projection is difficult. However, there no theoretical reason that this should be the case, especially for such projections of LLM hidden states.
We can make this statement precise as follows. Our attack is able to successfully reverse LLM hidden states with Ll-distance matching as demonstrated in Section 4.4. Assuming that two vectors are non-colliding with respect to L1 -1-distance, we can ensure random ID projections of these two vectors are also non-colliding with high probability.
Theorem J.1. Let k > 0. Suppose random weights E Rd are drawn from d-variate spherically symmetric distribution D. Then any y E Rd, we have the absolute difference of w-weighted sums of x and y exceeds the Ll distance between æ and y by factor 2 k, meaning
d
d
Wilh
2 A
o0 -
(4)
1=1
with probability 2 PywD(hal 2 dvd).
Proof. Denote z = x y. Observe that
d
d
d
WaYl
wi
v1)
Σ wi = -lwT> 2/-
Thus, Equation (4) is equivalent to |w= 2 2 k||==||-- Then, from the standard bound ||=||| S V/l|= which can proven by an application of Cauchy-Schware we see that Equation (4) holds whenever
Iw 2| 2 kv d 2112
(5)
We now aim to compute the probability of the above event. Choose a d x d orthogonal matrix Q such that z= Qz E Rd only has a nonzero coordinate L in its first position, i.c 2y = (L, O..., 0). By orthogonality and the fact that D spherically symmetric, we see wy = Qw has distribution D. Furthermore, orthogonal linear transformations are
26

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
length-preserving (by L2 norm), so have |z |Q=ll2 w² w² "=QTQQ Q==== (Qu))((z)) w zq. Hence, Equation (5) becomes
||=||2 [L] In fact, as QJQ I, observe that
mn zyl (.)1( k...vd.
This is equivalent to saying the first coordinate of q has magnitude at least kv dd. But showed wg has distribution D, so the probability that Equation (5) holds is precisely Pa~D((nul 2 kvd). This is therefore lower bound on the probability that Equation (4) holds, since we showed Equation (4) holds whenever Equation (5) does.
Although the above holds over all spherically symmetric distributions, we can obtain an exact bound above by setting D to a multivariate Gaussian. That is, for w = (Wi,.... wa), we i.i.d. sample each w; ~ NN o²). Then the lower bound in the theorem ( 2 kvd)= = (0 (/1) 2 kvd)= sufficiently large or small k, if we sample weights with
22(kvd/o)) where & is the normal CDF. With make this lower bound approach 2 -2)((0 = 1. For instance, for d 4096 in (as is done by Zheng et al. (2022) in the statement of Equation (3)), setting k: 1/64 gives a lower bound of 2 - (1) R 32%, and setting k = 1/32 gives a lower bound of 2 2 ~ 5%. To increase k (for a stronger guarantee of non non-collision of the weighted sums while maintaining the probability lower bound, one must proportionally increase the standard deviation a of the random weights.
-aama-3.1-8B-Instiii
therefore plausible that even with access random 1D linear projections of LLM hidden states, our attack would be successful. Further work should experimentally verify the efficacy of our attack with randomly-weightee sums, in the presence of non-determinism and other practical implementation considerations.
J.2. Distance Correlation Mísaligns With Reconstructibility
To measure privacy leakage, Zheng al. (2022) use expected distance correlation. They justify their choice by noting distance correlation is a well-known statistical metric, which represents structural similarity between datasets and is straightforward to estimate. However, as we now show, distance correlation is not a universal measure of how reversible one random variable is from another. To demonstrate this shortcoming, we introduce the notion of 'ò-reconstruciiiiiity which captures the ability to recover one variable from another variable up to given absolute threshold. We define it as follows. Definition J.2. Let X, Y be random variables. We say that (X, Y) is ó-reconstructible if there exists a function f(Y) such that X - f(Y) < 8 almost always.
This notion of b-reconstructibiiiity is directly tied to privacy in our setting, the non-determinism described in Sec- tion 4 forces us to choose the candidate token within a given absolute threshold. We now show by construction that 6-reconstructiiiliity does not perfectly align with distance correlation: there are 5-reconstructible pairs with a lower distance correlation than non-ô-recon coon--rrconttructiblle pairs.
Theorem J.3. For any 8 >> O, there exist random variables W, X,Y, Z such that Discorr(W, X) > Discorr(Y, Z), the pair (W,X) X) is not 5-reconstructible, and the pair (Y, Z) is 8-reconstructible.
Proof. Define independent random variables W.e ~ (V(0,)) Let Y come from an arbitrary symmetric distribution about zero with support [-8, 6). and construct
X = =W + / p²c, Z = Y
where > >> 0.945. Using standard properties of normal random variables, one can see X ~ N(,, 1), and the correlation between X and W is p. Thus, by Thcorem 7 in Szěkely et al. (2007). which lower bounds distance correlation of standard normals in terms of (Pearson) correlation, we have DisCorr (W, X) > 0.89p > 0.841. Furthermore, by Theorem 1 in Edelmann et al. (2021), which upper bounds the distance correlation of symmetric random variable and its absolute value, have DisCorr(Y (Y, 7) 2-14 < 0.841. Therefore, we have DisCorr( (W, X) DisComr(Y, Z).
Now, we claim that (W, is not ô-reconstructible. To see this, note (W, /N I) by independence, so the linear transformation (W,c) + (W, can be seen to induce the joint distribution
(W,X) N 0, (0 ( :))
27

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
From the standard conditional Gaussian formula, one obtains W x) Nor, / p²). Thus, for any estimator f(X) of Y, we have for each x: that
8
P(W f(X) _ P(W par = = x)= =20 (V1 (V1-p²) p²
- -1=e<
where is a constant dependent on p. 6, and & is the normal CDF. Here, the first inequality holds as WI(X = x) normal distribution: this means P ((W f(X)] Σ 8|X = z), the integral of the corresponding normal PDF over (f(x) - 6, (xx + 6). is upper bounded by its integral over the same-size mean-centered interval (px 6, par + 6), which precisely P (IW - paj I 8|.X- = z). This upper bound follows from the fact that an integral of a zero-centered normal (or generally any unimodal symmetric distribution) over a fixed-size interval is maximal when that interval is zero-centered. which is standard: see the first sentence in Anderson (1955), for example. Finally, taking the expectation of the above bound over X and applying the law of total expectation, we get P(IW - f(X) s 6) S e 1. Since f(X) was chosen arbitrarily, this shows (W, X) is not 6-reconstructible" as required for the claim.
However, (Y, 2) is certainly ò-reconstructible. Because |Y| v 5 almost always, we see f(Z) = 0 always estimates Y within a 8-threshold. Hence, we have our desired counterexample.
Additionally, we observe that Equation (3) involves an expectation of distance correlation over random linear maps and permutations. Therefore, is possible that there are particular linear weights and permutations where the distance correlation with randomly permuted linear projection is smaller than the distance correlation with random ID linear projection. So, Equation (3) cannot be applied to make universal claims about reconstructibility across different models and permutations.
J.3. Transformers Have Token Interdependence
Even taking Equation (3) face value, it is still questionable how it proves security for transformer models. Linear projections are only one component of these architectures: formal security guarantee should incorporate the other modules in transformer, especially self-attention, in which tokens are not processed independently. In particular, this means a valid result should be proved over a distribution over full N x d inputs, rather than a distribution of 1 x d embeddings as in Equation (3). In fact, the unidirectional nature of decoder-only LLMs through self-attention is a key property that enables the pocabulary-matchine attack to succeed (Section 4.2.1). Thus, the distance correlation result, which ignores this dependence, fails to anticipate such an attack.
K. BLEU Scores for CompNode Hidden Reversal
In Section 7. 7.2.2, we computed ROUGE-L scores to evaluate the success of learning-basse reversal attacks on shards h R: received by CompNodes at layer 1. Here, we further assess reconstruction quality at layer using BLEU scores, shown in Table 14. We find similar trend as in Table 5, observing that security improves as c or a increases. Here, for c 2 4, a = 8, we have a BLEU score between 0.1 and 0.2, indicating only marginal reconstructionabiiity: and for 2 4, a 12, the BLEU score lies below 0.1, indicating nearly no reconstructionabiiiyy
Table 14, BLEU scores of text reconstruction from layer I hiddens of Gemma-2-22-IT for different values of a under (c, 8) -hharding..
4
8
a 12
0.537
0.229
0.130
4
0.352
0.133
0.086
8
0.246
0.123
0.083
"In fact, shows something stronger: the optimal estimator's probability of reconstructing W up absolute of & is upper bounded by c. As + O, the value of e actually approaches 26(
0.
28

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
L. CompNode Hidden Reversal Analysis on Layers & Llama
In Section 7.2.2, we described experiments performed on the hidden states of Gemma-2-2B-ITT where a bidirectional- attention model was trained reverse the sharded hidden states into the original text prompt. In Table 5, we showed that the hiddens are largely secure to this attack for suitable choice of c and a.
In this section, we first analyze if this is also true for Llama 3.1 8B-Instruct. We run similar experimental setup described in Section 7.2.2, except we use Ilama hidden representations, and we also use it as the reversal model; this also therefore tests if increasing the reversal model's capacity is a suitable method for improving sharded reconstruction. Due to the computational constraints of training with a larger model, we examine this only for c= 8, a = 8 and c= 8, a = 12. The reconstruction ROUGE-L scores are 0. 1717 and 0. 1 1443 respectively, significantly lower than those obtained with the same parameters for Gemma. We leave to future work the interesting question of whether this implies that Llama representations are inherently more resistant to decoding than Gemma representations.
Next, analyze whether our results hold irrespective of the layer of the model used. We run additional experiments on the hiddens of layers 11 and 21 of Gemma-2-2B-1 IT. Our results are shown in Table 15. We see that there is no substantial difference in ROUGE-L score as the layer changes.
Table 15, ROUGE-L scores of text reconstruction from the hiddens of various layers of Cemma-2-2B-IT for different (c. 8) -sharding setups. We see that the reconstruction quality is similar across layers.
Layer
c= 4
a
1
0.4268
0.2218
11
0.4627
0.2467
21
0.4021
0,2158
M. AttnNode Security
First, we justify our point from Section 7.1 that S and T sharding can be made symmetric at no loss of AttnNode security.
S-T Symmetrization Symmetry relaxation arises from a pairwise coverage requirement of S and T sharding: recall that { and {Ta)k= cover [N]. so all index pairs (z, y) E [N] x [N] lie in some Sj x Ty. Because S and T sharding correspond to query and key/value sharding, this means for all such index pairs (z., v), there is some AttnNode that holds both the zth query row and the yth key row. Observe that a node holding these rows has in the worst case the same information as if they hold the yth query and æth key rows. This is because the query and key matrices are linear projections, which are injective and reversible in the worst-case, of the same hidden states. Therefore, we justify our simplification in Section 7.1 that T sharding may be set equal to S sharding without security loss.
Now, we introduce a technique that allows to improve AttnNode security. Since we have decided to set S and T sharding equal, we would like secure way to select S sharding, given Rt sharding. One option is to set S and R sharding equal, and have each Attn ju: receive the union of query shards from CompNode, and key/value shards from CompNode However, this results in each AttnNode having access to twice as many query/key/value rows as each CompNode. To reduce such leakage to AttNodes and thus improve security, we instead propose a further m-split of AttnNodes as follows.
m-Splitting of AttnNodes To form sharding from R sharding, we can let B = max and partition each Rd into m shards R R.m. Then the S shards are Sm((-1))+== = R4, for all S < a and < x S m. This ensures that pairwise coverage is maintained, but reduces the number of tokens (technically Q, K, V-projections of hidden state rows, but these are reversible to tokens in the worst case at layer 0) that each AttnNode has access to by factor of m. Using this split increases the value of 332 the total number of AttnNodes, by factor of m².
m-Splitting for (c. 8) Sharding We gave a general construction: there remains a degree of freedom in deciding the exact choice of subdividing R2 into the subsets R. Under the assumption that R; follows a (c, -harrrinn scheme, we propose that R contains the elements of sorted R, at indices x, x + 5, ....,, x + (t - 1)6, where N and the split factor is m = c. ca
29

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
For example, suppose that a
2, and N = 18. With a split of m 2, have 3 ma 6. Then,
Ri (1, 7, 13, 14]
R2 [3, 4, 9, 10, 15, 16}
R3 {5, 6, 11, 12, 17, 18)
R1 = {1,7, 13)
R2,1 = {3, 9, 15}
R3.1 {5, 11, 17}
R1, {2,8, 14)
R2.2 = (4, 10, 16)
R3,2 {6. 12, 18)
Sum = [3)7,13}
S121 = (1,3,7,9 7,,,,,,,,,11 15]
S131 = -11,5, 13, 17)
S1112 = [1,2,7,8, 14]
S112 [1.4,7, 10, 16)
S1132 = (1, 7, 12, 13, 18)
S2121 {3,9,15}
S2131 (8, 15,
S2112 (2,3,8,9, 14, 15)
S2122 {3,4,9, 10, 15, 16}
S2132 {3,6,9, 12, 12, 15,
S3131 (5, 11,11,17 17)
S3112 = 52,5, 11,14,11 17]
S3122 11,
S3132 (5,6, 6, 11, 12, 18]
S1212 = {2]8.14)
S1222 42,,,8, 10, 16)
S1232 = {2, 6,8, 12, 14,14, 18)
S2222 = (4, 10, 16)
S2232 = {4, 6, 10, 12, 16, 18) S3232 = (6. 12, 18)
where denote Sizjy = R U R3.y. which is the set of tokens that AttnNodea,5 has access to for m(i x. b= m(j - 1) + y. In other words, Rg above are the sets of token indices that the CompNodes receive, and the Sixjy are the sets of token indices that the AttnNodes receive. Note that some Sizjy entries are not included above (there are 21 listed, but 33 = 36 AttnNodes) because they exactly match a listed entry by Sizjy = Spyin.
Sharding in this way prevents vocab-matching, like in Section 7.2.2. Indeed, as each R has elements that are separated by 8, and each Sinyy combines elements from two different R 's, then there cannot be 3 consecutive elements in Sizjy if > Furthermore, the largest number of missing tokens between two elements of Suzjy (i.c. the largest "gap") is lower bounded by - Therefore, for sufficiently large 6, the vocab-matching attack is infeasible.
Vocab-Matching Attack
Learning- Based Attacks To test security against dearning-based attacks, we conducted experiments with the above scheme for m = 3,,3,44 4), with e= == 8 and a = 8, and the same dataset and setup as in Section 7.2.2. Due to computational constraints, we focus our experiments on Gemma-2-2B-1 on layer 1; we expect similar trends for 1--mn--.--B-IIssteee and other layers. We train single model for all shard possibilities that arise from Sinjy- Experiments are conducted with the same dataset and model setup as described. Our results are shown in Table 16. We see that although m 2 results in a relatively higher ROUGE-L than that for the CompNodes in Table 5, the score for m 4 is very similar; therefore, recommend using 2 4 for security.
Table 16. ROUGE-I. scores for different values of splitting parameter m layer of Gemma-2-22-14 with c 88 a 8. We that the score for m = 4 is similar to that of CompNodes in Table 5 for the same and a.
m
ROUGE-L
2
0.3057
0.2643
4
0.2376
N. Computational Overhead Analysis
In Section 1.3.1, we claimed that Cascade has little overhead in computational costs compared to vanilla inference. We justify this statement in the analysis below, by comparing CompNode and AttnNode steps against the vanilla forward pass. For simplicity of analysis, we assume symmetry of S and T sharding, as justified in Appendix M.
Indeed, most operations performed by CompNodes will treat the (row) token dimension as the batch dimension. In the pre-pass, these are normalization and Q, K, V proojecctoo;; and in the post-pass, these are attention value compilation (most of Algorithm 9), O-projection, residual connection, and the MLP block. Except for attention value compilation, these steps all occur in the vanilla pass, so the CompNodes combined will perform the exact same operations as in vanilla inference: there are no extra computations performed.
The only extra operations thus come from (a) attention value compilation (linear weighting of partial attention outputs) by CompNodes in the post-pass, and (b) Attn floating point computations which do not appear in the vanilla pass, i.e.
30

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
expsums of shards of attention score rows. This is because all other steps of the Cascade self-attention either treat the tokens as batch elements, or involve splitting up matrix multiplication into multiplication of sharded matrices; and the latter is blocked matrix multiplication, which does not inherently change the operations performed.
Now, (a) only involves ~ H| RR d operations for each CompNode,, since it involves a few steps of clementwise summation and multiplication of H x R x d matrices (after broadcasting). Summing this over all 1 1 i S a gives ~ E: H RRldd ddd extra operations. Also, (b) only involves ~ H|S, || operations for each AutnNode,ı because expsum is done over rows of an H |S| X [Sx] shard of attention scores. Summing over all v j. S 3, we see this requires ~ EE || H extra operations in total. This means the total AttnNode computation overhead is (N((+N)
operations.
Importantly, this is cheaper than most computation- steps in standard inference. Compared to the HN2d operations from multiplication of H x N x N attention scores with H x N x d values, this overhead requires ~ N + 3/2 times as many operations. Since is often in the hundreds, we can ensure for large N, say N 2 256, that this ratio is quite small. Furthermore, if N is not large, then the overhead is still limited compared to the ~ H delmed operations from Q, K, V V-projection, since it requires Jams + _N_ times as many operations and dem'' is in the hundreds or thousands. Essentially, the choice of sharding does not significantly affect the total computational overhead, and this overhead is quite modest compared to the computations performed in vanilla forward pass.
_
Zemb
O. Communication Analysis
In Section 7.3.1, we gave the total communication byte and time overheads for performing a inference on a single layer of an LLM with Cascade. Here, we provide a full justification of these equations. Like in Appendix N, we assume symmetry of S and T sharding, so the superscript T in sharded notation is replaced with S.
Recall that in each layer, there are two communication stages: (A) the CompNodes send sharded query, key, value matrices to the AttnNodes between pre-pass and attention- pass,, and (B) the AttnNodes send sharded attention outputs and expsums to the CompNodes between attention- ppsss and past-pass. We operate under the assumption that all CompNodes synchronize before (A) and all AtdnN synchronize before (B), so that we can derive an exact expression for communication cost; this makes our communication cost derivation a worst-case analysis. See Appendix Q for optimizations that can be made if this assumption is relaxed.
For single-layer inference, in stage (A), CompNode; must send each of the R&, rows of the H x |R x d query matrix dh to some AttnNodes. In particular, for a row index E RG it sends the row r. of td to all AttnNooessj. with 1 < k < 3, where j. is the unique index satisfying r E Sj.. That is, Comp.Node, sends each of its [R, rows to exactly B AttnNodes. Since each row contains Hd elements, then CompNode, must send out 8|R Hd d elements from sharded query states. A similar analysis shows CompNode; sends out 2,3) R2 H elements from sharded key and value states, so it sends out a total of B3 R. (d(H + 24) elements. Summing this over all and noting Σ.= [Ra = N gives the total bytes communicated in (A):
CommBytes = BBFd(I + 21lxv) N.
Assuming perfect parallel transport and uniform bandwidth across nodes, i.e. all communication overhead comes from CompNode with the most elements to send (plus latency T), the communication time in stage (A) is
CommTime = + BFd(H + +2Hkv)
max [Ry).
B
Next, in stage (B), each AttnNodejk must send each CompNode; some rows of its partial post-value attention outputs u S, partial attention score row maximums m S, and partial attention score row subtract-max expsums e,SSk, These matrices are of shapes H x |Sy] x d, H x |Sy] x 1, H x |S,| x 1, respectively, and CompNode, receives |R, n n,S,l out of the |S}| rows from each. This means the total number of elements that AttnNode, sends all CompNodes is
(d + H)H
Σ
R R = 22+ |S3).
Since Ejamr 1Sy1 = Ei |S51 = ,N, this means the total number of bytes sent by all f82 AttnNodes is CommBytes = =FF(dd + H) N.
31

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
And, again under the parallel transport and uniform bandwidth assumption, the communication time in (B) is
Comm'Timeg = ++ F(d (0++2) 2)H mmx |Syl-
Combining these costs, we obtain the following total communication byte and time overheads for single layer:
CommBytes = (F(22 + kv + +2H) NN,
CommTime = 2T 3Fd(H 2H max R + F(d + 2
mmx [S
B
B
Finally, we compute the number of communication rounds per layer. Stage (A) has each of the a CompNodes send results to at most 8 AttnNodes, which is at most a,3² rounds. Stage (B) has each of the 3 AttnNodes send results to at most CompNodes, which is at most a.3² rounds. In total, the rounds per layer are bounded above by 2a.32. This can be quite large, but we can guarantee tighter upper bound if our scheme involves (c. sh-sharding for CompNodes with m-splitting of AttnNodes (as in Appendix M). Here, 3 = ma since each of the a shards in { [Rs J==1 is split into m pieces to form j= Each CompNode sends results to m3 AttnNodes, and each AttnNode sends results to 1 CompNode, so there are ma.3 + B = 2,3 rounds. Essentially, the number of rounds scales linearly with the number of AttnNodes.
P. Full CompNode Leakage Analysis
P.I. Necessity of (c, 8)-Sharding
We have examined information leakage from h Rt in Section 7.2.1 and Section 7.2.2, as well as from A S in Section 7.2.3. For a comprehensive security analysis, all that remains is to consider additional leakage from e RR. the information that CompNode; receives from |3 AttnNodes to be-
m StS1 e St u Rt....... ...., m gin the post-pass. Our main theorem shows that considering this leakage, scheme like (c, -'-hhrinn is, in some sense, required to maintain security against vocab-matching: without sufficiently large gaps between consecutive clusters of indices, variant of the attack can be carried out at Layer 0 to reveal additional tokens to node.
R.S,, "is..........,
Theorem P.1. Suppose S and T sharding are equal, and the attention mask s is unidirectional. Furthermore, denote the vocab-matching threshold as p. as defined in Definition 7.2. Then to prevent the vocab-matching atlack, for all E [a)), each gap between clusters of consecutive indices in R2 must have size p.
Proof. Fix i, and denote R4 (ri, in ascending order. Consider any k E [8]. Now, since R..S q (k=Sk)TT + &R, and s is unidirectional, we see that the Ith row of exp(e RrSu )eSS is exactly f(ri, fs E Sp s ml), where we denote
((r = Σ exp
8, ())") vl; s,
sES
This Ith row is known CompNode; because we can write it in terms of known shards:
exp(a R.Sh So = (softmax(a RiS)) O expsum(a" R.Su) ) = u R.Se o RiSa o (.p()..S.))
Thus, for each Tı E R2 and & [8]. we see that CompNode; knows f(ri, {s Sy s<:<sr) At Layer O, since q. k, v are linear projections of token embeddings, we see that f(r, S) only depends on tokens with indices in the set (r) U.S. Since CompNode; knows all tokens with indices R² from h lt. at layer 0, then each f(r, {s E Sk : 8 < r(}) only depends on unknown tokens at indices {s E Ss : < ri) \ RG. Thus, f(rt+1, {s E S₁ : 8 < r)+1)) depends on the same unknown tokens as fri, {s E Sk s < ri)), ) and extra unknown tokens at {s E S : ri < r411. which we call the (k, !)-gap.
If there are < p tokens in (ks, g)-gap for some then following the generalized attack in Appendix C. CompNode; can perform forward pass over all V<p candidate sequences of such unknown tokens in the (k, !)ga and compute candidate values for fri, {s E Sk : < rt) and frr1+,, {s E Sş 3 < r1+1 H), and then select the candidate sequence which allows these quantities to match their known values. This would allow them to recover all tokens in the (k,, 1)-gap Thus, to prevent this vocab- matching attack variant, we need each (kap) to have size 2 or zero. This forces clusters of consecutive indices in R; to have size 2 P gaps between them.
32

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
P.2. Sufficiency of (c, -SShardgg
Now, we provide an argument that only considering Layer shards, when R and S sharding both follow a (c. dh-hardn scheme with sufficiently large c, 8, it is intractable for any CompNode to recover the input.
To do this, we will demonstrate a reduction to variant of the subset sum problem with vectors, which is known to be NP-complete. Our reduction relies on two assumptions (B1), (B2), which we highlight shortly. We begin by fixing i E [a], so that R2 = {ic, + ,,...,,ce ic + c c- 1, ic + 6, ic + 8 5 1, 1,..., ic + + e- e. 1...... .. As we mentioned earlier, Comp.Node; has access to m R,S), e u u
..... m RR,5, e eR u R:S, and n. at Layer O. Knowledge of the latter is equivalent to knowledge of tokens at indices R,, so we consider leakage from the former triples. In fact, at Layer O note each triple m R,S, eR.ss, RR only depends on tokens with indices in R2 U Sg. Since all tokens in R2 are known to CompNode;, then this triple only depends on unknown tokens Se R4. Across all k. these sets are disjoint. Thus, under the following assumption, we can conclude that the reversal problems from the B different triples are independent.
(B1) For any k * k2. CompNode; has independent priors on tokens with indices in Sk, and tokens with indices in Ska.
Thus, we now only need to consider leakage from one triple m RtS., ent.s,, u nt... Explicitly, S₂ = {kc, kc I,..., kc + e - ke + 6, ke + 8 + l..... ke + 8 + -- I..... So, if k = i and S = R; then all these shards are functions only of known tokens at indices R,, and no information is leaked to CompNode,. Thus, without of loss of generality, we now assume & < i, as k > i is similar. From now on, when we say shard depends on tokens, we ignore known tokens.
uR.S. + RRS. @ exp(m...5x). and expsum(a (R.Sk) eRR.s + exp(m R.S.) by definition. Thus, this triple reveals the exact same information as the triple m R,S&, , expsum(a R., exp(a (a RtSk S which have shapes (H. RR). 1). (H. R. 1), H. | d). We concatenate the last two to form b RR.Sk of shape (H, R d + 1). so our original triple is equivalent to m R.S,, b bR.s. Now, note that because S and It are both (c, d-hhardii and the attention mask is unidirectional, the first e out of [R&] rows of a R:Sk will have c elements followed by all -oc, with the nonzero e only depending on tokens indices kc. ..... kc + c-cl- 1, respectively. The next e rows have 2c elements that depend on tokens at indices kc. .... kc + 1, kc + 8, kc + 5 + 1....... kc
Recall that (xp(a
+ c 1, followed by all -co. A similar pattern holds for each next rows. Thus, the R2| rows of R2.SS follow a similar token dependence pattern: the first depend on tokens kc + c - 1, &c + kc + ó + -,..., kc + 8 + - 1, and so on.
kc,..., kc + c 1, the next e depend on tokens
Now, for each position x E [1], we define a list of V possible concatenations [kz,, Ug] E "x2d where kg denotes the æth row across all heads of the layer O query states, and likewise for Uz. Denote this list as As. which is distinct for different values of x due to the effects of positional embeddings; it is indexed in the same order as the vocabulary. For each r E R, and position E [N] with æ S Tú, we denote B as the list of (d + 1)-dimensional vectors whose first entry is exp(g(: r, r] and last d entries are exp (q r, =)4-7) U2, over all [Kg, Uz] E Ag. Note this is also of size V, and is indexed in the same order as the vocabulary. It is simple for node to compute Br, for all r E Rd and x S ri, as they know q(:, r, and can directly compute and iterate through A..
The key point, building on our observation from earlier, is that (d + -)-dimensional rows of b R: are sums of vectors from sets B In particular, there are , such that for all < r S c, the rth row equals Br [i]] + ... + B, Br [(ce) Then, there are ic+1...... ize such that for all c 1 S r S 2c, the rth row equals B, [i1] + ... + B, B..kctt-1li [5c] + B,,kc+a [ + ...... Bo, [22)] A similar pattern holds for 2c 1 S 3c, and so on. The final indices i1, i2, correspond to the positions of input tokens in the vocabulary, for all tokens with indices in Sz.
Therefore, reversal of the input from b R.S alone is at least as difficult as the following problem: given c different sets, each containing V vectors derived from token and position embeddings, select some vector from each set so that they sum to a given vector. This is a variant of the subset sum problem for vectors, which is computationally intractable for large enough V,c. Particularly, since V is in the hundreds of thousands, this likely already intractable for c 2
Finally, we consider additional leakage from m R.S., In the worst case, this reveals at most one of the tokens with indices in 5% for each k maximum of row of a R:Sk reveals most one element of the row, with upper bound constraints placed on the other elements. Given the large number of possibilities for these elements, is unlikely that the upper bound constraints provide much information, which we incorporate in the assumption below. Therefore, leakage from m R;S% is at worst equivalent to effectively reducing the parameter e above by one, since we have one less set to select a vector from. This means if e 2 was secure for reversal from RR.S., we need e > 9 to ensure security for reversal from b R.Sa, m R.S., Note that the variant of the subset sum problem for reversal from b R2SS. together with the inequality constraints from R.S, leakage, form a linear program. So, we have implicitly used the following assumption to claim security.
33

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
(B2) The linear program described above is computationally intractable.
Therefore, assuming choices of 6 which satisfy (B1) and (B2), we have shown Cascade is completely secure for any CompNode only executing Layer O. In practice, these assumptions may not always hold. In fact, learning- based attacks attempt to violate the independence assumption of (B1), through token-infilling between gaps of a (c, -eqquence Furthermore, even as the subset sum problem NP-complete, this does not mean that the particular choice of sets in our setup are not susceptible to, say, an approximation algorithm. To truly test (B2), future work should explicitly enumerate the linear program and test the efficacy of state-of-ther of-the-art solvers on it, perhaps with noken-infilling priors integrated. Nevertheless, the above explicit reduction shows that for large enough c, 6, it is quite likely that (B1) and (B2) nearly hold.
Q. Cost Optimizations
In Section 7.1, we gave a high-level overview of Cascade, and deferred discussions about optimization. Here, we discuss a few cost and communication optimizations, again assuming symmetry of and T sharding.
Caching After a new token is generated in Cascade, the CompNode holding that token will send it back to one of the existing CompNodes, and single-token generation will repeat get the next token. To speed up generation after the first new token, the CompNodes and AttnNodes can store their partial intermediate states, and only the 1 CompNode and | AttnNodes associated with the most recent token will need to participate in the single-token generation: this means K KV-caching naturally extends to Cascade. Formally, suppose n. is the index of the most recently generated token, and it belongs to the hidden shard R& and the query shard Sy. Only CompNode; needs to perform new computation in generating the (n + 1)st token, along with each AttmNode,, for S k S 3: this is because only these AttnNodes require the nih query row. Furthermore, these 1 nodes, having stored intermediate results from previous forward passes, can avoid repeat computation of attention scores and earlier hidden states. Essentially, this results in token-sharded K KVcachhing.
Symmetry Reduction We see that AttnNode,j and AttnNodea, actually have the exact same information in the worst- case: they both have access to indices Sj U.. Thus, at no loss of security, we can combine AttnNode ju. and AttnNodex, into one node, thereby approximately halving the number of AttnNodes required, and reducing communication byte overhead.
Synchronization A key assumption in our communication analysis from Appendix O was that nodes synchronize between stages. That is, AttnNodes wait until they all finish before sending information to CompNodes parallel; and likewise for the CompNodes sending information to AttnNodes. But in practice, depending on the sharding scheme, synchronization is not necessary; and relaxing it can allow some nodes proceed earlier than others. For instance, in a sharding scheme where CompNode; holds only the first k tokens, because the first l logits do not depend at all on tokens k + 1,..., n in unidirectional model, then CompNode, can proceed through all its forward passes without waiting for any information from other nodes. Future work could analyze the tradcoff between such synchronization relaxations, which are not possible with schemes like (c. -sharddgng,, and token security.
R. Cascade Scalability
Here, we demonstrate how Cascade for = 2 without m-splitting scales across different model sizes. The below numbers are obtained over 100 runs. Observe that the runtime grows sublinearly with the model size, suggesting Cascade can also scale well to larger models like Llama-2-70B. Furthermore, we emphasize that our baseline Puma on Llama-2-7B (Dong et al., 2023b) took around 300 seconds for full forward pass, so our approach is over 20x faster.
Model Name
Model Size (Parameters)
Mean Runtime (s)
95% Confidence Interval (s)
Bert-Base
110M
0.7
[0.62,0.74]
Large
335M
1.3
[1.24,1.46]
I.amm- 1-21BBInstrure
1B
2.6
[2.33,2.96]
Llama-2-7B
7B
12.7
[11.07,14.07]
Llama-2-13B
13B
22.7
[20.58,25.99]
Table 17. Model-size-scaling analysis for Cascade. Runtimes and confidence intervals obtained over 100 runs.
34

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
S. Noising method performance
Below, we provide exact (not only the maximum) ROUGE-L scores across layers 1,6, 11, 16, 21, 26, for all methods of noising discussed in Section 6. Table 18, Table 19, Table 20 show these results. We also provide complete breakdown of LiveBench scores per category in Table 22.
Table 18. The ROUGE-L scores of decoded texts with added noise and permutation.
Layer
10-2
= 10
Random Emb
8-bit quantization
4-bit quantization
0.9263
0.9177
0,9309
0.8901
0.8844
6
0.9273
0.3271
0.9340
0.8726
0.8652
11
0.9070
0.0856
0.8170
0.8943
0.8764
16
0.9175
0.0587
0.7552
0.8620
0.8669
21
0,9232
0.0977
0.8247
0,8834
0,8839
26
0.9070
0.0485
0.6257
0.8751
0,8771
Table 19. The ROUGE-L scores decoded texts with added noise and sequence dimension permutation.
Layer
10-2
10-1
Random Emb
8-bit quantization
4-bit quantization
0.0696
0.0000
0.1683
0.8167
0.8157
0.0354
0.0000
0.0418
0.8236
0.8409
0,0278
0.0011
0,0337
0.8479
0,8138
0,0133
0.0023
0,0202
0.8568
0.8116
21
0,0136
0,0051
0,0321
0.8283
0.8250
26
0.0096
0.0096
0.0236
0.8236
0.7956
Table 20. The ROUGE-L scores
scores of decoded texts with added noise and hidden dimension permutation.
Layer
10-2
10-1
Random Emb
8-bit quantization
4-bit quantization
0.0669
0.0000
0.1945
0.7544
0.7497
0.0353
0,0000
0,0359
0.6696
0.6420
11 0.0301
0.0009
0,0300
0.6667
0,8138
16
0.0166
0.0018
0.0144
0.6325
0.8116 16
21
0.0164
0.0036
0.0153
0.5029
0.8250
26
0.0116
0.0101
0.0114
0.3848
0.7956
Table 21. The ROUGE-L scores of decoded texts with added noise and factorized-2D permutation.
Layer
10-2
o = 10
Random Emb
8-bit quantization
4-bit quantization
0,0675
0.0000
0.1919
0.7328
0.7146
6 0,0346
0.0000
0,0361
0,6075
0,5820
11
0.0273
0.0016
0.0297
0.,9166
0,5753
0.0182
0.0027
0.0140
0.3731
0,5701
21 0.0196
0.0044
0.0151
0.3845
0.5568
26
0,0116
0.0120
0.0117
0.3496
0.5564
35

---

Hidden No More: Attacking and Defending Private Third-Party LLM Inference
Table 22. Performance Gemma-2-2B-IT on LiveBench with added noise.
Method
Avg.
Coding
Data Analysis
Instruction Following
Language
Math
Reasoning
Baseline (no noise)
20.7
9.4
26.1
48.9
15.2
13.1
11.3
Gaussian, a 10 2
21.0
11.1
27.4
51.2
13.7
13.4
9.3
Gaussian, = 10-1
1.2
0.0
0.0
6.9
0.4
0.0
0.0
Random emh. prefix
21.3
8.8
27.5
50.1
16.1
13.6
12.0
8-hit quantization
49.2
13.3
13.0
4-bit quantization
19.1
6.5
25.5
50.5
9.5
10.9
12.0
36


Reviews:
[{"review_id": "CCkvJdZst9", "reviewer": "Reviewer_dxey", "summary": "This paper proposes a vocabulary matching attack by exploiting the autoregressive characteristics of the generative model, which can attack the privacy-preserving large language model (LLM) inference framework based on permutation and noise under the assumption that the model parameters are public. At the same time, the author introduces a sharding-based privacy-preserving LLM inference framework Cascade. Cascade uses the token sharding method in the sequence dimension to maintain computational and communication efficiency, while providing security against the proposed attack and previous reversal methods.\n\n## update after rebuttal\nI thank the authors for their detailed responses. After reading the responses and comments from other reviewers, I think this paper requires major revisions regarding the writing, the theoretical security discussion, and the practicality of the multi-party setup. Therefore, I kept my score.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review. We are glad that you found our proposed attack to be effective in the open-weights setting, and that Cascade is novel. We provide responses to some of the points you have raised below.\n\n**W1 + Q1**\n\nA slight extension of our vocab-matching attack can additionally break the schemes of [[1]](https://arxiv.org/abs/2312.00025) and [[2]](https://arxiv.org/abs/2412.10652) in the closed-weights setting. Due to space constraints, please find the details of this in the response to reviewer nbMt.\n\n**W2**\n\nThank you for raising this important point. We have now tested Cascade in a real life WAN network setting with up to 18 different physical machines, and 72 different logical nodes. Our full results for single layer inference on BERT under these settings is shown below:\n\n| **Scheme**                        | **BERT-Base Runtime (s)**        | **BERT-Large Runtime (s)**       |\n|----------------------------------|----------------------------------|----------------------------------|\n| MPCFormer                        | 55.320                           | 141.222                          |\n| PUMA                             | 33.913                           | 73.720                           |\n| Cascade$_{α=2}$         | 0.662 [0.615, 0.738]                  |  1.331 [1.237, 1.464]    |\n| Cascade$_{α=4}$              | 0.588 [0.513, 0.688]             | 1.572 [1.441, 1.734]             |\n| Cascade$_{α=8}$              | 0.742 [0.622, 0.962]             | 1.584 [1.271, 1.965]             |\n| Vanilla Inference                        | 0.091 [0.084, 0.121]             | 0.273 [0.200, 0.993]             |\n\nThe above table shows the average runtimes for Cascade under three choices of $\\alpha$. Larger $\\alpha$ has more nodes. Mean results are given over 100 runs, and a 95% confidence interval is additionally shown in brackets. Values for MPCFormer and Puma are taken from their respective papers.\n\nWe also measured the total communicated bytes in the same setting. Even in the most expensive $\\alpha = 8$ setting, Cascade is $\\sim150\\times$ more efficient in total bytes transferred than the baselines. We conclude that although Cascade will be negatively impacted by poor network conditions, this is true for any SMPC method, and the effect of this will be less deleterious on Cascade than other protocols.\n\n**W3**\n\nWe point to the success of previous projects in decentralized training and inference ([[3]](https://github.com/learning-at-home/hivemind), [[4]](https://arxiv.org/abs/2209.01188), [[5]](https://github.com/PrimeIntellect-ai/prime)) that received contributions from thousands of distinct participants over diverse geographies. As such, we are optimistic that sufficient nodes can be gathered in such a setting in order to provide good security.\n\n**Q2**\n\nIn fact, our security analysis already assumes the worst case of perfect knowledge of the security parameters $c$ and $\\delta$ by the adversary. In practical deployment, the exact sharding scheme may not be known (it can even be changed or randomized continually). We have now made this point more clearly in our local draft and will update it for the camera-ready version.\n\n**Claims 1**\n\nWe agree with your assessment. We have now additionally computed BLEU, F1 and token accuracy, as well as provided reconstruction examples in the local draft.\n\n**Claims 2**\n\nExamining the literature, we did not find existing methods of attack that are not learning-based. Are there particular alternative methods that you believe are applicable to this setting?\n\n**Theoretical Claims**\n\nWe are clear in our submission that Cascade is _not_ a cryptographic scheme (e.g. lines 80, 321, 414). However, we do examine all possible sources of leakage in Appendix J of our submission.\nMoreover, it is our belief that novel defensive methods are of value to the wider research community if they provide sufficient practical defence, even if they do not have formal guarantees that can be proven. We point to the extensive literature on adversarial attacks and defences of neural networks such as [[6]](https://arxiv.org/abs/2406.05927), [[7]](https://arxiv.org/abs/2302.04638), [[8]](https://arxiv.org/abs/2404.09349), none of which have formal guarantees, yet are used commonly in practice due to their efficacy (e.g. see https://robustbench.github.io/).\n\n**Other Comments**\n\nWe agree with all of the readability points you have suggested, and have now included them in our local draft. We will make these changes to the camera-ready version as well.\n\nThank you once again for your thorough review and your insightful comments. If you have any further comments, or if you think our submission can be improved in any way, please let us know. We have made a significant effort to address each of your points and would appreciate it if you would consider raising your score in light of our response. Thank you!", "claims_and_evidence": "Overall, the claims made in this paper are supported by clear and convincing evidence but there are still areas for improvement. In particular,\n\n1. Using only the ROUGE score to measure the security of Cascade is not sufficient. More indicators and evidence are needed to enhance it.\n\n2. Considering only the two attack methods of vocabulary matching and learning is not comprehensive. Experimental results of other attack methods are needed.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are well-aligned with the problem of privacy-preserving LLM inference. They address both the attack and defense aspects comprehensively using appropriate datasets and metrics. Some additional evaluations could further strengthen the conclusions, but overall, the methods and criteria make sense for the problem at hand.", "theoretical_claims": "The security proof in Section 7.2 of the paper is reasonable, but requires more formal treatment, e.g., supplementary cryptographic security analysis.", "experimental_designs_or_analyses": "The experimental designs and analyses in the paper are generally sound and valid, particularly for the vocabulary-matching attack. The evaluation of the Cascade defense mechanism is reasonable but could be strengthened with more direct security assessments and additional experimental validations.", "relation_to_broader_scientific_literature": "The paper makes contributions by both advancing attack methodologies and proposing a practical defense mechanism that addresses demonstrated vulnerabilities, filling gaps in the literature on privacy-preserving LLM inference.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Strengths:**\n\n1. This paper proposes an effective attack method for the privacy-preserving LLM inference framework with random permutation and noise mechanism in the scenario where the model parameters are public.\n\n2. This paper proposes a privacy-preserving LLM inference algorithm based on token sharding, which is new to the area.\n\n**Weaknesses:**\n\n1. The effectiveness of the word list matching attack is mainly reflected in the open-weight setting, which may not represent all deployment scenarios. In closed-weight or more restricted environments, the word list matching attack will fail.\n\n2. The actual deployment of Cascade in a distributed environment may face challenges that are not fully addressed in this paper, such as network reliability and synchronization issues.\n\n3. In terms of security, Cascade cannot achieve theoretical security, and the security strength is related to the number of nodes. Finding a large number of non-colluding nodes in actual deployments seems difficult to achieve.", "other_comments_or_suggestions": "1. The notation becomes quite dense in sections describing Cascade's implementation. A notation table would help readers keep track of variables and sharding parameters.\n\n2. The algorithm description (Algorithm 1) could benefit from a step-by-step example to illustrate how it works in practice.\n\n3. The security analysis (Section 7.2) would be clearer with a diagram showing how token sharding prevents reconstruction attacks.", "questions_for_authors": "1. The attack assumes access to the full model architecture and weights. How would the effectiveness of the attack change in scenarios where the model architecture or weights are not fully known to the adversary? Would the attack still be feasible with partial knowledge?\n\n2. The security analysis assumes certain sharding parameters $(c, \\delta)$. How would the security properties change if an adversary could influence or discover these parameters in a real-world deployment?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TypF9JPWfk", "reviewer": "Reviewer_RAtg", "summary": "This manuscript explores the field of private inference and proposes a vocabulary-matching attack that exploits hidden states to recover the original input of an LLM. The authors highlight that existing permutation-based and noise-based schemes fail to provide sufficient security against such an attack. To address this vulnerability, the manuscript introduces a token-sharded multi-party inference framework that is crypto-free. Experimental results demonstrate its performance improvements over existing cryptographic methods.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review of our submission. We appreciate that you found our paper effectively identifies potential security risks in existing privacy-preserving schemes and that our work is comprehensive in coverage.\n\n**W4**\n\nWe agree with your point. We have now modified the implementation of MPCFormer in Crypten ([[1]](https://arxiv.org/abs/2109.00984)), the SMPC framework they used, to support the use of public weights. Crypten uses Beaver’s triples for matrix multiplication - see Appendix C.1.1 of their paper. For fair comparison, we run on the same setup as Cascade. The table below shows means and 95% confidence intervals over 100 runs:\n\n| **Scheme**                        | **BERT-Base Runtime (s)**        | **BERT-Large Runtime (s)**   |\n|----------------------------------|----------------------------------|----------------------------------|\n| MPCFormer (private weights) | 339.35 [311.58, 396.92] | 1407.26 [1281.12, 1680.31] |\n| MPCFormer (public weights) | 49.40 [45.61, 57.29]     | 143.88 [131.00, 178.64] |\n| Cascade$_{α=2}$         | 0.66 [0.615, 0.738]                  |  1.33 [1.24, 1.46]    |\n| Cascade$_{α=4}$              | 0.59 [0.51, 0.69]             | 1.57 [1.44, 1.73]             |\n| Cascade$_{α=8}$              | 0.74 [0.62, 0.96]             | 1.58 [1.27, 1.97]             |\n\nMPCFormer indeed benefits from a significant speedup by the use of public weights in its protocol - approximately in the range of 7-10x. However, this is still 50-100x slower than Cascade. Moreover we note that the runtime of Cascade does not seem to grow very quickly as a function of $\\alpha$.\n\nWe will also update the result of PUMA. This requires the use of a separate SMPC framework ([[2]](https://github.com/secretflow/spu)). We will have the experimental results for this ready for the final draft of the paper.\n\n**W2**\n\nThank you for bringing to our attention the work of [[3]](https://www.ijcai.org/proceedings/2020/488). It is a stark reminder of the importance of applying care when making claims about the strength of guarantees provided by a scheme – as with the claimed strength of plaintext permuted hidden states, which we demonstrate are easily decodable. We note that the work [3] devises a successful attack against, BAYHENN, claimed the same formal guarantees of privacy as FHE, by misapplication of the LWE assumption. However we are clear in our submission that Cascade is _not_ a cryptographic scheme (e.g. lines 80, 321, 414), and therefore do not claim any formal guarantees against e.g. learning-based attacks.\n\nThe subtract-max variant of softmax works by calculating the maximum $m^x_k$ over each partial row $a^x_k$ of the attention scores given to AttnNodes, where $x$ is the row and $k$ is the column index of the AttnNode – as well as $v^x_k=expsum(a_k^x-m_k^x)$. Thus in standard softmax, CompNode$_i$ gets $o^x_k=softmax(a^x_k)V_k,w^x_k=expsum(a^x_k)$ for all $k$ and rows $x\\in R_i$; and for subtract-max, it gets $o^x_k,m^x_k,v^x_k$.\n\nWe analyze the security of standard softmax in Appendix J, showing that it necessitates large ‘gaps’, which $(c,\\delta)$ sharding satisfies. We can now also show such gaps are _sufficient_ for first layer security – by showing equivalence to the subset-sum problem over vectors. Due to the 5000 character limit, we will include details of this in our next response. We briefly mention here that the subtract-max variant simply adds 1 to the value of $c$ required for security over standard softmax.\n\n**W1**\n\nOur attack is not brute-force; it exploits the properties of attention and a finite dictionary to break permuted hidden states in linear time rather than the exponential time that is assumed in the schemes of [[4]](https://arxiv.org/abs/2405.18744), [[5]](https://arxiv.org/abs/2312.00025) and [[6]](https://arxiv.org/abs/2412.10652). [6] even has a ‘proof’ using a misapplication of distance correlation theory, that is incorrect; we will include further details in the next response. The attack also requires suitable ‘matching functions’ such as sorted-L1-distance (see lines 234-235). Further, practical success of this attack was not obvious a-priori, due to the possibility of many ‘collisions’ of states when matching over all N hidden states - the result of nearly 0 collisions is intriguing in its own right.\n\nMoreover, our proposal for Cascade has not to our knowledge been proposed in prior literature. Even if it is considered intuitive, our extensive experimental coverage of performance and security is, we think, of value to the wider community.\n\n**W3**\n\nThank you for your points. We agree with your suggestions, and have added a notation table and modified the Python-style notation. \n\nThank you once again for your thorough feedback. Even if we do not fully align on the value of our work, we feel that your review was particularly thoughtful and of high value. We look forward to following up with our next response to expand on some of the above points in further detail.", "claims_and_evidence": "Partially.  \nSee Sec. Other Strengths And Weaknesses for detailed comments.", "methods_and_evaluation_criteria": "The proposed methods have limited practicality and potential security concerns.  \nSee Sec. Other Strengths And Weaknesses for detailed comments.", "theoretical_claims": "The proofs have been checked.  \nSee Sec. Other Strengths And Weaknesses for detailed comments.", "experimental_designs_or_analyses": "Experiments were conducted to support the manuscript's performance claims.  \nHowever, some experiments are not properly designed or require further clarification.  \nSee Sec. Other Strengths And Weaknesses for detailed comments.", "relation_to_broader_scientific_literature": "Despite its shortcomings, this manuscript introduces the potential for crypto-free or lightweight crypto-based techniques in developing more efficient privacy-preserving schemes.", "essential_references_not_discussed": "The reviewer recommends that the authors consider [1], as it relates to the security of the proposed method.  \nSee Sec. Other Strengths And Weaknesses for detailed comments.\n[1] Wong, Harry WH, Jack PK Ma, Donald PH Wong, Lucien KL Ng, and Sherman SM Chow. \"Learning Model with Error-Exposing the Hidden Model of BAYHENN.\" In IJCAI, pp. 3529-3535. 2020.", "other_strengths_and_weaknesses": "This paper introduces an attack method against permutation-based and noise-based defenses while proposing a crypto-free scheme to prevent original input reconstruction from intermediate hidden states.\n\n### Strengths:  \n+ The manuscript effectively highlights the performance limitations of crypto-based schemes, which hinder their adoption in real-world applications.  \n+ It identifies potential security risks in existing defense methods.  \n+ The manuscript is comprehensive, and its experimental results are notable.\n\n### Weaknesses:  \nHowever, the reviewer has identified several key issues, which lead to the recommendation to reject the manuscript in its current form.\n\n#### 1. Insufficient Technical Contribution  \n- While the proposed vocab-matching attack successfully breaks existing permutation-based and noise-based defenses, it primarily relies on an approximation-based brute-force search method. The attack strategy minimizes the distance between current and original input states, which is a straightforward extension of existing methods.  \n- The proposed defense method is fundamentally based on splitting the hidden states into multiple segments, ensuring no single entity has access to a complete hidden state. However, the idea is intuitive and lacks sufficient technical depth for publication in ICML.\n\n#### 2. Security Concerns and Practical Limitations  \n- According to [1], exposing intermediate plaintext values (rather than encrypted values) can still lead to privacy leakage. This concern needs to be formally addressed with rigorous proofs.  \n- While the scheme prevents full exposure of consecutive values in the hidden state vector, parties can still access partial consecutive values. The authors must prove whether this partial exposure can aid in reconstructing parts of the user’s input.  \n- Regarding the SoftMax layer, many variants use the formulation:  \n  $\n  e^{x_i - \\max(x)} / \\sum_j e^{x_j - \\max(x)}\n  $\n  Under the current sharding technique, how can the max(x) term be computed without cryptographic operations? If the max operation requires inputs from all parties, would this contradict the manuscript's core design principle, which restricts each party’s access to partial data?  \n- Given these concerns, the current security proof, which claims that search complexity is sufficiently large to ensure security, is inadequate. The authors must provide a more rigorous, formal security proof with numerical analysis, rather than relying on limited empirical experiments with specific attacks and models.\n\n#### 3. Issues in Presentation and Writing Quality  \n- The manuscript’s writing is informal, requiring substantial improvement.  \n- The notation system is inconsistent and incomplete. The authors should provide a comprehensive notation table, rather than defining symbols only when they first appear.  \n- Avoid using coding-style expressions such as `a[:, R_i, T_k]` without explicit explanation. While these may be common in Python-based implementations, they are not standard in academic writing.  \n- The organization of the manuscript needs restructuring. While space constraints exist, too many crucial details, including the construction of the inference protocol, are placed in the appendix. It is recommended to integrate \"Existing Work\" and \"Related Work\" into a single section for better readability.  \n- Clarify the conceptual rationale behind the proposed method.  \n  - Figure 1 should be redesigned to better illustrate the scheme. The current version is difficult to interpret unless the reader has prior knowledge of the method.\n\n#### 4. Experimental Design Issues  \n- While the reviewer acknowledges the significant overhead of MPC-based methods, the manuscript fails to accurately compare the performance gap between crypto-based methods and the proposed approach.  \n- The experimental setup does not properly account for potential optimizations in cryptographic schemes:  \n  - The manuscript assumes model weights are public while user input is private.  \n  - With this assumption, many expensive MPC operations can be replaced by more efficient alternatives, such as:  \n    - Secure multiplication via Homomorphic Encryption (HE)  \n    - Beaver’s triplets for multiplication  \n  - However, the baseline cryptographic methods (PUMA, MPCFormer) were designed for settings where both weights and inputs are private, leading to an unfair comparison.  \n- Unless the authors can explicitly clarify and adjust the baselines to match the same setting, the current performance claims remain questionable.\n\n[1] Wong, Harry WH, Jack PK Ma, Donald PH Wong, Lucien KL Ng, and Sherman SM Chow. \"Learning Model with Error-Exposing the Hidden Model of BAYHENN.\" In IJCAI, pp. 3529-3535. 2020.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "N/A.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hGBl5l5y7U", "reviewer": "Reviewer_7zaS", "summary": "This paper investigates privacy vulnerabilities in third-party LLM inference services, focusing on an open-weight setting. The authors first propose a vocabulary-matching attack, which can recover original user prompts from intermediate hidden states with near-perfect accuracy and remains effective against various permutation-based and noise-based defenses. Then, a multi-party inference scheme that shards hidden states at the token level is proposed, which is robust against the vocabulary-matching attack while maintaining computational and communication efficiency. Experiments on Gemma-2-2B-IT and Llama-3.1-8B-Instruct validate the effectiveness of the attack and defense.\n\n## Update after rebuttal\nSome of my concerns have been addressed, but the paper needs a major revamp in organization and writing. I will keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We are glad that you found our attack effective, and found our experimental work to be extensive. We address your comments below.\n\n**W3**\n\nThank you for raising this important point. We have now run scaling experiments to investigate the effect of model size on the performance of both our attack as well as the defense. We present this below.\n\n| Model Size (num parameters) | Average Attack Time (s) | Vocabulary Size | Model Name              |\n|----------------|--------------------------|------------------|--------------------------|\n| 1B              | 49                     | 128256           | Llama-3.2-1B-Instruct    |\n| 2B              | 124                      | 256000           | Gemma-2-2B-IT            |\n| 8B              | 69                       | 128256           | Llama-3.1-8B-Instruct    |\n| 27B              | 304                       | 256000           | Gemma-2-27B-IT ($\\epsilon = 30$)   |\n| 27B              | 124                       | 256000           | Gemma-2-27B-IT ($\\epsilon = 40$)   |\n\nThis table shows the average attack time over 10 decodings for each of the above models, including the optimizations mentioned in Section 4.2.2 of our submission. As can be seen, the attack time does not significantly increase due to model size, but is primarily a function of the vocabulary size, as well as the parameter $\\epsilon$. Even if $\\epsilon$ is not very well chosen, the attack still takes on the order of minutes for perfect decoding of length 100 prompts.\n\nNext, we present model-size-scaling analysis for Cascade:\n\n| Model Size (num parameters) | Mean Runtime (s) | 95% Confidence Interval (s) |\n|--------------------------|------------------|------------------------------|\n| 110M                    | 0.7            | 0.62 – 0.74              |\n| 335M                    | 1.3            | 1.24 – 1.46              |\n| 1B                      | 2.6            | 2.33 – 2.96              |\n| 7B                      | 12.7           | 11.07 – 14.07            |\n| 13B                     | 22.7           | 20.58 – 25.99            |\n\nThe above numbers are obtained over 100 runs, with $\\alpha = 2$. The models for the 110M and 335M sizes are BERT-base and BERT-Large, and for 1B-13B are Llama 2. We see that the runtime grows sublinearly with the number of parameters. We emphasize that our baseline, [[1]](https://arxiv.org/abs/2307.12533), reported a single forward pass on Llama 7B in approximately 300s, so our approach is ~24x faster. Due to computational constraints, we have not yet run on 70B, but we believe the same scaling law will apply as above. We have now updated our local revision to include the above results, and will include those - as well as the 70B result - in our camera ready version.\n\n**W2**\n\nThank you for mentioning this point. We agree, and we are very clear in our submission that Cascade is not a cryptographic scheme (e.g. lines 80, 321, 414). However, it is our belief that novel defensive methods are of value to the wider research community if they provide sufficient practical defence, even if they do not have formal guarantees that can be proven. We point to the extensive literature on adversarial attacks and defences of neural networks such as [[2]](https://arxiv.org/abs/2406.05927), [[3]](https://arxiv.org/abs/2302.04638), [[4]](https://arxiv.org/abs/2404.09349), none of which have formal guarantees, yet are used commonly in practice due to their efficacy (e.g. see https://robustbench.github.io/).\n\n**Q2**\n\nTo be clear, the use of multiple parties in Cascade is to provide additional security via token-sharding. For feasibility of obtaining enough parties, we point to the success of previous projects in decentralized training and inference ([[5]](https://github.com/learning-at-home/hivemind), [[6]](https://arxiv.org/abs/2209.01188), [[7]](https://github.com/PrimeIntellect-ai/prime)) that received contributions from thousands of distinct participants over diverse geographies. As such, we are optimistic that sufficient nodes can be gathered in such a setting in order to provide good security.\n\n**W1**\n\nWe agree with all the points you have raised here. We have now included references to Figure 1 in the text, reorganized certain sections such as experimental results and related works, and brought some of the Appendix D details regarding Algorithm 2 to the main body. We also thank you for your eagle-eyed spotting of the typo in Algorithm 2, which we have now fixed.\n\nThank you once again for your thoughtful and considered review. We strongly believe in the value of our work both to highlight the security inadequacy of permuted hidden states proposed by several existing protocols, and our proposed solution as a potential method to address it. In light of our addressal of your points above, we would be very grateful if you would consider raising your score. Thank you!", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "This paper is mainly empirical, and not many theoretical results are involved.", "experimental_designs_or_analyses": "Yes. The attack evaluation methodology is well-structured, covering different LLM architectures, defenses, and layers, while the security of Cascade is evaluated through $(c,\\delta)$-sharding experiments.", "relation_to_broader_scientific_literature": "1. The paper builds on prior works on LLM inversion attacks (e.g., Wan et al. (2024), Morris et al. (2023b)), improving attack effectiveness.\n2. It challenges the security assumptions of prior permutation-based defenses (Zheng et al. (2024), Yuan et al. (2024), Luo et al. (2024)).\n3. The proposed defending mechanism presents a new trade-off between privacy and efficiency, improving over SMPC approaches (Li et al., 2023; Dong et al., 2023b).", "essential_references_not_discussed": "The literature review is comprehensive enough in my opinion.", "other_strengths_and_weaknesses": "**Strengths:**\n1. The attack method is simple yet highly effective, even against some commonly considered defenses based on permutation and perturbation.\n2. Extensive experimental results are presented to validate the effectiveness of both the proposed attack and defense.\n\n**Weaknesses:**\n1. The paper is quite difficult to follow, the organization and writing need significant improvement. For example, Figure 1 is presented but not explicitly mentioned in the main text. The key steps of the proposed multi-party inference scheme (i.e., Algorithm 2) should be discussed in detail. \n2. The proposed defending mechanism, Cascade, lacks formal security guarantees and relies on empirical evaluation.\n3. It seems that the attack/defense suffers from high computational and communication overhead, and it is not clear how it works when scaled to larger models (e.g., Llama-3-70B).", "other_comments_or_suggestions": "There is a typo in Algorithm 2, line 10.", "questions_for_authors": "See my comments about weaknesses.\n\nIn addition, it would be helpful if the author could provide some exemplary scenarios in practice, in which a user requires multiple third parties to perform LLM inference as this may incur privacy concerns.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9XEw8YjbJT", "reviewer": "Reviewer_nbMt", "summary": "The paper investigates the vulnerabilities of private inference in large language models (LLMs). Recent organizations rely on third-party LLM inference services when deploying large models locally due to resource constraints. These setups raise significant privacy concerns as user prompts will be disclosed to untrusted parties.\n\nThe authors introduce a white-box reconstruction attack called the vocabulary-matching attack (VMA) that can recover user input text from the hidden states of LLMs with high accuracy. The attack leverages the causal ordering of decoder-only transformers and the finite set of tokens in the vocabulary, iteratively guessing the input token by comparing intermediate hidden states.\n\nTo mitigate the vulnerability, the paper introduces Cascade, a multi-party inference scheme based on token-level sharding. Cascade's key idea is to shard hidden states along the token dimension across multiple parties. In this way, no single party can get enough information to reconstruct the user's input. The authors demonstrate that Cascade effectively defends against both their VMA and the existing attack.\n\n## update after rebuttal\nThank the authors for the detailed response. My concern about the white-box access has been addressed. I will raise my rating for the point.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for recognizing Cascade's effectiveness against the vocab-matching attack (VMA). We address your comments below.\n\n**W1**\n\nRegarding white-box access: we clarify this differs from open-weights. Our setting involves access to permuted hidden states and weights, but not the corresponding input tokens. We emphasize that the security of schemes [[1]](https://arxiv.org/abs/2405.18744), [[2]](https://arxiv.org/abs/2312.00025) and [[3]](https://arxiv.org/abs/2412.10652) all assume the difficulty of this reversal problem for security. To the best of our knowledge, there is no prior work that demonstrates the insecurity of permuted hidden states.\n\nFurthermore, our attack extends to break the schemes of [2, 3] even in the closed-weights setting. These protocols give permuted model weights and embeddings to the party doing inference, where the embeddings are computed locally by the user. Therefore, the VMA may be applied exactly as mentioned in our submission - except that now the embedding matrix is not known, so the first step of inference in the attack seemingly cannot be done.\n\nHowever, it is straightforward to bypass this. The adversary can collect the (finite) set of input embeddings in the vocabulary over repeated inference calls, and can perform the VMA by iterating through this set. Decoding of the embeddings to tokens is also possible even if the tokenizer remains private – this essentially constitutes a simple substitution cipher, where each token in the vocabulary is substituted by its embedding vector. This may be easily broken by collecting data over many queries and using straightforward methods such as frequency analysis and contextual modelling.\n\nTherefore, our result extends to breaking the proposed schemes of [2] and [3] even in the closed-weight setting. We further note that the proposed scheme of [1] explicitly provides the model weights to the party performing inference, and so corresponds to the open-weights setting. \n\n**W2**\n\nWe wish to clarify your statement that: “The authors note that Cascade does not secure individual input embeddings and suggest SMPC for this layer. However, embeddings protected by SMPC provide computational indistinguishability, which means that VMA cannot work in this case.”\n\nFirst we assume that you mean that Cascade cannot work in this case. We clarify that here we mean the using SMPC for the first layer, but then _decoding into plaintext_ after it -- e.g. in additive secret sharing, parties send shards of their additive shares to Cascade nodes, who sum them. In this way, Cascade can be used on the plaintext hiddens from layer 1 onwards. Similarly, SMPC can be applied to any number of initial layers, followed by Cascade on the plaintext token-sharded hiddens for the remaining layers.\n\nRegarding lack of cryptographic guarantees - we are clear in our submission that Cascade is _not_ a cryptographic scheme (e.g. lines 80, 321, 414). However, it is our belief that novel defensive methods are of value to the wider research community if they provide sufficient practical defence, even if they do not have formal guarantees that can be proven. We point to the extensive literature on adversarial attacks and defences of neural networks such as [[4]](https://arxiv.org/abs/2406.05927), [[5]](https://arxiv.org/abs/2302.04638), [[6]](https://arxiv.org/abs/2404.09349), none of which have formal guarantees, yet are used commonly in practice due to their efficacy (e.g. see https://robustbench.github.io/).\n\n**W3**\n\nRegarding the tuning of parameters, we have shown from our experiments that for sufficiently large values of $c$ and $\\delta$, good security is obtained. Although _optimum_ performance may indeed be dependent on the use case, we are confident that users may follow our prescribed heuristics of $c \\geq 8, \\alpha \\geq 12$ and $m \\geq 4$ and achieve good security in the majority of cases.\n\nRegarding the difficulty of obtaining enough nodes, we point to the success of previous projects in decentralized training and inference ([[7]](https://github.com/learning-at-home/hivemind), [[8]](https://arxiv.org/abs/2209.01188), [[9]](https://github.com/PrimeIntellect-ai/prime)) that received contributions from thousands of distinct participants. As such, we are optimistic that sufficient nodes can be gathered in such a setting in order to enable the use of Cascade.\n\n**Conclusion**\n\nThank you again for your considered review. We have responded to your points above, where in some cases - such as the open-weights setting - we have shown extensibility of our method to also cover the closed-weights setting, and we have also clarified some misunderstandings, such as the compatibility of SMPC with Cascade. We strongly believe in the value of our work, both to show the insecurity of existing proposed schemes, as well as to offer a potential solution to their insecurity. We would be grateful if you would consider raising your score in light of the above.", "claims_and_evidence": "Not always.", "methods_and_evaluation_criteria": "Could be improved.", "theoretical_claims": "Not applicable.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "Not sure.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "The paper has natural weaknesses, which may limit its contributions. First, the attack assumes open-weight access, which may be less applicable in proprietary or black-box LLM inference setups. Besides, if white-box LLM access is granted, the adversary can get the input and output directly. There is no need to mount the proposed attack. Therefore, the VMA seems artificial.\n\nSecond, while Cascade prevents the VMA and the existing attack, it does not provide cryptographically rigorous guarantees like SMPC. The authors note that Cascade does not secure individual input embeddings and suggest SMPC for this layer. However, embeddings protected by SMPC provide computational indistinguishability, which means that VMA cannot work in this case.\n\nThird, Cascade's security relies on multi-party setups, which is impractical in typical LLM deployment environments, especially when scale shards are needed. Besides, the choice of sharding parameters (e.g., c and δ) needs careful tuning in practice, which may also challenge Cascade's practical applications.", "other_comments_or_suggestions": "No.", "questions_for_authors": "No.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work proposes an attack against permutation- and noise-based private inference methods when the weights are public. The attack is innovative and can decode model inputs with high accuracy. Based on this, this work then proposes a heuristic defense that shows success empirically in defending against various forms of leakage.

Overall, reviewers had consensus that this work had lacking clarity and that this work should be revised to improve the presentation of the work and its technical details and that the lacking security guarantees for the defence significantly detract from the efficacy of the approach. Some significant improvements were made during the rebuttal including extensions of the attack to closed-weight settings and more thorough experiments (including a fix of the experimental setting for a proper comparison).

Beyond this, reviewers were also concerned with the technical novelty of this work, as the attacks leverage simple observations to compute a brute-force search. Despite this, the AC believes that these insights have led to an effective attack that warrants merit.
Decision: Accept (poster)