ULD-Net: Enabling Ultra-Low-Degree Fully Polynomial Networks for Homomorphically Encrypted Inference
Authors: Xi Xie
Ran Ran
Jiahui Zhao
Bin Lei
Zhijie Jerry Shi
Wujie Wen
Caiwen Ding
Venue: ICLR 2026 Poster (2026)
Keywords: Privacy-Preserving Machine Learning
efficient private inference
machine learning as a service
homomorphic encryption
Fully Polynomial Networks
Ultra-Low-Degree operators
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Fully polynomial neural networks—models whose computations comprise only additions and multiplications—are attractive for privacy-preserving inference under homomorphic encryption (HE). Yet most prior systems obtain such models by post-hoc replacement of nonlinearities with high-degree or cascaded polynomials, which inflates HE cost and makes training numerically fragile and hard to scale.

We introduce ULD-Net, a training methodology that enables ultra-low-degree (multiplicative depth $\leq 3$ for each operator) fully polynomial networks to be trained from scratch at ImageNet and transformer scale while maintaining high accuracy. The key is a polynomial-only normalization, PolyNorm, coupled with a principled choice of normalization axis that keeps activations in a well-conditioned range across deep stacks of polynomial layers. Together with a special set of polynomial-aware operator replacements, such as polynomial activation functions and linear attention, ULD-Net delivers stable optimization without resorting to high-degree approximations.

Experimental results demonstrate that ULD-Net enables stable training of low-degree fully polynomial networks on large-scale model architectures and datasets. Applying ULD-Net to ViT-Small and ViT-Base achieves 76.70\% and 75.20\% top-1 accuracy on ImageNet, respectively, which are comparable to the original models and represent the first fully polynomial models successfully scaled to the ViT/ImageNet level. Additionally, ULD-Net outperforms several state-of-the-art open-source fully and partially polynomial approaches across diverse model architectures and datasets in both accuracy and HE inference latency.

Published as a conference paper at ICLR 2026
ULD-NET: ENABLING ULTRA-LOW-DEGREB FULLY
POLYNOMIAL NETWORKS FOR HOMOMORPHICALLY ENCRYPTED INFERENCE
Xi Xie
Rann Ran
Jiahui Zhao University of Connecticut
University of Connecticut xi w.x.eeucoon.ee.
North Carolina State University rr Fran@ncsu.edi
cacnui.zhao@ucce edu
Bin Lei
Zhijie Jerry Shi
University of Minnesota Twin Cities lei0012 wmmm..
University of Connecticut zshi Buconn.ede
Wujie Wen
Caiwen Ding University of Minnesota Twin Cities dingceumn, edu
North Carolina State University wwen2@ncsu. eddu
ABSTRACT
Fully polynomial neural networks models whose computations comprise only additions and multiplications- attractive for privacy-preserving inference un- der homomorphic encryption (HE). Yet most prior systems obtaín such models by post-hoc replacement of nonlinearities with high-degree or cascaded polynomials, which inflates HE cost and makes training numerically fragile and hard to scale.
We introduce ULD--Net, training methodology that enables ullro-low-degree (multiplicative depth < 3 for each operator) fully polynomial networks to be trained from scratch at ImageNet and transformer scale while maintaining high accuracy. The key is polynomial-only normalization, PolyNorm, coupled with a principled choice of normalization axis that keeps activations in a well- conditioned range across deep stacks of polynomial layers. Together with spe- cial set of polynomial-aware operator replacements, such as polynomial activation functions and linear attention, ULD-Net delivers stable optimization without re- sorting to high-degree approximations.
Experimental results demonstrate that ULD-Net enables stable training of low- degree fully polynomial networks on large-scale model architectures and datasets. Applying ULD-Net ViT-Small and ViT-Base achieves 76.70% and 75.20% top-1 accuracy on ImageNet, respectively, which are comparable to the original models and represent the first fully polynomial models successfully scaled to the ViT/ImageNet level. Additionally, UL.D-Net outperforms several state-of-the-art open-source fully and partially polynomial approaches across diverse model ar- chitectures and datasets in both accuracy and HE inference latency.
The code is available at GitHub?.
INTRODUCTION
Machine learning is increasingly delivered as a service (e.g., AWS SageMaker (ama), Azure MI. (tea, 2016)), raising serious concerns regarding the confidentiality of user data and propri- etary models. Homomorphic encryption (HE) (Dathathri et al., 2019; Kim et al., 2022) enables computation directly on ciphertexts, but today's deep networks rely on non-polynomial operators (e.g., ReLU, GELU, LayerNorm, Softmax) that are expensive or unsupported under HE. A popular
"These authors contributed cqually.
/https:/ / / thub. com exi5 S1/ULD-NNS

---

