Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

• URL: http://arxiv.org/abs/2609.03376v1
• Date: Thu, 03 Sep 2026 05:19:03 GMT
• Title: Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings
• Abstract summary: Spruce learns compact binary codes that preserve candidates for full-precision reranking.<n>Spruce preserves the original search quality with median candidate sets of only 382--1,952.<n>Private pruning takes 0.06--1.09 seconds, achieves $13.1$--$22.9times$ speedups, and retains $93.9%$--$97.3%$ of full-float NDCG.
• Score: 0.4859781642217615
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.7\times$ faster than the closest measured prior work. Private pruning takes 0.06--1.09 seconds, achieves $13.1$--$22.9\times$ 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\times$ at 1 Gbps per link.

Related papers

• Matryoshka Hash Representations for Model-Aware Compact Semantic Retrieval [0.4859781642217615]
  We introduce Matryoshka Hash Representations (MHR), a two-stage procedure that separates full-width training from prefix organization.<n>MHR reaches.5561 NDCG@10 and.6535 Recall@100 at 32 bytes, surpassing the best baseline of the same budget.<n>The code also strengthens two common pipelines: shortlisting candidates for full-precision reranking, and pruning a low-storage graph index.
  arXiv  Detail & Related papers  (2026-09-07T09:38:28Z)
• Pointing the Way, Hiding the Destination: Practical Private Dense Retrieval at Scale [19.48684574323907]
  Hosted retrieval-augmented generation (RAG) and semantic search allow users to query valuable provider-held corpora.<n>Existing cryptographic approaches either make this costly by processing the entire corpus for every query, or sacrifice quality for efficiency by scanning a few clusters.<n>This shortlist short-circuits full-corpus cryptographic search without sacrificing retrieval quality.
  arXiv  Detail & Related papers  (2026-08-26T12:46:36Z)
• Towards Retrieving Interaction Spaces for Agentic Search [62.666902610940525]
  Recent direct corpus (DCI) work shows that agents can interact with the raw corpus through shell tools such as 5.4 interaction and file reads.<n>We argue that the role of retrieval for agentic search is not just to select documents that fit in the LLM context window, but to construct an interaction space.
  arXiv  Detail & Related papers  (2026-06-05T03:47:40Z)
• No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval [51.43543998583709]
  Single-stage Sparse Retrieval (SSR) is a paradigm shift that replaces expensive clustering with efficient sparse coding.<n>It reduces indexing time by 15x compared to ColBERTv2, halves retrieval latency, and simultaneously improves retrieval performance.
  arXiv  Detail & Related papers  (2026-05-28T15:53:34Z)
• Practical Code RAG at Scale: Task-Aware Retrieval Design Choices under Compute Budgets [1.933829683108616]
  We study retrieval design for code-focused generation tasks under realistic compute budgets.<n>We compare retrieval configurations across various context window sizes along three axes: (i) chunking strategy, (ii) similarity scoring, and (iii) splitting granularity.
  arXiv  Detail & Related papers  (2025-10-23T14:40:11Z)
• Hierarchical Patch Compression for ColPali: Efficient Multi-Vector Document Retrieval with Dynamic Pruning and Quantization [0.0]
  Multi-vector document retrieval systems, such as ColPali, excel in fine-grained matching for complex queries but incur significant storage and computational costs.<n>We propose HPC-ColPali, a grained Patch Compression framework that enhances the efficiency of ColPali while preserving its retrieval accuracy.<n>Our approach integrates three innovative techniques: (1) K-Means quantization, which compresses patch embeddings into 1-byte centroid indices, achieving up to 32$times$ storage reduction; (2) attention-guided dynamic pruning, utilizing Vision-Language Model attention weights to retain only the top-$p%$ most
  arXiv  Detail & Related papers  (2025-06-19T08:45:52Z)
• SecONNds: Secure Outsourced Neural Network Inference on ImageNet [0.0]
  We introduce SecONNds, a non-intrusive secure inference framework optimized for large ImageNet-scale Convolutional Neural Networks.<n>Our novel protocol achieves an online speedup of 17$times$ in nonlinear operations compared to state-of-the-art solutions.<n>We also present SecONNds-P, a bit-exact variant that ensures verifiable full-precision results in secure computation.
  arXiv  Detail & Related papers  (2025-06-13T08:49:39Z)
• RemoteRAG: A Privacy-Preserving LLM Cloud RAG Service [10.383191657228826]
  We are the first to formally define the privacy-preserving cloud RAG service to protect the user query.<n>For privacy, we introduce $(n,epsilon)$-DistanceDP to characterize privacy leakage of the user query and the leakage inferred from relevant documents.<n>For efficiency, we limit the search range from the total documents to a small number of selected documents related to a perturbed embedding generated from $(n,epsilon)$-DistanceDP.
  arXiv  Detail & Related papers  (2024-12-17T10:36:52Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder.<n>We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Sparse R-CNN: End-to-End Object Detection with Learnable Proposals [77.9701193170127]
  We present Sparse R-CNN, a purely sparse method for object detection in images. Final predictions are directly output without non-maximum suppression post-procedure. We hope our work could inspire re-thinking the convention of dense prior in object detectors.
  arXiv  Detail & Related papers  (2020-11-25T00:01:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.