- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper focuses on reducing the communication rounds in secure autoaggressive decoding models by proposing a bucket-based maximum approximation for Softmax and an interval look-up-table based approximation protocol for GELU and Layernorm. Then the paper adopts existing protocols and evaluates the proposed scheme.
Critical strengths
The submission includes the details of their implementation and codebase.
The paper includes details of the proposed algorithms.
Critical weaknesses
-
The technical contribution is limited. The paper adopts existing MIC protocol directly in Section 3 and 4 without improvements. Although the paper proposed bucket-based approximate maximum and interval lookup table, it doesn’t give a comprehensive analysis of choosing the number and size of buckets/intervals. So the proposed techniques are difficult to be applied.
-
The paper aims to reduce the number of communication rounds in secure transformer inference, but it only considered SMPC-based baselines. Indeed, FHE-based transformer inference is also round-efficient, and I think authors should discuss about why rule out FHE-based baselines.
-
The improvement is not significant. From evaluation results, although the proposed method reduces the communication rounds and the online communication overhead, but the total communication overhead is even larger than baselines.
Questions for authors
-
In section B, authors said Boyle et al’s secure multi-interval containment (MIC) protocol is used to securely identify bucket membership and the rightmost non-empty bucket, which also contributes to the overall round complexity. I would like to know more about the protocol to ensure the round complexity of RESAD is O(1).
-
For the constant-round secure approximate maximum, is there any analysis/instructions about how to choose the number of bucket and the interval of each bucket to ensure that the approximate error won’t affect the model performance? Similarly, for Section 4.1, how to choose p? I think such analysis is necessary especially when the proposed algorithms are used in large and deep models.
3 comments
Response to Weakness W3
We thank the reviewer for highlighting this important tradeoff and motivating further analysis.
W3.
We agree that the total communication overhead is even larger than baselines. However, the main goal of this paper is to reduce online runtime. As shown in Table 5, RESAD achieves lower online runtime than SIGMA at the 512th and 1024th token positions under LAN settings, and at all evaluated token positions under WAN settings, across all three models.
Although communication overhead affects communication time and consequently overall runtime, it is not the only determining factor. Communication rounds must also be considered, particularly in latency-sensitive environments. Despite incurring higher total communication, RESAD achieves lower total runtime than SIGMA at the 512th and 1024th token positions under LAN settings, and at all evaluated token positions under WAN settings, across all three models. This demonstrates that the reduction in communication rounds can effectively offset the additional communication overhead.
The performance comparison is summarized below:
| Token position | LAN (Online) | LAN (Total) | WAN (Online) | WAN (Total) |
|---|---|---|---|---|
| 128th | ↓ 21.28%–37.50% | ↓ 21.11%–30.90% | ↑ 52.34%–56.18% | ↑ 29.90%–43.29% |
| 512th | ↑ 15.61%–22.48% | ↑ 2.88%–4.52% | ↑ 56.12%–59.44% | ↑ 20.56%–35.49% |
| 1024th | ↑ 39.48%–42.86% | ↑ 12.55%–16.44% | ↑ 58.96%–61.51% | ↑ 14.43%–27.70% |
↑: Runtime reduction relative to SIGMA (RESAD is faster); ↓: Runtime increase relative to SIGMA (RESAD is slower). The ranges cover GPT-2 Small, GPT-2 Medium, and TinyLlama-1.1B.
To quantify this tradeoff, we establish a latency cost model incorporating computation overhead, communication rounds, and communication volume, and theoretically derive the performance crossover conditions as functions of bandwidth and effective per-round latency (Equations (54)–(56)). We further validate these conditions through experiments on GPT-2 Small and Medium at the 512th and 1024th token positions, varying both bandwidth and RTT.
At a fixed bandwidth of 20 Mbps, the interpolated crossover RTTs are approximately 45.17/59.91 ms for GPT-2 Small and 59.48/83.16 ms for GPT-2 Medium (512th/1024th tokens, respectively). Increasing the bandwidth to 50 Mbps reduces these thresholds to 16.39/19.37 ms and 21.56/25.29 ms, respectively. At 100 Mbps, the identified crossover RTTs further decrease to 6.95–8.38 ms, while GPT-2 Small at the 1024th token already outperforms SIGMA at the lowest tested RTT of 5 ms.
Conversely, at a fixed RTT of 20 ms, RESAD achieves lower total runtime at tested bandwidths of at least 50 Mbps for GPT-2 Small and 100 Mbps for GPT-2 Medium, across both token positions. At 40 ms RTT, 50 Mbps is sufficient for both models. At 100 ms RTT, RESAD outperforms SIGMA even at 20 Mbps across all four evaluated cases.
Regarding preprocessing availability, RESAD achieves lower online runtime in all additionally tested configurations when preprocessing materials are ready. Even when preprocessing costs are included, RESAD maintains lower total runtime in 89 of 120 configurations. Furthermore, at 100 Mbps and 80 ms RTT, RESAD achieves 2.33–2.50× online speedups and 1.34–1.53× total speedups.
These results demonstrate that the reduction in communication rounds can effectively outweigh the additional preprocessing communication, yielding substantial runtime improvements across a broad range of network conditions.
See Section 6.3, Table 5, and Appendix F.3, Equations (54)–(56), Tables 9–10, and Figure 22 (pp. 33–34).
Response to Questions Q1–Q2
We thank the reviewer for these valuable questions, which have helped us clarify the protocol complexity and parameter-selection rationale.
Q1.
We thank the reviewer for this question. We have added a detailed description of the MIC protocol and a formal round-complexity analysis in Appendix B.4.
MIC protocol. We adopt the FSS-based Multiple Interval Containment (MIC) protocol proposed by Boyle et al. (Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation, EUROCRYPT 2021, Section 4.2 and Theorem 4). Given a secret input and public intervals , MIC securely computes the interval-membership indicators .
Specifically, MIC consists of two phases:
Offline phase: The trusted dealer generates an input mask , a single DCF key pair shared across all intervals, and interval-specific correction shares. The corresponding FSS keys are distributed to the two computing parties.
Online phase: Given the masked input , each party performs two local DCF evaluations per interval and combines the results with its correction shares to obtain additive shares of the interval-membership indicators. Importantly, all DCF evaluations are local and require no interaction. When a masked output is needed, the parties exchange their output shares in one communication round.
Therefore, MIC requires only one online round regardless of u, although the local DCF work and key material scale linearly with u, as established by Boyle et al.
Constant-round ApproxMax. In RESAD, the first MIC invocation evaluates bucket membership for all input elements in parallel. After aggregating bucket occupancy and encoding the nonempty buckets, the second MIC invocation identifies the rightmost nonempty bucket through its corresponding power-of-two interval. Since both MIC invocations rely on local FSS evaluations, the interaction overhead arises primarily from the necessary share-to-mask conversions. As detailed in Appendix B.4, each refinement stage requires at most three online communication rounds, including output conversion.
Furthermore, the refinement depth satisfies
where , , and are public parameters independent of the input length . Consequently, ApproxMax requires at most online communication rounds with respect to . Under our configuration , , and , we obtain , requiring at most six rounds.
See Section 3.2 (pp. 4–5) and Appendix B.4 (pp. 19–21) for the MIC construction, protocol costs, and formal round-complexity proof.
Q2.
We thank the reviewer for this valuable suggestion. We have added rigorous theoretical analyses of parameter selection and the accuracy–cost tradeoffs for both ApproxMax and ILUT.
For ApproxMax, Appendix B.2 establishes a one-sided approximation error bound . To ensure numerical stability in the subsequent Softmax computation, we derive a sufficient condition , accounting for the finite-precision exponential approximation and the reciprocal lookup domain . Under our reference public range and bucket budget , the round-first optimization selects and , requiring only six communication rounds. The two refinement stages use 256 buckets each, with widths of 128 and 0.5, respectively. Appendix B.2 also provides a generalized parameter-selection rule for other validated input ranges and bucket budgets.
For ILUT, our choice of follows the widely adopted BF16 numerical-precision format, which has seven explicitly stored fraction bits and one implicit leading significand bit, giving eight significant bits. Appendix C.2 establishes a relative input-approximation bound of . Requiring at least BF16-level significand resolution gives , hence . Since the table-size bound increases with for , is the smallest admissible choice under this precision criterion, balancing accuracy and lookup costs.
We further provide operator-specific error bounds at , including for the exponential and for the GeLU correction. For deeper models, Appendix C.2, Equations (52)–(53), also provides a sufficient precision-selection condition based on layer-wise error propagation and model sensitivity. These results justify our selected parameters under the stated numerical assumptions, while providing guidance for adapting them to other model architectures.
See Appendix B.2, Equations (1)–(14) (pp. 15–18), and Appendix C.2, Equations (35)–(53) (pp. 22–26).
Response to Weaknesses W1–W2
We thank the reviewer for the constructive feedback and valuable suggestions.
W1.
The key insight behind our first contribution is that secure Softmax does not require an exact maximum, but only a numerically safe shifting value. Existing maximum-based secure Softmax protocols typically compute the exact maximum through sequential comparisons, incurring input-length-dependent communication rounds. By exploiting the shift invariance of Softmax, we propose a bucket-based approximate maximum algorithm that replaces sequential comparisons with parallel bucket localization, achieving constant communication rounds with linear communication complexity, while maintaining numerical stability.
Our second contribution introduces a significant-bit-based interval construction that reduces the table-entry complexity for secure nonlinear evaluation from O(2n) to O(2p(n−p)). Combined with different secure MIC/ILUT protocols, we obtain efficient secure protocols for nonlinear functions. As shown in the ILUT-only ablation experiments (Appendix F.4, Figures 23–25), compared with SIGMA for GPT-2 Small and Medium, ILUT reduces online runtime by 42.4%–44.1%, total runtime by 33.7%–35.5%, online communication by 35.8%–41.1%, and total communication by 22.6%–25.1%, while maintaining comparable model accuracy. These results demonstrate the efficiency of our proposed ILUT construction.
While both contributions build on existing MIC/FSS primitives, our novelty lies in the new approximation constructions, i.e., bucket-based approximate maximum reducing communication rounds from O(logm) to O(1) and precision-aware interval tables reducing table-entry complexity from O(2n) to O(2p(n−p)), and the resulting nonlinear protocols that reduce communication rounds from 15 to 7 compared with Grotto, rather than the underlying cryptographic primitives.
We have added rigorous theoretical analyses of parameter selection and the accuracy–cost tradeoff. For ApproxMax, Appendix B.2 derives the numerical-stability condition δ≤0.689005 and proves that, under our reference range and bucket budget U=256, selecting δ=0.5 achieves the minimum refinement depth d=2, requiring only six rounds for the masked-output interface. For ILUT, Appendix C.2 establishes a relative input-approximation bound of 21−p and a table-size bound of O(2p(n−p)), showing that p=8 is the smallest admissible precision under the stated BF16-resolution criterion. These analyses provide explicit parameter-selection rules.
See Sections 3–4, Appendix B.2 (pp. 15–18), and Appendix C.2 (pp. 22–26).
W2.
We agree that FHE-based inference is an important alternative for reducing interaction rounds. However, RESAD and FHE-based schemes follow different technical paradigms. While FHE-based schemes can achieve low or even non-interactive inference, they often incur substantial computational overhead from homomorphic operations. In contrast, RESAD focuses on reducing communication rounds and online latency within the FSS-based secure inference paradigm with preprocessing.
To provide a concrete comparison, we have added experiments against Cachemir, a recent state-of-the-art FHE-based generative inference scheme, using its publicly available implementation (https://zenodo.org/records/23189548). Since Cachemir's public CPU artifact provides a benchmark for a single Transformer decoder block, we align the evaluation scope by measuring RESAD on CPUs at the same block level.
Experimental settings. We use the same CPU environment described in Section 6 and follow configuration supported by Cachemir's public artifact. Specifically, we evaluate a synthetic LLaMA-style decoder block with a hidden dimension of 512, an intermediate dimension of 2048, eight attention heads, and a batch size of one. The benchmark processes the 128th token with a preconstructed 127-token KV cache and synthetic weights. The Cachemir artifact uses a reduced CKKS configuration with logN=13, level 6, and 16 threads.
Cachemir performs homomorphic evaluation of encrypted inputs on a single server, whereas RESAD uses secret sharing between two non-colluding computing parties with a trusted preprocessing dealer. They rely on different cryptographic and trust assumptions, therefore, this comparison is intended to provide a runtime at the same block. We also acknowledge that RESAD includes interactive network communication, whereas Cachemir performs local homomorphic evaluation, leading to different performance characteristics. As shown in Table 13, Under WAN settings, RESAD achieves a 19.58$\times$ speedup over Cachemir, despite the additional network latency caused by interactive communication. Under LAN settings, where network latency is substantially lower, RESAD achieves a larger speedup of 154.42$\times$.
See Appendix F.6, Table 13, p. 37.