Published as a conference paper at ICLR 2026
workaround is approximate such operators with high-degree polynomials to offload them to alternative secure protocols (Tong et al., 2024; Lou et al., 2021; Ran et al., 2022). Unfortunately, high-degree or cascaded polynomials increase HE multiplicative depth and latency, and they remain brittle when scaled to large models and datasets.
Our goal. We revisit the problem from first principles: rather than approximating mom-polynomill operators after training, can we directly train networks whose every layer a low-degree polyno- mial, preserving accuracy while keeping HE cost small?
This paper. We present ULD-Net, a practical an- to that question. ULD-Net combines new polynomial-only normalization layer. PolyNorm, with specific set of training and architectural choices that together maintain tight control over ac- tivation ranges across depth. The design agnos- tic to backbone (ResNets, VanillaNets, ViTs) and naturally HE-friendly: altra-low-degree activations reduce ciphertext multiplications and multiplicative depth per layer, translating to faster encrypted infer- ence.
Anturcyy-Laaee Lattnnyyyyaayyyyyyoooo Farato Frontier Comparison
Verii
Imsgettet Top Accuracy (%)
76
uLiske (Dueal
Vuri
22-
21-
70
10a
10'
HE Inference Latency on AMD 1975WX (s)
Why this is hard. Polynomial functions of de- gree 2 2 can explode outside narrow input range; when stacked deeply, instability compounds and de- rails optimization, especially on large, high-variance datasets. Prior fully polynomial attempts that suc- ceed ImageNet often rely on high-degree or cascaded high-degree polynomials, trading stability for prohibitive HE cost (Hesamifard et al., 2017; Chou et al., 201 8; Al Badawi et al., 2020; Garimella et al., 2021; Lee et al., 2021; Tong et al., 2024).
Figure ULD-Net achieves better accuracy-latency Pareto frontier than prior SOTA fully polynomial works (Lee et al., 2021: Tong et al., 2024) on ImageNet.
Key ideas in ULD-Net.
1. Normalization-axis principle. We show that choosing the normalization axis to match the geometry of polynomial layers (and the data layout) imposes effective range constraints with minimal overhead, improving stability at scale.
2. PolyNorm:
golynomial-only normalization. PolyNorm implements strong numeric con- trol using only additions and multiplications, making it natively compatible with HE while serving the same stabilizing role as common non non-polynomial normalizers.
3. End-to-end design recipe. We provide an effective and broadly applicable design recipe- incpudinn suitable ultra-low-degree polynomial replacements for common activa- tion, attention, and normalization operators, as well as auxiliary training techniques such as variance-aware penalty losses that reliably trains fully polynomial networks on ImageNet and ViTs without high-degree approximations.
Results at glance. ULD-Net-applied ResNet- 18 achieves 69.79% top-1 accuracy ImageNet, outperforming the best fully polynomial baseline by +0.39% accuracy and 2.76x HE inference speedup; and reaches 78.81 % top-1 accuracy CIFAR-100, surpassing the best partial polynomial baseline by up to +3.33% accuracy and 3.17x speedup. ULD-Net-applied ViT-Small is successfully trained on CIFAR-I0 and Tiny-ImageNet, outperforming the best HE transformer baseline by up to +0.88% accuracy and 20.5x reduction in non pol-pollloiial operator cost. Applying ULD-Net to the VanillaNet-5/6f7 family yields 72.43% % %/76.40% % top-1 accuracy on ImageNet, with yields
substantially lower HE latency than ResNet-18. Applying ULD-Net to ViT-Small/ViT--a.. 76.70 % 75..20% ImageNet accuracy, representing, to the best of our knowledge, the first successful scaling of fully polynomial models to the ViT/ImageNet level. As shown in Figure 1, UL. achieves a significantly better accuracy-latency Pareto frontier than prior works.
Relation to prior work. Partial replacement methods (Peng et al., 2023a) prune locate non-polynomial operators to reduce secure-inference overhead but still require costly non-polynomial handling. Fully polynomial approaches avoid that cost but often rely on high-degree
2

---

Published as a conference paper at ICLR 2026
cascaded polynomials retain accuracy scale (Lee et al., 2021; Tong al., 2024). ULD-Net departs from both by training ultra-low-degree (multiplicative depth 3) fully polynomial networks directly, enabled by PolyNorm and principled design choices that maintain numerical stability with- out sacrificing HE efficiency.
In summary, ULD-Net turns fully polynomial network design into scalable, accuracy-preserving alternative for HE inference: it replaces post-hoc high-degree approximations with a pretraining-time solution that is simple to implement, architecture-agnosiic,, and demonstrably effi- cient under encryption.
2
RELATED WORKS
2.1 PARTIAL POLYNOMIAL REPLACEMENT
Partial replacement methods reduce, but do not eliminate, non-polynomial operators in deep net- works (Mishra et al., 2020; Lou et al., 2021; Peng et al., 2023a). While attractive for ease of adoption, these approaches still require specialized handling (or offloading) of the remaining non-polynomial components during secure inference, especially in homomorphically encryption scheme, which leads to non-negligible latency and system complexity. More importantly, the numerical constraints for fully polynomial networks substantially stricter than for partially replaced models. In prac- tice, directly scaling partial- reliiaalreplaemment techniques to the fully polynomial regime on large models or datasets often results in unstable training and/or impractical secure-inference costs.
2.2 FULLY POLYNOMIAL REPLACEMENT
A second line of work targets fully polynomial networks by approximating all non-polynomial op- erators with polynomials. Some prior works (Park et al., 2022; Aremu Nandakumar, 2023; Ali et al., 2020; Garimella et al., 2021) are successful small datasets but are unable to scale to Ima- geNet. Lee (Lee et al., 2021) proposed cascaded polynomials to reduce approximation error within target range. Although cascading can reduce coefficient storage, the effective degree relevant to HE cost grows with the product of per-stage degrees, resulting in very high multiplicative depth on large-scale tasks; e.g., stable ImageNet training for ResNet- 18 reported require effective degree of 6075, which is prohibitive for HE inference. Tong et al. (Tong et al., 2024) reduced the cascaded degree 81 via suite of techniques (coefficient tuning, progressive approximation, alter- nating training, dynamic/static scaling), obtaining 69.4% top-1 on ImageNet; however, the training pipeline complex and less portable across architectures, and found it difficult to extend fully polynomial ViTs. Diaa et al. (Diaa et al.. 2024) use quartic polynomial and introduce a penalty loss to constrain the inputs to the polynomial layers. However, does not scale effectively Im- ageNet and ViT-based architectures. Zimerman (Zimerman et al., 2024) reported fully polynomial VIT results on CIFAR-100, but did not specify the exact polynomial forms or degrees and did not release code, making the computational cost and stability trade-offs hard to assess.
2.3 POLYNOMIAL APPROXIMATIONS IN PRACTICAL HE INFERENCE
A complementary direction integrates polynomial approximation with system-level HE optimiza- tions. For instance, NEXUS (Zhang et al., 2024) accelcrate Transformer inference under HE by combining algorithmic changes with low-level HE engineering. Nevertheless, the approach still re- lies on iterative polynomial approximations for certain non-polys non-polynomial modules, which can require many steps and contribute substantially to multiplicative depth and runtime.
3 BACKGROUNDS
3.1 CKKS HOMOMORPHIC ENCRYPTION
Homomorphic encryption (HE) enables computation over encrypted data without decryption. Lev- eled HE (LHE) supports bounded number of additions and multiplications, while Fully HE (FHE) allows unbounded computation via bootstrapping to refresh ciphertext noise (Gentry, 2009). The CKKS scheme (Cheon al., 2017) is widely used LHE scheme for approximate arithmetic on
3

---

Published as a conference paper at ICLR 2026
fixed-point values encoded in complex slots, making it suitable for machine- workloads. CKKS supports pephertext-iihhereee addition (Add), siphertett-ciphereex multiplication (CMult), ciphertext-plaintexx multiplication (PMult), and slot rotations via Galois automorphisms (Rotation, p(ct, k)). In typical implementations, CMult and Rotation are substantially more expensive than Add and PMult (e.g., up to 20x slower), overall latency is largely driven by the number of ci- phertext multiplications, rotations, and the required multiplicative depth (Ran et al., 2023). Depth controlled by modulus-chain management (rescaling) and determines whether bootstrapping is needed. Consequently. model designs that minimize polynomial degree and rotation usage are gen- erally preferable for HE inference.
Notably, the nultiplicative depth is generally regarded as the primary determinant of HE computa- tion speed, and grows proportionally with the logarithm of the polynomial degree.
3.2 FULLY POLYNOMIAL. NETWORKS
Fully polynomial networks retain the original architecture while replacing every con-polyoomial operation (e.g., ReLU, GELU, MaxPool, LayerNorm) with polynomial operator, resulting in com- putation composed solely of additions and multiplications. This design eliminates the need for costly non-poly non-polynomial handling under HE and aligns with the operations that CKKS supports most effi- ciently. Common replacements include fixed or trainable low-degree polynomial activations (Lee et al., 2021; Peng et al., 2023b), AvgPool or polynomial pooling for MaxPool (Lee et al., 2021; Tong al.. 2024), and linear iterative polynomial surrogates for normalization layers (Chen et al., 2022). Training is typically conducted in plaintext with the same polynomial operators that will be used inference; any non-polynomial components used for stabilization must be removed or re-expressed before export to the encrypted setting. The degree of these polynomial operators directly impacts the multiplicative depth and number of ciphertext multiplications, and thus the practicality of HE inference. This motivates methods- as ULD-Net -that achieve accuracy and stability with ullra-low-degree (multiplicativv depth < 3) operators.
4 ULD-NET MODEL DESIGN
4.1 NUMERICAL CONSTRAINTS FOR FULLY POLYNOMIAL MODELS
Applying numerical constraints to the data flow of fully polynomial model is primarily achieved through the normalization layers. The general form of normalization layer is:
E[x]
Norm [x]
/ar[[a] +
where [[[x] and Var[æ] represent the mean and variance of the input æ, respectively, and e is a small value prevent division by zero. The input tensor constrained a mean of zero and a variance of one over the chosen normalization axes. When a normalization layer is placed before polyno- mial layer, this compression effect can effectively prevent the absolute value of the polynomial input from becoming excessively large, thereby avoiding divergent outputs. In particular, when the model contains many polynomial layers, it is generally necessary to insert a normalization layer before each polynomial layer to regulate the data flow and maintain stability.
4.2 CHOICE OF NORMALIZATION AXIS
We observe that different choices of normalization axes (i.e., the axes over which the statistics E[x] and Var[z] are computed) result in different levels of stability for fully polynomial models. The most favorable choice for stability is to apply normalization to each sample in the batch, i.c. normalization over all axes except the batch axis. For example, in CNNs the tensor typically has the shape B, C, H, W] (samples, channels, height, width). Applying normalization over the [C, H. W] axes provides the best stability for polynomial layers. For ViTs, the tensor typically has the shape [B, N, D) (samples, patches, embeddings). In this case, normalization over the [N, D] axes provides the most stable behavior.
4

---

Published as a conference paper at ICLR 2026
Comparison of gix) and RX)
Lognormal Distribution
Lognorma Fit Ings 0.09, o 0.37)
1.4
gix, 1,
Binned Statsties
gix, - 4,
0.6-
0.8
12
0.4
0.6
0.2
0.0
0.0
Figure 2: Experimental statistics the v val- in the normalization layers deep neural network model (ResNet-18) during training on ImageNet, defined Eq. (6), and their log- normal distribution fit. The fitted parameters are Iu 00.0 (mean close 1) and 0.37.
2.0
2.5
4.0 45
and g (z) with different k. Jr settings. It shows that g(z) fits f(x) best around jr and remains mono- tonically decreasing within the interval (0, kp) without exceeding f()).
Figure 3: Comparison of f(x) V
1
To explain this phenomenon, we examine a model consisting of n normalization layer and polyno- mial layer pairs. For simplicity. assume all polynomial layers share the same coefficients. For each sample x E Rm, the model computes the following sequence:
y = (eeen((
(2)
where 21.-.., Fn are normalization layers, with the i-th layer having parameters (mean,, var;), and Pi.....PM Pn are all equal a degree-d polynomial p(æ) - Ei= ag.x* d > 2, ds O. We will show through variance analysis that each sample requires its own suitable normalization layers parameters, otherwise numerical explosion may occur. Assume two samples X and X': X NN o2I and
X' Ni,, o² 1). Suppose both adopt normalization layers parameters determined by X. Hence μ., o². For X', the true standard deviation o', and after the first normalization its variance becomes of =
the first normalization layer uses
= r. From the second normalization onward, the parameters are determined by mean, E (Z) var, Var [p(Z), where Z (V I). Then, to compute the variance of X' after the (i + -h normalization layer and polynomial layer, we approximate using the highest-order term the polynomial:
a3 Var(z4] Var[p(Z)
1/4 cot
(3)
d- Therefore, after n layer pairs, the variance for X' satisfies vf, x c d-1 d When e d-1 > 1, we obtain v', O(r which shows an exponential-in-lay growth and an eventual explosion of variance. This demonstrates that normalization are not computed separately for each sample. fraction of samples may undergo numerical explosion. Moreover, the likelihood of such explosion increases with both the model depth and the number of samples, which verifies that fully polynomial models face scalability challenge. Therefore, applying sample-specific normalization within each batch is the most favorable strategy for stability.
4.3 POLYNORM
However, in Eq. (1), aside from the polynomial operations E[x]] and Var[ø] (where Var[æ] E[+?] -[22)²) there exists non polyoolyla operation:
f(x) = v
(4)
Thus, need to replace f(x) with polynomial function g(z).
Quadratic Approximation of f(x). We choose to approximate f(x) with quadratic function g(x:) a(x b)) To determine the values of a, b, and proceed as follows:
5

---

Published as a conference paper at ICLR 2026
Since the overall shape of (a) differs from that of the quadratic function, focus approxi- mating f()) around a specified positive point f and its neighborhood. We enforce that at μa, g(x) matches f(z) in both function value and derivative value: g(H) f(u), g'(u) = f()). In ad- dition, noting that g(x) is monotonically decreasing for x S h, we set b = kys, where l can be specified within certain range. The function g(x) must open upwards and remain strictly positive, i... a >> O and c > 0. By solving these conditions, we obtain:
1 4(1 - k)p5/22
5- k 4/2/22
EE (1,5).
Furthermore, require that g(x) S f(x) holds for all in the range kp). This ensures that g(x) maintains good numerical constraint properties within this interval. It can be proven that this inequality holds if and only it holds at x kp. Simplifying the expression, we obtain (5-k)vk S which leads to k 2 2.438. Consequently, the range of is reduced [2.438, 5).
The Expression of PolyNorm. The function g(x) has two key properties: it closely approximates f()) near j and is monotonically decreasing within (0, ky). To effectively utilize these properties, we cannot directly use Var[æ] as the input of g(z). Instead, we first compute the relative value:
Varlz]
2
(6)
Var
where Var the historical average of Var[æ] during training, ensuring that has an expected value of 1 (as shown in Fig. 2, experimental statistics indicate that e follows lognormal distribution with a mean close to 1). Consequently, pre has an expected value of J.. Therefore, we use juv as the input of g(z) so that most inputs fall near the point where g(x) exhibits its best properties. By combining Eq. (6) with Eq. (1) and ignoring e, we derive the following transformation:
E[r]
[[x]]
P
Norm[at [x]
(x
E[x]) f(wv)
Varla
Var [z]
Var
Var
Var
By replacing the function f with the quadratic function we obtain the expression of Poly
PolyNorm(zt = (xx -E(x)) g(mu)
/
Var
where
(x ku)²
5-k
g(x)
l E (2.438,5)
(8)
4(1 - k/
4/1//21
Here, l and are fixed parameters, and Var is a fixed value during inference. Consequently, is also a precomputable fixed value. Thus, PolyNorm[z] serves as the polynomial replacement for Norm(z] [x) We also apply this replacement during both the training and inference phases in order to maintain greater consistency.
The Numerical Constraint of PolyNorm. PolyNorm constrains inputs with variance less than or equal to A times the historical average to have zero mean and variance no greater than 1. The proof provided in Appendix A.
Analysis of Hyperparameters. Considering the average value g(ar) f(x) over the interval kp,)
denoted as RG we have:
kp g(z)
da 105 1) + (5 - k)2
4/.3/2
R
[(x) kipa Jo
6
can be proven that R is monotonically decreasing for E (2.438, 5) and satisfies 0.532 < S 0.913. On the other hand, we note that follows lognormal distribution, as shown in Fig. 2. The lognormal distribution exhibits a long-tail characteristic. Experimental statistics show that the probability of exceeding 3 is still approximately 3 x 10-4. while the probability of exceeding 5 falls below x 10-5 Since the monotonic decreasing range of g(z) increases as & increases, increasing the value of i enhances the numerical stability of PolyNorm
wider range of

---

Published as a conference paper at ICLR 2026
values. That is, although decreasing k improves the fitting accuracy of g(z) to f(x), too small value of & will lead to a higher proportion of samples with numerical instability. Fig. 3 illustrates the comparison between g(x)) under different k and a values, and f(z). We empirically verify that k = 4 is a choice that balances both fitting accuracy and stability. The value has relatively minor impact accuracy. In this work, consistently use the empirical hyperparameters k and μ = 2. The corresponding g(x) is:
g(x) - 0.01473x 0.23565x + 1.11937
4.4 OVERALL DESIGN RECIPE
In summary, we adopt the following fully polynomial replacement strategy:
For activation functions (e.g., ReLU, GELU), we employ trainable low-degree polynomial activa- tions (Lee et al., 2021: Peng al.. 2023b), combined with dropout to reduce overfitting. This denoted as PolyAct. is defined as
PolyAct(a) = Dropout
where (; are trainable coefficients and & are fixed adjustment factors. In this work, we consistently adopt ultra-low-degres polynomials with i S 3. For softmax attention replacement in ViT, adopt Linear Attention with Rotary Position Embedding (RoPE) (Su et al., 2024), defined as
LinearAttn(21 (1)) = RoPE(Q) RoPE(K)
(10)
where RoPB(.) denotes the rotary position embedding operation, which is composed entirely of runtime constants and linear operations. The max pooling layer is replaced with the average pooling layer (Gilad- BachhBa et al., 2016). Normalization layers are replaced with the proposed Poly Norm layer defined in Eq. (7). To provide better initialization for Var (the running average of Var[æ: during training), we still employ Eq. (1) during the warmup training epochs. To further improve the stability and accuracy of PolyNorm, when adopting Eq. (7) in training we introduce two penalty loss terms, L1 and L2, based on the magnitude of v (see Eq. (6)) and its deviation from 1:
C
D AI C2 C==N
(e, 1)3.>2 X2.
(11)
where N is the number of PolyNorm layers, Uú is the value of the i-th PolyNorm layer, and Y A2 are scaling coefficients. The introduction of L1 suppresses excessively large v values, enhancing stability, while L2 encourages the distribution of values to be closer to I, which is the optimal region for the function g(x).
Fig. illustrates overall design framework, which achieves near-extreme acceleration of the security scheme while largely preserving the capability the original model.
EXPERIMENT
5.1
EXPERIMENTAL SETUP
Architectures and Datasets. We evaluate ULD-Net on both CNN models (ResNet (He et al., 2016), VanillaNet family (Chen al., 2023)) and ViT-Small (Dosovitskiy al., 2021: Wightman, 2019). The datasets used include CIFAR-10. CIFAR-100, Tiny-ImageNet, and ImageNet.
Comparison with Prior Works. We conduct fair comparison of ULt terms of both model accuracy and HE inference speed against diverse set of toite--f-thh-arr approaches. These include fully polynomial replacement methods (Lee et al., 2021: Tong et al., 2024), partial polynomial re- placement methods (Cho et al., 2022; Peng al., 2023a), and recent Transformer HE inference acceleration work (Zhang et al., 2024).
ULD-Net Setup and Training. We follow the replacement strategy described in Subsection 4.4. Additional hyperparameters and training details are provided in Appendix B. Training is conducted using PyTorch 2.7 on NVIDIA A A10 GPUs.
7

---

Published as a conference paper at ICLR 2026
Client Private Inpui
Model Vendor
Polynomial Rephecement
Only uses and
boost spoed
Vir
CNN
Fully Polynomial ViT
Fully Polynomial CNN
Layer Norm
Conv
Nora
Poly
Conv
PolyNorn
0
MLP
PolyNorm
PolyAct
Emnline
Privero Infeerence Empline
Encrypt
Conv
Línear Attn
Conv
Ret UGGLU
PolyNoom
Add
Layer
PolvAct
Paly
Pols
Decrypt
Conv
Linear
Conv
Corvv
GELU U
Softmax Attn
PolsAct
Audd
Lincar
Linear
Rel
Poly
Add
Evaluation
RoFE(Q))
result:
Figure 4: Our lew-degree fully polynomial model design framework. Poly denotes a quadratic polynomial function.
Comparison with SOTA fully polynomial replacement methods in terms of accuracy and HE inference latency (on ResNet- 18/ImageNet, original aceuracy: 69.76%). The reported latency covers both single polynomial activation function and the entire model.
Table I:
ResNet-18 ImageNet
Activation Degree
Test
Activation Latency (s)
Model Latency (s)
Speedup
Speedup
(Fully Polynomial)
Acc.
Lee et al. (2021)
6075
69.35%
16448
16.06x 8. 8.12x
144896
3.50
SMART-PAF
81
69.40%
8311
112277
2.76x
ULD-Net (Ours)
2
69.79%
1024
41408
HE Latency Evaluation. We evaluate the HE inference latency of all experiments on machine equipped with an AMD Threadripper 3975WX CPU under the single-thread setting. Microsoft SEAL version 3.4.5 (SEAL) is used to implement the RNS variant of the CKKS scheme (Cheon al., 2018). We measure computation latency by running 20 samples and reporting the average. Our encryption parameter setting follows prior work (Tong et al., 2024), with polynomial degree 215 and modulus 881, ensuring a 128-bit security level (Albrecht et al., 2021; 2015) against known LWE attacks.
5.2 EXPERIMENT RESULTS
Comparison with SOTA Fully Polynomial Replacement Methods. We compare ULD-Net with Lee (Lee et al., 2021) and SMART-PAF (Tong et al., 2024) on fully polynomial ResNet-15 18 training with ImageNet. The results are presented in Table 1. All three methods enable stable training of fully polynomial ResNet-18 on ImageNet and achieve test accuracy comparable to the original model, with the main difference lying in the polynomial degree. Lee and SMART-PAF approximate the activation function using cascaded polynomials, leading to very high equivalent polynomial degrees and correspondingly high HE multiplicative depth. The multiplicative depth is generally regarded as the primary determinant of HE computation speed, and it grows proportionally with the logarithm of the polynomial degree. contrast, ULD-Net, with the aid of PolyNorm, performs the replacement entirely with quadratic activation functions (polynomial degree and multiplicative depth both equal 2). This not only achieves 8.12x speedup for the activation function and a 2.76 speedup for the entire model over SMART-PAF (the current SOTA), but also benefits from the non-linear functionality provided by quadratic activation functions (Peng et al., 2023b), leading to the highest accuracy among all methods (i.e., +0.39% higher than SMART-PAF and +0.03% higher than the original model).
Comparison with SOTA Partial Polynomial Replacement Methods. For the remaining ReLU functions in partial replacement methods, we adopt the approximation proposed by Lee et al. (2021). As shown in Table 2, ULD-Net demonstrates significant advantage in HE latency compared with SNL (Cho et al., 2022) and AutoReP (Peng et al., 2023a), achieving up to a 2.88x speedup acti- vation latency and 3 speedup in overall model latency. This improvement arises because full
8

---

Published as a conference paper at ICLR 2026
Table Comparison of accuracy and HE latency of non-polynomial operators for fully polynomial ViT-Small, Patch size is 4 on CIFAR- 10 and 16 on Iiny-lmageNet.
Dataset Original Acc.
Non-Polynomial Operator Latency (s)
Method
Test Ace.
Speedup
Softmax
LayerNorm
GELU
Total
CIFAR-10
NEXUS
91.39%
3055
2080
2860
7995
20.5
91.77%
ULD-Net (Ours)
91.48%
156
156
78
390
Tiny-ImageNet
NEXUS
60.52%
9259
6304
8668
24231
20.5x
60.90%
ULD-Net (Ours)
61.40%
472
474
236
1182
Using RoPE Attention.
replacement reduces the overall evaluation circuit depth, thereby lowering the need for bootstrapping and further decreasing the end-to-end model latency.
Moreover, partial polynomial re- placement methods generally cannot be directly extended to fully poly- nomial replacement replacements, as they fail to provide the required numerical sta- bility. From the accuracy perspec- tive, ULD-Net fully leverages the benefits of polynomial activations (quadratic in this case), achieving curacy even higher than the origi- nal model (+0.97%) and outperform- ing AutoReP by +3.33%. Therefore, ULD-Net clearly surpasses the exist- ing SOTA partial polynomial replacement methods in both accuracy and efficiency.
Table 2:
Comparison with SOTA partial polynomial re- placement methods (on CeaNee-18/CIAA--III original ac- curacy: 77.84%).
ReLU Replace Ratio Test Acc.
Activation Latency (s)
Model Latency (s)
Method
SNL 0.88
73.75%
45
2052
AutoReP 0.87
75.48%
46
2053
AutoReP 0.93
74.92%
35
2042
ULD-Net
78.81%
16
647
(Ours)
Evaluation with VIT-Small and ViT-Base. Our experiments demonstrate that ULD-Net scales to ViT-Small and ViT-Base, successfully training both models on ImageNet and achieving accuracy comparable the original versions (76. 7% vs. 76.5% and 75.2% vs. 75.3%, reported by Heo al. (2021)). In Table 3, we compare UL.D-Net with the recent Transformer HE inference acceleration framework NEXUS (Zhang al., 2024) on ViT-Small. Although NEXUS based on polynomial approximation, it requires very high polynomial degrees: the multiplicative depths of Softmax, Lay- crNorm, and GELU reach 16, 16, and 14, respectively. In contrast, ULD-Net uses RoPE, PolyNorm, and Poly Act (cubic in this case), which require multiplicative depths of only 2, 3, and 3. This leads to 20.5x speedup over NEXUS in total non-polynomial operator latency. ULD-Net also achieves strong accuracy: CIFAR- 10 it is +0.09% higher than NEXUS (-0.29% compared the original model), and on Tiny-ImageNet it exceeds NEXUS by +0.88% and the original model by +0.50%
These results demonstrate that ULD-Net has been validated the scale of modern Transformer models up to ViT-Base (approximately 86M parameters). Extending the proposed low-degree poly- nomial design to even larger-scale Transformers, such as ViT-Large, BERT-Large, or GPT-2, con- stitutes an important direction for future work.
Experiments with the VanillaNet family. VanillaNet (Chen et al., 2023) a lightweight CNN model that achieves strong accuracy perfor- mance on ImageNet. We apply ULD- Net to Van6 to validate its broad applicability and scalabil- ity. As shown in Table 4, ULD- Net successfully enables fully poly- nomial VanillaNets be trained sta- bly on ImageNet, achieving accuracy close that of the original models
Table 4: Extended experiments of ULD-Net with the Vanil- laNet family on ImageNet.
Model Activation Test Acc. Latency (s) Latency (s)
Activation Model
Original Acc. Degree
VanillaNet-5
2
72.43%
478
3469
72.49%
VanillaNet-6 76.36%
74.25%
597
4337
3
76.03%
939
4678
VanillaNet-7
2
74.91%
717
5204
77.98%
3
76.40%
1126
5614

---

Published as a conference paper at ICLR 2026
while maintaining substantially lower overall HE latency. In particular, VanillaNet-7 reaches 76.40% accuracy with a 7.4x HE latency speedup compared to ResNet-18.
CONCLUSION
We introduced ULD-Net, training methodology for ultra-low-degne degree fully polynomial networks at ImageNet and transformer scale. With polynomial-only normalization and operator replacements, ULD-Net overcomes prior instability and scalability issues. Experiments on ViT-Small and ViT- Base achieve 76. 70% and 75.20% top-1 accuracy ImageNet, representing the first ultra-low- degree fully polynomial ViT models trained at this scale.
7
ACKNOWLEDGMENTS
This research was supported in part by NSF ECCS-2534861, CNS-2505747, and CNS-2348733.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Aws sagemaker. httpps///avs..mmaaooo..o//////es
Azure
ml. machine-learningg 2016.
httpe://aaueeemcccooot.cccoorrre
Ahmad AI Badawi, Jin Chao, Jie Lin, Chan Fook Mun, Jun Jie Sim, Benjamin Hong Meng Tan, Xiao Nan, Khin Mi Mi Aung, and Vijay Ramaseshan Chandrasekhar. Towards the alexnet moment for homomorphic encryption: Henn, the first homomorphic cnn on encrypted data with gpus. IEEE Transactions on Emerging Topics in Computing, 2020.
Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, et al. Homomorphic encryption standard. Protecting privacy through homomorphic encryption, pp. 31-62, 2021.
Martin R Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 93):: 2015.
Rachid Elkadi Ali, Jaewoo So, and Salman A. Avestimehr. On polynomial approximations for
privcc-preserving and verifiable relu networks. arXiv preprint arXiv:2011.05550 2020.
Toluwani Aremu and Kandan Nandakumar. Polykervnets: Activation-free neural networks for effi- cient private inference. In 2023 JEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pp. 593-604. IEEE, 2023.
Hanting Chen, Yunhe Wang. Jianyuan Guo, and Dacheng Tao. Vanillanet: the power of minimalism in deep learning, 2023. URL https: arxiv..i.....
Tianyu Chen, Hangbo Bao, Shaohan Huang, Li Dong, Binxing Jiao, Daxin Jiang, Haoyi Zhou, Jianxin Li, and Furu Wei. The-x: Privacy-preserving transformer inference with homomorphic org. abs 2206 00216.
encryption, 2022. URL https:://///
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arith- metic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security, pp. 409 437. Springer, 2017.
Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. A full rns vari- ant of approximate homomorphic encryption. In International Conference on Selected Areas in Cryplography, pp. 347-368. Springer, 2018.
Minsu Cho, Ameya Joshi, Siddharth Garg, Brandon Reagen, and Chinmay Hegde. Selective network linearization for efficient private inference. ArXiv, abs/2202.00340, 2022. URL https: h/mpps:://pp// //api. org/ gemanticscher wwt Chtp//CrpuusDDDD 244634086 224.:ppsI:::45400..
Edward Chou, Josh Beal, Daniel Levy, Serena Yeung, Albert Haque, and Li Fei-Fei. Faster cryp- tonets: Leveraging sparsity for real-world encrypted inference. arXiv preprint arXiv:1811.0995: 2018.
Roshan Dathathri, Olli Saarikivi, Hao Chen, Kim Laine, Kristin Lauter, Saeed Maleki, Madanlal Musuvathi, and Todd Mytkowiez. Chet: an optimizing compiler for hully-homomopphic neural- network inferencing. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 142-156, 2019.
Ahmed Diaa, Lucas Fenaux, Thomas Humphries, Matthew Dietz, Farhad Ebrahimianghazani, Ben- jamin Kacsmar, Xiao Li, Nicolai Lukas, Reza A. Mahdavi, Shiho Oya, and Elmira Amjadian. Fast and private inference of deep neural networks by co-designing activation functions. In 33rd USENIX Security Symposium (USENIX Security 24). pp. 2191-2208, 2024.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition at scale. In International Conference Learning Representations (ICLR), 2021.

---

Published as a conference paper at ICLR 2026
Karthik Garimella, Nandan Kumar Jha, and Brandon Reagen. Sisyphus: A cautionary tale of using low-degree polynomial activations in savvacy-preeevvnng deep learning, 2021.
Craig Gentry. Fully homomorphic encryption using ideal lattices. In STOC, volume pp. 169-178, 2009.
Ran Gilad- Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Werns- ing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International conference on machine learning, pp. 201-210. PMLR, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Byeongho Heo, Sangdoo Yun, Dongyoon Han, Sanghyuk Chun, Jihun Choe, and Seong Joon Oh. Rethinking spatial dimensions of vision transformers. In Proceedings of the IEEE/CVF Interna- tional Conference on Computer Vision (ICCV), 2021.
Ehsan Hesamifard, Hassan Takabi, and Mehdi Ghasemi Cryptodl: Deep neural networks over encrypted data, arXiv preprint 1rXivv1711.055 2017.
Miran Kim, Xiaoqian Jiang, Kristin Lauter, Elkhan Ismayilzada, and Shayan Shams. Secure human action recognition by encrypted neural network inference. Nature communications, 13(1):1-13, 2022.
Junghyun Lee, Eunsang Lee, Joon- Woo Lee, Yongjune Kim, Young- Sik Kim, and Jong-Seon No. Precise approximation of convolutional neural networks for homomorphically encrypted data, 2021.
Qiuling Lou, Yu Shen, Hailun Jin, and Linnan Jiang. Safenet: A secure, accurate and fast neu- ral network inference. In International Conference on Learning Representations, 2021. URL http:///epeeeeeeeeeeeeeee.eeeee. net. wttp://wwwee.eett/oooonnnnddee forum?1d=022dbFm55
Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, Farinaz Koushanfar, Abhi Shelat, and Ahmad-Reza Sadeghi. Delphi: A cryptographic inference service for neural networks. In 29th USENIX Security Symposium (USENIX Security 20), pp. 2503-2520, 2020.
Jubyung Park, Min Jeong Kim, Wooseok Jung, and Jung Ho Ahn. Aespa: Accuracy preserving lew-degree polynomial activation for fast private inference. arXiv preprint arXiv:2201.06699 2022.
Hongwu Peng. Shaoyi Huang, Tong Zhou, Yukui Luo, Chenghong Wang, Zigeng Wang, Jiahui Zhao, Xi Xie, Ang Li, Tony Geng, et al. Autorep: Automatic relu replacement for fast private network inference. In Proceedings of the IEEF/CVE International Conference on Computer Vi- sion, pp. 5178-5188, 2023a.
Hongwu Peng. Ran Ran, Yukui Luo, Jiahui Zhao, Shaoyi Huang, Kiran Thorat, Tong Geng, Chenghong Wang, Xiaolin Xu, Wujie Wen, and Caiwen Ding. Lingen: Structural linearized graph convolutional network for homomorphically encrypted inference, 2023b. URL https: 14331.
Ran Ran, Wei Wang, Quan Gang, Jieming Yin, Nuo Xu, and Wujie Wen. Cryptogen: Fast and scalable homomorphically encrypted graph convolutional network inference. Advances in Neural Information Processing Systems, 35:37676-37689, 2022.
Ran Ran, Nuo Xu, Tao Liu, Wei Wang, Gang Quan, and Wujie Wen. Penguin: Parallel-packed homomorphic encryption for fast graph convolutional network inference. Advances in Neural Information Processing Systems, 19:19404-19116, 2023.
SEAL. Microsoft SEAL (release 3.4). http::/gitaaa..ccci//eeeeeeeeeee 2019. Microsoft Research, Redmond, WA.
October
12

---

Published as a conference paper at ICLR 2026
Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputingg 568:127063, 2024. ISSN 0925-2312. doi: http://dd..og///oooooff.uvvmeem1 sciencedi rect www.coo//ssooooo http://cc.c.aaaeeaaaaata////////
URL https: httss://wwwwwww //www.
Jianming Tong, Jingtian Dang, Anupam Golder, Callie Hao, Arijit Raychowdhury, and Tushar Kr- ishna. Accurate low-degree polynomial approximation of non-polynomial operators for fast pri- vate inference in homomorphic encryption, 2024.
Ross Wightman. Pytorch image models. 2019.
sytorch-image-men
Jiawen Zhang, Xinpeng Yang, Lipeng He, Kejia Chen, Wen jie Lu, Yinghao Wang, Xiaoyang Hou, Jian Liu, Kui Ren, and Xiaohu Yang. Secure transformer inference made non-interactive. Cryptol- ogy ePrint Archive, Paper 2024/136, 2024. URL https::t////.. wttps:://ppp.iieee
iacr. wwg//////222 /136.
Itamar Zimerman, Moran Baruch, Nir Drucker, Gilad Ezov, Omri Soceanu, and Lior Wolf. Con- verting transformers to polynomial form for secure inference over homomorphic encryption. In Proceedings of the 41st International Conference on Machine Learning, ICML'24. JMLR.org. 2024.
A PROOF OF POLYNORM NUMERICAL CONSTRAINT
Considering the mean and variance of PolyNorm(z]] evident that
E[PolyNorm(a]) [x]]] E[x E[æ]] g(wv) V
Var
and then
(ooloo =|PooyNorm[]]] (EPPolyNooommaalll [o(ooyNomm(2]]] = =B[(r [[x)) 91 g(wv)2 "
Var
Var[z]]
g(wu)2
Var
f( )
(g(uv)
pm g(w))²
< for E (0,
Thus, PolyNorm ensures expected value of 0 and variance greater than for inputs satisfying Var < k- Var.
B ADDITIONAL TRAINING HYPERPARAMETERS AND SETTINGS
For additional implementation details, please refer our GitHub repository and accompanying instructions, which serve as the authoritative reference for all experimental configurations and hy- perparameter settings.
Polynomial Operator Parameters. The parameter ranges are set follows: For the quadratic
operator, Oo 0.5, e = 1, C2 0.1. the cubic operator, ep 0.5, ca = 1, <2 0.1, and c3 0.01. The dropout rate is selected from the range j0, 0.3]. All pooling layers are replaced with AvgPool.
Other Hyperparameters and Settings. The training hyperparameters include those for ResNet- 18, the VanillaNet series, and ViT-Small. Additional training hyperparameters are summarized in Table 5. The loss function is defined LeE + L1 + L2, where Lce denotes the cross-entropy loss, and C,, L2 are defined in Eq. 11. Starting from the second epoch, PolyNorm is used to replace the original normalization layers during training. During inference, Pory is always applied.
13

---

Published as a conference paper at ICLR 2026
Table Training hyperparameters for ResNet-118, VanillaNet series, and ViT-Small. Definitions of A and X2 are given in Eq. (11).
Hyperparameter
ResNet-18
VanillaNet Series
ViT-Small
Batch Size
1600
960
300
A
0.001
0.001
0.001
A2
0.01
0.01
0.01
Epochs
300
300
300
Optimizer
LAMB
LAMB
LAMB
Learning Rate
5 x 10-3
5 x 10
5 x 10-3
Warmup Epochs
1
PolyAct Degree
2
2,3
Dropout
0.0
0.2
0.2
Mixup
0.0
0.2
0.2
Cutmix
0.0
1.0
1.0
k
4
4
4
2
2
C LLM USAGE
Large Language Models. We acknowledge the use of Large Language Models (LLMs) during the preparation of this paper. LLMs were employed exclusively to aid in language refinement and stylistic polishing of the manuscript. They were not used to generate research ideas, design exper- iments, analyze results, or mathematical derivations. All technical content, experimental design, implementation, and analysis are the sole work of the authors.
14


Reviews:
[{"review_id": "9k2AQwgkSJ", "reviewer": "Reviewer_2kfr", "summary": "The main bottleneck in performing homomorphic computation on modern AI models such as ResNet and ViT lies in the non-linear operations and non-linear normalization layers. These operations are known to play a crucial role in the overall performance of these models.\nIn this paper, we propose a method to replace all non-linear operations in these models with polynomial operations while maintaining comparable performance.", "questions": "I would like to know how the convolution layer was implemented. There are two possible methods — the MPConv approach and the Neujeans approach. Since this paper does not use bootstrapping (as it is implemented using SEAL), I assume it employs the MPConv method. Is that correct?\n\nIf bootstrapping were to be applied, the Neujeans method could also be used. Do you think incorporating this method would further improve performance?\n\nAlso, for the ViT comparison, it would be good to include THOR and PowerFormer models in the evaluation.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The non-polynomial parts of LayerNorm are replaced with a quadratic function and ensured numerical stability by fixing the normalization axis. Additionally, softmax attention and ReLU/GELU functions are replaced with low-degree polynomials, while still demonstrating strong performance on ResNet and ViT models — thereby validating the practical effectiveness of their approach.\n\nAlthough there have been several prior attempts to approximate non-polynomial functions with low-degree polynomials, the introduction of normalization-axis fixing in LayerNorm to improve training stability stands out as a clear and meaningful contribution. One potential concern is whether this simplification might lead to a loss of expressiveness or overfitting issues, but the authors address this through penalty regularization terms and dropout, successfully mitigating such risks. Their experiments on the ImageNet dataset show accuracy comparable to existing methods, which effectively demonstrates that the model’s representational capacity is preserved.\n\nThis finding has significant implications for privacy-preserving machine learning (PPML): it suggests that by incorporating axis fixing, penalty loss terms, and dropout during training, one can approximate non-polynomial layers using only low-degree polynomial functions without severe performance degradation. Even though the paper does not explicitly explore this, the same methodology could likely be extended to other non-polynomial layers.\n\nFinally, the paper clearly describes the conversion procedure for non-polynomial layers, which makes the proposed approach extensible and comparable for future applications in other architectures.", "weaknesses": "There was no comparison with state-of-the-art (SOTA) models for ViT in the paper. Among the current SOTA transformer models implemented under homomorphic encryption, two representative examples are THOR and PowerFormer. As far as I know, the NEXUS model is less efficient compared to these two models. Therefore, in Table 3, for the comparison of Softmax, LayerNorm, and GELU, the authors should include THOR and PowerFormer rather than limiting the comparison to NEXUS.\n\nMoon, Jungho, et al. \"THOR: Secure transformer inference with homomorphic encryption.\" CCS 2025.\nPark, Dongjin, et al. \"Powerformer: Efficient and High-Accuracy Privacy-Preserving Language Model with Homomorphic Encryption.\" ACL 2025.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "3DkRocAD1L", "reviewer": "Reviewer_puCa", "summary": "This paper presents an interesting approach to building homomorphic encryption (HE)-friendly neural networks by introducing PolyNorm, a polynomial-only normalization technique that eliminates the non-polynomial square root operation from traditional normalization layers. The authors demonstrate solid results on small to medium-sized models, showing significant reductions in HE computational complexity (up to 2.76× speedup on ResNet-18(ImageNet)) compared to prior work, and notably extend the approach beyond CNNs to Vision Transformers, which is a positive step forward. However, the practical applicability remains questionable, as the evaluation is limited to relatively small models like ViT-Small on CIFAR and Tiny-ImageNet. At the same time, the paper lacks critical training-time measurements and any demonstration on large-scale, real-world language models—a significant gap given recent progress in applying HE to LLMs like GPT-2. More fundamentally, the core concept of designing task-specific and model-specific networks for HE is not new and dates back to early CryptoNet, which raises concerns about whether the proposed method can generalize beyond its evaluated scope, especially given that simpler polynomial-based models tend to show accuracy degradation with increased model depth (as evidenced by the 1.58% drop in VanillaNet-7). To strengthen the contribution, the authors should either demonstrate applicability to larger, more practical models, provide a detailed analysis of training overhead, or show how existing pre-trained models can be efficiently adapted to this polynomial-only framework rather than requiring complete retraining from scratch. While the technical execution is sound and the incremental improvements are noteworthy, a more transparent discussion of the method's generalizability and scalability limits would better position this work within the broader context of practical HE-based machine learning.", "questions": "What are the total training times and computational costs for these models, and can the approach be scaled to train LLMs?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a solution to a fundamental problem in HE-based neural networks—replacing the non-polynomial square root operation in normalization with a quadratic polynomial approximation (PolyNorm)—which elegantly enables training fully polynomial networks from scratch and achieves substantial HE inference speedups 2.76× to 20.5× (up to 20.5× reduction in the latency of non-polynomial operations on ViT-Small) while actually improving accuracy compared to prior post-hoc approximation methods. Beyond the technical innovation, the authors demonstrate that their approach scales beyond CNNs to Vision Transformers, breaking the traditional limitation of task- or model-specific HE designs and suggesting broader applicability across different architectures.", "weaknesses": "The evaluation is limited to relatively small models (ResNet-18, VanillaNet, ViT-Small on CIFAR/Tiny-ImageNet), with no evidence of scalability to larger practical models or LLMs where HE-based inference would be most valuable. Crucially, the paper provides no training time measurements or overhead analysis for ViT-Small, making it impossible to assess whether the polynomial-only design introduces significant computational burdens during training that could limit practical adoption. Furthermore, the approach still requires training models from scratch with polynomial operators rather than adapting existing pre-trained models. The already observable accuracy degradation in deeper networks (1.58% drop for VanillaNet-7) raises serious concerns about whether the method's performance will generalize to significantly larger architectures, where polynomial activation functions may struggle even more due to limited expressiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "pcEudIwAqG", "reviewer": "Reviewer_G9h4", "summary": "To enable privacy-preserving machine learning (PPML) in homomorphic encryption (HE) settings, fully polynomial model design has become a promising approach. Previous works  suffer from high degree polynomials and high inference latency. This paper proposes normalization axis principle and two approximations of nonlinear approximation, PolyNorm (polynomial-only normalization) and PolyAct, with low-degree polynomials to enable efficient HE inference. ULD-net uses multiplicative depth less than 3 for each operators.", "questions": "- Authors introduce approximate inverse square root function well near $\\mu$, but it does not approximate well on other ranges. Why did the authors propose a new approximation of inverse square root function that have two parameters $\\mu$ and $k$ instead of using the well-known approximation methods of inverse square root function such as Newton-Rapson’s method? (e.g., Cho, W. *et. al.* used Newton’s method to approximate inverse square root)\n\nCho, W., Hanrot, G., Kim, T., Park, M., & Stehlé, D. (2024, December). Fast and accurate homomorphic softmax evaluation. In *Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security* (pp. 4391-4404).\n\n- Determination of the best combination of parameters $(\\mu,k)$ is based on experiment results without solid mathematical backbone. Will there be any mathematical reasons to determine the best parameter combination?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors propose the ultra low-degree training methodology replacing the nonlinear operations in HE. Authors provide replacement of non-linear operations from previous works (Roformer) and propose PolyNorm for the normalization layer, i.e., providing full end-to-end recipe to enable HE inference.\n\nSu, Jianlin, *et al*. \"Roformer: Enhanced transformer with rotary position embedding.\" *Neurocomputing* 568 (2024): 127063.\n\n- Proposed (and provides) logical mathematical reason for choosing the normalization axis. Focusing on the reduction in variance of the input for polynomial function is a logical process, and a good approach.", "weaknesses": "- Although ULD-Net achieved 76.40% accuracy (1.58% drop) from the largest model tested by the authors, VanillaNet-7, batch normalization and layer normalization are standard techniques, therefore the approximation (PolyNorm) might incur a performance drop on more complex task or different model.\n- Formulation of the inverse square root approximation depends on $\\mu$ and $k$ and the choice of them are based on experiments. $\\mu$ and Var varies when dataset differs — we cannot suggest a uniform optimal choice for these statistical values.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "HLXyxYM9ie", "reviewer": "Reviewer_Lj1U", "summary": "The authors propose a training framework for DNNs composed entirely of low-degree polynomial operations to make them natively suitable for privacy-preserving inference. The authors introduce PolyNorm that stabilizes training by maintaining activation ranges within well-conditioned bounds, along with a principled choice of normalization axes and auxiliary loss penalties for numerical control. ULD-Net achieves SOTA accuracy–latency trade-offs on encrypted inference, surpassing prior fully polynomial and partial polynomial methods with up to 3× faster inference and +3.3% accuracy gains, and scaling to large architectures such as ResNets and Vision Transformers.", "questions": "- How does PolyNorm fundamentally differ from earlier polynomial stabilization methods or activation co-design approaches? What exactly does it do differently?\n\n- Can the authors provide ablation results isolating the effect of PolyNorm and the normalization-axis principle to verify that these components are responsible for the reported stability and accuracy gains? Or can they provide a description as to what offers stability guarantees in their proposed approach.\n\n-  Could the authors include comparisons with more recent baselines  to better contextualize ULD-Net’s performance and novelty?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The work Introduces a polynomial-only normalization mechanism (PolyNorm) that effectively stabilizes ultra-low-degree polynomial networks, addressing the long-standing issue of training instability in fully polynomial architectures at ImageNet and transformer scale.\n- The method demonstrates strong empirical performance and scalability than prior state-of-the-art polynomial or partially polynomial methods.", "weaknesses": "- Very limited novelty. The authors failed to acknowledge or compare against highly relevant and more recent prior work [1, 2, 3, 4], all of which already introduced polynomial-only architectures or co-designed low-degree activation functions for PI. These prior works have also focused on low polynomial approaches, hence the ULD-Net's \"novel idea\" is an incremental extensions.\n\n- In addition to my main concern about the novelty, the proposed PolyNorm and normalization-axis heuristic are engineering refinements rather than fundamental algorithmic advances.\n\n- The adaptive numerical constraint and normalization principles are supported by descriptive reasoning but lack formal analysis or proofs of convergence and stability guarantees. The derivations are heuristic, and there is no quantitative ablation linking PolyNorm’s theoretical formulation to observed performance gains.\n\n- The experiments only compare against two baselines but omit many more recent and \"potentially\" stronger baselines [1, 2, 3, 4].\n\n- The authors admit that the polynomial activations tend to overfit and that accuracy degrades with depth (e.g., VanillaNet-7 drops 1.6% below the original) (PolyKervNets [3] and Sisyphus [5] mention this), yet they do not propose or analyze mitigation strategies beyond vague suggestions to enhance expressive power.\n\n**References**\n\n[1] Park J, Kim MJ, Jung W, Ahn JH. AESPA: Accuracy preserving low-degree polynomial activation for fast private inference. arXiv preprint arXiv:2201.06699. 2022 Jan 18.\n\n[2] Diaa A, Fenaux L, Humphries T, Dietz M, Ebrahimianghazani F, Kacsmar B, Li X, Lukas N, Mahdavi RA, Oya S, Amjadian E. Fast and private inference of deep neural networks by co-designing activation functions. In33rd USENIX Security Symposium (USENIX Security 24) 2024 (pp. 2191-2208).\n\n[3] Aremu T, Nandakumar K. Polykervnets: Activation-free neural networks for efficient private inference. In2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) 2023 Feb 8 (pp. 593-604). IEEE.\n\n[4] Ali RE, So J, Avestimehr AS. On polynomial approximations for privacy-preserving and verifiable relu networks. arXiv preprint arXiv:2011.05530. 2020 Nov 11.\n\n[5] Garimella K, Jha NK, Reagen B. Sisyphus: A cautionary tale of using low-degree polynomial activations in privacy-preserving deep learning. arXiv preprint arXiv:2107.12342. 2021 Jul 26.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)