betaFeedback

WorksComputer Science

Holo-NN: Holographic Nearest Neighbor Search via Compressive Sensing

Abstract

In the age of AI, privacy-preserving approximate nearest neighbor (ANN) search over high-dimensional embeddings has emerged as a critical yet frustratingly challenging domain, dominated by tradeoffs between speed, privacy, and accuracy. Traditional tree and graph-based indexing structures (e.g., HNSW, ScaNN) rely fundamentally on non-linear operations that are computationally intractable under Fully Homomorphic Encryption (FHE) or blind server-side constraints. In this paper, we introduce Holo-NN (Holographic Nearest Neighbor Search), an algebraic framework that replaces data-dependent branching with a single linear projection. Our key observation is that while distances across a database are dense, neighborhood membership is inherently sparse: only a handful of points ever lie close to a query. By pairing locality-preserving feature transforms with Compressive Sensing, Holo-NN folds the entire database offline into a compact holographic sensing matrix. At query time, encrypted search reduces to a single, non-interactive matrix-vector multiplication—requiring no FHE bootstrapping, no multi-round interaction, and no client-side index state. This turns private retrieval into an embarrassingly parallel, accuracy-tunable computation that runs out of the box on both CPUs and GPUs, scaling efficiently to production databases. We offer a comparison against other state-of-the-art Private ANN algorithms to help situate the method in the broader context of production-grade private retrieval.

Introduction

Motivation & Private Retrieval Landscape

Published in 1750, Cramer’s rule [19] established an exceptionally inefficient and computationally intensive method for solving systems of linear equations based on an exhaustive calculation of determinants. And yet, despite its inefficiency, it introduced an embarrassingly parallel mathematical primitive that modern high-throughput computational hardware can execute with extreme efficiency.

A similar paradigm shift governs modern privacy-preserving computation. The constraints imposed by fully end-to-end secure computation—such as Fully Homomorphic Encryption (FHE) and Private Information Retrieval (PIR)—fundamentally alter algorithmic tradeoffs, introducing choices that would be sub-optimal in most other settings. In unconstrained plaintext environments, Approximate Nearest Neighbor (ANN) search is dominated by hierarchical graphs (e.g., HNSW [35]) and quantized inverted files (e.g., ScaNN [28]), which exploit non-linear geometric branching to achieve sublinear query times (O(log⁡N)O(\log N)) for hierarchical graphs such as HNSW. In contrast, in private, blind-server settings, data-dependent branching leaks memory access patterns, rendering graph traversals either insecure, reliant on non-colluding multi-server assumptions (e.g., PRECO [40]), or subject to heavy multi-round cryptographic overheads across garbled circuits, oblivious RAM, or sublinear PIR (e.g., SANNS [14], Tiptoe [29], Pacmann [48], Panther [32], Compass [49]). Under strict single-server privacy constraints, non-interactive systems are forced into O(N)O(N) linear scan of the entire database. When server compute and memory capacity are abundant relative to communication bandwidth and cryptographic circuit depth, algorithm design shifts toward strictly linear, non-interactive mathematical formulations.

Compressed Sensing

Beginning with Claerbout and Muir in 1973 [18], it was discovered that seismological reflection data could be algorithmically improved, even with apparent “violations” of the Nyquist-Shannon sampling criterion [41]. Formalized later into the robust field of Compressive Sensing, it was shown that the supposed violation was backed by the inherent sparsity of the underlying signals [22, 10]. Specifically, for a signal that admits a kk-sparse representation where k≪Nk \ll N, significantly fewer measurements than NN are required for high-fidelity reconstruction. Intuitively, reconstruction is possible because one is attempting to solve for kk non-zero elements in an NN-dimensional space, which can be solved efficiently via convex ℓ1\ell_1-optimization algorithms. Formally, given an underdetermined system of linear measurements y=As∈RMy = As \in\mathbb{R}^{M} with M≪NM \ll N, an unknown kk-sparse signal s∈RNs \in\mathbb{R}^{N} can be recovered by solving the convex program min⁡s∥s∥1\min_s \lVert s\rVert_1 subject to As=yAs = y (or ∥As−y∥2≤ϵ\lVert As-y\rVert_2 \le\epsilon under noise), provided M=O(klog⁡(N/k))M = O(k \log(N/k)).

Compressive Sensing has since enjoyed a long series of successes in Signal Processing [12, 5, 34], though has become more of a background player in modern systems design, and it is rare to see application outside of practical acquisition systems like single-pixel optical imaging [26], Astronomy [7], WiFi or wireless sensor networks [4], to name a few.

In classical Compressive Sensing, a signal x∈RNx \in\mathbb{R}^{N} (e.g., an image in JPEG [44]) admits a kk-sparse representation s∈RNs \in\mathbb{R}^{N} under a sparsifying basis or dictionary F∈RN×NF \in\mathbb{R}^{N \times N} such that x=Fsx = Fs. Instead of acquiring all NN ambient samples and compressing them post hoc, compressive sensing directly acquires M≪NM \ll N non-adaptive linear measurements via a pseudorandom measurement matrix A∈RM×NA \in\mathbb{R}^{M \times N}:

y=Ax=AFs(1)y = Ax = AFs \tag*{(1)}

The sparse coefficient vector ss is then reconstructed from yy by applying convex ℓ1\ell_1-regularized recovery algorithms [42, 6, 43, 21, 15], after which the original signal x=Fsx = Fs can be synthesized if needed.

In our nearest-neighbor setting (§ 1.3), the paradigm is even more direct: the sparse vector s∈RNs \in\mathbb{R}^{N} is itself the primary object of interest. Specifically, ss is the database affinity vector whose coordinates indicate the nearest neighbors of a query. Consequently, recovering ss directly from compressed measurements y=Asy = As immediately reveals the nearest-neighbor candidates (and their approximate distances) without requiring secondary reconstruction of an underlying signal xx. Because AA is pseudorandom and the database features are known a priori, the server’s linear operator can be precomputed offline, leaving only the compact vector y∈RMy \in\mathbb{R}^{M} to be transmitted to the client.

Nearest Neighbor Search as Sparse Signal Recovery

Consider a database T={t1,t2,…,tN}⊂RDT = \{t_1, t_2, \ldots, t_N\} \subset\mathbb{R}^{D} of NN vectors and a query point q∈RDq \in\mathbb{R}^{D}. For a nearest-neighbor query we are interested in the domain of distances from the query point to the points in the database, most specifically with the closest point. While the pairwise distance vector d∈RNd \in\mathbb{R}^{N} with entries di=dist⁡(q,ti)d_i = \operatorname{dist}(q,t_i) is completely dense, the corresponding kk-nearest neighbor indicator vector s∈{0,1}Ns \in\{0,1\}^{N} is, by construction, exactly kk-sparse. In particular, for 1-NN retrieval, ss is a 1-hot vector containing a single non-zero entry among NN coordinates.

From this perspective, nearest neighbor search can be cast as the recovery of a sparse affinity signal from compressed linear projections. In our formulation, the target signal s∈RNs \in\mathbb{R}^{N} is not merely an uninformative binary 0/1 indicator, but a continuous local affinity vector whose entries si=sim⁡(q,ti)s_i = \operatorname{sim}(q,t_i) concentrate their mass within the query’s local Voronoi neighborhood. This continuous mass is a key feature: its relative amplitudes preserve metric resolution and local ranking among adjacent points within the cell (as visualized in Figure 2), while decaying rapidly to zero across distant background points to enforce effective sparsity.

Holo-NN 2D Voronoi boundary reconstruction across a priori regimes

Figure 2. Holo-NN 2D Voronoi spatial boundary reconstruction across increasing measurement budgets (75.0%, 85.0%, 95.0%, 99.9% recall regimes).

Nearest Neighbor search reformulated as sparse signal recovery

Figure 1. Nearest Neighbor search reformulated as sparse signal recovery. (a) 2D point constellation with directed 1-NN graph. (b) Dense 10×1010 \times10 pairwise distance matrix DD. (c) Distance-valued 1-sparse NN affinity matrix AA, where each row contains exactly one non-zero entry.

The server compresses this affinity field into M≪NM \ll N linear measurements y=As∈RMy = As \in\mathbb{R}^{M} via a pseudorandom measurement matrix A∈RM×NA \in\mathbb{R}^{M \times N}. The core challenge is designing feature embeddings F\mathcal{F} and G\mathcal{G} that guarantee that distances are meaningful, but that decay quickly enough such that ss is sufficiently sparse for stable Compressive Sensing recovery, allowing the server to compute y=Asy = As without ever computing the full NN-dimensional vector ss.

While the raw query q∈RDq \in\mathbb{R}^{D} is generally dense, and can be performed via linear operations simply (e.g., d=uTu+vTv−2(uTv)d = u^{T}u + v^{T}v - 2(u^{T}v) for vectors uu and vv), modern machine learning provides effective non-linear feature embeddings that induce sparsity in an expanded feature space RB\mathbb{R}^{B} (B≫DB \gg D). Specifically, Kernel Methods (e.g., Random Fourier Features [36]) and Locality Sensitive Hashing (e.g., FlyHash [20]) allow sparsified continuous metric distances to be approximated via linear inner products:

sim⁡(q,ti)≈⟨G(ti),F(q)⟩\operatorname{sim}(q,t_i) \approx\langle\mathcal{G}(t_i), \mathcal{F}(q) \rangle

Where G\mathcal{G} and F\mathcal{F} are sparsity-enhancing feature transforms. By stacking the NN transformed database vectors into a database feature matrix G=G(T)∈RN×BG = \mathcal{G}(T) \in\mathbb{R}^{N \times B}, where row ii is G(ti)T\mathcal{G}(t_i)^{T}, the uncompressed affinity vector s∈RNs \in\mathbb{R}^{N} across the entire database is then simply the matrix-vector product:

s=GF(q)=[⟨G(t1),F(q)⟩⋮⟨G(tN),F(q)⟩]∈RN(2)s = G\mathcal{F}(q) = \begin{bmatrix} \langle\mathcal{G}(t_1), \mathcal{F}(q) \rangle\\ \vdots\\ \langle\mathcal{G}(t_N), \mathcal{F}(q) \rangle \end{bmatrix} \in\mathbb{R}^{N} \tag*{(2)}

By pre-multiplying this database feature matrix by a pseudorandom measurement matrix A∈RM×NA \in\mathbb{R}^{M \times N}, we construct the Holographic Sensing Matrix:

H:=AG∈RM×B(3)H := AG \in\mathbb{R}^{M \times B} \tag*{(3)}

