CipherPrune: Efficient and Scalable Private Transformer Inference

We thank Reviewer Xg5m for their careful review of our protocol and manuscript, as well as for their constructive comments.

Q1: The communication cost of GELU and SoftMax.

While it is true that the token pruning protocol is executed after the SoftMax protocol in each layer, we would like to clarify that CipherPrune significantly reduces the overhead of both the SoftMax and GELU protocols, as demonstrated in Figure 10 of the manuscript. This is because Transformers consist of multiple layers, each with its own SoftMax protocol. By pruning tokens, CipherPrune reduces the computational cost of the SoftMax protocols in subsequent layers. Additionally, since the GELU protocol always occurs after our token pruning protocol, the overhead of all GELU operations is reduced. The only exception is the SoftMax overhead in the first layer, which remains unchanged. It has a minimal effect on the proposed methods.

To further highlight this improvement, we have included Figure 18 in Appendix E of the updated manuscript. This figure illustrates the reduction in overhead for these protocols.

In addition to token pruning, CipherPrune also reduces the polynomial degree used in the GELU and SoftMax protocols through its polynomial reduction protocol, which is invoked after token pruning.

We have conducted additional experiments to provide a detailed breakdown, presenting layer-by-layer communication costs for both the GELU and SoftMax protocols. These results clearly show the overhead reduction for pruned SoftMax (with our methods) compared to the original SoftMax, as well as for pruned GELU (with our methods) compared to the original GELU. The communication costs are presented in megabytes.

Dear Reviewer Xg5m,

Thank you for your comments on our paper. We hope the additional data and clarifications we provided have adequately addressed the concerns raised in your review. We would greatly appreciate your feedback on our responses.

Best regards,

The Authors

We thank Reviewer Mztk for the thorough reading of the manuscript and constructive comments.

Q1: Discuss tasks that are most suitable for CipherPrune.

For token pruning, it generalizes effectively to both discriminative and generative models and tasks (e.g., language modeling and machine translation). While applying token pruning to discriminative tasks is relatively straightforward, its application to generative models and tasks might initially seem counterintuitive. However, there is a key reason why token pruning is beneficial for generative tasks: each token generation in a generative task operates similarly to a discriminative task.

In a discriminative task using a BERT-based Transformer encoder, the model produces a single summarization for classification. Conversely, in a generative task, the model relies on an optional encoder summarization and performs multiple-iteration generation. Each iteration generates one token, taking the summarization and previously generated tokens as inputs. The initial summarization typically requires comprehensive token information. However, in later generation iterations, many tokens can be pruned significantly, as not all tokens contribute equally to generating each subsequent token. This property allows intermediate tokens to be pruned significantly during generation tasks.

As demonstrated in prior works [1, 4, 5, 6, 7], token pruning is effective for generative models and tasks, often producing results comparable to discriminative models [1, 2, 3]. Our experiments further confirm this, showing that CipherPrune reduces the execution overhead for private GPT-2 language modeling tasks by approximately 5.3× for 128-token inputs and 8.2× for 512-token inputs. We will include this result and explore more models and tasks in the next version of the manuscript.

[1] Wang et al., Spatten: Efficient sparse attention architecture with cascade token and head pruning.

[2] Kim et al, Learned token pruning for transformers

[3] He et al, Magic pyramid: Accelerating inference with early exiting and token pruning.

[4] Anagnostidis et al., Dynamic context pruning for efficient and interpretable autoregressive transformers.

[5] Zhang et al., H2o: Heavy-hitter oracle for efficient generative inference of large language models.

[6] Oren et al., Transformers are multi-state rnns.

[7] Fu et al., Lazyllm: Dynamic token pruning for efficient long context llm inference.

We thank Reviewer V3E7 for the thorough reading of the manuscript and for providing constructive comments.

Q1: Discussion of client-side overhead for Step 3 of Figure 4.

The introduced pruning imposes only marginal overhead on the client side. In Figure 10 of our manuscript, we provide a detailed breakdown of the execution time for each computational component, including the introduced pruning. The figure demonstrates that the pruning overhead accounts for less than $5\\%$ of the total runtime, and this overhead ratio is consistent for the client-side as well. Additionally, we have included specific client-side overhead data for pruning and reduction in our experiments, which are based on the BERT Base model in a WAN setting.

Q2: The overhead of LayerNorm may not be reduced

We clarify that CipherPrune effectively reduces the overhead of LayerNorm, as the number of tokens is decreased through encrypted token pruning. Since the complexity of LayerNorm is linear with respect to the number of tokens, this reduction directly lowers its computational overhead. Figure 10 in our manuscript illustrates this reduction in LayerNorm overhead.

