Private vector search stops scaling with database size: HNSecW brings online ANN queries to logarithmic time while holding recall at billion scale

Approximate nearest neighbor search can now be completed with online cost growing logarithmically in database size, rather than linearly, while the query and the database remain secret from each other. The closest prior MPC schemes, SANNS and PANTHER, follow a cluster-based route that partitions the database into clusters and searches the relevant ones, so online communication scales linearly with database size, and under MPC every extra vector access carries heavy communication. On benchmarks including SIFT-1M, GIST-1M, DEEP-100M and BIGANN-1B, HNSecW achieves up to orders-of-magnitude lower end-to-end latency than PANTHER in the 2PC wide-area setting and reduces communication by up to orders of magnitude.

The search is reshaped into an execution flow that does not depend on private inputs: each layer runs a fixed number of steps, and the candidate, result and visited sets become fixed-size arrays updated by fixed rules. In plain HNSW the stopping condition, set sizes and accessed addresses all vary with the query and the data, which would leak information inside MPC; the generic fix is distributed ORAM, but each access then costs work tied to database size. The protocol reshuffles graph and vector tables offline and gives each layer its own independently reshuffled vector table so no physical address is accessed twice; evaluation covers ten benchmark datasets from millions to billions of vectors and dimensions from tens to over a thousand.

Multiple and batch queries each get an extension: sequential queries reuse nodes and vectors already fetched through cross-query caches, while the batch protocol shares fetched vectors across all queries and advances them in parallel. Running the single-query protocol repeatedly would require reshuffling the tables after every query, an online latency that is impractical; the sequential multi-query protocol has amortized logarithmic cost, and the batch protocol lowers the critical path further to logarithmic. Sweeping query count on a wide-area network, amortized latency falls as queries grow and approaches the online floor, and HNSecW drops below PANTHER once the offline cost is amortized, with the same trend on all four datasets.

Evaluation covers ten datasets from millions to billions of vectors, including SIFT-1M, GIST-1M, DEEP-100M and BIGANN-1B, with dimensions from tens to over a thousand, using semi-honest 2PC in ABY and 3PC in MP-SPDZ under both LAN and WAN conditions. The index is built locally by the database owner before queries arrive, and the protocol targets the symmetric-privacy setting where both query and database stay hidden.

The fixed step bound comes from empirical calibration of HNSW termination behavior rather than a worst-case guarantee, and the best-known asymptotic bound for HNSW on arbitrary data remains linear. The batch protocol's critical-path analysis relies on proofs in the extended version. Secure index construction and dynamic graph updates are not yet part of the protocol and are listed as future work.