REVIEW 4 major objections 6 minor 1 cited by
An Attack to Break Permutation-Based Private Third-Party Inference Schemes for LLMs
T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper attacks permutation-based private LLM inference: a vocabulary-matching decoder recovers original prompts from permuted hidden states with 97.6–99.9% perfect-decoding rates, breaking PermLLM, STIP, and Centaur.
desk verdict Clever and novel attack on raw hidden states; the claimed break of PermLLM/STIP/Centaur is not supported by the experiments, which never test the tensors those schemes actually expose. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the sequential vocabulary-matching decoder. For each step $n$, the adversary performs a batched forward pass over all vocabulary tokens $v$ appended to the already-decoded prefix, obtains candidate hidden states, and selects the $v$ whose last-row hidden state lies within an $\epsilon$ threshold of the target row; unidirectional attention guarantees the $n$-th row depends only on the first $n$ tokens, so errors do not propagate. Hidden-dimension permutations are handled by sorting both vectors before taking the $\ell^1$-distance, mapping any permutation of a vector to the same sorted vector. Sequence permutations are handled by matching against all remaining rows. A proposal model orders the vocabulary by likelihood, reducing the typical search from $V/2$ to about 100 candidates per step, and a custom key-value cache shares prefix computations across the batched candidates.
What would settle it
For a given model and layer, count how many vocabulary tokens have candidate hidden states within the tuned $\epsilon$ of each target hidden-state row; if the average number of matches is well above 1 on realistic prompts, the $M^N$ search-tree growth makes the attack infeasible, so the central claim would fail for that model and layer. A complementary check is to find two distinct prompts whose hidden states at the same position fall within $\epsilon$ of each other, which would make decoding ambiguous.
Extended reading notes
Core claim
The central discovery is that permutation of LLM hidden states offers little obfuscation against an adversary who can compute candidate forward passes. Because decoder-only transformers use unidirectional attention, the hidden state at position n depends only on the first n tokens, so the attacker can enumerate vocabulary tokens prefix by prefix, compare candidate hidden states by $\ell^1$-distance (or sorted $\ell^1$-distance when the hidden dimension is also permuted), and find the true token as the unique near match. This sequential vocabulary-matching attack succeeds at roughly 99% or higher perfect-decoding rates across layers for sequence, hidden-dimension, and factorized-2D permutations on two state-of-the-art models. The paper further shows that the distance-correlation inequality used by STIP and Centaur to argue permutation security does not measure reconstructibility, and that a security proof for transformer hidden states must account for token interdependence, not just distributions of single embeddings.
Load-bearing premise
The attack rests on LLM hidden states being unique fingerprints: at each decoding step only one or very few vocabulary tokens produce a hidden state within the acceptable distance of the observed row, even after shuffling and nondeterministic noise; if many tokens matched, the search would branch exponentially.
Editorial extensions
If this is right
- PermLLM is broken in practice: any party that sees factorized-2D-permuted hidden states at softmax or layer-norm nonlinearities can decode the input with at least 97.6% perfect-decoding accuracy on the tested models.
- STIP and Centaur are broken as well: the party running inference can reverse hidden-dimension-permuted hidden states, and the private embedding layer does not prevent the attack because tied embeddings or collected inference queries give the attacker the needed vocabulary of embedding vectors.
- The theoretical security justification based on permutation-space size and expected distance correlation does not stand: distance correlation can rank a non-reconstructible pair as more private than a reconstructible pair, and the cited inequality ignores the interdependence of tokens in self-attention.
- Adding diagonal Gaussian noise with standard deviation 0.01 to input embeddings, combined with permutation, reduces reconstruction ROUGE-L to about 0.07 while leaving downstream task performance essentially unchanged, suggesting a concrete defensive direction.
- The attack is practical at scale: decoding a length-50 prompt takes about two minutes, and experiments on models from 1B to 27B parameters show runtime depends mainly on vocabulary size and the choice of $\epsilon$, not on parameter count.
Reading between the lines
- A natural extension, which the paper explicitly leaves open, is the fully unrestricted permutation of the whole $N \times d$ hidden-state matrix; if the attack extends there, then any scheme that reveals arbitrarily permuted hidden states at elementwise nonlinearities would also be insecure.
- Because the attack relies on structural properties of decoder-only transformers and on hidden-state non-collision rather than on model-specific weights, it is plausible that it transfers to other decoder-only LLMs beyond the two tested; running the same attack on a different family would test this directly.
- The paper's $\delta$-reconstructibility critique suggests a constructive research program for the field: security proofs for permutation-based private inference should bound the success probability of prefix-conditional vocabulary search, or demonstrate that non-collision fails, instead of citing average distance-correlation bounds.
- The defense result is only a necessary condition, as the paper notes; a stronger test would be to combine Gaussian noise with more sophisticated attacks that exploit the proposal model or use adaptive $\epsilon$ selection, which the authors leave to future work.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proposes an inversion attack against LLM hidden states. The adversary performs batched forward passes over candidate continuations of the partially recovered prefix (ordered by a proposal model) and matches the resulting layer-l hidden state against the target row by L1 distance with a tuned threshold epsilon. The attack is extended to three permutation settings: sequence-dimension permutation (matching against any remaining row), hidden-dimension permutation (sorted-L1 matching), and factorized-2D permutation (both combined). On 1000 held-out FineWeb-Edu prompts (CC-MAIN-2024-10 split, post-dating the models' training cutoffs) with epsilon tuned on a separate 50-prompt set, the authors report perfect decoding on 100% of Gemma-2-2B-IT samples at all tested layers, 99.7-100% on Llama-3.1-8B-Instruct for unpermuted states, and 97.6-99.9% perfect decoding under factorized-2D permutation. The paper argues that these results break three recently proposed private-inference schemes (PermLLM, STIP, Centaur), critiques the distance-correlation-based security proofs of the latter two, and evaluates noise-based defenses (Gaussian noise, random embedding prefixes, quantization).
Significance. If the headline claim is borne out, the paper is significant: it would replace the 'large permutation space implies security' heuristic used by several recent private-inference schemes with a concrete, efficient attack, and it exposes a real gap between distance-correlation bounds and reconstruction hardness. The empirical methodology is a genuine strength: held-out evaluation on a post-training-cutoff data split, epsilon tuned on an independent set, two model families of different scale and architecture, and six layers per model. The attack design is elegant, reduces decoding to linear-in-N cost with a proposal model and cross-sequence KV-caching, and reports practical runtimes (Appendix G). I credit the authors for explicitly stating their assumptions (non-collision, unidirectional attention, forward-pass determinism) and for flagging limitations, including that unrestricted permutations are not attacked and that the noise-defense result is necessary but not sufficient. The distance-correlation critique in Section 7 is a useful conceptual contribution.
major comments (4)
- [§5.3-5.4, §6] Tables 2 evaluates the attack only on raw residual-stream hidden states of an unmodified model with the full token-embedding table available to the attacker, while the quantities actually disclosed by the three protocols are different objects. PermLLM reveals factorized-2D-permuted pre-softmax attention logits and LayerNorm outputs (and elementwise-MLP outputs under a full (Nd)! permutation, which Section 10 concedes the attack does not handle); STIP and Centaur reveal hidden states computed under permuted weights Theta-prime with the embedding table withheld from the model server. Algorithms 3 and 4 compare the raw layer-l candidate states g = M_<=l([x_hat, v]), sorted or not, against the target rows, and never apply the corresponding nonlinearity (softmax, LayerNorm, or the MLP function) before matching. The non-collision property demonstrated in Table 2 is therefore a property of residual-stream geometry, not of the probability-vector or fixed-norm geometries of the revealed tensors, and the Section 6 statement that a party receiving the scheme's tensors can 'directly apply' the attack 'with the very high success rates demonstrated in Section 5.4' is an extrapolation. The manuscript should run the attack end-to-end on the exact tensors each scheme reveals, or explicitly restrict the claim to settings in which raw hidden states are the disclosed quantity; this is the main load-bearing gap for the headline insecurity claim.
- [§6.1, §D] The claimed attack on STIP and Centaur depends critically on recovering the private embedding table, but the recovery argument in Section D is under-specified and untested. The claim that P2 'can recover pi*pi_d^{-1} by looking for a sorted match between the columns of pi_d W^T pi_V and each e_i pi' does not explain how the full d x d permutation is determined: pi*pi_d^{-1} is observed only through its action on the N <= 50 prompt tokens of a single inference request, and the adversary needs its action on all V vocabulary embeddings in order to run candidate forward passes for arbitrary tokens. The non-tied-embedding variant, which collects sorted input embeddings over 'sufficiently many' inference requests and decodes the result as a substitution cipher, comes with no quantitative analysis of the required number of requests, no treatment of whether pi is per-user or per-request, and no experiment. Neither variant is demonstrated end-to-end under the actual protocol conditions (permuted weights Theta-prime, recovered embeddings, nondeterministic forward passes, L1-threshold matching). In the absence of such a demonstration, the claimed compromise of STIP and Centaur rests on an algebraic analogy rather than on evidence.
- [§5.4, Table 2] Table 2's caption says results are shown for 'sequence-dim, hidden-dim, and factorized 2D permutations,' but the table body contains only the Factorized-2D columns. The text's claims that sequence-dimension permutation is decoded 'at essentially a 100% success rate' and that hidden-dimension permutation is 'above 99% for earlier layers' are therefore not backed by any displayed data. Since hidden-dimension permutation is the mechanism relevant to STIP and Centaur, and sequence-dimension permutation is a distinct attack contribution, the missing per-layer columns for both models should be supplied.
- [§3.2, §5.1-5.3] Assumption 2 (non-collision) is the load-bearing premise for the attack's linear-in-N cost, but the paper supports it only through aggregate perfect-decoding rates. I ask for direct evidence: the distribution of the number of vocabulary tokens within the L1 threshold epsilon of each target row (the collision multiplicity M), the frequency with which Algorithms 1-4 fall back to the best-match branch (e.g., Algorithm 1, lines 18-20) rather than accepting an epsilon-match, and the quantitative results of the 'small-scale experiments with prompts exceeding 200 tokens' mentioned in Section 3.6, which are reported without numbers. These statistics would convert the non-collision assumption into a measurable statement and clarify whether the near-perfect rates persist for longer sequences and for models beyond the two tested here.
minor comments (6)
- [Abstract, §1, §6] There are several typos: 'permuation' in the Abstract and in Section 10, 'futher' in the contribution list of Section 1, and 'hiddens' used as a noun throughout Section 6; these should be corrected in a revision.
- [§7.1, Theorem 1] Theorem 1 bounds the probability that a random spherically symmetric projection separates a fixed pair of vectors, but in the actual schemes the projection or permutation is chosen once as part of the protocol rather than drawn fresh for each comparison; the paper appropriately flags that experimental verification for 1D projections is future work, and the surrounding discussion should state explicitly that Theorem 1 does not by itself establish an attack on 1D projections.
- [Table 3] In Table 3, the 'Downstream Performance' column reports normalized LiveBench scores with the baseline set to 100%; the entries above baseline (101.4% and 102.9%) are stated to be within noise, but reporting the raw scores from Appendix H with standard errors would make this comparison more interpretable.
- [§5.4] The claim that non-perfect decodings still show 'significant partial decoding' is not quantified; a ROUGE-L or per-token accuracy figure for the non-perfect cases would allow readers to assess how close those reconstructions actually are.
- [§6] For PermLLM, the paper should state which party holds which weights, since Assumption 4 of Section 3.2 requires the adversary to run candidate forward passes through the model; the current text says only that 'any party that receives the hidden states' can apply the attack, which is not sufficient if that party lacks the weights.
- [Reproducibility] No code, model checkpoints, or prompt-level decoding outputs accompany the manuscript; given that the core evidence is empirical and central to a security claim, releasing the attack implementation and the per-condition epsilon values would materially aid verification.
Circularity Check
No significant circularity: the attack is validated on held-out, post-training-cutoff prompts with epsilon tuned on a separate small set; the theoretical critique of distance correlation is independent of the attack's success.
full rationale
The paper's central claim—that permuted hidden states of LLMs can be nearly perfectly reversed—is supported by an external, held-out empirical benchmark (1000 FineWeb-Edu prompts from the CC-MAIN-2024-10 split, with epsilon tuned on 50 separate FineWeb prompts). The attack algorithm is not fitted to the evaluation data, and the decoding accuracy is measured against ground-truth tokens. The non-collision assumption (Assumption 2) is stated as an empirical premise and is tested by the attack, not derived from the attack by definition; using attack success as evidence for an unproven statistical property is a legitimate empirical consistency check, not a circular derivation. The theoretical sections (Theorems 1 and 2) are independent mathematical arguments that do not presuppose the attack's success. Self-citations are minor and non-load-bearing: the only notable one is LiveBench [White et al., 2024], co-authored by two of the present authors, used in Section 8 to measure downstream performance of proposed defenses; it does not support the attack's correctness or the insecurity claim. The paper also explicitly acknowledges limitations, e.g., it has not demonstrated an attack against unrestricted permutations, and the Gaussian-noise defense result is only necessary, not sufficient. Concerns about whether Table 2's raw residual-stream states match the tensors revealed by PermLLM/STIP/Centaur are validity/correctness issues, not circularity. Overall, the derivation chain is self-contained against external benchmarks, and no step reduces by construction to its own inputs.
Assumptions & free parameters
free parameters (1)
- epsilon (L1 threshold) =
Layer-dependent values in Appendix B, e.g. 22.0 for Gemma layer 1 unpermuted and 400.0 for Gemma layer 21 unpermuted
assumptions (5)
- domain assumption LLM hidden states are non-colliding under L1 and sorted-L1 matching, including across positions and in the presence of nondeterminism
- domain assumption Decoder-only LLMs have unidirectional attention, so the hidden state at position n depends only on tokens up to n
- domain assumption The attacker can run the target model's forward pass up to layer l over candidate prefixes
- standard math Known distance-correlation results used in Theorem 2 (Székely et al. 2007, Edelmann et al. 2021) are correct
- domain assumption Sorted rows of embedding matrices are unique for modern LLM families
Cite this review
Pith. "Pith review of An Attack to Break Permutation-Based Private Third-Party Inference Schemes for LLMs." pith.science (2026). https://pith.science/paper/CM4DHTX4
@misc{pith2026250518332,
author = {Pith},
title = {Pith review of: An Attack to Break Permutation-Based Private Third-Party Inference Schemes for LLMs},
year = {2026},
howpublished = {\url{https://pith.science/paper/CM4DHTX4}},
note = {Machine review of arXiv:2505.18332}
}
read the original abstract
Recent advances in Large Language Models (LLMs) have led to the widespread adoption of third-party inference services, raising critical privacy concerns. Existing methods of performing private third-party inference, such as Secure Multiparty Computation (SMPC), often rely on cryptographic methods. However, these methods are thousands of times slower than standard unencrypted inference, and fail to scale to large modern LLMs. Therefore, recent lines of work have explored the replacement of expensive encrypted nonlinear computations in SMPC with statistical obfuscation methods - in particular, revealing permuted hidden states to the third parties, with accompanying strong claims of the difficulty of reversal into the unpermuted states. In this work, we begin by introducing a novel reconstruction technique that can recover original prompts from hidden states with nearly perfect accuracy across multiple state-of-the-art LLMs. We then show that extensions of our attack are nearly perfectly effective in reversing permuted hidden states of LLMs, demonstrating the insecurity of three recently proposed privacy schemes. We further dissect the shortcomings of prior theoretical `proofs' of permuation security which allow our attack to succeed. Our findings highlight the importance of rigorous security analysis in privacy-preserving LLM inference.
Figures
Forward citations
Cited by 1 Pith paper
-
Cascade: Token-Sharded Private LLM Inference
Cascade performs LLM inference by sharding the token sequence across non-colluding nodes, claiming resistance to vocabulary-matching and learning-based reconstruction attacks while being orders of magnitude faster than SMPC.
Reference graph
Works this paper leans on
-
[3]
Dominic Edelmann, Tamás F Móri, and Gábor J Székely
URLhttps://arxiv.org/abs/2307.12533. Dominic Edelmann, Tamás F Móri, and Gábor J Székely. On relationships between the pearson and the distance correlation coefficients.Statistics & probability letters, 169:108960,
-
[6]
Kai Kugler, Simon Münker, Johannes Höhmann, and Achim Rettinger
doi: 10.1016/j.lindif.2023.102274. Kai Kugler, Simon Münker, Johannes Höhmann, and Achim Rettinger. Invbert: Reconstructing text from contextualized word embeddings by inverting the bert pipeline
arXiv 2023
-
[7]
URL https://arxiv.org/abs/2305.03010. Zhengyi Li, Kang Yang, Jin Tan, Wen jie Lu, Haoqi Wu, Xiao Wang, Yu Yu, Derun Zhao, Yancheng Zheng, Minyi Guo, and Jingwen Leng. Nimbus: Secure and efficient two-party inference for transformers,
-
[8]
URLhttps://arxiv.org/abs/2411.15707. Jinglong Luo, Guanzhong Chen, Yehong Zhang, Shiyu Liu, Hui Wang, Yue Yu, Xun Zhou, Yuan Qi, and Zenglin Xu. Centaur: Bridging the impossible trinity of privacy, efficiency, and performance in privacy-preserving transformer inference,
-
[9]
URLhttps://arxiv.org/abs/2412.10652. John X. Morris, V olodymyr Kuleshov, Vitaly Shmatikov, and Alexander M. Rush. Text embeddings reveal (almost) as much as text, 2023a. URLhttps://arxiv.org/abs/2310.06816. John X. Morris, Wenting Zhao, Justin T. Chiu, Vitaly Shmatikov, and Alexander M. Rush. Language model inversion, 2023b. URLhttps://arxiv.org/abs/2311...
-
[10]
URLhttps://eprint.iacr.org/2023/1893. Guilherme Penedo, Hynek Kydlíˇcek, Loubna Ben allal, Anton Lozhkov, Margaret Mitchell, Colin Raffel, Leandro V on Werra, and Thomas Wolf. The fineweb datasets: Decanting the web for the finest text data at scale,
work page 2023
-
[11]
15 Ivo Petrov, Dimitar I Dimitrov, Maximilian Baader, Mark Müller, and Martin Vechev
URLhttps://arxiv.org/abs/2406.17557. 15 Ivo Petrov, Dimitar I Dimitrov, Maximilian Baader, Mark Müller, and Martin Vechev. Dager: Exact gradient inversion for large language models.Advances in Neural Information Processing Systems, 37:87801–87830,
-
[12]
Congzheng Song and Ananth Raghunathan
URLhttps://arxiv.org/abs/2408.05148. Congzheng Song and Ananth Raghunathan. Information leakage in embedding models. CCS ’20, page 377–390, New York, NY , USA,
Show all 23 references
-
[14]
Arun James Thirunavukarasu, Darren Shu Jeng Ting, Kabilan Elangovan, Laura Gutierrez, Ting Fang Tan, and Daniel Shu Wei Ting
URL https://arxiv.org/abs/2408.00118. Arun James Thirunavukarasu, Darren Shu Jeng Ting, Kabilan Elangovan, Laura Gutierrez, Ting Fang Tan, and Daniel Shu Wei Ting. Large language models in medicine.Nature Medicine, 29:1930– 1940,
1930 arXiv
-
[15]
URLhttps://www.nature.com/articles/ s41591-023-02459-w
doi: 10.1038/s41591-023-02459-w. URLhttps://www.nature.com/articles/ s41591-023-02459-w. Review Article, Published: 17 July
-
[16]
URLhttps://arxiv.org/abs/2405.11916. Colin White, Samuel Dooley, Manley Roberts, Arka Pal, Ben Feuer, Siddhartha Jain, Ravid Shwartz- Ziv, Neel Jain, Khalid Saifullah, Siddartha Naidu, Chinmay Hegde, Yann LeCun, Tom Goldstein, Willie Neiswanger, and Micah Goldblum. Livebench: ...
-
[17]
Hengyuan Xu, Liyao Xiang, Hangyu Ye, Dixi Yao, Pengzhi Chu, and Baochun Li
URLhttps://arxiv.org/abs/2406.19314. Hengyuan Xu, Liyao Xiang, Hangyu Ye, Dixi Yao, Pengzhi Chu, and Baochun Li. Permutation equivariance of transformers and its applications,
-
[18]
URL https://arxiv.org/abs/2304. 07735. Andrew C. Yao. Protocols for secure computations. In23rd Annual Symposium on F oundations of Computer Science (sfcs 1982), pages 160–164,
1982
-
[20]
Fei Zheng, Chaochao Chen, Xiaolin Zheng, and Mingjie Zhu
URL https://arxiv.org/abs/2312.00025. Fei Zheng, Chaochao Chen, Xiaolin Zheng, and Mingjie Zhu. Towards secure and practical machine learning via secret sharing and random permutation.Knowledge-Based Systems, 245:108609,
-
[21]
A Attack Optimizations Proposal ModelAlthough the cost of the attack outlined in Section 3 is linear in V , the size of vocabularies can be quite large in practice
URLhttps://arxiv.org/abs/2304.04675. A Attack Optimizations Proposal ModelAlthough the cost of the attack outlined in Section 3 is linear in V , the size of vocabularies can be quite large in practice. For example, Gemma-2-2B-IT has a vocabulary size of 256000. Therefore we se...
2024 arXiv
-
[22]
Theorem 2.F or any δ >0, there exist random variables W, X, Y, Zsuch that Discorr(W, X)> Discorr(Y, Z), the pair(W, X)is notδ-reconstructible, and the pair(Y, Z)isδ-reconstructible
The idea is to construct aδ-reconstructible pair with low distance correlation by using absolute values of symmetric variables, and then form a non-δ-reconstructible pair with high distance correlation by using highly correlated normal variables. Theorem 2.F or any δ >0, there...
2007
-
[23]
25 Table 10: The ROUGE scores of decoded texts with added noise and sequence dimension permutation. Layerσ= 10 −2 σ= 10 −1 Random Emb 8-bit quantization 4-bit quantization 1 0.0696 0.0000 0.1683 0.8167 0.8157 6 0.0354 0.0000 0.0418 0.8236 0.8409 11 0.0278 0.0011 0.0337 0.8479 ...
1945
-
[1982]
Mu Yuan, Lan Zhang, and Xiang-Yang Li
doi: 10.1109/SFCS.1982.38. Mu Yuan, Lan Zhang, and Xiang-Yang Li. Secure transformer inference protocol,
1982 doi
-
[1987]
ISBN 0897912217
Association for Computing Machinery. ISBN 0897912217. doi: 10.1145/28395.28420. URLhttps://doi.org/10.1145/28395.28420. Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan...
-
[2020]
ISBN 9781450370899
Association for Computing Machinery. ISBN 9781450370899. doi: 10.1145/3372297.3417270. URL https://doi.org/10.1145/3372297. 3417270. Gábor J Székely, Maria L Rizzo, and Nail K Bakirov. Measuring and testing dependence by correlation of distances
-
[2023]
Theodore W Anderson
doi: 10.1109/EuroSP57164.2023.00031. Theodore W Anderson. The integral of a symmetric unimodal function over a symmetric convex set and some probability inequalities.Proceedings of the American Mathematical Society, 6(2): 170–176,
2023
-
[2024]
Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang
URLhttps://arxiv.org/abs/2407.21783. Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang. Iron: Private inference on transformers. InAdvances in Neural Information Processing Systems, volume 35, pages 15718–15731,
-
[2025]
Ye Dong, Wen jie Lu, Yancheng Zheng, Haoqi Wu, Derun Zhao, Jin Tan, Zhicong Huang, Cheng Hong, Tao Wei, and Wenguang Chen
Accessed: 2025-01-28. Ye Dong, Wen jie Lu, Yancheng Zheng, Haoqi Wu, Derun Zhao, Jin Tan, Zhicong Huang, Cheng Hong, Tao Wei, and Wenguang Chen. Puma: Secure inference of llama-7b in five minutes,
2025
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.