Investigate SLOTHE: Lazy Approximation of Non-Arithmetic Neural Network Functions over Encrypted Data

**SLOTHE : Lazy Approximation of Non-ArithmeticNeural Network Functions over Encrypted Data**
_Kevin Nam, Youyeon Joo, Seungjin Ha, and Yunheung Paek, Seoul National University_
https://www.usenix.org/system/files/usenixsecurity25-nam-slothe.pdf

> Machine Learning as a Service (MLaaS) introduces strong privacy concerns for both clients and model providers. Fully Homomorphic Encryption (FHE) offers a promising solution by enabling inference over encrypted data, but its limited expressiveness requires approximating non-arithmetic functions (NAFs) with polynomials, often leading to significant accuracy and performance trade-offs. Existing works adopt an eager approximation (EA) strategy, which statically replaces each NAF with a fixed polynomial, locking in computational errors and limiting optimization opportunities. We propose SLOTHE, a lazy approximation (LA) solution that recursively decomposes NAF codes into arithmetic and non-arithmetic sub-functions, selectively approximating only the non-arithmetic components when required. SLOTHE introduces a tunable cost model to balance accuracy and latency, and incorporates FHE-aware optimizations to eliminate redundant computation. Implemented using CKKS, SLOTHE achieves up to 42,378× lower maximum error than EA-based works, with improved inference accuracy and latency across BERT-based transformers. SLOTHE can also be adapted for MPC-based protocols, making it a flexible tool for secure neural network inference.

The key idea here seems to be that, rather than directly approximating, e.g., GeLU as a function, they look at the actual algorithm that implements the GeLU computation, which will decompose into some arithmetic and some non-arithmetic things, and only approximate the latter (potentially recursing the same idea into subfunctions).