Holo-NN: Holographic Nearest Neighbor Search via Compressive Sensing

Bryant Gipson

cs.CROct 23, 2026

Holo-NN: Holographic Nearest Neighbor Search via Compressive Sensing

Authors: Bryant Gipson

Organizations: Google

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.

Figures & tables

Dataset	Metric Space & Transform	$N$	$D$	$B$	Regime	$M$	$M/N$	$K^{*}$	Rec@1	Rec@ $K^{*}$	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%

Table 1: Multi-Scale Benchmark Results across 4 Datasets and 4 Operating Tiers (

M,K^{*}

). Rec@

k

is 1-recall@

k

: the fraction of queries whose true nearest neighbor appears among the top

k

candidates returned by FISTA.

Execution surface	Wire / query	Latency	Server keys
Plaintext (no encryption)	$0.16\text{ MB}$	$1.14\text{ s}$	$0\text{ MB}$
Holo-NN: LinPIR (CPU, BFV [ 31 ] exact-int.)	$\mathbf{31.41\text{ MB}}$	$\mathbf{3.29\text{ s}}$ ( $4.39\text{ s}^{\mathsection}$ )	$\mathbf{0\text{ MB}}$
Holo-NN: CKKS-CPU (OpenFHE [ 1 ] , 12-thr)	$1.60\text{ MB}$	$32.9\text{ s}$	$299\text{ MB}^{\star}$
Holo-NN: CKKS-GPU (Phantom [ 45 ] , $1\times$ RTX 3090)	$\mathbf{1.60\text{ MB}}$	$\mathbf{1.68\text{ s}}^{\diamond}$	$85\text{ MB}^{\star}$
Holo-NN: HEIR-GPU (Cheddar [ 3 , 17 ] , $1\times$ RTX 3090)	$\mathbf{0.79\text{ MB}}$	$\mathbf{0.134\text{ s}}^{\ddagger}$	$\mathbf{75\text{ MB}}^{\star}$

Table 2: Deployed encrypted Wikipedia-500k demonstrator (

N=500{,}000

B=8{,}192

M=32{,}768

4

blocks of

8{,}192\times 8{,}192

). Latency is end-to-end wall clock; wire cost is total serialized request plus response ciphertexts.

							Retrieval Quality
System	Mechanism & Hardware	RTT	Wire / query	Client / Server State	Latency	Benchmark ( $N$ )	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\text{ GB}^{\dagger}$	no offline hints	$1.55\text{--}45.3\text{ s}$	SIFT-1M ( $1\mathrm{M}$ )	—	—	$\approx 90\%$	—
PRECO (IEEE S&P ’22) [ 40 ]	LSH + DPF ( 2 non-colluding servers , 32-thr)	$1^{\mathsection}$	$1.5\text{ MB}^{\mathsection}$	2-srv DB replica	$1.1\text{--}28.2\text{ s}^{\mathsection}$	SIFT-1M ( $1\mathrm{M}$ )	—	—	$\approx 95\%$	—
Tiptoe (SOSP ’23) [ 29 ]	LHE + PIR ( public DB, 45-srv CPU)	$2^{\dagger}$	$59.7\text{ MB}^{\dagger}$	$0.29\text{ GiB}$ model+centroids	$2.7\text{ s}$	Common Crawl ( $364\mathrm{M}$ )	— ∗	—	—	—
Pacmann (ICLR ’25) [ 48 ]	Sublinear PIR ( public DB, CPU)	$20$	$61.6\text{ MB}^{\dagger}$	$0.6\text{ GB}$ client ( $2.7\text{ GB}$ init)	$1.1\text{ s}$	MS MARCO ( $3.2\mathrm{M}$ )	$0.266^{\ast}$	—	—	—
Pacmann (ICLR ’25) [ 48 ]	Sublinear PIR ( public DB, CPU)	$32$	$413.8\text{ MB}^{\dagger}$	$2.9\text{ GB}$ client ( $59.6\text{ GB}$ init)	$1.6\text{--}3.0\text{ s}$	SIFT ( $100\mathrm{M}$ )	—	—	$\approx 90\%$	—

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

N

. 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:

\lvert\text{ours}_{1:10}\cap\text{true}_{1:10}\rvert/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).

