Running a neural network on encrypted data with fully homomorphic encryption (FHE), meaning arithmetic performed directly on ciphertexts so the server never sees the input, is still several orders of magnitude slower than ordinary inference. Much of that cost comes from one structural fact. Every multiplication adds noise to a ciphertext. After a fixed number of sequential multiplications, the "level budget," the ciphertext must be refreshed by bootstrapping, an expensive operation that homomorphically runs the decryption circuit. Networks that run well under FHE therefore have to fit their nonlinear computation into this budget. The literature currently pulls in two directions on how to do that. Polynomial vision backbones argue that accuracy without ReLU requires depth, because stacking $L$ squaring layers gives polynomial degree $2^L$ (PolyNeXt). Encrypted-inference work argues that depth is exactly what FHE punishes (HEMET, CryptoGCN).
We propose to settle this tension with evolutionary architecture search, a population of candidate networks improved over generations by mutation and selection, using a different genotype and a different fitness from prior work. The genotype describes a network as a sequence of bootstrap segments. Each segment is a stretch of layers whose total multiplicative depth must fit the scheme's level budget. Within a segment the search can freely choose topology, width, skip connections and per-layer polynomial degree. The fitness is predicted encrypted latency from a level-aware cost model of the CKKS scheme, an approximate-arithmetic FHE scheme for real-valued vectors, calibrated against measured primitive costs. FLOPs and raw depth are not used. Our central hypothesis is that the depth-versus-shallowness conflict is mostly an artifact of measuring depth instead of bootstraps. Once bootstrapping is available, depth is nearly free inside a segment and costly only at segment boundaries. The accuracy–latency Pareto front should therefore show a staircase whose steps line up with bootstrap counts, and evolved networks should pack depth tightly up to each budget.
Core Claim
Searching over bootstrap-segmented polynomial architectures with a level-aware cost model should find CIFAR networks that dominate both hand-designed polynomial backbones and greedy or reinforcement-learning FHE searches on encrypted latency at matched accuracy. The gains should come from where depth and rotations are placed, not from fewer operations. What is new is not "evolution plus FHE" in general. It is a search space whose unit is the bootstrap segment, mutations that respect the level budget by construction, and a fitness that ranks candidates by actual CKKS cost, including bootstrapping, which prior architecture searches did not model.
Relation to Prior Work
Three searches already target encrypted or private inference, and each leaves out the variable we care about. HEMET identified the "depth trap": mobile blocks that save plaintext FLOPs add layers and so increase FHE latency. It fixed this with a greedy block-by-block choice in leveled FHE with fixed degree-2 activations, so it never meets bootstrapping and cannot restructure skip topology. NASS used a reinforcement-learning controller with analytical cost estimators for the BFV/Gazelle hybrid protocol. We reuse its idea of an analytical cost engine in the loop, but rebuild it for CKKS with bootstrapping, where the cost structure is different. SAFENet searched per-channel polynomial degrees (0, 2, 3) with population-based training, but only on fixed backbones. Its degree search is the closest single ingredient to ours, and we treat "SAFENet-style degree search on a fixed backbone" as the main threat (see below).
The other papers in the area supply methods or motivation rather than competing designs. PolyNeXt supplies building blocks: Hadamard-product polynomial mixers and stabilization recipes such as sigmoid-scale gating and multi-input skips. It also states that it never ran on an FHE backend, which motivates our setting. Adapting AlphaEvolve to Optimize Fully Homomorphic Encryption on TPUs is evolutionary search over FHE, but over kernel code such as rotation and blind rotation, not over network topology. Its work is complementary: faster primitives change the constants in our cost model, not its form. HEAT co-adapts weights with the iteration counts of approximation solvers inside a fixed GPT-2 and does not touch topology. DCT-CryptoNets prunes early ReLUs by hand after a frequency transform and reports diminishing returns at 32×32 resolution, so we leave frequency inputs out of scope for CIFAR.
The cryptographic constraints come from CryptoNets (square activations, slot batching), Polynomial Approximations for Secure Neural Network Inference (higher degree raises multiplicative depth), Mitigating the Computational Overhead of Encrypted Machine Learning and Circuit Bootstrapping: Faster and Smaller (bootstrapping as the main bottleneck), and HETAL, which reports that rotations can dominate encrypted matrix multiplication and that polynomial replacements destabilize training. Two warnings from the neuroevolution side shape our operators and our evaluation of candidates. Qian et al. note that noisy fitness destabilizes rank selection and that generic mutations ignore structural priors. EvoPose2D shows that letting children inherit their parents' weights makes population search affordable, completing a full search in about a day on eight v2-8 TPUs.
Research Program
Search space and mutations. A genotype is an ordered list of segments. Each segment holds a small directed graph of convolutional and polynomial-mixer nodes, with a width and a polynomial degree drawn from {0, 2, 3, 4} attached to each nonlinearity. An explicit depth counter is attached to every node. Mutations that preserve the level budget can do four things: move a degree-raising operation between adjacent segments, trade one deep path for two parallel shallower branches merged by addition (addition costs no level), add or remove a skip, and split or merge segments, which changes the bootstrap count by exactly one. Any mutation that would exceed the budget is repaired by rebalancing instead of being rejected. This is the structural prior that Qian et al. say generic operators lack.
Cost model. Predicted latency is
$$T(a) = \sum_{\ell} \big[ m_\ell(a)\, c_{\text{mult}}(q_\ell) + r_\ell(a)\, c_{\text{rot}}(q_\ell) \big] + B(a)\, c_{\text{boot}},$$
where $\ell$ indexes layers of architecture $a$, $m_\ell$ and $r_\ell$ count ciphertext multiplications and slot rotations under a fixed packing strategy, $q_\ell$ is the ciphertext level at layer $\ell$ (higher levels mean larger moduli and costlier primitives), $c_{\text{mult}}, c_{\text{rot}}$ are measured per-level primitive costs, $B(a)$ is the number of bootstraps, and $c_{\text{boot}}$ is the measured bootstrap cost. The per-level costs come from microbenchmarks on our CKKS backend. We validate the model before the search depends on it.
Search and training. We run multi-objective regularized evolution over predicted latency and validation accuracy. Children inherit parent weights as in EvoPose2D and are fine-tuned briefly. Training adds CKKS-scale Gaussian noise to activations, and PolyNeXt's gating recipe is applied so that rankings are not dominated by divergent polynomial training runs. Final Pareto members are retrained from scratch and run fully encrypted.
Baselines
The naive reference point is a standard ResNet-style CIFAR network with every ReLU replaced by $x^2$, as in CryptoNets. It is compiled to our CKKS backend with bootstraps placed by the compiler. Every method must clearly beat this.
The strongest hand-designed competitor is a CIFAR-scaled PolyNeXt. We run it in two forms: as published, which is deep and narrow, and as a shallower, width-matched variant. Both are trained with the same recipe and epochs as our final models. No encrypted number exists for it. PolyNeXt reports 83.9% ImageNet top-1 only in plaintext, so we would be producing the first encrypted measurement.
The strongest prior search for encrypted latency is HEMET's greedy block selector. HEMET reports 29.6 s CIFAR-10 latency for its SqueezeNet variant, down from 72.7 s, with a 0.4–0.5% accuracy gain, in leveled FHE. We reimplement its greedy rule using our cost model and backend so that the comparison isolates search strategy from cryptographic setting. We also run NASS's search space with an evolutionary or RL controller under the same cost model. NASS reports 84.6% CIFAR-10 accuracy with a 2× runtime reduction over Gazelle after about 60 GPU-hours, but that is a BFV-plus-garbled-circuits protocol and not directly comparable.
The most dangerous baseline is SAFENet-style search over polynomial degrees on a fixed ResNet-32 / CNN-7 backbone, given the same GPU-hour budget and the same cost model. SAFENet reports 85.1% on CNN-7 with 61% lower latency than Delphi, again in a hybrid HE/secure-multiparty-computation setting rather than pure FHE.
Two ablations isolate our ingredients. The first replaces the fitness with multiplicative depth plus FLOPs. The second replaces segment-aware mutations with generic graph mutations.
All searches get the same GPU-hour budget, which we fix at NASS's roughly 60 GPU-hours, plus the same final retraining recipe and the same encrypted evaluation harness. "Beating" a baseline means lower measured encrypted latency at equal or higher accuracy, within a seed-variance band estimated from three seeds, at two or more points along the Pareto front.
Why not just…?
Why not just hand-design a shallow polynomial network? Possibly one can. But the hand-designed option today, PolyNeXt, was tuned for plaintext expressiveness and argues for depth, while HEMET shows that intuitions from plaintext efficiency invert under FHE. If the width-matched shallow PolyNeXt lands on our Pareto front, the honest conclusion is that the cost model, not the search, is the contribution. Our evaluation is designed to reveal that outcome.
Why not just search degrees on a fixed backbone? This is the real threat. If topology barely matters once degrees and bootstrap placement are tuned, then SAFENet-style degree search under our cost model would match us more cheaply. The fixed-backbone baseline at equal budget decides this. We expect topology to matter specifically through branch-for-depth trades, which a fixed backbone cannot make. If it does not, we report that degree search with a level-aware cost suffices.
Why not just use random search or a greedy rule with the same cost model? In architecture search, random search with a good evaluator is often competitive. We run it at equal budget. If random search matches regularized evolution, the claim shrinks to the search space and the cost model, and we will say so. Greedy search is weaker by construction because merging or splitting segments is a non-local move, but this remains an empirical question.
Why not just tune approximation precision on a pretrained model, as HEAT does? HEAT gets a 1.4× speedup on GPT-2 by learning solver iterations, but bootstraps and depth stay fixed by the parent model. We include HEAT-style learnable degree truncation as a post-hoc step applied to both the baseline backbones and our evolved networks. If it closes the gap on baselines, topology search is not needed.
Proposed Experiments
The first decisive check validates the cost model. We sample 50 architectures across the search space, run each end-to-end encrypted on CIFAR-10, and require a Spearman rank correlation above 0.9 between predicted and measured latency. Without that, the search is ranking candidates on noise, the failure mode Qian et al. warn about. We also ask whether a depth-plus-FLOPs proxy ranks these architectures noticeably worse; if it does not, our fitness adds nothing.
The second check is the main comparison on CIFAR-10 and CIFAR-100 against all baselines above. We report encrypted latency per image, bootstrap count, rotation count, top-1 accuracy, and agreement between encrypted and plaintext predictions on the test set. The third check tests the staircase hypothesis directly. We plot the evolved Pareto front against bootstrap count and measure how much of each segment's level budget is used. The hypothesis predicts near-full use and accuracy jumps at segment boundaries. A smooth front with low budget use would falsify the claim that bootstrap segments are the right unit of design. Finally, we transfer the best CIFAR segment structure to a reduced-resolution ImageNet subset as a scaling probe. DCT-CryptoNets, at 66.3% encrypted top-1 and 2.5 hours per image under TFHE, is the reference point, interpreted cautiously because the scheme differs.
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
- CryptoGCN: Fast and Scalable Homomorphically Encrypted Graph Convolutional Network Inference
- NASS: Optimizing Secure Inference via Neural Architecture Search
- SAFENet: A Secure, Accurate and Fast Neural Network Inference
- Adapting AlphaEvolve to Optimize Fully Homomorphic Encryption on TPUs
- HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation
- DCT-CryptoNets: Scaling Private Inference in the Frequency Domain
- CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy
- Circuit Bootstrapping: Faster and Smaller
- HETAL: Efficient Privacy-preserving Transfer Learning with Homomorphic Encryption
- Derivative-free reinforcement learning: a review
- EvoPose2D: Pushing the Boundaries of 2D Human Pose Estimation Using Accelerated Neuroevolution With Weight Transfer