DeepReShape: Redesigning Neural Networks for Efficient Private Inference
Prior work on Private Inference (PI) -- inferences performed directly on
encrypted input -- has focused on minimizing a network's ReLUs, which have been
assumed to dominate PI latency rather than FLOPs. Recent work has shown that
FLOPs for PI can no longer be ignored and incur high latency penalties. In this
paper, we develop DeepReShape, a technique that optimizes neural network
architectures under PI's constraints, optimizing for both ReLUs and FLOPs for
the first time. The key insight is strategically allocating channels to
position the network's ReLUs in order of their criticality to network accuracy,
simultaneously optimizes ReLU and FLOPs efficiency. DeepReShape automates
network development with an efficient process, and we call generated networks
HybReNets. We evaluate DeepReShape using standard PI benchmarks and demonstrate
a 2.1% accuracy gain with a 5.2$\times$ runtime improvement at iso-ReLU on
CIFAR-100 and an 8.7$\times$ runtime improvement at iso-accuracy on
TinyImageNet. Furthermore, we investigate the significance of network selection
in prior ReLU optimizations and shed light on the key network attributes for
superior PI performance.
Nandan Kumar Jha, Brandon Reagen
# DeepReShape: Redesigning Neural Networks for Efficient Private Inference

###### Abstract

Prior work on Private Inference (PI)-inferences performed directly on encrypted input-has focused on minimizing a network's ReLUs, which have been assumed to dominate PI latency rather than FLOPs. Recent work has shown that FLOPs for PI can no longer be ignored, and also have high latency penalties. In this paper we develop DeepReShape: a network redesign technique that tailors architectures to PI constraints, optimizing for both ReLUs and FLOPs for the first time. The key insight is that a strategic allocation of channels such that the network's ReLUs are distributed in their criticality order simultaneously optimizes both ReLU and FLOPs efficiency. DeepReShape automates network development with an efficient process, and we call generated networks HybReNets. We evaluate DeepReShape using standard PI benchmarks and demonstrate a 2.1% accuracy gain with a 5.2\(\times\) runtime improvement at iso-ReLU on CIFAR-100, and a 8.7\(\times\) runtime improvement at iso-accuracy on TinyImageNet. Finally, we show that prior PI-specific network optimizations are complimentary, and apply them to HybReNets for further benefit.

## 1 Introduction

As machine learning inferences are increasingly performed in the cloud, privacy concerns have emerged, resulting in the development of private inference (PI) where a client sends encrypted input to the cloud service provider, enabling inferences without exposing their data. While effective, the usage of complex cryptographic primitives [1; 2; 3; 4; 5; 6; 7] in PI results into substantially higher computational and storage overheads [8; 9; 10; 11; 12; 13].

Prior work on PI-specific network optimization [14; 15; 16; 17; 18; 19; 20; 21] has primarily focused on mitigating overheads associated with non-linear (ReLU) operations, assuming FLOPs are free. Specifically, methods such as CryptoNAS [14] and Sphynx [19] use neural architecture search to optimize ReLU efficiency and disregard FLOP implications. However, a recent work [13] has challenged this assumption, emphasizing that FLOPs do carry significant latency penalties.

Improving PI efficiency is further constrained by the limitations associated with current ReLU-optimization techniques. Their effectiveness largely depends on the selection of the input network, resulting in significant performance disparities that cannot be solely attributed to the FLOP count or accuracy of the input networks. Moreover, techniques such as DeepReDuce [17] encounter scalability issues and require considerable manual effort. While fine-grained ReLU optimization [20; 21] shows potential, its effectiveness is _confined_ to networks with specific ReLU distributions and tends to _underperform_ in networks with higher ReLU counts or altered ReLU distribution.

Another major challenge that persists in this domain is identifying network attributes that enhance PI performance. Current ReLU optimization methods [17; 20; 21] offer limited insight into the network features contributing to the improved PI performance. Moreover, it remains elusive whether a network with specific features can consistently outperform across various ReLU counts or if targeted ReLU counts determine the desired network attributes.
Addressing these issues, we introduce a novel design principle, "ReLU-equalization," which utilizes our main _insight_ is that by expanding the network's width while distributing its ReLUs according to their criticality order, we can control the FLOPs growth in deeper layers without sacrificing ReLU efficiency. Thus, achieving ReLU and FLOPs efficiency simultaneously.

Our _key observation_, termed "Capacity-Criticality-Tradeoff," demonstrate that different network features are desirable for superior performance at varying ReLU counts. We find that wider networks are beneficial only for higher ReLU counts, while the proportion of non-critical ReLUs is crucial for lower ReLU counts. This observation _challenges the commonly held belief_ that a network's overall ReLU count is the key determinant for superior performance at lower ReLU counts. By utilizing this, we achieved a significant reduction, up to **45\(\times\)**, in FLOPs when targeting lower ReLU counts.

Leveraging the above insights, we develop "DeepReShape," to redesign the classical networks and synthesize PI-efficient networks "HybReNet" with a computational complexity of \(\mathcal{O}(1)\). Our approach results in a substantial FLOPs reduction with fewer ReLUs, outperforming the state-of-the-art in PI. Specifically, compare to SENet [21], we achieve a 2.3\(\times\) ReLU and 3.4\(\times\) FLOPs reduction at iso-accuracy, and a 2.1% accuracy gain with a **12.5\(\times\)** FLOPs reduction at iso-ReLU on CIFAR-100. On TinyImageNet our approach saves **12.4\(\times\)** FLOPs at iso-accuracy.

Our key contributions are summarized as follows.

1. Perform an exhaustive characterization to understand the essential network characteristics, architecture and ReLUs' distribution, for PI efficiency and demonstrate their generalizability.
2. Propose _ReLU-equalization_, a novel design principle for distributing the network's ReLU in their criticality order, and designed a family of networks, _HybReNet_, tailored to the PI constraints.
3. Propose _ReLU-reuse_, a channel-wise ReLU dropping technique to systematically reduce the networks ReLUs count up to **16\(\times\)**.

## 2 Preliminary