It’s useful to pause and note the connection to Holography and physical intuition behind it. Specifically for an isolated vector pair ⟨G(ti),F(q)⟩\langle\mathcal{G}(t_i), \mathcal{F}(q) \rangle, a priori, the computation shares no information with any neighbors and therefore the sis_i would need to be exhaustively calculated for a full comparison. (This is the primary mechanism behind the proof that any sorting algorithm’s complexity floor is O(Nlog⁡N)O(N \log N)). In Holography, however, information in one basis is “smeared out” across a complementary basis (e.g., the Fourier Transform) ensuring that every sample contains fractional information about every point in the conjugate basis. Here HH plays this role, dispersing distances across multiple measurements that, collectively and in far fewer number than NN, can infer the signal of interest.

The linear framing cleanly separates the problem into an offline precomputation and an online linear query evaluation:

y=HF(q)=(AG)F(q)=A(GF(q))=As∈RM(4)y = H\mathcal{F}(q) = (AG)\mathcal{F}(q) = A(G\mathcal{F}(q)) = As \in\mathbb{R}^{M} \tag*{(4)}

Here, HH is computed once offline and stored permanently. Given a query F(q)\mathcal{F}(q), the evaluator simply computes the linear product y=HF(q)y = H\mathcal{F}(q), producing the compressed measurements y∈RMy \in\mathbb{R}^{M} without ever materializing the uncompressed NN-dimensional vector ss. The querier, knowing only the pseudorandom matrix AA, can then recover the sparse affinity vector s^\hat{s} directly from y=Asy = As via standard convex recovery algorithms (discussed below) in a fully local environment, without ever needing to know or download the holographic database matrix HH.

Moreover, because of the lossy nature of the initial transform, we can, with judicious design of the matrix AA, precisely control the accuracy of the final output and more importantly, allow for an algorithmically tunable tradeoff between accuracy and cost.

By synthesizing Compressive Sensing with non-linear feature embeddings, this forms the basis of Holo-NN, a strictly linear approximate nearest neighbor retrieval framework designed for regimes where server storage and parallel compute are inexpensive relative to network bandwidth and client storage, and both query privacy and index protection are paramount.

Summary of Contributions

  1. Holographic Retrieval Formulation: We reformulate ANN search as a single-round-trip (1-RTT), non-interactive linear Compressive Sensing problem (y=HF(q)y = H\mathcal{F}(q)) utilizing an offline precomputed holographic matrix H=AG(T)∈RM×BH = AG(T) \in\mathbb{R}^{M \times B}.

  1. Asymmetric Neural Hashing & Geometric Duality: We characterize the manifold duality governing sparse feature lifting—showing why continuous Random Fourier Features sparsify spatial Euclidean manifolds while discrete hyperplane competition is required on high-dimensional semantic hyperspheres—and introduce Asymmetric FlyHash (kq>kdbk_q > k_{db}) to eliminate double-quantization dropouts at zero encrypted wire overhead (§ 4 and § 5).

  1. Multi-Backend Encrypted Implementation & SOTA Comparison: We implement Holo-NN across four complementary cryptographic backends—stateless exact-integer LinPIR (BFV) [31] on CPU (3.29 s across 4 cores or 4.39 s single-threaded on Wikipedia-500k, and 3.1–8.0 s of server compute across 6 cores on SIFT-1M, with zero server keys), depth-1 mod-switched OpenFHE CKKS [1] on CPU (1.60 MB wire), Phantom CUDA CKKS [45] on a single NVIDIA RTX 3090 GPU (1.68 s end-to-end / 1.54 s server on Wikipedia-500k, and 9.5–29.7 s on SIFT-1M), and 32-bit RNS HEIR/Cheddar CUDA CKKS [3, 17] on a single RTX 3090 GPU (0.79 MB wire in 0.134 s end-to-end / 50.5 ms server on Wikipedia-500k, and 2.10–5.37 MB wire in 0.26–0.82 s on SIFT-1M)—and benchmark against SANNS [14], PRECO [40], Tiptoe [29], Pacmann [48], Panther [32], Compass [49], and Onyx [37] across all published recall conventions (2.10–11.13 MB CKKS wire on SIFT-1M in 1 RTT, 8.3×–44.2× below Panther’s 92.9 MB, 159×–843× below SANNS’s 1.77 GB, and below Compass’s 12.2 MB over 8 RTTs).

Background & Problem Formulation

Threat Model & Security Setting

We consider a client-server architecture where an untrusted server SS hosts a large-scale database T={t1,t2,…,tN}⊂RDT = \{t_1,t_2,\ldots,t_N\} \subset\mathbb{R}^D of NN high-dimensional feature vectors, and a client holds a confidential query vector q∈RDq \in\mathbb{R}^D.

The objective is to retrieve the approximate nearest neighbor q∗=arg⁡min⁡ti∈Tdist⁡(q,ti)q^* = \arg\min_{t_i \in T} \operatorname{dist}(q,t_i) under standard metric spaces—specifically Euclidean distance ∥q−ti∥2\lVert q-t_i\rVert_2 (e.g., via RFF) or angular cosine similarity ⟨q,ti⟩∥q∥2∥ti∥2\frac{\langle q,t_i\rangle}{\lVert q\rVert_2\lVert t_i\rVert_2} (e.g., via FlyHash)—subject to basic privacy constraints:

  1. Query & Access-Pattern Privacy: Under standard IND-CPA Ring-LWE encryption, the server SS learns nothing about the client’s query qq. Crucially, unlike graph- or tree-based private search that leaks data-dependent branching paths, the server’s execution trace (y=HF(q)y = H\mathcal{F}(q)) is strictly data-oblivious: it touches every measurement channel uniformly in a single linear pass, and hence the holographic naming, eliminating memory access-pattern leakage.

  1. Index Protection (Bounded Single-Query Leakage): The client never downloads the raw database TT or the holographic index HH. For an honest-but-curious client issuing a query qq, the single MM-dimensional response y=AGF(q)∈RMy = A\mathcal{G}\mathcal{F}(q) \in\mathbb{R}^M (M≪NM \ll N) is an underdetermined linear projection with an (N−M)(N-M)-dimensional null space in RN\mathbb{R}^N, enabling sparse recovery of the K∗≪NK^* \ll N local Voronoi neighbors without transmitting raw vectors TT. Defending against an adaptive malicious client that issues O(B)O(B) chosen basis queries to reconstruct HH (or inspects ciphertext error terms) is orthogonal to our core primitive and requires standard query rate-limiting, noise flooding for circuit privacy, and zero-knowledge proofs of query well-formedness.

  1. Operational Model: We target deployment settings where server-side storage and high-throughput parallel compute are abundant, but client storage and network bandwidth across wide area networks (WAN) and multi-round cryptographic communication overheads are the dominant system bottlenecks.

Compressive Sensing & Restricted Isometry Property

Compressive Sensing [22, 10, 27] enables the stable, high probability, reconstruction of an NN-dimensional sparse signal

s∈RN(∣support⁡(s)∣≤k≪N)(5)s \in\mathbb{R}^N \qquad(|\operatorname{support}(s)| \le k \ll N) \tag*{(5)}

from an underdetermined measurement vector y∈RMy \in\mathbb{R}^M with M≪NM \ll N and support the number of non-zero entries:

y=As(6)y = As \tag*{(6)}

where A∈RM×NA \in\mathbb{R}^{M \times N} is a measurement operator satisfying the Restricted Isometry Property (RIP) [9, 11] of order kk. Specifically, there exists an isometry constant δk∈(0,1)\delta_k \in(0,1) such that for all kk-sparse vectors ss:

(1−δk)∥s∥22≤∥As∥22≤(1+δk)∥s∥22(7)(1-\delta_k)\lVert s\rVert_2^2 \le\lVert As\rVert_2^2 \le(1+\delta_k)\lVert s\rVert_2^2 \tag*{(7)}

In practice, AA is drawn from appropriately chosen random ensembles, most commonly:

A∈{−1,+1}M×N(Bernoulli)(8)A \in\{-1,+1\}^{M \times N} \qquad\text{(Bernoulli)} \tag*{(8)}
A∼N(0,1M)M×N(Gaussian)(9)A \sim\mathcal{N}\left(0,\frac{1}{M}\right)^{M \times N} \qquad\text{(Gaussian)} \tag*{(9)}

Though, given that Bernoulli amounts to random sums and negations of existing column entries, this distribution is typically the most efficient choice.

Because AA is pseudorandom, any entry (i,j)(i,j) or column can be evaluated on the fly in O(1)O(1) time by both client and server using a Pseudorandom Function (PRF) Fk(i,j)F_k(i,j) keyed by a compact shared seed kk (e.g., 128-bit AES-CTR), eliminating any requirement to transmit or materialize AA in memory or GPU VRAM.

Kernel Lifting & Distance Approximations

In metric nearest neighbor search, non-linear geometric distances (L2L_2 Euclidean distance or cosine similarity) can be directly evaluated via linear operations in the raw feature space RD\mathbb{R}^D (uTu+vTv−2uTvu^T u + v^T v - 2u^T v), but they are typically dense in NN. To bridge this gap, feature mapping functions F,G:RD→RB\mathcal{F},\mathcal{G} : \mathbb{R}^D \to\mathbb{R}^B lift continuous vectors into an expanded BB-dimensional space (B≫DB \gg D) where a localized similarity kernel sim⁡(q,ti)\operatorname{sim}(q,t_i)—defined as a positive, monotonically decreasing function of metric distance dist⁡(q,ti)\operatorname{dist}(q,t_i) that vanishes outside a local neighborhood—is preserved as a linear inner product:

sim⁡(q,ti)≈⟨F(q),G(ti)⟩(10)\operatorname{sim}(q,t_i) \approx\langle\mathcal{F}(q),\mathcal{G}(t_i)\rangle \tag*{(10)}

While many kernel feature mappings exist, two are of particular use for our purposes:

  1. Gaussian Radial Basis Function via Random Fourier Features: Approximating a radial distance function, Gaussian Radial Basis Function (RBF) [39] via Random Fourier Features (RFF) [36] allows L2L_2 minimization over a tunable radius without the need for an interactive rounding procedure. Via Bochner’s theorem [8], shift-invariant kernels such as the RBF K(x,y)=exp⁡(−γ∥x−y∥22)K(x,y) = \exp(-\gamma\lVert x-y\rVert_2^2) are approximated by

projecting vectors onto random Gaussian frequencies W∼N(0,2γI)W \sim\mathcal{N}(0,2\gamma I) to produce f(x)∈RBf(x) \in\mathbb{R}^{B}:

f(x)=1B/2[cos⁡(Wx)sin⁡(Wx)](11)f(x)=\frac{1}{\sqrt{B/2}} \begin{bmatrix} \cos(Wx)\\ \sin(Wx) \end{bmatrix} \tag*{(11)}

