Spruce Cuts Private RAG Retrieval From 90 GB Per Query to Practical by Searching Binary Codes Instead of Embeddings

arXiv 2609.03376·medium signalXBlueskyLinkedInCopy link

arXiv 2609.03376 addresses organizations outsourcing vector indexes to untrusted clouds, where each query touches corpus-scale state so a naive secure implementation costs minutes and roughly 90 GB of communication per query at million-document scale, and even recent optimized systems need 10-22 seconds. Spruce co-designs representation with protocol, learning compact binary codes that preserve candidates for full-precision reranking so corpus-wide embedding scoring becomes Hamming-distance computation under two-server MPC, with a corpus-calibrated fixed-radius protocol that avoids multi-round candidate selection. Across four corpora of 383K to 5.42M documents it preserves original search quality, and a one-core owner-operated dealer removes the cloud OT preprocessing bottleneck.