Fully homomorphic encryption (FHE) lets a server run a neural network on data it cannot read. The client encrypts an image, the server computes on the ciphertext, and only the client can decrypt the answer. The obstacle is cost: encrypted inference is orders of magnitude slower than plaintext. Most work on "encryption-friendly" networks fights this by counting things, such as how many ReLUs remain or how many sequential multiplications the network performs. That count matters because each multiplication consumes part of a fixed noise budget.
Accelerator research tells a different story. Specialized chips and repurposed AI chips have made raw arithmetic cheap, so time now goes to moving ciphertexts and keys and to periodically "refreshing" ciphertexts. We propose to design polynomial networks against the measured operation costs of the hardware they will actually run on. Concretely, we would build a per-platform cost model of encrypted inference, use it as the objective in architecture search over activation-free polynomial backbones, and test two claims. The first is that count-based proxies mis-rank architectures. The second is that the best encrypted architecture differs across CPUs, TPUs and the cost regimes that bootstrapping-capable accelerators imply.
Core Claim
Two results in the file pull in opposite directions. PolyNeXt (Activation-Free Backbones for Image Recognition) builds vision backbones with no pointwise activations. It multiplies two parallel linear branches element-wise, so stacking $L$ such layers yields polynomials of degree $2^L$. Its finding is that depth-over-width is what makes these networks accurate: 83.9% ImageNet top-1 for the standard model and 82.7% for a fully polynomial variant. HEMET (HEMET) shows the opposite pressure under leveled encryption, a "depth trap." Extra multiplicative depth forces larger encryption parameters and slows every operation, so deep mobile networks run slower than shallow ones. ULD-Net (ULD-Net) sides with HEMET by capping per-block degree, and it reaches 69.79% on ImageNet with ResNet-18.
Our claim is that this conflict is not a fixed fact about polynomial networks. It is a statement about one cost regime: leveled CKKS on a CPU, with no bootstrapping. CKKS is the approximate-arithmetic encryption scheme most vision work uses. Bootstrapping is the expensive procedure that refreshes a noisy ciphertext so that computation can continue.
Under bootstrapping, depth is paid for in chunks, one refresh per exhausted budget, rather than through ever-larger parameters. On hardware where refreshing is relatively cheap, the dominant cost can become the ciphertext rotations needed for linear layers rather than depth. A rotation cyclically shifts the thousands of values packed inside one ciphertext, and each rotation requires reading large key material from memory. F1 (F1) and CROSS (Leveraging ASIC AI Chips for Homomorphic Encryption) both identify data movement and rotations as the dominant cost once arithmetic is accelerated. CROSS also reports that rotations map poorly onto TPUs.
The prediction is falsifiable. If it holds, an architecture chosen under a measured, platform-specific cost model will beat one chosen under depth counts or FLOPs on that platform. The winning architectures should also differ systematically across platforms in depth, width and branch structure.
Research Program
The first component is a cost model. For a given architecture, packing layout and bootstrap placement, we compile the network into a trace of CKKS operations: ciphertext-ciphertext multiplication, ciphertext-plaintext multiplication, rotation, rescaling and bootstrapping. Each operation is tagged with the level at which it runs, meaning how much noise budget remains. Predicted latency on hardware $h$ is
$$C(a,h)=\sum_{o}\sum_{\ell} n_{o,\ell}(a)\, t_{o,\ell}(h),$$
where $n_{o,\ell}(a)$ is the number of operations of type $o$ that architecture $a$ executes at level $\ell$. The term $t_{o,\ell}(h)$ is the measured latency of one such operation on hardware $h$, with key-load time included.
We calibrate $t$ by microbenchmarking on a many-core CPU with OpenFHE and on a TPU using CROSS-style kernels, where the CROSS code can be obtained. For the dedicated-accelerator regime, we cannot run F1, CraterLake, BTS or CryptoLight, since all are simulated or closed per the SoK. We therefore treat that regime as a sweep over the cost ratios between bootstrapping, rotation and multiplication. The sweep covers the direction CryptoLight's simulated results point to: large reductions in multiplication and bootstrapping latency relative to electronic ASICs (CryptoLight). We make no claim about that chip's absolute numbers. We validate the model by checking that predicted and measured end-to-end latencies agree on fully encrypted runs.
The second component is the search space. It is built from PolyNeXt-style blocks: two-branch Hadamard-product MLPs, coarse-plus-fine Hadamard-product convolutions, and polynomial-kernel attention. ULD-Net's PolyNorm, a per-sample normalization with a bounded quadratic, keeps intermediate values inside the range where the approximations hold. HEMET's coefficient merging folds normalization and alignment masks into polynomial coefficients. The searchable choices are per-stage depth and width, kernel size, the attention polynomial degree, the channel-to-slot packing, and where bootstraps are inserted.
Search uses evolutionary sampling with short proxy training on CIFAR-100 and Tiny-ImageNet, scored on accuracy against $C(a,h)$. The best architecture per platform is retrained fully and run encrypted. Packing and bootstrap placement are searched jointly with architecture because they decide how many rotations a linear layer costs. Treating packing as a later compiler pass is exactly how count-based design hides the dominant term.
Baselines
The naive reference point is a ResNet-18 with its activations replaced by low-degree polynomials after standard training, compiled with an off-the-shelf CKKS pipeline. It shows how much any design effort buys.
The strongest existing method on this question is ULD-Net. It reports 69.79% ImageNet top-1 for ResNet-18 with a 2.76× encrypted-latency speedup over the prior fully polynomial model, and 78.81% on CIFAR-100 with a 3.17× speedup (ULD-Net). The file reports no absolute ULD-Net latency on any specific hardware ("no reported result found on Lacuna for ULD-Net absolute encrypted latency"), so we will measure it ourselves on each platform.
The second strong competitor is PolyNeXt's fully polynomial variant at 82.7% ImageNet top-1. It has never been run encrypted, so it is precisely the high-accuracy, depth-heavy design whose encrypted cost is unknown. We will compile it with the same pipeline, packing search and bootstrap placement our models get. That way it is not handicapped by a worse compiler.
The third is HEMET's greedy block search driven by multiplicative depth. It reports SqueezeNet CIFAR inference reduced from 72.7 s to 29.6 s against the EVA compiler. We re-implement it inside our search space so that only the cost signal differs.
All methods get identical training recipes and an equal number of fully trained candidates. They share the same CKKS parameter-selection procedure, bootstrap placement solver and packing search, at a matched security level. "Beating" a baseline means lower measured encrypted latency at equal or higher accuracy on that platform, outside run-to-run variance. Equivalently, higher accuracy at matched measured latency.
The key ablation holds the search space and budget fixed and swaps only the cost signal. The four signals are FLOPs, multiplicative depth, unweighted operation counts, and the calibrated $C(a,h)$. A further ablation transfers the CPU-optimal architecture to the TPU, and vice versa, to isolate the effect of platform-specific pricing.
Why not just…?
Why not just take ULD-Net or PolyNeXt as published and compile them? This is the real threat. If an existing model already sits on the measured Pareto front for every platform, our search adds nothing. Both papers optimize degree, variance and accuracy rather than rotations and key traffic. PolyNeXt explicitly leaves encrypted deployment open and warns that its deep, sequential structure hurts throughput. That gives some reason to expect slack, but not proof. The baselines above settle it directly, and we would report a null result if the published models are not beaten.
Why not just use HEMET's depth-based search, which already showed depth is what matters? HEMET's evidence comes from leveled encryption without bootstrapping on CIFAR. That is the regime where depth inflates parameters globally. Once bootstrapping is available, and especially where bootstrapping is relatively cheap, depth costs are paid in discrete steps and rotations can dominate. The cost-signal ablation tests this. If depth-only search matches calibrated search across the swept cost ratios, the hardware-pricing idea is wrong and HEMET's proxy suffices.
Why not just minimize FLOPs or nonlinearity count, as plaintext-efficiency and ReLU-reduction work does? HEMET already shows FLOP-minimizing mobile networks can be slower under encryption. DeepReDuce (DeepReDuce) and Circa (Circa) target garbled-circuit protocols, where ReLUs are the expensive part. A fully polynomial CKKS network has no ReLUs to count. We will report the rank correlation between each proxy and measured latency to show how far each one is off.
Why not just speed up the kernels, as the AlphaEvolve work did? Adapting AlphaEvolve shows LLM-driven search can speed individual TPU kernels, for example 1.31× on CKKS rotation. That changes $t_{o,\ell}(h)$ but not $n_{o,\ell}(a)$, so it is complementary rather than competing. If such kernels are available, we will recalibrate with them and check whether the architectural optimum moves.
Proposed Experiments
The first experiment validates the cost model. On roughly forty diverse polynomial architectures run fully encrypted on CPU and TPU, the calibrated model should rank measured latency much better than depth, FLOPs or unweighted counts. We measure ranking quality with Kendall's tau, a standard rank-correlation statistic, and report absolute prediction error. If no calibrated model beats depth counts here, the project stops.
The second experiment is the transfer test. The architecture found for each platform, and for each point of the accelerator cost-ratio sweep, is run on every other platform. The hypothesis predicts a clear diagonal: each architecture wins on the platform it was priced for. Structurally, we expect deeper, narrower networks with fewer rotation-heavy layers when bootstrapping is relatively cheap, and HEMET-like shallow networks in the leveled CPU regime.
The third experiment scales up. Final models are evaluated on CIFAR-100, Tiny-ImageNet and ImageNet-1K for accuracy, and on single-image measured encrypted latency for CPU and TPU, against ULD-Net, PolyNeXt-fully-polynomial and HEMET-search. The decisive outcome on ImageNet is a model above ULD-Net's 69.79% that is no slower on the measured platform, or one that matches it at clearly lower latency.
We will also report the achieved precision after decryption, to confirm that PolyNorm's variance control holds under real CKKS noise rather than only in plaintext simulation. As a secondary check, we will report whether PolyNeXt's depth-over-width accuracy advantage survives once each architecture's real encrypted cost is charged.
References
- Activation-Free Backbones for Image Recognition: Polynomial Alternatives within MetaFormer-Style Vision Models
- HEMET: A Homomorphic-Encryption-Friendly Privacy-Preserving Mobile Neural Network Architecture
- ULD-Net: Enabling Ultra-Low-Degree Fully Polynomial Networks for Homomorphically Encrypted Inference
- F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption (Extended Version)
- Leveraging ASIC AI Chips for Homomorphic Encryption
- SoK: Fully Homomorphic Encryption Accelerators
- CryptoLight: An Electro-Optical Accelerator for Fully Homomorphic Encryption
- DeepReDuce: ReLU Reduction for Fast Private Inference
- Circa: Stochastic ReLUs for Private Deep Learning
- Adapting AlphaEvolve to Optimize Fully Homomorphic Encryption on TPUs