The RBF acts as a spatial bandpass filter: points within a Euclidean radius ∝1/γ\propto1/\sqrt{\gamma} produce positive inner products, while distant points decay exponentially toward zero, inducing physical sparsity.

  1. FlyHash (Biologically Inspired Sparse Hashing): Serving as an angular analog to the Euclidean RBF, FlyHash [20] has frequently [33, 38] been used to approximate cosine similarity across directional semantic embeddings. Inspired by the Drosophila olfactory circuit [13], continuous vectors are projected onto random sparse binary hyperplanes W∈{0,1}B×DW \in\{0,1\}^{B \times D} and can be sparsified via winner-take-all (kk-WTA) competitive inhibition to yield a binary code, as in traditional applications, or a sparse gated projection as in our work f(x)∈RBf(x) \in\mathbb{R}^{B} whose jj-th coordinate is:

f(x)j=[WTA⁡k(Wx)]j={(Wx)jif (Wx)j∈Top⁡-k(Wx)0otherwise(12)f(x)_j=[\operatorname{WTA}_k(Wx)]_j = \begin{cases} (Wx)_j & \text{if } (Wx)_j \in\operatorname{Top}\text{-}k(Wx)\\ 0 & \text{otherwise} \end{cases} \tag*{(12)}

Much like RBF creates localized hyperspheres in Euclidean space, FlyHash creates localized angular cones on the hypersphere, mapping angular proximity directly to the inner product overlap ⟨f(x),f(y)⟩\langle f(x),f(y)\rangle of sparse representations while remaining resilient to high-dimensional metric concentration.

Throughout the remainder of this paper, the query mapping F:RD→RBF:\mathbb{R}^{D}\to\mathbb{R}^{B} and database mapping G:RD→RBG:\mathbb{R}^{D}\to\mathbb{R}^{B} denote these localized feature liftings—instantiated via RFF for Euclidean metric manifolds or Asymmetric FlyHash (Section 4) for directional semantic embeddings.

The Holo-NN Retrieval Architecture

Feature Projections & Shared Feature Space (F, G)

Given database points ti∈Tt_i \in T and query qq, the client and server apply complementary localized feature mappings F,G:RD→RBF,G:\mathbb{R}^{D}\to\mathbb{R}^{B} (instantiated via RFF or Asymmetric FlyHash as detailed in Section 4). These mappings are constructed to satisfy two properties: (1) Metric Locality, preserving local neighborhood similarity ⟨G(ti),F(q)⟩≈sim⁡(q,ti)\langle G(t_i),F(q)\rangle\approx\operatorname{sim}(q,t_i), and (2) Zero-Mean Background Incoherence, where global mean-centering (G(ti)←G(ti)−μG(t_i)\leftarrow G(t_i)-\mu) ensures that background inner products vanish in expectation (E[⟨G(tj),F(q)⟩]=0\mathbb{E}[\langle G(t_j),F(q)\rangle]=0). Stacking the NN transformed database vectors produces the database embedding matrix:

G=G(T)=[G(t1)TG(t2)T⋮G(tN)T]∈RN×B(13)G=G(T)= \begin{bmatrix} G(t_1)^{T}\\ G(t_2)^{T}\\ \vdots\\ G(t_N)^{T} \end{bmatrix} \in\mathbb{R}^{N\times B} \tag*{(13)}

The uncompressed affinity vector s∈RNs \in\mathbb{R}^{N} between query qq and all NN database points is:

s=GF(q)=[⟨G(t1),F(q)⟩⋮⟨G(tN),F(q)⟩]∈RN(14)s=GF(q)= \begin{bmatrix} \langle G(t_1),F(q)\rangle\\ \vdots\\ \langle G(t_N),F(q)\rangle \end{bmatrix} \in\mathbb{R}^{N} \tag*{(14)}

Because FF and GG act as localized spatial or angular bandpass filters, ss is keffk_{\mathrm{eff}}-compressible (approximately sparse): its keffk_{\mathrm{eff}} largest positive components capture the local Voronoi neighborhood around qq, while the residual background tail decays rapidly below the universal soft-thresholding floor λ\lambda.

Offline Server Database Grating

Rather than storing or scanning G∈RN×BG \in\mathbb{R}^{N\times B} at query time, the server pre-multiplies the database feature matrix with the pseudorandom measurement matrix A∈RM×NA \in\mathbb{R}^{M\times N}:

H=AG=AG(T)∈RM×B(15)H=AG=A\mathcal{G}(T)\in\mathbb{R}^{M\times B} \tag*{(15)}

The resulting matrix HH is the Holographic Sensing Matrix. It compresses the NN-point database into MM linear measurement channels across the BB feature dimensions. This computation is executed strictly offline, once, during index construction and stored permanently on the server. Given the offline pre-computation of HH, the function of the server benefits from theoretical or empirical optimization on algorithm parameters and hash choice. Further, because this computation is embarrassingly parallel, it can be seamlessly partitioned and executed in batch or form the basis for hierarchical design as needed.

Non-Interactive Linear Query Evaluation (y = H F(q))

At query time, the client computes its BB-dimensional feature representation F(q)F(q) locally and transmits it to the server (either in sparse-plaintext for bandwidth-constrained ANN, or encrypted under a Linearly Homomorphic Encryption scheme as detailed in Section 6). The server then executes a single linear matrix-vector evaluation:

y=HF(q)∈RM(16)y=HF(q)\in\mathbb{R}^{M} \tag*{(16)}

By association:

y=HF(q)=(AG)F(q)=A(GF(q))=As(17)\begin{aligned} y&=HF(q)=(AG)F(q)\\ &=A(GF(q))=As \tag*{(17)} \end{aligned}

The server thus produces the exact Compressive Sensing measurement vector y∈RMy \in\mathbb{R}^{M} of the latent sparse similarity signal s∈RNs \in\mathbb{R}^{N}, without ever materializing or inspecting the full NN-dimensional vector ss. Crucially, because the server operator HH is strictly linear, cryptographic deployment does not require deep Fully Homomorphic Encryption or bootstrapping; any Linearly Homomorphic Encryption (LHE) or Ring-LWE SIMD scheme suffices to evaluate y=H⋅Enc⁡(F(q))y = H \cdot\operatorname{Enc}(\mathcal{F}(q)) directly over ciphertexts.

Client Enclave Sparse Recovery & Candidate Reranking

Upon receiving the MM-dimensional measurement vector yy, the client recovers the sparse similarity vector s^∈RN\hat{s} \in\mathbb{R}^{N} by solving the non-negative ℓ1\ell_1-regularized inverse problem (LASSO [42]):

s^=arg min⁡s≥0 12∥As−y∥22+λ∥s∥1(18)\hat{s} = \underset{s \ge0}{\operatorname{arg\,min}}\ \frac{1}{2}\lVert As-y\rVert_2^2 + \lambda\lVert s\rVert_1 \tag*{(18)}

The client solves this convex optimization problem locally (or within a secure enclave) using any popular sparse recovery algorithm, such as Orthogonal Matching Pursuit (OMP) [43], Iterative Shrinkage-Thresholding (ISTA) [21], or the GPU-accelerated Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) [6] as we do in this work:

u(k)=z(k)−1LAT(Az(k)−y)(19)u^{(k)} = z^{(k)} - \frac{1}{L} A^{T}\left(Az^{(k)}-y\right) \tag*{(19)}
s(k+1)=Sλ/L(u(k))=max⁡(0,u(k)−λL)(20)s^{(k+1)} = S_{\lambda/L}\left(u^{(k)}\right) = \max\left(0,u^{(k)}-\frac{\lambda}{L}\right) \tag*{(20)}
tk+1=1+1+4tk22(21)t_{k+1} = \frac{1+\sqrt{1+4t_k^2}}{2} \tag*{(21)}
z(k+1)=s(k+1)+tk−1tk+1(s(k+1)−s(k))(22)z^{(k+1)} = s^{(k+1)} + \frac{t_k-1}{t_{k+1}}\left(s^{(k+1)}-s^{(k)}\right) \tag*{(22)}

with initial conditions s(0)=z(1)=0s^{(0)} = z^{(1)} = 0, t1=1t_1 = 1, Bai-Yin spectral step size L=∥ATA∥22≈(1+Nblock/Mblock)2L = \lVert A^{T}A\rVert_2^2 \approx\left(1+\sqrt{N_{\mathrm{block}}/M_{\mathrm{block}}}\right)^2 [46], and Donoho-Johnstone universal threshold λ=1Mblock2Nblockln⁡Nblock/D\lambda= \frac{1}{M_{\mathrm{block}}}\sqrt{2N_{\mathrm{block}}\ln N_{\mathrm{block}}/D} [23].

Upon convergence, the client extracts the top K∗K^{*} coordinates with the highest recovered affinity scores:

Top-⁡K∗(s^)⊂{1,2,…,N}(23)\operatorname{Top\text{-}}K^{*}(\hat{s}) \subset\{1,2,\ldots,N\} \tag*{(23)}

When only candidate IDs are required (or when the client caches lightweight metadata locally), retrieval terminates here in a single round trip. When full record payloads or exact metric reranking over the K∗K^{*} candidates is required, the client issues a secondary Private Information Retrieval (Batch PIR, e.g., via HintlessPIR [31]) re-query for those K∗K^{*} indices and computes exact distances locally without revealing the candidate support to the server.

Offline Index Tuning & Data-Dependent Operating Curves

In practice, the dimensions MM (measurement count), BB (feature embedding width), and K∗K^{*} (candidate verification budget) establish an operational tradeoff between accuracy, communication bandwidth, and computation. While Compressive Sensing theory establishes that MM scales logarithmically with ambient dimension for a fixed sparsity level (M=O(keffln⁡(Nkeff))M = O(k_{\mathrm{eff}}\ln(\frac{N}{k_{\mathrm{eff}}}))) [24, 25], the effective sparsity keffk_{\mathrm{eff}} of the affinity vector s=G(T)F(q)s = \mathcal{G}(\mathcal{T})\mathcal{F}(q)—and the magnitude of background cross-talk across non-neighbors—is inherently data- and manifold-dependent, varying with intrinsic dimensionality, metric concentration, and kernel bandwidth.

Crucially, because the holographic grating H=AG(T)H = A\mathcal{G}(\mathcal{T}) is constructed offline on the server, with the full database T\mathcal{T} in hand, Holo-NN requires no brittle closed-form heuristics to guess MM or K∗K^{*} in the blind. Much like tuning graph degree or probe budgets (e.g., efSearch [35], nprobe [30, 28]) in traditional plaintext ANN indices, the index operator has ample offline compute during index construction to profile recall across a validation query split and select the exact (M,B,K∗)(M,B,K^{*}) operating point along the dataset’s empirical bandwidth–accuracy Pareto curve.

Asymmetric Neural Hashing & Geometric Duality

The Double-Quantization Pathology in Symmetric Sparse Coding

High-dimensional semantic vectors (such as word embeddings and neural sentence representations) reside on continuous manifolds where continuous kernel functions often suffer from high-density concentration. To create sparse anchor representations, neural hashing algorithms draw inspiration from biological olfactory circuits [20], projecting inputs from low-dimensional projection neurons into an expanded Kenyon cell layer (B≫DB \gg D) and applying winner-take-all (kk-WTA) competitive inhibition.

