An Efficient Private GPT Never Autoregressively Decodes
Authors: Zhengyi Li
Yue Guan
Kang Yang
Yu Feng
Ning Liu
Yu Yu
Jingwen Leng
Minyi Guo
Venue: ICML 2025 poster (2025)
Keywords: privacy-preserving machine learning
GPT
homomorphic encryption
multi-party computation
Primary area: social_aspects->privacy

Abstract: The wide deployment of the generative pre-trained transformer (GPT) has raised privacy concerns for both clients and servers. While cryptographic primitives can be employed for secure GPT inference to protect the privacy of both parties, they introduce considerable performance overhead. To accelerate secure inference, this study proposes a public decoding and secure verification approach that utilizes public GPT models, motivated by the observation that securely decoding one and multiple tokens takes a similar latency. The client uses the public model to generate a set of tokens, which are then securely verified by the private model for acceptance. The efficiency of our approach depends on the acceptance ratio of tokens proposed by the public model, which we improve from two aspects: (1) a private sampling protocol optimized for cryptographic primitives and (2) model alignment using knowledge distillation. Our approach improves the efficiency of secure decoding while maintaining the same level of privacy and generation quality as standard secure decoding. Experiments demonstrate a $2.1\times \sim 6.0\times$ speedup compared to standard decoding across three pairs of public-private models and different network conditions.

An Efficient Private GPT Never Autoregressively Decodes
Zhengyi Li
Yue Guan
Kang Yang?
Yu Feng'
Ning Liu
Yu Yu 12 Jingwen Leng" 12 Minyi Guo 12
Abstract
comes a major concern. Recent works (Hao et al., 2022; Lu et al., 2025; Hou et al., 2023; Pang et al., 20ve) age secure two-party computation (2PC) to enable privacy- preserving GPT inference. These studies allow the client and server to jointly execute inference on encrypted inputs and models utilizing cryptographic techniques such as ho- momorphic encryption (HE) (Gentry, 2009) and multi parti computation (MPC) (Yao, 1986). Consequently, the client only learns the inference results without access to model weights, and the server knows nothing.
The wide deployment of the generative pre- trained transformer (GPT) has raised privacy con- cerns for both clients and servers. While crypto- graphic primitives can be employed for secure GPT inference to protect the privacy of both parties, they introduce considerable performance overhead. To accelerate secure inference, this study proposes a public decoding and secure veri- fication approach that utilizes public GPT models, motivated by the observation that securely decod- ing one and multiple tokens takes a similar latency. The client uses the public model to generate set of tokens, which are then securely verified by the private model for acceptance. The efficiency of our approach depends on the acceptance ratio of tokens proposed by the public model, which we improve from two aspects: (1) a private sampling protocol optimized for cryptographic primitives and (2) model alignment using knowledge dis- tillation. Our approach improves the efficiency of secure decoding while maintaining the same level of privacy and generation quality as stan- dard secure decoding. Experiments demonstrate a 2.1x 6.0x speedup compared to standard de- coding across three pairs of public-private models and different network conditions.
However, privacy protection incurs sigmificant computa- tional and communication costs for both the linear and nonlinear layers. Linear layers involving matrix multipli- cation are usually computed through HE, which requires substantial computation. Complex nonlinear layers, such as GELU and softmax, require numerous rounds of commu- nication and data transmission. To accelerate secure GPT inference, prior works focus on optimizing cryptographic protocols (Hao et al., 2022; Lu et al., 2025; Pang et al., 2024; Kim et al., 2024) or modifying GPT architectures to tailor the cryptographic primitives (Li et al., 2022: Zeng et al., 2023; Zimerman al., 2024; Ran et al., 2023; Li al., 2024a). Despite these efforts, achieving efficient secure inference remains major challenge.
This study explores an orthogonal approach by utilizing pub- lic GPTs to accelerate secure GPT inference, mainly during the decoding phase. We notice the availability of power- ful public GPT models within the GPT community (Wolf et al., 2019). These models share some linguistic and logical knowledge with private models (Chen & Gao, 2022; Zhao et al., 2023). Since this shared knowledge is inherently non- sensitive and publicly disclosed, more efficient approach is to only securely compute the exclusive parts of the private model instead of all. However, few works have explored this direction due the lack of interpretability of the GPT models (Friedman et al., 2024; Wen al., 2024), making challenging to separate shared knowledge.
1. Introduction
The generative pre-trained transformer (GPT) (Vaswani et al., 2017) has brought significant advancements in various machine learning tasks, such as coding (GitHub, 2025) and chatbots (Leiter et al., 2023). To deploy a GPT application, either the client needs to upload private data or the model owner needs to send its private model to the client. As GPT increasingly handles sensitive data and tasks, privacy be-
'Shanghai Jiao Tong University University"Shannhai Qizhi Institute 'State Key Laboratory of Cryptology. Correspondence Jingwen Leng <leng-jw @ wwwe@sstucco wwtp..edu..nn...... Kang Yang <yangk @ sklc.org>, Yu Yu <yyuu@ wet..sjuuuu.cee sjtu.edu.cn>..
This work introduces an observation of the performance characteristics of secure decoding to utilize public models for acceleration without comprising privacy. Standard se- cure decoding forwards only one token per decoding step. We observe that securely forwarding single and multiple tokens takes similar latency. This motivates us to treat the
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

An Efficient Private GPT Never Autoregressively Decodes
model as whole avoid the difficulties arising from dis- tinguishing shared knowledge. Inspired by the speculative decoding (Leviathan et al., 2023; Miao et al., 2024b), we propose a Public decOding and Secure verificaTion (Post) approach. Specifically, the client employs the public model to generate a set of draft tokens, which are then fed into the private model to verify their acceptance in a single decoding step. Given the shared knowledge between public and pri- vate models, it is likely that both models produce identical results when generating simple tokens or common phrases. This allows multiple tokens to be accepted in decoding step, reducing the required steps and the amortized cost per token.
2. Background
This work aims to accelerate the secure decoding of gener- ative pre-trained transformers (GPT). We present the nec- essary background on secure GPT inference and standard GPT decoding. Additional background and related works are in the Appendix 6.
2.1. Secure Two-Party Inference
Under the semi-honest threat model, where the corrupted party adheres to the protocol but may attempt to extract more information than permitted, secure two-party GPT inference guarantees the client receives inference results without accessing the model weights and the server remains oblivious to the client's private input (Juvekar et al., 2018; Hao et al., 2022: Lu et al., 2025; Pang et al., 2024; Li et al., 2024b). Existing approaches typically employ hy- brid protocols, combining homomorphic encryption (HE) and multi-party computation (MPC) based on the nature of each operation. HE is commonly used for linear operations, such as multiplication, which incurs intensive computation but requires minimal communication. MPC is generally em- ployed for nonlinear operations, such as comparison. MPC involves multiple rounds of communication and extensive transmitted data. Below, we provide a brief background on cryptographic primitives relevant to this work.
In POST, the reduction in decoding steps depends on the acceptance ratio of tokens proposed by the public models, which we further improve through two aspects. (1) Secure speculative sampling for soft matching: strict matching be- tween tokens generated by the public and private models causes unnecessary rejections, such as semantically equiv- alent tokens that are expressed differently. Therefore, we adopt the speculative sampling algorithm (Leviathan et al., 2023; Cai al., 2023), which applies "soft" matching to increase the acceptance ratio while ensuring the generated tokens follow the private model's output distribution. Since the computation in the speculative sampling algorithm is unfriendly to the cryptograph, we propose a protocol to op- timize the cryptographic-unfinne unfriendyy operations to achieve negligible overhead. (2) Knowledge distillation for model alignment: discrepancies between the public and private models reduce the acceptance ratio of draft tokens. To mitigate this, we align the two models through knowledge distillation, further increasing the acceptance ratio.
Additive Secret Sharing. Parties usually hold activations and model weights through secret sharing. In two-party setting, additive secret sharing over the ring Zye is defined as follows: for given value x E Zze, two random shares, (x) E Zze and (x)) E Zze, are uniformly sampled such that æ = (a)e + (x)) mod 2 holds. Here, (x)) and (z), are held by the client and the server, respectively.
In summary, this paper makes the following contributions:
Homomorphie Eneryption. The lattice-based additive HE scheme (Rathee et al., 2019) is proven secure under the ring learning with errors (RLWE) assumption (Lyubashevsky et al., 2010). HE enables one party to perform computa- tions another party's 's encrypted data without necessitat- ing access to the decryption key. HE typically employs Single Instruction Multiple Data (SIMD) techniques to re- duce amortized overhead (Brakerski et al., 2014; Juvekar et al., 2018). Multiple plaintext values are encoded into one polynomial ring, enabling homomorphic operations to be applied all encoded values in parallel.
We present a novel observation: the latency of secure GPT decoding is insensitive to input length. Based on this, we propose the PosT approach to integrate public GPT models into secure inference for acceleration while maintaining privacy and accuracy. This approach broadly applics across different cryptographic protocols and GPT models, where we observe similar insensitivity.
We further enhance the efficiency of PoST through two aspects: an optimized protocol that securely samples to- kens from two models and the alignment of models using knowledge distillation.
Oblivious Transfer. Oblivious Transfer (OT) is the build- ing block for various nonlinear operations, such as compari- son and truncation (Rathee al., 2020; Ma et al., 2023). Let (t) OT, denote the l-out-of-k OT functionality, which is a generalization of the l-out-of-2 OT. The sender's 's in- puts consist of k strings, Mg. ..., M+-1, each of length f bits, while the receiver's input is an index E [M.] The receiver obtains m, from the functionality, and the sender
We evaluate the performance under two network condi- tions and three pairs of private and public models, in- cluding Vicuna-7B and LLaMA-68N A 160M, FLAN-TS- XL. and 33-effiiient--mmalllbbass and FLAN-TS-XL. and TEAA--S--mmalllaarr Our approach shows 2.1x ~ 6.0x speedup than the standard secure decoding.
2

---

An Efficient Private GPT Never Autoregressively Decodes
receives nothing. The (1) a protocol requires two rounds of interaction and involves total communication
Longthei Longthe22 Length--4
Lengthed Longth=16
costs of kl + logg k bits (Yang et al., 2020).
2.2. Prefill and Decoding of the GPT
Ureee Unneat, Linean, Liner,,
The standard GPT generation process consists of two main phases: the prefill phase and the decoding phase. The prefill phase processes all tokens from the client's 's input prompt in a single forward pass, producing the output distribution for the first generated token. The decoding phase generates one token per decoding step in an auto-regressive manner. For a prefix << with t 1 tokens, which include both the input prompt and previously generated tokens, the forwarding of Teet generates the output distribution p (xr x<<e) of the teh token and samples from it. When t is clear or unimportant, p(z) is used simply for representation. To avoid repeatedly forwarding all previous tokens when generating a new token, the KV cache (Dettmers et al., 2022) stores the keys and values associated with past tokens, such that each decoding step only forwards one token.
Figure I. Latencies against different input lengths. The bandwidth and one one-way delay are 1000 Mbps and 10 ms.
10
One way De sy "Tarsm ssen Computation
Time Co
Linerr, Linaar, Linears, Linan,, Softmax Sofumax OK
OK?
LN 1000/30
LN 400/40
1000/10 400/40 1000/10 400.40 100M10 408/4D 1006/20 405/6C
Figure 2. of the x-axis ticks represents bandwidth and one-way delay. The bars corresponding to the same x-axis ticks illustrate input lengths 1, 2, 4, 8, and 16.
The latency breakdown of some layers. The second row
Since secure decoding accounts for the majority of com- putation time (Liang et al., 2024), this work focuses on improving its efficiency. A detailed explanation of the pre- fill and decoding phases is provided in Appendix A.
pretability in model weights and activations (Friedman et al., 2024; Wen et al., 2024), clearly separating shared knowl- edge between public and private models is challenging, and any reckless use of plaintext computations may introduce unforeseen risks. Therefore, current secure inference meth- ods require that all computations remain private.
3. Motivation
The public model shares partial knowledge with the private model. To utilize such knowledge for acceleration without comprising privacy, we introduce an observation on the per- formance characteristics of securely computed GPT layers.
3.2. Insensitivity of Latency to the Input Length
To utilize the public GPT model for acceleration, we in- troduce a unique performance characteristic observed in two-party secure decoding, which allows us circumvent the challenge of separating the knowledge between the pub- lic and private models. Figure 1 illustrates the decoding latencies for different input lengths using the open-source model FLAN-T5-XX (Chung et al., 2024). The latencies are profiled on the well-established framework SecretFlow- SPU (Ma et al., 2023). In standard decoding, GPT generates only one token per step. For such minimal input length one, we find that gradually increasing the input length has almost impact latencies. The latencies remain sim- ilar when the input length increases from 1 to 4. As the input length continues to increase to 8 or 16, latency only experiences a sub-linear increase. Consequently, the total latencies of Transformer decoder on input lengths 8 and are only 1.2x and 1.5x greater than that of input length of 1. In Appendix 1. we observe similar insensitivity to input length across various network conditions, GPT sizes, and underlying cryptographic protocols.
3.1. Shared Knowledge of Public and Private GPTs
Publicly Available GPTs. The availability of numerous public pre-trained models (Wolf et al., 2019; Touvron et al., 2023; Chung et al., 2024) introduces a distinctive charac- teristic compared to other privacy-related scenarios: the knowledge embedded in the private GPT's is not entirely private. The linguistic knowledge (grammar, syntax, and common facts) and logical abilities (understanding and rea- soning) can also be captured by the public model and are partly shared between public and private models (Chen & Gao, 2022; Zhao et al., 2023). As supporting evidence, the public models also present satisfying performance on var- ious tasks (Analysis, 2025), although less powerful than private models.
Given that public GPTs have revealed shared knowledge, an ideal secure inference for the private GPT should allocate costly cryptographic computation only exclusive knowl- edge while employing inexpensive plaintext computations for shared knowledge. However, due to the lack of inter-
To understand why such insensitivity generally holds, we decompose the latency of each layer into the one-way delay, computation time, and transmission time, as illustrated in Figure We analyze how each component contributes to
3

