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 () 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 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 -sparse representation where , significantly fewer measurements than are required for high-fidelity reconstruction. Intuitively, reconstruction is possible because one is attempting to solve for non-zero elements in an -dimensional space, which can be solved efficiently via convex -optimization algorithms. Formally, given an underdetermined system of linear measurements with , an unknown -sparse signal can be recovered by solving the convex program subject to (or under noise), provided .
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 (e.g., an image in JPEG [44]) admits a -sparse representation under a sparsifying basis or dictionary such that . Instead of acquiring all ambient samples and compressing them post hoc, compressive sensing directly acquires non-adaptive linear measurements via a pseudorandom measurement matrix :
The sparse coefficient vector is then reconstructed from by applying convex -regularized recovery algorithms [42, 6, 43, 21, 15], after which the original signal can be synthesized if needed.
In our nearest-neighbor setting (§ 1.3), the paradigm is even more direct: the sparse vector is itself the primary object of interest. Specifically, is the database affinity vector whose coordinates indicate the nearest neighbors of a query. Consequently, recovering directly from compressed measurements immediately reveals the nearest-neighbor candidates (and their approximate distances) without requiring secondary reconstruction of an underlying signal . Because is pseudorandom and the database features are known a priori, the server’s linear operator can be precomputed offline, leaving only the compact vector to be transmitted to the client.
Nearest Neighbor Search as Sparse Signal Recovery
Consider a database of vectors and a query point . 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 with entries is completely dense, the corresponding -nearest neighbor indicator vector is, by construction, exactly -sparse. In particular, for 1-NN retrieval, is a 1-hot vector containing a single non-zero entry among 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 is not merely an uninformative binary 0/1 indicator, but a continuous local affinity vector whose entries 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.

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

