# Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

arXiv: https://arxiv.org/abs/2609.03376 · HTML: https://mlsanity.com/paper/2609.03376/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Privacy and security of RAG, one of 15 directions in Retrieval-augmented generation.
- Builds on 32 of its 91 references that are in the map.
- First posted on arXiv 3 Sep 2026.

## Placed in

- Retrieval-augmented generation / [Privacy and security of RAG](https://mlsanity.com/rag/privacy-and-security-of-rag/)

## Builds on (most cited first, 30 of 32)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers](https://mlsanity.com/paper/2002.10957/) (2020)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [M3-Embedding: Multi-Linguality, Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation](https://mlsanity.com/paper/2402.03216/) (2024)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [CLIMATE-FEVER: A Dataset for Verification of Real-World Climate Claims](https://mlsanity.com/paper/2012.00614/) (2020)
- [Text Embeddings Reveal (Almost) As Much As Text](https://mlsanity.com/paper/2310.06816/) (2023)
- [Sentence Embedding Leaks More Information than You Expect: Generative Embedding Inversion Attack to Recover the Whole Sentence](https://mlsanity.com/paper/2305.03010/) (2023)
- [Central Similarity Quantization for Efficient Image and Video Retrieval](https://mlsanity.com/paper/1908.00347/) (2019)
- [Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications](https://mlsanity.com/paper/1801.03239/) (2018)
- [Feature Learning based Deep Supervised Hashing with Pairwise Labels](https://mlsanity.com/paper/1511.03855/) (2015)
- [One Loss for All: Deep Hashing with a Single Cosine Similarity based Learning Objective](https://mlsanity.com/paper/2109.14449/) (2021)
- [BioRAG: A RAG-LLM Framework for Biological Question Reasoning](https://mlsanity.com/paper/2408.01107/) (2024)
- [Hashing for Similarity Search: A Survey](https://mlsanity.com/paper/1408.2927/) (2014)
- [Deep Unsupervised Image Hashing by Maximizing Bit Entropy](https://mlsanity.com/paper/2012.12334/) (2020)
- [RemoteRAG: A Privacy-Preserving LLM Cloud RAG Service](https://mlsanity.com/paper/2412.12775/) (2024)
- [Deep Triplet Quantization](https://mlsanity.com/paper/1902.00153/) (2019)
- [Learning to Hash with Binary Deep Neural Network](https://mlsanity.com/paper/1607.05140/) (2016)
- [SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search](https://mlsanity.com/paper/1904.02033/) (2019)
- [NASH: Toward End-to-End Neural Architecture for Generative Semantic Hashing](https://mlsanity.com/paper/1805.05361/) (2018)
- [High Performance Logistic Regression for Privacy-Preserving Genome Analysis](https://mlsanity.com/paper/2002.05377/) (2020)
- [Breaking the Layer Barrier: Remodeling Private Transformer Inference with Hybrid CKKS and MPC](https://mlsanity.com/paper/2508.19525/) (2025)
- [Push for Quantization: Deep Fisher Hashing](https://mlsanity.com/paper/1909.00206/) (2019)
- [Locality Sensitive Hashing with Extended Differential Privacy](https://mlsanity.com/paper/2010.09393/) (2020)
- [PIR-RAG: A System for Private Information Retrieval in Retrieval-Augmented Generation](https://mlsanity.com/paper/2509.21325/) (2025)
- [A Highly Accurate Query-Recovery Attack against Searchable Encryption using Non-Indexed Documents](https://mlsanity.com/paper/2306.15302/) (2023)

## Built on by (most cited first, 2 of 2)

- [Semantics Delivery Network: Rethinking Web Retrieval Infrastructure for LLM Agents](https://mlsanity.com/paper/2609.22486/) (2026)
- [Matryoshka Hash Representations for Model-Aware Compact Semantic Retrieval](https://mlsanity.com/paper/2609.07276/) (2026)

## Abstract (arXiv)

Retrieval-Augmented Generation (RAG) has made dense retrieval over large document collections a standard building block. Organizations increasingly outsource vector indexes to untrusted clouds, exposing proprietary corpora and user queries. Cryptographic protection is challenging because each query searches corpus-scale state, causing computation, correlated randomness, and communication to grow with the corpus. At million-document scale, a naive secure implementation takes minutes and about 90 GB of communication per query. Even recent optimized systems require 10--22 seconds. We propose Spruce (Scalable Private Outsourced Retrieval Using Compact Embeddings), which co-designs representations with the cryptographic protocol. Spruce learns compact binary codes that preserve candidates for full-precision reranking, replacing corpus-wide embedding scoring with efficient Hamming-distance computation under two-server multi-party computation (MPC). A corpus-calibrated fixed-radius protocol avoids multi-round candidate selection while preserving retrieval quality. Spruce also provides private cluster pruning, which trades minor quality loss for substantially less computation, and a one-core owner-operated dealer that removes cloud OT preprocessing bottlenecks. Across four corpora containing 383K--5.42M documents, Spruce preserves the original search quality with median candidate sets of only 382--1,952. At 10 Gbps inter-server bandwidth, full scans take 0.21--2.97 seconds, 4.8--6.7× faster than the closest measured prior work. Private pruning takes 0.06--1.09 seconds, achieves 13.1--22.9× speedups, and retains 93.9%--97.3% of full-float NDCG. On the largest corpus, pruning and the dealer jointly improve sustained throughput by 31.5× at 1 Gbps per link.