---

An Efficient Private GPT Never Autoregressively Decodes
the insensitivity of the overall latency.
Accepted bonus tokens (iuon----2// Tell)
One-way Delay. The one-way delay is a fixed latency per communication round due to propagation time and hard- ware processing. Time spent on the one-way delay remains constant, the number of communication rounds is inde- pendent of the input length. Secure evaluation generally necessitates multiple rounds of communication, especially nonlinear protocols that require more than a hundred rounds. The time spent on one-way delays constitutes a substantial portion of the overall latency, directly contributing to the overall insensitivity to variations input length.
Public model's distributions (f(ttt..))... (fl
Prefix Axa
Secure Verlficttoon
Secure computation
Online Stage
Plaintext Decading
Piivate mocel's
||
distributons
Secure Forward
Public
tokens
fre. Reap I)
Aligned public model
Private model (x6)))
Server
Private client
X
Model Alignment
Mignment.delasett
P Painttett Decoding
Private to the server
Offline Stage
The computation time demonstrates a small variation in input length. The computation time is mainly spent on homomorphic operations, including matrix multiplication in the linear layer and Hadamard multiplica- tion of the approximated polynomials in the nonlinear layer. The insensitivity of computation time can be attributed to two aspects. First, larger input lengths typically enable bet- ter parallelization and more efficient hardware utilization. Second, increasing the input length improves the efficiency of SIMD operation in HE (Hao et al., 2022; Lu et al., 2025). To ensure security, SIMD operation typically encodes 8192 activation values into the ciphertext polynomial. However, with an input length of I, the number of activation values is often smaller than 8192. For instance, the hidden dimension of FLAN-TS-XL. is 2048, and smaller models like GPT-2 have dimensions as low as 768. Larger input lengths can better saturate all slots in the polynomial ring to enhance computational efficiency. As Figure 2 shows, homomorphic operations constitute significant portion of overall latency and contribute to the overall insensitivity.
Computation Time,
Public model
Non-sensitive dataset
Fiivate
Figure 3. The overview of the public decoding and secure ver- ification approach. (-) indicates the data are encrypted during computing, such as using the secret sharing, and is only visible the data owner.
4.1. Overview
We propose an approach to leverage knowledge from the public model to enhance efficiency: Public decOding and Secure verificaTion (PoST), as illustrated in Figure 3. POsT includes online and an one-time offline stages.
In the online stage, the client holds public model Myybb while the server holds private model Mpri- The client also holds the prefix Tet, consisting of f - tokens, which in- clude the input prompt and previously generated tokens. In prior secure inference works, only the next token is generated in a single decoding step. This results in only one vector being forwarded in the secure forward, lead- ing to inefficiencies demonstrated in Section 3.2. In con- trast, POST first lets the client autoregressively sample draft tokens from the public model's output distributions Ii ~ q(x Fet)) Iyy ~ ( xc(+t-1)- Subse- quently, both parties securely forward all draft tokens in de- coding step to generate private model's output distributions (p(x =.r)),.... {p(x <<(+))), which are secret shares the ring Zz. Then the secure verification (Section 4.2) adopts the speculative sampling algorithm (Leviathan et al., 2023) to determine which tokens can be accepted based on both the public and private models' output distributions. We give specialized optimizations to securely execute specula- tive sampling, minimizing its overhead. Tokens before the first rejection are kept, while those after are discarded. Since the private model accepts all tokens up the first rejection, the first rejected token can be re-sampled from the private model's adjusted output distribution to obtain an additional "bonus" token.
Transmission Time. The relationship between transmis- sion time and input length differs between HE and MPC. For HE, the transmission size increases sub-linearly due to the efficiency of SIMD. As input length increases, multi- ple embedding vectors are packed into a single ciphertext, which does not change the overall transmission size. In con- trast, the transmission size associated with MPC generally increases linearly with input length. Overall, compared to one-way delay and computation time, transmission time is more sensitive to input length variations. However, trans- mission time is not the primary bottleneck for extremely small input lengths, and its impact on the overall latency increase remains limited.
4. Public Decoding and Secure Verification
Based on the observation in Section 3, we first propose new approach for secure GPT decoding. Then, we further improve its efficiency from two aspects.
In the offline stage, we also perform model alignment (Sec- tion 4.3) to align the public model's output distribution with
4

---

