Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

Peichun Hua; Yunming Xiao

Source-linked AI summary

Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

Peichun Hua, Yunming Xiao

arXiv:2609.03376v1Sep 3, 2026cs.CRcs.IRcs.LG

TL;DR

Outsourced dense retrieval must protect proprietary corpora and private queries without making corpus-scale search impractical. Spruce co-designs compact learned binary codes with two-server MPC, calibrated fixed-radius filtering, client-side reranking, and oblivious fetching. Across corpora up to 5.42M documents, it preserves most full-float retrieval quality while substantially accelerating full scans and private pruning.

Problem
Outsourced retrieval must protect sensitive corpora and queries while keeping corpus-scale search within practical latency and throughput limits.
Method
Spruce co-designs compact learned binary codes with secure filtering, full-precision candidate reranking, and oblivious document fetching.
Results
Spruce retains 95.2–97.8% of full-corpus float NDCG with median candidate sets of 382–1,952 across four corpora.
Takeaways & Limitations
Private pruning and an owner-operated dealer jointly improve sustained throughput by 31.5× on the largest corpus at 1 Gbps per link.
Takeaways & Limitations
Spruce excludes malicious or colluding servers and permits coarse corpus access-pattern leakage under its stated threat model.

Abstract

from arXiv · show

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.

1 Introduction

Spruce addresses the privacy and scalability challenge of outsourced dense retrieval by co-designing compact binary representations with a two-server MPC protocol. It combines calibrated filtering, client-side reranking, oblivious fetching, and optional deployment optimizations to retain retrieval quality at corpus scale.

Motivation: Outsourced retrieval exposes proprietary corpora and private query intent, while corpus-scale secure search makes practical latency and throughput difficult.At one million documents, secure int8 cosine requires N·D secure multiplications and takes approximately 9.4 minutes with approximately 88 GB of communication per query.
Approach: Spruce separates retrieval into a corpus-wide secure filter over compact binary codes and a candidate-only exact reranking stage.The client reranks candidate embeddings with full precision and fetches final encrypted documents through two-server PIR.
Approach: Hamming-distance filtering replaces full-embedding secure multiplications with roughly L·N Boolean ANDs, making code length a direct gate-budget knob.The filter computes Hamming distance using XOR and popcount, while learned codes outperform the 768-bit sign-of-float baseline at lower gate cost.
Approach: Spruce calibrates a fixed Hamming radius offline to avoid data-dependent candidate-selection rounds while targeting final reranking quality.The calibration finds the smallest radius reaching a target final NDCG after float reranking.
Deployment optimizations: Private pruning and an owner-operated dealer reduce deployment cost by restricting filtering to padded clusters and removing cloud OT preprocessing bottlenecks.The optimizations are composable and independently disableable.
Results: Across four corpora, Spruce retains 95.2–97.8% of full-corpus float NDCG with median candidate sets of 382–1,952 and full-scan speedups of 4.8–6.7×.Private pruning reaches 13.1–22.9× speedups while retaining 93.9–97.3% of full-float NDCG; pruning and the dealer jointly improve sustained throughput by 31.5× on the largest corpus.

2 Background and Threat Model

The paper reviews dense retrieval, MPC, and PIR foundations, then defines Spruce's two-server threat model and permitted leakage. Its design relies on non-colluding semi-honest servers, secret sharing, and oblivious access to outsourced retrieval state.

Dense retrieval: Dense retrieval encodes queries and documents into a shared D-dimensional space, scores the static N×D index, and returns top-k results for RAG prompts.Recall@k measures retrieved gold documents, while NDCG@k weights graded relevance by rank.
Private search challenges: Plain dense indexes expose sensitive embeddings and make data-dependent traversal or corpus-wide scanning difficult to transplant into cryptographic backends.Binary hash codes instead reduce similarity to Hamming distance, consisting of XOR and popcount.
Cryptographic setting: Spruce uses two-server secure computation and PIR in a non-colluding, semi-honest model.The architecture includes owner setup, Boolean-MPC filtering, client-side reranking, and PIR-based fetching of encrypted content.
Cryptographic setting: Secret sharing makes each server's individual share reveal nothing, while local XOR is free and nonlinear AND gates consume Beaver triples and communication.Triple generation occurs offline through oblivious transfer, and its supply rate can bound sustained throughput.
Cryptographic setting: Hamming filtering is cheaper than cosine scoring because XORs are local, whereas cosine similarity requires one charged multiplication per embedding dimension.Thus cosine costs N·D charged multiplications, while Hamming distance spends ANDs mainly on popcount.
Threat model: The threat model protects both corpus and queries from each server but excludes colluding or malicious servers and server-side trusted hardware.Spruce explicitly permits coarse corpus access-pattern leakage and models it through simulation-based leakage functions.

3 System Design

Spruce separates private retrieval into a corpus-wide Hamming-distance filter over learned compact codes, followed by client-side full-precision reranking and oblivious content fetch. Its design reduces secure computation through shorter learned codes, calibrated fixed-radius selection, and optional pruning and dealer-assisted preprocessing.

System architecture: Spruce runs an offline hidden-index setup and an online Filter–Rerank–Fetch pipeline across two non-colluding servers.The owner secret-shares codes and embeddings, while client-encrypted content is replicated to both servers.
Binary representation: A learned 128-bit hash can outperform the 768-bit binary-naive baseline on three of four corpora, with gains of 10.0–62.2%.The hash head preserves candidates for full-precision reranking while decoupling code length L from embedding dimension D.
Binary representation: 3.8× higher online latency and 4.7× higher online traffic make the 768-bit baseline substantially costlier than the 128-bit code at N=4096.Both online cost measures grow roughly linearly with code length L.
Secure filtering: The Hamming Filter costs approximately L·N secure AND gates, making code length a direct corpus-wide circuit budget.A Boolean popcount has O(log L) depth and is the dominant corpus-linear component.
Optional optimizations: Private cluster pruning and a seeded institutional dealer independently reduce deployment work and preprocessing communication, and compose directly.Pruning trades slight quality loss for lower online work; the dealer moves query-independent triple generation from the clouds to an owner-operated service.
Secure filtering: Corpus-calibrated radius selection avoids oblivious top-K sorting and data-dependent online binary search.Calibration chooses the smallest radius reaching a target final NDCG after float reranking.
Rerank and fetch: PIR retrieves only selected encrypted content blobs while servers learn only the coarse candidate set, preserving client-side ranking and plaintext privacy.The client reconstructs candidate embeddings, reranks them locally, and fetches chosen ciphertexts through two-server PIR.

4 Leakage Analysis

Spruce explicitly characterizes what each server can learn, while keeping codes, embeddings, queries, rankings, and content hidden. Repeated full scans can still expose approximate unlabeled document neighborhoods through access patterns, though measured reconstruction precision remains low.

Spruce’s setup leakage includes public dimensions, fixed row width, and protocol parameters, while full scans additionally reveal the public radius and permuted physical slots.
Private pruning hides bucket IDs and exposes only fixed scan dimensions plus an indicator vector for the transient shared bucket buffer.
Codes, embeddings, query bits, selected cluster IDs, within-candidate ranking, and fetched content remain hidden from either server.
Repeated full-scan candidate sets can reveal approximate unlabeled document neighborhoods despite the protocol hiding codes, embeddings, rankings, content, and queries.
At L=128, conditional precision@10 is 0.017–0.070 on held-out workloads and 0.099–0.280 under a 20k-query coverage stress.Client-side hidden padding lowers the stress result by 39–57% at padding ratio r=2.

5 Evaluation

Evaluation across four BEIR corpora shows that compact binary filtering preserves retrieval quality while substantially reducing secure computation, communication, and latency. Private pruning and an owner-operated dealer further improve deployment efficiency and throughput.

5.1 Implementation and Setup: Spruce evaluates four BEIR corpora from 383K to 5.42M documents using code widths of 96, 128, and 256 bits, with calibration and evaluation performed on separate query sets.The fixed pruning configuration uses 256 clusters, capacity factor 1.2, and 43 probes.
5.2 Retrieval Quality: 95.2–97.8% of full-corpus float NDCG is retained at 128 bits, with median candidate sets of 382–1,952.At 128 bits, final NDCG retention remains above 0.952 even when float top-10 candidate recall ranges from 0.672 to 0.947.
5.2 Retrieval Quality: The fixed-radius filter is a candidate proposer rather than a final ranker: its hash-only floor remains far below the reranked result, especially at 96 bits.The evaluation therefore distinguishes candidate generation from full-precision reranking.
5.3 Protocol Overhead: At 128 bits, FR answers in 183 ms–2.60 s with 32.9–465.8 MB, yielding a 1,173× latency reduction and approximately 1,022× lower communication than DFP.FR replaces corpus-wide secure arithmetic multiplications with XOR and a 128-bit popcount.
5.3 Protocol Overhead: FR is 2.9–3.0× faster than BS and moves 1.4× less data because one pre-calibrated threshold replaces eight data-dependent count reveals.On Webis, FR uses 27 MPC rounds versus BS’s 531.
5.3 Protocol Overhead: Reranking adds 0.59–3.00 MB, below 2% of filter traffic, while two-server PIR fetch remains far from bottlenecking the pipeline at k=10.The client downloads only selected blobs rather than all candidate content.
5.4 Online Latency and Scaling: At 10 Gbps, full scans are 4.8–6.7× faster than the closest completed baseline, while pruning lowers latency to 61–1,090 ms and achieves a 13.1–22.9× advantage with 93.9–97.3% NDCG retention.The full scan scales from 0.482 s at 10^6 documents to 4.85 s at 10^7 documents for 128-bit FR.
5.5 Optional Optimizations Across Deployments: Pruning scans about 20% of the corpus, while the dealer supplies triples using one owner-side CPU core without changing retrieval quality.The optimizations are independently disableable and compose directly.

6 Related Work

Related systems protect different parties or optimize different search stages. Spruce targets client-owned outsourced retrieval with two non-colluding servers, binary representations, fixed-radius filtering, and private fetching.

Two-server private retrieval: p2RAG shares outsourced embeddings across two non-colluding servers but still securely scores every full embedding and uses interactive bisection.Spruce instead uses binary representations and fixes the radius before the online protocol.
Alternative privacy settings: Single-provider systems such as SANNS, PANTHER, Pisces, and RemoteRAG address different corpus-ownership or query-privacy assumptions using combinations of clustering, PIR, MPC, HE, or query perturbation.Their objectives differ from protecting both the outsourced corpus and encoded query in the client-owned setting.
Alternative privacy settings: Query-privacy systems for public or provider-available corpora include Tiptoe, Wally, Speakeasy, PACMANN, and PIR-RAG.These systems focus on protecting the querier when the corpus is public or available to the search service.
Hash-based private search: MESS searches randomized hash codes but exposes perturbed codes, shard assignments, graph topology, traversal traces, and candidate sets, with 16× indexed-record replication in its default configuration.Its privacy loss also composes across 16 independently perturbed releases.
Deep hashing: Spruce repurposes learned binary codes as an MPC-friendly representation, whereas prior deep-hashing work primarily supports plaintext search or randomized privacy mechanisms.The paper co-designs compact-code training with secure retrieval rather than treating hashing as a separate preprocessing step.

7 Conclusion

Spruce addresses corpus-linear private outsourced retrieval by co-designing compact learned codes with the secure protocol. Its calibrated fixed-radius filter, private pruning, and owner-side dealer preserve retrieval quality while improving latency and throughput at million-document scale.

Conclusion: Spruce combines short learned codes, a calibrated Hamming radius, and two-server PIR to reduce corpus-wide secure retrieval cost while retaining high-quality candidates for reranking.The 128-bit configuration retains 95.2–97.8% of float NDCG with median candidate sets of 382–1,952.
Conclusion: At 1 Gbps, private clustering and the one-core owner-side dealer jointly improve Climate-FEVER throughput by 31.5×, while the organization stores no retrieval index locally.Pruning trades minor quality loss for lower demand, and the dealer accelerates triple supply while retaining cloud-OT fallback.

A More Details of Candidate-Generation Protocols

This section compares direct full-precision scoring with binary-search radius selection and fixed-radius candidate generation. The direct baseline remains structurally tied to N·D arithmetic work, while the appendix details its measured breakdown and extrapolation.

ΠDFP (direct full precision): ΠDFP directly secret-shares int8 embeddings and computes N·D Beaver multiplications before a shared top-k operation.Its online protocol batches inner products into two rounds, followed by repeated shared argmax rounds.
ΠBS (binary-search radius): ΠBS adds ⌈log2(L+1)⌉ comparator-plus-count rounds to the shared popcount and reveals cumulative counts during radius search.Each reveal leaks a sample of the corpus distance CDF, while the reveal rounds dominate latency on bandwidth-limited links.
DFP step breakdown: Above N=256, ΠDFP wall-clock stays within 6% of 562 μs/doc and communication converges to 87.9 KB/doc.The reported extrapolation uses the measured N=4096 anchor because materializing arithmetic triples for BEIR-scale runs is infeasible on the measured machine.
DFP step breakdown: The DFP baseline table covers D=768, k=10, online-only arithmetic MPC with batched inner products and shared top-k.Corpus embeddings and queries are additive-shared during offline setup.

B Leakage: Formal Simulation Security and Relational Analysis

This section formalizes Spruce’s leakage and adaptive simulation security, then measures ciphertext-only relational inference and hidden-padding effects. The analysis identifies what access patterns remain visible and how padding changes the observed signal.

B.2 Simulation Security: The theorem assumes IND-CPA encryption, secure Boolean MPC, secure non-reused Beaver-triple preprocessing, and independent-selector two-server XOR-PIR.The result applies to one semi-honest corrupted server; colluding servers reconstruct shared codes and embeddings, although encrypted content remains confidential without the key.
B.2 Simulation Security: Under assumptions (A1)–(A4), Theorem B.4 gives an adaptive multi-query simulation for both full and pruned variants against one corrupted server.The simulator receives leakage online in query order, and the proof is organized through hybrids H0–H5.
B.2 Simulation Security: The simulation replaces encrypted content with equal-length encryptions of zeros, samples uniform XOR shares, and preserves repeated-row equality and overlap across queries.PIR responses retain their algebraic dependence on the simulated database rather than being replaced by independent random strings.
B.3 Ciphertext-only Relational Inference: Full-scan candidate sets form Hamming balls whose repeated stable slot identities induce a kernel-blurred proximity statistic over encrypted slots.Tighter radii sharpen conditional neighborhoods, while loose radii broaden them; slots never observed in candidate sets provide no incidence edge.
B.3 Ciphertext-only Relational Inference: The ciphertext-only experiment excludes plaintext corpora, slot mappings, and query-to-plaintext anchors, isolating relational leakage from auxiliary-information attacks.Held-out queries and coverage-stress workloads measure this leakage under different observed corpus scopes.
B.3 Ciphertext-only Relational Inference: The incidence estimator uses candidate-set membership columns, cosine similarity between slot incidences, and P@10 against true Hamming-distance neighbors.The evaluation samples five independent permutations and up to 1,500 anchor slots, with popularity as a null baseline.
B.3 Ciphertext-only Relational Inference: At L=128, held-out P@10 is 0.017–0.070, while coverage stress reaches 0.099–0.280 and longer codes reduce every stress result.Held-out NQ observes 76.0% of slots versus 2.4% for Climate-FEVER; five-seed standard deviation is at most 0.0073.
B.4 Hidden Candidate Padding: Hidden-padding simulation remains secure under the same assumptions, while server-visible union padding at r=2 reduces P@10 by 39–57% with a 0.24–1.10% revealed fraction.Ratio padding still reveals candidate-set size up to deterministic rounding, whereas fixed-target padding fixes response length subject to an overflow policy.

B.1 Experiments and Leakage Functions

Spruce’s leakage analysis defines a random physical layout, fixed-radius full-scan leakage, and hidden pruned buffers. The protocols expose selected permuted slots or controlled indicators while hiding logical identities and bucket mappings.

