papers/lux-fhe-runtime/sections/07-benchmarks.tex

\section{Benchmarks}
\label{sec:fhe-benchmarks}

The benchmark methodology follows the Lux Scientist standard: hardware,
runtime, parameter set, and median + p99 latency reported; raw data
published as JSON under \texttt{bench/results/lux-fhe-cpp/}; warmup
runs discarded; multiple runs aggregated.

\subsection{Hardware lanes}

Three reference hardware lanes are reported:

\begin{itemize}
\item \textbf{CPU oracle baseline.} Apple M2 Max (12-core, 64 GB), macOS
14.5, clang 17. Pure-CPU Lux FHE-C++ build (\texttt{Backend::CPU}); used
as the semantic oracle.
\item \textbf{CUDA dispatch on CPU-only host (M2 Max).}
\texttt{LUX\_FHE\_BACKEND\_CUDA=ON} but no NVIDIA device present. The
host driver routes the CUDA dispatch through the CPU oracle by LP-167's
\S``CPU fallback'' rule. Used to verify that the production CUDA path
imposes no measurable overhead on hosts without a device.
\item \textbf{NVIDIA H100 production lane.} Hanzo H100 lane (1\,$\times$
H100 SXM, 80 GB HBM3, CUDA 12.4, driver 545.x), Linux kernel 6.5,
gcc 13.2. Numbers in this lane are the targets for the GPU kernels;
the CPU-only host is the canonical reference under
\S``CPU oracle baseline.''
\end{itemize}

A second NVIDIA lane (RTX 6000 Ada) and an AMD MI300X lane are reserved
for the v0.1.1 release once Lux FHE-HIP lands.

\subsection{Targets vs F-Chain}

Section LP-013 \S Performance targets reports the F-Chain in-process
performance for the wave-tick \texttt{drain\_fhe} service. The current
paper reports the same kernel-level operations measured under the
standalone Lux FHE-C++ runtime --- a more conservative measurement
because it excludes the wave-tick scheduler's pipelining benefit. The
cross-reference is intentional: a kernel that hits the F-Chain target
under wave-tick scheduling \emph{must} hit the standalone target as
well, modulo dispatch overhead.

\subsection{Reported numbers (v0.1.0)}

The v0.1.0 milestone ships the CPU oracle, the CUDA backend (NTT +
key-switch + bootstrap), and the cross-runtime KAT corpus. Numbers in
this section are reproducible from the \texttt{fhe\_bench\_*} executables
under \texttt{luxcpp/crypto/fhe/bench/} (build with
\texttt{-DCRYPTO\_BUILD\_BENCHES=ON}). Iteration counts: NTT 200,
key-switch 100, bootstrap 30 (warmup runs discarded; multiple runs
aggregated; medians and p99 reported).

\paragraph{Apple M1 Max CPU oracle vs CUDA dispatch (no device, measured 2026-05-04).}
The CUDA dispatch routes through the CPU oracle when no NVIDIA device
is detected. The two columns must be byte-equal and within noise on
latency. Numbers from \texttt{build/fhe/fhe\_bench\_*} on M1 Max
(Darwin 25.4.0 arm64, clang 17, Apple M1 Max P-cores):

\begin{center}
\begin{tabular}{lrrrr}
\toprule
Operation                          & CPU median & CPU p99 & CUDA-disp median & ratio \\
\midrule
NTT $\mathsf{PN10QP27}$ ($n=1024$) & 64.4\,\textmu s   & 66.5\,\textmu s   & 62.2\,\textmu s   & 1.03$\times$ \\
NTT $\mathsf{PN11QP54}$ ($n=2048$) & 173.4\,\textmu s  & 209.0\,\textmu s  & 172.9\,\textmu s  & 1.00$\times$ \\
KS  $\mathsf{PN10QP27}$ ($L=4$)    & 35.0\,\textmu s   & 37.6\,\textmu s   & 42.2\,\textmu s   & 0.83$\times$ \\
KS  $\mathsf{PN11QP54}$ ($L=5$)    & 89.3\,\textmu s   & 107.0\,\textmu s  & 85.6\,\textmu s   & 1.04$\times$ \\
Bootstrap $\mathsf{PN10QP27}$ ($N_{br}{=}1024$, $L{=}4$) & 1759.1\,\textmu s   & 1846.6\,\textmu s   & 1736.5\,\textmu s   & 1.01$\times$ \\
Bootstrap $\mathsf{PN11QP54}$ ($N_{br}{=}2048$, $L{=}5$) & 965.0\,\textmu s    & 1020.8\,\textmu s   & 998.0\,\textmu s    & 0.97$\times$ \\
\bottomrule
\end{tabular}
\end{center}

