Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings
On the map: Retrieval-augmented generation → Privacy and security of RAG
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.
Key facts. Cited by 2 papers in the map (data through 7 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.
Builds on
32 of 91 references.
Closest ancestors · 2
Same direction, newest first
- 2025PIR-RAG: A System for Private Information Retrieval in Retrieval-Augmented Generation1 Sep
- 2024RemoteRAG: A Privacy-Preserving LLM Cloud RAG Service17 Dec
Other references · 30
- 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,160
- 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,049
- 2018Representation Learning with Contrastive Predictive Codingcited by 7,662
- 2020Dense Passage Retrieval for Open-Domain Question Answeringcited by 3,779
- 2020MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformerscited by 1,414
- 2020Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hyperspherecited by 1,393
- 2021BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Modelscited by 1,225
- 2024M3-Embedding: Multi-Linguality, Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillationcited by 1,050
- 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 853
- 2020CLIMATE-FEVER: A Dataset for Verification of Real-World Climate Claimscited by 195
- 2023Text Embeddings Reveal (Almost) As Much As Textcited by 189
- 2023Sentence Embedding Leaks More Information than You Expect: Generative Embedding Inversion Attack to Recover the Whole Sentencecited by 81
18 more
- 2019Central Similarity Quantization for Efficient Image and Video Retrievalcited by 77
- 2018Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applicationscited by 67
- 2015Feature Learning based Deep Supervised Hashing with Pairwise Labelscited by 59
- 2021One Loss for All: Deep Hashing with a Single Cosine Similarity based Learning Objectivecited by 43
- 2024BioRAG: A RAG-LLM Framework for Biological Question Reasoningcited by 42
- 2014Hashing for Similarity Search: A Surveycited by 34
- 2020Deep Unsupervised Image Hashing by Maximizing Bit Entropycited by 20
- 2019Deep Triplet Quantizationcited by 16
- 2016Learning to Hash with Binary Deep Neural Networkcited by 13
- 2019SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Searchcited by 12
- 2018NASH: Toward End-to-End Neural Architecture for Generative Semantic Hashingcited by 11
- 2020High Performance Logistic Regression for Privacy-Preserving Genome Analysiscited by 9
- 2019Push for Quantization: Deep Fisher Hashingcited by 6
- 2025Breaking the Layer Barrier: Remodeling Private Transformer Inference with Hybrid CKKS and MPCcited by 6
- 2020Locality Sensitive Hashing with Extended Differential Privacycited by 5
- 2023A Highly Accurate Query-Recovery Attack against Searchable Encryption using Non-Indexed Documentscited by 2
- 2025A Survey on Deep Text Hashing: Efficient Semantic Text Retrieval with Binary Representationcited by 2
- 2020Hiding the Access Pattern is Not Enough: Exploiting Search Pattern Leakage in Searchable Encryptioncited by 1
Built on by
Citing papers per year: 2026: 2.
2 papers.
Similar, not cited
Close in wording, no citation either way
- 2026Pointing the Way, Hiding the Destination: Practical Private Dense Retrieval at Scale
- 2026Quantization Enables Private Dense Retrieval against Malicious Service Providers
- 2026PILLAR: Private Inverted-Index Lexical Lookup for Augmented Retrieval
- 2026Efficient Privacy-Preserving Retrieval Augmented Generation with Distance-Preserving Encryption
- 2026P2RAG: Efficient Privacy-Preserving RAG Service Supporting Arbitrary Top-k Retrieval
- 2025Privacy-Preserving Federated Embedding Learning for Localized Retrieval-Augmented Generation
- 2026PRAG: End-to-End Privacy-Preserving Retrieval-Augmented Generation
- 2023Don't forget private retrieval: distributed private similarity search for large language models