An Efficient Private GPT Never Autoregressively Decodes
that of the private model through knowledge distillation. This can further increase the acceptance ratio of draft tokens and enhance performance improvements.
Algorithm 1 Privately Reject Draft Tokens
Input: P. holds public model's distributions q(2 I Tct)), .9(x xe and samples y draft to- kens "1,".. L.gg. P. and P. hold the secret sharing (p(x x<tt)), (p(x (<(+t)) E Zz of the distri- butions generated by the private model. The vocabulary size is V. The h+] means [0, 1, ......71.
Our approach offers following advantages.
Consistent Speedup: In worst case where all draft to- kens rejected, Post's secure forward still generates bonus token, the same as the previous secure decod- ing methods. In more general cases, easily predictable draft tokens are likely to be accepted by the private model. Therefore, forwarding multiple tokens incurs a cost comparable to forwarding just one token, while allowing for the generation of least one token in a single step, thus reducing the amortized cost per token.
q(xr| [<er)
1: Pa sets Q=
Ps and Pa set (P)= =
(p(x | (x(e))
(p(x (x<(+t))
Pe generates a random vector Rmat ~ (0, 1)7xV
3: Ps sets his share of (S), = -(P)s and Pa sets her share (S). m..:Q. Q RRmut (P)c mod 2
Security Guarantees: PoST ensures that the client ob- tains only the information permitted in standard secure inference protocols, while the server remains oblivious to the client's private input data.
4: for i E [71l, in parallel do
5: P. generates a random vector ~ Lze and masks
his share as (S(i,:)), (S :1), -[[] mod 2
6: P. chooses the secret share by (s]1, (
The token generated in PoST precisely maintains the output distribution of the pri- vate model in standard secure inference, ensuring accuracy degradation.
Accuracy Preservation:
( x2:).
7: Ps sets his share (s) = r[1 and Pa sets her share (s) - (S]ú, 2.l)e + (S)i a;l)s mod 2f.
8: end for
Practical Implementation: PoST imposes no change or fine-tuning on the private models and can be seamlessly integrated with existing secure inference methods.
9: P. and P. compute shares of boolean vector (n)
Fless (s)) and open n to Pa.
10: P. appends an element one at the end by n = n + [1]
11: P. computes = min (fi i h1, mii = 1}).
Future Scalability: The continuous advancement of public model capabilities presents significant potential of the acceptance ratio of the draft tokens, ensuring sustained performance improvement as the acceptance ratio increases.
12: P. chooses (px(x))
(+t)
OT&(Kp(= | I<<()).." <p(z [<<(t)))el,
Output: P. obtains index k and corresponding ple (x)).
of the public model, each token v; is rejected according to the probability defined by:
The following sections detail our designs for secure verifi- cation and model alignment enhance efficiency.
max p(2, (<(tte)) q(0; xec+se)
(1)
4.2. Secure Verification
Naive Sampling from Two Distributions. To determine whether draft tokens are accepted, a naive way is to sample from the output distribution of private models and only accept matched tokens. However, this method results in a low acceptance ratio. In many cases, tokens with similar meanings may exhibit similar output distribution densities, yet these proposals may still be rejected due to the "hard" matching.
The p(a; xe(ts) represent the probability density of the 24 If the first rejected token has i < 7, it is resampled from an adjusted distribution (xx = max(0, p(x x<(+s) - g(< | z<(+s)). If all draft tokens are accepted, the bonus token is directly sampled from the distribution p(x: (<(4))-
Challenge of Secure Speculative Sampling. The perfor- mance challenge lies in rejecting draft tokens according to the probability Equation (I). The standard approach is to privately compute Equation (1) and then compare it with random number within [0, 1]. However, the involved divi- sion and comparison are not friendly to the cryptographic primitives. Furthermore, the dimension of the output dis- tributions is the vocabulary size V (typically V > 30000), making probabilistic rejection in secret considerably slow.
Speculative Sampling. Therefore, we employ "soft" matching called speculative sampling (Leviathan et al., 2023; Cai et al., 2023). Speculative sampling ensures that the tokens sampled from p(x) and ((x) are distributed iden- tically to those sampled from p(æ) alone. Specifically, given y draft tokens [xi,'". 2ty] sampled from the distributions
5

---

An Efficient Private GPT Never Autoregressively Decodes
To mitigate this issue, the proposed protocol is in Algorithm 1. Next, we explain two key designs in our protocol.
the final output, the output distribution is supposed be dis- closed to the client for sampling tokens. Rejecting boolean values is natural result once the client knows which token Refactor the division into multiplication (lines 2-3). To avoid the division p(a.)
has been generated. In this way, the information revealed is no more than the standard decoding. All other information is in the form of secret shares and processed through crypto- graphic primitives. The security guarantee stems from the composability of cryptographic protocols. We put a more detailed analysis in Appendix D.
q(m))) we let the client generate a random matrix Reaul and execute Hadamard multiplication with Q locally. After the client subtracts ( from Q Rmut. both
parties hold shares of the scores (S) = (Q Rmat) P mod 2 For all draft tokens, the elements corresponding to the selected index 2y are compared with zeros to generate boolean rejection decision 1 (S]i, mx] 0} for i [n]-
4.3. Aligning Public and Private Model
Selection then Comparison (lines 4-9). For elements 25] that correspond to draft tokens, directly select- ing their most significant bit (MSB) out for sign bit is not feasible. This is because the S are represented as secret sharing on the ring Ze. Thus, the parties must se- curely compute the carry bits from the lower & - 1 bits to obtain the correct MSB. This computation necessitates a (1) - oT, (Rathee et al., 2020)'. Since the server cannot know which element is selected, both parties must securely compute the carry bits for all elements; then, the client se- lects the desired MSB through another (1) - OT, For each draft token, the total communication complexity is (2 V * 2 + V> + f + V + log, V). When selecting data, the communication complexity is linear with respect to the bit width. In contrast, when computing the carry bit, the bit width comes as the exponential complexity. Computing the carry bit of all elements incurs considerable unnecessary overhead.
It is observed that, although fundamental linguistic knowl- edge is expected to be common across models, variations in training datasets and methodologies lead to biased output distributions between models. To improve the acceptance ratio, we propose aligning the public model with the pri- vate model through knowledge distillation (Li et al., 2022; Agarwal et al., 2024).
To perform the alignment, the client can choose a dataset independent of his privacy, such as a public corpus or anonymized data (Tang et al., 2024). This ensures that the queries can be accessed by the service provider and processed through plaintext inference. The client begins by querying the model using the standard de- coding method and collects a dataset that includes the prompt and all output distributions, denoted as Q
{ (x(): {p(y(") (t) |x((), v=)) where n, is the response length for the in prompt. Note that the general GPT API only returns the output distributions' topK (usually top 5) elements (Leiter et al., 2023). The client can only use these topK elements for alignment. On an input prompt x(0), the client aligns the public and private models using the loss function
To eliminate this unnecessary overhead, we first recon- struct shares of the interested elements and then compares them with O. For each row of the score matrix :] the server masks his share by a common random value as :)) = [S],,;)) - r[i]]. The client employs the index of the draft token to retrieve the share of the selected ele- ment through (1) OT₃- The server remains unaware of which score share is retrieved yet retains the shares of the se- lected score, with the server holding r and the client holding (s). = x,ū r mod 2 Subsequently, the two parties evaluate comparisons on the selected element to derive re- jection decision. In this manner, the overall communication complexity is 0(V # E + log2 V + 2 2 + f).
((x(1) = Σ D (pist (x y 22ll 2 1x0
(2)
where D(pll - - plog q is the eross entropy. By mini- mizing this loss function, the public model learns to generate tokens that better align with the private model's output dis- tribution, improving the acceptance ratio of the draft tokens.
Security Analysis. In our private sampling, the server re- mains unaware of any client information. The only disclosed information consists of the rejection boolean values and the distributions used for re-sampling the first rejected token. As
Security Analysis The security of the model alignment is trivial to show since all used data are allowed disclose. The query data used in the alignment are public corpus or anonymized data. These data are safe to be obtained by the server. The knowledge distillation only uses the topK elements of the output distribution of the private model, which are allowed to be revealed to the client.
'Existing works usually trades more communication rounds with reduced transmitted size by breaking one (25) OT2 into instances of both secure AND operation and (2 OT2, where q=m = E (Rathee al., 2020; Ma et al., 2023). We use simplified comparison protocol for illustration, and this does not affect the conclusion.
Server Provided Public Model. Although the discussion lets the client select and align the public model, a more ef- fective approach is to let the server provide an aligned public
6

---

An Efficient Private GPT Never Autoregressively Decodes
Table 1. The acceptance ratio of tokens proposed by public models before and after the alignment (AL).
Task
Private Model
Public Model
SP
SP-AL
GS
GS-AL
CP
CP-AL
FN
FN-AL
Llama-68M
0,240
0.614
0.462
0.662
0.366
0.561
0.512
0.626
Vicuna-7B
Llama-1660 160M
0.302
0.592
0.536
0.691
0,405
0.665
0.576
0.650
-s-llf-smmal
0,404
0.539
0.315
0.517
0.562
0.700
0.338
0.633
FLAN TS-XL
T5-eff.-base 0.583
0.690
0.387
0.623
0.576
0.796
0.301
0.686
FLAN-TS T5-lllll
0,689
0.730
0.630
0.676
0.796
0.821
0.535
0.740
FLAN-TS-XL
FLAN-T5-bar 0.736
0.782
0.711
0.751
0.818
0.840
0.641
0.774
model. The server is willing offer an aligned public model because the alignment does not harm the server's 's privacy but allows a more efficient service. The server can offer a better- aligned public model than the client could achieve, leading to higher acceptance ratio. The server has better insights into the training datasets and has access more computa- tional resources. The server can select nonsensitive dataset that closely resembles the private dataset and select public models with larger size. This is already the case when the server publishes smaller versions of the private model, such as Gecko in the Palm2 series from Google (Ghahra- mani, 2023) and Qwen2.5 in the Qwen series from Alibaba Cloud (Aliyun, 2025). Our experiments show that public models from the same series as their corresponding private models produce more aligned tokens, making approach more appealing to the secure GPT decoding.
0.8
Acceptance
0.6
0.4
Vicuna-78 & LLaMA-160M
FLAN-TS-XL & TS-eft-base
FLAN-TS-XL FLAN-TS-base
0.2
2
Token Count
1e6
Figure 4. The alignment efficiency of three pairs of models on the Spider task.
on the C4 and Wiki-DPR datasets (Karpukhin et al.. 2020), followed by fine-tuning on wide range of downstream tasks across various languages. The T5-efficient series is only pre-trained on the C4 dataset without fine-tuning, The third pair examines the acceptance ratio when the server releases a small version of the private model from the same series. In this case, we compare FL-N--T-XIL (3B) with FLAN-T5-small&biee
5. Experimental Results
Section 5.1 begins by detailing the experimental setup. Sec- tion 5.2 then presents the improvement in the acceptance ratio of draft tokens achieved through alignment and Sec- tion 5.3 highlights the improvement in end-to-end latency. Finally, Section 5.4 demonstrates the minimal overhead in- troduced by the optimized speculative sampling protocol. We omit the accuracy analysis (e.g., perplexity) since our method guarantees an identical output distribution to the private model, ensuring zero accuracy degradation.
Among three pairs of models, we use models that from different series to show the robustness and general applicability and models from same series to show the performance in favorable setting.
We evaluate performance across four diverse tasks: Text- to-SQL (Spider) (Yu et al., 2018), graduate school math (Gsm&k) (Cobbe et al., 2021). Python code generation (Code-search-Pyttoon (Husain al., 2019), financial ques- tion answering (Alpaca- -anance) (Gaurang Bharti, 2024).
5.1. Experimental Setup
Models and Tasks Throughout our experiments, we em- ploy three pairs of private and public models, each dif- fering in architectures and training hyperparameters. The first pair Vicuna-7B (Chiang et al., 2023) and L-aMA- 68M&160M (Miao et al., 2024a). Vicuna-7B is pre-trained on the CommonCrawl dataset (Wenzek et al., 2020) and fine-tuned using approximately 125,000 conversations from ShareGPT..com. L.LMA-68M& 160M is pre-trained with the C4-en dataset (Raffel et al., 2020). The second pair is FLAN-T5-XX (3B) (Chung et al., 2024) and T5-efficient- small&base (Tay et al., 2021). FLAN-T5-XL is pre-trained
Secure Inference Setup Performance evaluations con- ducted on two nodes with 64 vCPUs and 128 GB memory. We utilize Linux Traffic Control (tc) to simulate Local Area Network (LAN) and Wide Area Network (WAN) environ- ments, setting bandwidth and one-way delay to (1 Gbps, 10 ms) for LAN and (400 Mbps, 40 ms) for WAN.
Baselines To the best of our knowledge, prior works mainly optimize the protocols or modify the model architectures. POST is complementary to these works and can be integrated for further performance improvements. The performance
7

---

An Efficient Private GPT Never Autoregressively Decodes
AP-AL
Standard decoding
Standard lengthed Draft l
Sp-AL
Standard diecoding
langthed
GS-AL
Dratt lengthidd
Spendup
CPAL
FN-AL
Dratt length-16
Draft length-@
Speecal
AL FN-L
Draft length-16
Sperdup
6-
FN AL
Draft longth-16
lengthmi
0.50 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90
0.50 0.55
0.80
0.65 0.70 0.75 0.80 0.85 0.90
0.50 0.55
0.50
0.75 0.50 0.55 0.90 Acceptance ratio
0.65
0.70
Acceptance ratio
Acceptance ratio
(a) Vicuna- 7B LLaMA-160M on LAN.
(h) FLAN-TS-XI. -S-eff--base on LAN. (c) FLAN- FLAN-TS-haase on LAN.
Sp-AL AL
Standard decoding
Sp AL
Standard deced
Sp
Standard decoddnng
CS-AL
Draft lengthed
GS-L
Draft lengthmd
GS-AL
Draft langthed
Speedup
FN-AL
Draft length=16
length-88
X
FN-AL
Draft length=16
length-8
Speedup
CPAL
FN-AL
Draft length-8
lingth-15
2-
Acceptance rablo
Acceptance ratlo
Accoptance ratio
(d) Vicuna-7B & LLaMA-160M WAN. (e) FLAN-TS-XLL & T5-eff.bbase on WAN. FLAN-TS-XL FLAN-TS-base WAN.
Figure 5. The end-to-end speedup across two network settings and three pairs models. The curves illustrate the relationship between speedup and acceptance ratio for various draft lengths. Specific speedups for four selected tasks marked these curves.
improvements are compared with SOTA inference protocols for the Transformer model, BumbleBee (Lu al., 2025) and Nimbus (Li et al., 2024b). Specifically, choose the linear protocol of Nimbus and the nonlinear protocol of BumbleBee, both of which have negative impact on the model accuracy. All experiments are conducted on the well- established framework SecretFlow-SPU (Ma et al., 2023) for secure inference.
indicate that larger public models achieve higher acceptance ratios, aligning with the intuition that larger models have greater capacity. In this study, the public GPTs employed are small and can be fine-tuned on single GPU with 20 GB of memory. We anticipate that using larger public GPTs would further enhance the acceptance ratio.
Alignment Efficiency Figure 4 presents the relationship between the acceptance ratio and the number of tokens used for knowledge distillation. We use the spider task as an example and the similar trend also holds for other tasks.
5.2. Alignment Results
Improvements on Acceptance Ratios Table lists the acceptance ratios before and after alignment (AL). The re- sults are based on eight draft tokens per decoding step. The acceptance ratio a represents the expected probability that draft token accepted. Consequently, our approach re- duces the number of decoding steps by _ T-a compared to standard decoding. Across various model pairs and tasks,
The results indicate that the alignment process notably efficient regarding the token number. The acceptance ratios increase rapidly for all three model pairs, achieving satis- fying acceptance ratio after approximately million tokens. Existing API of GPT service usually charges the client per token. Given the current API pricing (OpenAI, 2025), the total cost for this amount tokens is approximately $10, demonstrating the practical feasibility. Moreover, as dis- cussed in Section 4.3, more effective approach let the server perform the alignment.
the acceptance ratios after alignment range from 52% to 84%, resulting in 2.0x to 6.3x reduction in decoding steps compared to standard decoding.
The knowledge distillation enhances acceptance ratios. For model pairs from different series (the first two pairs), align- ment increases the acceptance ratio from 10% to 40%, with final values ranging from 60% to 80%. For model pairs from the same series (the third pair), the improvement is approximately 10%, the original public model already exhibits high acceptance ratio, resulting in final accep- tance ratios between 75% and 85%. Moreover, the results
5.3. End-to-end Performance
Figure shows the speedup against the acceptance ratio using 8, and 16 draft lengths. Markers on the curve indicate the speedup for four tasks. We present results for the selected model pairs and two network conditions. We also show the baseline for standard secure decoding (the red dot line), which has a speedup number one. For any task,
8

---

An Efficient Private GPT Never Autoregressively Decodes
the sparsity to linear layers reduce the homomorphic op- erations (Zimerman al., 2024; Ran al., 2023; Xu et al., 2024) For linear layers, some works (Chen et al., 2022; Zeng et al., 2023; Li et al., 2022) use aggressive approximation of Softmax and GELU. However, such aggressive approxima- tions lead to noticeable accuracy loss, even when employing knowledge distillation to mitigate the decline in accuracy. A more accurate way is to use piecewise polynomial to ap- proximate the nonlinear layers (Dong et al., 2023; Lu et al., 2025; Li et al., 2024b). They use high-degree polynomial and multiple pieces. It does not result in an accuracy drop but is also relatively costly to compute.
Table Comparison of the naive and optimized secure speculative
sampling.
Network Condition
Draft Length
Decoder Time/s
Naive Time/s
Ours Time/s
1 Gbps 10 ms
7.11
14.78
1.19
8.67
28.26
1,45
400 Mbps
20.32
24.44
3.04
40 ms
8
22.49
46.62
4.12
the client and server can choose the proper draft length for the best speedup, which we find ranges from 2. x to 6.0x.
In contrast, this work examines a different aspect by leverag- ing the knowledge shared between public and private models to accelerate secure inference, which can be combined with prior work for further speedup.
Typically, greater draft lengths correspond to lower curves. Since the time spent on the public decoding and secure sampling is negligible, the primary reason is the increased decoding time associated with larger input size. However, because a higher draft length leads to a higher expected number of accepted tokens per step, the overall end-to-end speedup may still be greater. Furthermore, the speedup is consistent across the two network conditions tested and tasks. This consistency demonstrates the great applicability in diverse deployment scenarios.
Speculative Decoding Speculative decoding is recent technique designed enhance the efficiency of autoregres- sive decoding of the GPTs (Leviathan et al., 2023; Cai et al., 2023; Liu et al., 2023). In the original speculative decoding, several draft tokens are generated using a tiny GPT and are forwarded by a large GPT in parallel, which also inspires the proposed PoST approach. However, PoST differs from the original speculative decoding in three key aspects. First, POST is based on a unique observation that cryptographic protocols in secure GPT decoding demonstrate insensitivity to input length. Second, speculative decoding must carefully balance the computational costs between the tiny and large GPT models. In contrast, in this work, the cost associated with the public model is negligible compared to the secure decoding process of the private model, and we primarily focus on optimizing the cost of securely executing the spee- ulative sampling algorithm. Third, while speculative decod- ing can freely choose models to propose draft tokens, this work selects public models that are not closely related to the private model. Consequently, we employ model alignment to demonstrate that pairs of models with low relevance can still achieve a high acceptance ratio following knowledge distillation.
5.4. Secure Speculative Sampling Performance
Table 2 presents the performance of secure speculative sam- pling using Vicuna-7B as an example, both with and with- out optimization. For reference, we also report the secure evaluation time of a single decoder. The vocabulary size associated with the sampling time is 32000, which is similar for different private models. Without optimization, the sam- pling process incurs latency equivalent to the latency of two decoders, which noticeably increases end-to-end delay. In contrast, our optimization yields approximately ten- fold latency reduction, rendering its impact on end-to-end latency negligible.
6. Related Work
Private Transformers. One type of works are to optimize cryptographic protocols improve the efficiency of the secure inference. For linear layers, existing works usually modify the encoding methods (Hao et al., 2022; Pang et al., 2024; Li et al., 2024b) and the ciphertext packing strat- egy (Lu et al., 2025; He et al., 2024) to improve the com- putation and communication. For nonlinear layers, Crypt- Flow2 (Rathee et al., 2020) proposes a faster millionaire protocol to reduce communication size. Other methods, such as look-up tables for faithful approximation (Rathee et al., 2021; Gupta et al., 2023; Pang et al., 2024), are com- putationally expensive to maintain model accuracy.
7. Conclusion
This work proposes novel POST approach to secure GPT inference. Our approach utilizes knowledge already dis- closed by public models for accelcration while maintaining the same privacy goal and generation quality comparable to standard secure decoding. Our approach demonstrates speedup ranging from 2.1 x 6.0x across various set- tings. Furthermore, our approach offers the potential for even greater speedup when applied to better-aligned public models, such as those provided by servers or larger public models. These optimizations enhance performance, advanc- ing the practical application of secure GPT inference.
Another type of works is to modify the Transformer model to tailor the eryptographic primitives. Some works integrate
9

---

An Efficient Private GPT Never Autoregressively Decodes
Acknowledgement
ings of the AAAI Conference on Artificial Intelligence, pp. 10509-10517, 2022.
This work was supported by the National Natural Science Foundation of China grants (62222210, 62125204, and 92270201). This work was also supported by Shanghai Qi Zhi Institute Innovation Program SQZ202316. Correspond- ing authors are Jingwen Leng (leng-jw @ ejsst.edu..oo edu.en), Kang Yang (yangk @ sklc.org), and Yu Yu (yyuu @ (ew.sssj..uuuu...
Chiang, W.-L., Li. Z., Lin, Z.., Sheng. Y., Wu, Z., Zhang, H., Zheng, I.., Zhuang, S., Zhuang, Y., Gonzalez, J. E.,, et al. Vicuna: An open-source chatbot impressing gpt-4 with 90%* * chaigpt quality. See htlps://vicuna. Imsys. org (accessed 14 April 2023), 2(3):6, 2023.
Chung, H. W., Hou, L., Longpre, S., Zoph, B., Tay, Y., Fe- dus, W., Li, Y., Wang, X., Dehghani, M., Brahma, S., et al. Scaling instruction -innttiio--ieetteeed language models. Journal of Machine Learning Research, 25(70):1-53, 2024.
Impact Statement
This paper presents work whose goal is advance the privacy-preservin GPT inference. Our work introduces more efficient method for privacy inference, which con- tributes to providing active protection against potential pri- vacy issues arising in the application of GPT.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems. arXiv preprint arXiv: 10. 14168, 2021.
References
Dettmers, T., Lewis, M., Belkada, Y., and Zettlemoyer, L. Gpt3, int8 (): 8-bit matrix multiplication for transformers at scale. Advances Neural Information Processing Systems, 35:30318-300
Agarwal, R., Vieillard, N., Zhou, Y.. Stanczyk, P., Garea, S. R., Geist, M., and Bachem, O. On-policy distillation of language models: Learning from ceff-generated mistakes. In The Twelfth International Conference on Learning Representations, 2024. URL httpstt////// http:::://ppeeeevieeee net/forund wttp:/ummmidiikktgxxttxee
2022.
Dong, Y., Lu, W.-j., Zheng, Y., Wu, H., Zhao, D., Tan, J., Huang. Z.,, Hong, C., Wei, T., and Cheng, W. Puma: Se- cure inference of Ilama-7b in five minutes, arXiv preprint arXiv:2307. 12533, 2023.
Aliyun. What is qwen Ilm. [Online], 2025. https://help. com/ zh/ model moddl-sstudddo/evelle-----eeeee http:////e//eoppeeeeeeeeeee///// rfference/ that-is-qwen--ee
Friedman, D., Wettig, A., and Chen, D. Learning trans- former programs. Advances in Neural Information Pro- cessing Systems, 36, 2024.
Analysis, A. Comparison of models: Quality, performance & price analysis. https:://// / /rrtiirti aaraaiffiiiii aiiiiallaaalla aaanallss aalaaallisssss.... ai/modelss s, 2025. Accessed: 2025-01-29.
Gaurang Bharti. finance- (revision 51d16b6), 2024. URL https: /hugg ngggiingacce.. co /atasetss Sahharti/finance-allpee
Brakerski, Z., Gentry, C., and Vaikuntanathan, V. (lev- eled) fully homomorphic encryption without bootstrap- ping ACM Transactions on Computation Theory (TOCT), 6(3):1-36, 2014.
Gentry, C. Fully homomorphic encryption using ideal lat- tices. In Proceedings of the 41th Annual ACM Symposium on Theory of Computing STOC"09, pp. 169-178. ACM, 2009.
Cai, T., Li, Y., Geng, Z., Peng. H., Lee, J. D., Chen, D., and Dao, T. Medusa: Simple Ilm inference acceleration framework with multiple decoding heads. In Forty-first International Conference on Machine Learning, 2023.
Ghahramani, Z. Introducing palm 2. [Online], 2023. https://blog http://bloooggggleeeeeoooeo www.ggll/eechneoggggee.o /.
2-ai sai-las large-rggeaaa paaarge-languse langge---enggaammmmemlele model/
Chandran, N., Gupta, D., Rastogi, A., Sharma, R., and Tripathi, S. Ezpe: Programmable, efficient, and scalable secure two-party computation. IACR Cryptol. ePrint Arch., 2009:1109, 2017.
GitHub, I. Github copilot, 2025. URL URLhttps://githbb com/ feat ures/ure//cooo cttp lot.
Gupta, K., Jawalkar, N., Mukherjee, A., Chandran, N., Gupta, D., Panwar, A., and Sharma, R. Sigma: secure gpt inference with function secret sharing. Cryptology ePrint Archive, 2023.
Chen, T., Bao, H., Huang, S., Dong, I.., Jiao, B., Jiang, D., Zhou, H. Li, J., and Wei, F. The-x: Privacy- preserving transformer inference with homomorphic cryption. arXiv preprini
2022.
Hao, M. Li, H., Chen, H., Xing, P., Xu, G., and Zhang T. Iron: Private inference on transformers. Advances in Neural Information Processing Systems, 35:15718- 15731, 2022.
Chen, Z. and Gao, Q. Probing linguistic information for log- ical inference pre-trained language models. In Proceed-
10

---

An Efficient Private GPT Never Autoregressively Decodes
He, J., Yang, K., Tang, G., Huang, Z., Lin, L.,, Wei, C., Yan, Y., and Wang. W. Rhombus: Fast homomorphic matrix- vector multiplication for secure two-party inference. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, pp. 2490-2504, 2024.
Leviathan, Y., Kalman, M., and Matias, Y. Fast inference from transformers via speculative decoding. In Inter- national Conference Machine Learning, pp. 19274- 19286. PMLR, 2023.
Li, D., Shao, R., Wang, H., Guo, H., Xing, E. P., and Zhang, H. Mpcformer. fast, performant and private transformer inference with mpc. arXiv preprint 1rXiv2221.00155. 2022.
Hou, X., Liu, J., Li, Y., Lu, W.-j., Hong, C., and Ren, K. Ciphergpt: Secure two-party gpt inference. Cryptology ePrint Archive, 2023.
Li, F., Zhai, Y., Cai, S., and Gao, M. Seesaw: Compensat- ing for nonlinear reduction with linear computations for private inference. Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp. F. (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Ma- chine Learning Research, pp. 27 Jul 2024a. URL ht /ptppooeceeingss.c mllr. press / /21./22555/// 1124c html.
Husain, H., Wu, H.-H., Gazit, T., Allamanis, M., and Brockschmidt, M. Codescarchnet challenge: Evaluat- ing the state of semantic code search. arXiv preprint (XXiv:9990009444 2019.
PMLR, 21-
Ishai, Y., Kilian, J., Nissim, K., and Petrank, E. Extending oblivious transfers efficiently. In Annual International Cryptology Conference, pp. 145-161. Springer, 2003.
Li, Z., Yang. K., Tan, J., Lu, W.-j., Wu, H., Wang, X., Yu, Y., Zhao, D., Zheng, Y., Guo, M., et al. Nimbus: Secure and efficient two-party inference for transformers. arXiv preprint arXiv:2411. 15707, 2024b.
Juvekar, C., Vaikuntanathan, V., and Chandrakasan, A. (GAZELLE): A low latency framework for secure neural network inference. In 27th USENIX Security Symposium (USENIX Security 18), pp. 1651-1669, 2018.
Liang, Z., Wang, P., Zhang, R., Xu, N., Zhang, S., Xing, L., Bai, H., and Zhou, Z. Merge: Fast private text genera- tion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 19884-19892, 2024.
Karpukhin, V., Oguz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W.-t. Dense pas- sage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 6769-6781, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/v1/ 2020.emnlp- 550. URL https: /twp///www/..//// www....wwbb. org/ antho ogy 22020 e mm..pmmaai.55..0
Liu, X., Hu, L.,, Bailis, P., Cheung, A., Deng, Z., Stoica, I., and Zhang, H. Online speculative decoding. In Forty-first International Conference on Machine Learning, 2023.
Lu, W., Huang, Z., Gu, Z., Li, J., Liu, J., Hong, C., Ren, K., Wei, T., and Chen, W. BumbleBee: Secure Two- party Inference Framework for Large Transformers. In 32nd Annual Network and Distributed System Security Symposium, NDSS 2025. The Internet Society, 2025.
Kim, J.-Y., Park, S., Lee, J., and Cheon, J. H. Privacy- preserving embedding via look-up table evaluation with fully homomorphic eneryption. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scar- lett, J., and Berkenkamp, F. (eds.), Proceedings of the s International Conference on Machine Learn- ing, volume 235 of Proceedings of Machine Learn- ing Research, pp. 24437-24457. PMLR, 21-27 Jul 2024. URL htRt:t::: : /ot:::///proeee /ptpp//eceengs...//////////..sse www.m.r.p... mlr.press/ v235/kim24an html.
Lyubashevsky, V., Peikert, C., and Regev, O. On ideal lat- tices and learning with errors over rings. In Advances in SxpptoooyyEUROCRYPP 2010: 29th Annual Inter- national Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30-June 3, 2010. Proceedings 29, pp. 1-23. Springer, 2010.
Ma, J., Zheng, Y., Feng, J.. Zhao, D., Wu, H., Fang, W., Tan, J., Yu, C., Zhang, B., and Wang, L. (SecretFlow- SPU}: A performant and (User-Friendly) framework for Privacy-Preserving machine learning. In 2023 USENIX Annual Technical Conference (USENIX ATC 23), pp. 17-
Kolesnikov, V. and Kumaresan, R. Improved ot extension for transferring short secrets. In Advances in Cryptology- CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22. 2013. Proceed- ings, Part II. pp. 54-70. Springer, 2013.
33, 2023.
Miao, X., Oliaro, G., Zhang, Z., Cheng, X., Wang, Z., Zhang, Z., Wong, R. Y. Y., Zhu, A., Yang, L., Shi, X., et al. Specinfer: Accelerating large language model serv- ing with tree-based speculative inference and verification.
Leiter, C., Zhang, R., Chen, Y., Belouadi, J., Larionov, D., Fresen, V., and Eger, S. Chatgpt: A meta-analysis after 2.5 months. arXiv preprint arXiv:2302. 13795, 2023.

---

An Efficient Private GPT Never Autoregressively Decodes
In Proceedings of the 29th ACM International Conference Architectural Support for Programming Languages and Operating Systems, Volume 3. pp. 932-949, 2024a.
Tay, Y., Dehghani, M., Rao, J., Fedus, W., Abnar, S., Chung, H. W., Narang, S., Yogatama, D., Vaswani, A., and Metzler, D. Scale efficiently: Insights from pre- training and fine-tuning transformers. arXiv preprint arXiv: 10686, 2021.
Miao, X., Oliaro, G., Zhang, Z., Cheng, X., Wang, Z Zhang, Z.. Wong, R. Y. Y., Zhu, A., Yang, L., Shi, X., et al. Specinfer: Accelerating large language model serv- ing with tree- bree-bsed speculative inference and verification. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3. pp. 932-949, 2024b.
Touvron, H.,, Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. Llama: Open and efficient foundation lan- guage models, arXiv preprint arXiv:2302.1397/ 2023.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. At- tention is all you need. Advances in neural information processing systems, 30, 2017.
OpenAI. Api pricing, 2025. URL https::///// //pttp:://ppeai... com/ hptp///pppprc.g/..../m/
Pang, Q., Zhu, J., Möllering, H., Zheng, W., and Schnei- der, T. Bolt: Privacy-preserving, accurate and efficient inference for transformers. In 2024 IEEE Symposium Security and Privacy (SP), pp. 130-130. IEEE Computer Society, 2024.
Wen, K., Li, Y., Liu, B., and Risteski, A. Transformers are uninterpretable with myopic methods: a case study with bounded dyck grammars. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc.
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, J. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21 (140):1-67, 2020.
Wenzek, G., Lachaux, M.-A., Conneau, A., Chaudhary, V., Guzmán, F., Joulin, A., and Grave, E. CCNet: Ex- tracting high quality monolingual datasets from web crawl data. In Calzolari. N., Béchet, F., Blache, P., Choukri, K., Cieri, C., Declerck, T., Goggi, S., Isahara, H., Maegaard, B., Mariani, J., Mazo, H., Moreno, A.. Odijk, J., and Piperidis, S. (eds.), Proceedings of the Twelfth Language Resources and Evaluation Conference, Marseille, France, May 2020. European Language Resources Association. ISBN 979-10-95546- 34-4. URL ttttps:s/aclaatthl..oo.. http:/tthww..ooooog/...gg 20000000000 2020. 1rec-1.499 494.
Ran, R., Luo, X., Wang, W., Liu, T., Quan, G., Xu, X., Ding, C., and Wen, W. Spenenn: orchestrating encoding and sparsity for fast homomorphically encrypted neural net- work inference. In International Conference on Machine Learning, pp. 18718-28729 PMLR, 2023.
pp.
Rathee, D., Schneider, T., and Shukla, K. K. Improved mul- tiplication triple generation over rings via RLWE-based AHE. In Cryptology and Network Security, volume 1 11229 of LNCS, pp. 347-359. Springer International Publishing, 2019.
Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., et al. Huggingface's transformers: State-of-the-arr natural language processing, arXiv preprint arXiv: 191.::1110.03771, 2019.
Rathee, D., Rathee, M., Kumar, N., Chandran, N., Gupta, D., Rastogi, A., and Sharma, R. Cryptflow2: Practical 2- party secure inference. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 325-342, 2020.
Xu, T., Wu, L.. Wang. R., and Li, M. Privcirntt: Effi- cient private inference via block circulant transformation. arXiv preprint arXiv:2405. 14569, 2024.
Rathee, D., Rathee, M., Goli, R. K. K., Gupta, D., Sharma, R., Chandran, N., and Rastogi, A. Sirnn: A math library for secure rnn inference. In 202/ IEEE Symposium on Security and Privacy (SP), pp. 1003-1020. IEEE, 2021.
Yang, K., Weng, C., Lan, X., Zhang, J., and Wang, X. Ferret: Fast extension for correlated with small com- munication. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 1607-1626, 2020.
Tang, X., Shin, R., Inan, H. A., Manoel, A., Mireshghallah, F., Lin, Z., Gopi. S., Kulkarni, J., and Sim, R. Privacy- preserving in-context learning with differentially private few-shot generation. In The Twelfth International Con- ference on Learning Representations, 2024.
Yao, A. C.-C. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfes 1986), pp. 162-167, 1986. doi: 10.1109/ 1986..9...25.
12

---

An Efficient Private GPT Never Autoregressively Decodes
Yu, T., Zhang, R., Yang, K., Yasunaga, M., Wang, D., Li, Z., Ma, J., Li, I., Yao, Q., Roman, S., et al. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql sql task. arXiv preprint arXiv:1809)
2018.
Zeng, W., Li, M., Xiong, W., Tong, T., Lu, W.-j., Tan, J., Wang, R., and Huang, R. Mpevit: Searching for accurate and efficient mpe-friendly vision transformer with het- erogeneous attention. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 5052- 5063, 2023.
Zhao, W. X., Zhou, K., J., Tang. T., Wang, X., Hou, Y., Min, Y., Zhang, B., Zhang, J., Dong, Z., et al. A survey of large language models. arXiv preprint arXw:23333112223, 2023.
Zimerman, I., Baruch, M., Drucker, N., Ezov, G., Soceanu, O., and Wolf, L. Converting transformers to polynomial form for secure inference over homomorphic encryption. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, (eds.), Pro- ceedings of the 41st International Conference on Ma- chine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 62803-6288 62814. PMLR, 21-27 Jul 2024. URL https: : httpp//ooceengg..... mlr press/ v235 z rme rma 2 a. html.
13

---

An Efficient Private GPT Never Autoregressively Decodes
A. Background of the Generative Pre-trained Transformer (GPT)
focus on GPTs (Vaswani et al., 2017), such as Vicuna (Chiang et al., 2023) and FLAN-TS (Chung et al., 2024), These models are stacked with Transformer decoders, each consisting of an attention module and a feed-forward network (FFN) module.
Attention Module. The attention module starts with three independent linear layers Lineargke that project the input to three activation tensors: Q K, and V. The multi-head attention mechanism splits them into and computes the self-attention of all heads in parallel. The lea head computed through
Qth Kh (2xx4 (Vll va.
Attention (Q" K", vh) Softmax
(3)
vdk
where dy is the hidden dimension of the key activation. The outputs of different heads are concatenated and fed into another linear layer Linear,, with one residue connection and one normalization layer to generate the final output of the attention module.
FFN Module. The FFN module is composed of two linear layers Linear and Linear and activation layer ACT. The FFN module is computed as follows
FFN(X) X
Linear,,, (ACT(Linear,,, (X))),
(4)
where ACT can be many variants, such as ReLU, GELU, and SiLU Similar the attention module, its output needs a residue connection and normalization layer.
Embedding Layer. The embedding layer is positioned at the beginning of the GPT. In this layer, each token is mapped from its index in the vocabulary to a fixed-size vector. Given that transformers do not possess inherent sequence awareness, positional encodings are incorporated into the token embeddings to convey information regarding the order of tokens within the sequence.
Sampling. The final task head in GPT predicts the output distribution of the subsequent token given an input prefix. This task head generally comprises linear layer that projects the hidden states from the final transformer decoder the dimensionality of the vocabulary, along with Softmax function that normalizes the resulting probability distribution. Then, the next token is sampled from the distribution. While various sampling methods exist, such as top-k and temperature settings, they can all be conceptualized as standard sampling from an adjusted original probability distribution. For instance, argmax sampling is equivalent to zeroing out all non-maximal elements the distribution and normalizing the result. Thus, we can concentrate exclusively on standard sampling from a probability distribution.
Prefill and Decoding Phase. The prefill phase begins text generation when GPT processes the initial input prompt. All input tokens fed into the GPT during the prefill phase. The model generates comprehensive set of probabilities for each input token. However, in both the prefill and subsequent decoding phases, only the final output distribution is of interest, as this represents the likelihood of generating the next token based on the provided input context. Consequently, the prefill phase generates the output distribution for the subsequent token and initializes the key-value (KV) cache. The KV cache prevents re-computing the representations of all previous tokens when decoding a new token. stores the keys and values associated with earlier tokens, thereby preserving the contextual information required for generating the following token.
The decoding phase generates tokens sequentially using the context from the prefill and previously generated tokens. With the presence of the KV cache, the model computes the output distribution for the token each decoding step and updates the information within the KV cache accordingly.
B. Complete POST Protocols
This section gives the full version of the Post approach, including the process of public decoding, secure verification, and the re-sampling of the "bonus" token.
14

---

An Efficient Private GPT Never Autoregressively Decodes
Algorithm 2 Full Algorithm of one decoding step using PoST
Input: Ps (server) holds private model Mp and generates Pe (client) holds prefix 2<r and public model Mg. Public
parameters include draft length 7y. The vocabulary size is V. The [y] means [0, 1, :.)
1: for i E [n]. Pa do
2: q(x (xct+i) = M,(prefir + (1=1)),
3: 2y ~ q(x (z<(+t)).
4: end for
5: P. and Pe parallely compute (p(x) I<t)),, (p(2r x<(tr)) Mp((prefta))...... (prefix ; ((2 (x())
(p(x (<(1))
6: Pe Q=
Ps and P. set (P)=
((x I<C+>-1)
(p(x (x(e=)))
7: Pa generates random vector Ronut (0, 1)7xv.
8: P. sets his share of (S), - (P)s and Po sets her share (S) Q P.Rul (P)c mod 2
9: for E [t]. in parallel do
10: Pa generates a random vector r ~ Zge. and masks his share as (S(1, = (S]i, :1s - -r( mod 2
11: Pa chooses the secret share by x:)), (9) OTo((S(iiS)))) (i, :), v4).
12: Ps sets his share [s) r[i] and Pe sets her share (s).li] = (S mille + (S xzI), mod 2
13: end for
14: P. and Pa compute shares of boolean vector (n) Fiess (0, (s)) and open Pa.
Pe appends an element one at the end by n -n [1]
16: P. computes & min (fi i E n(j] = 1}).
17: Pe chooses (#)), (7T1) ([pp( z<s)).. (p(x xcctr))e),
18: Pe reconstructs P& (a) = (px( + (p& (x))e.
19: if k < y then
20: Pe computes p(() = max(0, (x) 9x(2))
else if = 7 then
Pe sets pzx) = (x))
23: end if
24: Pe samples 2ạ ~ p' (z).
Output: Pe obtains fizfiz iz + IrI,..., rz).
C. Correctness of the Secure Sampling Protocol
Speculative sampling samples token from private model's output distribution p(x) and public model's 's output distribution ((x). In the original algorithm, the token proposed by the public model is rejected according to the following probability
p(ā) (())
max(0,
(5)
where à is the token index sampled from the output distribution of the public model. Next, we show that the protocol exactly follows the original functionality.
We first show the correctness of refactoring division multiplication. The original rejection to sample uniform random
15

---

An Efficient Private GPT Never Autoregressively Decodes
number r [0, 1], and reject token if max(0,
p()) [(2)
An equivalent way is to compute
(())
r < max
0, 1
(6))
1, p
2 min
((:)
1, p())
(6)
2 min
(())
2 p())
(()
r (+) 2 p(.).
The equivalence of second line and third line is because r and 1 r follow the same distribution when E [0,
1]. The
equivalence of the conditions in line and line is established through two cases based on the range of p(a) the min() function can be directly removed; p())
p( [0. 1].
{(a)
((
v(2) E (1, oo), the third line simplifies to r > 1. Since r is drawn from a uniform distribution over the interval [0. 1]. the conditions in both line 3 and line 4 are never satisfied. Consequently, the equivalence remains valid. The final line shows the correctness of the refactoring regarding one draft token. The correctness
of the protocol is obtained easily by extending the result to all proposed tokens.
For the selection then comparison, the correctness directly follows the original algorithm that computes the comparison results of the target element in the score matrix S.
D. Security Analysis of the Secure Sampling Protocol
This section proves that secure inference on POST maintains the same privacy goal as the standard GPT decoding, i.e., the client only learns the model's output distribution, and the server learns nothing. The security analysis can be categorized into two parts: security within the MPC protocol and security outside the MPC protocol.
For the data processed using MPC protocol, both the client and the server learn nothing. Our protocol calls the underlying cryptographic protocols a black box, which is the same as the common practice of secure inference works. Such black-box usage of the cryptographic protocols makes security straightforward and achieved according to the composability of cryptographic protocols.
A tricky part in our protocol is that we use the same random ring number to mask one row of the score matrix S. This is not secure in other cases as :] -r r mod 2 makes the relative difference leaked. Fortunately, the client in our mod 2 and prevents such leakage.
protocol only learns only one element Sli,
For public values outside MPC, we show they do not reveal additional information than standard GPT inference. First, there is nothing else to prove for the client's security since the server does not receive any messages in our protocol. Second, to prove the server's security, we compare the information revealed to the client in the standard decoding and POST. We first give some notations. In the standard secure GPT decoding, for prefix X the client can autoregressively obtain y output distributions p(æ ...).... .(z (x(et)) of the private model, from which the client samples tokens Zi,..., In the POST, the client learns the rejection boolean of all draft tokens and the private model's output distributions p(x: x<(+)) of the first rejected token. The output distribution is the final output, which is also revealed the client in the standard decoding. The indexes of rejected tokens learns which token is generated in the standard decoding. For example, for the ith generated token, the client can always know that the proposing draft token F, will receive acceptance while any other token will receive rejection.
direct result when the client
A more beneficial result is that PoST only lets the client obtain a subset of information than the standard secure decoding. The client only obtains output distributions p( &<(+)). For other accepted tokens, it is equivalent that the client only learns the Top1 element of the corresponding output distribution. This is in contrast to the standard decoding, where the client can learn the output distribution's 's TopK elements (usually K=5). In this way, the client information of POSt is subset of those in the standard decoding.
16

---

An Efficient Private GPT Never Autoregressively Decodes
Lenghhi
Lengthw2 Langhhid
Length Longthw22 26
155
Length-18
Time
10
Lineatzy Linsor, Linears
Lineaf, Softmax
GELU
OK
Total
Uncofge Linears
Lindar, Lnoar, Sofmax
GELU
OK
Total
(a) Bandwidth 3000 Mhps and one-way delay ms.
(b) Bandwidth 1000 Mhps and one-way delay 10 ms.
Length e]
L Lenghh--16 16
50
Lengthei
Length -B
Length-22 =2
Longth-
Time
Longth wd
Length
20
10
Linedr Lieet,
Lineat, Linent, mak GEUU
OK
Total
Uneeraas Unner,, Linesr, Lineer, Softmax GRLU
OK?
Total
(c) Bandwidth 400 Mbps and one way delay 40 ms.
(d) Bandwidth 200 Mbps and one-way delay 80 ms.
Figure 6. The latency of each layer against different input input lengths. We show the results of GPT-2 on EzPC frameworks.
Lengthi2 Lengthin
Length=16
Toue
Time
Lenghhoee
0.2
Lineo Linear, Linear, Linen,, Softmax GELU
PV
14
Tooal
Liner Liniar, Linear,, Linear, Softmax GELU
PV
LN
Total
(a) Bandwidth 3000 Mhps and one-way delay ms.
(b) Bandwidth 1000 Mbps and one-way delay 10 ms.
Lengthel
Lengthel
Length
Time 64
Longth-2 Longthed
Longth-16
Longth-15
Linaare: Undor,
Linears Linears, Softmax
GfL.
PV
1N
Total
Lindrre Linear, Linear, Linear, Softmax GELU
OK'
PV
LN
Total
(c) Bandwidth 400 Mbps and one-way delay 40 ms.
(d) Bandwidth 200 Mbps and one-way delay 80 ms.
Figure The latency of each layer against different input input lengths. show results GPT-2 on SecretFlow-S frameworks.
E. More Experiments
E.1. Latency Insensitivity to the Input Length
For the decoding of GPT, the input length of the operators is only Section 3.2 observes that the latency of cryptographic protocols is insensitive to input length at such minimal input length. This section presents additional results to further substantiate the observation. Our experiments encompass the following aspects.
Network Conditions: We employ four network conditions to simulate different Local Area Network (LAN) and Wide Area Network (WAN) scenarios, specifically varying bandwidth and one-way delay. The configurations are as follows: (3000 Mbps, ms), (1000 Mbps, 10 ms), (400 Mbps, 40 ms), and (200 Mbps, ms).
GPT Sizes: In secure inference studies, many existing works focus models comparable in size to GPT-2. Since models of such size are the closest to the practical usage of secure inference, we also include the GPT-2 model to illustrate our observations. Additionally, we incorporate two larger language models: FLAN-T5-XL (3 billion parameters) and Vicuna-7B.
Secure Inference Frameworks: We leverage two well-established frameworks: EzPC (Chandran et al., 2017) and SecretFlow-SPP (Ma et al., 2023). These frameworks utilize different underlying primitives and protocols for both linear and nonlinear layers.
For the EzPC framework, we adopt the state-of-the-at work BOLT (Pang et al., 2024), which implemented in EzPC, to profile the layers. The HE protocol employed BOLT implements matrix multiplication through Number
17

---

An Efficient Private GPT Never Autoregressively Decodes
Lenghe1 Length+2 Lenghhid
Length Longth-28 16
Lenghhe Langtri2
Lengthe8 Length=15
10
Timee
Lenghhoe
19
Linaaro Linear, Linears
Lineaf, Softmax
SIUV
OK
1.4
Total
Lincafge Lineal, Lindor, Lnoar,, Softmax
SLU
OK'
Total
(a) Bandwidth 3000 Mbps and one-way delay ms.
(b) Bandwidth 1000 Mhps and one-way delay 10 ms.
10.0
Length-]
Lengttos Lenghti116
Length-2
Longth=15
Longth m4
40
Time
Time
2.5
Unnetess Lineat, Lires, Linedt, Softmax
OK'
Uneeras, Unnerr, Linesr, Linear, Softmax 5010
OK?
Total
(c) Bandwidth 400 Mbps and one-way delay 40 ms.
(d) Bandwidth 200 Mbps and one-way delay 80 ms.
Figure 8. The latency of each layer against different input input lengths. We show the results of Vicuna-7B 7B on SecretFlow-Ste SPU frameworks.
1.00
Length-33
0.75
Length
Lengthwe
0.30
0.2
0:30
Unwelgs Linaa,, Linwar,
Solomax
GEUU
PV
LN
Total
Lirmatqu Linmer,
Linvert
Solkmax
GEL
OK?
PV
LN
Total
(a) Bandwidth 3000 Mbps and one-way delay ms.
(b) Bandwidth 1000 Mbps and ine-way delay 10 ms.
Longthw]
Langth-1
Length-8 Length-
Length-2
120
Lengtha2
Time
Lengthed
5.0
0.0
Untoreu Linerr, Unee, Uneor Saftmax GELU
PV
UN
Total
Untor Unear, Unear, Ureer Saftmax GELU
PV
LN
Total
(c) Bandwidth 400 Mbps and one-way delay 40 ms.
(d) Bandwidth 200 Mbps and one-way delay 80 ms.
Figure The latency each layer against different input input lengths. show results of FLAN-TS-XL on SecretFlow-SPU
frameworks.
Thcoretic Transform (NTT) encoding. Both polynomial approximation and lookup tables are utilized to evaluate the nonlinear layers. The underlying OT protocol (Kolesnikov & Kumaresan, 2013) an enhancement of the IKNP-OT protocol (Ishai al., 2003). We only present profiling results for GPT-2 within the EzPC framework, BOLT's implementation does not support larger model sizes.
For the SecretFlow-Se SPU framework, we utilize the state-of-the of-the-art works BumbleBee (Lu al., 2025) and Nimbus (Li et al., 2024b) conduct experiments. They employ coefficient encoding for linear layers and piecewise polynomial functions for nonlinear layers. The underlying OT protocol in SecretFlow-SPU is the Ferret-OT (Yang et al., 2020).
Across various settings, we observe a consistent insensitivity of latency to input length. When comparing the latency for input lengths of 16 and 1, the observed ratio ranges from 1.07 ~ 1.77x. x Next, we give a detailed analysis from different perspectives.
In examining four distinct network conditions, we note that latency increases more noticeably under optimal network conditions. For example, when comparing the latency for input lengths of and 16 at bandwidth of 3000 Mbps and latency of ms, the increasing ratio varies from 1.26x ~ 1.77x. In the case of 1000 Mbps and 10 ms, the increasing ratio ranges from 1.21x ~ 1.55x. For 400 Mbps and 40 ms, the ratio ranges from 1.21x ~ 1.43x, while for 200 Mbps and 80 ms, it 1.07 ~ 1.40x. The reason can attributed to the less significant one-way delay under good network conditions. Given that one-way delay is completely invariant to input length, its reduction will render overall latency more sensitive to input length variations.
18

---

An Efficient Private GPT Never Autoregressively Decodes
When comparing different frameworks, find that the EzPC framework exhibits greater insensitivity than the SecretFlow- SPU framework. This discrepaney is partly attributable to the implementation methods of the cryptographic protocols. The SecretFlow-SPU sometimes splits data and overlaps communication with computation. We find that increase in input length may necessitate additional rounds of communication, which consequently increases one-way delay time about input size. In contrast, the EzPC framework maintains constant communication rounds regardless of input length.
Regarding different model sizes, smaller models demonstrate greater insensitivity compared to larger models. For instance, in the case of GPT-2, both the EzPC and SecretFlow-St frameworks exhibit nearly unchanged layer latencies. This phenomenon because smaller models have smaller hidden dimensions, requiring greater input lengths to produce a noticeable increase in latency. However, the Softmax layer is exception, it is applied tensor whose size relates solely to the KV cache size.
E.2. Detailed Analysis for Different Layers
We also provide detailed analysis of the different layers. The layers be generally categorized into linear and nonlinear layers.
Linear Layers. We first discuss the matrix multiplication between the plaintext weights and ciphertext activations, including Linearglv Linear,, Linearh1, and Linear The required operation includes one matrix multiplication and one truncation. Overall, the most cost is spent on the homomorphic operation, including the encryption, decryption, and multiplication of the polynomial ring. As we have explained in Section 3.2, the computation and communication efficiency of the SIMD HE operations heavily depends the number of activations. The typical degree 8192 of the polynomial ring allows 8192 values to be operated in parallel. However, the single activation vector in the standard decoding is insufficient to fully utilize the slots in the polynomial ring, especially for the small model GPT-2. Existing works typically adopt packing methods to improve the utilization ratio of the slots. For example, the BOLT packs multiple input activation vectors into one plaintext polynomial. The polynomial is then encrypted and sent to the server for computation. In the Nimbus, the output ciphertext is packed into one and re- shared between parties. Therefore, when increasing the input length, the computation and communication efficiency can be improved, leading to sublinearly increased communication and computation times.
Similar rules also hold for the matrix multiplication between activations, including QKT and PV. Consider the multiplication between secret matrices X and Y, is computed by XY (X) (X), + (Y), + (Y)) s- The problem is transformed into two instances of plaintext-ciphertext multiplications of the two cross terms, which is the problem mentioned in the above paragraph. The low utilization of the SIMD operation is more significant for the activation matrix multiplication due to the multi- head mechanism. The hidden dimension of the matrix multiplication is further divided by the head number, leading to a lower utilization ratio and minimal sensitivity to the input length.
Nonlinear Layers. The nonlinear layers, including Softmax, GELU, SiLU, and layernorm. These layers are usually approximated by the piecewise polynomials that only include multiplication and comparison. Multiple truncations are also called reset the fixed-point precision after the multiplication. These nonlinear operations require numerous rounds of communication and transmitted data and are the main source of latency. Since the time spent the one-way delay is fixed despite the input length, when the input size is small, the time spent on the transmission is less significant than the one-way delay. This is much more obvious for the layernorm, as the reciprocal square root is only computed on one secret number for a whole vector. Almost all latency is spent on the one-way way delay. In this way, we observe the insensitivity of the overall latency.
19


Reviews:
[{"review_id": "6yOg8rGEDO", "reviewer": "Reviewer_SCbC", "summary": "To accelerate privacy-preserving inference, the authors propose a Public Decoding and Secure verificaTion (POST) approach that utilizes public GPT models, based on the observation that securely decoding one token vs. multiple tokens takes a similar latency.\nSince the efficiency of secure decoding depends on the acceptance rate of tokens proposed by the public model, they purpose two optimizations 1) a private sampling protocol specific to crypto primitives 2) model alignment using knowledge distillation. The optimized approach remains the same privacy level and generation quality while improving up to 6x speed up across different public-private model pairs.", "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": "We are grateful for the reviewer's appreciation of our efforts. Below, we respond to your constructive comments in detail.\n# Question 1: Could the author clarify the ambiguity in Line 90 in Introduction and the Line 27 in abstract?\nThank you for pointing out the potential ambiguity. We clarify it here and will revise the text to avoid any further confusion. Line 90 describes the whole POST approach, and line 27 refers to only the proposed sampling protocol.\n- In lines 90-92: We claim POST is compatible with mainstream 2PC protocols for Transformer models (e.g., BOLT [4], BumbleBee [2], Nimbus [3]) because the key observation: the latency insensitivity to input length holds across these protocols, for which we provide more experiments in Appendix F.\n- In line 27: We refer to the efforts of designing speculative sampling protocols in Section 4.2 to eliminate operations that are inefficient for cryptographic primitives.\n# Question 2: Line 292: Could the author clarify why the $2^l$ complexity is considered acceptable?\nThe $O(2^l)$ term in the comparison protocol's overhead represents a special case with maximal communication size but minimal communication rounds [1]. Since we focus on optimizing the number of comparison calls rather than the protocol itself, we use this special case as a simplification for easier understanding, and the footnote on page five writes the general form $O(q \\cdot 2^m)$ of communication complexity, where $q*m=l$. Here, $O(2^l)$ corresponds to use $q=1$. Larger $q$ reduces communication size but increases rounds. Existing works [2,3] typically choose $q=8$ to balance this trade-off, which we also adopt in experiments. In this way, bit width only partly contributes to exponential complexity. \n# Question 3: What is the underlying rationale for selecting two pairs from different series?\nWe design two kinds of experiments to show the effectiveness in different cases.\n- Same-series models: This is the favorable setting in practice, as private models often have open-source smaller versions, which can achieve speedups of 4.2X–6.0X.\n- Different-series models: This is to highlight robustness  and general applicability. Even in less favorable conditions, we still have speedups of 2.1X–4X.\n# Question 4: What dataset was used for the knowledge distillation? Whether the acceptance rate is influenced by any similarities between the alignment dataset and evaluation dataset.\nIn this work, the alignment dataset is randomly sampled from the downstream training dataset. As explained in Sec. 4.3, the rationale for using similar datset is the case when client uses relevant public datasets or generates sanitized datasets from his queries (e.g., via differentially private generation [5,6] that preserves utility while removing sensitive information).\n\nOur experiments show that alignment dataset similarity to the downstream task impacts the acceptance rate. For instance, testing Vicuna-7B and LLaMA-160M with an irrelevant alignment dataset, Alpaca [7], to the evaluated tasks. \n\n||Not-aligned|Irrelevant-aligned|Relevant-aligned|\n|-|-|-|-|\n|SP|0.302|0.372|0.592|\n|GS|0.536|0.602|0.691|\n|CP|0.405|0.463|0.665|\n|FN|0.576|0.595|0.650|\n\nDirectly using a non-aligned public models yields a 1.4X–2.3X speedup, while non-relevant dataset slightly improves it to 1.6X–2.5X. The best results (2.5X–2.9X speedup) occur when using a similar alignment dataset. Thus, we recommend selecting an similar alignment dataset for higher acceptance rates.\n# Question 5: Despite the use of different methodologies, I would appreciate a performance comparison with related work.\nSorry for any confusion regarding our experimental setup. In fact, the speedup in Figure 5 is the comparison with the latest work, both with and without the integration of our method. The baselines are the SOTA 2PC secure inference works for Transformer, as detailed in Line 366, including the linear layer protocol from Nimbus [1] and the non-linear layer protocol from BumbleBee [2]. We will further clarify this in the paper.\n# Question 6: The contribution of this work may be considered incremental since it primarily utilizes standard techniques such as knowledge distillation and batching multiple tokens.\nOur key contributions include being the first to introduce observations on public models and latency insensitivity to input length. The novel paradigm (public decoding and secure verification) is not merely a standard batching technique but a strategically designed approach based on these insights. Additionally, we optimize this paradigm not only through knowledge distillation but also with a specialized sampling protocol.\n# Reference\n[1] Cryptflow2, CCS 2020\n\n[2] Bumblebee, NDSS 2025\n\n[3] Nimbus, Neurips 2024\n\n[4] Bolt, S&P 2024\n\n[5] Dp-opt: Make large language model your privacy-preserving prompt engineer, ICLR 2024\n\n[6] Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation, ICLR 2024\n\n[7] https://github.com/tatsu-lab/stanford_alpaca", "claims_and_evidence": "page 2 col 1 line 90-92: “This approach broadly applies across different cryptographic protocols and GPT models, where we observe similar insensitivity.“\nIn the paper,  the authors clarify how the approach is applied to versatile GPT models, but it’s not clear to me how it can be applied to different cryptographic protocols. Specifically, in the abstract, the authors mention that the speculative sampling protocol is specific to crypto primitives.", "methods_and_evaluation_criteria": "I really enjoy reading the motivation section. The two observations clearly motivate the later-on approaches to optimize the decoding phase in the generation process.", "theoretical_claims": "* There is the proof for the correctness of the sampling protocol (in the appendix although) and also security analysis for privately reject draft tokens and knowledge distillation.\n* page 6 col 1 line 292: it appears that the complexity remains substantial since 2^l represents the size of the field. Could the author clarify why this level of complexity is considered acceptable?", "experimental_designs_or_analyses": "* The experimental design effectively addresses my initial questions from the 'methods' section, specifically regarding the runtime of the knowledge distillation process and the accuracy improvement post-alignment.\n* Could the author elaborate on the choice of the three pairs of public and private models? I understand the inclusion of pairs from different series (the first two pairs) and a pair from the same series (the third pair). However, what is the underlying rationale for selecting two pairs from different series?\n* What dataset was used for the knowledge distillation? I am curious whether the acceptance rate was influenced by any similarities between the dataset used for alignment and the dataset used for evaluation.\n* Despite the use of different methodologies, I would appreciate a performance comparison with related work.", "relation_to_broader_scientific_literature": "While other works mainly optimize the protocols or modify the model architectures, this work is complementary to those works and can be integrated for further performance.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: The experiment is well-designed and effectively demonstrates the enhancements achieved through the proposed methodologies.\n\nWeaknesses: The contribution of this work may be considered incremental since it primarily utilizes standard techniques such as knowledge distillation and batching multiple tokens.", "other_comments_or_suggestions": "Typos or Comments:\n\tpage 1 col 2 line 9: missing space after the parenthesis “Pang et al., 2024)lever-“", "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": "H9pTLqISVs", "reviewer": "Reviewer_PJwW", "summary": "This paper focus on secure inference on GPT, and presents POST, which contains (1) a private sampling protocol optimized for cryptographic primitives and (2) model alignment using knowledge distillation to speedup the secure inference. Experiments demonstrate speedup compared to standard decoding across three pairs of public-private models and different network conditions.", "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 thorough examination and thoughtful feedback on our paper. We address the main concerns as follows.\n# Question 1: In Appendix D, the authors try to prove the division can be refactored as multiplication. However, it is not stated what is the range of p(x)/q(x). Therefore, I am not sure whether the claim is correctly proved.\nWe provide an explanation here and will include more detailed explanations for the derivation in Appendix D to ensure it is easy to follow.\n\nEquation (6) derives the equivalent condition for determining whether a token should be rejected. We assume the reviewer’s concerns is about the elimination of the $min()$ function in the third line $r \\geq \\min \\left(1, \\frac{p(\\hat{x})}{q(\\hat{x})}\\right)$. The equivalence of the conditions in line 3 and line 4 is established through two cases based on the range of $\\frac{p(\\hat{x})}{q(\\hat{x})}$. \n- $\\frac{p(\\hat{x})}{q(\\hat{x})} \\in [0,1]$: The $min()$ function can be directly removed, as stated in Equation (6). \n- $\\frac{p(\\hat{x})}{q(\\hat{x})} \\in (1,\\infty)$: The third line simplifies to $r>1$. Since $r$ is drawn from a uniform distribution over the interval $[0,1]$, the conditions in both line 3 and line 4 are never satisfied. Consequently, the equivalence remains valid.\n\nIf you have any further questions, please feel free to let us know.\n\n\n# Question 2: If the alignment dataset closely resembles the private dataset (line 303-304), how to evaluate the potential privacy leakage?\nLine 303 discusses the case in which the server provides the aligned public model. We assume the concern is about the open-source aligned public model incurring potential privacy leakage of the alignment dataset. This issue is independent of this work and widely exists. For instance, the base model used for alignment, open-source smaller versions of private models, can similarly expose privacy risks related to the pre-training dataset (private dataset). Such kind of issue can be resolved using the well-established framework known as differential privacy [1]. Differential privacy preserves the utility of the training data while anonymizing it with metrics that quantify the upper bound of privacy leakage. In our alignment scenario, if the alignment data resembles the private dataset (for instance, including private information), the direct use of the original dataset for training is avoided. Instead, a sanitized aligning dataset is generated [2,3], or differential privacy is applied during the gradient descent process [4].\n\nMoreover, the potential for privacy leakage in our alignment is more manageable compared to the potential leakage of pre-training datasets from open-source small models. This is because the alignment's objective is to let the public model mimic the output distribution of easily predicted tokens. This makes the requirements on the alignment dataset much smaller than traditional training: a very small number of data is sufficient (Figure 4), and alignment on simple tokens rarely involves sensitive information.\n\nTo avoid any privacy leakage, a cautious server can choose to use relevant publicly available datasets or not provide the alignment. This may result in slightly slower performance, but thanks to our speculative sampling protocol, even non-aligned public models still achieve a 1.5X to 5X speedup.\n\n[1] The Algorithmic Foundations of Differential Privacy, Foundations and Trends in Theoretical Computer Science 2014\n[2] Dp-opt: Make large language model your privacy-preserving prompt engineer, ICLR 2024\n[3] Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation, ICLR 2024\n[4] Deep learning with differential privacy, CCS 2016\n\n# Question 3: Lack experimental comparison with prior works (such as CipherGPT and SIGMA) on secure GPT inference. Despite that the author claims the proposed work is orthogonal to prior works, it is worth to show at least one combination to verify this claim.\nSorry for any confusion regarding our experimental setup. In fact, the speedup in Figure 5 is the comparison with the latest work, both with and without the integration of our method. The baselines are the SOTA 2PC secure inference works for Transformer, as detailed in Line 366, including the linear layer protocol from Nimbus [1] and the non-linear layer protocol from BumbleBee [2]. We will further clarify this in the paper.\n[1] Bumblebee: Secure two-party inference framework for large transformers, NDSS 2025\n[2] Nimbus: Secure and efficient two-party inference for transformers, Neurips 2024\n\n# Question 4: Improve Figure 3 for better clarity. \nThank you for the valuable suggestion. We will enhance Figure 3 to improve its clarity. For example, we will highlight the workflow of the secure inference process, emphasizing the distinctions between our approach and prior works. We will also illustrate the appearance of the \"draft token\" and \"bonus token\" throughout the process to provide a clearer understanding.", "claims_and_evidence": "1. In section 4.2, the author claims that the division is refactored into multiplication (line 267). It is unclear why this can be done. The proof in Appendix D lacks showing the range of p(x)/q(x).\n\n2. In this paper, the author introduces the alignment of public model and private model. If the alignment dataset closely resembles the private dataset (line 303-304), how to evaluate the potential privacy leakage? No evidence is provided towards this.", "methods_and_evaluation_criteria": "The proposed methods and evaluation make sense.", "theoretical_claims": "In Appendix D, the authors try to prove the division can be refactored as multiplication. However, it is not stated what is the range of p(x)/q(x). Therefore, I am not sure whether the claim is correctly proved.", "experimental_designs_or_analyses": "1. This paper lacks experimental comparison with prior works [1-2] on secure GPT inference. Despite that the author claims the proposed work is orthogonal to prior works, it is worth to show at least one combination to verify this claim.\n\n[1] Hou, X., Liu, J., Li, J., Li, Y., Lu, W.-j., Hong, C., and Ren, K. Ciphergpt: Secure two-party gpt inference. Cryptology ePrint Archive, 2023.\n\n[2] Gupta, K., Jawalkar, N., Mukherjee, A., Chandran, N., Gupta, D., Panwar, A., and Sharma, R. Sigma: secure gpt inference with function secret sharing. Cryptology ePrint Archive, 2023.", "relation_to_broader_scientific_literature": "The proposed POST is in parallel with prior methods [1-3] in the field of secure inference of GPT, which is a strength of this paper. This paper also discussed recent secure inference on GPT in Appendix B.\n\n[1] Hao, M., Li, H., Chen, H., Xing, P., Xu, G., and Zhang, T. Iron: Private inference on transformers. Advances in Neural Information Processing Systems, 35:15718–15731, 2022.\n\n[2] Zeng, W., Li, M., Xiong, W., Tong, T., Lu, W.-j., Tan, J., Wang, R., and Huang, R. Mpcvit: Searching for accurate and efficient mpc-friendly vision transformer with heterogeneous attention. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 5052–5063, 2023.\n\n[3] Lu, W.-j., Huang, Z., Gu, Z., Li, J., Liu, J., Ren, K., Hong, C., Wei, T., and Chen, W. Bumblebee: Secure two-party inference framework for large transformers. Cryptology ePrint Archive, 2023.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength: The motivation section is well-written and intriguing. Showing latency breakdown in terms of one-way delay, transmission and computation is critical to the community.", "other_comments_or_suggestions": "A minor comment about clarity: Figure 3 is not clear enough for illustrating the proposed methods of this work. There is no information about where the secure inference happens, no input to the private model and public model, not showing 'draft tokens', 'bonus token'. I suggest the authors to enrich Figure 3 and present more details. As the authors claim the proposed POST is an orthogonal approach to prior works (in line 33), it is important to make the framework clearly visualized. Current Figure 3 does not help understand the paper.", "questions_for_authors": "In this paper, the author introduces the alignment of public model and private model. If the alignment dataset closely resembles the private dataset (line 303-304), how to show/evaluate/quantify whether there is privacy leakage?", "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": "aghcalt30a", "reviewer": "Reviewer_je2K", "summary": "The paper proposes an efficient method for secure inference in generative pre-trained transformer (GPT) models by replacing the traditional autoregressive secure decoding process with a Public decOding and Secure verificaTion (POST) approach. The POST method leverages publicly available GPT models to generate multiple candidate tokens in plaintext, which are then verified securely against a private model. The authors optimize this process through speculative sampling and knowledge distillation, significantly improving token acceptance rates. Their approach achieves between 2.1× and 6.0× speedups compared to traditional secure decoding, without compromising privacy or output quality.", "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 the reviewer's appreciation of our efforts and valuable feedback on our paper. We address the main concerns as follows.\n# Question 1: The approach relies on the acceptance ratio achieved by the public model; if the alignment is suboptimal, the speedup may diminish.\nOur experiments demonstrate a consistent acceptance ratio and speedup across three pairs of models and four tasks. Even under suboptimal conditions, such as utilizing a small, irrelevant public model, the alignment achieves acceptance ratios of 50%–70% (corresponding to a speedup of approximately 2X–3.3X). When employing a small model from the same series, the acceptance ratios improve to 75%–82% (corresponding to a speedup of around 4X–5.5X).\n\nFurthermore, as discussed in Line 293 and Line 370, the acceptance ratio has greater potential than what the experimental results suggest. For instance, our experiments only adopt the 68M or 160M GPT models as the public model. As client-side computational capabilities continue to advance, it is anticipated that the acceptance ratio will increase through the utilization of larger and more powerful public models. Additionally, our experiments only use a very small alignment dataset and do not involve extensive hyper-parameter searching. A more thorough alignment process is expected to yield higher acceptance ratios, particularly if the server provides a more appropriately aligned public model, benefiting from its insights into the training datasets and access to enhanced computational resources.\n\n# Question 2: The complexity of the secure verification protocol may present implementation challenges in real-world deployments.\nThe proposed approach reduces the execution time of secure inference by a factor of 2X to 6X, while preserving the same levels of security and accuracy. Although this introduces some additional implementation complexity, we are willing to mitigate this challenge by open-sourcing our implementation.\n\n# Question 3: Additional exploration of scalability with larger vocabulary sizes or more diverse model architectures would be beneficial.\nThank you for your advice on the scalability analysis. Currently, our experiment includes three pairs of model architectures and four tasks. We focus on these aspects as they are most relevant to the proposed approach. Regarding vocabulary size, we utilize a vocabulary consisting of approximately 30,000 tokens, which provides comprehensive token coverage and is commonly adopted by popular LLMs. The existing experiments are sufficiently convincing to demonstrate the effectiveness of our method, but we are willing to include additional experiments to further justify the scalability concerning vocabulary size and model architectures in our next version.", "claims_and_evidence": "The authors provide convincing evidence supporting their claims of increased inference efficiency and maintained privacy through extensive experimental validation. The speedup claims (2.1× to 6.0×) are backed by thorough performance measurements under different model pairings (Vicuna-7B/LLaMA, FLAN-T5-XL/T5-efficient, FLAN-T5-XL/FLAN-T5-small&base) and network scenarios (LAN/WAN).", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate and justified. The authors select a range of representative models (small and large GPT variants) and tasks (text-to-SQL, mathematical reasoning, code generation, finance QA) to demonstrate the broad applicability and effectiveness of their method. The benchmark datasets are standard and widely used, making the evaluation meaningful.", "theoretical_claims": "The theoretical claims (such as those related to speculative sampling) have been reviewed. The provided protocol for speculative sampling is logically sound, clearly described, and addresses critical performance bottlenecks inherent in secure computation.", "experimental_designs_or_analyses": "The experimental designs are sound and rigorous. The authors provide detailed latency analyses, clearly attributing observed performance improvements to their methodological innovations. The breakdown of latency components (communication, computation, transmission) further reinforces the validity of their findings.", "relation_to_broader_scientific_literature": "It clearly outlines differences from related approaches, such as BumbleBee, Nimbus, and other cryptographic optimizations, emphasizing the novelty of leveraging public GPT models for secure verification.", "essential_references_not_discussed": "The references discussed appear comprehensive.", "other_strengths_and_weaknesses": "Strengths:\n- Clearly articulated motivation and innovative use of public models for secure verification.\n- Strong experimental validation demonstrating significant practical improvements.\n- Practical protocol optimization for cryptographic operations enhancing real-world applicability.\n\nWeaknesses:\n- The approach relies on the acceptance ratio achieved by the public model; if the alignment is suboptimal, the speedup may diminish.\n- The complexity of the secure verification protocol may present implementation challenges in real-world deployments.\n- Additional exploration of scalability with larger vocabulary sizes or more diverse model architectures would be beneficial.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "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": "Cyo0qSxn76", "reviewer": "Reviewer_xivh", "summary": "The authors mainly aim to improve the efficiency of private inference for autoregressive language models. First, they observe that the decoding time is relatively insensitive to the input length. Next, they adapt speculative decoding to the private inference setting. The authors employ a small public model as a drafter and a larger private model as a verifier. A key technical challenge lies in the verifier's rejection rule, which typically requires computationally expensive reciprocal operations. To address this, the authors propose a novel protocol that allows rejection of draft tokens. Experimental results demonstrate improvements in decoding speed, achieving 2.1× to 6.0× efficiency gains.\n\n## update after rebuttal\nI appreciate the authors for commenting on the remaining concern. Using a smaller public model may be partly due to resource constraints, but the main reason is the copyright for larger models. If a public model could match the performance of a private one, there would be no need to use private models. Therefore, in realistic scenarios, public models are inherently expected to underperform compared to private models. As a result, for complex tasks like reasoning, the accuracy gap is likely to remain significant. While the proposed method may offer some speedup in such tasks, the overall impact would likely be limited. For this reason, I believe the broad effect of the work is not substantial enough and will maintain my score as weak accept.", "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 the positive feedback and appreciation of our work. We appreciate your insights and would like to provide more clarification.\n# Question 1: Figure 1&2 claim that the decoding time is relatively insensitive to the input length. However, for softmax, the cost increases drastically as the input length increases. Thus, if the input length is over 64 or 128, its time might be one of the major bottlenecks. \nWe appreciate the reviewer's rigorous feedback and will enhance our demonstration to clarify this claim. In standard decoding, the input length is fixed at one. Our method's selection of the input (or draft) length should keep the latency insensitivity. Experiments show that using too many draft tokens (e.g., 64 or 128) indeed increases latency, so we avoid such large numbers. Instead, we focus on a reasonable range, like 1 to 16 draft tokens in Figure 1, or 4, 8, and 16 in Figure 5. \n\n\n# Question 2: If performance (perplexity) is preserved, the paper would be significant, as it demonstrates substantial speedups by leveraging public drafter models for private inference.\nWe would like to clarify that soft matching through speculative sampling theoretically preserves the accuracy performance (e.g. perplexity) of the private model [1], as we mentioned in Line 239. It guarantees that tokens sampled from the distributions $p(x)$ and $q(x)$ using speculative sampling are distributed identically to those sampled from $p(x)$ alone. This implies that the probability of sampling any token $\\hat{x}$ from both $p(x)$ and $q(x)$ is precisely $p(\\hat{x})$. As a result, the expected perplexity of the sampled tokens with respect to some oracle baseline remains unchanged, thereby maintaining the performance concerned by the reviewer.\n\nWe provide a brief proof of why the tokens sampled by two types of sampling algorithm follow an identical distribution; further details can be found in Appendix A of [1]. The probability of sampling a token $\\hat{x}$ using speculative sampling is: \n$$\nP\\\\{x = \\hat{x}\\\\} = P\\\\{x = \\hat{x} | acc\\\\} \\cdot P\\\\{acc\\\\} + P\\\\{x = \\hat{x} | rej\\\\} \\cdot P\\\\{rej\\\\}\n$$\n- When the proposed token is accepted: The public model proposes $\\hat{x}$ with probability $P\\\\{x = \\hat{x} | acc\\\\} = q(\\hat{x})$. The acceptance probability for $\\hat{x}$ is $P\\\\{acc\\\\} = \\min\\left(1, \\frac{p(\\hat{x})}{q(\\hat{x})}\\right)$. \n- When the proposed token is rejected: The public model may propose any token, which is then rejected. The rejection probability is $P\\\\{rej\\\\} = \\sum_{x'} q(x') \\cdot \\left(1 - \\min\\left(1, \\frac{p(x')}{q(x')}\\right)\\right) = 1 - \\sum_{x'} \\min(q(x'), p(x'))$. The token is re-sampled from the adjusted distribution with $P\\\\{x = \\hat{x} | rej\\\\} = norm(\\max(0, p(\\hat{x}) - q(\\hat{x})))$. \n\nSubstituting these into the equation, we obtain: \n$$\nP\\\\{x = \\hat{x}\\\\} = q(\\hat{x}) \\cdot \\min\\left(1, \\frac{p(\\hat{x})}{q(\\hat{x})}\\right) + \\left(1 - \\sum_{x'} \\min(q(x'), p(x'))\\right) \\cdot norm(\\max(0, p(\\hat{x}) - q(\\hat{x}))) = p(\\hat{x})\n$$\nThis confirms that the speculative sampling process preserves the original distribution $p(x)$, as desired. If you have any further questions, please feel free to let us know.\n\n[1] Fast inference from transformers via speculative decoding. ICML 2023\n\n# Question 3: The paper does not report model performance (e.g., perplexity). An empirical analysis of how soft matching degrades output quality would be valuable for practitioners.\nAs discussed in Question 2, there is no inherent trade-off between efficiency and accuracy performance when adopting the soft maching. The soft matching theoretically maintains the accuracy performance, i.e. same expected perplexity towards some oracle output. This theoretical guarantee is a key strength of our method, allowing speed improvements without concerning the output quality.\n\n# Question 4: In practice, drafter models are limited to small LLMs, which often lack generalization across tasks and need task-specific alignment. Aligning drafters for every task is impractical, and without proper alignment, the efficiency declines.\nIn our experiments, even using non-aligned small models, we achieve an average acceptance rate of 40% for the different-series model and an average of 65% for the same-series model, which already presents approximately 1.6X and 3X average speedup. \n\nThe alignment further increases the benefits to 2X and 5X average speedup. Notably, the alignment is much easier and more practical than traditional fine-tuning tasks that prioritize accuracy as the primary objective. As illustrated in Figure 4, the alignment requires only a small public GPT, a minimal aligning dataset, and can be efficiently tuned on a small GPU.\n\nFurthermore, the effectiveness of our approach is expected to increase as client-side computational capabilities continue to advance. Such advancements enable the leveraging of larger and more powerful public models, thereby enhancing the acceptance ratio as Table 1 indicates.", "claims_and_evidence": "* They claim that the decoding time is relatively insensitive to the input length based on Figure 1 and Figure 2. However, for softmax, their computation cost increases drastically as the input length increases in Figure 1. Thus, if the input length is over 64 or 128, the input length might be one of the major bottlenecks. The comparison when input length is 64 would make the claim stronger. \n\n* The efficiency of the proposed protocol for rejection rule is shown in Table 2.", "methods_and_evaluation_criteria": "* Efficiency evaluation is well presented in Figure 5.\n\n* The paper does not report model performance (e.g., accuracy or perplexity), focusing solely on speed improvements.  While speculative decoding with hard matching theoretically preserves model outputs, the use of soft matching may introduce performance degradation. An empirical analysis of how soft matching impacts accuracy or output quality would be valuable for practitioners, especially to understand the trade-off between efficiency and performance.", "theoretical_claims": "There are no theoretical claims.", "experimental_designs_or_analyses": "See Evaluation Criteria.", "relation_to_broader_scientific_literature": "* If performance is preserved, the paper would be significant, as it demonstrates substantial speedups by leveraging public drafter models for private inference.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "* In practical deployments, the drafter is constrained to be a small LLM. However, small models typically lack the capacity to generalize across diverse tasks and require task-specific alignment. Obtaining aligned drafters for every possible task is impractical, and without proper alignment, the effectiveness of speculative decoding diminishes. This limitation is evident in Table 1, where the rejection rate increases substantially when the drafter is not aligned with the target task.", "other_comments_or_suggestions": "None.", "questions_for_authors": "See the above sections.", "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: The paper proposes a public decoding and secure verification method to accelerate privacy-preserving inference. However, some shortcomings need to be addressed in the current version. For example, Figure 3 and its description require a thorough examination, along with a more detailed explanation of the choice of public models. In addition, expanding the experimental evaluation to include larger vocabulary sizes or more diverse model architectures would also improve the paper. After reading the reviewers’ comments and the authors’ rebuttals, I believe these issues can be effectively addressed in the camera-ready version. Given that all reviewers have acknowledged the novelty of the authors' work, I recommend acceptance of the paper.
Decision: Accept (poster)