Figure 1. Nearest Neighbor search reformulated as sparse signal recovery. (a) 2D point constellation with directed 1-NN graph. (b) Dense pairwise distance matrix . (c) Distance-valued 1-sparse NN affinity matrix , where each row contains exactly one non-zero entry.
The server compresses this affinity field into linear measurements via a pseudorandom measurement matrix . The core challenge is designing feature embeddings and that guarantee that distances are meaningful, but that decay quickly enough such that is sufficiently sparse for stable Compressive Sensing recovery, allowing the server to compute without ever computing the full -dimensional vector .
While the raw query is generally dense, and can be performed via linear operations simply (e.g., for vectors and ), modern machine learning provides effective non-linear feature embeddings that induce sparsity in an expanded feature space (). 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:
Where and are sparsity-enhancing feature transforms. By stacking the transformed database vectors into a database feature matrix , where row is , the uncompressed affinity vector across the entire database is then simply the matrix-vector product:
By pre-multiplying this database feature matrix by a pseudorandom measurement matrix , we construct the Holographic Sensing Matrix:
It’s useful to pause and note the connection to Holography and physical intuition behind it. Specifically for an isolated vector pair , a priori, the computation shares no information with any neighbors and therefore the 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 ). 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 plays this role, dispersing distances across multiple measurements that, collectively and in far fewer number than , can infer the signal of interest.
The linear framing cleanly separates the problem into an offline precomputation and an online linear query evaluation:
Here, is computed once offline and stored permanently. Given a query , the evaluator simply computes the linear product , producing the compressed measurements without ever materializing the uncompressed -dimensional vector . The querier, knowing only the pseudorandom matrix , can then recover the sparse affinity vector directly from via standard convex recovery algorithms (discussed below) in a fully local environment, without ever needing to know or download the holographic database matrix .
Moreover, because of the lossy nature of the initial transform, we can, with judicious design of the matrix , 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
Holographic Retrieval Formulation: We reformulate ANN search as a single-round-trip (1-RTT), non-interactive linear Compressive Sensing problem () utilizing an offline precomputed holographic matrix .
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 () to eliminate double-quantization dropouts at zero encrypted wire overhead (§ 4 and § 5).
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 hosts a large-scale database of high-dimensional feature vectors, and a client holds a confidential query vector .
The objective is to retrieve the approximate nearest neighbor under standard metric spaces—specifically Euclidean distance (e.g., via RFF) or angular cosine similarity (e.g., via FlyHash)—subject to basic privacy constraints:
Query & Access-Pattern Privacy: Under standard IND-CPA Ring-LWE encryption, the server learns nothing about the client’s query . Crucially, unlike graph- or tree-based private search that leaks data-dependent branching paths, the server’s execution trace () 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.
Index Protection (Bounded Single-Query Leakage): The client never downloads the raw database or the holographic index . For an honest-but-curious client issuing a query , the single -dimensional response () is an underdetermined linear projection with an -dimensional null space in , enabling sparse recovery of the local Voronoi neighbors without transmitting raw vectors . Defending against an adaptive malicious client that issues chosen basis queries to reconstruct (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.
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 -dimensional sparse signal
from an underdetermined measurement vector with and support the number of non-zero entries:
where is a measurement operator satisfying the Restricted Isometry Property (RIP) [9, 11] of order . Specifically, there exists an isometry constant such that for all -sparse vectors :
In practice, is drawn from appropriately chosen random ensembles, most commonly:
Though, given that Bernoulli amounts to random sums and negations of existing column entries, this distribution is typically the most efficient choice.
Because is pseudorandom, any entry or column can be evaluated on the fly in time by both client and server using a Pseudorandom Function (PRF) keyed by a compact shared seed (e.g., 128-bit AES-CTR), eliminating any requirement to transmit or materialize in memory or GPU VRAM.
Kernel Lifting & Distance Approximations
In metric nearest neighbor search, non-linear geometric distances ( Euclidean distance or cosine similarity) can be directly evaluated via linear operations in the raw feature space (), but they are typically dense in . To bridge this gap, feature mapping functions lift continuous vectors into an expanded -dimensional space () where a localized similarity kernel —defined as a positive, monotonically decreasing function of metric distance that vanishes outside a local neighborhood—is preserved as a linear inner product:
While many kernel feature mappings exist, two are of particular use for our purposes:
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 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 are approximated by
projecting vectors onto random Gaussian frequencies to produce :
The RBF acts as a spatial bandpass filter: points within a Euclidean radius produce positive inner products, while distant points decay exponentially toward zero, inducing physical sparsity.
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 and can be sparsified via winner-take-all (-WTA) competitive inhibition to yield a binary code, as in traditional applications, or a sparse gated projection as in our work whose -th coordinate is:
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 of sparse representations while remaining resilient to high-dimensional metric concentration.
Throughout the remainder of this paper, the query mapping and database mapping 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 and query , the client and server apply complementary localized feature mappings (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 , and (2) Zero-Mean Background Incoherence, where global mean-centering () ensures that background inner products vanish in expectation (). Stacking the transformed database vectors produces the database embedding matrix:
The uncompressed affinity vector between query and all database points is:
Because and act as localized spatial or angular bandpass filters, is -compressible (approximately sparse): its largest positive components capture the local Voronoi neighborhood around , while the residual background tail decays rapidly below the universal soft-thresholding floor .
Offline Server Database Grating
Rather than storing or scanning at query time, the server pre-multiplies the database feature matrix with the pseudorandom measurement matrix :
The resulting matrix is the Holographic Sensing Matrix. It compresses the -point database into linear measurement channels across the feature dimensions. This computation is executed strictly offline, once, during index construction and stored permanently on the server. Given the offline pre-computation of , 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 -dimensional feature representation 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:
By association:
The server thus produces the exact Compressive Sensing measurement vector of the latent sparse similarity signal , without ever materializing or inspecting the full -dimensional vector . Crucially, because the server operator 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 directly over ciphertexts.
Client Enclave Sparse Recovery & Candidate Reranking
Upon receiving the -dimensional measurement vector , the client recovers the sparse similarity vector by solving the non-negative -regularized inverse problem (LASSO [42]):
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:
with initial conditions , , Bai-Yin spectral step size [46], and Donoho-Johnstone universal threshold [23].
Upon convergence, the client extracts the top coordinates with the highest recovered affinity scores:
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 candidates is required, the client issues a secondary Private Information Retrieval (Batch PIR, e.g., via HintlessPIR [31]) re-query for those 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 (measurement count), (feature embedding width), and (candidate verification budget) establish an operational tradeoff between accuracy, communication bandwidth, and computation. While Compressive Sensing theory establishes that scales logarithmically with ambient dimension for a fixed sparsity level () [24, 25], the effective sparsity of the affinity vector —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 is constructed offline on the server, with the full database in hand, Holo-NN requires no brittle closed-form heuristics to guess or 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 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 () and applying winner-take-all (-WTA) competitive inhibition.
In conventional symmetric sparse coding, both the database points and the query vector are pruned to an identical top- active anchor budget (). However, symmetric hard sparsification induces a severe double-quantization pathology: if a salient anchor ranks just above the top- 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 and database are different, with the latter being significantly sparser than the former:
Database Grating (): The server’s precomputed database feature representation maintains a strict, ultra-sparse support ( per row). This ensures that the offline holographic matrix remains compact and computationally efficient.
Query Aperture (): The client projects the query through a broader activation aperture ( with ).
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 , so cost grows with from a negligible base. Under homomorphic encryption, the query is a dense SIMD ciphertext spanning all slots whose byte size depends only on and the RNS limb count and is therefore completely independent of —transmitting only the active coordinates is not an option, since the support of 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 . MNIST-784 () falls squarely in the first regime while GloVe-25 () falls squarely in the second, as alone does not predict which transform applies.
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 create genuine physical sparsity because spatial volume scales as . Points outside the local kernel radius decay exponentially toward zero, enabling high-fidelity metric nearest neighbor recovery (Figure 2 and Table 1).
| Dataset | Metric Space & Transform | Regime | Rec@1 | Rec@ | Rec@50 | ||||||
| SIFT-1M | Euclidean RFF | 1,000,000 | 128 | 16,384 | 75.0% | 380,100 | 38.01% | 8 | 62.00% | 94.10% | 99.20% |
| 85.0% | 445,200 | 44.52% | 11 | 67.60% | 98.00% | 99.80% | |||||
| 95.0% | 631,200 | 63.12% | 19 | 72.30% | 99.70% | 100.00% | |||||
| 99.9% | 1,294,900 | 129.49% | 50 | 82.10% | 100.00% | 100.00% | |||||
| MNIST-784 | Pixel Manifold RFF | 60,000 | 784 | 8,192 | 75.0% | 6,000 | 10.00% | 30 | 23.37% | 75.42% | 79.95% |
| 85.0% | 9,000 | 15.00% | 30 | 32.22% | 86.02% | 90.54% | |||||
| 95.0% | 12,000 | 20.00% | 40 | 39.14% | 93.80% | 94.95% | |||||
| 99.9% | 16,000 | 26.67% | 50 | 46.46% | 97.79% | 97.79% | |||||
| GloVe-25 | Angular FlyHash (AFH) | 1,183,514 | 25 | 65,536 | 75.0% | 95,000 | 8.03% | 500 | 18.00% | 82.60% | 63.30% |
| 85.0% | 130,000 | 10.98% | 500 | 20.60% | 89.00% | 70.20% | |||||
| 95.0% | 200,000 | 16.90% | 500 | 24.90% | 94.80% | 78.70% | |||||
| 99.9% | 300,000 | 25.35% | 500 | 26.60% | 97.50% | 84.30% | |||||
| Last.fm-64 | Raw MIPS (no lifting) | 292,385 | 65 | 65 | 75.0% | 20,000 | 6.84% | 50 | 6.60% | 57.60% | 57.60% |
| 85.0% | 28,000 | 9.58% | 50 | 8.90% | 71.10% | 71.10% | |||||
| 95.0% | 40,000 | 13.68% | 50 | 14.40% | 82.30% | 82.30% | |||||
| 99.9% | 60,000 | 20.52% | 50 | 22.30% | 93.30% | 93.30% |
Table 1. Multi-Scale Benchmark Results across 4 Datasets and 4 Operating Tiers (, ). Rec@k is 1-recall@k: the fraction of queries whose true nearest neighbor appears among the top candidates returned by FISTA.
Unstructured Semantic Hyperspheres (intrinsic dimension ambient ): On unconstrained hyperspherical manifolds, pairwise Euclidean distances concentrate sharply around as grows, since and 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 .
In contrast, Asymmetric FlyHash partitions high-dimensional space via nearly orthogonal random hyperplanes. Discrete -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 () and angular (cosine) metric spaces:
SIFT-1M (, ): The canonical computer vision benchmark evaluated under Euclidean () distance across the first of the 10,000 official test queries. Vectors are mean-centered, globally rescaled, and lifted via Random Fourier Features (, ), mapping Euclidean proximity to real-valued inner products.
MNIST-784 (, ): Handwritten digit pixel vectors evaluated under Euclidean () distance across test queries, lifted via mean-centered Random Fourier Features (, ).
GloVe-25 (, ): Web-crawl word embeddings evaluated under angular cosine similarity across test queries, lifted via Asymmetric FlyHash () to resolve angular crowding on the unit hypersphere.
Last.fm-64 (, ): Sparse user-music interaction preference vectors evaluated under maximum inner product (MIPS) across test queries. Because the inner product is already linear, we apply no feature lifting (, ) 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, 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 sensing matrix (which would require 1.52 TB of float32 memory at , ), million-vector corpora are partitioned into disjoint blocks of vectors (). Each block’s sensing matrix is drawn from the normalized Bernoulli ensemble and generated on the fly from a shared 128-bit PRNG seed ( MB in GPU VRAM, fitting even on lightweight 4 GB client GPUs), enabling batched GPU FISTA across all blocks in 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 , whereas practical encrypted deployments operate at 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 –25.35%. By contrast, Last.fm-64 (, 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.
| Cheddar 32b Wire | Cheddar GPU | CKKS 64b Wire | LinPIR Wire | 1-r@1 | 1-r@10 | 10-r@10 | 10-r@50 | MRR@10 | |
| 98,300 | 2.10 MB | 0.26 s | 4.24 MB | 91.1 MB | 32.5 | 63.4 | 33.3 | 57.0 | 0.417 |
| 150,000 | 3.01 MB | 0.42 s | 6.36 MB | 135.8 MB | 40.5 | 75.8 | 43.8 | 72.5 | 0.518 |
| 200,000 | 3.80 MB | 0.54 s | 7.95 MB | 179.0 MB | 48.2 | 84.2 | 51.8 | 82.0 | 0.601 |
| 250,000 | 4.59 MB | 0.67 s | 9.54 MB | 222.2 MB | 53.5 | 89.3 | 57.3 | 88.0 | 0.652 |
| 300,000 | 5.37 MB | 0.82 s | 11.13 MB | 265.4 MB | 58.2 | 93.0 | 61.6 | 92.0 | 0.702 |
| 327,600 | 5.77 MB | 0.86 s | 11.66 MB | 289.2 MB | 59.7 | 93.3 | 63.8 | 93.0 | 0.718 |
| 380,1001 | 6.68 MB | 1.00 s | 13.78 MB | 334.6 MB | 62.0 | 95.6 | 66.8 | 95.1 | 0.741 |
| 500,000 | 8.65 MB | 1.30 s | 17.50 MB | 438.2 MB | 69.5 | 98.5 | 73.0 | 98.0 | 0.801 |
Table 4. Holo-NN on SIFT-1M (, , ), 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 KiB single-limb responses; CKKS 64b Wire (OpenFHE/Phantom) is 1.05 MB query plus MB responses; LinPIR Wire is 6.19 MB inline key+query upload plus 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:
Offline Precomputation (Server): The server computes the holographic index once across all database embeddings and pre-encodes its diagonals in NTT evaluation form.
Query Encryption (Client): The client lifts query and encrypts into SIMD ciphertext slots.
Blind Linear Evaluation (Server): The server evaluates 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.
Client Recovery & Optional PIR Reranking: The client decrypts locally, reconstructs sparse coefficients and extracts the top candidate IDs (issuing an optional secondary Batch PIR re-query for those 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 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:
Because is plaintext and 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, 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 , 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] ( for 8,192-slot blocks and for 16,384-slot blocks).
End-to-End Encrypted Deployment (Wikipedia 500k)
Upon receiving , the client decrypts the -dimensional measurement vector within its secure local enclave and launches parallel GPU-accelerated FISTA to recover .
For the following algorithm discussion, we deployed the full encrypted pipeline on a 500,000-vector Wikipedia semantic demonstration search index (, 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 surface | Wire / query | Latency | Server keys |
| Plaintext (no encryption) | 0.16 MB | 1.14 s | 0 MB |
| Holo-NN: LinPIR (CPU, BFV [31] exact-int.) | 31.41 MB | 3.29 s (4.39 s§) | 0 MB |
| Holo-NN: CKKS-CPU (OpenFHE [1], 12-thr) | 1.60 MB | 32.9 s | 299 MB⋆ |
| Holo-NN: CKKS-GPU (Phantom [45], 1× RTX 3090) | 1.60 MB | 1.68 s⋄ | 85 MB⋆ |
| Holo-NN: HEIR-GPU (Cheddar [3, 17], 1× RTX 3090) | 0.79 MB | 0.134 s‡ | 75 MB⋆ |
Table 2. Deployed encrypted Wikipedia-500k demonstrator (, , , 4 blocks of ). 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 . 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: ), 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).
| System | Mechanism & Hardware | RTT | Wire / query | Client / Server State | Latency | Benchmark () | MRR@10 | 1-r@10 | 10-r@10 | 10-r@50 |
| SANNS (USENIX Sec ’20) [14] | AHE + DORAM + GC 2PC (server-private DB, 32-thr) | Multi | 1.77 GB | no offline hints | 1.55–45.3 s | SIFT-1M (1M) | — | — | 90% | — |
| PRECO (IEEE S&P ’22) [40] | LSH + DPF (2 non-colluding servers, 32-thr) | 1 | 1.5 MB | 2-srv DB replica | 1.1–28.2 s | SIFT-1M (1M) | — | — | 95% | — |
| Tiptoe (SOSP ’23) [29] | LHE + PIR (public DB, 45-srv CPU) | 2 | 59.7 MB | 0.29 GiB model+centroids | 2.7 s | Common Crawl (364M) | — | — | — | — |
| Pacmann (ICLR ’25) [48] | Sublinear PIR (public DB, CPU) | 20 | 61.6 MB | 0.6 GB client (2.7 GB init) | 1.1 s | MS MARCO (3.2M) | 0.266 | — | — | — |
| Pacmann (ICLR ’25) [48] | Sublinear PIR (public DB, CPU) | 32 | 413.8 MB | 2.9 GB client (59.6 GB init) | 1.6–3.0 s | SIFT (100M) | — | — | 90% | — |
| Panther (CCS ’25) [32] | LHE + Batch PIR + SS/GC 2PC (server-private DB, 32-thr) | Multi | 92.9 MB | no offline hints | 1.49–9.32 s | SIFT-1M (1M) | — | — | 88.85% | — |
| Compass (OSDI ’25) [49] | Ring ORAM over HNSW (CPU) | 8 | 12.2 MB | 35.8 MB client RAM (36.95 MB init) | 0.04–0.85 s | SIFT-1M (1M) | matches BF | — | — | — |
| Onyx (arXiv ’26) [37] | Hardware TEE (SEV-SNP + ORAM) | 1 | n/a | 170 MB enclave (1.5 GB SSD) | 0.019 s | SIFT-1M (1M) | — | — | 90% | — |
| Holo-NN: LinPIR () | BFV exact-int. RLWE (6-core CPU) [31] | 1 (+ 1) | 91.1 MB | 0 MB client / 0 MB server | 3.1 s | SIFT-1M (1M) | 0.417 | 63.4% | 33.3% | 57.0% |
| Holo-NN: LinPIR () | BFV exact-int. RLWE (6-core CPU) [31] | 1 (+ 1) | 265.4 MB | 0 MB client / 0 MB server | 6.6 s | SIFT-1M (1M) | 0.702 | 93.0% | 61.6% | 92.0% |
| Holo-NN: LinPIR () | BFV exact-int. RLWE (6-core CPU) [31] | 1 (+ 1) | 334.6 MB | 0 MB client / 0 MB server | 8.0 s | SIFT-1M (1M) | 0.741 | 95.6% | 66.8% | 95.1% |
| Holo-NN: CKKS d=1 () | OpenFHE 64b CKKS (CPU) [1] | 1 (+ 1) | 4.24 MB | 0 MB client / 299 MB server | 192.0 s | SIFT-1M (1M) | 0.417 | 63.4% | 33.3% | 57.0% |
| Holo-NN: CKKS d=1 () | OpenFHE 64b CKKS (CPU) [1] | 1 (+ 1) | 11.13 MB | 0 MB client / 299 MB server | 591.0 s | SIFT-1M (1M) | 0.702 | 93.0% | 61.6% | 92.0% |
| Holo-NN: CKKS d=1 () | OpenFHE 64b CKKS (CPU) [1] | 1 (+ 1) | 13.78 MB | 0 MB client / 299 MB server | 750.1 s | SIFT-1M (1M) | 0.741 | 95.6% | 66.8% | 95.1% |
| Holo-NN: CKKS d=1 () | OpenFHE 64b CKKS (CPU) [1] | 1 (+ 1) | 17.50 MB | 0 MB client / 299 MB server | 990.0 s | SIFT-1M (1M) | 0.801 | 98.5% | 73.0% | 98.0% |
| Holo-NN: CKKS-GPU () | Phantom 64b CKKS (1× RTX 3090) [45] | 1 (+ 1) | 4.24 MB | 0 MB client / 85 MB server | 9.5 s | SIFT-1M (1M) | 0.417 | 63.4% | 33.3% | 57.0% |
| Holo-NN: CKKS-GPU () | Phantom 64b CKKS (1× RTX 3090) [45] | 1 (+ 1) | 11.13 MB | 0 MB client / 85 MB server | 29.7 s | SIFT-1M (1M) | 0.702 | 93.0% | 61.6% | 92.0% |
| Holo-NN: CKKS-GPU () | Phantom 64b CKKS (1× RTX 3090) [45] | 1 (+ 1) | 13.78 MB | 0 MB client / 85 MB server | 38.0 s | SIFT-1M (1M) | 0.741 | 95.6% | 66.8% | 95.1% |
| Holo-NN: CKKS-GPU () | Phantom 64b CKKS (1× RTX 3090) [45] | 1 (+ 1) | 17.50 MB | 0 MB client / 85 MB server | 50.5 s | SIFT-1M (1M) | 0.801 | 98.5% | 73.0% | 98.0% |
| Holo-NN: HEIR-GPU () | Cheddar 32b CKKS (1× RTX 3090) [3, 17] | 1 (+ 1) | 2.10 MB | 0 MB client / 75 MB server | 0.26 s | SIFT-1M (1M) | 0.417 | 63.4% | 33.3% | 57.0% |
| Holo-NN: HEIR-GPU () | Cheddar 32b CKKS (1× RTX 3090) [3, 17] | 1 (+ 1) | 5.37 MB | 0 MB client / 75 MB server | 0.82 s | SIFT-1M (1M) | 0.702 | 93.0% | 61.6% | 92.0% |
| Holo-NN: HEIR-GPU () | Cheddar 32b CKKS (1× RTX 3090) [3, 17] | 1 (+ 1) | 6.68 MB | 0 MB client / 75 MB server | 1.00 s | SIFT-1M (1M) | 0.741 | 95.6% | 66.8% | 95.1% |
| Holo-NN: HEIR-GPU () | Cheddar 32b CKKS (1× RTX 3090) [3, 17] | 1 (+ 1) | 8.65 MB | 0 MB client / 75 MB server | 1.30 s | SIFT-1M (1M) | 0.801 | 98.5% | 73.0% | 98.0% |
Table 3.
Because 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 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, 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…
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- + 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 candidate payloads for local exact-distance reranking, which promotes 10-r@50 directly to final reranked 10-r@10 (92.0% at ; 98.0% at ). 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 MB of wire traffic and CPU-hours per query on SIFT-1M (Appendix E of [40]). 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. 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 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 across 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 (32.4 bytes at ; 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 hoisted baby/giant rotation steps). Run against the same encoded block, depth-1 mod-switched CKKS agrees with a plaintext reference to relative error .
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 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 satisfies (), a single fused 2D CUDA kernel accumulates all baby-step products across all 4 blocks in 128-bit registers () before reducing modulo 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 () 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, bits at ) 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- 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 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 (265.4 MB) and 1-r@10 = 95.6% in 8.0 s at (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 (29.7 s on a single RTX 3090 GPU via Phantom, or 9.5 s at 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 , and 8.65 MB in 1.30 s at ) 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 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 , 66.8% at (matching the first SIFT-1M operating tier of Table 1), and 73.0% at — 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 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 , and 98.0% at . 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 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 , recall is a function of alone, and each backend’s wire cost is a deterministic function of 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 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 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 . Over the sweep, 1-recall@10 climbs from 63.4% to 98.5% and is effectively saturated by , 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 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 are highly correlated and the corresponding columns of 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] () or Group LASSO [47] proximal operator for the 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 (), Holo-NN executes blind, privacy-preserving retrieval via a single linear operator requiring measurements in a single non-interactive round trip, with no client-side index state and no pre-processing stream. Because 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]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]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]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]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]Richard G. Baraniuk. Compressive sensing. IEEE Signal Processing Magazine, 24(4):118–121, 2007.
- [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]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]Salomon Bochner. Monotone Funktionen, Stieltjessche Integrale und harmonische Analyse. Mathematische Annalen, 108(1):378–410, 1933.DOI
- [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]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]Emmanuel J. Candès and Terence Tao. Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203–4215, 2005.DOI
- [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]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]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]Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders. Atomic decomposition by basis pursuit. SIAM Review, 43(1):129–159, 2001.
- [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]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]Jon F. Claerbout and Francis Muir. Robust modeling with erratic data. Geophysics, 38(5):826–844, 1973.
- [19]Gabriel Cramer. Introduction à l’analyse des lignes courbes algébriques. Chez les Frères Cramer & Cl. Philibert, 1750.
- [20]Sanjoy Dasgupta, Charles F. Stevens, and Saket Navlakha. A neural algorithm for a fundamental computing problem. Science, 358(6364):793–796, 2017.
- [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]David L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289–1306, 2006.DOI
- [23]David L. Donoho and Iain M. Johnstone. Ideal spatial adaptation by wavelet shrinkage. Biometrika, 81(3):425–455, 1994.DOI
- [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]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]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]Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Birkhäuser / Springer, 2013.DOI
- [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]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]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]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]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]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]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]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]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]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]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]Isaac J. Schoenberg. Metric spaces and positive definite functions. Transactions of the American Mathematical Society, 44(3):522–536, 1938.
- [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]Claude E. Shannon. Communication in the presence of noise. Proceedings of the IRE, 37(1):10–21, 1949.
- [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]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]Gregory K. Wallace. The JPEG still picture compression standard. Communications of the ACM, 34(4):30–44, 1991.
- [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]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]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]Mingxun Zhou, Elaine Shi, and Giulia Fanti. Pacmann: Efficient private approximate nearest neighbor search. In International Conference on Learning Representations (ICLR), 2025.
- [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]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