B.1 Experiments and Leakage Functions: Setup samples a database-independent permutation, pads content rows to a public width, and distributes permuted code, embedding, and ciphertext rows to both servers.The client retains the encryption key and permutation, while public dimensions and protocol parameters are exposed.
B.1 Experiments and Leakage Functions: The permutation, pre-padding plaintext lengths, hash-prefix order, and cluster membership are absent from setup leakage.This separates public layout parameters from logical corpus organization.
B.1 Experiments and Leakage Functions: A full-scan query computes Hamming distances d_q,i and returns the set K_q of permuted slots within the public radius.Its leakage includes stable permuted slot identities, candidate-set size, and equality of response sets across queries.
B.1 Experiments and Leakage Functions: Private pruning evaluates shared Hamming indicators over a freshly randomized padded buffer of bucket contents.Selected bucket identifiers and the buffer-position-to-persistent-slot map remain hidden, with fresh selector and correction shares preventing cross-query linkage.
B.1 Experiments and Leakage Functions: The complete leakage for adaptive queries is defined as an ordered sequence of per-query leakage tuples, including the protocol-specific outputs and access information.The formal definitions distinguish full-scan and pruned-scan leakage rather than treating them as the same observation.
B.1 Experiments and Leakage Functions: Binary-search selection reveals ⌈log2(L+1)⌉ cumulative counts before revealing its final candidate set, whereas fixed-radius selection omits those intermediate count pairs.The two protocols have different selection functions, so their leakage tuples are not generally ordered by set inclusion.
C PIR Fetch Overhead: The Fetch step uses two-server PIR over replicated ciphertext and adds zero secure-computation gates, zero Beaver triples, and one network round.For 10-KB blobs, client-facing traffic is 206–210 KB and represents 0.04–0.63% of Filter traffic.

D Deep Hash Training: Configuration and Design Space

This appendix expands the details for reproducing the hash model training, but the supplied passage provides no further configuration or design-space results.

The appendix provides expanded details for reproducing hash model training.

D.1 Training Configuration

Training combines LoRA encoder adaptation, a linear hash head, cached hard-negative mining, and gradual soft-to-hard code annealing. The deployed configuration uses 128-bit codes while evaluating alternative widths and protocol overheads.

Model and optimization: LoRA adapts e5-base-v2 across all linear layers while a jointly trained linear hash head produces the codes.Learning rates and loss weights remain constant, with no warmup or learning-rate schedule.
Hard-negative mining: Hard negatives are mined by BM25 top-512 retrieval followed by MiniLM cross-encoder reranking, with m=3 negatives used per training step.Mining is cached by query and refreshed every 4 epochs, reducing cross-encoder forwards per epoch on long-tailed query distributions.
Evaluation configuration: Table 8 evaluates ciphertext-only Hamming-neighborhood inference at deployed radius using five-seed P@10 and corpus coverage, while Table 9 measures hidden-padding dose response under a 20k-query stress.Table 10 reports per-query PIR Fetch overhead at four deployed L=128 operating points with k=10.
Code discretization: The hash head anneals tanh(β·logit) from β=1 to 6, then emits sign(logit) codes at inference.Annealing keeps gradients useful early and concentrates outputs near ±1 late in training, reducing the soft-to-hard gap.

D.3 Regularizers

Spruce removes conventional deep-hashing regularizers and relies on its listwise margin and teacher anchor, arguing that the active objective already produces balanced, near-saturated codes. The section also motivates LoRA, a linear head, 128-bit codes, and strong hard-negative mining as complementary design choices.

Conventional objectives: Classic deep-hashing objectives target compact codes, bit balance, bit independence, and low quantization error.These regularizers shape relaxed outputs toward informative binary codes with low rounding error.
Conventional objectives: Quantization regularization drives soft values toward confident ±1, reducing the gap between training-time relaxed codes and inference-time hard codes.The literature implements this through penalties or related priors and margin-based formulations.
Conventional objectives: Bit-balance penalties prevent constant bits, while independence penalties suppress correlations so multiple bits do not encode the same direction.Both constraints can also be enforced structurally through balanced layers or orthogonal target codes.
Design rationale: Combining these regularizers introduces loss weights and hyperparameters, and can make optimization prone to poor local minima.This cost motivates single-loss designs that incorporate balance and quantization into ranking-style objectives.
Spruce objective: Spruce sets λq=λbal=λind=0 and relies on the listwise margin plus teacher anchor because the active objective empirically reaches the targeted code regime.A mid-training diagnostic reports per-bit entropy ≈0.99 and mean absolute bit activation ≈0.07.
Related design choices: LoRA preserves the pretrained embedding geometry while adding specialization, whereas full fine-tuning harms zero-shot transfer and freezing limits reshaping for Hamming retrieval.The same design sweep selects a linear hash head, L=128, and cross-encoder-enhanced hard-negative mining.