In conventional symmetric sparse coding, both the database points and the query vector are pruned to an identical top-kk active anchor budget (kdb=kq≪Bk_{\mathrm{db}} = k_q \ll B). However, symmetric hard sparsification induces a severe double-quantization pathology: if a salient anchor ranks just above the top-kk cutoff in a database vector but falls slightly below the cutoff in the query vector, their dot product vanishes completely. This sharp thresholding causes false-negative dropouts across high-dimensional semantic benchmarks.

To circumvent this limitation in compressed sensing environments, we apply an Asymmetric FlyHash (AFH), breaking the symmetry between database encoding and query representation. In this approach, the functions applied to query F\mathcal{F} and database G\mathcal{G} are different, with the latter being significantly sparser than the former:

  1. Database Grating (kdb≪Bk_{\mathrm{db}} \ll B): The server’s precomputed database feature representation G=G(T)∈RN×BG = \mathcal{G}(T) \in\mathbb{R}^{N \times B} maintains a strict, ultra-sparse support (kdb≪Bk_{\mathrm{db}} \ll B per row). This ensures that the offline holographic matrix H=AG∈RM×BH = AG \in\mathbb{R}^{M \times B} remains compact and computationally efficient.

  1. Query Aperture (kq>kdbk_q > k_{\mathrm{db}}): The client projects the query qq through a broader activation aperture (kq=αaperture⋅kdbk_q = \alpha_{\mathrm{aperture}} \cdot k_{\mathrm{db}} with αaperture>1\alpha_{\mathrm{aperture}} > 1).

Opening the query aperture is free in bandwidth terms across both plaintext and encrypted deployments. In plaintext, transmission communicates only the non-zero coordinates of F(q)\mathcal{F}(q), so cost grows with kqk_q from a negligible base. Under homomorphic encryption, the query is a dense SIMD ciphertext spanning all BB slots whose byte size depends only on BB and the RNS limb count and is therefore completely independent of kqk_q—transmitting only the active coordinates is not an option, since the support of F(q)\mathcal{F}(q) must remain hidden from the server. In both regimes, the broad query aperture allows all potentially relevant semantic dimensions while the server’s sharp database grating acts as a spatial filter, eliminating false-negative dropouts with no additional communication overhead.

Geometric Duality: Continuous Euclidean RFF vs. Discrete Hyperplane Competition

Empirical and theoretical investigations reveal idiosyncratic, data-dependent structures governing feature transform selection. That is, while arguments for a priori parameter selection can be made, the dominating influences on the parameter choices for a dataset come from the structure, distribution and density of the data manifold, in addition to its ambient dimension DD. MNIST-784 (D=784D = 784) falls squarely in the first regime while GloVe-25 (D=25D = 25) falls squarely in the second, as DD alone does not predict which transform applies.

  1. Spatially Structured Metric Manifolds (low intrinsic dimension): In Euclidean metric spaces with physical or spatial structure (e.g., 2D spatial seeds, MNIST-784 pixel spaces, and SIFT-128 image descriptors), pairwise Euclidean distances show meaningful local contrast. In this regime, Random Fourier Features (RFF) with Gaussian RBF kernels K(x,y)=exp⁡(−γ∥x−y∥2)K(x,y) = \exp(-\gamma\lVert x-y\rVert^2) create genuine physical sparsity because spatial volume scales as O(rD)O(r^D). Points outside the local kernel radius r>3/2γr > 3/\sqrt{2\gamma} decay exponentially toward zero, enabling high-fidelity metric nearest neighbor recovery (Figure 2 and Table 1).

DatasetMetric Space & TransformNNDDBBRegimeMMM/NM/NK∗K^*Rec@1Rec@K∗K^*Rec@50
SIFT-1MEuclidean RFF1,000,00012816,38475.0%380,10038.01%862.00%94.10%99.20%
85.0%445,20044.52%1167.60%98.00%99.80%
95.0%631,20063.12%1972.30%99.70%100.00%
99.9%1,294,900129.49%5082.10%100.00%100.00%
MNIST-784Pixel Manifold RFF60,0007848,19275.0%6,00010.00%3023.37%75.42%79.95%
85.0%9,00015.00%3032.22%86.02%90.54%
95.0%12,00020.00%4039.14%93.80%94.95%
99.9%16,00026.67%5046.46%97.79%97.79%
GloVe-25Angular FlyHash (AFH)1,183,5142565,53675.0%95,0008.03%50018.00%82.60%63.30%
85.0%130,00010.98%50020.60%89.00%70.20%
95.0%200,00016.90%50024.90%94.80%78.70%
99.9%300,00025.35%50026.60%97.50%84.30%
Last.fm-64Raw MIPS (no lifting)292,385656575.0%20,0006.84%506.60%57.60%57.60%
85.0%28,0009.58%508.90%71.10%71.10%
95.0%40,00013.68%5014.40%82.30%82.30%
99.9%60,00020.52%5022.30%93.30%93.30%

Table 1. Multi-Scale Benchmark Results across 4 Datasets and 4 Operating Tiers (MM, K∗K^*). Rec@k is 1-recall@k: the fraction of queries whose true nearest neighbor appears among the top kk candidates returned by FISTA.

  1. Unstructured Semantic Hyperspheres (intrinsic dimension ≈\approx ambient DD): On unconstrained hyperspherical manifolds, pairwise Euclidean distances concentrate sharply around 2\sqrt{2} as DD grows, since ∥x−y∥2=2−2⟨x,y⟩\lVert x-y\rVert^2 = 2 - 2\langle x,y\rangle and ⟨x,y⟩→0\langle x,y\rangle\to0 by measure concentration on the sphere. Continuous exponential kernels suffer from amplitude collapse, where the true neighbor similarity signal drops below the finite-sample RFF Monte Carlo noise floor O(1/B)O(1/\sqrt{B}).

In contrast, Asymmetric FlyHash partitions high-dimensional space via nearly orthogonal random hyperplanes. Discrete kk-WTA competition creates implicit Voronoi cells, preserving semantic locality without exponential amplitude attenuation and remaining robust to the curse of dimensionality. Moreover, because feature strength is preserved within each Voronoi cell, a local “in-cell Euclidean metric” breaks ties and further increases NN accuracy.

Algorithmic ANN Benchmark Evaluation

Benchmark Datasets & Experimental Setup

To validate the algorithmic accuracy and theoretical predictions of Holo-NN independently of cryptographic backends, we evaluate Holo-NN across four standard nearest-neighbor benchmark suites spanning Euclidean (L2L_2) and angular (cosine) metric spaces:

  1. SIFT-1M (N=1,000,000N = 1{,}000{,}000, D=128D = 128): The canonical computer vision benchmark evaluated under Euclidean (L2L_2) distance across the first Q=1,000Q = 1{,}000 of the 10,000 official test queries. Vectors are mean-centered, globally rescaled, and lifted via Random Fourier Features (B=16,384B = 16{,}384, γ=8.0\gamma= 8.0), mapping Euclidean proximity to real-valued inner products.

  1. MNIST-784 (N=60,000N = 60{,}000, D=784D = 784): Handwritten digit pixel vectors evaluated under Euclidean (L2L_2) distance across Q=10,000Q = 10{,}000 test queries, lifted via mean-centered Random Fourier Features (B=8,192B = 8{,}192, γ=2.0\gamma= 2.0).

  1. GloVe-25 (N=1,183,514N = 1{,}183{,}514, D=25D = 25): Web-crawl word embeddings evaluated under angular cosine similarity across Q=1,000Q = 1{,}000 test queries, lifted via Asymmetric FlyHash (B=65,536B = 65{,}536) to resolve angular crowding on the unit hypersphere.

  1. Last.fm-64 (N=292,385N = 292{,}385, D=65D = 65): Sparse user-music interaction preference vectors evaluated under maximum inner product (MIPS) across Q=1,000Q = 1{,}000 test queries. Because the inner product is already linear, we apply no feature lifting (F=G=id\mathcal{F} = \mathcal{G} = \mathrm{id}, B=D=65B = D = 65) and operate directly on the raw vectors. This dataset therefore has no sparsification mechanism, and serves as our boundary case.

All benchmarks are evaluated on an NVIDIA GeForce RTX 3090 GPU (24 GB VRAM) and an Intel Xeon W-2135 host (6 cores / 12 threads) across four representative operating points (75.0%, 85.0%, 95.0%, 99.9% nominal recall tiers). At each tier, (M,K∗)(M, K^{*}) represents the empirically profiled Pareto-optimal measurement budget and candidate cutoff along the dataset’s bandwidth–recall frontier. To prevent client-side FISTA from materializing a monolithic M×NM \times N sensing matrix (which would require 1.52 TB of float32 memory at N=106N = 10^{6}, M=380,100M = 380{,}100), million-vector corpora are partitioned into P=100P = 100 disjoint blocks of Nblock=10,000N_{\mathrm{block}} = 10{,}000 vectors (Mblock=M/PM_{\mathrm{block}} = M/P). Each block’s sensing matrix Ab∈RMblock×NblockA_b \in\mathbb{R}^{M_{\mathrm{block}}\times N_{\mathrm{block}}} is drawn from the normalized Bernoulli ensemble ±1/Mblock\pm1/\sqrt{M_{\mathrm{block}}} and generated on the fly from a shared 128-bit PRNG seed (≤152\le152 MB in GPU VRAM, fitting even on lightweight 4 GB client GPUs), enabling batched GPU FISTA across all PP blocks in <0.4< 0.4 s per query.

Multi-Scale Target Recall Benchmark Results

Table 1 illustrates how achieved recall tracks the sparsity induced by the feature transform across each data manifold. On spatially structured Euclidean manifolds (SIFT-1M and MNIST-784), Random Fourier Features concentrate affinity within a tight local radius, reaching 94.10%–100.00% on SIFT-1M and 75.42%–97.79% on MNIST-784 at 10.0%–26.7% sub-Nyquist compression (noting that pushing unclustered SIFT-1M to 100.0% crosses the Nyquist boundary M/N>100%M/N > 100\%, whereas practical encrypted deployments operate at M/N≤50%M/N \le50\% where 1-recall@10 already reaches 98.5%, as swept in Table 4). On the angular semantic hypersphere (GloVe-25), Asymmetric FlyHash resolves crowding to achieve 82.60%–97.50% at M/N=8.03%M/N = 8.03\%–25.35%. By contrast, Last.fm-64 (F=G=id\mathcal{F} = \mathcal{G} = \mathrm{id}, no feature lifting) provides no non-linear sparsification mechanism, causing background cross-talk to degrade recovery (57.60%–93.30%) and marking the boundary of the method’s applicability.