Q3: Add characterization of layerwise token redundancy.

We appreciate the reviewer’s suggestion to include this characterization. In Figure 19 in Appendix F, we present the detailed number of tokens at each layer from our experiments, along with the runtime of the secure pruning protocol. Our findings indicate that intermediate layers tend to exhibit more redundancy, leading to a higher number of tokens being pruned at these stages. We believe this data provides valuable insights into layer-wise token redundancy and can inform future research in this area.

Q4: The deployment difficulties due to protocol-network codesign.

Deploying CipherPrune in practice is straightforward. CipherPrune leverages modular block operations built on fundamental cryptographic primitives, such as oblivious transfer-based comparison and MSB extraction. We already offered the open-source code to enhance reproducibility and facilitate deployment. We plan to elaborate the readme and add a tutorial.

Editorial improvements and citations.

• We have corrected the typo at line 355 within the manuscript, highlighted in blue.
• We use the same configuration with previous works such as Bolt for the Post-LN. We have updated the FFN module in Figure 4 for better clarity.
• We thank Reviewer V3E7 for pointing out the missing citations. We have added these citations and discussed them in the related work section for a more comprehensive literature review.

Thank you for providing the rebuttal.

Q2: The overhead of LayerNorm may not be reduced

By pruning input tokens, you have reduced the number of LayerNorm operations, which is different from making the operations themselves faster, hence there is a distinction. By pruning tokens, both linear and nonlinear operations have been reduced, which is different from making the operations themselves more efficient.

I have one question on the newly added results (Figure 19)

This is because there are more input tokens in the early layers, resulting in more secure swap operations. For example, 8 tokens are removed in both layer 4 and layer 7, but the protocol runtime in layer 4 is ∼ 2.4× longer than that in layer 7.

How does removing the same number of tokens from two layers lead to different input token counts in those layers? Also, why there are only 11 layers in the BERT-base model?

Minor Please correct the BibTeX entry for the BumbleBee paper (It's accepted to NDSS 2025)

We appreciate the reviewer’s follow-up comments.

Overhead of LayerNorm protocol.

That is correct. The token pruning reduces the overhead of the total LayerNorm operations in the network inference, but does not reduce each LayerNorm's overhead. A more efficient LayerNorm protocol will further enhance the efficiency. We will clarify this more explicitly in our final version.

Number of tokens in Figure 19: How does removing the same number of tokens from two layers lead to different input token counts in those layers? 11 Layers (BERT) in Figure 19.

In CipherPrune, tokens are removed progressively, and once removed, they are excluded from computations in subsequent layers. Consequently, token pruning in earlier layers affects computations in later layers, whereas token pruning in later layers does not impact earlier layers. As a result, even if layers 4 and 7 remove the same number of tokens, layer 7 processes fewer tokens overall, as illustrated in Figure 19. BERT consists of 12 layers (layer 0 to layer 11). In the original Figure 19, we focused on layers 1 through 11 because layer 0 is distinct in its redundancy characteristics. Specifically, redundancy in layer 0 arises from both padding tokens (when the input length is shorter than the maximum sequence length, typically 128 in prior works like BOLT [1]) and the input itself. In contrast, redundancy in layers 1–11 is primarily derived from the input alone, as padding tokens are already removed in layer 0. Including only layers 1 through 11 allowed us to emphasize redundancy patterns specific to the input. However, to address concerns and improve clarity, we have now added layer 0 to the updated Figure 19 and its description, ensuring a more comprehensive representation of pruning behavior across all layers.

We are happy to provide further clarification or follow-up responses if needed.

[1] Pang et al., BOLT: Privacy-Preserving, Accurate, and Efficient Inference for Transformers.

We thank Reviewer Qed2 for the thorough reading of our manuscript and for providing constructive comments.

Q1: The 0.2% accuracy decrease.

We appreciate the reviewer pointing out that our methods may result in a marginal accuracy drop, rather than no accuracy drop as initially claimed. We have revised the manuscript to make this claim more precise and accurate.

Q2: Prior works on private token pruning.

Pruning on encrypted data remains a relatively new area for the research community. At the time of submission, BOLT [1] was the only relevant work we could identify. We have clarified the distinctions between our work and BOLT, and we highlight the improvements our method offers over BOLT.

We believe that CipherPrune represents an innovative contribution to the field, demonstrating the potential of crypto-machine learning co-design and inspiring future research in this area.

[1] Pang et al., BOLT: Privacy-Preserving, Accurate, and Efficient Inference for Transformers.