**Private inference protocols and threat model:** We use Delphi [9] protocols, as also used in [17; 20], for private inference. In particular, for linear layers Delphi performs compute-heavy homomorphic operations [1; 2; 3] in the offline phase (preprocessing) and additive secret sharing [22] in the online phase, once the client's input is available. Whereas, for nonlinear(ReLU) layers it uses garbled circuits [23; 24]. Further, similar to, [25; 8; 9] we assume an honest-but-curious adversary where parties follow the protocols and learn nothing beyond their output shares.

**Architectural building blocks:** Figure 2 illustrates a schematic view of a standard four-stage network, with design hyperparameters. Similar to ResNet [26], it has a stem cell (to increase the channel count from 3 to \(m\)), followed by the network's main body (composed of linear and nonlinear layers, performing most of the computation), followed by a head (a fully connected layer) yielding the scores for the output classes. The network's main body is composed of a sequence of four stages, and the spatial dimensions of feature maps (\(d_{k}\times d_{k}\)) are progressively reduced by \(2\times\) in each stage (except Stage1), and feature dimensions remain constant within a stage. We keep the structure of the stem cell and head fixed and change the structure of the network's body using design hyperparameters.

Figure 1: HybReNet outperforms state-of-the-art (SOTA) ReLU-optimization methods [21; 20; 17], achieving higher accuracy (CIFAR-100) and significant reduction in FLOPs while using fewer ReLUs.
**Definitions and design hyperparameters:** Each stage is composed of identical blocks1 repeated \(\phi_{1}\), \(\phi_{2}\), \(\phi_{3}\), and \(\phi_{4}\) times in Stage1, Stage2, Stage3, and Stage4 (respectively), and known as _stage compute ratios_. The output channels in stem cell (\(m\)) is known as _base channels_, and the number of channels progressively increases by a factor of \(\alpha\), \(\beta\), and \(\gamma\) in Stage2, Stage3, and Stage4 (respectively), and we termed it as _stagewise channel multiplication factors_. These width and depth hyperparameters primarily determine the distribution of FLOPs, ReLUs, and parameters in the network. When we widen the network: (1) by augmenting \(m\), which increases the #channels in each layer by the same factor, we denote this network as **BaseCh** (e.g., from \(m\)=64 to \(m\)=128); and (2) by homogeneously augmenting the (\(\alpha\), \(\beta\), \(\gamma\)), we denote this network as **StageCh** (e.g., from (\(\alpha\), \(\beta\), \(\gamma\)) = (2, 2, 2) to (\(\alpha\), \(\beta\), \(\gamma\)) = (3, 3, 3)).

Footnote 1: Except the first block (in all but Stage1) which performs downsampling of feature maps by \(2\times\).

## 3 Essential Network Attributes for Efficient Private Inference

We presents our key observations highlighting the influence of network architecture and their ReLUs' distribution on the efficacy of private inference.

**Observation 1: ReLU's criticality-aware network widening approach can address the FLOPs-ReLU-Accuracy imbalance, a key shortcoming of existing network widening methods.** Despite a line of seminal work on the network's width expansion [27; 28; 29; 30], the approaches to leverage the potential benefits of increased width without incurring FLOPs-ReLU-Accuracy imbalance remains elusive. The prevailing network widening method (BaseCh), including WideResNet [27], offers _limited_ ReLU-efficiency due to the conservative (\(\alpha\), \(\beta\), \(\gamma\)) = (2, 2, 2) values 2, which constrain channel growth in subsequent stages and restrict the network's complexity per ReLU unit (see Table 1). Since prior ReLU optimization methods rely on classical networks, this limitation _prevents_ the full realization of potential benefits associated with increased network width.

Footnote 2: Even the state-of-the-art vision model RegNets [31] have \(1.5\leq\)(\(\alpha\), \(\beta\), \(\gamma\)) \(\leq\) \(3\), for FLOPs-efficiency reason.

In contrast, StageCh networks significantly improve ReLU efficiency compared to BaseCh networks by removing the constraint on (\(\alpha\), \(\beta\), \(\gamma\)) and requiring fewer ReLUs for a given complexity (Figure 3(a)). However, the superiority of StageCh networks remains evident until reaching accuracy saturation, which varies with network configuration. In particular, as shown in Figure 3(b), accuracy saturation for StageCh networks of ResNet18, ResNet20, ResNet32, and ResNet56 models begins (\(\alpha\), \(\beta\), \(\gamma\)) = (4, 4, 4), (5, 5, 5), (5, 5, 5), and (6, 6, 6), respectively, suggesting deeper StageCh network plateau at higher (\(\alpha\), \(\beta\), \(\gamma\)) values, and accurate prediction of saturation is challenging. This observations challenge the assertion made in [14], that model capacity per ReLU peaks at (\(\alpha\), \(\beta\), \(\gamma\)) = (4, 4, 4). Consequently, _the extent to which a network can benefit from increased width for superior ReLU efficiency remains an open question_.

Our proposed ReLUs' criticality-aware network widening approach effectively optimizes both ReLU and FLOPs efficiency, which a StageCh network fails to achieve as distinct homogeneous sets of (\(\alpha,\beta,\gamma\)) are required for FLOPs and ReLU efficiency. We leverage the _insight_ that ReLU efficient StageCh networks suffer from rapidly increasing FLOPs in deeper layers, while our approach limits excessive FLOPs in deeper layers without compromising ReLU efficiency. Consequently, our approach attains ReLU efficiency on par with StageCh networks while significantly lowering FLOPs. For instance, Figure 3(c,d) demonstrates that the ReLUs' criticality-aware ResNet18 network 5x5x3x maintains similar ReLU efficiency with a \(2\times\) reduction in FLOPs count compared to the StageCh network 5x5x5x. This FLOPs reduction is consistently attained across the entire spectrum of ReLU counts, employing both fine-grained and coarse-grained ReLU optimization.

\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & Stage1 & Stage2 & Stage3 & Stage4 \\ \hline \(\frac{\sigma_{max}}{\sigma_{max}}\) & \(m(\frac{\sigma_{max}}{\sigma_{max}})\) & \(\alpha\)\(\beta\)\(m(\frac{\sigma_{max}}{\sigma_{max}})\) & \(\alpha\)\(\beta\)\(m(\frac{\sigma_{max}}{\sigma_{max}})\) \\ \(\frac{\sigma_{max}}{\sigma_{max}}\) & \(m^{\ell}\) & \(\alpha\)\(m^{\ell}\) & \(\alpha\)\(\beta\)\(m^{\ell}\) & \(\alpha\)\(\beta\)\(m^{\ell}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Network’s complexity (FLOPs and Params) per unit of nonlinearity varies with network’s width, and independent of the network’s depth. _Wider network require_ maintains similar ReLU efficiency with a 2\(\times\) reduction in FLOPs count compared to the StageCh network 5x5x5x. This FLOPs reduction is consistently attained across the entire spectrum of ReLU counts, employing both fine-grained and coarse-grained ReLU optimization.

Figure 2: Depiction of architectural hyperparameters and feature dimensions in a four stage network. For _fewer ReLUs for a given complexity_. (\(f\times f\) is the spatial size of kernel (e.g., \(3\times 3\)))
**Observation2: Performance of ReLU optimization methods is strongly correlated with the choice of input networks, leading to substantial performance disparities.** Table 2 lists input networks used in previous ReLU optimization methods with their relevant characteristics, while Figure 4 demonstrates how different input networks impact DeepReDuce [17] and SNL [20]. For DeepReDuce, accuracy differences of **12.9%** and **11.6%** at higher and lower iso-ReLU counts are observed. _These differences cannot be ascribed to the FLOPs or accuracy of the baseline network alone._ For instance, ResNet18 outperforms WideResNet22x8 despite having 4.4\(\times\) fewer FLOPs and a lower baseline accuracy, and ResNet32 outperforms VGG16 even though the latter has 4.76\(\times\) more FLOPs and a higher baseline accuracy.

**Observation3: Distinct network attributes are required for superior PI efficiency at higher and lower ReLU counts (Capacity-Criticality-Tradeeff).** To examine the essential network characteristics for PI efficiency across a broad spectrum of ReLU counts, we select three iso-ReLU ResNet18 variants with distinct ReLUs' distribution and FLOPs counts, achieved by altering the channel allocation per stage, in Table 3. In particular, 2x2x2x(\(m\)=32), 4x4x4x(\(m\)=16), and 3x7x2x(\(m\)=16) have stagewise channel allocation as [32, 64, 128, 256], [16, 64, 256, 1024], and [16, 48, 336, 672], respectively. We apply DeepReDuce and SNL on these networks and results are shown in Figure 5.

We observe that wider networks are superior _only_ at higher ReLU counts while networks with a higher proportion of non-critical ReLUs excel at lower ReLU counts. This trend is consistent with both DeepReDuce and SNL. Specifically, wider models 4x4x4x(\(m\)=16) and 3x7x2x(\(m\)=16) outperform 2x2x2x(\(m\)=32) at higher ReLU counts; however, 2x2x2x(\(m\)=32) excel at lower ReLU counts despite having \(\approx 4\times\) fewer FLOPs. This performance is attributed to the higher fraction (58.82%) of non-critical Stage1 ReLUs in the 2x2x2x(\(m\)=32) model, as ReLU optimization methods primarily target these ReLUs when aiming for low counts. Consequently, networks with more Stage1 ReLUs need to eliminate fewer critical ReLUs, resulting in less accuracy degradation. For a thorough validation and explanation of the above observations, refer to Appendices C.2 and C.3.

The above findings offer insight into the accuracy trends for SNL in Figure 4(b), higher the Stage1 ReLU proportion (58.8% for ResNet18, 47.7% for WRN22x4, and 43.9% for WRN16x8) higher

\begin{table}
\begin{tabular}{c
the accuracy at lower ReLU counts. Moreover, it elucidates the rationale for choosing WRN22x8 (48.2% Stage1 ReLU proportion) for higher ReLU counts while ResNet18 for lower ReLU counts, for ReLU-accuracy Pareto in SNL and SENet [21].

**Observation 4: ReLU-Thinning improves the efficacy of fine-grained ReLU optimization, predominantly for networks possessing higher ReLU counts.** We employ a _hybrid_ ReLU optimization approach and incorporate ReLU Thinning, a coarse-grained ReLU optimization step used in DeepReDuce, before SNL optimization. Interestingly, _even when baseline Thinned models are less accurate_, a significant boost (up to **3%** at iso-ReLUs) in accuracy is observed, more pronounced for networks with higher #ReLUs (ResNet34 and WRN22x8, in Table 4). Since ReLU-Thinning drops the ReLUs from the network's alternate layers, _irrespective of their criticality_, its integration into existing ReLU optimization methodologies would not impact their overall computational complexity and remains effective for reducing the search space required to identify critical ReLUs.

**Observation 5: Altering the network's ReLUs' distribution causes suboptimal performance in fine-grained ReLU optimization, and employing ReLU-Thinning reduces the performance gap.** We perform a contrastive analysis of fine-grained ReLU optimization (SNL) with DeepReDuce on the PI-amenable wider models 4x4x4x(\(m\)=16) and 3x7x2x(\(m\)=16), listed in Table 3. As shown in Figure 6(a) and 6(b) DeepReDuce outperforms SNL by a significant margin (upto 3%-4%); however, performing ReLU-Thinning before SNL optimization reduces this accuracy gap. This suggests that the benefit of fine-grained, over coarse-grained, ReLU optimization is _limited_ to a specific ReLUs' distribution, and it diminishes in the network with a lower proportion of the network's ReLU in Stage1. This constraint applies to ReLU's criticality-aware networks as well, as shown in Figure 18.

## 4 DeepReShape

**Intuition for ReLUs' criticality-aware network widening:** We first examine the impact of existing network widening approaches (BaseCh and StageCh) on the network's ReLU distribution. Interestingly, we observe that increasing the network's width by augmenting \(\alpha\), \(\beta\), and \(\gamma\) in StageCh networks results in a distinctive ReLU distribution, unlike BaseCh networks where all layers undergo the same scaling of #ReLUs. In particular, as illustrated in Figure 8, the proportion of Stage1 ReLUs decreases while that in other stages increases, and at higher (\(\alpha\), \(\beta\), \(\gamma\)), where accuracy starts saturating, proportion in Stage4 dominates. This implies that the proportion of non-critical ReLUs is decreasing while the distribution of ReLUs among the other stages does not strictly adhere to their criticality order (see criticality evaluation in Table 8). This leads us to propose a network widening approach to increase the width until the ReLU distribution follows the criticality order, where _most-critical stage dominates the distribution_. We find that widening beyond the point where the network's ReLUs align with their criticality order does not significantly alter their relative distribution (Figure 8(c)).

\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{Model} & C100 & Baseline & 2.02\% & 1.08\% & 1.08\% & 1.08\% & 1.08\% & 1.08\% & 1.08\% \\ \hline \hline ReLUs18 & Wallin & 20.48 & 27.03 & 15.36 & 26.02 & 73.53 & 73.53 & 73.53 & 72.26 \\ (37.666) & **37.18** & 27.95 & 76.02 & 25.54 & 27.02 & 25.22 & 27.64 & 77.74 \\ \hline \hline \end{tabular}
\end{table}
Table 4: A significant accuracy boost (on CIFAR-100) is achieved when ReLU-Thinning is employed prior to SNL, despite the least amount (**up to 4%**, CIFAR-100) when altering the less accurate ReLU-Thinnned models. \(\Delta=\) ReLU distribution in networks; however, using SNL Acc(w/ Th.)-Acc(Vanilla).

\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{Model} & \multirow{2}{*}{Acc(\%)} & \multirow{2}{*}{H.CO} & \multirow{2}{*}{Ref.} & \multicolumn{2}{c}{Shadows ReLU} & \multirow{2}{*}{Implementation} \\ \cline{3-4} \cline{6-7}  & & & & & **Superfit** & **Superfit** & **Superfit** \\ \hline \hline \multirow{2}{*}{2ReLUs2(32)} & 75.00 & 41.04 & 27.06 & 38.42\% & 13.97 & 13.91 & 38.98 \\  & 78.16 & 86.01 & 77.02 & 27.04 & 24.43 & 25.39 & 25.35 & 25.35 \\  & 78.02 & 66.04 & 66.04 & 38.05 & 31.05 & 31.05 & 31.05 & 18.54 \\ \hline \hline \end{tabular}
\end{table}
Table 3: A case study to investigate the capacity-criticality-tradeoff: Three Iso-ReLU ResNet18 models having distinct FLOPs count and ReLUs’ distribution, achieved by altering channels allocation per stage(Stage1) & (a) DeepReDuce at iso-ReLU (b) SNL at iso-ReLU (c) SNL at iso-ReLU (d) SNL at iso-ReLU (e)
**ReLU equalization and formation of HybReNet:** As illustrated in Figure 7, the ReLU-equalization step redistributes the network's ReLU in their criticality order, i.e., the (most)least critical stage having a (highest)lowest fraction of the network's ReLU. This is performed using an iterative process, as outlined in Algorithm 1, where in each iteration the relative distribution of ReLUs in two stages is rearranged in their criticality order, by altering network design hyperparameters. We select the sets of minimum values of (\(\alpha\), \(\beta\), \(\gamma\)) required for ReLU equalization and obtain four distinct HRN networks: HRN-5x5x3x, HRN-5x7x2x, HRN-6x6x2x, and HRN-7x5x2x (see Appendix A). Figure 7 shows the channel allocation, after ReLU-equalization, in the successive stages of HRN-5x5x3x, allocating fewer channels to initial stages more to deeper ones, compared to the input network.

**Network design for efficient PI at lower ReLU counts:** To enhance PI efficiency with lower ReLU counts, Stage1 needs to dominate the distribution of ReLUs (see observation 3); however, ReLU equalization in HRNs led to the lowest proportion of network ReLUs in Stage1. To address this, the \(\alpha\) value in HRNs is reduced to 2 as the decreasing \(\alpha\) value results in an increased proportion of Stage1 ReLUs. Consequently, HRN-2x5x3x, HRN-2x5x2x, HRN-2x6x2x, and HRN-2x7x2x have Stage1 dominating the network's ReLUs' distribution (see Table 9), and distribution of ReLUs in all but Stage1 follow their criticality order. Figure 7 shows the channel reallocation in HRN-2x5x3x after considering Capacity-Criticality-Tradeoff, allocating fewer channels even in deeper stages which results in significant FLOPs, up to \(\sim\)**45\(\times\)**, reduction.

**ReLU-reuse (Re2):**

We propose _ReLU-reuse_, to drop the ReLUs selectively from all but a (contiguous)fraction of feature maps in a layer. Inspired by [32, 33], feature maps of the layer are divided into \(N\) groups and ReLUs are employed only to the last group (Figure 9). Empirically, increasing the value of \(N\) results in a significant accuracy loss, despite \(1\times 1\) convolution being employed for cross-channel interaction. This is likely due to the loss of cross-channel information arises from a greater number of divisions in the feature

Figure 8: Impact of network’s width expansion on ReLU’s distribution: for ResNet18-based BaseCh (a), StageCh (b), and proposed HRN network (c). Once HRN network’s ReLU align in their criticality order (at 5,5,3), the relative distribution of ReLUs remains stable with increasing \(\alpha\) values.

Figure 7: The DeepReshape network redesigning pipeline. ReLU’s criticality-aware strategic allocation of channels (gray boxes) outputs FLOPs-balanced ReLU-efficient baseline networks for various ReLU counts (blue boxes). Numbers in green denote criticality order (Stage3 is most critical).
maps (see our ablation study in Table 14, Appendix G). To address this issue, we devise a mechanism that

decouples the number of divisions in feature maps from the ReLU reduction factor \(N\). Precisely, one-fourth of channels are utilized for feature reuse, while a \(Nth\) fraction of feature maps are activated using ReLUs, and the remaining feature maps are processed solely with convolution operations, resulting in only three groups. It is important to note that using the ReLUs in the last group of feature maps increases the effective receptive field as those neurons can take into account a greater portion of the input feature maps, using the skip connections.

## 5 Experimental Results

**Analysis of HybReNets Pareto points:** Figure 1 shows that HybReNet advances the ReLU-accuracy Pareto with a substantial reduction in FLOPs counts - a factor overlooked in prior PI-specific network optimization. Now, we present a detailed analysis of network configurations and ReLU optimization steps and quantify their benefits for ReLUs and FLOPs reduction. We use ResNet18-based HRN-5x5x3x for ReLU-accuracy comparison with SOTA PI methods in Figure 1, as its FLOPs efficiency is superior to other HRNs (see Table 16).

The key takeaway from Table 5 is that tailoring the network features for PI constraint significantly reduces FLOPs along with ReLUs. Specifically, lowering \(\alpha\) value and base channel count led to **23.6\(\times\)** fewer FLOPs in HRN-2x5x3x(\(m\)=8), compared to HRN-5x5x3x(\(m\)=16). Moreover, the criticality-aware ReLUs' distribution in HRNs simplifies the complexity of ReLU optimization steps to \(\mathcal{O}(1)\), as opposed to the iterative steps in DeepReDuce that lead to \(\mathcal{O}(D)\) complexity for a \(D\) stage network. In particular, we apply ReLU Culling only to Stage1 if it dominates the network ReLU distribution, such as HRNs with \(\alpha\)=2, and employ ReLU-Thinning for the remaining stages. Further reduction in ReLU count is achieved by implementing ReLU-reuse with a suitable reduction factor, as shown in Table 5. Finally, an accuracy boost is achieved by employing DKD [35], as the ReLU-reduced models greatly benefit from decoupling the target and non-target class distillation.

Note that we exclusively employ coarse-grained ReLU optimization steps for HRNs, based on the observation that fine-grained ReLU optimization techniques underperform when the distribution of ReLU is altered in classical networks (see Figure 6). Therefore, fine-grained ReLU optimization fails to take advantage of increased network complexity per ReLU unit in HRNs and remains subpar compared to classical networks. For an in-depth discussion, see Appendix C.4.

**HybReNets outperform state-of-the-art in private inference:** Table 6 presents competing design points for SENet [21] and SNL [20], and we select HybReNet points offering both accuracy and latency benefits for a fair comparison. The runtime breakdown is presented as homomorphic (HE) latency [1; 2; 3], arises from linear operations (convolution and fully-connected layers), and Garbled-circuit (GC) latency [36; 36; 24], resulting from non-linear (ReLU) operations [9; 10; 13].

On CIFAR-100, SENet requires 300K ReLUs and 2461M FLOPs to reach 80.54% accuracy; whereas, HRN-5x5x3x achieves 80.86% accuracy with only 163K ReLUs and 1055M FLOPs, providing 1.8\(\times\) ReLU and 2.3\(\times\) FLOPs saving. Similarly, at 25K ReLUs, our approach achieves a 2.1% accuracy gain with 12.5\(\times\) FLOPs reduction, thereby saving 5.2\(\times\) runtime. Even at an extremely low ReLU count of 13K, HRN is 1.7% more accurate and achieves 2.2\(\times\) runtime saving, compared to the SNL.

On TinyImageNet, HybReNets outperform SENet at both 300K and 142K ReLUs, improve runtime by 1.7\(\times\) and 8.7\(\times\), respectively. Compared to SNL at 489K ReLUs, HybReNets are 3.2% (1.7%) more accurate with a 1.8\(\times\) (2.8\(\times\)) reduction in runtime. At lower ReLU counts of 100K and 59K,

\begin{table}
\begin{tabular}{c c|c c|c c c c c} \hline \multirow{2}{*}{HybReNet} & \multirow{2}{*}{\(m\)} & \multicolumn{2}{c|}{ReLU optimization steps} & \multirow{2}{*}{\#ReLU} & \multirow{2}{*}{\#FLOPs} & \multicolumn{2}{c}{Accuracy(\%)} & \multirow{2}{*}{Acc./ReLU} \\ \cline{3-3} \cline{5-10}  & & & Culled & & Thinned & Re2 & & KD[34] & DKD[35] \\ \hline
5x5x3x & 16 & NA & S1+S2+S3+S4 & NA & 163.3K & 1055.4M & 79.34 & 80.86 & 0.50 \\
2x5x3x & 32 & S1 & S2+S3+S4 & NA & 104.4K & 714.1M & 77.63 & 79.96 & 0.77 \\
2x5x3x & 16 & S1 & S2+S3+S4 & NA & 52.2K & 178.5M & 74.98 & 77.14 & 1.48 \\
2x5x3x & 8 & S1 & S2+S3+S4 & NA & 26.1K & 44.6M & 70.36 & 72.65 & 2.78 \\
2x5x3x & 16 & S1 & S2+S3+S4 & 4 & 13.1K & 121.6M & 67.30 & 68.25 & 5.23 \\
2x5x3x & 16 & S1 & S2+S3+S4 & 8 & 6.5K & 130.5M & 62.68 & 63.29 & 9.70 \\
2x5x3x & 16 & S1 & S2+S3+S4 & 16 & 3.2K & 137.2M & 56.24 & 56.33 & 17.26 \\ \hline \end{tabular}
\end{table}
Table 5: Network configurations and ReLU optimization steps used for the Pareto points in Figure 1, on CIFAR-100. Re2 denotes ReLU-reuse, used for achieving very low ReLU-counts.
HybReNets match the accuracy with SNL and achieve a 12.4\(\times\) and 3.1\(\times\) FLOPs reduction, which results in 8.7\(\times\) and 2.8\(\times\) runtime improvement, respectively.

Our primary insight from Table 6 is that FLOPs reduction does not inherently guarantee a proportional reduction in HE latency, whereas a direct correlation exists between ReLU reduction and GC latency savings. In particular, a \(\sim\)12.5\(\times\) FLOPs reduction translates to 5.2\(\times\) and 8.7\(\times\) latency reduction on CIFAR-100 and TinyImageNet, respectively. This is due to the fact HE latency has an intricate dependency on the input/output packing [8; 37], rotational complexity [38; 39; 40] and slot utilization [41]. We refer the readers to [8; 10] for details.

**Generality case study on ResNet34:** We select ResNet34 for DeepReShape generality study for two key reasons: (1) its consistent use for the case study in prior PI-specific network optimization studies [17; 20; 21], and (2) its stage compute ratio (\(\phi_{1}\)=3, \(\phi_{2}\)=4, \(\phi_{3}\)=6, and \(\phi_{4}\)=3) distinguishes it from ResNet18, results in different sets of HRN networks, HRN-4x6x3x and HRN-4x9x2x, upon applying Algorithm 1. We use HRN-4x6x3x for comparison with SOTA in Table 7.

HybReNet advances the ReLU-accuracy Pareto on both CIFAR-100 and TinyImageNet, shown in Figures 10 (a, b). Table 7 quantifies the FLOPs-ReLU-Accuracy benefits along with runtime savings. On CIFAR-100, compared to SOTA, HybReNet improves runtime by 3.1\(\times\) with a significant gain in accuracy -- 9.8%, 7.2%, 5.9%, and 2.1% at 15K, 25K, 30K and 50K ReLUs (respectively). Further on TinyImageNet, SNL requires 300K ReLUs and 4646M FLOPs to reach 64% accuracy; whereas, HybReNet matches this accuracy with 8.8\(\times\) fewer FLOPs, leading to a runtime improvement of 6.3\(\times\). Conclusively, it highlights the effectiveness of DeepReShape and validates its generality.

**HybReNets outperform SOTA vision models ConvNeXt and RegNet:** We select SOTA vision models ConvNeXt-V2 [42] and RegNet [31] for our comparative analysis with HybReNets as these models possess distinctive depth/width hyperparameters, compared to the ResNet (Appendix E.4).

First, we compare the baseline RegNet-X models with (ResNet18-based) HybReNets on CIFAR-100, without applying any ReLU-optimization steps. Results are shown in Figure 10(c) where HRNs are evaluated with \(m\in\) {16, 32, 64 }. All HRNs achieve a substantial reduction in ReLU count, at iso-accuracies. For instance, to achieve accuracies of 78.26% and 80.63%, RegNet-X models

\begin{table}
\begin{tabular}{c c c c c c c c c|c c c c c c c c c} \hline \hline \multicolumn{1}{c}{} & \multicolumn{3}{c|}{SOTA in Private Inference} & \multicolumn{3}{c|}{HybReNet(Ours)} & \multicolumn{3}{c}{Improvements} & \multicolumn{3}{c}{Improvements} \\ \cline{3-14} \multicolumn{1}{c}{} & \#Re & \#FL & Acc. & HE & GC & Lat. & \#Re & \#FL & Acc. & HE & GC & Lat. & \#Re & \#FL & Acc. & HE & GC & Lat. \\ \hline \multirow{8}{*}{**FullyRecher**} & 300 & 2461 & 80.54 & 1004 & 33.7 & 1037 & 163 & 1055 & 80.86 & 770 & 18.4 & 788 & 1.8\(\times\) & 2.3\(\times\) & 0.3 & 1.3\(\times\) & 1.8\(\times\) & 1.3\(\times\) \\  & 240 & 261 & 79.81 & 1004 & 27.0 & 1031 & 163 & 1055 & 80.86 & 770 & 18.4 & 788 & 1.5\(\times\) & 2.3\(\times\) & 1.1 & 1.3\(\times\) & 1.5\(\times\) & 1.3\(\times\) \\  & 180 & 2461 & 79.12 & 1004 & 20.2 & 1024 & 103 & 1055 & 80.86 & 770 & 18.4 & 788 & 1.1\(\times\) & 2.3\(\times\) & 1.7 & 1.3\(\times\) & 1.3\(\times\) & 1.3\(\times\) \\  & 500 & 559 & 75.28 & 268 & 5.6 & 274 & 52.9 & 77.14 & 123 & 5.9 & 129 & 1.0\(\times\) & 3.1\(\times\) & 1.9 & 2.2\(\times\) & 0.9\(\times\) & 2.1\(\times\) \\  & 25 & 559 & 75.09 & 268 & 28.8 & 271 & 26.5 & 472.6 & 49 & 2.9 & 52 & 0.9\(\times\) & 12.5\(\times\) & 2.1\(\times\) & 5.5\(\times\) & 1.0\(\times\) & **5.2\(\times\)** \\  & 25 & 15 & 559 & 67.17 & 26.8 & 17.7 & 270 & 13 & 179 & 68.52 & 123 & 1.5 & 124 & 1.1\(\times\) & 3.1\(\times\) & 1.1 & 2.2\(\times\) & 1.0\(\times\) & 2.2\(\times\) \\  & 13 & 559 & 65.35 & 268 & 15.5 & 270 & 13 & 179 & 68.52 & 123 & 1.5 & 124 & 1.0\(\times\) & 3.1\(\times\) & 1.7 & 2.2\(\times\) & 1.0\(\times\) & 2.2\(\times\) \\ \hline \multirow{8}{*}{**FullyRecher**} & 300 & 2227 & 64.96 & 927 & 33.7 & 961 & 327 & 1065 & 64.92 & 526 & 36.7 & 563 & 0.9\(\times\) & 2.1\(\times\) & 0.0\(\times\) & 1.8\(\times\) & 0.9\(\times\) & 1.7\(\times\) \\  & 142 & 2227 & 58.90 & 927 & 16.0 & 943 & 104 & 104 & 179 & 58.90 & 97 & 11.7 & 10.8 & 1.4\(\times\) & 1.2\(\times\) & 0.0\(\times\) & 9.6\(\times\) & 1.4\(\times\) & **8.7\(\times\)** \\ \cline{1-1}  & 489 & 980.46 & 64.24 & 3600 & 53.0 & 3745 & 4316 & 67.83 & 2059 & 73.44 & 202 & 0.7\(\times\) & 2.3\(\times\) & 2.3\(\times\) & 1.8\(\times\) & 0.7\(\times\) & 1.8\(\times\) \\ \cline{1-1}  & 489 & 980.36 & 64.24 & 3600 & 55.0 & 3745 & 418 & 2842 & 66.30 & 1307 & 45.0 & 1352 & 1.2\(\times\) & 3.5\(\times\) & 1.7 & 2.8\(\times\) & 1.2\(\times\) & 2.8\(\times\) \\ \cline{1-1}  & 499 & 980.36 & 64.24 & 3600 & 55.0 & 3745 & 418 & 2842 & 66.30 & 1307 & 45.0 & 1352 & 1.2\(\times\) & 3.5\(\times\) & 1.7 & 2.8\(\times\) & 1.2\(\times\) & 2.8\(\times\) \\ \cline{1-1}  & 298 & 2227 & 64.04 & 927 & 33.5 & 961 & 327 & 1055 & 64.92 & 526 & 36.7 & 563 & 0.9\(\times\) & 2.1\(\times\) & 0.9\(\times\) & 1.8\(\times\) & 0.9\(\times\) & 1.7\(\times\) \\ \cline{1-1}  & 100 & 2277 & 58.94 & 927 & 11.2 & 930 & 140 & 179 & 58.90 & 97 & 117 & 10.8 & 1.0\(\times\) & 1.2\(\times\) & 0.0\(\times\) & 9.6\(\times\) & 1.0\(\times\) & **8.7\(\times\)** \\ \cline{1-1}  & 59 & 2227 & 54.40 & 927 & 6.6 & 934 & 52 & 712 & 54.46 & 329 & 5.9 & 33 & 1.1\(\times\) & 3.1\(\times\) & 0.1 & 2.8\(\times\) & 1.1\(\times\) & 2.8\(\times\) \\ \hline \hline \end{tabular}
\end{table}
Table 6: Comparison of HybReNet with state-of-the-art in private inference: SENet [21] and SNL [20]. HybReNet exhibits superior ReLU and FLOPs efficiency and achieve a substantial reduction in latency. #Re and #FL denote ReLU and FLOPs counts; Acc. is top-1 accuracy; Lat. is the runtime for one private inference, including Homomorphic (HE) and Garbled
require 1460K and 6544K ReLUs respectively, while the HRN-5x5x3x only requires 343K and 1372K ReLUs, leading to a 4.3\(\times\) and 4.7\(\times\) ReLU reduction respectively.

Now, we compare the ConvNeXt-V2 models with HybReNets on TinyImageNet, after employing ReLU optimization steps. The ReLU-accuracy Pareto is shown in Figure 10(b), with a detailed comparison outlined in Table 7. The competing HRNs achieve 1.3\(\times\) to 1.7\(\times\) ReLU savings; 1.4\(\times\) to 2.5\(\times\) FLOPs reduction; which results in 1.3\(\times\) to 2.3\(\times\) runtime improvements.

**Sensitivity study and analysis of networks produced by DeepReShape:** We analyze the impact of each stagewise channel multiplication factor (\(\alpha\), \(\beta\), \(\gamma\)) on the network's ReLU and FLOPs efficiency using a sensitivity analysis. With ResNet18 configured with \(m\)=16, we systematically vary one factor at a time, starting from 2, while other factors are held constant at 2.

We observe that augmenting \(\alpha\) and \(\beta\) values improves ReLU efficiency; notably, the latter optimizes the performance marginally better than the former until a saturation point is reached. On the other hand, FLOPs efficiency is most effectively improved by augmenting \(\alpha\), outperforming \(\beta\) enhancements while augmenting \(\gamma\) values yields the worst FLOPs-efficiency. This suggests that FLOPs growth in the deeper layers of StageCh networks is inconsequential. Conclusively, higher \(\alpha\) and \(\beta\) values with a _restrictive_\(\gamma\) value are desirable for FLOPs-ReLU-Accuracy balance.

We find that ReLU equalization in HRNs confines the \(\gamma\) values (see Appendix A). Precisely, all the four HRNs produced by DeepReShape method; HRN-5x5x3x, HRN-5x7x2x, HRN-6x6x2x, and HRN-7x5x2x; posses higher \(\alpha\) and \(\beta\) values while \(\gamma\) values are restricted as \(\gamma<\)4. Thus, higher \(\alpha\) and \(\beta\) values in HRNs boost ReLU efficiency, and a lower \(\gamma\) value restricts the FLOPs' growth in deeper layers, promoting FLOP efficiency.

## 6 Related Work

**PI-specific network optimization:** Delphi [9] and SAFENet [15] substitute the ReLUs with low-degree polynomials, while DeepReDuce [17] is a coarse-grained ReLU optimization and drops ReLUs layerwise. SNL [20] and SENet [21] are fine-grained ReLU optimization, and drops the pixelwise ReLUs. CryptoNAS [14] and Sphynx [19] use neural architecture search and employ constant number of ReLUs per layer for designing ReLU-efficient networks, disregarding FLOPs implications. In contrast, our approach achieves ReLU and FLOPs efficiency simultaneously. We refer the reader to [43] for detailed HE and GC-specific optimizations for private inference, and Appendix I for additional related work.

\begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c c c} \hline \hline \multicolumn{13}{c}{SOTA in Private Inference (on ResNet343)} & \multicolumn{1}{c}{HybReNet(Ours)} & \multicolumn{1}{c}{HybReNet(Ours)} & \multicolumn{1}{c}{HybReNet(Ours)} & \multicolumn{1}{c}{HybReNet(Ours)} & \multicolumn{1}{c}{HybReNet(Ours)} & \multicolumn{1}{c}{HybReNet} \\ \cline{3-13} \cline{13-13} \multicolumn{13}{c}{} & \#Re & **\#FL** & Acc. & HE & **\#FeL** & Acc. & HE & GC & **Lat.** & **\#Re** & **\#FL** & Acc. & HE & GC & **Lat.** \\ \hline \multirow{9}{*}{\begin{tabular}{} \end{tabular} } & 200 & 1162 & 78.80 & 459 & 22.5 & 482 & 134 & 527 & 674 & 15.1 & 419 & 15.2 \(\times\) & 2.2 \(\times\) & 0.8 & 1.1 \(\times\) & 1.5 \(\times\) & 1.1\(\times\) \\  & 80 & 1162 & 76.65 & 459 & 0.9 & 468 & 67 & 132 & 76.91 & 140 & 7.5 & 148 & 1.2 \(\times\) & 8.8 \(\times\) & 0.3 \(\times\) & 1.2 \(\times\) & 3.2 \(\times\) \\  & 50 & 1162 & 74.84 & 4.5 & 5.6 & 65 & 132 & 76.91 & 140 & 7.5 & 148 & 0.7 \(\times\) & 8.8 \(\times\) & 2.8 \(\times\) & 2.3 \(\times\) & 3.3 \(\times\) & 0.7 \(\times\) & 3.1 \(\times\) \\ \cline{1-1}  & 30 & 1162 & 71.00 & 459 & 3.4 & 462 & 67 & 132 & 76.91 & 140 & 7.5 & 148 & 0.7 \(\times\) & 8.5 \(\times\) & **5.9** & 3.3 \(\times\) & 0.4 \(\times\) & **3.1** \\  & 25 & 1162 & 69.68 & 459 & 2.8 & 462 & 67 & 132 & 76.91 & 140 & 7.5 & 148 & 0.4 \(\times\) & 8.8 \(\times\) & **5.9** & 3.3 \(\times\) & 0.4 \(\times\) & 3.1 \(\times\) \\  & 25 & 1162 & 67.08 & 459 & 1.7 & 461 & 67 & 132 & 76.91 & 140 & 7.5 & 148 & 0.4 \(\times\) & 8.8 \(\times\) & **5.9** & **3.3 \(\times\) & 0.2 \(\times\) & **3.1** \\ \hline \multirow{9}{*}{
\begin{tabular}{} \end{tabular} } & 500 & 4646 & 65.34 & 1710 & 56.2 & 1766 & 537 & 2109 & 67.48 & 880 & 60.3 & 940 & 0.9 \(\times\) & 2.2 & 2.1 \(\times\) & 1.9 \(\times\) & 0.9 \(\times\) & 2.3 \(\times\) \\  & 400 & 4646 & 63.32 & 1710 & 45.0 & 1755 & 337 & 2109 & 67.88 & 880 & 60.3 & 940 & 0.7 \(\times\) & 2.2 & 2.2 \(\times\) & 0.7 \(\times\) & 2.2 \(\times\) & 2.1 \(\times\) & 0.7 \(\times\) & 2.3 \(\times\) \\  & 300 & 4646 & 63.99 & 1710 & 3.7 & 1744 & 268 & 529 & 64.02 & 245 & 30.2 & 275 & 1.1 \(\times\) & 8.8 \(\times\) & 0.0 & 7.0 \(\times\) & **1.1** & **6.3** \\  & 200 & 4646 & 62.49 & 1710 & 22.5 & 1733 & 268 & 529 & 64.02 & 245 & 30.2 & 275 & 0.7 \(\times\) & 8.8 \(\times\) & 1.5 \(\times\) & 0.0 & 7.0 \(\times\) & **6.3** \\ \cline{1-1}  & 1622 & 17801 & 69.85 & 4067 & 18.24 & 2429 & 1270 & 2824 & 70.30 & 3091 & 1428 & 2233 & 1.3 \(\times\) & 1.4 \(\times\) & 0.4 & 1.3 \(\times\) & 1.3 \(\times\) & 1.3 \(\times\) \\  & 2178 & 9080 & 68.75 & 2368 & 143.7 & 2512 & 952 & 4638 & 69.15 & 1837 & 107.1 & 1944 & 1.3 \(\times\) & 2.0 & 4.0 & 1.3 \(\times\) & 1.3 \(\times\) & 1.3 \(\times\) \\  & 221 & 13436 & 67.08 & 1307 & 81.0 & 1388 & 537 & 2109 & 67.84 & 880 & 60.3 & 940 & 1.3 \(\times\) & 1.6 \(\times\) & 0.4 & 1.5 \(\times\) & 1.3 \(\times\) & 1.5 \(\times\) \\  & 541 & 1935 & 65.72 & 738 & 60.8 & 799 & 402 & 1187 & 65.77 & 592 & 45.2 & 637 & 1.3 \(\times\) & 1.6 \(\times\) & 0.0 & 1.3 \(\times\) & 1.3 \(\times\) & 1.3 \(\times\) \\  & 451 & 1345 & 640.70 & 546 & 50.7 & 597 & 268 & 529 & 64.02 & 245 & 30.2 & 275 & 1.7 \(\times\) & 2.5 \(\times\) & 0.0 & 2.2 \(\times\) & 1.7 \(\times\) & 2.2 \(\times\) \\ \hline \hline \end{tabular}
\end{table}
Table 7: ResNet34-based HybReNets outperform SOTA PI
Conclusion

In this work, we develop the DeepReShape method to achieve ReLU and FLOPs efficiency simultaneously and designed a novel family of networks named HybReNet. We further study the essential network attributes enabling PI efficiency over a wide range of ReLU counts. Our findings demonstrate that distinct network attributes are required for efficient PI at higher and lower ReLU counts.

## 8 Checklist

**Broader impact:** The privacy-preserving computations often necessitates significant resources, such as memory and compute time. For instance, the use of the garbled-circuit technique alone requires hundreds of gigabytes of memory, and homomorphic computations can take hours for a single private inference. This demand for resources highlights the necessity for efficient optimization strategies. Previously, a line of research on specialized hardware architectures and protocol optimizations have been put forward to address these overheads. However, these approaches come with their own limitations: the former presents sustainability issues [44], and the latter can introduce new security vulnerabilities and lack backward compatibility.

Contrastingly, algorithmic enhancements can be effectively deployed across a variety of hardware platforms and security protocols. In our research, we demonstrate that a substantial reduction in runtime, \(\sim\)(5\(\times\) to 10\(\times\)), can be achieved simply by strategically allocating channels in existing classical networks and employing straightforward ReLU optimization steps. Importantly, this decrease does not depend on specific network architectures or specialized hardware, thus broadening the potential impact of our algorithmic optimization work.

**Limitations:** Achieving a specific ReLU count with HRNs is challenging due to the use of coarse-grained ReLU optimization steps, which are influenced by the base channel counts and stage-wise channel multiplication factors. The difference between fine-grained and coarse-grained ReLU optimization lies in their performance and configurability to a target ReLU count. Fine-grained ReLU optimization allows for an independent target ReLU count input, while coarse-grained ReLU optimization adjusts based on the network's ReLU count. However, when applied to HRNs, fine-grained ReLU optimization has been found to underperform compared to the coarse-grained approach.

**Reproducibility statements:** We have provided all the implementation-specific details in Appendix H. Further, the details of the network architecture can be found in Appendix J. Also, the details of the ReLU optimization steps are presented in Table 5, Table 11, and Table 12.

## Acknowledgment

We would like to thank Karthik Garimella for his assistance in computing the runtime (HE and GC latency) for private inference. This research was developed with funding from the Defense Advanced Research Projects Agency (DARPA), under the Data Protection in Virtual Environments (DPRIVE) program, contract HR0011-21-9-0003. The views, opinions and/or findings expressed are those of the author and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.