MMCheddar 32b WireCheddar GPUCKKS 64b WireLinPIR Wire1-r@11-r@1010-r@1010-r@50MRR@10
98,3002.10 MB0.26 s4.24 MB91.1 MB32.563.433.357.00.417
150,0003.01 MB0.42 s6.36 MB135.8 MB40.575.843.872.50.518
200,0003.80 MB0.54 s7.95 MB179.0 MB48.284.251.882.00.601
250,0004.59 MB0.67 s9.54 MB222.2 MB53.589.357.388.00.652
300,0005.37 MB0.82 s11.13 MB265.4 MB58.293.061.692.00.702
327,6005.77 MB0.86 s11.66 MB289.2 MB59.793.363.893.00.718
380,10016.68 MB1.00 s13.78 MB334.6 MB62.095.666.895.10.741
500,0008.65 MB1.30 s17.50 MB438.2 MB69.598.573.098.00.801

Table 4. Holo-NN on SIFT-1M (N=106N = 10^{6}, D=128D = 128, B=16,384B = 16,384), 1,000 official queries, 80 FISTA iterations. Cheddar 32b Wire (and RTX 3090 server GPU latency Cheddar GPU) uses two 256 KiB 32-bit RNS query ciphertexts plus ⌈M/8192⌉×128\lceil M/8192\rceil\times128 KiB single-limb responses; CKKS 64b Wire (OpenFHE/Phantom) is 1.05 MB query plus ⌈M/16384⌉×0.53\lceil M/16384\rceil\times0.53 MB responses; LinPIR Wire is 6.19 MB inline key+query upload plus ⌈M/4096⌉×3.54\lceil M/4096\rceil\times3.54 MB BFV responses (zero persistent server keys). The LASSO [42] does not distribute the coefficient across the group; it concentrates the mass on a single representative and shrinks the remainder toward zero [50]. The surviving representative is reliably a member of the true neighbor set—which is why 1-recall is high—while its near-duplicates are demoted in magnitude though not eliminated, which is why they reappear as the cutoff widens.

Encrypted Retrieval System Implementation & SOTA Comparison

Holo-NN is designed for blind cloud retrieval across four complementary Ring-LWE encrypted execution backends: (1) exact-integer BFV homomorphic matrix-vector evaluation via Google’s HintlessPIR / LinPIR engine [31], (2) depth-1 modulus-switched approximate homomorphic encryption on CPU via OpenFHE [1] under the Cheon-Kim-Kim-Song (CKKS) scheme [16] compiled through HEIR [3], (3) 64-bit RNS GPU-accelerated CKKS evaluation on a single NVIDIA GeForce RTX 3090 GPU (24 GB VRAM) via Phantom [45] with a fused 128-bit lazy-reduction BSGS inner-product kernel, and (4) 32-bit RNS double-hoisted GPU CKKS evaluation on a single RTX 3090 GPU (and NVIDIA H100) lowered via HEIR [3] to Cheddar [17].

The encrypted retrieval pipeline executes via a strictly linear four-step protocol:

  1. Offline Precomputation (Server): The server computes the holographic index H=AG=AG(T)∈RM×BH = AG = A\mathcal{G}(T) \in\mathbb{R}^{M\times B} once across all database embeddings and pre-encodes its diagonals in NTT evaluation form.

  1. Query Encryption (Client): The client lifts query q→F(q)q \to\mathcal{F}(q) and encrypts Enc⁡(F(q))\operatorname{Enc}(\mathcal{F}(q)) into SIMD ciphertext slots.

  1. Blind Linear Evaluation (Server): The server evaluates Enc⁡(y)=H⋅Enc⁡(F(q))\operatorname{Enc}(y) = H \cdot\operatorname{Enc}(\mathcal{F}(q)) via diagonal NTT plaintext-ciphertext multiplication with zero bootstrapping—using single-generator cyclic query rotations and rotation-free row accumulation under LinPIR, or Baby-Step Giant-Step (BSGS) evaluation followed by single-limb modulus switching (Compress) under CKKS.

  1. Client Recovery & Optional PIR Reranking: The client decrypts y=Dec⁡(Enc⁡(y))y = \operatorname{Dec}(\operatorname{Enc}(y)) locally, reconstructs sparse coefficients s^=FISTA⁡(y,A,λ,L)\hat{s} = \operatorname{FISTA}(y,A,\lambda,L) and extracts the top K∗K^{*} candidate IDs (issuing an optional secondary Batch PIR re-query for those K∗K^{*} records when exact-distance reranking or document payloads are needed; § 3.4).

Degree-1 Blind Linear Arithmetic & Compiler Optimizations

Prior FHE-based vector search systems evaluate non-linear Euclidean distances or polynomial approximations of cosine similarity under homomorphic encryption. Evaluating polynomial approximations of degree d≥12d \ge12 requires deep homomorphic circuits, inducing large noise growth that necessitates expensive FHE bootstrapping operations (often requiring 10–60 seconds per ciphertext).

In Holo-NN, the server’s blind evaluation is strictly linear:

Enc⁡(y)=H⋅Enc⁡(F(q))(24)\operatorname{Enc}(y) = H \cdot\operatorname{Enc}(\mathcal{F}(q)) \tag*{(24)}

Because HH is plaintext and Enc⁡(F(q))\operatorname{Enc}(\mathcal{F}(q)) is a degree-1 ciphertext, the server executes only homomorphic plaintext-ciphertext multiplications, additions, and slot rotations:

  • Multiplicative Depth: Exactly 1 (Degree-1 linear operator).

  • FHE Bootstrapping: 0 bootstrapping operations required throughout the entire query lifecycle.

  • Compiler Optimization via HEIR: Lowering the matrix-vector multiplication through the MLIR-based

§ First figure (3.29 s end-to-end; 1.78 s server compute) is sharded across 4 CPU cores (4× 8,192 × 8,192 shards in parallel on the 6-core Xeon W-2135); parenthetical figure (4.39 s end-to-end; 2.88 s server compute) is single-threaded on 1 core.

⋄ On 1× RTX 3090 (24 GB VRAM), Phantom holds all 4 64-bit RNS blocks (12.0 GiB plaintexts, 17.1 GiB total VRAM) and evaluates all 4 blocks in 1.54 s of server compute (1.68 s end-to-end across 10 queries, or 0.385 s/block; vs. 6.95 s across 2× RTX 2080 Ti GPUs).

‡ HEIR/Cheddar [3, 17] uses 32-bit RNS words (uint32_t, log⁡2(QP)≈91\log_2(QP) \approx91 bits), halving wire footprint to 0.79 MB (256 KiB query + 4 × 128 KiB responses) and reducing plaintext VRAM by 3× to 4.00 GiB (8.1 GiB total VRAM). It evaluates a single 8,192 × 8,192 block in 12.58 ms on RTX 3090 (5.33 ms on NVIDIA H100; 8.67 ms RTX 3090 / 2.51 ms H100 at 4,096 × 4,096), completing all 4 Wikipedia blocks in 50.5 ms of server compute and 0.134 s end-to-end (100% Top-1 parity with plaintext).

⋆ At Nring=16,384N_{\mathrm{ring}} = 16,384, OpenFHE stores 190 64-bit RNS BSGS rotation keys (299 MB), Phantom stores 27 NAF/dyadic keys (84.9 MB), and Cheddar stores 190 32-bit RNS hoisted BSGS keys (74.7 MB).

HEIR compiler [3] automatically synthesizes diagonal ciphertext rotations and hoists plaintext weights, yielding optimal SIMD slot packing across OpenFHE backends.

  • Noise Growth: Minimal invariant noise budget, permitting compact RLWE parameter sets under OpenFHE’s HEStd_128_classic security standard [2] (Nring=16,384N_{\mathrm{ring}} = 16,384 for 8,192-slot blocks and Nring=32,768N_{\mathrm{ring}} = 32,768 for 16,384-slot blocks).

End-to-End Encrypted Deployment (Wikipedia 500k)

Upon receiving Enc⁡(y)\operatorname{Enc}(y), the client decrypts the MM-dimensional measurement vector y∈RMy \in\mathbb{R}^{M} within its secure local enclave and launches parallel GPU-accelerated FISTA to recover s^∈RN\hat{s} \in\mathbb{R}^{N}.

For the following algorithm discussion, we deployed the full encrypted pipeline on a 500,000-vector Wikipedia semantic demonstration search index (N=500,000N = 500,000, D=768D = 768 MPNet embeddings reduced to 128 dimensions by PCA) to validate the protocol at scale (Table 2). This deployment is a systems demonstration, not an accuracy benchmark: retrieval quality is evaluated on the standard suites of Table 1 and Table 3, which have published ground truth.

Execution surfaceWire / queryLatencyServer keys
Plaintext (no encryption)0.16 MB1.14 s0 MB
Holo-NN: LinPIR (CPU, BFV [31] exact-int.)31.41 MB3.29 s (4.39 s§)0 MB
Holo-NN: CKKS-CPU (OpenFHE [1], 12-thr)1.60 MB32.9 s299 MB⋆
Holo-NN: CKKS-GPU (Phantom [45], 1× RTX 3090)1.60 MB1.68 s⋄85 MB⋆
Holo-NN: HEIR-GPU (Cheddar [3, 17], 1× RTX 3090)0.79 MB0.134 s‡75 MB⋆

Table 2. Deployed encrypted Wikipedia-500k demonstrator (N=500,000N = 500,000, B=8,192B = 8,192, M=32,768M = 32,768, 4 blocks of 8,192×8,1928,192 \times8,192). Latency is end-to-end wall clock; wire cost is total serialized request plus response ciphertexts.

Table 3: State-of-the-art comparison across private ANN retrieval architectures. System figures are transcribed from each primary publication at its reported database scale NN. Wire / query is total mandatory per-query traffic (upload + download). Client / Server State lists persistent client RAM, per-session cold-start traffic, or server-side evaluation keys. Under Retrieval Quality, each metric occupies its own column: MRR@10 (Compass convention; ∗^{*}denotes MRR@100 on MS MARCO), 1-r@10 (true 1-NN in top 10), 10-r@10 (Panther/Onyx convention: ∣ours1:10∩true1:10∣/10|{\rm ours}_{1:10} \cap{\rm true}_{1:10}|/10), and 10-r@50 (1-RTT candidate-set coverage of true 10-NN in top 50, which equals final reranked 10-r@10 after the optional +1 RTT Batch PIR fetch).