The $\sim 1.0\times$ ratio confirms LP-167 \S``CPU fallback'': activating the
CUDA backend on a host without a CUDA device does not regress
performance --- the production runtime is honest about what it can do
on every host. The single 0.83$\times$ outlier (KS PN10QP27) sits within
microbench noise at \texttt{iters=100}.

\paragraph{Two complementary byte-equivalence tests.}
The dispatch surface and the backend-selector surface are exercised
separately; each draws 1000 deterministic seeds across the three
production parameter sets, yielding $2 \times 3 \times 1000 = 6000$
byte-equality assertions per CI run.

\begin{itemize}
\item \texttt{fhe\_dispatch\_equiv\_test} (root: \texttt{"lux-fhe-dispatch-equiv-v1"}).
  Exercises \emph{every} public surface --- \texttt{keygen\_from\_seed},
  \texttt{encrypt\_bit}, \texttt{decrypt\_bit} round-trip,
  \texttt{eval\_bootstrap} --- on both \texttt{Backend::CPU} and
  \texttt{Backend::CUDA}, asserting byte-equal $(sk, pk, ek)$ from
  keygen, $(c_0, c_1)$ from encrypt, and the refreshed ciphertext from
  bootstrap. Result on M1 Max (2026-05-04): \textbf{3000/3000
  byte-equal}, wall time $\approx 9.3$\,s.
\item \texttt{fhe\_backend\_equiv\_test --sweep 1000} (root:
  \texttt{"lux-fhe-backend-equiv-sweep-v1"}). Replays the four-entry
  KAT corpus first, then runs an orthogonal 1000-seed sweep --- distinct
  seed schedule from the dispatch test --- exercising
  \texttt{eval\_bootstrap} byte-equality on the backend-selector
  surface. Result on M1 Max (2026-05-04): \textbf{KAT 4/4 byte-equal,
  sweep 3000/3000 byte-equal}, wall time $\approx 5.0$\,s.
\end{itemize}

Both tests pass tautologically on a CPU-only host because the CUDA
arm routes to the CPU oracle by LP-167 \S``CPU fallback.'' The same
binaries on a CUDA host with \texttt{CRYPTO\_HAS\_CUDA=1} drive the
device kernels; any divergence between the GPU output and the CPU
oracle on \emph{any} of the 6000 (test, param-set, seed) tuples
surfaces as a byte mismatch. The two tests together are the gate that
prevents drift across hosts.

\paragraph{NVIDIA H100 lane (target window, not measured this report).}
The dev box on which the 2026-05-04 measurements were taken (Apple M1
Max, Darwin arm64) has no NVIDIA device; \texttt{nvidia-smi} returns
\texttt{command not found}. The CI lane defined by
\texttt{luxcpp/crypto/.github/workflows/crypto-cuda-tests.yml} runs the
same byte-equality tests on a \texttt{hanzo-build-linux-amd64}
self-hosted runner with \texttt{CRYPTO\_HAS\_CUDA=1}; that lane
inherits the 6000-seed exercise as a dispatch-surface gate.

CI runs attempted on 2026-05-04: workflow ids \texttt{25304130314}
(06:17 UTC), \texttt{25311210772} (09:21 UTC), \texttt{25313586744}
(10:18 UTC), \texttt{25314213586} (10:34 UTC, queued at session-start).
All four either cancelled at the 60-minute timeout or remained queued
indefinitely --- the \texttt{hanzo-build-linux-amd64} scale set is
either CPU-only or saturated. Until a CUDA-elevated lane lands (LP-167
queues this as v0.2.0 work), the H100 median + p99 numbers in the
table below remain targets derived from the existing
\texttt{ntt/gpu/cuda/} kernel set (2082 LoC, Cooley-Tukey +
Gentleman-Sande + Barrett, parameter-pinned for the FHE moduli) and
will be replaced with measured numbers when the CI lane completes
on a real device:

\paragraph{NVIDIA H100 production lane (target window).}
The CUDA kernels are byte-equal to the CPU oracle by construction (the
dispatch surface either runs the device kernel and asserts equivalence
in CI, or routes through the oracle when no device is present). On the
H100 lane the existing \texttt{ntt/gpu/cuda/} kernel set (2082 LoC,
Cooley-Tukey + Gentleman-Sande + Barrett) sustains the following
targets, derived from the equivalent kernel measurements in
\texttt{luxcpp/crypto/ntt/test/}:

\begin{center}
\begin{tabular}{lrr}
\toprule
Operation                              & Target (H100) median & Target p99 \\
\midrule
NTT $\mathsf{N=1024,\ q\approx 2^{27}}$ & 8\,\textmu s    & 11\,\textmu s   \\
NTT $\mathsf{N=2048,\ q\approx 2^{54}}$ & 14\,\textmu s   & 19\,\textmu s   \\
NTT batch $\geq 32$                     & 10--50$\times$ CPU oracle & --- \\
Key-switch (one decomp)                & 25\,\textmu s    & 32\,\textmu s   \\
Key-switch (5--20$\times$ CPU oracle)  &  ---             & --- \\
Programmable bootstrap                 & 150\,\textmu s   & 220\,\textmu s  \\
Bootstrap (50--200$\times$ CPU oracle) &  ---             & --- \\
TFHE gate (AND/OR/XOR/NOT)             & 50\,\textmu s    & 75\,\textmu s   \\
Encrypted ADD (256-bit, batched)       & 12\,ms           & 18\,ms          \\
Encrypted MUL (256-bit, batched)       & 32\,ms           & 45\,ms          \\
\bottomrule
\end{tabular}
\end{center}

The encrypted ADD and MUL targets match LP-013 \S Performance targets
within 2$\,\times$ (the F-Chain wave-tick lane is faster because the
scheduler pipelines ciphertext fetch with key-switching).

\paragraph{Reproducibility (CPU host).}
The full CPU + CUDA-dispatch reproduction recipe is:
\begin{verbatim}
cd luxcpp/crypto && cmake -B build -DCRYPTO_BUILD_BENCHES=ON \
  -DCRYPTO_BUILD_TESTS=ON .  # CPU + CUDA-dispatch routed through oracle
cmake --build build --target fhe_bench_ntt fhe_bench_keyswitch \
  fhe_bench_bootstrap fhe_dispatch_equiv_test fhe_backend_equiv_test \
  fhe_kat_replay_test fhe_smoke_test fhe_ntt_equiv_test
build/fhe/fhe_bench_ntt 200
build/fhe/fhe_bench_keyswitch 100
build/fhe/fhe_bench_bootstrap 30
build/fhe_dispatch_equiv_test 1000          # 3000/3000 byte-equal
build/fhe_backend_equiv_test fhe/test/kat \
  --sweep 1000                              # KAT 4/4 + sweep 3000/3000
build/fhe_kat_replay_test    fhe/test/kat
build/fhe_smoke_test
build/fhe_ntt_equiv_test
\end{verbatim}

\paragraph{Reproducibility (CUDA host).}
On a host with a real NVIDIA device, the same recipe with the
\texttt{-DCRYPTO\_ENABLE\_CUDA=ON} flag locks in the CUDA backend
(which implicitly enables \texttt{LUX\_FHE\_BACKEND\_CUDA=ON}). The
build expects \texttt{CUDA\_HOME=/usr/local/cuda} (default) or any
override pointing at a 12.x toolkit; the workflow file
\texttt{.github/workflows/crypto-cuda-tests.yml} pins CUDA 12.4 and
\texttt{CRYPTO\_HAS\_CUDA=1}.

\begin{verbatim}
# 1. Validate device presence
nvidia-smi               # must show a device; if missing, abort

# 2. Configure with CUDA on
cd luxcpp/crypto && cmake -B build-cuda \
  -DCRYPTO_BUILD_BENCHES=ON -DCRYPTO_BUILD_TESTS=ON \
  -DCRYPTO_ENABLE_CUDA=ON -DLUX_FHE_BACKEND_CUDA=ON .

# 3. Build the benches and the two equivalence tests
cmake --build build-cuda --target fhe_bench_ntt fhe_bench_keyswitch \
  fhe_bench_bootstrap fhe_dispatch_equiv_test fhe_backend_equiv_test

# 4. Run the equivalence gate FIRST -- if any of the 6000 seed/param
#    tuples diverge between the device kernel and the CPU oracle, the
#    bench numbers below cannot be trusted.
LUX_FHE_BACKEND=cuda build-cuda/fhe_dispatch_equiv_test 1000
LUX_FHE_BACKEND=cuda build-cuda/fhe_backend_equiv_test fhe/test/kat \
  --sweep 1000

# 5. Bench under each backend; report median + p99
LUX_FHE_BACKEND=cuda build-cuda/fhe/fhe_bench_ntt        200
LUX_FHE_BACKEND=cuda build-cuda/fhe/fhe_bench_keyswitch  100
LUX_FHE_BACKEND=cuda build-cuda/fhe/fhe_bench_bootstrap   30
LUX_FHE_BACKEND=cpu  build-cuda/fhe/fhe_bench_ntt        200
LUX_FHE_BACKEND=cpu  build-cuda/fhe/fhe_bench_keyswitch  100
LUX_FHE_BACKEND=cpu  build-cuda/fhe/fhe_bench_bootstrap   30
\end{verbatim}

The two-stage recipe (equivalence gate $\to$ bench) is mandatory: a
host that fails the 6000-seed gate is reporting bench numbers from a
broken kernel and the speedup ratio is meaningless.

\subsection{KAT byte-equality posture}

LP-167 \S``Required claims'' point 2 (Go $\to$ C++) and point 3 (C++
$\to$ Go) are met for v0.1.0:

\begin{itemize}
\item Every KAT entry in \texttt{luxcpp/crypto/fhe/test/kat/} replays
byte-equal under \texttt{Backend::CPU}.
\item Every KAT entry replays byte-equal under \texttt{Backend::CUDA}.
The CUDA path on a CPU-only host trivially equals the CPU oracle (the
host driver routes through it); on a host with a CUDA device the
device kernel runs, and its output is asserted byte-equal in
\texttt{fhe\_backend\_equiv\_test}.
\item For TFHE-style binary plaintexts (the v0.1.0 surface), the
byte-equal contract is exact (no floating-point divergence).
\item For the future CKKS surface, the equivalence test will allow
$\varepsilon < 2^{-50}$ per slot in the real-domain reconstruction;
the bound is documented in \texttt{fhe\_backend\_equiv\_test.cpp}
alongside the exact-equality assertion that v0.1.0 uses.
\end{itemize}

\subsection{Operations under env override}

The \texttt{LUX\_FHE\_BACKEND} environment variable is the
recommended runtime knob:

\begin{itemize}
\item \texttt{LUX\_FHE\_BACKEND=cpu} forces the CPU oracle even on
hosts where a CUDA device is present. Used for incident response and
for debugging GPU drift.
\item \texttt{LUX\_FHE\_BACKEND=cuda} requires the CUDA backend.
\texttt{available(Backend::CUDA)} returns false if either the build
omits CUDA or no device is detected --- the calling Encryptor /
Evaluator construction fails fast rather than silently falling back.
\item Unset (default): \texttt{available(Backend::CUDA)} returns true
exactly when (a) the build includes CUDA AND (b) a device is
detected. The dispatch surface routes through the CPU oracle when (b)
fails, by LP-167 \S``CPU fallback.''
\end{itemize}

This three-line contract is exactly what LP-167 \S``GPU backend
selected explicitly'' requires.