Preprint.
Layer-Parallel Inference Reduces Encrypted Nonlinear Depth in Transformers Ligong Han1,2,3 ∗ Kai Xu2,3 Hao Wang2,3 Ruijiang Gao5 Akash Srivastava3,4 1 MBZUAI IFM 2 Red Hat AI Innovation 3 MIT-IBM Watson AI Lab 4 Core AI, IBM 5 University of Texas at Dallas
arXiv:2607.04819v1 [cs.LG] 6 Jul 2026
Abstract Fully homomorphic encryption (FHE) enables computation on encrypted data, but practical encrypted Transformer inference is bottlenecked by the sequential composition of many nonlinear blocks. We study whether Structured Newton Layer Parallelism (SNLP) (Han et al., 2026) can make this inter-layer composition more FHE-friendly: each Transformer block still requires polynomial approximations for operations such as softmax and RMSNorm, but SNLP reduces the layerwise sequential nonlinear depth from L stages to a small number of solver iterations plus linear structured corrections. Using a simulation framework based on Chebyshev polynomial approximations, we measure error accumulation under sequential versus SNLP inference across 8 models and 4 architecture families. On a 0.5B IDN-trained model, SNLP reduces symbolic bootstraps from 53 to 20 (2.65×) with only +1.2% perplexity degradation, while lowering error amplification (1.36× vs. 1.42×). Across all tested models, SNLP has lower amplification than sequential inference. Ablations show that softmax approximation dominates the error budget and CKKS arithmetic noise is negligible in our setting, suggesting that SNLP is complementary to block-level FHE-friendly operator design rather than a replacement for it.
1
Introduction
Transformer language models (Vaswani et al., 2017) are sequential along the layer axis: the hidden state at layer l + 1 depends on the output of layer l. Under fully homomorphic encryption (FHE), this sequential composition is particularly costly. Each Transformer block contains operations that are not native to FHE arithmetic: softmax requires exponentiation, RMSNorm requires inverse square root, and activations require nonlinear evaluation, all of which must be approximated by polynomials when operating on encrypted data (Chen et al., 2022; Hao et al., 2022; Pang et al., 2024). These polynomial approximations introduce per-block errors that compound across L sequential layers, consuming the modulus budget and requiring frequent bootstrapping, the most expensive FHE operation, accounting for 50–86% of total inference latency (Agrawal et al., 2024). We observe that Structured Newton Layer Parallelism (SNLP) (Han et al., 2026) offers a complementary direction for reducing FHE inference cost. SNLP does not make an individual Transformer block FHE-native: softmax, normalization, and activations still require approximation or redesign. Instead, SNLP changes the inter-layer computation graph. Rather than composing L nonlinear block evaluations sequentially, SNLP evaluates suffix layers in parallel over K solver iterations and propagates information across depth using structured Newton-style corrections. For IDN, the correction is purely additive and has zero FHE multiplicative depth; for HCN, it is a small linear mixing over streams. Thus SNLP targets the sequential composition of FHE-unfriendly blocks, not the local block operators themselves. We introduce the metric NFE (Nonlinear Forward Evaluations) = ( L − N ) + K, where N is the number of parallel suffix layers. In our symbolic CKKS cost model, NFE tracks ∗ Work done while at Red Hat AI Innovation.
1
Preprint.
the FHE bootstrap count closely (ratio 0.99–1.02×). Using a simulation framework that replaces nonlinear operations with Chebyshev polynomial approximations, we measure how polynomial errors accumulate under sequential versus SNLP inference. Our main findings: • SNLP has lower error amplification than sequential across all 8 models at degree 12, and across all tested degrees on the 0.5B IDN model. On that model, SNLP reduces bootstraps from 53 to 20 (2.65×) with +1.2% PPL degradation and lower amplification (1.36× vs. 1.42×). • mHC architectures (Zhu et al., 2025; Xie et al., 2025) are inherently more FHE-friendly (1.24× amplification vs. 1.42× for standard models) because their HC connections are purely linear. • FHE-optimal SNLP configurations differ from wallclock-optimal ones: some higher-K configurations trade extra solver depth for lower error while remaining much shallower than the sequential baseline, despite being slower in wall-clock time. • Softmax approximation remains the dominant local error source, while CKKS arithmetic noise is negligible at the precisions we test; SNLP should therefore be viewed as complementary to, not a substitute for, FHE-friendly block design.
2
Related Work
FHE for neural network inference. Fully homomorphic encryption enables computation on encrypted data without decryption. The CKKS scheme (Cheon et al., 2017) supports approximate floating-point arithmetic, making it the most common choice for neural network inference. CryptoNets (Gilad-Bachrach et al., 2016) first applied neural networks to encrypted data. Subsequent work on encrypted Transformer inference includes THEX (Chen et al., 2022), Iron (Hao et al., 2022), BOLT (Pang et al., 2024), and THOR (Moon et al., 2025), which approximate all nonlinear operations (softmax, normalization, activations) with polynomials and report inference times of 30 seconds to 10+ minutes for BERT- or GPT-2-scale models. Beyond inference, HE has also been applied to data valuation and sharing (Yang et al., 2025). These approaches focus on improving per-block polynomial approximation quality and reducing per-layer circuit depth. Our work is complementary: rather than changing the per-block approximation, we change the inter-layer computation graph to reduce the number of sequential nonlinear stages. Parallel solvers and structured recurrences. SNLP builds on the view that a sequential computation can be solved as a coupled nonlinear system. DEER (Lim et al., 2024) applies Newton’s method to nonlinear recurrences; later work extends this to MCMC chains (Zoltowski et al., 2025) and improves scalability with quasi-Newton approximations (Gonzalez et al., 2024). Song et al. (Song et al., 2021) frame feedforward computation as parallel equation solving, and Jacobi decoding (Santilli et al., 2023) applies fixed-point iteration to autoregressive translation. Parallel prefix scan (Blelloch, 1990) underlies efficient recurrent and state-space models (Martin & Cundy, 2018; Gu et al., 2022; Gu & Dao, 2024); SNLP uses the same principle for depthwise correction. Our work rotates these ideas from sequence length to Transformer depth, using structured surrogates that avoid full layer Jacobians. Depth mixing and efficient inference. Residual connections (He et al., 2016) are central to deep Transformers; Hyper-Connections and mHC (Zhu et al., 2025; Xie et al., 2025) introduce learned residual-stream mixing, while value residual (Zhou et al., 2025) and x0 style connections (Jordan et al., 2024) alter how features persist through depth. Most efficient LLM inference work accelerates per-layer execution through KV caching (Kwon et al., 2023), kernel engineering (Dao et al., 2022), speculative decoding (Leviathan et al., 2023; Chen et al., 2023), or early exit (Schuster et al., 2022). SNLP targets a different bottleneck: the dependency chain across layers for a fixed token prefix. 2
Preprint.
3
Background
3.1
FHE for Neural Networks
FHE schemes such as CKKS (Cheon et al., 2017) enable approximate arithmetic on encrypted data. The key cost dimensions are multiplicative depth (each ciphertext-ciphertext multiplication consumes one modulus level), bootstrapping (refreshing the modulus chain, which is roughly 600× more expensive than a plaintext multiplication (Agrawal et al., 2024)), and rotations (for ciphertext packing and vector operations). Prior FHE-ML work on Transformer inference (Chen et al., 2022; Hao et al., 2022; Pang et al., 2024; Moon et al., 2025) reports latencies of 30 seconds to 10+ minutes for a single BERT or GPT-2 forward pass, with polynomial approximation of all nonlinear operations being the primary engineering challenge. For a Transformer block, the FHE-unfriendly operations are: softmax (requires exp), RMSNorm (requires rsqrt), activation functions (GELU, SiLU, or ReLU), and sigmoid/tanh gates. Linear operations (matrix multiplies, additions, rotations) are natively supported. In a standard L-layer Transformer, these nonlinear operations compose sequentially L times, yielding total encrypted nonlinear depth proportional to L. 3.2
SNLP Overview
Structured Newton Layer Parallelism (Han et al., 2026) treats the hidden-state trace h = (h1 , . . . , h L ) as the solution of a nonlinear residual equation Gl (h) = hl − f l (hl −1 ) = 0,
l = 1, . . . , L,
(1)
where f l is the l-th Transformer block. Rather than solving this sequentially, SNLP evaluates the first S layers sequentially (the prefix), then iteratively solves for the remaining N = L − S suffix layers. At iteration k, each suffix layer is first evaluated using the current estimate of its input: (k) (k) e h = fl h , l = S + 1, . . . , L. (2) l
l −1
These evaluations are independent across l and can be batched or fused. SNLP then applies the structured Newton correction: ( k +1) (k) (k) ( k +1) (k) ( k +1) hl =e hl + Al h l −1 − h l −1 , h S = hS , (3) (k)
where Al
(k)
is a structured surrogate for the block Jacobian Jl
(k)
= ∂ f l /∂hl −1 . If Al (k)
(k)
= Jl ,
this recovers the exact Newton update over depth. SNLP instead chooses Al so that the correction is much cheaper than evaluating or materializing the true Jacobian, while still propagating information from earlier corrected layer states to later ones. Identity Newton (IDN) uses Al = I, reducing the correction to additive prefix-sum propagation with zero FHE multiplicative depth. HC Newton (HCN) uses the mHC residual mixing res H res , which is a small S × S matrix over the stream dimension (Zhu matrix Al = Hmlp,l attn,l et al., 2025; Xie et al., 2025). Both surrogates keep the correction cost negligible compared to the nonlinear block evaluations. SNLP-aware training adds an auxiliary loss during pretraining that makes the finite-iteration SNLP solve match the sequential trace, enabling the model to work with the cheap surrogate (Han et al., 2026).
4
Method
4.1
FHE Cost Model and NFE
We define NFE (Nonlinear Forward Evaluations) as the number of sequential nonlinear stages in the computation graph: NFEseq = L,
NFESNLP = ( L − N ) + K,
(4)
where N is the number of parallel suffix layers and K is the number of SNLP iterations. NFE captures the FHE cost because each nonlinear stage requires polynomial approximation 3
Preprint.
(consuming multiplicative depth and potentially bootstrapping), while the IDN correction adds zero multiplicative depth (it consists only of ciphertext additions and plaintext scalar multiplies). To verify that NFE is a faithful proxy for actual FHE cost, we build a symbolic CKKS cost model. For a degree-d Chebyshev approximation of softmax, each Transformer block has nonlinear multiplicative depth roughly 4d + 7 (accounting for two RMSNorm evaluations, one QK-norm, one softmax, one activation, and one sigmoid gate). With 15 usable CKKS levels before bootstrapping, the number of bootstraps scales linearly with NFE. In this symbolic model, NFE tracks the bootstrap count within 1–2% across all tested configurations (Table 1). 4.2
HE-Approximation Simulation
Rather than implementing full CKKS encryption (which would limit us to small models due to the computational overhead), we simulate the effect of FHE-compatible operations by replacing each nonlinear operation with its polynomial approximation in the PyTorch forward pass. Chebyshev polynomial fitting. For each nonlinear function g( x ) (e.g., exp, σ, tanh), we compute a degree-d Chebyshev polynomial approximation on a calibrated interval [ a, b]. The fitting interval is determined by running 20 batches of validation data through the model and recording the input distribution (min, max, percentiles) for each nonlinear operation at each layer. For softmax, we use the interval [−20, 0] (after max-subtraction for numerical stability), which covers the 99th percentile of attention scores across all layers. At runtime, input values are clamped to the fitting interval before polynomial evaluation. We note that in real CKKS, the max-subtraction used for softmax stability requires comparison circuits, and the normalization step requires reciprocal approximation; these additional costs are not reflected in our NFE metric. Since both sequential and SNLP use identical per-block approximations, this does not affect the relative comparison. Per-operation approximation.
We replace each nonlinear operation as follows:
• Softmax: Chebyshev polynomial approximation of exp( x ) on [−20, 0], followed by renormalization. Degree d ∈ {8, 10, 12, 14} controls the accuracy-depth tradeoff. • RMSNorm: Simulated Goldschmidt iteration for rsqrt. Each iteration doubles the precision of the approximation; we model the residual error as controlled multiplicative noise with scale 10−(n+1) for n iterations. • Sigmoid and Tanh: Chebyshev polynomial approximation on calibrated intervals [−8, 8] and [−3, 3], respectively. • ReLU2 : Kept exact in our simulation. In real CKKS, max(0, x )2 is not itself a polynomial and would require either a comparison circuit or a smooth polynomial approximation; we leave this cost out of the simulated approximation error and include only its symbolic depth in the cost model. • CKKS arithmetic noise: Optional additive Gaussian noise with standard deviation σ = scale · 2−b , where b is the precision bits and scale is the signal magnitude. Implementation. We implement two modified forward passes: forward_sequential_he, which applies polynomial approximations in all L layers sequentially, and forward_snlp_he, which applies polynomial approximations in the K iterations of parallel block evaluation while keeping the IDN correction exact (since it is purely additive). Both paths share the same polynomial approximation code, ensuring that any difference in output is due to the computational structure (sequential vs. SNLP), not the approximation quality. A critical sanity check validates the implementation: with all polynomial degrees set to exact (bypassing approximation), both forward paths produce bit-identical results to the standard PyTorch forward (maximum absolute difference = 0.0 across all tested models). 4
Preprint.
Config Sequential SNLP n8-K4 SNLP n12-K2 SNLP n20-K4 SNLP n24-K4 SNLP n24-K8
NFE
Bootstraps
Mult. Depth
NFE Reduction
32 28 22 16 12 16
53 46 36 26 20 26
768 672 528 384 288 384
1.00× 1.14× 1.45× 2.00× 2.67× 2.00×
Table 1: Symbolic FHE cost comparison (0.5B model). NFE = nonlinear forward evaluations. Bootstraps estimated with 15 usable CKKS levels per bootstrap. Bootstrap counts depend on NFE and are independent of the polynomial degree used for nonlinear approximation, since IDN correction adds zero multiplicative depth. Error amplification. The key metric is error amplification: PPLHE /PPLexact , where PPLHE is the perplexity under polynomial approximation and PPLexact is the perplexity with exact operations. This ratio isolates the structural effect of error accumulation: if SNLP has lower amplification than sequential, it accumulates less polynomial approximation error despite computing the same per-block approximations. 4.3
Models
We evaluate 8 Nanochat (Karpathy, 2025) models spanning 4 architecture families, all with L = 32 layers: • Standard (3B and 0.5B): baseline and IDN-regularized (λ = 1/16–0.5). The 3B model has nembd = 2048 with 16 heads; the 0.5B model has nembd = 640 with 5 heads. • w/o x0 /VE (0.5B): removes value embeddings (Zhou et al., 2025) and x0 residual connections (Jordan et al., 2024), resulting in fewer nonlinearities per block (no sigmoid gate). • mHC (0.5B): manifold-constrained HyperConnections (Xie et al., 2025) with 4 streams and HCN correction. All models are trained from scratch on ClimbMix (Diao et al., 2025). PPL is evaluated on a fixed validation split at sequence length 2048. For efficiency, most experiments use 200k tokens; we verify that amplification ratios are stable at 1M tokens (within 0.3%).
5
Experiments
FHE cost comparison. We first evaluate the depth savings predicted by the symbolic CKKS cost model. Because the IDN correction adds no multiplicative depth, the cost is controlled by NFE: replacing 32 sequential nonlinear stages with n24-K4 reduces NFE to 12 and bootstraps from 53 to 20, a 2.65× reduction. The n24-K8 row illustrates a FHEspecific operating point: it uses more solver iterations than n24-K4, but still has half the bootstrap count of sequential inference while offering better approximation quality in later experiments. Per-operation ablation. The approximation error is highly concentrated in softmax. In Table 2, approximating RMSNorm or sigmoid alone changes PPL by less than 0.2%, while the logit softcap tanh contributes 12.8%. Softmax is the bottleneck: degree-4 and degree-8 approximations are unusable, and even degree 12 raises PPL by 43.7%. Approximating all operations at degree 12 gives nearly the same degradation as approximating softmax alone, so the remaining experiments focus on how SNLP changes the accumulation of this dominant error source. Polynomial degree sweep. On the 0.5B IDN model, approximation quality changes sharply between degrees 8 and 10 (Table 3). Degree 8 leaves both sequential and SNLP inference effectively broken, with 12–13× amplification. From degree 10 onward, SNLP retains a 5
Preprint.
Approximated Operation
Degree
Sequential PPL
Degradation
– 1 iter 4 4 4 8 12 12
13.08 13.10 13.11 14.76 480.60 168.70 18.80 18.75
– +0.2% +0.2% +12.8% +36.7× +12.9× +43.7% +43.4%
None (exact) RMSNorm only Sigmoid only Tanh only Softmax only Softmax only Softmax only All operations
Table 2: Per-operation ablation on the 0.5B IDN model (10 batches, seq_len=2048). Each row approximates one operation while keeping others exact. Softmax dominates the error budget at all polynomial degrees. Degree
Seq Amp.
n24-K4 Amp.
n20-K4 Amp.
SNLP Advantage (n24-K4)
8 10 12 14
12.57× 1.93× 1.42× 1.41×
11.85× 1.85× 1.36× 1.34×
12.34× 1.89× 1.38× 1.37×
0.7 pp 8.6 pp 6.3 pp 6.3 pp
Table 3: Error amplification vs. polynomial degree (0.5B IDN model, 200k tokens). A phase transition occurs at degree 10. Degrees 12 and 14 give similar results; degree 12 is the practical minimum. SNLP advantage is consistent at all degrees. 6–9 pp advantage over sequential, and degrees 12 and 14 are nearly indistinguishable. We therefore use degree 12 as the default in the remaining experiments. CKKS noise robustness. Adding simulated CKKS arithmetic noise on top of degree-12 approximation has no visible effect at the precisions we test (Table 4). The amplification values are unchanged, within rounding, from 40-bit precision down to an aggressive 20-bit setting. In this regime, softmax polynomial error is the dominant perturbation; arithmetic noise is roughly four orders of magnitude smaller even at 6-digit precision. Cross-model error amplification. With the approximation setup fixed at degree 12, we compare sequential and SNLP inference across all 8 models in Table 5. The SNLP configuration selected for each model has lower error amplification than the corresponding sequential run. The largest gap is on the 0.5B IDN-trained model (m4): n24-K4 reduces NFE from 32 to 12 and lowers amplification by 6.4 pp. By contrast, baseline models without SNLP-aware training (m3, m5) tolerate only conservative configurations, so their NFE reduction is limited to 1.14× and the amplification improvement stays below 1 pp. Architecture also matters. The mHC model (m8) has the lowest sequential amplification among 0.5B models (1.24×), close to the 3B model (1.25×). Its HC width and depth connections are linear matrix operations, and the HCN correction is a small S × S linear transform, so these architectural additions do not introduce extra nonlinear FHE depth. The 3B models are also less sensitive than the standard 0.5B models (1.25× vs. 1.42×), consistent with wider hidden states diluting per-element approximation errors. NFE vs. PPL Pareto analysis. The full ( N, K ) sweep in Figure 1 separates two effects that are hidden by the single best-configuration table. First, SNLP-aware training shifts the Pareto frontier: the IDN-trained model reaches NFE = 12 with only +1.2% PPL degradation, whereas the baseline cannot achieve practical quality below NFE = 20. Second, the useful frontier is narrow. NFE = 12–16 gives PPL within 1% of sequential while reducing bootstraps by 2–2.65×; below NFE = 10, quality drops rapidly (+14–50%). The n24-K8 point highlights why the FHE frontier differs from the GPU wall-clock frontier. It reaches near-sequential quality (+0.1%) with 2× fewer bootstraps, even though K = 8 6
Preprint.
Noise bits
Precision
Seq Amp.
n24-K4 Amp.
Seq PPLHE
∞ (none) 40 30 25 20
exact arith. ∼12 digits ∼9 digits ∼7.5 digits ∼6 digits
1.419× 1.419× 1.419× 1.418× 1.419×
1.355× 1.355× 1.354× 1.354× 1.355×
19.96 19.96 19.96 19.95 19.96
Table 4: CKKS noise robustness (0.5B IDN model, degree-12). Polynomial approximation error (∼1% per operation) dominates CKKS arithmetic noise by ∼10,000× even at 6-digit precision. All amplification values are identical within rounding. Model
Type
PPLexact
Seq Amp.
m1 Baseline m2 IDN Reg.
3B 3B
9.34 9.34
1.246× 1.270×
m3 Baseline m4 IDN Reg.
0.5B 0.5B
13.91 14.07
m5 Baseline m6 IDN Reg.
0.5B 0.5B
15.89 15.95
m7 Baseline m8 HCN Reg.
0.5B mHC 0.5B mHC
13.83 14.19
Best SNLP
SNLP Amp.
Boots
NFE
Advantage
1.212× 1.267×
46 46
28 28
−3.5 pp −0.3 pp
1.462× 1.355×
46 20
28 12
−0.9 pp −6.4 pp
1.457× 1.499×
46 20
28 12
−0.9 pp −2.5 pp
1.292× 1.217×
46 26
28 16
−1.7 pp −2.1 pp
Nanochat-3B n8-K4 n8-K4
Nanochat-0.5B standard 1.472× 1.419×
n8-K4 n24-K4
Nanochat-0.5B w/o x0/VE 1.466× 1.524×
n8-K4 n24-K4
Nanochat-0.5B-mHC 1.309× 1.238×
n8-K4 n20-K4
Table 5: Cross-model error amplification (PPLHE /PPLexact ) with degree-12 polynomial approximation (200k tokens, seq_len=2048). “Advantage” is the reduction in amplification percentage points. Boots = bootstrap count from symbolic CKKS cost model. All models have L = 32 layers, all SNLP configs employ h0 initialization. makes it slower than sequential inference on GPU. For encrypted inference, this is still a plausible operating point because the relevant cost is sequential nonlinear depth rather than ordinary wall-clock time. Per-layer error accumulation. Finally, we inspect where the error difference emerges. For n24-K1, the sequential and SNLP paths share layers 0–7, so their relative errors are identical in the prefix (Figure 2). The traces diverge in layers 8–31. Sequential inference repeatedly feeds polynomial approximation error into the next nonlinear block, while SNLP evaluates the suffix blocks in parallel within an iteration and propagates corrections through additive linear updates. The final hidden-state error is about 1.2% lower for SNLP, and the logit-level difference is about 13%.
6
Discussion
mHC is most FHE-friendly among 0.5B models. The mHC architecture (m8) achieves the lowest sequential amplification (1.24×) among 0.5B models, comparable to the 3B model (1.25×). The HC width and depth connections are purely linear matrix operations that add zero nonlinear FHE depth; the mHC-Newton correction uses a small S × S matrix multiply (also linear). This suggests that architectures with linear residual-stream mixing are inherently well-suited for encrypted inference, complementing the per-block polynomial approximation improvements pursued by prior FHE-ML work. FHE-optimal ̸= wallclock-optimal. The SNLP configuration n24-K8 (NFE = 16) achieves near-sequential PPLHE (+0.1%) with 2× fewer bootstraps, but is slower than sequential in wall-clock time because K = 8 iterations are compute-heavy. In FHE, cost scales with 7
PPL under HE Approximation (deg-12)
Preprint.
32
IDN-trained (m4) Baseline (m3)
30 28 26 24
Sequential (NFE=32)
n24 K4 (headline)
22 20 10
15
20
25
NFE (Nonlinear Forward Evaluations)
30
Figure 1: NFE vs. PPL under degree-12 HE approximation. Each point is one ( N, K, init) configuration from a full sweep. The IDN-trained model (blue) dominates the baseline (orange) Pareto frontier, reaching NFE = 12 with only +1.2% PPL degradation. The baseline cannot achieve practical quality below NFE = 20, confirming that SNLP-aware training is essential for accessing the low-NFE regime.
Relative Error hHE hexact / hexact
0.7 prefix (shared)
parallel layers
0.6 0.5 0.4 0.3
Sequential (NFE=32, Boots=53) SNLP n24 K1 (NFE=9, Boots=15)
0
5
10
15
Layer Index
20
25
30
Figure 2: Per-layer relative error ∥ hHE − hexact ∥/∥ hexact ∥ under degree-12 polynomial approximation (0.5B IDN model, N = 24, K = 1). SNLP uses 3.5× fewer bootstraps (15 vs. 53) yet achieves comparable per-layer error to sequential inference. Prefix layers (0–7) are shared. In the parallel layers (8–31, shaded), SNLP error stays at or below sequential despite evaluating all suffix blocks in parallel with only one Newton iteration. sequential depth, not wall-clock time: more iterations at lower depth is cheaper in FHE but slower on GPU. This creates a distinct FHE operating point not captured by the original SNLP speed-quality tradeoff, and suggests that future FHE-oriented SNLP training could specifically optimize for the depth-quality frontier rather than the speed-quality frontier. Larger models are more robust. The 3B models show lower amplification (1.25×) than 0.5B models (1.42×). With wider hidden dimensions (D = 2048 vs. 640), per-element polynomial approximation errors are diluted across more dimensions, resulting in less relative perturbation to attention patterns and MLP outputs. Limitations. Our framework simulates polynomial approximation, not actual CKKS encryption. The softmax implementation uses max-subtraction for numerical stability, which 8
Preprint.
requires comparison circuits in real FHE (an additional cost not reflected in our NFE metric). RMSNorm uses controlled noise rather than actual Goldschmidt iteration. These simplifications do not affect the relative comparison between sequential and SNLP (both use the same approximations), but mean that absolute FHE cost numbers are estimates. The models are trained at Nanochat scale (0.5B–3B); generalization to larger models remains to be tested, though the trend that larger models have lower amplification is encouraging. Since softmax dominates the approximation error in our ablations, future work should test whether SNLP composes well with architectures that reduce or replace softmax attention, including gated attention (Qiu et al., 2026), linear attention (Gu et al., 2022; Gu & Dao, 2024; Yang et al., 2024).
7
Conclusion
We showed that SNLP provides a complementary direction for FHE-friendly Transformer inference. It does not remove the need to approximate or redesign FHE-unfriendly block operations such as softmax. Instead, it makes the composition of many Transformer blocks more favorable by reducing layerwise sequential nonlinear depth from L stages to ( L − N ) + K stages, with linear structured corrections. Across 8 models and 4 architecture families, SNLP consistently accumulates less polynomial approximation error than sequential inference. The headline result: SNLP n24-K4 reduces bootstraps from 53 to 20 (2.65×) with only +1.2% PPL degradation under degree-12 Chebyshev softmax approximation, while exhibiting lower error amplification (1.36× vs. 1.42×).
References Rashmi S. Agrawal, Anantha P. Chandrakasan, and Ajay Joshi. HEAP: A fully homomorphic encryption accelerator with parallelized bootstrapping. In 2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA), pp. 756–769. IEEE, 2024. Guy E Blelloch. Prefix sums and their applications. In Synthesis of Parallel Algorithms, pp. 35–60. Morgan Kaufmann, 1990. Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318, 2023. 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 encryption. In Findings of the Association for Computational Linguistics: ACL 2022, pp. 3510–3520. Association for Computational Linguistics, 2022. Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In Advances in Cryptology – ASIACRYPT 2017, volume 10624 of Lecture Notes in Computer Science, pp. 409–437. Springer, 2017. Tri Dao, Daniel Y Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in Neural Information Processing Systems, 35, 2022. Shizhe Diao, Yu Yang, Yonggan Fu, Xin Dong, Dan Su, Markus Kliegl, Zijia Chen, Peter Belcak, Yoshi Suhara, Hongxu Yin, Mostofa Patwary, Celine Lin, Jan Kautz, and Pavlo Molchanov. Nemotron-climb: Clustering-based iterative data mixture bootstrapping for language model pre-training. Advances in Neural Information Processing Systems, 38, 2025. Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 201–210. PMLR, 2016. 9
Preprint.
Xavier Gonzalez, Andrew Warrington, Jimmy TH Smith, and Scott W Linderman. Towards scalable and stable parallelization of nonlinear rnns. Advances in Neural Information Processing Systems, 37:5817–5849, 2024. Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. In First Conference on Language Modeling, 2024. Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2022. Ligong Han, Kai Xu, Hao Wang, and Akash Srivastava. Snlp: Layer-parallel inference via structured newton corrections. arXiv preprint arXiv:2605.17842, 2026. Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang. Iron: Private inference on transformers. In Advances in Neural Information Processing Systems, volume 35, pp. 15718–15731, 2022. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770–778, 2016. Keller Jordan, Jeremy Bernstein, Brendan Rappazzo, Boza Vlado, You Jiacheng, Franz Cesista, and Braden Koszarsky. modded-nanogpt: Speedrunning the nanogpt baseline, 2024. URL https://github.com/KellerJordan/modded-nanogpt. Andrej Karpathy. nanochat: The best chatgpt that $100 can buy, 2025. URL https://github. com/karpathy/nanochat. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with PagedAttention. In Proceedings of the 29th Symposium on Operating Systems Principles, pp. 611–626, 2023. Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pp. 19274–19286. PMLR, 2023. Yi Heng Lim, Qi Zhu, Joshua Selfridge, and Muhammad Firmansyah Kasim. Parallelizing non-linear sequential models over the sequence length. In The Twelfth International Conference on Learning Representations, 2024. Eric Martin and Chris Cundy. Parallelizing linear recurrent neural nets over sequence length. In International Conference on Learning Representations, 2018. Jungho Moon, Dongwoo Lee, Minsu Jung, Jung Hee Lee, and Miran Kim. THOR: Secure transformer inference with homomorphic encryption. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2025. Qi Pang, Jinhao Zhu, Helen Möllering, Wenting Zheng, and Thomas Schneider. BOLT: Privacy-preserving, accurate and efficient inference for transformers. In 2024 IEEE Symposium on Security and Privacy (SP), pp. 4753–4771. IEEE, 2024. Zihan Qiu, Zekun Wang, Bo Zheng, Zeyu Huang, Kaiyue Wen, Songlin Yang, Rui Men, Le Yu, Fei Huang, Suozhi Huang, et al. Gated attention for large language models: Non-linearity, sparsity, and attention-sink-free. Advances in Neural Information Processing Systems, 38:100092–100118, 2026. Andrea Santilli, Silvio Severino, Emilian Postolache, Valentino Maiorca, Michele Mancusi, Riccardo Marin, and Emanuele Rodola. Accelerating transformer inference for translation via parallel decoding. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 12336–12355, 2023. 10
Preprint.
Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghani, Dara Bahri, Vinh Q Tran, Yi Tay, and Donald Metzler. Confident adaptive language modeling. Advances in Neural Information Processing Systems, 35, 2022. Yang Song, Chenlin Meng, Renjie Liao, and Stefano Ermon. Accelerating feedforward computation via parallel nonlinear equation solving. In International Conference on Machine Learning, pp. 9791–9800. PMLR, 2021. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30:5998–6008, 2017. Zhenda Xie, Yixuan Wei, Huanqi Cao, Chenggang Zhao, Chengqi Deng, Jiashi Li, Damai Dai, Huazuo Gao, Jiang Chang, Kuai Yu, et al. mhc: Manifold-constrained hyper-connections. arXiv preprint arXiv:2512.24880, 2025. Michael Yang, Ruijiang Gao, and Zhiqiang Zheng. Sell data to ai algorithms without revealing it: Secure data valuation and sharing via homomorphic encryption. arXiv preprint arXiv:2512.06033, 2025. Songlin Yang, Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim. Parallelizing linear transformers with the delta rule over sequence length. Advances in Neural Information Processing Systems, 37, 2024. Zhanchao Zhou, Tianyi Wu, Zhiyun Jiang, Fares Obeid, and Zhenzhong Lan. Value residual learning. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 28341–28356, 2025. Defa Zhu, Hongzhi Huang, Zihao Huang, Yutao Zeng, Yunyao Mao, Banggu Wu, Qiyang Min, and Xun Zhou. Hyper-connections. In The Thirteenth International Conference on Learning Representations, 2025. David M Zoltowski, Skyler Wu, Xavier Gonzalez, Leo Kozachkov, and Scott W Linderman. Parallelizing mcmc across the sequence length. Advances in Neural Information Processing Systems, 38, 2025.
11