💻 computer science

Decision-Aware Quadratic ReLU Replacement for HE-Friendly Inference

This paper proposes a decision-aware quadratic ReLU replacement method for Fully Homomorphic Encryption (FHE) inference that, by formulating the problem as a linear separation task in a lifted space, achieves calibration-set decision preservation without retraining while significantly accelerating inference speed compared to existing polynomial approximation techniques.

Original authors: Rui Li, Wenyuan Wu, Weijie Miao

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rui Li, Wenyuan Wu, Weijie Miao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Locked Box" Problem

Imagine you have a very smart AI (a neural network) that can tell you if an email is spam or not. You want to send your private email to a server to get this answer, but you don't trust the server with your data. So, you lock your email in a special "magic box" (called Fully Homomorphic Encryption or FHE).

The server can open the box, do math on the locked data, and give you a locked answer, all without ever seeing the actual email. This is great for privacy.

The Problem: The AI needs to make a decision like "Is this number positive or negative?" (a step called ReLU). In the real world, this is easy. But inside the "magic box," the server can only do simple addition and multiplication. It cannot easily do "if/then" decisions. To make the AI work inside the box, scientists usually replace the decision with a complex math curve (a high-degree polynomial).

The Old Way: Think of this like trying to draw a perfect circle using a ruler. You have to use a very long, complicated ruler (a high-degree polynomial) to get close enough to a circle. This takes a lot of time and effort (computing power) for the server.

The New Idea: "Decision-Aware" Replacement

The authors of this paper asked a different question: Do we need the curve to look exactly like the decision at every single point? Or do we just need the final answer to be the same?

The Analogy:
Imagine you are navigating a maze.

The Old Way: You try to trace the exact path of the maze walls with a pen. If you miss the wall by a tiny bit, you think you failed. You need a very precise pen (complex math).
The New Way: You only care about reaching the exit. If you take a slightly different path that still leads to the same exit, you are happy. You don't need a complex pen; a simple, short path (a low-degree quadratic curve) is enough, as long as it gets you to the right door.

The paper calls this "Decision-Aware." Instead of trying to perfectly mimic the AI's internal "thinking" (the activation), they only care that the final "Yes/No" or "Class A/Class B" decision stays the same for a specific set of test data (the calibration set).

The Solution: The "Quadratic" Shortcut

The authors found that a simple quadratic equation (a U-shaped curve, like $x^2$ ) is the "sweet spot."

It's simple enough for the "magic box" to handle quickly.
It's flexible enough to guide the AI to the correct final decision.

They developed a method to find the perfect settings (coefficients) for this U-shaped curve. They treat the problem like a game of geometry:

The Binary Case (Yes/No): They take all the "Yes" examples and all the "No" examples and turn them into points on a 2D map. If the "Yes" points and "No" points can be separated by a straight line with a little breathing room (a positive margin), they can mathematically prove that a simple U-shaped curve will work perfectly.
The Hard Cases: Sometimes the points are mixed up, and you can't draw a clean line. In this case, they use a "soft" version of the math (like a rubber band) that ignores a few messy outliers. This gives them a "good enough" curve that works for almost all cases.

The Results: Faster and Just as Smart

They tested this on real-world tasks (like recognizing images or classifying text) using the "magic box" (FHE).

Accuracy: Their method kept the AI's accuracy almost exactly the same as the original AI (and much better than the old "simple square" method).
Speed: Because their curve is so simple (just a U-shape), the server didn't have to do as many heavy calculations.
- It was 3.7 to 4.1 times faster at the specific step where the decision is made compared to the previous best method (Remez-7).
- The whole process from start to finish was 1.18 to 1.68 times faster.

Summary

Think of this paper as finding a shortcut through a forest.

Old Method: You try to walk exactly along the winding river (the complex math curve). It's precise but slow and tiring.
New Method: You look at where the river leads (the final decision) and cut a straight path through the trees using a simple curve. You arrive at the same destination, but you get there much faster and with less effort, all while keeping your map (data) hidden in a locked box.

The authors have also released a free software library called QUAD4FHE so others can use this shortcut.

Technical Summary: Decision-Aware Quadratic ReLU Replacement for HE-Friendly Inference

Problem Statement
Fully Homomorphic Encryption (FHE) enables privacy-preserving neural network inference by allowing computations on encrypted data without decryption. However, FHE natively supports only additions and multiplications, making nonlinear activation functions like ReLU ( $\max\{0, u\}$ ) computationally expensive. Existing FHE-only approaches typically replace ReLU with high-degree polynomials (e.g., Remez or Chebyshev approximations) fitted over empirical activation intervals. While these methods avoid comparisons, they often require high-degree polynomials to control approximation error, leading to increased multiplicative depth, rescaling operations, and latency. Furthermore, these methods optimize for local pointwise approximation fidelity rather than the global classification objective: preserving the final top-1 logit ordering.

