Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

arXiv:2609.03376v1 Announce Type: cross Abstract: 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.7imes faster than the closest measured prior work. Private pruning takes 0.06--1.09 seconds, achieves 13.1--22.9imes 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.5imes at 1 Gbps per link.

Related

• Auditing Privacy in Multi-Tenant RAG under Account Collusion
• CleanBase: Detecting Malicious Documents in RAG Knowledge Databases
• Membership Inference Attacks for Retrieval Based In-Context Learning for Document Question Answering
• Budget-Constrained Online Retrieval-Augmented Generation: The Chunk-as-a-Service Model

Source: arXiv cs.LG | 2026-09-04