$M$	Cheddar 32b	Cheddar GPU	CKKS 64b	LinPIR Wire	1-r@1	1-r@10	10-r@10	10-r@50	MRR@10
$98{,}300$	$\mathbf{2.10\text{ MB}}$	$\mathbf{0.26\text{ s}}$	$4.24\text{ MB}$	$91.1\text{ MB}$	$32.5$	$63.4$	$\mathbf{33.3}$	$57.0$	$\mathbf{0.417}$
$150{,}000$	$\mathbf{3.01\text{ MB}}$	$\mathbf{0.42\text{ s}}$	$6.36\text{ MB}$	$135.8\text{ MB}$	$40.5$	$75.8$	$\mathbf{43.8}$	$72.5$	$\mathbf{0.518}$
$200{,}000$	$\mathbf{3.80\text{ MB}}$	$\mathbf{0.54\text{ s}}$	$7.95\text{ MB}$	$179.0\text{ MB}$	$48.2$	$84.2$	$\mathbf{51.8}$	$82.0$	$\mathbf{0.601}$
$250{,}000$	$\mathbf{4.59\text{ MB}}$	$\mathbf{0.67\text{ s}}$	$9.54\text{ MB}$	$222.2\text{ MB}$	$53.5$	$89.3$	$\mathbf{57.3}$	$88.0$	$\mathbf{0.652}$
$300{,}000$	$\mathbf{5.37\text{ MB}}$	$\mathbf{0.82\text{ s}}$	$11.13\text{ MB}$	$265.4\text{ MB}$	$58.2$	$93.0$	$\mathbf{61.6}$	$92.0$	$\mathbf{0.702}$
$327{,}600$	$\mathbf{5.77\text{ MB}}$	$\mathbf{0.86\text{ s}}$	$11.66\text{ MB}$	$289.2\text{ MB}$	$59.7$	$93.3$	$\mathbf{63.8}$	$93.0$	$\mathbf{0.718}$

Table 4: Holo-NN on SIFT-1M (

N=10^{6}

D=128

B=16{,}384

), 1,000 official queries, 80 FISTA iterations. Cheddar 32b Wire (and RTX 3090 server GPU latency Cheddar GPU ) uses two

256\text{ KiB}

32-bit RNS query ciphertexts plus

\lceil M/8192\rceil\times 128\text{ KiB}

single-limb responses; CKKS 64b Wire (OpenFHE/Phantom) is

1.05\text{ MB}

query plus

\lceil M/16384\rceil\times 0.53\text{ MB}

responses; LinPIR Wire is

6.19\text{ MB}

inline key+query upload plus

\lceil M/4096\rceil\times 3.54\text{ MB}

BFV responses (zero persistent server keys).

Approximate Nearest Neighbor Search

Approximate nearest neighbor search finds close vectors without exhaustive comparisons, enabling scalable retrieval in high-dimensional datasets.

See all 43 papers

Panorama: Fast-Track Nearest Neighbors
Oct 1, 2025Vansh Ramani, Alexis Schlomer, Akash Nayar +3Product Quantization Approximate Nearest Neighbor Search
IIT Delhi & CMU & UCPH · Carnegie Mellon University · Indian Institute of Technology Delhi +1
Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach
Mar 1, 2026Kejing Lu, Zhenpeng Pan, Jianbin Qin +2Approximate Nearest Neighbor Search Graph-Based Retrieval
University of Yamanashi · Beijing Institute of Technology, Zhuhai · Shenzhen University +2
Onyx: Cost-Efficient Disk-Oblivious ANN Search
Apr 22, 2026Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao +2Privacy-Preserving ML Approximate Nearest Neighbor Search
UC Berkeley, NVIDIA · NVIDIA · UT Austin, NVIDIA +1

Oct 1, 2025J/K move · Enter open · S save

Panorama: Fast-Track Nearest Neighbors

Vansh Ramani, Alexis Schlomer, Akash Nayar, Sayan Ranu+2

IIT Delhi & CMU & UCPH · Carnegie Mellon University · Indian Institute of Technology Delhi+1

Product Quantization Approximate Nearest Neighbor Search

Open paper AskPDF arXiv

Approximate Nearest-Neighbor Search (ANNS) pipelines for high-dimensional neural embeddings spend the bulk of their query time in candidate verification, making it the primary bottleneck in the search process. In this paper, we present PANORAMA, a state-of-the-art refinement technique that accelerates verification by exploiting the inherent spectral decay of these embeddings. Using PCA to compact signal energy, PANORAMA evaluates candidate distances incrementally, computing at each step a strict lower bound on the full-vector distance and dynamically pruning candidates the moment this bound exceeds the running k-th nearest neighbor distance. While PCA's concentration of variance facilitates pruning, it breaks the uniform-variance assumption required by Product Quantization (PQ); we resolve this with a variance-shaping step that redistributes energy across subvectors, rendering accretive refinement compatible with quantized indexes. Optimized for modern memory hierarchies via vectorized bulk-pruning and cache-conscious data layouts, PANORAMA has been upstreamed into the FAISS library across major index families (IVFPQ/Flat, HNSW, and Refine). PANORAMA achieves higher QPS at any target recall with a cost that provably scales inversely with dataset spectral decay, delivering end-to-end speedups of up to 28.9x and outperforming probabilistic methods across all recall bands.

Abstract

Approximate Nearest Neighbor Search

Explore similar work

Panorama: Fast-Track Nearest Neighbors

Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach

Onyx: Cost-Efficient Disk-Oblivious ANN Search