SystemMechanism & HardwareRTTWire / queryClient / Server StateLatencyBenchmark (NN)MRR@101-r@1010-r@1010-r@50
SANNS (USENIX Sec ’20) [14]AHE + DORAM + GC 2PC (server-private DB, 32-thr)Multi†^{\dagger}1.77 GB†^{\dagger}no offline hints1.55–45.3 s‡^{\ddagger}SIFT-1M (1M)——≈\approx 90%—
PRECO (IEEE S&P ’22) [40]LSH + DPF (2 non-colluding servers, 32-thr)1§^{\S}1.5 MB§^{\S}2-srv DB replica1.1–28.2 s§^{\S}SIFT-1M (1M)——≈\approx 95%—
Tiptoe (SOSP ’23) [29]LHE + PIR (public DB, 45-srv CPU)2†^{\dagger}59.7 MB†^{\dagger}0.29 GiB model+centroids2.7 sCommon Crawl (364M)—∗^{*}———
Pacmann (ICLR ’25) [48]Sublinear PIR (public DB, CPU)2061.6 MB†^{\dagger}0.6 GB client (2.7 GB init)1.1 sMS MARCO (3.2M)0.266∗^{*}———
Pacmann (ICLR ’25) [48]Sublinear PIR (public DB, CPU)32413.8 MB†^{\dagger}2.9 GB client (59.6 GB init)1.6–3.0 sSIFT (100M)——≈\approx 90%—
Panther (CCS ’25) [32]LHE + Batch PIR + SS/GC 2PC (server-private DB, 32-thr)Multi†^{\dagger}92.9 MB†^{\dagger}no offline hints1.49–9.32 sSIFT-1M (1M)——88.85%—
Compass (OSDI ’25) [49]Ring ORAM over HNSW (CPU)812.2 MB†^{\dagger}35.8 MB client RAM (36.95 MB init)0.04–0.85 sSIFT-1M (1M)matches BF———
Onyx (arXiv ’26) [37]Hardware TEE (SEV-SNP + ORAM)1‡^{\ddagger}n/a‡^{\ddagger}170 MB enclave (1.5 GB SSD)0.019 s‡^{\ddagger}SIFT-1M (1M)——≈\approx 90%—
Holo-NN: LinPIR (M=98,300M = 98{,}300)BFV exact-int. RLWE (6-core CPU) [31]1 (+ 1)91.1 MB0 MB client / 0 MB server3.1 s∥^{\parallel}SIFT-1M (1M)0.41763.4%33.3%57.0%
Holo-NN: LinPIR (M=300,000M = 300{,}000)BFV exact-int. RLWE (6-core CPU) [31]1 (+ 1)265.4 MB0 MB client / 0 MB server6.6 s∥^{\parallel}SIFT-1M (1M)0.70293.0%61.6%92.0%
Holo-NN: LinPIR (M=380,100M = 380{,}100)BFV exact-int. RLWE (6-core CPU) [31]1 (+ 1)334.6 MB0 MB client / 0 MB server8.0 s∥^{\parallel}SIFT-1M (1M)0.74195.6%66.8%95.1%
Holo-NN: CKKS d=1 (M=98,300M = 98{,}300)OpenFHE 64b CKKS (CPU) [1]1 (+ 1)4.24 MB0 MB client / 299 MB server192.0 s∥^{\parallel}SIFT-1M (1M)0.41763.4%33.3%57.0%
Holo-NN: CKKS d=1 (M=300,000M = 300{,}000)OpenFHE 64b CKKS (CPU) [1]1 (+ 1)11.13 MB0 MB client / 299 MB server591.0 s∥^{\parallel}SIFT-1M (1M)0.70293.0%61.6%92.0%
Holo-NN: CKKS d=1 (M=380,100M = 380{,}100)OpenFHE 64b CKKS (CPU) [1]1 (+ 1)13.78 MB0 MB client / 299 MB server750.1 s∥^{\parallel}SIFT-1M (1M)0.74195.6%66.8%95.1%
Holo-NN: CKKS d=1 (M=500,000M = 500{,}000)OpenFHE 64b CKKS (CPU) [1]1 (+ 1)17.50 MB0 MB client / 299 MB server990.0 s∥^{\parallel}SIFT-1M (1M)0.80198.5%73.0%98.0%
Holo-NN: CKKS-GPU (M=98,300M = 98{,}300)Phantom 64b CKKS (1× RTX 3090) [45]1 (+ 1)4.24 MB0 MB client / 85 MB server9.5 s∥^{\parallel}SIFT-1M (1M)0.41763.4%33.3%57.0%
Holo-NN: CKKS-GPU (M=300,000M = 300{,}000)Phantom 64b CKKS (1× RTX 3090) [45]1 (+ 1)11.13 MB0 MB client / 85 MB server29.7 s∥^{\parallel}SIFT-1M (1M)0.70293.0%61.6%92.0%
Holo-NN: CKKS-GPU (M=380,100M = 380{,}100)Phantom 64b CKKS (1× RTX 3090) [45]1 (+ 1)13.78 MB0 MB client / 85 MB server38.0 s∥^{\parallel}SIFT-1M (1M)0.74195.6%66.8%95.1%
Holo-NN: CKKS-GPU (M=500,000M = 500{,}000)Phantom 64b CKKS (1× RTX 3090) [45]1 (+ 1)17.50 MB0 MB client / 85 MB server50.5 s∥^{\parallel}SIFT-1M (1M)0.80198.5%73.0%98.0%
Holo-NN: HEIR-GPU (M=98,300M = 98{,}300)Cheddar 32b CKKS (1× RTX 3090) [3, 17]1 (+ 1)2.10 MB0 MB client / 75 MB server0.26 s∥^{\parallel}SIFT-1M (1M)0.41763.4%33.3%57.0%
Holo-NN: HEIR-GPU (M=300,000M = 300{,}000)Cheddar 32b CKKS (1× RTX 3090) [3, 17]1 (+ 1)5.37 MB0 MB client / 75 MB server0.82 s∥^{\parallel}SIFT-1M (1M)0.70293.0%61.6%92.0%
Holo-NN: HEIR-GPU (M=380,100M = 380{,}100)Cheddar 32b CKKS (1× RTX 3090) [3, 17]1 (+ 1)6.68 MB0 MB client / 75 MB server1.00 s∥^{\parallel}SIFT-1M (1M)0.74195.6%66.8%95.1%
Holo-NN: HEIR-GPU (M=500,000M = 500{,}000)Cheddar 32b CKKS (1× RTX 3090) [3, 17]1 (+ 1)8.65 MB0 MB client / 75 MB server1.30 s∥^{\parallel}SIFT-1M (1M)0.80198.5%73.0%98.0%

Table 3.

Because y=HF(q)y = H F(q) is a pure matrix-vector product, Holo-NN provides four complementary encrypted execution surfaces with contrasting latency, hardware, state, and bandwidth profiles:

  • Holo-NN: LinPIR (Exact-Integer BFV RLWE, CPU): Built on Google’s HintlessPIR/LinPIR engine [31] with two 56-bit CRT plaintext moduli and a single cyclic-subgroup generator, a B=8,192B = 8,192 column strip incurs a fixed 1.24 s query baby-step Galios rotation cost (across both CRT primes) with 0.0545 s of marginal row-accumulation work per 1,024 rows on a single core. Sharding the 32,768 rows across 4 cores of the Xeon W-2135 (4 parallel 8,192 × 8,192 shards) completes the Wikipedia-500k query in 3.29 s end to end (1.78 s server compute; or 4.39 s end to end / 2.88 s server compute on a single CPU thread) — 10.0× faster end-to-end (17.9× faster in server compute) than the 12-thread CPU CKKS path — while requiring zero persistent server-side rotation keys, because its 1.45 MB Galois evaluation key per prime (3.10 MB total upload including query ciphertexts) is amortized over the query.

