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

Oct 1, 2025

Panorama: Fast-Track Nearest Neighbors

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.

Vansh Ramani, Alexis Schlomer, Akash Nayar +3

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

Product Quantization Approximate Nearest Neighbor Search

Ask PDF

Mar 1, 2026

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

Approximate Nearest Neighbor Search (ANNS) is fundamental to modern AI applications. Most existing solutions optimize query efficiency but fail to align with the practical requirements of modern workloads. In this paper, we outline six critical demands of modern AI applications: high query efficiency, fast indexing, low memory footprint, scalability to high dimensionality, robustness across varying retrieval sizes, and support for online insertions. To satisfy all these demands, we introduce Projection-Augmented Graph (PAG), a new ANNS framework that integrates projection techniques into a graph index. PAG reduces unnecessary exact distance computations through asymmetric comparisons between exact and approximate distances as guided by projection-based statistical tests. Three key components are designed and integrated into the graph index to optimize indexing and searching. Experiments on six modern datasets demonstrate that PAG consistently achieves superior queries per second (QPS)-recall performance -- up to 5x faster than HNSW -- while offering fast indexing speed and moderate memory footprint. PAG remains robust as dimensionality and retrieval size increase and naturally supports online insertions.

Kejing Lu, Zhenpeng Pan, Jianbin Qin +2

University of Yamanashi · Beijing Institute of Technology, Zhuhai · Shenzhen University +2

Approximate Nearest Neighbor Search Graph-Based Retrieval

Ask PDF

Apr 22, 2026

Onyx: Cost-Efficient Disk-Oblivious ANN Search

Approximate nearest neighbor (ANN) search in AI systems increasingly handles sensitive data on third-party infrastructure. Trusted execution environments (TEEs) offer protection, but cost-efficient deployments must rely on external SSDs, which leaks user queries through disk access patterns to the host. Oblivious RAM (ORAM) can hide these access patterns but at a high cost; when paired with existing disk-based ANN search techniques, it makes poor use of SSD resources, yielding high latency and poor cost-efficiency. The core challenge for efficient oblivious ANN search over SSDs is balancing both bandwidth and access count. The state-of-the-art ORAM-ANN design minimizes access count at the ANN level and bandwidth at the ORAM level, each trading-off the other, leaving the combined system with both resources overutilized. We propose inverting this design, minimizing bandwidth consumption in the ANN layer and access count in the ORAM layer, since each component is better suited for its new role: ANN's inherent approximation allows for more bandwidth efficiency, while ORAM has no fundamental lower bounds on access count (as opposed to bandwidth). To this end, we propose a cost-efficient approach, Onyx, with two new co-designed components: Onyx-ANNS introduces a compact intermediate representation that proactively prunes the majority of bandwidth-intensive accesses without hurting recall, and Onyx-ORAM proposes a locality-aware shallow tree design that reduces access count while remaining compatible with bandwidth-efficient ORAM techniques. Compared to the state-of-the-art oblivious ANN search system, Onyx achieves

1.7-9.9\times

lower cost and

2.3-12.3\times

lower latency.

Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao +2

UC Berkeley, NVIDIA · NVIDIA · UT Austin, NVIDIA +1

Privacy-Preserving ML Approximate Nearest Neighbor Search

Ask PDF

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