Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

Summary

Spruce lets an organization outsource its vector index to cloud servers that learn neither the documents nor the queries. Retrieval-augmented generation (RAG) depends on dense retrieval, and a cloud that stores the index sees the corpus and the questions users ask. Spruce encodes documents as compact binary codes and searches them with two-server secure multi-party computation (MPC, a way for servers to compute on secret-shared data). On corpora of up to 5.42 million documents, a full scan takes 0.21 to 2.97 seconds at 10 Gbps between servers, 4.8 to 6.7 times faster than the closest measured prior system.

Key numbers

• 0.21–2.97 sFull-scan query time on four corpora of 383K to 5.42M documents at 10 Gbps, 4.8–6.7× faster than the closest measured prior work
• 93.9–97.3%Share of full-float NDCG@10 retained by private cluster pruning, which takes 0.06–1.09 s per query
• 31.5×Throughput gain at 1 Gbps per link on the largest corpus when private pruning and the owner-operated dealer are combined

Method

Dense retrieval, which finds the documents whose embedding vectors are nearest to a query's, is the first step of RAG ^[1]. A cloud that hosts such an index holds the proprietary corpus and a stream of queries that reveal user intent, and embeddings can be inverted to recover text ^[2]. A naive secure implementation of cosine scoring over one million 768-dimensional embeddings takes about 9.4 minutes and 88 GB of communication per query. Spruce has three roles: a data owner who encodes and indexes the corpus once, two servers that store secret shares of the index, and a trusted client that issues queries. The servers are semi-honest and non-colluding, meaning each follows the protocol and may inspect its own view, and the two do not share views. The closest prior system in setting, p²RAG ^[4], also secret-shares the embeddings across two non-colluding servers but securely scores every full embedding.

The search runs in three stages. In the filter stage, the servers compute the Hamming distance (the number of differing bits) between the shared query code and every shared corpus code under Boolean MPC. This needs only an XOR and a small popcount, so the dominant per-document step requires no communication. A single radius, calibrated on the corpus so that final quality is preserved, selects the candidate set. In the rerank stage, the client reconstructs the candidates' full embeddings and scores them locally against the full-precision query, which it never released. In the fetch stage, the client retrieves the chosen documents by two-server private information retrieval (PIR, which hides which item was requested), so neither server learns which documents were returned.

Two options target deployment costs. Private cluster pruning scans only selected clusters, trading a small quality loss for much less computation. An owner-operated dealer, a single CPU core on the data owner's side, supplies the correlated randomness that MPC consumes, which removes cloud oblivious transfer as the preprocessing bottleneck.

Evaluation

The evaluation uses four BEIR ^[3] corpora: Natural Questions, DBpedia, Climate-FEVER, and Webis-Touché, spanning 383K to 5.42M documents. With 128-bit codes, the fixed-radius filter keeps 95.2 to 97.8% of full-float NDCG@10, the ranking quality of the top 10 results, with median candidate sets of 382 to 1,952 documents. The online filter takes 183 ms to 2.60 s, three orders of magnitude less than int8 cosine under MPC.

At 10 Gbps between servers, the full scan takes 0.21 to 2.97 s, which is 4.8 to 6.7 times faster than the closest completed baseline on each corpus. Private pruning takes 0.06 to 1.09 s, 13.1 to 22.9 times faster, and retains 93.9 to 97.3% of full-float NDCG. On Climate-FEVER at 1 Gbps, pruning alone raises throughput 4.9 times and the dealer 5.2 times, and the two together raise it 31.5 times.

Security model and limitations

The security guarantee covers semi-honest, non-colluding servers. Malicious or colluding servers are outside the model, and Spruce does not rely on trusted hardware such as a server-side TEE. The servers still learn a coarse access pattern: each full scan reveals the candidate set as a set of permuted slots. A co-occurrence attack on repeated scans predicts neighbor relations among encrypted slots with a conditional precision@10 of 0.017 to 0.070 on held-out workloads and 0.099 to 0.280 under a stress test of 20,000 queries. A client-side padding variant reduces the stress figure by 39 to 57%.

The quality results come from four BEIR corpora and a radius calibrated on 100 queries per corpus (ten for Webis-Touché). Pruning gives up some quality for speed, and the timings assume the stated two-server network of 1 to 10 Gbps.

Citation

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

References

1. Patrick Lewis et al. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. NeurIPS, 2020. arxiv.org/abs/2005.11401
2. John X. Morris, Volodymyr Kuleshov, Vitaly Shmatikov, and Alexander M. Rush. Text Embeddings Reveal (Almost) As Much As Text. EMNLP, 2023. arxiv.org/abs/2310.06816
3. Nandan Thakur et al. BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models. NeurIPS Datasets and Benchmarks, 2021. arxiv.org/abs/2104.08663
4. Yulong Ming et al. P²RAG: Efficient Privacy-Preserving RAG Service Supporting Arbitrary Top-k Retrieval. arXiv, 2026. arxiv.org/abs/2603.14778