HEIR/Cheddar [3, 17] uses 32-bit RNS words (uint32_t, log⁡2(QP)≈91\log_2(QP) \approx91 bits), halving wire footprint to 0.79 MB (256 KiB query + 4 × 128 KiB responses) and reducing plaintext VRAM by 3× to 4.00 GiB (8.1…

†^{\dagger} Baseline figures reflect each system’s published operating point (LAN–WAN latency ranges where both are reported). Wire / query sums all mandatory per-query stages, including SANNS’s 1.77 GB 2PC traffic (56.7 MB AHE distances +645 MB GC top-kk + 1.06 GB DORAM point retrieval), Tiptoe’s 42.2 MiB token round (+2 online RTTs), and Pacmann’s 1-round maintenance step (60.1 MB / 399.4 MB). For Holo-NN, 1 RTT executes blind holographic measurement and FISTA recovery to emit ranked candidate IDs (MRR@10, 1-r@10, and un-reranked 10-r@10); the parenthetical +1 RTT denotes the optional Batch PIR re-query (Section 3.4) to fetch the top K∗=50K^{*} = 50 candidate payloads for local exact-distance reranking, which promotes 10-r@50 directly to final reranked 10-r@10 (92.0% at M=300,000M = 300{,}000; 98.0% at M=500,000M = 500{,}000). SANNS and Panther are multi-round 2PC return paths. Tiptoe and Compass include record payloads. ∗^{*}Tiptoe reports MRR@100 graphically on MS MARCO (3.2M, avg. rank 7.7/100). PRECO [40] requires two non-colluding servers holding replicas of the LSH-indexed database and probes them via Distributed Point Functions (DPFs, 1.1 s on 32 CPUs / 28.2 s on 1 CPU; leaks query LSH radius). When instantiated in a single-server setting via lattice keyword PIR, the authors estimate ≈300\approx300 MB of wire traffic and ≈25\approx25 CPU-hours per query on SIFT-1M (Appendix E of [40]). ‡^{\ddagger} Onyx executes inside an AMD SEV-SNP hardware enclave over local NVMe SSD (18.8 ms min latency, 54.2 QPS peak throughput); its bandwidth is internal enclave-to-SSD I/O rather than client-to-server wire traffic. ∥\parallel Single-node server compute on our workstation (6-core Xeon W-2135 CPU, 1× NVIDIA RTX 3090 24 GB GPU; see Table 2 for server key sizes). Client GPU FISTA adds < 0.4 s, and WAN transfer at 320 Mbps adds < 0.3–5 s for CKKS (2.3–8.4 s for LinPIR). Because HH is row-separable across independent 8,192 × 8,192 blocks (6 CPU shards for LinPIR; 7.98 s/block on CPU, 0.385 s/block on Phantom RTX 3090, or 12.58 ms/block on HEIR/Cheddar RTX 3090 and 5.33 ms/block on H100), server compute scales as 1/P1/P across PP workers without increasing wire traffic.

  • Holo-NN: CKKS d=1 (CPU, OpenFHE AVX2): Provisioning the OpenFHE [1] CKKS context at multiplicative depth 1 (2 RNS limbs) and mod-switching (Compress) each response ciphertext to a single RNS limb before serialization reduces the unit response size to 32.7 bytes per measurement at B=8,192B = 8{,}192 (32.4 bytes at B=16,384B = 16{,}384; 1.60 MB total wire on Wikipedia-500k: a 530.5 KB query plus four 268.3 KB responses, a 19.6× total wire reduction over LinPIR), completing the 4-block query in 32.9 s (31.9 s server compute, 7.98 s per 8,192 × 8,192 block) with persistent per-session BSGS rotation keys (299.0 MB for all S+G−2=190S + G - 2 = 190 hoisted baby/giant rotation steps). Run against the same encoded block, depth-1 mod-switched CKKS agrees with a plaintext HvH v reference to relative L2L_2 error 2.609×10−82.609 \times10^{-8}.

  • Holo-NN: CKKS-GPU (Phantom CUDA [45], 1× RTX 3090): Hosting all 4 NTT-encoded, 8,192 × 8,192 blocks simultaneously in the 24 GB GDDR6X VRAM of a single NVIDIA GeForce RTX 3090 (12.0 GiB RNS plaintexts, 17.1 GiB total VRAM) allows the S−1=63S - 1 = 63 baby-step Galois rotations (0.139 s) to be computed once and reused across all 4 blocks in the GPU’s 6 MiB L2 cache. Furthermore, because each prime at chain_index⁡=1\operatorname{chain\_index}=1 satisfies qi<250q_i < 2^{50} (b⋅p<2100b \cdot p < 2^{100}), a single fused 2D CUDA kernel accumulates all S=64S = 64 baby-step products across all 4 blocks in 128-bit registers (64×2100=2106≪212864 \times2^{100} = 2^{106} \ll2^{128}) before reducing modulo qiq_i once per giant step, executing all 32,768 homomorphic plaintext-ciphertext multiplications and additions in a single launch of 0.0226 s (22.6 ms, plus 0.467 s for 512 RNS rescales and 0.906 s for 508 Horner giant-step rotations at 2 RNS limbs). This completes the entire 4-block (M=32,768M = 32{,}768) server MatVec in 1.54 s (0.385 s/block) and answers the full encrypted Wikipedia-500k query in 1.68 s end to end — 19.6× faster than 12-thread CPU CKKS (32.9 s), 4.1× faster than dual RTX

2080 Ti GPUs (6.95 s), and 2.0× faster than 4-core CPU LinPIR (3.29 s) while simultaneously delivering the 1.60 MB CKKS wire footprint (19.6× smaller than LinPIR) and a 3.5× smaller server Galois key table (84.9 MB vs. 299.0 MB).

  • Holo-NN: HEIR-GPU (32-bit RNS Cheddar CUDA [3, 17], 1× RTX 3090): Lowering the BSGS linear transform (BS = 128, GS = 64) through HEIR [3] onto the Cheddar 32-bit RNS GPU library [17] replaces 64-bit RNS limbs with 32-bit words (uint32_t, log⁡2(QP)≈91\log_2(QP) \approx91 bits at Nring=16,384N_{\mathrm{ring}} = 16{,}384) and fuses baby-step hoisting with giant-step key-switching in shared-memory NTT kernels. This halves the response wire to 16.0 bytes/measurement (0.79 MB total wire on Wikipedia-500k: 256 KiB query + 4×128 KiB responses), cuts plaintext VRAM by 3× to 4.00 GiB (74.7 MB rotation keys), and evaluates a single 8,192 × 8,192 block in 12.58 ms on RTX 3090 (5.33 ms on H100; 8.67 ms RTX 3090 / 2.51 ms H100 at 4,096 × 4,096) — completing all 4 Wikipedia-500k blocks in 50.5 ms of server compute and 0.134 s end to end (30.6× faster per block than Phantom RTX 3090, with 100% Top-1 plaintext agreement).

State-of-the-Art Comparison

We compare Holo-NN’s encrypted backends against seven private ANN systems spanning cryptographic (FHE, 2PC, DPF, PIR, ORAM) and hardware-enclave architectures: SANNS [14], PRECO [40], Tiptoe [29], Pacmann [48], Panther [32], Compass [49], and Onyx [37] (Table 3).

Two caveats govern how that table should be read. First, these systems are not all evaluated on a common benchmark or threat model: Tiptoe reports on a 364M-document Common Crawl corpus (and MS MARCO for quality), Pacmann on MS MARCO and SIFT-100M, and while SANNS, PRECO, Panther, Compass, and Onyx publish numbers on SIFT-1M, PRECO requires two non-colluding servers and Onyx relies on an AMD SEV-SNP hardware enclave. We therefore quote each system at its published scale rather than extrapolating, and focus like-for-like single-server cryptographic comparisons on SANNS, Panther, and Compass. Second, they do not share a quality metric — Tiptoe and Pacmann report MRR@100, Compass MRR@10, SANNS, PRECO, and Panther a 10-NN recall/accuracy, and Onyx a top-10 recall — so we score our own candidate lists under each convention rather than quoting a single number of our own choosing.

As seen above, Holo-NN backends bracket the single-server design space between stateless single-query execution and minimal wire footprint. Among server-private cryptographic protocols on SIFT-1M, SANNS established sublinear clustering with BFV and garbled circuits at 1.77 GB of per-query traffic (1.55–45.3 s across 32 threads), which Panther reduced by 19× to 92.9 MB (1.49–9.32 s across 32 threads) via improved batch PIR and multi-round 2PC top-kk selection. Holo-NN (LinPIR) requires zero pre-installed key state on the server and answers on a 6-core Xeon W-2135 CPU in 3.1 s at M=98,300M = 98{,}300 with 91.1 MB of total wire traffic (matching Panther’s 92.9 MB and cutting SANNS’s 1.77 GB by 19.4× in a single non-interactive round trip rather than multi-round 2PC), or reaches 1-r@10 = 93.0% (10-r@50 = 92.0%) in 6.6 s at M=300,000M = 300{,}000 (265.4 MB) and 1-r@10 = 95.6% in 8.0 s at M=380,100M = 380{,}100 (334.6 MB) — running 62× to 94× faster on the server CPU than 12-thread CKKS and 3.1× to 4.8× faster than the 64-bit Phantom GPU CKKS. Conversely, when rotation keys can be registered for a session, Holo-NN (CKKS) is the lowest-wire single-server cryptographic system measured on SIFT-1M: 11.13 MB at M=300,000M = 300{,}000 (29.7 s on a single RTX 3090 GPU via Phantom, or 9.5 s at M=98,300M = 98{,}300 for 4.24 MB), and 5.37 MB in 0.82 s under 32-bit RNS HEIR-GPU (2.10 MB in 0.26 s at M=98,300M = 98{,}300, and 8.65 MB in 1.30 s at M=500,000M = 500{,}000) against Compass’s 12.2 MB, Panther’s 92.9 MB, and SANNS’s 1.77 GB, in one round trip rather than Compass’s eight, SANNS/Panther’s multi-round 2PC, or Pacmann’s twenty to thirty-two, with no client-side index state and no preprocessing stream. While PRECO achieves 1.5 MB in 1 RTT via Distributed Point Functions over LSH buckets, it requires two non-colluding servers; instantiated on a single server via lattice keyword PIR, its own authors estimate ≈ 300 MB of wire traffic and ≈ 25 CPU-hours per query on SIFT-1M [40], against which Holo-NN’s holographic projection reduces single-server wire by 27×–143× (CKKS) and compute by more than four orders of magnitude. On a 100 ms-latency 4G link Compass’s own authors measure 0.94 s of user-perceived latency on SIFT-1M, against our single round trip; Compass’s 36.95 MB per-session cold start exceeds the entire per-query CKKS budget by 3.3×–6.9×.

On top-10 multi-neighbor ranking Holo-NN falls behind, and buying more bandwidth does not close the gap. Compass matches brute-force embedding search on SIFT-1M, though it publishes no absolute MRR@10 value; at M=300,000M = 300{,}000 our backends reach MRR@10 = 0.702. Panther resolves 88.85% of each query’s true ten nearest neighbors inside its own top ten (matching SANNS’s ≈ 90%); we resolve 61.6% at M=300,000M = 300{,}000, 66.8% at M=380,100M = 380{,}100 (matching the first SIFT-1M operating tier of Table 1), and 73.0% at M=500,000M = 500{,}000 — still 15.9 points short of Panther while spending 5.3× less wire bandwidth under CKKS. The deficit is therefore not a bandwidth deficit. It is a property of the ℓ1\ell_1 recovery step rather than of the holographic measurement, as § 6.4 shows: the very same candidate lists already contain 92.0% of the true ten nearest neighbors within the top fifty at M=300,000M = 300{,}000, and 98.0% at M=500,000M = 500{,}000. What Holo-NN produces cheaply is coverage; what it does not produce is a precise ordering within that coverage.

Recall versus Bandwidth, and the Limits of l1l_1 Ranking

Table 4 gives the full trade-off curve behind the Holo-NN rows of Table 3 for both encrypted protocols. Because LinPIR and CKKS evaluate the same linear operator y=HF(q)y = HF(q), recall is a function of MM alone, and each backend’s wire cost is a deterministic function of MM given its measured ciphertext sizes. All figures are for the bare 1-RTT protocol: the FISTA ranking, with no verification fetch and no reranking against plaintext vectors.

The sweep doubles as a consistency check on Table 1. Its M=380,100M = 380,100 row is the SIFT-1M 75% regime of that table, and it reproduces all three published figures.

The two conventions diverge sharply, and the divergence is informative. At M=300,000M = 300,000 Holo-NN locates the nearest neighbor within its top ten for 93.0% of queries, but recovers only 61.6% of each query’s ten nearest neighbors in that same top ten. The missing neighbors have not been lost: raising the cutoff to fifty recovers 92.0% of them, from a candidate set that is still 20,000× smaller than the database.

The gap is also strikingly persistent in MM. Over the sweep, 1-recall@10 climbs from 63.4% to 98.5% and is effectively saturated by M=500,000M = 500,000, whereas 10-recall@10 moves only from 33.3% to 73.0% and is still rising roughly linearly when 1-recall has flattened. Adding measurements sharpens the question “is the true nearest neighbor in this list” long before it sharpens “are these ten the right ten”. A budget that resolves the first question almost perfectly leaves the second one a quarter unanswered.

This is the expected behavior of ℓ1\ell_1 recovery on a correlated support, not a defect of the measurement operator. A query’s ten true nearest neighbors are, by construction, mutually near-identical, so their feature vectors G(ti)G(t_i) are highly correlated and the corresponding columns of H=AG(T)H = AG(T) are nearly collinear. Faced with a group of near-collinear atoms that jointly explain the measurement, the LASSO [42] does not distribute the coefficient across the group; it concentrates the mass on a single representative and shrinks the remainder toward zero [50]. The surviving representative is reliably a member of the true neighbor set—which is why 1-recall is high—while its near-duplicates are demoted in magnitude though not eliminated, which is why they reappear as the cutoff widens.

The implication is that Holo-NN, in its present form, is best understood as an unusually cheap, tunable, high-coverage approximate nearest-neighbor algorithm rather than a precise ranker, even in the limit of computation and bandwidth. Where a downstream exact-distance stage is available—a client that already holds the candidate payloads, or a private retrieval step as in § 3.4—the relevant quantity is the coverage figure, and 92.0% of the true ten neighbors for 5.37 MB in 0.82 s (HEIR-GPU CKKS), 11.13 MB (64-bit CKKS), or 265.4 MB with zero persistent server state (LinPIR) in one round trip compares favorably with Panther’s 88.85% for 92.9 MB and SANNS’s ≈ 90% for 1.77 GB—though the comparison is not strict, since SANNS and Panther deliver their top-ten sets already ranked within a top ten while Holo-NN is a top fifty, awaiting a reranking stage. Where no such stage exists, the ranking Holo-NN emits is materially weaker than Compass’s. Substituting an Elastic Net [50] (ℓ1+ℓ2\ell_1 + \ell_2) or Group LASSO [47] proximal operator for the ℓ1\ell_1 soft threshold would be expected to redistribute mass across correlated groups and close much of this gap, at no cost in bandwidth, round trips or server work, since it changes only the client’s local recovery step. We leave this to future work.

Conclusion

We presented Holo-NN, a holographic approximate nearest-neighbor retrieval architecture that reformulates nearest-neighbor search as an underdetermined linear Compressive Sensing problem. By precomputing a degree-1 compressed database representation offline (H=AG=AG(T)∈RM×BH = AG = AG(T) \in\mathbb{R}^{M \times B}), Holo-NN executes blind, privacy-preserving retrieval via a single linear operator requiring M≪NM \ll N measurements in a single non-interactive round trip, with no client-side index state and no pre-processing stream. Because HH is constructed offline on the server, the index operator can profile the empirical bandwidth–recall trade-off directly on the target dataset, while our Asymmetric FlyHash projection removes the double-quantization loss that a symmetric sparse code would incur on high-dimensional semantic manifolds.

Holo-NN works in plaintext as a generic high-confidence, approximate nearest neighbor algorithm. Because blind forms of the algorithm function as single-round private linear operations, they scale well to LinPIR or other private linear operations while retaining naturally scalable, embarrassingly parallel computational models that are well suited to modern hardware. Moreover, this framing may appear as a component of a broader nearest-neighbor pipeline, whether for optimizing candidate generation or used directly, in-line in machine learning settings.

References

  1. [1]Ahmad Al Badawi, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Ian Quah, Yuriy Polyakov, Saraswathy R.V., Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. OpenFHE: Open-source fully homomorphic encryption library. In Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography (WAHC), pages 53–63, 2022.
  2. [2]Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. Homomorphic encryption security standard. HomomorphicEncryption.org, Toronto, Canada, November 2018.
  3. [3]Asra Ali, Jaeho Choi, Bryant Gipson, Shruthi Gorantala, Jeremy Kun, Wouter Liegist, Lawrence Lim, Alexander Viand, Meron Zerihun Demissie, and Hongren Zheng. HEIR: A universal compiler for homomorphic encryption. arXiv preprint arXiv:2508.11095, 2025.arxiv.org/abs/2508.11095
  4. [4]Waheed U. Bajwa, Jarvis Haupt, Akbar M. Sayeed, and Robert D. Nowak. Compressive wireless sensing. In Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN), pages 134–142, 2006.DOI
  5. [5]Richard G. Baraniuk. Compressive sensing. IEEE Signal Processing Magazine, 24(4):118–121, 2007.
  6. [6]Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183–202, 2009.DOI
  7. [7]Jérôme Bobin, Jean-Luc Starck, and Roland Ottensamer. Compressed sensing in astronomy. IEEE Journal of Selected Topics in Signal Processing, 2(5):718–726, 2008.DOI
  8. [8]Salomon Bochner. Monotone Funktionen, Stieltjessche Integrale und harmonische Analyse. Mathematische Annalen, 108(1):378–410, 1933.DOI
  9. [9]Emmanuel J. Candès. The restricted isometry property and its implications for compressed sensing. Comptes Rendus Mathématique, 346(9-10):589–592, 2008.
  10. [10]Emmanuel J. Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(2):489–509, 2006.
  11. [11]Emmanuel J. Candès and Terence Tao. Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203–4215, 2005.DOI
  12. [12]Emmanuel J. Candès and Michael B. Wakin. An introduction to compressive sampling. IEEE Signal Processing Magazine, 25(2):21–30, 2008.DOI
  13. [13]Sophie J. C. Caron, Vanessa Ruta, L. F. Abbott, and Richard Axel. Random convergence of olfactory inputs in the Drosophila mushroom body. Nature, 497(7447):113–117, 2013.
  14. [14]Hao Chen, Ilaria Chillotti, Yihe Dong, Oxana Poburinnaya, Ilya Ranzenshteyn, and M. Sadegh Riazi. SANNS: Scaling up secure approximate k-nearest neighbors search. In 29th USENIX Security Symposium (USENIX Security 20), pages 2111–2128, 2020.
  15. [15]Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders. Atomic decomposition by basis pursuit. SIAM Review, 43(1):129–159, 2001.
  16. [16]Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong-soo Song. Homomorphic encryption for arithmetic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), pages 409–437, 2017.
  17. [17]Wonseok Choi, Jongmin Kim, and Jung Ho Ahn. Cheddar: A swift fully homomorphic encryption library designed for GPU architectures. In Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2026.
  18. [18]Jon F. Claerbout and Francis Muir. Robust modeling with erratic data. Geophysics, 38(5):826–844, 1973.
  19. [19]Gabriel Cramer. Introduction à l’analyse des lignes courbes algébriques. Chez les Frères Cramer & Cl. Philibert, 1750.
  20. [20]Sanjoy Dasgupta, Charles F. Stevens, and Saket Navlakha. A neural algorithm for a fundamental computing problem. Science, 358(6364):793–796, 2017.
  21. [21]Ingrid Daubechies, Michel Defrise, and Christine De Mol. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications on Pure and Applied Mathematics, 57(11):1413–1457, 2004.
  22. [22]David L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289–1306, 2006.DOI
  23. [23]David L. Donoho and Iain M. Johnstone. Ideal spatial adaptation by wavelet shrinkage. Biometrika, 81(3):425–455, 1994.DOI
  24. [24]David L. Donoho and Jared Tanner. Neighborliness of randomly projected simplices in high dimensions. Proceedings of the National Academy of Sciences, 102(27):9452–9457, 2005.pubmed.ncbi.nlm.nih.gov/15972808
  25. [25]David L. Donoho and Jared Tanner. Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. Philosophical Transactions of the Royal Society A, 367(1906):4273–4293, 2009.
  26. [26]Marco F. Duarte, Mark A. Davenport, Dharmpal Takhar, Jason N. Laska, Ting Sun, Kevin F. Kelly, and Richard G. Baraniuk. Single-pixel imaging via compressive sampling. IEEE Signal Processing Magazine, 25(2):83–91, 2008.DOI
  27. [27]Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Birkhäuser / Springer, 2013.DOI
  28. [28]Ruigi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning (ICML), pages 3887–3896, 2020.
  29. [29]Alexandra Henzinger, Emma Dauterman, Henry Corrigan-Gibbs, and Nicolai Zeldovich. Private web search with Tiptoe. In Proceedings of the 29th ACM Symposium on Operating Systems Principles (SOSP), pages 396–416, 2023.DOI
  30. [30]Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535–547, 2019.arxiv.org/abs/1702.08734
  31. [31]Baiyu Li, Daniele Micciancio, Mariana Raykova, and Mark Schultz-Wu. Hintless single-server private information retrieval. In Advances in Cryptology — CRYPTO 2024, volume 14922 of Lecture Notes in Computer Science, pages 183–217. Springer, 2024. Cryptology ePrint Archive, Paper 2023/1733.DOI
  32. [32]Jingyu Li, Zhicong Huang, Min Zhang, Cheng Hong, Jian Liu, Tao Wei, and Wenguang Chen. Panther: Private approximate nearest neighbor search in the single server setting. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 365–379, 2025.
  33. [33]Yuchen Liang, Chaitanya K. Ryali, Benjamin Hoover, Leopold Grinberg, Saket Navlakha, Mohammed J. Zaki, and Dmitry Krotov. Can a fruit fly learn word embeddings? In International Conference on Learning Representations (ICLR), 2021.arxiv.org/abs/2101.06887
  34. [34]Michael Lustig, David Donoho, and John M. Pauly. Sparse MRI: The application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine, 58(6):1182–1195, 2007.pubmed.ncbi.nlm.nih.gov/17969013
  35. [35]Yu A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824–836, 2020.
  36. [36]Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NeurIPS), volume 20, pages 1177–1184, 2007.
  37. [37]Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, and Raluca Ada Popa. Onyx: Cost-efficient disk-oblivious ANN search. arXiv preprint arXiv:2604.20401, 2026.arxiv.org/abs/2604.20401
  38. [38]Chaitanya K. Ryali, John J. Hopfield, Leopold Grinberg, and Dmitry Krotov. Bio-inspired hashing for unsupervised similarity search. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of PMLR, pages 8295–8306, 2020.arxiv.org/abs/2001.04907
  39. [39]Isaac J. Schoenberg. Metric spaces and positive definite functions. Transactions of the American Mathematical Society, 44(3):522–536, 1938.
  40. [40]Sacha Servan-Schreiber, Simon Langowski, and Srinivas Devadas. Private approximate nearest neighbor search with sublinear communication. In 2022 IEEE Symposium on Security and Privacy (SP), pages 911–929. IEEE, 2022.
  41. [41]Claude E. Shannon. Communication in the presence of noise. Proceedings of the IRE, 37(1):10–21, 1949.
  42. [42]Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996.
  43. [43]Joel A. Tropp and Anna C. Gilbert. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 53(12):4655–4666, 2007.
  44. [44]Gregory K. Wallace. The JPEG still picture compression standard. Communications of the ACM, 34(4):30–44, 1991.
  45. [45]Hao Yang, Shiyu Shen, Wangchen Dai, Lu Zhou, Zhe Liu, and Yunlei Zhao. Phantom: A CUDA-accelerated word-wise homomorphic encryption library. IEEE Transactions on Dependable and Secure Computing, 21(5):4895–4906, 2024.DOI
  46. [46]Y. Q. Yin, Z. D. Bai, and P. R. Krishniaiah. On the limit of the largest eigenvalue of the large dimensional sample covariance matrix. Probability Theory and Related Fields, 78(4):509–521, 1988.
  47. [47]Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68(1):49–67, 2006.DOI
  48. [48]Mingxun Zhou, Elaine Shi, and Giulia Fanti. Pacmann: Efficient private approximate nearest neighbor search. In International Conference on Learning Representations (ICLR), 2025.
  49. [49]Jinhao Zhu, Liana Patel, Matei Zaharia, and Raluca Ada Popa. Compass: Encrypted semantic search with high accuracy. In Proceedings of the 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 915–938, 2025.
  50. [50]Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(2):301–320, 2005.DOI

Paper details

vlnc:W_sw4rx9s2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents