Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings
cs.CR · cs.IR · cs.LG
Quick verdict
Spruce cuts private RAG retrieval to 0.2–3 s per query via 128-bit hashes under two-server MPC; strong results, but NDCG-retention and leakage caveats remain.
Summary
Spruce targets private dense retrieval for RAG when a document corpus is outsourced to two non-colluding, semi-honest cloud servers. The core idea is co-design: a LoRA-adapted e5-base-v2 encoder learns 128-bit binary codes whose Hamming distances are computed under Boolean MPC (free XORs plus a Wallace-tree popcount, roughly L AND gates per document), replacing corpus-wide int8 cosine scoring that costs N·D secure multiplications (~88 GB and ~9.4 minutes per million-document query). Candidate selection uses a corpus-calibrated fixed radius (one comparison, one reveal) instead of interactive binary search. Optional private cluster pruning (padded Hamming buckets fetched by PIR) and an owner-operated seeded dealer for Beaver triples further cut compute and preprocessing bottlenecks. On four BEIR corpora (382K–5.42M documents), full scans take 0.21–2.97 s at 10 Gbps — 4.8–6.7× faster than the closest measured baseline — retaining 95.2–97.8% of full-float NDCG@10 with median candidate sets of 382–1,952; pruning reaches 0.06–1.09 s (13.1–22.9×) at 93.9–97.3% retention, and pruning plus dealer raises sustained throughput 31.5× at 1 Gbps. The paper includes an adaptive simulation proof with explicit leakage and a ciphertext-only attack showing weak but measurable signal. Limitations: hash-only quality regresses on NQ, top-10 recall drops to 0.672 on Climate-FEVER despite high NDCG retention, radius calibration needs labeled in-distribution queries, and no code release is stated in the provided text.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Replacing corpus-wide secure int8-cosine scoring with 128-bit Hamming filtering under two-server MPC cuts candidate generation by roughly three orders of magnitude (1,173× latency, ~1,022× communication on Webis-Touché, §5.3/Table 4).
- A corpus-calibrated fixed radius (one comparison plus one reveal) is 2.9–3.0× faster than interactive binary-search radius selection while preserving calibrated final NDCG (§5.3).
- Spruce retains 95.2–97.8% of full-corpus float NDCG@10 on four BEIR corpora (382K–5.42M documents) with median candidate sets of only 382–1,952 (Table 3).
- Full scans take 0.21–2.97 s at 10 Gbps (4.8–6.7× vs the closest measured prior system); private pruning reaches 0.06–1.09 s (13.1–22.9×), and pruning plus the seeded dealer lifts sustained throughput 31.5× at 1 Gbps (Tables 5–6).
- The protocol carries an adaptive multi-query simulation proof against one semi-honest corrupted server with explicit leakage functions, and its revealed candidate sets leak only a weak ciphertext-only neighborhood signal (held-out P@10 0.017–0.070, §B.3).
Strengths
Clean, checkable gate-cost co-design
§3.3.1–3.3.2 and Table 1: Hamming under 2PC costs ~L ANDs/document (L=128) vs N·D int8 multiplications; at N=10^6 this is 1.3×10^8 ANDs / 86.0 MB / 0.482 s versus 7.7×10^8 multiplications / 87,863 MB / 562.1 s — the speedup mechanism is itemized, not asserted.
Baselines were actually run, with failures reported
Table 5 measures RemoteRAG, p2RAG, PANTHER, and Pisces on the same host with the same E5-base-v2 embeddings; PANTHER's OOM at 1M documents (256 GB PIR state) and Pisces's 300-s timeouts on DBpedia/Climate-FEVER are disclosed rather than hidden, and Pisces was patched to complete on Webis-Touché (23.747 s).
Unusually transparent leakage self-assessment
Evidence-backed simplification of hash training
Multi-seed variance reporting for calibration
Weaknesses
Hash-quality claim is dataset-dependent
NDCG retention masks top-10 recall loss
Fixed radius requires labeled in-distribution queries
Partial baseline coverage and extrapolation
Residual leakage and trust assumptions
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
Spruce (arXiv 2609.03376) is a systems/security method paper on private outsourced dense retrieval for RAG. Setting: a data owner secret-shares a document index across two non-colluding, semi-honest servers; a trusted client runs the query encoder locally. The paper advances three claims: (1) co-designing a learned 128-bit binary code with Boolean MPC makes corpus-scale filtering roughly three orders of magnitude cheaper than secure int8-cosine scoring — Table 1 shows N=10^6 costing 86.0 MB and 0.482 s for the hash versus 87,863 MB and 562.1 s for DFP; (2) an offline-calibrated fixed radius replaces interactive binary search (§5.3: BS is 2.9–3.0× slower and moves 1.4× more data, 531 versus 27 MPC rounds on Webis-Touché); (3) optional private cluster pruning and an owner-operated seeded dealer remove compute and triple-supply bottlenecks (Table 6: 185 → 5,826 queries/hour on Climate-FEVER at 1 Gbps, the claimed 31.5×). Evidence spans four BEIR corpora (382K–5.42M documents), an adaptive multi-query simulation proof (Theorem B.4), and a self-administered leakage attack.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What problem does the Spruce paper solve?
Organizations that outsource RAG vector indexes to a cloud expose both their proprietary corpus and their users' queries (embeddings can be inverted back to text). Spruce lets two non-colluding, semi-honest servers run dense retrieval so that neither sees the corpus or queries in the clear, at roughly 0.2–3 seconds per query for corpora up to 5.42 million documents instead of the minutes that naive secure scoring would take.
How much search quality does Spruce lose compared to normal dense retrieval?
After the client reranks a small candidate set (median 382–1,952 documents), Spruce retains 95.2–97.8% of full-corpus float NDCG@10 on four BEIR corpora; the optional private-pruning mode keeps 93.9–97.3% while running 13.1–22.9× faster. Note that the candidate set can miss part of the float top-10 (Rfloat@10 as low as 0.672 on Climate-FEVER at 128 bits) even when final NDCG is nearly unchanged.
How does Spruce achieve its speedup over prior private RAG retrieval systems?
It replaces secure cosine scoring over 768-dimensional embeddings (N·D multiplications, ~88 GB communication per million-document query) with Hamming distance over learned 128-bit binary codes under two-server MPC — XOR operations are free and only an L-bit popcount consumes expensive AND gates — plus an offline-calibrated fixed radius that reduces candidate selection to one comparison and one reveal, and optional cluster pruning that shrinks the scanned portion to about 20% of the corpus.
Is Spruce's code publicly available?
The provided paper excerpt contains no code or artifact release statement (one may exist in sections not included in the excerpt). The evaluation stack is public — MP-SPDZ, the e5-base-v2 encoder, LoRA, and BEIR corpora — so independent reimplementation is feasible, but reproducing the exact 10-Gbps two-server latencies requires a matching network testbed.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided text is a sampled excerpt with [...sampling gap...] markers: parts of §3.1, §4, portions of §5.1–5.2 narrative, part of related work, and Appendices A and C were skipped, so this review deliberately makes no claims about their contents.
- No code/artifact availability statement appears in the provided excerpt; such a statement may exist in skipped sections, so codeAvailable=false reflects only what is visible.
- The excerpt's abstract is cut mid-sentence, but every headline figure quoted here (0.21–2.97 s, 4.8–6.7×, 13.1–22.9×, 31.5×, 382–1,952 candidates, 95.2–97.8% retention) appears verbatim in §1 and the result tables, so all cited numbers were verified from body text.
- Table 8's per-corpus attack numbers are visible only as prose ranges in §B.3 (0.017–0.070 held-out; 0.099–0.280 stress at L=128); the table body itself fell in a skipped region, so per-corpus cells are not quoted.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.