Methodology
The authors propose a decision-aware framework that replaces ReLU with a shared low-degree quadratic polynomial ( $q(u) = \alpha u^2 + \beta u + \eta$ ) without retraining the model. The core insight is that for a trained single-hidden-layer ReLU Multi-Layer Perceptron (MLP) or an MLP head on frozen features, the final decision depends on the ordering of logits. Therefore, the replacement polynomial need not approximate ReLU pointwise; it only needs to preserve the relative ordering of the final scores on a declared calibration set.

The methodology proceeds in two phases:

Offline Coefficient Construction: Given a trained model and a calibration set, the authors formulate the search for coefficients $(\alpha, \beta, \eta)$ $(α, β, η)$ as a geometric feasibility problem.
- Binary Case: The problem is reduced to finding a positive-margin hyperplane separator between two lifted convex hulls in a 2D space defined by statistics $Q(x) = \sum a_j y_j(x)^2$ and $H(x) = \sum a_j y_j(x) + b$ . If the hulls are disjoint, exact calibration-lossless replacement is possible. The optimal coefficients are derived from the closest pair of points between the hulls.
- Multiclass Case: The condition becomes the strict feasibility of pairwise affine logit-margin inequalities.
- Relaxations: When exact separation fails (due to misclassified samples or small margins), the authors employ Reduced Convex Hulls (RCH) and Lagrangian-dual soft-margin relaxations. These techniques cap the influence of individual samples (via a parameter $\mu$ ) or introduce slack variables, converting the problem into convex quadratic programs (QPs) that yield approximately feasible coefficients with high empirical agreement.
Online Inference: The server evaluates the resulting polynomialized arithmetic circuit on encrypted inputs. The quadratic replacement requires only one ciphertext-ciphertext multiplication per activation, significantly reducing multiplicative depth compared to higher-degree alternatives.

Key Contributions

Decision-Aware Formulation: The paper shifts the objective from minimizing local activation error to maximizing calibration-set logit-ordering agreement. This allows the use of a degree-2 polynomial even if it is a poor pointwise approximation of ReLU, provided it preserves the final classification decisions.
Exact Finite-Sample Theory: For binary classifiers, the authors establish necessary and sufficient conditions for calibration-lossless replacement based on the positive-margin separability of lifted convex hulls. This provides a constructive algorithm with $O(n \log n)$ complexity for finding coefficients and a certificate for quantization tolerance.
Geometric Relaxations: For cases where exact separation is impossible, the paper introduces RCH and soft-margin relaxations that continuously extend the exact theory. These methods provide practical surrogates with explicit diagnostics (margins, slacks, agreement rates) rather than claiming exact preservation where it cannot be certified.
Implementation and Validation: The authors implemented the pipeline in the open-source QUAD4FHE library. They validated the approach on diverse datasets (tabular, vision, text) using both raw features and frozen representations (DINOv2, Qwen3).

Results

Accuracy: Under the CKKS scheme, the quadratic replacement matches the plaintext top-1 accuracy of the original ReLU model on multiple benchmarks (e.g., Otto, DINOv2/FGVC-Aircraft, Qwen3/MASSIVE). In many multiclass tasks, it outperforms or matches strong baselines like OLA and Precise Approximation, despite using a lower-degree polynomial.
Efficiency: The quadratic replacement runs 3.7–4.1× faster in the activation module and 1.18–1.68× faster end-to-end compared to Remez-7 (a high-degree baseline). This is achieved because the degree-2 circuit fits within a shallower multiplicative depth (depth 4 vs. depth 5 for Remez-7), allowing for a more efficient coefficient-modulus chain and reduced rescaling overhead.
Robustness: The method remains effective even when the calibration pool is small (as little as 1–5% of the dataset) and handles frozen feature extractors effectively.

Significance and Claims
The paper claims that by reframing ReLU replacement as a decision-preservation problem rather than a function approximation problem, it is possible to achieve high-accuracy FHE inference with minimal computational overhead. The significance lies in demonstrating that a degree-2 polynomial is sufficient for high-fidelity encrypted inference when chosen via a decision-aware geometric framework, thereby avoiding the latency penalties associated with higher-degree polynomials. The authors emphasize that their guarantees are scoped to the declared calibration set and do not provide distribution-free guarantees for unseen inputs, but the empirical results show strong generalization to test sets. The work provides a mathematically transparent path to optimizing the trade-off between accuracy and latency in FHE-only neural inference.