Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

Peichun Hua; Yunming Xiao

arXiv preprint · 2026

Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

Peichun Hua, Yunming Xiao

Read paper (PDF) arXiv record arXiv PDF

Overview

Spruce studies private dense retrieval when an organization outsources its document index to untrusted cloud servers. It co-designs compact embeddings and cryptographic search to protect corpus and query information while keeping retrieval practical at million-document scale.

Method

Learned binary codes preserve candidates for full-precision reranking. Two-server secure multi-party computation evaluates Hamming distances, and a corpus-calibrated fixed radius selects candidates. Private cluster pruning reduces search work; an owner-operated dealer reduces preprocessing cost.

Spruce architecture with an organization and dealer, two non-colluding search servers, and a client performing private filtering, reranking, and document retrieval. — Private retrieval from an outsourced index: filter, rerank, and fetch across two non-colluding servers. Figure 1 in the paper

Evaluation

Across four corpora containing 383K–5.42M documents, the full-scan configuration reports 0.21–2.97 seconds at 10 Gbps inter-server bandwidth. Private pruning reports 0.06–1.09 seconds while retaining 93.9–97.3% of full-float NDCG. These measurements use the paper’s two-server MPC setting and specified network conditions.

Fixed-radius retrieval quality and candidate counts (128-bit codes)
Corpus	Full-float NDCG@10	Fixed-radius NDCG@10	Median candidates	95th-percentile candidates
Natural Questions	0.5363	0.5250 ± 0.0011	1,952	8,191
DBpedia	0.3996	0.3865 ± 0.0044	1,207	5,749
Climate-FEVER	0.2597	0.2539 ± 0.0020	382	1,055
Webis-Touché	0.2686	0.2549 ± 0.0208	385	5,289

L = 128 rows from Table 3. Fixed radius is calibrated for 95% final-NDCG retention. NDCG values are mean ± standard deviation over five stratified calibration partitions (10 calibration queries for Webis-Touché, 100 otherwise). Full-float values are the matched full-corpus reference. Table 3 in the paper

private dense retrieval
secure multi-party computation
outsourced search
binary embeddings
RAG privacy

Citation

@misc{hua2026spruce,
    title={Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings}, 
    author={Peichun Hua and Yunming Xiao},
    year={2026},
    eprint={2609.03376},
    archivePrefix={arXiv},
    primaryClass={cs.CR},
    url={https://arxiv.org/abs/2609.03376}, 
}